PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems

Christopher De Sa, Kunle Olukotun, Christopher Ré

arXiv:1411.1134v3cs.LGmath.OCstat.ML

TL;DR

The paper addresses the lack of global convergence guarantees for standard SGD on low-rank factorized matrix problems. It introduces Alecton, an SGD-like method with a norm-dependent step size, and proves global convergence from random initialization under broad sampling and noise conditions. The method achieves O(ε^-1 n log n) steps with constant probability for constant-rank problems.

  • Problem

    Standard SGD efficiently handles low-rank factorized matrix problems but does not globally converge from every initialization, while prior alternatives lack global guarantees or require expensive initialization.

  • Method

    Alecton modifies SGD with a step size depending on the iterate norm and analyzes the resulting updates using a martingale-based technique related to stochastic power iteration.

  • Results

    Alecton converges globally from random initialization in O(ε^-1 n log n) steps with constant probability for constant-rank problems, under broad sampling conditions.

  • Takeaways & Limitations

    The variance-based result covers noisy samples and applications including matrix completion, phase retrieval, and subspace tracking without a special initialization phase.

  • Takeaways & Limitations

    The convergence rates are slower than those of prior analyses in their respective settings, although the paper states the rate is optimal in its more general setting.

Abstract

from arXiv · show

Stochastic gradient descent (SGD) on a low-rank factorization is commonly employed to speed up matrix problems including matrix completion, subspace tracking, and SDP relaxation. In this paper, we exhibit a step size scheme for SGD on a low-rank least-squares problem, and we prove that, under broad sampling conditions, our method converges globally from a random starting point within $O(ε^{-1} n \log n)$ steps with constant probability for constant-rank problems. Our modification of SGD relates it to stochastic power iteration. We also show experiments to illustrate the runtime and convergence of the algorithm.

1 Introduction

The paper studies stochastic optimization with low-rank factorization, targeting globally convergent SGD under broad sampling and noise conditions. Alecton uses random initialization and a norm-dependent step size, with applications including matrix completion, phase retrieval, and subspace tracking.

  • 1 Introduction: The work applies to matrix problems including matrix completion, general data analysis, subspace tracking, principal component analysis, optimization, and recommendation systems.These problems arise from a stochastic eigenvalue-style formulation involving the leading eigenvalues of E[Ã].
  • 1 Introduction: Low-rank factorization replaces an oversized matrix X with Y, reducing storage from n^2 to np while enforcing rank and positive-semidefinite structure.The substitution X = YY^T gives rank(X) ≤ p and X ⪰ 0 by construction.
  • 1 Introduction: Standard SGD on the factorized problem lacks global convergence because some initial values produce iterates whose norms diverge.More sophisticated geodesic and manifold-projection methods also lack a global-convergence guarantee.
  • 1 Introduction: Alecton globally converges from random initialization, without the expensive SVD-like initialization required by prior analyses.The paper establishes a convergence rate to a global optimum under this initialization scheme.
  • 1 Introduction: The analysis depends on sample variance rather than bounded noise magnitude, supporting robustness to different noise models and broader sampling conditions.The stated applications include matrix completion, phase retrieval, and subspace tracking.
  • 1 Introduction: Compared with prior analyses, the paper offers broader problem coverage and practical SGD algorithms, but its convergence rates are slower in the corresponding settings.The paper argues that this slower rate is optimal in its more general setting.

2 Algorithmic Derivation

The derivation connects Alecton’s low-rank stochastic optimization update to stochastic power iteration through a specially chosen metric and iterate-dependent step size. Because non-optimal fixed points defeat standard Lyapunov arguments, convergence is instead analyzed with supermartingales and optional stopping.

  • 2 Algorithmic Derivation: The factorized objective is invariant under orthogonal transformations of Y, motivating quotient-manifold and Riemannian-metric formulations.The relevant manifold is the quotient of R^(n×p) under the orthogonal group action.
  • 2 Algorithmic Derivation: Alecton chooses a Riemannian metric and step size so that, for p = 1, the resulting SGD rule matches an iterate-dependent step-size update.The metric provides intuition for selecting the step size while retaining a simpler update rule.
  • 2 Algorithmic Derivation: The simpler update preserves the iterates’ column space, effectively transforming optimization in R^n into optimization on the Grassmannian.Alecton estimates the angular component first and recovers the radial component by averaging.
  • 2 Algorithmic Derivation: Algorithm 1 separates angular eigenvector estimation from radial eigenvalue estimation using independent sampled matrices.The angular phase updates Yk, while the radial phase averages projected samples into R.
  • 2 Algorithmic Derivation: Non-optimal fixed points prevent uniform global convergence proofs based on a Lyapunov function whose expectation decreases at every iteration.The low-rank decomposition creates symmetric families of fixed points, including non-global ones.
  • 2 Algorithmic Derivation: Alecton uses a martingale-based proof that constructs a supermartingale and applies the optional stopping theorem to bound convergence probability and rate.These bounds are then used to derive convergence of the original algorithm.

3 Convergence Analysis

Alecton defines angular convergence through proximity to a target eigenspace and proves convergence under variance, rank, and step-size conditions using martingale arguments and optional stopping.

  • Convergence criteria: The angular success criterion measures whether the column space of Y_k lies close to the span of the q algebraically largest eigenvectors, with eigengap Δ = λ_q − λ_{q+1}.When eigenvalues are repeated, convergence is defined relative to the corresponding larger eigenspace rather than an individual eigenvector.
  • Assumptions: The theorem assumes the Alecton Variance Condition, an Alecton Rank Condition, and an upper-bounded step size; smaller feasible step sizes slow convergence.The rank condition allows either p = 1 or rank-1 samples.
  • Probability bound: The quantity Z_p in the probability bound is defined from a random Gaussian matrix and visualized empirically as an average over 10^5 samples.The supplied figure passage identifies the plotted quantity but does not provide additional numerical values.
  • Theorem 1: Under the variance, rank, and step-size conditions, Alecton’s angular phase converges with constant probability after O(ε^-1np^3 log n) iterations when σ_aΔ^-1 is dimension-independent.The same iteration bound is also the stated time bound, assuming samples are not reused.
  • Martingale technique: The proof tracks failure near unstable fixed points with stopping times, constructs a submartingale and supermartingale, and applies the optional stopping theorem to bound failure probability and convergence time.The radial phase is handled separately using Chebyshev’s inequality on an average of samples.

4 Application Examples

The variance-based analysis applies to several sampling models, including entrywise, rectangular, matrix-sensing, and subspace sampling, as well as noisy observations and one-at-a-time recovery.

  • 4.1 Entrywise Sampling: For constant-rank problems with eigenvalues independent of problem size, entrywise sampling yields an O(ε^-1n log n) convergence-time bound under incoherence.The incoherence assumption supplies the second-moment bound needed for the Alecton variance condition.
  • 4.2 Rectangular Matrix Recovery: Rectangular entrywise sampling satisfies the variance condition when matrix entries are bounded, and the same big-O convergence bound holds when singular values are size-independent.The rectangular problem is converted into a symmetric block-matrix eigenproblem.
  • 4.3 Matrix Sensing: Uniform trace sampling satisfies the variance condition for n > 50, so size-independent eigenvalues preserve the stated big-O convergence bound.Samples take the form n^2vv^T Aww^T for independent uniform unit vectors v and w.
  • 4.4 Subspace Tracking: Subspace sampling satisfies the variance condition when the sampled subspace is incoherent, and observed entries can be randomly split to construct the required independent samples.The sampling model uses randomly selected entries from vectors in a rank-r projection subspace.
  • Noise models: Because the analysis uses variance bounds, additive and multiplicative independent sample noise can be incorporated through the corresponding variance properties.The supplied passage states that additive noise increases sampling variance by an amount proportional to the noise variance.
  • One-at-a-time recovery: Repeated rank-1 Alecton runs recover additional eigenvalue/eigenvector pairs one at a time, requiring O(ε^-1pn log n) total steps when eigenvalues are size-independent.This strategy can be used when the desired number of eigenvectors is not known in advance.

5 Experiments

Experiments on synthetic and Netflix data illustrate Alecton’s convergence behavior, step-size trade-offs, and sequential higher-rank recovery, while leaving parallel non-convex convergence unresolved.

  • Synthetic experiments: On synthetic rank-10 matrices with n = 10^4, convergence trajectories varied across five random initializations and three sampling distributions.The experiment used p = q = 1.
  • Convergence scaling: Figure 2 reports convergence occurring in O(n log n) steps.The figure caption states the asymptotic convergence description without supplying further plotted values.
  • Step-size experiment: Smaller step-size parameter η produced slower but more accurate convergence, while making convergence time more sensitive to the initial value.This behavior was observed on a larger synthetic dataset with n = 10^6.
  • Netflix experiment: On the Netflix Prize problem, Alecton recovered the most significant singular vector and then additional singular vectors with the one-at-a-time procedure.The experiment used 110,198,805 revealed entries from a 480,189-column by 17,770-row matrix and ran up to p = 12.
  • Discussion: Whether a lock-free Hogwild! version of Alecton converges at a good rate for non-convex problems remains an open question.Hogwild! has parallel speedup and similar performance to sequential SGD on convex problems, but that evidence does not establish the non-convex result.

6 Conclusion

The paper presents Alecton as a globally convergent SGD method for non-convex low-rank factorization, using random initialization, variance-based analysis, and broad sampling and noise conditions.

  • Conclusion: Alecton globally converges from random initialization for a non-convex low-rank factorized problem and provides a convergence rate.The analysis covers sampling conditions including matrix completion and matrix sensing and accommodates noisy samples.
  • Conclusion: A novel martingale-based technique supports the convergence results and may extend to other non-convex optimization problems.The paper describes this possible extension as an optimistic outlook rather than an established result.

A Negative Results

The negative results show that generic SGD and broad extensions of low-rank factorization cannot guarantee rapid global convergence in all settings. Divergence, non-optimal fixed points, and constrained formulations motivate careful restrictions on algorithms and problem classes.

  • Divergence Example: For some step-size rules and initial conditions, the quartic SGD iteration diverges to infinity exponentially quickly.The proposition assumes the step size is not superexponentially decreasing; scaling the step size with the iterate norm motivates Alecton.
  • Global Convergence Counterexample: A low-rank rank-1 factorization can fail globally because an initialization orthogonal to the leading eigenvector remains orthogonal forever.Although y = 2e1 is the global solution, y0 = 0 preserves e1^Tyk = 0 and prevents convergence to it.
  • Global Convergence Counterexample: The counterexample shows that standard Lyapunov-based proofs cannot establish uniform rapid global convergence when non-optimal fixed points exist.A uniform guarantee would contradict the presence of starting points that cannot reach a global optimum.
  • Constraints Counterexample: Arbitrary constraints cannot inherit an O(n log n) global-convergence guarantee, since constrained low-rank optimization can encode the NP-complete MAXCUT problem.The relaxed problem has the same global solution as MAXCUT and can be represented as a low-rank factorization.

B Comparison with Other Methods

The comparison section situates the paper among low-rank optimization, manifold methods, stochastic power iteration, and martingale-based analysis. Existing approaches provide local or qualitative guarantees, whereas the paper develops convergence-rate analysis for its setting.

  • Comparison with other methods: The paper compares related algorithms using both sampling complexity and computational complexity, with dimension n and rank p as the principal parameters.Some tabulated formulas omit factors of log log ε^-1 for space.
  • Proof framework: The appendix organizes the proof around filtrations, martingales, stopping times, quadratic bounds, and determinant inequalities.These definitions and lemmas provide the technical framework for the main convergence analysis.

C.3 Main Proofs

The main proofs establish Alecton’s convergence by controlling angular progress, failure probability, stopping time, and radial behavior. Martingale and stopping-time arguments combine these bounds into the theorem’s global-convergence guarantee.

  • Main proof: Optional stopping proves both a bound on failure occurring before success and an expectation bound for the stopping time.These are established in Lemmas 13 and 14 and feed directly into the theorem’s angular analysis.
  • Main proof: The angular proof combines the failure-event decomposition with a union bound and Markov’s inequality.The resulting bound accounts for failure before success and for not reaching either event by time t.
  • Main proof: The radial proof bounds the expected distance to the mean using the Alecton variance condition and Markov’s inequality.The argument evaluates the deviation of the sampled updates and converts it into a radial failure bound.

D Proofs of Lemmas

The lemma proofs supply the probabilistic, matrix-analytic, and sampling-specific ingredients required by the main theorem. They derive initialization bounds, determinant inequalities, and variance conditions for the considered sampling models.

  • Matrix inequalities: Determinant and quadratic-rational lemmas provide lower and upper bounds needed to control the evolution of τ and related quantities.The proofs use projection properties, the matrix determinant lemma, Cauchy-Schwarz, and eigenvalue arguments.
  • Initialization lemmas: The initialization analysis uses Gaussian symmetry and independent signal and null-space components to bound the expected initial value of τ.Uniform initialization on the appropriate sphere is treated equivalently through independent standard normal entries for this calculation.
  • Variance conditions: The sampling-specific lemmas establish variance conditions using incoherence, commuting matrices, entrywise bounds, and sphere fourth moments.These ingredients cover entrywise, rectangular entrywise, trace, and subspace sampling analyses.
  • Subspace sampling: For subspace sampling, the appendix derives the required variance bound after introducing the sampling form and applying the sphere-component moment results.The sphere fourth-moment lemmas are the key probabilistic input for this sampling case.

E Lower Bound on Alecton Rate

This section proves a lower bound showing that Alecton’s convergence cannot generally be improved to a linear rate by changing its step-size schedule. It also describes extensions to spectahedral constraints and identifies an NP-hard constrained case that Alecton cannot efficiently solve.

  • Lower-bound setting: The analysis assumes p = 1, controls sample growth through a constant C, and considers a non-global eigenvector direction with bounded variance.The error quantity ρ_k measures the iterate’s error in that direction.
  • Proof strategy: The proof tracks ρ_k across iterations and shows that its expected value can decrease only at an Ω-rate under the stated assumptions.The argument uses a lemma and the Alecton update rule with time-varying step sizes.
  • Lower bound: Alecton cannot achieve a linear convergence rate under the stated bounded-sampling conditions, even with a different step size at every iteration.The lower bound applies to any time-varying step-size rule.
  • Handling constraints: For a spectahedral constraint, Alecton can use only its angular phase to recover the leading eigenvector, while retaining the same convergence analysis.The constrained objective is transformed into a unit-norm vector problem whose minimum occurs at y = u1.
  • Handling constraints: Alecton cannot efficiently solve every constrained problem because the elliptope-constrained MAXCUT embedding is NP-hard.This establishes a practical boundary for the method’s constrained-problem applicability.

G Towards a Linear Rate

This section combines Alecton’s fast stochastic phase with a heavier descent method to obtain linear convergence near an exactly recoverable solution. The construction relies on restricted isometry to establish local strong convexity and requires O(np log n) iterations for rank-p recovery before refinement.

  • RIP analysis: The p-RIP assumption preserves low-rank norms under the measurement operator and supports the inner-product bounds used in the strong-convexity proof.The proof extends RIP from norms to inner products for matrices with controlled ranks.
  • Local strong convexity: The quadratically transformed recovery objective is strongly convex in an O(1)-sized region around the solution under the stated RIP conditions.The region’s size does not depend on n, so standard convex descent methods can converge linearly once the iterate enters it.
  • Hybrid method: Alecton first brings the factorization into the strongly convex region, after which coordinate descent refines it monotonically at a linear rate.The hybrid method uses stochastic steps for rapid progress and heavier descent steps for precision.
  • Complexity: O(np log n) iterations suffice for rank-p recovery when Alecton uses O(n log n) angular-phase steps per rank component.The construction requires p iterations of the angular phase.
Loading 1411.1134v3…