PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations

Yuanzhi Li, Tengyu Ma, Hongyang Zhang

arXiv:1712.09203v5cs.LGcs.DSmath.OCstat.ML

TL;DR

Over-parameterized matrix factorization can have many zero-training-error solutions, and the paper asks whether gradient descent selects a low-complexity one. It analyzes squared-loss training from small initialization and shows recovery of the true low-rank matrix under RIP, with an extension to quadratic-activation networks.

  • Problem

    Over-parameterized matrix factorization admits zero-training-error solutions that do not recover the target, while the conjecture that gradient descent prefers a small trace-norm solution was supported by empirical evidence.

    Source: §1.1 · p. 2

  • Method

    The paper analyzes gradient descent on a full-rank factorized squared-loss model from small initialization, using RIP and an approximately low-rank characterization of the iterates.

    Source: §1 · p. 2, §1.1 · p. 3

  • Results

    Under RIP, gradient descent from small initialization converges to the true low-rank matrix, which is also the minimum trace-norm solution.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The over-parameterized method can select the minimum-rank or trace-norm solution fitting the data without knowing the correct rank in advance.

    Source: §1 · p. 2

    Whether similar results hold for deeper networks, other activations such as ReLU, and losses such as logistic loss remains open.

    Source: §7 · p. 21

Abstract

from arXiv · show

We show that the gradient descent algorithm provides an implicit regularization effect in the learning of over-parameterized matrix factorization models and one-hidden-layer neural networks with quadratic activations. Concretely, we show that given $\tilde{O}(dr^{2})$ random linear measurements of a rank $r$ positive semidefinite matrix $X^{\star}$, we can recover $X^{\star}$ by parameterizing it by $UU^\top$ with $U\in \mathbb R^{d\times d}$ and minimizing the squared loss, even if $r \ll d$. We prove that starting from a small initialization, gradient descent recovers $X^{\star}$ in $\tilde{O}(\sqrt{r})$ iterations approximately. The results solve the conjecture of Gunasekar et al.'17 under the restricted isometry property. The technique can be applied to analyzing neural networks with one-hidden-layer quadratic activations with some technical modifications.

1 Introduction

The paper studies how gradient descent can regularize over-parameterized, nonconvex models, where many solutions fit the training measurements but may not recover the target. It shows that small initialization and factorized training recover low-rank matrices under RIP, and extends the analysis to one-hidden-layer quadratic networks.

1.1 Setup and Main Results

  • Under RIP, gradient descent from small initialization on a full-rank factorization converges to the true low-rank matrix, which is also the minimum trace-norm solution.Over-parameterization avoids requiring the rank in advance; the theorem’s iteration complexity is approximately 1/η ≈ √r.Source: §1 · p. 2, §1.1 · p. 3
  • Over-parameterization permits zero-training-error factors whose product differs from the target, so training loss alone does not identify the desired solution.The paper’s setting assumes noiseless measurements and RIP for the matrix-sensing result.Source: §1.1 · p. 2
  • The iterates remain approximately low-rank because they stay near the set of matrices whose rank is no greater than the minimum rank that fits the labels.The relevant set depends on the labels rather than the measurement matrices; low-rankness then supports generalization.Source: §1.1 · pp. 3–4
  • Factorization contributes a denoising effect that slows growth of the iterates’ eigenvalue tails, unlike gradient descent directly on X with PSD projection.The paper reports that direct-space gradient descent generalizes less well empirically than factorized training.Source: §1.1 · p. 4

1.2 Extensions to Neural Networks with Quadratic Activations

  • The analysis extends to one-hidden-layer quadratic networks, for which a variant of gradient descent achieves generalization with ˜O(dr^5κ^6) examples.The authors note that the bound’s dependence on r is likely loose.Source: §1.2 · pp. 4–5
  • The neural-network analysis connects quadratic activations to matrix sensing with rank-1 measurements and also covers SGD when batches are sufficiently large.The stated batch-size condition is at least ≳dr^5κ^6.Source: §1.2 · p. 5

2 Preliminaries and Related Work

The section frames gradient-descent analysis around how restricted isometry can control iterates with limited measurements, then places the approach in work on implicit regularization and matrix factorization. It highlights the challenge of understanding the update’s effect on the factor while distinguishing this analysis from earlier approaches.

2 Preliminaries and Related Work

  • A central challenge is understanding how the update transforms U_t so gradient descent reaches the target factor quickly.The analysis must account for the dependence of U_t on the measurement matrices and for the limited number of measurements, which is insufficient for concentration in Euclidean norm.Source: §2 · pp. 5–6
  • RIP partially addresses these obstacles by approximately preserving low-rank matrix geometry, yielding lemmas on inner products and matrix actions.The stated extensions to higher-rank matrices have weaker bounds, which the text attributes to the finite number of measurements.Source: §2 · p. 6

2.1 Related Work

  • Gunasekar et al. [16] conjectured implicit regularization in matrix factorization, while related analyses studied logistic regression [35] and stability-based SGD bounds [19].The text notes that label-independent stability analysis may yield pessimistic bounds, and that explaining large-margin solutions from unregularized SGD remains unclear [2].Source: §2.1 · p. 7
  • Earlier matrix-sensing work used nuclear-norm relaxation, while later work analyzed nonconvex optimization with low-rank parameterizations [15] [3].The related-work discussion also cites quadratic-activation network landscape analysis [33] and empirical regularization from factorized recurrent networks [20].Source: §2.1 · p. 7

3 Proof Overview and Rank-1 Case

The proof strategy keeps gradient-descent iterates approximately low-rank so empirical and population risks can be compared on the trajectory. The rank-1 warm-up illustrates how the signal grows while the orthogonal error remains small.

3 Proof Overview and Rank-1 Case

  • The rank-1 warm-up shows that the (r + 1)-th singular value stays small while the top r singular vectors and values of UtUt^T converge to those of X* in logarithmic iterations.Source: §3 · p. 7
  • The population-risk update pushes Ut toward the signal span and contracts its singular values, so directions orthogonal to the signal shrink.Source: §3 · p. 8
  • The proof plan keeps the population-risk trajectory approximately low-rank, uses restricted uniform convergence to relate empirical and population risks there, and requires convergence before effective rank increases.These steps address the possibility that distance from the low-rank set accumulates over iterations.Source: §3 · p. 8

3.1 Warm-up: Rank-1 Case

  • In the rank-1 case, the signal term grows toward unit norm while the orthogonal error remains small, yielding approximate recovery.A signal of unit norm with zero error gives exact recovery.Source: §3.1 · p. 9
  • The rank-1 Theorem 3.1 is weaker than Theorem 1.1: its final error depends on the RIP parameter rather than linearly on initialization.Source: §3.1 · p. 9

4 Proof Outline of Rank-r Case

The rank-r proof tracks the iterates using a changing signal subspace and an error component. It establishes conditions for this decomposition to remain controlled and obtains linear convergence once the signal is sufficiently large.

4 Proof Outline of Rank-r Case

  • The theorem assumes a small initialization and an RIP condition on the measurement matrices.The theorem's stated initialization range is α ∈ (0, c/d), for a sufficiently small absolute constant c.Source: §4 · pp. 13–14
  • The proof decomposes each iterate using a recursively changing r-dimensional subspace that starts at the span of U* and stays close to it.The rank-r analysis uses this adaptive subspace rather than the fixed signal subspace used in the rank-1 case.Source: §4 · p. 14
  • The error component may grow exponentially, but the signal component grows faster and remains larger throughout the controlled trajectory.Source: §4 · p. 14
  • Once the signal is large enough, UtUt^T converges linearly to X* up to a small error.Source: §4 · p. 14

5 Neural networks with Quadratic Activations

The paper extends its matrix-sensing analysis to one-hidden-layer quadratic networks by truncating rank-one measurements to recover a restricted isometry property. Its network algorithm adds dynamic rescaling, while assuming the true parameter’s Frobenius norm is known.

5 Neural networks with Quadratic Activations

  • The network algorithm uses dynamic rescaling, which scales iterates down when their norm is small and up when it exceeds the norm of U⋆.The authors say this resembles weight decay, but standard weight decay or ℓ2 regularization cannot achieve zero recovery error in the noiseless setting.Source: §5 · pp. 16–17
  • The analysis assumes the true parameter’s Frobenius norm is known; estimating it from average predictions is suggested, but robustness to estimation error is left for future work.The algorithm takes this norm as τ.Source: §5 · p. 17
  • For Gaussian inputs, the network examples correspond to rank-one matrix-sensing measurements, but those measurements do not satisfy RIP with high probability before truncation.The paper therefore optimizes a truncated empirical risk for technical reasons.Source: §5 · pp. 16–17
  • Truncating Gaussian rank-one measurements makes them satisfy a restricted isometry property, allowing the matrix-sensing analysis to be reused for quadratic networks.The theorem proof replaces the matrix-sensing RIP bounds with the truncated-measurement lemma, using a δ parameter smaller by a factor of r.Source: §5 · pp. 17–18

6 Simulations

The simulations examine initialization, longer training, projected gradient descent, and stochastic gradient descent. They report better generalization with smaller initializations, continued test-error decrease, and stronger recovery from the factorized model than from projected gradient descent.

Choice of initialization

  • As initialization α decreases, the gap between training and test error narrows; at α = 1.0, training error falls below 10^-4 while test error remains on the order of 10^-1.The initialization comparison uses m = 5dr samples with rank r = 5.Source: §6 · p. 19, Figure 1 · p. 19

Accuracy

  • With initialization U0 = 0.01 Id, test error continues to decrease gradually through 10^5 iterations, so the experiment suggests early stopping is not necessary.The experiment uses the same parameters as the initialization experiment.Source: §6 · pp. 18–19, Figure 3 · p. 20

Projected gradient descent

  • The factorized model consistently recovers X⋆ accurately, while projected gradient descent performs worse and degrades further as d grows from 100 to 150.The comparison varies the number of sensing matrices from 5d to 35d and uses rank-one X⋆.Source: §6 · p. 20, Figure 4 · p. 20

Stochastic gradient descent

  • With identity initialization, stochastic gradient descent reduces training error to 10^-7 but leaves test error large.The experiment uses d = 100, r = 5, and m = 5dr random samples.Source: §6 · pp. 20–21, Figure 5 · p. 21

7 Conclusions

The paper theoretically explains gradient descent’s regularization in over-parameterized matrix factorization and one-hidden-layer neural networks with quadratic activations. Extending similar results to deeper networks and other activations or losses remains open.

7 Conclusions

  • Gradient descent prioritizes searching through low-complexity models in the matrix-factorization and quadratic-activation neural-network settings.Source: §7 · p. 21
  • Establishing similar results for deeper networks with activations such as ReLU and losses such as logistic loss remains an open question.Source: §7 · p. 21

A.1 Proof of Proposition 4.5

This proof bounds the next-step error using the update rule and restricted isometry property (RIP), then completes Proposition 4.5 using the target’s spectral-norm bound and the iterate’s column span.

  • The proof starts with a triangle-inequality bound on E_{t+1} in terms of E_t.Source: §A.1 · p. 21
  • The RIP controls the effect of M_t when bounding M_tE_t.Source: §A.1 · p. 22
  • The final step uses that X* has spectral norm below 1 and S_t is the column span of Z_t to complete Proposition 4.5.Source: §A.1 · p. 23

A.2 Proof of Proposition 4.6

The appendix bounds the update in Proposition 4.6 through a decomposition of Z_{t+1}, then prepares Proposition 4.7 by representing the iterate’s subspace deviation and introducing an intermediate iterate.

A.2 Proof of Proposition 4.6

  • The update decomposition expresses Z_{t+1} using Z_t, E_t, and the projection onto S_{t+1}.The proof uses that Z_t lies in its column subspace S_t and bounds the update using a bound on M_t.Source: §A.2 · p. 25

A.3 Proof of Proposition 4.7

  • The factor F_t measures the deviation of Z_t’s column space from U*, approximating the principal angle up to third-order terms.Source: §A.3 · p. 25
  • Because the updates of F_t and Z_t are difficult to analyze directly, the proof introduces Z̃_t to connect Z_{t+1} and F_{t+1} with Z_t and F_t.Source: §A.3 · p. 25

A.3.1 Proofs of Proposition A.6, A.7, and A.8

These proofs analyze the subspace and factor updates through an intermediate iterate, using the restricted isometry property to control perturbations and relate the update to gradient descent.

  • The proof uses the restricted isometry property on a rank-at-most-2r perturbation to control the gradient update.Source: §A.3.1 · p. 27
  • Z_{t+1} is very close to one gradient-descent step from Z̃_t, so the analysis focuses on Z̃_t.Source: §A.3.1 · p. 27
  • The intermediate iterate’s factor and subspace components are bounded through successive propositions and lemmas.The proof separately tracks R̃_t relative to R_{t+1} and F̃_t in relation to the subsequent update.Source: §A.3.1 · pp. 30–32

A.4 Proof of Proposition 4.8

The proof controls the least singular value under near-identity matrix transformations, then applies that bound to the update in Proposition 4.8. It uses the closeness of F_t to zero to relate Z_t and the transformed iterate.

A.4 Proof of Proposition 4.8

  • The technical lemma characterizes how multiplication by matrices close to identity changes a matrix’s least singular value.Its stated setting includes Y_1 and a positive semidefinite matrix Σ.Source: §A.4 · p. 32
  • The proof uses σ_min(AB) ≥ σ_min(A)σ_min(B) and σ_min(I+B) = 1 + σ_min(B) for symmetric positive semidefinite B.Source: §A.4 · p. 33
  • The least singular value of R_{t+1} is bounded from below by expressing it as a transformation of the prior iterate and applying the near-identity bound.The proof relates Z_t to the transformed iterate using that F_t is close to zero.Source: §A.4 · pp. 32–33

A.5 Proof of Proposition 4.3

The proof expands the gradient-descent error by powers of the step size and bounds its terms using rank structure and restricted-isometry tools. Its estimates include an assumption that the error matrix E_t has norm at most 1/d.

A.5 Proof of Proposition 4.3

  • The proof expands the next-step error and separates the update into terms whose bounds use rank structure and matrix norm controls.It treats degree-one, degree-two, and degree-three-and-four terms in the step size separately.Source: §A.5 · pp. 33, 35, 36
  • The degree-one and degree-two terms are handled through claims bounding components of the gradient expansion.The proof identifies Y_1, Y_2, and Y_3 as gradient components and applies matrix lemmas to control them.Source: §A.5 · pp. 34–35
  • Bounds on some error terms rely on the assumption that ∥E_t∥ ≤ 1/d.The proof uses this condition when bounding Y_2 and when controlling a term involving E_tE_t^⊤.Source: §A.5 · pp. 34–36

B Missing proofs in Section 5

The appendices supply missing proofs for Section 5 and state restricted-isometry extensions used in the analysis. They reduce general-rank arguments to rank-one components and adapt the sensing-matrix inequalities to symmetric applications.

B Missing proofs in Section 5

  • The rank-one proof bounds two terms, using symmetrization and contraction for one and a high-probability bound for bounded functions f_{u,v}.The stated probability is at least 1 − e^(−Ω(s²m/(dR⁴))).Source: B Missing proofs in Section 5 · pp. 37–38
  • For general-rank X, the missing proof reduces the argument to rank-one components and combines their bounds by the triangle inequality.The rank-one case is treated first.Source: B Missing proofs in Section 5 · pp. 37, 39

C Restricted Isometry Properties

  • For matrices satisfying the (r, δ)-restricted isometry property, the extension bounds the measurement inner product error using ∥X∥_*∥Y∥_F when rank(Y) ≤ r.The proof decomposes X by its singular value decomposition into rank-one matrices.Source: C Restricted Isometry Properties · pp. 39–40
  • For asymmetric sensing matrices, the proof uses their symmetrized versions and applies the resulting inequality when the matrices in question are symmetric.The text identifies the relevant applications as involving symmetric matrices.Source: C Restricted Isometry Properties · p. 40
Loading 1712.09203v5…