The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets
Authors: Yujun Kim
Chaewon Moon
Chulhee Yun
Venue: NeurIPS 2025 poster ()
Keywords: Robust memorization
Memorization
Adversarial training
Parameter Complexity
Primary area: theory
TL;DR: We analyze the parameter bounds for robust memorization as a function of the robustness ratio.

Abstract: We study the parameter complexity of robust memorization for ReLU networks: the number of parameters required to interpolate any dataset with $\epsilon$-separation between differently labeled points, while ensuring predictions remain consistent within a $\mu$-ball around each training example. We establish upper and lower bounds on the parameter count as a function of the robustness ratio $\rho = \mu / \epsilon$. Unlike prior work, we provide a fine-grained analysis across the entire range $\rho \in (0,1)$ and obtain tighter upper and lower bounds that improve upon existing results. Our findings reveal that the parameter complexity of robust memorization matches that of non-robust memorization when $\rho$ is small, but grows with increasing $\rho$. As a special case, when the input dimension is comparable to or exceeds the dataset size, our bounds become tight (up to logarithmic factors) across the entire range of $\rho$.

The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets
Yujun Kim
Chaewon Moon KAIST
Chulhee Yun
(kyujun02, mmaewon.moon, chulhee yun)akistt...
@kaist. ac.
Abstract
We study the parameter complexity of robust memorization for ReLU networks: the number of parameters required to interpolate any given dataset with c-separation between differently labeled points, while ensuring predictions remain consistent within y--ball around each training sample. We establish upper and lower bounds the parameter count function of the robustness ratio j/ee. Unlike prior work, we provide a fine-grained analysis across the entire range E (0, 1) and obtain tighter upper and lower bounds that improve upon existing results. Our findings reveal that the parameter complexity of robust memorization matches that of non-robust memorization when p small, but grows with increasing p.
Introduction
The topic of memorization investigates the expressive power neural networks required to fit any given dataset exactly. This line of inquiry seeks to determine the minimal network size-measuree in the number of parameters, or equivalently, parameter complexity- needed to interpolate any finite collection of N labeled examples. A number of works study both upper and lower bounds on the parameter complexity [Baum, 1988, Yun et al., 2019, Bubeck et al., 2020, Park et al., 2021]. The VC-dimension implies a lower bound of Q(v ((/N) [Chervonenkis, 2015, Goldberg and Jerrum, 1995, Bartlett et al., 2019], while Vardi er al. [2021] show that ((vN) parameters suffice for ReLU networks. Together, these results establish that memorizing any N distinet samples with ReLU networks can be done with θ(vN) parameters, tight up to logarithmic factors.
We now turn to a more challenging task beyond mere interpolation data: robust memorization. We aim quantify the additional parameter complexity required for network to remain robust against adversarial attacks, going beyond standard non-robust memorization. To address the sensitivity of neural networks small adversarial perturbations [Szegedy et al., 2014, Goodfellow et al., 2015, Ding et al., 2019, Gowal et al., 2021, Zhang et al., 2021, Bastounis et al., 2025], we consider the setting in which not only the data points but all points within distance μ referred to the robustness radius-fron from each data point must be mapped to the corresponding label. More concretely, for any dataset with c-separation between differently labeled data points, the network must memorize the dataset and the prediction must remain consistent within a puball centered at each training sample. As will be seen shortly, the parameter complexity for robust memorization is governed by the robustness ratio = j//e E (0, 1) rather than the individual values of and e. However, a precise understanding of how this complexity scales with o remains limited.
Authors contributed equally to this paper.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.1 What is Known So Far?
Existing Lower Bounds. Since classical memorization requires S2(VN) parameters, follows that robust memorization must also satisfy lower bound of at least S2( /N) parameters for any p E (0, 1). A lower bound specifie to robust memorization is established by the work of Li al. [2022], which shows that for input dimension d, (d) parameters 2-oom for sufficiently large p. However, the authors do not characterize the range of over which this lower bound remains valid. Our Proposition 3.3 presented later shows that the S2( (dVVd) lower bound can be extended to the range p E (V1 1/d, Combining these observations, we obtain the following unified lower bound: suppose that for any dataset D with input dimension d and size N, there exists a neural network with at most P parameters that robustly memorizes 'D with robustness ratio p under f2-norm. Then, the number of parameters P must satisfy
necessary for robust memorization under
P ((1+vd- vd. (2211-3 VN VN++) +d),
where the d term accounts for the parameters connected to the input neurons. In the setting d = O(VN), the lower bounds increase discontinuously from vN to Vdd.
While main analysis focuses the fz-norm, there also exist results under the -nom. In particular, Yu et al. [2024] show that under the -norm and certain assumptions, p-robust memo- rization requires the first hidden layer have width at least d. Our analysis not only strengthens but also generalizes this -nomm result by removing the assumption on the dataset-made in prior whrk-that the number of data points must be greater than d.
Existing Upper Bounds. From the work of Yu et al. [2024], it is proven that O(Nef) parameters suffice for any P E (0, 1). See Appendix D.2 for analysis of the parameter complexity of their construction. Furthermore, Egosi et al. [2025] show that for P E (0, (a)): network of width log N suffices for p-robust memorization. Although they do not explicitly quantify the total number of parameters, their construction with a width log N network requires Ó(N) parameters, as we verify in Appendix D.3. Additionally, state that their construction implicitly yields smooth interpolation varies within the intermediate range (1/vd,1/50)
between Ô(N) and Ö(Nd))
To sum up. the existing upper bound states that for any dataset D with input dimension d and size N, there exists a neural network that achieves robust memorization on D with the robustness ratio under lg -nrmm with the number of parameters bounded as follows:
Ö(N dd) O(Nd +d) Ō(NN))
p (0, 1/vØj.
p=
ippe (L/Vd, 1/9/.
(2)
if if (1/Vd,1).
When d == O(N), the upper bound transitions continuously from Ô(N) to ((N.)).
1.2 Summary of Contribution
We investigate how the number of parameters required for robust memorization in ReLU networks varies with the robustness ratio p. We improve both upper and lower bounds on the minimal number of parameters over all possible E (0, 1), which are tight in some regimes and substantially reduce the existing gap elsewhere. The improvement across different regimes of p is visualized in Figure 1.
Necessary Conditions for Robust Memorization. We show that the first hidden layer must have a width of at least p² min N, d). by constructing a dataset that cannot be robustly memorized using smaller width. Consequently, the network must have at least ?(p² min d'ya) parameters. Moreover, we prove that at least 12(/N/(1 p²)) parameters are necessary for p S / 1/d by analyzing the VC-dimension. Combining these two results, we obtain a tighter lower bound on the parameter complexity of robust memorization of the form
P= Ω (10²
(0 mimm(N,N d) 1)d + min
Vd VV
VI
p

---

Nd
Parameters
Existing Upper Bound
Our Upper Bound
Our Lower Boand
Existing Lower Bound
NYd
Pay 1-
Robustness ratio
Figure 1: Summary of parameter bounds on log-log scale when d = ((VN). We omit constant factors in both axes. Solid blue and red curves show the sufficient (Theorem 4.2) and necessary (Theorem 3.1) numbers of parameters, respectively; the solid black curves are the best prior bounds. Light-blue shading highlights our improvement in the upper bound, and light-red shading highlights our improvement the lower bound. The cross-hatched area marks the remaining gap. Notably, this gap disappears in the smallest regime. The yellow and green dashed line denotes the first term (Proposition 3.2) and second term (Proposition 3.3) Theorem 3.1, respectively.
Sufficient Conditions for Robust Memorization. We establish improved upper bounds on the parameter count by analyzing three distinct regimes of p. tightening the bound in each case. For 0, SN we achieve robust memorization using Ö(VN) parameters, matching the
existing lower bound. For SN 5vå obtain robust memorization with O(Ndd /2//2) parameters up to an arbitrarily small error, which interpolates between the existing lower bound 2(VN) and the existing upper bound Ö(N). Finally, for larger values of p. where p 1) robust memorization is achieved with Ó(Ndpp") parameters, which interpolates between the existing upper bound Ö(N) and Ō(Nd²).
All together, we provide, to the best of our knowledge, the first theoretical analysis of parameter complexity for robust memorization that characterizes its dependence the robustness ratio p the entire range p E (0, 1). Notably, when p < GN the same number of parameters as classical (non-robust) memorization suffices for robust memorization. These results suggest that, in terms of parameter count, achieving robustness against adversarial attacks relatively inexpensive when the robustness radius is small. As the radius grows, however, the number of required parameters increases, reflecting the rising cost of achieving stronger robustness.
2 Preliminaries
2.1 Notation
Throughout the paper, we use to denote the input dimension of the data, N to denote the number of data points in dataset, and C' to denote the number of classes for classification task. For natural number n E N, [n] denotes the set (1,2....,
For two sets A. B C Rdd we denote the fg-norm distance between and B dist (A, B) infflla bll2 a E A,b E B). where ||-11, denotes the Euclidean norm. When either A or B is singleton set, such as {a) or (b), we identify the set with the element and write a or b in place of or B, respectively; for example, dast2(a, (,, B). In the case d = 1, we omit the subscript and write ||
dist(.,.) .) denote the standard absolute distance on RR. We use B2(2r, 11) (ar
x 2222 < 11)
to denote open Euclidean ball centered at with radius μ.

---

We use Ó() to hide the poly-logarithmic dependencies in problem parameters such as N, d, and
2.2 Dataset and Robust Memorization
For d 2 1 and N 2 C 2, let Da,xC be the collection of all datasets of the form D {(a;, 9:) C Rd x [C], such that 2, & zj for all i j and has at least one data point per each class label. Hence, any D E DaN.cc is pairwise distinct d-dimensional dataset of size N with labels in [C].
Definition 2.1. For D E Da, the separation constant ép defined as
cD : min {||e, - 25ll2 (0t, Wi), (s)) E D, yi yz}.
Since the datasets we consider have at least one data point for each class label, the set we minimize over is nonempty. Moreover, since we consider D with x; * æ, for all + j. we have ep Next, we define robust memorization of the given dataset.
Definition 2.2. For D Dd,N.G C. and given robustness ratio p e (0, 1). define the robustness radius as μ pED. We say that function R2 E. p-robustly memorizes D
[(x') = yis for all (æ,, (k) D and x' BB((z,,
and (2) j.) is referred to as the robustness ball of æ;,
When 0, robust memorization reduces to classical memorization, which requires f(x;) = for all (x,, 9/) D. We emphasize that the range p (0, 1) covers the entire regime in which robust memorization is possible. Specifically, for 1, requiring memorization of pea--adius neighbor of each data point leads contradiction as (2, pEp) n B2(22,, (xt),pED) ) * ( for some y/ # Yj- Moreover, if 1, any continuous function f cannot p-robustly memorize D. If f is continuous and 1-robustly memorizes D, we have [B, +D)) {wr) for all i E [N], where (2 <D) is the closed ball with center æ, and radius cp. Since (2 6D) (2 (D) # ( for some y4 # yj- this leads to contradiction.
2.3 ReLU Neural Network
We define the neural network f recursively over L layers:
ao(x) x,
a.(x) = o (W<aaen(z)> + be) for l = 1,2,...,
f(x) Wzat-1(x) + bL.
where the activation (u) max (0, u) is the element-wise ReLU. We use d1, ........ d1-1 to denote the widths of the 1 hidden layers. We define the width of the network to be the maximum hidden layer width, max de. For l E [4]. the symbols We E deexde-1 and b, Rd denote the weight matrix and the bias vector for the č-th layer, respectively; here, we use the convention do and d,. = 1.
We count the number of parameters P of f as the count of all entries in the weight matrices and biases bel/ (including entries set to zero),
P Σ (de-1+ E=1
(3)
This reflects the common convention of parameter counting in practice. The set of neural networks with input dimension and at most P parameters is denoted as
Fa, { Rd R f is neural network with at most P parameters].
(4)
Although less relevant in practice, some prior work counts only nonzero entries when reporting the number of parameters. Appendix E adopts this alternative counting scheme and explains how our results translate under it, enabling comparisons with prior studies from different perspective. Even then, the key findings this paper remain true: for small p. robustness incurs no additional parameter cost, whereas as p grows, the number of required parameters increases.

---

2.4 Why Only p p/ep Matters
We describe both necessary and sufficient conditions for robust memorization in terms of the ratio p/ep. rather than describing it in terms of individual values if and ep. This is because the results remain invariant under scaling of the dataset.
Specifically regarding the sufficient condition, suppose f p-robustly memorizes 'D with robustness radius μ PCD. Then for any
0. the scaled dataset cD == {(ca;, )+));= whose separa- tion EDD = DC can be p-robustly memorized with robustness radius сμ by the scaled function + x) Moreover, the scaled function can be implemented through network with the same number of parameters as the neural network f via scaling the first hidden layer weight matrix by 1/c.
On the other hand, this implies that the necessary condition also be characterized in terms of p. Suppose we have a dataset D with a fixed ép for which p-robustly memorizing it requires a certain number of parameters P. Then, the scaled dataset cD with separation E2D cép also requires the same number of parameters for p-robust memorization. If cD can be p-robustly memorized with less than P parameters, then by parameter rescaling from the previous paragraph, 'D can also be p-robustly memorized with less than P parameters, leading to a contradiction.
Hence, the robustness ratio م w/eD captures the essential difficulty of robust memorization, independent of scaling. We henceforth state our upper and lower bounds in terms of p.
3 Necessary Number of Parameters for Robust Memorization
In this section, we establish necessity conditions the number of parameters and the width of neural networks for robust memorization, expressed in terms of the robustness ratio E (0, 1). The following theorem presents our main lower bound result on the parameter complexity of robust memorization.
Theorem 3.1. Let p E (0, 1). Suppose for any D E Dd,N. there exists a neural network f E Fa. that p-robustly memorize D. Then, the number of parameters P must satisfy
{1 V1 (VI- 0² Vd
P P= Ω (0² (inn, + 1)d min {
VN
The proof of Theorem 3.1 is provided in Appendix A.1. The theorem states a necessary condition on the number of parameters for binary classification (C 2). The same bound applies to C' > 2: any classifier that robustly memorizes a multiclass dataset can be converted into a one vs-ret binary classifier by appending final two-parameter layer (one weight and one bias) that separates designated label from the others. Therefore, a multiclass task requires at least the parameter scale needed for the binary case. Hence, Theorem 3.1 extends to C 2. Moreover, while Theorem 3.1 focuses on f2-norm, we extend the necessity results to general f--norm in Theorem C.5. The lower bound on the number of parameters consists of two parts: derived from the requirement on the first hidden layer width and the other from the VC-dimension.
First Term: Necessary Condition by the First Hidden Layer Width. The first term D((p² min [, d] + 1)d) comes from the following proposition on the first hidden layer width.
Proposition 3.2. There exists D E Da, 2 such that, for any E (0, 1), any neural network f Rd R that p-robustly memorizes D must have the first hidden layer width at least p² minn N - d.
For any fixed N, d, we can choose single dataset D that enforces the bound simultaneously for all p E (0. 1): every p-robust memorizer of 'D must have the first hidden layer width at least p² min(N N 1, d). Section 5.1 treats the simple case N
to illustrate the construction and provide a sketch of proof, while Appendix A.2 provides the full proof for the general case.
Proposition 3.2 for the (2-norm extends to the general norm in Proposition C.6. For every p > 2, the same lower bound on the first hidden layer width, p² min - 1, d), holds. For 1 S 2, nontrivial lower bound still holds. Furthermore, for the norm, we strengthen the result Yu et al. [2024]-whib, they show that width at least d is necessary when N> d and p 2 0.8, we obtain the stronger width requirement min(N - 1, d) for any p E (1/2, 1), without the assumption N > d, as formalized in Proposition C.7.
5

---

We now discuss the implications of Proposition 3.2 on the parameter complexity in Theorem 3.1. Since the input dimension is d, any neural network f R > R with the first hidden layer width m must have at least md parameters. Moreover, we have trivial lower bound m 2 1. Hence, the lower bound of width m becomes max min - 1, 1. (1)], 1} 2 1 (p² min (N - =.d] + +1, yielding a necessity of ((p²² min(NN d} + 1)d) parameters Theorem 3.1. The width from Proposition 3.2 dominates over the trivial lower bound of whenever p 2 1/ min(N 1.
2
Let us compare the result with Egosi et al. [2025], where they show logarithmic width in N is sufficient under the restricted condition of p S 1/Vd for robust memorization. Our necessary condition on width does not conflict with their logarithmic sufficiency, as their sufficiency holds only under S 1/Vd, in which our lower bound becomes trivial.
On the other hand, the necessary condition on width by Egosi et al. [2025] given as 2 log N/ log (og(4882p-) exceeds the trivial lower bound only when p N 4832/V. Even in the case where their lower bound becomes nontrivial, their bound is still at the ((1) scale, so that our lower bound either becomes tighter or matches their bound up to polylogarithmic factor over all P E (0. 1). As a side note, although we generally ignore polylogarithmic factors, we may also consider logarithmic terms for completeness. Under this consideration, the lower bound of Egosi et al. [2025] remains logarithmically nontrivial while ours remains trivial for 4832/N < < 1/c1///im////mm - 1, 1,d]. provided that such o exists.
Second Term:
Necessary Condition by the VC-Dimension. Now, let us look at the necessary number of parameters given by the VC-dimension of the function class.
Proposition 3.3. Let p E (0. V - Suppose for any D E Da,N. there exists f E Fa,p that p-robustly memorizes D. Then, the number of parameters P must satisfy
(V N p2
P=Ω
The detailed proof of Proposition 3.3 is in Appendix A.3 and its extension to the fy-norm appears in Proposition C.8. Before presenting our approach, we briefly review how the existing bound is obtained using VC-dimension arguments. Gao et al. [2019], Li al. [2022] prove that for sufficiently large whenever F&, contains p-robust memorizer of any D E D then VC-dim((aa.) 2(N d). Combining this with a known upper bound VC-dim (Fa,r) p= = O(P2) [Goldberg and Jerrum, 1995], they obtain P = 2 D(VNd).
However, the prior lower bound O D(vNo /Nd) is only known to apply for sufficiently large p. without specifying the precise range. Before our result, the only lower bound applicable to all p includdng small p regime-we was the one that trivially comes from non-robust memorization: 22 (2(VN). A wide range of p lacks VC--imenniion-buee based lower bound tailored to robust memorization.
In Proposition 3.3, carefully characterize how the VC-dimension scales over the range p E (0, /1 - 1/4]. In this range of p, we show whenever Fa, contains p-robust memorizer of any D E Da,N22, then VC-dim(Fa.p) = (( this thus gives the tighter bound = 22( (2(/N/1-07) At the endpoint o /I 1/a, Proposition 3.3 implies that Ω2( /Nd) parameters are required. There- fore, the same lower bound applies for all p 2 /1 /1- l/d, characterizing the regime in which the existing bound of vNd holds. By combining Proposition 3.3 over p E (0, VT 1/a and the ((vNd) bound over E (VI - 1/a, 1), we obtain the second term ([mmin/////pp) valvi in Theorem 3.1.
Finally, we clarify why Proposition 3.3 is stated for S VI- and why, for > this approach cannot improve upon the VNd scale. Any such improvement via VC-dimension would require showing that VC-dim(Fa.p) strictly exceeds Nd, i.e., that a p-robust memorizer Id shatters more than Nd points. Our shattering argument shows that robustly memorizing two arbitrary points forces shattering of (a subset of) the standard basis directions in IR:; iterating over N/2 disjoint pairs can yield Nd/2 shattered points. Consequently, our current construction neither establishes that a robust memorizer of N points can shatter beyond the Nd scale, nor that a robust memorizer of two points can shatter beyond the d scale. Thus, within this framework, the VC-dimension cannot
VI 1/a,

---

be pushed beyond Nd scale, and the induced parameter lower bound does not improve beyond the vNd scale for > v 1/d.
Sufficient Number of Parameters for Robust Memorization
In this section, we establish sufficient conditions the number of parameters for robust memorization, thereby complementing the lower bounds presented in the previous section. In fact, one of our upper bound results is derived under relaxed definition of robust memorization. For this, define p-robust memorization error of a neural network.
Definition 4.1. For any D Da,NCC, define the p-robust memorization error of network f: IR on D as
Lp((1)) == max P Par- # vel, (0..3))
where j = PED. When C,(fD)) < 1) we say f can p-robustly memorize D with error at most 7j.
Note that if network J p-robustly memorizes D (as in Definition 2.2), then the error is zero; that is, by definition (J, D) 0.
We now state our main upper bounds, showing that any given dataset in Da,N.C can be p-robustly memorized by network with p-dependent number of parameters.
Theorem 4.2. For any dataset D E Da.N.C and 1 E (0, 1), the following statements hold:
i) lfpe (0,
5NVd there exists Fa. with Ö(vN) that p-robustly memorizes D.
[ there exists f E Fa,p with P ÖNN p²) that p-robustly memorizes
(ii) If 5NVV' 5Vd
D with error at most
(iii) Pp (2a:1)) there exists f Fa,p with P Ö that p-robustly memorizes DD
We note that we omitted the trivial additive factor d that accounts for parameters connected to input neurons. The three regimes in Theorem 4.2-each referred to small, moderate, and large & regime csspectvely--collcttvvie
cover all values of p E (0, 1) and provide explicit upper bound complexity for robust memorization. Moreover, the constructions behind Theorem 4.2 architecture that depends only on the problem parameters N, d, C, p and not on the dataset: for every D E Da,N.e o and given p. choosing appropriate weights and biases on this same architecture achieves the stated guarantee.
single network
We present proof sketch in Section 5.2 and the detailed proof in Appendix B. The extended version of Theorem 4.2, which additionally states the explicit bounds on depth, width, and bit complexity is presented as Theorem 1. Importantly, the upper bound on the number of parameters in Theorem 4.2 does not come at the cost of implausible bit complexity. that the constructions in Theorem 4.2(i) and 4.i can be implemented with bit complexities that match the necessary bit complexity required for networks with the stated parameter counts. The extension of Theorem 4.2 the -o-morm setting is given in Theorem C.II.
fact, Remark B.2 shows
In contrast to prior results, Theorems 4.2(1) and 4.2(ii) provide the first upper bounds for robust memorization that are sublinear in N. Notably, our construction reveals continuous interpolation- driven by the robustness ratio f-from the classical memorization complexity of é ((vN) to the existing upper bound of Ô(N) in Theorem 4.2(ii), and further from Ô(N) ) to ((Nd" dP) shown in
Theorem 4ii(i. This demonstrates how the sufficient parameter complexity increases gradually with p. capturing the full spectrum of the robustness ratio.
Tight Bounds for Robust Memorization with Small p. Theorem 4.2(i) establishes a tight upper bound Ö(VN) on the number of parameters required for robust memorization when the robustness ratio satisfies < // Since VC-dimension theory [Goldberg and Jerrum, 1995] implies that
any network exactly memorizing given N arbitrary samples must use at least ((vN) parameters, our construction optimal up to logarithmic factors. This shows that, for sufficiently small p. robust memorization requires the same parameter complexity Õ(vN) as classical (non-robust) memorization.

---

Perfect Robust Memorization with Threshold Activation Function. Theorem 4.2(i)) builds upon the techniques Theorem 4.2 extending the applicability from small values of p to moderate ones. However, the extension requires the allowance of arbitrarily small robust memorization error. As discussed in Section 5.2 and shown Figure 4, the error arises because ReI.U-nll networks can represent only continuous functions. Near discontinuous transition regions, they incur small though these can be made arbitrarily small. In contrast, if we are allowed to use discontinuous threshold activation in combination with ReLU network, we can achieve p-robust memorization- and therefore zero robust memorization error-ever in the moderate regime using O(Nd4/1 parameters, the same rate as Theorem 4 4.2(i
Tight Bounds of Width. For small and moderate p. our construction shows width (1) is sufficient, recovering the logarithmic width sufficiency of Egosi et al. [2025]. For large our construction shows width of (p²dd) is sufficient for p-robust memorization. A complementary lower bound (Proposition 3.2) requires width least p² min [N 1,d} is also necessary, which matches with our upper bound when N > d. As a result, when the number of data points exceeds the data dimension, our results tightly characterize the required width up to polylogarithmic factors across the entire range
E (0, 1).
5
Key Proof Ideas
In this section, we outline the sketch of proof for some of the results from Sections 3 and 4.
5.1 Proof Sketch for Proposition 3.2
We briefly overview the sketch of the proof for Proposition 3.2. For simplicity, we sketch the case
N d + where Proposition 3.2 reduces showing that the first hidden layer must have width at
least p²d. To this end, we construct the dataset D = {ee, {)] U ((0, 2)}, assigning label 1 to the standard basis points and label 2 to the origin, shown in Figure 2a.
(c]
Let / an p-robust memorizer of D with the first hidden layer width m, and let W E <R denote the weight matrix of the first hidden layer. Since = 1/2, the robustness radius is pep pep p/2. For any j E [d]. take any æ E B2(e,,))) and x' E (0, jz). Then, f(x) = and f(x') = must hold, implying W x * Wx'. Therefore, possible differences æ x' form a ball of radius 2μ around each standard basis point, illustrated as the gray ball in Figure 2b. Thus, the distance between each standard basis point and the null space of W must be at least 2/x; otherwise, some gray balls intersect with the null space.
x' should not lic in the null space of W. All such
The null space of W is d m dimensional space, assuming that W has full row rank. (The full proof generalizes even without this assumption.) By Lemma A.1, the distance between the set of standard basis points and any subspace of dimension m is at most /m/d. Therefore, we have Null(W)) = 2p S dist2 Nuul))) S
Vm/d and thus the first hidden layer width satisfies
m 2 p²d
dist2 Null( (W)
y
e2
P
e1
Null(W) ((2, y, R&3 x y}
V
(a) Dataset for Proposition 3.2 (d = 3).
(b) Null(W) c R and the standard basis
Figure 2: (a), blue balls have label the red ball has label 2. (b) illustrates the distance between
W)) C R and the standard basis for W = =1 1 -1] with the first hidden layer width 1.
8

---

5.2 Proof Sketch for Theorem 4.2
We now highlight the key construction techniques used prove Theorem 4.2.
Dimensionality Reduction. All three results in Theorem 4.2 leverage strength- ened version of the Johnson-Lindenstrauss (JL) lemma (Lemma 181 to project data from high-dimensional space Idd (left in Figure 3) to lower-dimensional space R. (right), while preserving pairwise distances up to a multiplicative factor. Specifically, any pair of points that are 2ep-separated in RS remain at least V ee-sarrateed after the projection. Mcanwhile, each robustness ball of radius μ is preserved under the projection because our strengthened JL. lemma uses randomized orthonormal projections [Matousek, 2013]. Since the geometry is preserved sppeidiiillicilllll.y..... the separation remains at least / times its original value and the robustness radius is unchanged under projection- we can p-robustly memorize data points in Rd by projecting them to RT and memorizing the projected points, provided that projected robustness balls do not overlap, i.e., as long as 5 /
Separation-Presers
IRd
R
2ED
M 5 tD
Figure 3:
Projection
In Theorems 4.2(1) and 4.2(ii), we project to Rnm with m = (log N) in the first hidden layer. The remaining layers have width (m), so the network width is ((m) = O(log N), i.e., constant up to polylogarithmic factors. This logarithmic projection is valid only for p O(1/vd): projected p-balls remain disjoint as long as p S 2/8 /m/d Ó(1/Vd). If exceeds this scale, the projected balls overlap. For the larger-p regime, Theorem 4.2(1ii increases the projection dimension. As long as S / the projected robustness balls remain disjoint; accordingly, taking m ε påd maintains disjointness. Consequently, the width is proportional to p²d, and the parameter count is proportional to p²d². p
The idea of separation-preservingg dimension reduction and deriving conditions under which robust- ness balls remain disjoint after projection is concurrently proposed by Egosi al. [2025]. However, their approach to ensuring the separability of robustness balls is substantially different from ours. Since the classical JL lemma does not inherently guarantee the preservation of ball separability, the authors do not rely on the JL lemma directly. Instead, they establish a probabilistic analogue through technically involved analysis that bounds the probability that a random projection satisfies the required separation property. In contrast, we employ a strengthened version of the JL lemma and give straightforward proof that there exists a projection preserving separability; see Appendix B.5.
Mapping to Lattices from Grid. For Theorem 4.2(i) and 4.2(ii), we utilize the Ö(VN) (OVVNN)paramete parameter memorization devised by Vardi et al. [2021]. In order to adopt the technique, is necessary to assign a scalar value in I to each data point. This is because the construction memorizes the data after projecting them onto R. Furthermore, this scalar assignment must meaningfully reflect the spatial structure of the data preservnn relative distances and neighborhood relationships of robustness ball.
We achieve this using grid-based lattice mapping. Specifically, m = O(log Then we partition Rn into a regular grid, and assign an integer index to each grid cell. Through this grid indexing, we map each unit cube [[j [zy, Zj + 1) an index 21 Rm 22 +.... 2m for each z = (21, ................................ Zm E T and some sufficiently large integer R. Finally, we associate each index with the label of the projected robustness ball contained in that cell. The network then memorizes the mapping from each grid index to its corresponding label.
first reduce the dimension to
Under the condition P in Theorem 4.2(i), after an appropriate translation of the projected data, every projected robustness ball can be contained in a single grid cell in a way that no cell contains balls of two different labels; see Figure 4a. Hence, the label is constant on each cell that contains ball, and all points in the ball can be associated with the cell's grid index.
What remains is implementability with ReLU networks. The grid-indexing map is discontinuous, while ReLU networks are continuous and can only approximate it. Consequently, approximation errors can occur only in thin neighborhoods of cell boundaries (the purple bands in Figure 4a).

---

Theorem 4.2(1) guarantees translation that places every (projected) robustness ball strictly inside a cell and sufficiently far from all cell boundaries so that the ReL U-based indexing accurate on the entire ball. Hence, each ball is disjoint from the purple error-tolerant regions, every point in the ball is mapped to the same grid index, and this yields p-robust memorization using only Ó parameters.
However, in Theorem 4.2(ii), we consider larger p. where projected robustness balls can overlap more than one grid cell and may intersect the error-tolerant regions where the ReLU-based indexing is inaccurate. As grows, the number of such balls increases. To cope with this regime, we use sequential memorization strategy. We robustly memorize only the subset whose robustness balls are disjoint from the error-tolerant regions. The remaining balls may intersect those regions, but any resulting error is confined to those error-tolerant regions and can be made arbitrarily small by narrowing the error-tolerant regions.
In particular, partition the N points into multiple groups of approximately equal size and, at each stage, we robustly memorize one group, which we call the active group of this stage and we call the remaining groups of data points as inactive groups. We apply translation that the robustness balls of the active group lie strictly inside grid cells and away from the error-tolerant regions, while inactive balls may cross cell boundaries, provided they do not interfere with the cells occupied by the active group of this stage; see Figure 4b. The grid indexing is then implemented by ReLU approximator whose error-tolerant regions are chosen sufficiently thin-by increasing the slope as in Lemma B. B.16-sO so that indexing is exact on the active balls. Any error for the inactive balls is confined to those thin error-tolerant regions. By Lemma B. 1.11, the portion of a robustness ball covered by the error region scales with the region's 's width, and this width decreases as the ReLU slope grows; hence, the error can be driven arbitrarily small. The active group is robustly memorized using the construction of Theorem 4.2(i), and inactive balls do not interfere with the labels assigned in this stage, Iterating the stages and composing the resulting subnetworks yields memorization of all N points with arbitrarily small error.
22
2/
22
11
11
10
10
(a) The setting for Theorem 4,2(), where each robust ball is entirely contained within single grid cell, and no two balls with different labels occupy the cell. This guarantees well-defined indexing without ambiguity.
(b) The relaxed setting in Theorem 4,2(ii) allows some balls to extend across adjacent grid cell bound- aries, as long as they do not interfere with the specific cells being memorized at that step.
Figure 4: Grid-based Lattice Mapping.
6 Conclusion
We present a tighter characterization of the parameter complexity necessary and sufficient for robust memorization across the full range of robustness ratio E (0, 1). Our results establish matching upper and lower bounds for small p. and show that robustness demands significantly more parameters than classical memorization as P grows. These findings highlight how robustness fundamentally increases memorization difficulty under adversarial attacks.
We establish tight complexity bounds in the regime where < 5N However, in the remaining cases, gap between the upper and lower bounds persists. A precise characterization of the parameter complexity for some & remains open and is essential for a complete understanding of the trade-off between robustness and network complexity.
10

---

Acknowledgement
This work was supported by three Institute Information & communications Technology Planning & Evaluation (IITP) grants (No. RS-2019-11190075, Artificial Intelligence Graduate School Program (KAIST); No. RS RS-2022-1122018 184, Development and Study of AI Technologies to Inexpensively Conform to Evolving Policy on Ethics; No. RS-2024 RS-2024-00457888
National AI Research Lab Project) funded by the Korean government (MSIT) and the InnoCORE program of the Ministry of Science and ICT (No. N10250156).
References
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks, Journal of Machine Learning Research, 20(63):1-17, 2019.
Alexander Bastounis, Anders C Hansen, and Verner Vlačić. The mathematics of adversarial attacks in ai - why deep learning is unstable despite the existence of stable neural networks, 2025. URL ftttp::/aariv.orgge
Eric B Baum. On the capabilities of multilayer perceptrons. Journal of complexity, 4(3):193-215, 1988.
Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and weights size for memorization with two-layers neural networks, 2020. URL Utt.https://axxi..orr//// /2000 02855.
A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity: festschrift for alexey chervonenkis, pages 11-30. Springer, 2015.
Gavin Weiguang Ding, Kry Yik Chau Lui, Xiaomeng Jin, Luyu Wang, and Ruitong Huang. On the sensitivity of adversarial robustness input data distributions, 2019. URL htt.t::t///// htttpp://arxiv.orrg
htte/9922008338
Amitsour Egosi, Gilad Yehudai, and Ohad Shamir. Logarithmic width suffices for robust memoriza- tion, 2025. URL attps::/aaxxv..org///ao/
1 11162.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsieh, Liwei Wang, and Jason D Lee. Convergence of adversarial training in overparametrized neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Paul W Goldberg and Mark R Jerrum. Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. Machine Learming, 18(2-3):131-148, 1995.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples, 2015. URL https: http//aaxvvv.r.raaaa// www./org////////ooooooo.oeee arrg//b///412..... 11441...777...
Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples, 2021. URL https: //arxiv. org/ abs 2010 03593.
Binghui Li, Jikai Jin, Han Zhong, John Hopcroft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective of expressive power. Advances in Neural Information Processing Systems, 35:4370-433 4384, 2022.
Jiri Matousek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2013.
Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters, 2021. htttttt/t///xiitii wrgg/abs//00..... 13363.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks, 2014. URL. https://aaarat org/ abs/1312. 6199.
11

---

Matus Telgarsky. Benefits of depth in neural networks. CoRR, abs/1602.04485,, 2016. URL 04485.
http:// http://xxxvvoorgbbbar//e
Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of ReLU neural networks, 2021. URL https::/aaxiiv.orrg//////////// wttp:/iwvv.rr//b//1///01 001877.
Lijia Yu, Xiao-Shan Gao, and Lijun Zhang. OPTIMAL ROBUST MEMORIZATION WITH RELU NEURAL NETWORKS. In The Twelfth International Conference on Learning Representations, 2024. URL httpss://pppneeeeeeee
Chulhee Yun, Suvrit Sra, and Ali Jadbabaic. Small relu networks are powerful memorizers: tight analysis of memorization capacity, 2019. URL https: //axxvv./////////aa wwrg/abs/188 1810007770
Chongzhi Zhang, Aishan Liu, Xianglong Liu, Yitao Xu, Hang Yu, Yuqing Ma. and Tianlin Li. Interpreting and improving adversarial robustness of deep neural networks with neuron sensitivity. IEFE Transactions on Image Processing, 30:1291-1304, 2021. ISSN 1941-0042. doi: 10. 10.1109/tip. 2020.3042083. URL http///....ooo//...../o//// 11PP/TIP..... 2020.3042083.
12

---

Contents
Introduction
1.1
What is Known So Far?
1.2
Summary of Contribution
2
Preliminaries
2.1
Notation
2.2
Dataset and Robust Memorization
2.3
ReLU Neural Network
2.4
Why Only = u/cp Matters
3
Necessary Number Parameters for Robust Memorization
4
Sufficient Number of Parameters for Robust Memorization
5
Key Proof Ideas
5.1
Proof Sketch for Proposition 3.2
5.2 Proof Sketch for Theorem 4.2
Conclusion
10
Proofs for Section
15
A.1 Explicit Proof of Theorem 3.1
15
A.2 Necessary Condition on Width for Robust Memorization
16
A.3 Necessary Condition on Parameters for Robust Memorization
17
A.4 Lemmas for Appendix A
20
Proofss for Section
22
B.1
Sufficient Condition for Robust Memorization with Small Robustness Radius
22
B.2
Sufficient Condition for Near-Perfect Robust Memorization with Moderate Robust- ness Radius
26
B.2.1
Memorization of Integers with Sublinear Parameters in N
30
B.2.2
Precise Control of Robust Memorization Error
33
B.3
Sufficient Condition for Robust Memorization with Large Robustness Radius
39
B.4 Lemmas for Lattice Mapping
44
B.5 Dimension Reduction via Careful Analysis of the Johnson- BeiinsoonLinndnstraan Lindenstrauss Lemma
48
B.6 Lemmas for Bit Complexity
52
C Extensions to -n-norm
55
C.I Extension of Necessity Condition to fy-norm
55
C.I.1 Lemmas for Appendix C.I
59
C.2 Extension of Sufficiency Condition to L, -orm
60
13

---

D Comparison to Existing Bounds
64
D.I Summary of Parameter Complexity across fn-norms..
64
D.2 Parameter Complexity of the Construction by Yu et al. [2024)
64
D.3 Parameter Complexity of the Construction by Egosi et al. [2025]
65
Nonzero Parameter Counts
66
E,1 Nonzero Parameter Counts: An illustration.
66
E.2 Nonzero Parameter Counts: Lower Bounds
66
E,3 Nonzero Parameter Counts: Upper Bounds
67
E,4 Lemmas for Nonzero Parameter Count
72
14

---

A Proofs for Section
A.1 Explicit Proof of Theorem 3.1
Theorem 3.1. Let (0, 1). Suppose for any D E Da.N2. there exists a neural network f E FaPP that can p-robustly memorize D. Then, the number of parameters P must satisfy
P P= (iimin d) + 1)d min { VI- p²
Vd
VN
Proof. From Proposition 3.2, obtain D Da,N22 such that any f Rd - I that p-robustly memorizes D must have the first hidden layer width at least p² min - 1, d]. By the assumption of Theorem 3.1, there exists f E Fa.P that p-robustly memorizes with the first hidden layer width m 2 p² mNn - 1,d]. With the trivial lower bound that m 2 1, we have
2 pa min 1. 1.d]. 13 2 (0² min 1,d]+11
Since we count all parameters according to Equation (3), the number of parameters in the first layer (d + 1)m. Therefore,
P2 (d+1) - m (d+1)
7 (0 min 1, df + +) = 2(d(p² (N, + 1)).
2
In addition, for pe (o, V using Proposition 3.3 gives the lower bound of parameters
N
P=Ω 0t
(v
p²
For p E (0, /1 2).
we have Vi-pa S Vid so that the following relation holds:
min [I p² vd.
For (V1- 2.1 the lower bound P (2VNdd obtained by the p 1 also can be applied. In this case, vi-zz > Vd so that the following relation holds:
min {1 Vd
V11 - x² vd
VN= VNd.
Hence, in both p regimes,
p= Ω min
valvN
V1
serves the lower bound on the number of parameters.
By combining the bounds from Proposition 3.2 and Proposition 3.3, we conclude:
-1- VajvN N }
P max (i2 1)d, min
=Ω (0² min((N,, d3 1)d + minf -1- vajVN)
1
15

---

A.2 Necessary Condition on Width for Robust Memorization
Proposition 3.2. There exists D Da.N such that, for any p (0, 1), any neural network f R + I that p-robustly memorizes DD must have the first hidden layer width least p² min 11,11,,) d].
Proof. To prove Proposition 3.2, we consider two cases based on the relationship between N 1
and d. In the first case, where N - 1 S d, establishing the proposition requires that the first hidden layer has width at least ( - 1). In the second case, where N - > d, the required width is at least p²d. For each case, we construct dataset D Da.N22 2 such that any network that p-robustly memorizes D must have first hidden layer of width no smaller than the corresponding bound.
Case 1 : N S d. Let cD 1/2. Let be neural network that p-robust memorizes D, and denote the width of its first hidden layer
{(e,, 2)] U {(0,))) Then, D has separation constant
Denote by W mxd the weight matrix of the first hidden layer of f. Assume for contradiction that m < p² (N - 1).
Let pep denote the robustness radius. Then, the network f must distinguish every point in By (e,, (.) (u) from every point in (2 p)), for all j E [N - 1]. Therefore, for any æ B2(e,, p)) and x' (0, p.), we must have
We + Wx',
or equivalently, x' & Null(W), where Null(.) denotes the null space of a given matrix. Note that
() fx x' E B2(e,, 11) and x' B2 n)} B2(e,, 2p).
Hence, is necessary that (e(e, 2n) n Null(W) = 0 for all j E [N 1). or equivalently, dista Null(W))) 2 24u for all [N 1].
(5)
Since (Cln(ColWTT))) m. where Col(.) denotes the column space of the given matrix, it follows that dim (Null(W)) d m. Using Lemma A.2, we can upper bound the distance between the set [e,]setN-1] S _2 and any subspace of dimension d m.
Let C C (W) be subspace such that diin 2) = d-m, and apply Lemma A.2 with substitutions d= d= 1, = d m and
The conditions of lemma, namely S d and k: 2 d I, satisfied since N - 1 d and m p² (N 1) I N 1. Therefore, obtain the bound
min 2 2) JEIN-1J
m
N N
By combining the above inequality with Equation (5), we obtain
2μ < min dist2(e,, Null(W)) (ists(e,,Nul((W)) min dista (estz(ej,35) 2) S V N -E[N-1]
m
(6)
JE[N-1)
where (a) follows from that Z S Nu)l(W). Since cD = 1/2, we have 2p = 2pcp = p, so
Equation (6) becomes
m N-11
This implies that m PN 1), contradicting the assumption < P2 1). Therefore, the width requirement m 2 p² 1) is necessary. This concludes the statement for the case N - S d.
Case II: N 1 d. We construct the first d+ 1 data points in the same manner as in Case I, using the construction for N = d 1. For the remaining - d data points, we set them sufficiently distant from the first d + 1 data points ensure that the separation constant remains cp 1/2.
In particular, we set Ø = 2e1; Ø443 = 3e1; ... x (N d)e; and assign yd+2 = y/+3 = YN 2. Compared to the case N = d + 1, this construction preserves ép while adding more data points to memorize. Since the first d + data points are constructed as in the case N d 1, the same lower bound applics. Specifically, by the result of Case I, any network that p-robustly
16

---

memorizes this dataset must have first hidden layer of width at least p² + - -1) = p²d. This concludes the argument for the case N > d.
Combining the results from the two cases N 1 v and N > d completes the proof of the proposition.
L
A.3 Necessary Condition on Parameters for Robust Memorization
For sufficiently large p. Gao et al. [2019] and Li et al. [2022] prove that, for any D E Da..cc, there exists E Fa,P that p-robustly memorizes D, the number of parameters P should satisfy = (d).d). However, the authors do not characterize the range of p over which this lower bound remains valid.
Motivated from Gao et al. [2019] and Li et al. [2022], establish lower bound that depends P in the regime p S v - 1/d, which becomes v VNd when P v1 1/d. This implies that the existing lower bound v dd remains valid for p E IvI- 1111/d,1 1). As a result, we obtain lower bound that holds continuously from R 0 up
ss 1, and thus interpolates between the lower bound VN for memorization to the lower bound v N for robust memorization.
Proposition 3.3. Let p E (0. (0.V1-3) à..
Suppose for any D E Da,N2 there exists J E Fa,p that p-robustly memorizes Then, the number of parameters P must satisfy
P=Ω
(V
(v ( p2
N
Proof. To prove the statement, we show that for any D E Dd,N22, if there exists network f e Fa,P that p-robustly memorizes D, then
VC-dim(Far)= = p2
2
(7)
the above bound holds, then as VC-dim(Fap) = it follows that P MV/N/(NNN
Let = 1Tt2). 1. establish the desired VC-dimension lower bound, it suffices to show that
N VC-dim(Fa,p) 2
This implies Equation (7), as desired. To this end, suffices to construct k 1 points in Rd that can be shattered by Fa.r. These points are organized as an union of N of k points.
groups, each group consisting
2
Step 1 (Constructing M(N/(1 - (1)) points to shattered by Fa.p).
We begin by constructing the first group. Since p (o.v
have h: 1T-10 E (1, (1.
Define the first group X1 = { C Rd. consisting of the first l standard basis vectors in Rd The remaining L - groups are constructed by translating X; For each = 1, define
X =
{q + x x E
where : (1 -1) ensures that the groups are sufficiently distant from one another. Note that e₁ = 0, so that X, consistent with the definition above. Now, define X' == Ute as the union of all groups, comprising & 1 points in total.
Step 2 (Showing Fa,p shatter X²).
We follow the definition of VC-dimension by Bartlett al. [2019]. Note that VC-dimension of real-valued function class is defined as the VC-dimension of sign(F) == {sign o I f F}. Since we consider the label set [2] = {1, 2} for robust memorization while the VC-dimension requires the label set (+1, -1}. we take additional step of affine transformation in the last step of the proof.
17

---

y
el
Figure 5: Reduction of Shattering Robust Memorization, The cross marks refer to the points be shattered, and the circular dots refer to the points for robust memorization The centers of robustness balls change with respect to the labels the points to be shattered.
We claim that for any D E Da.N.2, if there exists a network E Fa that p-robustly memorizes D. then the point set is shattered by Fa To prove the claim, consider an arbitrary labeling
--= = {mn h of the points in X, where each label yt, E {+1} corresponds to the point 2t,j :- Ct + e, E X.
Given the labeling V, we construct D E Da,N.2 with labels in {1. 2 such that any function f E Fa.P that p-robustly memorizes D can be affinely transformed to = 2f 3 Fa.P, which satisfies f' (a( = Mi E } for all mn X. In other words, f' exactly memorizes the given labeling y over X, thereby showing that X' is shatterd by Fa The affine transformation necessary match the (1, 2) 2)-vuue outputs of f with the { (+1} labeling required for the shattering argument.
For each I [LNV/2]]. define the index sets
J = (j [b] My = +1), JT=
(j E [k]
--==
which partition the group-wise labeling (un C C into positive and negative indices. We then define
021-1 = 4 Σ ej Σ
ej
jEJT
jEJT
Σ
ej Σ
22 Ci +
ej.
jEJT
jEJt
Let y/t-1
2, y21 1, and define the dataset D {(m; vi)]EENN E Da,N,2- Figure 5 illustrates
the first group = 1 with k where the labels gives the index sets J = [1,3) and Jr = {2). The blue and red dots denote the points I and 22, respectively.
To analyze the separation constant ep. consider the distance between pairs of points with different labels. Specifically, for each I, the two points 22 and œ2 have opposite labels by construction. Consider their distance:
| x22122
2
2
E JEJ
ee-
Σ e,
(a)
2Vk,
jEJ,
where (a) holds since JJ J. @ and Ji JJ = [k]. Now, for * I' consider the distance between x2 and Ø2r, which again correspond to different labels. We have:
dist2 (x2 W2rr 2 dista ( (12 cr) - dista(ci, #21 - diste(Cr,,20) 22r)
2d Vk - Vi
18

---

220 2vd
22v7
22Vh:
where (a) follows from the triangle inequality, (b) uses disty 22-1) (cs, x2r) Vk, (c) and (e) use h S d, and (d) holds for all d 2 2. Thus, conclude that <D 2 vk.
Let f FaP function that p-robustly memorizes D. We begin by deriving a lower bound on the robustness radius μ in order to verify that f 2 - correctly memorizes the given labeling }
over X. Define (tt) == V بيب
The function is strictly increasing for 2 1, and maps [1, 00) onto
[0, 1). Hence, it admits inverse o=1 [0,1) + [1, oo), defined as / o- T-p= Therefore, have
p -- )= = (
p1-1p)) o(k))
Given cD 2 V and
k-1 it follows that pcp 2 vk- Thus, any function f that p-robustly memorizes D must also memorize all points within b2-ball of radius vk: 1 centered each point in D.
Next, for Fi, E X' with positive label Vi +1, we have
[i. x21-112=
(a tet - (ct Eey-
ey E ez)
i'EJT
j'EJT
Σ ej- Σ ej
=
j'et
S'EJT
j'
2
Vk 1.
Now consider sequence (2, Jee such that nn -> 2..j
and
|| - 221-1112 < w for all n e N.
In particular, we can take
11
1
Zn
Li,j
+ -22-1:
n1
which satisfies such properties. Then, E B((221111 (4) for all n, and by robustness of f, f(zn) [(xx=1) 2. By continuity of f, we have
f(x1,)) = f( lim 2n)) lim f(z,) lim 2 +2000
n
n
Similarly, for 3i E X' with negative label yı = -1, we have | -221l2 Vk so that f(x15)) = 1.
Since can adjust the weight and the bias of the last hidden layer, Far is closed under affine transformation; that is, af + b E Fa, whenever f E Fa,P. In particular, f = 2f E FaP This f satisfies f'(x1,)) = 2 (x1,)) 2f(x))) 3 = 2-1
3 2 2 - 3 +1 whenever yt, +1 and f f((x11) = = -1 whenever St,j = 1. Thus, sign of perfectly classifies X' according the given labeling y. Since such E Fa exists for arbitrary labeling Y, it follows that Fa, shatters X, completing the proof of the theorem.
19

---

A.4 Lemmas for Appendix A
The following lemma upper bounds the di-dtntnnce between the standard basis and any subspace of given dimension.
Lemma A.1. Let {eshyej C Rdd denote the standard basis of Rd. Then, for any k-dimensional subspace Z C IRd.
max Projz jEld]
2\
In particular,
d d- k d
min dist2(e,, jEld]
Proof. Let u,,.... ) C Rd be an orthonormal basis of Z, and denote each u
(ui, "12-"" uss) Let U E Rd be the matrix whose columns are U1 .. uk. so that
U
Ui
U2
U
Then the projection matrix P onto Z is given by
P == P-UOO'U =U = Σ inii E Raxd
Now, for each standard basis vector ej, the squared norm of its projection onto Z is:
h
Pe,
Σ
a ej
Σ
Wy
uuj )
1=1
1=1
where the last equality holds uy orthonormal. Moreover,
k
k
max JE
Pe,le Σ Pe,
7
w1))
(wn)) Σ
d'
jE(d
jEId
JE[d]
This proves the first statement of the lemma. To prove the second statement, observe that for any E Rd, we can write
v = Projz(D) + Projz=(1) (v),
so that |012 |Proj (1) Projj (b)1 Noticing dist2(v, Z) = |Projjz (7)ll2 together with the first statement, we have
min distz(e,, Z) = min Projz (e,))l2 jeld
jE[d]
min JE[d]
[Projz
max |Prooz(e;))] sEld]
k
d
k
d
which concludes the second statement.
20

---

The next lemma generalizes Lemma A. to the case where we consider only the distance to a subset of the standard basis, instead of the whole standard basis.
Lemma A.2. Let S t S d, and let {e, he(( S R denote the first standard basis vectors. Then, for any k-dimensional subspace Z _ Rd with lo 2 d - t, we have
k (d 1)
max Projz (er)ll2 2 sE
In particular,
min dist mindistz(ej... 2) 1 d
t
Proof. Let Q = e. E txd Then, we have the orthogonal decomposition:
IR Col(Q ) Null(Q) = (Z n Col(Q )) @ (z+ + n Col(Q )) + Nu)l(Q).
By taking dimensions, dim(ZnCol(Q")) = dim (R - dim(2 (Z n Col((Q - dim (Null( (Q))
2 dim ) dim (2) ') dim(Null(())
d (d k) (d
= k - (d - t).
Now, consider the restriction of dR. T by the linear map
a1
Φ span e,) c R + R. & Σ a,e
at
Since Col(QT) = span (e.....,ee: e.J. the projection satisfies:
Proizncol(aT (e>) = max jE(
(rois(zncolaTT)((ef
max
jE
By applying Lemma A.1 with the restricted space R we obtain
Proizncoraa 2 (d (d-1)
max jE[t]
Since Z 2 n Col(Q ), it follows that
(d -d-1 1) t
max
[|Proiz(e5)1122 2 max jE(T
Projzncolia ((e))
jER(
This proves the first statement. To prove the second statement, for any E IRd, decompose v as Projz (v) + Projz- (v),
and note that ||01| = (Prooz(())))) with the first statement, we have
( Using dist2(v, Z) = |Projz (v)ll2 together
min dist 2) jEf(
min Projz (e,)ll2 _E
min V |Projz(e;)]]
jEld
max jEl!
||Projz (e;)
k (d - t)
d k
t
which concludes the second statement.
21

---

B Proofs for Section 4
In this section, we prove an extended version of Theorem 4.2, which additionally states the explicit bounds on depth, width, and bit complexity, in addition to the sufficient number of parameters. We present the normm version Theorem 4.2 in Theorem C.III
Theorem B.1. For any dataset 'D E DaN.CC and 17 E (0, 1), the following statements hold:
ii If E (0. 5Nva there exists f with Ö(VN) parameters, depth Ö(VN), width Ö(1) and bit complexity Ō(vN) that p-robustly memorizes D.
(ii) p E (aNVa' ovaj there exists I with Ö(Nd p²) purameters, depth ( p²), width (1) and bit complexity Ô (2/2k that p-robustly memorizes DD with error at most
(iii) If E (Gt..1). there exists f with Ó( parameters, depth Ö(N), width Ö and bit complexity Õ(N) that p-robustly memorizes D.
Here, the bit complexity is defined as a bit needed per parameter under a fixed point precision. To prove Theorem B.I, we decompose into three theorems (Theorems B.3, B.5 and B.14), each corresponding to one of the cases in the statement. Their proofs are provided in Appendices B.1 B.3, respectively.
Remark B.2 (Tight Bit Complexity). The bit complexities in Theorems B.) and Bii essentially tight within our construction framework. Vardi et al. [2021] provide a lower bound on bit complexity using upper and lower bounds on VC-dimension. In particular, for network with P nonzero parameters (refer Appendix E for detailed analysis on nonzero parameters) and bit complexity B, the VC-dimension is upper bounded
VC-Dim O(PB Plog P).
Since VC-dimension is lower bounded by N by the robust memorization, combining these two bounds suggests the necessary bit complexity required under our constructions in Theorem 4.2. For simplicity, assume the case where the omitted d in the upper bound not dominant. In Theorem E.2, show that under constructions, the number of nonzero parameters satisfies P = Ö(vN) for small p and O(Ndt/a for moderate p. Consequently, the bit complexity becomes
B (2(NN and B ② /1/4
respectively, which matches the upper bounds.
B.1 Sufficient Condition for Robust Memorization with Small Robustness Radius
Theorem B.3. Let E (0. VV For any dataset D E Do,N.C, there exists f with Ō(VN) parameters, depth Ö(VN), width ((1) and bit complexity Ö(vN) that p-robustly memorizes' DD
Proof. For given p and D ((I,,,)) E Da,N.C, construct network f Fa. that p-robustly memorizes D with Ó(VN) parameters. The construction proceeds four stages. In each stage, define function implementable by neural network, such that their composition yields p-robust memorizer for D.
Stage (Projection onto log-scale Dimension and Scaling via the First Hidden Layer Weight Matrix). By Lemma B.20, we obtain an integer Ö(log N) and a 1-Lipschitz linear map Φ Rd + R such that the projected dataset D' := ((d(x;), ..).)))))))) E Dm,N.C satisfies the separation bound
5
S
12 V d ED.
We define fproj: d Td as (2)o)())
11 Ld c
-d which is 11 Lil Lipschitz.
22

---

We apply Lemma B.23 with Sproj whose depth is 1, 1/ = min 109
11880 m. 88 360N: 1 and
R == | (2 ui) for some E [[]] to obtain fproj with the same number of parameters, depth and width and O(1) bit complexity such that
max I
|| fll2 S v.
(9)
We set the first hidden layer bias b R that
Foroj (2:) 2 for all e [N] and all æ E (2(x,,
(10)
where the comparison between two vectors is wise
We claim that for D = {(o(Fproj (z;) + b), Be)he we have (i) ED 2 vmm22 2 and (ii) for (x) b) can
p" -Nep.. if g(x) E Fm,,. can p"-robustly memorize D", then p-robustly memorize D. For any i with yt # yy, we have
| (Spros (x;) + b) o ((proj(())) + bill2
(a)
|| [pro (a;) + b) - (prroj(2)) + b)]l2
(ppoo((x))) (proj(at;)) 112
[[/oros - fproj (z;)) (2;) - fxro)(2;))) + (z.) - Srros (x (2)
where (a) holds by the construction of b (Equation (10)). For simplicity, we denote
A(o,, = (x,) (pro)(x.)) - (frros fa)o)(a;)).
Then, we have
[f (x.) + b) of (f (2)) (2t)) + b)1l
| x3)) + (x;) - f proj (x;,) )1
2 (plf (x:) fproj (z) [2,)112 2|112210 - | I. Tzi,) 112)
l ppojj (a::) Srroj (1,, 112 pro (xx) Sproj (1z 222 + [ax, 12
2 profpro)(22) - Spros (21))1
(oopp)o((z)) Sproj (z,) Il A(x; 22)112,
where (a) holds from ||a + bll 2 (Ilal12 - 11bll2) By the construction of f (Equation (9)),
|| 2,) f (z;) - Spros( (x;) ) + (x))) Sproj (2;)) 2v,
so we have
[a([pooj (2:;) + b) - o (Fros ( (xx) + b)]l
2 [p)n)(a3)) - Spran ( ) 1 Arll Sproj (1z))l2.
(11)
Now we derive
11 Vd
[2:r)((23)) - (2,))
|((xx,) 6(0,))12
GD
(b)
11 Vd
2eD
9 6D
(c) 11 vd
x
12 V π ED
9 6D
55
Vm.
(12)
54
where (a) is by the definition of Sproj. (b) is by the definition of D' and its separation constant, and (c) follows from Equation (8). Plugging this inequality to Equation (11) gives
55
(x, [Froo (x.) + b) (f)r))(Z)) b))ll 2 [2, Spros (xno(( (xx
Vm 4v)
54
23

---

55
109
[(pooo)(z.) Spros (x)) 2)2
vm
m)
54
2970
54
-prro [pro)(22;)
(2))l2
Vm
55
(b) 55
54
vm-
Vm
54
55
m
where (a) holds from S
11880 vm, and (b) holds from Equation (12). This proves the first claim ED" 2 vm/2. To prove the second claim, let μ ;= pep and μ" ppe Then,
109
(a) Sproj (B2 (1) +
(B2 pJ) b)
(b)
C Sproj (Bo (ii + v)) + b
89
3 Sproj (B2 (
(1)) + b
88
(d)
89
Vd
3 B2(fproj (
x 11) + b
72
(e)
Ba(Sproj (xi))
89
Vdp) + b
72
(
2 B2 [2por (2:),
89
+
360.V'
(9)
89
B2(fproj (z:))
+ + b
360N
(h)
C By Be(sproj(111))
4N
(4) B2 (proa (xx)), p"(Dr)) + b
B2 B2(Sproj (x:;) b, p'
3 (2 (Froj (2:) b), p" (D=),
where (a) and (j) are by Equation (10), (b) and (g) are by the construction of f (Equation (9)), (c) because S 5g (d) is because projj is 11 Ld g eD
Lipsshhti (e) uses μ pcp. (f) uses p S 5NV4
(h) is because v S 360. and (i) is because p'ED" INep ED" IN.
Hence, g(x:) memorizing the robustness ball (Jproj (ax) b), eD") projected space leads to g a o (xproj(x) b) memorizing the robustness ball for D. In other words, if g(x)) E Fm,, can p'-robustly memorize D", then gooro (Fpro) (z) b) can p-robustly memorize D. With p" ANEp" Stage to IV aims to find a p" robust memorizer g of DD.
Stage II (Translation for Distancing from Lattice via the Bias) For simplicity of the notation, let 2; == (fpro(((x)) + b) for each [N]. that D" {(2,,. ())se(n]. Recall that p" ANep"
gives the robustness radius is μ² p" 4N
By applying Lemma B.15 21. Nv. we obtain translation vector b (b21. .2m) with bit complexity [log(6N)] such that
R
dist(zi, baj. Z) Z 3N'
Vi [N], [d].
(13)
i.e., the translated points (z, by bel are coordinate- wise far from the integer lattice. Moreover, by additional translation {z. by ( (by adding some natural number, coordinate-wise) we
can ensure all coordinates are positive while keeping the property Equation (13). Hence, we may assume without loss of generality by also has the property
b2 2 0 for all E [N].
(14)
24

---

Let us denote D = {(z), Us) hE[M, where 2 := b2. Then ÉpI éD"(2 vm/2). For p² := INep"" we have the robustness radius μ² == p" = Strans as Strans(
p" = μ² IN Define b2. Then, Strans can implemented via one hidden layer neural network, with ((m²) parameters.
Upon the two layers constructed from stage and II, it suffices construct network that robusslyy memorizes D since the translation preserves separation and ball containment properties. Note that the robustness balls after stage are not affected when passing the a, by Equations (13) and (14).
Stage III (Grid Indexing) From Equation (13), each z E R is at least 4
3 "/"" distant away from any lattice hyperplane Hz. == {z R" 2j = with any [m]] and z E Z. Thus, each robustness ball of "D" lies completely within a single integer lattice (or unit grid) of the form II [ms, my + 1),
for some (T mmmm E "n
Moreover, CDM 2 mm/2, for any * i' with ii # yer, we have || sup 21112 2, x' E [T [n, n, +1] = vm, two such points 2 and z that corresponds to distinct labels cannot lie in the same grid. Since each -allball lies within single grid, we conclude that no two -balball with different labels lie within the same grid.
2//12 vm Since
We define R ;= [max || (= max;e[M].jE (21,))1 E N. Our goal in this stage is to construct Flatten mapping defined as
Flatten(z) := Rm- [21] 2m [22] +... Lam].
This maps each grid 17 [mj, 15+1) onto the point ΣØ= R In-
However, since Flatten is discontinuous due to the use of floor functions, construct Flatten, which is a continuous approximation that exactly matches Flatten in the region of our interest. By applying Lemma B.16 to y IN and n [log2 R1, we obtain the network Floor Floor [lor, with Ologg, R) parameters such that
1
Floor(=) = [z] Vz E [0, R] with 2 [2]
(15)
4N
Moreover, since apply y 1/4N Lemma B.16, the lemma guarantees that Floor, can be exactly implemented with (n + log N) = Olog I + log N) bit complexity. In particular, we can define our network Flatten with (log log N +og Rm-11) ) = O(log R+ N +olog N log R) = Õ() bit complexity as
Flatten(z) = R. Floor(21) + ......... Floor(zm).
(16)
This implementation is [0, R] dist?(zy, 2 2N for all j E [m]}) characterized by the margin guaranteed by Equa-
Flatten(z) x) = Flatten(z) the region of interest (f*
tion (13).
As Floor: R + can be implemented with width 5 and depth Ollog, R) network (Lemma B.1 Flatten can be implemented with width 5m and depth (log, R) network. Thus, we can construct Flatten with (m3 log, R) = Ōmm) parameters.
By Equations (13) and (15), we guarantee that each robustness ball lies in the region where the Flatten is properly approximated by Flatten. i.e.
(1atten(z) = Flatten(z) for all z E (2(22111))
Since Flatten maps each unit grid into point and each robustness ball of D lies on single unit grid, we conclude
Flatten(z) Flatten(z) Flatten(z.) for all = E B2(z/, (.")
Let m, == Flatten(z'). Then each robustness ball around is mapped to m, We have m, E Z n [0, Rd + for all E [N], since
Flatten(z2)
|2/11] R.th 22 2 + (
25

---

(4) I Rm
R
22 RR+ ........ + +R Rm-22
Rm+1
where (a) by ||
S R.
Stage IV (Memorization) Finally, it remains to memorize N points {(m, B:) Zzo [C]. Since multiple robustness balls for D with the same label may correspond to the same grid index in Stage III, it is possible that for some i + with yi yj. we have my = my. Let N' N denote the number of distinct pairs (m,, 91)- It remains to memorize these N' distinct data points in R.
Since my (la I Rm+1, apply Theorem B.4 from Vardi et al. [2021] with R
to construct fmem IR + R with width 12 and depth
Ō(VN' log(5R N26 VTm)) = (0:0mmmvv = -(
such that frem (m:) = yi-
The final network f R + R is defined as
f(x) = Sme c a a Flatten o ftrans o (ar) + b).
The depth network Spxcj (a: + has width m, and also the depth network Strans has width m. Flatten has width 5m and depth (logg R) and fmem has width 12 and depth ((VN). The total construction requires Ö(md + m² + m + vN)= = O VN) parameters, where each term md, m², m² and vN comes from Sproj- Swans: Flatten, and Jmem respectively. The width of the final network Ó(1 and the depth is (VVN..
The bit complexity of Fpeoj is ((1 and that of is
O([log(6N) log.loox (r)) x B2( p))
for some E [N]])) Ö(1)
The network furau has the bit complexity log(mna{[]2:ll) i E [N]]) = Ö(1). Flatten has the bit complexity Ö(1), and fnom needs at most Ö(vN) Hence, the bit complexity of the final network is Ö(vN).
The following is the classical memorization upper bound of parameters used in the proof of Theo- rem B.3
Theorem B.4 (Classical Memorization, Theorem 3.1 from Vardi et al. [2021]). Let N, d, E N, and
T, > O, and let (I1, 91), .... (IN, UN) Rd x [C] be set of N labeled samples with || I for every and |a; æz 2 2e fe every i j.. Denote R N -! VTd. Then, there exists neural network F IRd IR with width 12 and depth
( log N V+
o ( (VNlog
N log N
max flog R, log C1
and bit complexity bounded by Olog d + log max max R, log C}) such that F(x.,) ys for every [N].
B.2 Sufficient Condition for Near-Perfect Robust Memorization with Moderate Robustness Radius
Theorem B.5. Let pape E sval. and n E 1). For any dataset D E Da,.cc, there exists f with à(Ndà p²)) parameters, depth O(Nd's p²)), width Õ(1) and bit complexity Ô (v/akp)) that p-robustly memorizes D with error at most 17.
77. and D ((.,, Mi) Dd,N.C, we construct network f that p-robustly memorizes 'D with Ô(N p²) parameters.
Proof. For given p. any desired
Stage I (Projection onto logls Dimension and Scaling via the First Hidden Layer Weight Matrix).
26

---

The first stage closely follows that of Theorem B.3. By Lemma B.20, we obtain an integer m (loo N) and a 1-Lipschitz linear map á I + R such that the projected dataset D ((o(a))) MeeN D N,,N.C satisfies the separation bound
5 m c
12
d
CD-
(17)
We define Sproj IRd R as (proj(a) = # Eo (x)) which is y/ vd Lipschitz.
We apply Lemma B.23 with fproj whose depth is 1, V = min 100
Vm, 8g/4 360N 1) and
11880
R == max |x|le a B2(x,, for some E [N]] to obtain fproj with the same number of parameters, depth and width and O(1) bit complexity such that
max || -fll2 Sv.
(18)
a I
We set the first hidden layer bias b E R so that
Prroj (2:) 2 for all E [N] and all x e B2(
(19)
where the comparison between two vectors is element-wise.
We obtain the grouping scale E [0.1] here for Stage II-we we call a the grouping scale, as we group the points by approximately No points per group in Stage II. From the condition, we have
5pyd 1. Thus, there exists a [0, such that satisfies [Na] Lonval- Let us bound the p in
terms of a. Since [N*]
we have
5pva
5pvd
S 5LNaJVd
(20)
5[NolVd
We claim that for D" = ((o (x.) + b), 81) Mie E DM,N.C, we have (i) ED" 2 vm/2 2 and (ii) for p" = J[N"Jemp if g(x) E FM, can p" r'obusustly memorize D", then o a (Sproj (x:;) + b) can p-robustly memorize D. For any i + with yi # yj, we have
| (x;) + b) o (x + b)][[2
(a) [[proo (2x;) + b) - (Uproo((2)) + b)]l2
fproj((t)) (x:)
[|(/pro - (poo)(()))))) (froo((az)) Sproj (2;;) + (fpro((2,)) Sproj (2, where (a) holds by the construction of b (Equation (19)). For simplicity, we denote
(ai, 2.)) = (Fproj(a:)) - Speaj (x:)) - (Fproj(22, (x,))
Then, have
(ppros(())) + b) - 0 (fproj + b)]l
A 2.)) + (Sproj (2:; I proo ( (x.z) )) ))1
(a)
2 fpoo (xx) - Spros (zx))l 1|12211000 - AA(x; x )12))
Spooj (x:) - Spros (x: )11 pro. (ar,) Spro| (2r,) 112 (ax, (z,, a; 1)2
+ || (a x,)
2 froo (xx)) - fproj (x,))11 211.proj )- Spruj (2)))l2 A(x, x 12,,,
where (a) holds from |la + bll3 2 (Ila|12 11bl12) By the construction of f (Equation (18)),
|| [xx 222 < [ (x:) - (x:))2 + (x5)))((t))) - Spros(2;))le S 2v,
so we have
[po(Fpo)((0)) + b) o (Fpoo (x,) b)]l
27

---

2 211fpoo(2zs) - Spros (2, 2 frros()))) Spros (22)
(21)
Now we derive
11 Vd
(()r)((())) f2ro)(2;)11
(x,))l2
(a)
||((x,) - 0(0x))12
CD
M
11 Vd
2ED
9
6D
(
vd
m
9 CD
x
12 V
ED
55
vm,
(22)
54
where (a) by the definition of fproj, (b) is by the definition of D and its separation constant, and (c) follows from Equation (17).
Plugging this inequality to Equation (21) gives
[|rosp))) (xxs) + b) - (fproj ) + b)(l2 2 [pro)((as)) - Sproj (az,) 12
55
V - 4v)
54
(a) || proj Sproj] (3) )112(
55
109
Vm
2970 Vm)
54
54
(x;) -proaj (o3, l2
Vm
55
(b) 55
54
m
V
54
m
where (a) holds from <
118s0 Vm, and (b) holds from Equation (22). This proves the first claim ED" 2 mm/2. 2. To prove the second claim, let := ped and μ² := ED... Then,
109
o(Froo (Bp u)) 6)
(a) Fpro (B2(x,, (z,, m4) +
(b)
S fproj (B₂ xc + v)) +
(c)
89
C Sproj (1ii
(mis
88 (1) + b
(d)
89 Vd
C (froo (x:).
x u1) + b
72
(e)
89
B2(fpros (xx))
dp) + b
72
(
2
B2(fproj (xx,),
89
+
360
(0)
89
C (proo (x,),
+ v) + b
360N
(A)
C
B2 B2(Fr (2:))
4N
( B2 [Froo (arro)(()),pe)>/ p.E)")) + b
Be (froo (x:)) + b, ETD:) ('ppp)))
(
b), p" cD²).
where (a) and (i) are by Equation (19), (b) and (g) are by the construction of f (Equation (18)), (c) is because 88 14, (d) is because Sproj is 11 vd Lipschii, (e) uses μ p<D. (f) uses p I 5N/7 cp
1
(h) is because < 300 and (i) is because &" INop" CD"
aN.
28

---

Hence, g(x) memorizing the robustness ball (f (z;) + b). p p'em") on projected space leads to g goo (fpros(x) + b) memorizing the robustness ball for D. In other words. if g(x) E Fm.P can pr-roustyly memorize D", then a o (x)) + b) can p-robustly memorize D. With p" "[N"]ep"" Stage aims to find a p" /"-robust memorizer of DD. For simplicity of the notation, let 2, == (xproj((z))) + b) for each E [N]. so that D" {(z,, y/ ME(M)-
Stage II (Memorizing No Points at Each Layer): Using the grouping scale a obtain in Stage I, we group N data points to [Ni-0] groups with index {1 { each with [7 - [N + 1. Then, we
construct J, that memorizes data points and their robustness balls with index 1,. and the error rate remains small for other data points and their robustness balls.
For each j E [[A]-a1], we apply Lemma B.13 with error rate 1j NT t a, D
D" E Dm,N.C. P < p" and + 15. Then it satisfies that ex" 2 vml2 2, p" aI
and |/| S [Na] + Thus, we obtain neural network /₃ with width ((m) = 0()) depth Ö(N#)
and Ô (N + m²) = Ô (N parameters and bit complexity Ô (N + +m) = Ô (N such that:
f)(2) = Vi
Vi E J E B( p² (D"),
(B [īx(z) [0. 21 NI-o
1
Wi [N]V,
Thus, we have
P "
[T]()] E 10. 21 Ni-a
WE E [N'-9.
(23)
We define for each
11 3 = y (1((0) :
fj
so that the last coordinate is given as y + a (fx(z) - -v) max (z), y). Finally, we define the full robust memorizing network
f(x) = ( f Ni fo.... fo f2o fi (Fro((z) (z))zz)
0
We now verify the correctness of the construction. For any x E B(x;; pep) and z = -prroj (r) E B(zi, pD))). since we partition [N] into disjoint groups {z)) there exists a unique index ji such that i E Ij. and thus fr. (z) ) = yi holds. For all * jc. the networks satisfy fz() E {0, w with high probability, so none of them can exceed yı. Since the final network outputs the maximum among y and all fz), we have (=x = yı as long as each fz()) e {0, v:. Therefore, it suffices to show that (z) E {0, 313 holds for Vj, namely,
[F(x) E (0 Vj [N'-a]] = f(x) y..
Considering the contrapositive, we have
f(x) + vi + [ & (0 for some j E [[V--a]
Since each f, satisfies Unif(( (m (z) E (0, 2 NY= for all j E [N'-0], upper bound the error probability using the union bound:
P PretUii(((( [f(x) # yil SP 2E
[[](]] & (0.0: for some E [Nt-a]]
Σ
P PrEUni((( [}(=] (0.wo)
]E[NI-a] o]
(0) N1-a x
?7
Nl-a
29

---

where (a) holds by Equation (23). Hence,
P (ee [fx) = V/] P (B (f(x) # v.l
We verify width, depth and the number of parameters of Recall that the final network is
f(x) = ( f N1- o... o.........o 0 fi (frag(ar) (Fron((()) b)
The depth network Fpruj + b has width m Ó(1) For E [[NV-07], each fy has width Õ(1)
depth Ō(V3) ) and (N parameters.
The network froj needs dm ((d) parameters. Hence, the number of parameters of f
(NN2~a x N = ÖN (a) Ô (
The width of f is Ô(1) and the depth of f is where (a) holds by [Na]_ = 5pva
Ô (N x N = Ō (Ndàpt).
The bit complexity of Forot is Õ(1) and that of b is log(max( (I (z) [l) (2( for some i E [N]H) Ó(1) The network fj has the same bit complexity f.. which is Ô (N#) Ô (1/app)) Hence, the bit complexity of the final network is Ô (2/akpt)
x E
The above construction is motivated by the need to handle overlapped robustness balls with the same label. We transform the construction classical memorization in Vardi et al. [2021] in two key directions: first, from memorizing isolated data points neighborhoods (x; μ);; and second, to ensuring correct classification even within regions where multiple robustness balls with the same label overlap. To accomplish this, introduce disjoint, integer-aligned interval encodings and carefully control the error propagation caused by dimension reduction, addressed in Lemma B.
memorizing entire robustness
B.2.1 Memorization of Integers with Sublinear Parameters in N
Lemmas in this subsection are slight extension of those in Vardi et al. [2021], adapted to integer-based encoding scheme.
From here, (n) denotes the bit string from position i to j (inclusive) in the binary representation of For example, BIN (37) 4, since (37) (100101); that BIN,aa(7) (100),
1o)
Lemma B.6. Let > 0 and m, E N with m < Then, there exists neural network F R. + R
with width 2, depth 2 and bit complexity Õ(1) such that
F(x) = {00
for [m, 7). for x E (-20, m - nl oo).
Proof. We construct network F:
F(x) = (1-0 (--o--1o-1))) (-1(s-m)) + (1 (1-0 (n - m)))
(
It satisfies the requirements with depth 2 and width 2. The bit complexity is O + log log(1/n)) Ö(1).
30

---

Lemma B.7. Let 1) E (0, and let mi <... < my be natural numbers. Let N1. E N satisfy Ni N2 N, and let wi...., WN, E N. Then, there exists neural network F with width depth 3N1 + 2 and bit complexity ((1) such that,
W Ne
if [m, my + 1 for some [M] 77, myNz + 1).
F(x)
if & U
where define mN+1 MNNN m..
Proof. L E [M.]. We define network blocks Fj R R and Fj RR
ER as follows. By
applying Lemma B.6, we construct F, such that:
Fイ(x) [1 if E (mo-1)N++1+ miN; +1 17]
0 i S mij-1)N2+1 or x 2 mgN₂ + 1.
As result, for any [N]. any [m,, m.
satisfies
F((z) {
if E [(i - 1) N2 + 1.j N2). otherwise.
Next, we define:
(
x
Fj
= (V + Wj F₃(2))
11
Finally, we define the network F(x)
FN, Fi
We now verify the correctness of the construction. For i [N], let E [m, m, + 1 -n]. For j 1. we have (z) 1, and for all j' + (x)(x) = 0. Therefore, the output of F satisfies
F(a:) Wj l so
The width of each F, is at most the width required to implement Fj. plus two additional units to carry the values and y. Since the width of F3 is 2, the width of is at most 4. Each block F3 has depth and F is composition of N1 blocks. Additionally, one layer is used for the input get
and another to extract the last coordinate of the final input. Thus, the total depth of F is
3.11 + 2. The bit complexity is Ô(1).
Lemma B.8 (Lemma A.7, Vardi et al. [2021]). Let n E N and let i,j E N with i < S. Denote Telgarsky's 's triangle function by xp(2) == (22) (42- Then, there exists neural network
F F +
with width 5 and depth 3(j - i 1), and bit complexity n + 2, such that for any x E N
+
x
2
with x S 2", if the input of F
(((--1)
2
2
x
2m
2
then it outputs:
BIN
2R
+
2642
In the following lemma, note that p does not refer to the robustness ratio.
Lemma B.9 (Extension of Lemma A.5, Vardi et al. [2021]). Let 1) > O, and let n, p.e. e E and u, w E N. Assume that for all E, k E (0,1....,
1} with E + k, the bit segments of u satisfy 1- + BIN (++)))()((()((())))))
BIN
p-8+ PIN--t-i
Then, there exists neural network F: : R + IR with width 12, depth 3n max(p, cJ + 2n + 2 and bit complexity n max c} such that the following holds:
For every x > 0, if there exist j E {0, 1,..,..., n - 1} such that
[BIN (w), BIN ( +1 - -1),
then the network satisfies
F
BIN
u
31

---

Moreover, F
w - 0 for
E R
U
(BIN p=+t 7. BIN p ( +1).
jE -.. n-1
Proof. We define the triangle function (pz) == (() - -42 2)) as introduced by Telgarsky
[2016]. For {0, (0.1....,,7 1}. we construct a network block Ft:
(olt-p)
((((+1))p))
2
2
(((+1)00)
+
F
foline)
2
2m
2m-p42
(((++1))))
(ale)e)
2we
2
2
2
2we
2
2
2
y yi
where
BIN BIN (e 0
if E [BIN, (p+1((+)) BIN BIN
n/}
y/
i S & L((t))))) - or x 2 BIN ((tt)))
To compute yss first extract the relevant bit segments from and w using Lemma B.8. We define two subnetworks F.P. F.:
(0((++)))))
(p(+tp)
(p(1)p)
2
2"
(0((+1))p))
I
200p
BIN
((((+t))))
Fr
(plt)e)
(
+ 2nict1) 2i0 + 2n
2n
(((i+1))e)
2
2
(((t))
20ic22
subnetwork F maps the pair of triangle encodings of u to the updated encodings for + 1, along with the extracted bits BIN ((Net A subnetwork F." does the same for w, yielding 1IN+).+((())))(
We then construct a network with width 2 and depth 2 to obtain y, from inputs BIN p 11(44))) and x. Firstly, we use Lemma B.6 construct network that output ye:
if E [BIN, - BIN (t1 + 7), 2 BIN (LNe)))((+)))pp(u) + 1.
J.
0
if < BIN, (NNipt
Secondly, we construct the following 1-layer network that use ú, as input:
U BIN (HIN))) + a 2 2 BIN
This ensures that the output is BIN, BIN ((C)))())) ÿt 1, and the output is ÿ = 0 since BIN (IN))+1(+++))((w))) 2
Finally, the full network is constructed as composition:
F G Fn ........ H
where for x, w. 0: (1) H: R > R is a 1-layer network that maps (ær, w, u) to the required initial encoding inputs, namely:
T
Zepp p
2
H
20
11
32

---

G R + is 1-layer network that outputs the last coordinate.
We verify the correctness of the construction. The output of the full network is given by:
F
w
y--
Ž=0
If there exists j E {0, n n then by the construction we obtain = BIN -1 while yr = 0 for all 8 j.j. This is because the bit-encoded intervals are disjoint as BIN (et) & BIN (*+bo Hence, the final output of F is:
such that I E [BIN PJ+ p BIN p. (-) (1))
ΣE= BIN BINo)-oo(+)(())
We analyze the width and depth of the constructed network F. Each block F; comprises F. and FT" each of width 5. In addition, two neurons are used to process x and resulting in a total width of 12. The outputs Yi and yi are produced by additional layers with width 2 and I, respectively, both of which are smaller than 12. We also compose the networks H and G, with width 6 and 1, respectively, again remaining within 12.
Each of the networks F." and F!" has depth at most 3 max c}. The layers obtaining üJ and y: contribute additional 2 layers, resulting in total depth of 3 max c} + 2 for each block F,- Composing all such blocks, and including one additional layer each for H and G, the total depth of the network F is 3n max (p, c) 2n
The bit complexity of F.V P. and bounded by max +2+ and all other parts of the network require less bit complexity. Hence, the bit complexity of F is bounded by max c} + 2.
B.2.2 Precise Control of Robust Memorization Error
Lemma B.13 constructs the network for Stage Theorem B.5, while the robust memorization error is controlled in Lemma B.11.
Lemma B.10. Let N, C E N, and let (m1, (1m,,y))........ (m UN) ) E DI.NCC C x [C] be a set of N labeled samples with my F my for every i + Then, there exists neural network F R TK with width 12, depth Ö Ö(YN), Ö(VN) parameters and bit complexity Ö(yN) such that
yt t0
for every m mm with E (N), for every m E N, N.(meheet
F(m)
Proof. Let M = (ms We group the elements in M to [VN] groups, each containing at most [VN] + natural numbers inside. For each interval indexed by j fl..... [V]], we define two integers Wj, Ug E N to encode the integer m, E M and the corresponding labels yi as follows.
For each E [N], letting j = [ 1. == mod (IVN) + 1) and R == maxic[[] mi we define:
BIN, loog, R+ R+1((++))-oo,, R Ru,)) m;
BIN log, C+1:(k+1) C (w;) = y/
Thus, each group j. the integer u, contains log2 R bits per integer, which represent the k-th integer in this group. In the same manner, wy contains log, C' bits per integer, which represent the label of k-th integer in this group.
By applying Lemma B.7 to 1. we construct neural network Fi that maps m E M to their corresponding groups, and maps m N UJE[[ [m [ m "{(vV]+)) + 1) Thus, all natural numbers are assigned to their corresponding group O.
For each i E [N], we define the group index
jc
+1
33

---

Then, the network Fi maps any input m E M to the representation
m
[(mm
W/e
and Fi (i(m) = (m)
for m E EN (m
"([vNH+) + 1). The network
Fi has width 9, depth Ö(VN) and bit complexity (()).
Now, we apply Lemma B.9 to construct network F2 R - R with the following property. For each [M] [V]]] and &s E {0. { [VNJ]. suppose that m, is the k-th integer the j-th
group. Then, the network :
m4
F2
Wi
BIN k I- C+1:(k-1)-loo, c(w,) yi-
Uj
Moreover, for m E N M.
W = 0 or F2
= O. Thus, the network F2 extracts
U
the label corresponding to each data point from the encoded label set of the group to which the interval belongs or outputs 0. The network F2 has width 12, depth Ö(v and bit complexity Ö(vN).
Finally, we define the classifier network F _2d + IR as
F(x) F2 (x)..
The overall network F has width 12 and depth Ö(VN), which corresponds to the maximum width and total depth of its component networks. The bit complexity of Ö(VN).
Lemma B.11.
Let B2(w0, μ) be Euclidean ball with center Do I. and radius μ > O. Ler u Rd be a unit vector, and define the affine function f(x) == 2p. (u' x + b) for some E TR. Then for any interval I C R of length the volume fraction of the ball mapped into I satisfies:
Vol E =B2(xo p) f(x) 1})
Va-1
< 2n
Vol (B2
Va
where Va
2//2 +(4+1)
denotes the volume of the d-dimensional unit ball.
Proof. Let 20 + my. so that y E Ba 1). Under this change of variables,
f(x) = 2p (u (mo + myy + b) = (u 7) + 24
(u ao + b).
Thus, f(x) E 7 if and only if u y E J, where
J 21
(u xD + b) R
an interval of length 2n.. We define the preimage of under if with the intersection of B2 p1) as
A = {x E (2 p) f(x) 1}.
Then,
Vol(A) = = Vol ((v E (2 1) uT y E J}).
The distribution of T y, where y ~ Uni (0, 1)), has density
p(() = Va-1
V (1 12 for 1 E [-1,1] 1,1),
where V, r(S + 1)
d/2
34

---

Thus,
Vol(A) 1² Va p(t)dts n² S. Va-1 Va-1 2n Vo-11
(a n)) Va.
Hence,
Vol (x E (2 p.) f(x) ET)
Vol(A)
S 2n Va-1
Vol (B, 11)
Vol uu)
V/2
Lemma B.12. For all integers d 2 1,
Va
S
Va-1
4/2
where Va
is the volume of the d-dimensional unit ball.
[ +1
Proof. Set
Va Vi
Rd =
Va-1
I +1
Let = df and define
g = log Ra, = 2 log π + log [ r + 2)) - log [(x + 1).
Differentiating and using the digamma function 1 = 1 /T, we get
g((x) = (x - (xx <
since & is strictly increasing. Hence Rs is strictly decreasing in d. Therefore max.21 Ra Ri V = 2, which proves Rs S with equality only at d d1.
Lemma B.13. Let 17 10,
10 and D {( (ID,,NN) Da,N.C be dataset with separation ep 2 vd/2, and let the robustness ratio be p T[NoJeD' Then, for any index set I []] with [I] < [N*]+ 1, there exists a neural network f with width O(d), depth Ö(N δ (N + d) parameters and Ö(N + d) bit complexity such that:
f(x) ys [f(=) (0, v 21-1
Vi E 1, E ((x;;
Vi E [N]
network f, obtained from this lemma, memorizes each data point and robustness ball for all indices i E T. maps every other data point and its robustness ball to either its correct label or 0 with high probability
Proof. We construct a network proceeding in three stages. In each stage, we define subnetworks such that their composition satisfies the requirements.
Stage I (Translation for Distancing from Lattice via the Bias) We first translate the data points so that for E I, the robustness ball centered æ; lies far from integer lattice boundaries. This ensures that each ball lies entirely within single unit grid cell. By applying Lemma B.15 to the points (eeher
we obtain translation vector b = (b), ... bb) E Rd with bit complexity [log(6) ZI) such that
dist(Zr bn. Z)
Wieij [d].
(24)
3 ][
i.e., the translated points (æ; (aie are coordinate-wise far from the integer lattice. Additionally, we apply an integer-valued translation (coordinate- wise) so that coordinates of the points (x;-b))e(M -b)e[M] become positive, while preserving the distance property in Equation (24). Hence, without loss of generality, we can assume also has property
- b 0 for all i [N].
(25)
35

---

Let De := {( [e) where x := - b. Then Epr = ED. For p' := 1[N" we have the robustness radius yl := p cp = pep = =[ Define ftraus as ftrans (x) = x b. Then, Strans can be implemented via one hidden layer with (d²) parameters in neural network.
Since the translation preserves separation (Ep = ep:) and ball containment properties (robustness ball of D is mapped to the robustness ball of D' through the translation), it suffices to construct network that satisfies the requirements with - o' and D +- D'. Observe that the robustness balls after Stage I are not affected when passing the σ. by Equations (24) and (25).
Stage II (Grid Indexing) From Equation (24), each a/ E E (for i I) is at least 1 distant from any lattice hyperplane Ha.j == {æ R zj = =} for each j E [d] and E Σ. Hence, each robustness ball centered at æ, (for i E 1) lies completely within single integer lattice (or unit grid)
My: Rj + 1), for some (01,-... ,na) E Zá. Moreover, for any x E (2),,,1))) the distance from the integer lattice remains at least p'.
Furthermore, by the separation condition eD = ED 2 vd/2. for any i i' with y, + yv, we have Ing, || - x l12 2 Vd. Since sup - z'112 x, x, E I ny + +)} = Vd. two such points cannot lie in the same grid. Recall the separation condition holds for all data points x for i E [M] and each ball (2(2,,, (for E I) lies within a single grid. We conclude that for each E 1, the robustness ball (2 ) is not intersected by any other robustness ball By (a' μ²) with a different label, for any j E [N], i.c., no ball with different label overlaps the grid cell containing B3 (2 H²).
We define R = [maxier |ar/|l (= maxier (1),))) N. Our goal in this stage is construct Flatten mapping defined as
Flatten(x:) == [ + Rd [ +... + [oa)-
This maps each grid II - (nj, 1)+1) onto the point Σラ= R In..
However, since Flatten is discontinuous due to the use of floor functions, we construct Flatten which is a continuous approximation that exactly matches Flatten the region Uler B2 n²), and incurs only small error on the remaining region USEINTY
j()). We choose large enough 4/2
t N so that for n 1/t, we have r/ S "zVe_, Mnn where V2 = [(++)
denotes the volume of the d-dimensional unit ball. Moreover, we can take such E N which at the same time satisfies
V1
L I 2dVa-1 +
2dT d + +1 1- - 1)p'n
+ =f (((
Vajen
π 11/21(
By Lemma B.16, for = 1/1 v/ and = [loga R], we obtain the network Floor Floor Floor[oog flog, R) with O(log2 R) parameters such that
Floor(x: = [s]] Vx E [0, R] with [x]] > n/.
(26)
- Since we apply 1/t to Lemma 1.,,, Floor can be implemented with O(n + log t) = Olog R log(d? [ Flatten with O(log(dRN/1) log -d = (dlogg/////)) + log R) = ((d) bit complexity as Flatten(x)) =d Floor()) + Floor(za).
bit complexity. In particular, we can define our network
(27)
As Floor: IR + RR can be implemented with width 5 and depth O(log2 R) network (Lemma 16),), Flatten can be implemented with width 5d and depth O(log, R) network. Thus, we can construct Flatten with 1o22 R) = (dd) parameters.
We first observe that this implementation is valid on the region Uler B2(0%, For I and E (a n!), we have
V2
V2
(d) 2 11/
nl'
n'1
2V
2dV
where (a) holds by Equation (24), (b) holds since 1) < 1, (c) holds since Va
Va_ < 2 by Lemma 1.
and (d) holds from the choice of n/" Thus, for any E I and any B2(2', H²), xy satisfies the
36

---

requirement in Equation (26). Therefore, we guarantee that each robustness ball centered at æ for i / lies in the region where the Flatten is properly approximated by Flatten. i.e.
Flatten(x)) Flatten(x)) for all and B2(a',,
Since Flatten maps each unit grid into point and each robustness ball centered at a/ for i I lies on a single unit grid, we conclude
(latten(x)) = Flatten(()) = Flatten(zf) for all i E and E B2( R.). Let == Flatten(ar)) for i E I. Then for i E 7, each robustness ball centered at a is mapped to my We have m, E zn [0, Rd++| for all E I, since
m, Flatten (ax)
R L Rd 20-2(a0'2) +... [dia]
(
3 Rd + 22-2R ....
< nett1
where (a) is by || S R.
Next, we consider the case i E [N]... Note that the lattice distance condition in Equation (24) applies only to the subset {(ar, ler. rather than the entire dataset. result, for indices E [N] \ the distance from the lattice is not guaranteed. Thus, it can lie across the lattice.
For E [M] \ I, we analyze the error of Flatten on the remaining region USE[NTY (2 1/). For
i [N] 7, we have
Un Flatten(()) * Flatten(x:))
P Unil((B [ij [d], Iy. Lx,] S n/)
P PueUni((B(a) (ag [x,] S n'
SE[4
Σ
max
(() [zj Z
ICR Lon(Z)=n'
jE(d
(
2n Va-
Σ
N'Va
jEld
2n/ dVa-1
P'Va
17
where (a) follows from Equation (26) and the fact that Flatten(x)) Flatten(x)) whenever 2j [ay] 1/' for all j [d]. (b) follows from Lemma B. applied to a unit vector u = ej. and an interval Z, and (c) holds by the choice of r/. Hence, we have x
IP (P Flatten(a))
* Flatten(2)] S 1.
(28)
We observe at what happens if Flaiten(x)) (latten(x)) for i E [N] / and x E B2(21, n²). To ensure that no robustness ball centered at æ; for i E [N] / / is mapped to grid index my with different label, namely, satisfying j E with y: yj. we define label-specific grid index sets. For each class e [C], define the set
G. = U (m,) and G = U G. {makkeNT SET
eE(C]
S.C.
where G, is the collection of all grid indices m, assigned to data points in that have label ys In other words, G. contains all grid cells that are claimed by class e. The set G represents valid grid indices.
37

---

Recall that for each E I, the robustness ball By p²) is not intersected by any other robustness ball (z' n²) with different label. Specifically, consider E [M] For j E with y; yj- the robustness ball (2 jz) can have a portion that intersects the grid containing B2(a',, p²), then the portion is mapped to the corresponding grid index mj. However, for j E I with # yj. the robustness ball never intersects the grid, and is never mapped to my. Formally, if Flatten(x)) G.
must be Flatten(z)) Gy, Otherwise, Flatten(x)) & G. i.e., the robustness ball does not intersect any selected grid. Thus, combining the probabilities.
(ne Flatten(()) E Gy. or Flatten(a)) $ G)
P (e Flatten(x) Flatten(x))
21-1,
(29)
where (a) holds since (= [Flatten(z) Gy, or Flatten(z) & G] = 1, and (b) fol- lows by Equation (28). Hence, if we memorize {(m;, y:) her and map other integer N \ {ma her to
zero, B2 n²) for E I is exactly mapped ye, and with high probability 1 17. (2 p²) for i [N] 7 is mapped to either Y/ or O.
Stage III (Memorization) Finally, {(m,, v:) C Zz0 x [C]- Since multiple robustness balls for 'D' with the same label may correspond the same grid index in Stage II, is possible that for some + j with y, yj, we have my my. Let N' < | denote the number of distinct pairs (m,, Vi). It remains to memorize these N' distinct data points IR.
construct the network to memorize [ points
Applying Lemma B.10, obtain neural network fmem with width 12, depth Ö(N), Ö(N%) parameters and bit complexity Ō(N satisfying:
Smem (m) = yi
for every m = m, with i E
0
for every m E N)
For m N, fimm (m) c for some E [C] if and only if m Go. The final network f Rd + R is defined as
fmem aa a Flatten a ftrans.
Let us verify the correctness of the construction.
For E and any x E B(x,, peD), we have
(a)
fuem (m,) (b) fmem fmem(m;) yi-
f(x) fuem o Flatten firaus
where (a) holds since Flatten o o (trans())==a)) (b) holds since m. E N, and (c) follows that f is constructed memorize {[m;, (=)
Next, consider E [N] \ I. observe
P Pee (xx) E {0,y:]]
(E [ Flatten ( E Gy, or Flatten o ftaas (x) G]
(Umif((a((((1))) a Flatten(x') E Gy, or a Flatten(x")) & G]
Flatten(a') (EUni((Bs(((
E Gy, or Flatten(x') & G]
2 1
where (a) holds from the construction of fnem- (b) holds using x' := a o (arans()),, (c) holds by Equation (25) and (d) holds by Equation (29). This concludes the proof.
The depth network firans has width d. Flatten has width 5d and depth O R) and f fmem has width 12 and depth Ö(N2). The total construction requires Õ + d N ) Ō + N
38

---

parameters, where each term d,, d..d dd, and N comes from furans. Flatten, and fmem respectively. The width of the final network is (d) and the depth is ((N
The bit complexity of Strams is Ollo No, log(max [| E [N]])] - 0(1). Platten has the bit complexity O(d), and feem needs at most ((N3) Hence, the bit complexity of the final network is Ö(N d).
B.3 Sufficient Condition for Robust Memorization with Large Robustness Radius
Theorem B.14. Let p E 11) For any dataset E D&,,CC, there exists f with Ó(N p²) parameters, depth Ō(N), width (pp2d) ) and bit complexity Õ(N) that p-robustly memorizes D.
Proof. Let D {{(;;; yi) ME( Da be given. We divide the proof into five cases, the first case under E 11/3,11 1), the second case under E (1/5vd, 1/3) and < 600 600log// N, the third case under E (1/5vd,1/3 and N < 600 log N S d, the fourth case under E (1/5v 1/3), N 2 d 2 600 log N, and finally the fifth case under E (1/5vd, 1/3 and d > N 2 600 6001og N. To check that these cases cover all the cases, refer Figure 6.
E 13 1)?
Case
d < 600 log N?
Case II
N 600 log N?
Case III
d S N?
Case IV
Case V
Figure 6: Different cases Theorem 1.14. The left child is for the answer "Yes", and the right child is for the answer "No"
The first two cases follow easily from prior works, while the remaining cases require careful analysis using dimension reduction techniques. The most interesting cases cases IV and V. While track the width, depth, and parameter complexity for each case, we initially implement them using infinite precision. We address the bit complexity by approximating the infinite precision network using finite precision network at the very last part of the proof. As spoiler, the bit complexity of all cases handled within unified framework using Lemma B.23. Let us deal with each case by one.
Case I: p E [1/3, 1). In the first case, where p E [1/3, 1), the result directly follows from the prior result by Yu et al. [2024]. In particular,
apply Lemma D.2. Let denote R == max4e[N] ||æ and y := (1 p)ED. Note that > ||ævll.o for all [N] as ||0||| 2 ||~||| o0 for all i2d. By applying Lemma D.2, there exists f Fa. with P O(Nd (log(,5) + log R)) parameters that p-robustly memorize D. The number of parameters can be further bounded as follows:
O(Nd{(log( ?
+ log R)) (a)
O(Nd (log( + log R)) (b) Ō(NdPt*)
where (a) is due p = [()), (b) hides the logarithmic factors. Moreover, by Lemma D.2. the network has width O(d) O(p² d) and depth Ô(N).
Case I: p E (1/5Vd,1/3 1/3) and d 600 log N. In the second case, where d 600 600 N and (1/5vd, 1/3), the result also directly follows from the prior result by Yu el. [2024]. In particular, we apply Lemma D.2. Let us denote R == max || and 7 == (1 p)eD. Note that R 2 ||0 for all [N] as | 2 || for all Rdd By Lemma D.2, there exists f FaP with
39

---

P O(Nd (35 log R)) parameters that p-robustly memorize D. The number of parameters can be further bounded as follows:
d 7 + log R)) @ O(oglog))) (log( (م + log R)) (b) Ö(N) ( O(Nd
O(
where (a) is due d s 600 log N, (b) hides the logarithmie factors, and (c) is because N s p2 for all p 3) Moreover, by Lemma D.2, the network has width O(d) Ollog N) Õ(1) Ö(p²d) and depth Ö(N).
Case III: p E (1/5/d, 1/3) and N < 600 log N < d. In the third case, where N < 600 log N and (1/5vd, 1/3). we first apply Proposition B.21 to D to obtain I-Lipschitz linear yp Rd + R such that D' = ((p(x;) vo) HE(N has Ep ED. This is possible as d 2 N.
We apply Lemma D.2 by Yu et al. [2024] to D', Let us denote R =- max (l9((z;) ll2 and
:= (1 - -.)ED. Note that R 2 [| for all E [N]] as I 2 I| for all E RV By Lemma D.2, there exists fi E FN.P with P = O(N _Nog( x>) log Rt) parameters that
N
p-robustly memorize D'. fi has width O(N) and depth Ö(N).
f fi op. This can be implemented by changing the first hidden layer matrix of fi by composing G. This is possible because yp is linear. f has at most dNN additional parameters compared to fi. and has same width and depth fi. Since fi is 1 1-Lipschitz and ED ED. every robustness ball of D is mapped to the robustness ball of D' via /1. As fi p-robustly memorizes D', the composed f satisfies the desired property.
The number of parameters can be further bounded as follows:
d d ( + log R)) (a) O(dlog N + (log [)3. (log(5>) + log R)) Ö(d),
O(Nd+N. 22og((
where (a) due to N $ 600 600 N, and (b) hides the logarithmic factors. The width of f is O(N) = Ollog(())) = 0(1) Ó(påd). The depth of f is Ō(N).
Case IV: e (1/5vd, 1/3), and N 2 d 2 600 600 N. In the fourth case, where d Z 600 log N, we utilize the dimension reduction technique by Proposition B. We apply Proposition B.19 to D with m = m [dp'', [600 log NN, [10 [ log } and = 1/5. Let us first check that the specified satisfies the condition 24a log N < m I d for the proposition to be applied. a 1/5 and m 2 600 log N ensure the first inequality 24a 2 log N I m. The second incquality m I is decomposed into three parts. Since p S 3. we have 9dp² < d so that
[9dp²] < d.
(30)
Moreover, 600 N < d implies
[600 log N1 I d.
(31)
Additionally, as N 2 2, have d 600 N 2 600 log 2 2 400. By Lemma B.22, this implies 10 log d S and therefore
[10log d] S d.
(32)
Gathering Equations (30) to (32) proves d.
By the Proposition B. there exists 1-Lipschitz linear mapping á Rd - Rm and B such that D' = [(((z)), heee E Dm,N.o satisfies
cD N BED-
(33)
5
As m 2 10 d, the inequality
3 2
2 2V
1
7
is also satisfied by Proposition 1. Therefore, we have
m
(a) 1
[9dp2]
1
9dp2
3
B 2 2/ d
2
2 P
(34)
2
2
d
40

---

where (a) is by the definition of m. Moreover, since & is 1-Lipschitz linear,
) l, 0)l[2 ll((z)) o0))l2 S I|=, 0 |
(35)
for all i E [M]. Hence, by letting At == max < 21 we have ||0( S R for all i E [M]
Now, we set the first layer hidden matrix as the matrix W E R corresponding to Φ under the stan- dard basis of I& and R Moreover, set the first hidden layer bias == 2R1 -2R(1, 1...,,,............ 1) R... Then, we have
We + b
(36)
for all æ E (2,,,, ED) for all i E [N], where the comparison between two vectors are element-wise. This is because for all i [N].j E [m]] and x: E (2 ED), have
(a) (Wa x + bb; (W x); 2R 2R W 2 2R ||إ|| 2 2R (R + ED) 2 0,
(6)
where (a) is by Equation (35), (b) is by the triangle inequality, and (c) is due to R > ED.
We construct the first layer of the neural network as f1(x) (W + b) which includes the activation ø. Then, by above properties, D := ((fi(z)). (.) hE( satisfies
6 cD" 5 PED
(37)
This is because for i + with yi * y, we have
(x.) - fi = 10 loo x + b) o (Wa, + bb]l
II x; + b) - (Wa, + bbll
= |(((x,) - o(xx))12
20D'
(c)
4
2 2 x
5 BED
(4)
3
2 x x PED
5 2
12
PED:
where (a) is by Equation (36), (b) is by the definition of the eD' (c) is by Equation (33), and (d) by Equation (34). By Lemma D.2 applied to D" E Dm,N,C, there exists f2 E Fm, with P = ( m + log R")) number of parameters that g-robustly memorize D", where
5 EDD
(a)
1
12
2
3" = (1
2
X
peD = =EPED.
6
6
5
R" = max IE(N]
fi
(x1)
[z;
max (lo(wx, + bbll2 = max =E[N]
WW; + b112
[E[N]
max .E[N]
[Wa + ||b||2 S 3R.
Here (a) is by Equation (37). Moreover fz has width (m)) and depth Ö(N) by Lemma D.2.
Now, we claim that f= f2 fa p-robustly memorize D. For any E [N], take E B2(x, pep). Then, by Equation (36), we have (x) = W x + b and fi (xx)) = W x. + b so that
[ (2:))l2 Wa Wæ,
>;112 2l $ |
2 S PCD.
(38)
Moreover, combining Equations (37) and (38) results [lfi fi (ax))l2 s feo.. Since fa g robustly memorize D", we have
f(x) (f( ((((())))))( ys-
In particular, f(x) y: for any x (2 pcp), concluding that f is a p-robust memorizer D. Regarding the number of parameters to construct f. notice that fi consists of (d 1)m Ö(d
41

---

parameters as m (ddp)). fa consists of O(N2²) O(Nd assumes N 2 d and large p regime deals with p 2 5vā'
parameters. Since the case IV
have
dp Ndp² < p
Therefore, f in total consists of Ó(d'p² + Nd p²) p(N)Pp") number of parameters. Moreover, since / has the same width as f2 and depth one larger than the depth of /2. it follows that f has width O(m) (ppdd) and depth O(N). This proves the theorem for the fourth case.
Case V: p E (1/5vd, 1/3), and d 2 600 log N. The last case combines the two techniques used in Cases III and IV. We first apply Proposition B.21 to D obtain 1-Lipschitz linear yp R - RN such that D = {(p();), 36) HEEN) E DN,NCC has ep = ED. Note that we can apply the proposition since d N.
Next, we apply Proposition B.19 to D' E DN.N.C with m = m p²1. 6600 log N]} and = 1/5. Let us first check that the specified m satisfies the condition 24a 2 log N S m S N for the proposition to be applied. The second inequality m I is decomposed into two parts. Since S 5. we have 9N p² s N so that
1/5 and m 2 600 log N ensure the first inequality 24x log N < m.
19Np'1 S.N. N.
(39)
Moreover, 600 log N < N implies
600 log N S N.
(40)
Gathering Equations (30) and (31) proves m S N. Additionally, as N 2 2, we have N 2 600 log N 2 600 log 2 2 400. By Lemma B.22, this implies 10 log N < N.
By the Proposition B.19, there exists I-Lipschitz linear mapping Φ : RV R and such that D" = {()({<()))), y1 hE] E Dm,N.c satisfies
4
CD"
Sc 5
(41)
As 600 log N Therefore, we have
10log N, the inequality 3 2
2 V
is also satisfied by Proposition B.19.
2V m 1
9N 2
1
9Np²
B
N
2
N
2
N
2p:
(42)
where (a) is by the definition of Moreover, since &p and @ are both I-Lipschitz linear, o op: R2d + 1Rm is also I-Lipschitz linear. Therefore.
(()(p(()))) |l [1ő(p(<; 0)) l22 (l((p((;;) - (()())) S ||= - O1l = |2ll|
(43)
for all [N]. Hence, by letting R max4e[N] 112, we have [}((((;))) S R for all i [N].
Now, we set the first layer hidden matrix as the matrix W E Rad corresponding to Φ o under the standard basis of Rd and R". Moreover, set the first hidden layer bias as = 2R1 1, 1) E R Then, we have
Wx + +
(44)
for all æ E B2 ep) for all e [N], where the comparison between two vectors are element-wise. This is because for all i E j E [m] and x E B2(x, <D), we have
(a) W [ 2R - ||ا|| _
(
(Wa x + b); = (Wa) x) + 2R 2 2R
2n (R (R+ep) 0.
where (a) is by Equation (43), (b) is by the triangle incquality, and (c) is due to R 2 Ep.
We construct the first layer of the neural network as f1()) == (WW x + b) which includes the
activation a. Next, we show that, D" = {x:() (() satisfies
6
cD" 2
5 PED.
(45)
42

---

by the above properties. This is because for i * with ys * yj we have
(x,) f1 = (Wo + b) o (aa b)ll
(0) II(Wa: n; + b) - (Wa, b)ll2 |10()((x))) <((((x)))]
2cp"
- 2 x 36D
5
(
3
2 2
2 PED
12
5 PCD
(c) 12
5 PED,
where (a) is by Equation (44), (b) is by the definition of the ED (c) is by Equation (41), (d) is by Equation (42), and (e) is because eD ED.
By Lemma D.2 applied to D" E Dm.Ncc, there exists f2 E Fm,P with P = O(Nm (log( log R")) number of parameters that g-robustly memorize D", where
m
5
(a)
1
12
2 pcD 5DDD
>" (1 DD"
2
x
6
5
R" max K
| (xx))l2
max NE[N]
llo b)ll2 = max iE[N]
[W + b112
max sE[N]
12 + ||b|| S 3R.
Here, (a) is by Equation (45). Moreover, f2 has width ((m) and depth Ö(N) by Lemma D.2.
Now, we claim that f2 fi p-robustly memorize D. For any E [N]. take x E (2(x,,
Then, by Equation (44), we have fix = W x + b and fxx = W b so that
[x - - fz.))l1
Ww Wa, 11 $ | 2: 2 S PED.
(46)
Moreover, putting Equation (45) to Equation (46) results [| (xx) - fi (xx) - ReDr. Since S2 5 6 g-robustly memorize D we have
f(x) = =e(((()))=(((((()))) yi-
In partieular, f(x) y/: for any æ E (2 peD), concluding that is p-robust memorizer D.
Regarding the number of parameters to construct f, notice that fi consists of (d + 1)m Ö(Ndp²) parameters Ó(Np²). fu consists of Ó(Nm²) = Ō(N3pp) parameters. Since the case V
assumes < d and large regime deals with 2 5va we have
Ndp² < 25. N < pd
Therefore, ff in total consists of Ö(N' + Ndp²) d( number of parameters. Moreover, since f has the same width as f2 and depth one larger than the depth of f2, follows that width of is ((m) Ö(p²N) O(p2d) and the depth of is Ö(N). This proves the theorem for the last case.
Bounding the Bit Complexity. Now, let us analyze how we can implement the above network under finite precision. We have demonstrated that for every five cases, the depth Ö(N) and width pdd suffice for constructing f that robustly memorizes D.
43

---

Let : == maxie(N | + μ.. Let D == =(p'd) and L = (N) denote the width and the depth of the constructed network. Let M be the maximum absolute value of the parameter used for constructing f. Finally let v 0.1. By Lemma B.23, there exists with ((N) bit complexity, that approximates f uniformly over (0, Rt) with error at most v, where Ō(-) here hides polylogarithmic terms in D, M, L and R. i.e.
max | - Su. |
Finally, to handle the error v, we use the floor function approximation from Lemma B.16. By Lemma B.16 with 7 1/10, there exists Floor R such that Floor(æ)) [ for all æ E [0, 1) with [a] 7 0.1. Moreover, the lemma guarantees that Floor can be exactly implemented with O(n + log 10) Oloog C*) Ó(1) bit
with depth : [log, (C 1) and width
complexity.
Thus, if y E R satisfies ly' S 0.1 for some y E [C]. then
y' - 0.5 E yy - 0.5, 0.1 0.5] S (v + 0.1,
In particular, W + 0.5] = y and Ly/ 0.5| - (y/ + 0.5) e (0.1.1) so that Floor(y)) | = y. For E (2 p),, we have f(x) = 1/4 so that the approximation f outputs y' = f(x) such that
[(x) [a)) /// yil S v.
This shows Floor(f(x)) Floor(y/) = yı- Moreover, Floor o can be implemented with parame- ters, width, and depth of the same scale as f. and bit complexity Ö(N). This finishes the proof for the bit complexity.
B.4 Lemmas for Lattice Mapping
Lemma B.15 (Avoiding Being Near Grid). Let N, d E N and " Rdd Then, there exists translation vector E Rdd such that:
dist(E - by,
2N Vi [NE,j E [d].
i.e. the translated points (x, - bl are coordinate-wise 2N far from the integer lattice.
Moreover, there exists b E Rdd which has bit complexity [log(6N)] and satisfies
dist(x - b) 3N'
Vi [M,j E [d].
Proof. For each coordinate j E [d]. consider the set {xi, HEIj of all j-th coordinate values. For x E RR let {z} = x - [a] denote the fractional part of x. We consider the collection of fractional Without loss of generality, may assume 0 < {II.)) < {x2.i < <
parts
(KN.) <1. 1.
For each j E [d]. define the maximum fractional gap Oj E [0, as
((x++1.) - (1i (IN.S} + (Bnss)
9j = max max iE[N-1]
claim:
9j N' for all j E [d].
Suppose for contradiction that gj < N for some j E [d]. Then, we have by the definition of gj.
1
N-1
N -
(KNS) (x1,) = Σ (1141)) (xir)) S 1)g, <
(47)
N
i=1
1
N
1 1 fIN,rt + {x1,}} } S 9j
<
= -
(48)
N
N
44

---

Equations (47) and (48) lead to a contradiction, proving the claim.
Now, define the translation of the j-th coordinate, bj IR, based the location where the maximum 9j is attained. If the maximum in the definition of gj occurs by the difference of some consecutive pair (( (1e+1.g)) satisfying (5v+15) { Dj. we set
{xy } + {oe-1.5)
bj
In this case, ( by, 2) = dist (1y41. by, = ž0 2 2N For other i, dist(ar, - by. 2) even larger by the order relation within {f2r,))ie(N)
Otherwise, if the maximum in the definition of 0j is attained as - {2Ns) + {21 9ý. we define
(fxN,)) - + fa1,r}
by
In this case, dist(r11 - b,, = dist(xn,, - b) 20: 2 2N J. For other i, dist(xi. - b,. 23) is even larger by the order relation within {[Ii,] lie|N-
We define the full translation vector b (b1....,ble ba) Rd. Then the translated points {x, be satisfy:
dist(xi, by. Z. 2 2N'
for all E [N]. [d].
Intuitively, by is chosen as the midpoint of the widest gap between fractional values, ensuring that all fractional parts after the translation are at least & away from the nearest integer. Therefore, the 2 -far from lattice points.
translated points are coordinate-ve
We define 5 such that each its coordinates equal the first [lo(6NN)] bits of the corresponding coordinate of b. Then, for all j E [d], we have (by - byl < 2ingienT S EN Using with bit complexity [log(6N)], we can still ensure the distance 3N from the lattice points.
1
dist(r bj. 2) dist(xrj - b,. 2) -bb b,9
for allll i e [N], e [d].
2N
GN
3N
The following lemma shows that we can approximate the floor function using logarithmic number of ReLU units with respect to the length of the interval of interest.
Lemma B.16 (Floor Function Approximation), For any n E N and any y E (0, 1), there exists an n-layer network Floor, with width 5 and 5n ReLU units such that
Floor, (x) [x] for all x E [0,2*) such that |x|
Moreover, if= =
for some E N, then Floor, can be exactly implemented with 2n + log, bit complexity under fixed point precision.
Proof. To reconcile discontinuity of the floor function with the continuity of ReLU networks, we first define discontinuous ideal building block that exactly replicates the floor function the target interval 2". We then approximate this building block using a continuous neural network with ReLU activations.
The ideal building block A is defined as:
2x
if E (0, z):
A(x) = 2x -1
if E (2, 1].
otherwise.
For N, define the function Floor, by:
Floor, (2) Ax)= 2n
+ +1)+r--
45

---

We will show by induction that Floor, |x]] for all x E (0,2%). For the base 1,
2 (2(- 2 1) -1+
if [0. 1),
Floor (x) = A(- 2 +1) x
2( x -
if E 2), otherwise.
00+ x 1 -
This proves the base case: for all E (0, we have Floor (x) |x].
For the inductive step, assume that Floor, (x) [æ] holds for all [0, 2*). We aim prove that Floor (x) [x] for all x E [0, 1m+
Recall that:
+1
if E (0,2%)
(+
+ 1 (2) 1I),
2
2
A 2
+
I
+2
2
x-2 2
i E 22",2*t]
(+
I
+ 1 E (0, Z)
2
2n
2n+1
otherwise.
Thus, have
Floor a (x) = A n+tl
+ +1) +
2
= A
+ +1)) + -
2n+1
A"(
+ +
Floor, (x) | Floor, (x 2n) + -
if x [0,2"),
2"
A
+ +
if E [2n, 2nt
2"
A" + +
otherwise.
Therefore, by induction,
Floor, [x] for all [0,2").
Next, we define the a approximation A 7.n the discontinuous block A as:
(x) 20)
x
+ 77
+ _ x 2
In
2
Yn
1 7n
-- -
o (x- +
o (I 1),
(49)
In
where 7,. 3 Check Figure 7 for illustration of how Ay, looks like on [0, 1]. It straightfor- ward to check that
(x) = (xx) for all x E [0. - 7al unlu(? 1- 1-7
1 7v
Figure 7: Plot of the ReL.Ubbsedd approximation D (Ir) of the ideal discontinuous building block A (z) on (0, 1].
46

---

We now explain why this approximation remains valid under recursive composition up to depth n. Let define the variable x' == 2 + 1, that 21 x') and x' (0, 1]. Our target function is:
Floor, (x) = A x We are given the assumption I - |æ| > y and we aim to express this in terms of x' to ensure
+ + - 1 A (a + x
2
Arn (x') = (z"x). We proceed step-by-step:
[ 7
= 21 -01-x') x') 12 - d')2> >7
- 22" - 1--2" >7
= 22" + 12"x'> >?
- 2" < <12"x'1 -9
2"'' E (12"x'1 - 1 -7)
2n U (k: - 1, 77
kEZ
k 1-11 k -
x'
E
2
2n
KEZ
Since x' E (0, 1], we only need to consider
E i.e.
s'
U
-
k
2
2
kE(2"]
We will now prove by induction on the following statement:
h-1
k -
For any E (0, A,, (x) = (x))) for a E
2n
2
kE[2")
For the base case n = 1, by construction of (x)), we know A , (I)) (xx) for all x [0, 1/2 31 3). which contains the union UkEp k-1 1=
Hence the base case holds.
For the inductive step, assume the claim holds for n. We show it holds for n + 1. By using 7/2 in place of 7 for the inductive hypothesis, we have
/222 (x) Dy,+ "(x) (x)x) for al
U
k-
k -1122
(50)
2
2
kE(2"]
Let x E UkE|2nt1 x ) We analyze two cases based on x E [0, } or x E 1).
First, consider the case E UkE|e4]
k-y Z 2
C H). Then x < k-7 S 1n+1, 80
A = 2x. Let y = 2r. Then:
k k 7/2
y E
2n
2
2
2n
k<(2")
AE
Thus, we have
n+1
A
A
(x) = 7,n+1
=
(A,nt
(2))
A -,,11
(2xr)
1 (3)
(a)
(y)
47

---

(2x(2x)
=A"+1(a
where the equation (a) follows by Equation (50).
Second, consider the case x E Ukg [M2m]
k-1 k-y 2 1 2
C
12 1).
Then
S x
<
2
k-?
S
1 - 1, so y (I) = 2x 1. Let y 2r 1. Then:
U
k 2
1
k 2
7
1
k
1
k 7/2
y E
2
2
2
2
2
2
kE|2***[\(27)
ke(22)
ke
Thus, we have
A
7
n+1
(x)
=0 7,0+1 11
( 7,, (,,+1((4) (2))
nm+1
(2x-1) - 1)
7
(v)
(a) AV(
A A - 1)
= = (x),
where the equation (a) follows by Equation (50).
Therefore, by induction, we have shown that for any E (0, and any n E N.
k --1 1
h: 7
Dy, (xd') A (x') for all x'
U kE(2n)
2n
2
We now define the ReLU-based floor approximation by
Floor, 4n." 10
(- 2
+1
x
(51)
Recall that the ideal target function is given by
Floor,, (I)) A
+
+ x - 1.
2n
Let us denote x' ==- 2 1. When xf
[ > the value x' satisfies
a' k k-?
2
kE[2"]
"x') so that A,, (x') = "(x') by the result above. Therefore, we conclude:
Floor, (x:) Floor, (xx)
[x] for all x E [0,2") such that [ 7
Finally to prove the additional statement regarding the bit complexity, consider the case 7 for some E N. By Equation (51), the bit complexity to implement Floor, upper bounded by n plus the bit complexity implement A Now. it suffices to consider the bit complexity required to implement A. From Equation (49), observe that 1/Th 2 /?- 2n for ? 1/t. Since t N, this can exactly implemented with log(2" 1) = n + log, bit complexity. Thus, Floor, can be implemented exactly with 2n log, f bit complexity.
B.5 Dimension Reduction via Careful Analysis of the Johnson-Lindenstraass Lemma
We begin with lemma that states concentration of the length of the projection.
48

---

Lemma B.17 (Lemma 15.2.2, Matousek [2013]). For a unit vector a E Sd-1, let
(xx)) (x1, 22, ". Fmm
be the mapping of a onto the subspace spanned by the first mn coordinates, Consider x S chosen uniformly at random. Then, there exists B such that [[b(@))l2 is sharply concentrated around B.
Pll 23 3- - 1 2e Paj2 and P(lo(())) 3 - 2e
- Pa/22
where for m 2 10 10gog d, we have 3 82 222V 2V
Based on the above concentration inequality, we state the which reflects the benefit on the ratio of the norm preserved when the projecting dimension increases. The proof follows that of Theorem 15.2.1 in Matousek [2013] with a slight modification.
lemma, in version
Lemma B.18 (Strengthened Version of the Johnson-Lindenstrnn be an N point set. Then, for any a E (0, 1) and 24a -2 log N I m S d, there exists a I-Lipschitz linear mapping à Rd + mm and 3 > such that
Lemma), For N 2 2, ler X B
a) -
x' 1l2 S llo(x) o(x') 112 S (1 + aa) x'1l2
(52)
for all w, w' E X. Moreover, 3 3 whenever m 10 10
Proof. If x x', the inequality trivially holds for any 6. Hence, suffices find that satisfies Equation (52) for all x, E X with x + x'. Consider a random m-dimensional subspace L, and & be a projection onto L. For any fixed x + x' e X, Lemma B.17 implies that concentrated around some constant B. i.e.
inequa
is
||0 m
P
x' )
> (1 + a
$ 2e 00
(b) (a) < 2e - m
< 2e 3lg N
2
x
N3
N2
where we use 3 N 2
m
at (a), m 2 24a
2 log N at (b), and 2 2a at) (c). Similarly,
x x' 2 )
x x'
Φ
<1 - a)
<
N
By linearity of d. we have <(x - x') = 6(x) - 6(x'). Taking the union bound over the two probability bounds above, the following event happens with probability at most 2/N2:
[|Ø(z) (12)) 2 (1+ a)3 o
x' z'll2 or (lo(x) - 6(x')l2 I (1 - a) - - x' 22112
(53)
Next, we take a union bound over all N(N-1) pairs n, x' E with + x'. Then, the probability 2 N2 N(N-1)
2
that Equation (53) happens for any x, x' X with # x' is at most
N 1.
2
Hence, there exists m-diimnnsional subspace I. such that Equation (53) does not hold for any pair
of x. x' X. In other words, there exists m-dimensional subspace T. such that
(1 2 I x'112 I [lx(x) <(x')l I|2 - (1 + a) || =''l2>
for all x * x'. By Lemma B.17, 3 2 whenever m 2 10 log d. This concludes the lemma.
Proposition B.19 (Lipschitz Projection with Separation). For 2, let D = ((x,, H DAN.C.. For any a E (0, 1) and 24a log N S < d, there exists 1-Lipschitz lineur mapping 6. Rd R and B > 0 such that D' = (()())) ( Dm,,.c satisfies
6 2 (1 BED.
In particular, D' Dm.,NC whenever D E Dd,NCC- Moreover, 3 2 1/4 whenever m 2 10 log
Proof. Let X = ( By Lemma B.18, there exists 1-Lipschitz linear mapping Φ: R + R and B > 0 such that
- (1 |æ: 22 S [| o(2;))12 $ (1 + (1+ 2,1122
(54)
49

---

for all i.j E [N].
The inequality ep (1 B)) follows from the inequality from Lemma B.18. In particular,
1
min (lin())(z;)) - 6(0x))12 i.j E [N] and ys * yリ
2
(a) 1
2 2
min - a.)3 ||= +,ا12 1,j [M] and yE + yz
1
ز.j E [AV] and y + ys} (1 a3 x minf|l 8اار2
= (1 - BED:
where we use Equation (54) at (a).
We next show D' E D M whenever D Dd.N.C. C. To show this, need to prove ((x.) + d(x,) for all * j. Since - a > and 3 > O, we have [Ø(x;; p(z;))l, 2 (1 a) | وjllg > whenever 22 of z.. Moreover, D Da,N.G indicates that æ; + æj whenever i + j. All together, have o (x)) # ((t)) for all i + j so that D' E -D,.NO..
Lemma B.20 (Projection onto log-scale Dimension). Let E Da.N.c- Then, there exist an integer m = Óloo N) and a 1-Lipschitz linear map Φ : Rd - R such that the projected dataset D' WNM E Dm.N. satisfies the separation bound
5 6
12
d ED.
Proof. Let 1/6 and m == min (d, maxx[244 -2 log N1, [10 d]}}, then m Ö(lg N). We construct the linear mapping into m dimension by dividing the cases into d < 24a log N or 2 24a 2 log N.
For the case d < 24a log N. we have d < max m log N1, log d]}, and therefore
m = d. We consider the identity map Φ Rd - (= Rm)) which is 1-L.ipschizz. We have D' = (()(x;), veee = ((...))) = D, so that eD = ep > ED = 5 / ED.
Otherwise, for the case 24a-22og N, we first observe that m S d. Since 24a 2 log N < d, we have
244 2 log N S d.
(55)
Additionally, as N > 2, we have d 2 24a log N 2 864 16g 2 2 e By Lemma B.22, this implies 10 log d S and therefore
[10log d] S d.
(56)
By Equations (55) and (56), we have max maax[12Aa=* 12a log N1, [10 log d} < d. Thus, it follows
m = max[[24a log N1, [10 log d S d. By Proposition 19 with a 3. there exists 1- Lipsehitz linear mapping Φ Rdd - R.m and > such that D' ((0(2;). 91) satisfies <D' 2 BeD. Since m = max [ [ log N7, [10log d]} 2 10 log d, the inequality 3 2 2V m is 5
also satisfied by Proposition 19. Therefore, eD 2 B 2 12 / TED.
In both cases, we have I-Lipschitz linear map & such that D' = { (<(.)) yi) beeNNN has separation
5 m
< 2
ED-
12
Proposition B.21 (Natural Projection of High Dimensional Data). For d N, let D ((mi, v:)he([N] E DaN.c. Then, there exists 1-Lipschitz linear mapping Rd + IR such that D' = ((p((,)) (((g(a:)),))eee yiheen E DN.NCC satisfies
ED ED
50

---

Proof. Consider the tall matrix X E R N defined as
X
(57)
Then dim (X) - N Σ d. Take any subspace V such that Col(X) S CV& C Rd and dim = N, and let = {v1,-.. UN| J be an orthonormal basis of V. Let V E gdxN be the matrix whose columns consist of vectors in B:
11
2/2
UN
Define o IRd + RN ((x)) = V x. We first verify that is I-Lipschitz. For any E R4 let x = BV + vv- where æv E V and av E V-. Then, ev Vz for some 2 E RN, as æv E Col(V). Moreover,
V V (av + +BV))
VTay +0
= V
INZ
= 2.
(58)
Therefore, we have
(c)
V x 2|2
|
| 12
S
|
(59)
where (a) by Equation (58), (b) is because | 12 [EEEN 2,00
EiEN 2f ||=1||- and
(c) is because ||011/ = | 1/2 + Ævi 12. Moreover, whenever E V, then the equality holds for
(c) of Equation (59). Therefore,
V T x 20| || for all x V..
Since y linear
11((x) (xx'))122 = 1| x:) x')112
V (x: xx )|1
- a' ll2
where (a) by Equation (59). This shows that yo I-Lipschitz.
Next, for i.j E [VV, we have
[1p(())) - - = |1<p( 21))
|| (xr; 2x,) l12
|0; xz 22
where the last equality holds because - æÿ E Col(X) C V.
This shows that
CD min (1lp(())) - <<x;))l y1 + v,
2
Di イッ} min [1aa; 2,
cp-
This shows that D' also has the desired property.
Lemma B.22. Fort 2 ea, have 2 10 t.
51

---

Proof.
Define u(t) = t 10gog on the domain (0, oo). Then, for all t >> 10,
du 10
>
dt
so that is an increasing function oo). In particular,
u(E = 10loo(e") =
0
This concludes that u(t) 2 0 for all 2 e², or equivalently, 22 10 for all 2 e
L
B.6 Lemmas for Bit Complexity
The following lemma bounds how much bit complexity is sufficient for implementing the parameters of the neural network in order to obtain the required precision the output. Note that we not require the network to output scala values. i.c. the following lemma also applies to neural networks that output vectors.
Lemma B.23. Let be neural network of P parameters, depth and width D in which the parameters have infinite precision. Let R 2 be the radius of the domain in which we want to approximate J- If all the parameters of are bounded by some M 2 then for any < u < there exists f. which is implemented with P parameters, depth L, width D, and O(L) bit complexity such that
|| 1f1l2= SV.
80 SR
where Ö(-) hides a polylagarithmic dependency on D, M, L, R and 1/v.
Proof. Let f I2d + IR be the neural network defined as
ag x
ag oWW (Waas-i(22 (x)) + be) for é 1,2, f(x) (a(aa-1) + bL.
where W, E Rdexde 1, b, E R with d, - D for l E [L]. Although a, depends on æ for all t= 0, ... L- 1, we omit in the notation. Note that do = d. Given that every elements of W, and b, are bounded by M, for any < < < M, there exists W. and by that can be implemented with [logg(M/C) bit complexity in which
Wr Wello SC | belloo SC
Using the approximated parameters Wt and by, we recursively define f 1dd the finite-precision approximation of f.
āg
a, o (W, (x) by) for é = 1,2, 1.
f(x) W,. (a. bi..
Similarly, although â depends on æ for all 0, O,... L - 1, we omit x the notation.
Let us denote the difference of parameters as AW, = W; We. Ab; == b, b, for f E [L] and the difference of layer outputs Aa; a. as for [L. 1].
straightforward to check
[W&ll S [Wellr S 1 M S DM
bell VdM S VDM
AWW/ < |AWell S Vdidi-is < DC
| Vdcs 5 VDC.
where the norm ||:|| and |1 for the matrix denote the spectral norm and the Frobenius norm, respectively.
52

---

We first claim that there exists degree 2L + polynomial S on D, M, L and R such that |aell2 S S for all & [L 1].
aaill2 1o + bi)ll2
Wtas-1 + bell2 ll2
Well |a-_1ll2 ||bell2
DM |ar-1ll2 + VDM.
Thus for all & [L 1].
a0el22
VDM (DMME--1 + (DM) 1aoll PElA
(DML S
This proves the first claim. Moreover, composed of two monomials whose coefficients are all 1.
We next claim that the error || < QC for some degree 4L + 1 polynomial Q on D, M,M, L and R. Consider the following recurrence
Aaz l2
0g
aell2
|o + by) (W bi)ll2
(Wiar-1 + b.) (Wea-- + bb)ll2
II((W: + (a- Aa, (b, Abi)) (Wa b:)ll2
||AW;a;11 1,:h+:WWa::--10 + A A + Abell2
< ||AWell + | A A
A |Aar-1l2 + 1|Abell2
< DÇ ||a DM A + DC Aax-1l2 + +DC
(DM 12) ||
(1) a VDK
< (DM + DC) 1|a + (DS + VDJC.
Thus noting that Aag x - x = 0 we have,
||ry- - (DS+ + VD) Σ (DM + DCY-11
(E(L-1)
< (DS + (DS+VD) VD) (x
L(DM + DC)
< DL(S + 1)(M+++++++ +
< DL(S + 1)(2DM)
where the last inequality follows from Ç S M. Let Q = DL(S + 1)(DM)) Since S is
degree 2L + polynomial on D, M, L and R. follows that Q is a degree 4L + polynomial on M,M, L and R. This proves the second claim. Moreover, Q is composed of three monomials whose coefficients are at most 24.
Thus.
[[((x) - f(x))l [W by) W
< (K(WW, AWr)(a + dat-1) + (b; + Abb)) - (Wrar-1+ + bb)ll JAW LWWaa,-1+ W, + AW, + Abils
+ +1W Aar, + ||bbyl22 + DM || + DC ||A0,-111, + vDg
||
DCI|at-1l,++
DCS +MM DÇQC D(
(DS + DMQ + DMQ+DMMQ + D)Ç.
53

---

where we use S M in the last inequality. Now, by letting Ç = D842DMQ+D it follows that
[](()) 1 S
for all æ with || I R. Thus, it suffices to have logg(M/() (DDS 2DMQ + D)M/v) bit complexity to attain an approximation of accuracy uniformly over the bounded domain with radius R. (DS + 2DMQ + D)M is a degree 4L + 4 polynomial on D, M. L and R. Morcover, it is composed of + 3 + = monomials, whose coefficients are at most 2 Hence, it follows that
log2 (M/{) logz (DS 2DMQ + D)M/v)
I loga (6 2 x (DMLR) ())))) + log(1/v)
(o (2DMLR) + log(1/v))
(())
bit complexity suffices.
54

---

C Extensions to ---norm
In this section, we extend the previous results on æ2-norm arbitrary p-norm, where p oo].
In the following, we use distp(::)) to denote the lp norm distance between two points, a point and set, two sets. For the case d = omit the notation since every ey-norm in 1-dimension denotes the absolute value.
We denote (a, n1) {a' 1 - æl1 (a) open e--ball centered at with radius μ..
Definition C.I. For D E DaN,o the separation constant eD,, under e--norm is defined as
CD, = min (1 F lp (ax, Ui). (I) D, Di リj}
As consider with æ; + 2, for all i + j. we have ED,, O. Next, define robust memorization under f--norm.
Definition C.2. For E DaN.Cc. E oo], and a given robustness ratio E (0, 1), define the robustness radius as μ = ptD.p. We say that a function f R2 + lk p-robustly memorizes 'D under the lp norm if
f(x') ye, for all (æ;, 9:) E D and x' E Bp(x..))
and (2,,, (4) referred as the robustness ball of s;--
Similarly, extend the notion of p-robust memorization error Lp-norm.
Definition C.3. Let D E Da.Nce be class(or seiatt--eparated dataset. The p-robust error of network f Fd + R. on D under the f--norm is defined as
Cp max P (a + vil, where μ = pCD,p (or μ = pé)
The following inclusion between p-norm balls with different p-values is well known.
Lemma C.4 (Inclusion Between Balls). Let 0 < p < g co. Then, for any a E Rdd and > 0,
(x, S (a, C B, d - 11),
or equivalently,
(, - S B, u) C (x,
For any p oo], let us denote
(rld)) dl
throughout this section. For 0 <<<<9> 0o, we have
CD.g S CD. I d cD..
(60)
since |,0||,, S ||00|
5 d | |,01 In particular, we have
eD < ED2
when 2 2,
(61)
cD, 7p (d)
when 2.
(62)
C.1 Extension of Necessity Condition to t--norm
Theorem C.5. Let p E (0, 1). Suppose for any Da,..2 there exists a neural network f E Fa.P that p-robustly memorize D under normm. Then, the number of parameters P must satisfy
P Q (0²² min((Nd) d) + 1) d min - Vd VN Vd)VN)ifp2> ifD22.
P= ((()e)) min (N .,d, d) + d + min Vi-pp va VN if f11$p<2
55

---

Proof. This follows by combining Proposition C.6 and Proposition C.8.
Proposition C.6. There exists D E N.2 such that any neural network 18. RR that p-robustly memorizes D under Ey norm must have the first hidden layer width at least
MinnnN d) 2
( %p(d) min - s
Proof. We take the same dataset as in Proposition 3.2. Recall that in the proof of Proposition 3.2, take the dataset D () U {0, when N I d + with additional data points d)e1. 2) when N fp-norm for all 1, on the both case N < d -d++1 and N > d + 1. Let f be neural network that under f,-norm. Since CD,p = cD,2, the robustness radius μ under mnrm
(2e1, 2), (3e1. 2)................... ... ((NV
+ 1. This has separation eD,p 1 under
robustly memorizes satisfies PCD.p = pCp,2. With this in mind, we now prove the proposition. The statement of the proposition consists of two parts, p and p
Part I: 2 2. First, we prove the result under 2 2 Robust memorization under fp-norm implies
f(x) y: for all (æ,, v1) D and a E Bp(x, p),
where μ = PCD,p = p.p.2- For p 2 2, we have B2 (2 10) S Bp(a, (4) by Lemma C.4. Thus, f(x) = ys for all (z,, E D and æ E (2(x;.))
Since μ = p,D,2 this implies that f p-robustly memorize ID under no-m By Proposition 3.2, f should have the first hidden layer width least p² min 1,
Part II: 1 S < 2. Next, we prove the result under 1 S < 2. Robust memorization under norm implies
f(x) yi for all (æi, v:) D and By(as,, pi)
where μ PéD.p pED.2. For S p < 2. we have B2(x, d' d by) S Ba p)) by applying and to Lemma C.4. Since (p(d) = d we have B2 (d)p(d)) S (p,,, In particular, J memorize every (d) neighbor around the data point under norm.. Let
p' = (d) PCD.2/7p(d)
P
cD2
cD.
(p(d)
Then, f memorize every (d) = p'Ep.2 radius neighbor around each data point under f--norm. In other words, p' -robustly memorize D under forno By Proposition 3.2, f should have the first hidden layer width at least minn - -1, d). Putting back p' (d( concludes the desired statement.
Proposition C.7. There exists point separated E Da,N.2 such that any neural network that p-robusily memorizes D under loc- -nom must have the first hidden layer width at least
min N - 1} if E (1
min(d, - 1} p p 1).
Proof. The first bullet an immediate corollary of Proposition C.6, so we focus on the second bullet for 1//,
1). To prove the second bullet, we consider two cases based on the relationship between - and In the first case, where N hidden layer has width at least N 1. In the second case, where N 1 > d, the required width is least d. For each case, we construct dataset D Da,N.2 such that any network that p-robustly memorizes D must have first hidden layer of width smaller than the corresponding bound.
d, establishing the proposition requires that the first
56

---

Case I: - d. Let D = f(e 2)beeN U {)). Then, D has a separation constant ED,00 1/2 under lo- -nom. Let f be a p-robust memorizer of DD under Loo -nom whose first hidden layer width is m. Let W E IR denote the first hidden weight matrix. Suppose for a contradiction, m 1.
Let = pép,oo denote the robustness radius. Then, has to distinguish every point in each (e,)) from every point in (0) for all j E [N - 1]. Therefore, for Bxc (eg, μ)) and x' E (0, u)) we have
W Wa',
or equivalently, x x' o W)) Moreover
(e, (0, 11) = {x - x': x E Beo(e and w' E Box (0, = Bxx 2p).
Hence, it is necessary have Boc (ej, 2p) n Nu) 0 for all j E [N 11, or equivalently,
dist (ej, Null( 2/4
(63)
for all j [N- 1].
Since dim C)l(WT) < dim R = m, we have dim Null(W) 2 d - m. Using Lemma C.10, we can upper bounds the maximum possible distance between {ej}JE(N-11 S Rd and arbitrary subspace of fixed dimension.
Take Z S. Null(W) such that dim d m and substitute d d, N 1, k- m and Z = Z into Lemma C.10. The assumptions t S d for the lemma are satisfied since N N d. The additional assumption & 2 d + is equivalent to m 2 d - (N - 1) + 1 and is satisfied since m N 1. Therefore, we have
1
min dist. (e,, 7) JE[N-1]
By combining the above inequality with Equation (63),
(o) min distoc (ej, jE
2μ < min distoc Nu)l(W))
(64)
JE(N-1)
2
where (a) is due to Z S Null(W).. Since ED,cc 1/2, we have 2p D p so that Equation (64) becomes Σ 1/2. This contradicts our assumption p E (1/2, 1), and therefore the width requirement m 2 N is necessary. This concludes the proof for the case N - d.
Case II : N d. We construct the first d + 1 data points in the same manner as in Case data points, we set them
I, using the construction sufficiently distant from the first d + data points to keep <D.x0 1/2. In particular, we can set Jd+2 = 2e,, Id43 = 3e1,... xx = (N - d)e; and yd42 = Md+3 = = YN = 2. Compared to the case N d + L, we have <D,oc unchanged while having more data points memorize. By the necessity for the case = d + 1, this dataset also requires the first hidden layer width at least (d + 1) d. This concludes the statement for the case N - 1 > d.
N = d + For the remaining N -
Combining the result of the two cases N S d and N
concludes the proof of the theorem.
Proposition C.8. For E (1, letp (1. (1) Suppose for any D E Da there exists E Fa,P that p-robustly memorizes D under E, nornommm Then, the number of parameters P must satisfy P =
=Q( 2 )
Proof. The main idea of the proof the same as Proposition 3.3. We construct
1 1 1-
number of data points that can be shattered by Farr. This proves VC-dim(Fa.r) 2 1 9(N/(1 - p²)). Since VC-dim(Fa.p O(P²). this proves P= = (B(/N/( pP)).
x
LT-PP
57

---

For simplicity of the notation, let us denote k == 1--p= J. To prove the lower bound on the VC- dimension, we construct
_ points IR that can be shattered by Fa As the proof of 2 x k number of points as [ groups, where each group consists of l
Proposition 3.3, we define points.
N
We start by constructing the first group. Since E (0, (Z)))) we have A = | E [1, d... The first group Xi : {e,} C Rd is defined as the set of the first & vectors in the standard basis of Rd. The remaining | 1 groups are simply constructed as translation of A1. In particular, for I IL 2 ]], we define
Xi = c; + X1 = (c + x {1}
where c = 22 1) x e₁ ensures that each group is sufficiently far from one another. Note that e 0 ensures X1 also satisfies the consistency of the notation. Now, define X' UIEIL//2/ the union of all ] groups which consists
] points.
We claim that if for any D E Da,N.2, there exists f E Fa.P that p-robustly memorizes 'D under lg f--norm, then X' is shattered by Fd.p. To prove the claim, suppose we are given arbitrary label of X, where Vl,j E {+1} denotes the label for æt,j == Cj + tey E X. Given the label V. we construct D Da.N.2 2 such that whenever E Fa.P p-robustly memorize D under e--norm, then its affine translation f = 2f - 3 Fa, satisfies (T(,) Vt,j for all æt E X.
) = beeLL
UL. = 1}. Define For each 1 E [[N/2]], let J = {i E [ U1 = +1} and J, = {j E [K]
021-1 1 C Σ Ej Σ ej
jEJi
JEJi
Σ ej Σ ej
F2 = Ci +
JEJ
jEJT
Furthermore, define 1 = 2, 1/2 = and let = Wilieei E Da,.22. To consider the separation ép,2, notice that
[221-1 - 122011 2 Σ e 2 Σ Ej
(a)
2/P
WEJT
jEJ
where (a) is due to J nj = 0 and Ji UJi = -k]] For + l',
(e)
(22
2
dp (c: cr) - (c, 2211 dp( x22)
(
2 2d 1111 k11p
2
(
2d 22
20
2k2/P,
where (a) by the triangle incquality under typ norm (namely, the Minkowski inequality), (b) uses dp(ci, 11) = (p( w2r) = k1/p, (c),(e) is by < d, and (d) holds for all d 2 2 and 2 1. Thus, we have ED.p 2 1/p
Take E Fa,r that p-robustly memorize D. We first lower bound the robustness radius μ. Since t + // ب is an strictly increasing function from onto [0, 1) 3 it has well defined inverse 1 = T-p Therefore,
mapping o- 11 (0, + [1, o0) defined as o x
p ② (p) ( pm
(1-1)) ((k) = -V k
b is composition two strictly increasing one-to-one corresponding functions + 1-1 from [1, oc) onto [0, and &/ from 00, 1) onto [0, 1)
58

---

Since CD.p 2 ///r and ( we have μt pep.p 2 pkl 2 (k - 1) Thus, every f that p-robustly memorizes D must also memorize (I: 1)1/v radius open ep-ball around each point in D as the same label as the data point.
Moreover, for æi.j E X' with positive label M1 +1, we have
[1,J 12-
(ct (q Σey ey- Σ ex)
YEET
J'EJT
Σ ej ej-- Σ ej
J'EJt j'
J'EJT
(k: 1)
Take a sequence of points = IEE such that 2n + 2115 as 0o and
|| - 121- < (k: - 1)
for all n E N. In particular,
2n
Lt.j + - -22
71
satisfies such properties. Then, we have f(zn) = f(x21-1) = for all n E N. Moreover, by the continuity of f (under the usual topology),
f(r1))) lim 2n) lim f(zn) lim == =.2. 2. 100000
n-
Similarly, for 2t, with negative label yt 11 have || T2il fx,,,) =
1-)//,, that
Since we can adjust the weight and the bias of the last hidden layer, Far is closed under affine transformation; that is, af b E Fa, whenever f Fa.r. In particular, f' = 2 3 Fa. This f satisfies ('(x).) = 2f(x))
2 3 = +1 whenever Yt.j = +1 and f' - whenever W. -1 Thus, sign perfectly classify X with the label V. Since we can take such f' E Fa. given an arbitrary label y of X, it follows that Fa.
2x(1) - 2-
shatters X, concluding the proof of the theorem.
C.1.1 Lemmas for Appendix C.1
Lemma C.9. Let {esliejg S Ra denote the standard basis in Rd. Then, for any k-dimensional subspace Z Rd with k we have.
1
min dist (e:: Z) <
jEld
2
Proof. For any subspace Z' of Z, we have
min distoc (e,, Z) < min distac (ej, Z"). sE(d]
JE(d]
As every k-dimensional subspace of RRd with & 2 1 has one-dimensional subspace, suffices to prove the second statement for 1. ie., for any one-dimensional subspace Z of IRd.
1
min dist (e,. (e..Z) 2) 2
jEld
'We consider the convergence of the sequence the usual topology induced by nomm.
59

---

Let Z = Span(z), 2), where = (21.-.: .2d) # 0. Without loss of generality, let || = 1 and take j E [d] such that |رy| = 1. Let x' = 3/2 E Z. Then,
2| e, 2|
2j
2/3
3j
2j
2
2
00
(a)
[3
2j
2, /-1
2
2
2
1
2
2
2
2
where (a) by |zy| = and (b) by ||=1|0 Therefore,
1 min (e,, 2) S oo (ej, 2) s 1| - e,,loo S 2 %
concluding the statement.
The following lemma generalizes Lemma C.9 to the case where we consider only the distance to subset of the standard basis, instead of the whole standard basis.
Lemma C.10. For 1 it d, let {eybjen S R denote the first vectors from the standard basis in Rdd Then, for any k-dimensional subspace Z of IRd with k 2 d 1
min dist (e, 7) - 2 jEld
Proof. Similar Lemma A.2, start by considering the dimension of the intersection between Z and R', both as a subspace of Rd. Let Q = (e162- ... e,] e.l E Rxtd Then,
2 Col(QT) @ Null(Q) (Z n Col(Q )) @ (z+ n C))(QT)) @ Null(Q).
By considering the dimension,
dim(Z n Col(( dim Rd dim(2 Z n Col(Q )) dim Null(Q)
2 dim Rd dim Z dim Null(Q)
d (d k) (d t)
= k (d t)
Under the assumption d ++ + we have
dim ((Z n Col(QT) T dim Z n Col(( (d- -t-t] 2 1.
Then.
min dist (ej, 2) < min dist (e,, Z ()l((TT) sE(t]
jE(t]
min dist dist. 6(2 (o(e)),
Coll(("))) (ol(()))
(6)
5
where (b) is by Lemma C.9,
C.2 Extension of Sufficiency Condition to f,-norm
Theorem C.11. Let p E oo). For any dataset DD DaN.C and n E (0,1), the following statements hold:
i If E (o. (N) there exists f E Fa,p with P Ö(VN) that p-robustly memorizes
D under no-momm.
60

---

i If E (NN (oNvo) sv there exists f Fa, with P Ö(Ndi (2 that p-robustly memorizes DD under ey e-norm with error at most 1)-
(ii) p E bvddyldd' Tota.) there exists J E Fa, with P O( (pd))()))))))))))))))))))))))( that p-robusily memorizes D under nn-nrrm.
To prove Theorem C.11, we decompose it into three theorems (Theorems C.12 to C.14), each corresponding to one of the cases the statement. They are following.
Theorem C.12. Let p (0, (NV/in and E oo). For any dataset D E DaN.C. there exists f FaP with Ö(VN) that p-robustly memorizes D under ty-norm.
Proof. Let p' (d)pp. Then, have o' 0. 5N from the condition of p. By Theorem 4.2(1), there exists E FaP with = Ö(VN) that o o'-robustly memorizes D under norm In other words, it holds f(x') Ut. for all (z,, (x). D and x' B2(x,, pDe2.)).
We consider two cases depending on whether p 2 or p 2, which affect the direction of inclusion between Ep and & balls.
Case I 1:p2 2. this case, we have
(6) (a) S Ba pEp.2) S (2 (dd)pppp)) = B2(2,, pDE (a peD.o)
where (a) holds by Equation (61) and (b) holds by Lemma C.4 applying p and q - p. Thus, for all (ær, Wi) E DD and æ' Bp(a, peD,p), also holds f(xx' = yi. other words, f p-robustly memorizes DD under e--norm with Ö(vN) parameters.
Case <p In this case, have
(b) (x(x,, S Ba (d) S B2(x, (dd)pep).) (2 poo,,,'epp p.E.)))
where (a) holds by Equation (62) and (b) holds by Lemma C.4 applying and 2. Thus, for all (I,, yi) D and æ' Bp(x, pED,p). also holds f(x') yı. In other words, p-robustly memorizes under fn-norm with Ö(vN) parameters.
Theorem C.13. Let p 3NN/dnld) 5vdr,(d) and E [L, For any dataset D Da,,C there exists f E Fa,P with P = O(Nd' p2 (d))) that p-robustly memorizes under En-norm with error most n.
Proof. Let p' = (pd)pp. Then, we have p' E (Nvd' 5ya) from the condition of
1
We consider two cases depending whether p 2 or p 2, which affect the direction of inclusion between l, and l balls.
Case I: 2. In this case, have:
(a pED.;) C B, pED.2) B2 (d))pe)))) B2(2,, p'eD.2),
where (a) holds by Equation (61) and (b) holds by Lemma C.4 applying 2 and q p.
61

---

Case 1I: pl:p<<. 2. In this case, we have:
(a) Bplmi peD.)) S By( Yo (plam)nppd)eee
(M) (p))p C B2(ms, 7/ (d))pe = B2 p'e.,,,)e..)))
where (a) holds by Equation (62) and (b) holds by Lemma C.4 applying and q = 2.
Thus, in both cases, it holds:
(,(,,, (2(2,, p'D,2))
(65)
We define vy' VollB,(aa,,een.il error rate r/', then we obtaín Fa,r with P= Ö(Ndt p (NNdtttpp that pl p'-robustly memorizes D with error at most v/ under nornm In other words, for all (æt, Us) E D, it holds that
(ar.p"))) We apply Theorem 4.2(ii) with the robustness ratio p' and the
P (a (f(x') # v.l < <n
(66)
f(xx)) * y Then, we have For simplicity, we denote E = fo E
Pa Bn
(x') + vil
Par
x E E]
Vol(E n Bp pEp.p)
(ol PED,p)
(a) Vol(E n (2
Vol(B, ptD,))
Ba (Ba
(o, PCD,
Vol(B2 (o,, p'eD.2))
P Bi
El
Vol(B, (ti,
Vol (Bl p'e),2)
-P P +
BB, (x;,
Vol(Ba(z,,,'en) p'ED.2))
(ol PED,))
where (a) holds by Equation (65), (b) holds by Equation (66), and (c) holds by the definition of r/. Thus, for (x., v.) E D, it holds:
P Par ")) * ys] <
In other words, f p-robustly memorizes D under f--norm with error at most 77 and ( p (d) parameters.
(
Theorem C.14. Let p E (vdrs(a) : %old] and E (1, For any dataset DD DaN.C there exists f E Fa,p with P = dN ( (dy)) that p-robustly memorizes 'D under t--norm.
Proof. Let p' = Then, have pf ( 55/. 1) from the condition of p. By Theorem 4.2(iii) there exists f E Fa. with P Ô(Nd p*4) = Ö(Nd (d)) that pl o/-robustly memorizes D under f2-norm. In other words, it holds f(x') yi. for all (æi,, y1) E D and x E B2 p'e
consider two cases depending on whether p 2 or p 2, which affect the direction of inclusion between lp and &g balls.
62

---

Case 1:p 2 2. In this case, we have:
(a) Bp(a, pCD.)) E Bp(a, pCD22 - (2 (odd)pep:2 B2 p cD22),
where (a) holds by Equation (61) and (b) holds by Lemma C.4 applying 2 and = Thus, for all (Ii, Vi) D and x' Bp(as, pCD,p), it also holds f(x') yi- In other words, p-robustly memorizes under e--norm with Ó(Nd² p² (dd))))) parameters.
Case II: < In this case, we have:
(b) By peD,)) S By( (dd))pED22 S BB (d))pep)2) = B2 2
where (a) holds by Equation (62) and (b) holds by Lemma C.4 applying and = 2. Thus, for all (ae,, yi) D and x' By(as peD.p), it also holds [(x') yi- In other words, p-robustly memorizes D under -n-norm with Ó(Nd' pa (d))") parameters.
63

---

D Comparison to Existing Bounds
D.1 Summary of Parameter Complexity across lp -ormss
Table 1: Summary of our results and a comparison with prior works. We omit the constants for the range of p. %p(d) under p reduces to the results in Sections 3 and 4.
---norm
Robustness Ratio p
Bound Parameters
p > 2
(0, 1)
Ω (Mi Proposition C.6
S 2
(0, 1)
Ω
[in(N, djd (p/7, (d))² Proposition C.6
= 00
(1/2, 1)
Ω [min{_V N, d]d)) Proposition C.7
LB
0C
0.8
Q (dP), Yu et al. [2024]
0C
(0, 1/]
Ω
1-pp
Proposition C.8
p 2
p
?
v /Nd
Li et al. [2022]
(0, (ONNV
V/N
Theorem C.12
Ô (Nd (ptp()) Theorem C.13
Told)Naa Soldiva
Ô (N), Egosi et al. [2025]
UB
p=p p
saldiaa
Ô(Nd ((N Theorem C.14
(
(dldva so(a))
(Nd (p))pp)))))))))))))))))))))))))) (d))), Egosi et al. [2025]
(0,1)
Ô ONd'pp) Yu al. [2024]
Requires N. >> d.
result holds sufficiently 3 Requires p N.
D.2 Parameter Complexity of the Construction by Yu et al. [2024]
We now analyze the number of parameters of the network construction proposed by Yu al. [2024), which provides the upper bound not depending on p. but still applies to all E (0,
Lemma D.1 (Theorem B.6, Yu et al. [2024]). Let p E N. For any dataset D {(x,, U:) VieNN E Da,NCC, let > by any real value with ||æv|lo S R for all E [N]. For p E (0, 1), define = (1 p) > 0. Then, there exists a network with width Od), and depth ON log R + log p)) that p-robustly memorize 'D under t--orm.
We note that in the Yu et al. [2024] uses the notation X2/2 2 for cD.p. and the radius X - in the original statement corresponds to the value μu := pCD,p pp in notation. We count parameters in their construction in the following lemma, specifically in the case = 2. Although the original statement of Yu et al. [2024] includes a parameter count, they consider a different parameter counting strategy-by counting only the number of nonzero parameters. We therefore count the number of all parameters following Equation (3) in the subsequent lemma. Note that results and comparison under nonzero parameter counts are provided in Appendix E.
Lemma D.2. For any D E DA,No and E (0, 1), define T == (1- (1-p)es p)eD > O and R > 1 with | & R for all E [N]. Then, there exists a neural network such that p-robustly memorizes D using at most O( (log( (t) + log R)) parameters. Moreover, the network has width (dd) and
depth Ö(N).
Proof. By applying Lemma D.I with p = 2, we obtain neural network that p-robustly memorizes D with width Odd, and depth O ,2 + log R))). In their construction, d, ( through all 1, as the input & propagates over the layers using a width d. We count all parameters as defined in Equation (3),
upper bound the number of parameters used for the construction
64

---

of f as follows:
(d:1 + 1). = Σ ( O(d)
i=1
(No 722
+ log R)) O(d?)
G(Nd (log( 72 22) log R)).
D.3 Parameter Complexity of the Construction by Egosi et al. [2025]
We observe that although Egosi [2025] do not explicitly quantify the total number parameters in their construction, it implicitly yields network with O(Nd pd) parameters. Specifically, we can establish the following:
For any D E DA,.CC and p (7t, 1), there exists neural network f that p-robustly memorizes D using O(Nd parameters.
This result follows from the network constructed in Theorem 4.4 of Egosi et al. [2025]. The proof of Theorem 4.4 proceeds under the assumption that for 7 k S d 5, and p < 1yE V /
Given this range. Theorem 4.2 of Egosi et al. [2025] is applied construct robust memorizer of the projected data from R R Figures and their paper illustrate this construction. this construction, the projected point propagates through the network ((Nk) times. The width of the network scales with k, while the other component, that is not propagating the point remains constant in width. Thus, the number of parameters used for the construction given by:
I Σ (dd-+11).4 1=1
((NK)
+1)
E = 9(N4: 12) = @(N1*). 1=1
To translate this to a bound terms of A we analyze the relationship between p and k. For k 2 4 4og N + 6, we verify the following inequality:
(a)
k
d
A
d
4e
d
where (a) holds by N Log Therefore, for p V the network p-robustly memorizes D with (NN*3) parameters. From the relationship between and k, solving for & in terms of p yields (dp²). Since the minimum value of l under the assumption 7, the minimum achievable is va
Thus, for p > va the construction yields a network that p-robustly memorizes D with @(Nk*) = ((Ndpp) parameters, as desired.
65

---

E Nonzero Parameter Counts
While our main parameter counting method follows the approach of counting all parameters, including zeros, as defined in Equation (3), some prior works on memorization and robust memorization adopt different parameter counting strategy-countinng only the nonzero parameters. We emphasize that counting all parameters, including zeros, better aligns with how the matrices are stored in practice. Nevertheless, we also present how our results extend to the case of counting only nonzero parameters, offering an alternative perspective for interpreting our findings and comparing them with prior work.
In contrast Equation (4), let define the set of neural networks with input dimension d and at most P nonzero parameters by
Far - (f: R R is neural network with at most P nonzero parameters]
(67)
E.1 Nonzero Parameter Counts: An illustration.
We provide the corresponding illustration of Figure under only nonzero parameter counting in Figure 8, combining Theorem E.1 and Theorem E.2.
Nd
Parameters
Existing Upper Bound
Our Upper Bound
Out I Lover Boon
Existing Lower Bound
NVd
vd
Robustness ratio p
Figure 8: Summary of parameter bounds, counting only nonzero parameters log-log scale when d = O).N). We omit constant factors in both axes. Solid blue and red curves show the sufficient (Theorem E.2) and necessary (Theorem E. numbers parameters, respectively; the solid black curve is the best prior bound. Light-blue shading highlights our improvement in the upper bound, and light-red shading highlights our improvement in the lower bound. The cross-hatched area marks the remaining gap.
E.2 Nonzero Parameter Counts: Lower Bounds
The lower bound in Theorem 3.1 that counts all parameters consists of terms: one based on the network width and another based on the VC-dimension. Although the lower bound by VC-dimension remains valid even when counting only nonzero parameters, the lower bound on the first hidden layer width can be translated into a lower bound on parameters only if we also include zero-valued parameters in the parameter counting convention. As result, we obtain the following lower bound consisting of only the lower bound from the VC-dimension.
Theorem E.1. Let p E (0, 1). Suppose for any D Da,N.2. there exists a neural network f E Fa,r that can p-robustly memorize D. Then, the number of parameters P must satisfy
P= Ω
min
VN
The main reason why the VC-dimension lower bound remains valid even for the nonzero parameter count is because the key relation VC-dim(Fu.p) O(P²) [Goldberg and Jerrum, 1995] holds even for the Fa,p instead of Fa,p. Below, provide explicit proof of the Theorem E.
66

---

Proof. Since Fa.P S Fa.p, we have VC-dim(Fap) & VC-dim(Fa.p). In particular, by Equa- tion (7), have for 0, (o.v à that
N VC-dim(Fa,n) VC-dim(Faap) 1
By [Goldberg and Jerrum, 1995], we have VC-dim(Fa.r) = 0(22). Combining the two relations proves that for (0, /
N
P=Ω Ω
1 p2
Since Vi-pe S Vd for (0, V 2
the following relation holds:
N
min
vdlvN-
VI 1
1- D²
For p (V1-
3: 2.1 the lower bound P 12( /N)) obtained by the case p /1- 1/ also can
be applied. Since 1 Vi- > V for p E (Vi 1) the following relation holds:
1 Vd VNd.
mint
As result, applying P Q (v I-p² results in
for p E (0.v1 1- and 22 (l(VNd) for p (V1 1 2:11
Vd vaj VN VN
P=0 Ω min v1 - p2
E.3 Nonzero Parameter Counts: Upper Bounds
While upper bounds on parameter counts of all parameters in Theorem 4.2 are naturally upper bound for parameter counts of nonzero parameters, we provide tighter upper bound regarding the nonzero parameters.
Theorem E.2. For any dataset D E Da,N.C and (0,1), the following statements hold:
(i) Ifp (v.a there exists f E Fa,p with P = Ö(VN d) that p-robustly memorizes D.
(ii p (SNVa' s there exists E Fa.P with Ö(Nd pà + d) that p-robustly memorizes 'D with error at most 1/.
(iii) fp (vva 1). there exists f Fa with P= O(N + d) that p-robustly memorizes
D.
In comparison to the total parameter count as in Theorem 4.2, only Theorem E.2(iii have modified rate from P = O(Nd2p to P = ((Ndp)) Below, we provide an explicit proof of Theorem E.2. The d term the parameter bounds of all three cases comes from the upper bound on the parameters of the first hidden layer.
Proof. Upper bounds on all parameter counts are natural upper bounds on the nonzero parameter counts. Since Theorem E.2() and Theorem E.2(ii) claims the same rate as Theorem 4.2() and
67

---

Theorem 4.2(ii) respectively, they trivially follows from Theorem 4.2. Another way of speaking, Fa,p S a and the first two cases directly follow from Theorem 4.2.
Now let us prove Theorem E.2(i Here, we mainly follow the proof of Theorem B.14, where instead of counting every parameter using Lemma D.2, count only the nonzero parameters using Lemma E.3, We divide the cases into five, following Theorem B.14 as in Figure 6.
Da,NCC be given. We divide the proof into five cases, the first case under E [1/3, 1), the second case under E (1/5vd, 1/3) and < 60g N, the third case under p E (1/5v/, 1/3) and N < 600 N Σ d, the fourth case under p E (1/5vd, 1/3), N 2 d 2 600 log N, and finally the fifth case under E (1/5vd, 1/3) and d > N 2 600 N. To check that these cases cover all the cases, refer Figure 6.
Let D ((J),,)))
Case I: p [1/3.1] 1). Let us denote R == [ | 1l2 and := (1 - p)ep. Note that R loo for all E [N] as | 2 |||| for all R. By applying Lemma E.3, there exists Fa,P with P O ( (No((lo(( { log R)) nonzero parameters that p-robustly memorize D. The number of nonzero parameters can be further bounded follows:
d log R)) O(Ndp² (log( (5) + log R)) (b) Ö(Ndp²)
O(Nd(log(
(a)
where (a) is due to p= P (b) hides the logarithmic factors.
Case II: p (1/5V d, 1/3) and d < 600 log N. Let us denote ;= := [aX | and y (1- pleD. Note that R ||0; for all i [N] as || 2 || for all Rd By Lemma E.3, there exists f E Far with P ((Nd(log( / + log R)) nonzero parameters that p-robustly memorize D. The number of nonzero parameters can be further bounded as follows:
O(Nd(log( ( log
loggog R?) O(Nolog (log(
d 7 + log R)) (b) Ö(N) ( Ö(Ndp"),
where (a) is due d < 600 log N, (b) hides the logarithmic factors, and (c) is because N S 25 for all p 3v8 3
Case III: P E (1/5/d,1/3) and 600 log S d. We first apply Proposition B.21 to to obtain 1-Lipschitz linear yp Rdd + R such that D' = ((p((x)))))))))))))>)((<)))))( vi) has cD = 6p. This possible as d N.
Take b E R such that (xx) b > 0 for all (2((((x;), pezr), ensuring that does not affect the output of the first hidden layer. Let D = ((p(x;) - b, yi b. be)N Then, ep = ep = epr. For simplicity the notation, let us denote z; == ((x,) Moreover, the first hidden layer is defined as fi(x) ((x) b.
We apply Lemma E.3 to D" Let us denote == max [|=(())) and == (1 p)e Note that R 2 || for all E [N] as || 2 || for all E IN.. By Lemma E.3, there exists + log R)) nonzero parameters that p-robustly memorize D f2 E FN.P with = O(N N (log N )
Let =2 f1. Since f1 is 1-Lipschitz and epr = ep, every robustness ball of D is mapped to the robustness ball of D via f1. Since the does not affect the first hidden layer output of the robustness ball, and fz p-robustly memorizes D", the composed f satisfies the desired property
The number of nonzero parameters can be further bounded as follows:
+ log R)) (a) Oddog N + N)o (log( 72
+ log R)) (b) Ō(d),
O(Nd+ + N. .(ogg( ??
where (a) due to N 600 N, and (b) hides the logarithmic factors.
Case IV: P E 1//5/d.1/3) and N > d 2 600 N. We utilize the dimension
reduction technique by Proposition B.19. We apply Proposition B.19 to D with
68

---

max max[[9dp") [[ddp'], [600
N1, log d]]
and a = 1/5. Let us first check that the specified m satisfies
the condition 24a 24a-2101 log S m I d for the proposition to be applied. a 1/5 and m 2 600 log N
ensure the first inequality 24a-2 log N < m. The second inequality mn S d is decomposed into three parts. Since p S 3. we have 9dp² I d so that
[9dp²] 2 d.
(68)
Moreover, 600 N < implies
[600 log N1 S d.
(69)
Additionally, as N 2 2, we have d 2 600 N 2 600 600log 2 2 400. By Lemma B.22, this implies 10 log d I and therefore
[10 d < d.
(70)
Gathering Equations (68) to (70) proves m S d.
By the Proposition 19 there exists I-Lipchitz linear mapping & Rd -> I and / > 0 such that D' (:))a)) E N.C satisfies
<D 2 BED.
(71)
As m 2 log d, the inequality
2 2 2 is also satisfied by Proposition B.19. Therefore, we have
B m
9dp21
1
9dp² 3 2
(72)
2
d
where (a) is by the definition of Moreover, since o is I-Lipchitz linear,
[10(x;))12 = 1, 0)ll2 = |1((;;)) - <())l2 S ||=, - 0112 ||0:||
(73)
for all E [N]. Hence, by letting R max a2 [12) have 1|ob(;;)112 S R for all [N].
Now, we set the first layer hidden matrix as the matrix W E Rx corresponding under the stan- dard basis of dR and RT. Moreover, set the first hidden layer bias as b = 2 2R(1, 1, 1) E
R.m Then, we have
Wx + b 0
(74)
for all w E (2 ED) for all i E [N], where the comparison between two vectors are element-wise. This is because for all i E [N] E [mm] and æ E B2 ED), we have
(a) (W W b)j (W x); 2R 2R W 2 2R - ||ا||| 2 2R (R + ED) 0,
(8)
where (a) is by Equation (73), (b) is by the triangle inequality, and (c) is due to R > ep.
We construct the first layer of the neural network as fi( (W + b) which includes the activation a. Then, by above properties, D" = ((f( y1) JE[N] satisfies
6
D 2 5 peD.
(75)
This is because for i + j with y/4 * y, we have
(xx)) f1 = (Wo + b) a (Wa, + b)ll
(I m + b) (Wa, b)ll2
[((())) ((xx)) ll
2 2cd'
$ 2 x
BCD
5
(8)
3
2 pcD
69

---

12
PCD: 5
where (a) is by Equation (74), (b) is by the definition of the eD., (c) is by Equation (71), and (d) by Equation (72). By Lemma E.3 applied to D E Dm,N,C, there exists f2 E Fm.r with m P= O(Mm(log (7n7a) + log ))) nonzero number of parameters that 5 -robustly memorize D",
6
where
5
[a]
1
12
>" = (1
2
x
PCD
PCD:
6
6
5
R" = max (E[N]
1/ (ax))ll
max
(1o + bbll2 = max [Wx, + b112 [E[N]
iE[N]
< max .E[M]
T.lll + ||b|| S 3R.
Here (a) is by Equation (75).
Now, we claim that f == f2 fa p-robustly memorize D. For any E [M] take E B2(2i, pCD). Then, by Equation (74), we have f1 = W x + and f1(z;) = W x; + so that
llf( - fi (2.))l2 = W x W x; 11 I 2 2;112 1 pCD.
(76)
Moreover, combining Equations (75) and (76) results f f1(x))l22 I gep.. Since fz 3.
robustly memorize D", we have
f(x) = f2(f((=))) fz(f((z)) = yi.
In particular, f()) yi for any x (2 PED), concluding that f is a p-robust memorizer D. Regarding the number of parameters to construct f. notice that f1 consists of (d 1)m Ö p²) parameters (and thus Ó(dpp² nonzero parameters) as m (dp²). f2 consists of Ó(Nm) = Ó(Ndp²) nonzero parameters. Since the case IV assumes N 2 d, we have
dp² < Ndp²
Therefore, f in total consists of Ó(Ppp² + Ndp²) = Ö(Ndp²) number of nonzero parameters. This proves the theorem for the fourth case.
Case V: (1/5vd, 1/3), and d> N 2 600 log N. The last case combines the two techniques used in Cases III and IV. We first apply Proposition B.21 to D to obtain 1-Lipschitz linear yp Rd - R. such that D == ((((xx,) y: MeEM E DN,NCC has ep cD. Note that we can apply the proposition since d > N.
max [[9 21 [600 log N1} and 1/5. Let first check that the specified satisfies the condition 24a log N m N for the proposition to be applied. a = /5 and m 2 600 log N ensure the first inequality 24a -2 log N < m. The second inequality < N is decomposed into two parts. Since p 3 we have 9Np N so that
Next, we apply Proposition B.19 to D' DN,NCC with
19Np21 N.
(77)
Moreover, 600 log N < N implies
6600 log N1 S N. Gathering Equations (68) and (69) proves m < N. Additionally, N 2 2, we have N > 600 N 600 log 2 400. By Lemma B.22, this implies 10 log N S N.
(78)
By the Proposition 1.19, there exists I-Lipchitz linear mapping á R. + Rm and | > 0 such that D" == ((((p(()))) m))ee( DM,N. satisfies
ED
2 5
3eln
(79)
As m 2 600 log N 2 10 N. the inequality 2 2 Therefore, we have
/ /m is also satisfied by Proposition B.19. N
m
(a)
1
99 2
1
9N
3 PP,
B
(80)
2
N
2
N
70

---

where (a) is by the definition of m. Moreover, since and @ are both I-Lipchitz linear, & up R 4 IT is also 1-Lipschitz linear. Therefore,
()(()()))) (1 0)) (1)()((;))) (()(0))) = 1|= Ol12 | (81) for all i [N]. Hence, by letting R == max ( we have ([)()(=)))] S R for all i E [A].
Now, we set the first layer hidden matrix as the matrix W E R corresponding to @ yp under the standard basis of R and R" Moreover, set the first hidden layer bias as b = 2/11 28(1, 1, 1) E R Then, we have
We + b 2 0,
(82)
for all æ E (2 ep) for all i e [N], where the comparison between two vectors are element-wise. This is because for all i E [ E [m] and x E B2(x, x. CD), we have
(a) (Wx + b)j (Wæ), + 2R > 2R - [Wal] 2 2R - ||ق|| 2 2R (R + ED) 20
where (a) is by Equation (81), (b) is by the triangle inequality, and (c) is due to R 2 ED.
We construct the first layer of the neural network as fi()) o(W x + b) which includes the activation a. Next, we show that, D" == (x;), villieN) satisfies
6
ED" 2 5 PED:
(83)
by the above properties. This is because for i + j with ys + yj we have
(x.) - f1,,))l = |0 W x; + b) o (Wa, b)ll
II x; + b) - (Wa, + +bll22 [10(p((x))) - (<<((,)))]1
N 2ED"
(9) 4
2 2 Bdg
(
x 3
2 2
2 PDD
5
12
5 PED
(c) 12
PED:
where (a) is by Equation (82), (b) by the definition of the ED"r (c) by Equation (79), (d) is by Equation (80), and (c) is because eD
By Lemma E.3 applied to D" Dm,N.c, there exists f2 E Fmr with P O(Nm(log( (z)) log R")) nonzero number of parameters that - g-rbbustly memorize D", where
5
(a)
1
12
2 pED = PED.
>" = (1 JED
2
6
x
5
R" == max [
fi (x
(xx))l2
max llo(Wa, x, + b]ll2 = max WW + b112 iE[N]
[E[N]
max .E[M]
W Wa:lla + ||b||2 S 3R.
Here, (a) is by Equation (83).
Now, we claim that f := f2 o fi p-robustly memorize D. For any E [N], take x E (2(x,, Then, by Equation (82), we have S1 (1))) W b and fi (xx)) W ax b so that
(z) fi (2,))l,
We Wx, < | x; < PCD.
(84)
71

---

Moreover, putting Equation (83) to Equation (84) results [[f(()) f1(xx))l S eepr. Since f2 e-robustly memorize D", we have
f(x)) (2()i(a=)) (2(fi yi-
In particular, f()) yi for any a E (z,, PCD). concluding that f is p-robust memorizer D.
Regarding the number of nonzero parameters construct f. notice that consists of (d + 1)m O(Ndp²) nonzero parameters as m (NN p²). f2 consists of O(Nm) Ó(N p²) nonzero parameters. Since the case V aassumes N < d. we have
p² I Ndp².
Therefore, f in total consists of ON + +N² = ((N number of nonzero parameters. This proves the theorem for the last case.
Nonzero Parameter Counts: Existing Upper Bounds. In Section 1.1, the existing upper bound is stated by counting all parameters. When counting only the nonzero parameters, the corresponding existing upper bound takes different form. Specifically, for any dataset D with input dimension and size N, there exist neural network that achieves robust memorization on D with the robustness ratio p under fo-nrmm with the number of parameters bounded as follows:
Ö(N + d) p= O( + Ö(Nd)
pf (0, 1/vd].
pf (1/Vd, 1/V/).
(85)
p (1)
This is the counterpart to Equation (2) that considers all parameter counts. As in the case of full parameter count, the first and the third case in Equation (85) directly follow from Yu al. [2024] and Egosi et al. [2025] respectively. The work by Egosi et al. [2025] can be implicitly improved to the second case under the moderate p condition, using the same translation technique provided in Appendix D.3.
E.4 Lemmas for Nonzero Parameter Count
Here, state Lemmas D.I and D.2-that corresponds to Theorem B.6 of Yu et al. [2024] to its original version that contains the nonzero parameter count with f--norm into the consideration.
Lemma E.3 (Theorem B.6, Yu et [2024]). For any D E DINNCC and p E (0, 1), define 7 (1 p)eD > 0 and R > with || olo S for all i E [N]. Then, there exists neural network with width (d)) depth ((o(l 3 + log R)) that p-robustly memorizes D using most O(Nd(log 4) + log R)) nonzero parameters.
72

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clarify the main claims in the abstract and introduction through the theorems in Sections 3 and 4. The abstract and introduction clearly state the claims made by the paper, with comparison the prior works.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our result in Sections 3 to 5, as well as Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
73

---

Answer: [Yes]
Justification: We specify the basic settings and network architectures in Section 2. The complete proof of all the results is given in the supplementary material.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper is fully theoretical. We contain no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., .., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
74

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper is fully theoretical. We have no experiments, and therefore no data and code reproduce any experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
wwwoooooooiioooooooooooooooooooo liyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/ wttpcccccc/c////eec.cc.c.ccc.lll http:/uulllluuuieeee Seriiidess/oeeSuuui ssisssolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is fully theoretical. We contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification: The paper is fully theoretical. We contain no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
75

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper is fully theoretical. We contain no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that NeurlPS Code of Ethics https::////// wwtpeerww...cppup..peeeeeeceeeee hetublic/thhicccuidellnneee
didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer:
[Yes]
Justification:
The research fully complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper fully theoretical. The main focus is on the mathematical aspect without direct relation to downstream applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
76

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper is fully theoretical and poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper is fully theoretical. We do not use existing code or dataset.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
77

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper fully theoretical. We do not release new dataset/code/moodl.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification; The paper fully theoretical. We do not involve any crowdsoureing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper fully theoretical. We do not involve any crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
78

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: We used LLM only for editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy (https /ttpaaippp.cccooofeeeeeeeeeeeeee / for what should or should not be described.
79


Reviews:
[{"review_id": "AsEGgsAX3y", "reviewer": "Reviewer_17QC", "summary": "This work expands on existing work on memorization bounds for ReLU nets by expanding the problem definition to consider \"robust memorization\" and extends the bounds for robustness ratio $\\rho \\in (0, 1)$. They also show that their bounds are tight up to log factors.", "questions": "- Is there a reason the authors left out memorization results on threshold networks in their discussion on related work? I would strongly recommend including them as they are important contributions to the area. See for example Vershynin, Roman. \"Memory capacity of neural networks with threshold and rectified linear unit activations.\" SIAM Journal on Mathematics of Data Science 2.4 (2020): 1004-1033.\n and Rajput, Shashank, et al. \"An exponential improvement on the memorization capacity of deep threshold networks.\" Advances in Neural Information Processing Systems 34 (2021): 12674-12685.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and provides good intuition behind the proofs and constructions.\n- The paper does a good job at positioning their results among existing results and comparing their settings.\n\nWeaknesses:\n- The authors updated the paper to change the parameter count definition in terms of all parameters, not just non-zero ones. However, they compare their results with other works - which I believe consider only non-zero parameters. I recommend sticking to a single standard.\n- The main weakness I see in the paper is the importance of considering $\\rho$ in the computations. The memorization problem inherently considers the challenges of memorizing arbitrarily labeled points with some separation assumptions. By enforcing $\\rho \\in (0, 1)$, we are limiting some of these configurations w.r.t how points can be labeled within $\\ell_{p}$-balls around each of these points. I am not sure if this is significant - although it is clear that this is technically challenging.\n- I would like to also see bit-complexity of the constructions factoring into the bounds since these constructions (including Baum's) typically rely on choosing intercepts very precisely using real numbers with extremely high bit complexity making these constructions unrealistic to implement.", "was_revised": true, "final_justification": "The authors have clarified most of my concerns and I am continuing to recommend acceptance. I urge the authors to include their clarifications in their manuscript so that the readers may benefit from them.", "rebuttal": "We thank the reviewer for the constructive feedback.\n\n**W1. Inconsistent parameter count standard across comparisons**\n\n- We thank the reviewer for pointing this out and apologize for any confusion caused by the change in the definition of parameter count. As described in the supplementary material, we chose to adopt the number of all parameters (including zero entries) as a unified standard throughout the paper.  We chose this because one of our lower bound results does not hold for the original standard and holds for the revised standard. We updated the upper bound results accordingly to ensure consistency. The lower bound results remain unchanged, and the updated upper bound results are provided on **page 20**.\n- We acknowledge that prior works we compared against report results in terms of the number of *non-zero* parameters. To ensure a fair comparison:\n    1. We compute the number of all parameters in their constructions and compare our results based on the total number of parameters. The comparison is presented in **Figure 5**, and details on the computation of their constructions are provided in **Appendix D.2 and D.3**.\n    2. Additionally, we provide a complementary analysis in **Figure 6** of the appendix, where we evaluate our construction under the non-zero parameter count and compare the prior work based on the number of non-zero parameters. This figure shows that our construction still improves upon the known upper bounds even under the non-zero parameter metric.\n\n**W2. Potential limitation on allowable labeling due to the assumption $\\rho\\in (0,1)$**\n\n- We appreciate the reviewer’s thoughtful comment regarding the role of $\\rho$. We would like to clarify that **the dataset $\\mathcal{D}$, consisting of arbitrarily labeled points, is fixed in advance.** Then, we define $\\epsilon_\\mathcal{D}$ as half of the minimum distance between points with different labels. The robustness ratio is set to $\\mu=\\rho \\epsilon_\\mathcal{D}$ for some $\\rho \\in (0,1)$, and the goal is to memorize $\\mu$-balls centered at the data points.\n- Importantly, the choice of $\\rho$ **does not constrain** the labeling of the dataset. Instead, it determines the relative size of the neighborhood around each point that must be robustly memorized. If $\\rho>1$, then $\\mu$-balls around differently labeled points necessarily overlap, making robust memorization impossible (see line 111). Moreover, in the case $\\rho=1$, we show in lines 112-115 that robust memorization is impossible using continuous functions. In contrast, when $\\rho \\in (0,1)$, $2 \\mu$ is strictly less than the separation $2\\epsilon _{\\mathcal{D}}$, which ensures that the $\\mu$-balls around differently labeled points remain disjoint and can be robustly memorized.\n- Therefore, our choice to restrict to $\\rho \\in (0,1)$ is not a limitation on the dataset itself, but a natural condition that characterizes the feasible regime for robust memorization. This formulation is also **consistent with prior works** such as Yu et al. (2024) and Li et al. (2022), where robust memorization is similarly defined for neighborhoods of radius $\\mu$ strictly smaller than the separation $\\epsilon_\\mathcal{D}$. Regarding the upper bound, Yu et al. (2024) consider the regime where $\\rho = \\frac{\\mu}{\\epsilon_\\mathcal{D}}\\in(0,1)$, while Li et al. (2022) analyze the regime where $\\rho = \\frac{\\mu}{\\epsilon_\\mathcal{D}}\\in(0, 1/2)$. However, their upper bounds do not depend on $\\rho$, failing to capture the interpolation between non-robust ($\\rho=0$) and fully-robust ($\\rho=1$ or $1/2$) memorization.\n\n**W3. Potentially unrealistic precision requirements due to high bit complexity**\n\n- Under our construction, the bit complexity—defined as a bit needed **per parameter** under a fixed point precision—to implement our construction tightly matches the lower bound for the small and moderate $\\rho$ regimes. Moreover, construction on large $\\rho$ regimes also has a reasonable $\\tilde{O}(N)$ bit complexity. Overall, our constructions **do not need unrealistically high bit complexity.**\n- Upper bounds\n\n   We first introduce a bit complexity upper bound of the constructions in Theorem 4.2(i) and (ii). In both cases, the subnetworks for operations such as projection, translation, or coordinate mapping do not contribute significantly to the bit complexity. Instead, the dominant cost comes from the (non-robust) memorization subnetwork used in the final step, extended from Vardi et al. (2021), whose bit complexity scales with the network depth. The resulting bounds are $\\tilde{O}(\\sqrt{N})$ for (i) and $\\tilde{O}(d^{-1/4}\\rho^{-1/2})$ for (ii). \n \n    For Theorem 4.2(iii), we provide a separate derivation, yielding an $\\tilde{O}(N)$ upper bound on the bit complexity. \n \n    Let each weight $W_l, b_l$ be approximated by $\\bar{W}_l, \\bar{b}_l$ due to finite precision. Upon the recursive definition of a neural network on line 117, the limited-precision feedforward is: \n\n    $$\n    \\bar{a}\\_{l}(x)=\\sigma(\\bar{W}\\_{l}\\bar{a}\\_{l-1}(x)+\\bar{b}\\_l).\n    $$\n    \n    If we denote \n    - $\\zeta$: the precision (element-wise upper bound on $\\Delta W_l:=W_l-\\bar{W}_l$ and $\\Delta b_l:= b_l-\\bar{b}_l$),\n    - $D:=\\max_{0\\leq l \\leq L} d_l$ the maximum hidden layer width,\n    - $p$: an upper bound on the absolute value of every parameter,\n\n    We claim that the error $\\Delta a_l:=a_l-\\bar{a}_l$, can be bounded as $\\|\\|\\Delta a_L\\|\\|\\leq Q\\zeta$ for some $O(L)$ degree polynomial $Q$ on problem parameters.\n    \n    Consider the key recurrence:  \n    $$\n    \\begin{align*}\n    \\|\\|\\Delta a_{l+1}\\|\\|&=\\|\\|a_{l+1}-\\bar{a}_{l+1}\\|\\|\\\\\\\\\n    &= \\|\\|\\sigma(W_la_l+b_l)-\\sigma(\\bar{W}_l \\bar{a}_l+\\bar{b}_l)\\|\\|\\\\\\\\\n    &\\leq \\|\\|(W_l a_l+b_l)-(\\bar{W}_l\\bar{a}_l+\\bar{b}_l)\\|\\|\\\\\\\\\n    &=\\|\\|(W_l a_l+b_l) - ((W_l +\\Delta W_l)(a_l+\\Delta a_l)+(b_l+\\Delta b_l))\\|\\| \\\\\\\\\n    &\\leq \\|\\|W_l\\|\\| \\cdot \\|\\|\\Delta a_l\\|\\|+\\|\\|\\Delta W_l\\|\\| \\cdot\\|\\|a_l\\|\\| + \\|\\|\\Delta W_l\\|\\| \\cdot \\|\\|\\Delta a_l\\|\\| + \\|\\|\\Delta b_l\\|\\|\\\\\\\\\n    &\\leq (D p)\\|\\|\\Delta a_l\\|\\| + (D \\zeta) \\|\\|a_l\\|\\| + (D \\zeta) \\|\\|\\Delta a_l\\|\\| + \\sqrt{D} \\zeta\\\\\\\\\n    &= (Dp+D\\zeta)\\|\\|\\Delta a_l\\|\\|+ (D\\|\\|a_l\\|\\|+\\sqrt{D}) \\zeta.\n    \\end{align*}\n    $$\n    \n    By recursive definition of $a_l$, it is straightforward to check that $\\|a_l\\|$ is upper bounded in a scale of $S:=(\\textrm{poly}(\\cdot))^L$, where the polynomial is on problem parameters like $D, p$ and maximum radius $R$ of inputs. The recursive bound above therefore, concludes\n    \n    $$\n    \\|\\Delta a_L\\| \\leq (DS+\\sqrt{D})\\sum_{l=0}^{L-1}(Dp+D\\zeta)^l\\zeta = Q\\zeta,\n    $$\n    where $Q$ is some degree $O(L)$ polynomial. \n\n    Thus, once we have $\\zeta \\leq \\nu/Q$ for some small $\\nu$ (e.g. $\\nu=0.1)$, we can guarantee $\\|\\Delta a_L\\| \\leq \\nu$. Yet, the final output has a perturbation from the infinite precision network. One can resolve this perturbation by an additional “rounding” layer that maps $[c-\\nu, c+\\nu] \\mapsto c$ for all $c \\in [C]$. \n\n    To represent parameters bounded by $p$ with precision $\\zeta$, we require $\\log(p/\\zeta) = O(\\log(Qp/\\nu))$ bits. As $Q$ is a degree $O(L)$ polynomial, this corresponds to $O(L(\\log p + \\log D + \\log R))$ bit complexity. The construction of Theorem 4.2(iii) has $p=\\textrm{poly}(\\cdot)$ and $L = \\tilde{O}(N)$. Hence, $\\tilde{O}(N)$ bit complexity suffices. However, the framework introduced in (iii) for counting bit complexity works for a general neural network, leaving the possibility to reduce the complexity under construction-specific counting.\n\n- Lower bounds\n\n    Vardi et al. (2021) also provide a lower bound on bit complexity using upper and lower bounds on VC-dimension. When a network has bit-complexity $B$ and $P$ **nonzero** parameters, the VC-dimension is upper bounded as\n    \n    $$\n    \\textrm{VC-Dim}=O(PB+P\\log P).\n    $$\n    \n    As VC-dimension is lower bounded by $N$ by memorization, combining these two bounds suggests the necessary bit complexity required under our constructions in Theorem 4.2. For simplicity, assume the case where the omitted $d$ (as mentioned in line 210) is not dominant. \n\n    Recall that for small, moderate, and large $\\rho$ regime, we use $\\tilde{O}(\\sqrt{N})$, $\\tilde{O}(Nd^{1/4}\\rho^{1/2})$, and $\\tilde{O}(Nd\\rho^2)$ nonzero parameters, respectively. Consequently, the bit complexity becomes $\\tilde{\\Omega}(\\sqrt{N})$, $\\tilde{\\Omega}(\\frac{1}{d^{1/4}\\rho^{1/2}})$, and $\\tilde{\\Omega}(\\frac{1}{d\\rho^2})$. For the last case, the lower bound of bit complexity is upper bounded by $O(1)$ scale and becomes trivial. \n \n- As a result,\n    - For small $\\rho$ regime (Theorem 4.2(i)), the bit complexity is $\\tilde{\\Theta}(\\sqrt{N})$, tight up to the logarithmic factor.\n    - For moderate $\\rho$ regime (Theorem 4.2(ii)), the bit complexity is $\\tilde{\\Theta}(\\frac{1}{d^{1/4}\\rho^{1/2}})$, tight up to the logarithmic factor.\n    - For large $\\rho$ regime (Theorem 4.2(iii)), the bit complexity is $\\tilde{O}(N)$.\n\n**Q1. Threshold network memorization results not mentioned in related work?**\n\n- Thank you for pointing out important contributions in the area of memorization, particularly the results on threshold networks. We included Baum et al. (1988), which is indeed an example of such work, showing that a 2-layer threshold network with $\\lceil N/d\\rceil$ neurons suffices to memorize an arbitrarily given $N$ data points in general position in $d$ dimensions.\n- However, we acknowledge that due to space constraints, we were not able to include all relevant work. We will incorporate additional works in the final version, including those you mentioned—such as Vershynin (2020), Rajput et al. (2021), as well as [1] and [2].\n\n---\n\n> **References**\n>\n> [1] Eric B. Baum and David Haussler. What size net gives valid generalization? In Advances in Neural Information Processing Systems, 1989.\n>\n> [2] Wolfgang Maass. Bounds for the computational power and learning complexity of analog neural nets. SIAM Journal on Computing, 26(3):708–732, 1997."}, {"review_id": "vY2URaWQ67", "reviewer": "Reviewer_LKzZ", "summary": "The paper investigates the necessary and sufficient numbers of parameters needed for robust memorization\nof a dataset of size N, i.e. the correct classification of data even with small perturbations in the input. They\nestablish improved or completely new lower and upper bounds for the parameter complexity for all reasonable\nrobustness ratios.", "questions": "The authors already realized that they made a mistake, being inconsistent in their notion of “number of\nparameters”. While they considered only non-zero parameters in most of their results, one of their lower\nbounds relies on counting all parameters. In a separate document, they give a detailed explanation of this and\ntheir later choice to consider all parameters, also zero-valued ones. Further they provide the corrected results\nand the differences to the ones in the original paper. However, these corrected results are not compared to\nexisting literature in as much detail and result in a significant difference to a very prominent part of the\nproposed work, as the bound is no longer tight in the case of d= Θ(N). They should thoroughly revise the\nsubmitted paper to include the changes and avoid any misinterpretation of their results. Additionally there\nare some other corrections to make:\n\n1-The authors do not explain why they add up the two lower bounds on the parameter complexity. This\nseems counter intuitive and the sum is no longer a lower bound. Instead they should use the maximum\nof both bounds.\n\n2-In line 72, they wrote ρ ∈ (1/(5√d),1] as a half open interval including 1, while they consider ρ ∈\n(1/(5√d),1) elsewhere in the paper and explicitly explain that ρ = 1 leads to a contradiction in the\nrobust memorization setting.\n\n3-In Definition 2.1, they do not explicitly exclude the fact that all data points are classified equally\n(yi = yj ∀i,j). In this case the minimum is taken over an empty seta and thus ϵD is not defined.\n\n4-The authors write in line 230 that the robust memorization error mentioned in Theorem 4.2 ii) can be\narbitrarily small, but do not discuss why this is the case and how this can be done.", "limitations": "No", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The authors  give all necessary definitions and explain their choices and limitations (of which there are very few) in detail. They also give comprehensive sketches of proofs and visualized their results very well.", "was_revised": true, "final_justification": "I have raised my score to 4 and vote for acceptance", "rebuttal": "We thank the reviewer for the constructive feedback. Below, we address the reviewer’s concerns.\n\n**Q. Insufficient comparison of revised results to prior work; bound not tight for $d=\\Theta(N)$**\n\n- The corrected results under the new counting method are compared with prior works in Table 1 of Appendix D, and will be reflected in the main text. We will update the main text to reflect the new counting method as presented in the appendix and remove the tightness claim for $d=\\Theta(N)$, which we acknowledged to be incorrect (line 768).\n- We nevertheless want to emphasize that the new counting method still preserves the originally claimed lower bounds. This is mainly because the lower bound on nonzero parameter complexity serves as a lower bound on total parameter complexity (including zeros). Hence, comparisons between our lower bounds and existing ones remain valid.\n- Even from the upper bound perspective, although the rates have changed in certain ranges of $\\rho$, the important properties remain unchanged: tight complexity for small $\\rho$, and a continuously increasing upper bound with respect to $\\rho$.\n- Additionally, the original explanation and the comparison under the original counting method—including Figure 6—will be moved to an additional section in the appendix, to assist readers who are also interested in the results based on the non-zero parameter counts.\n\n**Q1. Justification for adding up the two lower bounds instead of taking the maximum?**\n\n- There are two lower bounds derived using different techniques: width and VC dimension. It is natural that the lower bound is given as the maximum of the two lower bounds. However, we can translate this into the addition of the two terms through the following inequality.\n    \n    $\\textrm{LB} \\geq \\max\\{\\textrm{LB by Width}, \\textrm{LB by VC-Dim}\\} \\geq \\frac{1}{2}(\\textrm{LB by Width} + \\textrm{LB by VC-Dim})$\n    \n    Since $\\Omega(\\cdot)$ for the lower bound hides constant terms (e.g. $\\frac{1}{2}$), it is reasonable to write the lower bound as the sum of the two lower bounds. We kindly refer the reviewer to lines 160-161 for a brief explanation on these, with further details provided in Appendix A.4. \n    \n\n**Q2.** $\\rho=1$ **included in line 72?**\n\n- Thank you for the careful reading. We will revise the typo by changing the half-open interval into an open interval, making it consistent with other parts of the writing.\n\n**Q3. Excluding trivial cases with single-class labels**\n\n- Yes, when all points in $\\mathcal{D}$ have the same label, $\\epsilon_\\mathcal{D}$ using the minimum notation is not properly defined. However, if we interpret the minimum as an infimum, we get $\\epsilon_\\mathcal{D}=+\\infty$ for being the infimum of an empty set. Consequently, $\\mu=\\rho\\epsilon_\\mathcal{D} = +\\infty$ for any $\\rho \\in (0, 1)$. In this case, assigning the bias of the last layer to the common label and setting all other parameters to zero yields a constant output over the entire domain. Thus, this trivially satisfies $\\rho$-robustly memorization for any $\\rho$.\n- Since this case is mathematically trivial, we will revise our writing to **exclude** single-class label datasets to maintain rigor and clarity. Thank you for pointing this out.\n\n**Q4. Why can the error in Theorem 4.2 (ii) be made arbitrarily small?**\n\n- We provide a brief explanation of how an arbitrarily small error can be achieved in the last paragraph of Section 5.2 (proof sketch). To guide readers who may have similar concerns when first encountering Theorem 4.2, we will include a reference to Section 5.2 in the discussion following Theorem 4.2.\n- In addition, we elaborate below on how the construction ensures an arbitrarily small error in greater detail—this explanation will also be supplemented in the proof sketch:\n    \n    The proof of Theorem 4.2(ii) partitions the $N$ points into multiple **groups** of approximately equal size. The robust memorizer is constructed by composing a set of subnetworks, each responsible for robustly memorizing one group.\n    \n    To achieve this, each subnetwork creates its own grid based on its group's data points, ensuring that the robustness balls of the group’s points lie entirely within the grid. Using a coordinate mapping, the subnetwork is designed to output the correct labels within its associated grids and zero elsewhere (Lemma B.10). \n    \n    However, since the coordinate map is discontinuous, its approximation using ReLU introduces an **error-tolerant regions**—areas where the output is not guaranteed. These regions are illustrated in purple in Figure 4(b).\n    \n    Each subnetwork accurately labels its own group’s robustness balls by ensuring they are placed within the grid while avoiding its error-tolerant regions. However, robustness balls from other groups may intersect this error-tolerant region, resulting in errors. As shown in Lemma B.9, the volume of a ball intersecting the error-tolerant region is proportional to the region’s width. This width can be made arbitrarily small by increasing the slope of the ReLU network (Lemma B.15). Consequently, the probability that a point of the robustness ball falls into the error-tolerant region—i.e., the error of robust memorization—is inversely proportional to the ReLU slope and can be made arbitrarily small."}, {"review_id": "6EDw6yZCbU", "reviewer": "Reviewer_nD17", "summary": "This paper analyzes the number of ReLU neural network parameters needed to achieve robust memorization, which requires that the network interpolate a discretely-labeled dataset while maintaining the same output value within $\\mu$ distance of each training point. The parameter complexity is studied as a function of the robustness ratio $\\rho = \\mu/\\epsilon$, where $2\\epsilon$ is the minimum distance between any distinctly-labeled training points. The paper demonstrates novel and improved upper and lower bounds across all values of $\\rho$, which are tight (unlike previous bounds) for small $\\rho \\in (0, 1/\\sqrt{N/d})$ in the case $d = \\Theta(\\sqrt{N})$.", "questions": "- See my above question regarding Theorem 4.2 (ii) under \"weaknesses.\"\n- Comment: it would be helpful to illustrate the robustness radius $\\mu$ of a simple low-dimensional dataset and various interpolating solutions with different robustness ratios.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is well-written and the organization is clear. Figure 1, which illustrates graphically how the authors' bounds compare to previous ones in different regimes, is particularly helpful.\n- The idea of analyzing parameter complexity across the entire possible range of robustness ratio $\\rho$ is interesting, as it allows for a more unified view of the complexity required for robust vs. non-robust memorization. The bounds demonstrated here are novel and strictly improve upon previous results in almost all cases.\n- In the supplementary material, the authors correct an inconsistency in their original submission which led to overly tight bounds in the $d = \\Theta(N)$ regime; their honesty and rigor in doing this is appreciated.\n\nWeaknesses:\n- There is still a substantial gap between the upper and lower bounds demonstrated in the paper, suggesting that they could be further improved (which the authors acknowledge). The claimed tightness in the $d = \\Theta(N)$ regime in the initial submission is clarified to be incorrect in the supplementary material, although the revised bounds in this case still improve upon existing results.\n- The upper bound in Theorem 4.2 (ii) only shows $\\rho$-robust memorization up to an arbitrarily small error $\\eta > 0$. The authors note that this arises from inability of ReLU networks to exactly represent discontinuous functions, but because it seems to arise from their specific coordinate map technique, it is not clear to me whether this error is inherent to the problem itself (i.e., memorization with $\\eta = 0$ is actually not possible in this regime with $\\tilde{O}(Nd^{1/4} \\rho^{1/2})$ parameters) or whether it is just an artifact of the proof strategy. If the former, is there a simple example (say in $d = 1$) which illustrates why $\\eta = 0$ error is not possible?", "was_revised": true, "final_justification": "I thank the authors for their feedback. I continue to recommend acceptance. I encourage them to consider adding some of what they included in their response to me regarding the $\\eta > 0$ error in Theorem 4.2 (ii) to the paper itself (at least the appendix), as this may be a natural question that other readers could have, and to consider adding a figure illustrating interpolation with different robustness ratios in a simple scenario, as I believe this will help intuitively convey the concept.", "rebuttal": "We thank the reviewer for the positive and careful comments. Below, we address the reviewer’s concerns and comments.\n\n**W1. Substantial gap remains between upper and lower bounds**\n\nYes, there does remain a gap between upper and lower bounds for certain ranges of $\\rho$. Although we tried to further tighten this gap, we faced challenges on both sides. \n\n- On the upper bound side, devising a construction that can adapt to **arbitrary geometric configuration** of data points under a limited budget of parameters remains challenging.\n- On the lower bound side, our bound on the minimum width of the first hidden layer is already tight, so further improving the parameter lower bound would require more sophisticated techniques beyond characterizing the first hidden layer width. In the large $\\rho$ regime, our bounds tightly characterize the necessary (Proposition 3.2) and sufficient (Proposition B.16 and the paragraph “Tight Bounds of Width with Large $\\rho$” in Section 4) first hidden layer width. Additionally, for small and moderate $\\rho$ regime, improving the lower bound on width is impossible, since it has been shown that logarithmic width suffices ([1] and our Theorem 4.2 (i), (ii)).\n\nNevertheless, overcoming these challenges and closing the remaining gaps between the upper and lower bounds remains a substantial and promising direction for future work.\n\n**W2 & Q1. Unclear whether the small error $\\eta$ in Theorem 4.2 (ii) is inherent or technical**\n\nThe inevitability of $\\eta$ error is **mainly due to our coordinate map technique** followed by the continuous nature of ReLU. Approximating the discontinuous coordinate map using a continuous function that is made of ReLU naturally requires **error-tolerant regions**—where the approximation can be inexact—around the discontinuous points of the coordinate map. These error-tolerant regions are illustrated as a purple region in Figure 4 in our construction and are the entire source of the error. \n\nWe further conjecture that it is not inherent to the problem itself. \n\n- At least for the special case $d=1$ you mentioned, interestingly, a tight upper bound $\\tilde{O}(\\sqrt{N})$—matching the lower bound for memorization—can be achieved for all $\\rho \\in (0, 1)$ without error. The result is based on a careful modification of the (non-robust) memorization construction (Vardi et al. (2021)), which does not rely on our coordinate mapping techniques.\n    \n    In the first step of their construction, they linearly project the inputs to 1-dimension. This projection step, when viewed in the context of robust memorization, significantly restricts the feasible $\\rho$ at the cost of simplifying the geometry while keeping the projected balls separated. However, $d=1$ case already has the simplified geometry from the start, and so the feasible range of $\\rho$ needs no restriction. A modification of the remaining steps, ensuring the predictions remain consistent within each robustness ball, proves the result. This suggests that the $\\eta$ error is not inherent, at least in this special case.\n    \n- As a side remark, threshold activations have inherent discontinuity unlike ReLU. Therefore, the additional use of threshold activation on top of ReLU is one possible remedy to overcome the error, although this makes the problem inherently different. Simply speaking, we can completely remove the error-tolerant regions in this case, because we can perfectly implement ideal building blocks for the floor function (introduced as $\\Delta$ in line 1428) using both ReLU and threshold activations together. Thus, combining ReLU and threshold activations allows the robust memorization without an error using the same number of parameters as in Theorem 4.2(ii).\n\n**Q2. Illustration of robustness radius and interpolating solutions in a low-dimensional setting with varying robustness ratios?**\n\nWe thank the reviewer for the suggestion on the illustration. We will consider adding an illustrative figure that depicts interpolating solutions corresponding to different robustness ratios. \n\n---\n> **References**\n>\n> *[1] Amitsour Egosi, Gilad Yehudai, and Ohad Shamir. Logarithmic width suffices for robust memorization, 2025.*\n>\n> *[2] Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of ReLU neural networks, 2021.*"}, {"review_id": "qXV593lxf5", "reviewer": "Reviewer_YP8D", "summary": "The paper studies the robust memoization problem for neural networks. In this problem, the input is a labeled dataset, and the goal is to return a memorizing neural network that is as small as possible and robust to small perturbations. In this paper, perturbations are measured in an l2 sense, so that the labels in a small Euclidean ball around any data point must remain constant, and the size of the network is measured in the number of parameters.\nThe paper derives several new upper and lower bounds for the network size, depending on the input dimension, dataset size, and radius of the robustness ball.", "questions": "1. I understand that some of the literature about robust memoization naturally deals with ReLU networks. However, since the labels are necessarily discrete, to me it seems natural to consider piecewise constant networks, rather than piecewise linear. I.e. replace ReLU by threshold/step. Would things simplify significantly in that case? Do the authors believe their approach could yield tight bounds for these networks?\n\n2. For adversarial examples, the L_\\infty norm is the most natural way to measure the size of perturbations. As far as I can see from Appendix C, not all results extend to this norm. Can the authors please comment on this point?", "limitations": "No societal impact.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Overall, this is an interesting paper. The problem of memoization in general, and in particular robust memoization, has garnered a lot of attention in recent years. The paper adds new results to this line of research and will probably draw the attention of some parts of the community.\nIt is particularly nice that the authors manage to derive tight bounds in the regime where the robustness radius goes to 0 with the other parameters. This is perhaps not too surprising, since they show that the robust memoization problem essentially reduces to the standard memoization problem. Still, it complements the existing literature in a natural way.\n\nThe techniques in the paper are not particularly novel. The upper bound relies on VC dimension consideration as well as an explicit natural construction. The lower bound follows from dimensionality reduction considerations, which have appeared before in one form or another. I will make the remark that even if the approach is based on existing techniques, it was not implemented it this exact way before, so I would not necessarily hold it against the paper. \n\nIn light of the above, it is my impression that the paper meets the bar for NeurIPS\n\nI have gone over the proofs, some of which seem to be very technical, and I think I agree with everything. I have one comment about the current writing of the paper. The introduction seems to contain a lot of redundancies and many repetitions about the obtained bounds and existing bounds in the literature. In my opinion, it would be much better and improve readability to condense those repeated discussions into a single table to detail the new bounds and compare to previous results. This would leave more room to discuss the different aspects of the proofs, give more intuition for the technical parts, and explain the differences between the different regimes. Currently, Section 5 does a decent job of explaining some parts of the paper, but it would be of great benefit to expand this section.", "was_revised": true, "final_justification": "As indicated in my original report, I have a positive impression of the paper. I maintain that impression after reading the authors' response.", "rebuttal": "We thank the reviewer for the careful reading and constructive feedback. Below, we address the reviewer’s concerns and questions.\n\n**W1. Limited novelty in techniques for both lower and upper bounds**\n\n- We appreciate the reviewer’s recognition that, despite building on existing ideas, our implementation offers a novel contribution. As the reviewer noted, the lower bound based on VC-dimension and the use of dimensionality reduction in the upper bound can be seen as extensions of known ideas. Nevertheless, we would like to elaborate on parts of our approach that go beyond existing techniques and involve substantial technical challenges.\n    1. **Upper bound:** To the best of our knowledge, using lattice mapping to preserve the geometry of the ball is novel. In Theorem 4.2(i), we establish a condition ensuring that the robustness ball lies sufficiently far from the lattice grid (Lemma B.12), and we show that the discontinuous floor function can be approximated by a continuous ReLU network  (Lemma B.13). \n    In Theorem 4.2(ii), we compute the probability that a uniformly random point from the ball falls into the error zone under random projection (Lemma B.9). Another key technical challenge was ensuring correct classification even within regions where multiple robustness balls with the same label overlap. To address this, we devised disjoint, integer-aligned interval encodings and carefully bounded the propagation of error (Lemma B.10).\n    2. **Lower bound:** Prior work (Theorem 4.3 in Yu et al.) established a lower bound on the first hidden layer width under the $\\ell_\\infty$-norm, but not under the $\\ell_2$-norm. In our work, we analyze the lower bound on width under the $\\ell_2$ -norm using more sophisticated geometrical analysis—by computing the upper bound on the distance between the standard basis vectors and any subspace of given dimension (Lemma A.1). The $\\ell_2$-norm requires a more intricate analysis since, unlike the $\\ell_\\infty$-norm, it does not allow coordinate-wise analysis. \n        \n        Furthermore, to overcome the constraint $N \\geq d$ in the prior lower bound and to cover even the case $N<d$, we derive a new bound on the distance between a **subset** of standard basis vectors and subspaces of given dimension (Lemma A.2), deriving the first lower bound on the first hidden layer width **without** such a restriction.\n        \n\n**W2. Redundancy in the introduction**\n\n- We appreciate your thoughtful comments regarding the writing, particularly the redundancy in the introduction. We will revise the introduction to remove repetitions and present the key results more concisely.\n\n**Q1. Would the results simplify or yield tight bounds when using threshold networks instead of ReLU?**\n\n- We would like to discuss the potential relevance of piecewise constant networks, such as threshold networks, from two different perspectives—(1) using a combination of ReLU and threshold, and (2) using threshold alone.\n- Firstly, as we describe in lines 228-235, if we are allowed to use threshold activations on top of ReLU, we can construct a network where the upper bound in the moderate $\\rho$ regime (Theorem 4.2(ii)) holds without any error.\n    \n    Moreover, we agree with the reviewer’s view that the use of piecewise constant networks can be seen as natural for discrete label classification, especially at the last layer. In fact, our construction explicitly approximates threshold functions using ReLU in order to achieve robust memorization within robustness balls. \n    \n- Secondly, consider the case where we use only threshold activations.\n    1. **Lower bound by the first hidden layer width** (Proposition 3.2): This result is independent of the activation function, so the same lower bound remains valid for threshold networks. \n    2. **Lower bound by VC-dimension** (Proposition 3.3): This result can in fact improve when using threshold activations. While the VC-dimension of a ReLU network with $P$ parameters is $O(P^2)$, the VC-dimension of a threshold network is only $\\tilde{O}(P)$ (Baum and Haussler (1989) [1]). \n        \n        Notably, our result that the VC-dimension of a robust memorizer is $\\text{VC-dim}(\\mathcal{F})=\\Omega\\left( \\frac{N}{1-\\rho^2} \\right)$ for $\\rho \\in \\left( 0, \\sqrt{1-\\frac{1}{d}} \\right]$ still holds under threshold activation. This implies a lower bound on the number of parameters $P = \\tilde{\\Omega}\\left( \\frac{N}{1-\\rho^2} \\right)$ for $\\rho \\in \\left( 0, \\sqrt{1-\\frac{1}{d}} \\right]$ and $P=\\tilde{\\Omega}(Nd)$ for $\\rho \\in \\left(\\sqrt{1-\\frac{1}{d}},1 \\right)$. These bounds are stronger than those for ReLU networks, and they exceed $N$. \n        \n    3. **Upper bound** (Theorem 4.2): The VC-dimension result implies that parameter complexity identical to the ReLU upper bounds in the small and moderate $\\rho$  regimes (Theorem 4.2(i), (ii)) cannot be achieved by threshold-only networks, since those rates are sublinear in $N$. The threshold lower bounds by VC-dimension indicate that showing such upper bounds is impossible in general.\n        \n        However, the adaptability of Theorem 4.2(iii) to threshold-only networks in the large $\\rho$ regime remains an open question. Our current construction relies on the ability of ReLU to propagate input values as-is across layers, which is not directly achievable using threshold functions. As a result, it is nontrivial to determine whether the rate in Theorem 4.2(iii) can be matched using threshold networks. We believe this is an interesting direction for future research.\n        \n        We also note that Rajput et al. (2021) [2] provide an upper bound $\\tilde{O}(N+\\frac{d}{\\epsilon_\\mathcal{D}})$ for non-robust memorization using threshold networks, which may offer a useful reference point for further developing analogous results in the robust setting.\n        \n    \n\n**Q2. Limited extension of results to the $\\ell_\\infty$-norm?**\n\n- We appreciate the reviewer’s question about the applicability of our results to the $\\ell_\\infty$-norm, which is indeed a natural choice.\n1. **Lower bound by the first hidden layer width**:  Proposition C.7 shows that the same lower bound of width $\\rho^2 \\min\\{N,d\\}$ holds under the $\\ell_\\infty$-norm.\n2. **Lower bound by VC-dimension**: While we do not provide an exact VC-dimension lower bound specifically for the $\\ell_\\infty$-norm, we do present a result under the general $\\ell_p$-norm (Theorem C.6) for $p \\in [1,\\infty)$, where the VC-dimension is lower bounded by $\\Omega \\left( {\\frac{N}{1-\\rho^p}}\\right)$. This implies that the number of parameter is lower bounded by $\\Omega \\left( \\sqrt{\\frac{N}{1-\\rho^p}}\\right)$. This bound also holds in $p \\to \\infty$, but in that case it simplifies to $\\Omega(\\sqrt{N})$, which is the trivial bound from the standard memorization. \n3. **Upper bound:** We provide the result in Theorem C.10 with $\\gamma_\\infty(d)=\\sqrt{d}$ .\n    \n    (i) For $\\rho \\in(0,\\frac{1}{5Nd})$, the same upper bound $\\tilde{O}(\\sqrt{N})$ holds as in the $\\ell_2$ case.\n    \n    (ii) For $\\rho \\in(\\frac{1}{5Nd},\\frac{1}{5d})$, we obtain an upper bound of $\\tilde{O}(Nd^{1/2}\\rho^{1/2})$ with arbitrarily small error.\n    \n    (iii) For $\\rho \\in(\\frac{1}{5d},\\frac{1}{\\sqrt{d}})$, we obtain an upper bound of  $\\tilde{O}(Nd^4\\rho^4)$.\n    \n    We also note a minor mistake in the constants defining $\\rho$ intervals in lines 1691 and 1693, where 2 should be corrected to 5.\n    \n\n---\n\n> **Reference**\n>\n> *[1] Eric B. Baum and David Haussler. What size net gives valid generalization? Computation, 1(1):151–160, 1989.*\n>\n> *[2] Shashank Rajput, Kartik Sreenivasan, Dimitris Papailiopoulos, and Amin Karbasi. An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks. In Advances in Neural Information Processing Systems, volume 34, pp. 12674–12685. Curran Associates, Inc., 2021.*"}]

Author rebuttal:

Meta-review: The paper considers the parameter-complexity robust memorization with ReLU networks: That is, given $N$ datapoints, how large should a ReLU network be to memorize this data such that it is robust to input perturbations. This work presents upper and lower bounds for the same. The reviewers raised some concerns such as:
- Inconsistent usage of non-zero parameter count and total parameter count 
- Possible high bit complexity
- The gap between upper and lower bounds in terms of $\rho$

The rebuttal answered these concerns satisfactorily. This work pursues an important direction in understanding the parameter complexity of ReLU networks, even though it uses standard techniques. Thus, it would be a positive addition to the literature. Based on the positive reviewer recommendations, I recommend accepting the paper.
Decision: Accept (poster)