PaperlayerView exact revision on arXiv

Source-linked AI summary

Size-Independent Sample Complexity of Neural Networks

Noah Golowich, Alexander Rakhlin, Ohad Shamir

arXiv:1712.06541v5cs.LGcs.NEstat.ML

TL;DR

The paper studies how to explain and bound the sample complexity of neural networks despite their large size. It develops norm-based Rademacher-complexity techniques that improve depth dependence and, under suitable constraints, yield bounds independent of network size. These guarantees rely on restrictive cross-layer norm assumptions, and lower bounds show that spectral-norm control alone is insufficient for size independence.

  • Problem

    The paper addresses the lack of neural-network generalization bounds that avoid strong dependence on depth and network size despite controlled parameter norms.

  • Method

    The paper develops modified contraction and network-approximation techniques for deriving Rademacher-complexity bounds under Frobenius, Schatten, and other layerwise norm constraints.

  • Results

    The bounds improve depth dependence and can be fully independent of network size under suitable norm constraints, while lower bounds show spectral-norm control alone cannot achieve size independence.

  • Takeaways & Limitations

    Norm-based assumptions can yield size-independent sample-complexity guarantees for standard neural networks, but the required cross-layer control is restrictive.

  • Takeaways & Limitations

    The size-independent bounds require products or ratios of norms across all layers to be bounded by a constant, which is quite restrictive in practice.

Abstract

from arXiv · show

We study the sample complexity of learning neural networks, by providing new bounds on their Rademacher complexity assuming norm constraints on the parameter matrix of each layer. Compared to previous work, these complexity bounds have improved dependence on the network depth, and under some additional assumptions, are fully independent of the network size (both depth and width). These results are derived using some novel techniques, which may be of independent interest.

1 Introduction

The paper asks whether norm-constrained neural networks can have sample-complexity bounds that avoid strong depth dependence and, under suitable assumptions, network-size dependence. It develops Rademacher-complexity techniques yielding improved depth dependence and fully size-independent bounds, while identifying restrictive assumptions and lower-bound barriers.

  • Motivation: Neural-network generalization remains difficult to explain because large models can generalize despite their capacity to overfit, suggesting an incompletely understood inductive bias.The bias may be explicit, through regularization, or implicit, through the training algorithm.
  • Problem: Existing norm-based bounds can avoid width dependence but retain strong, often exponential, depth dependence, motivating the question of whether norms alone can remove it.This issue persists even when various norms are controlled, while common activations such as ReLU do not satisfy the anti-symmetry assumption used by one prior approach.
  • Motivation: For generalized linear predictors, the sample complexity scales as O(MB/√m) independently of depth and the dimension of w1, providing the intuition for analogous neural-network bounds.Here M is a norm product and inputs are bounded by B.
  • Contributions: A modified contraction argument changes exponential depth dependence in Rademacher analysis to polynomial dependence for Frobenius- and ℓ1/ℓ∞-constrained networks.For the ℓ1/ℓ∞ setup, the resulting dependence on d is described as polynomial and mild, unlike the exponential dependence reported by Neyshabur et al. (2015).
  • Contributions: A generic approximation technique converts depth-dependent bounds into depth-independent bounds under control of Schatten norms, including Frobenius and trace norms.The technique approximates the network prediction by composing a shallow network with univariate Lipschitz functions.
  • Contributions: The paper presents a first explicit fully size-independent bound under suitable norm constraints, while lower bounds show spectral-norm control alone cannot guarantee size independence and norm products across layers are generally unavoidable.The lower bound extends earlier results to any Schatten p-norm and, for p > 2, rules out size-independent bounds under that control alone.
  • Limitations: The size-independent bounds require products or ratios of norms across all layers to remain bounded by a constant, an assumption the authors describe as quite restrictive in practice.The paper notes that even Frobenius norms of at least 2 per layer can make the bound scale as 2^d.

2 Preliminaries

The paper formalizes neural networks with Lipschitz activations and matrix-norm constraints, then uses Rademacher complexity to study their sample complexity and generalization.

  • Notation: Matrix norms are treated through Schatten p-norms: p = ∞ is spectral norm, p = 2 is Frobenius norm, and p = 1 is trace norm.The paper also uses ∥W∥F as notation for the Frobenius norm.
  • Neural Networks: Neural networks are defined over inputs with Euclidean norm at most B, using parameter matrices W_j and fixed Lipschitz activations.The network depth is d, and its width h is the largest row or column dimension among the parameter matrices.
  • Neural Networks: The activations are assumed to have Lipschitz constant at most 1 and satisfy σ_j(0) = 0, with constants absorbable into neighboring norm constraints.Element-wise activations apply the same univariate function to each coordinate.
  • Neural Networks: Subnetworks are represented by layer ranges, with N_b^r denoting the function computed by layers b through r.The tuple of matrices from W_b through W_r is denoted by W_b^r.
  • Rademacher Complexity: Rademacher complexity measures uniform convergence for predictor classes and can be converted into generalization-error bounds from m i.i.d. training examples.The paper’s bounds may be independent of the sample inputs when their norms are bounded by B.

3 From Exponential to Polynomial Depth Dependence

The paper replaces exponential depth dependence in Rademacher-complexity bounds with polynomial dependence by applying contraction inside a transformed complexity expression. It develops norm-specific results under Frobenius and ℓ1/ℓ∞ constraints, while noting conditions needed for the technique.

  • Motivation: Standard peeling can produce a 2^d dependence on depth, even when every layer has Frobenius norm at most 1.The exponential factor arises from applying the Rademacher contraction principle at each layer.
  • Technique: The method applies Jensen’s inequality and exponential transformations so peeling factors accumulate inside a logarithm, yielding polynomial rather than exponential depth dependence.The resulting dependence includes log(2^d) = d before tuning the free parameter λ.
  • Frobenius Norm: The Frobenius-norm analysis relies on a lemma for element-wise, positive-homogeneous, 1-Lipschitz activations such as ReLU, allowing peeling inside the exponential function.The lemma applies to convex, monotonically increasing functions g and vector-valued function classes.
  • Frobenius Norm: For Frobenius-bounded networks, Theorem 1 gives a Rademacher-complexity bound whose depth factor replaces the earlier 2^d dependence.The theorem concerns real-valued depth-d networks over the bounded domain X, with layer norms bounded by M_F(j).
  • Scope: The real-valued presentation extends to vector-valued networks composed with real-valued Lipschitz losses, using a variant of the peeling lemma.The paper omits the precise proof details for this extension.
  • ℓ1/ℓ∞ Constraints: The same strategy extends to ℓ1/ℓ∞ constraints, where each row’s 1-norm is bounded and the resulting theorem gives a corresponding depth-dependent bound.This setting uses the maximal 1-norm of the rows of each parameter matrix and element-wise 1-Lipschitz activations.
  • Limitations: The exponential-transform construction has a limitation: improving g^{-1} beyond logarithmic growth requires controlling an expectation that becomes difficult when g grows faster than exponentially.The paper therefore introduces a different idea for eliminating depth dependence under additional assumptions.

4 From Depth Dependence to Depth Independence

The paper converts depth-dependent Rademacher-complexity bounds into depth-independent bounds by exploiting near-rank-1 layers and their representation as shallow networks composed with univariate Lipschitz functions. Under suitable norm constraints, the resulting sample-complexity bounds can be independent of both network depth and width, although the required assumptions are restrictive.

  • General technique: Schatten-norm control yields a general conversion from depth-dependent to depth-independent Rademacher-complexity bounds.The technique applies for any finite Schatten p-norm when the relevant norms are sufficiently controlled.
  • General technique: Bounded products of Frobenius norms can force layers close to rank-1, enabling approximation by a shallow network followed by a univariate Lipschitz function.This extends the intuition from diagonal linear networks to general activations and parameter matrices.
  • General technique: Theorem 4 bounds the complexity of composing a function class with univariate Lipschitz functions using the complexity of the original class.Its bound includes a logarithmic sample-size factor multiplying the Rademacher complexity of the base class.
  • General technique: The resulting bound depends on a chosen truncation depth r rather than the original depth d, allowing r to be tuned to remove explicit depth dependence.The construction first introduces a rank-1 layer among the first r layers, then applies the composition bound.
  • Applications: Under bounded norm products or ratios across all layers, the upper bound becomes independent of network width and depth while retaining the asymptotic sample-size rate.For Frobenius constraints, the paper states a size-independent bound up to logarithmic factors and compares it with the original depth-dependent bound.

5 A Lower Bound for Schatten Norms

The paper establishes lower bounds for networks whose layer matrices have bounded Schatten norms, showing when size-independent complexity is impossible and when Frobenius control can achieve it.

  • Lower bound: Theorem 7 gives a lower bound for depth-d, width-h networks with each parameter matrix bounded in a Schatten p-norm.The result is stated for p including the spectral norm via the convention p = ∞.
  • Comparison: The lower-bound construction strengthens an earlier result by adding width dependence, while requiring a non-element-wise activation for depths larger than one.The comparison also differs in whether the bound holds for arbitrary versus uniformly chosen data points.
  • Implications: Controlling only layerwise norms generally leaves an unavoidable dependence on the product of the norms.This matches the corresponding implication noted in prior lower-bound work.
  • Implications: For p = ∞, the lower bound contains an inevitable h^1/2 factor, so spectral-norm control cannot provide width-independent bounds.More generally, Schatten p-norm control with p > 2 is insufficient for size independence.
  • Implications: For p = 2, corresponding to Frobenius norms, the lower bound becomes independent of network size.Its dependence on the layer norm bounds is similar to the paper’s upper bound up to logarithmic factors, although its sample-size dependence is worse.

6 Additional Remarks

Additional remarks extend the analysis to post-hoc guarantees and Lipschitz-function classes, revealing a depth-independent alternative whose cost is strong dependence on input dimension.

  • Post-hoc guarantees: Rademacher-complexity bounds for fixed norm-constrained classes can be converted into probabilistic guarantees for unconstrained training algorithms.The conversion applies to a learned predictor even when the algorithm does not enforce a fixed norm class in advance.
  • Lipschitz networks: A network with spectral-norm bounds is Lipschitz with constant equal to the product of its layer spectral-norm bounds.This permits complexity analysis through the class of Lipschitz functions over the input domain.
  • Lipschitz networks: The Lipschitz-function bound is independent of network depth and all matrix norms except the spectral norm, but depends poorly on input dimension.Input dimension is equivalent here to the width of the first layer.

7 Proofs

The proofs develop technical lemmas for Lipschitz compositions, rank-1 matrix replacements, and layerwise norm relations, then combine them to establish the main complexity bounds.

  • Technical lemmas: The proof framework bounds Rademacher complexity through contraction arguments and exponential-moment estimates.The derivations repeatedly apply symmetry, Lemma 2, and Ledoux–Talagrand-style contraction reasoning.
  • Rank-1 approximation: A matrix can be replaced by a rank-1 approximation formed from its top singular value and singular vectors while controlling the resulting norm changes.The singular-value decomposition supplies the replacement matrix.
  • Main theorem: Replacing one layer by a rank-1 matrix preserves the network’s layer dimensions and permits the decomposition used in the depth-independent bound.The proof also treats the small-r regime by using an all-zeros replacement when needed.
  • Main theorem: The remaining proof cases use elementary exponential bounds and Lipschitz-constant calculations to complete the theorem statements.The cases are simplified separately after taking appropriate roots or applying the layerwise Lipschitz estimates.

7.3 Proof of Thm. 4

The proof bounds the covering numbers of a Lipschitz function class through discretization and composition, then converts these entropy bounds into Rademacher-complexity bounds using Gaussian complexity and Dudley’s integral.

  • Reduction and setup: The proof begins with covering-number definitions and reduces the target class FL,a ◦H to F1,0 ◦H.The reduction uses the equivalence FL,a ◦H = {Lg(·) + a : g ∈ F1,0 ◦H}.
  • Complexity conversion: Sudakov’s minoration and the equivalence of empirical Gaussian and Rademacher complexities control the entropy contribution up to a c log(m) factor.The proof then applies Dudley’s entropy integral to obtain the stated upper bound.
  • Discretization: Discretizing [−R, R] into grids Ux and Uy yields piecewise-linear approximations f ′ with sup-norm error at most ǫ.Neighboring inputs map to neighboring or identical output-grid points, enabling finite parameterization of the approximating functions.
  • Composition covers: At scale ǫ, compositions f ◦h are covered by composing ǫ/2-cover elements f ′ and h′.The triangle-inequality argument bounds the empirical distance through separate approximation errors for f and h.
  • Complexity conversion: The resulting upper bound includes an m term and a log(m) · ˆGm(H) term before the final conversion to Rademacher complexity.The displayed fragments identify the final complexity expression and its dependence on sample size and Gaussian complexity.

7.4 Proof of Thm. 5

The proof controls the complexity of deep network losses by replacing a selected layer with a rank-1 parameter matrix, decomposing the resulting class into bounded Lipschitz components, and applying a union-complexity lemma.

  • Union bound: Lemma 7 bounds the Rademacher complexity of a union of uniformly A-bounded function classes using a logarithmic factor and the complexity of each class.Its proof applies bounded differences to the Rademacher supremum and then a union bound.
  • Rank-1 reduction: For any fixed r, the proof constructs ˜H by replacing one parameter matrix in each network with a rank-1 matrix.The selected layer r′ lies among the first r layers.
  • Rank-1 reduction: The crucial decomposition expresses each modified network as a composition involving a function in Hr′ and a univariate function with Lipschitz constant at most 1.The rank-1 factor is shown to satisfy the relevant norm constraints, while subsequent layers map input 0 to a fixed output a.
  • Union bound: Functions in Hr′ have outputs bounded by ±B Qr′, supplying the boundedness condition required by Lemma 7.This bound is used when applying the union-complexity estimate to the decomposed class.
  • Final bound: The resulting loss-complexity bound contains log3/2(m) · ˆRm(Hr′) and is valid for every fixed r, after which the proof uses the assumption on |a|.The displayed bound is obtained by substituting the union estimate into the preceding inequality and simplifying.

7.5 Proof of Lemma 3

The lemma proves that, for the stated parameters, some index r among the first d layers satisfies the required inequality by case analysis.

  • Existence argument: The proof establishes existence of an r ∈ {1, . . . , d} for any α, β, b, c, n satisfying the lemma’s conditions.It proceeds by analyzing the relevant cases.

7.6 Proof of Corollary 1

The corollary follows by applying the main theorem with p = 2 and matrix spaces chosen for each layer, then combining the resulting bounds through minimization over r.

  • Application of prior bounds: Applying Theorem 1 and the 1/γ-Lipschitz property of the loss yields the initial complexity bound used for the corollary.The proof then substitutes Eq. (12) into Theorem 5.
  • Parameter choices: The substitution uses p = 2, takes each Wj to be the space of all matrices, and sets M(j) = MF(j).The proof also invokes the corresponding norm constraint on Wj.
  • Simplification: The O term from Theorem 5 is absorbed into the O term minimized over r in Eq. (22).This simplifies the resulting expression before combining the alternative bounds.
  • Final bound: The final bound is obtained by upper bounding the loss complexity with the minimum of Eq. (21) and Eq. (22).The proof explicitly combines the two displayed alternatives.

7.7 Proof of Corollary 2

The proof bounds the Rademacher complexity of composed neural-network classes using Theorems 5–6 and Lemma 3, then establishes matching lower bounds through restricted network subclasses. It also considers an alternative lower-bound construction that is better when p < 2.

  • Upper bounds: Theorem 6 is applied to bound the Rademacher complexity of H_r, using that W_r is a vector when r ≥ 1.The proof identifies the relevant matrix norm with the Euclidean norm of W_r.
  • Upper bounds: Theorem 5 and a direct application of Theorem 6 provide two upper bounds for the composed class ℓ◦H.The proof combines these bounds and applies Lemma 3, absorbing the O term from Theorem 5 into the minimization term.
  • Upper bounds: The resulting bound uses c = ¯log^3/2(m), n = √(1/p)m, and a quantity b involving the product of layer norms and Γ.The proof explicitly defines these auxiliary quantities before applying Lemma 3.
  • Lower bounds: A lower bound is obtained by restricting to diagonal first-layer weights, max pooling σ(z) = max_j z_j, and basis-vector inputs x_i = B e_(i mod h).The construction groups examples by their coordinate index through the sets A_k.
  • Lower bounds: An alternative real-valued construction over R yields a lower bound that is better when p < 2.This construction uses a scalar input class with x_i = B for every i.
  • Conclusion: Taking the better of this lower bound and the lower bound from Eq. (23) completes the result.
Loading 1712.06541v5…