acceptodds
Under review as a conference paper at ICLR 2027

ScaledGD for Underparameterized Matrix Factorization: Global Convergence and Stepsize Universality

Abstract

We study the dynamics and convergence of scaled gradient descent (ScaledGD), a preconditioned gradient method, for underparameterized nonconvex matrix factorization. Given a symmetric positive semidefinite matrix of rank , we seek to identify its best rank- approximation, , namely, the leading -dimensional eigenspace and its associated eigenvalues. Assuming an eigengap at rank , we prove that ScaledGD converges almost surely to a single global minimizer from a normalized randomized range initialization, for every fixed step size . This interval is independent of the target spectrum; the explicit asymptotic contraction factor depends on the relative eigengap. A fixed linear change of coordinates reveals that ScaledGD is exactly ordinary gradient descent on a hidden objective. This representation exposes the coupled dynamics of subspace selection and eigenvalue recovery, enabling a global convergence analysis throughout the full step-size interval. We extend the analysis to rectangular matrices through symmetric dilation, under a suitable initialization and a spectrum-dependent step-size bound. For rank-one approximation in both the symmetric and rectangular settings, we obtain stronger, explicit geometric rates from initialization under a strict leading gap. We also establish gap-free bounds on excess reconstruction error. Both guarantees hold for every fixed under the respective initialization conditions.

Primary area:
optimization
Keywords:
Preconditioned Gradient Descent, Nonconvex Matrix Factorization, underparameterized regime, Global Convergence, Random Initialization, Stepsize Universality

Reviews

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

This paper studies ScaledGD for underparameterized matrix factorization, with the goal of recovering the best rank-k approximation of a positive semidefinite matrix when k is smaller than or equal to the true rank of the target matrix. The main result establishes almost-sure global convergence of ScaledGD from random initialization for any fixed step size η∈(0,1)\eta\in(0,1), assuming a nonzero eigengap at the rank-k boundary. The paper also derives an asymptotic linear convergence rate and extends part of the analysis to rectangular matrix factorization through symmetric dilation.

The proof introduces a useful change of variables that turns ScaledGD into ordinary gradient descent on a transformed nonconvex objective. The analysis combines determinant ascent, uniform control of the iterates, a matrix-valued Heron-type recursion, finite trajectory length, and strict-saddle avoidance. To my knowledge, global convergence of ScaledGD in this underparameterized setting, particularly with the full step-size interval η∈(0,1)\eta\in(0,1), has not been established previously.

Critical strengths
  1. The paper addresses a meaningful and relatively underexplored setting.

Most existing analyses of preconditioned or scaled gradient methods focus on exactly-parameterized or overparameterized matrix factorization, sensing and completion. The underparameterized case is qualitatively different because the algorithm must identify the leading invariant subspace rather than simply factorize the entire target matrix.

  1. The global convergence result is nontrivial.

The paper proves that simultaneous rank-k ScaledGD converges almost surely to the best rank-k approximation, rather than analyzing a sequential rank-one deflation procedure.

  1. The step-size result is clean and potentially useful.

In the symmetric setting, convergence holds for every fixed η∈(0,1)\eta\in(0,1), without requiring the step size to depend on the global condition number of the target matrix or matrix dimensions.

  1. The transformed-objective viewpoint is technically interesting.

The change of variables and the decomposition into radial and subspace components provide a useful perspective on why ScaledGD behaves differently from ordinary gradient descent. The determinant and matrix-recursion arguments also appear to be reusable in related nonconvex factorization problems.

  1. The paper is generally well written, and the main line of the argument is reasonably easy to follow despite the technical nature of the proofs.

Overall, this is definitely a solid paper.

Critical weaknesses
  1. The paper does not establish an explicit iteration complexity.

The theorem only states the linear rate with trajectory-dependent constants, and the time required to enter the local regime is not quantified. Parts of the global analysis still involve spectrum-dependent quantities. Therefore, the current result supports condition-number-independent step size selection and asymptotic behavior, but not a complete condition-number-independent complexity bound.

  1. The experiments do not directly test the predicted relative eigengap dependence.

In Figure 1(a), the relative eigengap (λk−λk+1)/λk(\lambda_k-\lambda_{k+1})/\lambda_k is fixed at 0.2, while the global condition number and the step size are varied. The experiment therefore supports robustness to the global condition number conditional on a fixed normalized eigengap, but it does not empirically examine the dependence of the convergence rate on the relative eigengap. An experiment varying the relative eigengap while controlling the remaining spectral properties would provide more direct validation of the theoretical rate.

  1. The proposed asymptotic rate bound appears conservative.

The theoretical factor depends on η(1−η)\eta(1-\eta), which means η=0.2\eta=0.2 and η=0.8\eta=0.8 would give the same rate. In Figure 1(a), however, these two step sizes exhibit visibly different convergence slopes. This is not a contradiction, since the theorem provides an upper bound rather than an exact local spectral radius, but it suggests that the stated rate does not tightly characterize the observed asymptotic dynamics.

Questions for authors
  1. Can the authors provide an explicit bound on the number of iterations required to enter the local linear convergence regime? In particular, can this entrance time be bounded independently of the global condition number?

  2. Is it possible to derive the exact local linearization of ScaledGD around the optimal rank-k solution? This may provide a tighter rate than the current factor involving η(1−η)\eta(1-\eta) and may better explain the difference between η=0.2\eta=0.2 and η=0.8\eta=0.8 in Figure 1(a).

3 comments

We thank the reviewer for the thoughtful comments and encouraging feedback. These suggestions will definitely help us clarify the scope of our findings and strengthen our work. Please find below further clarification in response to your comments and answers to your questions.

W1, Q1: Regarding the iteration complexity.

For general kk, our analysis does not give an explicit bound on the time required to enter the local contraction region. The challenge is to bound the exit time if a trajectory enters a neighbourhood of a non-optimal saddle manifold, and its subsequent transit to the region of local contraction. Our saddle-avoidance analysis is qualitative and supplies neither bound. In particular, whether this entrance time admits a bound independent of the global condition number remains open.

Nonetheless, for k=1k=1, we obtain explicit non-asymptotic bounds from initialization (see Theorems 7.1 and 7.2). The rank-one proof is instructive for understanding why the entrance time is harder to quantify for general kk. With a leading eigengap and nonzero initial alignment with the leading eigenvector, we can bound how quickly the transformed iterate aligns with the leading eigenvector. If θt\theta_t is the angle between them, then tan⁡2θt\tan^2\theta_t contracts at every step. If we could likewise show that sin⁡θmax⁡,t=∥(I−EkEk⊤)Qt∥2\sin\theta_{\max,t}=\Vert(I-E_kE_k^\top)Q_t\Vert_2 decreases to zero at a quantifiable rate along the trajectory from random initialization, we could extend the rank-one angle analysis to bound the time to reach a prescribed subspace accuracy. However, Figure 1(c) shows that even monotonicity fails for k>1k>1: sin⁡θmax⁡,t\sin\theta_{\max,t} can increase between successive iterates while Ψ(Qt)=log⁡det⁡(Qt⊤ΛQt)\Psi(Q_t)=\log\det(Q_t^\top\Lambda Q_t) continues to increase. It remains unclear how to use the monotonicity of Ψ(Qt)\Psi(Q_t) to bound the time required to escape a saddle neighborhood and reach the local contraction region.

W2: Dependence on the relative eigengap.

We thank the reviewer for suggesting a direct test of how the convergence rate depends on the relative eigengap. Appendix F.4 of the revised manuscript derives the local prediction and compares it with the measured rates in the eigengap sweep. At η=0.5\eta=0.5, the local analysis predicts a contraction factor r=1−ηδr=1-\eta\delta. Across 29 gaps δ=(λ4−λ5)/λ4\delta=(\lambda_4-\lambda_5)/\lambda_4 between 0.050.05 and 0.400.40, the median factor differed from this prediction by less than 10−410^{-4}. We varied only λ5\lambda_5, fixing d=50d=50, k=4k=4, κ=100\kappa=100 and the same six Gaussian initializations. Halving the gap also roughly doubled the median number of iterations from initialization to relative error 10−1210^{-12} over the tested range. Taken together, the measurements show that the predicted linear dependence of the late-stage fractional error reduction 1−r1-r on the relative eigengap δ\delta is accurate over the tested range.

W3, Q2: Tightness of the asymptotic rate.

The displayed theorem factor is conservative, as the reviewer notes. The Hessian calculation in Appendix A.4 (Lemma A.9) yields the exact local linearization in transformed coordinates: radial modes have multiplier 1−2η1-2\eta, while a mode rotating selected eigenvector ii toward omitted eigenvector jj has multiplier 1−η(1−λj/λi)1-\eta(1-\lambda_j/\lambda_i). Hence the slowest normal-mode factor is max⁡{∣1−2η∣,1−ηλk−λk+1λk}.\max \left\lbrace \vert 1-2\eta\vert, 1-\eta\frac{\lambda_k-\lambda_{k+1}}{\lambda_k}\right\rbrace. In Figure 1(a), the larger step corrects a greater fraction of the subspace error at each iteration. At relative gap 0.20.2, increasing η\eta from 0.20.2 to 0.80.8 reduces the slowest subspace multiplier from 0.960.96 to 0.840.84, while the radial multiplier has magnitude 0.60.6 in both cases. The subspace mode therefore predicts the steeper late-stage slope at η=0.8\eta=0.8. As η\eta approaches 11, however, ∣1−2η∣|1-2\eta| approaches 11 and radial convergence can become the limiting factor. Appendix F.4 now derives this local factor and compares it with the measured rates. Theorem 3.1 gives a bound valid from initialization, with a trajectory-dependent prefactor.

Thank you for your detailed reply. I have raised my rating. It would be better if you can try to give a detailed analysis of the initial region (before entering the local neighborhood) and try to give an iteration bound in your final version or later work.

Overall, I would say this paper is technically solid and I highly recommend it to be accepted.

Thank you for your very positive feedback and also encouraging suggestions. Yes, we are working towards establishing a full non asymptotic analysis and we feel we are close. Hopefully we achieve that in our final version.

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

This paper studies the low-rank symmetric matrix factorization under a preconditioned gradient method scaledGD. The authors prove the convergence under symmetric and asymmetric settings, with an explicit rank-one example. They also show the equivalence between scaledGD and GD through a coordinate transform. Experiments are provided to verify theoretical claims.

Critical strengths
  • The paper provides a rigorous and rather complete characterization of the convergence of scaled GD across multiple settings: symmetric, asymmetric, and an explicit rank-one result.
Critical weaknesses
  • Part of the paper lacks some interpretation and explanation and thus is not very reader friendly (e.g. Section 4).
Questions for authors
  • I wonder if the authors could explain more on the intuition of why η=1/2\eta=1/2 is a threshold in Lemma 4.1 beyond the discussion around line 256.
  • In my opinion, the scaledGD is about adding a nice precondition. It works well in the symmetric setting; however, in asymmetric settings, the singular values still affect the dynamics through the stability limit of the learning rate. I wonder whether there is a more consistent version of scaledGD extending from symmetric case to asymmetric case such that the asymmetric case is also independent of any singular values. The current version seems not designed for the same effect.
  • I wonder whether there is additional/deeper intuition on the equivalence of scaledGD and GD under different objectives since the log det term seems quite natural and common.
  • I wonder whether the authors could briefly talk about the intuition of the technique used to deal with 0<η<10<\eta<1 instead of some fixed learning rate.
1 comment

Thank you for your thoughtful questions and encouraging assessment of our convergence results. Your feedback will help us improve the clarity and exposition of our findings. Please find below our answers to your questions and concerns.

W1: Clarity of Section 4.

We thank the reviewer for drawing our attention to the need for more intuition in Section 4. Immediately after Lemma 4.1 we now explain how the radial update keeps the Gram matrix positive definite and why our initialization gives a sharper lower bound for η≤1/2\eta\leq 1/2.

Q1: On the threshold η=1/2\eta=1/2 in Lemma 4.1.

First, we wish to highlight that for any W0≻0W_0\succ0, the Gram recursions in equations (15) and (90) already give Wt⪰4η(1−η)IW_t\succeq4\eta(1-\eta)I from the first update onward, for every 0<η<10<\eta<1. Indeed, the radial map fη(r)=(1−η)r+η/rf_\eta(r)=(1-\eta)r+\eta/r satisfies fη(r)2≥4η(1−η)f_\eta(r)^2\geq4\eta(1-\eta) for r>0r>0 by the arithmetic–geometric mean inequality, and the subspace correction is positive semidefinite (Appendix B.1, Step 1 of the proof of Lemma B.1).

We adopt the stronger initialization W0=Sinit2≻IW_0=S_{\mathrm{init}}^2\succ I for convenience in the analysis and exposition. The threshold η=1/2\eta=1/2 arises when we ask whether the update preserves Wt⪰IW_t\succeq I. For η≤1/2\eta\leq1/2, fηf_\eta is nondecreasing on [1,∞)[1,\infty) and fixes 11, so every radial scale at or above one stays there. For η>1/2\eta>1/2, fη′(1)<0f_\eta'(1)<0, so a scale just above one can overshoot below one. More generally, starting from W0⪰mIW_0\succeq mI with 0<m≤10<m\leq1, the same argument preserves mImI whenever η≤m/(1+m)\eta\leq m/(1+m).

Q2: Scaled GD for the asymmetric case.

In the asymmetric case, the shared-inverse update inherits a step-size restriction from the negative eigenvalues of the rectangular dilation. For a symmetric positive semidefinite target, this instability does not occur for any 0<η<10<\eta<1. The local multipliers explain the difference. In the asymmetric update, the most restrictive negative mode has multiplier 1−η(1+σ1/σk)1-\eta(1+\sigma_1/\sigma_k), whose magnitude exceeds one for η>2/(1+σ1/σk)\eta>2/(1+\sigma_1/\sigma_k). In the symmetric update with a boundary eigengap, the subspace multipliers 1−η(1−λj/λi)1-\eta(1-\lambda_j/\lambda_i) for i≤k<ji\leq k<j lie strictly between zero and one, and the radial multiplier satisfies ∣1−2η∣<1|1-2\eta|<1.

For k=1k=1, the ratio σ1/σk\sigma_1/\sigma_k equals one, so the local threshold is exactly η=1\eta=1. Theorem 7.2 shows that every fixed 0<η<10<\eta<1 also gives global convergence whenever the initialization has a nonzero projection onto the leading positive dilation eigenspace. This projection lets us control every competing component throughout the trajectory. Extending this argument to general kk would require comparable control of alignment with the entire leading subspace. Whether a different preconditioner can overcome the instability caused by negative dilation modes, or whether the spectrum dependence reflects a fundamental limitation, remains open.

Q3: Deeper intuition on the equivalence between ScaledGD and GD and extensions to other objectives.

We thank the reviewer for this observation. The log determinant arises naturally because its gradient, with the factor of 1/21/2 in the objective, produces the inverse-Gram term in the ScaledGD update. In our setting, the log determinant helps separate how the factor adjusts its scale from how its columns align with the leading eigenspace. We are not sure yet how this insight might extend to other objectives, but we share the reviewer's interest in this direction and are quite excited about the possibilities.

Q4: Why the proof covers every fixed 0<η<10<\eta<1.

For ordinary gradient descent on an LL-smooth objective, the descent lemma gives the familiar step-size range 0<η<2/L0<\eta<2/L. ScaledGD adapts the step to the current factor through (Xt⊤Xt)−1(X_t^\top X_t)^{-1}, which rescales the gradient along each factor direction. This explains why a fixed η\eta can accommodate changes in factor scale. To see why the argument works for every fixed 0<η<10<\eta<1, consider equation (15) when the current subspace is invariant. The subspace residual then vanishes. Taking r=λi(Wt)r=\sqrt{\lambda_i(W_t)}, where Wt=Zt⊤ZtW_t=Z_t^\top Z_t, gives the scalar update r↦(1−η)r+η/rr\mapsto(1-\eta)r+\eta/r. For r≠1r\neq1, every such step lies strictly between rr and 1/r1/r, so ∣log⁡r∣|\log r| decreases even when the scale crosses one. Equation (124) gives the corresponding contraction bound for the matrix logarithm of the radial update. At η=1\eta=1, by comparison, the scale simply alternates between rr and 1/r1/r. When the subspace is still moving, the same radial recursion has an additional term driven by the subspace residual. Equation (113) bounds the sum of the squared residuals through log-determinant ascent, allowing us to control their cumulative effect on the scale. This is why the argument works for each fixed η∈(0,1)\eta\in(0,1), even when individual scales overshoot and global descent of the hidden objective is unavailable.

Comments on the paper

1 comment

We thank the reviewer for their valuable comments and feedback, which will help us improve the paper. Please find below our response, which we hope addresses the concerns and weaknesses you raised.

W1: Iteration complexity.

We agree with the reviewer's comment. Theorem 3.1 allows any fixed η∈(0,1)\eta\in(0,1) independently of the spectrum, but leaves the time to reach the local contraction region unquantified. Within that region, the choice of η\eta still affects convergence speed. For the relative gap 0.20.2 in Figure 1(a), the local factors are 0.960.96 at η=0.2\eta=0.2 and 0.840.84 at η=0.8\eta=0.8, consistent with the steeper slope at the larger step size. We give this calculation in Appendix F.4, as discussed in our response to Reviewer 537c (W3, Q2). We now clarify alongside Theorem 3.1 that its random prefactor absorbs the initial transient. Obtaining an explicit iteration bound from initialization for general kk remains an interesting open question.

W2: Initialization and rectangular scope.

The paragraph following Theorem 3.1 now explains that the guarantee extends to unnormalized random initializations whose columns lie in range⁡(M)\operatorname{range}(M) and have a joint density in coordinates on that range (Appendix B.8, Corollary B.10). In particular, when M≻0M\succ0, ordinary Gaussian initialization suffices. Section 6 now clarifies that the rectangular theorem covers the dilation update, whose two factors share (X⊤X+Y⊤Y)−1(X^\top X+Y^\top Y)^{-1}. Extending the guarantee to methods with separate Gram inverses requires a different analysis.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.