PaperlayerView exact revision on arXiv

Source-linked AI summary

SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics

Emmanuel Abbe, Enric Boix-Adsera, Theodor Misiakiewicz

arXiv:2302.11055v2cs.LGstat.ML

TL;DR

The paper asks which data properties govern SGD learning time for regular neural networks and how SGD exploits them in training dynamics. It introduces leap complexity, conjectures a d^{max(Leap(f),2)} scaling, and proves a specialized result for 2-layer networks under technical SGD assumptions, with total complexity matching CSQ lower bounds.

  • Problem

    The paper asks whether structural properties of data govern SGD learning complexity for regular neural networks and how SGD exploits those properties during training.

  • Method

    The paper introduces leap as a measure of target-function hierarchy and analyzes 2-layer networks with layer-wise, projected SGD on a representative class of Gaussian isotropic functions.

  • Results

    The paper proves total time complexity ˜Ωd(d^{Leap(h∗)∨2})poly(1/ε) for bounded-width/depth networks and establishes d^{O(Leap(h∗))} sample and runtime sufficiency for modified SGD.

  • Takeaways & Limitations

    Leap provides a formal hierarchy-based complexity measure that extends the leap-1 result and connects full SGD training-trajectory complexity with CSQ lower bounds.

  • Takeaways & Limitations

    The formal result is restricted to 2-layer networks, Gaussian isotropic data, and technical assumptions including layer-wise and projected gradient steps; the CSQ correspondence may fail beyond finite P.

Abstract

from arXiv · show

We investigate the time complexity of SGD learning on fully-connected neural networks with isotropic data. We put forward a complexity measure -- the leap -- which measures how "hierarchical" target functions are. For $d$-dimensional uniform Boolean or isotropic Gaussian data, our main conjecture states that the time complexity to learn a function $f$ with low-dimensional support is $\tildeΘ(d^{\max(\mathrm{Leap}(f),2)})$. We prove a version of this conjecture for a class of functions on Gaussian isotropic data and 2-layer neural networks, under additional technical assumptions on how SGD is run. We show that the training sequentially learns the function support with a saddle-to-saddle dynamic. Our result departs from [Abbe et al. 2022] by going beyond leap 1 (merged-staircase functions), and by going beyond the mean-field and gradient flow approximations that prohibit the full complexity control obtained here. Finally, we note that this gives an SGD complexity for the full training trajectory that matches that of Correlational Statistical Query (CSQ) lower-bounds.

1 Introduction

The paper asks which structural properties govern SGD time complexity in regular neural networks and develops leap complexity as a measure of hierarchy. It conjectures and partially proves that SGD learns low-dimensional functions through sequential saddle-to-saddle support discovery, with complexity matching CSQ lower bounds.

  • Research question: SGD learning complexity is studied for low-dimensional functions under regular neural-network architectures and isotropic or Boolean data.The setting excludes generic emulation networks and seeks finite-time, finite-width complexity guarantees.
  • Leap complexity: Leap complexity measures hierarchical structure and predicts neural-network learning time beyond degree or spectrum sparsity alone.Staircases and monomials can share statistical complexity while differing computationally; their CSQ dimensions are Θ(d) and Θ(d^4), respectively.
  • Main conjecture: The paper conjectures total SGD time ˜Θ(d^max(Leap(h*)∨2)) for bounded-width/depth networks, with risk ε requiring ˜Ω(d^(Leap(h*)−1∨1))poly(1/ε) steps.The conjecture applies to low-latent-dimension targets under rotationally invariant initialization and online-SGD.
  • Formal results: Formal results analyze 2-layer networks with smooth activations, layer-wise SGD, projected steps, and representative Gaussian isotropic targets.These assumptions enable full finite-time control without infinite-width or continuous-time approximations.
  • Complexity comparison: The resulting SGD trajectory achieves d^Θ(Leap(h*)) computational complexity, matching the optimal CSQ algorithm on the considered sparse-function class.The paper also derives CSQ lower bounds and reports experimental evidence for the broader conjecture.
  • Training dynamics: SGD sequentially learns reachable support coordinates and monomials through saddle-to-saddle phases, with each new coordinate set requiring at most ˜Θ(d^max(L−1,1)) steps.Lower-degree features produce an initial loss descent, then guide learning of higher-level features.

2 Lower bounds on learning leap functions

Linear methods require degree-dependent sample complexity, while CSQ lower bounds scale with the target's leap and can be smaller than degree-based bounds. These CSQ scalings match the conjectured SGD time complexity in the Boolean setting, but the correspondence has important scope limitations.

  • Linear methods require at least ch∗d^D samples to learn degree-D targets with unknown permutation or rotation support.
  • CSQ complexity scales exponentially with leap: at least ch∗d^Leap(h∗) for Boolean inputs and ch∗d^Leap(h∗)/2 for Gaussian inputs.
  • For Boolean functions, the CSQ lower bound matches the conjectured total SGD time complexity scaling d^Leap(h∗).
  • These lower bounds apply to CSQ or noisy population-GD models, not directly to online-SGD, which uses one sample per time step.
  • For large support dimension P, regular-network SGD may struggle to fit the support function after identifying its coordinates, unlike CSQ when the function g is known.

3 Learning leap functions with SGD on neural networks

The paper analyzes online-SGD for learning low-dimensional polynomial targets with two-layer networks, using layerwise training and projections to control first-layer dynamics. The analysis shows support discovery through sequential saddle escapes, followed by second-layer fitting.

  • Setting: The setting uses isotropic Gaussian inputs, low-dimensional latent targets, and online-SGD on a two-layer neural network.For analysis, the latent coordinates are assumed to be a subset of the input coordinates, with fresh noisy samples at each step.
  • Fitting guarantees: The second-layer guarantee is proved for specific monomials and requires particular activation and initialization conditions.For general monomials, additional diversity in the first-layer projection would be needed because the limitation arises from the alignment proof technique.
  • Algorithm: The theoretical algorithm trains the first and second layers sequentially, freezes biases, and projects first-layer weights to keep them bounded.The first phase uses projected spherical and ℓ∞ operations; the second phase uses standard SGD with ridge regularization.
  • Algorithm: Layerwise training creates a stability problem because the first-layer weights continue evolving after support discovery while the second layer remains untrained.The projection is introduced to prevent these weights from growing excessively during the long first phase.
  • Single monomial: For a single degree-D monomial, first-layer training takes T1 = C0d^(D−1) log(d)^C0 steps and aligns weights with the target support.The stated high-probability event controls behavior on and outside the support, with alignment appearing only near the end of the dynamics.
  • Single monomial: The dynamics separate into a support-search plateau and a fitting phase in which second-layer training rapidly reduces the risk.With early stopping during first-layer training, the second layer cannot approximate the target under the stated layerwise procedure.
  • Leap functions: For leap-staircase targets, the modified SGD procedure learns the function in T1 = ˜Θ(d^(Leap(h∗)−1)) first-layer steps, followed by polynomial-in-1/ε second-layer training.The training moves between saddles, with each new support block requiring at most ˜Θ(d^max(L−1,1)) steps to identify its coordinates.

4 Discussion

The discussion conjectures that leap complexity governs neural-network learning time and presents matching CSQ lower bounds and modified-SGD upper bounds for restricted function classes. The analysis still relies on technical modifications and leaves broader extensions open.

  • Contributions: The paper conjectures that neural-network learning complexity is governed by the target function’s leap complexity rather than polynomial degree alone.For leap-staircase functions, modified SGD learns relevant indices and fits multilinear targets within d^O(Leap(h∗)) samples and runtime.
  • Complexity comparison: The proved SGD upper bounds align with d^Ω(Leap(h∗)) CSQ lower bounds for the studied class of functions.The lower bounds concern CSQ or noisy population-GD models rather than online-SGD itself.
  • Limitations and future work: The analysis uses layerwise training and projection modifications that the authors identify as directions for removal in future work.Other open directions include extending the dynamics beyond leap-staircase forms and generalizing leap complexity beyond isotropic inputs.

A Additional numerical simulations

The simulations show that SGD can learn hierarchical target functions through saddle-to-saddle dynamics, sequentially aligning network weights with the relevant support. The experiments also illustrate differences between leap levels, architectures, and data distributions.

  • Observed training dynamics: Across several experiments, SGD exhibits saddle-to-saddle dynamics as neural networks sequentially identify the target function’s support.This behavior appears for Boolean and Gaussian data, including leap-3 and leap-4 targets.
  • Gaussian simulations: For the Gaussian leap-3 target, SGD first aligns with x1 and x2, then slowly identifies x3, x4, and x5 before fitting the remaining function.The risk correspondingly shows an initial decrease, a plateau, and a later sharp decrease.
  • Boolean simulations: Increasing the Boolean ambient dimension from d = 50 to d = 400 makes saddle-to-saddle behavior more salient, with saddle escape dominating the trajectory.The leap-3 target is h∗(z) = z1 + z1z2z3 + z1z2z3z4z5z6.
  • Leap-level comparison: At d = 500 with Gaussian data, the leap-3 Hermite task plateaus at a saddle, whereas adding a He1(z1) term in the leap-1 task prevents this trapping.The comparison uses He3(z1) versus He1(z1) + He3(z1).
  • Architecture and support recovery: A leap-4 Boolean target produces saddle-to-saddle dynamics while the first layer iteratively picks up the relevant support.The experiment uses a width-1000, 5-layer ReLU ResNet with one-pass SGD.
  • Leap-1 and depth: For a leap-1 target, a two-layer sigmoid network quickly aligns with the support without saddles, while deeper networks fit the monomials faster than the two-layer network.The reported comparison uses d = 50 and contrasts a width-1000 two-layer network with a width-1000 five-layer ResNet.

B.3 Intuition for the proof of Theorem 1

The proof intuition tracks individual-neuron SGD through deterministic drift and stochastic fluctuations, showing sequential support alignment under carefully chosen step sizes and a projection correction. The discussion also marks scope boundaries for parity and post-support function fitting.

  • Drift–martingale decomposition: The analysis decomposes stochastic dynamics into population-gradient drift and a martingale difference term.Independence of samples supports this decomposition, while concentration controls the stochastic contribution over the learning horizon.
  • Sequential alignment: The first-layer dynamics amplify coordinates aligned with h∗ while keeping coordinates outside its support small during the analyzed phase.The heuristic tracks separate parameters for aligned and non-aligned coordinates and derives their distinct population-gradient scalings.
  • Drift–martingale decomposition: Choosing η1 and T1 balances martingale control against sufficient drift for support-aligned coordinates to grow.The stated conditions are η1κT1 ≲ d^-1/2 for fluctuations and η1κT1 ≳ d^(D/2−1) for drift.
  • Projection correction: A projection step is introduced because statistical fluctuations can otherwise cause unsupported coordinates to grow over long trajectories.The spherical-gradient analysis shows that projection changes the dynamics only negligibly, allowing the drift-plus-martingale argument to remain effective.
  • Scope and limitations: For fixed support dimension, learning the latent support dominates the dimension scaling, while fitting the function on that support contributes mainly constants.The discussion notes that this separation depends on sufficient expressivity and may fail for more complex post-support fitting tasks.
  • Scope and limitations: The complexity correspondence with CSQ lower bounds is qualified because CSQ and noisy-GD do not exactly match the SGD model.The paper states that population-gradient drift dominates on the analyzed horizon, whereas CSQ adds noise to query outputs.

C.3 Proof of Theorem 1

The proof controls neuron dynamics with stopping times, concentration bounds, and sequence estimates. It establishes high-probability growth of support coordinates while bounding off-support coordinates over the theorem’s time horizon.

  • Proof strategy: The proof first bounds the dynamics up to a stopping time controlling initialization, positive and negative excursions, and the theorem horizon.The argument assumes the theorem’s step-size and time conditions and works on a high-probability event.
  • Support coordinates: Coordinates in the target support are shown to grow through drift while remaining within controlled ranges.The proof separates endpoint control, growth bounds, and the associated stopping times for support coordinates.
  • Off-support coordinates: Coordinates outside the support remain bounded by combining martingale estimates with drift upper bounds.The argument treats the off-support coordinates after controlling the support and derives the required stopping-time inequalities.
  • Proof conclusion: The proof concludes Theorem 1 by choosing η1 and T1 so that all stopping-time conditions hold simultaneously.This yields the theorem’s parts through the previously established coordinate and excursion bounds.
  • Auxiliary estimates: Gaussian tail and hypercontractivity bounds control gradient-related random quantities under bounded activation and derivative assumptions.The auxiliary lemmas provide conditional probability and moment estimates used in the martingale and drift analysis.
  • Auxiliary estimates: Geometric sequence bounds supply the growth estimates needed for the nonlinear coordinate recurrences.The proof uses upper and lower bounds for sequences, with a separate simple form when the exponent equals 2.

D Proof of Theorem 2: sequential alignment to the support

The proof of sequential support alignment extends the single-monomial argument to multiple monomials. Each phase corresponds to aligning with one additional support block.

  • Phase decomposition: The dynamics are divided into L phases, each associated with alignment to one of the L monomials.The proof follows the single-monomial strategy while tracking the phases separately.
  • Phase decomposition: The analysis reuses the single-monomial bounds while allowing constants to depend only on the stated degree and activation parameters.This keeps the multi-monomial proof structurally parallel to the earlier argument.
  • Sequential alignment: Sequential alignment is therefore established by controlling successive support-alignment phases rather than treating the full support as one simultaneous event.The phase structure is the central proof device for Theorem 2.

D.1 Proof of Theorem 2: alignment to the full support

The full-support proof propagates coordinate and stopping-time bounds across successive phases. It shows that newly exposed support blocks align while earlier blocks remain controlled and off-support coordinates stay bounded.

  • D.1 Proof of Theorem 2: alignment to the full support: The population gradient is evaluated separately according to whether a coordinate belongs to the currently active support block or lies beyond the full support.This case distinction supplies the phase-dependent drift structure used throughout the proof.
  • D.1 Proof of Theorem 2: alignment to the full support: The multi-monomial gradient estimates follow by applying the single-monomial lemma to a sum of monomials.This provides the auxiliary reduction needed for the full-support theorem.
  • D.1 Proof of Theorem 2: alignment to the full support: The proof tracks the dynamics until a stopping time combining initialization, positive and negative excursions, and the theorem horizon.The same high-probability control event used for Theorem 1 underlies the phasewise argument.
  • D.1 Proof of Theorem 2: alignment to the full support: During earlier phases, coordinates in the next support block remain controlled until their designated alignment phase begins.This induction prevents later support blocks from growing prematurely.
  • D.1 Proof of Theorem 2: alignment to the full support: The proof bounds growth for coordinates in each newly aligned block using the same recurrence estimates as in the single-monomial case.The argument also maintains lower bounds for coordinates outside the currently active support block.
  • D.1 Proof of Theorem 2: alignment to the full support: Applying the phasewise bounds yields Theorem 2(a) and (b) under the prescribed choices of η1, T, and growth conditions.The final step explicitly reuses the earlier stopping-time argument for the theorem’s second conclusion.

D.2.1 Adaptive step-size

The adaptive step-size analysis establishes phase-wise alignment to increasingly complex monomials, with each phase operating on a distinct time scale. It also identifies proof limitations for constant-step-size joint training and for general leap functions.

  • Adaptive dynamics: Increasing leaps D1 < D2 < ... < DL make neurons align with the support sequentially at increasing time scales.The largest leap D determines the overall leap complexity.
  • Adaptive dynamics: O(d^Dl−1) steps suffice to escape the saddle associated with the l-th monomial under constant step size in practice.The text describes this saddle-to-saddle behavior even though the tight theorem uses scheduled learning rates.
  • Adaptive step-size theorem: Theorem 3 uses L learning-rate phases to obtain eΘ(d^Dl−1) scaling for aligning to each new monomial.The schedule chooses phase durations and step sizes according to the leap levels.
  • Limitations: The tight constant-step-size scaling remains unproved because it would require analyzing joint training of both layers.The authors instead establish the scaling using a learning-rate schedule.
  • Sequential support alignment: At the end of each phase, all neurons have selected exactly the current support [Pl] and no additional coordinates.The result also implies that the network cannot fit the remaining monomials using only second-layer weights at that point.
  • Scope: The proof leaves the conjecture for general leap functions to future work, while noting that compositionality is not required for the leap-complexity phenomenon.The presented theorems use nested sums of monomials as a convenient simplifying assumption.

E.1 Proof of Corollary 1: fitting one monomial

The proof of Corollary 1 constructs trained first-layer features for a single monomial and then fits its coefficients through second-layer ridge-regularized least-squares SGD. The argument combines concentration, feature construction, and a bounded-norm certificate.

  • Setup: The proof first analyzes h*(z) = z1 ··· zP, with the Hermite case handled by a similar argument.The analysis fixes zero biases in this part.
  • First-layer training: After first-layer training, relevant coordinates approach signed magnitude Δ while coordinates outside the support remain close to initialization.This yields the support-alignment guarantees used later in the certificate construction.
  • Feature construction: Trained neurons with matching initial coordinates can be combined to approximate EG[σ(Δ⟨δ,z⟩ + G)] for each sign vector δ.Lemma 8 supplies the good-feature construction underlying the certificate.
  • Certificate: A bounded-norm certificate is then used to represent the target monomial with trained first-layer features.The certificate exists with high probability under the stated parameter conditions.
  • Second-layer fitting: The second layer is trained with first-layer weights fixed, reducing the remaining problem to online SGD for ridge-regularized least-squares regression.The proof applies the linear-model convergence result to obtain low population loss.
  • Technical estimates: The proof controls feature correlations and approximation errors using Gaussian rotational invariance, Taylor expansions, and concentration bounds.These estimates establish the required high-probability feature and certificate properties.

E.2 Proof of Corollary 2: sequential learning of monomials

The sequential-learning proof extends the certificate construction from one monomial to a sum of monomials with increasing support sizes. It relies on specially designed activation diversity and phase-wise first-layer training.

  • Final fitting: The resulting bounded-norm certificate supports a generalization guarantee after second-layer training.The proof concludes by applying the same type of regression argument used for one monomial.
  • Target and theorem: The target is a sum of monomials with increasing support sizes P1 < P2 < ··· < PL = P.The theorem assigns separate training phases to these support levels.
  • Sequential training: Theorem 3 uses phase-specific durations and learning rates to align the first layer successively with each new monomial.The stated construction provides the parameters needed for the sequential dynamics.
  • Activation design: The proof requires an activation function with sufficient diversity, achieved by using biases that alter Hermite-coefficient signs.Simulations nevertheless report that standard ReLU activations are sufficient for these functions.
  • Activation construction: A linear system over sign vectors and degree indices is made invertible by choosing sufficiently separated bias locations.Diagonal terms remain bounded while off-diagonal terms become small for large separation.
  • Certificate construction: Bias-integrated features approximate powers of ⟨δ,z⟩, allowing linear combinations over sign vectors to reconstruct the monomial sum.The approximation error is stated as O(Δ).

E.3 Technical result: last iterate convergence of SGD on linear models

The technical result analyzes the last iterate of online SGD for a ridge-regularized linear model. It decomposes the excess loss into bias and variance terms and controls the stochastic variance through martingale bounds.

  • Setting: The section studies online SGD for a linear model on an embedding ϕ(x), using ridge-regularized square loss.The embedding abstracts the trained neural-network features used elsewhere in the paper.
  • Variance control: A martingale concentration lemma controls the variance term under bounded feature and label assumptions.The technical lemma applies to nonnegative processes with conditional contraction and bounded differences.
  • Population quantities: The proof defines the covariance-plus-regularization operator H and the feature-label vector v to express excess loss at iteration t.These quantities characterize the population linear-regression objective.
  • Error decomposition: The last-iterate analysis uses a bias-variance decomposition of the excess loss.The two terms are treated separately in the subsequent bounds.
  • Convergence guarantee: The resulting bound provides high-probability control of the variance contribution throughout the online-SGD dynamics.The argument uses an auxiliary process and a stopping-time construction.
  • Final iterate: The final lemma combines the convergence analysis with the regularized optimum to bound the excess loss of the last iterate.The comparison uses optimality of the ridge-regularized solution.

F.1 Linear methods

The section shows that linear methods face degree-dependent sample and representation complexity when learning low-support functions with unknown support on isotropic data. It establishes analogous limitations on both the Boolean hypercube and Gaussian data.

  • Linear-method setup: The linear estimator is obtained by minimizing regularized empirical risk in a Hilbert-space feature representation and predicts through an inner product with the learned weight vector.The learned vector lies in the span of the sample feature vectors.
  • Linear-method limitations: Ω(d^D) samples and width dim(H) ≥ d^D are required for linear methods to learn degree-D functions with small unknown support on isotropic data.The section states this takeaway for isotropic data and cites the hypercube result as established by prior work.
  • Hypercube data: On the hypercube, the lower bound applies to functions formed by permuting the coordinates on which a degree-D target h* depends.The proposition considers the class f*,σ(x)=h*(xσ(1),…,xσ(P)) over coordinate permutations.
  • Gaussian data: On Gaussian data, the proposition gives a new degree-driven limitation for linear methods that was not derived in ABM22.The result concerns a uniformly random semi-orthogonal embedding of the target support.
  • Proof strategy: The proof represents degree-D monomials as linear combinations of embedded target functions and lower-bounds prediction error through projection onto the span of observed features.The construction uses semiorthogonal matrices and then exploits orthogonal projection for Gaussian inputs.

F.2 Correlational Statistical Query (CSQ) methods

The section develops CSQ lower bounds for learning low-support functions whose leap measures the degree of structure outside a known coordinate subset. The bounds apply on both the Boolean hypercube and isotropic Gaussian data, with Gaussian results extending the analysis to general CSQ algorithms.

  • CSQ framework: A CSQ algorithm accesses data through bounded queries whose correlations with noisy labels are returned within tolerance τ.Noisy population gradient descent with injected gradient noise is given as an example of a CSQ algorithm.
  • Hypercube data: On the hypercube, n queries of tolerance τ succeed with probability at most controlled by 1−C_h* n d^−Leap(h*)/τ^2 over randomly permuted supports.The bound applies to the class obtained by applying h* to an unknown subset of coordinates.
  • Hypercube proof strategy: The hypercube lower bound uses a subset T witnessing the leap, then conditions on the corresponding known coordinates to show that remaining random permutations produce indistinguishable query responses.A union bound controls the probability that all initial queries return zero, and the final output is treated as a statistical query.
  • Gaussian data: For Gaussian data, the CSQ limitation is stated for polynomial targets of finite degree and depends on the isotropic leap of the target.The proof reduces to the components outside a coordinate subset witnessing the leap and analyzes random rotations using Hermite expansions.
  • Gaussian data: The Gaussian lower bound is presented as a limitation for any CSQ algorithm using n queries of tolerance ±τ over a random subspace embedding.The proposition gives a high-probability statement for the estimator returned by the algorithm.
Loading 2302.11055v2…