PaperlayerView exact revision on arXiv

Source-linked AI summary

Benefits of depth in neural networks

Matus Telgarsky

arXiv:1602.04485v2cs.LGcs.NEstat.ML

TL;DR

The paper studies whether adding layers increases neural-network representation power. It proves exponential depth-versus-size separations for semi-algebraic networks and shows that the proof relies on oscillation bounds and VC-dimension arguments.

  • Problem

    The paper asks whether standard neural networks always gain representation power from additional layers, beyond function classes representable with constant-depth networks.

  • Method

    The paper models networks using semi-algebraic gates and combines few-layer oscillation bounds with VC-dimension arguments to establish representation and labeling results.

  • Results

    Θ(k^3)-depth networks with Θ(1) nodes per layer and Θ(1) distinct parameters can require Ω(2^k) nodes for approximation by O(k)-depth networks.

  • Takeaways & Limitations

    The results establish benefits of depth for networks built from standard ReLU gates and the broader semi-algebraic network class.

  • Takeaways & Limitations

    The VC-dimension analysis is adapted from piecewise-polynomial networks, with a more involved region-counting lemma for semi-algebraic networks, while retaining essentially the same bound.

Abstract

from arXiv · show

For any positive integer $k$, there exist neural networks with $Θ(k^3)$ layers, $Θ(1)$ nodes per layer, and $Θ(1)$ distinct parameters which can not be approximated by networks with $\mathcal{O}(k)$ layers unless they are exponentially large --- they must possess $Ω(2^k)$ nodes. This result is proved here for a class of nodes termed "semi-algebraic gates" which includes the common choices of ReLU, maximum, indicator, and piecewise polynomial functions, therefore establishing benefits of depth against not just standard networks with ReLU gates, but also convolutional networks with ReLU and maximization gates, sum-product networks, and boosted decision trees (in this last case with a stronger separation: $Ω(2^{k^3})$ total tree nodes are required).

1. Setting and main results

The paper shows that adding layers increases neural-network representation power: certain deep networks cannot be approximated by comparably narrow shallow networks without exponentially many nodes. The result applies broadly to semi-algebraic gates and yields companion bounds on how many functions deep networks can realize.

  • 1. Setting and main results: Θ(k^3) layers, Θ(1) nodes per layer, and Θ(1) distinct parameters suffice for networks that shallow O(k)-layer networks cannot approximate with o(2^k) nodes.The explicit ReLU construction uses 2k^3 + 8 layers, 3k^3 + 12 total nodes, and 4 + d distinct parameters.
  • 1. Setting and main results: The approximation framework uses L1 distance, while the shallow approximating class is defined using semi-algebraic gates and includes linear combinations of bounded-size decision trees.The target many-layered function uses standard ReLU gates, although the general theorem allows broader choices.
  • 1. Setting and main results: Semi-algebraic gates extend the analysis beyond standard ReLU networks to convolutional networks, sum-product networks, and boosted decision trees.The considered class includes ReLU and maximization gates, polynomial nodes, and decision-tree combinations.
  • 1. Setting and main results: A few compositions can create highly oscillatory functions, whereas adding nodes at fixed depth produces functions with few oscillations.An elementary counting argument then separates the resulting function classes by showing that low-oscillation functions cannot approximate high-oscillation functions.
  • 1. Setting and main results: O(2^k^3) points with a fixed labeling can make shallow networks perform hardly better than random guessing.The companion result also states that shallow networks are useless on most random labelings of O(k^9) points.
  • 1. Setting and main results: Theorem 1.2 bounds the random-labeling behavior of networks with p parameters, l layers, and m semi-algebraic nodes using VC-dimension arguments.Its proof follows a small modification of the VC-dimension analysis for piecewise-polynomial networks.

2. Semi-algebraic gates and assorted network notation

The paper models networks using semi-algebraic gates and explicit parameterized graph notation. This abstraction includes piecewise polynomial, ReLU, min/max, decision-tree, and boosted-decision-tree gates while supporting layer- and node-count descriptions.

  • Semi-algebraic gates: A semi-algebraic gate represents functions built from polynomial pieces selected by polynomial inequalities.Its definition uses polynomial tests qi, subsets Uj and Lj, and polynomial terms pj of degree at most β.
  • Semi-algebraic gates: The number of polynomial terms m is excluded from the gate’s parameter name because it does not affect the paper’s complexity estimates.
  • Semi-algebraic gates: Semi-algebraic gates include standard piecewise polynomial gates, maximization and minimization gates, decision trees, and boosted decision trees.These cases connect the abstraction to ReLU-based, convolutional, and tree-based network models.
  • Network notation: A network node receives the shared parameter vector, the input or parent-node outputs, and applies a semi-algebraic gate to compute its output.Inputs are conventionally accessed only by root nodes, while internal nodes use parent outputs and network parameters.
  • Network notation: The network class N(G) consists of the functions obtained by varying the free parameters while keeping the graph, gates, and wiring fixed.The notation Nd(m, l, t, α, β) further describes networks with at most l layers and m nodes per layer.

3. Benefits of depth

The proof separates deep and shallow networks by counting oscillations: composition creates many crossings, while fixed-depth addition yields few. This produces explicit depth–size separations for semi-algebraic networks.

  • The proof proceeds in three steps: few-oscillation functions poorly approximate highly oscillatory ones, shallow networks have few oscillations, and deep networks can have many.
  • 3.1. Approximation via oscillation counting: Cr(f) counts classifier intervals, and when f has many more crossings than g, g disagrees with f on many regions.Regular crossings are needed for the L1 result, while arbitrary-measure classifier separation needs no additional regularity.
  • 3.2. Few layers, few oscillations: A shallow semi-algebraic network restricted to an affine line has crossing number bounded through piecewise-polynomial complexity, with layers affecting the exponent and nodes affecting the base.The argument first bounds the number of polynomial pieces and then uses Cr(f) ≤ t(1 + α).
  • 3.2. Few layers, few oscillations: Composing polynomial and semi-algebraic gates refines partitions while multiplying complexity parameters, yielding bounds such as stk(1 + αγ) pieces and degree βγ.These bounds support the induction over network layers.
  • 3.3. Many layers, many oscillations: Iterating a triangle-wave function produces 2^k−1 peaks, because each composition stretches copies across existing intervals and doubles the oscillatory structure.The composition lemma gives the corresponding crossing-number growth, Cr(fk) = (2t)^k + 1.

4. Limitations of depth

The depth advantage is limited by the complexity of the shallow-network class: semi-algebraic networks admit VC-dimension and region-counting bounds that constrain their realizable labelings.

  • The Θ(k^3)-depth networks used in the separation realize relatively few different labelings, as controlled by the VC dimension of semi-algebraic networks.
  • Semi-algebraic networks compute polynomial functions on parameter regions defined by polynomial predicates, enabling growth-function and VC-dimension bounds.The partition has intersections of predicates, and the restricted network output is a fixed polynomial on each region.
  • The VC-dimension proof extends the piecewise-polynomial argument to multivariate semi-algebraic networks by inducting through network layers.
  • The resulting VC-dimension bound is basically the same as for piecewise-polynomial networks despite the more general gate representation.
  • The supporting counting argument uses polynomial-region intersection bounds and a probabilistic labeling lemma related to Gilbert–Varshamov packing.

5. Bibliographic notes and open problems

The paper situates its depth hierarchy result within approximation theory and related circuit analyses, then identifies characterizing difficult functions as an open direction.

  • Bibliographic notes: Earlier approximation results primarily separated broad function classes from smaller polynomial classes, whereas depth hierarchy theorems compare circuits at nearby depths.The cited literature includes Weierstrass, Kolmogorov, Vitushkin, Warren, and H˚astad’s circuit-complexity work.
  • Bibliographic notes: Related analyses address sum-product networks and networks of linear threshold functions, extending depth-separation questions toward neural-network architectures.The passage names work on sum-product networks and two- and three-layer threshold networks.
  • Bibliographic notes: Triangle-wave targets have appeared in studies of highly oscillating piecewise-affine functions and in analyses of sigmoidal networks approximating high-degree polynomials.These prior works provide related oscillatory constructions and approximation analyses.
  • Open problems: A future direction is to characterize many or all functions that are not well-approximated by smaller depths.The paper suggests that discovering such underlying structure could have value in machine learning.
  • Open problems: For symmetric signals, pre-composition with the ReLU triangle function can repeat the signal 2^k times at a horizontally scaled resolution.Proposition 5.1 states h(x) = h(x + i2^-k) = g(x2^k) over the specified domain.

Appendix A. Deferred proofs

Appendix A collects proofs that were omitted from the main text.

  • Appendix A: Appendix A serves as a repository for proofs deferred from the main paper.Its stated purpose is to collect omitted proofs.
  • Appendix A: The appendix complements the main exposition rather than introducing a separate stated result.The passage describes its contents as proofs omitted from the main text.
  • Appendix A: Readers seeking the paper’s omitted proof details should consult Appendix A.This follows directly from the appendix’s stated purpose.

A.1. Deferred proofs from Section 2

The deferred Section 2 proofs establish that standard piecewise-polynomial, maximum/minimum, and decision-tree gates are semi-algebraic.

  • Semi-algebraic gates: Piecewise-polynomial composition with a degree-α polynomial yields a (t, α, αβ)-semi-algebraic gate.The construction uses predicate polynomials derived from the gate’s interval boundaries.
  • Maximum and minimum gates: Minimum gates reduce to maximum gates through min_i x_i = −max_i(−x_i).The maximum construction uses pairwise difference polynomials and produces an (r(r−1), α, α)-semi-algebraic gate.
  • Decision trees: A k-decision tree is shown inductively to be (k, 1, 0)-semi-algebraic.The induction combines the predicate polynomial at the root with the semi-algebraic representations of both subtrees.
  • Decision trees: A (t, k)-boosted decision tree is (tk, 1, 0)-semi-algebraic by combining the representations of its t constituent trees.The proof unions the polynomial and predicate sets across trees.

A.2. Deferred proofs from Section 3

The deferred Section 3 proofs develop interval and crossing-number tools, propagate semi-algebraic complexity through networks, and analyze oscillatory triangle-wave constructions and polynomial consequences.

  • Partition tools: A partition refinement preserves the interval count bound |B| ≤ |A| = kt.The construction handles boundary points by splitting into at most two or three intervals.
  • Network complexity: Semi-algebraic composition bounds propagate layerwise polynomial complexity from network inputs through successive gates.The induction starts with affine input coordinates and applies the composition rule at each layer.
  • Network complexity: Composing with an affine map preserves decision-tree and boosted-decision-tree structure while yielding the corresponding polynomial representations.The affine map is pushed into tree predicates before applying the composition analysis.
  • Triangle-wave constructions: The ReLU triangle-wave compositions are analyzed inductively using symmetry and explicit piecewise formulas.The induction establishes periodic repetition and completes the refined form of the iterated triangle function.
  • Measure construction: A continuous measure is constructed by placing half its mass uniformly on disjoint balls around points where the triangle function alternates between 0 and 1.The radius is chosen using continuity so function values remain within 1/4 of their values at the selected points.
  • Polynomial consequence: There exists a polynomial of degree 2^k with a positive continuous measure under which every polynomial of degree ≤ 2^k−3 satisfies the stated approximation bound.This is presented as a corollary of the more general theorem.

A.3. Deferred proofs from Section 4

The deferred proofs establish VC-dimension bounds for semi-algebraic networks by combining a probabilistic dichotomy lower bound with an inductive control of polynomial regions across layers. The resulting growth-function estimate yields the stated VC bound and feeds directly into the main lemmas and theorem.

  • VC lower bound: Hoeffding’s inequality supplies a Gilbert–Varshamov-like lower bound on the number of dichotomies through fair Bernoulli labellings and a union bound.The argument fixes dichotomies, compares them with random labelings, and uses the chosen error parameter.
  • VC upper bound: The VC upper bound tracks piecewise polynomial behavior by induction over network layers, following the scheme for piecewise polynomial activations.The induction maintains layerwise polynomial representations and parameter-space partitions.
  • VC upper bound: Each subsequent semi-algebraic layer refines parameter-space regions according to gate predicates, while restricting every node to a fixed polynomial on each refined region.The predicates have degree at most α, and the previous-layer polynomials have degree at most βi.
  • VC upper bound: At layer 0, input coordinates are represented as affine maps, with a single initial parameter-space region and coordinate polynomials for all examples.The construction sets S0 := {Rp}, Q0 := ∅, and uses the nd possible coordinate maps.
  • Consequences: The recursive region-count estimate bounds the growth function, and choosing N so that Sh(N(G); N) < 2N yields an upper bound on VC(N(G)).The proof then derives Lemma 1.3 and Theorem 1.2 by applying the VC estimate and substituting it into the probabilistic lemma.

A.4. Deferred proofs from Section 5

The deferred proof of Proposition 5.1 is obtained immediately from Lemma 3.11.

  • Proposition 5.1 follows directly from Lemma 3.11.
Loading 1602.04485v2…