Source-linked AI summary
On the Computational Efficiency of Training Neural Networks
Roi Livni, Shai Shalev-Shwartz, Ohad Shamir
TL;DR
Neural-network training is theoretically hard despite strong expressiveness and practical success, motivating a modern study of when training can be computationally efficient. The paper analyzes over-specification and alternative activations, obtaining positive results including polynomial-time learning for constant-depth polynomial networks and a practical depth-2 algorithm.
Problem
Neural networks have strong expressive and statistical properties, but worst-case training is computationally hard, leaving their computational efficiency unresolved.
Method
The paper studies over-specified networks and quadratic activations, using rank-based optimization, linearization, and greedy selection to develop efficient training procedures.
Results
The paper provides positive and negative computational results, including polynomial-time learning for constant-depth quadratic networks and a practical, provably correct algorithm for depth-2 polynomial networks.
Takeaways & Limitations
Over-specification can make global optima easy to find, while changing the activation function yields efficient and practical training methods for certain polynomial-network classes.
Takeaways & Limitations
The over-specification result concerns extremely large networks that overfit, and the polynomial-network learning discussion relies on a small hidden-neuron representation assumption distinct from generic kernel-margin assumptions.
Abstract
from arXiv · showhide
It is well-known that neural networks are computationally hard to train. On the other hand, in practice, modern day neural networks are trained efficiently using SGD and a variety of tricks that include different activation functions (e.g. ReLU), over-specification (i.e., train networks which are larger than needed), and regularization. In this paper we revisit the computational complexity of training neural networks from a modern perspective. We provide both positive and negative results, some of them yield new provably efficient and practical algorithms for training certain types of neural networks.
1 Introduction
Neural networks offer broad expressive power and favorable statistical properties, but their training-time complexity remains a central obstacle. The paper revisits this tension and develops positive results based on over-specification, activation functions, and efficient algorithms for polynomial networks.
- Expressiveness: Neural networks can represent every Boolean function computable in time T(d) using depth O(T(d)) and size O(T(d)^2).The result follows from simulating Boolean computation with fixed-size neural implementations of standard gates.
- Statistical perspective: For every runtime T(d), a network of depth O(T(d)) contains all predictors runnable within time T(d), while its sample complexity depends polynomially on T(d).This frames neural networks as statistically broad hypothesis classes despite their training challenges.
- Training-time complexity: Training is computationally hard in the worst case, including finding best-fitting weights for depth-2 networks and even weights with close-to-minimal empirical error.These results concern proper learning with a fixed architecture, motivating consideration of alternative architectures through improper learning.
- Practical training tricks: Practical training commonly uses smooth or piecewise-linear activations, larger-than-needed networks, and weight regularization.ReLU avoids the threshold function’s zero derivative almost everywhere, over-specification is empirically easier to train, and regularization is reported to speed convergence.
- Paper contributions: The paper revisits neural-network computational efficiency with both positive and negative results, including efficient learning results for quadratic-activation networks.Its contributions include expressiveness of quadratic networks, polynomial-time learning for constant depth, and a practical provably correct depth-2 training algorithm.
2 Sufficiently Over-Specified Networks Are Easy to Train
The paper argues that sufficiently over-specified networks can make training computationally easy because fixing a representation with full row rank reduces optimization to a convex problem. This benefit is limited to extremely large networks that overfit.
- Main observation: Sufficiently over-specified networks generally have easy optimization problems and ubiquitous global optima.The authors present this as an indication that computational cost may decrease as over-specification increases.
- Scope: The result applies only to extremely large networks, which will overfit in reasonable scenarios.Thus, the observation establishes computational tractability under a strong over-specification regime rather than a general training guarantee.
- Optimization formulation: The training objective is min_W,V ℓ(W f(V)), where f(V) maps inputs to hidden-neuron outputs and ℓ is a convex loss.The network is decomposed into a representation map followed by a linear output map.
- Full-rank condition: When the hidden representation has n ≥ m and Rank(f(V)) = m, fixing V leaves a tractable convex optimization over W.The full-rank representation makes the resulting solution a global optimum of the original objective.
- Rank assumption: The full-rank condition is considered likely under random choices of V because neural-network mappings are nonlinear.A sigmoid first-layer mapping is given as an example whose output columns are not generally linearly dependent.
3 The Hardness of Learning Neural Networks
The section establishes computational hardness results for learning neural-network hypothesis classes, then shows that these barriers extend to sigmoidal and ReLU networks without weight regularization, while constant weight bounds and fixed depth admit later positive results.
- Efficient learning seeks a polynomial-time algorithm that returns a classifier evaluable in polynomial time on new instances.
- Depth-2 threshold networks can represent intersections of halfspaces, connecting neural-network learning to established hardness results for such classes.
- Under the stated cryptographic or complexity assumptions, threshold-activated network classes are not efficiently learnable for the specified growing network parameters.
- Unrestricted weights let threshold neurons be simulated by sigmoidal neurons or by two ReLU neurons, so the hardness result transfers to both activation functions.The sigmoid inclusion uses large weights, while the ReLU construction uses σrelu(z)−σrelu(z−1)=σ0,1(z) for |z| ≥1.
- Learning remains hard for depth-2 sigmoidal and ReLU networks when the input-weight bound satisfies L = Ω(d), despite their compatibility with gradient-based training.
- For constant L and fixed depth, the paper later gives positive results using polynomial networks, marking weight regularization as a boundary for tractability.
4 Polynomial Networks
Polynomial networks use squared activations to represent polynomials, yielding both expressiveness results and depth-dependent learning guarantees. Constant-depth cases admit polynomial-time linearization, while logarithmic-depth networks remain hard; practical GECO procedures provide guarantees for restricted depth-2 and depth-3 classes.
- Expressiveness: Squared-activation networks compute polynomial functions, and polynomial-size networks can express every function implementable by a sufficiently efficient Turing machine.Theorem 3 uses depth t = c T(d) log(T(d)) + b, size n = t^2, and bounded input-weight norm L = b.
- Expressiveness: Polynomial networks can uniformly approximate bounded-weight sigmoidal networks using a larger squared-activation network.For 0 < ϵ < 1, the approximation holds on inputs with ||x||∞ < 1, with depth and size expanded by factors depending on t, L, and ϵ.
- Computational complexity: Depth t = Ω(log(d)) and size n = Ω(d) define a polynomial-network class that is not efficiently learnable.This hardness result follows by combining the sigmoidal-approximation theorem with an earlier hardness corollary.
- Computational complexity: Constant-depth polynomial networks can be learned in polynomial time by embedding them in the linear space of multivariate polynomials of degree at most 2^t.Explicit linearization has runtime polynomial in d^(2^t), so the guarantee is polynomial for fixed depth but grows rapidly with depth.
- Regularization: With sufficient regularization, depth-2 sigmoidal networks are efficiently learnable, contrasting with the corresponding hardness result without regularization.Theorem 5 gives runtime poly(T), where T = (1/ϵ) · O(d^4 L ln(11L^2+1)).
5 Experiments
The experiments evaluate GECO and SGD on pedestrian detection and synthetic network-fitting tasks, including comparisons involving squared activations, ReLU, and over-specification.
- Pedestrian detection: GECO was evaluated on pedestrian detection using 200k 88x40-pixel image patches and HOG features.Half the examples were used for training and half for testing.
- Pedestrian detection: The study used hard negative image patches, selected because a simple sliding-window linear classifier labeled them as pedestrians.This construction targeted difficult negative examples for pedestrian detection.
- Pedestrian detection: A depth-2 polynomial network with 40 hidden neurons was trained using GECO and compared with SGD on the same squared-activation architecture.A 40-hidden-neuron ReLU network was also trained for comparison.
- Over-specification: The synthetic experiment found that SGD converges much faster with larger over-specification factors.The tested factors were 1, 2, 4, and 8, using up to 240 hidden neurons for a target network with 60.
A.1.1 Hardness result for the class N2,n,σsig,L:
The hardness construction shows that threshold-signature networks can represent conjunctions of halfspace tests, using neurons built from integral hyperplane parameters.
- Construction: For every h ∈ Ha, there are integral w and b such that h(x) = w⊤x − b − 1.The construction also states that |h(x)| ≥ 1/2.
- Construction: Given k hyperplanes, the construction uses neurons associated with the hyperplanes to build the target function.The supplied passages introduce the neurons and their output conditions but do not fully preserve the intermediate definitions.
- Bounds: The construction controls neuron outputs through exponential terms involving the parameter C and the number of hyperplanes k.The displayed bound compares the cases where all neuron outputs are positive and where at least one is not.
- Result: The target function sign(g(x)) implements h1 ∧ h2 ∧ . . . ∧ hk.This is the stated conclusion of the threshold-signature construction.
A.1.2 Hardness result for the class N2,n,σrelu,L:
For ReLU networks, the construction uses two neurons per hyperplane and yields a function that implements the conjunction of the corresponding halfspace tests.
- Construction: For each of k hyperplanes, the construction considers two neurons.The passage explicitly introduces a pair of neurons for every hyperplane.
- Network class: The resulting function belongs to N2,2k+1,σrelu,L whenever L ≥ 2d.The construction therefore uses depth 2 and 2k+1 neurons under the stated weight bound.
- Result: The ReLU construction implements h1 ∧ h2 ∧ . . . ∧ hk.This conjunction result is stated directly after the network-class guarantee.
A.2 Proof of Thm. 3
Polynomial networks can implement Boolean gates and simulate fixed-fan-in circuits, while oblivious Turing machines provide a route to simulating computations with predictable network depth.
- Gate construction: Polynomial networks implement AND, OR, NEG, and Id gates with fixed depth and size.NEG maps x to 1−x, while Id maps x to x.
- Gate construction: AND(x1, x2) = x1 · x2, and OR(x1, x2) = x1 + x2 − AND(x1, x2).These polynomial identities give the two-input gate constructions.
- Circuit simulation: A fixed-fan-in circuit of size T can be implemented with O(T) layers and O(T^2) neurons.Each layer simulates all gates at the corresponding circuit depth.
- Turing-machine simulation: Any Turing machine with runtime T can first be simulated by an oblivious Turing machine in O(T log T) steps.Obliviousness makes the machine-head position at each time known ahead of time, supporting network simulation.
A.3 Proof of Thm. 4
The proof of Thm. 4 builds polynomial networks efficiently, then uses polynomial approximation of sigmoidals to replace sigmoid activations while controlling depth, width, and approximation range.
- Polynomial-network construction: Any T-degree polynomial can be represented with O(log T) layers and O(T) neurons.This construction is established in Lemma 1 part 4.
- Sigmoid approximation: Sigmoidal functions are approximated on a ball of radius L by polynomial networks, enabling sigmoid activation units to be replaced by added approximation layers.Lemma 2 supplies the approximation step used in the proof of Thm. 4.
- Polynomial-network construction: Multiplication is implemented by adding one layer and one neuron to a network with two output neurons.The construction uses x1 · x2 = 1/4(x1 + x2)^2 − 1/4(x1 − x2)^2.
- Polynomial-network construction: For g ∈ N_t,n,σ2,L, the power g^T uses t′ = t + log T + log log T layers and n′ = n + 2 log T + log T(log log T) neurons.The construction represents powers of two and combines them through pairwise products.
- Polynomial-network construction: A polynomial with coefficient vector a has width overhead depending on its sparsity ∥a∥0, while its range parameter becomes L′ = max{∥a∥1, L, 2}.The stated width expression is n′ = n + 2∥a∥0(2 log T + log T(log log T)).
A.3.1 Back to proof of Thm. 4
The argument returns to Thm. 4 by recursively replacing sigmoid layers with polynomial approximations, while the GECO analysis handles the remaining three-layer approximation step through approximate eigenvector computation.
- Back to proof of Thm. 4: The resulting construction includes explicit depth and neuron-growth bounds, including B_n = 1 + 2T(2 log T + log T log log T) ∈ Õ(L log L^t).The bound quantifies the network-size overhead in the approximation construction.
- Back to proof of Thm. 4: The sigmoid-to-polynomial replacement proceeds by induction over network depth and preserves the target function's layerwise structure.For a network with s output nodes, the proof constructs approximations for each coordinate and combines them into P = P1, . . . , Ps.
- Back to proof of Thm. 4: The approximation uses bounded inputs: neuron outputs are at most 1, weight ℓ1-norms are at most L, and the sigmoid is 1-Lipschitz.These bounds control the propagated approximation error at each inductive step.
- GECO approximation: GECO uses an Approx procedure over V = ∪V_i, and its guarantees follow in the same manner as the cited prior analysis.The computational bottleneck is the case g* ∈ V3; cases g* ∈ V2 or V1 reduce to the two-layer scenario.