PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent

Tian Tong, Cong Ma, Yuejie Chi

arXiv:2005.08898v4cs.LGcs.ITeess.SPmath.OCstat.ML

TL;DR

Ill-conditioned low-rank estimation forces a choice between gradient descent's cheap but condition-number-dependent iterations and alternating minimization's expensive updates. The paper introduces ScaledGD, an adaptively preconditioned factor method, and theoretically shows condition-number-independent linear convergence across matrix sensing, robust PCA, and matrix completion while preserving low per-iteration cost.

  • Problem

    Existing low-rank factor methods either converge in iterations that scale with the matrix condition number or require computationally expensive iterations for large matrices.

  • Method

    ScaledGD adaptively preconditions factor-gradient updates using small matrices, retaining gradient descent's low per-iteration complexity without explicit balancing regularization.

  • Results

    Across matrix sensing, robust PCA, and matrix completion, ScaledGD variants achieve O(log(1/ǫ)) iterations independent of the condition number under stated assumptions.

  • Takeaways & Limitations

    ScaledGD provides a theoretically validated compromise between fast condition-number-independent convergence and the low per-iteration cost of gradient descent across several low-rank estimation tasks.

  • Takeaways & Limitations

    The analysis focuses on fast local convergence; strengthening sample-complexity and attraction-basin guarantees remains open, and matrix completion without projection is unresolved.

Abstract

from arXiv · show

Low-rank matrix estimation is a canonical problem that finds numerous applications in signal processing, machine learning and imaging science. A popular approach in practice is to factorize the matrix into two compact low-rank factors, and then optimize these factors directly via simple iterative methods such as gradient descent and alternating minimization. Despite nonconvexity, recent literatures have shown that these simple heuristics in fact achieve linear convergence when initialized properly for a growing number of problems of interest. However, upon closer examination, existing approaches can still be computationally expensive especially for ill-conditioned matrices: the convergence rate of gradient descent depends linearly on the condition number of the low-rank matrix, while the per-iteration cost of alternating minimization is often prohibitive for large matrices. The goal of this paper is to set forth a competitive algorithmic approach dubbed Scaled Gradient Descent (ScaledGD) which can be viewed as pre-conditioned or diagonally-scaled gradient descent, where the pre-conditioners are adaptive and iteration-varying with a minimal computational overhead. With tailored variants for low-rank matrix sensing, robust principal component analysis and matrix completion, we theoretically show that ScaledGD achieves the best of both worlds: it converges linearly at a rate independent of the condition number of the low-rank matrix similar as alternating minimization, while maintaining the low per-iteration cost of gradient descent. Our analysis is also applicable to general loss functions that are restricted strongly convex and smooth over low-rank matrices. To the best of our knowledge, ScaledGD is the first algorithm that provably has such properties over a wide range of low-rank matrix estimation tasks.

1 Introduction

Low-rank factorization makes large-scale matrix estimation tractable, but existing methods trade off condition-number-dependent convergence against expensive iterations. ScaledGD uses adaptive factor preconditioning to target condition-number-independent convergence while retaining low per-iteration cost across several estimation problems.

  • 1 Introduction: Factorizing X as LR^⊤ reduces memory and computation compared with optimizing over the full matrix, despite creating a nonconvex optimization problem.Properly initialized gradient descent and alternating minimization can still converge to the true factors for several low-rank estimation tasks.
  • 1 Introduction: Existing methods expose a central trade-off: gradient descent requires O(κ log(1/ǫ)) iterations, whereas alternating minimization has higher per-iteration cost from solving large linear systems.This motivates an algorithm combining the favorable iteration complexity of alternating minimization with the cheaper iterations of gradient descent.
  • 1 Introduction: ScaledGD preconditions each factor update by inverses of small r × r Gram matrices, adding minimal overhead while improving the search directions.The scaling is intended to permit larger step sizes without computing the full Hessian.
  • 1 Introduction: ScaledGD targets O(log(1/ǫ)) iterations independent of the condition number for matrix sensing, robust PCA, and matrix completion under standard assumptions.The guarantees use spectral initialization and are established for tailored variants of the algorithm.
  • 1 Introduction: For matrix sensing, ScaledGD improves on gradient descent from O(κ log(1/ǫ)) to O(log(1/ǫ)) iterations at the same sample-complexity requirement.The result is stated under an RIP condition involving the rank and condition number.
  • 1 Introduction: For robust PCA and matrix completion, ScaledGD variants likewise achieve O(log(1/ǫ)) iterations, with matrix completion requiring larger sample complexity than projected gradient descent.Robust PCA combines ScaledGD with hard thresholding, while matrix completion uses a projection operator.

2 Scaled Gradient Descent for Low-Rank Matrix Estimation

ScaledGD combines diagonally scaled factor updates with low-rank preconditioners to obtain condition-number-independent linear convergence while retaining inexpensive iterations across several low-rank estimation problems.

  • Scaled Gradient Descent: ScaledGD interprets factor-gradient updates as quasi-Newton steps, using two inverses of r × r matrices to keep each iteration computationally cheap.The method uses adaptive scaling of the factor search directions as a preconditioner.
  • Scaled Gradient Descent: A new scaled distance metric accounts for factor non-identifiability and preconditioning, enabling contraction analysis of the iterates.The metric aligns equivalent factorizations and incorporates diagonal scaling effects.
  • 2.1 Matrix sensing: For matrix sensing, ScaledGD reaches ǫ-accuracy in O(log(1/ǫ)) iterations independently of κ, while alternating minimization has higher per-iteration cost.The guarantee holds under an RIP condition and spectral initialization; a warm-started variant can use O(nr) measurements.
  • 2.2 Robust PCA: For robust PCA, ScaledGD with hard thresholding converges in O(log(1/ǫ)) iterations under α ≲1/(µr3/2κ), improving on projected gradient descent's κ-dependent iteration complexity.The method alternates scaled factor updates with thresholding of the residual's small entries.
  • 2.4 Matrix completion: For matrix completion, ScaledPGD achieves O(log(1/ǫ)) iterations independent of κ, but requires higher sample complexity than projected gradient descent.The paper attributes the sample-complexity increase to proof techniques and reports no numerical degradation in sample complexity.

3 Proof Sketch

The proof sketch explains ScaledGD through a scaled distance metric and quasi-Newton interpretation, then establishes local linear convergence under initialization and problem-specific conditions.

  • 3.1 A warm-up analysis: matrix factorization: ScaledGD approximates the Hessian by retaining only its diagonal blocks, giving a quasi-Newton interpretation of the adaptive scaling.The resulting preconditioners are tied to the factor-wise second derivatives rather than the full Hessian.
  • 3.1 A warm-up analysis: matrix factorization: With initialization within 0.1σr(X⋆) and step size 0 < η ≤ 2/3, ScaledGD contracts the factor distance at a constant linear rate.This improves on gradient descent's contraction rate of 1 − 1/κ for matrix factorization.
  • 3.2 Low-rank matrix sensing: For matrix sensing, RIP lets the algorithm mimic the matrix-factorization update, while spectral initialization supplies the neighborhood needed for recursive contraction.The proof combines local convergence and initialization lemmas under a 2r-RIP condition.
  • 3.3 Robust PCA: For robust PCA, initialization and iterates must satisfy both closeness and incoherence conditions; these conditions preserve linear convergence without an explicit projection step.The incoherence requirement depends on the corruption fraction, incoherence parameter, rank, and condition number.
  • 3.4 Matrix completion: For matrix completion, scaled projection maintains non-expansiveness and incoherence, enabling local linear convergence once sampling and initialization conditions hold.The analysis uses a projection radius and a sufficiently large observation probability to invoke the local convergence lemma.

4 Numerical Experiments

Experiments compare ScaledGD with vanilla gradient descent and alternating minimization across four low-rank estimation problems, varying conditioning, noise, step size, and runtime.

  • 4.1 Comparison with vanilla GD: Across matrix sensing, robust PCA, matrix completion, and Hankel completion, ScaledGD's convergence rate remains independent of κ in noise-free experiments.Figure 2 varies κ over 1, 5, 10, and 20 and tracks relative reconstruction error against iterations.
  • 4.1 Comparison with vanilla GD: ScaledGD and vanilla GD eventually reach the same statistical error under noise, but ScaledGD converges faster across SNR levels.Figure 3 uses κ = 10 and SNR values of 40, 60, and 80dB across four tasks.
  • 4.1 Comparison with vanilla GD: The step-size study evaluates relative error after 80 iterations for η from 0.1 to 1.2 in matrix completion with n = 1000, r = 10, and p = 0.2.The authors use η = 0.5 in the main comparisons and describe it as a typical comparison choice.
  • 4.2 Run time comparisons: ScaledGD and AltMin are condition-number-independent in convergence rate, while ScaledGD retains lower per-iteration cost and only minimal runtime overhead over vanilla GD.Figures 5 and 6 compare iteration count and runtime for matrix sensing and matrix completion under κ = 1, 5, and 20.
  • 4.2 Run time comparisons: The runtime experiments demonstrate competitive performance rather than claiming state-of-the-art results because runtime depends on problem parameters and implementation details.This qualification limits how broadly the runtime comparisons should be interpreted.

5 Conclusions

The paper establishes condition-number-independent convergence for ScaledGD while retaining low per-iteration cost, and identifies directions for extending and accelerating the method.

  • 5 Conclusions: ScaledGD reaches ǫ-accuracy in O(log(1/ǫ)) iterations without condition-number dependence for matrix sensing, robust PCA, and matrix completion under standard assumptions.The guarantee assumes spectral initialization and relies on a new distance metric accounting for preconditioning and factor unbalancedness.
  • Improved analysis: The analysis focuses on fast local convergence, leaving sample complexity and the size of the basin of attraction as subjects for stronger theory.For matrix completion, the paper also leaves open whether similar guarantees hold without projection.
  • Other low-rank recovery problems: Future work includes extending condition-number-independent ScaledGD guarantees to additional ill-conditioned recovery problems and applications beyond low-rank matrix estimation.Examples include robust PCA with missing data and quadratic sampling.
  • Acceleration schemes: ScaledGD may still converge slowly when the loss is ill-conditioned over low-rank matrices, motivating combinations with acceleration techniques such as momentum.The relevant loss-function condition number is denoted κf.

A.1 New distance metric

This appendix develops the proposed distance metric, establishes existence of an optimal alignment matrix, and relates the metric to low-rank matrix approximations and Frobenius norms.

  • A.1 New distance metric: The optimal alignment matrix minimizes the new distance over invertible matrices and exists under a sufficient condition established through a compact constrained reformulation.The proof uses continuity and the Weierstrass extreme value theorem after restricting the optimization domain.
  • A.1 New distance metric: A first-order condition characterizes the optimal alignment criterion for the minimizing matrix.The criterion follows by expanding the squared distance and setting the gradient to zero.
  • A.1 New distance metric: The appendix connects the new factor distance to the usual Frobenius norm through singular-value and alignment arguments.The derivation uses compact SVDs, orthonormal alignment, Weyl-type bounds, and factor perturbation relations.
  • A.1 New distance metric: The partial Frobenius norm is characterized through top-r singular values, rank-r variational representations, and top-r right singular vectors.The best rank-r approximation Pr(X) also minimizes approximation error under this partial norm.

B Proof for Low-Rank Matrix Factorization

This section expresses the factor gradients and Hessians and rewrites the ScaledGD update in vectorized form for subsequent analysis.

  • B Proof for Low-Rank Matrix Factorization: The gradients and Hessians of the factorized loss are explicitly formulated with respect to L and R.The Hessian expressions are written for vectorized factor variables.
  • B Proof for Low-Rank Matrix Factorization: The ScaledGD factor update is rewritten in vectorized form to support the proof analysis.This representation prepares the update for the subsequent convergence arguments.

B.2 Proof of Theorem 5

The proof establishes contraction of the new distance under ScaledGD, preserves optimal alignment, and uses restricted isometry and perturbation bounds to control the update terms.

  • B.2 Proof of Theorem 5: The proof maintains the existence of an optimal alignment matrix Qt between each iterate Ft and the ground truth F⋆.This property is propagated using the earlier existence lemma.
  • B.2 Proof of Theorem 5: The induction expands the ScaledGD update around the factor errors and controls three resulting terms, F1, F2, and F3.The first term is nonnegative, while the latter terms are bounded using scaled factor-error controls.
  • B.2 Proof of Theorem 5: The low-rank matrix sensing argument invokes the 2r-RIP assumption to bound measurement-operator terms in the update analysis.The resulting estimates use Frobenius/operator norm relations and analogous bounds for the second factor square.

C.1 Proof of Lemma 1

The proof establishes contraction by aligning the iterates, decomposing the error into a main term and perturbations, and bounding each component. Under the stated parameter conditions, the contraction factor is at most 1 − 0.6η.

  • C.1 Proof of Lemma 1: The proof decomposes the aligned update error into one main term and three perturbation terms, then controls them separately.The alignment matrix exists under the local-distance condition, allowing the factors to be rewritten relative to the target.
  • C.1 Proof of Lemma 1: The factor-error bound ∥F_t − X⋆∥F ≤ 1.5 dist(F_t, F⋆) follows from Lemma 13, leaving distance contraction as the central proof task.
  • C.1 Proof of Lemma 1: The resulting bounds combine into a contraction rate ρ(η; ϵ, δ2r) expressed in terms of the step size, local tolerance, and perturbation parameter.
  • C.1 Proof of Lemma 1: With ϵ = 0.1, δ2r ≤ 0.02, and 0 < η ≤ 2/3, the rate satisfies ρ(η; ϵ, δ2r) ≤ 1 − 0.6η.

C.2 Proof of Lemma 2

The proof combines initialization properties, truncation bounds, and aligned-factor error decompositions to establish contraction and preserve incoherence. For ϵ = 0.02 and αμr ≤ 10^-4, the distance contraction has rate at most 1 − 0.6η.

  • C.2 Proof of Lemma 2: The proof first relates the initialized factor distance to the rank-2r matrix error and uses truncation and incoherence lemmas to control the initialization.
  • C.2 Proof of Lemma 2: The truncation analysis bounds sparse-error entries using row and column order statistics, yielding the stated ℓ∞ norm bound.
  • C.2 Proof of Lemma 2: The aligned update error is decomposed into a main term and three perturbation terms, whose collective bounds control the next-iterate distance.
  • C.2 Proof of Lemma 2: With ϵ = 0.02, αμr ≤ 10^-4, and 0 < η ≤ 2/3, the contraction rate satisfies ρ(η; ϵ, αμr) ≤ 1 − 0.6η.
  • C.2 Proof of Lemma 2: Under the same small-error conditions and 0.1 ≤ η ≤ 2/3, the proof also establishes the required incoherence condition.

D.3 Proof of Lemma 5

The proof establishes initialization guarantees by analyzing the truncated sparse component and the top-r SVD of the resulting matrix. It then controls the aligned factor errors and obtains the stated conclusion under incoherence conditions.

  • D.3 Proof of Lemma 5: The initialization uses the top-r SVD of Y − Tα[Y], where Y = X⋆ + S⋆, and analyzes its aligned factorization.
  • D.3 Proof of Lemma 5: The factor-error analysis separately controls the terms I1 and I2 using operator, ℓ1,∞, and ℓ2,∞ norm inequalities.
  • D.3 Proof of Lemma 5: The truncation lemmas show that S⋆ − Tα[X⋆ + S⋆] has at most 2αn2 nonzero entries per row and is bounded entrywise by 2∥X⋆∥∞.
  • D.3 Proof of Lemma 5: Combining the bounds yields the desired conclusion when ϵ = 0.02 and αμrκ ≤ 0.1.

E.1.2 Proof of Lemma 6

The proof establishes that the projection used in the factor update contracts each row under a suitable scaling condition. A scalar monotonicity argument verifies the rowwise contraction, after which the result is combined with incoherence control.

  • E.1.2 Proof of Lemma 6: The proof identifies a projection that contracts each row and applies it to the aligned factor representation.
  • E.1.2 Proof of Lemma 6: The proof then combines the rowwise contraction with the factor-distance and incoherence bounds to reach the desired conclusion.
  • E.1.2 Proof of Lemma 6: For vectors u and u⋆ with λ ≥ ∥u⋆∥2/∥u∥2, the scalar function h(λ) is shown to be monotone on the relevant range.
  • E.1.2 Proof of Lemma 6: The monotonicity argument gives h(λ) ≤ h(1), establishing the claimed rowwise contraction.

E.2 Proof of Lemma 7

The proof establishes the required contraction by decomposing the update error into one main term and several perturbation terms, then bounding them under high-probability sampling conditions. The resulting inequalities yield the target bound when the sampling rate and step size satisfy the stated conditions.

  • The argument operates on an event where the auxiliary sampling bounds hold simultaneously, with overwhelming probability.This event is defined as the intersection of the events in Lemmas 21 and 22.
  • The factors are aligned with the ground truth, and the projected next iterate is reduced to proving a corresponding pre-projection distance relation.The proof introduces the optimal alignment matrix, aligned factor errors, and the projected update.
  • The update error is decomposed into a main term and perturbation terms, which are controlled separately before being combined.The proof identifies P1 as the main term and P2, P3, and P4 as perturbation terms.
  • The main-term and perturbation bounds collectively produce the desired contraction inequality for the factor distance.Bounds for P1 through P4 are combined, followed by an analogous treatment of the second square.
  • A sufficiently large sampling rate ensures δ1+δ2 ≤ 0.1, and for 0 < η ≤ 2/3 the contraction factor satisfies ρ(η; ǫ, δ1, δ2) ≤ 1 − 0.6η.These conditions lead directly to the upper bound identified as equation (67).

F.1 Proof of Theorem 4

The theorem proof analyzes ScaledGD near the target by introducing an auxiliary restricted-smooth and convex function and decomposing the update into four terms. Under the stated step-size and neighborhood conditions, it obtains a contraction rate bounded by 1 − 0.7ηµ.

  • The analysis aligns the iterates with the target, defines factor errors, and studies the update within a local distance neighborhood.The proof assumes dist(Ft, F⋆) ≤ 0.1σr(X⋆)/√... and uses the optimal alignment matrix.
  • An auxiliary function with restricted smoothness and convexity is combined with the ScaledGD update to expand the error into four analyzable terms.The factor-product error is decomposed using LR⊤−X⋆= ∆LR⊤ + L⋆∆R⊤.
  • The four component bounds are combined with gradient and distance inequalities to derive the contraction expression.The proof uses Lemma 24 and related inequalities to control the gradient-dependent terms.
  • The proof establishes the contraction rate ρ(η; ǫ, µ, L) ≤ 1 − 0.7ηµ under the stated step-size and conditioning conditions.The bound applies when 0 < η ≤ 0.4/L and ηµ ≤ 0.4.
  • The numerical contraction-rate verification is presented under a stricter condition, while verifying κf more generally requires a subtler analysis.The proof explicitly notes the stricter setting ǫ = 0.02/√... for the displayed rate argument.
Loading 2005.08898v4…