PaperlayerView exact revision on arXiv

Source-linked AI summary

Hidden Minima in Two-Layer ReLU Networks

Yossi Arjevani

arXiv:2312.16819v4cs.LGmath.OCstat.ML

TL;DR

Hessian spectra at hidden and non-hidden minima coincide up to O(d^-1/2), complicating their analytic distinction. The paper studies loss-minimizing and loss-maximizing tangency arcs, finding that their structure and symmetry distinguish the minimum types through higher-order eigenvalue terms.

  • Problem

    Hessian spectra at the two minimum types agree up to O(d^-1/2), limiting their usefulness for analytically distinguishing hidden minima.

    Source: §1 · p. 3

  • Method

    The paper analyzes the structure and symmetry of tangency arcs realizing minimum or maximum loss near critical points, using group representation theory and o-minimal results.

    Source: §1 · p. 4, O-minimal theory · p. 8

  • Results

    Type I and type II minima differ in the structure and symmetry of their minimum-loss arcs, as determined by leading Hessian eigenvalue terms beyond those previously analyzed.

    Source: §1 · p. 4, §5 · p. 15

  • Takeaways & Limitations

    In the setting studied, distinguishing the minimum types requires analyzing tangency-arc structure and symmetry rather than relying on the previously computed Hessian spectrum alone.

    Source: §1 · p. 3, §5 · p. 15

    The paper restricts itself to selected results from the broader theory and does not develop the full theory presented in [1].

    Source: §2 · p. 7

Abstract

from arXiv · show

We consider the optimization problem associated with training two-layer ReLU networks with \(d\) inputs under the squared loss, where the labels are generated by a target network. Recent work has identified two distinct classes of infinite families of minima: one whose training loss vanishes in the high-dimensional limit, and another whose loss remains bounded away from zero. The latter family is empirically avoided by stochastic gradient descent, hence \emph{hidden}, motivating the search for analytic criteria that distinguish hidden from non-hidden minima. A key challenge is that prior analyses have shown the Hessian spectra at hidden and non-hidden minima to coincide up to terms of order \(O(d^{-1/2})\), seemingly limiting the discriminative power of spectral methods. We therefore take a different route, studying instead certain curves along which the loss is locally minimized. Our main result shows that arcs emanating from hidden minima exhibit distinctive structural and symmetry properties, arising precisely from \(\Omega(d^{-1/2})\) eigenvalue contributions that are absent from earlier analyses.

1. Introduction

This paper studies whether curves of locally minimal or maximal loss can distinguish hidden from non-hidden minima in two-layer ReLU networks. It shows that these arcs have distinct structure and symmetry, including differences determined by Hessian eigenvalue terms beyond the order previously analyzed.

1. Introduction

  • Type I minima are hidden because gradient-based methods do not detect them empirically, and their loss stays bounded away from zero while known type II minima have loss O(1/d).Type I minima are nevertheless provable local minima; global minima are type II.Source: §1 · p. 3
  • The Hessian spectra at type I and type II minima agree through O(d^-1/2), limiting their use for distinguishing the two types.Expected loss at initialization is at least an order of magnitude larger than loss at either type of minimum.Source: Table 1 · p. 3, §1 · p. 3
  • The paper studies arcs realizing the minimum or maximum loss on spheres centered at critical points, focusing on their structure and symmetry.These arcs are examined as a means of identifying properties that distinguish hidden minima.Source: §1 · pp. 3–4
  • For symmetry-breaking critical points, arcs minimizing or maximizing loss are themselves symmetry-breaking; the analysis uses isotropy groups under row and column permutations.When the target has certain invariances, empirically observed minima have isotropy groups that are proper subgroups of the diagonal subgroup.Source: §1 · p. 4
  • The authors classify admissible arc structures using intersections of subgroup-invariant and fixed subspaces, with tangency arcs approaching critical points along Hessian eigenspaces.The representation-theoretic methods are stated to apply beyond the groups considered in the paper.Source: §1 · p. 4
  • For four infinite families of minima, two leading Hessian eigenvalue terms determine arc structure and symmetry, distinguishing type I from type II where earlier spectral analyses could not.The paper also describes numerical construction and continuation of tangency arcs to estimate distances from minima to adjacent critical points.Source: §1 · pp. 4–5

2. Framework: the tangency set and symmetry

The section uses tangency sets to study curves attaining local loss minima and maxima near critical points. O-minimal and representation-theoretic tools describe these arcs and their symmetry, including for large-dimensional critical-point families.

2. Framework: the tangency set and symmetry

  • The framework studies m(r) and M(r) through tangency sets, which inherit symmetries from their associated functions and are used to characterize hidden minima.The paper restricts its treatment to selected tangency-arc results rather than developing the full theory, which could also use global topological methods or higher derivatives.Source: §2 · pp. 5, 7

O-minimal theory.

  • Definability ensures arcs attaining the minimum and maximum loss on spheres around a point, and such arcs approach a critical point tangent to the Hessian eigenspace for the minimal or maximal eigenvalue, respectively.For quadratic functions, the tangency set consists of eigenvectors; for definable functions, the extremizing arcs exist even though this is not guaranteed for arbitrary functions.Source: §2 · pp. 6–7, O-minimal theory · p. 8

Representation theory of groups.

  • For invariant functions, group representations organize Hessian invariant subspaces, while Table 2 links the minimal eigenvalue’s irreducible representation to minimizing-curve structure and symmetry.The table caption also states that maximal eigenvalues with leading terms growing linearly with d belong to the t- and s-representations, with dynamics concentrating near subspaces of multiplicity O(d).Source: Table 2 · p. 6, Representation theory of groups · pp. 9–10

Expressing curves of critical points as Puiseux series in d.

3. Main results: structure and symmetry of tangency arcs

The results use representation theory to constrain the symmetry types of tangency arcs. Applied to type I and type II minima, they give different maximal isotropy types for arcs realizing the local minimum of the loss.

3. Main results: structure and symmetry of tangency arcs

  • For an Sd-map on M(d,d), Theorem 1 describes how eigenvalues on the trivial, standard, exterior-square, and y isotypic components appear in subspaces with specified maximal isotropy types.The trivial component has maximal isotropy ΔSd; the standard component has Δ(Sd−1 × S1), and the exterior-square and y components have Δ(Sd−2 × S1²).Source: §3 · p. 12
  • Combining the isotypic-component restrictions with tangency arcs’ Hessian eigenspace alignment yields constraints on the maximal isotropy type of an arc’s initial direction.For an eigenvalue in the trivial component the type is ΔSd; in the standard component it is Δ(Sd−1 × S1), and in the exterior-square or y component it is Δ(Sd−2 × S1²).Source: §3 · p. 12

3.1. Structure and symmetry of tangency arcs of type I and type II minima.

  • For the specified type I and type II minima, the Hessian eigenvalues are represented by Puiseux series computed to two leading terms, and their minimal and maximal eigenvalues identify isotypic components.The minimal-eigenvalue component is used to determine the isotropy types of arcs realizing m(r).Source: §3.1 · p. 13
  • For type I minima, arcs giving m(r) have maximal isotropy type Δ(Sd−p−2 × Sp+2), whereas for type II minima it is Δ(Sd−p−1 × Sp+1).The stated families have isotropy Δ(Sd−p × Sp), for p in {0, 1}, with k=d; the methods and results also apply to other p and k>d.Source: §3.1 · p. 13

4. Numerical results: bounding the distance to the nearest critical point

The authors numerically continue tangency arcs from minima to estimate distances to adjacent critical points. The estimates support the predicted arc symmetries and show that nearby spurious minima are closer than global minima at small dimensions, a pattern that changes as dimension grows.

4. Numerical results: bounding the distance to the nearest critical point

  • Definable tangency arcs can connect a minimum to nearby critical points, and their numerical construction provides a way to estimate those distances.Local triviality supplies the connection; the tangency set has finitely many definable connected components.Source: §4 · pp. 13–14
  • Numerical continuation estimates arc lengths by solving constrained stationarity equations in small radius increments, stopping at a singular Jacobian or the chosen maximum radius.Arcs start at C + 10^-7 B, with B an eigenvector; arcs from small-eigenvalue directions tend to terminate earlier.Source: §4 · p. 14
  • The observed radii drop when the ambient invariant space is enlarged, as predicted from the symmetry of the arc realizing m(r).For CII_1, the arc has symmetry Δ(S_{d−2} × S^2_1), motivating the larger invariant space.Source: §4 · p. 14

5. Concluding remarks and future work

The conclusion identifies tangency arcs as a way to distinguish hidden type I minima from type II minima through their structure and symmetry. It also situates the analysis alongside a biased-kernel extension and broader work on symmetry breaking in deep architectures.

Bias terms.

  • For biased networks, the kernel and its derivatives admit explicit expressions, while a systematic structural and spectral analysis of the biased case is carried out in.The expressions use normal and bivariate-normal distribution functions.Source: Bias terms · pp. 16–17

Symmetry breaking and deep architectures.

  • The paper frames tangency-arc symmetry breaking as an instance of a general approach to tractability in symmetric nonconvex optimization, developed in [1].Related work analyzes deep-network loss landscapes using distribution theory and geometric measure theory.Source: Symmetry breaking and deep architectures · p. 17

7. The o-minimal structure Ran

The section establishes that the loss can be treated within the o-minimal structure Ran. Its axioms support definability under standard operations, and the loss’s component functions are definable there.

7. The o-minimal structure Ran

  • An o-minimal structure is a sequence of collections of sets closed under Boolean operations, products with R, projections, and polynomial zero sets, with each one-dimensional set a finite union of intervals and points.The axioms are listed in the section’s definition.Source: §7 · p. 21
  • Definable sets remain definable under first-order constructions, and standard operations such as inversion, addition, multiplication, and composition preserve definability.The discussion points to [50, Section A] for further details.Source: §7 · p. 21
  • The loss components are Ran-definable because their norms and normalized inner products are algebraic, while sin, cos, and arccos are definable on the required compact domains.The loss can therefore be expressed as a sum of terms built from these functions.Source: §7 · p. 21

8. Proof of Lemma 1

The proof uses definability and the monotonicity theorem to establish tangency arcs and identify their initial directions with Hessian eigenspaces. For arcs realizing the local minimum, the direction corresponds to the minimal Hessian eigenvalue.

8. Proof of Lemma 1

  • The monotonicity theorem partitions a definable function’s domain into finitely many intervals on which it is continuously differentiable and either constant or strictly monotone.The proof invokes this result to obtain the relevant one-sided limits.Source: §8 · pp. 21–22
  • A definable tangency arc has a finite one-sided tangent at the critical point, and its initial direction is a Hessian eigenvector.The proof obtains the tangent and limiting coefficient using the monotonicity theorem and the Hessian expansion.Source: §8 · p. 22
  • For an arc realizing m(t), the initial direction is an eigenvector associated with the minimal eigenvalue of the Hessian.The proof uses arc-length parameterization, a second-order expansion, and eigenvalue perturbation.Source: §8 · p. 22
  • The proof compares the arc’s limiting coefficient with the least eigenvalue of the perturbed Hessian, which converges to the least eigenvalue at the critical point.This yields the stated initial-direction result for the minimizing arc.Source: §8 · pp. 22–23

9. Proof of Theorem 1

The proof decomposes the matrix representation into isotypic components and analyzes them case by case. For the standard component, a three-dimensional scalar matrix determines the restricted eigenvalues and the maximal isotropy type.

Representation decomposition

  • The natural coordinate-permutation representation splits into the invariant all-equal subspace E and its complementary hyperplane.The all-equal subspace carries the trivial representation, while E and Hd−1 are irreducible, real, and non-isomorphic.Source: §9 · p. 23
  • The proof collects the sub-representations of Dd, Sd, and Ad by isomorphism type and proves Theorem 1 case by case.The decomposition identifies trivial, standard, and exterior-square components among these spaces.Source: §9 · pp. 23–24

The isotypic component Vs

  • The three eigenvalues of [αij] give the eigenvalues of A|Vs with multiplicities multiplied by d−1, and also determine the restriction to the maximal-isotropy subspace.The maximal isotropy type in Vs is (Sd−1 × S1).Source: §9 · pp. 24–25

The isotypic components Vx and Vy

  • The x- and y-isotypic components each have a single eigenvalue of multiplicity (d−1)(d−2)/2, with a one-dimensional intersection with the specified isotropy-fixed subspace.Both components have zero intersection with the fixed subspaces for Sd and Sd−1×S1.Source: §9 · p. 25

10. Proof of Theorem 2

The proof computes higher-order Puiseux terms for type I and II minima to identify eigenvalue contributions of order O(d−1/2). It uses a subgroup decomposition and symmetry-based simplifications for the analysis.

Higher-order eigenvalue terms

  • Higher-order Puiseux terms for type I and II minima are required to compute O(d−1/2) eigenvalue terms.The analysis seeks the isotypic components giving the minimal eigenvalue.Source: §10 · p. 26

Subgroup decomposition

  • The analysis restricts the diagonal Sd action on M(d, d) to Sp×Sq, with p+q=d and d>p>d/2.The matrix space is decomposed into M(p,p), M(q,q), M(p,q), and M(q,p), with the subgroup actions specified by row and column permutations.Source: §10 · p. 26

Symmetry and simplifications

  • By orthogonal symmetry of the Gaussian distribution, the results hold for any T determined by a matrix in O(Rd); the proof sets T=I and the second-layer weights to ones.The second-layer simplification is justified because the object of study is the loss landscape rather than optimization processes.Source: §10 · p. 26
Loading 2312.16819v4…