PaperlayerView exact revision on arXiv

Source-linked AI summary

Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?

Samet Oymak, Mahdi Soltanolkotabi

arXiv:1812.10004v1cs.LGmath.OCstat.ML

TL;DR

Overparameterized nonlinear learning can have many global optima, raising questions about which solutions first-order methods reach and how their trajectories depend on initialization. This paper develops convergence theory for gradient descent and SGD under local conditions, showing convergence to nearby global optima along short paths across several nonlinear learning settings.

  • Problem

    Overparameterized nonlinear models can have infinitely many global minima, motivating questions about which optimum first-order methods reach, how initialization matters, and what trajectories they follow.

  • Method

    The paper analyzes gradient descent and SGD when the nonlinear mapping or loss is well behaved in a minimally small neighborhood of initialization, and specializes the theory to several model classes.

  • Results

    The iterates converge linearly to global minimizers that are nearly closest to initialization and follow near-direct paths, with SGD remaining in a minimally small initialization neighborhood.

  • Takeaways & Limitations

    The results provide a general account of optimization behavior in overparameterized nonlinear learning and apply to generalized linear models, low-rank regression, and shallow neural-network training.

  • Takeaways & Limitations

    The theory requires heavy overparameterization in the shallow-network setting, leaving a substantial gap from practical regimes; generalization implications remain unresolved.

Abstract

from arXiv · show

Many modern learning tasks involve fitting nonlinear models to data which are trained in an overparameterized regime where the parameters of the model exceed the size of the training dataset. Due to this overparameterization, the training loss may have infinitely many global minima and it is critical to understand the properties of the solutions found by first-order optimization schemes such as (stochastic) gradient descent starting from different initializations. In this paper we demonstrate that when the loss has certain properties over a minimally small neighborhood of the initial point, first order methods such as (stochastic) gradient descent have a few intriguing properties: (1) the iterates converge at a geometric rate to a global optima even when the loss is nonconvex, (2) among all global optima of the loss the iterates converge to one with a near minimal distance to the initial point, (3) the iterates take a near direct route from the initial point to this global optima. As part of our proof technique, we introduce a new potential function which captures the precise tradeoff between the loss function and the distance to the initial point as the iterations progress. For Stochastic Gradient Descent (SGD), we develop novel martingale techniques that guarantee SGD never leaves a small neighborhood of the initialization, even with rather large learning rates. We demonstrate the utility of our general theory for a variety of problem domains spanning low-rank matrix recovery to neural network training. Underlying our analysis are novel insights that may have implications for training and generalization of more sophisticated learning problems including those involving deep neural network architectures.

1 Introduction

The paper studies first-order optimization in overparameterized nonlinear learning, where nonconvex training losses may have many global minima. It shows that, under local regularity near initialization, gradient methods converge globally while selecting nearby solutions and following short trajectories.

  • Motivation: Overparameterized learning reverses the classical n > p setting, with modern models often having more parameters than training examples.This creates new questions about interpolation, solution selection, trajectory, and generalization.
  • Motivation: The paper asks whether first-order methods can globally fit nonconvex training data and which global optimum they select from different initializations.It also raises how these solutions may relate to generalization and avoidance of overfitting.
  • Main contributions: Under suitable assumptions in a small neighborhood of initialization, gradient descent finds a globally optimal model, an approximately closest global optimum, and a nearly direct trajectory.The analysis provides matching upper and lower bounds for these properties.
  • Main contributions: SGD exhibits the same qualitative behavior as gradient descent and converges linearly without leaving a small initialization neighborhood, even with rather large learning rates.This extends the local convergence picture beyond deterministic gradient descent.
  • Applications: The theory is applied to generalized linear models, low-rank matrix regression, and shallow neural network training.The paper focuses mainly on nonlinear least-squares problems while also treating broader loss functions.

2 Convergence Analysis for Gradient Descent

Under local Jacobian spectrum and deviation conditions around initialization, gradient descent on nonlinear least-squares problems converges globally despite nonconvexity. Its trajectory remains near initialization, selects a near-nearest global optimum, and follows a nearly direct path, with neighborhood size and convergence rate controlled by Jacobian conditioning and sample size.

  • Assumptions and main theorem: Under a locally bounded Jacobian spectrum and controlled Jacobian deviations, gradient descent converges geometrically to a global optimum of the nonlinear least-squares loss.The assumptions hold on a neighborhood containing the initialization, with learning-rate conditions specified by the Jacobian bounds.
  • Trajectory geometry: The total gradient path is bounded, so the iterates remain in a neighborhood around initialization and reach the selected optimum along a near-direct trajectory.The trajectory is constrained by nearly matching upper and lower bounds on distance to initialization and misfit error.
  • Convergence guarantees: Gradient descent achieves zero training error and perfectly interpolates the data, even when the fitting problem is nonconvex.The residual converges to zero at a geometric rate.
  • Selection among global optima: Gradient descent converges to a global optimum whose distance from initialization is within a factor 4β/α of the closest global optimum.The analysis also bounds a weighted combination of initialization distance and misfit error throughout the iterations.
  • Refined guarantees: Sharper approximation ratios and smaller neighborhoods are possible, but they require a smaller learning rate and therefore slower convergence guarantees.The more general result improves the approximation ratios while shrinking the neighborhood radius.
  • Role of sample size: The required local neighborhood grows proportional to √n, while more samples slow convergence by degrading the Jacobian condition number.Larger sample sets require the Jacobian to remain well behaved over a larger region for fast convergence.

3 Convergence Analysis for Stochastic Gradient Descent

The paper extends its convergence analysis to SGD for nonlinear least-squares problems, showing that stochastic iterates retain global convergence and initialization-proximity properties with high probability. A martingale-based potential keeps the iterates inside the local neighborhood, even with comparatively large learning rates.

  • Method: A nonlinear least-squares SGD update samples one training point and uses its individual gradient, G(θτ;γτ), to update θτ.The sampled index γτ is drawn uniformly from the n training samples.
  • Problem: SGD is analyzed for nonlinear least-squares problems to determine whether gradient descent’s three trajectory properties persist under stochastic updates.The targeted properties concern global convergence, proximity to initialization, and near-direct paths.
  • Guarantees: With high probability, all SGD iterates remain inside the local neighborhood D.The theorem establishes an event with an explicit probability lower bound, though the supplied passage truncates its numerical expression.
  • Guarantees: SGD converges to a globally optimal solution close to the initialization while retaining the paper’s near-initialization trajectory behavior.The result is stated under local Jacobian conditioning and bounded row norms over a neighborhood around θ0.
  • Proof technique: A martingale-based technique tracks average distances to points near initialization and prevents SGD from leaving the neighborhood.This approach supports aggressive learning rates comparable to gradient descent, unlike an Azuma-based argument requiring a very small learning rate.
  • Rate: Ignoring a β/α factor, the SGD convergence rate is approximately 1 − c/n, so n iterations yield a constant misfit decrease comparable to one full-gradient iteration.The result explains why the method can use a relatively large learning rate.

4 Case studies

The paper applies its general theory to generalized linear models, low-rank matrix regression, and shallow neural networks. Across these cases, gradient descent achieves global fitting under overparameterization, while the neural-network result requires stronger structural assumptions and leaves a gap with practical regimes.

  • Overview: The case studies cover generalized linear models, low-rank regression, and shallow neural-network training.These applications specialize the general convergence analysis in three fundamental overparameterized learning problems.
  • Generalized linear models: For GLMs with n ≤ p and a strictly increasing activation, gradient descent converges linearly to the globally optimal solution closest to initialization.The activation derivative is assumed bounded above and away from zero, and the step size is constrained by the data and derivative bounds.
  • Generalized linear models: The GLM gradient path length is bounded by a constant multiple of the distance from initialization to the closest global optimum.The bound applies with a step size on the order of 1/(∥X∥2Γ2), with a possible improvement for smaller learning rates.
  • Low-rank regression: Low-rank regression uses the Burer–Monteiro factorization ΘΘT and studies gradient methods in the overparameterized regime n < dr.The model fits trace(ΘT XΘ) using random Gaussian input features and arbitrary labels.
  • Low-rank regression: When dr ≳ n, gradient descent linearly converges to a globally optimal low-rank model with zero loss despite the nonconvex factorized formulation.The degrees of freedom are dr, and the paper identifies a transition when n exceeds dr for arbitrary-label interpolation.
  • Shallow neural networks: For one-hidden-layer networks with n ≤ d, fixed unit-norm output weights, and strictly increasing activations with derivative bounded away from zero, the theorem gives geometric global convergence.The result is independent of the number of hidden units k and applies from arbitrary initialization.
  • Shallow neural networks: The shallow-network guarantee requires much heavier overparameterization than the practical condition kd ≳ n, leaving a substantial gap between theory and use.The paper notes that its assumptions require more overparameterization and suggests sharper random-matrix and stochastic-process analyses as a possible direction.

5 Beyond nonlinear least-squares

The paper extends its nonlinear least-squares conclusions to general differentiable losses using local PL and smoothness conditions near initialization. Under these assumptions, gradient descent converges globally, selects a near-closest optimum, and follows a short path, while a lower bound shows the required neighborhood scale is nearly optimal.

  • Setup: The broader analysis considers differentiable losses with global minimum zero and introduces a local Polyak–Łojasiewicz condition.The zero-minimum convention is without loss of generality because losses can be shifted by their global minimum.
  • Guarantees: If the loss is locally PL and L-smooth around initialization, gradient descent with η ≤ 1/L satisfies the theorem’s convergence and trajectory inequalities.The neighborhood is defined around θ0, and the iterates are controlled throughout the analysis.
  • Implicit selection: The selected global optimum has near-minimal Euclidean distance to the initial parameter among all global optima.Corollary 5.3 defines θ* as the closest global optimum and bounds the gradient-descent solution relative to it.
  • Guarantees: Gradient descent converges at a linear rate to a global optimum, remains within a neighborhood of initialization, and follows a near-direct route.The path length is within a factor of the distance to the closest global optimum, according to the stated summary of the theorem and corollary.
  • Neighborhood lower bound: A lower bound shows that no global minimum need exist inside B(θ0,R) when R < 2L(θ0)/L, establishing near-optimality of the theorem’s neighborhood scale.The paper further states that the bound is optimal up to a factor of two.

6 Numerical Experiments

Experiments on MNIST and low-rank regression examine the predicted tradeoff between training misfit and distance from initialization. The observed trajectories are initially near-linear, while larger sample sizes or weaker overparameterization produce earlier flattening and wider uncertainty.

  • Experimental design: Experiments on MNIST and low-rank matrix regression test the predicted misfit–distance tradeoff.The authors define normalized misfit and normalized distance to initialization for these evaluations.
  • MNIST: MNIST experiments use LeNet with least-squares loss, compare n = 500 and n = 5000, and repeat training 20 times with independent initialization and dataset selection.Training uses Adam with learning rate 0.001, batch size 100, and 1000 iterations.
  • MNIST: For n = 500, all tracked layers initially follow a straight loss–distance line when misfit ≤ 0.2, with slight leveling near the end.The layers are Conv1, Conv2, FC1, and FC2; the leveling is most visible for FC2.
  • MNIST: At misfit = 0.2, FC2 has normalized distance 0.5 for n = 5000 versus 0.25 for n = 500.With n = 5000, the initially straight trajectory extends through misfit ≤ 0.4 before leveling occurs earlier and more visibly than for n = 500.
  • Low-rank regression: In low-rank regression, the misfit–distance relation is linear with a narrow confidence interval, but n = dr/2 produces notably wider intervals near zero misfit.The setup uses r = 4, d = 100, sample sizes {25, 50, 100, 200}, and 200 gradient-descent iterations.
  • Low-rank regression: As the number of labels n increases, the distance to the initialization Θ0 increases gracefully.This behavior is reported as consistent with the main theorem’s prediction.

7 Prior Art

Prior work studies implicit regularization, overparameterized neural-network training, and first-order methods for nonconvex learning. These results differ in assumptions, regimes, and comparability, while related work also examines generalization and stochastic guarantees.

  • Implicit-regularization studies show that gradient-based methods can favor particular solutions, such as max-margin or minimal-norm solutions, rather than arbitrary optima.
  • For low-rank recovery, classical results require fitted rank r ≥ dr∗, whereas the paper’s results apply when r ≳ r∗.
  • Recent work shows that sufficiently wide overparameterized neural networks can fit data from random initialization and may possess a global minimum near that initialization.
  • Related neural-network results are not directly comparable because they assume different relationships among n, d, and k, as well as different activation conditions.
  • Prior work also develops martingale-based probabilistic guarantees for stochastic methods and studies nonconvex optimization through conditions such as PL and regularity conditions.
  • Provable first-order methods have also been studied for low-rank regression, generalized linear models, and neural networks in overdetermined settings.

8 Discussion and future directions

The paper develops a general theory for first-order optimization in overparameterized nonlinear learning and applies it to several model classes. It also emphasizes that the relationship between nearby solutions and generalization remains unresolved.

  • Under local Jacobian conditions, gradient descent globally minimizes the loss, selects an approximately closest global optimum, and follows a nearly direct trajectory from initialization.
  • The theory extends to SGD, establishing linear convergence while keeping iterates inside a minimally small neighborhood of initialization.
  • The framework covers generalized linear models, low-rank regression, and shallow neural-network training, with experiments on real and synthetic data supporting the loss-distance tradeoff.
  • The paper does not directly address generalization, and understanding how first-order optimization relates to generalization remains future work.

9 Proofs

The proofs establish local geometric convergence and shortest-path properties through residual recursions, Jacobian conditions, and a potential function. The SGD analysis adds martingale arguments to control stochastic iterates within the initialization neighborhood.

  • Theorem 9.3 assumes Jacobian conditions over a local neighborhood and yields bounded iterates, a bounded total gradient path, and convergence to global optima.
  • Choosing the closest global optimum θ∗ to θ0, the gradient-descent iterates satisfy the theorem’s near-minimal-distance guarantee.
  • The proof starts from a residual recursion and shows linear residual convergence when I −ηC(θτ) has spectral norm less than 1.
  • A potential sub-level set contains reachable parameters, and under local assumptions each gradient update remains inside the surrounding ball.
  • The analysis controls both residual norm and distance to initialization, combining their changes through a potential function.
  • The new potential function is defined to combine residual and distance terms, and its value is non-increasing along the analyzed iterates.
  • For SGD, martingale arguments address the difficulty of proving neighborhood containment and permit aggressive learning rates without leaving the local neighborhood.
  • In the GLM specialization, the closest global optimum combines the initialization’s null-space projection with a pseudo-inverse solution and is shown to attract the iterates linearly.

A.1 Uniform upper bounds on the nuclear norm (Proof of Lemma 9.13)

This appendix bounds a stochastic nuclear-norm process uniformly over matrix and vector spheres. It combines fixed-point Gaussian analysis, concentration, and covering arguments.

  • The proof rewrites the stochastic quantity Γv,Θ as a process indexed by Θ and v and seeks a uniform supremum over unit Frobenius and Euclidean spheres.
  • For fixed Θ and v, a Gaussian matrix representation reduces the analysis to bounding the nuclear norm of YΣ.
  • The nuclear norm is shown to be a 1-Lipschitz function of the Gaussian matrix, enabling Gaussian concentration around its expectation.
  • A standard union bound over ε = 1/4 covers of the matrix and vector spheres extends the fixed-point bound uniformly.
  • The cover approximation transfers the supremum bound from cover points to the optimizing pair using triangle-inequality and linearity arguments.

A.2 Proof of Lemma 9.14

The proof combines Gaussian-vector properties with a sequence of inequality-based bounds to establish the lemma’s conclusion.

  • The argument invokes properties of a Gaussian random vector g ∼ N(0, Id).
  • A chain of intermediate definitions and inequalities is used to derive the stated conclusion.
  • The proof attributes its steps to Hölder’s inequality, Cauchy–Schwarz, norm comparisons, and earlier results labeled (A.4)–(A.6).
  • The resulting inequalities include the bound 3re^-2r ≤ 3/4 before the proof concludes.

A.3 Proof of Lemma 9.15

The proof studies a random matrix process indexed by unit vectors, establishes fixed-vector concentration, and extends the result uniformly through a finite cover and union bound.

  • For fixed Θ, the random matrices define a process Γ_v indexed by v, whose lower bound is studied over the unit sphere.
  • For fixed v, Γ_v = YΣV^T, where Y has i.i.d. N(0, 1) entries and the nuclear norm is Lipschitz in Y.
  • Gaussian concentration is applied to obtain a high-probability bound for the fixed-vector process.
  • A 1/19000-cover of S^(n−1) has logarithmic size at most 11n, enabling a union-bound argument.
  • The proof transfers the cover bound to every unit vector using a nearest cover point and the stated approximation bounds.

A.4 Proof of Lemma 9.16

The proof completes a uniform bound for the Jacobian-related quantity and then establishes a Lipschitz operator bound for differences of J across parameter matrices.

  • Combining the preceding bounds with Θ ∈ D and the triangle inequality yields a high-probability conclusion.
  • The identity ∥mat(J(Θ)^T v)∥F = ∥J(Θ)^T v∥ℓ2 allows the result to hold uniformly over v.
  • For Θ1 and Θ2, the operator difference is bounded through a supremum over unit vectors and the Frobenius norm of the matricized Jacobian difference.
  • This final bound completes the proof of the stated result.
Loading 1812.10004v1…