PaperlayerView exact revision on arXiv

Source-linked AI summary

Loss landscapes and optimization in over-parameterized non-linear systems and neural networks

Chaoyue Liu, Libin Zhu, Mikhail Belkin

arXiv:2003.00307v2cs.LGmath.OCstat.ML

TL;DR

The paper addresses how gradient methods can optimize over-parameterized nonlinear systems despite their lack of local convexity. It develops PL* and its tangent-kernel characterization, showing that wide neural networks satisfy the condition and proposing a relaxation for almost over-parameterized systems. The framework connects PL* to solution existence and GD/SGD convergence.

  • Problem

    Over-parameterized nonlinear systems are generally non-convex even locally, limiting the applicability of convexity-based analyses to gradient optimization.

  • Method

    The paper develops PL*, relates it to the tangent-kernel spectrum, and relaxes it for systems optimized toward early stopping without exact interpolation.

  • Results

    PL* in a ball of radius O(1/µ) guarantees a global minimum and exponential convergence of GD/SGD, and sufficiently wide neural networks satisfy PL*.

  • Takeaways & Limitations

    PL* offers a mathematical framework for analyzing solution existence and gradient-based convergence in over-parameterized nonlinear systems.

  • Takeaways & Limitations

    The theory's treatment of transition along optimization paths between over- and under-parameterization remains beyond precise technical analysis.

Abstract

from arXiv · show

The success of deep learning is due, to a large extent, to the remarkable effectiveness of gradient-based optimization methods applied to large neural networks. The purpose of this work is to propose a modern view and a general mathematical framework for loss landscapes and efficient optimization in over-parameterized machine learning models and systems of non-linear equations, a setting that includes over-parameterized deep neural networks. Our starting observation is that optimization problems corresponding to such systems are generally not convex, even locally. We argue that instead they satisfy PL$^*$, a variant of the Polyak-Lojasiewicz condition on most (but not all) of the parameter space, which guarantees both the existence of solutions and efficient optimization by (stochastic) gradient descent (SGD/GD). The PL$^*$ condition of these systems is closely related to the condition number of the tangent kernel associated to a non-linear system showing how a PL$^*$-based non-linear theory parallels classical analyses of over-parameterized linear equations. We show that wide neural networks satisfy the PL$^*$ condition, which explains the (S)GD convergence to a global minimum. Finally we propose a relaxation of the PL$^*$ condition applicable to "almost" over-parameterized systems.

1 Introduction

Over-parameterized nonlinear systems are generally essentially non-convex, so convexity is not the right local framework. The paper proposes PL* as an alternative, links it to tangent-kernel spectra, and applies it to wide neural networks and almost over-parameterized systems.

  • Problem formulation: The paper models supervised learning as solving F(w) = y and minimizes a loss constructed so exact solutions are global minimizers.For over-parameterized systems with m > n, exact solutions are expected to exist and correspond to interpolation.
  • Essential non-convexity: Over-parameterized systems are not generally convex in any neighborhood of a global minimizer because their solution sets are typically curved positive-dimensional manifolds.This contrasts with under-parameterized systems, which are typically locally convex near isolated minimizers.
  • PL* framework: PL* provides an alternative framework: when it holds in a ball of radius O(1/µ), a global solution exists there and (S)GD converges exponentially to a global minimum.The radius constant differs between GD and SGD.
  • Tangent-kernel criterion: For square loss, verifying PL* reduces to analyzing the spectrum of the tangent kernel K(w) = DF(w) DFT(w), especially its smallest eigenvalue.The tangent kernel uses first-order derivatives, unlike the Hessian-based convexity condition.
  • Parameter-space geometry: The paper argues that PL* holds across most, but not all, of parameter space because the singular set where the tangent kernel degenerates is comparatively small when m > n.The argument is based on parameter counting and excludes neighborhoods of the singular set.
  • Neural networks and relaxation: Sufficiently wide neural networks satisfy PL*, while an approximate PL* relaxation covers almost over-parameterized systems whose optimization paths reach early stopping before exact interpolation.The wide-network argument uses near-constant tangent kernels; the relaxation assumes PL* above a loss threshold along the optimization path.

2 Notation and standard definitions

The paper defines notation for vectors, matrices, derivatives, norms, Jacobians, Hessians, Lipschitz maps, and the equation-solving problem addressed by gradient-based optimization.

  • The notation distinguishes vectors, matrices, and tuples of matrices or higher-order tensors using different capitalization conventions.The index set [n] denotes {1, 2, · · · , n}.
  • F maps R^m to R^n, with DF represented as an n × m matrix of first derivatives.The differential and Jacobian notation specify how output changes with respect to parameters.
  • The paper denotes second derivatives using the Hessian tensor HF and the loss Hessian HL, while λmin(K) denotes a matrix's smallest eigenvalue.The Hessian tensor norm is defined through the spectral norms of the output Hessian components.
  • The paper studies solving F(w) = y by minimizing a loss such as square loss with gradient-based algorithms.Gradient descent starts from an initialization point and updates the parameters iteratively.
  • The map F is assumed to be Lipschitz continuous and smooth, with LF-Lipschitz continuity providing a bound on its differential norm.This regularity assumption also yields a bounded spectral norm for the tangent kernel.
  • In supervised learning, each output is modeled as (F(w))i = f(w; xi), linking the equation-system notation to predictions on training examples.The Lipschitz behavior of F is related to the model's parameter-wise Lipschitz continuity.

3 Essential non-convexity of loss landscapes of over-parameterized non-linear systems

Over-parameterized nonlinear systems have solution sets that are typically curved, positive-dimensional manifolds, making their loss landscapes non-convex in every neighborhood of a global minimizer.

  • Solution geometry: Over-parameterized systems typically have exact solutions forming continuous manifolds of dimension m − n > 0, so global minimizers are not isolated.Wide neural networks specifically have non-isolated global minima according to Proposition 6.
  • Solution geometry: The curvature of these solution manifolds prevents local convexity because minimizers of a convex function over a convex domain must form a convex set.The argument connects nonlinear solution geometry directly to the loss landscape.
  • Hessian analysis: For the square loss, the Hessian at a solution contains a positive-semidefinite term of rank at most n with at least m − n zero eigenvalues.At a global minimizer, the residual-dependent term vanishes.
  • Hessian analysis: Nearby points can make the second-derivative contribution full rank, preventing the loss Hessian from remaining positive semidefinite in any neighborhood.This provides an analytical route to essential non-convexity beyond the geometric argument.
  • Formal result: A complementary argument shows that when DF(w*) ≠ 0 and an output Hessian has sufficiently high rank, one of two arbitrarily close points has a loss Hessian with negative eigenvalues.This rules out local convexity at the solution.
  • Formal result: Proposition 2 states that if L(w*) = 0, DF(w*) ≠ 0, and rank(HFi(w*)) > 2n for some output i, then L is not convex in any neighborhood of w*.The proposition formalizes the local non-convexity claim under explicit derivative and rank conditions.
  • Comparison: Under-parameterized systems contrast with this behavior because isolated minima with positive-definite loss Hessians are locally convex by continuity.The paper emphasizes that classical local convexity applies in that setting.

4 Over-parameterized non-linear systems are PL∗on most of the parameter space

Over-parameterized nonlinear systems can satisfy PL* across most of parameter space despite essential non-convexity. The condition is characterized through tangent-kernel conditioning and applies to sufficiently wide neural networks.

  • Over-parameterized loss landscapes are generally non-convex in every neighborhood of global minimizers.Their positive-dimensional solution manifolds generically have non-zero curvature.
  • Uniform conditioning of the tangent kernel implies the square loss satisfies the PL* condition.The key inequality is 1/2∥∇L(w)∥2 ≥ λmin(K(w))L(w) ≥ µL(w).
  • The PL* condition fails at singular points where the tangent kernel has zero minimum eigenvalue.Such points prevent PL* from holding for all label vectors on any set containing them.
  • For m > n, the singular set is expected to have positive codimension and measure zero, with non-PL* regions concentrated around it.The expected codimension is m − n + 1 and increases with over-parameterization.
  • Increasing over-parameterization improves conditioning in a Gaussian tangent-kernel example.E(log κ) < 2 log m/(m − n + 1) + 5, and κ approaches a small constant as over-parameterization increases.
  • 4.2 Wide neural networks satisfy PL*condition: Wide neural networks satisfy PL* in a ball around random initialization, even though their landscapes are nowhere convex.The analysis uses small Hessian norm for linear-output networks and conditioning at initialization.

5 PL∗condition in a ball guarantees existence of solutions and fast convergence of (S)GD

A local PL* condition on a suitable ball guarantees a solution and exponential convergence of GD and SGD. The framework applies to wide neural networks under stated smoothness, width, and initialization conditions.

  • The nonlinear condition number generalizes tangent-kernel conditioning and reduces to the standard tangent-kernel condition number for linear systems.For F(w) = Aw, the Hessian and tangent kernel share their non-zero eigenvalues.
  • A PL* condition on a sufficiently large local ball guarantees existence of a global solution within that ball.The ball radius is chosen as R = 2LF∥F(w0)−y∥/µ under Lipschitz and smoothness assumptions.
  • Gradient descent converges exponentially to a global solution when initialized at the ball center with an appropriate step size.The optimization path remains in a finite local region around initialization.
  • The paper extends the local PL* convergence result from gradient descent to mini-batch stochastic gradient descent.With suitable batch size and step size, SGD converges with probability 1 − δ at an exponential rate.
  • 5.1 Convergence for wide neural networks.: For sufficiently wide neural networks, gradient descent converges to a global minimizer in B(W0,R), with R = O(1/µ).The result combines the wide-network PL* theorem with the local convergence theorem.
  • 5.1 Convergence for wide neural networks.: Near-constancy of the tangent kernel is not necessary for exponential convergence of gradient-based methods.The framework requires PL* conditioning rather than tangent-kernel constancy itself.

6 Relaxation to PL∗ ϵ condition

The PL*_ϵ condition relaxes PL* by requiring it only above a target loss ϵ, allowing arbitrary behavior below that threshold while retaining fast approximate optimization.

  • The relaxation addresses mildly under-parameterized systems where exact solutions may not exist, because optimization need only reach loss ϵ.Early stopping is treated as practically sufficient when exact convergence is unavailable.
  • PL*_ϵ matches PL* wherever L(w) ≥ ϵ, but permits an arbitrary loss landscape where L(w) < ϵ.This relaxation is illustrated by Figure 5 and supports early-stopping analyses.
  • There exists w* within a ball around initialization whose loss is below ϵ under smoothness and PL*_ϵ assumptions.The radius is given as R = 2√(2βL(w0))/μ in the supplied result passage.
  • Gradient descent reaches loss below ϵ after T = Ω(log(1/ϵ)) iterations with exponential convergence inside the ball.The step size uses the inverse supremum Hessian spectral norm over the ball, and the condition number is κL,F(B(w0,R)) = 1/(ημ).
  • Under the relaxed condition, SGD also converges exponentially to an approximation of the global solution or reaches expected loss below ϵ.The supplied passages state this for mini-batch SGD and describe a high-probability optimization path within the relevant region.
  • The guarantees are local: they find approximate solutions within a specified ball around the initialization point, despite possible global landscape complexity.The global loss landscape need not be controlled outside that ball.

7 Concluding thoughts and comments

The paper frames PL* as a general theory for essentially non-convex over-parameterized systems, while identifying scope boundaries and extensions for optimization and geometry.

  • The framework claims PL* holds on most, but not all, of the parameter space, supporting solution existence and gradient-based convergence for over-parameterized systems.Under-parameterized systems cannot satisfy PL* for any target y in the stated squared-loss setting.
  • Crossing the interpolation threshold changes optimization geometry from local convexity to essential non-convexity, motivating alternatives to convex analysis.The paper states that this loss of local convexity has little consequence for optimization within its analyzed scope.
  • The authors conjecture that some large models transition from effective over-parameterization to under-parameterization during optimization and fail to reach zero loss.They speculate that realistic large-model trajectories may nevertheless remain inside the PL*_ϵ domain.
  • Conditioning may govern accelerated methods in over-parameterized nonlinear systems, extending the paper’s gradient-descent perspective beyond GD and SGD.Nesterov and stochastic accelerated methods are offered as expected examples rather than analyzed results.
  • The framework may extend from Euclidean equations to maps between Riemannian manifolds, with over-parameterization defined by dim(M) > dim(N).The paper notes that manifold gradient descent requires additional care.
  • Structural assumptions on weights and outputs can model settings such as convolutional networks and robot motion planning.These examples involve invariances or outputs constrained to manifolds.

A Wide neural networks have no isolated local/global minima

Sufficiently wide feedforward neural networks have no isolated local or global minima because parameters can connect through constant-loss paths to distinct block-structured parameters.

  • The network consists of L hidden layers with minimum hidden-layer width m, parameters W, and convex loss in the network output.The training loss aggregates l(f(W; x_i), y_i) over n samples.
  • If m ≥ 2c(n + 1)L, every local or global minimum has other local or global minima in any neighborhood.This is the stated no-isolated-minima proposition for the network and loss under consideration.
  • Path constantness means two parameters are joined by a continuous path lying entirely in a level set of the loss.The loss remains constant along the connecting path.
  • Upper-block and lower-block parameters impose complementary zero patterns on weight matrices across hidden layers.The supplied definitions specify the corresponding upper and lower index blocks and their parameter sets.
  • For sufficiently large width, every parameter is path connected to both an upper-block and a lower-block parameter.The proposition uses s = c(n + 1)L and continuous constant-loss paths.
  • Distinct block-parameter sets connected to an arbitrary minimum yield distinct minima connected to it through a constant-loss path.The proof relies on the upper- and lower-block sets being distinct when m ≥ 2s.

B Proof of Proposition 2

The proof establishes essential non-convexity by finding negative curvature arbitrarily near a global minimizer, while wide structured models can have arbitrarily small Hessian spectral norm.

  • The proof exploits rank separation: loss Hessian terms have rank at most n, while one output Hessian component has rank greater than 2n.Continuity preserves the relevant rank condition for sufficiently small δ.
  • A suitable unit vector v makes the second-order contributions from the output map nonzero near both sides of the minimizer.The resulting directional curvature analysis separates the two sign cases and forces negativity on one side.
  • At least one arbitrarily nearby point w* + δ or w* − δ has negative Hessian curvature, so the loss has no convex neighborhood around w*.The argument tests the quadratic form along a shared direction v on both sides of the minimizer.
  • The negative-curvature conclusion follows by continuity and arbitrarily small perturbations around the minimizer.The proof adjusts δ slightly when a directional second-order term is exactly zero.
  • For a sufficiently wide linear combination of independent sub-models, the model Hessian spectral norm becomes arbitrarily small.The scaling factor is o(1) in model size, with 1/√m given as a neural-network example.
  • The small Hessian norm arises because sub-model parameters are disjoint, leaving at most one nonzero summand for each Hessian entry.This structural sparsity enables the spectral-norm bound.

D An illustrative example of composition models

The composition model illustrates that uniform tangent-kernel conditioning can survive nonlinear composition when the intermediate outputs remain sufficiently separated. Conditioning of the composed model is controlled by the separation between the inputs to the second component.

  • Model setup: The model h = g ◦ f is analyzed as a composition of two large random Fourier feature models, with f’s outputs serving as g’s inputs.The construction can also be viewed as a bottleneck neural network whose second hidden layer has one neuron.
  • Conditioning mechanism: Uniform conditioning of the composed tangent kernel Kh can be guaranteed when the partial kernel Kg is uniformly conditioned.The tangent kernel of h decomposes into positive semi-definite components, so conditioning one component is sufficient in the stated analysis.
  • Separation condition: A minimum output separation ρ(S) ≥ 2ln(2n −2)/n implies infu∈S λmin(Kg(u)) ≥ 1/2.Here ρ(S) measures the minimum pairwise separation among f’s outputs over S.
  • Conclusion: Nonlinear composition may make the tangent kernel non-constant while preserving its uniform conditioning.The example identifies intermediate-output separation as the controlling property.

E Wide CNN and ResNet satisfy PL∗condition

The paper extends the PL∗ analysis from fully connected networks to wide CNNs and ResNets. Under initialization, activation, and width conditions, both architectures satisfy PL∗ locally around their initial parameters.

  • Main result: Wide CNNs and ResNets are shown to satisfy the PL∗ condition as over-parameterized neural-network models.The result is presented as a basis for analyzing gradient-based optimization in these architectures.
  • CNN formulation: The CNN analysis uses convolutional activations represented as matrices and convolutional weights represented as order-3 tensors.The notation is introduced first for one-dimensional CNNs, with the analysis stated to extend to higher dimensions.
  • ResNet formulation: The ResNet differs from the fully connected form by adding the previous-layer activation through a skip connection.The paper notes that its definition places skip connections at every layer, unlike the standard architecture cited there.
  • Technical bound: With high probability over initialization, the Hessian spectral norm is bounded within a ball around the initial parameters when hidden layers are sufficiently wide.The relevant width is the minimum hidden-layer width m = minl∈[L] ml.
  • PL∗ guarantee: If λ0 := λmin(K(W0)) > 0, |σ′L+1(z)| ≥ ρ > 0, and µ ∈ (0, λ0ρ^2), then sufficient width yields the µ-PL∗ condition for square loss in B(W0, R).These are the stated local assumptions and conclusion of the wide CNN and ResNet theorem.

F Proof for convergence under PL∗condition

Under smoothness and a local PL∗ condition, the paper proves that a global minimizer exists inside the initialization-centered ball and that gradient descent converges to it exponentially. The convergence rate is linked to a condition number defined from the step size and PL∗ parameter.

  • Existence: For a β-smooth loss satisfying the µ-PL∗ condition in B(w0, R), the proof establishes existence of a global minimizer within that ball.The theorem states that the minimizer is a solution with F(w∗) = y.
  • Gradient descent: Gradient descent with η ≤ 1/supw∈B(w0,R) ∥HL(w)∥2 converges exponentially to a global solution in B(w0, R).The argument uses smoothness to control each update and induction to keep iterates inside the ball.
  • Conditioning: The convergence condition number is κL,F(B(w0, R)) = 1/(ηµ).The quantity combines the step size η with the local PL∗ parameter µ.
  • Proof structure: The proof maintains the local guarantee by showing that each update remains inside B(w0, R), starting from w0.The induction begins with w0 in the ball and uses the smoothness-based update bound.

G Proof of Theorem 7

The proof relaxes the PL∗ requirement from the entire parameter space to a neighborhood around initialization. For mini-batch SGD, a probabilistic bound on the optimization path ensures that this local condition suffices with high probability.

  • Local relaxation: The proof begins by assuming the µ-PL∗ condition holds throughout R^m, then relaxes it to the ball B(w0, R).The relaxation is justified by proving that the optimization path remains within the ball.
  • SGD convergence: For any mini-batch size s, mini-batch SGD with step size η∗(s) has an exponential convergence rate under the global PL∗ assumption.The stated result applies for all t > 0.
  • Path-length control: The expected length of the stochastic optimization path is bounded, providing the quantity needed for a high-probability radius guarantee.The path-length estimate is the bridge from stochastic updates to local PL∗ analysis.
  • High-probability localization: With probability at least 1 − δ, the entire SGD path is contained in B(w0, R).Markov’s inequality converts the expected path-length bound into the stated probability guarantee.
Loading 2003.00307v2…