The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets

We thank the reviewer for the careful reading and constructive feedback. Below, we address the reviewer’s concerns and questions.

W1. Limited novelty in techniques for both lower and upper bounds

• 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.

  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). 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).

  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.

     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.

W2. Redundancy in the introduction

• 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.

Q1. Would the results simplify or yield tight bounds when using threshold networks instead of ReLU?

• 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.

• 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.

  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.

• Secondly, consider the case where we use only threshold activations.

  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.

  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]).

     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$.

  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.

     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.

     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.

Q2. Limited extension of results to the $\ell_\infty$-norm?

• We appreciate the reviewer’s question about the applicability of our results to the $\ell_\infty$-norm, which is indeed a natural choice.

1. 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.

2. 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.

3. Upper bound: We provide the result in Theorem C.10 with $\gamma_\infty(d)=\sqrt{d}$ .

   (i) For $\rho \in(0,\frac{1}{5Nd})$, the same upper bound $\tilde{O}(\sqrt{N})$ holds as in the $\ell_2$ case.

   (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.

   (iii) For $\rho \in(\frac{1}{5d},\frac{1}{\sqrt{d}})$, we obtain an upper bound of $\tilde{O}(Nd^4\rho^4)$.

   We also note a minor mistake in the constants defining $\rho$ intervals in lines 1691 and 1693, where 2 should be corrected to 5.

Reference

[1] Eric B. Baum and David Haussler. What size net gives valid generalization? Computation, 1(1):151–160, 1989.

[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.

We thank the reviewer for the positive and careful comments. Below, we address the reviewer’s concerns and comments.

W1. Substantial gap remains between upper and lower bounds

Yes, 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.

• 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.
• 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)).

Nevertheless, overcoming these challenges and closing the remaining gaps between the upper and lower bounds remains a substantial and promising direction for future work.

W2 & Q1. Unclear whether the small error $\eta$ in Theorem 4.2 (ii) is inherent or technical

The 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.

We further conjecture that it is not inherent to the problem itself.

• 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.

  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.

• 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).

Q2. Illustration of robustness radius and interpolating solutions in a low-dimensional setting with varying robustness ratios?

We 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.

References

[1] Amitsour Egosi, Gilad Yehudai, and Ohad Shamir. Logarithmic width suffices for robust memorization, 2025.

[2] Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of ReLU neural networks, 2021.

We thank the reviewer for the constructive feedback. Below, we address the reviewer’s concerns.

Q. Insufficient comparison of revised results to prior work; bound not tight for $d=\Theta(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).
• 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.
• 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$.
• 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.

Q1. Justification for adding up the two lower bounds instead of taking the maximum?

• 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.

  $\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})$

  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.

Q2. $\rho=1$ included in line 72?

• 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.

Q3. Excluding trivial cases with single-class labels

• 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$.
• 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.

Q4. Why can the error in Theorem 4.2 (ii) be made arbitrarily small?

• 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.

• 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:

  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.

  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).

  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).

  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.

Dear Reviewer,

Thank you again for your review and for expressing earlier that you intended to raise your score after the rebuttal. As the discussion period is coming to a close, we just wanted to kindly remind you of this in case you would like to update anything.

Best, Authors

We thank the reviewer for the constructive feedback.

W1. Inconsistent parameter count standard across comparisons

• 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.
• We acknowledge that prior works we compared against report results in terms of the number of non-zero parameters. To ensure a fair comparison:
  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.
  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.

W2. Potential limitation on allowable labeling due to the assumption $\rho\in (0,1)$

• 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.
• 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.
• 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.

W3. Potentially unrealistic precision requirements due to high bit complexity

• 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.

• Upper bounds

  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).

  For Theorem 4.2(iii), we provide a separate derivation, yielding an $\tilde{O}(N)$ upper bound on the bit complexity.

  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:

  $$\bar{a}\_{l}(x)=\sigma(\bar{W}\_{l}\bar{a}\_{l-1}(x)+\bar{b}\_l).$$

  If we denote

  • $\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$),
  • $D:=\max_{0\leq l \leq L} d_l$ the maximum hidden layer width,
  • $p$: an upper bound on the absolute value of every parameter,

  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.

  Consider the key recurrence:

  $$$$

$

\|\|\Delta a_{l+1}\|\|&=\|\|a_{l+1}-\bar{a}_{l+1}\|\|\\\\
&= \|\|\sigma(W_la_l+b_l)-\sigma(\bar{W}_l \bar{a}_l+\bar{b}_l)\|\|\\\\
&\leq \|\|(W_l a_l+b_l)-(\bar{W}_l\bar{a}_l+\bar{b}_l)\|\|\\\\
&=\|\|(W_l a_l+b_l) - ((W_l +\Delta W_l)(a_l+\Delta a_l)+(b_l+\Delta b_l))\|\| \\\\
&\leq \|\|W_l\|\| \cdot \|\|\Delta a_l\|\|+\|\|\Delta W_l\|\| \cdot\|\|a_l\|\| + \|\|\Delta W_l\|\| \cdot \|\|\Delta a_l\|\| + \|\|\Delta b_l\|\|\\\\
&\leq (D p)\|\|\Delta a_l\|\| + (D \zeta) \|\|a_l\|\| + (D \zeta) \|\|\Delta a_l\|\| + \sqrt{D} \zeta\\\\
&= (Dp+D\zeta)\|\|\Delta a_l\|\|+ (D\|\|a_l\|\|+\sqrt{D}) \zeta.

$

$$

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

$$
\|\Delta a_L\| \leq (DS+\sqrt{D})\sum_{l=0}^{L-1}(Dp+D\zeta)^l\zeta = Q\zeta,
$$
where $Q$ is some degree $O(L)$ polynomial. 

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]$. 

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.

• Lower bounds

  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

  $$\textrm{VC-Dim}=O(PB+P\log P).$$

  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.

  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.

• As a result,

  • For small $\rho$ regime (Theorem 4.2(i)), the bit complexity is $\tilde{\Theta}(\sqrt{N})$, tight up to the logarithmic factor.
  • 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.
  • For large $\rho$ regime (Theorem 4.2(iii)), the bit complexity is $\tilde{O}(N)$.

Q1. Threshold network memorization results not mentioned in related work?

• 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.
• 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].

References

[1] Eric B. Baum and David Haussler. What size net gives valid generalization? In Advances in Neural Information Processing Systems, 1989.

[2] Wolfgang Maass. Bounds for the computational power and learning complexity of analog neural nets. SIAM Journal on Computing, 26(3):708–732, 1997.

I thank the authors for the detailed clarifications and adding the bit complexity bounds. I am glad to see that they are not unreasonable.

I continue to recommend acceptance. I urge the authors to include their clarifications in their manuscript so that the readers may benefit from them.