PaperlayerView exact revision on arXiv

Source-linked AI summary

Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks

Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang

arXiv:1901.08584v2cs.LGcs.NEstat.ML

TL;DR

The paper asks how overparameterized networks can fit arbitrary labels while differing in training speed and generalization. It analyzes randomly initialized gradient descent for two-layer ReLU networks through a related kernel, obtaining label-sensitive convergence, a width-independent data-dependent generalization bound, and broad function learnability.

  • Problem

    The paper investigates why true labels train faster and generalize differently from random labels, and whether a verifiable complexity measure can distinguish them.

  • Method

    The paper analyzes gradient-descent dynamics and generalization for randomly initialized overparameterized two-layer ReLU networks using properties of a related kernel.

  • Results

    The analysis characterizes label-dependent convergence, gives a data-dependent generalization bound independent of network width, and establishes learnability for a broad class of functions.

  • Takeaways & Limitations

    Training dynamics and generalization can be analyzed through a related kernel without assuming a ground-truth model, while covering broad learnable function classes.

  • Takeaways & Limitations

    The results require sufficiently large network width and a non-degeneracy assumption for optimization to achieve zero training loss.

Abstract

from arXiv · show

Recent works have cast some light on the mystery of why deep nets fit any data and generalize despite being very overparametrized. This paper analyzes training and generalization for a simple 2-layer ReLU net with random initialization, and provides the following improvements over recent works: (i) Using a tighter characterization of training speed than recent papers, an explanation for why training a neural net with random labels leads to slower training, as originally observed in [Zhang et al. ICLR'17]. (ii) Generalization bound independent of network size, using a data-dependent complexity measure. Our measure distinguishes clearly between random labels and true labels on MNIST and CIFAR, as shown by experiments. Moreover, recent papers require sample complexity to increase (slowly) with the size, while our sample complexity is completely independent of the network size. (iii) Learnability of a broad class of smooth functions by 2-layer ReLU nets trained via gradient descent. The key idea is to track dynamics of training and generalization via properties of a related kernel.

1 Introduction

The paper addresses why overparameterized networks fit both true and random labels yet train at different speeds and generalize differently. It analyzes optimization, generalization, and learnability for overparameterized two-layer ReLU networks trained by gradient descent.

  • Randomly labeled and properly labeled data can both achieve zero training error, but only properly labeled data generalizes.
  • True labels converge faster than random labels because training speed depends on their projections onto Gram-matrix eigenvectors.These projections differ significantly on MNIST and CIFAR.
  • The proposed generalization bound uses a data-dependent complexity measure that is independent of hidden-layer width.The measure distinguishes true and random labels on MNIST and CIFAR.
  • The bound applies to any labels, can be efficiently computed from the data, and upper-bounds test error when gradient descent achieves zero training error.
  • Gradient descent can learn a broad class of smooth functions with two-layer ReLU networks, including linear functions and networks using polynomial or cosine activations.The required smoothness is weaker than in Allen-Zhu et al. (2018a).

2 Related Work

Prior work explained low training error and some generalization in overparameterized networks, but left label-dependent convergence and data-dependent generalization unresolved. This paper relates its analysis to trajectory methods and kernel methods while addressing those gaps.

  • Earlier trajectory analyses established global convergence but often required much greater overparameterization than the experiments of Zhang et al. (2017).
  • Classical VC-dimension, Rademacher, norm-based, and compression-based bounds were considered too weak for explaining generalization in modern overparameterized networks.
  • The paper's generalization bound depends only on training data, can be computed without training the network, and does not assume a true underlying model.
  • The analysis uses properties of a kernel associated with the ReLU activation, connecting it to recent work on neural-network kernel methods.

3 Preliminaries and Overview of Results

The paper studies randomly initialized gradient descent on a two-layer ReLU network and develops a kernel-based overview of convergence and generalization. Its results characterize label-dependent optimization, width-independent generalization, and learnability of broad function classes.

  • 3.1 Setting: The model is a two-layer ReLU network with m hidden neurons, first-layer weights W, and second-layer weights a.
  • 3.1 Setting: Training uses randomly initialized gradient descent on quadratic loss while fixing the second-layer weights and optimizing the first-layer weights.
  • 3.2 Kernel: The matrix H∞ is a Gram matrix associated with the ReLU kernel and is central to both the optimization and generalization analyses.Positive definiteness of H∞ supports convergence to zero training loss when the network is sufficiently wide.
  • 3.3 Overview of Our Results: The convergence trajectory is essentially a power method involving I −ηH∞ applied to the label vector y.
  • 3.3 Overview of Our Results: Convergence rates are determined by label projections onto the eigenvectors of H∞, distinguishing different labels and answering Question 1.
  • 3.3 Overview of Our Results: The generalization bound applies to any 1-Lipschitz loss, is computable from the data, and is independent of network width.
  • 3.3 Overview of Our Results: The network trained by gradient descent can learn a broad class of functions, including linear functions and polynomial- or cosine-activation networks.

4 Analysis of Convergence Rate

The analysis refines convergence estimates by decomposing label error across the eigenvectors of the Gram matrix H∞. Convergence is faster when labels align with top eigenvectors, explaining why true labels train faster than random or worst-case labels.

  • Theorem 3.1’s linear-convergence bound cannot distinguish label types, motivating a fine-grained convergence-rate analysis.
  • With small initialization and large width, the network dynamics are approximated by a linear update involving the Gram matrix H∞.The update is ˜u(k + 1) = ˜u(k) −ηH∞(˜u(k) −y).
  • Label error decomposes into projections onto H∞ eigenvectors, with the component associated with eigenvalue λ_i shrinking at ratio (1 −ηλ_i)^2.
  • Labels aligned with top eigenvectors converge quickly, whereas uniform projections or alignment with small-eigenvalue directions produce slower convergence.
  • On MNIST and CIFAR, true labels align better with top eigenvectors than random labels, while least-eigenvalue labels exhibit extremely slow convergence.The experiments compare true, random, and worst-case labels using eigenvalue projections and gradient-descent convergence rates.

5 Analysis of Generalization

The analysis bounds generalization for overparameterized two-layer ReLU networks trained by gradient descent using a data-dependent complexity measure and controlled parameter movement. Under non-degeneracy and probabilistic assumptions, the resulting bound is independent of network width and distinguishes true from random labels experimentally.

  • Generalization bound: Theorem 5.1 provides a high-probability generalization bound for gradient-descent solutions under a non-degeneracy assumption on the data distribution.The theorem applies to 1-Lipschitz losses bounded in [0,1] that vanish on matching predictions and labels.
  • Complexity measure: The bound’s dominant term is a data-dependent complexity measure that can be computed without training a network or assuming a ground-truth model.The measure is based on the labels and the limiting Gram matrix, with the cited result giving the term y^T(H∞)^-1y/(2n), up to negligible errors.
  • Complexity measure: The sample-complexity guarantee is completely independent of the network width m.This is stated as a specific advantage of the proposed complexity measure and bound.
  • Empirical evaluation: On two-class MNIST and CIFAR experiments, the complexity measure increases with the random-label fraction and nearly follows the generalization-error trend.The figure compares ℓ1 loss and classification error with the measure after training to convergence; ℓ1 loss upper-bounds classification error.
  • Proof strategy: The proof controls the trajectory of gradient descent by bounding the total Frobenius-norm movement of all neurons from initialization.This total-movement bound is identified as the paper’s main contribution beyond prior bounds on individual neuron movement.
  • Proof strategy: The learned network lies in a restricted near-initialization function class whose Rademacher complexity yields the generalization bound.The argument first bounds parameter movement, then bounds the Rademacher complexity of the resulting function class.

6 Provable Learning using Two-Layer ReLU Neural Networks

The section proves that gradient descent on sufficiently wide two-layer ReLU networks can learn a broad class of functions, including linear, polynomial-activation, cosine, and less-smooth examples. The result follows from combining optimization and generalization analyses under a bounded complexity condition.

  • Provable learning: A broad class of functions is provably learnable by two-layer ReLU networks trained with gradient descent.The class includes linear functions, polynomial-activation networks, and cosine activation.
  • Closure property: The learnable-function result is closed under addition: sums of learnable functions are also learnable.This follows directly from the theorem’s treatment of label vectors and yields a corollary.
  • General learnability: Functions of the form (12) are learnable when the associated quantity M_g is bounded independently of the sample size n.This condition lets the generalization theorem apply to the underlying function class.
  • Examples: Linear functions and quadratic functions satisfy the required condition, with the quadratic case characterized by the nuclear norm O(∥A∥∗).The quadratic example corresponds to a two-layer neural network with quadratic activation.
  • Examples: Cosine-activation functions are included among the learnable examples through their Taylor-series representation.The paper considers g(x) = cos(β⊤x) − 1.
  • Smoothness scope: The smoothness requirement is weaker than the requirement in Allen-Zhu et al. (2018a), and a not-so-smooth arctan-based function is still learnable.The comparison states that the earlier theorem’s required boundedness condition is not satisfied for this example.

7 Conclusion

The paper presents a fine-grained analysis of optimization trajectories and generalization for overparameterized two-layer ReLU networks trained by gradient descent. It suggests that the approach may also help analyze overparameterized deep networks and other machine-learning models.

  • Conclusion: The paper analyzes optimization trajectories and generalization ability in overparameterized two-layer ReLU networks trained by gradient descent.The conclusion frames this as the paper’s central analytical contribution.
  • Conclusion: The approach may also be useful for analyzing overparameterized deep neural networks and other machine-learning models.This is stated as a potential extension rather than an established result.

A Experiment Setup

The experiments use fixed-width, full-batch gradient descent on two binary image datasets, with true and randomly modified labels evaluated through training and generalization quantities. The setup fixes the architecture and optimization hyperparameters across experiments.

  • Training setup: m = 10,000 hidden neurons are used in every experiment.The network has a fixed second layer, while only the first layer is optimized.
  • Training setup: η = 10^-3 is the fixed learning rate for full-batch gradient descent.The initialization scaling factor is fixed at κ = 10^-2.
  • Datasets: The experiments use CIFAR and MNIST binary classification data with 10,000 training images and 2,000 validation images per dataset.Only the first two image classes are used, with labels +1 and −1.
  • Label conditions: Random-label experiments uniformly replace selected training and test labels with independent values from {−1, 1}.This creates the random-label condition used in Figure 2.
  • Evaluation: Generalization error is defined as the population-loss minus empirical-loss gap, LD(f) − LS(f).The empirical loss is computed on n sampled examples, while population loss is taken over the data distribution.
  • Evaluation: Bounding the Rademacher complexity of a function class containing the learned predictor yields a generalization bound.The cited theorem assumes bounded and Lipschitz loss conditions.

C Proofs for Section 4

The proof controls gradient-descent dynamics by showing that weights and associated matrices remain close to initialization and to the limiting kernel when the network is sufficiently wide. These stability bounds support the training analysis under random initialization.

  • Proof structure: The proof begins with technical lemmas, many of which were previously established by Du et al. (2018c).The paper includes proofs for completeness.
  • Weight stability: Each weight vector remains within a bounded distance R of its initialization throughout optimization with high probability.This bound is used to control changes in activation patterns and kernel-related matrices.
  • Matrix stability: The matrices H(k) and Z(k) remain close to their initial values when the hidden-layer width m is sufficiently large.Lemma C.1 provides the norm bounds used for this conclusion.
  • Kernel concentration: The initialization kernel H(0) is shown to be close to the limiting kernel H∞ with high probability.The argument uses concentration of averages of independent bounded random variables and a union bound.
  • Activation control: The proof partitions neurons according to activation behavior and treats neurons whose activation patterns change as a perturbation.Neurons in S_i do not change activation patterns on data point x_i during optimization.
  • Recursive control: The recursion is controlled using the contraction of I − ηH∞ and bounds on initialization and perturbation terms.The proof uses ∥H∞∥2 ≤ tr[H∞] = n to establish the relevant spectral bound.

D.1 Proof of Lemma 5.3

The proof of Lemma 5.3 decomposes the iterate into a main kernel-driven term and perturbation terms, then combines bounds under high-probability events. It also controls parameter movement and the resulting Rademacher complexity.

  • High-probability control: The argument assumes the relevant high-probability events and uses a union bound to obtain an overall success probability of at least 1−δ.The proof notes that the intermediate failure probabilities can be rescaled to achieve this final bound.
  • Iterate decomposition: The update rule for W is combined with bounds from Theorem 4.1 and Lemma C.2 to analyze the iterates through a summed recurrence.The second and third terms are treated as perturbations, while the first term is analyzed using the spectral structure of H∞.
  • Spectral analysis: Because T is a polynomial of H∞, it shares H∞’s eigenvectors, enabling the proof to bound the principal kernel-dependent term spectrally.The resulting estimate is substituted into the preceding decomposition together with the other three bounds.
  • Parameter control: The proof separately bounds neuron-wise and Frobenius parameter movement within prescribed radii before completing the lemma.The movement quantity is defined by the maximum change of an individual neuron from initialization.
  • Complexity bound: Hoeffding’s inequality controls initialization-dependent activation counts, yielding a high-probability bound on the Rademacher complexity.The argument uses independence of neurons at initialization and combines two probability bounds to obtain an overall probability of at least 1−δ.

D.3 Proof of Theorem 5.1

Theorem 5.1 combines optimization, parameter-movement, and Rademacher-complexity controls under non-degeneracy and random initialization. These ingredients yield simultaneous training and generalization-related bounds, with the ramp-loss corollary following from its Lipschitz and loss-dominance properties.

  • Theorem 5.1: Non-degeneracy gives λmin(H∞) ≥λ0 with probability at least 1−δ/3, after which the proof conditions on this event.The remaining probability controls concern the sample and random initialization.
  • Theorem 5.1: Theorem 3.1 supplies optimization success and an upper bound on the training error LS(fW(k),a).This is one of three properties established simultaneously in the theorem’s proof.
  • Theorem 5.1: The iterates remain within neuron-wise radius R and Frobenius radius B around initialization.The proof records these movement bounds as the second simultaneous property.
  • Theorem 5.1: The function classes indexed by increasing bounds Bi have simultaneous Rademacher-complexity bounds, and the smallest Bi covering B determines the relevant index i∗.The proof combines this complexity control with the optimization and movement properties.
  • Corollary 5.2: The ramp loss is 1-Lipschitz for y∈{±1}, vanishes on correct unit-margin predictions, and upper-bounds the 0-1 loss.These properties support the corollary derived from Theorem 5.1.

E Proofs for Section 6

The proofs for Section 6 establish matrix inequalities for positive semidefinite order and develop polynomial-kernel representations using tensor and Khatri–Rao products. These tools are then applied to the theorem’s cases, including p=1 and p=2l.

  • Matrix inequality: Lemma E.1 states that for B⪰A⪰0, A†⪰PAB†PA, with the invertible special case reducing to A−1⪰B−1.The proof analyzes the generalized determinant equation and bounds its solutions between 0 and 1.
  • Polynomial-kernel tools: The proof defines tensor products, Khatri–Rao products, and Hadamard products to represent polynomial kernel matrices.For K=X⊤X, the entries of K◦l are powers of the corresponding inner products.
  • Theorem 6.1: The proof separately completes the case p=2l after establishing the polynomial-kernel and matrix-inequality tools.The cited passage marks the end of that case without giving its intermediate calculations.
  • Theorem 6.1: For p=1, the labels are represented as y=αX⊤β1, and the relation H∞⪰K is combined with Lemma E.1.The projection identity PKX⊤=X⊤ is then used to complete this case.
  • Notation: The proof introduces the Moore–Penrose pseudoinverse as A† and uses projection matrices associated with the span of a positive semidefinite matrix.These definitions organize the comparison between A and B in Lemma E.1.
Loading 1901.08584v2…