PaperlayerView exact revision on arXiv

Source-linked AI summary

SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data

Alon Brutzkus, Amir Globerson, Eran Malach, Shai Shalev-Shwartz

arXiv:1710.10174v1cs.LG

TL;DR

Existing generalization theory does not explain why SGD can generalize well in over-parameterized networks, where multiple global minima may fit the data poorly. The paper studies SGD on two-layer networks learning linearly separable data, using Leaky ReLU activations and a compression-based analysis. It proves convergence to a global minimum and network-size-independent generalization guarantees, while showing that ReLU can have spurious local minima.

  • Problem

    Existing generalization bounds do not explain why SGD finds well-generalizing solutions in over-parameterized networks despite the existence of poorly generalizing global minima.

  • Method

    The paper analyzes SGD training of two-layer over-parameterized networks on linearly separable data, using Leaky ReLU optimization guarantees and a compression-based generalization analysis.

  • Results

    SGD converges to a global minimum with good generalization for Leaky ReLU, with guarantees independent of network size; ReLU instead has spurious local minima.

  • Takeaways & Limitations

    In the studied setting, SGD provides an inductive bias toward solutions expressible using a small set of training points, supporting generalization despite over-parameterization.

  • Takeaways & Limitations

    The analysis does not establish the same convergence and generalization results for ReLU activations or for different data assumptions.

Abstract

from arXiv · show

Neural networks exhibit good generalization behavior in the over-parameterized regime, where the number of network parameters exceeds the number of observations. Nonetheless, current generalization bounds for neural networks fail to explain this phenomenon. In an attempt to bridge this gap, we study the problem of learning a two-layer over-parameterized neural network, when the data is generated by a linearly separable function. In the case where the network has Leaky ReLU activations, we provide both optimization and generalization guarantees for over-parameterized networks. Specifically, we prove convergence rates of SGD to a global minimum and provide generalization guarantees for this global minimum that are independent of the network size. Therefore, our result clearly shows that the use of SGD for optimization both finds a global minimum, and avoids overfitting despite the high capacity of the model. This is the first theoretical demonstration that SGD can avoid overfitting, when learning over-specified neural network classifiers.

1 Introduction

The paper studies why SGD can generalize well in over-parameterized neural networks despite their capacity to fit training data with poor test performance. It tests whether this behavior persists for two-layer networks learning linearly separable data.

  • Over-parameterized networks have far more parameters than training points, yet SGD often finds models with low training error and good generalization.The paper frames this observed behavior as unexplained by existing theory.
  • Multiple global minima can generalize poorly, so low training error alone does not guarantee low test error.This motivates studying how the optimization procedure selects among global solutions.
  • The paper asks whether a large network overfits linearly separable data, even though a linear classifier would suffice.The setting isolates the effect of over-parameterization from the need for nonlinear decision boundaries.
  • SGD is proposed to introduce an inductive bias toward low-complexity solutions that generalize well in this over-parameterized setting.The paper uses this setting as a test bed for studying over-parameterization.

2 Problem Formulation

The problem formulation uses linearly separable binary data and a two-layer network with fixed second-layer weights. SGD updates only the first-layer weights while minimizing mean hinge loss.

  • The data distribution is binary and linearly separable with unit margin: y⟨w∗,x⟩≥1 almost surely.Inputs lie in the unit Euclidean ball, and training examples are sampled i.i.d. from the distribution.
  • The model is a two-layer network with 2k hidden units, parameters W and v, and element-wise nonlinear activation σ.The network output is defined from these parameters and the activation function.
  • The empirical objective is the mean hinge loss over the training set.
  • The second-layer weights are fixed, while only the first-layer weight matrix W is optimized.Positive homogeneity of Leaky ReLU and ReLU preserves the expressive power of the represented networks in this formulation.
  • For the considered activations, the empirical loss has a zero global minimum.
  • SGD uses batch size 1, randomly selects a training point at each iteration, and updates W with constant learning rate η.The update is driven by the selected example's loss gradient.

3 Main Result

For linearly separable data, Leaky ReLU networks admit SGD optimization and generalization guarantees independent of network size, whereas ReLU networks exhibit different optimization behavior.

  • Leaky ReLU: Leaky ReLU activations are defined as σ(z) = max{αz, z} for 0 < α < 1.
  • Optimization guarantees: SGD converges to a global minimum despite optimizing the non-convex loss.
  • Optimization guarantees: The convergence bound is independent of the number of hidden neurons, and the paper also establishes a lower bound on the number of non-zero updates.
  • Generalization guarantees: A compression bound shows that, with sufficiently many samples independent of network size, SGD reaches a global minimum with good generalization despite other global minima overfitting.
  • Generalization guarantees: The learned solution is biased toward models expressible using a small set of training points, which supports its good generalization behavior.
  • Summary: Overall, the paper provides provable optimization, generalization, and expressive-power guarantees for over-parameterized networks in the Leaky ReLU, linearly separable setting.
  • ReLU setting: For ReLU activations, the loss has spurious local minima, so the Leaky ReLU global-convergence result does not extend to this case.
  • ReLU setting: With ReLU, sufficiently large networks can make SGD converge globally with high probability, whereas sufficiently small networks can lead to local minima with high probability.

4 Related Work

Prior work established complexity-based and optimization-landscape analyses, but important gaps remained for over-parameterized neural networks. In particular, existing approaches often omit the optimization algorithm, require smooth activations or restrictive data assumptions, or lack generalization guarantees.

  • Earlier generalization bounds based on VC dimension scale linearly with the number of network parameters.
  • Rademacher-complexity bounds may become vacuous for over-parameterized networks because they depend on weight norms and ignore the optimization algorithm.
  • Existing SGD stability bounds for non-convex problems require smooth loss functions, unlike the non-smooth activations studied here.
  • Model-recovery studies make assumptions on the underlying model and input distribution, and do not analyze over-parameterized networks in this setting.
  • Related optimization analyses provide landscape guarantees under rank, Gaussian-data, or differentiable-activation assumptions, but do not provide the same combination of SGD convergence and generalization guarantees.

5 Convergence Analysis

For Leaky ReLU networks, the loss is non-convex but every critical point is a global minimum, and SGD is shown to reach such a minimum within a bounded number of non-zero updates. The resulting convergence bound is independent of network size, while the rate also admits a lower bound.

  • 5 Convergence Analysis: Every critical point of the Leaky ReLU loss is a global minimum, even though the loss is non-convex.
  • 5 Convergence Analysis: The convergence analysis assumes bounded initialization of the rows of W0 and counts non-zero SGD updates until reaching a critical point.
  • 5 Convergence Analysis: SGD converges to a global minimum after at most M_k non-zero updates.
  • 5 Convergence Analysis: The proof controls the norm growth and objective progress recursively, then uses Cauchy-Schwarz to bound the number of updates.
  • 5 Convergence Analysis: The upper bound contains a margin-dependent term and a term scaling inversely with η, and is independent of network size.
  • 5 Convergence Analysis: An initialized linearly separable sequence requires at least an Ω lower bound on SGD updates, showing the upper bound cannot be much improved.

6 Generalization

The generalization analysis combines the SGD update bound with compression arguments to show that, for Leaky ReLU networks, SGD reaches a global minimum with controlled test error independently of network size. Experiments on over-parameterized MNIST support this conclusion, despite the existence of other global minima that overfit.

  • 6 Generalization: The analysis combines the convergence theorem with a compression generalization bound for Leaky ReLU networks.
  • 6 Generalization: SGD's output can be represented using at most c_k selected training examples, yielding a compression scheme for the hypothesis class H_k.
  • 6 Generalization: With probability at least 1 − δ, SGD converges to a global minimum whose 0-1 test error is bounded when n ≥ 2c_k.
  • 6 Generalization: On MNIST digits 3 and 5, SGD reached a global minimum and generalized well with 10, 100, and 1000 hidden neurons, averaging 40 runs per setting.
  • 6 Generalization: For fixed ∥w*∥ and η, the sample-complexity guarantee is independent of network size, although sufficiently large networks contain global minima with arbitrarily high test error.
  • 6 Generalization: The η-bound holds for any η, but its worst-case analysis does not imply that large η is practically optimal.

7 ReLU- Success and Failure Cases

For ReLU networks, the loss can have spurious local minima, so SGD may fail to reach a global minimum. In the orthogonal-vector case, sufficiently small and sufficiently large networks exhibit different convergence behavior.

  • ReLU activation: ReLU loss contains arbitrarily bad local minima, unlike the global-minimum guarantee established for the analyzed Leaky ReLU setting.The construction yields a local minimum with training loss greater than 1.
  • Small networks: For sufficiently small networks, SGD converges to a local minimum with high probability under the specified orthogonal-vector setting.The convergence outcome depends on the initialization and the network width.
  • Large networks: For sufficiently large networks, SGD converges to a global minimum with probability at least 1 −δ.The theorem gives a width threshold involving log2(2d/δ) and an iteration bound involving d, C, η, and v.
  • Interpretation: The trained network can be interpreted only approximately as a linear classifier because of the grid’s limited resolution.This is an explicit qualification on the interpretation of the numerical analysis.
  • Small networks: The basin of attraction of the non-global minimum can be made exponentially large by setting δ = e^−αd for α ≤1.This strengthens the small-network failure result by allowing exponentially small failure probabilities.

8 Conclusion

The paper gives provable optimization and generalization guarantees for over-parameterized networks on linearly separable data with Leaky ReLU activations. It attributes good generalization to SGD compressing its output, while noting that the analysis does not extend to ReLU networks.

  • Conclusion: The paper provides the first stated provable generalization guarantees for over-parameterized networks in its linearly separable, Leaky ReLU setting.The guarantees concern both optimization and generalization performance.
  • Conclusion: SGD compresses its output when learning over-parameterized networks, and the paper links this behavior to good generalization performance.The conclusion presents output compression as the paper’s explanation for the observed generalization behavior.
  • Limitations and future work: The Leaky ReLU analysis does not apply to ReLU because the ReLU loss contains spurious local minima.The paper identifies convergence guarantees and generalization bounds for ReLU as future work.

A.1.1 Proof of Proposition 5.1

The proof analyzes SGD for a fixed two-layer over-parameterized network on linearly separable data. It establishes when initialization traps SGD at a non-global point and when sufficient width permits convergence to a global minimum.

  • Proof setup: If an example has margin yN_W(x) < 1, its loss gradient is nonzero; if yN_W(x) ≥ 1, the gradient vanishes.This separates updating examples from zero-gradient examples in the hinge-loss analysis.
  • Proposition 5.1: Every critical point is a global minimum, although the loss function is non-convex.A nonzero-loss critical point is ruled out because any violated margin would produce a nonzero gradient.
  • Generalization: The generalization argument uses a sample-size condition independent of network size to obtain a high-probability bound for the SGD output.The proof invokes an existing generalization theorem and requires independence between the training set and initialization.
  • Orthogonal-vector analysis: For the orthogonal-basis example, the set K_t of coordinates blocked by all neurons remains unchanged throughout SGD.This invariance is stated as Lemma 11 and underlies the characterization of failure and success.
  • Non-global convergence: When initialization leaves a coordinate blocked, SGD converges almost surely to a stationary point that is not a global minimum.The blocked coordinate keeps network output at most zero despite having positive label, leaving positive loss.
  • Global convergence: When no coordinate is initially blocked, SGD reaches zero loss after finitely many updates, with the bound scaling with d, C, and η.The proof bounds updates per basis vector and sums across all d coordinates.
Loading 1710.10174v1…