Byzantine-Resilient Federated Alternating Gradient Descent and Minimization for Partly-Decoupled Low Rank Matrix Learning
Authors: Ankit Pratap Singh
Ahmed Ali Abbasi
Namrata Vaswani
Venue: ICML 2025 poster (2025)
Keywords: Byzantine robustness
Low Rank Matrix Recovery
Multi-Task Representation Learning
Primary area: social_aspects->security

Abstract: This work has two contributions. First, we introduce a provably secure (Byzantine-resilient) sample- and communication-efficient alternating gradient descent (GD) and minimization based algorithms for solving the federated low rank matrix completion (LRMC) problem. This involves learning a low rank (LR) matrix from a small subset of its entries. Second, we extend our ideas to show how a special case of our algorithms also solves another partly-decoupled vertically federated LR matrix learning problem, that is  LR column-wise sensing (LRCS), also referred to as multi-task linear representation learning in the literature. Finally, we also show how our results can be extended for the LR phase retrieval problem.  In all problems, we consider column-wise or vertical federation, i.e. each node observes a small subset of entries of a disjoint column sub-matrix of the entire LR matrix. For the LRMC problem, horizontal federation is equivalent since it is symmetric across rows and columns; while for the other two it is not. In all problems, the data at  different nodes is heterogeneous (not identically distributed), making it harder to obtain provable guarantees.

Fyzantine-Resilievn Federated Alternating Gradient Descent and Minimization for Partly-Decoupled Low Rank Matrix Learning
Ankit Pratap Singh' Ahmed Ali Abbasi
Namrata Vaswani
Abstract
tions in many different modern ML and medical imaging domains recommender system design (Koren, Bell, & Volinsky, 2009), multi-task representation learning for few shot learning (Collins, Hassani, Mokhtari, & Shakkottai, 2021; Shome & Kar, 2021), federated sketching (Srinivasa, Lee, Junge, & Romberg, 2019; Anaraki & Hughes, 2014; Azizyan, Krishnamurthy, & Singh, 2014), accelerated dy- namic MRI (Babu, Lingala, & Vaswani, 2023; Haldar & Liang, 2010; Lingala, Hu, DiBella, & Jacob, 2011; Yao, Xu, Huang, & Huang, 2018) and Fourier ptychography (Jagatap, Chen, Nayer, Hegde, & Vaswani, 2019). All these problems can be expressed as: learn an n x rank r ma- trix X from measurements of the form y/s := Agæ or | & [q] with the matrix As defined differently. For LRMC it is a 0-1 very sparse matrix, while for LRCS and LRPR it is random Gaussian matrix. These problems can be federated horizontally or vertically. For LRMC, both settings are analogous (due to row-column symmetry) and both involves learning from data that is not identically distributed at the different nodes. This so-called hetero- geneous data setting is known be more difficult to de- sign secure
This work has two contributions. First, we intro- duce novel provably Byzantine-resilient sample- and communication--fficcee alternating gradient descent (GD) and minimization based algorithms for solving the federated low rank matrix com- pletion (LRMC) problem. This involves learn ing a low rank (LR) matrix from a small sub- set of its entries. Second, we extend our ideas to show how a simple modification of our al- gorithms also provably solves two other partly- decoupled vertically federated LR matrix learn- ing problem.- - LR column- -wise sensing (LRCS), also referred to as multi-task linear representa- tion learning, and its phaseless generalization, LR phase retrieval (LRPR). In all problems, we consider column-wist or vertical federation, i.c. each node observes small subset of entries of a disjoint column sub-matrix of the entire LR ma- trix.
algorithms for. For LRCS and LRPR, the horizontal setting is the easier homogeneous data setting, while the vertical one involves heterogeneous data. We consider the vertical one in this work. This is also the practically relevant one.
1. Introduction
Modern machine learning (ML) systems are vulnerable to various kinds of failures. One natural and powerful attack class is that of Byzantine attacks (Guerraoui, Rouault, et al., 2018) This means that the adversarial nodes have com- plete knowledge of the data every node and of the exact algorithm (and all its parameters) implemented by every node, including center; and all the adversarial nodes can collude to use this information to design the worst pos- sible attacks. In this work we develop, and analyze, se- cure (Byzantine resilient) algorithms for solving three dif- ferent federated low rank matrix learning problems that share certain common features Low rank matrix com- pletion (LRMC), LR column- sensing (LRCS), and LR phase retrieval (LRPR). These find important applica-
Centralized LRMC problem has been extensively studied. Solutions consist of convex relax- ation (Candes & Recht, 2008), which was very slow, Al- ternating Minimization (AltMin) with spectral initializa- tion (Netrapalli, Jain, & Sanghavi, 2013), and gradient descent (GD) based algorithms Projected GD (ProjGD) (Cherapanamjeri. Gupta, & Jain, 2017: Jain & Netrapalli, 2015) and Factorized GD (FactGD) (Yi, Park, Chen, & Caramanis, 2016; Zheng & Lafferty, 2016). AltMin al- gorithms for LRPR and LRCS have been introduced and studied theoretically in the last six years (Nayer. Narayana- murthy. & Vaswani, 2019; Nayer & Vaswani, 2021). The works of (Nayer & Vaswani, 2023, on arXiv since Feb. 2021; Collins et al., 2021; Thekumparampil, Jain, Ne- trapalli, & Oh, 2021; Vaswani, 2024) introduced much faster and novel GD-based algorithm called alternating GD and minimization (AltGmmin). This algorithm is also
Related Work.
'Department of Electrical and Computer Engineering, Iowa State University, Ames IA, USA. Correspondence to: Ankit Pratap Singh Saannki@@astat..cdi
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Byzantine- Resillent Federated Alternating Gradient Deseent and Minimization for LR matrix learning
communication-effiiennn for federated LRCS or LRPR. In recent work (Abbasi & Vaswani, 2024; Abbasi, Moothe- dath, & Vaswani, 2023), AltGDmin based solution was introduced and analyzed for solving the federated LRMC problem. This was as fast as AltMin or FactGD, while be- ing the most communication--ffciinn
al., 2022; Dadras, Stich, & Yurtsever, 2024).
Contributions and Novelty. This work has two contribu- tions. (1) Our main contribution is novel provably secure algorithms,
and communication--ffieee and GM-AltGDmin, for solving the federated LRMC prob- lem. Krum is an easy to compute estimator but needs order Lr 2 time to compute. GM can only be approximated, and the only algorithm for it that comes with a useful guaran- tee is way too complicated to implement (even the algo- rithm authors have not implemented it). But the guarantee is near-linear- time, order nrL times log factors. We also explain why use of coordinate-wise median is not useful in this setting: its required sample complexity is very high. This comparison is summarized in Table 1. (2) Second, we explain how both our novel algorithm and our proof approach can be extended directly to also solve two other federated LR problems - LRCS and LRPR. All three prob- lems involve solving a partly decoupled optimization prob- lem and all three also involve dealing with heterogeneity across nodes. We use the term "partly decoupled" to re- fer to optimization problems in which the unknown can be split into two subsets, and the optimization with respect to at least one subset of variables, keeping the other fixed, is decoupled. Heterogeneity means that the data at the differ- ent federated nodes is not identically distributed.
erzaantnne-rsillinn federated learning algorithms,, primar- ily (stochastic) GD and modifications, have been devel- oped and studied extensively recently. Typical solutions involve replacing the mean/sum of the gradients from the different nodes by a different robust statistic, such as ge- ometric median (GM) or GM of means (Chen, Su, & Xu, 2017), coordinate-wei wise median or trimmed mean (Yin, Chen, Kannan, & Bartlett, 2018), or Krum (Blanchard, EI Mhamdi, Guerraoui, & Stainer, 2017). One of the first non-asymptotic results for Byzantine attacks is (Chen et al., 2017). This studied GD and used the geometric median (GM) of means to replace the regular mean/sum of the par- tial gradients from each node. Under standard assumptions - -trong convexity, Lipschitz gradients, sub-exponentiall -ity of sample gradients, and an upper bound on the fraction of Byzantine nodes- it provided an exponentially decaying bound on the distance between the estimate at the (-th it- eration and the unique global minimizer. In (Yin et al., 2018), the authors developed non-asymptotic guarantees for coordinate-wise median and the trimmed-mean estima- tors based GD for both convex and non-convex problems, albeit under very strong assumptions this work needed bounds on variance and skewness along each dimension, and also needed smoothness and convexity along each di- mension. Other work is (Alistarh, Allen-Zhu, & Li, 2018; Allen-Zhu, Ebrahimian, Li, & Alistarh, 2020). All the above works assumed homogeneous data distributions
The work most closely related to ours is (Singh & Vaswani, 2024b), however this deals with a much easier setting of horizontally federated LRCS. In this case, the data, and hence node gradients, are homogeneous, making it easier to study. Also, LRCS only requires incoherence of right singular vectors of the true unknown matrix, and of each algorithm estimate. Since the columns of B (the right fac- tor of X = U), are updated locally at the nodes, the analysis of this step does not require any changes for the secure algorithm. Thirdly, it only provides guarantees for GM, which cannot be computed exactly and theory and practical algorithms for it are different. On the other hand, (1) Incoherence of U: LRMC also requires assuming in- coherence of U* and ensuring it for each U at each al- gorithm iteration. This is tricky because update of U re- quires interaction between nodes and the GM or Krum out- put may not be incoherent. For this, we have to introduce novel filtering step to eliminate the non-incoherent gradi- ents. (2) Heterogeneous gradients: it well known in the secure federated optimization literature that heterogeneity makes it more difficult to design secure algorithms: if the data at different nodes is very different, it is impossible to distinguish a Byzantine node output from an honest node output. Clearly, one can only handle a bounded amount of heterogeneity. All past work for this setting assumes a bound on the difference between gradients from different good nodes, at each algorithm iteration (Data & Diggavi, 2023, Assumption 2), (Allouah et al., 2023, Assumption
More recent work has explored the more difficult heteroge- neous data distribution setting by either assuming bound on the amount of heterogeneity (Pillutla, Kakade, & Har- chaoui, 2019; Data & Diggavi, 2021; Li, Xu, Chen, Gian- nakis, & Ling, 2019; Ghosh, Hong, Yin, & Ramchandran, 2019; Allouah et al., 2023), or by assuming the existing of a trusted dataset at the center (root dataset) and using detection methods to remove bad nodes (Regatti, Chen, & Gupta, 2022; Lu, Li, Chen, & Ma, 2022; Cao, Fang, Liu, & Gong, 2020; Cao & Lai, 2019; Xie, Koyejo, & Gupta, 2019). Recently (Singh & Vaswani, 2024a, 2024b) studied Byzantine-resiliency of LRCS using GM in the easier hor- izontally federated setting. But the ideas presented in these works cannot be extended for LRMC or vertically federated LRCS/MTRL which we explain next. (He, Ling, & Chen, 2019) presents experimental results for Byzintine-resilient LRMC, but with no theoretical guarantees. Other related works include (Alistarh et al., 2018: Cao al., 2020; Allen-Zhr et al., 2020; Wu, Ling, Chen, & Giannakis, 2020; Defazio, Bach, & Lacoste-Julien, 2014; Acharya et
2

---

Krum ZKr Frrantine-Resileen Federated Alternating Gradient Deseent and Minimization for LR matrix learning
D). This is confusing assumption on intermediate algo- rithm outputs and it is not clear how to satisfy it. The son it is needed is the past works consider a large class of optimization problems. Our work only solves three LR problems and hence a bound on the difference between the column sub- matrimet of X at different nodes suffices. (3) Guarantees for Krum: Our work provides guarantees for both Krum and GM. In fact, our result may be the first non- asymptotic guarantee for using the Krum estimator, which is simple, intuitive, and easy to compute estimator, in- troduced in (Blanchard et al., 2017). By proving a result for Krum that is analogous to that for GM, we show how we can use it to replace GM. We obtain this result by care- fully borrowing and modifying an argument embedded in the asymptotic proof given (Blanchard et al., 2017). This may be of independent interest.
X U.B". We state guarantees in terms of i where min = minse(1] mmin mmin (Xz), and max [L max (x)). Our guarantees actually only depend the maximum and minimum singular values over the set of good nodes (and not all nodes). We reuse the letters c, C to denote different numerical constants in each use with the convention that e < 1 and C' 2 1.
min
Definition 2.1 (Krum). For a set of matrices { 1Z Zz ..... Z their Krum and the corresponding best index Kr are defined as follows
Kr argmin <E(L)
Σ 88'
1 - -Zell/
where the sum
Σ
runs over the (T. T-yz 22) matrices
2. Secure Federated LRMC
Ze which are closest Ze in Frobenius norm.
Problem Setting. LRMC involves recovering a rank-r matrix X E R where r < min(n, q). from a subset of its entries. Entry j of column k. denoted aje- is ob- served, independently of all other observations, with prob- ability p. Let Ejı= lid Bernoulli(p) for E [m), k [g]. For each k E [g]. define diagonal 1-0 matrix A& E H as
Assumptions. We need three standard assumptions. The first is incoherence of the left and right singular vectors of each X7. This is needed in all works that study LRMC so- lutions. The second is bound on the fraction of Byzantine nodes, which is also always needed. For notational sim- plicity, we assume this to be at most 40%. But any bound that satisfies Loys < 2 (Blanchard et al., 2017) can be assumed. Lastly, we need a bound on the amount of het- erogeneity, this is also needed in all past work that deals with heterogeneous data and does not assume existence of trustworthy root dataset.
A == dSag(Est:: j E [m1)
Then, we can write yv: A k E [q] and the data ma- trix Y = [yn, y2....... yn] is of the same size as X but with unobserved entries zeroed out.
Assumption 1. Assume that Lays < 0.4. L
For federated LRMC, we assume that there are a total of L nodes out of which at most Loys can be Byzantine. Let Sg,l E [L] be a partition of [q] := {1.2..... 3 such that |8 2 9/ L > r for all f. Node l observes subset of entries of X; := [zt, k E St), i.e., it has access to yı: A. We assume that each X has rank and can be expressed as Xi = U*B B, where U is an n X r. The goal is to recover U and B; for each l E [L], and thus recover x== [X x,....,Xi] Xi.).
Assumption 2. Assume row norm bounds on U*:
maxje[ni || S HV//n, and assume that right singu- lar vectors' incoherence holds locally for each node, i.e., maxkes: ||b]]| S / (X;) for a constant μ 2 1. Assumption (Bounded heterogeneity).
B - B S G.o E
max
We bound Gn in our guarantee. This assumption in turn implies that, for all e, E {44)
Notation.
We use ||||| to denote the Frobenius norm and ||-II without a subscript denote the (induced) la norm; T denotes matrix vector transpose. We use eū to denote the k-th canonical basis vector (k-thh column of identity matrix D); and M = (M M)-1M orthonormal columns U1. U2 we use SDp(U1, U2) := II(I- U !2 l as the Subspace Distance (SD) mea- sure between the column spans of the two matrices. For any matrix M- (m.,.... my). we denote its sub-matrix with ; = S = 4 columns corresponding to indices in St by M, Thus, M =
| - = -U Groma max
x
For tall matrices with
2.1. Krum-AltGDmin
The complete stepwise algorithm is provided in Algorithm 1. We explain its steps below, starting with first reviewing the basic altGDmin idea. Guarantee is provided after that.
Basic AltGDmin. We first explain the basic AltGDmin idea. This imposes the LR constraint by expressing the unknown matrix X as X = UB where U is an n X r matrix and B is an r x q matrix. The goal is to min- imize f(U B) := El= ll - A,bbbl with U be- ing a matrix with orthonormal columns. After a careful
.M,..,,,, Mr..
Let X syp V == U"B", where U* E Raxr and has orthonormal columns and V E Rrxq with or- thonormal rows. Also, we let B" = V* so that
3

---

Byzantine- Resillent Federated Alternating Gradient Deseent and Minimization for LR matrix learning
Methods->
Krum (Blanchard et al., 2017)
GM
CWMed
(Chen al., 2017)
(Yin et al., 2018)
Sample Comp for Byz-AltGDmin
> log log(
Pgoo @ (og(
r n @log or log(
(lower bound on nipp)
Communic Cost
nr log( +
log( +
ny log(=)
Approximate Algorithm
No
Yes
No
Compute Cost at Center- GD
nr L' log(
nr" L log' Cayprus log(.) :)
nr" L log (L) log(.) [Fd]
Compute Cost at Node - GD
max(n, H8
L log()
max(n, [F]]
1 )rr log(;)
max(n,
I )r² log(?)
Q set of observed entries, [[]]] npg
Table I: We compare Krum, Geometric Median (GM), and Coordinate wise median (CWMed) based modification of AltGDmin. Observe that Compute cost for CWMed is smallest but its sample complexity unreasonably high making it useless. Krum and GM have same sample complexity. GM compute cost is slightly less than Krum but it is an approximate algorithm i.c., can compute GM with Copprox error.
Algorithm Byz-AlGDmin-LLRN
spectral initialization for U, at each iteration, alterna- tively updates B and U as follows: (1) Minimization for B: keeping U fixed, update B by solving ming f(U,
AltGDmin Initialization:
2: Nodes f 1..., L
3: Uoo < top r left left-singular vectors of Y,
Clearly, this minimization decouples across columns, mak- ing it cheap least squares problem of recovering q dif- ferent r length vectors. It is solved as bN + (A,U)* y for each l E [q]- (2) GD for U: keeping B fixed, up- date U by a GD step, followed by orthonormalizing its columns: U+ + QR(U (U,
4: Compute Il (Uoo): if row of Uoo has 2-norm more than /v/r/n, then re-normalize the row entries so that its norm equal the this value, else do nothing.
5: Up 4 (Uo)).
6: Push Une + (QR(TT((uoo)) to center
Due to the decoupling in the minimization step, its time complexity only as much as that of computing one gradient w.r.t. U. In federated setting, AltGDmin is also communication- efficient because each node needs to only send nr scalars (gradient w.r.t U) at each iteration. The updating of bys is done locally at the node where its data is available. The ini- tialization is computed as given in line and the two lines below it in Algorithm 1. The algorithm implementation uses special features of the LRMC problem to speed up all computations. e.g., A&U is computed by just sub- sub-selecting the rows corresponding to the nonzero diagonal entries of Ag. Sample-splitting is assumed to prove the guarantees.
7: Central Server
8: Define set To = 0
9: for l = to L do
10: if || < /. for all j E [n] then
11: Add e to set To
12: end for
13: Compute PUn + UOrUTT é Io
14: KKrPuKke = Krum (rrum(Puse leeZ,
15: Push Un UKr nodes.
16: AltGDmin Iterations:
17: for ( 1 to 7 do
18: Nodes f= 1,.... L
19: by + (A,,,~)) V Se
AltGDmin-Krum The resilient Krum based modifica- tion proceeds as follows.
20: V. 2' SNES. (A bb )
each iteration, node first updates b&s for l E Se locally using the yıs. This step the same in the basic case. It can also be analyzed sim- ilarly using (Abbasi & Vaswani, 2024, Lemma 4.2, 4.3). Next, it computes the partial gradient, denoted Ve as given in Algorithm 1, line 20. This is sent to the center.
21:
Central Server
22:
Define set I, O
23:
for l 1 to L do
24:
Compute Utemp <- U1-1 V/ if ||u/empl S (1 0.4
25:
R² )|{ /.4 for all
j jE [n] then
The center does not know which received Ve, if any, is Byzantine. To deal with this, it processes them in two steps. First, finds the index set of és for which Ve such that the updated U would be sufficiently incoherent (as needed by our proof). This filtered set is computed as I I: {E maxje(=) IIU - 1 || < (1 (1-0.4/x²) ) + 1. 1r4m//r/n) See line 25. Next, we compute Krum of the set of gradients V., l I. The filtering needed because LRMC algorithms need to ensure incoherence of the up- dated U at each iteration. While the gradients computed
26:
Add l to It
27:
end for
28:
VK. = Krum Krum{Veleet, VeleeT,
29:
Compute U, + QU( kr))
30:
Push U, to nodes.
end for
32:
Output UT.
4

---

Srrantine-Resileenn Federated Alternating Gradient Deseent and Minimization for LR matrix learning
by the good (honest) nodes will satisfy this w.h.p. (can be proved), this cannot be guaranteed for Byzantine outputs.
Algorithm 2 By--AliGDmin-LMMCC-GG
Consider Algorithm with the following changes:
Subspace-Krum for initialization. The initialization at the nodes is done exactly as in the basic AltGDmin al- gorithm (Abbasi & Vaswani, 2024). This involves com- puting the top r singular vectors of Y: projecting the re- sulting matrix Uno onto space of row incoherent matrices, i.c., computing (U0o)) = min | Voo where U == (Ü : || || S PVr/n):: and finally computing a QR decomposition of (U00)) See line 6. This is com- puted as given in line 4. The projection needs time nr while the QR step needs time nr?. The nodes send their Uoz to the center. The center processes these in two steps. The first step is again filtering step that selects only those Uoes which are incoherent. See line 10. The second step involves computing the Subspace-Krus Krum. This is done as follows. Observe that the received Uoes are subspace es- timates. Their actual entries can be quite different. Thus we cannot use Krum on them to get a meaningful aggre- gate. We need a different approach that applies Krum to subspace distances. To do this, we rely on the fact that, for subspace basis matrices U1, U2, || 22U2 || is another measure of subspace distance.
Replace Line 14 by [Chests Pusson Ji Ebest
argmingez, [[GM HeeI - -PuellF
Replace Line 28 by Viscni Chest
argmingez, [[GM[Veeee, - VellF
guarantee holds only with constant probability (the approx- imate GM algorithm works only with this much probability. The entire algorithm would be the same as Algorithm I ex- cept for one change. After the GM step, in both initializa- tion and GD iterations, we need to find the gradient that is closest to the GM and use that as the output. This needed because the GM is not one of the entries being aggregated. So then there is no way to prove that (U - v)aa will satisfy the required incoherence. The proof technique of Theorem 2.2 also extends to GM.
Corollary 2.3. (GM-alGDDmin-LRMC) Consider Algo- rithm 2. Assume everything in Theorem 2.2. Its conclu- sion holds with probability at least 1 - (L + 1)n
CapprouGM - Ck2 log(lll//// (og(1/e)(Lnn - CapprorGM)
3. Proof Outline for Theorem 2.2
We can prove the fol- lowing for Algorithm 1. Under the three simple assump- tions stated earlier, and if Gg is small enough, then, as long as we observe roughly order nr² log [log (1g(1/c) matrix en- tries at each node, w.h.p.. the subspace distance between U and U., and hence error between X; U By and X, = U, decreases exponentially with iteration t un- til either the desired error level E is reached or the hetero- geneity bound Gg is reached. Convergence up to the het- erogeneity bound is also what the other SGD works show (Pillutla et al., 2019; Data & Diggavi, 2021; Li et al., 2019; Ghosh et al., 2019; Allouah et al., 2023).
Guarantee for Krum-AltGDmin.
The theorem statement is subset of the following main claim. Let 6; D U*) and Maa = 88 Let Ioood denote the set of good (honest) nodes and let E be any one good node, i.e., any one entry of Tgood-
Claim 3.1. w.p. least 1 -3Lp3 U(Lp2 + 2Lp1)
0.65mpo +2
(i) 8e S (1
max y:50
R²
+2 + npo
max
C8.6GB
Σ
0. 0.65mpa
max y
+2
722
==
Theorem 2.2. (Krum-altGiDminn-LARa)
Consider Algo- Let T
(i) | S (1 03 | 2/////n Σ E6
03)"
rithm/ 1 with Krum, and cample-splitring CR2 log(1/e), and step-size 1) S 0.5/ 0.5/po po max Assume thut Assumption 1, 2, 3 holds and GB S a If
(iii) d S do. and (iv) Tgood S I. Here P
R
exp(log C max p p. a p + exp(logg C Cpptp
pn ), and ps = n- 10 P2 = exp(log C2pp
nap= 2 CR p 2
2 log γ (og()/)),
3.1. Proving Claim 3.1
This claim is proved using an induction argument and the following five lemmas. Lemma 3.2 proves the base case, while the others are used to prove the induction step. Claim (iv) follows using Lemma 3.4. Once have Tgood C I, Lemma 3.6, 3.7 holds. Claim (ii) follows by construction (see Fact 3.5) and Lemma 3.7. Claim (i) follows by sub- stituting the bounds on Err Lemma 3.6, and denomina- tor term Lemma 3.7 in algebra Lemma 3.3. Since doing QR step results in a denominator term amin Tnin(U----oVa Vo) Lemma 3.7. To obtain a bound on this term Claim (tii) is re- quired which is a consequence of Claim (i) and GB S C. Full proof is in Appendix A.
then w.p. at least 1 3Ln 10 CR2 log log(I/e)
SDr(U*, (U),)) S max
14C1
and| || - -x-1e S eat². Compute and communication cost are stated in Table 1.
2.2. GM-AIGDDmn
It is possible to obtain a different algorithm and guarantee with using GM to replace Krum. GM is theoretically, faster to compute than Krum, although its theoretical and practi- cal algorithms are not the same (as noted earlier). Also, its
5

---

Byzantine- Resilleen Federated Alternating Gradient Deseent and Minimization for LR matrix learning
Lemma 3.2 (Initializationn. Let Assumption 1, and 2 holds. Assume p p2 CR2 log log (/ (nog). Let ps 12 Then,
2. O mmx (Bz) (1 + m and F ( 2
V 1 F mm-x Thus, if di-1 S c/R², (Bi)
then mmiul ( 2 0.90 min and m (Bt) S 1.10 max
1. w.p. at least 1 - Lps J goood S To
2. w.p. at least 1 - 3lp3. SD (Uo. U*) S d0-
3. ||bı|| S L.10i//T//
3. wap. at least 1 - -.pps. Un is 1.5p now-incoherent, i.e.,
This is used in the proof of the lemmas needed for the Err bound. It is also used to prove the || || -X bound of the theorem.
||u/||| / T/ for all j E [ns]
Lemma 3.3 (Algebra Lemma). Let Err == Kr
(U,-1, B.,]]. For [Ut-1 Vgr QR U.R we
3.2. Proof of Initialization lemma
have
We need to first show that each good node returns an accu- rate enough estimate and one that is also incoherent. Item one of Lemma 3.2 follows using second part of (Abbasi & Vaswani, 2024, Lemma 4.1) that Uoe is 1.5p row- incoherent for all e E Igood and then using union bound over Tgood-
SD=(U",U) IT. Br, B, (D (U-I)) + nn Erril minn (UL-1 x))
Lemma 3.4 (Good nodes contained in filtered set), Sup- pose that Igood S I--1. Then, w.p. at least 1 1- Lpg. at iter- ation 1, Tgood C It. Here p2 exp(log cpm/p R 22 Fact 3.5 (Incoherence of Utmpp for any e Iz). Utemp U,-1 e, for any l E I, by construction (Line 25 of Algorithm 1) [ |I S (1 /24 || + 1.4
Next we need to analyze the proposed Subspace Krum ap- proach. This requires using the following Krum Lemma 3.9 which we modified from (Blanchard et al., 2017) to in- clude probabilistic argument.
Fact says any gradient with index in Ie gives incoherent Utemp. The set I, contains all of Jyood but also can con- tain some of the Byz gradients. Our construction of the filtered set Z₁ guarantees that all gradients in it give inco- herent Utemp. Thus the Krum gradient (which one of the gradients from I,) also gives incoherent Utemp-
Lemma 3.9 (Krum (Blanchard et al., 2017)), Let ze S R", for l E [L] and let zkr denote the vector selected by Krum operator Kr Krumfzz]ee For a 0.4, suppose that, for at least (1 - T) ze's
Pr[[ze- - ž|| S <||=||> 21 p
Lemma 3.6 (Bounding Err). Assume Tgond S Is and Assumption 1. 2, 3 holds. Let P1 exp(log
Then, w.p. at least 1 - -1 T)p
mmxx (=))))))=) + exp(log at least - -2Lp1.
.2 pm
c
). We have w.p.
zKr - = S 10c
| Kr Ellll S Opo (8ed,
(1)
Proof. Proof is in Appendix G
Lemma 3.7
(Bounding denominator). Con-
Subspace Krum is modified version of Krum for subspaces using the idea from (Singh & Vaswani, 2024c) that the Frobenius norm of the difference between two subspace projection matrices is within a constant factor of the sub- space distance between their respective subspaces. There- fore Krum is calculated for Pu = UUT where U is any subspace with the distance metric as ||Pu. -Pu, 11.. We next give Subspace Krum Lemma 3.10
sider the setting of Lemma 3.6.
If n satisfies
upooiiax ((.5 + C + C4.3GB)
1, then
w.p. at least
2Lp,, Omin 10.1--VVA
1 + upoti max ((5 + C16c)6; + C).6GB)
The algebra lemma and the denominator lemma follow us- ing ideas similar to those in (Abbasi & Vaswani, 2024). We show next how to prove the others.
Lemma 3.10 (Subspace-Krum). Consider Algorithm I Lines 13-15. For a < 0.4, suppose that, for at least (1-T) (L-r)LUG's.
Bounding error in B and showing its incoherence. We borrow this from (Abbasi & Vaswani, 2024). It does not change because Pys are updated locally at the nodes, and thus, we do not need to worry about Byzantine resilience.
Pr(SDr(U* U1) < 58)
Lemma 3.8 (Lemma 4.2, 4.3 (Abbasi & Vaswani, 2024)). For any node &. & Toood- Assume || S Mu vr/n. Then, w.p. at least exp(logq
then, w.p. at least 1 - 1-2L(1 T)p,
3p F
SDp(U", Uout) < 106.
1. | - GellF S 16i-1 and X - Xille S
Fact 3.11. For any l E Tg. By construction (Line 10 of Algorithm 1) [e S 1.5// for all j E [n].
20,-10max max
6

---

Byzantine-Reslleent Federated Alternating Gradient Deseent and Minimization for LR matrix Iearning
Item two of Lemma 3.2 follows using first part of Lemma 3.2, (Abhasi & Vaswani, 2024, Lemma 4.1), and Lemma 3.10. From (Abbasi & Vaswani, 2024, Lemma 4.1) we have SD U² I 8' = 6o/10 10 w.h.p. for all & E Tyood- From first part of Lemma 3.2 good S To w.h.p. implies using Lemma 3.10 SD, (UKr: U*) I 60 w.h.p.
get dense measurements of each column but not of the dif- ferent rows. Consequently, we only need right singular vec- tors' incoherence (instead of that of both). Also, because of the use of random Gaussian matrices, the measurements are now unbounded and we need different concentration inequalities to analyze these problems. However, in spite of these differences, we show how simple modifications of our algorithm provide very similar guarantees for both these problems as well. The following assumption replaces Assumption 2.
Lemma 3.2 item three follows from Fact 3.11 as Kr E To- 3.3. Proof of Lemmas 3.4 and 3.6
First we prove Lemma 3.4. This lemma follows using mod- ified version of second part of (Abbasi & Vaswani, 2024, Lemma 4.6), where for Utemp = - V/ we have || S (1 - 0.4/R2][lue[]] + 1.44//r/
Assumption (right singular vectors' incoherence).
maxkes; |[b|]| - HVTT/00mx((X for a constant μ 2 1.
vr/n r for all j E [n] w.h.p. and then using union bound over Iood we have the required proof.
|
Consider Algorithm with the following changes: (1) the node initialization step replaced by the LRCS initialization from (Vaswani, 2024); and (2) remove the filtering step from both initialization and GD.
Once we have Igood S It then Lemma 3.6 is a direct consequence of Lemma 3.9, and 3.12 which we give next.
Theorem 4.1. (Krun-AllGDmin for LRCS) Consider the algorithm as described above. Assume that Assumptions 1, 3 and 4 hold, and GB S S. The conclusions of Theorem 2.2 hold if mq 2 k. "=" log and m Z R max(log q. r)) log(?),
Lemma 3.12. Assume Tyood E It, and Assumption 2, 3 holds. Then for all E goood.
2pm pn 1. w.p. at least 1 - exp(logā - C maxx( (E ( pe)
IIV, - E[Vell S eporttxx d1
For LRPR, the algorithm for LRCS needs three simple modifications. (1) The node initialization needs to be the one for LRPR introduced in (Nayer & Vaswani, 2023, on arXiv since Feb. 2021). (2) The update of by involves solving an r-dimensional standard phase retrieval problem, e.g., using the RWF algorithm of (Zhang, Zhou, Liang, (2) We estimate the phase (sign in case
3 2. w.p. at least - exxp(log 7 - "maxx(F (2' "Mu exp(log 7- (
IV - ElV S max (Sed,-1 + 4.3Gn)
& Chi, 2017). of real measurements which is what consider here) af- ter updating by as sign( Ub)) and use this to obtain in = sign ba)))))) @ Zg- This is used to replace yı: in the gradient expression. Denote this gradient as V.
Proof. Item one follows directly from (Abbasi & Vaswani, 2024, Lemma 4.5) which uses matrix Bernstein inequal- ity and Lemma 3.8 in its proof. We prove item two in Appendix B. This follows using the first item and care- ful algebra that allows us to express |/V, E(Ve, 11 in terms of V/ - E[Ve]lee; || Be Gelle, Fmax ( and [B; B% |r.. And since Joood S I, i.e., U, is row inco- herent we can bound each term using (Abbasi & Vaswani, 2024, Lemma 4.5), Lemma 3.8, and Assumption 3 respec- tively. Proof is in Appendix B.
Corollary 4.2. (Krum-AltGDmin for LRPR) Con- sider the algorithm as described above. The conclusions of Theorem 4.1 hold if mq Z max (0 log()), R 222r22 log( m 2 R max(log q. r) log (?).
and
LRCS needs order nr² log(1/c) samples which is also what LRMC needs. LRPR needs times more samples for its initialization since it is more difficult problem. Remark 4.3. Both above results also hold apply for GM.
4. Secure Federated LRCS and LRPR
In the writing below |z| and sign(z) return the element- wise magnitude and sign of z respectively. LRCS and LRPR involve recovering X from yk == A l E [g] (LRCS) and from 25 := ly E [4] (LRPR), with each yk being an m-length observed vector with m < n. and the measurement/kkttcingg matrices A₁ gmxx being known dense matrices (random Gaussian for guarantees) that are mutually independent over k. We consider the ver- tically federated setting, i.c., distinct subsets of columms of Y are available at different nodes. These are completely different problems than federated LRMC because here the matrices Ag are dense. This means there is asymmetry, we
Proof. Our proof techniques introduced for LRMC apply here with minimal changes. For LRCS, only three things change: (i) we do not need to prove incoherence of U or worry about the filtering step (which is removed from the algorithm); (ii) the concentration bound lemmas change the bound on B - TXx is obtained using Lemma 3 of (Vaswani, 2024) and the gradient deviation bound in the first part of Lemma 3.12 given above gets replaced by Lemma 5 of (Vaswani, 2024).
7

---

Arrantine-Resileent Federated Alternating Gradient Deseent and Minimization for LR matrix learning
For LRPR, the following additional modifications are needed. (1) The B lemma gets replaced by Lemma 3.3
1 (og()/)) of n 1,2
and GM has compute cost of I < (Gaperoz ) (1g(1/)) when using (Cohen al., 2016, Algorithm 1). To see any speedup from GM in sim- ulations, one would need to use (Cohen et al., 2016, Al- gorithm 1) with large L. This also requires large q to maintain accuracy. As a result, the total simulation time becomes much higher.
of (Nayer& & Vaswani, 2023, on arXiv since Feb. 2021). (2)
The computed Ve uses ÿ/ defined above. Thus, in order to obtain a bound similar to the first item of Lemma 3.11, we need two steps: (i) We first need to bound ||V - Velle with V being the gradient expression if the linear mea- surement y/ were available, i.e. the gradient used in case of LRCS. ||V Vell is the same as the Err Ph term that is bounded in Lemma 5.3 of (Nayer & Vaswani, 2023, arXiv since Feh. 2021) (LRPR section). (ii) Next we use Lemma 5 of (Vaswani, 2024) and triangle inequality to fi- nally get a bound on ||V- - ElV, to replace the first
LRCS: Figure 1b. We plot the average subspace distance SD,,U, /T vs Time in seconds over 100 Monte Carlo (MC) runs. The data generation part for X remains same as LRMC. For each Monte Carlo run we generated matrices A E [q] with each entry being i.i.d. stan- dard Gaussian and we set yv: = A k E [g]. We used 1 = 1/m(onaaa) where Tuuax = maxee[[] mmax (X₃). We used Weiszfeld's Algorithm with 1000 iterations to approx- imate Geometric Median (GM).
item of our 3.12.
5. Experiments
LRMC: Figure 1a. We plot the average subspace dis- tance (U,, / /Faainst against Time in seconds over 100 Monte Carlo (MC) runs The averaging is over the ob- served entries of X", with each entry being observed in- dependently with probability p at every MC run. The ma- trix X B" is generated once by letting U E Roxr be the left-singular vectors of an n r random ii.d. Gaussian matrix and B E R be a random Gaussian matrix. Thus, X" has J = O() incoher- ence. At each iteration, Lays = 8 of the I. = 20 gradi- ents communicated from the nodes to the center are cor- rupted. We consider Reverse Gradient Attack for each ex- periment where we corrupt the Loyz gradients by setting Vbys = - i E/ Ve. This forces the GD step to move in the reverse direction of the true gradient. We set the step- size 17 = 1/p(a122 x2ax): where max = max mma (X;), estimated as mmax = maxee][] (5maa((Y)) We com- pared Krum-AltGDmin, GM-AlGGDmin, and CWMedian- AltGDmin. We use Weiszfeld's algorithm with 1000 itera- tions to approximate the Geometric Median (GM).
Observation from Figure 1b. Same as LRMC observa- tion Section 5.
Real world MovieLenns 1M dataset (Real World); Fig- ure Ic. We test our proposed algorithm on the real-world MovieLens 1M dataset (Harper & Konstan, 2015), which contains 1, 000, 209 ratings for about 3, 900 movies from 6, 040 users. The algorithms are compared using the rel- ative error ( X ||ll//|XXX shown on the y-axis, where Q is the set of observed entries. This is used be- cause, in real data, unlike synthetic data, the true rank-r U is not known.
Observation from Figure 1c. We observe that our algo- rithm, Byz-AllGDmin-LMMC. converges on the federated MovieLens 1M dataset even with 40% Byzantine nodes (Loys = 8, L 20). We also observe that CWMedian converges in this setting due to the large number of sam- ples (ngj).
Heterogeneity Effect (LRMC): Figure 1d. We first gen- erate B" as a random Gaussian matrix. Each B; is formed by selecting a subset of columns E S, from B". Then, with L = 10 total nodes, we multiply 5 randomly cho- sen Bi by a factor C' to introduce heterogeneity across the datasets see Assumption 3 (Bounded heterogeneity). This was done once (outside Monte Carlo loop). For 25 Monte Carlo runs we did Reverse Gradient Attack and compared 'Krum-AltGDmin' for different values of C = 1,,46
Observation from Figure 1a. Theoretically, GM- AltGDmin has similar sample complexity to Krum- AltGDmin, so it also converges in the experiments. CW- Median does not converge due its large sample complex- ity requirement. GM-AltGDmin is slower than Krum, pos- sibly for two reasons mentioned below:
a) We use an approximate algorithm Weiszfeld's 's algorithm (Weiszfeld, 1937; Beck & Sabach, 2015) to approximate GM. Weiszfeld's algorithm (Beck & Sabach, 2015, The- orem 5.1) is known to converge, but the number of itera- tions is not specified. In theory, GM can be faster when using (Cohen, Lee, Miller, Pachocki, & Sidford, 2016, Al- gorithm 1). However, that algorithm is complex and to our best knowledge has no known experimental results.
Observations from Figure 1d. can be seen that increas- ing heterogeneity C means that the SDp saturates higher, as shown in our main result Theorem 2.2.
b) As shown in Table 1, Krum has a compute cost
8

---

Byzantine-Reslient Federated Alternating Gradient Deseent and Minimization for LR matrix learning
Subspace Error Time
Subspace Error Time
10
CriMocian
Subspace Erior
10'
Subspaace Enorr
10"9
10"10
10"1
15
20
25
30
Time (secondo)
(secconds)
(a) LRMC: (U, U// VF vs Time(seconds) with 1000, 0 = 500, T. 20, and Tays 8.
(b) LRCS: SD,(U: U>/ Time(seconds) with
1000, m 50, q 1000, = 3, I 20, and Tbys
CWMoodann
0.5
0.46
Rellttvve Errost
10
SDy(U, UP)
0.25
0.2
10
2500 Iterations
3005
10000
lverations
(c) Real-world MovieLens IM dataset: -Xallllllo (d) Heterogeneity Effeet (LRMC): SD:(UDUU..) U') /F vs Iter-
Iteration with n 6040, = 3940, 3. = 0.041902, ation with n p = 0.4, and using Krum.
200, q 1000, r 4.L 10, Lhys
L = 20, and Loyz =
6. Addressing reviewer comments
We have strengthened the experiments by adding results for GM and for the LRCS problem. We have now also eval- uated our algorithm on the MovieLens dataset. We have included and compared the related works as mentioned by the reviewer. We have also highlighted the technical differ- ences between this work and the related ones.

---

Byzantine-Reslient Federated Alternating Gradient Deseent and Minimization for LR matrix Iearning
Impact Statement
algorithm robust to an arbitrary number of byzantine attackers. IEEE Transactions on Signal Processing, 67(22), 5850-5864,
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, Y., Chi, Y., Fan, J., Ma, C., et al. (2021). Spectral
methods for data science: A statistical perspective. Foundations and Trends
References
Abbasi, A. A., Moothedath, S., & Vaswani, N. (2023).
rextregistered in Machine Learning, 566
Fast federated low rank matrix completion. In 2023 59th annual allerton conference on communication, control, and computing (allerton) (pp. 1-6).
Chen, Y., Su, L., & Xu, J. (2017). Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Mea- surement and Analysis of Computing Systems, 1(2), 1-25.
Abbasi, A. A., & Vaswani, N. (2024). Efficient feder- ated low rank matrix completion. arXiv preprint arXiv:2405.06566
Cherapanamjeri, Y., Gupta, K., & Jain, P. (2017). Nearly optimal robust matrix completion. In International conference on machine learning (pp. 797-805).
Acharya, A., Hashemi, A., Jain, P., Sanghavi, S., Dhillon, S., & Topcu, U. (2022). Robust training in high dimensions via block coordinate geometric median descent. In International Conference on Artificial In- telligence and Statistics (pp. 11 11145-11168).
Cohen, M. B., Lee, Y. T., Miller, G., Pachocki, J., & Sid- ford, A. (2016). Geometric median in nearly linear time. In Proceedings the forty-eighth annual ACM symposium on Theory of Computing (pp. 9-21). Collins, L.., Hassani, H., Mokhtari, A., & Shakkottai, S. (2021). Exploiting shared representations for per- sonalized federated learning. In International con- ference on machine learning (pp. 2089-2099).
Alistarh, D., Allen-Zhu, 7.,, & Li, J. (2018). Byzantine stochastic gradient descent. Advances in Neural In- formation Processing Systems, 31.
Allen-Zhu. Z., Ebrahimian, F., J., & Alistarh, D. (2020). Byzantine-resillent non-convex stochastic gradient descent. arXiv preprint arXiv:2012. 14366.
Dadras, A., Stich, S. U., & Yurtsever, A. (2024), Per- sonalized federated learning via low-rank matrix fac- torization. Opt 2024: Optimization for machine learning.
Allouah, Y., Farhadkhani, S., Guerraoui, R., Gupta, N.,
Pinot, R., & Stephan, J. (2023). Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In International conference on artificial intelligence and statistics (pp. 1232-1300).
Data, D., & Diggavi, S. (2021). Byzantine-resilient SGD
in high dimensions heterogeneous data. In 2021 IEEE International Symposium on Information The- ory (ISIT) (pp. 2310 2315).
Anaraki, F. P.,& & Hughes, S. (2014). Memory and com- putation efficient pea via very sparse random projec- tions. In International conference on machine learn- ing (pp. 1341-1349).
Data, D., & Diggavi, S. N. (2023). Byzantine-resilient high-dimensional federated learning. IEEE Transac- tions on Information Theory, 69(1), 6639-6670. Defazio, A., Bach, F., & Lacoste-Julien, S. (2014). SAGA:
Azizyan, M., Krishnamurthy, A., & Singh, A. (2014). Sub- space learning from extremely compressed measure- ments. In 2014 48th asilomar conference on signals, systems and computers (pp. 311-315).
A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27.
Babu, S., Lingala, S. G., Vaswani, N. (2023). Fast low
rank compressive sensing for accelerated dynamic MRI. IEEE Trans. Comput. Imag.-
Ghosh, A., Hong, J.. Yin, D., & Ramchandran, K. (2019). Robust federated learning in heterogeneous envi- ronment, arXiv preprint arXiv:1906.000 06629.
Beck, A., & Sabach, S. (2015). Weiszfeld's method: Old and new results. Journal of Optimization Theory and Applications, 164(1), 1-40.
Guerraoui, R., Rouault, S., et al. (2018). The hidden vul- nerability of distributed learning in byzantium. In International Conference on Machine Learning (pp. 3521-3530).
Blanchard, P., El Mhamdi, F. M., Guerraoui, R., & Stainer,
J. (2017). Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in
Haldar, J. P., & Liang, Z.-P. (2010). Spatiotemporal imag- ing with partially separable functions: A matrix re- covery approach. In 2010 ieee international sympo- sium on biomedical imaging: From nano to macro (pp. 716-719).
Neural Information Processing Systems, 30.
Candes, E. J., & Recht, B. (2008). Exact matrix com- pletion via convex optimization. Found. of Comput. Math(9), 717-772.
Cao, X., Fang, M., Liu, J., & Gong, Z. (2020). Fitrust: Byzantine-robust federated learning via trust boot- strapping, arXiv preprini arXiv:2012. 139955.
Harper, F. M., & Konstan, J. A. (2015). The movielens datasets: History and context. Acm transactions on interactive intelligent systems (liss) 5(4), 1-19.
Cao, X., & Lai, L. (2019). Distributed gradient descent
He, X., Ling, Q., & Chen, T. (2019). Byzantine-rohust
10

---

Byzantine- Resilient Federated Alternating Gradient Deseent and Minimization for LR matrix learning
stochastic gradient descent for distributed low-rank matrix completion. In 2019 ieee data science work- shop (dsw) (pp. 322-326).
on computer vision (pp. 4168-4175).
Singh, A. P., & Vaswani, N. (2024a). Byzantine resilient and fast federated few-shot learning. In Forty-first international conference on machine learning.
Jagatap, G., Chen, Z., Nayer, S., Hegde, C., & Vaswani,
N. (2019). Sample efficient fourier ptychography for structured data. IEEE Transactions on Computa-
Singh, A. P., & Vaswani, N. (2024b). Byzinntne-resilient federated pea and low rank column-wise sensing, IEEE Transactions on Information Theory.
tional Imaging, 6, 344-357.
Jain, P.. & Netrapalli, P. (2015). Fast exact matrix comple- tion with finite samples. In Conference on learning theory (pp. 1007-1034).
Singh, A. P., & Vaswani, N. (2024c). Byzantine- federated principal subspace estimation. In 2024 ieee international symposium on information theory (isit)
Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factor- ization techniques for recommender systems. Com- puter, 42),), 30-37.
(pp. 25 13514-25 2519).
Srinivasa, R. R.S., Lee, K., Junge,,, M., & Romberg, J. (2019).
Decentralized sketching of low rank matrices. In (pp.
Li, I., Xu, W., Chen, T., Giannakis, G. B., & Ling, Q. (2019). RSA: Byzantine-robust stochastic aggrega- tion methods for distributed learning from heteroge- neous datasets. In Proceedings of the AAAI Con- ference on Artificial Intelligence (Vol. 33, pp. 1544- 1551).
10101-101 10).
Thekumparampil, K. K., Jain, P., Netrapalli, P., & Oh, S. (2021). Statistically and computationally efficient linear meta-representation learning. Advances in Neural Information Processing Systems, 34, 18487- 18500.
Lingala, S. Hu, Y., DiBella, E.,, & Jacob, M. (2011). Ac- celerated dynamic mri exploiting sparsity and low- rank structure: kt slr. IEEE transactions on medical imaging, 30(5), 1042-1054.
Vaswani, N. (2024). Efficient federated low rank matrix re- covery via alternating gd and minimization: A sim- ple proof. IEEE Trans. Info. Th.,
Weiszfeld, E. (1937). Sur le point pour lequel la somme des distances de points donnés est minimum. Tohoku Mathematicul Journal, First Series, 43, 355-386. Wu, Z., Ling, Q. Chen, T., & Giannakis, G. B. (2020). Fed- crated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEE Transac- lions on Signal Processing, 68, 4583
Lu, S., Li, R., Chen, X., & Ma. Y. (2022). Defense against local model poisoning attacks to byzantine- robust federated learning. Frontiers of Computer Sci- ence, 16(6). 166337.
Nashed, M. (1968). A decomposition relative convex sets. Proceedings of the American Mathematical So- ciety, 19(4), 782-786.
Xie, C., Koyejo, S., & Gupta, I. (2019). Zeno: Dis- tributed stochastic gradient descent with suspicion- based fault-tolerance. In International Conference on Machine Learning (pp. 6893-6901).
Nayer, S., Narayanamurthy, P., & Vaswani, N. (2019). Phaseless pea: Low-rank matrix recovery from cosumn-wise phaseless measurements. In Interna- tional conference on machine learning (pp. 4762- 4770).
Yao, J. Xu, Z., Huang, X., & Huang, J. (2018). An effi- cient algorithm for dynamic mri using low-rank and total variation regularizations. Medical image analy- sis, 44, 14-27.
Nayer, S., & Vaswani, N. (2021). Sample-efficient low rank phase retrieval. IEEE Transactions on Information Theory, 67(12), 1190-8206.
Yi. X., Park, D., Chen, Y., & Caramanis, C. (2016). Fast algorithms for robust pea via gradient descent. Advances in neural information processing systems, 29.
Nayer, S., & Vaswani, N. (2023, on arXiv since Feb. 2021, Feb.). Fast and sample-efficient federated low rank matrix recovery from column-wiss wise linear and quadratic projections. IEEE Trans. Info. Th..
Yin, D., Chen, Y., Kannan, R., & Bartlett, P. (2018). Byzantine-robust distributed learning: Towards op- timal statistical rates. In International Conference on Machine Learning (pp. 5650-5659).
Netrapalli, P., Jain, P., & Sanghavi, S. (2013). Low-rank matrix completion using alternating minimization.. Pillutla, K., Kakade, S. M., & Harchaoui, Z. (2019). Robust aggregation for federated learning. arXiv preprint arXiv:1912.1 13445.
Zhang, H., Zhou, Y., Liang, Y., & Chi, Y. (2017). A nonconvex approach for phase retrieval: Reshaped wirtinger flow and incremental algorithms. The Jour- nal of Machine Learning Research, 18(1), 5164- 5198.
Regatti, J., Chen, H., & Gupta, A. (2022). Byzantine Re- silience With Reputation Scores. In 2022 58th An- nual Allerton Conference on Communication, Con- trol, and Computing (Allerton) (pp. 1-8).
Zheng, Q. & Lafferty, J. (2016). Convergence analysis for rectangular matrix completion using moter-monteiro factorization and gradient descent. arXiv preprint arXiv:6605.0703
Shome, D., & Kar, T. (2021). Fedaffect: Few-shot fed- erated learning for facial expression recognition. In Proceedings of the ieee/cvf international conference

---

Byzantine-Resiie Federated Alternating Gradient Descent and Minimization for LR matrix Iearning
A. Proof of Claim 3.1
This claim is proved using an induction argument similar to that of (Abbasi Vaswani, 2024).
Proof. Base case: From Lemma 3.2 (i), (ii), (iii) and (iv) holds for 1 = 0 w.p. at least 1 - -Lp33
Induction assumption: Assume that the Claim 3.1 holds for t =
Induction proof: From Lemma 3.4 w.p. least Lp2, Tgood S I. Hence Claim 3.1 (iv) holds for Also
(Joood] L- Lbys implies set Ie + 0. Now since Kr implies using Fact 3.5 Utemp Ut 1/V Kr satisfies
| templl S (1
0.4 R²
1| 1-1 + +1.40 n
We bound || $ ( where Utemp = - kr
QR U (Line 29 of Algorithm 1).
[[
o min (temp))
min (U,-1 V)rr)
Kr)
Since Tguad Iz, use Lemma 3,7. With least 1 - 2Lp1,
0.1 CT6RT
d.-1 S d0
0.1 5.1
and GB
0.2.0
we have w.p. at
5.1.8.0CR
1
0.2
0.2npon'a
+2
0.1
S1+ +
max
< +
(2)
min (U-11-VV
R²
R²
Above we have used
S
0.5 pe 22
Hence we get
0.4
1
|w 1-1 1-1111(R**)) | 1.4
(RR))
R2
71
0.4
0.1
r (11 0.1
|| -- + 1.
1.4
1+
R2
R2
R2
0.3
| + 2
R2
0.3
0.3 バ2
0.3
(1
+[1+ + (1
+
12
R2
11
u/ll
+
2/h
V
T s (1.5p+ 11)
0.3
n
The last incquality above used the infinite geometric series bound. This shows that U is in.rrow-incoherent i.e., (ii) holds for tort= = t. Now using Lemma 3.3 get
SDP(U*,U)) S I1, Br, B, (U,,(U),,,))) + m||Brr|I
(3)
Fmin (U,- - Vx))
Here Err Vrr - (U,,, Br))
Again since Igood C IG, we can use Lemma 3.6 which implies w.p. at least 1 2Lp1.
|Erl|r S Cpa max (Scδ 4.3GB)
(4)
12

---

Seeantine-Resilieen Federated Alternating Gradient Descent and Minimization for LR matrix learning
and from (2)
0.2mpo max
S 1 +
(5)
min (U,-1 kVKr)
R²
By Lemma 3.8, mmin (Be,) 2 0.90 min and mmax (max(BBb)) S 1. Thus, if S 0.5/po max then, I - Bi B is positive semi-definite (psd) and so
- Bp,,, B% = Amax (1 Bp, - 0.9mpo =
By,
ap min (Br,)
0.9mpo max
(6)
R²2
Using (6), (4), and (5) in (3) we get
SDp(U*,U, U,) 5( 0.9mpo 2
0.2rpooma 2
(1 +
)
R²
R²
0.2npo +2
+ mp Co max + 4.3GB)(1 +
max
X²
Since 0.1
0.2mpoom2 max
(1 1+
S 2 we have
C16R22
R?
0.65mpo max
+2
)8,-1 + nypor
22
C8.6G B
0.2 0.1
0.1
Since GB S 5.1 8.6CR2 6g
have
5.1
0.65mporn2 +2
(1
)6p + 0.160
< 0.7756
(8)
Above we have used 17 <
0.5 poms
From (8) we have 6, S 8, implies Claim 3.1 (iii) holds for t = t, and from (7) we have
5, S (1 bound Claim 3.1 holds for t = w.p. at least 3Lps t(Lp2 + 2Lp1). By principle of mathematical induction Claim
0.65mpo'2 mum y6 + myport C8.6GB Et (1 R2
0.65mpo min )"r implics Claim 3.1 (i) holds for Using union
R²
3.1 is true.
Fort t = T and using infinite geometric series bound
0. 0.65mpo max TT 80 + 14CR2Gp
5T - (1
R²
w.p. at least - 3Tps - T(Lp2 + 2.pp)).
Setting T = CR2 (og(1/e),
50 = $. and if nap 2 pR log [lo([1/e) then w.p. at least 1 - 3Lpz - T(Lp2 +
2Lp)) 2 3Ln CR2 CC2 Ln 10
SDr(U*,U) & max(e, 14CK2GB)
B. Proof of Grad Concentration Lemma 3.12
Proof. Item one follows directly from (Abbasi & Vaswani, 2024, Lemma 4.5).
Bounding V Ell
V E[V,]llr & V - E(Vellr+ + [V[ ElVell
& 10 max
from Lemma 3.12 item
+ |lp(Xe. X2,
p(Xe xi)BBl IF
13

---

Byzantine-Resine Federated Alternating Gradient Deseent and Minimization for LR matrix learning
é w.p. at least exp(log 7- maxx ( j R Pas
Bounding ||p( B/ pXx Xi) B
(i, X |B, - p(x; -xi) ||
- (B,, B,, - - By B
(B,, By - B;B. ||
=p|lU(B,, - B; B
- =pllU(B,, -
-B; - -B;; B.)
=pllU(B, B/ B,B, = - (Br, -B,) - (B; - Bi, B, )l
- (Br, B,) (U(B, B: BU, (Br, -Ba) (U, BB,) B F
$ < Bc |l + |U|
| || B |]] - Be, ll + GBo [|
from Assumption
{P((10 + 1.lo7 + o B: BG, l1 + 1.1G mux)
from Lemma 3.8
Now Bounding |B: B ||F
BB B l F
B: - Bi, = GG,
|G&, Br, Bi F
||e,, Be, + B: U X +U X
||Gr, Bd, + (B: Gi) - U (X - x
< ||22, B₁, |l + +B Gelle + Ggo
$ 20 + GBo
from Lemma 3.8
w.p. at least - exp(log 7
pm +²
Using this we get
llp(Xe - X; B - pxx B,) 1| -
< ((.1o0 + 1.10; + oi) B - B&, Bo
(333000)) + G B L.1G max
p(TE6=-10 + +
mux GB)
w.p. at least - exp(log q
pm G pu
ppn
This then implies w.p. at least exp(log max (K' p² R pu)tsr??
exp(log q
V - E[Vellle S epô;-10 max + |lp(Xi, - -X;, - x -;; B BT
S epô, 10 nax + 11776,1100221 + 4.30 a.
max
po max (8eδ, + 4)3G
C. Proof of Lemma 3.6
Proof. From Lemma 3.12 item two for all & E Tgood, w.p. at least 1 e-exp(log 1- --c maxx (K - per
2pm
+exp(log - 2
| - E(Ve)]lr S x2 2 (Scō,-1 + 4.3GB)
(10)
14

---

Byzantine-Reslient Federated Alternating Gradient Descent and Minimization for LR matrix learning
Using Lemma 3.9 and the fact ||M]] || [|vec(M)]] for any matrix M get w.p. least 1 20
|Vr - - S (8ed-1 + 4.3GB)
D. Proof of Lemma 3.7
Proof.
1 min (Ut-1 1/V Kr)
1
Umin(U-a ()E e (UL-1, Be, (Vrr E(Ve, (U--1, Bt, ))))
$ 1- 1- (U, BB,) 7) Err]
E VKr - EVV,, (U,-1, B(.)
Using Lemma 3.6 w.p. at least 2Lp
Errle S C (8c6,-1 + 4.3GB)
(11)
Using the bound [|E[Ve, (U, Bel)lle from (Abbasi & Vaswani, 2024, Lemma 4.5) and |Err] |F from (11). We get ( (U, B,, )lll + [Erl])= Σ upo ((2.5 + C8c)6 + C4.3GB).
Above we have used the fact that |M| || < | FF.
Implies
mmin (U1-1- - v/)r))
ippo #2 (22.5 + 11 C4.3Gn)
+ kpa 2 ((5 + C166) + C8.6GB)
Above we have used for 0 0<<<11/(1-0) < 1 + 2r assuming mppor max (22.5 + C4.3GB) <
E. Proof of Lemma 3.3
Proof. Utemp U--1 V/VKr- Kr-
Adding and subtracting ( (U,-1, BI, )) Note E(VA, (U,-1, B (X;; - -x,, B
Utemp U, V (U,- BA)) (V E(V (U,-1, B&,)))
-U-- - 11-1-1p(XX) (X, X2, BI, n/Er
Denote Err VKY Ky E(V (U,-1, B₁,)), ). Multiplying both sides by P := I - we get
PUsemp = PU,-1 - mpP(Xe, - -X BT 1/PEr
= PUU,1 upPU B:, B 1/PErr
-P - mpBr, B(,) P/r
15

---

Byzantine-Resllent Federated Alternating Gradient Descent and Minimization for LR matrix learning
Taking Frobenius norm and using | || we get
[UU temp |r - PPUU-Ilell44 mp B n||PErr||s
(12)
Now Utemp URR and since |2, S ||M this means that SD(U", ,U)
QR
2 11
U.U Saaempple/((6 |||||||(((]+)) Since
||(R))- 1/ //Tmin (R+) ) 1/0 min (Utemp),
|[(Rt)-1|- =
0 min (U,- 1
Combining the last two bounds gives.
I,, np B SDp(U', (U-)))))) 7//Err| m (Uz-1 -VVKr)
;U)
F. Why we cannot use projection step to guarantee incoherence
A natural question would be to use projection Il at center after each GD step to make rows of U, incoherent. We cannot get a very useful bound on S (U", (U4) which we explain next. By Lemmas 2.5 and 2.6 of (Chen, Chi, Fan, Ma, et al., 2021), for two n x matrices with orthonormal columns, U1, U2, (U1,U v2SDr (U,, U2).
I argming anitary || - S
Let us say you have a bound & before projection step i... SD=(U*, (U=,U, S 6, After the projection from you have SD2 (U), U*) s (U,) - UlQ for any Q unitary. Now the row norm clipping step can be interpreted as projecting its input onto a convex set, 4 := {Ū | < (1 04) ) + /.44/= with the projection being in Frobenius norm. And projection onto convex sets non-expansive, i.e. (U,) (U2))l I | U2|( (Nashed, 1968, eq (1)), et al., 2016). Also, (U*)) Q*Q for any x r unitary matrix Q (since U well U times any unitary matrix belong to 2)) Let Q+,1 argmin unitary | Q+ this then implies SDμ (UI,(U,), < [[ - Qullle = (U,, - - (U*QU.Q) Q.,I)l I ||U--U'A U'Q..elle I V2SD, (U,, U*) I /25,. So introduces factor of 2 after each projection, and hence for large T this will grow exponentially making sample complexity worse.
Thats why we use filtering step.
G. Proof of Lemma 3.9
Proof. Denote the Loys Byzantine vectors as { Jk=1 vector j is the neighbor of vector f. For each index (good or Byzantine) we denote by óy (1) (resp. (1) the number of good (resp. Byzantine) indices such that i + j. We have
B Laus and L- L-Loys Loys good vectors as {
L- By l - j we mean
85(1) + 56()
Lby=
L 2Tay= -2 5)(1) < I. Tbyy=
do(1) < Lbys.
Let Kr is the index selected by Krum. Let L be the index of any good vector. Now we can write
= 2|| = -|2kr 2 +
Σ
2j|
8,(Kn
Kr
good j
< || (K(rr)
Σ
+
|1
1
Σ
zyll
(Kr)
Kr-+ good
Kr good j
16

---

Byzantine-Reslientt Federated Alternating Gradient Deseent and Minimization for LR matrix learning
Σ
||
Eill
Σ
| اnب
5g (K))
(g(Kr)
Kr guod
good
- (Kr)
|| 2gll +
max Kr Kr- good
||2 - -2i1l
(13)
Kr- good j
Analyzing the first term. There are two possibilities 1) Kr Igood, or 2) Kr J good i.e.,
ZKr
Σ
|| 2z Ke +
Σ
B
25|11
Kr
(K))
(1(
5y
good
Kr- g
(- good
ggod
We will first analyze the case when Kr Io l' such that
Since Kr minimizes the score therefore there exist a good gradient
Σ
Σ
B
Σ
EZ - Zz1 +
Σ -'
||
k
b- good j
byz
8- good
byzs
Each l has L - Lbyz neighbors, and Lay= + non-neighbors. Thus there exists a good gradient (((') which is farther
from L' than any of the neighbors of f". In particular, for each Byzantine index such that l byz i, || 2 <
Zz - =<(r>)) Implies
Σ good j
12
2yl1 S
Σ
| 2z
Σ
||
2,
k good j
+ hyz
<
Σ
|| - zj +
Σ
|2 2 II
8 + good j
8' byz
|| اا + (f")))) =ς(e)'l
8' good j
< (l')))
max - good
|| - 1, + (o())) ||= - =c(())l
Now bounding ||= =zyl for any i.j E Igood.
|| - 2 = =1|2: - 2 #1l
$ 1|| El| ||ا
2|
w.p. at least - 2p.
Using union bound w.p. at least 1 - 2(L Loys - 2)p
Σ
1
B
2, 5 (6)(()) + (e(
-ー good j
$ (L Loyz 2)
For Kr L E T goood
(1) /- good
1
Σ
E - z, Krl1kr=t
<
(- good
max
1| - -2,1
2e||221
17

---

Srrantine-Resllien Federated Alternating Gradient Deseent and Minimization for LR matrix Iearning Combining Kr Igood and Kr Io we get
Σ
|
2z max 2e||
L Loys - 2 -2 |||
5g (r))
(k)
good
-byy
< max
1,
L 2Loyz 2 2c|1211
This then implies
=kkr El| S
1
Σ
E -zyl +
max
|| =,
(K))
Kr-+ good
Kr
good
Lays
< max
1,
2e|1221 + +
2bbyx
2
L Lbyy -2
max
2, 1 +
2c|1E|1
L 2L -2
L - Liy= - 2
2
2c ž|1
L 2Lbyz
10c||E1
(14)
w.p. at least
2(L Loys )p 1 - 21(1 - -T)p. For т Layz < +04,2
L- 25. 5.
L-
18


Reviews:
[{"review_id": "kZ85D3vRtj", "reviewer": "Reviewer_RNhd", "summary": "This paper mainly focuses on the low-rank matrix completion problem, under the setting of federated (centralized) learning with Byzantine attacks. The authors propose an algorithm designed to be resilient to the attacks by employing robust aggregators such as Krum or the Geometric Median. Theoretical analysis and simulations are provided to demonstrate the convergence of the algorithm. Additionally, the approach is extended to other low-rank learning problems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincerest gratitude for your diligent study of our work and the thoughtful reviews. We will now answer your questions and concerns.\n* Figure 1 of our paper shows that our Algorithm 1, Byz-AltGDmin-LRMC, converges for the federated LRMC problem even when $40\\\\%$ of the nodes are Byzantine. It also shows that coordinate-wise median (CWMedian) does not converge. As we explain in the paper, CWMedian needs a much higher sample complexity (depends on the gradient dimension) see Table 1 and is also evident from Figure 1.\n* Purpose of paper is to show (i) the framework provably works; (ii) we can prove results for Krum and for GM. Theoretically, Krum can be slower than GM when GM is approximated using (Cohen, Lee et al., 2016, Algorithm 1) and the number of nodes $L$ is very large.\n* We have now added GM and will include it in the final version. We have provided the discussion for it in our response to\nReviewer **uCLY**. An anonymous link to the simulation results PDF is provided for the reviewer. [Link](https://send.vis.ee/download/08042171bf7ca9bd/#_zNz4g5BylyRmIrCCb_YqA) **(Please Note: The link will expire after 10 downloads/2.5 days)**\n* As noted in \"Observations from Fig. 2: Heterogeneity\" subsection on Page 8, Heterogeneity question is already addressed. We briefly reiterate for clarity: we first generate $\\mathbf{B}^*$ as a random Gaussian matrix. Each $\\mathbf{B}^*_\\ell$ is formed by selecting a subset of columns $k \\in S_{\\ell}$ from $\\mathbf{B}^*$. Then, with $L = 10$ total nodes, we multiply $5$ randomly chosen $\\mathbf{B}^*_\\ell$ by a factor $G_B$ to introduce heterogeneity across the datasets see Assumption 3 (Bounded heterogeneity). \n* **Novelty, Key Differences, and Difficulties Compared to (Singh & Vaswani, 2024b)** We respectfully note that this point has already been addressed in detail in the paper (see “Contributions and Novelty” subsection on Page 2). We reiterate it here for clarity:\n1) **Heterogeneous gradients:** Our setting involves heterogeneous data across nodes (vertical federation), making gradients different\nat each node. (Singh & Vaswani, 2024b) assumes a homogeneous setting (horizontal federation) , which is much easier to handle. **Definitions for terminologies, horizontal v.s. vertical settings?** The data matrix is $\\mathbf{Y}$ of size $n \\times q$. Horizontal federation means each node $\\ell\\in[L]$ sees a subset of $n/L$ rows of $\\mathbf{Y}$ but all $q$ columns. This is like partitioning data by examples, each node has different samples but all features. This is usually a homogeneous setting (Kairouz et al., 2021). Whereas Vertical federation partitions data by features: each node sees a subset of $q/L$ columns but all rows (samples), resulting in a heterogeneous setting.\n2) **Incoherence of** $\\mathbf{U}^*$: (Singh & Vaswani, 2024b) studied the LRCS problem, which does not require incoherence of $\\mathbf{U}^*$. In LRMC, we need to ensure incoherence of $\\mathbf{U}$ at every iteration. This is hard because $\\mathbf{U}$ is updated using possibly non-incoherent gradients from GM or Krum. To handle this, we introduce a **filtering step**. See Algorithm 1, Lines 22–27 and 9–12, Lemma 3.4, Fact 3.5 (for the GD step), and Lemma 3.2 item 3 (for initialization).\n3) **Guarantees for Krum:** (Singh & Vaswani, 2024b) only provides theoretical results for GM, which cannot\nbe computed exactly. The theory and practical implementation differ. In contrast, we provide non-asymptotic guarantees\nfor both Krum and GM.\n* We focus only on GM and Krum because the other two common aggregators used in the literature CWMedian, and\nTrimmed Mean, have very high sample complexity, which makes the results impractical. The sample complexity for\nCWMedian (Yin et al., 2018, Theorem 1) and for Trimmed Mean (Yin et al., 2018, Theorem 4) depends on the gradient\ndimension.\n* We fixed the fraction of Byzantine nodes to a specific value for simplicity. For the general case, we provide the result again: Theorem 2.2 with the following changes. If $L_{byz}<\\frac{L}{2} - 1$, and $n\\tilde{q} p\\geq CC_{Kr}\\tilde{\\kappa}^{10} \\mu^2 \\tilde{q}  r^2\\log \\tilde{q} \\log (1/\\epsilon),$ then with high probability, $ SD_F(U^*, U_{T})  \\leq   \\max(\\epsilon, 14C_{Kr}\\tilde{\\kappa}^2 G_B).$ Where $C_{Kr}=2+\\frac{1-\\tau-2/L}{1-2\\tau-2/L}$, for $\\tau=\\frac{L_{byz}}{L}<0.4$, $C_{Kr}\\lessapprox 5$.\n\nIf  $\\tau\\rightarrow \\frac{1}{2} - \\frac{1}{L}$ then $C_{Kr}\\rightarrow\\infty$ which blows up everything. For $\\tau = 0$, our sample complexity matches the result of Byzantine free result (Abbasi & Vaswani, 2024, Theorem 2.1). It should be noted\nwhenever we are using a robust aggregator GM or Krum the estimation accuracy is as good as that of one good node. So,\nthe effective sample size is $\\tilde{q}$ and we see the heterogeneity factor $G_B$ in $SD_F(U^*, U_{T})$ bound.\n___\nWe will address all minor comments, add the necessary references, and improve the document's readability in the final version of the paper.", "claims_and_evidence": "The claims made in this work would benefit from stronger support—both through more intuitive explanations to aid understanding and through more thorough discussions and comparisons with existing literature to enhance credibility.", "methods_and_evaluation_criteria": "The experiment description is unclear:\n- What is the purpose of Figure 1? Does the algorithm benefit from the robust aggregator Krum, or from the algorithm framework? And how do the two curves compare with GM?\n- In Figure 2, how do the authors change the heterogeneity? There is no description in the Supplementary material on the data generating process.", "theoretical_claims": "I went over the proofs, which inherits a lot from the literature (Singh & Vaswani, 2024b). The soundness of the results are good, though the originality should be highlighted.", "experimental_designs_or_analyses": "Details of the experimental settings in the supplementary material will be appreciated. Otherwise, it is too vague to evaluate the simulations.", "relation_to_broader_scientific_literature": "The key contributions of the paper root in the theoretical results, which as the authors point out, originates from Singh & Vaswani (2024b) a lot. Instead of sketching each step of the proofs in details, it could be better to emphasize the main difficulties or differences between your work and the previous one.", "essential_references_not_discussed": "There should be more references in the discussion of application in the first paragraph of introduction. On the other hand, literature of related works, especially in Byzantine algorithms that are not specific to low-rank problems, are cited too much without recent updates.", "other_strengths_and_weaknesses": "The theoretical derivations are presented in thorough detail; however, the paper's weak structural organization and lack of a clear logical roadmap significantly hinder readability.", "other_comments_or_suggestions": "1. Please properly use citation format, including \\citet, \\citep, etc.\n\n2. The writing is readable but logically weak. Hope the writing can be refined.\n\n3. In the last paragraph of Section 1, there is a typo \"X=UB, B,are updated...\". Not sure what is the correct statement.\n\n4. The notation $x_k^*$ in Section 1 is not clearly defined.\n\n5. There should be a title for Assumption 2, similar to \"Bounded heterogeneity\" in Assumption 3. For example, stating that Assumption 2 is the so-called incoherence.", "questions_for_authors": "1. Could you provide explanations or definitions for terminologies, e.g., horizontal v.s. vertical settings?\n\n2. Could you emphasize what are important features that limit the analysis to two aggregators (GM and Krum)?\n\n3. Although you assume that the fraction of Byzantine nodes is <= 0.4. How would the results rely on the fraction? In particular, for sanity check I would like to see that fraction = 0 recovers the literature results on this problem, and fraction going to the upper bound (L/2-1) gives explosive error bound.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q531gEDY9z", "reviewer": "Reviewer_uCLY", "summary": "This paper proposes a provably secure sample and communication-efficient federated alternating minimization-based algorithms Krum-AltGDminv and GM-AltGDmin for low-rank matrix completion (LMRC) problems that are resilient to Byzantine attacks. They then extend their analysis to show how a simple modification of assumptions about the right singular vector's coherence (Assumption 4 instead of Assumption 2) and steps of the federated algorithm can also solve partly-decoupled vertically federated LR matrix learning problems including the LR column-wise sensing (LRCS) and its phaseless generalization, the LR phase retrieval (LRPR). They conclude with experimental evaluation of their federated learning LRMC algorithms against Additive $\\mathcal{N}(1, 1)$ attack and the Reverse Gradient Attack (Figure 1) and given data heterogeneity (Figure 2).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincerest gratitude for your diligent study of our work and the thoughtful reviews. We will now answer your questions and concerns.\n* We have strengthened the experiments by adding results for GM and for the LRCS problem. We have now also evaluated our algorithm on the MovieLens dataset. An anonymous link to the simulation results PDF is provided for the reviewer. [Link](https://send.vis.ee/download/08042171bf7ca9bd/#_zNz4g5BylyRmIrCCb_YqA) **(Please Note: The link will expire after 10 downloads/2.5 days)**. These will be included in the final version.\n* Theoretically GM-AltGDmin sample complexity is similar to Krum-AltGDmin, so it also converges in the experiments. However, GM is an approximate algorithm, while Krum is not. Our work provides, to the best of our knowledge, the first non-asymptotic guarantee for Krum, which is simple, intuitive, and easy to compute (Blanchard et al., 2017) see Lemma 3.9.\n*We thank the reviewer for the helpful observation* that the Weiszfeld algorithm used in practice is not guaranteed to be\nfaster than Krum. This holds both in theory and can also be seen in experiments. Nothing concrete can be said about which\none is faster in general. Now we explain the **practical difficulties with implementing GM**:\n1)  In practice, Weiszfeld’s algorithm (Weiszfeld, 1937; Beck & Sabach, 2015) is used to approximate GM. Weiszfeld’s algorithm (Beck & Sabach, 2015, Theorem 5.1) is known to converge, but the number of iterations is not specified. In theory, GM can be faster when using (Cohen et al., 2016, Algorithm 1). However, that algorithm is complex and to our best knowledge has no known experimental results.\n2) As shown in Table 1 of the paper, Krum has a compute cost of $nr^2L^2\\log(1/\\epsilon)$, and GM has a compute cost of $nr^2L\\log^3(L/\\epsilon_{approx})\\log(1/\\epsilon)$ when using (Cohen et al., 2016, Algorithm 1). To see any speedup from GM in simulations, one would need to use (Cohen et al., 2016, Algorithm 1) with a large $L$. This also requires a large $q$ to maintain accuracy. As a result, the total simulation time becomes much higher.\n* We will include and compare the related works as mentioned by the reviewer in the final version of our paper. We iterate it here: (Abbasi, Moothedath, & Vaswani, 2023) show experimental results for federated LRMC using AltGDmin, but without theoretical guarantees. (He, Ling, & Chen, 2019) show experimental results for Byzantine-resilient LRMC, again with no theoretical guarantees. (Dadras, Stich, & Yurtsever, 2024) provides results for personalized federated learning using the Burer-Monteiro\nfactorization method.\n* While LRMC has been widely studied in the centralized setting (Candes & Recht, 2008; Jain, Netrapalli, & Sanghavi, 2013; Fazel, 2002; Keshavan, Montanari, & Oh, 2010), to the best of our knowledge, there is no existing work on provably accurate federated LRMC, except (Abbasi & Vaswani, 2024). Some related works exist in distributed (Mackey, Talwalkar, & Jordan, 2015; Teflioudi, Makari, & Gemulla, 2012) and decentralized (Ling, Xu, Yin, & Wen, 2012; A.-Y. Lin & Ling, 2015; Mardani, Mateos, & Giannakis, 2013) settings, but they are not directly comparable to our federated setup.", "claims_and_evidence": "The claims made in the paper are backed up with experimental evaluation using Additive $\\mathcal{N}(1, 1)$ attack and the Reverse Gradient Attack (Figure 1) and given data heterogeneity (Figure 2). For the first set of experiments (Figure 1), authors make the observation that Krum converges faster than CWMedian and that CWMedian fails for Reverse Gradient Attack, which is a harder attack, which clearly demonstrates that Krum is more effective. The experimental evaluation is limited and there is no comparison of Krum-AltGDminv and GM-AltGDmin algorithms against other federated algorithms for LMRC.", "methods_and_evaluation_criteria": "While simulation datasets are sensible to use in this setting, it would be good to see more matrix completion datasets that are used in real-life like the MovieLens datasets: https://grouplens.org/datasets/movielens/.", "theoretical_claims": "I could not check the correctness of the proofs.", "experimental_designs_or_analyses": "The experiments are limited and few. They serve to show that Krum is more effective than CWMedian and that data heterogeneity matters. However, there is no evaluation of the Krum-AltGDminv and GM-AltGDmin for low-rank matrix completion (LMRC) problems.", "relation_to_broader_scientific_literature": "The Low-Rank Matrix Recovery (LMRC) problem is well studied in the centralized or non-federated setting. Early work include  Solutions consist of the convex relaxation developed by (Candes & Recht, 2008), which was very slow and the Alternating Minimization (AltMin) algorithm with a spectral initialization by (Netrapalli, Jain, & Sanghavi, 2013). The authors make extensive use of the results in (Abbasi & Vaswani, 2024) to prove their results. The work by (Singh & Vaswani, 2024b) is most closely related to this work but it deals with a much easier setting of horizontally federated LRCS, where the data, and hence node gradients, are homogeneous.", "essential_references_not_discussed": "It would be good to add these works to the discussion:\n\n1. Abbasi, Ahmed Ali, Shana Moothedath, and Namrata Vaswani. \"Fast federated low rank matrix completion.\" 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2023.\n\n2. Dadras, Ali, Sebastian U. Stich, and Alp Yurtsever. \"Personalized Federated Learning via Low-Rank Matrix Factorization.\" OPT 2024: Optimization for Machine Learning. 2024.\n\n3. He, Xuechao, Qing Ling, and Tianyi Chen. \"Byzantine-robust stochastic gradient descent for distributed low-rank matrix completion.\" 2019 IEEE Data Science Workshop (DSW). IEEE, 2019.", "other_strengths_and_weaknesses": "The main strength of this paper is the detailed theoretical analysis of security of the Krum-AltGDminv and GM-AltGDmin for low-rank matrix completion (LMRC) problems. The main weakness is the lack of experimental evaluation of the proposed algorithms. The reason could be the difficulty of implementation as the authors state that Krum is an easy-to-compute estimator but requires $nrL^2$ time to compute and that GM can only be approximated and that the only algorithm with a useful guarantee for it is too complex to implement even for the algorithm authors.", "other_comments_or_suggestions": "None", "questions_for_authors": "1. Have you implemented the Krum-AltGDminv and GM-AltGDmin for low-rank matrix completion (LMRC) problems? If not, what are the practical difficulties with implementation?\n2. Have you tried to solve two other federated LR problems – LRCS and LRPR with your proposed algorithms? \n3. You mentioned that Weiszfeld algorithm used in practice is also practically faster than Krum. Is there a citation for this? How does it compare to your proposed algorithms?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}, {"review_id": "kMAGoJK7tz", "reviewer": "Reviewer_2BbT", "summary": "This paper considers multiple versions of low-rank matrix completion problem under different observation models, in a federated learning scenario. In this scenario, the columns of the observed matrix are distributed among multiple clients. The paper proposes a Byzantine-resilient algorithms that may use two different similarity-based mechanisms and provably converges to the true model. Some simulation experiments are presented that discuss the speed of convergence under different attacks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincerest gratitude for your diligent study of our work and the thoughtful reviews. We will now answer your questions and concerns.\n* We have strengthened the experiments by evaluating our algorithm on real-world MovieLens 1M dataset (Harper & Konstan, 2015). The dataset contains $1,000,209$ user ratings for about $3,900$ movies from $6,040$ users. An anonymous link to the simulation results PDF is provided for the reviewer. [Link](https://send.vis.ee/download/08042171bf7ca9bd/#_zNz4g5BylyRmIrCCb_YqA) **(Please Note: The link will expire after 10 downloads/2.5 days)**. These will be included in the final version. We observe that our algorithm, Byz-AltGDmin-LRMC, converges on the federated MovieLens 1M dataset even with $40\\\\%$ Byzantine nodes ($L_{byz} = 8$, $L = 20$). We also observe that CWMedian converges in this setting due to the large number of samples ($n\\tilde{q} p$). We view applying the method to other real-world datasets for LRCS, and LRPR problem as a promising direction for future work.\n*  **Novelty, Key Differences, and Difficulties Compared to (Singh & Vaswani, 2024)** We respectfully note that this point has already been addressed in detail in the paper (see “Contributions and Novelty” subsection on Page 2). We reiterate it here for clarity:\n1) **Heterogeneous gradients:** Our setting involves heterogeneous data across nodes (vertical federation), making gradients different\nat each node. (Singh & Vaswani, 2024) assumes a homogeneous setting (horizontal federation) , which is much easier to handle. **Definitions for terminologies, horizontal v.s. vertical settings?** The data matrix is $\\mathbf{Y}$ of size $n \\times q$. Horizontal federation means each node $\\ell\\in[L]$ sees a subset of $n/L$ rows of $\\mathbf{Y}$ but all $q$ columns. This is like partitioning data by examples, each node has different samples but all features. This is usually a homogeneous setting (Kairouz et al., 2021). Whereas Vertical federation partitions data by features: each node sees a subset of $q/L$ columns but all rows (samples), resulting in a heterogeneous setting.\n2) **Incoherence of** $\\mathbf{U}^*$: (Singh & Vaswani, 2024) studied the LRCS problem, which does not require incoherence of $\\mathbf{U}^*$. In LRMC, we need to ensure incoherence of $\\mathbf{U}$ at every iteration. This is hard because $\\mathbf{U}$ is updated using possibly non-incoherent gradients from GM or Krum. To handle this, we introduce a **filtering step**. See Algorithm 1, Lines 22–27 and 9–12, Lemma 3.4, Fact 3.5 (for the GD step), and Lemma 3.2 item 3 (for initialization).\n3) **Guarantees for Krum:** (Singh & Vaswani, 2024) only provides theoretical results for GM, which cannot\nbe computed exactly. The theory and practical implementation differ. In contrast, we provide non-asymptotic guarantees\nfor both Krum and GM.\n* There is no assumption on the attacker. We mention in the Introduction section Page 1 *“that the adversarial nodes have\ncomplete knowledge of the data at every node and of the exact algorithm (and all its parameters) implemented by every\nnode, including center; and all the adversarial nodes can collude to use this information to design the worst possible attacks”*\nso adversarial nodes can send any arbitrary sequence of messages.\n* We will improve the structure and overall readability in the final version.", "claims_and_evidence": "The claims regarding convergence are verified both theoretically and by simulated experiments. However the experiments are limited.", "methods_and_evaluation_criteria": "The methods make sense for the problem of interest. The experiments indeed support the methods, but they are introduced only in a simulated scenario and the results in a more realistic problem are still unknown.", "theoretical_claims": "I did not check the details of the proof, but the overview presented in the main body of the paper makes me confident that the proof is correct.", "experimental_designs_or_analyses": "The experiments are based on simulation which makes sense for the claims, but does not motivate the importance of the problem under study.", "relation_to_broader_scientific_literature": "I believe that the problem is of general interest and can be used in many applications. Federated learning problems and security are the main topics of broad interest in this work.", "essential_references_not_discussed": "I am not aware of any reference.", "other_strengths_and_weaknesses": "The paper discusses the low-rank matrix factorization and completion, which can have application in various scenarios. There is a rigorous mathematical study regarding Byzantine resilience and convergence of the algorithm.\n\nWeakness: There is a similarity to the previous work (Singh and Vaswani 2024) and I am still unsure how much this paper improves the results in the previous work. The application of this problem is not also well-justified. The experiments are only in a simulated scenario.", "other_comments_or_suggestions": "I suggest the authors to consider proofreading. The text is not understandable at some points, but it is generally easy to read it. Particularly the notation for columns and rows of a matrix is not introduced.", "questions_for_authors": "I do not have any major question, but two minor ones:\n\n1) I am still unsure what are the main differences between this work and (Singh and Vaswani 2024). It is helpful if the authors can list the differences clearly.\n\n2) In Theorem 2.2 is there any assumption on the attacker or is this result for any arbitrary sequence of messages sent by the attackers?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rN42oMpkRn", "reviewer": "Reviewer_FvfR", "summary": "This paper presents a Byzantine-Resilient federal low-rank matrix completion algorithm, which aims to recover the decomposition of the ground truth matrix $X^\\star=UB$ from its entrywise measurements. The proposed algorithm works by minimizing $U$ and $B$ alternatively under the settings of federated learning. The authors also incorporate the method of Krum and GM to make their algorithm Byzantine-Resilient. The proposed algorithms can be extended to solve low-rank columnwise sensing and phase retrieval.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincerest gratitude for your diligent study of our work and the thoughtful reviews. We will now answer your questions and concerns.\n* We have strengthened the experiments by adding results for GM and for the LRCS problem. We have also evaluated our algorithm on real-world MovieLens 1M dataset (Harper & Konstan, 2015). The dataset contains $1,000,209$ user ratings for about $3,900$ movies from $6,040$ users. An anonymous link to the simulation results PDF is provided for the reviewer. [Link](https://send.vis.ee/download/08042171bf7ca9bd/#_zNz4g5BylyRmIrCCb_YqA) **(Please Note: The link will expire after 10 downloads/2.5 days)**. These will be included in the final version. We observe that our algorithm, Byz-AltGDmin-LRMC, converges on the federated MovieLens 1M dataset even with $40\\\\%$ Byzantine nodes ($L_{byz} = 8$, $L = 20$). We also observe that CWMedian converges in this setting due to the large number of samples ($n\\tilde{q} p$). We view applying the method to other real-world datasets for LRCS, and LRPR problem as a promising direction for future work.\n* We will improve the structure and readability in the final version. We will also fix all typos and grammar errors.", "claims_and_evidence": "All the claims made in the submission are supported by convincing evidence.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I only have time to check the proof of Theorem 2.2 and it seems correct to me.", "experimental_designs_or_analyses": "The experimental section in the paper is really weak.\n\nFirst of all, the experiment is only done on synthetic data generated from Gaussian distribution. As mentioned by the authors in the introduction \"These (federated low rank matrix learning) find important applications in many different modern ML and medical imaging domains – recommender system design, multi-task representation learning for few shot learning, federated sketching, accelerated dynamic MRI and Fourier ptychography.\", the authors should at least evaluate their proposed algorithm using one of the above applications mentioned above.\n\nSecond, the experimental results for LRCS and LRPR are not shown.", "relation_to_broader_scientific_literature": "The paper presents a Byzantine-Resilient federal low-rank matrix completion algorithm.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "The writing of this paper needs to be improved as are so many typos and grammatical mistakes in the paper. For example, the second sentence of the introduction is missing a period (.) at the end; \"the this value\" should be \"this value\" in line 4 in algorithm 1; and many more.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates the Byzantine-robust federated low rank matrix completion problem and its variants. The proposed algorithms are based on alternating minimization and two robust aggregation rules, Krum and geometric median. Overall, the reviewers recommend acceptance, although the numerical experiments are weak (in terms of data sets, data distributions, types of Byzantine attacks, etc). They also give several suggestions that should be considered in preparing the final version: (i) Highlighting the technical differences between this work and the related ones; (ii) Citing and discussing several relevant references.
Decision: Accept (poster)