- 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 , 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 , has not been established previously.
Critical strengths
- 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.
- 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.
- The step-size result is clean and potentially useful.
In the symmetric setting, convergence holds for every fixed , without requiring the step size to depend on the global condition number of the target matrix or matrix dimensions.
- 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.
- 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
- 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.
- The experiments do not directly test the predicted relative eigengap dependence.
In Figure 1(a), the relative eigengap 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.
- The proposed asymptotic rate bound appears conservative.
The theoretical factor depends on , which means and 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
-
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?
-
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 and may better explain the difference between and in Figure 1(a).
3 comments
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.
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 k, 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=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 k. 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 is the angle between them, then tan2θt contracts at every step. If we could likewise show that sinθmax,t=∥(I−EkEk⊤)Qt∥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>1: sinθmax,t can increase between successive iterates while Ψ(Qt)=logdet(Qt⊤ΛQt) continues to increase. It remains unclear how to use the monotonicity of Ψ(Qt) 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, the local analysis predicts a contraction factor r=1−ηδ. Across 29 gaps δ=(λ4−λ5)/λ4 between 0.05 and 0.40, the median factor differed from this prediction by less than 10−4. We varied only λ5, fixing d=50, k=4, κ=100 and the same six Gaussian initializations. Halving the gap also roughly doubled the median number of iterations from initialization to relative error 10−12 over the tested range. Taken together, the measurements show that the predicted linear dependence of the late-stage fractional error reduction 1−r on the relative eigengap δ 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η, while a mode rotating selected eigenvector i toward omitted eigenvector j has multiplier 1−η(1−λj/λi). Hence the slowest normal-mode factor is max{∣1−2η∣,1−ηλkλk−λk+1}. In Figure 1(a), the larger step corrects a greater fraction of the subspace error at each iteration. At relative gap 0.2, increasing η from 0.2 to 0.8 reduces the slowest subspace multiplier from 0.96 to 0.84, while the radial multiplier has magnitude 0.6 in both cases. The subspace mode therefore predicts the steeper late-stage slope at η=0.8. As η approaches 1, however, ∣1−2η∣ approaches 1 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.