acceptodds
Under review as a conference paper at ICLR 2027

Silver Steps Beyond Convexity: Accelerated Convergence for Low-Rank Matrix Recovery

Abstract

Low-rank matrix recovery problems are often solved through a low-rank factorization, which turns the rank constraint into a nonconvex optimization problem. Recent work has shown that carefully designed Silver stepsize schedules can accelerate gradient descent for convex optimization. In this paper, we study whether this acceleration extends to nonconvex low-rank factorization for matrix recovery from linear measurements. We show that gradient descent with a fixed-depth Silver stepsize schedule achieves an accelerated convergence rate when initialized near a constrained minimizer, while all intermediate iterates remain in its neighborhood despite the occasional large steps in the schedule. We also show that, even in a simple rank-one problem, the same fixed-depth Silver schedule diverges with nonvanishing probability under arbitrarily small Gaussian initialization, demonstrating that the local initialization condition cannot in general be removed. We apply our results to Gaussian matrix sensing and low-rank multivariate regression, and provide numerical experiments that support our theoretical findings.

Primary area:
optimization
Keywords:
Silver schedule, low-rank optimization, matrix sensing, gradient descent

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Ag46OpenReview ↗
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
  1. 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?

  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.

  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?

6 comments
AuthorsOpenReview ↗

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

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?

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.

AuthorsOpenReview ↗

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 c∈0.1,0.5,1,2,4,8c \in \\{0.1,0.5,1,2,4,8\\}, with all other settings held fixed across these runs. For each value of cc, we repeated the experiments over 10 independent random seeds and measured the number of iterations required to reach a common relative reconstruction error of 10−810^{-8}.

Table 4. Sensitivity of Silver GD to initialization magnitude. Mean ± standard deviation of iteration counts over 10 independent random seeds.

Perturbation (cc)κ=16,κX=4\kappa=16,\\ \kappa_X=4κ=4,κX=16\kappa=4,\\ \kappa_X=16
0.1376.2 ± 20.4371.7 ± 15.4
0.5419.3 ± 34.7394.4 ± 14.1
1460.8 ± 59.4424.0 ± 22.5
2526.7 ± 87.0462.0 ± 19.3
4582.2 ± 78.1531.3 ± 67.0
8618.3 ± 61.0618.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.

AuthorsOpenReview ↗

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.

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

The paper analyzes gradient descent with a repeated, fixed-depth Silver stepsize schedule for the balanced low-rank factor objective. Under restricted curvature, a bound on the normal gradient at a rank-rr minimizer, and sufficiently accurate initialization, every block halves the factor error while controlling all intermediate iterates. The resulting local gradient complexity is O(Kθ(1+log⁡(D0/ε)))O(K^{\theta}(1+\log(D_0/\varepsilon))), with θ=log⁡1+22≈0.786\theta=\log_{1+\sqrt{2}}2\approx 0.786, where KK combines measurement conditioning and target-matrix conditioning. A scalar rank-one counterexample gives a nonvanishing divergence probability under arbitrarily small Gaussian initialization for the prescribed depth and normalization. Applications cover isotropic and anisotropic sensing and multivariate regression, with numerical comparisons against constant-step gradient descent.

Critical strengths
  1. The analysis addresses the main obstacle to transferring Silver acceleration to the factorized problem. Quadratic endpoint contraction alone does not ensure that large intermediate steps remain in the local nonconvex basin. The proof handles rotational flat directions, constructs a local convex comparison, and combines a finite-trajectory bound with continuity in the starting point to establish within-block stability (Appendices A–B). This supplies a substantive bridge from the quadratic schedule to local factor convergence.

  2. A precise limitation complements the local guarantee. Theorem 4.2 proves divergence with probability bounded away from zero as the Gaussian initialization scale shrinks, for the depth-6 schedule and normalization prescribed in its scalar instance. The result is specific to that schedule; it does not rule out all Silver variants. Section 4.3 also shows how a sufficiently accurate warm start supplies the singular-value estimates used to choose the schedule. Together these results clarify the scope and implementation of the local guarantee.

Critical weaknesses
  1. The motivation for restricting acceleration to stepsizes alone is insufficient, and the related-work comparison is incomplete. Preserving the factor-gradient direction is a clear algorithmic constraint, but the paper does not establish why this constraint is important for the recovery problems studied. Section 2 already cites ScaledGD and newer preconditioning methods; in suitable settings, ScaledGD removes target-matrix conditioning from the local iteration rate while retaining low per-iteration cost (Tong, Ma, and Chi, 2021). The relevant question is therefore what benefit Silver offers in assumptions, initialization, total computation, or applicability relative to these alternatives. Comparisons only against constant-step GD do not answer this. Several relevant works are also missing: Li and Lin, Provable accelerated gradient method for nonconvex low rank optimization (2020), Xu et al., Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks (2024), and Mishra and Sepulchre, Riemannian preconditioning (2016). These concern accelerated factor methods and geometry-based preconditioning, directly informing the motivation for the chosen restriction. Their settings and assumptions differ, so they do not automatically subsume the theorem, but the missing comparisons leave its incremental significance unclear.

  2. The guarantee is too restricted, and the empirical evidence too limited, to establish a compelling recovery advantage. The theorem requires restricted curvature, a sufficiently small normal gradient at a rank-exact minimizer, and initialization within a certified factor radius scaling as σ1/K\sqrt{\sigma_1}/K. Thus the basin shrinks precisely as conditioning worsens. For the specified one-step spectral initializer, Proposition C.3 gives a sufficient noiseless isotropic sample bound of order r2κX3(d1+d2)log⁡(d1+d2)r^2\kappa_X^3(d_1+d_2)\log(d_1+d_2); Corollary C.6 adds a cubed covariance-condition-number factor in the anisotropic case. These are sufficient guarantees, not necessary sampling requirements, but the paper does not quantify the total cost of entering the Silver basin from a weaker initialization. The divergence theorem concerns a prescribed schedule and does not establish that such restrictive initialization is unavoidable for other methods. Empirically, the conditioning experiment starts from true factors perturbed by an amount proportional to 1/K1/K, Constant GD is not independently tuned, and initialization and curvature probing are excluded from iteration counts. The sensing and regression comparisons are single-instance within each setting, with sensing basin entry uncertified. Both Figure 1 panels also show slopes 0.998 and 0.779, whereas Appendix E.1 reports 0.983 and 0.770 for the target-conditioning sweep. The local acceleration result is technically interesting, but these limitations substantially weaken its end-to-end significance.

Questions for authors
  1. Motivation and alternatives. In what concrete regime is changing only the stepsizes preferable to ScaledGD, other preconditioned methods, or accelerated factor methods? Please compare the relevant assumptions, initialization requirements, conditioning dependence, and total computational cost, and explain how the omitted works identified above affect the positioning of the contribution. Merely preserving the gradient direction does not by itself establish an advantage.

  2. Strength of the guarantee. Do the existing estimates yield a total gradient-complexity bound when a preliminary phase enters the Silver basin from a weaker warm start? How do basin entry, curvature estimation, and the normal-gradient condition affect the resulting conditioning and sample requirements? This would clarify whether the local speedup survives once its prerequisites are included.

  3. Experimental support and reporting. Do existing results establish an advantage over an independently tuned Constant GD baseline or a suitable preconditioned baseline when initialization and curvature-probing costs are included? Please also reconcile the two Figure 1 legends with Appendix E.1. Broader benchmarking would be useful future work; the immediate request is to clarify what the current evidence supports and correct the reporting discrepancy.

3 comments
AuthorsOpenReview ↗

Thank you for the comments

We thank the reviewer for the detailed assessment of the theoretical contribution and its limitations, and for suggesting relevant accelerated and geometry-based methods. The comments have helped us sharpen the motivation and distinguish local iteration gains from total recovery cost.

Motivation, Related Work, and Alternatives — Weakness 1 and Question 1

In what concrete regime is changing only the stepsizes preferable to ScaledGD, other preconditioned methods, or accelerated factor methods? Please compare the relevant assumptions, initialization requirements, conditioning dependence, and total computational cost, and explain how the omitted works identified above affect the positioning of the contribution. Merely preserving the gradient direction does not by itself establish an advantage.

Our contribution is to establish that scalar stepsize scheduling can accelerate ordinary factor-gradient descent locally while controlling intermediate iterates, despite nonconvexity and rotational flat directions. G2 compares the conditioning dependence, assumptions, initialization requirements, and computational costs with existing methods and provides the requested empirical comparisons. In particular, our anisotropic sensing experiments with modest target conditioning show that Silver GD achieves the lowest mean gradient-evaluation counts and running times among the tested methods, including ScaledGD. These results highlight a concrete setting in which stepsize-only acceleration is competitive.

We thank the reviewer for pointing us to Li and Lin (2020), Xu et al. (2024), and Mishra and Sepulchre (2016). We have incorporated these works into the revised Related Work section, clarifying the methodological distinctions between stepsize scheduling, accelerated factor methods, and geometry-based preconditioning.

AuthorsOpenReview ↗

Official Comment by Authors

Basin Entry and Total Complexity — Weakness 2 and Question 2

How do basin entry, curvature estimation, and the normal-gradient condition affect the resulting conditioning and sample requirements? This would clarify whether the local speedup survives once its prerequisites are included.

G4 establishes a PGD-to-Silver guarantee from a weaker warm start, providing an explicit total gradient-evaluation bound that includes the preliminary iterations required for basin entry. Under the stated additional assumptions, this analysis also improves the sufficient isotropic sample dependence from cubic to quadratic in κX\kappa_X. G2 reports running times that include initialization and curvature-estimation costs, while G3 explains the empirical nature of the curvature estimates and their theoretical admissibility conditions. Furthermore, G4 provides an explicit sufficient noise condition for the normal-gradient assumption.

Regarding the divergence theorem, we clarify its significance and scope:

The divergence theorem concerns a prescribed schedule and does not establish that such restrictive initialization is unavoidable for other methods.

Small Gaussian random initialization is a widely studied approach in low-rank matrix recovery. In particular, Soltanolkotabi, Stöger, and Xie (2023) establish recovery guarantees for standard factorized gradient descent from small random initialization in asymmetric matrix sensing, a setting closely related to ours.

Our counterexample shows that, even in a simple rank-one problem with full observation, the prescribed fixed-depth Silver schedule can diverge with nonvanishing probability under arbitrarily small Gaussian initialization. Thus, recovery guarantees for standard GD from small random initialization cannot be straightforwardly extended to the Silver schedule considered in our work.

AuthorsOpenReview ↗

Official Comment by Authors

Experimental Evidence and Reporting — Weakness 2 and Question 3

Please also reconcile the two Figure 1 legends with Appendix E.1. Broader benchmarking would be useful future work; the immediate request is to clarify what the current evidence supports and correct the reporting discrepancy.

We have updated Figure 1 and Appendix E.1 to report consistent results from the repeated experiments, as detailed in G1.

Reviewer_zz5gOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates whether Silver stepsize schedules can accelerate gradient descent for nonconvex low-rank matrix recovery. The authors establish a local convergence guarantee for a fixed-depth Silver schedule, achieving an iteration complexity of O(Kθlog⁡(1/ε))O(K^\theta \log(1/\varepsilon)), where θ≈0.786\theta\approx 0.786, under suitable initialization and restricted curvature conditions. They also construct a rank-one counterexample showing that the same schedule can diverge under arbitrarily small Gaussian initialization. The theoretical results are further applied to Gaussian matrix sensing and low-rank multivariate regression, with numerical experiments illustrating the acceleration over constant-step gradient descent.

Critical strengths
  1. The paper extends Silver stepsize acceleration to nonconvex low-rank matrix factorization and establishes an improved local convergence rate under suitable conditions.

  2. The analysis of intermediate-iterate stability and the rank-one divergence counterexample provide useful insights into the benefits and limitations of Silver stepsize schedules in nonconvex optimization.

Critical weaknesses
  1. The main convergence result requires the initial factors to be sufficiently close to a rank-exact constrained minimizer, with the initialization neighborhood shrinking as the effective condition number increases. Although the authors provide spectral initialization guarantees, the resulting sufficient conditions can be demanding, particularly for ill-conditioned problems. Furthermore, the conditioning experiment directly initializes the factors near the ground-truth solution rather than demonstrating how such an initialization can be obtained in practice. Consequently, the proposed method primarily provides a local acceleration guarantee, while its effectiveness as an end-to-end low-rank recovery algorithm remains less clear.

  2. The experiments mainly compare Silver GD against conventional constant-step GD, without including other relevant accelerated optimization methods, such as Nesterov-type accelerated gradient methods or established preconditioned methods for low-rank recovery. Moreover, the experiments are conducted on relatively small synthetic problems, and the condition-number scaling experiment uses a fully observed linear operator rather than an underdetermined sensing setting. More comprehensive comparisons across different problem sizes, initialization conditions, and competing acceleration techniques would be necessary to better establish the practical advantages of the proposed approach.

Questions for authors
  1. How does the proposed Silver GD compare with existing acceleration techniques, such as Nesterov-type methods and ScaledGD, in terms of gradient evaluations and computational time?

  2. The theoretical schedule depends on restricted curvature constants, whereas the experiments estimate these quantities using random low-rank probes. How sensitive is the proposed method to estimation errors in these constants, particularly given the large stepsizes in the Silver schedule?

  3. Can the convergence analysis or empirical effectiveness be extended to cases where the factorization rank exceeds the true rank? This setting is common in practical low-rank matrix recovery problems.

3 comments
AuthorsOpenReview ↗

Thank you for the comments

We thank the reviewer for the careful assessment and suggestions on initialization, competing methods, and overparameterization.

Initialization and End-to-End Recovery

Furthermore, the conditioning experiment directly initializes the factors near the ground-truth solution rather than demonstrating how such an initialization can be obtained in practice. Consequently, the proposed method primarily provides a local acceleration guarantee, while its effectiveness as an end-to-end low-rank recovery algorithm remains less clear.

We agree with this distinction. As explained in G1 and G4, Experiment 1 studies local scaling using a controlled near-solution initialization; it does not demonstrate practical basin entry. The sensing experiments instead start from a spectral initializer computed from the observations, and G2 reports running times including initialization and curvature estimation. G4 states the sufficient spectral initialization conditions and the additional PGD-to-Silver argument, together with their limitations.

In the revised manuscript, we describe the main theorem as a local acceleration guarantee and distinguish empirical recovery from spectral initialization from certified basin entry.

Comparisons and Problem Size — Question 1

Moreover, the experiments are conducted on relatively small synthetic problems, and the condition-number scaling experiment uses a fully observed linear operator rather than an underdetermined sensing setting.

How does the proposed Silver GD compare with existing acceleration techniques, such as Nesterov-type methods and ScaledGD, in terms of gradient evaluations and computational time?

G2 provides comparisons with independently tuned Constant GD, NAG, and ScaledGD in underdetermined sensing, including a larger (128×96128 \times 96) setting. Tables 1–2 below report both gradient evaluations and running times, with setup costs included in the total-time column and tuning costs excluded.

Silver GD achieves the lowest mean gradient-evaluation counts, running times, and total running times in these anisotropic comparisons. Additional experimental results are provided in Appendix E.3 of the revised manuscript.

These results support Silver GD as a competitive stepsize-only method for low-rank recovery.

AuthorsOpenReview ↗

Official Comment by Authors

Curvature Sensitivity — Question 2

How sensitive is the proposed method to estimation errors in these constants, particularly given the large stepsizes in the Silver schedule?

G3 addresses the limitations of random probing, the replacement estimation procedure, and the conditional normalization tolerance.

While large intermediate Silver steps make this issue especially relevant, our refined analysis shows that the schedule depth does not require an upper bound. Under the stated local initialization and normalization conditions, any depth kk satisfying ρk≥192K\rho^k \geq 192K preserves local convergence and control of all intermediate iterates, including those associated with large Silver steps.

We have explicitly labeled the sensing curvature estimates as empirical and distinguished admissible-parameter guarantees from experimentally observed convergence with estimated parameters.

AuthorsOpenReview ↗

Official Comment by Authors

Overparameterized Factorization — Question 3

Can the convergence analysis or empirical effectiveness be extended to cases where the factorization rank exceeds the true rank? This setting is common in practical low-rank matrix recovery problems.

Sections 3–4 consider a deterministic rank-constrained optimization problem with fixed observations, without introducing any ground-truth matrix. Theorem 4.1 assumes that the constrained minimizer X^\widehat X has rank exactly rr, where rr is also the number of columns in each factor UU and VV.

In contrast, Section 5 introduces a statistical observation model in which the ground-truth matrix X⋆X_\star may have rank r⋆≤rr^\star \leq r. The statistical error bound in Lemma C.2 allows r⋆<rr^\star < r. However, Theorem 4.1 still requires the constrained minimizer X^\widehat X to have rank exactly rr, along with its other assumptions. In particular, when the constrained minimizer itself has rank below the factorization rank, our current theorem does not apply.

To investigate empirical behavior in this latter setting, we used multivariate regression, where curvature constants can be computed from the empirical design covariance. We fixed the minimizer rank at four and varied the factorization rank s∈4,5,6,8s \in \\{4,5,6,8\\}. Silver GD and constant-step GD were compared under otherwise identical conditions across 10 seeds.

Table 3. Gradient evaluations for error reduction under overparameterization.

Factorization rank (ss)90% GD90% Silver GD99% GD99% Silver GD
4157 ± 1645 ± 6700 ± 100131 ± 10
52,253 ± 907354 ± 1189,460 ± 7,543 (2/10)4,313 ± 2,467
62,870 ± 424458 ± 59NR (0/10)6,165 ± 858
83,134 ± 711475 ± 59NR (0/10)8,226 ± 837

The targets are 90% and 99% reductions in the initial relative optimization error. Entries are mean ± standard deviation. All runs reach the 90% target, and all Silver runs reach the 99% target. Parentheses give the number of successful runs when fewer than 10 reach the target; those statistics use only successful runs. NR denotes failure to reach the target within 20,475 gradient evaluations.

Silver GD consistently uses fewer gradient evaluations for the 90% reduction and reaches the 99% target for every tested rank and seed. These results support finite-budget empirical benefits even when the factorization rank exceeds the minimizer rank. Establishing a corresponding accelerated convergence guarantee for this setting remains an interesting direction for future work.

Comments on the paper

6 comments
AuthorsOpenReview ↗

General comments

Dear Reviewers,

We sincerely thank all three reviewers for their careful reading, constructive suggestions, and recognition of the theoretical contribution. Their comments have helped us clarify the scope of our local acceleration guarantee and strengthen the experimental comparisons. We first address four recurring concerns and then respond to each reviewer individually.

AuthorsOpenReview ↗

Addressing common question (1):

G1. Figure 1 discrepancy and variability across random seeds

“Both Figure 1 panels also show slopes 0.998 and 0.779, whereas Appendix E.1 reports 0.983 and 0.770 for the target-conditioning sweep.”

“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?”

We thank the reviewers for identifying this discrepancy and apologize for the inconsistent presentation. We have repeated both condition number experiments over 10 independent random seeds. The fitted Silver GD slopes are 0.777 for the restricted condition number sweep and 0.770 for the target condition number sweep, consistent with the predicted exponent θ≃0.786\theta\simeq0.786. We have updated Figure 1 and Appendix E.1 together to present the corresponding mean iteration counts and variability, with legends matched to the respective sweeps.

We also wish to clarify that Experiment 1 is specifically designed to examine the condition number dependence predicted by our local convergence theory. The fully observed operator allows us to vary the restricted condition number κ\kappa and the target condition number κX\kappa_X independently, while initialization near the constrained minimizer isolates the local convergence behavior.

AuthorsOpenReview ↗

Addressing common question (2):

G2. Comparisons with accelerated and preconditioned baselines

“How does the proposed Silver GD compare with existing acceleration techniques, such as Nesterov-type methods and ScaledGD, in terms of gradient evaluations and computational time?”

“Do existing results establish an advantage over an independently tuned Constant GD baseline or a suitable preconditioned baseline when initialization and curvature-probing costs are included?”

We thank the reviewers for recommending these comparisons. Our motivation follows a growing line of research investigating how far gradient descent can be accelerated by carefully designing scalar stepsizes alone, beginning with Altschuler and Parrilo (2025) and extending to proximal and projected gradient methods (Bok and Altschuler, 2025) and Riemannian optimization (Park et al., 2025). Building on these developments, we investigate whether the Silver stepsize schedule can achieve provable acceleration in nonconvex low-rank factorization, where large stepsizes introduce additional challenges in controlling intermediate iterates. Unlike momentum-based or preconditioned methods, Silver GD retains the standard factor-gradient update and achieves accelerated local convergence using only scalar stepsizes. We further evaluate its computational performance against independently tuned accelerated and preconditioned baselines.

Conditioning dependence and assumptions. These methods differ in how their local convergence rates depend on κ\kappa and κX\kappa_X. Our local iteration bound is

O((κκX)θlog⁡(1/ε)),θ≃0.786.O\left((\kappa\kappa_X)^\theta\log(1/\varepsilon)\right), \qquad \theta\simeq0.786.

The general-loss ScaledGD guarantee of Tong et al. (2021, Theorem 11) has iteration complexity O(κlog⁡(1/ε))O(\kappa\log(1/\varepsilon)), removing dependence on κX\kappa_X while retaining dependence on κ\kappa. Comparing these parameter dependences, Silver GD has a more favorable bound when κ\kappa is sufficiently large relative to κXθ/(1−θ)≈κX3.68\kappa_X^{\theta/(1-\theta)}\approx\kappa_X^{3.68}. This is a comparison of local upper bounds under different assumptions, not a prediction of a universal performance crossover.

Our theorem allows a small, potentially nonzero normal gradient at a rank-constrained minimizer, whereas the cited general-loss ScaledGD result assumes an unconstrained minimizer of the loss. Both analyses require local initialization. The accelerated factor method of Li and Lin (2020) also provides a relevant local guarantee, using alternating constraints and a stationary-target assumption; the corresponding bound is O(κX(d1+d2)rκlog⁡(1/ε))O(\kappa_X\sqrt{(d_1+d_2)r\kappa}\log(1/\varepsilon)). We have incorporated these references into the revised Related Work section, highlighting the methodological differences between Silver GD and existing accelerated and preconditioned methods.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.