PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding Deep Neural Networks with Rectified Linear Units

Raman Arora, Amitabh Basu, Poorya Mianjy, Anirbit Mukherjee

arXiv:1611.01491v6cs.LGcond-mat.dis-nncs.AIcs.CCstat.ML

TL;DR

The paper asks how ReLU DNN architecture affects representable functions, approximation, and training complexity. It characterizes ReLU networks through piecewise-linear functions, develops depth-separation results and a global optimization algorithm for one-hidden-layer networks, and derives stronger affine-piece lower bounds. The results include super-exponential shallow-network size requirements and training time polynomial in data size but exponential in input dimension, with deeper training and network-size dependence left as open challenges.

  • Problem

    The paper investigates the function classes, depth-size trade-offs, and training complexity of ReLU DNNs.

  • Method

    The paper characterizes ReLU DNNs using piecewise-linear functions, constructs smoothly parameterized hard-function families, and develops an algorithm for globally optimizing one-hidden-layer networks.

  • Results

    ReLU DNNs represent exactly the piecewise-linear functions at bounded depth; shallow approximations can require super-exponential size, while one-hidden-layer training is polynomial in data size but exponential in input dimension.

  • Takeaways & Limitations

    The results connect ReLU expressive power to piecewise-linear structure and show that depth can yield strong representation advantages over shallower networks.

  • Takeaways & Limitations

    The global optimization algorithm is exponential in input dimension and hidden-node count, and optimal training for networks with two or more hidden layers remains open.

Abstract

from arXiv · show

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give an algorithm to train a ReLU DNN with one hidden layer to *global optimality* with runtime polynomial in the data size albeit exponential in the input dimension. Further, we improve on the known lower bounds on size (from exponential to super exponential) for approximating a ReLU deep net function by a shallower ReLU net. Our gap theorems hold for smoothly parametrized families of "hard" functions, contrary to countable, discrete families known in the literature. An example consequence of our gap theorems is the following: for every natural number $k$ there exists a function representable by a ReLU DNN with $k^2$ hidden layers and total size $k^3$, such that any ReLU DNN with at most $k$ hidden layers will require at least $\frac{1}{2}k^{k+1}-1$ total nodes. Finally, for the family of $\mathbb{R}^n\to \mathbb{R}$ DNNs with ReLU activations, we show a new lowerbound on the number of affine pieces, which is larger than previous constructions in certain regimes of the network architecture and most distinctively our lowerbound is demonstrated by an explicit construction of a *smoothly parameterized* family of functions attaining this scaling. Our construction utilizes the theory of zonotopes from polyhedral theory.

1 INTRODUCTION

The paper studies ReLU DNNs as a framework for understanding deep learning, focusing on their function classes, architecture, and piecewise-linear structure. It defines ReLU networks and their key architectural measures as groundwork for analyzing expressive power.

  • ReLU networks use the non-saturating activation σ(x) = max{0, x}, which is the paper’s focus for studying deep architectures.
  • The paper formally investigates the functions represented by ReLU DNNs and how depth and width affect their expressive power.
  • A ReLU DNN is specified by hidden-layer widths and affine transformations followed by a final linear transformation.
  • The network’s depth is the number of transformations, width is the maximum hidden-layer width, and size is the sum of hidden-layer widths.
  • Every ReLU DNN represents a continuous piecewise-linear function, motivating the paper’s analysis of affine regions and function structure.

2 EXACT CHARACTERIZATION OF FUNCTION CLASS REPRESENTED BY RELU DNNS

This section characterizes ReLU DNNs through continuous piecewise-linear functions and derives depth and size guarantees for representation and approximation. It also establishes universal approximation in Lq spaces, with especially tight size bounds in one dimension.

  • Every Rn → R ReLU DNN represents a piecewise-linear function, and every piecewise-linear function can be represented with depth at most ⌈log2(n + 1)⌉ + 1.
  • The converse representation uses linear combinations of piecewise-linear convex functions, each formed from maxima of at most n + 1 affine functions.
  • ReLU DNNs implement composition, addition, and pointwise maximum of piecewise-linear functions; balanced maxima yield depth at most ⌈log2(n + 1)⌉.
  • For a one-dimensional piecewise-linear function with p pieces, a 2-layer DNN needs at most p nodes and every such network needs at least p − 1 nodes.
  • Every Lq(Rn) function for 1 ≤ q ≤ ∞ can be arbitrarily well approximated by a ReLU DNN with at most ⌈log2(n + 1)⌉ hidden layers.

3 BENEFITS OF DEPTH

The paper shows that depth gives ReLU DNNs strong representational advantages: smoothly parameterized hard functions can require super-exponentially larger shallower networks, while zonotope-based constructions yield many affine pieces with compact architectures.

  • Depth-size trade-offs: Depth enables smoothly parameterized families of R → R hard functions whose shallower representations require exponentially or super-exponentially greater size.The results extend earlier depth-size gaps beyond countable families and improve some prior exponential lower bounds to super-exponential scaling.
  • Depth-size trade-offs: For every natural number k, some function uses k^2 hidden layers and k^3 nodes, whereas any network with at most k hidden layers needs at least 1/2 k^(k+1) - 1 nodes.This is the stated special case of the depth-size gap.
  • Depth-size trade-offs: The paper also establishes hardness-of-approximation versions of the depth-size results with the same gaps up to constant terms.The approximation statement applies to the hard functions in the one-dimensional construction.
  • Affine pieces: The paper constructs R^n → R functions with many affine pieces using zonotopes, represented by depth k + 2 networks of size 2m + wk.The construction k,w,m[a1, ..., ak, b1, ..., bm] has (m - 1)^(n - 1)wk pieces.
  • Affine pieces: The affine-piece lower bound is attained by a smoothly parameterized family in one-to-one correspondence with a higher-dimensional torus.The paper presents this smooth parameterization as a distinction from prior constructions.
  • Affine pieces: The zonotope family improves prior affine-piece constructions in some regimes, including n ≤ w < 2n and k ∈ Ω(n/log(n)), while allowing network size independent of input dimension.The comparison specifically concerns the paper’s complexity measure and bottleneck architectures.

4 TRAINING 2-LAYER Rn →R RELU DNNS TO GLOBAL OPTIMALITY

The paper gives a globally optimal ERM algorithm for two-layer ReLU DNNs by combining combinatorial activation-pattern search with convex optimization. Its runtime is polynomial in data size for fixed input dimension and width, but exponential in both input dimension and hidden-node count.

  • Global-optimality guarantee: The algorithm finds a global optimum for empirical risk minimization with two-layer R^n → R ReLU DNNs under a convex loss.It returns a network from the class being learned.
  • Complexity: The runtime is O(2^w(D)n^w poly(D, n, w)), which is polynomial in data size D for fixed n and w.The exponential factors arise from the input dimension and number of hidden nodes.
  • Algorithmic strategy: The method searches over hidden-node activation partitions and top-layer signs, then solves a convex constrained optimization problem for each configuration.The convex subproblem uses linear inequality constraints induced by the activation patterns.
  • Algorithmic strategy: The implementation enumerates sign assignments and combinations of data partitions before returning the parameters associated with the minimum-loss iteration.These steps correspond to the algorithm’s exhaustive combinatorial search.
  • Scope: The result addresses ERM for one hidden layer, whereas obtaining optimal training algorithms for networks with two or more hidden layers remains substantially harder.The paper contrasts its result with related improper-learning work because its algorithm returns a ReLU DNN from the learned class.

5 DISCUSSION

The proposed exact-training algorithm has exponential dependence on input dimension and hidden-node count. The paper identifies removing the input-dimension dependence and extending global-optimality guarantees to deeper networks as open problems.

  • Limitations: The algorithm’s runtime is exponential in input dimension n and the number of hidden nodes w.The paper states that exponential dependence on n cannot be removed unless P = NP.
  • Open problems: Optimal training algorithms for DNNs with two or more hidden layers remain an open challenge described as substantially harder.The discussion also identifies gap results between consecutive constant depths or between logarithmic and constant depths as open directions.

A EXPRESSING PIECEWISE LINEAR FUNCTIONS USING RELU DNNS

The appendix characterizes one-dimensional piecewise linear functions through slopes and breakpoints and constructs equivalent two-layer ReLU representations. Flat end pieces reduce the required size to p − 1 for a p-piece function.

  • Function representation: A one-dimensional m-piece piecewise linear function is uniquely specified by its leftmost slope, nondifferentiable points, and rightmost slope.The nondifferentiable points are represented by breakpoint-coordinate pairs.
  • ReLU construction: Each ReLU flap uses one breakpoint and a slope parameter, allowing a piecewise linear function to be decomposed into a sum of such components.The construction uses expressions implemented by two-layer ReLU networks of size 1.
  • Parameter construction: The slope parameters satisfy a system of linear equations that has a unique solution obtained by backward substitution.The construction first determines the rightmost slope and then solves successively for the remaining parameters.
  • Size bounds: A general p-piece function requires at least p − 1 nodes for any two-layer ReLU representation.The appendix separately derives an upper construction using p flaps.
  • Size bounds: When the leftmost or rightmost piece is flat, a p-piece one-dimensional function can be computed by a two-layer ReLU DNN of size p − 1.A flat rightmost piece makes the corresponding outer slope parameter zero; the left-flat case is analogous.
  • Approximation: Continuous piecewise linear functions are dense in Lp(R^n) for 1 ≤ p ≤ ∞, and each is representable by a ReLU DNN.Together, these facts yield approximation of such Lp functions by ReLU DNNs.

B BENEFITS OF DEPTH

Composing ReLU functions produces many affine pieces while preserving controlled range and amplitude. These constructions support depth-based separation results against shallower piecewise-linear networks.

  • B BENEFITS OF DEPTH: (p+1)^k + 2 pieces are obtained by composing k functions, with (p+1)^k pieces lying in [0, M].Each such piece is affine with minimum value 0 and maximum value M.
  • B BENEFITS OF DEPTH: w^k pieces are produced by a k+1-layer ReLU DNN of width w+1, with exactly w nodes in every hidden layer.Each component function has w+1 pieces and can be represented by a 2-layer ReLU DNN of size w.
  • B BENEFITS OF DEPTH: ⌊w^k/2⌋ triangles force any affine comparator to incur ℓ1 error at least 1/(2w^k) on each such triangle.The hard function contains triangles of width 1/w^k and unit height.
  • B BENEFITS OF DEPTH: 1/(2w^k) is the minimum integral error attained by an affine function on one triangle when both endpoint values equal 1/2.The construction then combines these local errors to lower-bound the global approximation error.

B.2 A CONTINUUM OF HARD FUNCTIONS FOR Rn →R FOR n ≥2

Zonotopes provide an explicit, smoothly parameterized construction of high-piece ReLU functions in dimensions n≥2. The construction combines zonotope support functions with one-dimensional composed functions.

  • B.2 A CONTINUUM OF HARD FUNCTIONS FOR Rn →R FOR n ≥2: |⟨r,b1⟩|+...+|⟨r,bm⟩| is represented as a sum of max-affine terms using ReLU operations.Each absolute inner product is rewritten as max{⟨r,bi⟩,−⟨r,bi⟩}.
  • B.2 A CONTINUUM OF HARD FUNCTIONS FOR Rn →R FOR n ≥2: 2m + wk is the size of a k+2-layer ReLU DNN representing the constructed function k,w,m[a1,...,ak,b1,...,bm].The representation follows by combining the zonotope support-function construction with the composed one-dimensional function.
  • B.2 A CONTINUUM OF HARD FUNCTIONS FOR Rn →R FOR n ≥2: The construction’s piece count combines Pn−1 distinct linear pieces from the zonotope support function with wk pieces from Ha1,...,ak.This yields the stated high-piece scaling for the smoothly parameterized family.

C EXACT EMPIRICAL RISK MINIMIZATION

Exact empirical risk minimization is reduced to enumerating activation patterns and solving convex optimization problems. The resulting algorithms are polynomial per pattern but exponential in relevant structural parameters.

  • C EXACT EMPIRICAL RISK MINIMIZATION: Each data point’s active ReLU terms form a partition induced by a hyperplane, reducing the network expression to a linear function under a fixed partition.The algorithm guesses these partitions and then performs constrained linear regression.
  • C EXACT EMPIRICAL RISK MINIMIZATION: poly(D,n,w) time suffices for each convex optimization problem, giving the claimed global optimization runtime after enumeration.The objective is convex when the loss is convex in its first argument.
  • C EXACT EMPIRICAL RISK MINIMIZATION: 2^wD^(nw) guesses cover hyperplane partitions and sign vectors for the w hidden units in input dimension n≥2.Each guess leads to a convex optimization problem with (n+1)w variables and Dw constraints.
  • C EXACT EMPIRICAL RISK MINIMIZATION: O((2D)^w poly(D)) is the one-dimensional running time for enumerating breakpoint intervals and slope-order patterns.The algorithm solves O(2^w·D^w) convex optimization problems, each taking O(poly(D)) time.

D AUXILIARY LEMMAS

The auxiliary lemmas establish closure properties of ReLU networks and relate depth, width, size, and piecewise-linear complexity. They also provide constructions and lower bounds used in the paper’s expressivity arguments.

  • D AUXILIARY LEMMAS: A composition of ReLU networks adds their sizes and combines their depths according to Lemma D.1.This closure rule supports the layered constructions used throughout the paper.
  • D AUXILIARY LEMMAS: A maximum of m ReLU-representable functions has depth at most max{k1,...,km}+log(m)+1 and size at most s1+...+sm+4(2^m−1).The same lemma also provides an analogous construction for minima.
  • D AUXILIARY LEMMAS: At most twice as many pieces can result when applying g(x)=max{0,f(x)} to a piecewise-linear input f.Each original affine piece can be intersected by the x-axis.
  • D AUXILIARY LEMMAS: 2^(k−1)p^(1/k)−1 is a lower bound on the size of a depth-k+1 ReLU representation of a p-piece function.The bound follows by applying AM-GM to the product constraint on layer widths.
Loading 1611.01491v6…