- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes accelerated optimization methods for the low-rank matrix recovery problem and investigates whether such acceleration extends to non-convex low-rank factorization. Under appropriate constraints on curvature and initialization conditions, the local convergence of the fixed-depth step-size scheduling strategy is proved. Furthermore, we construct a counterexample demonstrating that this strategy can still diverge when using small-scale random initialization, and we propose a method for selecting scheduling parameters based on initialization information. Experiments on synthetic data show that this approach offers superior iteration complexity scaling and optimization performance compared to gradient descent with a constant step size.
Critical strengths
This paper presents a theoretically grounded study on Silver-type acceleration strategies in factorized low-rank recovery. Rather than assuming that acceleration properties from convex optimization can be directly transferred to non-convex factored problems, the study establishes local convergence results and analyzes the behavior of intermediate iterates within each step-size scheduling interval. This contributes to a better understanding of the conditions under which accelerated step-size scheduling can be reliably employed, offering significant theoretical value. Furthermore, the discussion on noisy and anisotropic sensing problems strengthens the connection between this research and statistical recovery tasks.
Critical weaknesses
The format and data of the experimental results need to be carefully checked. In Figure 1, the right-hand panel is identical to the left-hand panel. Meanwhile, the results for the two sets of condition number experiments presented later in Appendix E.1 are inconsistent with each other.
Questions for authors
-
Could you please re-verify the data in the right-hand panel of Figure 1 against the numerical results listed in Appendix E.1, and update the figure accordingly?
-
Does the initialization used in the condition number experiments satisfy the local initialization requirement stipulated by the main convergence theorem? If this has not yet been verified, please clearly distinguish between the empirical convergence observed in the experiments and the scenarios covered by the theoretical guarantees.
-
Could you conduct repeated experiments using multiple independent random seeds and report the variation in the number of iterations required? Furthermore, regarding the matrix sensing experiments, could you explain the limitations of estimating restricted curvature based on a finite number of random probes, and discuss how these estimates influence the experimental results?
6 comments
Official Comment by Authors
Initialization versus the Theoretical Guarantee — Question 2
Does the initialization used in the condition number experiments satisfy the local initialization requirement stipulated by the main convergence theorem? If this has not yet been verified, please clearly distinguish between the empirical convergence observed in the experiments and the scenarios covered by the theoretical guarantees.
The initializations used in Experiment 1 do not satisfy the sufficient initialization bound in Theorem 4.1. However, we observe accelerated convergence even from initializations outside the theoretically certified region.
To further investigate this behavior, we conducted additional experiments varying the initialization perturbation coefficient over , with all other settings held fixed across these runs. For each value of , we repeated the experiments over 10 independent random seeds and measured the number of iterations required to reach a common relative reconstruction error of .
Table 4. Sensitivity of Silver GD to initialization magnitude. Mean ± standard deviation of iteration counts over 10 independent random seeds.
| Perturbation () | ||
|---|---|---|
| 0.1 | 376.2 ± 20.4 | 371.7 ± 15.4 |
| 0.5 | 419.3 ± 34.7 | 394.4 ± 14.1 |
| 1 | 460.8 ± 59.4 | 424.0 ± 22.5 |
| 2 | 526.7 ± 87.0 | 462.0 ± 19.3 |
| 4 | 582.2 ± 78.1 | 531.3 ± 67.0 |
| 8 | 618.3 ± 61.0 | 618.1 ± 21.6 |
All runs successfully reached the target accuracy. Despite an 80-fold increase in the initialization perturbation coefficient, the iteration counts increased only moderately in both settings. These results suggest that the sufficient initialization condition in Theorem 4.1 may be conservative and that Silver GD can exhibit stable convergence over a substantially larger initialization region in practice.
Official Comment by Authors
Random Seeds and Curvature Estimation — Question 3
Could you conduct repeated experiments using multiple independent random seeds and report the variation in the number of iterations required? Furthermore, regarding the matrix sensing experiments, could you explain the limitations of estimating restricted curvature based on a finite number of random probes, and discuss how these estimates influence the experimental results?
Both condition number sweeps have been repeated over 10 seeds, as reported in G1. G2 provides mean and standard deviation for the anisotropic sensing comparisons over 10 seeds and the larger setting over five seeds. The overparameterization comparison in our response to the overparameterization question also reports 10-seed results and explicitly distinguishes unsuccessful runs.
G3 explains the optimistic bias that can arise from finite random probes, its implications for stepsize normalization and depth, and the updated subspace-and-refinement estimator. The latter remains empirical. In the revised manuscript, we explicitly distinguish these estimates from certified curvature bounds; repeated successful runs are reported as empirical evidence of convergence.
Thank you for the comments
We thank the reviewer for the careful checks of the experimental presentation and the suggestions to clarify initialization and curvature estimation.
Figure 1 and Appendix E.1 — Weakness and Question 1
As detailed in G1, the repeated 10-seed experiments give Silver slopes of 0.777 and 0.770 for the sensing- and target-conditioning sweeps, respectively. We have updated both panels and Appendix E.1 together, including the corresponding mean iteration counts and variability.