# Structured vs. Unstructured Pruning: An Exponential Gap

Davide Ferre', Frédéric Giroire, Frederik Mallmann-Trenn, Emanuele Natale

<figure><img src="image_1.png" /></figure>

## To cite this version:

Davide Ferre', Frédéric Giroire, Frederik Mallmann-Trenn, Emanuele Natale. Structured vs. Unstructured Pruning: An Exponential Gap. 2026. hal-05507068v2

HAL Id: hal-05507068

https://hal.science/hal-05507068v2

Preprint submitted on 14 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Structured vs. Unstructured Pruning:
An Exponential Gap

Davide Ferré¹, Frédéric Giroire¹, Frederik Mallmann-Trenn², and Emanuele Natale¹

¹Université Côte d'Azur, CNRS, Inria, I3S, France

²Department of Informatics, King's College London

February 14, 2026

## Abstract

The Strong Lottery Ticket Hypothesis (SLTH) posits that large, randomly initialized neural networks contain sparse subnetworks capable of approximating a target function at initialization without training, suggesting that pruning alone is sufficient. Pruning methods are typically classified as unstructured, where individual weights can be removed from the network, and structured, where parameters are removed according to specific patterns, as in neuron pruning. Existing theoretical results supporting the SLTH rely almost exclusively on unstructured pruning, showing that logarithmic over-parameterization suffices to approximate simple target networks. In contrast, neuron pruning has received limited theoretical attention.

In this work, we consider the problem of approximating a single bias-free ReLU neuron using a randomly initialized bias-free two-layer ReLU network, thereby isolating the intrinsic limitations of neuron pruning. We show that neuron pruning requires a starting network with $\Omega(d/\varepsilon)$ hidden neurons to successfully $\varepsilon$-approximate a target ReLU neuron. In contrast, weight pruning achieves $\varepsilon$-approximation with only $O(d \log(1/\varepsilon))$ neurons, establishing an exponential separation between the two pruning paradigms.

# 1 Introduction

Modern neural networks are typically trained in highly overparameterized regimes, often containing orders of magnitude more parameters than are seemingly necessary to represent the target function. Despite this redundancy, empirical evidence suggests that such large models can be pruned aggressively after training, yielding sparse subnetworks that retain comparable performance. Understanding the origin of this phenomenon has become a central topic in the theory of deep learning.

A prominent line of work addressing this question is the *Lottery Ticket Hypothesis* (LTH), introduced in Frankle and Carbin [2018]. The LTH posits that sufficiently large randomly initialized networks contain sparse subnetworks—called *winning tickets*—which, when trained in isolation, can achieve the performance of the original dense network. Subsequent empirical works refined this perspective and proposed pruning strategies that identify such subnetworks efficiently [Zhou et al., 2019, Ramanujan et al., 2020].

These developments motivated an even stronger conjecture, known as the *Strong Lottery Ticket Hypothesis* (SLTH), which asserts that winning tickets already exist at initialization, without requiring any training of the retained weights. In other words, pruning alone suffices to obtain a performant subnetwork. This formulation removes the need to analyze training dynamics and has enabled a series of rigorous existence proofs for fully connected
and convolutional architectures [Malach et al., 2020, Pensia et al., 2020, Orseau et al., 2020, Ferbach et al., 2022].

Given a target network and $\varepsilon > 0$, the guiding research question is to determine what level of overparameterization (function of $\varepsilon$) a network requires so that it likely has a sub-network that approximates the target network (see Definition 1 for the precise metric). A crucial aspect of these results is their dependence on the approximation accuracy $\varepsilon$. In multilayer networks, approximation errors accumulate across layers, so existing guarantees implicitly require $\varepsilon$ to be small with respect to the width and depth of the network; consequently, a pruning scheme whose overparameterization scales linearly in $1/\varepsilon$ is considered too demanding in deep settings [Pensia et al., 2020].

**Unstructured pruning and logarithmic overparameterization.** Most existing theoretical results establishing the SLTH rely on *unstructured pruning*, also known as *weight pruning*, in which individual edges are removed from the network. A key technical insight, first identified in Malach et al. [2020] and later sharpened in Pensia et al. [2020], is that weight pruning allows one to approximate target weights by doing subset sums of randomly initialized weights. By leveraging a classical result of Lueker [1998] on the random subset sum problem, Pensia et al. [2020] showed that a random network with only logarithmic overparameterization—on the order of $O(\log(1/\varepsilon))$ per target weight—contains subnetworks that $\varepsilon$-approximate a broad family of target functions. Matching lower bounds show that this logarithmic dependence is essentially optimal for constant-depth networks [Pensia et al., 2020]. While unstructured pruning provides a powerful theoretical framework for establishing the existence of accurate subnetworks, its implications for computational efficiency are less clear. Indeed, unstructured pruning typically produces sparsity patterns with zeros in arbitrary locations in the weight matrices. Such sparsity does not, by itself, translate into predictable speedups on standard hardware, where dense linear algebra routines are optimized for contiguous memory access and regular computation.

**Structured pruning and neuron pruning.** The aforementioned gap between parameter sparsity and actual speedups motivates the study of *structured pruning* methods, which enforce sparsity at the level of entire blocks, rows, or columns of weight matrices. Such structure directly translates into smaller matrices and fewer arithmetic operations, yielding genuine reductions in memory usage and inference time. Among structured approaches, the simplest and most natural is *neuron pruning*, in which entire hidden units are removed, effectively deleting rows (and corresponding columns) of the network's weight matrices. Understanding the expressive power and limitations of neuron pruning is therefore essential for bridging theoretical guarantees with practically meaningful efficiency gains. In contrast to weight pruning, the role of neuron pruning has received comparatively little theoretical attention. This is not accidental: Malach et al. [2020] explicitly observed that neuron pruning appears fundamentally weaker than weight pruning, and pointed to results on random feature models to support this claim. In particular, Yehudai and Shamir [2019] showed that there exist target ReLU neurons with bias for which approximation by random features is provably hard: unless one allows either an exponential number of random features or exponentially large coefficients, uniform approximation over standard Gaussian inputs is impossible. Subsequent work strengthened this result by showing with a similar proof strategy that even when the magnitude of the coefficients is unrestricted, approximating such target ReLU neurons still requires an exponential number of random features [Kamath et al., 2020]. This impossibility results are proved under the assumption that the target ReLU neuron may have a bias as large as $O(d^4)$, where $d$ is the dimension of the input. It therefore leaves open the possibility that the observed hardness of approximation is driven, at least
in part, by this bias assumption rather than by an inherent limitation of neuron-pruning<fnref n="1" />.
This raises the following natural questions: *does the inefficiency of neuron pruning persist when one rules out biases? What is the dependency of neuron pruning w.r.t. ε?*

**1.1 Our Contribution**

In this work, we revisit neuron pruning in a clean and natural setting. We focus on approx-
imating a single ReLU neuron using a larger randomly initialized ReLU network with one
hidden layer, where both the target neuron and the hidden neurons have zero bias. This set-
ting isolates the expressive limitations of neuron pruning from confounding effects caused by
large biases. Importantly, approximating a single neuron is arguably the simplest nontrivial
approximation task, so lower bounds in this regime already indicate fundamental limita-
tions of neuron pruning. Our main result is a lower bound showing that to $\epsilon$-approximates
a single ReLU bias-free neuron through neuron pruning, the starting network must contain
$\Omega(d/\epsilon)$ hidden neurons (Theorem 1). This effectively establishes an exponential separation
between weight and neuron pruning, as existing results show that weight pruning achieves
$\epsilon$-approximation with only $O(d \log(1/\epsilon))$ hidden neurons. This underscores the importance
of distinguishing between different forms of sparsification when analyzing overparameterized
neural networks.

At a technical level, to handle the bias-free setting, we adopt a novel proof strategy in which we track the location of hidden units' nonlinearities along carefully constructed input families and derive necessary conditions for successful approximation. We then reformulate these conditions as hitting events of suitable stochastic processes, whose hitting probabilities yield bounds on the success probability of approximation.

**2 Related Work**

After the Lottery Ticket Hypothesis was introduced in Frankle and Carbin [2018], a large
body of empirical work has investigated algorithms for identifying such subnetworks, includ-
ing pruning strategies that learn masks or importance scores for individual weights without
changing their initial values [Zhou et al., 2019, Ramanujan et al., 2020, Wang et al., 2020].
These empirical results lead to the Strong Lottery Ticket Hypothesis (SLTH), which claims
that pruning alone can reveal subnetworks that approximate some target network. The
first rigorous SLTH guarantees were obtained by Malach et al. [2020], who showed that
sufficiently overparameterized random ReLU networks contain accurate subnetworks with
high probability. Subsequent works [Orseau et al., 2020, Pensia et al., 2020] refined these
guarantees by reducing the required overparameterization and extending the framework to
broader architectural settings. In particular, Pensia et al. [2020] established that logarith-
mic overparameterization in the approximation accuracy $\epsilon$ is sufficient for dense networks
through connections with the random subset sum problem. Later works extended these
results to convolutional and residual architectures [da Cunha et al., 2022, Burkholz, 2022a,
da Cunha et al., 2023] and to more general equivariant architectures [Ferbach et al., 2022].
Further refinements addressed broader activation functions, reduced depth overhead, and
introduced notions such as universal lottery tickets [Burkholz, 2022b, Burkholz et al., 2022,
Fischer et al., 2022].

Despite strong theoretical progress for weight pruning, unstructured sparsity does not
directly translate into computational speedups on modern hardware. This limitation has
motivated extensive research on structured pruning methods, which remove entire blocks of
parameters such as channels or neurons. Early works related to structured pruning include
classical studies on estimating the relevance of individual hidden units and removing those

<footnote n="1">¹The proof in Yehudai and Shamir [2019] relies on the presence of such a bias, and removing this as-
sumption would require a fundamentally different proof strategy, as confirmed by the authors via private
communication.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 1: A target ReLU neuron $f$, a random network $g$ with $N_h = 5$ hidden neurons, and a network $g_S$ obtained from $g$ through neuron pruning, by only keeping a subset $S$ of hidden units. The input dimension is $d = 2$, and each hidden unit $i$ in $g$ has incoming weights $\mathbf{w}_i \in \mathbb{R}^2$ (not written) and an output coefficient $\alpha_i \in \mathbb{R}$.</figcaption></figure>

deemed unimportant [Mozer and Smolensky, 1988, 1989]. Since then, structured pruning has developed into a broad research direction, particularly for convolutional architectures; we refer to the surveys in [Hoefler et al., 2021, He and Xiao, 2023] for comprehensive overviews. This line of work predominantly focuses on designing pruning algorithms and studying their empirical efficiency. By contrast, structured pruning has received little attention within the SLTH literature. Some recent works have established SLTH guarantees for some forms of structured convolutional pruning using multidimensional extensions of random subset sum techniques [da Cunha et al., 2023]. However, understanding the expressive power of the simplest structured pruning strategy—neuron pruning—remains largely open.

In particular, Malach et al. [2020] observed that neuron pruning appears intrinsically weaker than weight pruning, by using previous results [Yehudai and Shamir, 2019] on random features model. In a random features model, hidden weights are fixed and only output coefficients can be trained. Indeed, if the output coefficients associated with retained neurons were allowed to be refitted after pruning, neuron pruning would reduce to selecting a subset of random features and learning their linear combination. Neuron pruning in the SLTH setting is strictly more restrictive, as both the hidden weights and output coefficients are inherited from the original random network and cannot be changed. Several works have established strong lower bounds for random feature models that highlight intrinsic approximation limitations. In particular, Yehudai and Shamir [2019] showed that approximating certain ReLU neurons with bias using random features requires either exponentially many features or exponentially large coefficients under Gaussian inputs. This result was further strengthened in Kamath et al. [2020], which proved exponential lower bounds even when the magnitude of output coefficients is unrestricted. More lower bounds for random feature models were also established in Hsu et al. [2021], with a focus on approximating smooth functions. However, the aforementioned results rely on target neurons with large biases, and it remains unclear to what extent such assumptions are necessary or whether similar barriers arise in bias-free settings. These thus provide indirect evidence that neuron pruning may face fundamental limitations compared to weight pruning.

# 3 Preliminaries and Setup

In this work, vectors are denoted in boldface (e.g., $\mathbf{x}, \mathbf{w}$), while scalars are written in regular font. For vectors $\mathbf{u}, \mathbf{v} \in \mathbb{R}^d$, we write $\langle \mathbf{u}, \mathbf{v} \rangle$ for their dot product. We use $\sigma(t) := \max\{t, 0\}$ to denote the ReLU activation function. When we say that a function $h: \mathbb{R} \to \mathbb{R}$ is *linear* on an interval, we mean that it coincides on that interval with an *affine* function of the form $t \mapsto at + b$, for some $a, b \in \mathbb{R}$.

In Section 4, we study the problem of approximating a single target ReLU neuron using
a larger randomly initialized neural network g, solely by pruning neurons in the hidden layer. Specifically, we consider a bias-free two-layer ReLU network of the form g(x) = $\sum_{i=1}^{N_h} \alpha_i \sigma(\langle w_i, x \rangle)$, where x ∈ ℝ$^d$, with hidden-layer neuron weights w_i ∈ ℝ$^d$ and output weights α_i ∈ ℝ. Figure 1 provides a visual overview of the neuron pruning setting and the notation we use.

The target function we will consider in our work is a single bias-free ReLU neuron $f(\mathbf{x}) := \sigma(\langle \mathbf{w}^*, \mathbf{x} \rangle)$, with $\|\mathbf{w}^*\|_2 = 1$. A neuron-pruned subnetwork $g_S$ is obtained from g by selecting a subset $S \subseteq \{1, \dots, N_h\}$ of hidden units and retaining exactly those neurons with all their incident edges, yielding $g_S(\mathbf{x}) = \sum_{i \in S} \alpha_i \sigma(\langle \mathbf{w}_i, \mathbf{x} \rangle)$. In line with the Strong Lottery Ticket Hypothesis, pruning is the only operation allowed: the retained weights are not trained or modified.

Throughout the paper, we will often use the following notion of ε-approximation.

**Definition 1** (ε-approximation). For ε > 0 and radius R ≥ 1, we say that a function h ε-approximates another function f on the ball of radius R if $\sup_{\|x\|_2 \le R} |h(x) - f(x)| \le \varepsilon$.

## 4 Main Result

Theorem 1 shows that, in a one hidden layer random network, neuron pruning alone cannot even uniformly ε-approximate a single target ReLU neuron without bias, unless the initial width is at least of the order of (d/ε). This section presents a sketch of the proof of the theorem, in which we introduce the main ideas and provide an overview of the argument, referring the reader to Section 5 for the complete, detailed proof.

**Theorem 1** (Lower bound for neuron pruning). Let $d \ge 2$, $\varepsilon \in (0, 1)$, and let $\mathbf{w}^* \in \mathbb{R}^d$ with $\|\mathbf{w}^*\|_2 = 1$. Consider a one hidden-layer ReLU network without bias of the form

$$g(\mathbf{x}) = \sum_{i=1}^{N_h} \alpha_i \sigma(\langle \mathbf{w}_i, \mathbf{x} \rangle),$$

where the weights $\{\mathbf{w}_i\}_{i=1}^{N_h}$ are drawn independently from $\mathcal{N}(0, I_d)$, the coefficients $\{\alpha_i\}_{i=1}^{N_h}$ are drawn independently from $\mathcal{N}(0, 1)$, and $\mathbf{x} \in \mathbb{R}^d$. Then, there exists a universal constant $c > 0$ such that, if $N_h < \min\{c\varepsilon, 2^{cd}\}$, then with probability at least $1 - e^{-\Omega(d)}$ over the joint draw of $\{(\mathbf{w}_i, \alpha_i)\}_{i=1}^{N_h}$, for every subset $S \subseteq \{1, \dots, N_h\}$ and a fixed constant $R > 2$,

$$\sup_{\|x\|_2 \le R} \left| \sum_{i \in S} \alpha_i \sigma(\langle \mathbf{w}_i, \mathbf{x} \rangle) - \sigma(\langle \mathbf{w}^*, \mathbf{x} \rangle) \right| \ge C\varepsilon,$$

for some universal constant $C > 0$.

*Proof Idea.* As neuron pruning may retain any number $k \in \{1, \dots, N_h\}$ of hidden units, we begin in Section 5.1 by controlling the probability of successful approximation uniformly over all possible pruned network sizes. This is achieved via a union bound over k, which reduces the analysis to bounding, for a fixed k, the probability $p_k$ that a random network with k hidden units ε-approximates the target.

Our analysis is then based on tracking the evolution of breakpoints—the locations at which ReLU activations of the hidden neurons change slope—along carefully chosen one-dimensional input families, as described in Section 5.2. When a high-dimensional ReLU network is restricted to such paths, both the target function and the approximating network reduce to piecewise-linear functions whose behavior is entirely determined by the number, location, and interaction of these breakpoints. Crucially, these breakpoints impose necessary conditions for approximation. Definition 2 formalizes when a breakpoint induces a non-negligible approximation error. Lemma 1 shows that the presence of a breakpoint away from the target nonlinearity prevents ε-approximation, while Lemma 2 establishes that at
least one breakpoint must be placed within an ε-neighborhood of the target nonlinearity. Together, these results imply that successful neuron pruning requires introducing exactly one suitably aligned breakpoint and canceling all others.

We formalize this constraint by viewing neuron pruning as a stochastic sequential process in which neurons are selected one by one and the number of unresolved breakpoints evolves over time. The resulting process, faithfully captures the breakpoint dynamics induced by pruning. To make this process tractable, we construct a sequence of couplings: first to a capped process that limits the total number of breakpoints, and then to a homogeneous birth-death process (Sections 5.4 and 5.5). Each coupling is designed so that the dominating process is strictly more favorable to successful approximation, and therefore yields an upper bound on the success probability of the original pruning process.

The above argument bounds allows us to derive an upper bound for the ε-approximation of a single one-dimensional input family (Lemma 7). To obtain dimension-dependent bounds, we exploit the fact that our construction uses ⌊d/2⌋ input families supported on disjoint coordinate pairs. The induced breakpoint processes are independent across these families, and therefore the overall success probability decays exponentially in the input dimension d (Lemma 8); see also Figure 2 in Appendix A for a visual intuition.

Finally, Section 5.6 combines these bounds on p_k with the initial union bound over all pruned subnetworks, yielding the stated lower bound on the number of hidden neurons required for neuron pruning to achieve ε-approximation with non-negligible probability. □

Theorem 1 requires input dimension d ≥ 2. Notice that, for d = 1, neuron pruning reduces to weight pruning, as removing a hidden neuron is equivalent to pruning the single weight connecting that neuron to the input; in this setting, we can directly use the pruning lower bound proved in Pensia et al. [2020].

# 5 Proof of Theorem 1

In this section, we prove Theorem 1. Because of space constraints, some proofs of intermediate results are omitted and given in Appendix B.

## 5.1 Union bound over all pruned subnetworks

For $k \in \{1, \dots, N_h\}$, pruning the network g down to k hidden neurons produces $\binom{N_h}{k}$ distinct subnetworks. Let $E_k$ be the event that is a k-neuron pruned subnetwork that ε-approximates the target, and let $p_k := \Pr(\text{a fixed } k\text{-neuron network } \epsilon\text{-approximates the target})$. Then, by a union bound,

$$ \Pr\left(\bigcup_{k=1}^{N_h} E_k\right) \le \sum_{k=1}^{N_h} \binom{N_h}{k} p_k. \qquad (1) $$

The rest of the proof is devoted to quantifying the probability $p_k$.

## 5.2 Restriction over simple input families

We introduce some simple families of inputs that will be used to derive necessary conditions on the function g for neuron pruning to succeed. For each index $i \in \{1, \dots, \lfloor d/2 \rfloor\}$ define the d-dimensional input family $\mathbf{x}_i(t) := (0, \dots, 0, \underbrace{t}_{(2i-1)}, \underbrace{1}_{(2i)}, 0, \dots, 0), t \in \mathbb{R}$. That is, the

family $\mathbf{x}_i(t)$ has exactly two nonzero coordinates: a variable entry $t$ in position $2i-1$ and a fixed entry 1 in position $2i$. There are ⌊d/2⌋ such families, supported on disjoint pairs of coordinates.
Recall that $\mathbf{w}^* = (w_1^*, \dots, w_d^*) \in \mathbb{R}^d$ denotes the target weight vector. Along the input path $\mathbf{x}_i(t)$, the output of the target neuron is

$$f(\mathbf{x}_i(t)) = \sigma(\langle \mathbf{w}^*, \mathbf{x}_i(t) \rangle) = \sigma(w_{2i-1}^* t + w_{2i}^*),$$

which defines a one-dimensional piecewise-linear function of $t$ with a single breakpoint $t_i^* := -\frac{w_{2i}^*}{w_{2i-1}^*}$. On one side of $t_i^*$ the function is affine with slope $w_{2i-1}^*$, and on the other side it is identically zero.

Similarly, for the randomly initialized network $g(x)$, for each hidden neuron $j$ with weight vector $\mathbf{w}_j = (w_{j,1}, \dots, w_{j,d})$, and for each input family $\mathbf{x}_i(t)$, we have

$$\sigma(\langle \mathbf{w}_j, \mathbf{x}_i(t) \rangle) = \sigma(w_{j, 2i-1} t + w_{j, 2i}).$$

Each hidden neuron $j$ therefore introduces its own breakpoint $t_{i,j} := -\frac{w_{j, 2i}}{w_{j, 2i-1}}$ for the input family $\mathbf{x}_i(t)$. Consequently, given a subset $S \subseteq \{1, \dots, N_h\}$ of hidden neurons, the restriction $g_S(\mathbf{x}_i(t))$ of the pruned network $g_S$ on the input family $\mathbf{x}_i(t)$ yields a piecewise-linear function of $t$, whose breakpoints are induced by the neurons in $S$.

## 5.3 Breakpoints and necessary conditions for approximation

To analyze the probability $p_k$, it is convenient to view neuron pruning as a sequential selection process in which the $k$ neurons that are kept in the final subnetwork are chosen one at a time.

Fix an index $i \in \{1, \dots, \lfloor d/2 \rfloor\}$ and consider the restriction of the network to the input family $\mathbf{x}_i(t)$ introduced above, in which each hidden neuron induces a single breakpoint at a location determined by its weights.

As neurons are selected sequentially, each newly added neuron can have one of the following effects on the breakpoint structure of the current partial sum of chosen neurons for the input family $\mathbf{x}_i(t)$: (i) it may introduce a new breakpoint, (ii) it may cancel an existing breakpoint through interaction with previously selected neurons, or (iii) it may leave the breakpoint structure unchanged.

After all $k$ neurons have been selected, the restriction of the resulting pruned network to $\mathbf{x}_i(t)$ is a piecewise-linear function whose breakpoints are entirely determined by the selected neurons.

Since we are interested in inputs $x$ satisfying $\|x\|_2 \le R$, for an input family $\mathbf{x}_i(t)$ this restriction implies $|t| \le \sqrt{R^2 - 1}$. Consequently, only breakpoints lying in the interval $I_R = [-\sqrt{R^2 - 1}, \sqrt{R^2 - 1}]$ can affect the approximation error on bounded inputs. Breakpoints outside this interval have no effect and will therefore be ignored and not counted.

We partition $I_R$ into $\frac{R}{\epsilon}$ subintervals (bins) $I_{B_1}, \dots, I_{B_{\frac{R}{\epsilon}}}$ of length $\epsilon$, and denote this partition by $P_{\epsilon}$. Given a subset $S \subseteq \{1, \dots, N_h\}$ of hidden neurons, we say that a generic bin $I_B \in P_{\epsilon}$ is broken for $g_S$ and input family $\mathbf{x}_i(t)$ if $g_S(\mathbf{x}_i(t))$ is non-linear in $I_B$ (see Definition 2 for a formal statement). Bins that contain only canceled breakpoints, or no breakpoints at all, are considered unbroken.

**Definition 2 (Broken bin).** Let $I_B \subset \mathbb{R}$ be an interval (bin) of length $\epsilon$, and let $h: I_B \to \mathbb{R}$ be a function. We say that $I_B$ is broken for $h$ if there exist three points $t_1 < t_2 < t_3$ in $I_B$ such that for every affine function $\ell(t) = at + b$, $\max_{j=1,2,3} |h(t_j) - \ell(t_j)| \ge c\epsilon$ for some universal constant $c > 0$.

By Lemma 1 and Lemma 2, $\epsilon$-approximation along the path $\mathbf{x}_i(t)$ requires the breakpoint structure of the pruned network to be aligned with that of the target: after selecting $k$ neurons, the only possible broken bin is the one containing the target breakpoint $t_i^*$, and no additional broken bins may occur.
**Lemma 1** (Broken bin prevents approximation). Let $f(t) := \sigma(at + b)$, with $a \neq 0$, and let $I_B \subset \mathbb{R}$ be an interval of length $\varepsilon$ such that the breakpoint $t^* := -b/a$ satisfies $t^* \notin I_B$. Let $h: \mathbb{R} \to \mathbb{R}$ be any function. If $I_B$ is broken for $h$ in the sense of Definition 2, then $\sup_{t \in B} |f(t) - h(t)| \geq c\varepsilon$, for a universal constant $c > 0$.

**Lemma 2** (A breakpoint is necessary for approximation). Let $f(t) := \sigma(at + b)$, $a \neq 0$, and let $t^* := -b/a$ be its breakpoint. Let $h: \mathbb{R} \to \mathbb{R}$ be a function that is linear on an interval $I$ containing $[t^* - \delta, t^* + \delta]$ for some $\delta > 0$. Then, there exists a constant $c = c(a) > 0$ such that $\sup_{t \in [t^* - \delta, t^* + \delta]} |f(t) - h(t)| \geq c\delta$.

It is convenient to rephrase the necessary $\varepsilon$-approximation conditions derived from Lemma 1 and Lemma 2 in an alternative form that simplifies the following analysis. Rather than viewing the goal as approximating the target ReLU itself, we conceptually start from a mirrored version of the target along $\mathbf{x}_i(t)$, obtained by flipping its output sign while preserving the same breakpoint location $t_i^*$. This mirrored function induces exactly one broken bin, namely the bin containing $t_i^*$. A neuron whose breakpoint lies in this same bin and whose slope jump is suitably close to the target's slope will cancel the mirrored breakpoint, so that their sum is linear on the bin and hence the bin becomes unbroken.

From this viewpoint, successful $\varepsilon$-approximation on the input family $\mathbf{x}_i(t)$ is equivalent to starting from a configuration with a single broken bin (in which the target breakpoint lies) and requiring that, after selecting $k$ neurons, no broken bins remain. We adopt this reformulation throughout the remainder of the proof: the bin containing $t_i^*$ is treated as initially broken, and we consider approximation to be successful only if after selecting $k$ neurons we have no broken bins.

Using this reformulation, we now describe the sequential selection of $k$ neurons as a stochastic process that tracks the number of broken bins. As we will introduce other stochastic processes later in the proof, we will refer to this one as the original pruning process. For each step $s = \{1, \dots, k\}$, a new neuron is added and it may increase by one, decrease by one, or leave unchanged the number of broken bins in $\mathcal{P}_\varepsilon$, depending of where its breakpoint falls. Since we treat the bin containing $t_i^*$ as initially broken, the starting number of broken bins at step $s = 0$ will be one.

**Definition 3.** We define $B_s^{\text{orig}}$ as the number of broken bins after having selected $s$ neurons in the original pruning process, with $B_0^{\text{orig}} = 1$.

As noted above, for a successful $\varepsilon$-approximation on the input family $\mathbf{x}_i(t)$, we want to have $B_k^{\text{orig}} = 0$. Now consider all $\lfloor d/2 \rfloor$ disjoint input families $\mathbf{x}_i(t)$. For the overall approximation to be successful, we need to have $B_k^{\text{orig}} = 0$ for all such families. By construction, the breakpoints $t_{i,j}$ are independent across all $\lfloor d/2 \rfloor$ families $\mathbf{x}_i(t)$, so $p_k \le \prod_{i=1}^{\lfloor d/2 \rfloor} \Pr(B_k^{\text{orig}} = 0)$, which gives the following.

**Lemma 3.** It holds $p_k \le (\Pr(B_k^{\text{orig}} = 0))^{\lfloor d/2 \rfloor}$.

## 5.4 Construction of a dominating capped process

In this section, we introduce a simplified process that stochastically dominates the original pruning process described in Section 5.3, in the sense that it produces fewer broken bins. Analyzing this simplified process will yield an upper bound on the probability that the original pruning procedure succeeds. As in the previous section, fix an index $i \in \{2, \dots, d\}$ and consider the restriction of the network to the input family $\mathbf{x}_i(t)$.

We define a capped process, analogous to the original pruning process defined in Section 5.3, except for the fact that the number of broken bins is constrained not to exceed a fixed threshold. Fix an integer $T \in \{1, \dots, k\}$. The number $B_s^{\text{cap}}$ of broken bins in the capped process after selecting $s$ neurons, for $s \in \{1, \dots, k\}$, is updated according to these rules:
* If $B_s^{\text{cap}} < T$, as for the original process, $B_s^{\text{cap}}$ may increase by one if the newly selected neuron introduces a breakpoint that breaks a previously unbroken bin; it may decrease by one if the neuron introduces a breakpoint that cancels an existing one; otherwise, $B_s^{\text{cap}}$ remains unchanged.

* If $B_s^{\text{cap}} = T$, then even if breakpoint falls into a previously unbroken bin, we do not increase $B_s^{\text{cap}}$ further; $B_s^{\text{cap}}$ may still decrease if cancellations happen.

By construction, after having selected $s$ shared neurons, if we look at the capped and original processes we have

$$B_s^{\text{cap}} \le B_s^{\text{orig}}, \quad \forall s \in \{1, \dots, k\} \qquad (2)$$

The capped process is more favorable to maintaining a small number of broken bins. Consequently, the probability that the original pruning process reaches 0 broken bins after $k$ steps is upper bounded by the corresponding probability for the capped process. In particular, from eq. (2), we have the following upper bound on the probability of a successful $\varepsilon$-approximation for a random network with $k$ hidden neurons.

**Lemma 4.** It holds $\Pr(B_k^{\text{orig}} = 0) \le \Pr(B_k^{\text{cap}} = 0)$.

## 5.5 Construction of a dominating birth-death process

In the capped process described in Section 5.4, the probability that a selected neuron creates a new broken bin depends on the current number and locations of broken bins. For example, this probability is high when few bins are broken and lower when most are already broken. This dependence makes the exact process difficult to analyze. To simplify the analysis, we introduce a homogeneous birth-death process that we will use to upper bound $\Pr(B_k^{\text{cap}} = 0)$.

**Definition 4.** A $(q, p, T)$-chain $(B_s^{\text{bd}})_{s \ge 0}$ is a birth-and-death process on a state space $\{0, 1, \dots, T\}$ such that $B_0^{\text{bd}} = 1$ and

* from any state $b < T$, it transitions from state $b$ to $b+1$ with probability $p$;

* from any state $b > 0$, it transitions from state $b$ to $b-1$ with probability $q$;

* otherwise, it remains at $b$.

Similarly to what we did in section Section 5.4, where we introduced a capped process that keeps a lower number of broken bins than the original pruning process, here we want to choose a triple $(q, p, T)$ such that the associated $(q, p, T)$-chain $(B_s^{\text{bd}})_{s \ge 0}$ stochastically dominates the capped process, in the sense that, for a suitable coupling, we have

$$B_s^{\text{bd}} \le B_s^{\text{cap}}, \quad \forall s \in \{1, \dots, k\} \qquad (3)$$

To achieve this, we can choose $p$ as a lower bound on the probability of introducing a new broken bin in the capped process, and $q$ as an upper bound on the probability of removing a broken bin, both uniformly over all steps $s \in \{1, \dots, k\}$. Such a choice ensures that eq. (3) holds and we get the following.

**Lemma 5.** It holds $\Pr(B_k^{\text{cap}} = 0) \le \Pr(B_k^{\text{bd}} = 0)$.

As far as the choice of the maximum number $T$ of broken bins goes, what we want is to keep it somehow smaller than the total number of bins, in such a way that in the capped process the probability of introducing a broken bin is always more likely than removing one. Let us fix, for a sufficiently large constant $c > 0$,

$$T = \frac{R}{c\varepsilon}. \qquad (4)$$

We now make more precise the choice of the probability $p$. Since the total number of bins is $\Theta(R/\varepsilon)$, as long as $b < T$, the fraction of broken bins is at most $1/c$, and the fraction
of unbroken bins is at least $1 - 1/c$. By Lemma 6, there exists a constant $\gamma > 0$ such that if a bin contains a single well-placed breakpoint with slope jump $|\Delta| \ge \gamma$, then that bin is broken in the sense of Definition 2, where “well-placed” means that the breakpoint is not too close to the boundaries of the bin, as specified in Lemma 6. Since the slope of a neuron on a given input family is determined by a single weight of the initial random network $g$, which is distributed as a standard Gaussian, there exists a constant $c_2 > 0$ such that the slope jump $\Delta$ of a newly sampled neuron satisfies $|\Delta| \ge \gamma$ with probability at least $c_2$.

Note that the fraction of unbroken bins where a breakpoint would be well-placed is at least $c_1 > 0$, for some constant $c_1$. Moreover, recall that only breakpoints in the interval $I_R$ matter, and since a neuron’s breakpoint is the ratio of two independent standard Gaus- sians—hence Cauchy with continuous positive density on $\mathbb{R}$—there exists $c_3 > 0$ such that a newly sampled neuron has its breakpoint in $I_R$ with probability at least $c_3$.

We conclude that with probability at least $p_0 := c_1c_2c_3 > 0$, uniformly over all steps, the newly added neuron has a breakpoint falling in a suitable location of an unbroken bin and induces a slope jump of magnitude at least $\gamma$, which by Lemma 6 causes that bin to become broken. Therefore, we can set $p = p_0$.

**Lemma 6 (A single sufficiently steep neuron breaks a bin).** There exist universal constants $\gamma, c > 0$ such that the following holds. Let $B = [u, u + \varepsilon]$ be an interval, and let $h: B \to \mathbb{R}$ be a piecewise-linear function with exactly one breakpoint $t_0 \in B$. Assume that the left and right slopes at $t_0$ satisfy $|m_+-m_-| \ge \gamma$. Then, $B$ is broken for $h$ in the sense of Definition 2.

On the other hand, the fraction of broken bins is at most $1/c$. Even assuming that cancellation always succeeds when a breakpoint falls inside a broken bin (i.e., the bin becomes unbroken), choosing $c$ in eq. (4) sufficiently large ensures the existence of a constant $q_0 < \min\{1/3, p_0/2\}$ such that, with probability at most $q_0$, uniformly over all steps, a newly added neuron changes a bin from broken to unbroken. We can then set $q = q_0$.

The resulting birth–death process stochastically dominates the capped process in favor of successful approximation, and thus provides an upper bound on the probability that neuron pruning yields a network $g_S$ that $\varepsilon$-approximates the target ReLU.

We can now finally bound the probability $\text{Pr}(B_k^{bd} = 0)$ of such a $(p, q, T)$-chain to be in state 0 after $k$ steps, which by Lemma 5 gives us an upper bound on the probability of a successful $\varepsilon$-approximation.

A crucial part of the proof is now to show the following, which we prove via an elegant use of total probabilities. Because of space constraints, the proof is deferred to the appendix.

**Lemma 7.** It holds $\text{Pr}(B_k^{bd} = 0) \le e^{-\Omega(\min(k, T))}$.

With Lemma 7, we now have all the ingredients to establish an exponential upper bound for $p_k$. Combining Lemmas 3 to 5 and 7 yields the following.

**Lemma 8.** It holds $p_k \le e^{-\Omega(\min(k, T)d)}$.

Lemma 8 gives the desired exponentially small upper bound on the probability of successful $\varepsilon$-approximation, as shown in the next section.

## 5.6 Back to the union bound

We now conclude the proof by returning to the union bound of eq. (1). We split the sum in two, depending on the value of $k$:

$$ \sum_{k=1}^{N_h} \binom{N_h}{k} p_k = \sum_{k=1}^{T-1} \binom{N_h}{k} p_k + \sum_{k=T}^{N_h} \binom{N_h}{k} p_k \quad (5) $$

From Lemma 8, we can prove the following.
**Lemma 9.** It holds

$$ \sum_{k=1}^{T-1} \binom{N_h}{k} p_k \le e^{-\Omega(d)} \quad \text{and} \quad \sum_{k=T}^{N_h} \binom{N_h}{k} p_k \le e^{-\Omega(d)}. \qquad (6) $$

From Lemma 9, we get that eq. (5) is at most $e^{-\Omega(d)}$, proving that with probability at least $1 - e^{-\Omega(d)}$, no neuron-pruned subnetwork $\varepsilon$-approximates the target ReLU uniformly on the unit ball. This completes the proof of Theorem 1.

# 6 Conclusion and Future Work

This work establishes a fundamental separation between neuron pruning and weight pruning within the framework of the Strong Lottery Ticket Hypothesis. While weight pruning is known to approximate a single ReLU neuron with polylogarithmic dependence on the approximation error $\varepsilon$, we show that neuron pruning incurs an intrinsic cost of order $\Omega(d/\varepsilon)$ hidden neurons. Our results therefore identify neuron pruning as a strictly weaker pruning mechanism from an approximation-theoretic perspective, even in the clean, bias-free setting.

An interesting open question concerns the optimal dependence on the input dimension $d$. Our lower bound scales linearly in $d$ (when $\varepsilon = \Omega(2^{-cd})$), whereas results for random feature models suggest that approximation may in fact require exponentially many neurons in $d$ when doing neuron pruning. We conjecture that a similar phenomenon should also hold for our simple neuron pruning scenario, and that even the trivial strategy of retaining a single neuron is asymptotically optimal, as a function of the dimension. For this simple setting, in which only a single neuron can be retained, we provide a proof of an exponential lower bound in $d$ in Appendix C. Establishing a dimension-dependent lower bound would further clarify the limitations of neuron pruning and strengthen the separation with weight pruning. We leave this question, as well as extensions to deeper architectures and other activation functions, for future work.

# References

* Rebekka Burkholz. Convolutional and Residual Networks Provably Contain Lottery Tickets. In *Proceedings of the 39th International Conference on Machine Learning*, pages 2414–2433, Baltimore, July 2022a. PMLR.

* Rebekka Burkholz. Most Activation Functions Can Win the Lottery Without Excessive Depth. In *Thirty-Sixth Conference on Neural Information Processing Systems*, December 2022b.

* Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos. On the Existence of Universal Lottery Tickets. In *International Conference on Learning Representations*, virtual, April 2022.

* Arthur da Cunha, Emanuele Natale, and Laurent Viennot. Proving the Strong Lottery Ticket Hypothesis for Convolutional Neural Networks. In *ICLR 2022 - 10th International Conference on Learning Representations*, Virtual, France, April 2022.

* Arthur da Cunha, Francesco D'Amore, and Emanuele Natale. Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets. In *Thirty-Seventh Conference on Neural Information Processing Systems*, November 2023.

* Damien Ferbach, Christos Tsirigotis, Gauthier Gidel, and Joey Bose. A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis. In *The Eleventh International Conference on Learning Representations*, September 2022.
Jonas Fischer, Advait Gadhikar, and Rebekka Burkholz. Lottery Tickets with Nonzero Biases, June 2022.

Jonathan Frankle and Michael Carbin. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. In *International Conference on Learning Representations*, September 2018.

Yang He and Lingao Xiao. Structured pruning for deep convolutional neural networks: A survey. *CoRR*, abs/2303.00566, 2023. doi: 10.48550/arXiv.2303.00566. URL https://doi.org/10.48550/arXiv.2303.00566.

Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. *J. Mach. Learn. Res.*, 22:241:1–241:124, 2021. URL http://jmlr.org/papers/v22/21-0366.html.

Daniel Hsu, Clayton Sanford, Rocco A. Servedio, and Emmanouil V. Vlatakis-Gkaragkounis. On the approximation power of two-layer networks of random relus. In Mikhail Belkin and Samory Kpotufe, editors, *Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA*, volume 134 of *Proceedings of Machine Learning Research*, pages 2423–2461. PMLR, 2021. URL http://proceedings.mlr.press/v134/hsu21a.html.

Pritish Kamath, Omar Montasser, and Nathan Srebro. Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In *Conference on Learning Theory*, pages 2236–2262. PMLR, 2020.

George S. Lueker. Exponantially small bounds on the expected optimum of the partition and subset sum problem. *Random Structures and Algorithms*, 12:51–62, 1998.

Eran Malach, Gilad Yehudai, Shai Shalev-shwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In *Proceedings of the 37th International Conference on Machine Learning*, ICML’20, pages 6682–6691. JMLR.org, July 2020.

Michael C. Mozer and Paul Smolensky. Skeletonization: a technique for trimming the fat from a network via relevance assessment. In *Proceedings of the 2nd International Conference on Neural Information Processing Systems*, NIPS’88, page 107–115, Cambridge, MA, USA, 1988. MIT Press.

Michael C Mozer and Paul Smolensky. Using relevance to reduce network size automatically. *Connection Science*, 1(1):3–16, 1989.

Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. In *Proceedings of the 34th International Conference on Neural Information Processing Systems*, NIPS’20, pages 2925–2934, Red Hook, NY, USA, December 2020. Curran Associates Inc. ISBN 978-1-71382-954-6.

Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subsetsum: logarithmic over-parameterization is sufficient. In *Proceedings of the 34th International Conference on Neural Information Processing Systems*, NIPS ’20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.

Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What’s Hidden in a Randomly Weighted Neural Network? In *2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)*, pages 11890–11899, June 2020. doi: 10.1109/CVPR42600.2020.01191.
Yulong Wang, Xiaolu Zhang, Lingxi Xie, Jun Zhou, Hang Su, Bo Zhang, and Xi-
aolin Hu. Pruning from scratch. *Proceedings of the AAAI Conference on Artifi-
cial Intelligence*, 34(07):12273-12280, Apr. 2020. doi: 10.1609/aaai.v34i07.6910. URL
https://ojs.aaai.org/index.php/AAAI/article/view/6910.

Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. CoRR, abs/1904.00687, 2019. URL http://arxiv.org/abs/1904.00687.

Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask. In *Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 (NIPS 2019)*, page 3592-3602, 2019.
## A Additional Figures

<figure><img src="image_4.png" /><figcaption>Figure 2: Stacked state-line representation of the birth–death chain $(B_s^{bd})_{s \ge 0}$. Each horizontal line is the state space $\{0, 1, \dots, T\}$ for one input family, and the filled dot marks the current value of $B_s^{bd}$. A necessary condition for $\epsilon$-approximation is that all $|d/2|$ independent chains reach state 0.</figcaption></figure>

## B Omitted Proofs

**Lemma 1** (Broken bin prevents approximation). Let $f(t) := \sigma(at + b)$, with $a \neq 0$, and let $I_B \subset \mathbb{R}$ be an interval of length $\epsilon$ such that the breakpoint $t^* := -b/a$ satisfies $t^* \notin I_B$. Let $h: \mathbb{R} \to \mathbb{R}$ be any function. If $I_B$ is broken for $h$ in the sense of Definition 2, then $\sup_{t \in B} |f(t) - h(t)| \ge c\epsilon$, for a universal constant $c > 0$.

*Proof.* Since $t^* \notin I_B$, the function $f$ is linear on $I_B$. By Definition 2, for any affine function $\ell$, there exist three points in $I_B$ on which $h$ differs from $\ell$ by at least $c\epsilon$. Taking $\ell = f$ yields the claim. $\square$

**Lemma 2** (A breakpoint is necessary for approximation). Let $f(t) := \sigma(at + b)$, $a \neq 0$, and let $t^* := -b/a$ be its breakpoint. Let $h: \mathbb{R} \to \mathbb{R}$ be a function that is linear on an interval $I$ containing $[t^* - \delta, t^* + \delta]$ for some $\delta > 0$. Then, there exists a constant $c = c(a) > 0$ such that $\sup_{t \in [t^* - \delta, t^* + \delta]} |f(t) - h(t)| \ge c\delta$.

*Proof.* By translation, we may assume $t^* = 0$, so that $f(t) = \sigma(at)$. Let $h(t) = \alpha t + \beta$ be any linear function. Consider the three points $t = -\delta$, $0$, $\delta$. At these points, $f(-\delta) = 0$, $f(0) = 0$, $f(\delta) = a\delta$ if $a > 0$, and the roles of $\pm\delta$ are reversed if $a < 0$. In either case, $|f(\delta) - f(-\delta)| = |a|\delta$. Define the errors $\Delta_- := h(-\delta) - f(-\delta)$, $\Delta_0 := h(0) - f(0)$, $\Delta_+ := h(\delta) - f(\delta)$. Since $h$ is linear, $h(0) = \frac{1}{2}(h(-\delta) + h(\delta))$, which implies $\Delta_0 = \frac{1}{2}(\Delta_- + \Delta_+ + |a|\delta)$ (up to relabeling the endpoints when $a < 0$).

If $|\Delta_-| < \frac{|a|\delta}{4}$ and $|\Delta_+| < \frac{|a|\delta}{4}$, then $\Delta_0 > \frac{1}{2}(-\frac{|a|\delta}{4} - \frac{|a|\delta}{4} + |a|\delta) = \frac{|a|\delta}{4}$, so $|\Delta_0| \ge \frac{|a|\delta}{4}$.

Therefore, at least one of $|\Delta_-|$, $|\Delta_0|$, $|\Delta_+|$ is at least $\frac{|a|\delta}{4}$, and hence

$$ \sup_{t \in [-\delta, \delta]} |f(t) - h(t)| \ge \frac{|a|\delta}{4}. $$

Taking $c = \frac{|a|}{4}$ concludes the proof. $\square$

<figure><img src="image_5.png" /></figure>
<figure><img src="image_6.png" /><figcaption>Figure 3: Breakpoint alignment intuition along a one-dimensional input family $\mathbf{x}_i(t)$. Along $\mathbf{x}_i(t)$, a bias-free ReLU neuron $\sigma(\langle w, x \rangle)$ reduces to the one-dimensional function $t \mapsto \sigma(w_{2i-1}t + w_{2i})$, whose breakpoint is $t_i(w) = -w_{2i}/w_{2i-1}$. The target (red) has breakpoint $t_i^*$, while a randomly drawn neuron (cyan) has breakpoint $t_{i,j}$. If $|t_{i,j} - t_i^*| > \varepsilon$, then on the $\varepsilon$-neighborhood of $t_i^*$ the cyan function is linear (in the picture, flat) whereas the target changes slope, yielding a nontrivial uniform error, as stated in Lemma 2.</figcaption></figure>

**Lemma 6** (A single sufficiently steep neuron breaks a bin). There exist universal constants $\gamma, c > 0$ such that the following holds. Let $B = [u, u + \varepsilon]$ be an interval, and let $h: B \to \mathbb{R}$ be a piecewise-linear function with exactly one breakpoint $t_0 \in B$. Assume that the left and right slopes at $t_0$ satisfy $|m_+ - m_-| \ge \gamma$. Then, $B$ is broken for $h$ in the sense of Definition 2.

*Proof.* Let $\Delta = \varepsilon/4$ and define three points $t_1 := t_0 - \Delta, t_2 := t_0, t_3 := t_0 + \Delta$, which all lie in $B$ for $\varepsilon$ small enough. Since $h$ is linear on each side of $t_0$, we have

$$ \frac{h(t_2) - h(t_1)}{t_2 - t_1} = m_{-}, \quad \frac{h(t_3) - h(t_2)}{t_3 - t_2} = m_{+}. $$

Let $\ell(t) = at + b$ be any affine function. Assume that $\ell$ fits the three points with error at most $\eta\varepsilon$, i.e., $|h(t_j) - \ell(t_j)| \le \eta\varepsilon$ for $j = 1, 2, 3$. We compare slopes. Since $\ell$ is affine,

$$ a = \frac{\ell(t_2) - \ell(t_1)}{t_2 - t_1}. $$

Thus,

$$ |a - m_{-}| = \left| \frac{(\ell(t_2) - h(t_2)) - (\ell(t_1) - h(t_1))}{t_2 - t_1} \right| \le \frac{2\eta\varepsilon}{\Delta} = 8\eta. $$

The same argument applied to $(t_2, t_3)$ gives $|a - m_+| \le 8\eta$. By the triangle inequality, $|m_+ - m_-| \le |m_+ - a| + |a - m_-| \le 16\eta$. Since $|m_+ - m_-| \ge \gamma$, this implies $\eta \ge \gamma/16$. Therefore, for every affine function $\ell$,

$$ \max_{j=1,2,3} |h(t_j) - \ell(t_j)| \ge \frac{\gamma}{16} \varepsilon. $$

Taking $c = \gamma/16$ concludes the proof. $\square$

**Lemma 7.** It holds $\mathrm{Pr}(B_k^{bd} = 0) \le e^{-\Omega(\min(k, T))}$.

*Proof.* Let $R_k$ and $L_k$ denote the number of right moves and left moves, respectively, during the $k$ steps of the process. A right move happens when a new broken bin is introduced, and a left move when it is removed. Then $B_k^{bd} = 1 + R_k - L_k$, which means that in order to
have $B_k^{bd} = 0$ we must have $L_k > R_k$. By the law of total probability, we thus have

$$
\begin{align*}
\Pr(B_k^{bd} = 0) &= \Pr(1 + R_k = L_k) \\
&\le \Pr(L_k > R_k) \\
&= \Pr(L_k > R_k | R_k < pk/2)\Pr(R_k < pk/2) + \\
&\qquad + \Pr(L_k > R_k | R_k \ge pk/2)\Pr(R_k \ge pk/2) \\
&\le \Pr(R_k < pk/2) + \Pr(L_k > R_k | R_k \ge pk/2) \\
&\le \Pr(R_k < pk/2) + \Pr(L_k \ge pk/2 | R_k \ge pk/2) \\
&\le \Pr(R_k < pk/2) + \Pr(L_k \ge pk/2), \tag{7}
\end{align*}
$$

where, in the last inequality, we used that conditioning on performing at least a certain number of right moves can only decrease the probability of performing at least a given number of left moves, since those moves cannot be to the left. More formally, if we define $h(r) := \Pr(L_k \ge pk/2 | R_k = r)$ we have

$$
\Pr\left(L_k \ge \frac{pk}{2}\right) = \sum_{r=0}^{k} h(r) \Pr(R_k = r) = \mathbb{E}[h(R_k)],
$$

and, similarly,

$$
\Pr\left(L_k \ge \frac{pk}{2} \mid R_k \ge \frac{pk}{2}\right) = \sum_{r=\frac{pk}{2}}^{k} h(r) \Pr\left(R_k = r \mid R_k \ge \frac{pk}{2}\right) = \mathbb{E}\left[h(R_k) \mid R_k \ge \frac{pk}{2}\right].
$$

Now, since $h(r)$ is a decreasing function of $r$, it follows that

$$
\mathbb{E}[h(R_k) \mid R_k \ge \frac{pk}{2}] \le \mathbb{E}[h(R_k)] \iff \Pr(L_k \ge \frac{pk}{2} \mid R_k \ge \frac{pk}{2}) \le \Pr(L_k \ge \frac{pk}{2}),
$$

justifying the last step in eq. (7).

Intuitively, eq. (7) states that the probability that the process ends in a state $B_k^{bd} = 0$ can be bounded by the event that the number of right moves is too small, or that the number of left moves is at least the number of right ones.

**Case 1:** $k \le 2T/3$. Since $k \le 2T/3$ the cap at $T$ of the birth-death process is never reached. Since each step produces a right move independently with probability $p$, then $\mathbb{E}[R_k] = pk$, and by a Chernoff bound $\Pr(R_k < pk/2) \le e^{-\Omega(k)}$. On the other hand, each step produces a left move with probability at most $q \le p/2$ is a constant. Hence $\mathbb{E}[L_k] \le q_0 k$. Applying a Chernoff bound to $L_k$, we obtain $\Pr(L_k \ge \frac{p}{2}k) \le e^{-\Omega(k)}$, hence

$$
\Pr(R_k < pk/2) + \Pr(L_k \ge pk/2) \le e^{-\Omega(k)}. \quad (8)
$$

**Case 2:** $k > 2T/3$. At step $\hat{k} = k - 2T/3$, there are two possibilities: either $B_k^{bd} \le T/3$ or $B_k^{bd} > T/3$. If $B_k^{bd} \le T/3$, then we can use the same argument as in Case 1 to bound the probability of success, as the cap at $T$ of the birth-death process will not be reached after $k$ steps. If $B_k^{bd} > T/3$, then the probability of reaching state 0 in the remaining $2T/3$ is bounded by the probability that the process does at least $T/3$ left moves, which is at most $e^{-\Omega(T)}$. Formally, we have

$$
\begin{align*}
\Pr(B_k^{bd} = 0) &\le \Pr(L_k > R_k) \\
&= \Pr\left(L_k > R_k \mid B_k^{bd} \le T/3\right) \Pr(B_k^{bd} \le T/3) + \\
&\qquad + \Pr\left(L_k > R_k \mid B_k^{bd} > T/3\right) \Pr(B_k^{bd} > T/3) \\
&\le \Pr\left(L_k > R_k \mid B_k^{bd} \le T/3\right) + \Pr\left(L_k > R_k \mid B_k^{bd} > T/3\right) \\
&\le \Pr\left(L_k - L_{\hat{k}} \ge R_k - R_{\hat{k}} \mid B_k^{bd} \le T/3\right) + \Pr\left(L_k - L_{\hat{k}} > T/3 \mid B_k^{bd} > T/3\right).
\end{align*}
$$
The first term in the last line are bounded by $e^{-\Omega(T)}$ as shown in Case 1 using similar arguments: note that starting at position larger than 1, only makes it less likely to reach 0. The second term is bounded by a standard Chernoff bound.

Putting both cases together, we get

$$ \mathrm{Pr} (B_k^{bd} = 0) \le e^{-\Omega(\min(k,T))}. \quad \square $$

**Lemma 9.** It holds

$$ \sum_{k=1}^{T-1} \binom{N_h}{k} p_k \le e^{-\Omega(d)} \quad \text{and} \quad \sum_{k=T}^{N_h} \binom{N_h}{k} p_k \le e^{-\Omega(d)}. \quad (6) $$

*Proof.* For $k \le T$, from Lemma 8 we get that $p_k \le e^{-c_4kd}$ for some constant $c_4 > 0$. Using the bound $\binom{N_h}{k} \le (eN_h/k)^k$, we obtain

$$ \sum_{k=1}^{T-1} \binom{N_h}{k} p_k \le \sum_{k=1}^{T-1} e^{-k(\log N_h - c_4d + O(1))} \stackrel{(a)}{\le} \sum_{k=1}^{T-1} e^{-\Omega(kd)} \stackrel{(b)}{\le} e^{-\Omega(d)}, \quad (9) $$

where in (a) we used that $\log N_h \le cd$, and in (b) we upper bounded $\sum_{k=1}^{T-1} e^{-\Omega(kd)} \le \sum_{k=1}^{\infty} (e^{-\Omega(d)})^k$ and used that $\sum_{k=1}^{\infty} x^k = \frac{x}{1-x}$.

For $k > T$, given Lemma 8 and the choice of $T$ in eq. (4), we get $p_k \le e^{-c_5d/\epsilon}$ for some constant $c_5 > 0$. Using the crude bound $\sum_{k>k_0} \binom{N_h}{k} \le 2^{N_h}$, we obtain

$$ \sum_{k=T}^{N_h} \binom{N_h}{k} p_k \le 2^{N_h} e^{-c_5 d / \epsilon} \le e^{-\Omega(d / \epsilon)} \le e^{-\Omega(d)}, \quad (10) $$

where in the last inequality we used the hypothesis $N_h \le cd/\epsilon$. $\square$

## C ReLU Approximation with a Single Neuron

**Lemma 10** (Single-neuron approximation requires exponential width). Given $\mathbf{w}^* \in \mathbb{R}^d$, with $\|\mathbf{w}^*\|_2 = 1$, let $f(\mathbf{x}) := \sigma(\langle \mathbf{w}^*, \mathbf{x} \rangle)$ be a target ReLU neuron without bias. Let $\mathbf{w}$ be sampled uniformly at random from the unit sphere $\mathbb{S}^{d-1}$, and consider approximations of the form

$$ g(\mathbf{x}) := a \sigma(\langle \mathbf{w}, \mathbf{x} \rangle), \quad a \in \mathbb{R}. $$

There exist universal constants $c, C > 0$ such that for any $\epsilon \in (0, 1)$,

$$ \mathrm{Pr} \left( \inf_{a \in \mathbb{R}} \sup_{\|\mathbf{x}\|_2 \le 1} |f(\mathbf{x}) - g(\mathbf{x})| \le \epsilon \right) \le (C\epsilon)^{cd}. $$

Consequently, if a width-$N_h$ random network is initialized with i.i.d. weights $\mathbf{w}_1, \dots, \mathbf{w}_{N_h} \sim \mathrm{Unif}(\mathbb{S}^{d-1})$ and only a single neuron may be retained, then achieving uniform $\epsilon$-approximation of $f$ with non-negligible probability requires $N_h \ge e^{\Omega(d)}$.

*Proof.* Fix $\epsilon \in (0, 1)$ and suppose that for some $a \in \mathbb{R}$,

$$ \sup_{\|\mathbf{x}\|_2 \le 1} \left| \sigma(\langle \mathbf{w}^*, \mathbf{x} \rangle) - a \sigma(\langle \mathbf{w}, \mathbf{x} \rangle) \right| \le \epsilon. \quad (11) $$

Evaluating (11) at $\mathbf{x} = \mathbf{w}^*$ yields

$$ |1 - a \sigma(\langle \mathbf{w}, \mathbf{w}^* \rangle)| \le \epsilon. $$
Since $\sigma(\langle \mathbf{w}, \mathbf{w}^* \rangle) \le 1$, this implies $|a| \ge 1 - \varepsilon$, and in particular $|a| = \Theta(1)$. Thus the scalar coefficient $a$ cannot compensate for a significant misalignment between $\mathbf{w}$ and $\mathbf{w}^*$.

Let $\theta \in [0, \pi]$ denote the angle between $\mathbf{w}$ and $\mathbf{w}^*$, so that $\langle \mathbf{w}^*, \mathbf{w} \rangle = \cos \theta$. Consider the two-dimensional subspace span{$\{\mathbf{w}^*, \mathbf{w}\}$}, and choose a unit vector $\mathbf{x}$ in this plane such that $\langle \mathbf{w}^*, \mathbf{x} \rangle = \sin \theta$ and $\langle \mathbf{w}, \mathbf{x} \rangle = 0$. Such a choice is always possible by elementary planar geometry. For this $\mathbf{x}$ we have $\sigma(\langle \mathbf{w}^*, \mathbf{x} \rangle) = \sin \theta$ and $\sigma(\langle \mathbf{w}, \mathbf{x} \rangle) = 0$, and therefore

$$|f(\mathbf{x}) - g(\mathbf{x})| = \sin \theta.$$

Combining with (11) yields

$$\sin \theta \le \varepsilon,$$

which implies $\theta \le 2\varepsilon$ for all sufficiently small $\varepsilon$.

Since $\mathbf{w}$ is uniformly distributed on $S^{d-1}$, the probability that $\angle(\mathbf{w}, \mathbf{w}^*) \le 2\varepsilon$ equals the normalized surface area of a spherical cap of half-angle $2\varepsilon$, where by $\angle(\mathbf{w}, \mathbf{w}^*)$ we denote the angle between the two vectors $\mathbf{w}$ and $\mathbf{w}^*$. It is standard that there exist universal constants $c, C > 0$ such that for all $\varepsilon \in (0, 1)$,

$$\Pr(\angle(\mathbf{w}, \mathbf{w}^*) \le 2\varepsilon) \le (C\varepsilon)^{c(d-1)}.$$

If $N_h$ neurons are sampled independently, a union bound shows that the probability that any single neuron can $\varepsilon$-approximate $f$ is at most $N_h(C\varepsilon)^{cd}$. Thus, unless $N_h \ge e^{\Omega(d)}$, this probability vanishes exponentially in $d$. $\square$