PaperlayerView exact revision on arXiv

Source-linked AI summary

Diverse Neural Network Learns True Target Functions

Bo Xie, Yingyu Liang, Le Song

arXiv:1611.03131v3cs.LGstat.ML

TL;DR

The paper asks whether stationary points of non-convex neural-network training can learn the target function and what factors support that outcome. It analyzes one-hidden-layer ReLU networks using first-order conditions and connects an extended feature matrix’s minimum singular value to activation-kernel spectrum and unit diversity. It reports no spurious local minima under a sufficiently large minimum singular value, with numerical simulations supporting the theory.

  • Problem

    Because neural-network training minimizes a non-convex empirical loss with potentially many local minima and saddle points, it remains unclear whether stationary points learn the target function and what conditions support that.

    Source: §1 · p. 1

  • Method

    The paper analyzes first-order optimality in one-hidden-layer ReLU networks and bounds the extended feature matrix’s minimum singular value using activation-kernel spectrum and weight discrepancy.

    Source: §5 · p. 7

  • Results

    Diverse units have no spurious local minima when the extended feature matrix’s minimum singular value is sufficiently large, and reported simulations match the theory.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results suggest regularizing for unit diversity as a way to potentially improve generalization.

    Source: §10 · p. 14

    The analysis does not establish how to obtain a solution with small gradient, and theoretical analysis of gradient descent is left for future work.

    Source: §9.1 · p. 13

Abstract

from arXiv · show

Neural networks are a powerful class of functions that can be trained with simple gradient descent to achieve state-of-the-art performance on a variety of applications. Despite their practical success, there is a paucity of results that provide theoretical guarantees on why they are so effective. Lying in the center of the problem is the difficulty of analyzing the non-convex loss function with potentially numerous local minima and saddle points. Can neural networks corresponding to the stationary points of the loss function learn the true target function? If yes, what are the key factors contributing to such nice optimization properties? In this paper, we answer these questions by analyzing one-hidden-layer neural networks with ReLU activation, and show that despite the non-convexity, neural networks with diverse units have no spurious local minima. We bypass the non-convexity issue by directly analyzing the first order optimality condition, and show that the loss can be made arbitrarily small if the minimum singular value of the "extended feature matrix" is large enough. We make novel use of techniques from kernel methods and geometric discrepancy, and identify a new relation linking the smallest singular value to the spectrum of a kernel function associated with the activation function and to the diversity of the units. Our results also suggest a novel regularization function to promote unit diversity for potentially better generalization.

1 Introduction

The paper asks whether stationary points of neural-network training can learn the target function despite a non-convex loss, and what conditions support that outcome. It analyzes one-hidden-layer ReLU networks, relating optimization to unit diversity and activation-kernel spectrum.

1 Introduction

  • Diverse units yield no spurious local minima when the extended feature matrix has a sufficiently large minimum singular value.The training loss is tied to the gradient magnitude and that singular value.Source: §1 · p. 2
  • The minimum singular value is linked to activation-kernel spectrum and unit diversity, with slower spectral decay and more diverse weights associated with better optimization and generalization.The bound separates an ideal spectrum and diverse weight configuration from deviations measured by discrepancy.Source: §1 · p. 2
  • The analysis uses first-order optimality conditions to bypass non-convexity and does not assume activation patterns are independent of the data.The dependence of activation patterns on data and weights underlies the kernel-spectrum and diversity connection.Source: §1 · p. 2
  • The analysis suggests a regularization scheme to promote unit diversity for potentially better generalization.The proof uses techniques from kernel methods and geometric discrepancy.Source: §1 · p. 2
  • Numerical simulations support the theory by examining discrepancy, minimum singular values, and regularization effects.The reported examples match the theory and accord with gradient-descent practice.Source: §1 · p. 2

2 Related work

Prior work offers partial explanations of neural-network optimization, but the cited analyses leave gaps in their fit to ReLU networks, generalization guarantees, or practical gradient-based learning.

2 Related work

  • The random-feature perspective connects kernels to neural networks, but uses random rather than learned weights; learned weights can yield smaller models [Rahimi and Recht, 2009, Cho and Saul, 2009].The paper applies kernel-method techniques to analyze learned neural-network weights.Source: §2 · p. 2
  • Spin-glass analysis finds many low-loss local optima in a special random polynomial network, but differs from ReLU networks and gives no generalization guarantee [Choromanska et al., 2015].Source: §2 · p. 2
  • Work on nonlinear networks that assumes activation-pattern independence from actual data relies on an unrealistic assumption [Kawaguchi, 2016].Source: §2 · p. 2
  • Tensor methods avoid non-convex optimization but produce algorithms unlike typical methods using only empirical-loss gradients [Janzamin et al., 2015].Other cited work addresses saddle points in gradient descent [Lee et al., 2016, Ge et al., 2015], while saddle points were proposed as a major optimization obstacle [Dauphin et al., 2014].Source: §2 · p. 3
  • A zero-gradient result outside a measure-zero exception set does not ensure small loss at small gradients, and the exception set is uncharacterized [Soudry and Carmon, 2016].Source: §2 · p. 3

3 Problem setting and preliminaries

The paper sets up one-hidden-layer ReLU regression and seeks conditions under which approximate stationary points have low error. It relates this question to the extended feature matrix’s minimum singular value, the activation-kernel spectrum, and unit-weight diversity.

3 Problem setting and preliminaries

  • The setup studies least-squares learning from unit-sphere inputs with a one-hidden-layer ReLU class, seeking conditions where small gradients bound training and test errors.Source: §3 · p. 3

3.1 First order condition

  • At an exact stationary point, full column rank of the extended feature matrix forces zero residual; with approximate stationarity, its minimum singular value must be large to control residual size.The analysis assumes the feature matrix has more rows than columns, a necessary condition for full column rank.Source: §3.1 · p. 4

3.2 Spectrum decay of activation kernel

  • For d = 1500, kernel eigenvalues are about Ω(m−1) over a large range; for d = 15 and m = 3000, the Gram-matrix spectrum closely resembles the kernel spectrum, underlying its relation to D⊤D.The kernel is a dot-product kernel whose spectrum is obtained through spherical-harmonic decomposition; its m-th eigenvalue γm is related to sm(D).Source: §3.2 · pp. 4–5

3.3 Weight discrepancy

  • Weight diversity is measured by discrepancies between the empirical weight distribution and the uniform sphere measure over input-defined slices; smaller discrepancy indicates more diverse weights.The paper considers both L∞ and L2 discrepancy measures.Source: §3.3 · p. 5

4 Main results

For sufficiently large n and d, the results bound training loss and generalization error for most feasible weight configurations. Within the characterized set, small-gradient solutions have small error, and critical points are global optima.

4 Main results

  • With probability at least 1 − cm^−log m − δ, the result holds for every W in a set GW covering a 1 − δ′ fraction of feasible weights.The theorem states this set-based result for any v in {−1, 1}^n.Source: §4 · p. 6
  • For W in GW, gradient norm at most ε gives training loss O(ε) and generalization error ˜O(ε + 1/√m).The result applies to solutions in GW and is stated for sufficiently many data points.Source: §4 · p. 6
  • Any critical point in GW is a global optimum, and randomly sampled weights are likely to lie in this set.The paper connects this condition to random initialization, while noting that remaining in GW during training is part of the proposed explanation.Source: §4 · p. 6
  • The explicit closed form for discrepancy makes membership in GW checkable and allows regularization to keep weights in the set.The paper notes that the discrepancy is given in closed form and can be used to design such regularization.Source: §4 · p. 6
  • Taking n and d of order ˜O(m^β) satisfies the theorem's condition with ξ = η = 1/4 and yields the special-case result.The paper also notes another option involving larger n, matching the empirical observation that overspecified networks are easier to optimize.Source: §4 · p. 7

5 Analysis roadmap

The analysis bounds the smallest singular value of the extended feature matrix using the activation-kernel spectrum and weight diversity. This bound supports the training-loss and generalization results, while distinguishing a quantitatively large singular value from mere full rank.

5 Analysis roadmap

  • The key technical result lower-bounds the smallest singular value of D using the activation-kernel spectrum and weight discrepancy, then uses it to bound training loss and generalization error.The generalization bound uses Rademacher complexity.Source: §5 · p. 7
  • When ξ = η = 1/4, with probability at least 1 − c m^(-log m) − δ, the squared smallest singular value sm(D)^2 is at least c m, for some constant c > 0.Source: §5 · p. 7
  • Full rank with probability one under small perturbations [Soudry and Carmon, 2016] does not ensure a useful lower bound on the smallest singular value.The paper instead relates that value to the activation and weight diversity.Source: §5 · p. 7
  • If all unit weights coincide when d < m, D cannot have rank m; near-identical weights can likewise make its smallest singular value small or zero.This motivates requiring a notion of weight diversity.Source: §5 · p. 7
  • The proof bounds the kernel matrix's smallest eigenvalue, around mγ_m/2, and controls its difference from the data-dependent matrix through weight discrepancy.The ideal spectrum term is handled using kernel eigendecomposition and matrix concentration; sufficiently diverse weights make the spectral difference small.Source: §5 · p. 8

6 Bounding the smallest singular value

The section derives a lower bound on the smallest singular value by comparing a data-dependent matrix with a kernel-based matrix. It then characterizes the weight discrepancy that controls their difference and is small for most uniformly sampled weights.

6 Bounding the smallest singular value

  • Lemma 4 yields the singular-value bound when the discrepancy term is sufficiently small relative to the kernel-spectrum term.The proof first bounds the discrepancy quantity and then applies Lemma 4.Source: §6 · p. 8

6.1 Proof of Lemma 4

  • For ReLU, the proof assumes unit-norm weights without loss of generality, defines G from the uniform-sphere expectation, and identifies its entries with the kernel g(x_i, x_j).This lets the proof reason about the eigenspectrum of G.Source: §6.1 · pp. 8–9
  • The proof bounds λ_m(G) first, then bounds |λ_m(G) − λ_m(G_n)| to obtain the bound for G_n.It uses a truncated spherical-harmonic decomposition and a matrix Chernoff bound for the first step, then Weyl's theorem for the eigenvalue difference.Source: §6.1 · p. 9
  • Because the summands in the relevant U-statistic are dependent, the proof uses a Bernstein inequality for U-statistics rather than an i.i.d.-entry concentration bound.The bound is stated to hold with probability at least 1 − δ.Source: §6.1 · p. 9

6.2 Characterizing the discrepancy

  • The L2 discrepancy measures the difference between average pairwise unit similarity and its uniform-distribution expectation, and is small with high probability for uniformly sampled weights.The paper uses concentration of a U-statistic to show that most weights lie in the characterized set GW.Source: §6.2 · p. 10

7 Final bound on generalization error

The proof sketch turns the smallest-singular-value bound into a bound on the residual and training loss, then derives generalization error using concentration and complexity bounds. It obtains the special-case theorem by choosing n and d so that most weights satisfy the required discrepancy condition.

7 Final bound on generalization error

  • For a solution satisfying Theorem 2's assumption, the gradient bound and Theorem 3 imply a bound on the residual through the inverse smallest singular value.The proof uses ∥r∥ ≤ ∥∂L/∂W∥/sm(D).Source: §7 · p. 11
  • McDiarmid's inequality and Rademacher complexity are used to derive the generalization bound, with function-class complexity at most CW/√m.The argument bounds the loss difference between data points and composes the complexity bound with the loss function.Source: §7 · p. 11
  • Choosing n = ˜O(m^β) and d = ˜O(m^β) makes the discrepancy condition hold for weights in GW and yields Theorem 1 from Theorem 2.The proof sketch invokes Lemma 8, which shows that most W fall into GW.Source: §7 · p. 11

8 Discussions

The discussion extends the analysis beyond least-squares loss and ReLU, and considers subgradients and nonuniform input distributions. These extensions expose trade-offs and conditions on the loss, activation, and weight distribution.

8.1 Other loss functions

  • For strongly convex losses, including logistic loss, bounded residuals imply small individual derivatives and therefore small loss.The analysis is currently tied to least squares, but the authors describe this extension as fairly straightforward.Source: §8.1 · p. 11

8.2 Other activation functions

  • Larger rectified-polynomial degree t slows spectrum decay but raises Rademacher complexity, while smaller t improves the stated generalization bound.The preferred t balances the minimum-singular-value benefit of slower spectrum decay against the smaller complexity for smaller t.Source: §8.2 · p. 12

8.3 (Sub)gradient of the activation function

  • The ReLU guarantees hold with high probability for any valid subgradient choice at zero under the theorem conditions.The analysis argues that choices at zero do not affect its expectations because that event has probability zero.Source: §8.3 · p. 12

8.4 Other input distribution

  • For nonuniform inputs, weights should match the input distribution to preserve slow kernel-spectrum decay; on a positive-orthant sphere, matching weights yield larger or equal minimum eigenvalues, with the gap becoming negligible at higher dimensions.The authors consequently regard uniform weights on the whole sphere as reasonable in high dimensions; for general input distributions, they describe forming a weight distribution by superposing local matching distributions.Source: §8.4 · pp. 12–13, Table 1 · p. 13

9 Numerical evaluation

The numerical evaluation examines gradient descent's discrepancy and discrepancy-based regularization. Experiments find reasonable discrepancy scaling and generally lower errors or larger minimum singular values with regularization.

9.1 Discrepancy and gradient descent

  • Gradient-descent solutions' squared discrepancy scales slightly worse than O(n^-1) but better than O(n^-1/2), suggesting reasonable discrepancy.The experiment used dimension d = 50, a 50-unit target, and networks of varying size.Source: §9.1 · p. 13, Figure 3 · p. 14

9.2 Regularization

  • Minimizing R(W) corresponds to smaller regularization values and larger minimum singular values in the tested weights.The comparison used 20 random weight sets with n = 100 and d = 100, evaluating singular values with m = 3000.Source: §9.2 · p. 13, Figure 4 · p. 14
  • Regularization lowers training and test errors in most settings, and slightly improves test error for every tested one-hidden-layer MNIST network.When unregularized performance is better, the errors remain small and within the same range as the standard deviation.Source: §9.2 · p. 14, Table 2 · p. 14

10 Conclusion

The conclusion identifies conditions under which local optima become global optima, and names kernel spectrum and unit diversity as key factors. The appendices develop spectral and matrix-concentration results used in the analysis.

10 Conclusion

  • Local optima become global optima under novel conditions, with kernel spectrum and unit diversity measured by discrepancy identified as key factors.The analysis focuses on one-hidden-layer networks.Source: §10 · p. 14
  • The analysis focuses on least-squares loss and uniform inputs, while the authors say the technique can readily extend to other losses and input distributions.The analysis is independent of the actual algorithm; exploring its interplay with gradient descent remains future work.Source: §10 · pp. 14–15

A Spherical harmonic decomposition and kernel spectrum

B Bounding λm(G) using matrix concentration bound: Proof of Lemma 5

  • The proof bounds λm(G) using matrix concentration, relying on positive-semidefinite matrices and the equality of the relevant eigenvalues for G[m] and Y.The proof invokes a matrix Chernoff bound before setting ϵ = 1/2.Source: B Bounding λm(G) using matrix… · pp. 17–18

C Bounding the difference between λm(G) and λm(Gn): Proof of Lemma 6

These appendices bound the difference between population and empirical kernel-matrix eigenvalues, relate weight discrepancy to uniformity, and analyze discrepancy and kernel-spectrum properties relevant to the bounds.

C Bounding the difference between λm(G) and λm(Gn): Proof of Lemma 6

  • For uniformly distributed spherical data, an inner-product tail bound contributes to a high-probability bound on the difference between λm(G) and λm(Gn).The analysis relies on pairwise input inner products being sufficiently small.Source: C Bounding the difference between… · pp. 18–19

D Discrepancy of the weights

  • The weight discrepancy dsp(W, S) measures the difference between the empirical measure induced by W and the measure induced by a uniform distribution.For ReLU, the derivative does not depend on the norm of the weight vector, so the analysis can focus on unit-norm weights.Source: D Discrepancy of the weights · p. 19

D.1 Computing L2 discrepancy for ReLU 

  • The analysis gives a concrete high-probability bound on L2 discrepancy when the weight vectors are sampled uniformly from the unit sphere.Theorem 7 computes L2 discrepancy for fixed W, and Lemma 8 treats uniformly random W.Source: §D.1 · p. 21

E The spectrum of γm

  • ReLU's associated kernel spectrum decays faster than the desired O(1/√m) rate, while some arccos kernels decay more slowly; larger n gives more nonlinear activations and slower decay.The analysis seeks slower spectrum decay within a practical range such as m ≤ 1000000.Source: E The spectrum of γm · p. 23

F Rademacher complexity and final error bounds: Proof of Theorem 2 and Theorem 1

The proof bounds generalization error for bounded data using Rademacher complexity, then combines that bound with earlier results to obtain Theorems 2 and 1.

F Rademacher complexity and final error bounds: Proof of Theorem 2 and Theorem 1

Loading 1611.03131v3…