- 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
- The proposed method addresses an important distributed recovery problem. Combining generalized alternating gradient descent and minimization with mergeable KLL sketches is well motivated.
- 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
- 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.
- 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
- Can the convergence analysis be extended to sample reuse, or can experiments quantify the gap between split-sample and reused-sample implementations?
- 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.
- 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
Thank the authors for their response, including additional experimental results. I will keep my score.
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 B-step and U-step act on a fresh, independently drawn observation set, with every occurrence of p 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.jpgat https://anonymous.4open.science/r/rebuttal-FC94/. Sample splitting is for the theoretical guarantee.W1 + Q2 (how bytes vary with L, r, K; crossover regimes; PCA vs. LRMC). We now measure the transmitted floats directly (table below), and the dependence on L, r, K follows the closed forms in Sec. 2.3 (gradient round nr per node; threshold round nKH with K=Θ(LlogL)), which the measured counts match so the crossover regimes are computable:
Against federated factGD the r-fold advantage is independent of L: both methods pay the same per-round threshold cost, and we measure a 3.4× total communication advantage at matched accuracy; see
alt_vs_fact.jpgat https://anonymous.4open.science/r/rebuttal-FC94/. Against local-thresholding baselines the communication advantage requires KH≲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 L. For robust PCA (p=1) the r-fold communication advantage does not apply and only the L-fold outlier-tolerance advantage remains.W2 + Q3 (misspecified rank and α; structured outliers; nonuniform observations). New experiment, true r=10, α=0.10, every combination run to convergence or stall:
Underestimating α^ and overestimating r^ the directions in which standard heuristics are harmless. Underestimating the rank fails necessarily (a rank-5 factor cannot represent a rank-10 subspace; this holds for any method). Overestimating α^ at the exact rank over-trims uncorrupted entries and stalls; even this is rescued by rank headroom (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.