PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization

Sanjeev Arora, Nadav Cohen, Elad Hazan

arXiv:1802.06509v2cs.LG

TL;DR

The paper asks whether depth necessarily complicates optimization or can improve it independently of expressiveness. It analyzes linear networks as depth-induced overparameterizations and finds that depth acts as an implicit preconditioner that can accelerate convergence, while this effect is not obtainable from any fixed regularizer.

  • Problem

    Deep learning lacks a full theoretical account of how depth affects optimization, amid a consensus that greater expressiveness comes with more difficult optimization.

  • Method

    The paper studies gradient-descent differential equations for arbitrarily deep linear networks, where added layers replace one matrix parameter with a product of matrices without changing expressiveness.

  • Results

    Depth-induced overparameterization acts as a preconditioning scheme combining adaptive learning rates and momentum, accelerating optimization even for ℓp regression with p > 2 and sometimes outperforming AdaGrad and AdaDelta.

  • Takeaways & Limitations

    Overparameterization by depth can accelerate optimization on simple problems without changing expressiveness, and its effect cannot be attained via gradients of any fixed regularizer.

  • Takeaways & Limitations

    Very deep networks with small initialization can suffer vanishing gradients because the end-to-end matrix becomes extremely close to zero; complete nonlinear-network analysis remains challenging.

Abstract

from arXiv · show

Conventional wisdom in deep learning states that increasing depth improves expressiveness but complicates optimization. This paper suggests that, sometimes, increasing depth can speed up optimization. The effect of depth on optimization is decoupled from expressiveness by focusing on settings where additional layers amount to overparameterization - linear neural networks, a well-studied model. Theoretical analysis, as well as experiments, show that here depth acts as a preconditioner which may accelerate convergence. Even on simple convex problems such as linear regression with $\ell_p$ loss, $p>2$, gradient descent can benefit from transitioning to a non-convex overparameterized objective, more than it would from some common acceleration schemes. We also prove that it is mathematically impossible to obtain the acceleration effect of overparametrization via gradients of any regularizer.

1. Introduction

The paper challenges the expressiveness–optimization trade-off by showing that increasing depth can accelerate optimization without changing expressiveness in linear networks.

  • 1. Introduction: Increasing depth can accelerate optimization, countering the conventional expressiveness-versus-optimization trade-off.The effect resembles momentum and adaptive regularization while requiring no other modification.
  • 1. Introduction: Linear neural networks isolate depth’s optimization effect because added layers replace one matrix parameter with a product of matrices without altering expressiveness.This replacement is an overparameterization rather than a representational change.
  • 1. Introduction: Depth-induced overparameterization makes gradient descent behave like shallow-network training with a particular preconditioning scheme.The scheme combines momentum with adaptive learning rates and can significantly speed training on ℓp regression for p > 2.
  • 1. Introduction: Overparameterization can outperform naïve gradient descent and, in some experiments, AdaGrad and AdaDelta.The effect also appears empirically in a nonlinear model formed by replacing hidden layers with depth-2 linear networks.
  • 1. Introduction: The paper reports that acceleration through overparameterization need not be computationally expensive and depends on depth rather than width.Theory and experiments indicate that wide and narrow overparameterized networks have the same optimization effect from this perspective.

2. Related Work

Related work studies optimization dynamics, objective landscapes, and acceleration methods; this paper differs by analyzing depth-induced acceleration for general losses and depths.

  • 2. Related Work: Prior theoretical work analyzes critical points and landscape properties in linear networks and under restrictive assumptions for nonlinear networks.Examples include local minima, saddles, and monotonically descending paths to global optima.
  • 2. Related Work: Fukumizu and Saxe analyze gradient descent through differential equations for linear networks, mainly focusing on ℓ2 regression.Fukumizu studies only a two-layer network, while Saxe considers depths beyond two.
  • 2. Related Work: Saxe et al. conclude that increasing depth can modestly slow optimization, whereas this paper finds acceleration for ℓp regression when p > 2.The differing loss setting explains the contrast between the conclusions.
  • 2. Related Work: Accelerated-gradient methods accumulate gradients across the optimization path, while preconditioners alter optimization using direction- or curvature-related information.Momentum and Newton-style preconditioning provide established comparison points for the paper’s analysis.
  • 2. Related Work: The paper excludes work proposing theoretical guarantees for non-convex optimization because it focuses on algorithms already used by practitioners.This defines the scope of the related-work comparison.

3. Warmup: ℓp Regression

The warmup shows that replacing a linear-regression parameter vector by a vector–scalar product can implicitly transform gradient descent into an adaptive accelerated method.

  • 3. Warmup: ℓp Regression: A single-scalar overparameterization can have an immense optimization effect in linear regression with ℓp loss.Gradient descent on the overparameterized objective corresponds to accelerated gradient descent on the original objective.
  • 3. Warmup: ℓp Regression: The model replaces w with the product of a vector w1 and scalar w2, creating a non-convex objective without changing the linear model’s expressiveness.The paper asks how this reparameterization changes gradient-descent dynamics.
  • 3. Warmup: ℓp Regression: Gradient descent over L(w1,w2) with a fixed small learning rate and near-zero initialization is equivalent to gradient descent over L(w) with adaptive learning rate and momentum.This is stated as Observation 1 for the warmup construction.
  • 3. Warmup: ℓp Regression: Near-zero initialization makes the underlying parameter w a weighted combination of past gradients at every iteration.The weights are represented by coefficients µ(t,τ).
  • 3. Warmup: ℓp Regression: The resulting dynamics use time-varying adaptive learning rates and momentum coefficients.This follows from the dynamics of the underlying parameter w = w1w2 after neglecting O(η2) terms for small η.

4. Linear Neural Networks

The paper formulates depth-N linear networks as products of layer matrices, allowing optimization effects of depth to be studied independently of expressiveness.

  • 4. Linear Neural Networks: Training loss is defined over parameterized linear predictors and evaluated on a labeled training set using a point-wise loss.The parameterized loss maps the network’s weight matrices to nonnegative training-loss values.
  • 4. Linear Neural Networks: A depth-N linear network maps x to W_NW_{N−1}· · ·W_1x, with each W_j representing one layer’s weight matrix.The input and output dimensions are d and k, with hidden widths determining intermediate matrix dimensions.
  • 4. Linear Neural Networks: The paper distinguishes depth-induced overparameterization from direct linear parameterization while keeping the predictor family linear.This setup provides the basis for comparing optimization across depths.
  • 4. Linear Neural Networks: The analysis focuses on how gradient-descent behavior depends on N, especially whether increasing depth can accelerate convergence.Depth-1 networks are treated as directly parameterized linear predictors.
  • 4. Linear Neural Networks: For depth-N networks, the only difference from a depth-1 linear model is replacing a matrix parameter with a product of N matrices.Thus any acceleration from increasing N is attributed to depth-induced overparameterization rather than increased expressiveness.

5. Implicit Dynamics of Gradient Descent

The paper derives how depth changes gradient-descent dynamics in linear networks: the end-to-end matrix follows shallow-model optimization with a depth-dependent preconditioner. This preconditioning favors directions aligned with prior movement and is independent of hidden widths.

  • Implicit dynamics: Gradient descent on a depth-N linear network can be rewritten as preconditioned gradient descent on the corresponding depth-1 model.The result is derived from continuous-time dynamics and translated into an end-to-end update rule.
  • Implicit dynamics: The analysis uses continuous differential equations to characterize the end-to-end matrix We under small learning rates and structured near-zero initialization.The discrete-to-continuous approximation requires a sufficiently small learning rate, while the initialization must approximately satisfy the stated alignment conditions.
  • Preconditioning: The induced transformation acts as a positive-semidefinite preconditioner whose eigendirections are determined by the singular vectors of We.Its eigenvalues depend on the corresponding singular values, so the gradient is transformed according to the current end-to-end matrix.
  • Acceleration interpretation: Overparameterization promotes movement along directions already taken by optimization, which the paper interprets as an acceleration effect.Near-zero initialization lets the current parameter location represent the cumulative movement from initialization.
  • Width versus depth: The end-to-end update depends on depth but not hidden widths, so wide and narrow networks have the same optimization effect at a given depth.The paper therefore attributes the optimization effect to depth rather than width and reports a minimal computational price.
  • Single-output dynamics: In the single-output case, depth introduces an adaptive learning-rate factor and amplifies the gradient projection onto the current end-to-end direction.The adaptive scaling increases with distance from initialization, while the projection amplification behaves like a momentum term.

6. Overparametrization Effects Cannot Be Attained via Regularization

The paper proves that overparameterization-induced acceleration cannot generally be reproduced by adding a fixed regularizer to the original loss. The proof constructs a vector field with a nonzero closed-curve line integral, contradicting gradient-field behavior.

  • Scope of theorem: The conclusion requires N > 2 under the stated assumptions; N = 2 needs additional assumptions on the shallow loss.Without those assumptions, a nonzero linear loss provides a counterexample whose transformed field is itself a gradient.
  • Main result: For the single-output case, no function of W has a gradient field equal to the vector field induced by overparameterization.The result excludes obtaining the same dynamics by adding a regularization term to the original training loss.
  • Proof strategy: The proof uses the fundamental theorem for line integrals: gradients of differentiable functions integrate to zero around every closed curve.The authors construct a closed curve Γr,R on which the transformed field has a positive line integral as r and R approach zero.
  • Main result: Overparameterization transforms the original gradient into a direction depending on both the gradient and the current parameter point.This transformation differs from simply following the original gradient of the shallow model.

7. Illustration of Acceleration

A two-coordinate linear-regression example shows how depth couples otherwise independent errors under ℓp loss. When p > 2 and y1≫y2, this coupling can accelerate the slower coordinate while controlling the faster one.

  • Baseline convergence: With sufficiently small learning rate, both residuals eventually reach Δ1* = Δ2* = 0 under ordinary gradient descent.This condition prevents divergence in the baseline dynamics.
  • Linear regression example: For p > 2 with y1≫y2, ordinary gradient descent makes Δ2 converge very slowly because the learning rate is determined by the larger target coordinate.The example describes this as an ill-conditioned problem with no communication between coordinates.
  • Overparameterized dynamics: Overparameterization couples the coordinates, so reducing Δ1 changes the effective learning rate governing the other coordinate.The update rule is the single-output depth-induced dynamics from Equation 12.
  • Acceleration mechanism: The mechanism can temporarily slow Δ2 while preventing Δ1 from diverging, after which faster progress in Δ1 helps accelerate Δ2.The paper formalizes this intuition in a special case and derives a concrete acceleration bound.

8. Experiments

Experiments test whether depth-induced overparameterization accelerates optimization independently of expressiveness, compare it with explicit optimizers, and examine width, initialization, and a nonlinear MNIST setting.

  • Linear-network validation: Deep linear networks emulate the corresponding preconditioning schemes, while hidden-layer widths of 1 and 100 yield similar convergence.This supports the analysis that depth, rather than width, drives the observed optimization effect.
  • Linear-network validation: The experiments compare deep linear networks with analytically derived preconditioning schemes on ℓ2 and ℓ4 regression losses.The dataset is the UCI Ethanol scalar regression task with 2,565 examples and 128 features.
  • Loss-dependent acceleration: With per-model grid-searched learning rates, depth slightly hinders ℓ2 optimization but significantly accelerates convergence for ℓ4 loss.The comparison isolates optimization behavior without relying on a shared, potentially suboptimal learning rate.
  • Comparison with explicit optimizers: A depth-3 network optimized by gradient descent outperforms AdaGrad and AdaDelta in the evaluated ℓ4 setting, while Adam further accelerates optimization when combined with depth.The paper notes that Adam was considerably faster than overparameterization alone in this specific comparison.
  • Initialization and depth: For depths 4 and 8, near-zero initialization causes vanishing gradients, whereas near-identity initialization eliminates that problem.The experiments identify initialization as a practical boundary on how deeply the linear network can be overparameterized.
  • Nonlinear-network test: Replacing dense-layer matrices with successive matrix products in a TensorFlow MNIST convolutional tutorial accelerates optimization with roughly 15% more parameters.The effect persisted across tested learning rates and initialization standard deviations, though the paper cautions that nonlinear-network effects may be mixed.

9. Conclusion

The paper concludes that increasing depth can accelerate optimization through overparameterization, including on simple problems, without changing expressiveness in the demonstrated nonlinear setting.

  • 9. Conclusion: Depth-based overparameterization can accelerate optimization even on very simple problems.This conclusion is supported by both theoretical analysis and experiments.
  • 9. Conclusion: For linear neural networks, depth overparameterization acts as a preconditioning scheme with a closed-form description.The result is formalized in Theorem 1 and subsequent claims.
  • 9. Conclusion: Replacing an internal weight matrix with a product of two can significantly accelerate nonlinear optimization without affecting expressiveness.The paper reports this empirical result for the nonlinear model in Figure 5-right.
  • 9. Conclusion: The acceleration question also arises for convex linear regression with ℓp loss when optimization transitions to a non-convex overparameterized objective.The paper identifies this as a counterintuitive departure from conventional wisdom and a subject for quantitative analysis.

A.1. Proof of Theorem 1

The proof derives the closed-form preconditioning induced by depth in linear networks by transforming the gradient-flow equations and exploiting matrix decompositions and algebraic identities.

  • A.1. Proof of Theorem 1: The proof starts from the gradient-descent differential equations for each weight matrix in a depth-N linear network.It substitutes the network definitions and combines neighboring layer equations.
  • A.1. Proof of Theorem 1: Singular value decompositions and orthogonal basis changes are used to characterize the matrices governing the layerwise dynamics.The proof tracks singular values and eigenspaces across adjacent weight matrices.
  • A.1. Proof of Theorem 1: The argument concludes by showing that the constructed matrix satisfies the theorem’s characterization of P_W.This completes the proof after the singular-value and Kronecker-product calculations.
  • A.1. Proof of Theorem 1: A differential-equation uniqueness lemma establishes that matching an initial value and a first-order relation forces two trajectories to coincide throughout the interval.The lemma is proved by applying continuity to the difference of the trajectories.
  • A.1. Proof of Theorem 1: Kronecker-product identities and vectorization reduce the matrix dynamics to the claimed preconditioning representation.The proof defines the Kronecker product, applies its properties, and verifies the characterization of P_W.

A.4. Proof of Theorem 2

The proof of Theorem 2 shows that the overparameterization-induced vector field cannot be the gradient of any fixed regularizer by constructing a closed curve with nonzero line integral.

  • A.4. Proof of Theorem 2: The proof tests whether the vector field satisfies the gradient theorem on a neighborhood of the origin.For a gradient field, every closed curve in the neighborhood must have zero line integral.
  • A.4. Proof of Theorem 2: The vector-field construction is linear in an arbitrary continuous vector field and is analyzed through line integrals.The resulting functional is bounded using curve length, distance from the origin, and the vector-field norm.
  • A.4. Proof of Theorem 2: A piecewise smooth closed curve is formed from two radial segments and two spherical geodesics at radii r and R.The curve remains inside the neighborhood and avoids passing directly through the origin.
  • A.4. Proof of Theorem 2: The curve’s line integral is shown to be positive for suitable choices of R and r.This contradicts the zero-integral condition required of gradient fields.
  • A.4. Proof of Theorem 2: The proof therefore establishes that the acceleration vector field cannot arise as the gradient of a fixed regularizer.The contradiction is obtained without relying on a point-wise singularity at the origin.

B. A Concrete Acceleration Bound

In an ill-conditioned ℓ4-loss example, depth overparameterization immediately solves one coordinate while inducing a faster effective learning rate for the other.

  • B. A Concrete Acceleration Bound: The appendix formalizes the qualitative acceleration example by deriving a concrete bound for a special case.This section turns the illustrative dynamics into an explicit quantitative result.
  • B. A Concrete Acceleration Bound: The concrete example uses p = 4, a depth-2 network, and ill-conditioned targets and initializations.The assumptions include y1 ≫ y2, ϵ1/ϵ2 ≈ y1/y2, y2 on the order of 1, and ϵ1y1 ≫ 1.
  • B. A Concrete Acceleration Bound: Under standard gradient descent, stability constraints force a very slow convergence rate for the ill-conditioned coordinate w2.The optimal single-step learning rate for w2 is 1/y2^2, but the global constraint prevents using it.
  • B. A Concrete Acceleration Bound: Overparameterization makes w1 approximately fixed at y1 while w2 follows gradient descent with effective learning rate ηOP = 1/(2ϵ1y1).The behavior persists throughout the iterations under the stated assumptions.
  • B. A Concrete Acceleration Bound: The overparameterized update achieves immediate single-step convergence for w1 while accelerating w2 by at least ηOP/ηGD > y1/(4ϵ1).Both effective learning rates remain below 1/y2^2.

C. Implementation Details

The experiments use carefully specified initializations, optimization settings, and overparameterized replacements, including a convolutional MNIST model. Additional checks compare learning rates and initialization scales to assess whether the reported speedup depends on those choices.

  • Linear-network setup: Linear networks omit biases and use small Gaussian weight initialization, except identity initialization adds 1 to each diagonal element.The standard initialization has mean zero and standard deviation 0.01.
  • Optimization settings: Learning-rate searches use values from 10^-5 through 5 · 10^-1, while depth-8 near-zero initialization either diverges or fails through vanishing gradients.This failure occurs for every tested learning rate in that setting.
  • Convolutional MNIST experiment: The convolutional MNIST experiment factorizes two dense layers, replacing each original matrix with a product of two matrices.The hidden layer becomes 3136×512 multiplied by 512×512, and the output layer becomes 512×10 multiplied by 10×10.
  • Convolutional MNIST experiment: Adding roughly 250K parameters to the 1.6M-parameter MNIST model produced the speedup reported in Figure 5-right.The added matrices use Gaussian initialization with mean zero and standard deviation 0.1, with no other code changes.
  • Robustness checks: A learning-rate grid search selected the fastest-converging configuration separately for the original and overparameterized models.The tutorial’s exponentially decaying schedule has base value 10^-2, and tested base values range from 10^-5 to 5 · 10^-1.
  • Robustness checks: Varying the overparameterized-layer initialization standard deviation from 10^-3 to 5 · 10^-1 yielded almost identical convergence rates across runs.The originally used standard deviation was 10^-1.
Loading 1802.06509v2…