Source-linked AI summary
Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
Peter L. Bartlett, Nick Harvey, Chris Liaw, Abbas Mehrabian
TL;DR
The paper addresses the previously unknown tight dependence of VC-dimension on depth and network size for piecewise linear neural networks. It proves matching-up-to-a-log-factor upper and lower bounds, including a tight parameter-unit bound, and extends the results to pseudodimension. The bit-extraction approach itself has a barrier preventing stronger lower bounds than the stated Ω(WL log(W/L)) rate.
Problem
The tight characterization of how depth affects VC-dimension was unknown, despite depth influencing the complexity of networks with the same number of weights.
Method
The paper proves upper and lower VC-dimension bounds for piecewise linear networks and uses a piecewise-polynomial upper-bound framework together with a refined bit-extraction construction.
Results
For piecewise linear networks, the VC-dimension satisfies c · WL log(W/L) ≤ d(W, L) ≤ C · WL log W, while the upper bound is O(WU log((d + 1)p)) in the piecewise-polynomial setting.
Takeaways & Limitations
The bounds are asymptotically tight across almost the entire parameter range and automatically apply to neural-network pseudodimensions.
Takeaways & Limitations
The bit-extraction approach cannot produce a lower bound better than Ω(WL log(W/L)).
Abstract
from arXiv · showhide
We prove new upper and lower bounds on the VC-dimension of deep neural networks with the ReLU activation function. These bounds are tight for almost the entire range of parameters. Letting $W$ be the number of weights and $L$ be the number of layers, we prove that the VC-dimension is $O(W L \log(W))$, and provide examples with VC-dimension $Ω( W L \log(W/L) )$. This improves both the previously known upper bounds and lower bounds. In terms of the number $U$ of non-linear units, we prove a tight bound $Θ(W U)$ on the VC-dimension. All of these bounds generalize to arbitrary piecewise linear activation functions, and also hold for the pseudodimensions of these function classes. Combined with previous results, this gives an intriguing range of dependencies of the VC-dimension on depth for networks with different non-linearities: there is no dependence for piecewise-constant, linear dependence for piecewise-linear, and no more than quadratic dependence for general piecewise-polynomial.
1. Introduction
The paper studies how network parameters, units, and depth affect VC-dimension, proving nearly tight bounds for piecewise linear networks and extending them to pseudodimension. Its results sharpen prior bounds and clarify depth dependence across activation classes.
- Motivation: VC-dimension characterizes uniform convergence of misclassification frequencies and asymptotically determines PAC sample complexity for classifiers.
- Contribution: The paper proves nearly-tight VC-dimension bounds for deep networks using piecewise linear activations with a constant number of pieces, including ReLU networks.ReLU is the commonly used activation σ(x) = max{0, x}, which is piecewise linear.
- Proof limitation: The bit-extraction technique cannot yield a lower bound better than Ω(WL log(W/L)) because approximating the mod function requires m = O(L log(W/L)).This barrier follows from Theorem 5 and concerns this lower-bound approach.
- Comparison with prior work: The upper bound improves prior piecewise-polynomial bounds to O(WL log W) for piecewise linear activations, while the lower bound improves prior Ω(WL) and Ω(W log W) results to Ω(WL log(W/L)).
- Bounds by parameters and depth: c · WL log(W/L) ≤ d(W, L) ≤ C · WL log W for piecewise linear networks with W parameters and L layers.When L is significantly smaller than W^0.99, these results give d(W, L) = Θ(WL log W); when L = Θ(W), they give Θ(WL).
- Bounds by units: VC-dimension is O(WU log((d + 1)p)) for networks with W parameters, U units, and piecewise-polynomial activations of degree at most d with at most p pieces.For piecewise linear activations with d = 1 and p = 2, the corresponding W-and-U bound is tight.
2. Proof of Theorem 3
The proof strengthens VC-dimension lower bounds by extracting multiple bits per block in a ReLU network, yielding Ω(WL log(W/L)) while also establishing tight Ω(WU) scaling in the unit-based regime.
- Bit extraction: The key refinement partitions bit extraction into blocks and extracts r bits at a time rather than one bit at a time.This produces a more efficient bit-extraction network and supplies the additional logarithmic factor in the lower bound.
- Main construction: Ω(mn) VC-dimension is achieved by a ReLU network with explicitly bounded layers, parameters, inputs, and computational units.Theorem 9 gives 3 + 5k layers, 2 + n + 4m + k((11 + r)2^r + 2^r + 2) parameters, and m + 2 + k(5 × 2^r + r + 1) computational nodes, where k = ⌈m/r⌉.
- Main construction: Ω(WU) is tight for networks with W = O(m + n) parameters and U = O(m) nonlinear units.Choosing r = 1 in Theorem 9 yields VC-dimension Ω(mn) = Ω(WU), matching the upper bound O(WU).
- Encoding and shattering: The construction encodes an arbitrary Boolean function on S_n × S_m into binary digits of n parameter values and extracts the requested bit.For input (x1, x2) = (e_i, e_j), the network outputs the i-th bit of a_j, which equals the encoded function value.
- Technique limitation: The bit-extraction approach cannot improve the lower bound beyond Ω(WL log(W/L)).Theorem 5 imposes a bound on the number of extractable bits, creating an inherent barrier for this proof technique.
- Bit extraction: A five-layer ReLU block extracts the r most significant bits of a binary number and returns the remaining suffix.The block uses 5 × 2^r + r + 1 units and 11 × 2^r + r2^r + 2^r + 2 parameters.
3. Proof of Theorem 5
The proof bounds how many oscillations a piecewise polynomial network can represent by tracking breakpoint growth through layers. This yields the key depth-dependent restriction m = O(L log(W/L)) for piecewise linear networks.
- Breakpoint growth: A composition lemma shows that applying a piecewise polynomial activation to a weighted sum of piecewise polynomials multiplies degree and bounds breakpoint growth.With degree D, B input breakpoints, and activation parameters d and b, the resulting function has degree Dd and at most (B + 1)(2 + bD) −1 breakpoints.
- Depth-dependent bound: m ≤ L log_2(13pd(L+1)/2 · W/L), bounding the number of alternating values that a network can approximate.The approximation condition forces the output to cross 1/2 at least 2^m −1 times, which is limited by its number of pieces.
- Depth-dependent bound: For piecewise linear activations, the bound specializes to m = O(L log(W/L)).This is the stated special case of the general piecewise-polynomial theorem.
- Consequence: The resulting approximation lower bound implies that networks with Θ(k) layers and O(2^{kε}) parameters must incur pointwise error greater than 1/2 for some input when m = k^{1+ε}.This gives a qualitative comparison with an earlier construction using O(m) layers and O(m) parameters.
4. Proof of Theorem 6
The proof of Theorem 6 partitions parameter space layer by layer so network outputs become bounded-degree polynomials within each region. Polynomial sign-pattern bounds then control the growth function and VC-dimension.
- Relation to prior work: Unlike the earlier piecewise-polynomial upper-bound proof, this argument is described as similar but optimized in several places.The broader predecessor approach uses bounds on connected components of semi-algebraic sets, related to Warren’s lemma.
- Polynomial sign patterns: K ≤ 2(2emd/n)^n bounds the possible sign vectors of m polynomials of degree at most d in n variables.This geometric estimate is the key ingredient applied inside each parameter-space region.
- Growth-function reduction: For fixed inputs, the proof treats the W network parameters as real variables and bounds the number of output sign patterns they can induce.This number is denoted K and bounds the growth function of the classifier class.
- Layerwise partition: The parameter domain is partitioned into regions where every network response is a fixed polynomial of bounded degree.The partition is refined successively across layers, preserving polynomial descriptions of unit inputs and outputs.
- Layerwise partition: Layerwise refinement uses activation breakpoints and polynomial sign patterns to split each region while keeping all relevant signs fixed.Within a final region, each unit lies between activation breakpoints, so its output is polynomial in the parameters.
- VC-dimension conclusion: The proof combines the region-wise sign-pattern bounds with iterative growth-function inequalities to obtain the VC-dimension bound.The final step uses the definition of VC-dimension and a logarithmic estimate under the condition U > 2.
5. Proof of Theorem 8
The proof expresses a piecewise-polynomial network’s output sign as a Boolean formula over polynomial inequalities. Goldberg–Jerrum’s theorem then converts the formula’s size and degree into a VC-dimension bound.
- Boolean representation: The output sign can be represented as a Boolean formula whose predicates encode activation states and the final output inequality.A ReLU example enumerates hidden-unit states and corresponding polynomial conditions.
- Polynomial predicates: Goldberg–Jerrum bounds VC-dimension by 2k log_2(8eds) for Boolean formulas with s polynomial predicates of degree at most d and k parameters.The theorem applies when predicates are polynomial inequalities or equalities in parameters and inputs.
- Polynomial predicates: The state of each computation unit is determined by polynomial predicates describing which activation piece contains its input.Topological ordering lets the proof propagate these state descriptions through the acyclic network.
- Counting predicates: The construction uses fewer than 2(1 + p)^U atomic predicates, each of degree at most max{U + 1, 2dU}.Here U is the number of computation units, p the number of activation pieces, and d the maximum polynomial degree per piece.
- VC-dimension conclusion: The resulting VC-dimension upper bound is O(WU log((1 + d)p)).The bound follows by substituting the predicate count and degree into the Goldberg–Jerrum theorem.