acceptodds
Under review as a conference paper at ICLR 2027

Provably Communication-Efficient Federated Robust Matrix Completion and PCA

Abstract

Robust low rank matrix completion (LRMC) and PCA find important applications in computer vision, recommender system design, and, most recently, in new approaches to parameter-efficient fine-tuning of large language models (LLMs). In many of these applications, the data is either available in a federated fashion, or it is available centrally, but we need to distribute it in order to speed up computing. In both settings, there is a need for communication-efficient solutions. In this work, we introduce a novel solution approach and prove that it is -times more communication efficient than, and order-wise as fast as, the fastest existing robust LRMC solution, while tolerating the same number of outliers and having comparable sample complexity (order-wise). Here denotes the rank of the unknown low rank matrix to be recovered. Our proposed solution relies on a multi-block generalization of the recently introduced Alternating Gradient Descent and Minimization (AltGDmin) framework, combined with a new application of a mergeable quantile sketching algorithm, KLL, for federated computation of the global row thresholds needed for outlier support estimation. We prove that the resulting federated algorithm converges under the same assumptions, and with the same outlier tolerance and sample complexity, as its centralized counterpart. Experiments on simulated data and on real videos corroborate our claims.

Primary area:
optimization
Keywords:
Robust PCA, Robust matrix completion, Federated learning, Communication efficiency, Quantile sketching

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_85eQOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the authors proposed a communication-efficient federated algorithm for robust matrix completion and PCA. A multi-block alternating gradient descent and minimization framework is combined with mergeable quantile sketches to estimate global thresholds for outlier detection. Theoretical analysis of convergence guarantees is provided. Experimental results on simulated and real-world data demonstrate the effectiveness of the proposed method.

Critical strengths
  1. The proposed method addresses an important distributed recovery problem. Combining generalized alternating gradient descent and minimization with mergeable KLL sketches is well motivated.
  2. The theoretical analysis connects sketch approximation to sparse-error estimation and convergence. The comparison explicitly discusses communication, outlier tolerance, sample complexity, and condition-number dependence.
Critical weaknesses
  1. The communication advantage depends on the number of nodes, rank, sketch capacity, and problem setting. The robust PCA special case does not inherit every stated robust-completion advantage, so practical crossover regimes need careful interpretation.
  2. The real-video examples use fixed rank and corruption parameters, and do not fully establish robustness to rank misspecification, approximately low-rank data, or structured missingness beyond the Bernoulli model.
Questions for authors
  1. Can the convergence analysis be extended to sample reuse, or can experiments quantify the gap between split-sample and reused-sample implementations?
  2. How do total bytes and end-to-end time vary jointly with node count, rank, sketch capacity, and network latency? Please separate robust PCA from robust matrix completion.
  3. How sensitive is the method to misspecified rank and corruption fraction, and how does it perform with approximate low rank, structured outliers, and nonuniform observations?
2 comments
AuthorsOpenReview ↗

Response to Reviewer 85eQ

We thank the reviewer for the positive assessment and the useful questions, and we appreciate the recognition that the method is well motivated and that the analysis explicitly accounts for communication, outlier tolerance, sample complexity, and condition-number dependence.

Q1 (sample reuse vs. splitting). We ran both variants on identical data: the splitting variant implements the analyzed scheme (initialization and every BB-step and UU-step act on a fresh, independently drawn observation set, with every occurrence of pp replaced by the per-update rate), the reuse variant uses one observation set throughout. The two curves coincide up to small fluctuations and reuse is never worse; see samplesplit.jpg at https://anonymous.4open.science/r/rebuttal-FC94/. Sample splitting is for the theoretical guarantee.

W1 + Q2 (how bytes vary with LL, rr, KK; crossover regimes; PCA vs. LRMC). We now measure the transmitted floats directly (table below), and the dependence on LL, rr, KK follows the closed forms in Sec. 2.3 (gradient round nrnr per node; threshold round nKHnKH with K=Θ(Llog⁡L)K=\Theta(L\sqrt{\log L})), which the measured counts match so the crossover regimes are computable:

ddlocal thresh.exact globalKLL (proposed)KLL/exact
10310^3160,000768,041768,0411.00
10410^4160,0006,169,0961,666,5610.27
10510^5160,00060,176,6512,430,4650.04

Against federated factGD the rr-fold advantage is independent of LL: both methods pay the same per-round threshold cost, and we measure a 3.4×3.4\times total communication advantage at matched accuracy; see alt_vs_fact.jpg at https://anonymous.4open.science/r/rebuttal-FC94/. Against local-thresholding baselines the communication advantage requires KH≲rKH\lesssim r; however, local thresholding only works when outliers are (roughly) uniformly distributed across nodes and fails outright when they concentrate on one node (Fig. 1b), at every LL. For robust PCA (p=1p=1) the rr-fold communication advantage does not apply and only the LL-fold outlier-tolerance advantage remains.

W2 + Q3 (misspecified rank and α\alpha; structured outliers; nonuniform observations). New experiment, true r=10r=10, α=0.10\alpha=0.10, every combination run to convergence or stall:

iterations to SDF≤10−6SD_F\le 10^{-6}α^=0.05\hat\alpha=0.05α^=0.10\hat\alpha=0.10α^=0.20\hat\alpha=0.20
r^=5\hat r=5———
r^=10\hat r=1040131— (stall)
r^=20\hat r=201183139771

Underestimating α^\hat\alpha and overestimating r^\hat r the directions in which standard heuristics are harmless. Underestimating the rank fails necessarily (a rank-55 factor cannot represent a rank-1010 subspace; this holds for any method). Overestimating α^\hat\alpha at the exact rank over-trims uncorrupted entries and stalls; even this is rescued by rank headroom (r^=20\hat r=20), at an iteration cost. We also note that our guarantees place no assumption on the outliers beyond the bound on their number: their magnitudes and signs can be arbitrary, and in all our experiments we simulated the hardest federated case all outliers concentrated in the columns of a single node. For the observation model we assume Bernoulli sampling, as does all existing work on provable robust LRMC; extending the guarantees to non-uniform observation patterns is an interesting open question for the field.

Thank the authors for their response, including additional experimental results. I will keep my score.

Reviewer_CZszOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies federated robust matrix completion and PCA under column partitioned data. It develops a three-block generalization of AltGDmin and uses mergeable KLL quantile sketches to approximate the global row thresholds required for sparse corruption estimation. The analysis establishes geometric convergence for the sample-splitting variant and shows that approximate thresholding preserves the centralized recovery conditions up to constants, including under arbitrarily unbalanced column partitions. Synthetic experiments, sketch capacity ablations, and video background-separation examples illustrate the proposed approach.

Critical strengths
  1. The paper is clearly written, with precise terminology and readable explanations of the proposed method and its theoretical results.
  2. The theoretical analysis meaningfully connects quantile approximation errors with recovery guarantees, showing that sketch-based thresholding preserves the centralized recovery conditions up to constants.
Critical weaknesses
  1. Because Corollary 2.1 and Theorem 2.2 depend heavily on the condition number, scaling as κ10\kappa^{10} for samples and κ−8\kappa^{-8} for corruptions, their theoretical guarantees are severely restricted for ill conditioned matrices, leaving their practical impact unexamined empirically.
  2. Because the convergence analysis requires independent fresh sample subsets whereas the implementation reuses all observations, the theoretical guarantees do not directly cover the practical algorithm, leaving the parameter rescaling insufficiently clear given that the thresholding rule and step size continue using pp instead of the subset probability p/(2T)p/(2T).
  3. Because the evaluation primarily reports wall clock convergence on an eight node setup, it lacks systematic comparisons of cumulative communication at matched recovery accuracy across varying node counts and ranks, and incorporating a FactGD baseline with the same KLL thresholding mechanism would help isolate the optimization benefit from the sketching benefit.
Questions for authors
  1. Could the authors clarify which proof steps introduce the κ10\kappa^{10} sample and κ−8\kappa^{-8} corruption dependencies, whether these bounds are loose analytical artifacts, and how the algorithm performs empirically under increasing condition numbers?
  2. Could the authors clarify how the step size and thresholding parameters should be rescaled when switching from the theoretical p/(2T)p/(2T) subset probability to pp, and provide empirical comparisons comparing sample splitting against sample reuse?
  3. Could the authors provide cumulative communication comparisons at matched recovery accuracy across varying node counts and ranks, and clarify whether the method maintains its advantage over a FactGD baseline equipped with the same KLL thresholding mechanism?
3 comments
AuthorsOpenReview ↗

Response to Reviewer CZsz

We thank the reviewer for the positive assessment and the precise technical questions, and we appreciate the recognition that the paper is clearly written and that the analysis meaningfully connects quantile approximation errors with recovery guarantees.

W1/Q1 (origin of the κ\kappa factors; empirical behavior). These factors enter in Corollary 2.1 through the sparse estimation error bound, Lemma A.3, which requires α≲1/(κ8μ2r)\alpha\lesssim 1/(\kappa^8\mu^2 r) and p≥Cμu2κ4r2log⁡d/np\ge C\mu_u^2\kappa^4 r^2\log d/n. The κ8\kappa^8 arises as κ4⋅κ4\kappa^4\cdot\kappa^4: the per-row support bound pays the squared iterate incoherence μu2\mu_u^2 with μu=O(κ2μ)\mu_u=O(\kappa^2\mu) (Lemma A.6), and converting bounds in σmax⁡∗\sigma_{\max}^\ast into targets in σmin⁡∗\sigma_{\min}^\ast pays another κ4\kappa^4; sample splitting then multiplies the sample cost by T=Cκ2log⁡(1/ϵ)T=C\kappa^2\log(1/\epsilon), giving κ10\kappa^{10}. To study the behavior empirically, we ran the algorithm to convergence or stall for each (κ,α)(\kappa,\alpha) pair:

iterations to SDF≤10−6SD_F\le 10^{-6}α=0.01\alpha=0.01α=0.02\alpha=0.02α=0.05\alpha=0.05α=0.10\alpha=0.10α=0.20\alpha=0.20
κ=1\kappa=13030441351847
κ=2\kappa=286891002593412
κ=5\kappa=56056088142540— (stall)

Empirically, the algorithm recovers at α=0.10\alpha=0.10 for every κ\kappa tested, the iteration count grows with κ\kappa at roughly the κ2\kappa^2 rate of the theorem, and increasing corruption slows convergence before causing failure (single stalled cell at κ=5\kappa=5, α=0.2\alpha=0.2).

The κ\kappa-dependence can be provably improved using the scaled GD idea of Tong, Ma, and Chi ("Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent," Journal of Machine Learning Research, 2021): in the UU update, the gradient is right-multiplied by (BB⊤)−1(BB^\top)^{-1} before the GD step, which cancels the factor B⊤B^\top and with it the κ\kappa factors it introduces. Developing and analyzing this scaled multi-block AltGDmin is part of our future work.

W2/Q2 (splitting vs. reuse; parameter rescaling). Rescaling is a one-symbol substitution: pp enters the algorithm only through the step size and the two thresholding levels, and in each of these one simply uses the observation rate that the update actually sees the per-update rate p~=p/(2T+1)\tilde p = p/(2T+1) under sample splitting, and pp under reuse. No other parameter changes and no retuning is needed; our experiment below runs both variants exactly this way. Empirically, we ran both variants on identical data: the splitting variant implements the analyzed scheme (initialization and every BB-step and UU-step act on a fresh, independently drawn observation set), the reuse variant uses one observation set throughout. The two curves coincide up to small fluctuations and reuse is never worse; see samplesplit.jpg at https://anonymous.4open.science/r/rebuttal-FC94/. Sample splitting is for the theoretical guarantee.

W3/Q3 (cumulative communication at matched accuracy; factGD with the same sketch). We implemented exactly the requested baseline: factGD equipped with our KLL thresholding mechanism, so both methods pay the identical per-round threshold cost; see alt_vs_fact.jpg at https://anonymous.4open.science/r/rebuttal-FC94/. To reach SDF≤10−8SD_F\le 10^{-8} on the same instance, Gen-AltGDmin-KLL needs 235235 iterations (1,4431{,}443 MB) versus 790790 iterations (4,8614{,}861 MB) for factGD-KLL: a measured 3.4×3.4\times advantage attributable purely to the LS-based BB-update. The per-iteration costs for other LL and rr follow the closed forms in Sec. 2.3 (gradient nrnr; sketch nKHnKH with K=Θ(Llog⁡L)K=\Theta(L\sqrt{\log L})), which the measured counts match.

Dear Reviewer CZsz,

As the discussion period closes shortly, we would be grateful if you could take a moment to consider it.

With thanks for your time and for the care you put into the review. If your concerns are addressed by our rebuttal, we would be grateful if you would consider revising your score accordingly.

Reviewer_CZszOpenReview ↗

Comments

Thank you for the authors’ response. For W1 and Q1, the authors have provided a fairly thorough explanation and supplemented experiments with different condition numbers and corruption rates to demonstrate the slowdown and stagnation of convergence. This addresses my main concerns. However, the experiments are conducted only with limited values of k, which cannot fully support the theory. For W2 and Q2, the authors elaborated on the settings of parameters such as step size and threshold, so the issues regarding parameters and implementation are largely resolved. Although the authors clarified the applicable scope of the theory, the reuse of samples still lacks solid guarantees. For W3 and Q3, the authors responded to my questions about baseline comparisons, yet the examples are limited. Systematic experiments with different node numbers and ranks are missing, and complexity analysis cannot fully substitute for such experiments. In summary, I will keep my original score.

Reviewer_JSuhOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies the problems of robust low-rank matrix completion and robust PCA, where the goal is to recover a low-rank matrix given either partial or complete access to a noisy version of the matrix. The noise is a sparse matrix and the columns of the entire noisy data is distributed across multiple nodes, though this choice is arbitrary as the problem is symmetric. The authors propose an adaptation of AltGDmin, which like its moniker suggests, alternatively applies gradient descent to minimize the loss based on previously fixed left and right low-rank factors. To reduce the overall communication of the distributed protocol, the paper considers mergeable sketches for quantile estimation and in particular, the KLL sketch. Convergence rates are then analyzed, given assumptions on the incoherence and sparsity. Finally, the paper provides experiments on synthetic data.

Critical strengths
  1. Theoretical analysis with improved bounds on the computation cost, the communication cost, and the outlier tolerance.
  2. Robust matrix completion and PCA are well-motivated problems with strong connections to the ML community
Critical weaknesses
  1. The current presentation of the paper, especially the appendix, is perhaps well-below the conference standard. For example, theoretical proofs should in general have more content beyond blocks of calculations/algorithms. The model is not formally defined (not just the federated setting, but also what exactly is the model for computation cost, communication cost such as broadcast or point-to-point). There is a line that extends beyond the page margins.
  2. The technical novelties of the paper are not clearly described. For example, it is stated that one of the technical novelties is a careful multi-block extension of simple AltGDMin to handle the three-block structure of this problem, but it is not clear what the extent of the technical novelties in the actual extension are. Similarly, is the novelty the observation that a quantile sketching algorithm suffices or are there further technical challenges? My understanding is that there have been subsequent improvements to the KLL algorithm, why not use of those?
  3. The experiment in the main body is for synthetic data. There seems to be an experiment on a real-world dataset in the appendix, but there is only a single baseline (FactGD) and it is not sufficiently extensive to argue practicality.
Questions for authors

See above.

3 comments
AuthorsOpenReview ↗

Response to Reviewer JSuh

We thank the reviewer for their time, and we appreciate the strengths identified: the improved bounds on computation, communication, and outlier tolerance, and the strong motivation of the problems. We respectfully believe that most of the requested items are already in the paper; we give precise pointers below.

W1 — "the model is not formally defined." The federated model is defined in the "Federation" paragraph of Sec. 1.1: LL nodes, a column partition S1,S2,…,SLS_1, S_2, \ldots, S_L of [d][d] fixed by data ownership, node ℓ\ell observing the column submatrix Y(ℓ)Y_{(\ell)}. The communication structure is described in the federated algorithm section (Sec. 2.3) and in the theorem: each iteration, every node uploads its gradient (nrnr floats) and nn row sketches (≤KH\le KH floats each) to the center, which broadcasts UU and the nn row thresholds back; the theorem's cost display itemizes these per-node upload and broadcast costs, and computation cost counts floating-point operations per node. All communication is node-to-center and center-to-nodes (star topology); we will state this explicitly in one sentence in the final version.

W1 — "proofs should have more content beyond blocks of calculations." Sec. 3 is a complete prose outline of the proof: it walks through the induction claim and each of the BB, SS, and UU update analyses, states why each step is needed and which lemma delivers it, and explains the two new ingredients (the cross-term induction hypothesis and the direct product bound) before any calculation. The appendix is calculation-dense given that outline, which we believe is the appropriate division between main text and appendix.

W2 — "what is the extent of the technical novelty?" This is discussed in the Novelty subsection of the Contributions (Sec. 1.3); we also note that Reviewer 1YzR identifies the multi-block extension as a "meaningful methodological contribution" whose analysis "addresses nontrivial challenges," and Reviewer CZsz highlights that "the theoretical analysis meaningfully connects quantile approximation errors with recovery guarantees." We summarize the technical content. (i) Three-block extension: standard two-block AltGDmin cannot even be initialized here with UU initialized first, the unremoved sparse corruption makes the init error too large, because SS has no magnitude bound while UU, BB do. Our scheme initializes SS first, and its analysis requires two ingredients absent from all prior AltGDmin/factGD work: an induction that carries the cross-term bound ∥U⊤(S−S∗)∥F\Vert U^\top(S-S^\ast)\Vert_F alongside the subspace error, and a direct product bound on (ΠΦ(S+−S∗))B⊤(\Pi_\Phi(S^+-S^*))B^\top via per-row support counts times column incoherence rather than operator norms. These yield a constant thresholding parameter and constant step size the source of the rr-fold iteration gain. (ii) Sketching: The merged sketch over per-node top-candidate sets answers rank queries only within the union of those sets, not within the full row; showing the union's order statistics agree with the full row's above the threshold rank, with a two-sided guarantee, is where the technical work lies. (iii) Why KLL and not its successors: the proof needs mergeability and an all-quantiles guarantee; later variants improve constants but not these properties.

W3 — experiments. We have carried out new experiments: measured communication in transmitted floats, including a factGD baseline equipped with our own sketch 3.4×3.4\times less communication at matched accuracy, see alt_vs_fact.jpg at https://anonymous.4open.science/r/rebuttal-FC94/ — a sample-splitting vs. reuse study (samplesplit.jpg, same link), a condition-number/corruption grid (see response to Reviewer 1YzR), and an input misspecification study (see response to Reviewer 85eQ). We agree the real-data study is modest; the contribution of the paper is theoretical.

Given that the model definitions and the prose proof outline the reviewer asks for are present in the submission (Secs. 1.1, 2.3, 3), we would be grateful if the reviewer could point to any specific remaining gap, which we will gladly address.

Dear Reviewer JSuh,

As the discussion period closes shortly, we would be grateful if you could take a moment to consider it.

With thanks for your time and for the care you put into the review. If your concerns are addressed by our rebuttal, we would be grateful if you would consider revising your score accordingly.

Thank you for the response.

My main concern is that while the experimental evaluations have been strengthened, my impression (which the authors also stated) is that the primary contribution of the paper is theoretical, but the current version of the paper does not meet the standards of theoretical papers.

W1 — "the model is not formally defined."

I disagree that the federated model is formally defined. For instance, the details provided in the rebuttal such as floating-cost operations (as opposed to bit complexity or the RAM model) are not specified in the paper. I believe the other reviewers also had confusions about form of how the communication is measured. The rebuttal also mentions various aspects of the model being split across multiple sections, which increases the difficulty of understanding this paper.

W1 — "proofs should have more content beyond blocks of calculations."

Additionally, the appendix has substantial problems beyond the density of calculations. Many equations are numbered without future reference and as I previously stated, there are expressions (such as in line 1137) that extend into or past the margins. Although these are simple presentation issues that can be fixed in a fast round of editing, I don't see that a revised version that addresses them.

W2 — "what is the extent of the technical novelty?"

The description in the rebuttal for (i) is clearer than the current version in Section 1.3 because it clarifies which specific ingredients were absent from previous analysis. Unfortunately, while the contribution of (ii) is described as technical work, it is still unclear what the novelty is. For (iii), I believe https://arxiv.org/pdf/2610.18347 handles both mergeability and an all-quantiles guarantee -- is my understanding incorrect?

In any case, my concern is that if the paper is to be framed as a primarily theoretical contribution, a much more thorough technical overview is expected.

On one hand, I recognize that my response is quite late in the rebuttal process and I will defer to the majority if the other reviewers argue that the paper is well-written in the discussion phase. On the other hand, I do not believe an updated version of the PDF has been uploaded with clear changes incorporating the initial reviews.

Reviewer_1YzROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates communication-efficient federated robust low-rank matrix completion (LRMC) and principal component analysis (PCA) in the presence of sparse corruptions and incomplete observations. The authors propose Generalized-AltGDmin-KLL, a federated optimization framework that extends the conventional two-block Alternating Gradient Descent and Minimization (AltGDmin) approach to a multi-block setting involving low-rank factors and sparse outliers. The proposed method combines alternating minimization, gradient-based subspace updates, and mergeable KLL quantile sketches to efficiently approximate global row thresholds without requiring extensive communication between distributed nodes. The paper establishes theoretical convergence guarantees under standard incoherence, random observation, and bounded corruption assumptions. In particular, the authors claim an order-wise rr-fold improvement in communication efficiency over a naive federated extension of factorized gradient descent for robust LRMC, while maintaining comparable computational complexity and outlier tolerance. Experiments on synthetic datasets and real video data are presented to support the theoretical findings.

Critical strengths
  1. Well-motivated problem formulation. Communication-efficient robust matrix recovery is an important problem in distributed machine learning. The paper addresses the challenging combination of missing observations, sparse corruptions, and federated computation.
  2. Meaningful methodological contribution. The extension of AltGDmin from two blocks to a multi-block optimization framework is technically interesting. The proposed update strategy carefully separates sparse corruption estimation, low-rank coefficient minimization, and subspace optimization.
  3. Integration of KLL sketches. The use of mergeable quantile sketches to approximate global row thresholds is an appealing design choice. It avoids the limitations of local threshold estimation while substantially reducing the communication required by exact global thresholding.
  4. Theoretical analysis. The paper provides convergence guarantees for both centralized and federated settings. The analysis addresses nontrivial challenges involving sparse estimation errors, incoherence preservation, and approximate threshold computation.
  5. Support for heterogeneous data partitions. Unlike local-thresholding approaches, the proposed method does not require balanced column partitions. The experiment in Figure 1(b), where several nodes contain only one column, illustrates this advantage.
Critical weaknesses
  1. Both AltGDmin and KLL sketches are established methods. Although their integration into federated robust LRMC is technically meaningful, the paper should more clearly distinguish the genuinely new algorithmic insights from adaptations of existing techniques. In particular, the authors should explain why the proposed multi-block extension is fundamentally different from conventional alternating minimization or block-coordinate optimization frameworks.
  2. The theoretical analysis establishes favorable asymptotic communication complexity, but the empirical evaluation should more directly quantify the actual amount of transmitted data. Reporting total communication volume in bytes, the number of communication rounds, and communication overhead under different network conditions would make the claimed improvements more convincing.
  3. The convergence analysis assumes incoherence, Bernoulli observations, bounded corruption fractions, and sample splitting. These assumptions may not hold in practical federated environments with highly structured missing patterns, correlated outliers, or heterogeneous data distributions. The authors should investigate how sensitive the proposed method is to violations of these assumptions.
Questions for authors
  1. The main theoretical result establishes an rr-fold communication advantage for robust LRMC. Could the authors clarify the parameter regimes in which this improvement remains significant after accounting for KLL sketch communication, initialization, and other communication overheads? In particular, how does the advantage change when LL becomes comparable to or larger than rr?
  2. The experiments emulate federated computation using MATLAB parfor on a single multi-core machine. How would the proposed algorithm perform in a genuinely distributed environment with network latency, limited bandwidth, and heterogeneous computational resources?
  3. Could the authors provide a direct comparison between approximate KLL-based thresholding and exact global thresholding in terms of reconstruction accuracy, convergence rate, and communication volume?
  4. The convergence analysis assumes a specific upper bound on the corruption fraction α\alpha. How does the algorithm behave when the corruption level exceeds this theoretical threshold? Is there a sharp degradation in performance?
  5. The theoretical analysis requires sample splitting, whereas the implementation reuses all available observations. Can the authors provide empirical evidence demonstrating whether this difference affects convergence reliability, particularly under limited observations or high corruption levels?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 1YzR

We thank the reviewer for the careful reading, and we appreciate the strengths identified: the recognition that the multi-block extension is a meaningful methodological contribution, that the analysis addresses nontrivial challenges, and in particular the reviewer's attention to the heterogeneous-partition experiment (Fig. 1b) support for arbitrary partitions is indeed a key differentiator of our method. We have carried out four new experiments; we summarize the ones relevant to your points below.

W2 + Q3 (measure the transmitted data; KLL vs. exact global thresholding). We instrumented all methods to count every transmitted float. Per-iteration communication of AltGDmin with local, exact global, and KLL-based thresholding:

ddlocal thresh.exact globalKLL (proposed)KLL/exact
10310^3160,000768,041768,0411.00
10410^4160,0006,169,0961,666,5610.27
10510^5160,00060,176,6512,430,4650.04

Exact global thresholding grows linearly in dd while the sketch cost is nearly flat (25×25\times less at d=105d=10^5); in accuracy the two are indistinguishable iteration-by-iteration (the sketch perturbs the threshold only by constants, Lemma C.2), and our KLL-thresholded runs reach machine precision (≈10−15\approx 10^{-15}). For cumulative communication at matched accuracy we ran factGD equipped with our own KLL thresholding, so both methods pay the identical per-round threshold cost; see alt_vs_fact.jpg at https://anonymous.4open.science/r/rebuttal-FC94/. To reach SDF≤10−8SD_F\le 10^{-8}, Gen-AltGDmin-KLL needs 235235 iterations (1,4431{,}443 MB) versus 790790 iterations (4,8614{,}861 MB) for factGD-KLL: a measured 3.4×3.4\times advantage attributable purely to the LS-based BB-update.

Q1 (regimes where the rr-fold advantage survives; L≳rL\gtrsim r). Our method retains its rr-fold communication advantage over federated factGD for every LL: factGD also needs global row thresholds, so both methods pay the same per-iteration cost (one gradient round plus one threshold round), and our rr-fold reduction in the number of iterations multiplies the whole of it; alt_vs_fact.jpg (link above) confirms this with both methods given the identical sketch.

In comparison with local-thresholding baselines, the main advantage of our method is outlier tolerance: local thresholding only works when the outliers are (roughly) uniformly distributed across the nodes — an assumption that cannot be guaranteed in a federated setting — and it fails outright when the outliers concentrate on one node (Fig. 1b of the paper), at every LL. Our global (sketch-based) thresholds provide guarantees for arbitrary partitions. In communication, local baselines skip the threshold round and pay just nrnr per iteration, while ours is nr+nKHnr+nKH; our advantage over them thus additionally requires KH≲rKH\lesssim r, i.e., L≲rL\lesssim r up to log factors since K=Θ(Llog⁡L)K=\Theta(L\sqrt{\log L}). We note, however, that every method that is provably correct under arbitrary partitions needs global thresholds, and against all of these our advantages are independent of LL: rr-fold fewer iterations than factGD, and up to 25×25\times less threshold communication than exact global thresholding (table above); the only baselines that become cheaper than us for L≳rL\gtrsim r are ones that fail. The initialization is a one-time cost and does not affect the per-iteration comparison.

Q2 (real network with latency and limited bandwidth). Transmitted bytes and round counts, which we measure above, are network-independent: on any real network, wall-clock time is approximately (rounds ×\times latency) ++ (bytes // bandwidth), so the measured round and byte advantages translate directly and grow with latency.

AuthorsOpenReview ↗

Response to Reviewer 1YzR

Q4 (corruption above the theoretical bound — sharp degradation?). For each (κ,α)(\kappa,\alpha) pair we ran the algorithm to convergence or stall:

iterations to SDF≤10−6SD_F\le 10^{-6}α=0.01\alpha=0.01α=0.02\alpha=0.02α=0.05\alpha=0.05α=0.10\alpha=0.10α=0.20\alpha=0.20
κ=1\kappa=13030441351847
κ=2\kappa=286891002593412
κ=5\kappa=56056088142540— (stall)

Increasing corruption first slows convergence at κ=1\kappa=1, the iteration count grows from 135135 at α=0.10\alpha=0.10 to 18471847 at α=0.20\alpha=0.20, while still recovering to 10−610^{-6} and only then causes failure, in the single hardest cell (κ=5\kappa=5, α=0.2\alpha=0.2). There is no sharp breakdown at the theoretical threshold. The table also shows that the only cost growing with κ\kappa is the iteration count, at roughly the κ2\kappa^2 rate our theorem states.

Q5 (sample splitting vs. reuse). We ran both variants on identical data. The reuse variant uses one observation set at every update; the splitting variant implements the analyzed scheme, with the initialization and every BB-step and UU-step acting on a fresh observation set drawn independently. The two curves coincide up to small fluctuations and reuse is never worse; see samplesplit.jpg at https://anonymous.4open.science/r/rebuttal-FC94/. Sample splitting is for the theoretical guarantee.

W1 (novelty vs. adapting known methods). We note that the reviewer's own Strength 2 describes the multi-block extension as "technically interesting" with an update strategy that "carefully separates" the three estimation tasks, and Reviewer CZsz highlights as a strength that "the theoretical analysis meaningfully connects quantile approximation errors with recovery guarantees." The novelty is indeed in the analysis, not in assembling two known tools; please see our response to Reviewer JSuh (W2), which we summarize: the three-block structure requires a new induction carrying a cross-term bound, and a direct product bound on the sparse error term that yields a constant thresholding parameter and constant step size (the source of the rr-fold gain); on the sketch side, the merged sketch answers rank queries only within the union of the per-node candidate sets, and closing this gap (our union order-preservation argument) is where the technical work lies.

W3 (assumption violations). Our guarantees place no assumption on the outliers beyond the bound on their number: their magnitudes and signs can be arbitrary. In all our experiments we simulated the hardest federated case all outliers concentrated in the columns of a single node. For the observation model we assume Bernoulli sampling, as does all existing work on provable robust LRMC; extending the guarantees to non-uniform observation patterns is an interesting open question for the field. We also carried out an input-misspecification study (see our response to Reviewer 85eQ).

Dear Reviewer 1YzR,

As the discussion period closes shortly, we would be grateful if you could take a moment to consider it.

With thanks for your time and for the care you put into the review. If your concerns are addressed by our rebuttal, we would be grateful if you would consider revising your score accordingly.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Discussion summary (for reviewers and AC convenience)

As we approach the end of the discussion period, we provide a status update on all issues raised. Most issues requested further experiments or clarification and have been resolved. We have provided detailed individual responses to each reviewer, and added four new experiments: one measuring communication, one for sample reuse vs. sample splitting, one for a grid of condition number/corruption and one for input misspecification.

Issues raised by multiple reviewers and all resolved with new experiments:

  • Communication not measured in bytes (1YzR W2/Q3, CZsz W3/Q3, 85eQ Q2): we now track every float communicated. We report per-iteration costs for local, exact-global and KLL thresholding for d=103,104,105d=10^3,10^4,10^5 (KLL transmits 25×25\times less than exact thresholding for d=105d=10^5), total communication at equal accuracy to the baseline algorithm (as requested by Reviewer CZsz), using our own KLL sketch in factGD. We see a 3.4×3.4\times communication improvement (1,4431{,}443 vs. 4,8614{,}861 MB to reach SDF≤10−8SD_F\le 10^{-8}).

  • Sample splitting (analyzed) vs. sample reuse (implemented) (1YzR Q5, CZsz W2/Q2, 85eQ Q1): both were implemented on the same data and the curves are identical. We also see that sample reuse is never worse than sample splitting. Regarding the rescaling requested by Reviewer CZsz, this is only a one-symbol change (the rate of per-update observations), nothing else has changed.

  • Behavior outside the theoretical regime (1YzR W3/Q4, 85eQ W2/Q3): we ran a grid over (κ,α)(\kappa,\alpha) until convergence or stall and saw graceful degradation (convergence degrades prior to failure, a single failure occurs at κ=5\kappa=5, α=0.2\alpha=0.2). We also ran a grid over input misspecification and saw that the behavior of underestimating tolerance and overestimating rank are harmless.

Reviewer CZsz: all three requests were addressed with the requested content. For the κ8\kappa^{8}/κ10\kappa^{10} factors, we provide the lemma (Lemmas A.3 and A.6) that derives the factors and provide an experiment that reveals that the corruption tolerance is far lower than the derived bound and that the number of iterations matches the claimed κ2\kappa^2 scaling. For the sample splitting/rescaling question and experiment, we provide the requested answer and experiment. For the experiment comparing with factGD using the identical sketch we provide the requested experiment.

Reviewer 1YzR: All five questions were addressed individually and each included either a new experiment or an analysis in a specific regime (also including the discussion of L≳rL\gtrsim r in Q1). We believe the answers address the issues and are happy to continue to provide additional feedback if desired.

Reviewer JSuh: The requested content (federated learning model, communication model and a prose sketch of the proof) can be found in the paper in Secs. 1.1, 2.3 and 3 respectively. In our response we provide specific references to the locations of the requested content. We ask the reviewer to point out any remaining issue and are happy to address it.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.