Provable Tempered Overfitting of Minimal Nets and Typical Nets
Authors: Itamar Harel
William M. Hoza
Gal Vardi
Itay Evron
Nathan Srebro
Daniel Soudry
Venue: NeurIPS 2024 poster (2024)
Keywords: Deep Learning
Tempered Overfitting
Generalization
Primary area: learning_theory
TL;DR: We prove that fully connected neural networks with quantized weights exhibit tempered overfitting when using both the smallest interpolating NN and a random interpolating NN.

Abstract: We study the overfitting behavior of fully connected deep Neural Networks (NNs) with binary weights fitted to perfectly classify a noisy training set. We consider interpolation using both the smallest NN (having the minimal number of weights) and a random interpolating NN. For both learning rules, we prove overfitting is tempered. Our analysis rests on a new bound on the size of a threshold circuit consistent with a partial function. To the best of our knowledge, ours are the first theoretical results on benign or tempered overfitting that: (1) apply to deep NNs, and (2) do not require a very high or very low input dimension.

Provable Tempered Overfitting of Minimal Nets and Typical Nets
Itamar Harel
William M. Hoza
Gal Vardi Weizmann Institute of Science
Technion
The University of Chicago
ttamarhare1100gmm 00gemaa1110mmm111111mmmm com
Itay Evron Technion
Nathan Srebro
Daniel Soudry Technion
Toyota Technological Institute at Chicago
Abstract
We study the overfitting behavior of fully connected deep Neural Networks (NNs) with binary weights fitted to perfectly classify noisy training set. We consider interpolation using both the smallest NN (having the minimal number of weights) and random interpolating NN. For both learning rules, we prove overfitting tempered. Our analysis rests on new bound on the size of threshold circuit consistent with a partial function. To the best of our knowledge, ours are the first theoretical results on benign or tempered overfitiing that: (1) apply to deep NNs, and (2) do not require very high or very low input dimension.
Introduction
Neural networks (NNs) famously exhibit strong generalization capabilities, seemingly in defiance of traditional generalization theory. Specifically, NNs often generalize well empirically even when trained to interpolate the training data perfectly 97 This motivated an extensive line of work attempting to explain the overfitting behavior of NNs, and particularly their generalization capabilities
when trained to perfectly fit training set with corrupted labels (e.g.. 5 28 57
In an attempt to better understand the aforementioned generalization capabilities of NNs, Mallinar al. [57] proposed taxonomy of benign, tempered, and catastrophic overfitting. An algorithm that perfectly interpolates a training set with corrupted labels, i.e., an interpolator, is said to have tempered overfitting its generalization error neither benign nor catastrophic than trivial. However, the characterization of overfitting in NNs is still incomplete, especially in deep NNs when the input dimension is neither very high nor very low. In this paper, we aim understand the overfitting behavior of deep NNs in this regime.
not optimal but much better
We start by analyzing tempered overfitting in "min-size" NN interpolators, i.e., whose neural layer widths are selected to minimize the total number of weights. The number parameters in a model is natural complexity measure in learning theory and practice. For instance, it is theoretically well understood that L1 regularization in a sparse linear regression setting yields sparse regressor. Prac- tically, finding small-sized deep models is common objective used in pruning (e.g., (33) and neural architecture search (e.g., (54)). Recently, Manoj and Srebro (58) proved that the shortest program (Turing machine) that perfectly interpolates noisy datasets exhibits tempered overfitting, illustrating how powerful model can avoid catastrophic overfitting by returning a min-size interpolator.
Furthermore, study tempered overfitting in random ("typical"") interpolators NNs sampled uniformly from the set of parameters that perfectly fit the training set. Given a narrow teacher model and no label noise, Buzaglo et al. [13] recently proved that such typical interpolators, which may be highly overparameterized, generalize well. This is remarkable since these interpolators do not rely on
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

explicit regularization or the implicit bias of any gradient algorithm. An immediate question arises what kind generalization behavior do typical interpolators exhibit in the presence of label noise? This is especially interesting in light of theoretical and empirical findings that typical NNs implement while interpolating noisy training sets may require high frequencies.
low-feeqeency functions
For both the min-size and typical NN interpolators, we study the generalization behavior under an underlying noisy teacher model. We focus on deep NNs with binary weights and activations (similar NNs are used in resource-constrained environments; e.g., 422). Our analysis reveals that these models exhibit tempered overfitting behavior that depends on the statistical properties of the label noise. For independent noise, in addition to an upper bound we also find a lower bound on the expected generalization error. Our results are illustrated in Figure [ below. which the yellow line in the right panel is similar to empirically observed linear behavior (e.g., 57] Figures 2, 3, and 6].
0.5
0.5
Generalization error En(A(S))
Peneralizzatin error Enr(A(5))
0.4
0.4
0.3
0.3
0.2
0.2
Trivial performance
011
Bound under arbitrary noise
0.1-
Concentration under indep, noise
Bayes optimal
0.
3.6
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Noise level
Noise level
(a) With noisy labels distribution D
(b) With clean labels distribution Do
Figure 1: Types of overfitting behaviors. Consider binary classification problem of learning a realizable distribution Dp- Let 'D be the distribution induced by adding an E* E"-probability for data point's 's label be flipped relative Do- Suppose model is trained with data from D. Then, assuming the classes are balanced, the trivial generalization performance is 0.5 (in gray; e.g. with constant predictor). Left. Evaluating the model 'D, Bayes-optimal hypothesis (in red) obtains generalization error of e*. For large enough training sets, our results (Section 4 dictate tempered overfitting behavior illustrated above. For arbitrary noise, the error approximately bounded by 1-E** (1 -1-5" =====)===" (blue). For independent noise, the error is concentrated around the tighter 2.* (1 s*) (yellow). A similar figure was previously shown in Manoj and Srebro (58) for shortest-program interpolators. Right. Assuming independent noise, the left figure can be transformed into the error of the model on Do (see Lemma A.9). The linear behavior in the independent setting (yellow) is similar to the behavior observed empirically in Mallinar et al. [57 Figures 2, 3, and 6].
The contributions of this paper are:
Returning a min-size NN interpolator is a natural learning rule that follows the Occam' s-razor principle. We show that this learning rule exhibits tempered overfitting (Section 4.1)
We prove that overparameterized random NN interpolators typically exhibit tempered overfitting with generalization close to a min-size NN interpolator (Section 4.2).
To the best of our knowledge, that: (1) apply to deep NNs, and (2) do not require a very high or very low input dimension.
the first theoretical results on benign or tempered overfitting
The above results rely on a key technical result datasets generated by a constant-size teacher model with label noise can be interpolated jusing NN of constant depth with threshold activations, binary weights, a width sublinear in N. and roughly H(=*). N weights, where H(=*) is the binary entropy function of the fraction of corrupted labels (Section
As long has no repeated data points with opposite labels. See Def. 2.5 of consistent datasets.

---

2 Setting
Notation, We reserve bold lowercase characters for vectors, bold uppercase characters for matrices,
and regular uppercase characters for random elements. We use log to denote the hase logarithm, and
In to denote the natural logarithm. For pair of vectors d (d1, ....... (di,...,dz) d2)
d' (d/, ..... : d²) E N we denote d S d' if for all I [L], di I d'. We use @ to denote the XOR between two binary {0. 1} values, and @ to denote the Hadamard (elementwise) product between two vectors. We use H (D) to denote the entropy of some distribution D. Finally, use Ber (E) for the Bernoulli distribution with parameter e, and H (e) for its entropy, which is the binary entropy function.
2.1 Model: Fully connected threshold NNs with binary weights
Similarly to Buzaglo et al.
13 we define the following model.
Definition 2.1 (Binary threshold networks). For depth T., widths d = (d1 (d1,...,d2) ,z,), input dimension da. a scaled-neuron fully connected binary threshold NN, or binary threshold network, is mapping 0 - he such that he {0. 1) + {0, 1)d,, parameterized by
0 (w()), ba) b(,, 70)0 Im1
where for every layer / E [L],
W E ol"h f0, 1]doxd-1 (1) E 11-1000, boo = 1...-,,........1.111.
This mapping is defined recursively ho (x) 1((4) (x) where
10) (x) = x E ADD (x) = of (7:00) (W())-)) (x)) + bb))
> 0}
We denote the number of weights by w(d) = Et. d:d-11 and the total number of neurons
by n (d) Σt= d. The total number of parameters in such NN is M (dl) = w (d) + (d). We denote the set of functions representable as binary networks of widths d by HPTN and their
corresponding parameter space by @BTN (d).
Remark 2.2. Our generalization results are for the above formulation of neuron scalars 7, i.e. ternary
scaling before the activation. However, we could have derived similar results if, instead, we changed the scale to appear after the activation and also adjusted the range of the biases (see Appendix G). Although we chose the former for simplicity, the latter similar the ubiquitous phenomenon in neuroscience known as "Dale's 's Law" (22. This law, in simplified form, means that all outgoing synapses of neuron have the same effect, e.g., are all excitatory (positive) or all inhibitory (negative).
Remark 2.3 (Simple counting argument). Let dmax max {di,... dr.-13 be the maximal hidden- layer width. Then, combinatorially, it holds that
log
|HBTN
< log BBIN (d) <
(d)
(d)
(log(3) log 2d 2ddmax
hypotheses
# pammeter assignments
weights
# neurons
muximal quantization
This implies, using classical PAC bounds (75], that the sample complexity learning with the finite
hypothesis class HPBN is O (w (d) + n (d) log dmmax) (a more refined bound on | is given in
Lemma F.I) In Section 4 we show how this generalization bound can be improved in our setting.
2.2 Data model: A teacher network and label-flip noise
Data distribution. Let X = {0, 13dh and let D be some joint distribution over a finite sample space X' x 10 of features and labels.
Assumption 2.4 (Teacher assumption). We assume "teacher NN" h* generating the labels. A label flipping noise is then added with a noise level of E* P(XY)D (Y * hX))),, or equivalently
Y O h (X) Ber (E*)
The label noise is independent when Y Φ h² (X) is independent of the features X (in Section 4 Icads to stronger generalization results compared ones for arbitrary noise).
3

---

2.3 Learning problem: Classification with interpolators
We consider the problem of binary classification over training set ((x, yo y/ )
with N data points, sampled from the noisy joint distribution 'D described above. We always assume that sampled i..d., and therefore, with some abuse of notation, we use ( D (S) =
II D (x1, (x), For a hypothesis h X - {0, 1.. we define the risk, i.e, the generalization error w.r.t. D, as
Lo (h) a Px (h(X) YY
We also define the empirical risk, Le., the training error,
Ls (h)
Σ
11((xn) # 4y
N
==1
We say a hypothesis is an interpolator if Ls (h) O. In this paper, specifically interested in consistent datasets that can be perfectly fit. This is formalized in the following definition.
Definition 2.5 (Consistent datasets). A dataset S = [(x;, 9:) | is consistent if
Vi.j E [N] x; = y y
Motivated by modern NNs which often extremely overparameterized, the generalization behavior of interpolators, i.e., models that a consistent training set perfectly. Specifically, we consider Framework[] [ While this framework is general enough fit any minimal training error models, we shall be interested in the generalization of A (S) in cases where the training set is most likely consistent (Def. 2.5).
interested in
Framework 1 Learning interpolators
Input: A training set S.
Algorithm:
if S is consistent:
return an interpolator A (S) (such that Ls (h) = 0)
else:
return an arbitrary hypothesis (S) h (e.g., h(x) 0, Vx)
In Section we analyze the generalization of two learning rules that fall under this framework: (1) learning min-size NN interpolators and (2) sampling random NN interpolators. Our analysis reveals a tempered overfitting behavior in both cases.
Interpolating a noisy training set
Our main generalization results rely on key technical result, which shows how to memorize any consistent training set generated according to our noisy teacher model. We prove that memorizing "student" NN can be small enough to yield meaningful generalization bounds in the next sections.
We begin by noticing that under teacher model h* (Assumption 2.4). the labels of consistent dataset S (Def. 2.5) can be decomposed as
Vi [N] y. = h (x:) @ (xx)
(I)
where f 10, - (0, 1) indicates a label flip the 7th example, and can defined arbitrarily for x E S. Motivated by this observation, we now show upper bound for the dimensions of network interpolating S, by bounding the dimensions of an NN implementing an arbitrary "partial" function f defined on N points.

---

Theorem 3.1 (Memorizing the label flips), Let f: {0,1) 7 (0,1, be any function
Let N if (fO, 13)1 and Ni (1), There exists a depth-14 binary threshold network h: {0, 1j + {0, 13, with widths d, satisfying the following.
1. h is consistent with f. Le., for every x E (0, if f(x) E {0,1), then h(x) f(x).
N (N,) + poly(do). More precisely, 2. The total namber of weights in h is at most (1 + o(1) log
N
3/4
log
+
1og
-polylog N + O log N).
N2
N1
3. Every layer of h has width at most (log (Ni) ( )3/4 poly(do). More precisely,
Amax
(log
N₂ (N))
(N
3/4
polylog N Odd log N).
The main takeaway from Theorem 3.1 that label flips can be memorized with networks with number of parameters that is optimal in the leading order N Ls (h*) ), i.e., not far from the minimal Chormation-theorttii value. The proofs for this section are given in Appendix
Proof idea. Denote S S= f 1)). We employ established techniques from the pseudorandom- ness literature construct an efficient hitting set generator (HSG) for the class of all conjunctions of literals. The HSG definition implies that there exists a seed which the generator outputs truth table that agrees with f on S. The network computes any requested bit of that truth table.
Remark 3.2 (Dependence on do). In Appendix we show that the O (db log N) term is nearly tight, yet it can be relaxed when using some closely related NN architectures. For example, with a single additional layer of width 12 (vdg- log N) with ternary weights in the first layer, i.e., Q = {-11, 0, 1} instead of {0, the O (db log N) term of Theorem 3.1 can be improved to O 3/2 llog N do log N).
Next, with the bound on the dimensions of a NN implementing f. we can bound the dimensions of a min-size interpolating NN by bounding the dimensions of a NN implementing the XOR of and h*. Lemma 3.3 (XOR of two NNs). Let f1, b2 be two binary NNs with depths L1 S L2 and widths (1 (22), respectively. Then, there exists NN with depth Lxon A L2 + 2 and widths
(d ((2)
( (2) (2) L
d2 - -2,
dxoR
+ Li 11+1 +
such that for all inputs x E (0. 13 h (x) h1 (x) + hr (x).
Combining Theorem 3.1 and Lemma 3.3 results in the following corollary.
Corollary 3.4 (Memorizing consistent dataset), For any teacher he of depth L* and dimensions d' and any consistent truining set generated from it, there exists an interpolating NN h (i.e., Ls (h) 0) of depth L max {L* 14] + 2 and dimensions d, such that the number of weights is
w (d) S (d') + N H (Ls (h")) 2n (d') N3/4 33/4H H (Ls (11))3/4 polylog.N
+ (do (do (d') log N)
and the maximal width is
dmax S dinax + N3/4
H (Ls (h+))3/4 polylog (N) + O (do log (N))
Proof idea. We explicitly construct NN with the desired properties. We can choose subset of neurons to implement the teacher NN and another subset to implement the NN memorizing the label flips. Furthermore, we zero the weights between the two subsets. Two additional layers compute the XOR of the outputs, thus yielding the labels as in IT. This is illustrated Figure
When fxx = x, the interpretation that f is "undefined" on x, Le.. f is "partial" function. A variant of the pseudorandom generator (PRG) concept.
5

---

d
di
d2
dz
do
d1
d2
d3
dg
d1
d2
d3
d4
ds
XOR
(a) A teacher model ft".
(b) A NN hy memorizing the label flips w.r. h" in S.
(c) A wider student NN can interpolate the training set S, e.g., using an XOR construc- tion.
Interpolating a dataset. To memorize the training set, we use a subset of the parameters match those of the teacher and another subset memorize the noise (label flips). Then, we "merge" these subsets to interpolate the noisy training set. In our figure, (1) blue edges represent weights identical to the teacher's; (2) yellow edges memorize the noise; (3) red edges are O; and two additional layers implement the XOR between outputs, thus memorizing the training set.
Figure 2:
4 Tempered overfitting of min-size and random interpolators
In this section, we provide our main results on the overfitting behavior of interpolating NNs. We consider min-size NN interpolators and random NN interpolators. For both learning rules, prove tempered overfitting. Namely, we show that the test performance of the learned interpolators is not much worse than the Bayes optimal error.
First, for sake of readability, let us define the marginal peak probability of the distribution.
Definition 4.1 (Peak marginal probability). Danx - maxxex P(x,y)~ (X = x).
Our results in this section focus on cases where the number of training samples is N w (db log do) and N = (1/ /Dmaxx. In such regimes, the data consistency probability is high and our bounds are meaningful. Note that given the binarization of the data, N o (1/ Dmax)) implies exponential upper bound of N o (2do/2), achieved by the uniform distribution, i.e., when D 2 2-o Due to the exponential growth of the sample space w.r.t. the input dimension, we find this assumption to be reasonable. Also, N w (de log do) implies that input dimension cannot be arbitrarily large, but may still be non trivially small (see comparison previous work in Section 5).
4.1 Min-size interpolators
We consider min-size NN interpolators of fixed depth, i.e., networks with the smallest number of weights for a certain depth that interpolate a given training set. In realizable settings, achieving good generalization performance by restricting the number of parameters in the learned interpolating model is natural and well-understood approach. Indeed, in such cases, generalization follows directly from standard VC-dimension bounds 4 (55) However, when interpolating noisy data, the size the returned model increases with the number of samples (in order to memorize the noise: see e.g. Vardi al. (88)). ), making it challenging to guarantee generalization. In what follows, we prove that even when interpolating noisy data, min-size NNs exhibit good generalization performance.
Learning rule: Min-size NN interpolator. Given a consistent dataset and fixed depth min-size NN interpolator, or min-#weightt interpolator, is a binary threshold network h (see Def. 2. that achieves Es (h) 0 using minimal number of weights. Recall that w(d) = Et= dich-1 and define the minimal number of weights required to implement a given hypothesis h.
wL (h) A min w (d) s.t. E BTN
The learning rule is then defined as
Ag (S) E argmin, we (h) s.t. Ls (h) = =0
'N o [L/VDanae implies a rough bound on the consistency probability via the union bound. For example, when the marginal of X under D is uniform (Dmax 1/12'), and the inconsistency probability corresponds to the well-known birthday problem.

---

Theorem 4.2 (Tempered overfitting of min-size NN interpolators). Let D be a distribution induced by noisy teacher of depth L*, widths d',, r(d") neurons, and noise level of < <1/2 (Assumption 2.4). There exists > O such that the following holds. Let S DD be a training set such that N == (n ( H (E log (n (d")) + di log do) and N ol //////mmxx) Then, for any fixed depth L 2 max {L*, 14] + 2. the generalization enor of the min-size depth-L L NN interpolator satisfies the following.
Under arbitrary label noise,
Es (CD (AL (S)) < - 2- + (1). [S [Cp (Az (S)) -2s* (1-+*)
. Under independent label noise,
Here, o (1) indicates terms that become insignificant when the number of samples N is large. We illustrate these behaviors in Figure Moreover, we discuss these results and the proof idea in Section 4.3 after presenting the corresponding results for posterior sampling. The complete proof with detailed characterization of the o(1) terms is given in Appendix F.1
4.2 Random NN interpolators (posterior sampling)
87 and theoretical works have shown that, somewhat surprisingly, randomly sampled deep NNs that interpolate training set often generalize well. We now turn to analyzing such random interpolators under our teacher assumption and noisy labels (Assumption (2.4). As with min-size NN interpolators, our analysis here reveals tempered overfitting behavior.
Recent empirical
Prior distribution.
A distribution over parameters induces a prior distribution over hypotheses by
P (h) = Fo (ho h)
We focus on the prior induced by the uniform prior over the parameters of binary threshold networks. Specifically, for fixed depth L and dimensions d, we consider A ~ Uniform (@RTN (d)) In other words, to generate ~ P. each weight, bias, and neuron scalar the NN is sampled independently and uniformly from its respective domain.
Learning rule: Posterior sampling. For any training set S, denote the probability to sample an interpolating NN by ps & P (Cs (h) =). When ps > define the posterior distribution ps as
Ps (h) P (h) Ls (h) 0) P(h) 1 (Cs (h) = 0}
ps
When p==00
= 0, use an arbitrary Ps. Finally, the posterior sampling rule As (S) ~ Ps.
Remark 4.3 (Hypothesis expressivity). The following result requires that the student NN is large enough to interpolate any consistent S (see Corollary 3.4), thus, ps > 0 and Pg is defined in ②
Theorem 4.4 (Tempered overfitting of random NN interpolators). Let D be distribution induced by a noisy teacher of depth L*, widths d", s(d") neurons, and a noise level of < 1/2 (Assumption) 2.4). There exists constani >> O such that the following holds. Let S ~ DDN be training set such that
N w(n (d*)* log (n (d + dh log do) and N ol o(////Dmax) Then, for any student network
of depth L 2 max (L* 14) + 2 and widths d E N holding
== 1,..., - di 2 di + N3/4 (log NY + c. du log (N)
(3)
the generalization error of posterior sampling satisfies the following.
Under arbitrary label noise,
Es,A)(S) [LD (A) 5 51-2-H(6") (c) log (dmax + do)
Under independent label noise,
Es,Ay(8) CDD (Ag (5)) 25" (1-E")) 50 (v (n(d) logg (dmax + do)
N
7

---

The proof and a detailed description of the error terms are given in Appendix F2
Remarkably, note that the interpolating NN in the theorem might be highly overparameterizze. and that for such NNs good generalization is not guaranteed by standard generalization bounds [4 (5]. This theorem complements similar result by Buzaglo et al. 13 for the realizable setting.
4.3 Discussion
The overfitting behaviors described in this section are illustrated in Figure 1
Proof idea. We extend the information thhorreiicat generalization bounds from (58] to this paper's s setting in which label collisions in the datasets have non-zero probability. In particular, we bound the interpolator's s complexity from below by the mutual information between the model and the training set. Since the model is interpolating, we can further bound the mutual information by a quantity dependent on the population enror. From the other direction, we bound the model's complexity from above by (1) its size the min-size setting of Section 4.1 and (2) by the negative log interpolation
probability for the posterior sampling of Section 4.2 Together with Corollary 3.4 we obtain the
bounds above on the expected generalization error.
In Figure 2 we illustrated the construction of memorizing network used to bound the complexity of the min-size interpolator. the following Figure 3 we illustrate how the interpolation probability ps can be bounded to induce a meaningful generalization bound.
Figure 3: Interpolating dataset with an overparam- eterized student. We build on the construction from Figure that memorizes a dataset using a subset of the parameters (blue, yellow, and red edges). Then, redun- dant neurons (gray) can be effectively ignored by setting their neuron scaling parameters (r) to O, leaving the re- dundant weights (gray edges) unconstrained. Thus, the interpolation probability ps can be bounded by quantity exponentially decaying in the number of neurons n (d) rather than in the number of weights (d) w (N).
da
d
d2
d3
d4
ds
Following Remark 3.2
the assumption N = wi (dg log da) be relaxed in some related architec- tures. For example, with a single additional layer of width O (Vdo log N) and temnrry weights in the first layer Q!" = { {-1, 1], the requirement can be relaxed to N w (1g log do).
Remark 4.5 (Higher weight quantization). The bounds in the arbitrary noise setting can easily be extended to NNs with higher quantization levels. For example, letting Q such that O Q and (0, 1) S OW, under the appropriate assumptions, we get that
((S.A(S)) [CD (A (S)) & 1-QQ-H(")
which is meaningful bound for noise levels =* < E (Q) for some (Q) < 1/2 Tighter results would require utilizing the additional quantization levels to achieve smaller dimensions of the interpolating network, and are left to future work.
5 Related work
The benign overfitting phenomenon has been extensively studied in recent years. Previous works analyzed the conditions in which benign overfitting occurs in linear regression [34
Benign and tempered overfitting.
[T
5 65
67|
21 47 933 86 98 44 90
19
B 76
31.. kemel regression
5I
61
53
57
72
10
60,
g 50
99
6], and linear classification [8
66
64
76
52 85
92
25
Moreover, several works proved benign overfitting in classification using nonlinear NNs 30 46). All the aforementioned benign overfitting results require
28
29
15
49
94
95 62
high-dimensional settings, namely, the input dimension is larger than the number of training samples.
"Specifically, (Q) such that 1 ((((()))) 1/2.
8

---

Mallinar et al. [57] suggested the taxonomy of benign, tempered, and catastrophic overfitting, which we use in this work. They demonstrated empirically that nonlinear NNs in classification tasks exhibit tempered overfitting. As mentioned in the introduction, our theoretical results for the independent noise case closely resemble these empirical findings (see Figure I. Tempered overfitting in kernel ridge regression was theoretically studied in Mallinar et al. [57]. Zhou et al. [99]. Barzilai and Shamir [6]. In univariate ReLU NNs (namely, for input dimension 1), tempered overfitting was obtained for both classification [48] and regression [4]. Manoj and Srebro [58] proved tempered overfitting for learning rule returning short programs in some programming language. Finally, tempered overfitting
is well understood for the Sheearest-neihhor learning rule, where the asymptotic risk is roughly
twice the Bayes risk (23).
Circuit complexity. Theorem 3.1 (our NN for memorizing label flips) is in a similar spirit as several prior theorems in the area of circuit complexity. For example, Lupanov famously proved that every function f: {0, 1 + {0, }} can be computed by a circuit consisting of (1 + o(1)) 2 /do many AND/OR/NOT gates, where the AND/OR gates have fan-in two (55). Lupanov's bound, which is
tight 77, is analogous to Theorem 3.1 because a NN can be considered a type of circuit.
Even more relevant is line of work that analyzes the circuit complexity of an arbitrary partial function f: {0, 1]d0 - {0, 1, *) with a given domain size N and a given number of 1-inputs Ni. similar to the setup of Theorem 3.I See Jukna's 's textbook for an overview 445 Section 1.4.2]. We highlight the work of Chashkin, who showed that every such function can be computed by a circuit log
(of unbounded depth and bounded fan-in) with (1 + o(1))
+ ((dy) gates
log log
To the best of our knowledge, prior to our work, nothing analogous to Chashkin's theorem 17 was known regarding constant-depth threshold networks. It is conceivable that one could adapt Chashkin's construction [17 to the binary threshold network setting as method of proving Theorem 3.1 but our proof of Theorem 3.1 uses a different approach. Our proof relies on shallow threshold networks computing k-wise independent generators (36) and an error-reduction technique that was developed in the context of bounde derandomization (38). among other ingredients.
Memorization. Our construction shows how noisy data can be interpolated using small threshold NN with binary weights. essentially requires memorizing the noisy examples. The task of memorization, namely, finding smallest NN that allows for interpolation of arbitrary data points, has been extensively studied in recent decades. Memorization of N arbitrary points in general position in Rd with two-layer NN can be achieved using O (( 1) hidden neurons 7 81 12]. Memorizing arbitrary N points, even if they are not in general position, can be done using two-layer networks with
O(N) neurons [41 74 40 97 With lhyer-layer networks, O (VVN) neurons suffice, but the number of parameters is still linear in N 33 96
89
7 Using deeper networks allows for memorization
with sublinear number of parameters (68 88 For example, memorization with networks of depth
VN requires only Ö(VN) parameters 88 However, we note that in the aforementioned results, the number of quantization levels is not constant, namely, the number of bits in the representation of each weight depends on N (6) Moreover, even in the sublinear constructions of [68 (8), the number of bits required to represent the network is w(N). As a result, in this work cannot rely these constructions to obtain meaningful bounds.
Posterior sampling and guess and check. The generalization of random interpolating neural networks has previously been studied, both empirically and theoretically [87
63
34 20
13]
Theisen et al. (84) studied the generalization of interpolating random linear and random features classifiers. Valle-Perez al. (87), Mingard et al. (63) considered the Gaussian process approx- imation to random NNs which typically requires networks with infinite width. Buzaglo et al. B provided a method to obtain generalization results for quantized random NNs of general architectures - possibly deep and with finite width, under the assumption of narrow teacher model. variant of this approach was used to prove our generalization results of posterior sampling, with the XOR network (Lemma 3.3) used in the role of the teacher.
'ee note that in most papers, the required number of quantization levels is implicit in the constructions, and is not discussed explicitly.

---

Extensions, limitations, and future work
In this work, we focused on binary (fully connected) threshold networks depth L 2 16 (Section 2.1 with binary input features (Section 2.2b. for which we were able to derive nontrivial generalization bounds.
Our results can be extended with simple modifications to derive bounds in other settings. For instance, NNs with higher weight quantization (see Remark (4.)). or to ReLU networks (since any threshold network with binary weights can be computed by not-much- larger ReLU network with a constant quantization level). Unfortunately, without more sophisticated arguments these extensions result in looser generalization bounds. The "bottleneck" of our approach is the reliance on (nearly) tight bounds on the widths of interpolating NNs.
Extending the results to other architectures (e.g., CNNs or fully connected without neuron scaling) and other quantization schemes (e.g,, floating point representations) will mainly require utilizing their specific structure to derive tighter bounds on the complexity (e.g., number of weights or number of bits) needed to interpolate consistent datasets. Furthermore, our bounds require the depth of the networks to be at least 16, and the width to be (N")),, which might be deemed impractical for real datasets The key to alleviating these requirements is, again, obtaining tighter complexity results.
Our paper focused on consistent training sets (Def. 2.5 in order to allow perfect interpolation. Realistically, models do not always perfectly interpolate the training set, and therefore it is interesting to find generalization bounds for non non- interppollaaing models, depending on the training error. In addition, it is interesting relate the generalization the training loss, and not just the training accuracy. Such extensions will require either broadening our generalization results or deriving new ones.
Acknowledgments and Disclosure of Funding
We thank Alexander Chashkin for generously providing English-language expositions of some results from his work [17] as well as some results from Lupanov's 's work [56) (personal communi- cation). The research of DS was Funded by the European Union (ERC, A-B-C-Deep. 101039436). Views and opinions expressed are however those of the author only and do not necessarily re- flect those of the European Union the European Research Council Executive Agency (ERCEA). Neither the European Union nor the granting authority can be held responsible for them. DS also acknowledges the support of the Schmidt Career Advancement Chair in AI. GV is sup- ported by research grants from the Center for New Scientists at the Weizmann Institute of Sci- ence, and the Shimon and Golde Picker Weizmann Annual Grant. Part of this work was done as part of the NSF-Simons funded Collaboration on the Mathematics of Deep Learning. NS was partially supported by the NSF TRIPOD Institute on Data Economics Algorithms and Learning (IDEAL) and an NSF-IIS award.
References
[1] N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567-583, 1986. ISSN 0196-6774. doi: 10.101660196-67444699900444
[2] N. Alon, O. Goldreich, J. Hå stad, and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures Algorithmss, 3(3):289-304, 1992. ISSN 1042-9832. doi: 10. 10.1002//sa.324003000
[3] I.. Bartlett and M. Long. Failures of model-dependent generalization bounds for least-norm interpolation. The Journal of Machine Learning Research, 22(():9297-9311 2021. 2021.
[4] L. Bartlett, N. Harvey, C. Liaw, and A. Mchrabian. Nearly-tight ve-dimension and pseudodi- mension bounds for piccewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
"Oe can relax the width requirement by strengthening the depth requirement; Remark D.7
10

---

[5] P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30033-3007 2020.
[6] D. Barzilai and O. Shamir. Generalization in kemel regression under realistic assumptions. In Forty-first International Conference on Machine Learning. 2024.
[7] E. B. Baum. On the capabilities of multilayer perceptrons. Journal of complexity, 4(3):193-215, 1988.
[8] D. Beaglehole, M. Belkin, and Pandit. On the inconsistency of kernel ridgeless regression in fixed dimensions. SIAM Journal on Mathematics of Data Science, 5(4):854 872, 2023. doi: 10.1137/22M1499819
[9] P. W. Beame, S. A. Cook, and H. J. Hoover. Log depth circuits for division and related problems. SIAM Comput., 15(4):994-1003, 1986. ISSN 0097-5397. doi: 10.1137/0215070.
[10] M. Belkin, J. Hsu, and P. Mitra. Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[11] M. Belkin, D. Hsu, and J. Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4): 167-1180, 2020.
[12] S. Bubeck, R. Eldan, Y. T. Lee, and D. Mikulincer. Network size and size of the weights in memorization with two-layers neural networks. In Neural Information Processing Systems, 2020.
[13] G. Buzaglo, I. Harel, M. S. Nacson, A. Brutzkus, N. Srebro, and D. Soudry. How uniform random weights induce non-uniform bias: Typical interpolating neural networks generalize with narrow teachers. In International Conference on Machine Learning (ICML), 2024.
[14] Y. Cao, Q. Gu, and M. Belkin. Risk bounds for over-parameterized maximum margin clas- sification aub-gaussian mixtures. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[15] Y. Cao, Z. Chen, M. Belkin, and Q. Gu. Benign overfitting in two-layer convolutional neural networks. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
[16] A. K. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility, SIAM J. Comput., 13(2):423-439 1984. ISSN 0097-5397. doi: 10.1137/021000 13028.
[17] A. Chashkin. On the realization of partial boolean functions. In Proceedings of the 7th International Conference on Discrete Models in the Theory of Control Systems, pages 390-404, 2006. In Russian.
[18] N. S. Chatterji and M. Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129);1-30, 2021.
[19] N. S. Chatterji, P. M. Long, and P. Bartlett. The interplay between implicit bias and benign overfitting in two-layer linear networks. Journal of machine learning research, 23(263): 1-48, 2022.
[20] P. Chiang, R. Ni, D. Y. Miller, A. Bansal, J. Geiping, M. Goldblum, and T. Goldstein. Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent. In The Eleventh International Conference on Learning Representations, 2023.
[21] G. Chinot and M. Lerasle. On the robustness the minimum & interpolator. arXiv preprint arXiv:2003.05838, 2020.
[22] B. Chor and O. Goldreich. On the power of two-point based sampling. Complexity, 5(1): 96-106, 1989. ISSN 0885-064X. doi:

---

[23] T. Cover and P. Hart. Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1):21-27, 1967.
[24] M. Dietzfelbinger. Universal hashing and k-wise independent random variables via integer arithmetic without primes. In STACS 96 (Grenoble, 1996), volume 1046 of Lecture Notes in Comput. Sci., pages 569-580. Springer, Berlin, 1996.
[25] K. Donhauser, N. Ruggeri, S. Stojanovic, and F. Yang. Fast rates for noisy interpolation require rethinking the effect of inductive bias. In International Conference on Machine Learning (ICML), 2022.
[26] W. Eberly. Very fast parallel polynomial arithmetic. SIAM J. Comput., 18(5):955-976, 1989. ISSN 0097-5397. doi: 10.1 1111137221000
[27] G. Even, O. Goldreich, M. Luby, Nisan, and B. Veličković. Efficient approximation of product distributions. Random Structures & Algorithms, 13(1):1-16, 1998.
[28] S. Frei, N. S. Chatterji, and P. L. Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory (COLT), 2022.
[29] S. Frei, G. Vardi, P. Bartlett, and N. Srebro. Benign overfitting in linear classifiers and leaky relu networks from kkt conditions for margin maximization. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 3173-3228. PMLR, 12-15 Jul 2023.
[30] E. George, M. Murray, W. Swartworth, and D. Needell. Training shallow relu networks on noisy data using hinge loss: when do we overfit and benign? Advances in Neural Information Processing Systems, 36, 2024.
[31] N. Ghosh and M. Belkin. A universal trade-off between the model size, test loss, and training loss of linear predictors. SIAM Journal on Mathematics of Data Science, 5(4):977-1004, 2023.
[32] A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, and G. Turán. Threshold circuits of bounded depth. J. Comput. System Sci., 46(2): 1993, ISSN 0022-0000. doi: 10.1016/0022-000099)) 90001-D.
[33] S. Han, J. Pool, J. Tran, and W. Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
[34] T. Hastic, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high- nigh-dimensional ridgeless least squares interpolation. Annals of statistics, 50(2):949, 2022.
[35] Hatami and W. Hoza. Paradigms for unconditional pseudorandom generators. Foundations and Trends@ in Theoretical Computer Science, 16(1-2):1-210, 2024. ISSN 1551-305X. doi: 10.1561004000001099
[36] A. Healy and E. Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. In STACS 2006, volume 3884 of Lecture Notes in Comput. Sci., pages 672-683, Springer, Berlin, 2006. doi: 10.1007/1 16721421 55.
[37] T. Hofmeister, W. Hohberg, and S. Köhling. Some notes on threshold circuits, and multiplication in depth 4. Inform. Process. Lett., 39(4)2219-225, 1991. ISSN 0020-0190. doi: 1016/ 0020-0190(9) 19901331.
[38] W. M. Hoza and D. Zuckerman. Simple optimal hitting sets for small-success RL. SIAM J. Comput., 49() 1 820, 2020. ISSN 0097-5397. doi: 00.11377/9M12687007
[39] G.-B. Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE transactions on neural networks, 14(2):274-281, 2003.
[40] G.-B. Huang and H. A. Babri. Upper bounds on the number of hidden neurons in feedforward networks with arbitrary bounded nonlinear activation functions. IEFE transactions on neural networks, 9()::22422) 222922222222 1998.
12

---

[41] S.-C. Huang, Y.-F. Huang, et al. Bounds on the number of hidden neurons in multilayer perceptrons. IEEE transactions on neural networks, 2(1))47-55, 1991.
[42] I. Hubara, M. Courbariaux, D. Soudry, R. Yaniv,,,, and Y. Bengio. Binarized neural networks. Advances in neural information processing systems, 29, 2016.
[43] N. Joshi, G. Vardi, and N. Srebro. Noisy interpolation learning with shallow univariate reLU networks. In The Twelfth International Conference on Learning Representations, 2024.
[44] P. Ju, X. Lin, and J. Liu. Overfitting can be harmless for basis pursuit, but only to degree. Advances in Neural Information Processing Systems, 97677, 2020.
[45] S. Jukna. Boolean function complexity, volume 27 of Algorithms and Combinatorics. Springer, Heidelberg, 2012. ISBN 978-3-642-225077-7, doi: 10.10077997--3-44--446665 frontiers.
Advances and
[46] K. Karhadkar, E. George, M. Murray, G. Montúfar, and D. Needell. Benign overfitting in leaky relu networks with moderate input dimension. arXiv preprint arXiv:2403.06900 066003, 2024.
[47] F. Koehler, L. Zhou, D. J. Sutherland, and N. Srebro. Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting. In A. Beygelzimer, Y. Dauphin. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[48] G. Kornowski, G. Yehudai, and O. Shamir. From tempered benign overfitting in relu neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[49] Y. Kou, Z. Chen, Y. Chen, and Q. Gu. Benign overfitting for two-layer relu networks. arXiv preprint arXiv:2303. 04145, 2023.
[50] Lai, M. Xu, R. Chen, and Q Lin. Generalization ability of wide neural networks on R. arXiv preprint arXiv:2302.05993 2023.
[51] T. Liang and A. Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. Annals of Statistics, 48(3): 1329-1377,, 2020.
[52] T. Liang and B. Recht. Interpolating classifiers make few mistakes. Journal of Machine Learning Research, 24(20):1-27, 2023.
[53] T. Liang, A. Rakhlin, and X. Zhai. On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels. In Conference on Learning Theory (COLT), 2020.
[54] Z. Liu, J. Li, Shen, G. Huang, S. Yan, and C. Zhang. Learning efficient convolutional networks through network slimming. In Proceedings of the IEEE international conference on computer vision, pages 2736-2744, 2017.
[55] O. B. Lupanov. A method of circuit synthesis. Iavesitya VUZ, Radiofizika, 1, 1958. In Russian.
[56] O. B. Lupanov. On a certain approach to the synthesis of control systems the principle of local coding. Problemy Kibernetiki, 14:31-110, 1965. Russian.
[57] N. R. Mallinar, J. B. Simon, A. Abedsoltan, P. Pandit, M. Belkin, and P. Nakkiran. Benign, tempered, catastrophic: Toward refined taxonomy of overfitting. In Advances in Neural Information Processing Systems, 2022.
[58] N. S. Manoj and N. Srebro. Interpolation learning with minimum description length. arXiv preprint arXiv:2302.07723,, 2023.
[59] Y. Mansour, N. Nisan, and P. Tiwari. The computational complexity of universal hashing. Theoret. Comput. Sci., 107(1):111-133, 1993. ISSN 0304-3975. doi: 10.101600304-397500 90257-T.
[60] A. D. McRae, S. Karnik, M. Davenport, and V. K. Muthukumar. Harmless interpolation in regression and classification with structured features. In International Conference on Artificial Intelligence and Statistics, pages 5853-5875. PMLR, 2022.
13

---

[61] S. Mei and A. Montanari. The generalization enror of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 2019.
[62] X. Meng, D. Zou, and Y. Cao. Benign overfitting in two-layer relu convolutional neural networks for xor data. arXiv preprint arXiv:2310.01995, 2023.
[63] C. Mingard, G. Valle-Pérez, J. Skalse, and A. A. Louis. Is sgd bayesian sampler? well, almost. The Journal of Machine Learning Research, 22(1 235773357,33 2021.
[64] A. Montanari, F. Ruan, Y. Sohn, and J. Yan. The generalization error of max-margin lin- ear classifiers: High-dimension arXiv:1911.01544, 2020.
asymptotics in the overparametrized regime. Preprint,
[65] V. Muthukumar, K. Vodrahalli, V. Subramanian, and A. Sahai. Harmless interpolation noisy data in regression. JEEE Journal on Selected Areas in Information Theory, 2020.
[66] V. Muthukumar, A. Narang, V. Subramanian, M. Belkin, D. Hsu, and A. Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? Journal of Machine Learning Research, 22(222):1-69 2021.
[67] J. Negrea, G. K. Dziugaite, and D. Roy. In defense of uniform convergence: Generalization via derandomization with an application interpolating predictors. In International Conference on Machine Learning, pages 7263-7272, 2020.
[68] S. Park, J. Lee, C. Yun, and J. Shin. Provable memorization via deep neural networks using sub-linear parameters. In Conference on Learning Theory, pages 3627-3661. PMLR, 2021.
[69] N. Pippenger. The complexity of computations by networks. IBM J. Res. Develop.. 31(2): 235 235-243, 243, 1987. ISSN 0018-8646. doi: 10. (0.1147/rd3322.0235
[70] N. Rahaman, A. Baratin, D. Arpit, F. Draxler, M. Lin, F. Hamprecht, Y. Bengio, and A. Courville. On the spectral bias neural networks. In International conference on machine learning, pages 1001-5310. PMLR, 2019.
[71] S. Rajput, Sreenivasan, Papailiopoulos, and amin karbasi. An exponential improvement on the memorization capacity of deep threshold networks. In A. Beygelzimer, Y. Dauphin, Liang, and W. Vaughan, editors, Advances Neural Information Processing Systems, 2021.
[72] A. Rakhlin and X. Zhai. Consistency of interpolation with laplace kernels is a high-dimensional phenomenon. In Conference on Learning Theory, pages 2595-2623. PMLR, 2019.
[73] J. H. Reif and S. R. Tate. On threshold circuits and polynomial computation. SIAM J. Comput., (1(5):8669088 1992. ISSN 0097-5397. doi: 10.1 10.1137/022105..
[74] M. A. Sartori and Antsaklis. A simple method to derive bounds on the size and to train multilayer neural networks. IEEE transactions on neural networks, 2(4):467-471, 1991.
[75] S. Shalev-Shwartz and Ben-David. Understanding machine learning: From theory to algorithmss Cambridge university press, 2014.
[76] O. Shamir. The implicit bias of benign overfitting. In Conference on Learning Theory, pages 448-478. PMLR, 2022.
[77] C. F. Shannon. The synthesis of two-terminal switching circuits. Bell System Tech. J., 28:59-98. 1949. ISSN 0005-8580. doi: 10. 1002/j. 1338-7305.19499 1h...44..44..
[78] K.-Y. Siu and J. Bruck. On the power of threshold circuits with small weights. SIAM J. Discrete Math., (0:42-43355 1991. ISSN 0895-4801. doi: 10. 13/0447//
[79] K.-Y. Siu and V. P. Roychowdhury. On optimal depth threshold circuits for multiplication and related problems. SIAM J. Discrete Math., 7(2):284 292,, 1994. ISSN 0895-4801. doi: 10.1 101117770099544001222889999
14

---

[80] K.-Y. Siu, J. Bruck, T. Kailath, and T. Hofmeister. Depth efficient neural networks for division and related problems. IEEE Trans. Inform. Theory, 39(3):946-956 1993. ISSN 0018-9448. doi: 10.1 109/18091222 8.26601..
[81] D. Soudry and E. Hoffer. Exponentially vanishing sub-optimal local minima in multilayer neural networks. arXiv preprint arXiv:1702.05777 2017.
[82] P. Strata and R. Harvey. Dale's principle. Brain Research Bulletin, 50(5):349-355) 1999. ISSN 0361-9230. doi: https:/dd..oo////ooooo6666111120 sci
BRRLhttps://
[83] D. Teney, A. M. Nicolicioiu, V. Hartmann, and E. Abbasnejad. Neural redshift: Random networks are not random functions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4786 4766, 2024.
[84] R. Theisen, J. Klusowski, and M. Mahoney. Good classifiers abundant in the interpolating regime, In International Conference on Artificial Intelligence and Statistics, pages 3376-3384. PMLR, 2021.
[85] C. Thrampoulidis, S. Oymak, and M. Soltanolkotabi. Theoretical insights into multiclass classification: A high-dimensional asymptotic view. Advances in Neural Information Processing Systems, 33:8907-8922 2020.
[86] A. Tsigler and P. L. Bartlett. Benign overfitting in ridge regression. Journal of Machine Learning Research, 24(123):1-76, 2023.
[87] G. Valle-Perez, C. Q. Camargo, and A. A. Louis. Deep learning generalizes because the parameter-function map is biased towards simple functions. In International Conference on Learning Representations, 2019.
[88] G. Vardi, G. Yehudai, and O. Shamir. On the optimal memorization power of ReLU neural networks. In International Conference on Learning Representations, 2022.
[89] R. Vershynin. Memory capacity of neural networks with threshold and relu activations. arXiv preprint arXiv:2001.06933 2020.
[90] G. Wang, K. Donhauser, and Yang. Tight bounds for minimum 11-norm interpolation of noisy data. In International Conference on Artificial Intelligence and Statistics (AISTATSS, 2022.
[91] K. Wang and C. Thrampoulidis. Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting, and regularization. SIAM Journal on Mathematics of Data Science, 4(1):260-28)) 2022.
[92] K. Wang, V. Muthukumar, and C. Thrampoulidis. Benign overfitting in multiclass classifica- tion: All roads lead to interpolation. In Advances in Neural Information Processing Systems (NeurlPS), 2021.
[93] D. Wu and Xu. On the optimal weighted &g regularization in overparameterized linear regression. Advances in Neural Information Processing Systems, 33:101 12111221101 10-11013,,,, 2020.
[94] X. Xu and Y. Gu. Benign overfitting of non-smooth neural networks beyond lazy training. In International Conference on Artificial Intelligence and Statistics, pages 11094-11117. PMLR, 2023.
[95] Z. Xu, Y. Wang, S. Frei, G. Vardi, and W. Hu. Benign overfitting and grokking in reLU networks for XOR cluster data. In The Twelfth International Conference on Learning Representations, 2024.
[96] C. Yun, S. Sra, and A. Jadbabaie. Small relu networks are powerful memorizers: tight analysis of memorization capacity. In Advances in Neural Information Processing Systems, pages 15558-155660 2019.
[97] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):077-155, 2021.
15

---

[98] L. Zhou, F. Koehler, P. Sur, D. J. Sutherland, and N. Srebro. A non-asymptotic moreau envelope theory for high-dimensional generalized linear models. In Advances Neural Information Processing Systems, 2022.
[99] L. Zhou, J. B. Simon, G. Vardi, and N. Srebro. An agnostic view on the cost of overfitting in (kernel) ridge regression. In The Twelfth International Conference on Learning Representations 2024.
16

---

A Preliminaries and Auxiliary Results
A.1 Preliminaries
Before moving to the proofs of the main results, we recall and introduce some notation that will be used throughout the supplementary material.
Notation. We denote a (possibly random) learning algorithm by A (S), and assume that it takes values in some hypothesis class H. We use to denote the joint distribution over a finite sample space X' x {0, 1 of the features and labels, V to denote the marginal distribution of the algorithm, and p denote the joint distribution of training set D and the algorithm A (S). Specifically, the training set is a random element
S (
(XN, YN)) ~N DM
where (X,, Y2) is reserved for the i-th example in S. That is (X,, Y.) is always a sample in S, whereas (X, Y) is used to denote a data point which is independent of S. We use dD (x. y). dv (h) and dp (s, h) = dp (f(21, y1)................... ...... (zN, yN)} h) to denote the corresponding probability mass functions. With some abuse notation, we use dD (z) for the probability mass function of the marginal of 'D over X'
dD (x) PxYY (X x)
and dp ((11, 31) h) for the marginal of the joint probability of single point from S and the output of the algorithm, i.e.,
dp (111, ( h) = (((.A(())> (X1 =
= y1, i, A h))
Similarly, use dp (æ1, h). dp (311 x1, etc., for the probability mass functions of the appropriate marginal and conditional distributions.
Interpolating algorithm. In order to simplify the analysis, we introduce a framework of interpolation learning related the one introduced in Framework [1]
Let (S) be learning rule satisfying Framework] and let be some arbitrary token distinct from any hypothesis the algorithm may produce. We define a modified learning rule A ( such that
If S is inconsistent then A (S) Otherwise, if S is consistent then A (S) = (S), so particular Ls (S)) = O.
Notice that since the A (S) A()) when S is consistent
E LD (A (S)) consistent S] = E CD (A()) consistent s]
and therefore we can find bounds for the generalization error of À (S) by analyzing (S). In
addition, when it can be inferred from context we use (S) to denote the min-size and posterior sampling interpolators (instead (S) or As(S), respectively).
For ease of exposition, throughout the appendix, we rephrase the assumptions made in Section namely, that N w (dh du) and N o L//xx)........ as follows.
Assumption A.1 (Bounded input dimension). do - do=o(vNN/ [V/llog
Assumption A.2 (Data distribution flatness). Dmax (1/N2).
"s most of the appendix deals with the modified learning rule, use Á for the original one and A (S) for the modified one.
17

---

A.2
Auxiliary results
We start by citing several standard results from information theory and lemmas from Manoj and which will be useful throughout our supplementary materials.
Srebro (58
Lemma A.3 (Chain rule of mutual information). For any random variables A1, A2 and B
I ((A (A,, A2): - = (A2; (A;
Lemma A.4. Let A and B be any two random variables with associated marginal distributions A pn, and joint PA,B Let 9A/B be any conditional distribution (i.e. such that for any b, QAIB (-,b) is normalized non-negative measure). Then:
dQAIB (A[B)
I [(A; B) 2 BABB-AAEE log
dp (A)
Lemma A.5. Let A1, A2, B be random variables where A1 and A2 are independent. Then
I [(AA, A2): (A1:
(A2; (A;;
Lemma A.6 (Lemma A.4 from Manoj and Srebro 58 ) For C and S 1 it holds that
1 1-2 1-2-H(0)-C S 2 H()) +C.
Lemma A.7. Let (0, 2 and
(t) - de (t)
et + (1 E)² 1+ 1)
Then, & is monotonically decreasing as a function of and convex in (0, oc).
Proof. Denote a A then
é (t) = 1 a*
o' (t) - In (a) =n)n 1+ 2a + at
a²
(1 a1+)
8" (t) (a). (n) (1 + a1 a' 2(1 a (a))
(1+
In) a. (1 +++ - 20 =In(a) a'. a
(1+at)3
(1+at)3
Notice that for any E (0, 1), - 1>> so for 1>
a' - 1>0
and σ" (t) > so the function is indeed convex, and - In (a) < 0 so ó is decreasing.
18

---

Corollary A.8. For all t 0 it holds that
(1) 2 Φ (1) ø (1) (t- 1) ( + (e)) (t 1)
Proof. Substituting 1,
(1) E 8)
= In ( -)
i - = In - (²=²) -
o' d(11 In (a)
(1 (1+a)²
(
(1 1)-
E (
= e (e) - (1- (1 - ln) -c)
= (In - -n (n (n
In 2 (1-
=)))
=8 E In (log (e) + 11 (6)) 2 log (e) + +Hf (s))
The inequality then holds due convexity.
Finally, for completeness, we derive the relationship between the generalization error with respect the noisy distribution LD (h), and the generalization error with respect the clean distribution LD. (h).
Lemma A.9. Let DD be a distribution as in Section 2.2 with independent noise with label flipping probability s* E (0) Let Do be the clean distribution, i.e., the distribution with label flipping probability If
LD = Poxx=Pxxx (bx))
and
(h) = P(XYYDD (X) Y) P(X)DD (h (X) # h² (X))
then
CD (h) -
LD. (h)
1 25*
Proof. By definition,
Lo (h) = P(x (h (X) *
= =P(xy)>D (1 (X) * Y 11" -/ -Y)))
+P(x,y)D (h (X)
( (h' (X) +Y= =))
Since we assume that the noise is independent,
LD (h) (1-+*) Y ( xY
D (h
h (X)
=(1
(h + ki" (x)))()))x)))))))))))))))))))))) (e)))+""P(x)))) (h (X) 11- (X))
(1 - =*) LD. (h) + + (1 (1- Lp, (h))
=- + (1 28a) LD. (h),
equivalently,
LD. (h) CD (h) -
2=*
Remark A.10. In particular, under the assumptions of the lemma, Lp (h) 2 (1 -*) is equivalent to LD. (h) = s*
19

---

B Data consistency
Before moving on generalization, we address some key properties of the training set's consistency.
Lemma B.1. For any distribution over the data D, P (inconsistent S) S 2 N Dmax
Proof. Using the union bound,
IP (inconsistent S) P Ei + [N] X; = x
PEi サ [ X; Xÿ)
P (X; X,) (~)
N
NN
(X2 (xx==X)= (
Σ
P P(X, = 2X) x)
(
ZEd'
N
D max P (X = =x)= === (N
1 5N max
Σ
D
Daaxx
2
2
DEA
Hence, under Assumption is asymptotically small.
A.2
we have P (inconsistent 5) = (1), i.e, the inconsistency probability
B.1 Independent label noise
We now focus the case of independent label noise, i.e., + h" (X) {X =x} any x E X. Recall the noise level
Ber (s*) for
E" = -x (Y + 1² (X)) = Ps +Vi (X1))
and we define the "effective" noise level a consistent training set
Ps (Y1 + ht (X1) consistent 5) & e
(4)
We relate En to E* in the following lemma. Lemma B.2. In the independent noise setting, it holds that
D max ( - ---1 S [ln2 (E" log (E*) + HEtH H (=*)) (NN -1) IP (consistent S)
and moreover, Enr E*
Proof. Conditioning on S being consistent (having no label "collisions"), all occurrences of x in S
must have the same label so
c+
Ps (Yi + h2 (X1) (X,,, Yi) appears & times in S, consistent S) e+ + (1 - E*)
Therefore,
Ps (Y1 # h² (X1) consistent S) er
Σ Ps (Y1 + h² (X1) (X), appears times in S, consistent S)
IP ((X,,Y) appears times in S consistent S)
g
(1 )+) ((X1, Y1) appears l times in S consistent S)
(5)
N
g+1
-P ((X(1,,)) Yi) appears & times in S consistent S)
g+l + (1 (I-
P (() appears k times in S consistent S) e*.
sums to
20

---

On the other hand, define
N
K ( [ X = = = X1}
1=1
then
Eg [K (S)
consistent S] +
Eg [I (X; X1}
consistent s]
1=
11 + (N Ps (X2 X1
consistent .)
Next,
P (X22 X1, consistent S) P (consistent 5)
F P(, X2) (consistent 5)
(X2 X1
consistent 5)
Since d'D (x) S mmax for all X, as the proof Lemma B.1
P (X1 X2) (cconsistent.) S)
D max
Es [K (S) consistent S] S 1+ (N 1)
S + (N-
P (consistent S)
Then, using Lemma A.7 get,
e*
g* + (1 - e1- (X1 appears & times in consistent S)
der (k)) (X, appears times in S consistent S)
= Es
Φ. (K (S))
consistent $
[enssnn Φe (Es [K (S)
consistent ST)
D Diax IP (consistent S)
[decreasing Φ..
1 + (N 1)
Corollary A.8 implies that
6n 2 de. (1+ (N-1)
D Dmax
P P(consistent. 8)
Dynx P (consistent S)
- + In2 (o" (E") + E (E*)) (N -1)
Combining the bounds we get
D Dmaxx P (cconsistent.S)
j - 5 Iln log (E*) + (s*)) (N 11)
21

---

C Generalization bounds
We present two generalization bounds for the population error of an interpolating algorithm in terms of the mutual information of it with the training set.
Remark C.I (High consistency probability). Throughout the appendix assume that the consistency satisfies Ps (consistent S) 2 While this assumption is not without loss of generality, it is a weaker version of Assumption A.2 and implied by it (asymptotically). As Assumption A.2 is assumed in all "downstream results" that this appendix aims to support, we find it is reasonable to assume here.
C.1 Arbitrary label noise
In this subsection, provide generalization bound for interpolating algorithms without any assumptions on the distribution of the noise Y < h (X) {x = æ), other than LD (h*) = e*.
Lemma C.2. For any interpolating learning algorithm A (S).
A
llo (1 - EsS,A()) [Cp (A))) consistent ST) S N Ps (consistent.S)
Proof. We rely on Lemma A.4
Specifically, shall use the following suggested conditional
distribution. For h # let
1 Zn
dq (s|h) I[c, (h) 03 dDN (s)
where
2n = Σ T(c (b) = 03 dDN (s)
Esl (Cs (h) = 0}
Pss (Cs (h) 0)
= (1 - LD (h))
For let
II finconsistent 8) &DD (s)
d' N
dq (s|+)
E. (inconsistent 5 dDN (s') = I
I (inconsistent $}
P (inconsistent S)
Clearly, h of * and dy (s]h) = then either dD (s) so dp (x, h) = 0 as well, or L. (h) + So. since h # *, can be interpolated and dp (s h) = O. That is, the proposed conditional distribution absolutely continuous w.r.t. the true conditional distribution. When h *, g the true conditional distribution given that / it is also absolutely continuous w.r.t it. That is, the proposed distribution is
I (inconsistent $} Ps (inconsistent 5)
I1C, (h) = 0)
dq (s h)
T(h DDN (8)
(h + x] aD (s).
(1 Lo (h))
From Lemma A.4
dq (SIAA)))) dDN (S)
AS;A Es.A(S)
log
EsSA((9)
log
Par (inconsistent ST) (S) [C (A(S) # *+)] (I-C)((())))
Linconsistent S)
I(A(S): +} and II (S) + +} are mutually exclusive so I (S)
2 Es,A(S) log
I (inconsistent 8)
[(AAS)=+* + log ( (I-S)(())))) [(A *+]
Sr (inconsistent S7)
The first term is when A(S) * * and positive when (S) = (and so always nog-negai.ve). Furthermore, whenever dp (S)) > and (SA * }} 1 hold together, they imply that
22

---

(A 0} = so we have
( 2 BS,A(S) log
(1 -1- (A T(A +(A +*)
= --Bs,A(S) IN log (1 - LD (A(())) **]]
Using Jensen's 's inequality,
-Es.A(s) [N log (1 LD (A(S)) +]]
A(5) log - (A)(5)) [[A + [ Ps, (A +)
2 Nog (1 ES,A(S)) LDp (A())) [[{A(S) & ++]]) Ps.A(S) (A & *)
-Nllog (1 (.S.A()) LD (A (5)) consistent S)) Ps (consistent S)
SO
AS;A 2 - Nloo (1 - Es.A(S) (CD (A (5)) consistent SI) Ps (consistent S)
Rearranging the inequality
I (S; A (S))
- log (1 Es.A(S) [ED (A (S)) consistent SI) <
N IPs (consistent S)
23

---

C.2
Independent Noise
Lemma C.3. Assuming independent noise, the generalization error of interpolating learning rules satisfies the following.
(S))(S) [CD (A))
consistent S] -2=" -1=(11 (1-=")
(1')=²) ([()))) (N - 1max
where C (N) A ((S.A(S))NN((((e))) - S))
N(1-P(inen P(inconsistent. S))
Proof. As in the proof of Lemma 4.2 in Manoj and Srebro 558 since S is sampled i.idd, we have
AS)A
((x,,)) N (I)
AB
N ( + N / (Y:: A (S) Xi)
(6)
Using properties of conditional mutual information,
T(Y;; A (S) X1) H (Yi X1) H (Yi A (5), .21)
(7)
For the first term in 7 employ the fact that for any E X, either Y1 X1 Ber (E*)
Y X1 = x ~ Ber (1 - =*) to get
(Yi X1) E (x [ (Yi X1 = X)] = E H (= = H (E*)
For the second term in
again employ the definition of conditional entropy,
dp (), dp (21,h)
(Y, AA()) X1) (s),
E E
dp ((z log
21EA NEAU(H)
dp ((F1, 1), dp (x h)
dp ((x1, 1), log
When * x, the marginal distribution of a training data point and a hypothesis is dp ((x, y) h) = dp (y xr, h) dp (ær, h) = I {y = ha (x)) dp (x, h)
and the inner sum becomes a sum over expressions of the form:
dp (p h (21)), dp (x1, h) dy (x1, h))
dp (I1, h) dp (2 h) 0.
dp ((11, (x1)) h) log
=0
Therefore, we have that,
H (Yn A())
dp ((1,,))) log (dp (d)(((1,)),:t)) dp ((x1,)),))) 1), log
dp ((21, 1), )
Σ
dp (x1,*)
dp (I11 *)
21ER
Employing conditional probabilities (notice that dp((=).0)++) we get,
dp(0) +))p(11)) = dp x1, x)),
dp(z1.e)
dp(21.*)
(Yi ((S), X1)
Σ (x +) [dp (0 I1, x) log (dp 21, x)) + dp (1 x1, x) (dp (1 x1, x)]]
= Σ dp (2 +) H (dp (0 x))+)) = dp(+)) Σ dp (#1 ()) (dp (0 x æ1,
ZIEX
FIEX
= IP (A E(S,A(())) H (dp (0 x))
inconsistent s) Ps (inconsistent S)

---

Overall, the right term in (6 is lower bounded by.
A X1) HI (Yi X1) H (Yi A(S), 2 H (s*) IP (inconsistent S)
For the left term, i.e., [X1; A (S)), we use the variational bound Lemma A.4 with the following suggested conditional distribution.
For h = choose dg (a1 () = dp (x1) (notice that Σz,ex dg (21 x) = Ex, dp (z1) 1.
Otherwise, if h + denote q-- = Ber (s), and
E Ps (Y1 + h (X1) consistent S)
E (())
PP X~D (A(5) (X) + h (X)) A()) #*|
gen
Note that fnr may differ from E*. We choose the following conditional distribution
dqz, (h (x1) @ h" (x1))
dg (21 h) Zn dgigo (h (x1) h (x1))
dp (x1)
In total, we choose,
1 dqe, (h (x1) ① h- (x1))
dg (11 h)
[h # x} dp (z1) + 11 *} dp (z1)
Zn dg: (x1) + ht (x1))
where Zn is the corresponding partition function.
Then, we use (A.4) and properties of logarithms and indicators to show that,
log (g (X]]AA
7 (X1; A (S)) 2 (SS)
dp (X1)
doa, (M(X) (X,) (x.))
ZA(S) dge (k(X))@h* (X13)
Es,A(S)
log
dp (X1)
dqe, (H1) ( (SA +x)+ =+]]
Eg,A(S)
log
ZA(S) dgego (h(X1) @ hi (Xi))
dqe, (h (X1) @ li* (Xi))
I[A(S)**) +1]+
= Es,A(S) log
ZA(S) dgeam (X1) @ ht (X1))
Es,A(S)
log
(A) x
=0
d4e, (h (X1) + h" (X1)) I{A(S) ++] Es,A(S) log AAS) dg:am (h (X1) + h+ (X1))
Using the law of total expectation, the above becomes,
= PAA + (s.AA()) log 1 dge, (h 2 h1 (Xi) dyeg (h (X1) @ hr (X1))
)
A +
ZA(S)
where we also use Jensen's inequality to show,
1 dgs, (h (X2) @ ht (Xx))
Es.A(S)
log
A $*
Z A dupp. (h (Xx) @ h" (X1))
dqs,, (h (X1) @ ht (X1)
)
=ES,A(S)
log
A(5)**
Ess.(S)) [log (ZA(s)) **
duEp (h (X1) le (X1))
dga, (h (X1) @ ht (X1)
2 E.S.A(9)
log
A(S)**
- log (Es,A(S) [ZA(S] A (S)
dgezm (h (X1) @ h (X1))
25

---

The partition function satisfies for all h + +.
Zn Σ dge, (h (x1) ht (x1))
dqe, (h h- (X))
dp (x1) ExaD
duen (h (x11 @ (x1))
dagg (h (x) @ 1o (X))
Ex
1 -- Evr PX-D (h (X) = ht* (X))
+ PXxD (1 (X) + h² (x))
1- Egen
gge
Taking the expectation w.r.t. (S, (S)) p. get
E ((S)A()))~
AA(S) (S) # +] Es,A(S) [P (A (S) (X) = h1 (X)) A(S) + ++
1 Enr
Egen
êtr ggnn
+
ES.A(S) [P (A M (X)) A(S) + =1
Combining the above, we have that,
log ( dqe, (XI + ha (X1))
dgggo (A())(X,) @ h (X1)) AA #*
((1;;((S)) 2 P (A +) Es.A(S)
Notice that
(AI (Xi) (A + x)) = (Y @ h² (Xi) {consistent S})
so (S)) (X1) hh (X,) (A( +} ~ Ber (Eu), and thus
T(x;; (S)) > (AA (S) # *) DKL. (1e (1 TP (inconsistent 5) DEL (gtulluep)
Putting this all together,
6 is lower bounded by,
I (S; (S)) 2 N(1 P (inconsistent S)) DEL (9E, (gEg)))))m) (H IP (inconsistent S)
Rearranging the inequality
I AS) - N (H*) (inconsistent S)) & C (N).
DKL (geml)
N (1 IP (inconsistent S))
Using Pinsker's inequality, we have,
S Egenl S / } DKL (gealluemm) S VC(N).
We proceed bound Es,a(s) [LD (A))) consistent SJ in terms of j Égeal. Notice that Es,A(s) [LD (A))) consistent S]
-Es,A(s)
(Ix.))-DAA (X) Y) consistent S]
Es.A(s)
((AA(S) Y ht (X h (X))
consistent s +
no label tlip
+ Es.A(S)
((A(S) // (X)) P (Y + h² (x))
consistent s
label flip
=ss,A(S) (4)))))))))) h* (X)) e* consistent $)
=(1 -1-E8 (1-E")ES,AISS IP (S) h² (X)) consistent 8] +
+E*ES.A(S) [P (A h² (X)) consistent S
E-= + E- (1 - Egen)
26

---

Then, using the triangle inequality,
([S) (CD (A(S) consistent 5] 2e" (1 E*)
= =(1 - (1)) + E" (1 - Egen) - 25" (1 - En)l = [ Egen EgenE" + - -Egent" -2=" + 2=
Egenn 2 gene - + 2 |ggon (1 2²*) -E* (1-2e") (1 -2222) |ēgon E*1
S (1 - 2c*) geé Eul + fêu - E*1)
Combining with the result from Lemma
B.2 and Remark C.1
fe e'1 [In 2 (e" log (E*) + (c")) (N - D (consistent. S)
In (e" log (E*) + H (E*)) 2N - 1) maxx.
we conclude that
(s,)(s) [CD (A (5)) consistent S] - 2=* (1 =-)
$ (1-)=") (V) + lm (e" log (=*) + =" H (s ))} ( 1) Dmax)
Finally, we can the algebraic property that (1 -1-23 2 Il 2 (s* log (5*) + + (e))) s t. to get
Es.)(S) [CD (A())) consistent S] -2" (1 (1-E*)
2=*) v (N) (N 1) Dmax
We can now bound the expected generalization error without conditioning on the consistency of the training set.
Lemma C.4. It holds that,
Es, Es,A(S) [ED (A (8)) - 25- (1 --))
s [s,)(s) [CD (S)) consistent S] 2= (1 E*) Ps (inconsistent S)
Proof. Let X be arbitrary RV in [0, 1] and Y be binary RV. Then,
E X] F (Y) E X Y + P [XIY)
E [X] Y P (Y) IE X Y B|X Y] -X -
[X (
-(X))
E - = - - (-Y)
As result
ES,A()) (CD (A (S)) - Es.A(S) [LD (A (S)) consistent S]| (iicoonssittt S)
Then, the required inequality is obtained by simply using the triangle inequality on
[SSA(S) [CD (A (S))) 2s (1- (1==")]
27

---

D Memorizing the label flips (proofs for Section 3
In this section, we prove Theorem 3.1 We begin with an informal outline of the proof idea. Inspired by Manoj and Srebro's 's analysis 158) our proof of Theorem 3.1 is based on the concept of pseudorandom generator, defined below.
Definition D.1 (Pseudorandom generator), Let G: (o, 10,1)' + {0, 1 be function, let V be a class of functions V: {0. 13 - {0, 1). let D distribution over {0. 1] and let e >> O. We say that G is an e-pseudorandom generator (e-PRG) for V with respect to D if for every V E V. we have
|Py~D(V(>)) = 1) - uu
(V(G(u)) (uefo.i-(V(C((u 1) se
where u is sampled uniformly at random from {0,
To connect Definition D.1 to Theorem 3.1 let R = 2dh Let V be the class of all conjunctions of literals, such V(y) Y1 A V2 A Y4. Let X ([0, There is function V E V such that given the entire truth table of NN h, the function Vy verifies that h agrees with f on &. This function Vy is a conjunction of N1 many variables and (N - -N1) many negated variables.
Let a /i,N, and D Ber(a) Suppose G an c-PRG for V with respect to D, where < Py PyyDD(VVy = 1). Then P (oooo.)--V such that V)(((u") 1. Therefore, we let be a NN that computes the function
1) * 0, i.e., there exists some u² E 10,
h(x) G(u*) xx
(8)
then h agrees with f on X. In the equation above, G(u")x ) denotes the x-th bit of G(u"), thinking of X as number from R represented by its binary expansion.
There is a large body of well-established techniques for constructing PRGs. (See, for example, Hatami and Hoza's 's recent survey (35) Therefore, constructing suitable PRG might seem like promising approach to proving Theorem 3.1 However, this approach is flawed. The issue concerns the seed length (r). According the plan outlined above, the seed u* is effectively hard-coded into the neural network h, which means that, realistically, the number of weights in h will be at least r. Meanwhile, for the plan above to make sense, our PRG's error parameter (e) must satisfy
P PywD(Vy (y)) 1) = 2- H(o).N x 2 (x1)
Comparing
9 Theorem 3.1
that would need PRG with seed length
(1 o log(1/c).
But this is too much ask. There is real reason to expect such PRG to exist, even if we ignore explicitness considerations. Indeed, in some cases, it is provably impossible to achieve a seed length
smaller than (2 o(1)) log(1/e) [2]
To circumvent this issue, we will work with a more flexible variant of the PRG concept called a hitting set generator (HSG).
Definition D.2 (Hitting set generator). Let G: (0,1)" + {0, 1 a function, let be a class of functions V: {0, 13 + (0, 1), let D be distribution over {0, 1) and let >> 0. We say that is an e-hitting set generator (e-HS)) for V with respect to D if for every V e such that PV~D(V (y)= 1) e, there exists u {0, 1)" such that V(G(("))
1.
Definition i.2 weaker than Definition D.I. but an HSG is sufficient for our purposes. Crucially, one can show nonconstructively that for every V. D, and e, there exists an HSG with seed length
log(1 /e) + log log \> + O(1),
whereas the nonconstructive PRG seed length is 2 log(1/ /e) + To prove Theorem 3.1
we will
construct an explicit HSG for conjunctions of literals with respect to Ber(a) with a seed length of (1 + o(1) log(1/e) + polylog
R. We will ensure that our HSG is "explicit enough" to enable computing the function h defined by (8) using a constant-depth NN with approximately many weights.
Our HSG construction uses established techniques from the pseudorandomness literature. In brief, we use k--wise independence to construct an initial HSG with a poor dependence on e, and then we apply an error reduction technique due to Hoza and Zuckerman (38). Details follow.
28

---

D.1 Preprocessing the input to reduce the dimension
Before applying an HSG as outlined above, the first step of the proof of Theorem is actually
preprocessing step that reduces the dimension to approximately 2 log N. This step is not completely essential, but helps to improve the dependence on dg in Theorem 3.1 The preprocessing step based on standard trick, namely, we treat the input as a vector in E2 and apply a random matrix, where F2 denotes the field with two elements. That is:
Definition D.3 (Fn--inear and F2-affine functions). A function C: (0. + {0, 1] is Ez-linear if has the form
C(x) Wx,
where W E {0, 1] and the arithmetic is mod 2. More generally, say that C' is F2-affine if it has the form
C(x) Wx b,
where We E (0,1) b (0, 13 and the arithmetic is mod 2.
The following fact is standard; we include the proof only for completeness.
Lemma D.4 (Preprocessing to reduce the dimension). Let do let & (0,1] and let N [.) There exists an Fz-linear fanction Co: {0, 1] + {0, 12aloo N1 that injective on &.
Proof. Pick W E {0, 1]2[log xix uniformly random and let Co(x) Wx. For each pair of distinct points x, x' X, we have
P(Wx= = Wx') P(W x') 0) = 2 N1 < 1/N2.
Therefore, by the union bound over all pairs x, x', there a nonzero chance that Co is injective on &. Therefore, there is some fixing of W such that Co is injective on X.
We will choose Co to be injective on the domain of f. That way, after applying Co to the input, our remaining task is to compute some other partial function f': {0, 1 1]2[log N1 - {0, 1, +), namely, the function f' such that I' Co = This function f' has the same domain size (N), and it takes the value on the same number of points (N1), so the net effect that we have decreased the dimension from do down to 2 flog N7. This same technique appears in the circuit complexity literature, along with more sophisticated variants. For example, see Jukna's 's textbook [45, Section 1.4.2).
To apply Lemma D.4 in our setting, we rely on the well-known fact that Fi-linear functions, and more generally F2-affine functions, can be computed by depth-two binary threshold networks. More precisely, have the following.
Lemma D.5 (Binary threshold networks computing Ez-linear functions). IfC: 10, + {0, the parity function or its negation, then there exists depth-one binary threshold network Co: {0, 1) + (0, 11(422) and number b E IR. such that for every x E 1], we have
C(x) = 17 Cx()) +b,
where 1 denotes the all-ones vector. Moreover, every affine function C: {0, 1 - {0, 1)dd can be computed by depth-nwo binary threshold network with -dd (d+7 2) nodes in the hidden layer.
Proof. First, suppose C is the parity function. For each i E [d], let Φe:: 10, - {0, 1} be the function
(xi(x) =1
X, S i
/=1
and similarly define dz (0, - by
(2) = +
Σ x, 2 i.
29

---

Then
if PARITY (x) = [d/2] if PA (x) = 0,
[d/2] +
051(x) + x21(x)) + 053(x) + 023(x) +...
so we can take b = -dd22] Now, suppose C' is the negation of the parity function. This reduces to the case of the parity function because PARITY(x) PARITY(x: 1). Finally, the "moreover" statement follows because is E2-affine, then every output bit of either the parity function or the negated parity function applied to some subset of the inputs.
be generalized the of any symmetric function instead of PARITY. This technique is well-known in the circuit complexity literature; for example, see the work of Hajnal, Maass, Pudlák, Szegedy, and Turán 32
Lemma D.5
D.2 Threshold networks computing k-wise independent generators
One of the ingredients of our HSG will be a family of pairwise independent hash functions. We will use the following family, notable for its low computational complexity.
Lemma D.6 (Affine pairwise independent hash functions), For every a, E N, there is a family H. of hash functions hash {0, 1)a {0, with the following properties.
[ < 20(etr).
H pairwise independent. That is, for every two distinct w, w' E {0, 13,, if we pick hash E H uniformly random, then hash(w) w) and hash (os) are independent and uniformly distributed over {0,1} 13
Each function hash E F2-affine.
Proof. See the work of Mansour, Nisan, and Tiwari
59 Claim 2.2].
Remark D.7 (Alternative hash families). By Lemma D.5 each function hash E H can be computed by a depth-two binary threshold network with a wires (weights). There exist alternative pairwise independent hash function families with lower wire complexity. In particular, one could use hash functions based on integer arithmetic 224, which can be implemented with wire complexity (a + ++7 for any arbitrarily small constant
[73]. This would lead to slightly better width and wire complexity bounds in Theorem 3.1 each occurrence of 3/4 could be replaced with 2/3 + y. However, the downside of this approach is that the depth of the network would increase to very large constant depending on 7,.
Another ingredient of our HSG will be threshold network computing "k-wise uniform generator," defined below.
Definition D.8 (i-wise uniform generator). A k-wise uniform generator a function G: 10" (0. 1) such that if sample u {0, 13 uniformly random, then every k of the output coordinates Guu) are independent and uniform. In other words, G is a (-PRG for V with respect the uniform distribution, where V consists of all Boolean functions that only depend & bits.
Prior work has shown that k-wise uniform generators can be implemented by constant-depth threshold networks (36]. We will need to re-analyze construction to get sufficiently fine-grained bounds, In the remainder of this subsection, we will prove the following.
30

---

Lemma D.9 (Constant-depth k-wise uniform generator), Let k. R where R is power of two. There exists k-wise uniform generator G: {0. 1)" + {0, 13 where r O(k log R), such that for every RP F2-affine function hash: {0, 1) - (0. 1,, there exists a depth-5 binary threshold network C:: 10, 1]
1jattog log i
+ {0, 13 (0,1) polyloo It with widths d satisfying the following.
1. For every w E {0, 1) and every z E {0, 1loss it we have
G(hash( (w);: )) PARITY(C(W,
thinking of as number in {0, 10.1,...,AA R 1-11 1}.
2. The maximum width Imax is at most ak polylog R.
3. The total number of weights w (d) is at most (a + k) ak polylog R.
Remark D.10 (The role of the parity functions). One can combine Lemma D.9 with Lemma D.5 to obtain threshold networks computing the function (u, z) + G(u)2. In Lemma D.9 instead of describing a network that computes the function (u, z) + G(u),. we describe network C' satisfying
G(hash( (w) )))x PARITY (C w, z)). The only reason for this more complicated statement is that
leads to a slightly better depth complexity in Theorem 3.1
We reiterate that the proof of Lemma D.9 heavily relies on prior work. For the most part, this prior work studies Boolean circuit model that closely related to, but distinct from, the "binary threshold network" model in which we are interested. We introduce the circuit model next.
L circuits). An LT₃ circuit is defined just like a depth-L binary threshold network (Definition 2. except that we allow arbitrary integer weights (W()) E 7 xdi=1)) we allow arbitrary integer thresholds (b()) zd); and we do not allow any scaling (y(11) 1(). The size of the circuit is the sum of the absolute values of the weights, i.e.,
Definition D.11 (LT,,
1 di d ΣΣΣ
Remark D.12 (Parallel wires). In the context of circuit complexity, it is perhaps more natural to stipulate that the weights are always {+1]: there can be any number of parallel wires between two nodes, including zero; and the size of the circuit is the total number of wires. This is completely equivalent to Definition D.11
The proof of Lemma D.9 relies on circuits performing arithmetic. A long line of research investigated
the depth complexity of (iterated) integer multiplication [16
9
69
78
37
32
80 79. culminating
in the following result by Siu and Roychowdhury 79
Theorem D.13 (Iterated multiplication in depth four 79 For every n E N, there exists an LT4
circuit of size (nly(n) that computes the product of n given n-bit integers.
By a standard trick (26). Theorem implies circuits of the same complexity that compute the iterated product of polynomials over F2. We include proof sketch for completeness.
Corollary D.14 (Iterated multiplication of polynomials over F2). For every n E N, there exists an I.T circuit of size poly(n) that computes the product of given polynomials in F2(2)) each of which has degree less than n and is represented by an n-bit vector of coefficients.
Proof sketch. Think of the given polynomials as polynomials over E, say qı (2)....., (2). If we evaluate one of these polynomials on power of two, say 9: (2*). and then write the output in binary, the resulting string consists of the coefficients of qi, with - 1 zeroes inserted between every two bits. Therefore, by using the poly(ns) -ize circuit of Theorem D.13 (with some of its inputs fixed to zeroes), we can compute the product q1 (2*) -22(2)) gn Every coefficient of q is a nonnegative integer bounded by n²" so if we choose s = [n log ni ] then the binary expansion of gy2*) ) is the concatenation of all of the binary expansions of the coefficients of q. To reduce mod 2, we simply discard all but the lowest-order bit of each of those coefficients. D
q (2*), where 4 = 91 42 qn-
31

---

At this point, we are ready to construct circuit that computes k-wise uniform generator. The construction is based on the work of Healy and Viola [6].
Lemma D.15 (A k-wise uniform generator in the LT,, model). Let k, R where R is a power of two. There exists k-wise uniform generator G: {0, (0, 10,1)R, Fz-linear function Co: {0, 13 + {0, 1jollog Rl, and an LTa circuit C₁: {0, 10 R) - {0, 13 10 R) with the following properties.
The seed length is O log R).
For every seed u 10, and every z {0, 1) it we have
G(u); = PARITY (u, Co(2)))
thinking of as a number in (0.1...., R - 1}.
The circuil C₁ has size k polylog
Proof: If 2 R. the lemma is trivial, assume is < R. We use the following standard example of k-wisee independent generator [2 Let n log R, let Exx) E F2[2]] be an irreducible polynomial of degree and let 2" be the finite field consisting of all polynomials in F2(1r modulo E(x). The
seed of the generator is interpreted as a list of field elements: u (po. Pl..... Pk-1) E F Each index z {0, 1, .............................. ......... R. 1} can be interpreted as field element z F2.. The output of the generator is given by
G(u), the lowest order bit of po z + P1 z² + + Pk-1
where the arithmetic takes place in F2..
To study the circuit complexity of this generator, let us first focus on a single term p; z'. Since we thinking of z as field element E Fz",
also think of it polynomial z(x) E F2[2] of degree less than n. Write z(x) = ΣI= 2j 2 We compute the power z' by a "repeated squaring" approach. Write Emem 2tm, where C (0.1,..., [log i.
Then
2
(x(x) =<=)==(==x)) (x(
II
Σ Z3
-P(
II
Zz x/22
MEM M
MEM j=0
since working in characteristic two. For each M and each < n, let em.((z) 20.2" mod E(w), a polynomial of degree less than n. That way,
n-1
pr(x) z(x)² = p((x) II
(2)((2) (mod E(x)).
(10)
mEM j=0
The function Co(z) computes Ef=0 Zj Em.j for every m E {0, 1,.,, [log kJ}. This function is Ez-linear, because for each m E {0, 1, log k]} and each s < n, the s-th bit of ΣØ=0 given by
Cm.
Zj.
j.em.j.
where Em.j.e denotes the s-th coefficient of the polynomial emj-
Next, the circuit C₁ applies is copies of the iterated multiplication eircuit from Corollary D.14 in parallel, to compute the polynomial on the right-hand side of (TO) for each < i < k. Each iterated multiplication circuit has size polylog R. altogether, C1 has size polylog R.
At this point, we have computed polynomials To: .i. Pk-1 E Fz [r]. each of degree O(n log k). such that rx(x)) p;()) 2(r)f (mod E(x)). Next, we need to sum these terms up, reduce mod F(x), and output the lowest-order bit. For each j < On log k), let riş be the x coefficient of r;
Our circuit needs output the lowest-order bit of
O(n loggog))
Ti mod E(x)
Tij 60.
1=0
32

---

Now, we are working over characteristic two, so Σ means bitwise XOR. In other words, the output given by
Taj.
i.e. it is the parity function applied to some subset of the output bits of C1. To complete the proof, modify C1 by deleting the unused output gates.
We have almost completed the proof of Lemma D.9 The last step is to bridge the gap between LT circuits and binary threshold networks. We do so via the following lemma.
Lemma D.16 (Simulating LT,, r. circuits using binary threshold networks). Let L 2 1 be constant. Let Co: (0, (0,1)d {0, 10, be an Rz-affine function,, and let C1 {0, 1]: - {0, 1] da be an LTT circuit of size Then the composition C₁ o Co can be computed by a depth- + 1) binary threshold network with widths d satisfying the following.
1. The maximum width Lmax is at most S (do + 2).
2. The total number of weights w (d) is at most OSS + Sd.))
Proof. Let us define the cost of a layer in an LT,, circuit to be the sum of the absolute values of the weights that layer, so the size of the circuit the sum of the costs. Lemmal D.5 immpiess that C Co = Cj C-. where C is depth-one binary threshold network and Cj is an LT,, r. circuit in which the first layer has cost at most S (do + 2) and all subsequent layers have cost most S.
To complete the proof, let us show by induction on that in general, if C depth-one binary threshold network and C is an L circuit in which the layers have costs S1, S...... SL. then Cf o C can be computed by depth- + 1) binary threshold network which the layers after the input layer have widths S1, S2....... Sr.- Let us write Cj C3 o C2. where C33 is the last layer of C₁. By induction, C2 C. can be computed by a depth-L binary threshold network C' in which the layers after the input layer have widths S1 S2,.... S 1. Now let us modify C3 and C so that every wire in C3 has weight either or If wire in C3 an integer weight w E {0, 1}. then we make |w| many copies of the appropriate output gate of C. negate them if < O, and then split the wire into |wl many wires, each with weight +1. This process has no effect on the cost C3. The process could potentially increase the width of the output layer of C, but its width will not exceed St, the cost of C3. After this modification, we can simply think of C3 as one more layer in our binary threshold network.
Lemma D.9 follows immediately from Lemmas D.15 and D.16
33

---

D.3 A hitting set generator with a non-optimal dependence on
In this subsection, we will use the w-wise independent generators that we developed the previous subsection to construct our first HSG:
Lemma D.17 (Non-optimal HSG for conjunctions of literals). Let R be a power of two and let
a,& E (0, 1). Assume that 1/R S a S 1-1/R. Let V be the class functions V {0, 1) R {0, that can be expressed as a conjunction of literals. There exists a generator G: 10, - (0, 1] satisfying the following.
1. For every V E V, if Berr(a) (V()) = =) 2 2e, then P (0, (V(G(() 1) 2 e.
2. The seed length is r = Ollog(1/e) log" R).
3. For every Ez-affine function hash: 10 {0, the function C(w, Ghashh ()) can be computed by depth-8 binary threshold network with widths d such that the maximum width dmax at most a log(1/c) polylog R and the total number of weights w (d) is at most (log(1/c) a² + log (1/c) a) polylog R.
Remark D.18. The parameters of Lemma.D.17aaa not yet sufficient to prove Theorem 3.1 need the number of weights to be only (1+ o(1)) log(L/e). On the other hand, Item is stronger than what the HSG definition requires. This will enable us to improve the seed length of the generator later.
Remember,
The proof of Lemma D.17 is based on the work of Even, Goldreich, Luby, Nisan, and Veličković 27 In particular, we use the following lemma from their work.
Lemma D.19 (Implications k-wise independence (27)). Let XI,..., XR be independent {0,1)- valued random variables. Let X1...., Xx be k-wise independent {0, 1--vulued random variables such that X, is distributed identically to X; for every Then
[I((X = X2 -.. X 1) P(X = 82= - XR 1) S 2 Q(()
Proof of Lemma D.17 Let Q be the smallest positive integer such that Q 2 4R² and log log Q an integer. Let Φ: {0, 1,,.,,,..... - + {0, 1} be the function
<xx)= = 1 - x S a.a. Q.
We think of o as a function Φ: {0, lo - {0, 1} by representing in binary.
Let ē: {0, 10.11Bllg RRng Q + f0, 13ah be R copies of & applied to R disjoint input blocks. Let Go: {0, 1)" + {0, 1]_llgg @ be a k-wise independent generator for a suitable value k = (log((//e-
log R). Our generator G' is the composition @ Go-
Now let prove that G has the claimed properties. The seed length bound is clear. Now let us analyze the computational complexity of G. To compute G G(hash(w)) (w)). we begin by computing {0, 1..... log Q 1}. all in parallel, where C1 is the depth-5
Ci (w, z log Q + for every network from Lemma D.9 Since log Q is power of two, the binary expansions of the numbers simply consist of followed by all possible bitstrings of length log log Q. The maximum width of one of these layers is bounded by ak polylog
z log Q, z log Q + z log Q + 2,..., z log Q + log Q
log(1/c) polylog R, and the total number of weights among these layers is at most (a + k) ak polylog R = (a + log( (og()/))) a log(1/c) polylog R. Furthermore, the number of output bits log(1/e) polylog
Next, recall that to compute a single bit of the output of Go. we need to apply the parity function to the outputs of C₁. Therefore, to compute an output bit of our generator G, we need to apply an Fz-linear function followed by 6. Observe that á can be computed by depth-two "AC circuit," i.e., a circuit consisting of unbounded fan-in AND and OR gates applied to literals, in which the total number of gates is O(log Q) Ollog R). This can be viewed as special case of an LT2 circuit of size (log² R). Therefore, by Lemma D.16 the Ey-linear function followed by & can be computed by a depth-3 binary threshold network in which every layer has width at most log(1/e) polylog R and the total number of weights is at most log² (1/e) polylog R. This completes the analysis of the computational complexity of G.
34

---

Next, let us prove the correctness of G, i.e., let us prove Item | of Lemma D.17 Let V V and assume P. yy-Beaaa (V 1) 2 2e. Since V is conjunction of literals, we can write V(y) Vi(yi) V2(22) (y(RR) for some functions V1, V2...., VR: {0,1} 10.
We will analyze (o.1). (V(((u))
1) in two stages. First, we compare V V(o(Go(u))) to (()())), where y {0, 1R is uniform random. Then, in the second stage, we will compare (()())) to Vyy), where y Ber(a)
For the first stage, we are the situation Lemma D.19 because the It many (log Qit blocks of Go(u) are (k/ log Q)-wise independent. Therefore,
P Pueto.1) (V(((u) = 1) - o (V = =1) S exp (-2
log Q )) S 0.5c,
provided we choose suitable value O(log(//c) log R).
Now, for the second stage, observe that if we sample y {0, 1 1os uniformly at random, then [TP((()) = 1) a S पे. For each i, since 1/R S a S 1/R, we have
P Pe (Vi(d()) = 2 py yerBaa (Vi(y) 1) - 4R²
2
P (y))Be(a)((3((1)) = 1).
4R
Therefore,
1
R
Pyε (V(oly)) =)
1
(Py-Bar())a((()
4R
2 1.5c
by Bernoulli's inequality. Combining the bounds from the stages completes the proof.
L
D.4 Networks for computing functions that are constant vertain intervals
At this point, we have constructed an HSG for conjunctions literals with a non-optimal dependence on the threshold parameter (Lemma D.17 To improve the dependence e, we will use technique introduced by Hoza and Zuckerman [38] They introduced this "error-reduction" technique in the context of derandomizing general space-bounded algorithms, but it is simpler in context (conjunctions of literals).
The basic idea is as follows. Let V be conjunction of literals with a low acceptance probability: Py~Ber(a))* (V 1) We will split V up as product,
V = (y))) (0))
(1)) v(T (yT-))
where each (i) is a conjunction of literals with a considerably higher acceptance probability:
I Pyt)BBr(a)) (V (y ) 1) x Eo > E.
We choose (0) to be the conjunction of the first few literals in V: (1) is the conjunction of the next few literals; etc. To hit a single V(0, we can use our initial HSG with a relatively high threshold parameter (Eg). Then, use pairwise independent hash functions "recycle" the seed of our initial HSG from one (i) to the next.
To implement this technique, one of the ingredients we need is a network that figures out which block (i) contains particular given index z (0, 1...., 1}. In this subsection, we describe networks that handle that key ingredient. The constructions are elementary and straightforward.
First, review standard circuits for integer comparisons.
Lemma D.20 (DNFs for comparing integers). Let R be power of two, let 1 C R) be an interval, and let gr: {0, 1/ R - {0. 1} be the indicator function for In {0, 1......, 1} (identifying numbers with their binary expansions). Then gi be expressed DNF formula consisting of Olog" R) terms.
35

---

Proof. First, consider the case that I = [0,r) for some r E (1,2...., RR. If R, then the lemma trivial, so assume < R. Let S be the set of indices at which the binary expansion of r has a one. For each i E S, we introduce term that asserts that the input agrees with the binary expansion of prior to position i, and then has a zero in position The disjunction of these |S] many terms computes 91-
The case [6, R) for some é E {0, 1, ...... R 1} is symmetric. Finally, in the general case, we can assume that / is an intersection of an interval of the form [e. It) with an interval of the form [0, r). Therefore, 9ı can be expressed in the form AND; Oo & o AND R. where AND; / OR, denotes an AND / OR gate with fan-in k. To complete the proof, observe that every AND, o OR, formula can be re-expressed as an OR AND, formula.
Lemma D.21 (Computing function that is constant intervals). Let T and R be powers of two. Suppose the interval [0, R) has been partitioned into T subintervals, say [0, R) Io U..UTU Let g: {0, 1,..,.... R 1} - {0, 1 be function that is constant on each subinterval I Then for every R2-affine function Co: {0, do + {0, log R there depth-6 binary threshold network C:: {0, 1]do {0, 10,1)att 1aattag ft with widths d satisfying the following.
1. For every x E {0, 13,0, we have
C(x) = Co(()())),
2. The maximum width Lmax is at most O(T Ser-ooo'' log R + a + do log R).
3. The total number of weights w (d) is at most
aT + O(T log* R + db log R + do log" R + a log R).
We emphasize that the leading term in the weights bound is aT', with a coefficient of 1. This is crucial. It is also important that the weights bound has only a linear dependence on T, the number of intervals.
Proof. We begin by computing (x) and the negations of all of those bits. By Lemma D.5 we can compute these bits using a depth-two network where the hidden layer has width (do log R) and the output layer has width Ollog R).
Let - Cx() E {0, lo Rt and think of to compute the (log bbit binary expansion of the unique j. E (0, 7-....,T-111 such that z E I,,. To do so, for each position i E {0. 1...., log T 1}, let S. be the set of j E (0, I....... such that j has a in position i of its binary expansion. We have disjunction, over all j S, of the DNF computing 91, from Lemma D.20 We also compute all the negations of the bits of j., and we also copy z. Altogether, this is depth-two network where the hidden layer has width O(T- log T - log" R) = O(T log Rt) and the output layer has width O(log R)..
number z E {0, 10 R 1}. Our next goal is
1}
Our final goal is to compute g(z), which can be written in the form ((4)) since g constant each subinterval. We use a "brute-force DNF" to compute g'. First, for every j E 1.. T 1}. we have AND gate that checks whether j. = j. Then each output bit of g is disjunction of some of those AND gates. We also copy z. Altogether, this is a depth-two network where the hidden layer has width T + log R and the output layer has width log R.
36

---

D.5 Error reduction
In this subsection, we improve our HSG's dependence on e, as described in the previous subsection. The following theorem should be compared to Lemma D.17 As discussed previously, the proof is based on technique due to Hoza and Zuckerman [38].
Theorem D.22 (HSG with near-optimal dependence on e), Let R be power of two and let
(0, 1). Assume that 1/R S a S 1/R. Let V the class of functions V {0, R that can be expressed as conjunction of literals. There exists generator G: {0, 13" + {0, 1] satisfying the following.
1. G is an e-HSG for V with respect to Ber(a) That is, if Pyy-Ber(a)a (V(y) 1) > for every
V V, then there exists seed E 10, such that V(G(o)) =1
2. The seed length is r = log(l/e) log 3/4 (1/e) polylog R.
3. For every F2-affine function Co: { 1] + {0, 10 and every fixed seed a {0, the function h(x) G( Coix) Cott) can be computed by depth-14 binary threshold network with widths d such that the maximum width dmax at most
log 3/4 1og ((L/e) polylog R + O(do log R),
and the total number of weights w (d) is at most
log(1/e) + log (1/e) polylog R + O log R + do log? R).
Proof. First we will describe the construction of G; then we will verify its seed length and computa- tional complexity; and finally we will verify its correctness.
Construction. Let T be the smallest power of two such that 7 10/c/((1/c). Let
2/T
= 2R
and note that log(1/Eg) ((ogg//(L/e)) + log R). Let Go: (0,1)= be the generator of Lemma D.17 with eтror parameter cu, ie., for every V E V, if (V) y
1) 2 2cg, then Fu 1j (V (u) 1) 2 Let a be the smallest positive integer such that 2 >> R/eo- Let H.
be the family of F2-affine hash functions hash: {0, 13a + (0, 1) from Lemma D.6
A seed for our generator G consists of function hash H. inputs wo.... T-1 E {0, 1] and nonnegative integers ... (T), the output of the generator is given by
to S e < I Y R. Given this data o
(hash, w ..... w ,o,,..,
G(o) Go (hashhw')))) (w)) "))) e.1 & Go Go(hash(we )) & ... & Go(hash(w (w" T "ee"""""ee""ee"e"r""" --
In the equation above, Ya...b denotes the substring of consisting of the bits positions a, + 1,a 2, b, and & denotes concatenation.
Seed length and computational complexity. Since [H] < 20(atro), the description length of hash is (aa + ro). The description length of w....., w T- oT, and the description length of 8 (T is O(T R). By our choices of and Eg. we have
a S log(1/eo) + O(lo R) log(1/c)
+ O(log R).
T
Furthermore, by Lemma D.17
we have
= (log(1/eo) log² R).
Therefore, the overall seed length of our generator is
aT + O(ro T log R a) < log(1/e) + log log (1(() polylog R. To analyze the computational complexity, fix an arbitrary seed
(hash, w ..... w T-1 ,o. lT).
37

---

The numbers to. to...., er partition the interval [0, R) into subintervals, namely [0, R) = [fo. ( U
(2),42 Ulr--,, (.. ( Define g: {0, .., 1} - {0, 1] by the rule
g(z) w where j is such that [eg. lz+1).
Then g constant on each subinterval 1,,, ()+1), so we may apply Lemma D.21 to obtain
depth-6 binary threshold network C1: {0. 1) do - {0,1]a 1] R computing the function C(x)
(9(Co(x)), Co(x)). In this network, every layer has width at most
O log" R+ + do -log R) = log 3/4 (1/c) polylog R + O(do log R),
and the total number of weights is at most aT + O log" R + df log + do log" R + a log R)
I llo((1/e) + log log (1/c) polylog R Od log R + do logg R)-
Let Cx) and let = g(2). Our remaining goal is compute G(o),, which is equal to (oohsh(()) 2. To do so, we use the network guaranteed to exist by Lemma D.17 This network, which we call C22, has depth Every layer in this network has width at most
(og((1/r)) polylog R /log(1/c) polylog R. The total number of weights in this network is at most (log(1/<o) a² (1/co) a) polylog log (log)/((//)) polylog R.
Composing C2 with C1 completes the analysis of the computational complexity of our HSG.
Correctness. Finally, let us prove the correctness of our HSG. For convenience, for any n E N and any function V: f0, 1}" {0, 1}, write E(V) to denote the quantity P Py-Ber(a)" (V(y) 1).
Fix any V E V such that EV() > Since V is a conjunction of literals, we can write V in the form Vyy) Vo(yo) Vi (y1) VR- (YR-1)
for some functions Vo, VI...., VR-1: {0. 1} {0, 1}. For each S s bsbbk R 1, define Va... = Va Va+1 V/.
We inductively define numbers 0 = to < l S ... S lr as follows. Assume that we have already defined co...., l. Let 4++1 be the smallest integer in {4 I,..., 1} such that
E(
C/T
let l++1 R if such f--1 exists. Define V(1) Vi Observe that by R. because otherwise we would have
T-1
c <<V &
II B(V) - (2/TY"
i=0
a contradiction. Furthermore, [V())) > e//T/RR R = 2eg. because each literal in V is satisfied with probability least minfa, 11a a} 2 1/R. Therefore, if define
S. = {u E (0, and p; = | then the correctness of Go ensures that P; 2 E0.
(() 1-1) = 1}
Next, will show that there exist hash, w....., T- such that for every we have hash(w") S. To prove it, pick hash E H at random. For each i 1.. ---1 1} and each w E {0. 1]a. let X,, be the indicator random variable for the "good" event hash w) S,. Define X; Ewe(o, Niw- Then for every i, by pairwise independence, we have
BEX2)) = 2a Pt
and Var(X; 2a Pi (1-Pi) pi) S 2 Pr.
Therefore, by Chebyshev's inequality,
P(X: = 0) S 2a P:
2a 0 K0
R
Consequently, by the union bound over all i, there is a nonzero chance that Xo = X1 Xy-1 0, in which case there exist w" ,..., T- such that hash(w") S. for every i.
At this point, we have constructed our seed (hash, w ...., T- .o...., ..). By the construc- tion of G, we have (G(()) 1.
38

---

Theorem 3.1 readily follows from Theorem D.22 as we now explain.
Recall Theorem 3.1 Let f: (0, 13 + {0, 1, * any function Let N (f0) 1)) and
.i = (1)) There exists depth-14 -4 binary threshold network h: {0, 13 + (0, 1), with widths
d. satisfying the following.
1. à is consistent with f. ie., for every x E [0, if f(x) E {0, 10, then h(x) = f(x).
2. The total number of weights in is at most (1 + o(1) log (N,) + poly(do). More precisely,
N +
(1og5
N₂ )
(N
N 3/4
W
log
polylog N + O log N).
N₂
3. Every layer of h has width at most (log
)
poly(do). More precisely,
mmx
[log
(M)
3/1
polylog N O(do log N).
Proof. Let = 22[log N1 Let Co: (0, 13 - {0, 1] R be an F2-affine function that is injective
on X; such function is guaranteed exist by Lemma D.4 Define V: {0, 1) {0, by the rule
V(y) =1 > Vx E X, VCoix) f(x).
This function V is conjunction of N₁ variables and - Nı negated variables.
N1 E [J, then the theorem is trivial because we can take h a constant function. Assume, therefore, that 0 < N1 < N. Let N1/N, and note that I/R s s 1/R. Let a a1a =2 N- and note that
IP & (V(y) = =)
Let G: (0, 13 {0, 1), be the HSG from Theorem D.22 There exists seed a E {0, 1)" such that ((G()) 1. Our network h computes the function (xx) G(o))o(x)- Since V(G(a))
1
we must have hxx) = f(x for every x E X.
To bound the computational complexity, observe that log(1/e) = H(a) +1 s log (N,) Ollog N). Therefore, every layer of has width most
3/4
NV
log
polylog N + O(do log N);
N₂
and the total number of weights in is at most
+ log (M))
3/1
log
poolyoo N + O(th log N + do logg N).
Finally, we have N < 2d0, so the last term above can be simplified to Odt log N).
Remark D.23. In Theorem 3.1 the weights bound has an Odf log N) term. This term is close to optimal; see Appendix for further details.
When f(x) the interpretation that f "undefined" x. i.e., f is "partial" function.
39

---

D.6 XOR networks
In what follows, we denote the activation function (2) =
Lemma D.24 (XOR NN). The XOR function can be implemented with sengge---iden--ee -laee fully connected binary threshold network with input dimension 2 and сxoR parameters by
hXOR
31 22
-o -10 1).0 ((-)) o
=
(11) 1 1
21 )
+
(2)
0 ))
-
-1)
22
Proof.
We can simplify hxon
hxon
31
1 1 1
1 1
1
2 )) -1)
22
-1
1
22
(1 1
-21 22 +
#a +2 22
-1
= a (a (r) + +
- -2
22
- 1)
[TT (3)
+ 12
> 03 +1 + 22 < < >>> 1]
T
Ø1
*
0 0
}
+
I1
x {1)}
32
x2
21
7
and
31
+
1
}
1
22
32
XOR (2))
Remark D.25. Notice that the function Id : {0, 13 + {0. 1} defined as Id (0) 0 and Id (1) - can be implemented using any depth network with single input dimension and cıa parameters.
Following this remark, for simplicity we shall assume that h1 and h2 the following Lemma are of the same depth, as they can be elongated with O (L) additional parameters, which are negligible in the subsequent analysis.
40

---

Recall Lemma 3.3 Let h1, h2 be two binary networks with depths L1 S Lg and widths d()) dd respectively, Then, there exists network with depth LxOR - L2 + 2 and widths
dxoR (af + df
2 Li L
- 11,
+
such that for all inputs x E 10, h (x) - h1 (x) @ h2 (x).
The lemma above is given immediately by the lemma we state and prove next.
Lemma D.26 (XOR of Two NNs). Let h1, h2 X - {0, 1} be quantized fully connected binary
threshold networks with depths L' and widths d()) ddd) respectively. Let L > L' and dxoR-
Let BBTN (d: h1,h2) h2) be the subset of @BTN (d) such that for all e E @ (d: h1, h2), O has the following form:
For
w(I))
b (I)
W1
2 W1
bi
b (2)
b1
di
with arbitrary W1, bj.
For 1 = 22...,L's L';
w
W!
x
W
w(2)
W
E (0, 11,1xd
W
W
W
b =
b
(2)
E E di 11-1-11-
- 1,0,1
d 11at
b
71 =
(2)
E [0,11a
with arbitrary W1. WT, WP, WA. W.,b, For T/ k 1,2:
WXOR
W! W
W
E (0, 10.
W?
bi
by bi
XOR
E(-di-,..... -,,,, ...., d-1 - 13a .7
XOR
+1
0
for 1 L' 2:
Wid
W!
E (0, 1j
W,
W?
w
ld
-1,, d - 13at - (1 E (0, +1
bi bi
(-dd-_1,..,,
Then for all 0 E ITN (d: h2) ho hi @ h22
An illustration of this construction is given in Figure
41

---

Proof. We prove the claim by induction. For / = 1 we have do = =g6
=dp²)
and
=1
W
(0)
(x) + +bi)
1 di
w
b b
df
w
b
di -- -d
W1
b
W x + bj ((u)
h (2) (x)
0
W x (2)
(x)
df
di
Assume that for some / S L' we have
h ((111) (x)
hg
(1-1) (x)
h2 11-1) (x)
0 di of
Then,
ng
(1)
(x)
n O o
(iih
(x) + bi)
w
x
W
h
((-1) (x) h2 1)-1)
(1)
1 (2)
O
d xa
w(2)
Wi
(x)
+
b (2)
0
2)
W
W
W
b
W
(x) + b;
(x)
o
(x) + +b/²² (2) 11
(1-1)
h2
11) 1
hi (x)
(1.) (x)
is left to show that the claim holds for > L'. By the previous steps, h6
h2 (x)
O Odgy
Under the assumptions on W W44k, br.4 and 71/44, k = 1, 2 it holds that
(L'+2) (x) = ( h1 (x) + h2 (x) (x() hg
)
Od
Under the assumptions on layers 1 >> 1/ + 2,
h1 (x) ( h1 (x) h2 (x)
(xx)
Od.-1
In particular, assuming that d, = 1, ho (x) = h1 (x) @ ha (x).
42

---

Corollary D.27. Let h1, h2 be networks with depths L1. L2 and widths d dd²). Then 1ı @ h2 can be implemented with a network of depth max {Li L2] 2 and widths such that
w ( S w (d + w (d + 2dd n (40)+00
and
Lmax
d(i) + d
Following D.25 we assume shall assume that L1 L2 We know from D.26 that there exists network h with dimensions d = (d + , 2, such that h h1 @ h2. Therefore
Proof.
w (d) = (1))
(2) + 22
do +
11) + d(²t)
(1 + +2)) +011)
1=2
= c do= +
(2)
dg
+ Σ
+ Σ
10 d +0(1)
1=2
(1)
+
(2)
01
S
(1)
+
(2)
+
(2)
2
O())
max
max
(1))) +
(2)
(2)
(1) + 1 0(1)
w ) + (2)
+ 20(2)
1 (d(1)) + 011).
In addition, d dmaxx I d ((2) and n (d) = n (d)2)) + (d(2))
Recall Corollary 3.4 For any teacher h* of depth L and dimensions d' and any consistent
training set S generated from it, there exists an interpolating network (i.e., Ls (h) = 0) of depth L max (L* 14] + 2 and dimensions d. such that the number of edges is
w (d) < (d') + H (Cs (h")) + 2n ( /3/4 и (Cs (ht)) 3/4 polylog.V
+ +0 (do (do (d))) log N)
and the dimensions are
dmax S & + N3/4, H (Cs (h*)) (ht)) polylog + (do log (N))
Proof. We Corollary D.27 with h h² and h2 hs, the noise memorizing network from
Theorem 3.1 to get
w (d) < w
+ w (2s) + 2ds n (dd)+++ 0(1)
/
3/4 N )m
N
S w (d*) + log
+ (og
polylog N + O log N)
NN₂
N
3/4
+ 2n (d")
log
polylog N + O(dg log.v) + O(1).
Ni1
Using Stirling's s approximation
N N
Ni
log
= N
O (log (N)) = N (Cs (h*)) + (log (N))
N
43

---

Therefore
w (xdd) S w (d') + N. H (Ls (h*)) O (log (N)) + N3/4 H (Ls (h (//)) polylog N
+0 (db log N) + 2n (d') (N3/4 polylog N + O (do log N))
( (d") + N (Ls (h")) 2n (d') N3/4 H (Cs (h1)) polylog.V
+ 0 (do (do (d) log N) The bound of dmax is derived similarly.
44

---

E The label-fii--memoriztion network's dependence on the dimension
In Theorem 3.1 the wire bound has an O(1 log N) term. (Recall that do is the input dimension and N is the domain size.) this section, we discuss (a) approaches for improving this term and (b) a lower bound showing that it cannot be significantly improved.
E.1 Improving the O(dy log Term
The Odd log N) term in Theorem 3.1 can be improved by using the following fact.
Lemma E.1 (Using sign matrix for preprocessing). Let do E N. ler & S (0,1)dd, and let N = 1& There exists di O / do N) and there exists a matrix W E {=1]dixdo such that the function Co: {0, 1] + (0, 1]d defined by Co(x) = TI (Wx > 0} is injective on X.
Proof. Pick W E [=1]dixdo uniformly at random. We will show that there is a nonzero chance that Co is injective on X.
Let x, x' be any two distinct points in X. Consider a single row W. of W. Let E be the good event that
W. (x (0, 1).
Then Pr[A] (l) because are taking simple one-dimensional random walk of length at most do- Conditioned on E, there is an 12(1) chance that I [ 0} & 1 [ x > 0}, because we are taking two independent one-dimensional random walks starting from either 0 or at least one of which has nonzero length, and asking whether they land on the same side of 1/2. Therefore, unconditionally, Pr[[ (W; x x>>>>>> 0) * (WW x' > independence.
0}} 2 ((1/v/o)- Consequently, by
Pr[Co(x) Co(x')] < (1 (1- 1 221 /do)) 1/N2,
provided we choose suitable value di = Ol log N). By the union bound over all pairs x, x', it follows that there is nonzero chance that Cp is injective on &.
There are two approaches to using Lemma E.1 for the sake of improving the O log N) term in Theorem 3.1
One approach would be to start with trivial layer that copies the input x E {0, 13 as well as computing all the negations of the bits of x; then we have layer that applies the function Cu from Lemma (using negated variables to implement -1 weights); and then we continue with the network Theorem 3.I. The net effect that the depth has increased by two (so the network now has depth 16 instead of 14), and in the weights bound, the Odl log N) term has been slightly improved Odh + 2/ log N + do log3 N).
A second approach would be to change the model. If we permit ternary edge weights (i.c., weights in the set (-1, 0, 1)),. then the function Co of Lemma E. can be implemented as the very first layer of our network, and then we need ternary edge weights only in the first layer; the edge weights in all subsequent layers are binary. The benefit of this approach is in the weights bound, the O log N) term of
continue with the network of Theorem 3.1 Note that
Theorem 3.1 would be improved to ( 3/2 log N + do log N)-
45

---

E.2 A dg Lower Bound on the Number of Weights
We now show that the ( log N) term in Theorem 3.1 cannot improved something better than dg if we insist on using the "binary threshold network" model. The argument is elementary.
Proposition E.2 (dg wire lower bound). For every du E N, there exists a partial Boolean function f: {0, 11.00 7 {0,1, x)., defined on domain X of size do + 1, such that for every binary threshold
network h, if agrees with f everywhere in its domain and d is the widths of h, then w (d) 2 dg.
Proof. For each i E ,0,1,...,day let x(() be the vector consisting of i zeroes followed by do i ones. Let X {x(): :0000000 S i do}. and let
f(x) (ARITY(
if E & otherwise.
For the analysis, let h be fully connected binary threshold network that agrees with f on all points in &. Consider the layer immediately following the input layer. Each node y in this layer computes either monotone Boolean function or an anti-monotone Boolean function of the input variables. Therefore, there is at most one value i E {1,2.-. ..... .1....... do} such that (xx(t11) * 9xx()). On the other hand, for every i E {1, 2, ..... da). we have h (i) f h(x(*)), and hence there must be at least
one node in this layer such that ((x((-1)) * ()) Therefore, there are at least de many nodes
Thus, the first two layers of both have widths of at least do, demonstrating that h has at least df many weights.
46

---

Generalization results (Proofs for Section 4
Denote by H the set of functions representable as binary threshold networks with dimensions (given fixed depth L). We start by bounding the cardinality H in terms of the number of edges (d).
Lemma F.1. Let d be the dimensions of a binary threshold network with w - w (d) edges. Then there are 2 (VVlog(())) functions representable as networks with dimensions d.
Proof. We bound the number of function representable as binary threshold networks with dimensions d having w edges by suggesting a way to encode them, and then bounding the number of bits in the encoding. First, permute each layer so the neurons sorted by the bias and neuron scaling terms (bu, ru). As NNs are invariant to permutations, this does not change the function. Now, at each layer we encode the bias term based on one of two encodings.
If di < d:-1, then list each the bias terms as a number with (log (d--)) bits plus 2 bits for the scaling term for total of (di (log (di-1) + 2)) s O (v log (d:-1)). where the inequality is due di d
di 2 d--1. then we encode the bias and scaling terms by listing the number of times each pair (brs, 7hs (-..-1..... dr-1 }} { {-1, 0, appears in (bi, ?)) (recall that the neurons are or- dered according to these pairs). Each pair can appear at most d times and so requires (log (di)) bits to encode for total of O (6d;-1 log (d:) = O (d--1 log (di) s O (v didh-1 log (1)
By encoding each weight with a single bit, this means that for all layers, we can encode the weights, biases and scaling terms using did, + O (Vd,d, d/dd log (d)d--)) bits for total of
I.
Σ ded +0 (Vdrds log (drdk-1)) = +
Σ
Vdidh log (dedi-1)
1=1
1=1
S +0
V didi log
Σ dedi-1
L
I w +
/ djdh log (wc)
= w +
log (w)
didi-1
L
1=1
[Jensen] + 0 log (w) L
Σ
1
didh-1
0
log (w) .VL
Σ dids-1
T.
+ O (log (w) VLVW
+ O (log (w) Vw)
Corollary F22 Assuming that the depth T, is fixed and known, a binary threshold network of depth L with unknown number of weights w, can be encoded with O (Vw log (w)) bits.
Proof. After specifying the architecture d. from Lemma F.1 we require + O (Vw log (w)) bits. Therefore remains to bound the length the encoding of d. We first use O (log (w)) bits encode the number of weights, then, since d E [w]*, we only need O (log (w- = O (log (w)) additional bits for a total of w + O (Vw log (w)) + O (log (w)) = + O (v (Vw log (w)).
47

---

F1 Derivation of the min-size generalization bounds (Proofs for Section 4.1
Throughout this subsection, we use A (S) denote the min-size interpolating NN of depth L,
Ag (S).
Lemma F.3. Let 2 16 be fixed. Then
(( S w (d')
where
5 (N, do = n =nd") (e*)3/4 polylog (N + n (d') + do)
+ dB log N + don (d') (n (d' ) + N + do) 3/2 d
Proof.
Using Shannon's source coding theorem:
I AS: < H (A()) - [S)(
where [A()) denotes the number of bits in the encoding of (S). Following Corollary consistent S, A (S) a network with fixed depth and at most
3.4 for
(d') + N H (Cs (h")) + 2n ( (Cs (h*)) 3/4 polylog.V + (d (do + n (d")) log N)
weights and therefore, using the result from Corollary F2 and
w (d" S do + (d").
IA S w + O (v log (w)) = = (d') + N H (Cs (11*) + -0
-polylog (N (Gs (h")))"4-pooylog (N+n(d")+do)
+0 de--loge log + do (d') log (n (d (n
= (d) N H (Cs (h*)) 0 (N, (N, d"))
where we grouped all lower order terms in In case S is inconsistent, A = so |A = (1). Taking the expected value and using Jensen's inequality gives
E (() [|A (S)) (inconsistent S}] + E (S) I [consistent S}]
(1) + E I
{ (consistent S)
(d) + N (Cs (h + o (8 d'))
21
20
50(1) + (d") + N (Css +0 (6 (No.dodd")) d')) [Jensen] w (d') + N. H (Es O
=d(d") + N H (8) do)d"))
48

---

With this result, we are ready to derive the generalization results.
Recall Theorem 4.2, Consider a distribution induced by a noisy teacher model of depth L and widths d' (Assumption 2.4) with noise level of E* 1/2. Let S ~ D. be training set such that N o MV1/Da mmxx). Then, for any fixed depth L max {L* 14] the generalization error of the min-size depth-L L NN interpolator satisfies the following.
Under arbitrary label noise,
Es [LD (A (5)) < 2-H(e")) ( 8) (inconsistent S) + (CCin (N, do, d')
Under independent label noise,
Es [LD (A))) - 2e" (1 (1-e*)l
< (1 - 2=") / O(Cmia (N dg. 1)+F (inconsistent S) P(consistent S)
(N 11) D
P (inconsistent S)
3
where
Cmin (N, do d²) w (dd 8 do d')
with (N, do. d as defined in Lemma
F3
Remark F.4. The bound shown in Section 4.1 is found by bounding [iiinooniistett S) S 2 as in Lemma B.1 Then using the Taylor approximation with small N Dmxx
max
H(e*)
I 1 2 1- M(e3)
2
Dmax
= 1 2 -H((=") -(000((+
= 1 - 2-H(e") (1+ (N Dmax))
1 --H((e)) (N max).
Lemma B.1 used similarly to bound the error in the independent noise case. Assuming that
N n (d')² H (e*)² polylog (n (d")) + dg log do) when e* we can deduce that N
w (w (d") as well since
w (d) (n (d') + do)² < (max {n (d'))
Together with N (VI/D max we get the desired form of the bounds. Finally, note that when
g* = 0, the convergence rate of Ô (1/N) instead of Ô (1/VT) 1/VN), where Ô hides logarithmic terms arising as artifacts of our analysis, and dependence on other parameters such as the input dimension do-
Proof. Starting with the bound in the arbitrary noise setting, we combine C.2 with
T(S; A (SS)
log (1 Es [CD (A)) consistent S]) S N Ps (consistent S)
w (d" N H (E*) (8 do, d²))
N Ips (consistent 5)
(H (s*) O (Cmin (N, do, d'' d')))
Ps (consistent S)
Rearranging the above inequality and recalling Remark C.1 we have,
H(+*)
Eg CC (A (S)) consistent 8] < 1 - 2 Fg (commtntent OCCmmn (N.do
49

---

Then, using Lemma A.6 we get,
((=*)
Es C (A (S)) consistent S] S
2
Es (comeictent
+ O (Cmin (N, do.d")).
The bound is derived using the following observation. Since for RV X in [0, 1] and a binary RV Y have
E E = X P()
E P(- S E Y + P[-Y),
we conclude the proof as LD (A))) Es (CD (A)) consistent S] IP (inconsistent S) For the independent noise setting, we combine Lemma C,3 and Lemma F33 to get
Ess [Cp (S))
consistent S] - 2=* (1 - E*) --=))
$ - (1-22=) 0 (VC(V) + (N 1) D max
where
(NN) A N (E*) (inconsistent S))
N (1 - (inconsistent S))
w(d')-N-HE (O88 (M(e))))))(( S))
(11 (In-n(inonsisttent S))
P (inconsistent S)
(consistent S)
O (Cmin (N, da d))) + IP (inconsistent S)
(consistent S)
Finally, using the inequality from Lemma we have,
E (SS)(S)) (CD (S))) 2=t (1 1---" -e=]
$ [S.A(S) [LD (S)) consistent S] - 22 (1 e*)l + Piiccnnsistent S)
50

---

F.2 Derivation of the posterior sampling generalization bounds (Section 4.2
Lemma F.3. For the posterior sampling algorithm
1
2
((;A S IEs
log
consistent S Ps (consistent S) + e eln2
Ps
Proof. Recall the definition of the marginal distribution of the algorithm's output (a hypothesis h) is
dv (h)
Σ dp hs,
where s are all possible realizations a (training) sample of size N.
For h = *, we have dv (+) Ps (inconsistent 5).
For h + *, since L. (h) 0 implies that is consistent, we have
dv (h) ~ Σ (s, h) = Σ II Ifc, (h) 0}
dp (h) dDN (s)
Ps
11C, (h) = 0} dP (h) dDN (s)
#:p.>0
11c, (h) = 0} dDD (s)
dPP (h)
Σ
Ps
s:p. 20
I Hps 0)
[[Cs (h) = 03]
dP (h) ES-D
Ps
where, for ease of notation, we use the convention that kp.00]
when ps = 0. Denoting
1 [ps > 0}
(h) A ESWDN
11 (Cs (h) 03
ps
we get
dv (h) dP (h) π (h)
Notice that if there exists supp (DN) such that Le (h) 0 then x (h) 0. Using the definition of the mutual information:
dp (s,
(S;A E Σ
dp (s
dv (h) dD (s)
AEAU
dp (8,*)
(s, (s, h) du (h) dD (s)
Σ dp (s, x) log
du (+) dD (8)
Σ
Σ
dp (s, log
s:p, 20 hEN
dD (8)
Σ =p.=0 =U
dD (s) log
P9 (inconsistent 8) d' (s)
P. LdP (h) dD (s)
Σ
dP (h) dD log
Ps
JP (P)h) क (h) dD
sp,>0 20 l:L,, (h)=0
Σ dD dD(s) log
(e ST
Σ Σ
_
1
dP (h) dD (s) dD)
log
11,5)
P. (h)
Ps
0
O:C (k)=0
Simplifying each term separately, the first sum immediately simplifies to
1
-Ps (inconsistent S) log (Ps (inconsistent S)) < In
51

---

and
Σ
Σ
dP (h) dD (s) log
sp. htC, (k)=0 Ps
P&T (h)
E
E
dP (h) dD (s) log (p=)
E Σ
dP (h) dD (s) log (π (f))
Ps
sp, >0 (1)=0
8:ps 20 le: (k)==
Σ
- (pg
Σ dP((h)
s:,,00 Ps
(h)
=p.
Ifc, (h) = 0}
E Σ
dP (1)) dD (8) log (T (h))
Ps
s:p, 30 (:)()))2
-
1 IfC, (h) 0}
Σ
log dD (s))p=
E
log (TT (h)) dp (h)
Σ
dD
Ps
sP,
SPp,20
=x(h)
Σ log (p,)dD (s)
E
(h) log (1r (h)) dP (h)
(1)30
-Es [log (ps) {ps > 0}] - En~P { (h) 0} ক (4) log ( (h))
1
-Es
log
Ps > 0 Ps (ps > 0) + En~P |- (h) log (T (h)) (h) >H 0H
PS
$1/cl12
1
<
Es
log
consistent 5 IPs (consistent S) + e In
ps
Putting all of this together,
1 consistent S Ps (consistent S) + e eln
I (S; ((S) S Es
log
52

---

Corollary F.6. The generalization of posterior sampling satisfies
Es
log
1 ps
consistent s) +3
-log (1 (SS))()) (LD (A)) consistent S])
Proof.
Combining Lemma C.2 and Lemma F.5
we get
((S:A(5)) 2 lolog (1 Es,A(S) [CD (A(5))
consistent 51 Ps (consistent S)
and
1 ps
AS) & Es
log
consistent
Ps (consistent S) + In 2
so
-N log (1 - (s))(s)
[CD (A (S)) consistent ST) Ps (consistent S)
- Es
log
consistent $
P s (consistent 5) + e eln
and finally, using 2/e ln2 S 1.5 and recalling
C.I
we get
Es
log
consistent s) +
- log (1 -SE,,A()) [CD (A)))
consistent S])
Ps
N
53

---

OTTY (d). Let be network with depth L, dimensions d, and parameters 0 W.. Tt Let 2 d. Similar to @BTN (d: h2) introduced in Lemma D.26 let O (d:h) = OBTN (d) be the set of parameters 0 that implement h setting a subset of the parameters to be equal to O. and zero the effect of redundant neurons by setting their bias and neuron scaling terms to be 0. This is illustrated in Figure In particular, in our notation, OBIN (d: h2)
@BTN (d: hı @ h2).
do
d
d2
d3
d4
ds
Figure 4: Implementing narrow network with wider network. Blue edges represent parameters set to equal the parameters of h, gray nodes represent zero neuron scaling, and gray edges represent unconstrained parameters.
Lemma F.7. Let h be network with depth I. and dimensions 1. Let d 2 d. Then
10TTN
(d:
-
llo
(d) +0 (n (d) log (d + do))
OBIN
Proof. We prove this by counting the number of constrained parameters in BTN (d: The number of constrained weights is
di do +
didh11,
which is exactly w (d). In addition, there are n (d) constrained bias terms, and (d) constrained scaling terms. In total, after accounting for the quantization of each parameter, this means that
OBIN (d:h) BOBTN (d)
(d
II (2d(-1)
weights
scaling terms
80
OBTN (d: ROTN (d)
-log
< w ( + n
log 3 + Σ di log (2d
1=1
< w d + n m((d) log 3 + n2 (d) log (2dmaax + 2do)
O (n (d) log (dmax do))
54

---

Combining Lemma F.7 with Assumption 2.4 and Corollary 3.4 gives the following lemma.
Lemma F.8. Consider a distribution induced by a noisy teacher model of depth L* and widths d' (Assumption 2.4) with noise level of E* < 1/2. Let S ~ DD be a training set with effective training set label noise Eir as defined in (4). Then there exist constants eı, C2 such that for any student network of depth L 2 max {L* 14] 2 and widths N satisfying
1I
L -1 di di N3/4 (log NY c2 do log (N)
holds for posterior sampling with a uniform prior over parameters that
1
Es
log
consistent S
Ps
S w (d') + N (étr) + 2n (d") /// "polylog
+ (da (do + (d*)) log (N) + n (d) log (dmax + do))
Remark F.9. Unlike the bounds for min-size interpolators, there is no H (éir) 8/4 term multiplying the N3/4 term. This is because the architecture of random interpolators is fixed, in setting must assume that is wide enough order to guarantee interpolation any noisy training set.
Proof. Notice that for posterior sampling with uniform distribution over parameters, the interpolation probability ps can be lower bounded as
OBIN d: ht
hs
ps
BBTN (d)
and therefore
O ht + hs)
log
log
BBB (d)
ps
Then, using the bounds from Lemma E.7 with the one from Corollary 3.4
1
log
w (d' N H (Ls (h²)) + (d*) 33/4 polylog
ps
O (do (do + (d*)) log N + n (d) log (dmax do))
By taking the expectation and using Jensen's inequality with the concave we arrive at
Es [ (Cs (h*)) consistent $] H (Es [Cs (h*) consistent 51) = H (Éx)
Hence
Es log
consistent 5
w (d*) + N H (&xz) + 2n (d') h3//ppoyloo//
+ 0 (do (do + n (d))) log (N) + n (d) log (dmax + da))
55

---

Recall Theorem 4.4, Consider a distribution D induced by noisy teacher model of depth L* and widths d' (Assumption 2.4p with noise level of 1/2. Let S ~ D. be a training set such that
N o( W1/DDmDa (axm) Then, there exist constants c1, C2 > such that for any student network of depth Z max {L", 14] + and widths d E N holding
11 1. - de di + N3/4 (log N) +2 do log (N)
(11)
the generalization error of posterior sampling satisfies the following.
Under arbitrary label noise,
Es.)()) [CD (S))) < 21-2-H(E") 2 max + O (Crand (N))
Under independent label noise,
[ssA(s) [CD (A(S)) - 2Et (1-E*))
0 (Crnn (N)) + IP (inconsistent S) (N - -1) + (inconsistent .S) P (consistent S)
$ (1 (1-2z")
where
Grand (N) n (d .polylog (N)
w + (do + (d")) -log (N) +n (d)-log (dmax + do)
+
V/
N
Remark F.10.
The bound shown in Section 4.2 is found by bounding TP (inconsistent S) as in Assuming that N = w (n (d') polylog (n (d*)) + dg log do) we can deduce that
Lemma
B.
N w w d
as well since
w (d)) (n (d") + du)² < 4 (max {n ,du))
Together with N a (V1//Dmas) we get the desired form of the bounds.
such that student NN satisfying (II can interpolate any consistent dataset, and so posterior sampling is interpolating for all consistent datasets.
Proof. Corollary 3.4 implies that there exist Cı 02
We start by proving the bound for arbitrary label noise. First, notice that
P(Y1 + hX1),, consistent S)
E = P(Y * h" hxXG)) consistent S)
IP (consistent S)
< P(Y + (X1))
(consistent.
(consistent $)
The entropy function H is increasing in [0. 1 and achieves its maximum at } so together with the inequality above, we get,
(Éw) < H (min Flconsistett ST+ +)) = 11 ((( min [Fcoonsistent -5 --*))
H I!(e" min fe*
Piinconsistent 8) 1
P(eansistent 5) -=}} Hl (6* + A)
Employing the concavity of the entropy function, we get,
IP (inconsistent S) P (consistent S)
H (Ex) < H (s* + A) < H(e*) (e*) A H(E))+ H'()))
algebraacaally
56

---

By combining the above with Corollary F6 Lemma F.8
we have that
ls [log (1/ps)
consistent S] +
log (1 - ((S)A(S)) CCD (5)) consistent S1) S
N
H (6x) + (d') + N. H (étr) (d") /3/ polylog.
+ +0 (do (do + n (d))) log (N) + (d) log (dmax + do))
- H (En) + 0 n(d') polyyoog())
w(d") doldd log (N)lolgNNonnnnononnn + ( (dum +do)
VN
N
H(**) +
P'inconsistent 8)
[conssstent S)
+ 0 (olyo)polylog(N) wld +d((d=+((((( (oo (Smon +do)
N
-+()) +
Fiinconiistent 8)
(Crand (N))
2F (consistent 3)
Rearranging the inequality results in
((S))(S)) [CD (A consistent S]
I - H(e*)- Finconstetens 0 O(Crand(N))
Then, using Lemma A.6 we get,
((s,A(S)) [CD (A (S)) consistent S]
< 1 2- [((")) P (inconsistent 5)
O (Crand (N))
2P (consistent 8)
Repeating the argument from the proof of Theorem Y we have
since for an RV X in [0, 1] and a binary RV
E[ E[X P(Y) + E[X -Y
B[X +)+((-
we have,
E ((S,A(S)) [CD (A (S)) S ((S.A(s)) [Cp (A (S)) consistent S] + (inconsistent S)
P (inconsistent 8)
< $1-2-H('"). + 2I (consistent S) + P (inconsistent 5) (Crand (N))
IP (inconsistent S) O (Crand (N))
< 21-2-H(e" H((")) + (consistent. S)
1 N max
< 2- H())) +
+ +0 (Crand (N))
1 N22Daax max
< 2- H())) + 2N max + (Crand (N))
where in the last inequality used t/ (1 S 2t for t 00,
Moving on the independent noise setting, combine Lemma from Lemma B.2 to bound the mutual information as
F.5
Lemma
F.8 and & 5
<1
1
2
I (S:A(S)) < Es
log
consistent
S
Ps (consistent S)
Ps
In
1
< Es
log
consistent S
+ 1.1
ps
< N H (E + O (N- Crand (N))
57

---

Plugging the above into C(N) of Lemma C.3 we get,
(NN) = A(S:A(S) N. H (E*) + N SDNN (inconsistent S)
N P (consistent S)
N-H(s")+O(N COHHHONN-CaaaCCC Grana(())))aa N Plosossistettt S)
J+N M--N---Piinnnsiiiit Plinconsisteat S)
(Crand (N)) + IP (inconsistent S) PP (consistent S)
Then we continue as in the arbitrary noise setting to get the desired bound.
58

---

G Alignment with Dale's Law
In this section, we show that our results apply a model resembling "Dale's Law" [2], i.e. such that for each neuron, all outgoing weights have the same sign. To this end, we define the following model, in which the main difference from Def. i. is that neuron scaling applied after the threshold activation.
Definition G.1 (Binary threshold networks with outgoing scaling). For depth L, widths d d= (di,....,,da dr.), input dimension do. a scaled-neuron fully connected binary threshold NN with outgoing weight scaling (oBTN), is mapping 0 ge such that ge {0, 0, parameterized by
b 0 { (w0,,b,,7000
Jmm1
where for every layer I [L],
w E O = [0, -10, x t0 =1-1,00, boy = + l.......................... .
This mapping is defined recursively as go (x) (L) (x) where
g0t) (x) = x, g (x) - @
(x) (b)) > 0)
E [Z]
Lemma G.2. Let ge be an oBTN as in Def. G.1 Then there exists BTN he with the same dimensions
and ((u)) E 2 & {-2d; + 1..... 2d such that hgg = Da + s for s E {0, 17dz. such that for all i 1, ,,... dr s; only ( -1
Proof. We prove the lemma by induction on depth. As we will see, the base case is a particular case of the step of the induction, so we start with the latter. Let 1 = 1.... L. For ease of notation,
we denote C' = (d) and A = g(--1), as well as C' = (1))) A' = (1-1), In addition, we omit the superscripts from the 1th layer's parameters. Let I,..., di, then by the induction hypothesis there
exists some a E {0, 1) di such that (x) (x) - a, for inputs x.
di-
Wis (A' (A'(x); a,) > o
>0}
C (x)), = =/s .I
+ Σ
Why
A (x);
>
7/2 I
bi
Σ 1=1
j=l
di-1 Σ
= =..1l 11
Σ
wijaj
wiy A' (x);
If +1, choose 7/6 11, and b1 = b; Σ/11 di-1
Wiaaj. Clearly, since wij. aj E {0, 1}. it holds
that Σ wijas s d so byg E 2 Then
di-
(x),, = 1 61 +
Σ
W Ax)) > =C' -x'(x);
j=1
59

---

L.e, the claim holds with 8; 00. y = -1 then
di-1
di-
C(x), = % I
b;
Σ
Wijaj
+
Σ
wiy (xx, >
j=1
j=1
d=11
d
}
b;
Wiyaj
+
Σ
WayA' A' (xx; =0}
Wiy
y=1
j=1
d-11
d-11
by
ajjaj
+
Wij (x))x 50 5
j=1
j=l
d1
4t Σ
Σ
Wijaj
wij (xxz 2 $
j=1
j=1
di-1
di-1
)
1
b
Wijaj
Σ
Wiy A' (xx) 20]
Thus, we can construct the 1ch layer of by choosing % -1 and 1/3 = - - - wija;) so
di-1
di-
}
((x), = -
bi
Σ
Wig(i
-
Σ ==1
mij
Wij Al (x); > o
==1
d2
= -11+I
by +
Wiy Wiy A' (x); > 0
=C' (x); - 8;
with 8; 1. Finally, 7/ O, then Cj is identically 0,, we can choose %/6 b3 = 8, 0. Notice that this construction also proves the base case / = 1 where a = O.
Corollary G.3. Let O' be the set of oBTN parameters such that for all I O¹ go (0, 1) do (0, (0,1)dt Then there exists BTN, as in Lemma G.2 such that go =
Proof. Let 0 E O'. Since go (x) of for all there exist parameters O' E O' such that go go. and (L)) 2 0. Hence, by Lemma G.2 there exists BTN h such that h = ger, i.e., with 8 = 0. O
Remark G.4. Similar results can be shown in the other direction. That is, that BTNs can be represented as slightly larger oBTNs.
Finally, recall from Appendix F that the cardinality of the hypothesis class is related to the error terms of Theorem and Theorem| logarithmically, meaning that we can apply the results to Def. G.I without qualitatively changing them.
60

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We accurately state the general setup and the essential results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are 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 theory in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create 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 (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 address problems of privacy and faimess.
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?
Answer: [Yes]
61

---

General assumptions on the sabel-generating process are clearly stated in Section 2.2 Additional assumptions are stated at the beginning of each theorem. Rigorous proof' are given in our supplementary materials and are referred to in the main body of the paper.
Justification:
Guidelines:
The answer NA means that the paper does not 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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: 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 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, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access 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 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.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (c.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
62

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer:
[NA]
Justification:
No experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https::/niis.cc)
for more details.
While we encourage the release of code and data, we 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 new 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. //wpss.ccppb.ii.. http:puulcggggdese....eeppe
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: No 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 to 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, or as supplemental material.
63

---

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: No experiments.
Guidelines:
The answer NA means that the paper does 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 run with given experimental conditions).
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 I-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 or 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: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 as 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 or failed experiments that 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 NeurlPS Code of Ethics http:///wurrpps.cccuucllee/e/eee
Answer: [Yes]
Justification: Our work adheres NeurlPS' ethical guidelines.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
64

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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: Our work is theoretical in nature, and we do not see direct social impact.
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 or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 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 point 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 a generic algorithm for optimizing neural networks could enable people 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 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 to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
No data or models are released.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a 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 challenging, and many papers do not require this. but we encourage authors to take this into account and make best faith effort.
65

---

12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Not using external assets.
Guidelines:
The answer NA means that the paper does not 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 of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If 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:
This is theoretical papers; we do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details 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 was obtained from people whose asset 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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.
66

---

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: Our research did not involve 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.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
67


Reviews:
[{"review_id": "vqqGJNikZT", "reviewer": "Reviewer_gENy", "summary": "The paper studies the generalization ability of the interpolated minimal quantized nets. It considers the task of classification with a binary sequence input using Quantized neural networks. It establishes the generalization error of the minimal-width neural network that interpolates the dataset and claims that it belongs to the tempered overfitting regime. Overall the paper is well-written and technically solid.", "questions": "(a) The first thing I'm concerned about is the definition of a consistent dataset. Does introducing the consistent dataset just make the definition of interpolator well-defined, or the proof will depend heavily on the fact that the dataset is consistent? For example, if I define the interpolator $\\hat{h}$ to be the one such that $L_S(\\hat{h}) = \\inf_{h} {L}_S(h)$ can one expect a result similar to line 144 with the term containing N^2 D\\_{max} be removed?\n\n(b) The paper establishes the asymptotic risk of the interpolator, which is good. In the noiseless setting, the risk converges to 0 at the rate of $N^{-1/4}$ if the teacher network is fixed, this is slower than the standard parametric rate $N^{-1}$. Is this because of the fundamental limits of the proposed estimator such that the error bound is tight, or the analysis can be improved?\n\n(c) The result of Theorem 3.1 is for a fixed-depth network. Can similar, matching results hold for the case with varying depth L and width N networks?", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(a) The paper presents a novel theoretical analysis of overfitting behaviors in neural networks with binary weights. The new approximation result Theorem 3.1 and generalization result Theorem 4.1 are all novel to some extent.\n\n(b) The paper is well-structured, with clear definitions and thorough explanations of the models and assumptions used.", "weaknesses": "(a) I'm not sure how the theoretical results derived in this paper will provide any insights into how people understand interpolated neural networks even in theory. It seems that this paper just plugged in the new approximation result Theorem 3.1 in the framework of (Manoj & Srebro, 2023). In other words, the paper provides marginal new information in this regard. The main theorem Theorem 4.1 is somewhat can be expected.\n\n(b) The paper seems to combine everything in a whole, complex theorem and the reader cannot get any insights beyond the conclusion in Theorem 4.1, and the presented results are the same and can be expected after reading (Manoj & Srebro, 2023).\n\n(c) I strongly recommend another round of refactoring to improve the readability of the paper, for example\n\n i) I think in the statement, the term $2^{H(\\epsilon^\\star)}$ should be  $2^{-H(\\epsilon^\\star)}$, given the usual definition of entropy.\n\n ii) the notations are heavy, which prevents potential audience. \n\n iii) some inconsistency in notations. For example, it defines the weights in the notation section, but it uses ``edges'' in the theorem statement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed constructive feedback.\n\nBelow we address the reviewer’s concerns and explain how they’ll help us improve our paper.\n\n> (Weak.a) I'm not sure how the theoretical results … provide any insights into how people understand interpolated neural networks ... In other words, the paper provides marginal new information in this regard. The main theorem Theorem 4.1 is somewhat can be expected.\n\nOur general framework is indeed similar to the one in M&S (2023). The main conceptual novelty in our paper is that we show this framework can be adapted to\n\n(1) Neural networks (using Theorem 3.1 which is the main novel technical result) and\n\n(2) Random interpolators (building upon the approach from Buzaglo et al. 2024).  \n\nWe agree that direct implications of our results to more practical settings (e.g., networks trained with SGD) require further investigation, but we think that these results are interesting in and of themselves as well, as they predict the same tempered behavior observed in practice (see our explanation in the general comment on the fact that our independent setting results in the linear behavior observed in Mallinar et al. (2022); we will explicitly mention this in the revised paper).\n\n> (Weak.b) The paper seems to combine everything in a whole, complex theorem and the reader cannot get any insights beyond the conclusion in Theorem 4.1, and the presented results are the same and can be expected after reading (Manoj & Srebro, 2023).\n\nWhile our results can perhaps be conjectured after reading M&S (2023), they are not trivial, and require the novel memorization result (Theorem 3.1), as well as additional adaptations to match our setting (e.g., when the input dimension is finite).\n\n\n> (Ques.a) The first thing I'm concerned about is the definition of a consistent dataset. Does introducing the consistent dataset just make the definition of interpolator well-defined, or the proof will depend heavily on the fact that the dataset is consistent? For example, if I define the interpolator $\\hat{h}$ to be the one such that $L_S (\\hat{h}) = \\inf_{h} L_S (h)$ can one expect a result similar to line 144 with the term containing $N^2 D_{max}$ be removed?\n\nAs in previous work, we aim to study the behavior of interpolators, and thus must require the consistency of the training set (otherwise it’s impossible to interpolate). The $N^2 D_{\\max}$ term serves as a bound on the probability that the data is inconsistent, and is needed due to the fact that we examine a setting with a finite sample space. \n\nImportantly, as currently phrased, Framework 1 *allows* defining the interpolator $L_S (\\hat{h}) = \\inf_h L_S (h)$ as suggested by the reviewer, but our analysis requires that the value of this minimal loss equals 0 with high probability. We will explicitly explain this after presenting the framework.\nWe agree that it is interesting to study the suggested learning rule, $L_S (\\hat{h}) = \\inf_h L_S (h)$, when the inconsistency probability is not small, and we explicitly mention it in the future work section. \n\n> (Ques.b) The paper establishes the asymptotic risk of the interpolator, which is good. In the noiseless setting, the risk converges to 0 at the rate of $N^{-1/4}$ if the teacher network is fixed, this is slower than the standard parametric rate $N^{-1}$. Is this because of the fundamental limits of the proposed estimator such that the error bound is tight, or the analysis can be improved?\n\nThe $N^{-1/4}$ term comes from the lower order $N^{3/4}$ term in Corollary 3.3, and the fact that we omitted for simplicity an $H(L_S (h^\\star))$ scaling term in the proof of the corollary (see the proof of Corollary 3.3 in page 43, lines 1095 and 1096). In fact, by reintroducing the entropy term with $L_S (h^\\star) = 0$, the $O (1 / N)$ bound in the noiseless setting can be recovered from our results up to a logarithmic term. This is expected, as, without the noise-memorizing-network, our bounds depend only on the teacher model (up to logarithmic error terms accumulated in the analysis). \nThere is a slight caveat in the random interpolator model — with a positive error rate, we require the width of the network to be at least $N^{3/4}$ in order to guarantee interpolation of any consistent training set (with any number of label flips), so the $N^{-1/4}$ rate in the bound remains. To get the desired $N^{-1}$ rate, we must assume that the width of the network is constant w.r.t N, which is reasonable if we know that there is no noise. \n\nWe will clarify this in the paper.\n\n> (Ques.c) The result of Theorem 3.1 is for a fixed-depth network. Can similar results hold for the case with varying depth L and width N networks?\n\nIndeed, in Theorem 3.1, the $3/4$ exponent can be improved to roughly $2/3$ at the cost of an increased depth (see Remark D.7, page 30). That being said, we don’t know the *optimal* dimensions of an interpolating network, as our approach — calculating the XOR between the teacher and label flip memorizing networks — may not be optimal. Therefore, we leave this interesting question for future research. However, we *do* know it is not possible to decrease the max-width bound in Theorem 3.1 below $\\sqrt{N}$, assuming the depth is a constant. In such cases, the total number of parameters will be too small to be able to interpolate an arbitrary configuration of label flips.\n\nMinor note: in the question the reviewer used $N$ to denote width, but the paper uses $N$ to denote the number of samples. We assumed this was unintentional (as width $N$ does not not make much sense in our approach).\n\nFinally, like the reviewer suggested, we will make another pass to improve the paper’s readability even further. Specifically, we will fix the missing minus sign and make sure to unify the terminology (e.g., edges / weights). Additionally, we will try to unburden the notations as much as possible, and verbally re-mention their ‘role’ as we use them throughout the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zERdSEDkBI", "reviewer": "Reviewer_q6NB", "summary": "The paper proves that both minimum size and random interpolators exhibit tempered overfitting in the case of binary classification using a threshold network with binary weights on a noisy training set.", "questions": "I wonder if there is any way one could empirically verify the tightness of the proven results, even for small networks.", "limitations": "Limitations are addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proves tempered overfitting for minimum size and random interpolators in the presence of label noise. This can be seen as an extension of previous analysis, which considers settings without label noise, or other learning rules (e.g. shortest description length of Turing machines). The proof of the results relies on a new construction of a relatively small neural network that can learn arbitrary label noise.\n\nThe paper is well-written and easy to follow.", "weaknesses": "The derived bounds require some additional constraints on the width of the network and the number of examples due to the presence of label noise. Such requirements may not always be satisfied in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback.\n\n> I wonder if there is any way one could empirically verify the tightness of the proven results, even for small networks.\n\nKindly see our comment on this in the general rebuttal response. \nBriefly, our results in the independent setting agree with the linear behavior observed empirically in Mallinar et al. (2022). Following the question from the reviewer, we will explain this in the revised manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ecbKiEMm7T", "reviewer": "Reviewer_E8Kb", "summary": "This paper investigates the overfitting behavior of fully connected Deep Neural Networks (DNNs) with binary weights fitted to perfectly classify a noisy training set. The authors analyze the interpolation using both the smallest DNN (having the minimal number of weights) and a random interpolating DNN. They prove that overfitting is tempered for both learning rules. The analysis is based on a new bound on the size of a threshold circuit consistent with a partial function.", "questions": "1. What are the limitations of your research? Are there any particular scenarios or datasets where your method may not perform well? It would be helpful to have a more thorough discussion of the limitations and potential future directions of the research.", "limitations": "The authors addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) This paper presents innovative research on the overfitting behavior of DNNs with binary weights, which adds to the existing literature on the generalization capabilities of neural networks.\n2) The analysis is based on a new bound on the size of a threshold circuit consistent with a partial function, which provides a theoretical foundation for the results.\n3) This paper provides a clear and well-structured explanation of the research problem and methodology, making it easy for readers to follow.", "weaknesses": "1) This work focuses on the learning theory and presents the first theoretical results on benign or mitigated overfitting. It would be better if authors could provide necessary evaluation studies to support theoretical results.\n2) This paper could benefit from a more thorough discussion of the limitations and future directions of the research.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and valuable feedback.\n\n**Regarding Weakness 1:**\n> This work focuses on the learning theory and presents the first theoretical results on benign or mitigated overfitting. It would be better if authors could provide necessary evaluation studies to support theoretical results.\n\nKindly see our comment on this in the general rebuttal response. \nBriefly, our results in the independent setting agree with the linear behavior observed empirically in Mallinar et al. (2022). Following the question from the reviewer, we will explain this in the revised manuscript.\n\n**Regarding Question 1:**\n> What are the limitations of your research? Are there any particular scenarios or datasets where your method may not perform well? It would be helpful to have a more thorough discussion of the limitations and potential future directions of the research.\n\nWe specify the setting in which our results apply in Section 2, and the assumptions under which our results apply in the appropriate theorems/lemmas. In short, we assume binary input features, and labels that are generated by some fixed teacher model with added noise. In the model, we assume binary $\\{0, 1\\}$ weights with threshold activations and $\\{-1, 0, 1\\}$ neuron scaling. In Theorems 4.1 and 4.3, our assumptions are (1) that the data is consistent with high probability, (2) that the training set is large enough to make our bounds non-trivial, and (3) that the model is large enough to guarantee interpolation of consistent training sets. \n\nWhile our results agree with previous empirical works in more realistic settings (see our general comment referenced previously), we do not claim that our theoretical results apply to them. The adaptation for scenarios other than those described in Section 2 is left for future work. We will make this point clearer in the discussion of limitations and future work in Section 6.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hRbV7DPL8h", "reviewer": "Reviewer_X2nX", "summary": "This paper studies the tempered overfitting phenomenon in deep neural networks. The authors show the upper bound of test loss in both Min-size interpolators and random interpolators, which indicates the tempered overfitting.", "questions": "Generally speaking, incorporating synthetic experiments could further support the theory. Is it possible for the authors to include some synthetic experiments to validate the theoretical results? I am not suggesting that the authors are required to add experiments. I understand that this is primarily a theoretical analysis paper, and adding synthetic experiments seems difficult.  Therefore, I am asking the authors to consider the possibility of adding synthetic experiments.", "limitations": "See weakness and questions above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors considered the quantized networks, and gave theoretical results on the tempered overfitting in DNNs without requiring the data dimension to be very low or very high.", "weaknesses": "a) I am concerned about the claim made in your contribution (Line 40) that \"any noisy dataset can be interpolated using a neural network of constant depth with threshold activations and binary weights.\" Doesn't this only hold under specific data settings? I would appreciate it if the authors could comment on this point.\n\nb) The mathematical symbols are used somewhat casually. For instance, (1) in line 94-95, the meaning of $A(S)$ and $\\\\mathcal{H}$; (2) in line 112, the meaning of $\\tilde{h}\\_{S} $. I recommend that the authors provide more explanations for the mathematical symbols, as this would strengthen the paper.\n\nc) The motivation behind selecting quantized networks is unclear. Why were the networks quantized? Were the networks designed to fit the data model? I recommend that the authors provide some explanation for the motivation behind using quantized networks. In practice, few models use quantized networks.\n\nd)  In line 180, the statement that $d\\_0=o(\\sqrt{N/\\log(N)})$ requires the data dimension to be low. Does this contradict the previous comment (line 39) that the input dimension is not very low?\n\ne) I recommend that the authors provide more explanation about Theorem 3.1 to help readers better understand it. I am not sure if I fully understand Theorem 3.1. \n\nf) I am confused of the term $N^2 \\mathcal{D}\\_{max}$ in Theorem 4.1 and 4.3. Is this a small term? Can we find some conditions to ensure $N^2 \\mathcal{D}\\_{max}$ is small? It seems that $N^2 \\mathcal{D}\\_{max}$ loses the tightness.\n\ng) In Remark 4.4, what's the meaning the dimension of $\\underline{d}$ is small enough? Does it mean the network depth $L$ is small enough (constant level)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and constructive feedback.\n\nBelow we address the reviewer’s concerns and explain how they’ll help us improve our paper.\n\n> a) I am concerned about the claim made in your contribution (Line 40) ... Doesn't this only hold under specific data settings? I would appreciate it if the authors could comment on this point.\n\nIndeed, this was not clear. We refer to interpolation of training sets with binary input features which labels are generated by a constant-size teacher model with label noise (as specified in Section 2). We will rephrase this line to clarify this.\n\n> b) The mathematical symbols are used somewhat casually. For instance, (1) ... $A(S)$ and $\\mathcal{H}$; (2) ... $\\tilde{h}_S$. I recommend that the authors provide more explanations for the mathematical symbols, as this would strengthen the paper.\n\nThank you, we will make sure to explain the mathematical symbols and emphasize their role.\n\n> c) The motivation behind selecting quantized networks is unclear ... I recommend that the authors provide some explanation for the motivation behind using quantized networks. In practice, few models use quantized networks.\n\nFrom a theoretical point of view, the focus on quantized models simplifies the analysis considerably (e.g. we follow a similar proof technique for random interpolators as in [A], which also discussed quantized and continuous neural networks). We don’t find this assumption too restrictive as most continuous models can be approximated by quantized networks with sufficiently-fine quantization, under appropriate assumptions on the data (e.g. see [B]).\n  \nThe restriction to networks with binary weights is stronger, and is due to Theorem 3.1 which is the main technical tool of the paper, and for which we do not have a sufficiently tight analog for networks with higher quantization levels. As we note in Section 6 (line 241), some of our results can be extended to networks with higher quantization at the cost of looser bounds. We will explicitly write them in the paper.\n\nMoreover, from a practical point of view, all practical models are quantized to some extent (e.g., using float32) and there is a vast literature which studies NNs with lower numerical precision (e.g. see [C]), some even using as few as 1 bit [D]. Numerical precision has a large impact on efficiency (memory and computation), and thus, using a lower numerical precision is a very popular method to improve this efficiency.\n\nWe will clarify these important points in the paper.\n\n[A] G. Buzaglo, I. Harel, M. S. Nacson, A. Brutzkus, N. Srebro, and D. Soudry. How uniform random weights induce non-uniform bias: Typical interpolating neural networks generalize with narrow teachers. In International Conference on Machine Learning (ICML), 2024.\n\n[B] Ding Y, Liu J, Xiong J, Shi Y. On the universal approximability and complexity bounds of quantized relu neural networks. arXiv preprint arXiv:1802.03646. 2018 Feb 10.\n\n[C] Gholami A, Kim S, Dong Z, Yao Z, Mahoney MW, Keutzer K. A survey of quantization methods for efficient neural network inference. In Low-Power Computer Vision 2022 Feb 22 (pp. 291-326). Chapman and Hall/CRC.\n\n[D] Courbariaux M, Hubara I, Soudry D, El-Yaniv R, Bengio Y. Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1. arXiv preprint arXiv:1602.02830. 2016 Feb 9.\n\n> d) In line 180, the statement that $d_0 = o (\\sqrt{N / \\log N})$ requires the data dimension to be low. Does this contradict the previous comment (line 39) that the input dimension is not very low?\n\nThe input dimension is indeed bounded, but can still be large (e.g., $O (N^\\gamma)$ for any $\\gamma < 1 / 2$). An upper bound is to be expected, as the size of neural networks depends on the input dimension. This does *not* contradict the “very low” dimension statement in line 39, which refers to the references [42,47] cited in the related works section, which proved tempered overfitting in the case of $d_0=1$. We will clarify this.\n\n> e) I recommend that the authors provide more explanation about Theorem 3.1 to help readers better understand it. I am not sure if I fully understand Theorem 3.1.\n\nThe main takeaway from Theorem 3.1 is that label flips can be memorized with networks with a number of parameters that is optimal in the leading order $N \\cdot L_S (h^\\star)$, i.e., not far from the minimal information-theoretical value.\nWe will emphasize this.\n\n> f) I am confused of the term $N^2 D_{max}$ in Theorem 4.1 and 4.3. Is this a small term? Can we find some conditions to ensure $N^2 D_{max}$ is small? It seems that $N^2 D_{max}$ loses the tightness.\n\nWe use $N^2 D_{\\max}$ as a bound on the probability to sample an inconsistent training set, which is required to be small in our analysis.  \nWe find that the assumption that $N^2 D_{\\max}$ is small is very reasonable, as the size of the input space is *exponential* in the input dimension. For example, if we assume that $D$ is a uniform distribution over all inputs in dimension $d_0$, then $D_{\\max}=2^{-d_0}$. We tried to explain this in footnote 3 on page 6, and Remark 4.4 about the required relationship between $d_0$ and $N$, but we now see that it is not clear enough, so we will clarify it further. \n\n> g) In Remark 4.4, what's the meaning the dimension of $\\underline{d}$ is small enough? Does it mean the network depth $L$ is small enough (constant level)?\n\nThe $O ( n(\\underline{d}) \\log (d_{\\max}) )$ error term in Theorem 4.3 vanishes when $n(\\underline{d}) \\log (\\underline{d}_{\\max}) = o (N)$ (what we referred to by “small enough”) thus making our bounds meaningful.\n\nRegarding $L$, throughout the paper we assume a constant depth, but our results can be extended to variable depth. This is simple in the posterior sampling case (see Remark D.25 and the following paragraph, lines 1059-1063), and more subtle in the min-size setting as it changes the learning rule.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all reviewers for their constructive and valuable comments which we will use to improve our paper in its revised version.

As the subject of **empirically validating** our results appeared in multiple reviews, we address it here in this general comment.

Finding min-size interpolators and random interpolators is computationally hard. Therefore, only very small-scale experiments are feasible when directly testing our results (see for example [A] as an empirical work on random interpolators). But such small-scale experiments are typically *inadequate* to test *asymptotic* results, as we derived.

While working on our author response, we realized that our theoretical results already match very well the empirically-observed results from [B] (which was the original paper that observed the “tempered overfitting” behavior in a practical setting, i.e., using standard SGD training on various datasets). Specifically, denote by $D$ a noiseless distribution over features and labels (without label noise), and by $D_{\varepsilon^\star}$ the corrupted distribution with independent label flip noise with error rate $\varepsilon^\star$. Then, Mallinar et al. [B] found empirically that, in standard binary classification settings with interpolating neural networks, the clean test error is approximately the training set’s error rate, $L_D (h) \approx \varepsilon^\star$ (see Figures 2, 3, and 6 in [B]). In the independent noise setting (used in [B]) it is easy to show that
$$
L_{D_{\varepsilon^\star}} = \varepsilon^\star + (1 - 2 \varepsilon^\star) L_{D} (h) ,
$$
so plugging in $L_{D} (h) \approx \varepsilon^\star$ implies that $L_{D_{\varepsilon^\star}} \approx 2 \varepsilon^\star (1 - \varepsilon^\star)$, and so, their empirical $L_D (h)$ behaves exactly as our analysis dictates in Theorems 4.1 and 4.3.

Thank you for making us realize this very important point. We will add this discussion to the revised paper. 


[A] Chiang PY, Ni R, Miller DY, Bansal A, Geiping J, Goldblum M, Goldstein T. Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent. InThe Eleventh International Conference on Learning Representations 2022 Sep 29.

[B]  N. R. Mallinar, J. B. Simon, A. Abedsoltan, P. Pandit, M. Belkin, and P. Nakkiran. Benign,
tempered, or catastrophic: Toward a refined taxonomy of overfitting. In Advances in Neural
Information Processing Systems, 2022.

Meta-review: This paper investigates the overfitting behavior of fully-connected binary neural networks with threshold activation, specifically networks trained/sampled to perfectly interpolate a noisy dataset. The paper demonstrates that overfitting is tempered, meaning that the interpolation is not optimal but still much better than trivial.

Overall, there is a consensus on the quality and relevance of the paper.

The reviewers have outlined that the paper is well-written and clear (*gENy*, *q6NB*, *E8Kb*). The results derived for neural network interpolators, specifically in the context of label noise and without imposing unrealistic constraints on input dimensions, have been identified as novel (*gENy*, *q6NB*, *E8Kb*, *X2nX*). The result on the memorization of random noise by binary threshold networks have also been highlighted as novel and valuable (*gENy*, *q6NB*, *E8Kb*).

This is a strong work, and I recommend acceptance.

The authors are encouraged to address the recommended proofreading checks (*gENy*) and to incorporate the clarifications they provided in their rebuttal, particularly regarding the reasoning behind the empirical validation discussed in their global response.
Decision: Accept (poster)