PaperlayerView exact revision on arXiv

Source-linked AI summary

Dropping Convexity for Faster Semi-definite Optimization

Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi

arXiv:1509.03917v3stat.MLcs.DScs.ITcs.LGmath.NAmath.OC

TL;DR

The paper asks whether gradient descent remains effective after convex PSD optimization is rewritten through a non-convex factorization. It introduces Factored Gradient Descent with a specialized step size and first-order initialization, proving sublinear convergence for smooth objectives and linear convergence under restricted strong convexity, subject to initialization and rank assumptions.

  • Problem

    Gradient methods for factorized PSD optimization are widely used but lacked convergence guarantees for general convex functions under common convex assumptions.

  • Method

    The paper factorizes X as UU^T, applies gradient descent to U, selects a step size using convexity parameters and the optimum's spectral characteristics, and develops first-order initialization procedures.

  • Results

    FGD converges sublinearly for smooth convex f and linearly for smooth restricted-strongly-convex f, with convergence to optimal or near-optimal solutions under suitable initialization.

  • Takeaways & Limitations

    The factorized non-convex formulation can retain convergence-rate guarantees analogous to convex gradient descent under the paper's assumptions.

  • Takeaways & Limitations

    The analysis assumes r ≤ rank(X⋆) and suitable initialization; extending it to r > rank(X⋆) or weaker initialization is left for future work.

Abstract

from arXiv · show

We study the minimization of a convex function $f(X)$ over the set of $n\times n$ positive semi-definite matrices, but when the problem is recast as $\min_U g(U) := f(UU^\top)$, with $U \in \mathbb{R}^{n \times r}$ and $r \leq n$. We study the performance of gradient descent on $g$---which we refer to as Factored Gradient Descent (FGD)---under standard assumptions on the original function $f$. We provide a rule for selecting the step size and, with this choice, show that the local convergence rate of FGD mirrors that of standard gradient descent on the original $f$: i.e., after $k$ steps, the error is $O(1/k)$ for smooth $f$, and exponentially small in $k$ when $f$ is (restricted) strongly convex. In addition, we provide a procedure to initialize FGD for (restricted) strongly convex objectives and when one only has access to $f$ via a first-order oracle; for several problem instances, such proper initialization leads to global convergence guarantees. FGD and similar procedures are widely used in practice for problems that can be posed as matrix factorization. To the best of our knowledge, this is the first paper to provide precise convergence rate guarantees for general convex functions under standard convex assumptions.

1 Introduction

The paper recasts convex positive-semidefinite optimization as an unconstrained factorized problem and analyzes gradient descent on the factors. It provides step-size, convergence, and initialization results under standard convex assumptions.

  • Factoring X as UU^T makes the problem unconstrained, avoiding eigen-decompositions during iterative updates such as gradient descent.
  • Factored Gradient Descent applies gradient descent directly to the factorized variable U.
  • The proposed step size depends on f's convexity parameters and the top singular value of the unknown optimum; a constant-relative-distance estimate can suffice in practice.
  • For M-smooth convex f, FGD converges sublinearly, while restricted strong convexity yields linear convergence to the unique optimum under a good initialization.
  • When r < r⋆, FGD can converge near the best rank-r approximation of X⋆, while smaller r reduces variables and may prevent overfitting.
  • Using only first-order oracle access, initialization based on ∇f(0) can provide a constant-relative-error starting point for certain condition numbers.

2 Preliminaries

The paper establishes notation, assumptions, and geometry for optimizing convex functions over positive semi-definite matrices through factored variables. It defines smoothness and restricted strong convexity conditions, factorization ambiguities, and the gradient used by the factored method.

  • Positive semi-definite matrices form the feasible convex set, denoted S_n^+, with X ⪰ 0 indicating positive semi-definiteness.
  • The rank-constrained optimum is assumed close to the best rank-r approximation when the residual ||X⋆ − X⋆_r||_F is sufficiently small.This assumption models a low-rank latent matrix with a small perturbation; an alternative step size can remove it at the cost of two spectral-norm computations per iteration.
  • For X = UU^T, the gradient with respect to U is 2∇f(X)U, and PSD projection is obtained by retaining positive eigenvalues and eigenvectors.
  • A factorization X = UU^T is non-unique because right multiplication by any orthonormal rotation R preserves UU^T.The paper therefore introduces a rotation-invariant distance in the factored space.
  • The objective is assumed convex and differentiable, with M-smoothness characterized by Lipschitz-continuous gradients.The smoothness condition bounds gradient differences using the Frobenius norm.
  • The analysis also considers m-strong convexity and (m,r)-restricted strong convexity, the latter applying to rank-r matrix pairs.Restricted strong convexity is motivated by settings where global strong convexity fails in high dimensions.

3 Factored gradient descent

Factored Gradient Descent (FGD) applies gradient descent to the factorized variable U, using careful initialization and a step size adapted to spectral quantities. This avoids repeated eigen-decompositions and supports convergence under standard convex assumptions.

  • FGD optimizes the factorized problem using the update U⁺ = U − η∇f(UUᵀ)U.The algorithm absorbs the factor 2 from the true gradient into η.
  • FGD requires careful initialization and a special step size because the UUᵀ parametrization is non-convex and can otherwise overshoot near the optimum.The paper motivates step-size control by the need to prevent divergence caused by large spectral quantities.
  • η depends on the smoothness parameter M, the current iterate’s spectral norm, and the gradient’s spectral norm rather than only on M.In practice, the spectral quantities at the initialization point can serve as surrogates.
  • Using η = 1/M can cause overshooting because the optimum and its gradient may have spectral norms O(α^2) and O(β^2), independently of M.A scaled rule proportional to 1/(M∥X⋆∥₂ + ∥∇f(X⋆)∥₂) reduces the influence of the O(α^3) and O(β^3) update terms.
  • FGD’s per-iteration cost is dominated by gradient computation plus matrix operations bounded by nnz(∇f(·))·r, avoiding full eigenvalue decompositions.For r = O(n), both FGD and projected gradient descent have O(n^3) per-iteration complexity, but FGD uses matrix multiplication instead of SVD.

4 Local convergence of Fgd

Under suitable initialization and step-size conditions, FGD has sublinear convergence for smooth convex objectives and linear convergence under restricted strong convexity, including exact recovery when the factor rank matches the optimum.

  • Assumptions: FGD requires a good initialization with constant relative error to the optimum, which helps avoid saddle points introduced by factorization.The initialization is assumed for both smooth and restricted strongly convex settings.
  • Smooth convex objectives: For M-smooth convex f with matching rank, FGD converges sublinearly toward an optimal point, with function values decreasing at an O(1/k)-type rate.This mirrors the sublinear rate of classical gradient descent in the original variable space.
  • Restricted strong convexity: When r = rank(X⋆), FGD achieves linear convergence to an optimal factor, and K = O(log(1/ε)) iterations suffice for ε-accuracy.For r = n, this recovers exact semi-definite optimization.
  • Restricted strong convexity: Under restricted strong convexity, FGD converges linearly to a neighborhood of the rank-r optimum, including when r < rank(X⋆).The neighborhood reflects the rank-constrained approximation setting.
  • Rate dependence: The convergence factor depends on the condition number and gradient spectral norm at the optimum in addition to the convexity parameters.This dependence results from the specialized step-size choice.
  • Assumptions: The step size depends on convexity parameters and spectral characteristics of the optimum, rather than only on the smoothness parameter.A surrogate based on the initial point can be used when the optimum is unknown.

5 Initialization

The paper develops initialization strategies for FGD, including first-order-oracle constructions for smooth strongly convex objectives and alternatives that first obtain a constant-error point before switching to FGD.

  • Initialization motivation: Because factorized optimization is non-convex, convergence guarantees require starting from a sufficiently decent point near the optimal factor.The initialization condition is used to obtain provable convergence to the target factor.
  • Generic initialization: A standard convex algorithm can first produce a constant-error approximation, after which FGD refines it to high precision.This provides a generic route when a direct factor initialization is unavailable.
  • First-order initialization: For smooth strongly convex objectives, scaling the PSD projection of −∇f(0) by 1/M provides a usable initialization based on first-order information.A surrogate for M can be used when the smoothness parameter is difficult to compute exactly.
  • Guarantees and limits: The initialization guarantee is strongest for small condition numbers; as the condition number increases, the initial point can move farther from the optimum.For an ℓ2 loss with condition number 1 and rank-matched optimum, the construction recovers the optimum.
  • Guarantees and limits: For exact rank-r optima, the initialization guarantee extends under the stated theorem conditions, including restricted strong convexity.The exact-rank corollary applies when the optimum has rank r.

6 Convergence proofs for the Fgd algorithm

The convergence proofs transfer convex-space descent arguments to the factor space by establishing a suitable inner-product lower bound and then applying it to smooth and restricted strongly convex cases.

  • Proof strategy: A key descent lemma lower-bounds the factor-space inner product despite the non-convexity of the factored objective.Its proof relies on initialization, rank-approximation assumptions, and convexity in X.
  • Restricted strong convexity proof: For restricted strongly convex objectives, the lower bound combines smoothness and strong convexity with a feasible modified update.This yields the linear contraction used in the strongly convex proof.
  • Smooth convex proof: For merely smooth convex objectives, a separate lower bound controls progress toward the optimum and leads to sublinear convergence.The proof handles the smooth case through a distinct sequence of bounds and recursion.
  • Descent recursion: With the prescribed step size, the proof shows that the distance-based potential decreases or remains controlled across iterations.The recursion is obtained by expanding the update and applying smoothness-based bounds.

7 Related work

Related work spans convex SDP solvers, first-order methods, and specialized matrix-factorization algorithms, while this paper targets general convex objectives with convergence guarantees for the factored formulation.

  • Convex approaches: Classical SDP methods include interior-point algorithms for linear objectives and first-order methods aimed at improving scalability.Large-scale SDPs motivated approaches such as augmented-Lagrangian and spectral-bundle methods.
  • Convex approaches: For generic smooth convex objectives, SparseApproxSDP uses rank-1 gradient refinements and provides sublinear approximation guarantees.Its output is explicitly controlled by the iteration-dependent rank.
  • Factorization methods: Specialized factorization methods cover matrix completion, phase retrieval, nonnegative matrix factorization, and sparse PCA, often with linear rates from good initializations.These guarantees generally apply to particular problem structures rather than arbitrary convex objectives.
  • Factorization methods: Prior factorized approaches may require local assumptions in the factored space, bounded gradients, or additional structural conditions.The cited framework can also accommodate extra constraints when a faithfulness property holds.

8 Conclusion

The paper analyzes factored gradient descent for convex optimization over the positive semi-definite cone. It establishes convergence guarantees despite the non-convex factorization and identifies initialization and extension directions for future work.

  • Factored gradient descent factorizes X as UU^⊤, introducing non-convexity while targeting convex positive semi-definite optimization.
  • When f is smooth and (restricted) strongly convex, an appropriate non-trivial step size yields linear convergence; smooth objectives alone yield sublinear convergence.
  • Future work includes weaker or absent initialization requirements, accelerated convergence rates, and extensions to stochastic or coordinate descent.
  • Non-smooth constraints on factor variables, including those arising in sparse PCA, motivate extensions using proximal techniques.

B.1 Proof of Lemma 6.2

The proof of Lemma 6.2 derives a descent bound for factored gradient descent under strong convexity. It uses a surrogate step, smoothness, optimality, and local factor-distance bounds to control the non-convex update.

  • The proof introduces a pseudo-iterate and surrogate step size because the factored update is unprojected.
  • The surrogate matrix remains feasible for the original problem, allowing optimality of X⋆ and smoothness of f to bound the objective change.
  • Restricted strong convexity supplies a lower bound involving the matrix error, while KKT conditions control the optimum-gradient term.
  • Combining the bounds produces a positive descent guarantee for the factored gradient update.
  • The selected step size is defined using M, the current matrix norm, and a gradient term, then bounded through local spectral and distance estimates.

C Main lemmas for the smooth case

The smooth-case lemmas relate factor-space updates and distances to matrix-space errors and gradient terms. Together they establish local descent and non-increasing factor distance under smooth convex objectives.

  • The lemmas bound error terms involving ∇f(X)U and relate them to Dist(U,U⋆_r) under local initialization conditions.
  • A lower bound controls ⟨∇f(X), X−X⋆_r⟩ for smooth convex f, using the optimum and a condition on factor distance.
  • The proof uses convexity along rank-one directions and trace inequalities to establish the required sign and gradient-error relationships.
  • In the smooth-only case, removing restricted strong convexity simplifies the descent argument and yields a corresponding U-space descent condition.
  • Under the stated local assumptions, the factor distance Dist(U,U⋆_r) is non-increasing across FGD iterations.

D.1 Proof of Lemma 5.1

The proof of Lemma 5.1 compares factored and projected-gradient quantities through spectral and Frobenius norm bounds. Projection properties and strong convexity support the initialization analysis.

  • The argument compares consecutive matrix estimates with the optimum using projected-gradient bounds and condition-number-dependent spectral estimates.
  • A sufficiently small matrix update implies a Frobenius-distance bound to X⋆, with the factor τ(X^r)σ_r(X) controlling the scale.
  • The proof uses PSD structure, truncation, Weyl inequalities, and projection onto the PSD cone to control rank and spectral perturbations.
  • Strong convexity around X⋆ and the feasible point 0 yields a gradient-based lower bound involving m and ∥X⋆∥².

E Dependence on condition number in linear convergence rate

FGD’s convergence rate depends not only on the conditioning of f but also on the condition number of the optimal matrix X⋆. The analysis links this dependence to the factor U in the reparameterized gradient and confirms it empirically for matrix sensing.

  • Condition-number dependence: FGD’s convergence rate depends on the condition number τ(X⋆), unlike classic gradient descent schemes whose rate depends on the condition number κ of f.The paper explicitly identifies τ(X⋆) as an additional factor affecting FGD convergence.
  • Hessian analysis: The extra factor U in the FGD gradient direction produces dependence on σ_r(X⋆) and ∥∇f(X⋆)∥₂, matching the scaling in FGD’s convergence factor α.This contrasts the factored update with standard gradient descent on X and explains why the conditioning of X⋆ enters the rate.
  • Hessian analysis: For separable smooth, twice-differentiable functions, the Hessian analysis assumes each entrywise component is M-smooth and m-strongly convex.The result is developed for f(X) = Σ_(i,j) ϕ_ij(X_ij), with a rank-r optimum X⋆ = U⋆(U⋆)ᵀ.
  • Hessian analysis: At an optimum, the Hessian has zero-curvature directions associated with rotations of U⋆, while directions orthogonal to U⋆ admit a positive lower bound involving σ_min(X⋆).The factorization makes U⋆R optimal for rotation matrices R, creating multiple zero-gradient points and corresponding Hessian degeneracy.
  • Empirical validation: In matrix sensing experiments with n = 50, m = ⌈2n log n⌉, and rank r = 2, larger τ(X⋆) produces slower convergence in log error versus iterations.The experiment uses Gaussian linear measurements and least-squares optimization in the UUᵀ parameterization.
  • Matrix sensing setting: Under restricted isometry settings, restricted strong convexity connects the sensing operator’s low-rank geometry to FGD’s convergence analysis.RIP and restricted strong convexity both lower-bound ∥A(X)∥₂² on restricted low-rank sets, and RIP implies restricted strong convexity.

F.3 Empirical results

The experiments evaluate FGD’s step-size selection, initialization, convergence behavior, and computational efficiency across affine rank minimization, matrix sensing, and quantum state tomography settings. Results show faster convergence in iterations or total time in several comparisons, while convergence depends on initialization, step size, rank, and the optimum’s spectral condition.

  • Step size and initialization: FGD’s step-size rule produced linear convergence, although carefully tuned constant step sizes could sometimes perform better and required trial and error.Line search could identify better per-iteration steps, but may be computationally undesirable or infeasible for complicated objectives.
  • Step size and initialization: Arbitrary or configuration-specific constant step sizes could converge slowly or degrade when the number of observations changed.Figure 5 varied Csam over {4, 6, 10} with n = 1204 and rank r = 5 across 20 Monte Carlo trials.
  • Comparison with projected methods: With the same initialization, FGD required fewer iterations than SVP (SDP) under the proposed step-size selection.The comparison used Csam = 6 and rank configurations r = 5 and r = 10.
  • Comparison with projected methods: Avoiding per-iteration SVD projections reduced FGD’s per-iteration computational burden relative to SVP (SDP).When step sizes and initialization were held fixed, the SVD-based PSD projection in SVP (SDP) became a time bottleneck.
  • Spectral and rank effects: FGD converged more slowly as the optimum’s condition number worsened, including a plateau near the 80th iteration when σ1(X⋆)/σ3(X⋆) = 100.For rank r = 2, convergence was similar across the tested σ3(X⋆) values because the relevant spectral dependence differed.
  • High-rank PSD problems: In high-rank PSD problems with r = O(n), FGD converged faster than low-rank projection methods in practice and outperformed SparseApproxSDP in total execution time.The tested settings included n = 1024 or 2048, with r = n/4 or n/8; RSVP and SparseApproxSDP did not require specialized initialization procedures theoretically.

I.2 Proof of linear convergence

For restricted strongly convex objectives, the proof establishes a locally contracting FGD update using a problem-dependent step size. The contraction factor depends on the restricted strong-convexity parameter, the smallest nonzero singular value at the optimum, smoothness, and gradient terms.

  • Theorem I.4: Theorem I.4 analyzes FGD for restricted strongly convex f using the update U+ = U − η∇f(X)U.The theorem assumes a current iterate near U⋆ and sets X = UU⊤.
  • Step-size choice: The prescribed step size is bη = 1/[16(M∥X∥2 + ∥∇f(X)QUQ⊤U∥2)].This choice is used in the convergence bound for the factored update.
  • Contraction rate: The contraction parameter is α = 1 − mσr(X⋆)/[64(M∥X⋆∥2 + ∥∇f(X⋆r)∥2)].The resulting estimate U+ remains controlled in distance to U⋆ under the theorem’s assumptions.
  • Proof strategy: The proof applies smoothness to the feasible matrix X+ = U+(U+)⊤ and then invokes restricted strong convexity because rank(X⋆r) = r.Intermediate bounds are combined with auxiliary lemmas to complete the contraction argument.
  • Proof strategy: The bound is refined by introducing the strong-convexity parameter m and condition number κ, with auxiliary singular-value and distance bounds controlling error terms.The proof uses Lemma A.3 and related inequalities to bound terms involving Δ and σr(X).
Loading 1509.03917v3…