Norm-Based Capacity Control in Neural Networks

Behnam Neyshabur; Ryota Tomioka; Nathan Srebro

Source-linked AI summary

Norm-Based Capacity Control in Neural Networks

Behnam Neyshabur, Ryota Tomioka, Nathan Srebro

arXiv:1503.00036v2Feb 27, 2015cs.LGcs.AIcs.NEstat.ML

TL;DR

The paper asks how regularization affects the capacity and convexity of feed-forward neural networks. It develops group-norm analyses for ReLU networks and characterizes when capacity control is independent of size, while identifying depth-dependent and scope limitations.

Problem
The paper asks how explicit or implicit regularization changes feed-forward networks’ hypothesis classes and capacity, including whether norm control works without bounding network size.
Method
The paper analyzes ReLU networks using group norms that unify per-unit and overall weight regularization, studying capacity, convexity, and equivalent regularizers.
Results
The paper characterizes when norm regularization provides size-independent capacity control and shows that capacity can retain exponential depth dependence.
Takeaways & Limitations
The results provide a framework for analyzing and designing learning methods using feed-forward networks under broader norm regularization choices.
Takeaways & Limitations
The precise polynomial dependence of margin-based classification on the norm may not be tight and could likely be improved.

Abstract

from arXiv · show

We investigate the capacity, convexity and characterization of a general family of norm-constrained feed-forward networks.

1. Introduction

The paper asks how regularization changes the capacity of feed-forward networks, especially whether norm constraints can control capacity independently of network size. It studies norm-based regularizers, convexity, and the dependence of capacity on norms and depth.

Regularization can be explicit or implicit, including weight decay, early stopping, max regularization, and dropout.
The central question is whether norm-based regularization alone can bound capacity even when network size is unbounded or infinite.
The paper also asks how capacity varies with the norm and network depth.
Unlike size-controlled networks, infinite magnitude-controlled networks may yield convex hypothesis classes, which might be easier to optimize over.
The paper studies ReLU networks with per-unit and overall norm regularization, unified through group norms over within-unit weights and across units.
The work extends prior size-independent analyses beyond per-unit ℓ1 and two-layer per-unit ℓ2 regularization to broader regularizers, including overall norms.

2. Preliminaries: Feedforward Neural Networks

A feed-forward network is represented by a weighted directed acyclic graph whose nodes propagate inputs through an activation function to a scalar output. The preliminaries define network structure, ReLU properties, function classes, and norm-induced complexity measures.

A feed-forward network computing f: R^D → R is specified by a weighted DAG with input nodes, an output node, and an activation function.
Inputs initialize input-node outputs, internal nodes apply the activation to weighted incoming signals, and the output node sums weighted predecessor outputs.
Network size is the number of edges, depth is the longest directed-path length, and width is the maximum vertex in-degree.
Layered fully connected networks use matrix weights between successive layers, with hidden-layer width H and depth d.
The paper focuses on ReLU, σ_RELU(z)=max(z,0), whose non-negative homogeneity permits compensating weight rescaling without changing the computed function.
A weight-magnitude measure induces function complexity by taking the infimum over all weight settings that realize the function.

3. Group Norm Regularization

The paper introduces group-norm regularization and characterizes when it gives size-independent capacity control, when width dependence is unavoidable, and when the resulting hypothesis classes are convex.

3. Group Norm Regularization: Group regularization applies an ℓp norm within each unit and an ℓq norm across units.
3. Group Norm Regularization: q=∞ gives per-unit control, while q=p gives overall control; overall ℓ1 and ℓ2 correspond to sums of magnitudes and square magnitudes, respectively.
3. Group Norm Regularization: For ReLU networks, homogeneity allows layerwise norm balancing, making the two norm measures equivalent and giving identical hypothesis-class level sets.
3.1. Generalization and Capacity: The Rademacher-complexity bound loses its width dependence when q≤p*, including overall ℓ1, overall ℓ2, and per-unit ℓ1 regularization.
3.2. Tightness: When 1/p + 1/q < 1, width dependence is unavoidable, and the bound is tight even for binary classification with margin over binary inputs.
3.2. Tightness: For any p and q, controlling the group norm still permits sample complexity with exponential dependence on depth.
3.2. Tightness: When 1/p + 1/q < 1, sufficiently large width can drive the magnitude control arbitrarily low without reducing capacity, making the capacity infinite.
3.3. Convexity: The paper also establishes sufficient conditions for convexity of the magnitude-controlled hypothesis classes, contrasting with nonconvex optimization over network weights.

4. Per-Unit and Path Regularization

Per-unit regularization is equivalent to path regularization on layered networks, enabling capacity and convexity results but exposing limitations in depth, width, and feature sharing.

Regularizer definitions: Per-unit regularization constrains incoming weights separately, while path regularization aggregates products of weights along input-to-output paths.The path measure captures aggregated influence because weights entering nodes without strong outgoing paths have limited effect on the output.
Equivalence: Path and per-unit regularization are equivalent on layered graphs after appropriately balancing weights, but not generally on non-layered graphs with unequal path lengths.They become equivalent again when considering all directed acyclic graphs of depth at most d.
Capacity: For p = 1, per-unit regularization yields size-independent generalization bounds, whereas for p > 1 beyond two layers, width control is necessary.The lower bound rules out generalization guarantees without controlling network size for deeper networks.
Convexity: Unbounded-width per-unit regularization is convex for every p ≥ 1, but for depth greater than two this is meaningful only at p = 1 because the measure collapses for p > 1.Convexity concerns combinations of functions rather than combinations of weights.
Sharing: Optimal per-unit representations can be trees, so per-unit regularization does not incentivize sharing lower-level units across downstream features or tasks.Theorem 9 guarantees a representation whose internal non-input subgraph is a tree directed toward the output.

5. Overall Regularization

Overall norm regularization yields width-independent capacity control in important cases, but convexity and finite capacity impose depth- and norm-dependent restrictions.

Capacity: For p ≤ 2, overall ℓp regularization gives generalization guarantees independent of width, assuming bounded corresponding dual-norm inputs.This includes overall weight decay, corresponding to overall ℓ2 regularization.
Convexity: Convexity requires p ≥ d, leaving N^2_2,2 as the principal unconstrained-width convex class.For depth two, ℓ2 regularization yields convexity, whereas ℓ1 does not; for greater depth, the relevant overall regularizers degenerate to infinite-capacity classes.
Convexity: Overall ℓ2 regularization with two layers is equivalent to a convex neural net with ℓ2-constrained bottom units and ℓ1-regularized output weights.The output-layer penalty is ℓ1 rather than ℓ2.
Computational hardness: Convexity does not guarantee efficient learning: under stated hardness assumptions, unit-margin functions in the two-layer class cannot be efficiently PAC learned.The hardness results apply even to improper learning.

6. Depth Independent Regularization

The paper asks whether depth dependence can be removed from norm-based control and examines path- or γ-based measures as alternatives to group norms.

Motivation: Bounding only the group norm cannot remove depth dependence because arbitrarily deep networks can shrink it without changing the computed function’s scale.The resulting sample complexity necessarily increases exponentially with depth in terms of µp,q.
Depth-independent measures: The γ-measure, equivalently the path regularizer φ, remains a sensible complexity measure for arbitrarily deep graphs.The paper defines the measure by minimizing over DAGs and states φp(f) = γp,∞(f).
Anti-symmetric activations: For anti-symmetric 1-Lipschitz activations, the paper obtains a depth-independent Rademacher-complexity bound through an inductive argument.The theorem applies to activations such as the ramp.
ReLU limitation: For ReLU, the analogous inductive strategy cannot avoid exponential depth dependence, while the equivalence among µ, γ, and φ relies on homogeneity.The ramp is not homogeneous, so that equivalence breaks down there.

7. Summary and Open Issues

The paper characterizes when norm-based regularization controls feed-forward-network capacity without size constraints, while identifying depth dependence and unresolved expressive-power questions.

Summary: In depth d > 2 networks, per-unit control with p > 1 and overall regularization with p > 2 require network-size control for capacity control.This differs from linear models and two-layer networks, where broader norm regimes suffice.
Open issues: The precise polynomial dependence of margin-based classification on the norm may not be tight and could require analysis beyond real-valued Rademacher complexity.The authors specifically note that the bound is identical for per-unit and overall ℓ1 regularization despite expecting lower capacity for the latter.
Open issues: The expressive power of γ-based classes as a function of depth remains open, including whether increasing depth can reduce the γ-measure for some functions.The paper notes that depth two already contains all binary functions on {±1}^D and is dense among continuous real-valued functions.
Proof framework: The paper’s Rademacher-complexity proof proceeds inductively over depth, reducing later-layer matrix maximizations to independent vector maximizations and bounding the first layer separately.The argument uses contraction and bounded-ℓp linear-separator results.

A.4. Theorem 12

Theorem 12 extends the Rademacher-complexity analysis to anti-symmetric, 1-Lipschitz activations using a contraction argument without absolute values.

Theorem statement: The theorem applies to any anti-symmetric 1-Lipschitz activation function over a sample S ⊆ R^D.Anti-symmetry means σ(−z) = −σ(z).
Proof: Its proof uses a contraction lemma without the absolute value, exploiting the activation’s anti-symmetric property.Applying the same argument across layers and bounding the first layer completes the Rademacher-complexity proof.
Characterization: The resulting complexity measure p,q(f) is a semi-norm in N^d.

Appendix B. Proof that γd

The appendix proves that γd_p,q is a seminorm on N_d by establishing convex sublevel sets, non-negative homogeneity, and the triangular inequality.

Appendix B: γd_p,q is a seminorm on N_d.The proof combines convexity of its level sets, non-negative homogeneity, and a general implication from these properties to the triangular inequality.
Convexity of the level sets: Convexity is shown by constructing weights that realize αf1 + (1 − α)f2 while remaining in the same norm-bounded hypothesis class.The construction combines two networks whose regularizer values are bounded by γ and uses 0 ≤ α ≤ 1.
Non-negative homogeneity: Non-negative homogeneity follows by rescaling weights so the realized function is multiplied by α for α ≥ 0.The argument applies to rectified linear and other non-negative homogeneous activation functions.
Triangular inequality: A non-negative homogeneous functional with convex sublevel sets satisfies the triangular inequality and is therefore a seminorm.The proof rescales the two functions to a common level and invokes convexity of that level set.

C.1. Theorem 5

Theorem 5 addresses the norm characterization for networks with arbitrary width, including finite or infinite H. Its proof reduces networks to a normalized layered representation by rescaling weights without changing the represented function or increasing the regularizer.

Proof: The proof begins by selecting a network representation with γp,∞(w) = γd,H_p,∞(f) and constructs an equivalent layered representation.The construction normalizes input-weight norms while preserving the represented function.
Proof: An incremental rescaling algorithm equalizes the ℓp norms of incoming weights across neurons layer by layer.At each step, incoming weights are scaled down while outgoing edges are scaled up to preserve the same function.
Proof: The normalized network has γp,∞(ew) ≤ γp,∞(w), with equality because it realizes the same function and attains γd,H_p,∞(f).A final scaling of layer weights completes the proof.
Theorem 5: Theorem 5 applies for p ≥ 1, any depth d, and finite or infinite width H.The supplied theorem statement quantifies over any f ∈ N_d,H.

C.2. Proof of Theorem 6

The proof of Theorem 6 transforms arbitrary DAG networks into equivalent layered networks while preserving the computed function and the path-based quantity φ.

Assumption: The argument assumes internal DAG nodes have both incoming and outgoing edges, since otherwise they can be discarded.The depth-related quantities din and dout are defined under this assumption.
Graph characterization: A DAG is sublayered exactly when every input-to-output path has length d, the graph’s longest-path length.This condition permits placing each vertex in a layer determined by its distance from the inputs.
Graph characterization: If a DAG is not sublayered, it contains an edge (u → v) with din(u) + dout(v) < d − 1.This edge identifies where a new intermediate vertex can be inserted.
Graph transformation: The transformation inserts intermediate vertices on selected edges and assigns weights so rectified linear activations preserve the computed function.The inserted edge weight uses the absolute value of the original weight, relying on [x]+ = x for x > 0.
Graph transformation: After finitely many insertions, the resulting sublayered graph has the same function and φ value as the original graph.The path-length sum increases at each step, and reaching the bound implies a sublayered graph; zero-weight edges then make it layered.

Appendix D. Hardness of Learning Neural Networks

The appendix constructs bounded-norm neural networks that realize intersections of homogeneous halfspaces with unit margin, connecting norm-bounded representation to learning hardness.

Motivation: Prior hardness results for efficiently PAC learning intersections of homogeneous halfspaces motivate the bounded-norm realization.The cited hardness results rely on the strong random CSP assumption or intractability of a unique shortest vector problem.
Theorem 22: Intersections of k homogeneous halfspaces are realizable with unit margin by N^2 networks.This is stated for any k > 0.
Construction: The construction uses two first-layer units for each hyperplane ⟨wi, x⟩ > 0 and sets all incoming output-node weights to 1.The first-layer units use rectified linear functions shifted by 1.
Construction: For integer inputs and weights, the difference of the shifted rectified outputs is zero or one, yielding the intersection with unit margin.The construction then verifies that the resulting network satisfies the required norm bound.