Communication-efficient distributed eigenspace estimation with arbitrary node failures
Authors: Vasileios Charisopoulos
Anil Damle
Venue: NeurIPS 2022 Accept (2022)

Abstract: We develop an eigenspace estimation algorithm for distributed environments with arbitrary node failures, where a subset of computing nodes can return structurally valid but otherwise arbitrarily chosen responses. Notably, this setting encompasses several important scenarios that arise in distributed computing and data-collection environments such as silent/soft errors, outliers or corrupted data at certain nodes, and adversarial responses. Our estimator builds upon and matches the performance of a recently proposed non-robust estimator up to an additive $\tilde{O}(\sigma \sqrt{\alpha})$ error, where $\sigma^2$ is the variance of the existing estimator and $\alpha$ is the fraction of corrupted nodes.

Communication-effcieeet distributed eigenspace estimation with arbitrary node failures
Vasileios Charisopoulos
Anil Damle
Operations Research & Information Engineering Cornell University
Computer Science
Cornell University Ithaca, NY 14853
Ithaca, NY 14853
vc333@cornel1.
damle@cornell. edu
Abstract
We develop an eigenspace estimation algorithm for distributed environments with arbitrary node failures, where subset of computing nodes can return structurally valid but otherwise arbitrarily chosen responses. Notably, this setting encompasses several important scenarios that arise in distributed computing and data-collection environments such as silent/soft errors, outliers or corrupted data certain nodes, and adversarial responses. Our estimator builds upon and matches the performance of a recently proposed non-robust estimator up to an additive ((ava) error, where a² is the variance of the existing estimator and a is the fraction of corrupted nodes.
Problem overview and background
Modern machine learning has seen the proliferation of heterogeneous distributed environments for training and deploying data science pipelines. As communication between machines is often the most time-consuming operation distributed systems, the design communication-effiieee algorithms is of paramount importance for scaling to massive datasets [36]. However, the move to distributed environments also adds several additional layers complexity the design algorithms.
For example, in the distributed setting would like algorithms to be robust and providing meaningful answers even in settings where some nodes contain outlier data [4], silently fail during the computation [27, 31], central solution.
compromised and returning malicious results designed corrupt the
This work focuses on distributed eigenspace estimation in the context of robustness to node-level corruptions. Formally, we assume a computing environment with nodes numbered 1..... m, where every node i observes local version A, of unknown symmetric matrix A Iddxd, the goal to approximate the subspace spanned by the r & principal eigenvectors A. Distributed PCA standard example in this framework: every machine draws i.i.d. samples from unknown distribution P with covariance matrix and forms a local empirical covariance matrix A₁. Recently proposed coannunncaaion-ffffcice
algorithms have every node i transmit V,, the d matrix of principal eigenvectors A,, to a central server, which then aggregates all the local solutions via a carefully-crafte aggregation procedure [10, 18).
We devise and analyze an algorithm that robust to a wide range of corruptions that can occur to subset of the computational nodes. In particular, we assume that some fraction of the computational nodes can respond with completely arbitrary, but structurally valid, responses (i.c., they return arbitrary matrices V; with orthonormal columns). This model encompasses three common forms of node-level corruption that cannot easily detected by the central machine in isolation:
Silent/soft errors. While computational errors may be rare on single machines, as distributed workloads span large numbers of nodes probability that some them fail becomes significant.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Though catastrophic failures may be detectable, allowing the central server to simply ignore the output of specific nodes, the more nefarious issue is that of so-called silent (or soft) errors [16, 19. 27]. More specifically, silent enror is one where a node returns erroneous but structurally valid response to the central machine query. Because the response is structurally valid and the central machine may not have access to the per-node data it is not possible to "validate" the response of each node and, instead, the central estimator must be adapted to be robust to such errors.
Outliers or corrupted data. In certain settings the data collection may be distributed in addition the computation. If some of the nodes are drawing samples from an invalid or corrupted data source they may introduce gross outliers to the set of responses (V; distributed PCA example, while most machines draw a sufficient number of samples, minority of them may have only small amount of data available such that the principal eigenspaces of the local empirical covariance matrices are too far from the ground truth, and thus violate standard modelling assumptions in distributed learning. Again, robustness to such outlier responses must be a feature of the estimator since they cannot be detected by individual nodes (as they do not have information about the global problem).
[m]]. Similarly, in the
Adversarial responses. In some settings, a subset of nodes may be compromised by an adversary who wishes to influence the central solution by crafting and returning malicious Vi. In fact, the adversarial nodes may be collaborating when constructing their responses. Since the central node does not get to see all the data it cannot validate responses or directly detect adversaries. Therefore, the estimator itself must be adapted be robust to collections of responses designed to push the solution in specific directions.
The main contribution of our paper is a communication-efficii algorithm that is robust to node corruptions (as outlined above) for the distributed eigenspace estimation problem. We note that our corruption model is similar to so-called Byzantine failures [25] in distributed systems.
1.1 Related work
Distributed eigenspace estimation. The problem of distributed eigenspace estimation has been well-studied in the absence of malicious noise. One of the challenges in the distributed setting is aggregating local solutions in the presence of symmetry: for example. if v is an eigenvector of A, both Iv are valid solutions our problem. Various works deal with such symmetries in different ways; in the algorithms of [5, 18], the central node averages the spectral projectors of the local eigenspaces, and performs an eigendecomposition of the resulting average to approximate the principal eigenspace. This approach is similar to the algorithms of [3, 11, 26], although the latter works focus on distributed low-rank approximations and do not address the issuc of approximating the principal eigenspace directly. Another standard approach is for the central server to aggregate local solutions after an alignment step designed to remove the orthogonal ambiguity [10, 17, 21] (see also [7] for the non- distributed setting). Indeed, our work builds the two-stage algorithm presented and analyzed in [10] for the non-robust setting. Finally, we briefly mention a recent line of work [12, 21] that adapts the shift-are and--eer--- invert preconditioning framework [20] to the distributed setting; however, the latter approach leads to algorithms that require multiple rounds of communication.
Robust PCA. The literature contains a number of different formulations for robust principal component analysis. The seminal work of Candés al. [9] formulated robust PCA as the task of separating an observed matrix Y E Rdxd into a low-rank and sparse component - a slightly different problem from that considered in this paper. Xu et al. [34] considered the problem of approximating a low-dimensional distribution from a set of n i.i.d. samples, a constant fraction of which have been individually corrupted by gross outliers. Follow-up works focused on high- nigh-dimensional sparse robust
estimation and applications to sparse robust PCA [2. 15]. However, communication-cfficco PCA appears be overlooked. A notable exception is the sketch-based algorithm of [30], although the assumptions therein depart significantly from our setting. Another relevant line of work is that of Byzantine- robust distributed learning (typically focusing on distributed gradient descent); see, e.g.. [1, 6, 8, 13, 14, 24, 29, 35] as well as the survey [23]. In these works, an iterative algorithm distributed across machines that send individual updates to a central server, which combines them using robust aggregation procedure (e.g., the geometric median [29]). Such works are more general in scope, but typically lead to estimators that require multiple rounds of communication. For minimization of strongly convex quadratics, [35] proposes a ohe-shot algorithm employing a robust
2

---

aggregation scheme. However, this special case departs from our setting as their underlying problem convex and solved under the assumption that solutions are unique.
Notation
We let gØ-1 denote the unit sphere in d dimensions. We write ||||| == V(A, A) and |||||2 == sup Axil2 for the Frobenius and spectral norms of a matrix A E Ruxd We write On for the set of n x matrices with orthonormal columns and O, 0,,-- Given U, V E On.r we write
= VV
for their Eg - Eg subspace distance and Bdist (U:r) for the scaled unit ball centered at U: B(Urr) = (V Car dist(U, V) r).
Finally, we the notation A A B indicate that A s cB for dimension-indeeeedden constant <> and Bf A B and B S simultaneously.
2 Robust distributed eigenspace estimation
We now formally introduce the problem setting. particular, we assume there exists an unknown symmetric matrix A with spectral decomposition
A VAVT +VIALVI Ve On.ri A = diag (ia)((), A = diag (iag(( (2)
assuming a nonincreasing ordering on the eigenvalues:
(A) 2 2 (A) > Ar+1 ... Aa(A).
Our goal is approximate the principal r-dimensional eigenspace V = span(V) (V) of A given m machines, each of which observes a local version A; of A, communicating with a central coordinator. We assume that m is even for simplicity. When queried for response, machine responds either with an eigenvector matrix spanning the principal eigenspace of the local matrix A,, or with an arbitrary r matrix with orthonormal columns. The latter case corresponds so-called compromised machines. In contrast, prior work [10, 18] assumes that every machine responds truthfully.
Assumption 1 (Corruption model). There exists constant E (0, 1/2) and an index set Ibad C [m] with Zead /m S a such that the following holds: all nodes & Tbad observe symmetric matrix A; E Rdddd Moreover, when queried for response, every node returns
Vi i [m] Ibad,
Vi = 1 E Inad:
(3)
Qi
where the columns of V; E Os.r span the principal r-dimensional eigenspace of A; and Qi Od,r is an arbitrary d x r matrix with orthonormal columns.
For notational convenience, also define the set of "good" responses:
Igood = [m] Ibad, with
[Zgood (1 a)m.
(4)
Furthermore, we require the principal eigenspace of A to be sufficiently separated from its complement and that the local errors E, == A; A are not too large.
Assumption 2. There is constant > 0 such that the following hold:
1. (Gap) The matrix A has a nontrivial eigengap:
(A) = Xr - Ar+1
(5)
2. (Approximation) For all i Igood, the local observations satisfy:
|| A - 8, (A)
(6)
8
3

---

The problem admits a natural proxy of difficulty in the form of the normalized inverse eigengap k:
||Al|2
(A)
(Normalized inverse eigengap)
(A) (A) x
Our algorithm for the robust distributed eigenspace estimation problem is outlined in Algorithm which is essentially robust version of the Procrustes fixing algorithm from [10]. The latter (non- robust) algorithm operates as follows: first, every machine i computes its local eigenvector matrix V, and broadcasts it to the central server. Because invariant subspaces do not admit unique representa- tions, naively averaging these estimates can fail to reduce the approximation error further. Instead, the algorithm of [10] first picks one of the local solutions (say Vi) reference and "aligns" every other solution with by solving a so-called Procrustes problem:
Z == argmin ||VU VillF i= 2 m..
(8)
Ueeo,
After the alignment step (8), the solution of which is available closed form via the SVD [22], the central coordinator computes and returns the empirical average (1/m) E V.Z.
2.1 Technical challenges and main result
To robustify the algorithm described above against node failures, we need the following ingredients:
Reference estimation. In the presence of corruptions one must guard against the possibility of choosing an outlier reference solution (which would render the alignment step (8) useless). The first step of our algorithm robustly determines a reference guaranteed to have nontrivial alignment with the ground truth (Algorithm 2).
Solution aggregation. With the robust reference at hand, the next step of the algorithm aligns other local solutions with it. However, since some of the solutions are outliers, use robust mean estimation algorithm in the last step of Algorithm to compute the empirical average only over inliers (and possible "benign" outliers) with high probability.
Combining the above ingredients requires working around additional technical challenges. The first challenge is showing that averaging over inliers that have been aligned with Vies is equivalent (up to small error) to averaging over inliers that have been aligned with the ground truth V. To do so, we leverage auth-independence result from [33] to view the aligned estimates the eigenvectors arising from a carefully chosen sequence of perturbations to the unknown matrix (Lemma 1).
After aligning local estimates, we approximate the empirical mean over inliers with spectral filtering algorithm. Existing analyses of that algorithm focus on vector-valued inputs and lead to error bounds in the Euclidean norm (or other vector norms, see [32]). Invoking these error bounds in a black-box fashion for matrix-valued inputs (by flattening every eigenvector matrix to a (dr) -dimensional vector) has multiple drawbacks. On one hand, it leads to unnatural scaling as the final result depends on the empirical covariance over flattened inputs. On the other hand, the resulting eтror bounds are with respect to the Frobenius norm, while the spectral norm is standard error measure in eigenspace estimation. To avoid this, we modify the iterative filtering algorithm so that inputs are not flattened and obtain error bounds with respect the spectral norm (3).
We analyze each ingredient of Algorithm separately, Sections 2.2 to 2.4; all proofs appear in the supplementary material. Our analysis is almost completely deterministic: indeed, the only source of randomness is the filtering algorithm used the final stage (Algorithm 5).
Algorithm Robust distributed eigenspace estimation
Input: responses { corruption fraction a, failure prob. p, error parameter w.
V = RobustReffr RebusstReferrmmceEssimtttoor (V,,..., Vm).
D Algorithm 2; Section 2.2
: ProcrustesFixiing (V,,.. .., Vm Vrot)
Algorithm 3; Section 2.3
V = Adaptivefilter Vm w. (,
Algorithm 5; Section 2.4
return

---

Our main theorem on the performance of Algorithm 1 follows below. The result is first stated for inputs from generic eigenspace estimation problem. In Section 3, we apply black-bon fashion to specialize its results for distributed PCA.
Theorem 1.
Lel Assumptions
and hold and suppose that the corruption level a satisfies
6log(1/p) 1
p = a
m
12'
For fixed failure probability p and error parameter w, Algorithm 1 returns V E Rdxr satisfying:
dist(V V)
Σ A
A
+
k²
||A All2
2
p max (w, o²)
Igood|
gooo
8
iEIyood
ie Tgodd
Erobua
Exracl
Brigh
(10)
with probability at least 1 log (%/w) P. Moreover, the variance o² satisfies
0²
-VyT - VVT +2.
V iE
Σ
(11)
Igood
Igood
LE I
Remark 1 (Error bound interpretation). The error bound (10) decomposes naturally into three terms that can be controlled individually in applications. The first term, Eoracle corresponds to an oracle estimator that approximates V via the principal eigenspace of 1/14gnal LieIgne A. The second term, Erigh, represents high-order errors that occur as a result of the alignment step in Algorithm 3 that are dominated by Eoracle in "typical" situations. Finally, the term Erobust quantifies the effect of outliers, vanishing as the fraction of corrupted nodes a 4 O. We comment on the scaling of Erobust relative to the error of the non-robust algorithm in the context of distributed PCA in Section 3.
2.2 The robust reference estimator
This section focuses on the analysis of Algorithm 2, which yields the robust reference estimator Veef used to remove the orthogonal ambiguity from local solutions. We note that the construction of the estimator dates back to the seminal work of Nemirovski and Yudin [28].
Algorithm 2 RobbuttteeferrreccEeettttttootro Y.)
for i 1, ... m do
E = min {r 2 0 [Bai (Y;r) (X) 7
return Y.,, where i, = argminge(m] E3
Remark 2. The quantities e; in Algorithm 2 be found in time O(m²dr²) by first computing rj == dY, Y,Y,, Y,),for all j # and setting S; == median( (ari(nn(())))))) yzs)-
Note that even though Vief could be chosen among some of the compromised samples, its construction ensures that inherits the accuracy of the majority of the responses.
Proposition (Robust reference estimator). Given sample (Y,...., Ym where Y; Oa, and Hi E [m] dist(Y,, V) < =}1 > f/r a fixed > 0, Algorithm outputs Y., satisfying
dist(Y,, V) 3e.
(12)
2.3 The ProcrustesFixing algorithm
In this section, we formally introduce the Procrustes-fiine procedure and show that properly aligns all the non-compromised responses given the reference solution described in Section 2.2. The procedure is described in Algorithm 3; it accepts a set x matrices with orthonormal columns as well as reference matrix Yre of the same shape.
The work [10] provides an error bound for the ProcrustesFixing algorithm under idealized conditions; namely, that the reference solution is equal to the ground truth V.
5

---

Algorithm 3 ProcrustesFixing(V
Ym Yret)
for i I,..., do
Y, = Y,Z where
: argmin |YZ Yeefle
Procrustes alignment
return (Y) / [m]}
Theorem 2 (Theorem 2 in [10], Let Assumption 2 hold and let
where (Viies ProcrusteFFixnn(MMeeee V), Igood.
S
Then the following bound holds:
1 S
V| v
|4 All +
Σ A. EES
(13)
82 |
While the setting of Theorem 2 is idealized, when the reference chosen by Algorithm 2 is sufficiently close to one would expect that the aligned estimates are not far from their ideal version. The next Lemma shows that aligning the local solutions with Vief is equivalent to aligning with the ground truth V, up higher-order errors.
Lemma 1. Let V; E Oa.r spun the principal r r-dimensional eigenspuce of the matrix A; and let V E Oar span the principal r-dimensional invariant subspuce of A. Suppose that there Vref E Od.r satisfying dist dist(Vreff V) = < 6r(A)/s, and define the sets of aligned estimates
Videal
V4 argmin [V, Vllp Viam = V, argmin VVZ Vierlpp- ZEO,
ZEO,
Then for any Igood the following holds:
Videal
V.oor
S
1
max {IIA;
(14)
82
Putting everything together, we arrive at a deterministic characterization the error attained by the empirical average over any subset of responses that come from non-compromised nodes and have been aligned with the robust reference estimator. Note that this characterization does not immediately translate algorithm, since the of compromised nodes is not known a-priori.
Proposition (Error of clean samples). Let Vref be the output of Algorithm 2 given inputs Vi.... Pin. For any index set 5 Igood and E S, define
Veair = V4 argmin
V,2 Veetllp
Videal = V; arrgmn VV2 Vlle-
ZEO
ZEO.
Suppose that dist(V, Viet) = < (A)/s.
Then the following bound holds:
cor
V
S
max (11,--A)) - A Σ
1412 6²)
+
1
Σ
A;
(15)
S
S
S
IES
iES
iES
2
Proof. From the triangle inequality, Lemma and Theorem 2 it follows that
yeor
Veor
Videall
Vrideal
V
|S|
|
iES
2
2
vcor Videal
+
V
Videal
S
2
iES
max (IIA; Alla ||A1|2
Σ
A,
A
82
S
S
1E
1ES

---

2.4 Analysis of robust mean estimation
We now analyze the last phase the algorithm, which approximates V using the robust mean of the aligned samples. The mean estimation procedure used is the randomized iterative filtering method shown in Algorithm 4, which is an appropriate modification of the spectral filtering algorithm from the robust statistics literature for matrix-valued inputs. Its analysis is available in the Appendix, while Theorem below summarizes guarantees.
Algorithm 4 Filter(S := (Xi), I..... Aub)
Compute empirical mean and covariance:
Os = S iES
X
Es: =
Σ(x, 0s) - -Os)
|5|
iES
Compute leading eigenpair (A, of Es. if < 18Aub then
return 0s
else
Compute outlier scores T; == (X; 0s) 0s) for u S. Sample Z from S following P (Z = X;) = T1
Eses
return Filter(S \ {2), Aub)
Theorem 3. Suppose Go C [m]] and that the corruption level a and failure probability p satisfy 6log(1/p)
1
<
12 and |Gol (1-a)mm.
(16)
m
Moreover, let Eg. = [Gol Eiec, -
AG.) T where IG. =
(Gol EiEGo X and fix
Aub 2 |EGolle llz Then Algorithm 4 invoked with { and Aub returns an estimate Ox satisfying
218 (10--111xx), xx111
(a+ 4log(1/p)
1/2
- Σ
SP.
(17)
Go
tEGo
Remark 3. The upper bound a < 1/12 appears to be a proof artifact and could likely be improved by optimizing choices of constants in the proof of Theorem 3. Numerical evidence in Section 3.1 suggests that the breakdown point of Algorithm 4 is closer to the natural limit 1/2
The error in (17) scales with the upper bound Aub, which may be far from the "optimal" ||CG, lla. We describe an adaptive version of Algorithm 4 that achieves this logarithmic additional cost. Indeed, suppose an upper bound on a is available and the unknown parameter ||Eooll llz lies in an interval [Διb. Aub]. We construct a search grid 9 as follows:
g
22 j
Jhi)) ti [log2 (Ab)) Jmi [log)(Aub)]]
(18)
We are now good shape to describe our estimator. To simplify notation, we define the error proxy
f():p, = 18V5A a+ 4log(1/p)) 1/2
(19)
Our estimator, 0z. implemented in Alg. and defined as: 0g where î min (A e ||0x - 1x1 S f(x:p. S(N:p, VX (G))), (20)
Algorithm 5 AdaptiveFilterr$ (Xil Aubs Alb. P. ())
Set up search grid: ji [log2 >bal, Ini [ogg dubl.
for j = Jhi....,.jj.. do 02 FSlter((S,@) (S,2))
Algorithm 4
3k > j such that |00z 0z f(2/: p(2h:pp0) then
> f defined in (19)
return 025+1
return 824

---

If ||EG,12 E Dib, Aubl, the estimator attains the optimal enror up to constant while the success probability degrades only logarithmically, shown by the following Proposition.
Proposition 3. If Go. p. and satify (16) and |Ecolle Aub, the estimator 0x from (20) satisfies
02
1
Σ
xx111
S 1 max {1l , dbb (a+ 4log(1/p) 1/2
Go
iEGo
with probability at least logg (Nut/>e) p.
2.5 Proof sketch of main theorem
We briefly sketch the proof Theorem here. We decompose
dist (V.V)
V) S V Vil2 -
Σ V r/ TE
Igood
Igood
ic iE
A
The error A can be directly controlled by applying Proposition 3 with Gn Igood combined with the fact that the spectral norm of the matrix EIgeo admits the upper bound in (21); we refer the reader to the supplement for complete derivation.
I 112
Σ HE
V.V - VVT
+
Σ V,
V.
(21)
Igood
goood
SEZgood
Finally, we control the error A2 by invoking Proposition 2 with S Igood, since
VÚ = V; argmin
V Vret lp. for all E Igood-
Zec
Combining the resulting upper bounds yields the error in Theorem 1.
Remark 4. Both of the terms in (21) typically small and can be directly controlled in concrete
applications such as distributed PCA. Moreover, while the bound (21) is not directly computable, it is immediate that || 122 < and thus may initialize Algorithm 5 with Xub O(1) in the absence of a finer upper bound.
Robust distributed PCA
In this section, specialize the results of Section robust distributed PCA for subgaussian distributions. We first formalize the sampling model for the problem.
Assumption 3 (Subgaussian data). Every machine Igood draws (x in fj=1
iid P, where P
is zero-mean, subgaussian distribution with covariance matrix A == Ex-p [XX"], and forms
A = プド= x (x
Our main theorem follows directly from Theorem I and control of EEgena ll under Assumption 3. Theorem 4. Let Assumptions hold and suppose that n 2 x² (r- + log(mn/p)) and a, m and p satisfy (9). Then Algorithm 1 initialized with w = 7/mm returns a V satisfying
log(1/p) m
r(r. + +lg(n))
(1-a)mn + + r (r. + log(mn log /
dist(V (esttV,o V) S
a
=VV
(22)
with probability at least - 2/n- Here, r. = Tr (A) || and ø is given by
= r(r, + log(n))
max 2 VF.KA) n4.
+
a)mn
When x 1. high-order terms in Theorem 4 can be discarded and we arrive at the following:

---

Corollary 1. Assume that the conditions of Theorem 4 hold and K x 1. Then:
(ist(V.V) Va log(log(mn)/p) [r(r- + log(n))
1/4
r(r. + log(n))
+
m
or a)mm
a)mm
with probability at least - 2/n- p.
We briefly compare the error of Algorithm to that its non-robust counterpart from [10] when & x 1.
The latter algorithm returns an estimate /nonrobust satisfying dist((Vnnnrbbuus V) = Ô (0 /r./mm)
Ignoring the / factors, which are likely an artifact of our proof, our algorithm also introduces an additive error of the order O % (rrt/mn)//4) Note that for constant absolute number of corruptions a x 1/m, this additive factor scales as
T. 1/4
1/4
(mm))
1
mn
mm5
If mn and are comparable, this is similar to the error of the non-robust algorithm up to an (r/r,) 1//4 factor. Therefore, the performance of Algorithm 1 degrades gracefully as function of the corruption level under not too restrictive assumptions on the ratio m/n.
3.1 Numerical study
We provide brief numerical illustration of the performance of Algorithm on data sampled from an unknown Gaussian distribution D == (0,, VAVT + V[)A where [V Vi] E Oa is a random
d x d orthogonal matrix and A, A are generated according the following model:
A A= Ir: (Ai)as = - 5ym', -......,,-3 d-,, where 7= 1 E (0,
(23)
We simulate adversary by replacing the first [am] responses by the same Vadv Od,r, chosen be near-orthogonal to V. We fix the gap 5 = 0.25 throughout. We compare Alg. (labelled Robust in our plots) against two baselines: the algorithm from [10] (labelled Naive). which corresponds to Alg. 3 using the first response which is al always corrupted our experiment - as the reference followed by naive averaging: and version of Alg. without the robust mean estimation step (labelled Procrustes). Our implementation always removes the sample with the largest outlier score in each step of Alg. 4 and uses simplified error proxy f(A; == Vā instead of (19) in Alg. 5.
Our experiment is illustrated in Figure 1. Clearly, the baseline methods break down in the presence of coruptiinn, yielding solutions nearly orthogonal to V as a approaches 1/2. In contrast, the error of Alg. degrades gracefully with We note that our algorithm yields nontrivial solution when almost half of the measurements are corrupted (a = 45%), in line with intuition suggesting that 0+, 1/2 is natural breakdown point for outlier-robust algorithms.
Haive Frocrustes
Kaive Procrustes
0.8
Robuat
0.8
Robuat
dia v)
0.6
0.4
0.1
0.2
0.2
0
0.1 0.2
0.3
0.4
0.1
0.2
0.3
0.4
a
Figure 1: Robust distributed PCA with m = 150, 50r, r, = 2r, and 5 under Model (23). We report the mean subspace distance one standard deviation over 10 independent runs for subspace dimension = 5 (left) and 10 (right). In addition, we study the effect of the number of per-machine samples and total number of machines m in distributed PCA. We r = 5, r. 2r, K 5 and 5 0.25 and experiment with {0.25, 0.45).
n) (322,2) 5, 5,...,10)...... (m, n) {(2,, 128) 4 ......9.. .).

---

The results can be found in Fig. 2 and are consistent with our theory: for fixed m, a small number of samples per machine leads to inaccurate local solutions and inaccurate final estimates for all variants, while increasing leads to decrease in error for all configurations. On the other hand, the robust algorithm produces good estimates for all attempted values of m after fixing a sufficiently large sample size and increasing m only decreases the error for the robust variant. Finally, we observe that the error of the non-robust variants plateaus since the corruption fraction a is bounded away from zero.
0.25
0.15
dist V)
0.6
0.6
0.4
0.2
0.2
Naive
Procruatea
Procristad Robust
Robust
2
28
27
2
2P
200
2
2
2
2
2
0.25
0.45
Naive
Haiva Procrustes Robust
Procrustes
Robuct
0.8
dist(V, ())
0.6
0.14
0.2
24
25
2
27
24
26
27
Figure 2: Top: Effect of sample size n for fixed number of machines m 32, Bottom: Effect of number of machines m for fixed sample size 128.
4 Discussion
We presented a communication-efficcn algorithm for distributed eigenspace estimation that is robust to 1/12 fraction of nodes returning structurally valid but otherwise potentially adversarial responses. Numerical evidence suggests its breakdown point is closer to the (optimal) a. = 1/2, which might be achievable by an improved analysis of the filtering procedure in Alg 4. Our adaptive version of the filtering procedure in Alg. trades off knowledge of (an upper bound on) the corruption level a with the need for tight bound on | ll2. Alternatively, one can design version of Algorithm that is adaptive to the corruption level a using a similar construction that evaluates the error proxy f(x p, a)) for different values of and fixed À |EIgual llz instead.
Acknowledgements.
We thank Jayadev Acharya and Damek Davis for their insightful comments and suggestions. We also thank the anonymous reviewers for invaluable feedback that greatly improved the manuscript.
References
[1] Dan Alistarh, Zeyuan Allen-Zhu and Jerry Li. Byzantine stochastic gradient descent, Advances in Neural Information Processing Systems, 31, 2018.
10

---

[2] Sivaraman Balakrishnan, Simon S. Du, Jerry Li, and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. In Satyen Kale and Ohad Shamir, editors, Pro- ceedings of the 2017 Conference Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 169-212, Amsterdam, Netherlands, 07-10 Jul 2017. PMLR.
[3] Maria Florina Balcan, Yingyu Liang, Le Song, David Woodruff, and Bo Xie. Communication efficient distributed kernel principal component analysis. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, page 725-734, New York, NY, USA, 2016. Association for Computing Machinery.
[4] Marco Barreno, Blaine Nelson, Anthony D. Joseph, and J. D. Tygar. The security of machine learning. Machine Learning, (1)2):221-148, 2010.
[5] Aditya Bhaskara and Pruthuvi Maheshakya Wijewardena. On distributed averaging for stochas- tic k-pea. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'Accé--Buc E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 11026-11035. Curran Associates, Inc., 2019.
[6] Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Guyon, U. Von Luxburg, S. Ben- gio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[7] R. Bro, E. Acar, and Tamara G. Kolda. Resolving the sign ambiguity in the singular value decomposition. Journal of Chemometrics, 22(2):135-140, 2008
[8] Saikiran Bulusu, Prashant Khanduri, Pranay Sharma, and Pramod K. Varshney. On distributed stochastic gradient descent for nonconvex functions in the presence of byzantines. In ICASSP 2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3137-3141, 2020.
[9] Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
[10] Vasileio Charisopoulos, Austin R. Benson, and Anil Damle. Communication-effcieent dis- tributed eigenspace estimation. SIAM Journal on Mathematics of Data Science, 344):1067 2021.
[11] Ting-Li Chen, Dawei D. Chang, Su-Yun Huang, Hung Chen, Chienyao Lin, and Weichung Wang. Integrating multiple random sketches for singular value decomposition, August 2016, 1608.08285.
[12] Xi Chen, Jason D. Lee, He Li, and Yun Yang. Distributed Estimation for Principal Component Analysis: an Enlarged Eigenspace Analysis. arXiv e-prints, page arXiv:2004.02336, April 2020, 2004.02336.
[13] Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1 2017.
[14] Deepesh Data and Suhas Diggavi. Besinttn sgd high dimensions on heterogeneous data. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 2310-2315, 2021.
[15) Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, and Alistair Stewart. Outlier- robust high-dimensional sparse estimation via iterative filtering. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 10689-10700. Curran Associates, Inc., 2019.
[16] Jack Dongarra, Thomas Herault, and Yves Robert. Fault tolerance techniques for high- performance computing. In Fault-tolerance techniques for pirfopperfomancce computing, pages 3-85. Springer, 2015.
11

---

[17]
Noureddine El Karoui and Alexandre d' Aspremont. Second order accurate distributed eigen- vector computation for extremely large matrices. Electron. J. Statist,, 4:1345-1385, 2010.
[18] Jianqing Fan, Dong Wang, Kaizheng Wang, and Ziwei Zhu. Distributed estimation of principal eigenspaces, Ann. Statist., 3706),300,,, 12 2019.
[19] David Fiala, Frank Mueller, Christian Engelmann, Rolf Riesen, Kurt Ferreira, and Ron Brightwell. Detection and correction of silent data corruption for large-scale high-performance computing. In 12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, pages 1-12. IEEE, 2012.
[20] Dan Garber, Elad Hazan, Chi Jin, Sham Kakade, Cameron Musco, Praneeth Netrapalli, and Aaron Sidford. Faster eigenvector computation via shift-and-invert preconditioning. In Maria Florina Balcan and Kilian Q. Weinberger, editors. Proceedings of The 33rd Interna- tional Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2626-26666
New York, New York, USA, 2016. PMLR.
[21] Dan Garber, Ohad Shamir, and Nathan Srebro. Communication-efficee
algorithms for dis- tributed stochastic principal component analysis. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceed- ings of Machine Learning Research, pages 1203-1212. PMLR, 06-11 Aug 2017.
[22] Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, 2nd edition, 2013.
[23] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji. Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Har- chaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi. Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-110 2021.
[24] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on hetero- geneous datasets via bucketing. In International Conference on Learning Representations, 2022.
[25] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, July 1982.
[26] Yingyu Liang, Maria-Florina F Balcan, Vandana Kanchanapally, and David Woodruff. Improved distributed principal component analysis. Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 31 13-3121. Curran Associates, Inc., 2014.
[27] Shubhendu S Mukherjee, Joel Emer, and Steven K Reinhardt. The soft error problem: An architectural perspective. In 1 11th International Symposium Hrigh-Performncce Computer Architecture, pages 243-247, IEEE, 2005.
[28] A. S. Nemirovsky and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley-Intersciencce series in discrete mathematics. Wiley-Intersciencee, 1983.
[29] Krishna Pillutla, Sham M. Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 70:1 142-1154, 2022.
[30] Mostafa Rahmani and George K. Atia. A decentralized approach to robust subspace recovery. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerion), pages 802-807, 2015.
12

---

[31] Daniel A Reed and Jack Dongarra, Exascale computing and big data. Communications of the ACM, 58(7):56- 68, 2015.
[32] Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 Leibniz International Proceedings in Informatics (LIPles), pages 45:1-45:21, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibnizz Zentrum fuer Informatik.
[33] G. W. Stewart. Smooth local bases for perturbed eigenspaces. Technical Report TR-5010, University of Maryland, Institute for Advanced Computer Studies, 2012.
[34] Huan Xu, Constantine Caramanis, and Shie Mannor. Outlier-robust pea: The high-dimensional case. IEEE Transactions on Information Theory, 59(1):546 572, 2013.
[35] Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett. Byzantine- -obbust Dis- tributed Learning: Towards Optimal Statistical Rates, March 2018, 1803.01498.
[36] Zhen Zhang, Chaokun Chang, Haibin Lin, Yida Wang. Raman Arora, and Xin Jin. Is network the bottleneck of distributed training? In Proceedings of the Workshop Network Meets Al & ML, NetAl '20, page 8-13, New York, NY, USA, 2020, Association for Computing Machinery.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "yDJooC-ony", "reviewer": "Reviewer_2GaG", "summary": "The paper develops and analyzes a decentralized algorithm for eigenspace estimation in the presence of compromised nodes. This work extends the work of (Charisopoulos et al. 2021) to the robust setting, i.e., when a fraction of the nodes send faulty responses. The most interesting contribution of the paper is the performance guarantee in the form of an upper bound on the error between the true and estimated space.   ", "questions": "* It would help to clarify where the loosness of the bound is coming from. Is it from the robust mean estimation component? You could probably add some thoughts to the discussion regarding stronger techniques to tighten the bounds. \n* Please make the theorems self-contained by defining the symbols in the statement of the theorem.\n* More numerical results could be added to the supplement.  ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The proof is elegant and very well written. This is a solid paper. \n+ Developing a robust version of the procrustes algorithm is commended given the emergence of robust learning.\n+ The ideas are compelling. In particular, (i) since a fraction of the measurements is corrupted, a reliable reference is constructed to be used for alignment by choosing the index corresponding to the smallest radius of sufficiently large balls around the received sample containing more than half of the machines; (ii) robust mean estimation is adequately used to aggregate the local versions given the presence of outliers.\n+ The different ingredients of the algorithm are analyzed in a nice progression leading to a deterministic analysis, which is then used to give high probability bounds for subgaussian distributions. \n\nWeaknesses (most are minor)\n- While the paper provides performance guarantees, the sufficient condition is loose. It requires the fraction of compromised nodes to be even smaller than 1/12. The numerical results show sustained performance even when half of the nodes are corrupted.   \n- There is non-cited work on communication efficient robust PCA in the distributed setting. This is one example: \n M. Rahmani and G. Atia, “A Decentralized Approach to Robust Subspace Recovery,” Allerton 2015.\nWhile the approaches are different this is relevant and the claim in the Related Work section should be corrected. \n- Some symbols are never defined in the body of the theorem and the reader has to look carefully at the parameters passed to the functions in the algorithms to understand what they represent (examples: p, omega, \\Sigma_G0, ...). \n- The numerical results section is a bit limited and can be improved for further validation. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "tKAb3VfQ1YW", "reviewer": "Reviewer_86Mv", "summary": "Thanks for the rebuttal. It provides some clarity and I have increased my score slightly. However, as can be inferred from the rebuttal, my original assessment of algorithmic and theoretical contribution being quite limited is accurate. The existence of a CVPR paper with an inferior methodology does not warrant acceptance of a paper with limited contribution.\n\nRegarding the spectral norm analysis, as the authors acknowledged, there is a number of papers requiring spectral norm conditions and spectral-norm based analysis. See, e.g.,\n\na) Steinhardt, J., Charikar, M., and Valiant, G. (2017). Resilience:\nA criterion for learning in the presence of arbitrary\noutliers\n\nb) Data, D. and Diggavi, S. (2020). Byzantine-resilient SGD\nin high dimensions on heterogeneous data.\n\nc) Blanchard, P., Guerraoui, R., Stainer, J., et al. (2017). Machine\nlearning with adversaries: Byzantine tolerant gradient\ndescent. In Advances in Neural Information Processing\nSystems\n\nd) Bulusu, S., Khanduri, P., Sharma, P., and Varshney, P. K.\n(2020). On distributed stochastic gradient descent for\nnonconvex functions in the presence of byzantines.\n\nand the references therein and their citations.\n\n-----Original review\nThis paper proposes an algorithm for the problem of eigenspace estimation algorithm for distributed environments with arbitrary node failures. In particular, a Byzantine adversary model is chosen where a fraction of the participants may communicate arbitrary orthogonal matrices to a server where aggregation happens. The paper builds upon the existing work to put together three components that result in the proposed scheme: i) suitable reference selection, ii) alignment, and iii) robust filtering. It is shown the proposed algorithm enjoys a bounded error consisting of three additive error terms.\n\n", "questions": "1. What is novel about putting the three components discussed in Algs 2,3,4? What are the algorithmic and theoretical challenges in doing so?\n2. To me, the interesting part was the robust reference selection method discussed in Algorithm 2. It is stated that this method builds upon [25]. Could you elaborate on this and discuss the similarities and differences?\n3. An iterative refinement method is discussed in [8] to limit the variance stemming from arbitrary reference selection. How does the proposed method without the robust filtering component compare with the iterative refinement method from [8]?", "limitations": "yes.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. A specialized algorithm for robust distributed eigenspace estimation and PCA.\n\nWeakness:\n1. Limited contribution and significance. Although the paper may be technically sound, the contribution seems to be a mere application of three existing components put together in a seemingly non-difficult fashion.\n2. Limited experiments. The impact of changing important parameters such as the number of samples $n$ and number of nodes must be studied. Furthermore, the performance against the centralized solution must be compared and other attach mechanisms must be tested (the latter is important to test the efficacy of the robust reference selection method).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZF4gZOZCxi_", "reviewer": "Reviewer_GRdZ", "summary": "This paper considers a setting where $m$ nodes collaborate via a server to (approximately) compute the eigenspace spanned by the $r$ principal eigenvectors of a matrix $A$. Each node has access to i.i.d. samples of $A$, and the goal is to exchange information among the nodes to compute an estimate of $A$ that is \"better\" than what each node could compute in isolation. The key challenge tackled in the problem is the aspect of *security*: a fraction $\\alpha$ of the nodes is adversarial and can act arbitrarily. The problem then is to still provide meaningful results for the estimation of $A$ that scale gracefully with the corruption fraction $\\alpha$. The authors address this problem by developing a robust distributed eigenspace estimation algorithm that requires only one round of communication; rigorous convergence bounds are also established for this algorithm. ", "questions": "I have no further questions beyond the clarifying questions I posed earlier. ", "limitations": "I do not see any negative societal impacts of this work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I found the paper quite well-written in general; the main algorithmic ideas and proof techniques are explained in a very clear way. My main comments are as follows. \n\n*Strengths*\n- Although adversarially robust distributed optimization/statistical learning has been studied in several prior works, the specific formulation considered in this paper is novel: I have not seen robust mean estimation ideas used in the context of distributed eigenspace estimation before. The analysis of the proposed algorithm is also solid, making the overall approach a meaningful contribution.\n\nThe comments I have are mainly to clarify a few issues, but nothing major. I should also point out here that I am not an expert on eigenspace estimation.\n\n*Comments*\n- Coming back to the aspect of novelty, the contribution of the paper would be further strengthened in my opinion if the authors could articulate more elaborately why their algorithmic ideas/analysis are not subsumed by the numerous prior works on Byzantine-robust distributed optimization. What exactly makes their setting different/challenging? Can't the eigenspace estimation problem also be cast as an optimization problem? What precludes this line of approach?\n\nRight now, the authors mention in passing that the existing works on robust distributed optimization/learning typically employ iterative algorithms that require multiple rounds of communication between the master and the worker nodes. In contrast, their approach requires only one round of communication. If this is the main/only point of departure from existing literature, then it is not too convincing. Indeed, consider the paper *Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates*, Yin et al., 2018 (ref [30] in this paper). The authors in this paper do in fact study a *one-shot* robust distributed learning algorithm that requires just one round of communication with the server right at the very end. Thus, the aspect of communication-efficiency/one-shot communication is by no means unique to the eigenspace estimation problem considered in this work. In this context, I would encourage the authors to clarify distinctions relative to prior work.\n\n- It seems that the authors consider a *batch* setting where each node $i$ already has access to multiple samples of $A$, and has been able to construct an estimate $A_i$ that is not too far off from $A$ (at least line 114 alludes to this). Would the ideas/results in this paper extend naturally to a *streaming/online* setting where nodes acquire samples of $A$ over time, and exchange information immediately via the server to compute instantaneous estimates? The challenge that I foresee here is that initially, even for the good nodes, their estimates $A_i$ may be far off from the ground truth $A$ (since they haven't acquired enough samples yet). Hence, it may be hard to separate adversarial errors from statistical errors. \n\n- In this work, the additional price paid due to adversarial corruption is $O(\\sqrt{\\alpha})$. While such an additive price is in fact unavoidable (based on lower bounds in the robust mean estimation literature), could the dependence on $\\alpha$ be improved if the noise is well behaved? To be more precise, suppose the samples of $A$ seen by the good nodes are perturbed by i.i.d. Gaussian noise. In this case, recent results in the high-dimensional robust mean estimation literature reveal that one can go from $O(\\sqrt{\\alpha})$ to $O({\\alpha})$, in terms of the dependence on the corruption fraction $\\alpha$; see [R1] below. I am wondering if similar conclusions can be drawn for the eigenspace estimation problem considered here.\n\n[R1] *All-in-one robust estimator of the gaussian mean*, Dalalyan and Minasyan, Annals of Statistics, 2022.\n\n- On a final note, is Algorithm 2 and its analysis in Proposition 1 new? How does the analysis compare with that in Ref [25]?\n\n\n----------------------------------------------- **Post Rebuttal**  ---------------------------------------------\n\nI thank the authors for the rebuttal. I have read through the authors' responses to both my questions, and the questions raised by the other Reviewers. I think the authors have done a good job highlighting the non-trivial aspects of both the algorithm design and the analysis. In particular, my own opinion is that an approach **should not be penalized** just because it combines/builds on existing algorithmic ideas. There is considerable credit in piecing together existing ideas in a meaningful way, and providing concrete theoretical statements to back up the developed theory - the paper under review falls in this category. As such, I have increased my score. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V6PqHCsDzx", "reviewer": "Reviewer_z2xR", "summary": "This paper studies distributed PCA. Let A be the matrix of interest. Each machine has access to a local version of A_i, and the goal is to design communication-efficient algorithms to estimate the eigenspace of A. This is a classical problem, and the contribution of this paper falls into a new algorithm that is robust to outliers in A_i. It is shown that the approximation error matches a recent non-robust algorithm up to a certain additive error.", "questions": "See above. In particular, I feel it is a serious technical flaw to have a failure probability = $1/n + \\log(mn)p$, which makes sense only when the problem size stays as a constant.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The term `local matrix' was used in many places but its definition remains unclear. The only example was given at line 23, and a formal restriction was set out in Eq. (6). It is, however, unclear to me when (6) is satisfied under standard assumptions on the clean data.\n\n- Theorem 1: the presentation here is too general to understand the merit. For example, the scaling of $E_{high}$ is unclear. While it can easily be upper bounded by $(\\delta_r / \\delta)^2$, the latter itself is unbounded. Readers have to read 4 more pages to see that it is a vanishing term (under certain conditions).\n\n- Theorem 4 and Corollary 1: it is surprising that the failure probability does not vanish - it even grows with problem size! I guess this is the price paid to make the approximation error diminish, but overall such tradeoff is inherently making the results vacuous.\n\n- The Algorithm 1 seems a sandwich of prior results: step 1 is borrowed from [25], step 2 is from [8], and step 3 (robust mean estimation) has been broadly studied in recent years. So what is the main technical contribution?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept