Source-linked AI summary
Proving the Lottery Ticket Hypothesis: Pruning is All You Need
Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, Ohad Shamir
TL;DR
The paper asks whether randomly initialized networks contain useful subnetworks, extending the lottery ticket hypothesis beyond subnetworks found through training. It proves that pruning random networks can approximate target networks and relates neuron-pruning to random features, while optimal weight-pruning is computationally hard to find.
Problem
Existing lottery-ticket results concern subnetworks that are reset and then trained, leaving open whether random networks contain subnetworks matching target performance without further training.
Method
The paper analyzes weight-subnetworks and neuron-subnetworks, approximating ReLU targets by pruning random networks and proving neuron-pruning equivalence to random-features models.
Results
A sufficiently wide random network contains a pruned subnetwork with accuracy roughly matching a bounded-weight target network; weight-subnetworks use a comparable parameter count.
Takeaways & Limitations
The results indicate that pruning can be as expressive as weight optimization, motivating pruning-focused algorithms while leaving practical heuristic performance as an open consideration.
Takeaways & Limitations
Finding an optimal weight-subnetwork is computationally hard in general, so no efficient algorithm is guaranteed to return one for every input distribution.
Abstract
from arXiv · showhide
The lottery ticket hypothesis (Frankle and Carbin, 2018), states that a randomly-initialized network contains a small subnetwork such that, when trained in isolation, can compete with the performance of the original network. We prove an even stronger hypothesis (as was also conjectured in Ramanujan et al., 2019), showing that for every bounded distribution and every target network with bounded weights, a sufficiently over-parameterized neural network with random weights contains a subnetwork with roughly the same accuracy as the target network, without any further training.
1 Introduction
The paper strengthens the lottery ticket hypothesis by proving that random over-parameterized networks contain accurate subnetworks without training, while distinguishing weight- and neuron-based pruning. Its results provide theoretical support for pruning as an alternative to weight optimization, though pruning methods differ in compression, inference efficiency, and computational tractability.
- Motivation: The lottery ticket hypothesis proposes that a randomly initialized network contains a subnetwork that can match the trained original network when trained in isolation.Follow-up work conjectured that sufficiently over-parameterized random networks may contain competitive subnetworks without any training.
- Contribution: The paper proves this stronger conjecture for over-parameterized deep and shallow neural networks, providing theoretical evidence for previously empirical claims.The authors describe this as the first theoretical work explaining the strong lottery ticket conjecture.
- Contribution: Weight-subnetworks approximate a ReLU target network of depth l by pruning a random network of depth 2l, whereas neuron-subnetworks apply to shallow networks.The paper also relates neuron-subnetworks to random-features classifiers.
- Results: The pruned weight-subnetwork uses a number of parameters similar, up to a constant factor, to the target network.The initial random network is polynomial in the problem parameters.
- Implications: Pruning a random network is competitive with optimizing weights, motivating pruning mechanisms that select weights rather than optimize their values.The related-work discussion notes that weight pruning compresses better, while neuron or channel pruning can provide more effective inference-time gains on modern hardware.
2 Approximating ReLU Networks by Pruning Weights
The paper shows that pruning weights from a sufficiently wide random ReLU network can approximate target networks, using a network twice as deep and polynomially wide. The resulting pruned network retains a comparable number of active weights, while the pruning problem is computationally hard in general.
- Weight-subnetwork construction: A depth-l ReLU network can be approximated by pruning a random network of depth 2l and sufficient polynomial width.The construction uses weight-subnetworks, which remove specific weights rather than entire neurons.
- Assumptions: The theorem assumes bounded target-network weights and uniform random initialization, while extensions cover other uniform intervals through output rescaling.The target weights satisfy spectral and maximum-norm bounds, and the theorem’s input-norm assumption can be extended with polynomial dependence on the bound.
- Weight-subnetwork construction: The pruned network has O(dn + n2l) active weights, comparable up to a constant factor to the target network’s parameter count.The random network’s width depends polynomially on input dimension, target width, and target depth.
- Proof idea: A single ReLU neuron can be approximated using pairs of randomly selected weights, requiring only 2d active weights instead of training the weights.Appropriate pairs are found with high probability when the random network width is much larger than d/ǫ.
- Proof idea: Stacking the single-neuron constructions yields full-network approximation, with each target layer represented by two layers in the pruned network.For depth-two targets, a stronger result uses a depth-three random network, with O(dn) active weights.
- Universality and computational efficiency: Although pruning random weights has universal approximation power, finding an optimal weight-subnetwork is computationally hard for arbitrary input distributions.An efficient optimal-pruning algorithm would approximate the best depth-two network, contradicting known hardness results under stated assumptions.
3 Equivalence Between Pruning Neurons and Random Features
This section shows that neuron-subnetworks of randomly initialized depth-two networks are equivalent in expressive power to random-features models, while also establishing settings where they can approximate target functions and datasets.
- Random-features formulation: Training only the second layer of a random-features model is equivalent to fitting a linear model over randomly chosen first-layer features.The features are σ(⟨w_i, x⟩), while only the coefficients u_i are trained.
- Expressive-power boundary: The equivalence means neuron pruning is competitive with random features whenever the latter achieves small loss, but inherits their approximation limitations.In particular, efficiently approximating a single ReLU neuron may require exponentially many features or exponentially large weights under a standard Gaussian distribution.
- Equivalence with random features: Neuron-subnetworks in randomly initialized depth-two networks are equivalent to random-features models under the stated distributional conditions.A random-features model with small loss exists if and only if a sufficiently wide random network contains a neuron-subnetwork with comparable loss.
- Construction and algorithm: The proof intuition partitions a wide random network into smaller networks and prunes neurons whose initialized output weights are far from suitable linear predictors.An explicit polynomial-time pruning procedure follows this construction, though the authors describe it as naive and leave more efficient algorithms for future work.
- Learning target functions: For finite datasets and RKHS targets, sufficiently wide randomly initialized depth-two networks contain neuron-subnetworks that achieve the target approximation guarantees with high probability.The width depends on problem complexity, including the number of examples and the minimum eigenvalue λ in the finite-dataset case, or the function-class constant C in the RKHS case.
- Learning target functions: In binary classification on a finite dataset, the construction can achieve zero 0−1 loss without scaling the resulting neuron-subnetwork.Using ǫ = 1/2 ensures the subnetwork’s signs match the labels.
4 Discussion/Future Work
The discussion argues that pruned random networks have strong expressive power but highlights computational and methodological limits, motivating more practical pruning algorithms and broader theoretical extensions.
- Limitations: Finding a good weight-pruned subnetwork is computationally hard in the worst case, much like finding good weights by optimization.The paper states that both approaches may contain good solutions even when locating them efficiently is hard.
- Practical implications: Heuristic pruning algorithms may work well in practice despite the worst-case hardness of weight-pruning.The discussion points to prior empirical demonstrations and distinguishes practical heuristics from worst-case guarantees.
- Future work: The authors identify heuristic algorithms with provable guarantees under mild distributional assumptions as an immediate direction for future work.They also propose improving polynomial width dependencies and extending the results to convolutional layers and ResNets.
A Proofs of Section 2
The proofs show that sufficiently wide randomly initialized networks contain weight- or neuron-subnetworks approximating target networks without training. The construction builds approximations from individual coordinates and neurons, then composes them across layers while controlling accumulated error.
- Weight-subnetworks: A sparse linear function can be approximated by pruning a two-layer random network with high probability.The construction uses binary masks selecting random weights and achieves error at most ǫ on inputs with bounded infinity norm.
- Weight-subnetworks: A one-neuron network can be approximated by pruning a three-layer random network.The approximation holds on the unit Euclidean ball, with the mask selecting suitable hidden-layer connections and output weights.
- Weight-subnetworks: An n-neuron target network follows by summing the independently constructed one-neuron subnetworks.A union bound provides simultaneous approximation for all components, yielding a binary-mask subnetwork with error bounded on ∥x∥2≤1.
- Deep networks: Each target layer can be approximated by pruning a wider random layer, with sparse masks controlling the number of retained parameters.The formal theorem assumes bounded target weights and constructs matching binary masks for both weight and interlayer matrices.
- Deep networks: Layerwise approximation errors accumulate through composition, but induction and positive homogeneity keep the final deep-network error bounded.The proof enlarges the input range for intermediate subnetworks to accommodate deviations from the target activations, then applies a union bound across layers.
B Proofs of Section 3
These proofs establish that pruning neurons from sufficiently large two-layer random networks can approximate target networks sharing first-layer weights and bounded second-layer weights. The argument combines concentration bounds, Rademacher complexity, and random-feature approximation.
- Random coordinate pruning: Pruning coordinates independently yields a generalization bound for linear predictors under bounded inputs.The proof uses McDiarmid’s inequality to control deviations caused by random coordinate pruning.
- Neuron-subnetworks: A sufficiently wide random two-layer network can approximate another network with the same first-layer weights and bounded output weights.The key construction prunes neurons so their retained output vectors approximate the target output vectors.
- Neuron-subnetworks: Concentration inequalities control the approximation uniformly over bounded inputs.Hoeffding-type bounds and union bounds establish simultaneous control of the relevant coordinatewise and function-level errors.
- Main theorem: The main theorem identifies many random neurons whose output weights can be pruned to approximate the target network.The proof counts independently successful neurons, then uses concentration and Rademacher complexity to construct a neuron-subnetwork.
- Main theorem: The resulting neuron-subnetwork inherits a bounded loss through the approximation argument and a final rescaling step.The proof separately bounds the approximation and residual terms before rescaling the network output.
C Proofs of section 3.1
This section constructs random-feature approximations for finite datasets and function classes, then transfers them to pruned two-layer networks. The resulting arguments use matrix conditioning, concentration, and neuron pruning.
- Random-feature approximation: The proof begins by approximating finite datasets with a random-features model under assumptions on the data.It relies on a prior random-features approximation result and then applies the same pruning argument to the resulting model.
- Finite datasets: For finite datasets, a well-conditioned feature Gram matrix enables a two-layer network to fit the labels exactly.The construction uses the inverse of XᵀX to obtain output weights, with bounded norm under the stated eigenvalue condition.
- Function classes: For the broader function-class variation, random features approximate functions represented through bounded Lipschitz activations and bounded coefficients.The target model is selected according to the complexity of either the finite dataset or the RKHS function.
- Width and concentration: With sufficiently large hidden layers, concentration and union bounds provide suitable output-weight vectors for all required random features.The proof establishes these vectors under separate width conditions for the finite-data and function-class cases.
- Pruned approximation: Pruning the random features then produces a subnetwork approximating the target model on the relevant dataset or function class.The final construction applies the neuron-pruning lemma to the bounded coefficient vectors obtained from the random-feature approximation.