Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient

1 Introduction

• Ramanujan et al. [26] and Wang et al. [27] found that high-accuracy sparse subnetworks can reside in random networks without training, although finding them is NP-hard.Frankle and Carbin [20] define lottery tickets as sparse subnetworks that, when trained once, can match the fully trained dense model, potentially avoiding iterative pruning and retraining.Source: §1 · p. 2
• Malach et al. [1] proved the strong LTH for fully connected ReLU networks, but their polynomial over-parameterization bound left unclear how theory explains experimental tickets found with near-constant-factor widening.Their stated width bound is eO(d^5l^2/ϵ^2), improved to eO(d^2l^2/ϵ^2) under input sparsity assumptions; Ramanujan et al. [26] reported pruning a random Wide ResNet50 to ResNet34 accuracy.Source: §1 · p. 2
• Using subset sums rather than selecting one random sample can approximate a target weight with O(log(1/ϵ)) samples, and adapting this result to ReLU enables the improved strong-LTH bound.Lueker established the subset-sum approximation for target numbers using samples from distributions containing a uniform distribution on [−1, 1].Source: §1 · p. 3
• With probability at least 1 − δ, a random network of width O(d log(dl/min{ϵ, δ})) and depth 2l can be pruned to approximate any width-d, depth-l network within error ϵ.No training is required to obtain the approximating subnetwork; pruning the single larger network provides an ϵ-net of target networks.Source: §1 · p. 3
• A width-d, two-layer network exists that cannot be approximated within error ϵ by pruning a random two-layer network narrower than Ω(d log(1/ϵ)).This lower bound makes the logarithmic over-parameterization essentially optimal for constant-depth networks, up to logarithmic terms in width.Source: §1 · p. 3
• The paper improves on Malach et al. [1] with width O(d log(dl)); it also proves the result for a broad class of initialization distributions, improving on the O(d^2 log(dl)) bound of Orseau et al..Orseau et al. used hyperbolic initialization and conjectured their result also held for uniform initialization.Source: §1 · p. 3

• The target f(x) is a fully connected ReLU network, and the goal is to approximate it by pruning a larger network g(x).The input is x ∈ Rd0.Source: §2 · p. 4
• Pruning applies binary masks to weights, not entire neurons, with the larger network’s width controlled; Malach et al. [1] discuss the difference between these approaches.The masks have the same dimensions as the corresponding weight matrices and are applied element-wise.Source: §2 · p. 4
• The larger network’s weight matrices are randomly initialized, with each entry an independent sample from U[-1, 1].Source: §2 · p. 4
• Approximation error is measured uniformly on the unit norm-ball; bounded domains are necessary because ReLU networks are positively homogeneous.The domain can be extended to radius r by scaling ϵ appropriately, while any nonzero error can grow arbitrarily large on an unbounded domain.Source: §2 · p. 4

3 Lottery Tickets via Subset Sum

• One random 2l-layer network can uniformly approximate every target in F within error ϵ with probability 1 −δ, using logarithmic over-parameterization.The guarantee applies to all targets in F by pruning the same base network; the theorem is stated for spectral-norm-bounded weights.Source: §3 · pp. 4–5
• The theorem’s guarantee extends to standard normal and unit-variance zero-mean Laplace initialization, up to constants depending on the mixture parameters.The stated distribution condition is that P = (1 −α)Q + αU[−c, c] for α ∈ (0, 1] and c > 0.Source: §3 · p. 5

3.1 Single Link: Pruning a Linear Network

• For a linear two-layer network, pruning reduces approximation of a single weight to random SubsetSum, requiring n ≥ C log(1/min{ϵ, δ}) for the stated guarantee.Selecting a subset of the sampled weights and pruning the rest yields the logarithmic dependence on width.Source: §3.1 · pp. 5–6

3.2 Single Link: Pruning a ReLU Network

• A random ReLU network can approximate a single weight by pruning, using separate positive- and negative-input constructions whose coefficients are selected via SubsetSum.The lemma uses 2n hidden units with i.i.d. weights from U[−1, 1]; for the positive-input part, a subset approximates each w in [0, 1] within ϵ/2 with probability 1 −ϵ/2.Source: §3.2 · pp. 6–7
• The proof scales the single-link construction to approximate a neuron with d weights and a whole layer of d neurons using O(d log(d/ϵ)) width, reusing weights across neurons.Approximating each target layer individually yields a good approximation of the full network.Source: §3.2 · p. 7

4 Lower Bound by Parameter Counting

• With arbitrary network distributions, approximating every hW ∈ F with probability at least 0.5 requires Ω(d² log(1/ϵ)) parameters; for two-layer networks, width must be Ω(d log(1/ϵ)).Source: §4 · pp. 7–8
• The lower bound does not require uniform approximation over F, unlike Theorem 1’s d log(d/ϵ) width upper bound, and applies to the lottery-ticket version considered by Malach et al. [1].Source: §4 · p. 8
• Theorem 2 concerns linear multivariate functions as building blocks for multilayer approximation, but its bounds are tight only at constant depth; deeper-network generalization is left for future work.Source: §4 · p. 8
• A counting argument lower-bounds the number of pruned networks needed: unless |G| is large, some matrix W is far from every pruned network with high probability.Since |G| scales with the parameter count, this yields the stated lower bound.Source: §4 · p. 8

Experiment 2: Pruning Random Networks

• The experiments used MNIST; the pruning study compared the proposed structure against baselines and parameter-matched wider random networks using edge-popup.It evaluated two- and four-layer fully connected networks and LeNet5, selecting each architecture’s maximum accuracy across training durations of 10 to 100 epochs.Source: §5 · pp. 8–9

Experiment 1: SUBSETSUM

• SUBSETSUM approximated all 397,000 target weights with 3,725,871 coefficients in 21.5 hours while preserving 97.19% MNIST test accuracy.The target was a two-layer network with 500 hidden nodes; each weight used a subset sum of about 21 coefficients for ϵ = 0.01.Source: §5 · p. 8

Experiment 2: Pruning Random Networks

• At small parameter counts, adding ReLU activations performed worse than using an identity mapping.The authors suggest that ReLU adds sparsification to an already sparsified network.Source: Figure 2 · p. 9, §5 · p. 9
• Pruning performance varied with network topology, indicating that architecture affects a pruning algorithm’s approximation performance and efficiency.The compared topologies contained approximately the same number of weights.Source: §5 · p. 9

6 Discussion

• A random network only O(log(dl)) times wider can contain a subnetwork that comes close to a target network’s accuracy, with the analysis relying on Lueker.A key building block approximates a linear function on d parameters by selecting coefficients from a random function with d log(dl/ϵ) parameters.Source: §6 · p. 9
• Future directions include extending results beyond fully connected networks, exploiting sparsity or low-rank structure, and developing provably efficient pruning algorithms under mild data assumptions.The discussion notes that strong LTH implies worst-case NP-hardness of pruning [1] and asks whether the analysis can improve existing pruning algorithms [26].Source: §6 · p. 9

Broader Impact

• Pruning may offer a more efficient alternative to gradient-based training, and sparse deployed networks can reduce memory, computation, energy use, and carbon footprint [37] [20] [26] [27].The authors cite the carbon footprint of training a deep model, including experimentation, as equivalent to four cars’ lifetime emissions [37].Source: Broader Impact · p. 10
• Pruning algorithms, if successful, will need scrutiny for issues such as robustness to adversarial examples.Source: Broader Impact · p. 10
• The authors connect SUBSETSUM with neural-network pruning and optimization, drawing on prior work and Lueker’s result that logarithmically many random numbers can approximate any bounded-domain number with high accuracy and probability.They suggest exploring whether SUBSETSUM results can inform other theoretical and practical machine-learning problems.Source: Broader Impact · p. 10

A Proof of the upper bound

• The proof proceeds hierarchically from a single weight to a neuron, a layer, and finally the whole network.The single-weight approximation uses a ReLU random network; the neuron and layer steps are developed in the appendices.Source: A Proof of the upper bound · p. 13

A.1 Approximating a single neuron

• The single-neuron proof treats a univariate linear function as the key step toward approximating a multivariate linear function.The passage points to Lemma 3 for the multivariate case.Source: §A.1 · p. 13, §A.2 · p. 15
• The single-neuron construction uses d blocks, each with k = O(log(d/ϵ)) neurons, to approximate σ(wT x).After preprocessing the first layer into a block structure, the construction uses the blocks to approximate the terms w_i x_i.Source: Figure 3 · p. 13
• After preprocessing the first layer, pruning only the second layer lets the construction reuse weights to approximate other neurons in a layer.The figure describes each block as approximating a coordinate contribution to wT x.Source: Figure 3 · p. 13

A.2 Approximating a single layer

• The layer construction approximates a target layer by pruning two layers of a randomly initialized network.Its overview uses d blocks, with a block structure created by pruning the first layer.Source: §A.2 · pp. 14–15
• With probability at least 1 − ϵ, Lemma 3 establishes a pruned-network approximation of a linear single-layer target.The pruned network is (S ⊙ N)T σ((T ⊙ M)x). The supplied passage does not expose the approximation-error bound.Source: §A.2 · p. 15

A.3 Proof of Theorem 1

• For each layer, Lemma 3 supplies binary matrices S2i and S2i−1 that achieve its guarantee.The proof applies the 1-Lipschitz property of ReLU and recursively bounds the difference between original and pruned layer inputs, using Equation (12) to unroll the bound.Source: §A.3 · pp. 16–17
• With probability at least 1 − ϵ, inequalities (12) and (13) hold for every layer, and the proof uses them to construct a pruned network for any fixed function f.The final inequality holds with probability at least 1 − ϵ; replacing ϵ by min{ϵ, δ} gives the theorem statement.Source: §A.3 · p. 17

Packing argument and subnetworks

• A 2ε-separated packing ensures each approximating function can cover at most one target, so more packed targets than available subnetworks implies a difficult target.The proof compares the packing cardinality with the maximum number of subnetworks and uses an expectation argument to establish the target’s existence.Source: B Proof of Lower Bound · p. 18

Packing-size lower bound

• A volume bound on an operator-norm covering set supplies a lower bound on the packing size used in the proof.The packing is chosen with maximum cardinality, and the proof relates it to the covering number of the unit ball in matrix space.Source: B Proof of Lower Bound · p. 18

Case l = 2

• For depth 2, the proof counts the matrices obtainable by pruning the two layer matrices to bound the number of subnetworks.It uses this count to derive the required lower bound on the intermediate width.Source: B Proof of Lower Bound · p. 18

Lower-bound result

• The proof concludes that a lower-bound requirement is needed to approximate every function in F by pruning g with probability 1/2.The supplied passage truncates the expression for that requirement.Source: B Proof of Lower Bound · p. 18

Case l > 2

• For depth greater than 2, the proof bounds the number of subnetworks using the total parameter count and applies the same argument to obtain a lower bound.The passage states the resulting parameter bound as m = Ω, but its expression is truncated in the supplied text.Source: B Proof of Lower Bound · p. 19

C.1 Product of uniform distributions contains a uniform distribution

• Lemma 4 characterizes the density of XY when X is uniform on [0, 1] or [−1, 0] and Y is independently uniform on [−1, 1].Source: §C.1 · p. 19
• For X uniform on [0, 1], the proof notes that the density of XY is zero for z > 1 and partitions the CDF calculation according to whether Y is below or above z.Source: §C.1 · p. 19
• Because XY is symmetric around 0, the density expression is extended to |z| ≤ 1.Source: §C.1 · p. 19
• Corollary 1 states that the product distribution contains a uniform component and that a residual distribution Q exists.Source: §C.1 · p. 19

C.2 Subset sum problem with product of uniform distributions

• For i.i.d. samples from Corollary 1’s product distribution, Corollary 2 asserts a subset-sum conclusion with probability at least 1 − ϵ once n meets its stated threshold.Source: §C.2 · p. 19
• The proof of Corollary 2 applies Markov’s inequality to Corollary 3.3 from.Source: §C.2 · p. 20