Provable Tempered Overfitting of Minimal Nets and Typical Nets

Authors: itamar  harel
william m hoza
gal  vardi
itay  evron
nathan  srebro
daniel  soudry technion
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:23:55

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.

Main paper: 
 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 a training set with corrupted labels (e.g., [5, 28, 57, 48] ).In an attempt to better understand the aforementioned generalization capabilities of NNs, Mallinar et al. [57] proposed a 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 if its generalization error is neither benign nor catastrophic -not optimal but much better 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 to understand the overfitting behavior of deep NNs in this regime.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 of parameters in a model is a natural complexity measure in learning theory and practice. For instance, it is theoretically well understood that L 1 regularization in a sparse linear regression setting yields a sparse regressor. Practically, finding small-sized deep models is a 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 a powerful model can avoid catastrophic overfitting by returning a min-size interpolator.Furthermore, we 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 explicit regularization or the implicit bias of any gradient algorithm. An immediate question ariseswhat kind of 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 low-frequency functions [70, 83] , while interpolating noisy training sets may require high frequencies.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., [42] ). Our analysis reveals that these models exhibit a 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 1 below, in which the yellow line in the right panel is similar to empirically observed linear behavior [e.g., 57, Figures 2, 3 Then, assuming the classes are balanced, the trivial generalization performance is 0.5 (in gray; e.g., with a constant predictor). Left. Evaluating the model on D, a Bayes-optimal hypothesis (in red) obtains a generalization error of ε ⋆ . For large enough training sets, our results (Section 4) dictate a tempered overfitting behavior illustrated above. For arbitrary noise, the error is approximately bounded by 1-ε ⋆ε ⋆ (1 -ε ⋆ )1-ε ⋆ (blue). For independent noise, the error is concentrated around the tighter 2ε ⋆ (1 -ε ⋆ ) (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 D 0 (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, 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.• The above results rely on a key technical result -datasets generated by a constant-size teacher model with label noise can be interpolated1 using a 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 3).V ∈ V, if P y∼Ber(α) R (V (y) = 1) ≥ 2ϵ, then P u∈{0,1} r (V (G(u)) = 1) ≥ ϵ. 2. The seed length is r = O(log(1/ϵ) • log 2 R).3. For every F 2 -affine function hash : {0, 1} a → {0, 1} r , the function C(w, z) = G(hash(w)) z can be computed by a depth-8 binary threshold network with widths d such that the maximum width d max at most a • log(1/ϵ) • polylog R and the total number of weights w (d) is at most(log(1/ϵ) • a 2 + log 2 (1/ϵ) • a) • polylog R.Remark D.18. The parameters of Lemma D. 17 are not yet sufficient to prove Theorem 3.1. Remember, we need the number of weights to be only (1 + o( 1)) • log(1/ϵ). On the other hand, Item 1 is stronger than what the HSG definition requires. This will enable us to improve the seed length of the generator later.The proof of Lemma D.17 is based on the work of Even, Goldreich, Luby, Nisan, and Velicković [27] .In particular, we use the following lemma from their work. Lemma D.19 (Implications of k-wise independence [27] ). Let X 1 , . . . , X R be independent {0, 1}valued random variables. Let X1 , . . . , XR be k-wise independent {0, 1}-valued random variables such that Xi is distributed identically to X i for every i.Then |P(X 1 = X 2 = • • • = X R = 1) -P( X1 = X2 = • • • = XR = 1)| ≤ 2 -Ω(k) .Proof of Lemma D.17. Let Q be the smallest positive integer such that Q ≥ 4R 2 and log log Q is an integer. Let ϕ : {0, 1, . . . , Q -1} → {0, 1} be the functionϕ(x) = 1 ⇐⇒ x ≤ α • Q.We think of ϕ as a function ϕ : {0, 1} log Q → {0, 1} by representing x in binary.Let ⃗ ϕ : {0, 1} R log Q → {0, 1} R be R copies of ϕ applied to R disjoint input blocks. Let G 0 : {0, 1} r → {0, 1} R log Q be a k-wise independent generator for a suitable value k = O(log(1/ϵ)• log R). Our generator G is the composition ⃗ ϕ • G 0 .Now let us 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(hash(w)) z , we begin by computing C 1 (w, z log Q + i) for every i ∈ {0, 1, . . . , log Q -1}, all in parallel, where C 1 is the depth-5 network from Lemma D.9. Since log Q is a power of two, the binary expansions of the numbersz log Q, z log Q + 1, z log Q + 2, . . . , z log Q + log Q -1simply consist of z followed by all possible bitstrings of length log log Q. The maximum width of one of these layers is bounded byak • polylog R = a • log(1/ϵ) • polylog R,and the total number of weights among these layers is at most(a + k) • ak • polylog R = (a + log(1/ϵ)) • a • log(1/ϵ) • polylog R. Furthermore, the number of output bits is log(1/ϵ) • polylog R.Next, recall that to compute a single bit of the output of G 0 , we need to apply the parity function to the outputs of C 1 . Therefore, to compute an output bit of our generator G, we need to apply an F 2 -linear function followed by ϕ. Observe that ϕ can be computed by a depth-two "AC 0 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) = O(log R). This can be viewed as a special case of an LT 2 circuit of size O(log 2 R). Therefore, by Lemma D.16, the F 2 -linear function followed by ϕ can be computed by a depth-3 binary threshold network in which every layer has width at most log(1/ϵ) • polylog R and the total number of weights is at most log 2 (1/ϵ) • polylog R. This completes the analysis of the computational complexity of G.Next, let us prove the correctness of G, i.e., let us prove Item 1 of Lemma D.17. Let V ∈ V and assume P y∼Ber(α) R (V (y) = 1) ≥ 2ϵ. Since V is a conjunction of literals, we can writeV (y) = V 1 (y 1 ) • V 2 (y 2 ) • • • V R (y R ) for some functions V 1 , V 2 , . . . , V R : {0, 1} → {0, 1}.We will analyze P u∈{0,1} r (V (G(u)) = 1) in two stages. First, we compare V ( ⃗ ϕ(G 0 (u))) to V ( ⃗ ϕ(ȳ)), where ȳ ∈ {0, 1} R log Q is uniform random. Then, in the second stage, we will compare V ( ⃗ ϕ(ȳ)) to V (y), where y ∼ Ber(α) R .For the first stage, we are in the situation of Lemma D.19, because the R many (log Q)-bit blocks of G 0 (u) are (k/ log Q)-wise independent. Therefore,P u∈{0,1} r (V (G(u)) = 1) -P ȳ∈{0,1} R log Q (V ( ⃗ ϕ(ȳ)) = 1) ≤ exp -Ω k log Q ≤ 0.5ϵ, provided we choose a suitable value k = O(log(1/ϵ) • log R).Now, for the second stage, observe that if we sample ȳ ∈ {0, 1} log Q uniformly at random, then|P(ϕ(ȳ) = 1) -α| ≤ 1 Q ≤ 1 4R 2 . For each i, since 1/R ≤ α ≤ 1 -1/R, we have P ȳ∈{0,1} log Q (V i (ϕ(ȳ)) = 1) ≥ P y∼Ber(α) (V i (y) = 1) - 1 4R 2 ≥ 1 - 1 4R • P y∼Ber(α) (V i (y) = 1).Therefore,P ȳ∈{0,1} R log Q (V ( ⃗ ϕ(ȳ)) = 1) ≥ 1 - 1 4R R • P y∼Ber(α) R (V (y) = 1) ≥ 1.5ϵby Bernoulli's inequality. Combining the bounds from the two stages completes the proof.At this point, we have constructed an HSG for conjunctions of literals with a non-optimal dependence on the threshold parameter ϵ (Lemma D.17). To improve the dependence on ϵ, we will use a 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 our context (conjunctions of literals).The basic idea is as follows. Let V be a conjunction of literals with a low acceptance probability: P y∼Ber(α) R (V (y) = 1) = ϵ. We will split V up as a product,V (y) = V (0) (y (0) ) • V (1) (y (1) ) • • • V (T -1) (y (T -1) ),where each V (i) is a conjunction of literals with a considerably higher acceptance probability:P y (i) ∼Ber(α) R i (V (i) (y (i) ) = 1) ≈ ϵ 0 ≫ ϵ.We choose V (0) to be the conjunction of the first few literals in V ; V (1) is the conjunction of the next few literals; etc. To hit a single V (i) , we can use our initial HSG with a relatively high threshold parameter (ϵ 0 ). Then, we use pairwise independent hash functions to "recycle" the seed of our initial HSG from one V (i) to the next.To implement this technique, one of the ingredients we need is a network that figures out which block V (i) contains a particular given index z ∈ {0, 1, . . . , R -1}. In this subsection, we describe networks that handle that key ingredient. The constructions are elementary and straightforward.First, we review standard circuits for integer comparisons. Lemma D.20 (DNFs for comparing integers). Let R be a power of two, let I ⊆ [0, R) be an interval, and let g I : {0, 1} log R → {0, 1} be the indicator function for I ∩ {0, 1, . . . , R -1} (identifying numbers with their binary expansions). Then g I can be expressed as a DNF formula consisting of O(log 2 R) terms.Proof. First, consider the case that I = [0, r) for some r ∈ {1, 2, . . . , R}. If r = R, then the lemma is trivial, so assume r < R. Let S be the set of indices at which the binary expansion of r has a one. For each i ∈ S, we introduce a term that asserts that the input z agrees with the binary expansion of r prior to position i, and then z has a zero in position i. The disjunction of these |S| many terms computes g I .The case I = [ℓ, R) for some ℓ ∈ {0, 1, . . . , R -1} is symmetric. Finally, in the general case, we can assume that I is an intersection of an interval of the form [ℓ, R) with an interval of the form [0, r). Therefore, g I can be expressed in the form AND 2 • OR log R • AND log R , where AND k / OR k denotes an AND / OR gate with fan-in k. To complete the proof, observe that every AND a • OR b formula can be re-expressed as an OR b a • AND a formula.Lemma D.21 (Computing a function that is constant on intervals). Let T and R be powers of two. Suppose the interval [0, R) has been partitioned into T subintervals, say [0, R)= I 0 ∪I 1 ∪• • •∪I T -1 .Let g : {0, 1, . . . , R -1} → {0, 1} a be a function that is constant on each subinterval I j . Then for every F 2 -affine function C 0 : {0, 1} d0 → {0, 1} log R , there is a depth-6 binary threshold network C : {0, 1} d0 → {0, 1} a+log R with widths d satisfying the following.1. For every x ∈ {0, 1} d0 , we haveC(x) = (g(C 0 (x)), C 0 (x)). 
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 base 2 logarithm, and ln to denote the natural logarithm. For a pair of vectors d = (d 1 , . . . , d L ) , d ′ = (d ′ 1 , . . . , d ′ L ) ∈ N L we denote d ≤ d ′ if for all l ∈ [L], d l ≤ d ′ l . 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, we use Ber (ε) for the Bernoulli distribution with parameter ε, and H (ε) for its entropy, which is the binary entropy function.Similarly to Buzaglo et al. [13] , we define the following model. Definition 2.1 (Binary threshold networks). For a depth L, widths d = (d 1 , . . . , d L ), input dimension d 0 , a scaled-neuron fully connected binary threshold NN, or binary threshold network, is a mapping θ → h θ such that h θ : {0, 1} d0 → {0, 1} d L , parameterized byθ = W (l) , b (l) , γ (l) L l=1, where for every layer l ∈ [L],W (l) ∈ Q W l = {0, 1} d l ×d l-1 , γ (l) ∈ Q γ l = {-1, 0, 1} d l , b (l) ∈ Q b l = {-d l-1 + 1, . . . , d l-1 } d l .This mapping is defined recursively as h θ (x) = h (L) (x) whereh (0) (x) = x , ∀l ∈ [L] h (l) (x) = I γ (l) ⊙ W (l) h (l-1) (x) + b (l) > 0 .We denote the number of weights by w(d) = We denote the set of functions representable as binary networks of widths d by H BTN d and their corresponding parameter space by Θ BTN (d). Remark 2.2. Our generalization results are for the above formulation of neuron scalars γ, 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 is similar to the ubiquitous phenomenon in neuroscience known as "Dale's Law" [82] . This law, in a simplified form, means that all outgoing synapses of a neuron have the same effect, e.g., are all excitatory (positive) or all inhibitory (negative). ) . This implies, using classical PAC bounds [75] , that the sample complexity of learning with the finite hypothesis class H BTN d is O (w (d) + n (d) log d max ) (a more refined bound on H BTN d is given in Lemma F.1). In Section 4 we show how this generalization bound can be improved in our setting.Data distribution. Let X = {0, 1}d0 and let D be some joint distribution over a finite sample space X × {0, 1} of features and labels. Assumption 2.4 (Teacher assumption). We assume a "teacher NN" h ⋆ generating the labels. A label flipping noise is then added with a noise level of ε ⋆ = P (X,Y )∼D (Y ̸ = h ⋆ (X)), or equivalently Y ⊕ h ⋆ (X) ∼ Ber (ε ⋆ ) . The label noise is independent when Y ⊕ h ⋆ (X) is independent of the features X (in Section 4 it leads to stronger generalization results compared to ones for arbitrary noise).We consider the problem of binary classification over a training set S = {(x i , y i )} N i=1 with N data points, sampled from the noisy joint distribution D described above. We always assume that S is sampled i.i.d., and therefore, with some abuse of notation, we use D (S) = D N (S) = N i=1 D (x i , y i ). For a hypothesis h : X → {0, 1}, we define the risk, i.e., the generalization error w.r.t. D, asL D (h) ≜ P (X,Y )∼D (h(X) ̸ = Y ) .We also define the empirical risk, i.e., the training error,L S (h) ≜ 1 N N n=1 I {h(x n ) ̸ = y n } .We say a hypothesis is an interpolator if L S (h) = 0.In this paper, we are 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 i , y i )} N i=1 is consistent if ∀i, j ∈ [N ] x i = x j =⇒ y i = y j .Motivated by modern NNs which are often extremely overparameterized, we are interested in the generalization behavior of interpolators, i.e., models that fit a consistent training set perfectly. Specifically, we consider Framework 1. While this framework is general enough to 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).A training set S. Algorithm: if S is consistent: return an interpolator A (S) = h (such that L S (h) = 0) else: return an arbitrary hypothesis A (S) = h (e.g., h(x) = 0, ∀x)In Section 4, 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.h is at most (1 + o(1)) • log N N1 + poly(d 0 ). More precisely, w d = log N N 1 + log N N 1 3/4 • polylog N + O(d 2 0 • log N ) .3. Every layer of h has width at most (log N N1 ) 3/4 • poly(d 0 ). More precisely,dmax = log N N 1 3/4 • polylog N + O(d 0 • log N ) .The 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 • L S (h ⋆ ), i.e., not far from the minimal information-theoretical value. The proofs for this section are given in Appendix D.Proof idea. Denote S = f -1 ({0, 1}). We employ established techniques from the pseudorandomness literature to construct an efficient hitting set generator (HSG) 3 for the class of all conjunctions of literals. The HSG definition implies that there exists a seed on which the generator outputs a truth table that agrees with f on S. The network h computes any requested bit of that truth table. Remark 3.2 (Dependence on d 0 ). In Appendix E we show that the O d 2 0 • 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 Ω √ d 0 • log N with ternary weights in the first layer, i.e.,Q W 1 = {-1, 0, 1} instead of {0, 1}, the O d 2 0 • log N term of Theorem 3.1 can be improved to O d 3/2 0 • log N + d 0 • log 3 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 h and h ⋆ . Lemma 3.3 (XOR of two NNs). Let h 1 , h 2 be two binary NNs with depths L 1 ≤ L 2 and widths d (1) , d (2) , respectively. Then, there exists a NN h with depth L XOR ≜ L 2 + 2 and widthsEQUATIONEQUATIONL2 + 1, 2, 1 , such that for all inputs x ∈ {0, 1} d0 , h (x) = h 1 (x) ⊕ h 2 (x).Combining Theorem 3.1 and Lemma 3.3 results in the following corollary. Corollary 3.4 (Memorizing a consistent dataset). For any teacher h ⋆ of depth L ⋆ and dimensions d ⋆ and any consistent training set S generated from it, there exists an interpolating NN h (i.e., L S (h) = 0) of depth L = max {L ⋆ , 14} + 2 and dimensions d, such that the number of weights isw (d) ≤ w (d ⋆ ) + N • H (L S (h ⋆ )) + 2n (d ⋆ ) N 3/4 H (L S (h ⋆ )) 3/4 polylogN + O (d 0 (d 0 + n (d ⋆ )) • log N )and the maximal width isd max ≤ d ⋆ max + N 3/4 • H (L S (h ⋆ )) 3/4 • polylog (N ) + O (d 0 • log (N )) .Proof idea. We explicitly construct a NN with the desired properties. We can choose a 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 (1) . This is illustrated in Figure 2 . 4 Tempered overfitting of min-size and random interpolators𝑑 0 𝑑 1 ⋆ 𝑑 2 ⋆ 𝑑 3 ⋆ (a) A teacher model h ⋆ . 𝑑 0 ሚ 𝑑 1 ሚ 𝑑 2 ሚ 𝑑 3 (b) A NNIn 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, we 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 the sake of readability, let us define the marginal peak probability of the distribution.Definition 4.1 (Peak marginal probability). D max ≜ max x∈X P (X,Y )∼D (X = x).Our results in this section focus on cases where the number of training samples isN = ω d 2 0 log d 0 and N = o 1/ √ D max .In such regimes, the data consistency probability is high 4 and our bounds are meaningful. Note that given the binarization of the data, N = o 1/ √ D max implies an exponential upper bound of N = o 2 d0/2 , achieved by the uniform distribution, i.e., when D max = 2 -d0 . Due to the exponential growth of the sample space w.r.t. the input dimension, we find this assumption to be reasonable. Also, N = ω d 2 0 log d 0 implies that the input dimension cannot be arbitrarily large, but may still be non trivially small (see comparison to previous work in Section 5).(d) is at most O(S 2 d 0 + Sd 2 0 ).Proof. Let us define the cost of a layer in an LT L circuit to be the sum of the absolute values of the weights in that layer, so the size of the circuit is the sum of the costs. Lemma D.5 implies thatC 1 • C 0 = C ′ 1 • C ′ 0 ,where C ′ 0 is a depth-one binary threshold network and C ′ 1 is an LT L circuit in which the first layer has cost at most S • (d 0 + 2) and all subsequent layers have cost at most S.To complete the proof, let us show by induction on L that in general, if C ′ 0 is a depth-one binary threshold network and C ′ 1 is an LT L circuit in which the layers have costs S 1 , S 2 , . . . , S L , then ∈ {0, 1}, then we make |w| many copies of the appropriate output gate of C, negate them if w < 0, and then split the wire into |w| many wires, each with weight +1. This process has no effect on the cost of C 3 . The process could potentially increase the width of the output layer of C, but its width will not exceed S L , the cost of C 3 . After this modification, we can simply think of C 3 as one more layer in our binary threshold network. Lemma D.9 follows immediately from Lemmas D.15 and D.16.C ′ 1 • C ′ 0 canIn this subsection, we will use the k-wise independent generators that we developed in 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 α, ϵ ∈ (0, 1). Assume that 1/R ≤ α ≤ 1-1/R. Let V be the class of functions V : {0, 1} R → {0, 1} that can be expressed as a conjunction of literals. There exists a generator G : {0, 1} r → {0, 1} R satisfying the following.d max is at most O(T • log 3 R + a + d 0 • log R).3. The total number of weights w (d) is at mostaT + O(T • log 4 R + d 2 0 • log R + d 0 • log 2 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 C 0 (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 O(d 0 • log R) and the output layer has width O(log R).Let z = C 0 (x) ∈ {0, 1} log R , and think of z as a number z ∈ {0, 1, . . . , R -1}. Our next goal is to compute the (log T )-bit binary expansion of the unique j * ∈ {0, 1, . . . , T -1} such that z ∈ I j * .To do so, for each position i ∈ {0, 1, . . . , log T -1}, let S i be the set of j ∈ {0, 1, . . . , T -1} such that j has a 1 in position i of its binary expansion. We have a disjunction, over all j ∈ S i , of the DNF computing g Ij from Lemma D.20. We also compute all the negations of the bits of j * , and we also copy z. Altogether, this is a depth-two network where the hidden layer has widthO(T • log T • log 2 R) = O(T • log 3 R) and the output layer has width O(log R).Our final goal is to compute g(z), which can be written in the form g ′ (j * ) since g is constant on each subinterval. We use a "brute-force DNF" to compute g ′ . First, for every j ∈ {0, 1, . . . , T -1}, we have an AND gate that checks whether j * = j. Then each output bit of g ′ is a 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 a + log R.The numbers ℓ 0 , . . . , ℓ T partition the interval[0, R) into subintervals, namely [0, R) = [ℓ 0 , ℓ 1 ) ∪ [ℓ 1 , ℓ 2 ) ∪ • • • ∪ [ℓ T -1 , ℓ T ). Define g : {0, 1, . . . , R -1} → {0, 1}a by the rule g(z) = w j where j is such that z ∈ [ℓ j , ℓ j+1 ). Then g is constant on each subinterval [ℓ j , ℓ j+1 ), so we may apply Lemma D.21 to obtain a depth-6 binary threshold network C 1 : {0, 1} d0 → {0, 1} a+log R computing the function C(x) = (g(C 0 (x)), C 0 (x)). In this network, every layer has width at mostO(T • log 3 R + a + d 0 • log R) = log 3/4 (1/ϵ) • polylog R + O(d 0 • log R),and the total number of weights is at mostaT + O(T • log 4 R + d 2 0 • log R + d 0 • log 2 R + a • log R) ≤ log(1/ϵ) + log 3/4 (1/ϵ) • polylog R + O(d 2 0 • log R + d 0 • log 2 R). Let z = C 0 (x), and let w = g(z). Our remaining goal is to compute G(σ) z , which is equal to G 0 (hash(w)) z . To do so, we use the network guaranteed to exist by Lemma D.17. This network, which we call C 2 , has depth 8. Every layer in this network has width at mosta • log(1/ϵ 0 ) • polylog R = log(1/ϵ) • polylog R. The total number of weights in this network is at most (log(1/ϵ 0 ) • a 2 + log 2 (1/ϵ 0 ) • a) • polylog R = log 3/4 (1/ϵ) • polylog R.Composing C 2 with C 1 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 ∈ N and any function V : {0, 1} n → {0, 1}, we write E(V ) to denote the quantity P y∼Ber(α) n (V (y) = 1).Fix any V ∈ V such that E(V ) > ϵ. Since V is a conjunction of literals, we can write V in the form V (y) = V 0 (y 0 ) • V 1 (y 1 ) • • • V R-1 (y R-1 ) for some functions V 0 , V 1 , . . . , V R-1 : {0, 1} → {0, 1}. For each 0 ≤ a ≤ b ≤ R -1, define V a•••b = V a • V a+1 • • • V b .We inductively define numbers 0 = ℓ 0 ≤ ℓ 1 ≤ • • • ≤ ℓ T as follows. Assume that we have already defined ℓ 0 , . . . , ℓ i . Let ℓ i+1 be the smallest integer in {ℓ i + 1, . . . , R -1} such thatE(V ℓi•••ℓi+1-1 ) ≤ ϵ 1/T , or let ℓ i+1 = R if no such ℓ i+1 exists. Define V (i) = V ℓi•••ℓi+1-1 . Observe that ℓ T = R, because otherwise we would have ϵ < E(V ) ≤ T -1 i=0 E(V i ) ≤ (ϵ 1/T ) T = ϵ, a contradiction. Furthermore, E(V i ) > ϵ 1/T /R = 2ϵ 0 , because each literal in V is satisfied with probability at least min{α, 1 -α} ≥ 1/R. Therefore, if we define S i = {u ∈ {0, 1} r0 : V i (G 0 (u) ℓi•••ℓi+1-1 ) = 1} and ρ i = |S i |/2 r0 , then the correctness of G 0 ensures that ρ i ≥ ϵ 0 .Next, we will show that there exist hash, w 0 , . . . , w T -1 such that for every i, we have hash(w i ) ∈ S i . To prove it, pick hash ∈ H at random. For each i ∈ {0, 1, . . . , T -1} and each w ∈ {0, 1} a , let X i,w be the indicator random variable for the "good" event hash(w) ∈ S i . Define X i = w∈{0,1} a X i,w . Then for every i, by pairwise independence, we haveE(X i ) = 2 a • ρ i and Var(X i ) = 2 a • ρ i • (1 -ρ i ) ≤ 2 a • ρ i .Therefore, by Chebyshev's inequality,P(X i = 0) ≤ 1 2 a • ρ i ≤ 1 2 a • ϵ 0 < 1 R .Consequently, by the union bound over all i, there is a nonzero chance thatX 0 = X 1 = • • • = X T -1 =0, in which case there exist w 0 , . . . , w T -1 such that hash(w i ) ∈ S i for every i.At this point, we have constructed our seed σ = (hash, w 0 , . . . , w T -1 , ℓ 0 , . . . , ℓ T ). By the construction of G, we have V (G(σ)) = 1.Theorem 3.1 readily follows from Theorem D.22, as we now explain.Recall Theorem 3.1. Let f : {0, 1} d0 → {0, 1, ⋆} be any function. 9 Let N = |f -1 ({0, 1})| andN 1 = |f -1 (1)|.There exists a depth-14 binary threshold network h : {0, 1} d0 → {0, 1}, with widths d, satisfying the following.1. h is consistent with f , i.e., for every x ∈ {0, 1} d0 , if f (x) ∈ {0, 1}, then h(x) = f (x).2. The total number of weights in h is at most(1 + o(1)) • log N N1 + poly(d 0 ). More precisely, w d = log N N 1 + log N N 1 3/4 • polylog N + O(d 2 0 • log N ) . 
interpolating a noisy training set: 
 Our main generalization results rely on a key technical result, which shows how to memorize any consistent training set generated according to our noisy teacher model. We prove that the memorizing "student" NN can be small enough to yield meaningful generalization bounds in the next sections.We begin by noticing that under a teacher model h ⋆ (Assumption 2.4), the labels of a consistent dataset S (Def. 2.5) can be decomposed asEQUATIONwhere f : {0, 1} d0 → {0, 1} indicates a label flip in the i th example, and can be defined arbitrarily for x / ∈ S. Motivated by this observation, we now show an upper bound for the dimensions of a 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} d0 → {0, 1, ⋆} be any function. 2Let N = |f -1 ({0, 1})| and N 1 = |f -1 (1)|. There exists a depth-14 binary threshold network h : {0, 1} d0 → {0, 1}, with widths d, satisfying the following.1. h is consistent with f , i.e., for every x ∈ {0, 1} d0 , if f (x) ∈ {0, 1}, then h(x) = f (x).(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) z . In Lemma D.9, instead of describing a network that computes the function (u, z) → G(u) z , we describe a network C satisfying G(hash(w)) z = PARITY(C(w, z)). The only reason for this more complicated statement is that it 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 a Boolean circuit model that is closely related to, but distinct from, the "binary threshold network" model in which we are interested. We introduce the circuit model next. Definition D.11 ( LT L circuits). An LT L circuit is defined just like a depth-L binary threshold network (Definition 2.1), except that we allow arbitrary integer weights (W (l) ∈ Z d l ×d l-1 ); we allow arbitrary integer thresholds (b (l) ∈ Z d l ); and we do not allow any scaling (γ (l) = 1 d l ). The size of the circuit is the sum of the absolute values of the weights, i.e.,L l=1 d l i=1 d l-1 j=1 |W (l) ij |.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, 73, 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 ∈ N, there exists an LT 4 circuit of size poly(n) that computes the product of n given n-bit integers.By a standard trick [26] , Theorem D.13 implies circuits of the same complexity that compute the iterated product of polynomials over F 2 . We include a proof sketch for completeness. Corollary D.14 (Iterated multiplication of polynomials over F 2 ). For every n ∈ N, there exists an LT 4 circuit of size poly(n) that computes the product of n given polynomials in F 2 [x], 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 Z, say q 1 (x), . . . , q n (x). If we evaluate one of these polynomials on a power of two, say q i (2 s ), and then write the output in binary, the resulting string consists of the coefficients of q i , with s -1 zeroes inserted between every two bits. Therefore, by using the poly(ns)-size circuit of Theorem D.13 (with some of its inputs fixed to zeroes), we can compute the product q 1 (2s ) • q 2 (2 s ) • • • q n (2 s ) = q(2 s ), where q = q 1 • q 2 • • • q n .Every coefficient of q is a nonnegative integer bounded by n n , so if we choose s = ⌈n log n⌉, then the binary expansion of q(2 s ) 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.At this point, we are ready to construct a circuit that computes a k-wise uniform generator. The construction is based on the work of Healy and Viola [36] .Lemma D.15 (A k-wise uniform generator in the LT L model). Let k, R ∈ N where R is a power of two. There exists a k-wise uniform generator G : {0, 1} r → {0, 1} R , an F 2 -linear functionC 0 : {0, 1} log R → {0, 1} O(log R•log k) , and an LT 4 circuit C 1 : {0, 1} O(k•log R) → {0, 1} O(k•log R)with the following properties.• The seed length is r = O(k • log R).• For every seed u ∈ {0, 1} r and every z ∈ {0, 1} log R , we haveG(u) z = PARITY(C 1 (u, C 0 (z))),thinking of z as a number in {0, 1, . . . , R -1}.• The circuit C 1 has size k • polylog R.Proof. If k ≥ R, the lemma is trivial, so assume k < R. We use the following standard example of a k-wise independent generator [22, 1] . Let n = log R, let E(x) ∈ F 2 [x] be an irreducible polynomial of degree n, and let F 2 n be the finite field consisting of all polynomials in F 2 [x] modulo E(x). The seed of the generator is interpreted as a list of field elements: u = (p 0 , p 1 , . . . , p k-1 ) ∈ F k 2 n . Each index z ∈ {0, 1, . . . , R-1} can be interpreted as a field element z ∈ F 2 n . The output of the generator is given byG(u) z = the lowest order bit of p 0 • z 0 + p 1 • z 1 + • • • + p k-1 • z k-1 ,where the arithmetic takes place in F 2 n .To study the circuit complexity of this generator, let us first focus on a single term p i • z i . Since we are thinking of z as a field element z ∈ F 2 n , we can also think of it as a polynomial z(x) ∈ F 2 [x] of degree less than n. Write z(x) = n-1 j=0 z j • x j . We compute the power z i by a "repeated squaring" approach. Write i = m∈M 2 m , where M ⊆ {0, 1, . . . , ⌊log i⌋}. Thenp i (x) • z(x) i = p i (x) • m∈M   n-1 j=0 z j • x j   2 m = p i (x) • m∈M n-1 j=0 z j • x j•2 i ,since we are working in characteristic two. For each m ∈ M and each j < n, let e m,j (x) = x j•2 m mod E(x), a polynomial of degree less than n. That way,EQUATIONThe function C 0 (z) computes n-1 j=0 z j • e m,j for every m ∈ {0, 1, . . . , ⌊log k⌋}. This function is F 2 -linear, because for each m ∈ {0, 1, . . . , ⌊log k⌋} and each s < n, the s-th bit of n-1 j=0 z j • e m,j is given by j:em,j,s=1 z j , where e m,j,s denotes the s-th coefficient of the polynomial e m,j .Next, the circuit C 1 applies k copies of the iterated multiplication circuit from Corollary D.14, in parallel, to compute the polynomial on the right-hand side of (10) for each 0 ≤ i < k. Each iterated multiplication circuit has size polylog R, so altogether, C 1 has size k • polylog R.0 , r 1 , . . . , r k-1 ∈ F 2 [x], each of degree O(n log k), such that r i (x) ≡ p i (x) • z(x) i (mod E(x)). Next, we need to sum these terms up, reduce mod E(x), and output the lowest-order bit. For each j ≤ O(n log k), let r ij be the x j coefficient of r i . Our circuit needs to output the lowest-order bit ofk-1 i=0 r i mod E(x) = k-1 i=0 O(n log k) j=0 r ij • e 0,j .Now, we are working over characteristic two, so means bitwise XOR. In other words, the output is given by j:e0,j,0=1 k-1 i=0 r ij , i.e., it is the parity function applied to some subset of the output bits of C 1 . To complete the proof, modify C 1 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 L circuits and binary threshold networks. We do so via the following lemma.Lemma D.16 (Simulating LT L circuits using binary threshold networks). Let L ≥ 1 be a constant. Let C 0 : {0, 1} d0 → {0, 1} d1 be an F 2 -affine function, and let C 1 : {0, 1} d1 → {0, 1} d2 be an LT L circuit of size S. Then the composition C 1 • C 0 can be computed by a depth-(L + 1) binary threshold network with widths d satisfying the following.1. The maximum width d max is at most S • (d 0 + 2).(log N N1 ) 3/4 • poly(d 0 ). More precisely, dmax = log N N 1 3/4 • polylog N + O(d 0 • log N ) . Proof. Let R = 2 2⌈log N ⌉ . Let C 0 : {0, 1} d0 → {0, 1} log R be an F 2 -affine function that is injective on X ; such a function is guaranteed to exist by Lemma D.4. Define V : {0, 1} R → {0, 1} by the ruleV (y) = 1 ⇐⇒ ∀x ∈ X , y C0(x) = f (x).This function V is a conjunction of N 1 variables and N -N 1 negated variables.If N 1 ∈ {0, N }, then the theorem is trivial, because we can take h to be a constant function. Assume, therefore, that 0< N 1 < N . Let α = N 1 /N , and note that 1/R ≤ α ≤ 1 -1/R. Let ϵ = 1 2 α N1 • (1 -α) N -N1 = 2 -H(α)•N -1, and note thatP y∼Ber(α) R (V (y) = 1) = 2ϵ.Let G : {0, 1} r → {0, 1} R be the HSG from Theorem D.22. There exists a seed σ ∈ {0, 1} r such that V (G(σ)) = 1. Our network h computes the function h(x) = G(σ) C0(x) . Since V (G(σ)) = 1, we must have h(x) = f (x) for every x ∈ X .To bound the computational complexity, observe that log(1/ϵ) = H(α) • N + 1 ≤ log N N1 + O(log N ). Therefore, every layer of h has width at mostlog N N 1 3/4 • polylog N + O(d 0 • log N ),and the total number of weights in h is at mostlog N N 1 + log N N 1 3/4 • polylog N + O(d 2 0 • log N + d 0 • log 2 N ).Finally, we have N ≤ 2 d0 , so the last term above can be simplified to O(d 2 0 • log N ). Remark D.23. In Theorem 3.1, the weights bound has an O(d 2 0 • log N ) term. This term is close to optimal; see Appendix E for further details.In what follows, we denote the activation function σ (x) = I {x > 0}. Lemma D.24 (XOR NN). The XOR function can be implemented with a single-hidden-layer fully connected binary threshold network with input dimension 2 and c XOR parameters byh XOR x 1 x 2 = σ 1 ⊙ ( 1 1 ) • σ 1 -1 ⊙ 1 1 1 1 x 1 x 2 + 0 2 -1 .Proof. We can simplify h XOR ash XOR x 1 x 2 = σ ( 1 1 ) • σ 1 -1 ⊙ 1 1 1 1 x 1 x 2 + 0 2 -1 = σ ( 1 1 ) • σ x 1 + x 2 -x 1 -x 2 + 2 -1 = σ (σ (x 1 + x 2 ) + σ (2 -x 1 -x 2 ) -1) = I {I {x 1 + x 2 > 0} + I {x 1 + x 2 < 2} > 1} = I I x 1 x 2 ̸ = 0 0 + I x 1 x 2 ̸ = 1 1 > 1 = I x 1 x 2 ̸ = 0 0 and x 1 x 2 ̸ = 1 1 = XOR (x 1 , x 2 ) .Remark D.25. Notice that the function Id : {0, 1} → {0, 1} defined as Id (0) = 0 and Id (1) = 1 can be implemented using any depth L network with a single input dimension and c Id • L parameters.Following this remark, for simplicity we shall assume that h 1 and h 2 in 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.Proof. We prove the claim by induction. For l = 1 we haved 0 = d (1) 0 = d (2) 0 and h (1) θ (x) = γ 1 ⊙ σ W 1 h (0) θ (x) + b 1 =   1 d ⋆ 1 1 d f 1 0 d1-d ⋆ 1 -d f 1   ⊙ σ       W (1) 1 W (2) 1 W1 1    x +    b (1) 1 b (2) 1 b1       =     σ W (1) 1 x + b (1) 1 σ W (2) 1 x + b (2) 1 0 d1-d (1) 1 -d (2) 1     =    h (1) 1 (x) h (1) 2 (x) 0 d1-d ⋆ 1 -d f 1    .Assume that for some l ≤ L ′ we haveh (l-1) θ (x) =    h (l-1) 1 (x) h (l-1) 2 (x) 0 d l -d ⋆ l -d f l    . Then, h (l) θ (x) = γ l ⊙ σ W l h (l-1) θ (x) + b l =   1 d (1) l 1 d (2) l 0 d l -d (1) l -d (2) l   ⊙σ         W (1) l 0 d (1) l ×d (2) l-1 W1 l 0 d (2) l ×d (1) l-1 W (2) l W2 l W3 l W4 l W5 l        h (l-1) 1 (x) h (l-1) 2 (x) 0 d l -d (1) l -d (2) l   +    b (1) l b (2) l bl        =     σ W (1) l h (l-1) 1 (x) + b (1) l σ W (2) l h (l-1) 2 (x) + b (2) l 0 d l -d (1) l -d (2) l     =    h (l) 1 (x) h (l) 2 (x) 0 d l -d (1) l -d (2) l    .It is left to show that the claim holds for l > L ′ . By the previous steps, h(L ′ ) θ (x) = h 1 (x) h 2 (x) 0 d L ′ -2.Under the assumptions onW L ′ +k , b L ′ +k and γ L ′ +k , k = 1, 2 it holds that h (L ′ +2) θ (x) = h 1 (x) ⊕ h 2 (x) 0 d L ′ -1 .Under the assumptions on layers l > L ′ + 2,h (l) θ (x) = h 1 (x) ⊕ h 2 (x) 0 d l -1 .In particular, assuming thatd L = 1, h θ (x) = h 1 (x) ⊕ h 2 (x).Corollary D.27. Let h 1 , h 2 be networks with depths L 1 , L 2 and widths d (1) , d (2) . Then h 1 ⊕ h 2 can be implemented with a network h of depth L = max {L 1 , L 2 } + 2 and widths d such that w (d) ≤ w d (1) + w d (2) + 2d (2) max • n d (1) + O(1) and d max ≤ d (1) max + d (2) max .Proof. Following D.25 we assume shall assume that L 1 = L 2 = L. We know from D.26 that there exists a network h with dimensions d = d (1) + d (2) , 2, 1 such that h = h 1 ⊕ h 2 . ThereforeEQUATIONEQUATIONl-1 + d(2)l-1 + O(1)= d(1)EQUATIONl-1 + d(2)EQUATIONl d(2)EQUATIONl d(2)EQUATIONl d(1)l-1 + O(1)= w d (1) + w d (2) EQUATION(2)EQUATIONl-1 + O(1)≤ w d (1) + w d (2) EQUATIONl d (2) max + d (2) max d(1)l-1 + O(1)= w d (1) + w d (2) + d (2) maxEQUATIONl-1 + O(1)≤ w d (1) + w d (2) + 2d (2) max • n d (1) + O(1) .In addition, d max ≤ d (1) max + d (2) max and n (d) = n d (1) + n 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 h (i.e., L S (h) = 0) of depth L = max {L ⋆ , 14} + 2 and dimensions d, such that the number of edges isw (d) ≤ w (d ⋆ ) + N • H (L S (h ⋆ )) + 2n (d ⋆ ) N 3/4 H (L S (h ⋆ )) 3/4 polylogN + O (d 0 (d 0 + n (d ⋆ )) • log N )and the dimensions ared max ≤ d ⋆ max + N 3/4 • H (L S (h ⋆ )) 3/4 • polylog (N ) + O (d 0 • log (N )) .Proof. We use Corollary D.27 with h 1 = h ⋆ and h 2 = hS , the noise memorizing network from Theorem 3.1, to getw (d) ≤ w (d ⋆ ) + w dS + 2 dS,max • n (d ⋆ ) + O(1) ≤ w (d ⋆ ) + log N N 1 + log N N 1 3/4 • polylog N + O(d 2 0 • log N ) + 2n (d ⋆ ) log N N 1 3/4 • polylog N + O(d 0 • log N ) + O(1) .Using Stirling's approximationlog N N 1 = N • H N 1 N + O (log (N )) = N • H (L S (h ⋆ )) + O (log (N )) . Therefore w (d) ≤ w (d ⋆ ) + N • H (L S (h ⋆ )) + O (log (N )) + N 3/4 • H (L S (h ⋆ )) 3/4 • polylog N + O d 2 0 • log N + 2n (d ⋆ ) N 3/4 • polylog N + O (d 0 • log N ) = w (d ⋆ ) + N • H (L S (h ⋆ )) + 2n (d ⋆ ) N 3/4 H (L S (h ⋆ )) 3/4 polylogN + O (d 0 (d 0 + n (d ⋆ )) • log N ) .The bound of d max is derived similarly.In Theorem 3.1, the wire bound has an O(d 2 0 • log N ) term. (Recall that d 0 is the input dimension and N is the domain size.) In this section, we discuss (a) approaches for improving this term and (b) a lower bound showing that it cannot be significantly improved. Proof. Pick W ∈ {±1} d1×d0 uniformly at random. We will show that there is a nonzero chance that C 0 is injective on X . Let x, x ′ be any two distinct points in X . Consider a single row W i of W. Let E be the good event thatW i • (x ⊙ x ′ ) ∈ {0, 1}. Then Pr[E] ≥ Ω(1/ √ d 0 ), because we are taking a simple one-dimensional random walk of length at most d 0 . Conditioned on E, there is an Ω(1) chance thatI {W i • x > 0} ̸ = I {W i • x ′ > 0},because we are taking two independent one-dimensional random walks starting from either 0 or 1, at least one of which has nonzero length, and asking whether they land on the same side of 1/2. Therefore, unconditionally,Pr[I {W i • x > 0} ̸ = I {W i • x ′ > 0}] ≥ Ω(1/ √ d 0 ). Consequently, by independence,Pr[C 0 (x) = C 0 (x ′ )] ≤ (1 -Ω(1/ d 0 )) d1 < 1/N 2 ,provided we choose a suitable valued 1 = O( √ d 0 • log N ).By the union bound over all pairs x, x ′ , it follows that there is a nonzero chance that C 0 is injective on X .There are two approaches to using Lemma E.1 for the sake of improving the O(d 2 0 • log N ) term in Theorem 3.1.• One approach would be to start with a trivial layer that copies the input x ∈ {0, 1} d0 as well as computing all the negations of the bits of x; then we have a layer that applies the function C 0 from Lemma E.1 (using negated variables to implement -1 weights); and then we continue with the network of Theorem 3.1. The net effect is that the depth has increased by two (so the network now has depth 16 instead of 14), and in the weights bound, the O(d 2 0 • log N ) term has been slightly improved to O(d 2 0 + d3/2 0 • log N + d 0 • log 3 N ).• A second approach would be to change the model. If we permit ternary edge weights (i.e., weights in the set {-1, 0, 1}), then the function C 0 of Lemma E.1 can be implemented as the very first layer of our network, and then we can continue with the network of Theorem 3.1. Note that 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(d 2 0 • log N ) term of Theorem 3.1 would be improved to O(d We now show that the O(d 2 0 • N ) term in Theorem 3.1 cannot be improved something better d 2 0 , if we insist on using the "binary threshold network" model. The argument is elementary. Proposition E.2 (d 2 0 wire lower bound). For every d 0 ∈ N, there exists a partial Boolean function f : {0, 1} d0 → {0, 1, ⋆}, defined on a domain X of size d 0 + 1, such that for every binary threshold network h, if h agrees with f everywhere in its domain and d is the widths of h, then w (d) ≥ d 2 0 .3/2 0 • log N + d 0 • log 3 N ).Proof. For each i ∈ {0, 1, . . . , d 0 }, let x (i) be the vector consisting of i zeroes followed by d 0 -i ones. Let X = {x (i) : 0 ≤ i ≤ d 0 }, and letf (x) = PARITY(x) if x ∈ X ⋆ otherwise.For the analysis, let h be a fully connected binary threshold network that agrees with f on all points in X . Consider the layer immediately following the input layer. Each node g in this layer computes either a monotone Boolean function or an anti-monotone Boolean function of the input variables. Therefore, there is at most one value i ∈ {1, 2, . . . , d 0 } such that g(x (i-1) ) ̸ = g(x (i) ). On the other hand, for every i ∈ {1, 2, . . . , d 0 }, we have h(x (i-1) ) ̸ = h(x (i) ), and hence there must be at least one node g in this layer such that g(x (i-1) ) ̸ = g(x (i) ). Therefore, there are at least d 0 many nodes g.Thus, the first two layers of h both have widths of at least d 0 , demonstrating that h has at least d 2 0 many weights.Denote by H BTN 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 are sorted by the bias and neuron scaling terms (b li , γ li ). 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 d l < d l-1 , then list each of the bias terms as a number with O (log (d l-1 )) bits plus 2 bits for the scaling term for a total of O (d l (log(d l-1 ) + 2)) ≤ O d l d l-1 log (d l-1 ), where the inequality is due to d l < d l-1 .• If d l ≥ d l-1 , then we encode the bias and scaling terms by listing the number of times each pair (b li , γ li ) ∈ {-d l-1 , . . . , d l-1 -1} × {-1, 0, 1} appears in (b l , γ l ) (recall that the neurons are ordered according to these pairs). Each pair can appear at most d l times and so requires O (log (d l )) bits to encode for a total ofO (6d l-1 log (d l )) = O (d l-1 log (d l )) ≤ O d l d l-1 log (d l d l-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 Throughout this subsection, we use A (S) to denote the interpolating NN of depth L, A L (S).d l d l-1 + O d l d l-1 log (d l d l-1 ) bits for a total of L l=1 d l d l-1 + O d l d l-1 log (d l d l-1 ) = w + O L l=1 d l d l-1 log (d l d l-1 ) ≤ w + O L l=1 d l d l-1 log L l=1 d l d l-1 ≤ w + O L l=1 d l d l-1 log (w) = w + O log (w) • L L l=1 1 L d l d l-1 [Jensen] ≤ w + O   log (w) • L L l=1 1 L d l d l-1   = w + O   log (w) • √ L L l=1 d l d l-1   = w + O log (w) • √ L √ w = w + O log (w) • √ w .Lemma Let L 16 be fixed. ThenI (S; A (S)) ≤ w (d ⋆ ) + N •H (ε ⋆ ) + O (δ (N, d 0 , d ⋆ ))whereδ (N, d 0 , d ⋆ ) = n (d ⋆ )•N 3/4 H (ε ⋆ ) 3/4 • polylog (N + n (d ⋆ ) + d 0 ) + d 2 0 • log N + d 0 n (d ⋆ ) log (n (d ⋆ ) + N + d 0 ) 3/2 .Proof. Using Shannon's source coding theorem:I (S; A (S)) ≤ H (A (S)) ≤ E |A (S)| ,where |A (S)| denotes the number of bits in the encoding of A (S). Following Corollary 3.4, for a consistent S, A (S) is a network with fixed depth and at mostw ≜ w (d ⋆ ) + N • H (L S (h ⋆ )) + 2n (d ⋆ ) N 3/4 H (L S (h ⋆ )) 3/4 polylogN + O (d 0 (d 0 + n (d ⋆ )) • log N )weights and therefore, using the result from Corollary F.2 and w (d⋆ ) ≤ d 0 + n (d ⋆ ), |A (S)| ≤ w + O √ w log (w) = w (d ⋆ ) + N • H (L S (h ⋆ )) +O n (d ⋆ )•N 3/4 H (L S (h ⋆ )) 3/4 •polylog (N +n(d ⋆ )+d 0 ) +O d 2 0 •logN +d 0 n (d ⋆ ) log (n (d ⋆ )+N +d 0 ) 3/2 = w (d ⋆ ) + N • H (L S (h ⋆ )) + O δ (N, d 0 , d ⋆ )where we grouped all lower order terms in δ. In case S is inconsistent, A (S) = ⋆ so |A (S)| = O (1).Taking the expected value and using Jensen's inequality givesE |A (S)| = E [|A (S)| • I {inconsistent S}] + E [|A (S)| • I {consistent S}] ≤ O(1) + E I {consistent S} ≤1 w (d ⋆ ) + N • H (L S (h ⋆ )) + O δ (N, d 0 , d ⋆ ) ≥0 ≤ O(1) + E w (d ⋆ ) + N • H (L S (h ⋆ )) + O δ (N, d 0 , d ⋆ ) [Jensen] ≤ w (d ⋆ ) + N • H (E [L S (h ⋆ )]) + O (δ (N, d 0 , d ⋆ )) = w (d ⋆ ) + N • H (ε ⋆ ) + O (δ (N, d 0 , d ⋆ )) .Then, using Lemma A.6, we get,E S [L D (A (S)) | consistent S] ≤ 1 -2 - H(ε ⋆ ) S (consistent S) + O (C min (N, d , d )) .The bound is derived using the following observation. Since for a RV X in [0, 1] and a binary RV Y we haveE[X] = E[X | Y ] P(Y ) ≤1 + E[X | ¬Y ] ≤1 P(¬Y ) ≤ E[X | Y ] + P[¬Y ] ,we conclude the proof asE S [L D (A (S))] ≤ E S [L D (A (S)) | consistent S] + P (inconsistent S) .For the independent noise setting, we combine Lemma C.3 and Lemma F.3 to get|E S [L D (A (S)) | consistent S] -2ε ⋆ (1 -ε ⋆ )| ≤ (1 -2ε ⋆ ) O C (N ) + (N -1) D max 3 ,whereC (N ) = I (S; A (S)) -N • (H (ε ⋆ ) -P (inconsistent S)) N (1 -P (inconsistent S)) ≤ w(d ⋆ )+N •H(ε ⋆ )+O(δ(N,d0,d ⋆ ))-N •(H(ε ⋆ )-P(inconsistent S)) N (1-P(inconsistent S)) = O w(d ⋆ )+δ(N,d0,d ⋆ ) N + P (inconsistent S) P (consistent S) = O (C min (N, d 0 , d ⋆ )) + P (inconsistent S) P (consistent S)Finally, using the inequality from Lemma C.4, we have, For h ̸ = ⋆, since L s (h) = 0 implies that s is consistent, we haveE S,A(S) [L D (A (S))] -2ε ⋆ (1 -ε ⋆ ) ≤ E S,A(S) [L D (A (S)) | consistent S] -2ε ⋆ (1 -ε ⋆ ) + P(inconsistent S)dν (h) ≜ s dp (s, h) = s I {L s (h) = 0} p s dP (h) dD N (s) = s:ps>0 I {L s (h) = 0} p s dP (h) dD N (s) = dP (h) s:ps>0 I {L s (h) = 0} p s dD N (s) = dP (h) E S∼D N I {p S > 0} p S I {L S (h) = 0} .where, for ease of notation, we use the convention that I{ps>0} ps = 0 when p s = 0. Denotingπ (h) ≜ E S∼D N I {p S > 0} p S I {L S (h) = 0} , we get dν (h) = dP (h) π (h) .Notice that if there exists some s ∈ supp D N such that L s (h) = 0 then π (h) > 0. Using the definition of the mutual information:I (S; A (S)) = s h∈H∪{⋆} dp (s, h) log dp (s, h) dν (h) dD (s) = s:ps=0 dp (s, ⋆) log dp (s, ⋆) dν (⋆) dD (s) + s:ps>0 h∈H dp (s, h) log dp (s, h) dν (h) dD (s) = s:ps=0 dD (s) log dD (s) P S (inconsistent S) dD (s) + s:ps>0 h:Ls(h)=0 1 p s dP (h) dD (s) log 1 ps dP (h) dD (s) dP (h) π (h) dD (s) = s:ps=0 dD (s) log 1 P S (inconsistent S) + s:ps>0 h:Ls(h)=0 1 p s dP (h) dD (s) log 1 p s π (h).Simplifying each term separately, the first sum immediately simplifies to I {L s (h) = 0} p s dD (s) =π(h) = - s:ps>0 log (p s ) dD (s) - h:π(h)>0 π (h) log (π (h)) dP (h) = -E S [log (p S ) I {p S > 0}] -E h∼P [I {π (h) > 0} π (h) log (π (h))] = E S log 1 p S | p S > 0 P S (p S > 0) + E h∼P [-π (h) log (π (h)) I {π (h) > 0}]≤1/e ln 2 Proof. We prove this by counting the number of constrained parameters in Θ BTN d; h . The number of constrained weights isd1 d 0 + L l=2 dl dl-1 ,which is exactly w d . In addition, there are n (d) constrained bias terms, and n (d) constrained scaling terms. In total, after accounting for the quantization of each parameter, this means thatΘ BTN d; h |Θ BTN (d)| ≥   2 w( d) weights • 3 n(d) scaling terms • L l=1 (2d l-1 ) d l   -1 so -log Θ BTN d; h |Θ BTN (d)| ≤ w d + n d • log 3 + L l=1 dl • log (2d l-1 ) ≤ w d + n d • log 3 + n (d) • log (2d max + 2d 0 ) = w d + O (n (d) • log (d max + d 0 )) .Combining Lemma F.7 with Assumption 2.4, and Corollary 3.4 gives the following lemma. Remark F.9. Unlike the bounds for min-size interpolators, there is no H (ε tr ) 3/4 term multiplying the N 3/4 term. This is because the architecture of random interpolators is fixed, so in our setting we must assume that it is wide enough in order to guarantee interpolation of any noisy training set.Proof. Notice that for posterior sampling with uniform distribution over parameters, the interpolation probability p S can be lower bounded as Together with N = o 1/D max we get the desired form of the bounds.Proof. Corollary 3.4 implies that there exist c 1 , c 2 > 0 such that a student NN satisfying (11) can interpolate any consistent dataset, and so posterior sampling is interpolating for all consistent datasets.We start by proving the bound for arbitrary label noise. First, we notice that εtr = P(Y 1 ̸ = h ⋆ (X 1 ) | consistent S) = P(Y 1 ̸ = h ⋆ (X 1 ), consistent S) P (consistent S)≤ P(Y 1 ̸ = h ⋆ (X 1 )) P (consistent S) = ε ⋆ P (consistent S).The entropy function H is increasing in 0, 1 2 and achieves its maximum at 1 2 , so together with the inequality above, we get,H (ε tr ) ≤ H min ε ⋆ P(consistent S) , 1 2 = H ε ⋆ + min ε ⋆ P(consistent S) -ε ⋆ , 1 2 -ε ⋆ = H ε ⋆ + min ε ⋆ P(inconsistent S) P(consistent S) , 1 2 -ε ⋆ ≜∆ = H (ε ⋆ + ∆) .Employing the concavity of the entropy function, we get, H (ε tr ) ≤ H (ε ⋆ + ∆) ≤ H(ε ⋆ ) + H ′ (ε ⋆ ) • ∆ ≤ H(ε ⋆ ) + H ′ (ε ⋆ ) • ε ⋆≤ 1 -2 -H(ε ⋆ ) + 2 1 2 N 2 D max 1 -1 2 N 2 D max + O (C rand (N )) ≤ 1 -2 -H(ε ⋆ ) + 2N 2 D max + O (C rand (N ))where in the last inequality we used t/ (1 -t) ≤ 2t for t ∈ [0, 1/2].Moving on to the independent noise setting, we combine Lemma F.5, Lemma F.8, and εtr ≤ ε ⋆ < 1 In this section, we show that our results apply to a model resembling "Dale's Law" [82] , 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. 2.1 is that neuron scaling is applied after the threshold activation. W (l) ∈ Q W l = {0, 1} d l ×d l-1 , γ (l) ∈ Q γ l = {-1, 0, 1} d l , b (l) ∈ Q b l = {-d l-1 + 1, . . . , d l-1 } d l .This mapping is defined recursively as g θ (x) = g (L) (x) where g (0) (x) = x , ∀l ∈ [L] g (l) (x) = γ (l) ⊙ I W (l) g (l-1) (x) + b (l) > 0 .Lemma G.2. Let g θ be an oBTN as in Def. G.1. Then there exists a BTN h θ ′ with the same dimensions and b ′(l) ∈ Q 2b l ≜ {-2d l-1 + 1, . . . , 2d l } such that h θ ′ ≡ g θ + s for s ∈ {0, 1} d L such that for all i = 1, . . . , d L , s i = 1 only if γ (L) i = -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 l = 1, . . . , L. For ease of notation, we denote C = g (l) and A = g (l-1) , as well as C ′ = h (l) , A ′ = h (l-1) . In addition, we omit the superscripts from the l th layer's parameters. Let i = 1, . . . , d l , then by the induction hypothesis there exists some a ∈ {0, 1} d l-1 such that A (x) = A ′ (x) -a, for all inputs x,C (x) i = γ i • I    b i + d l-1 j=1 w ij A (x) j > 0    = γ i • I    b i + d l-1 j=1 w ij A ′ (x) j -a j > 0    = γ i • I      b i - d l-1 j=1 w ij a j   + d l-1 j=1 w ij A ′ (x) j > 0    .If γ i = +1, choose γ ′ i = +1, and b ′ i = b i -d l-1j=1 w ij a j . Clearly, since w ij , a j ∈ {0, 1}, it holds that ′ i = 1 -b i - d l-1j=1 w ij a j soC (x) i = -1 + I    1 -   b i - d l-1 j=1 w ij a j   - d l-1 j=1 w ij A ′ (x) j > 0    = -1 + I    b ′ i + γ ′ i d l-1 j=1 w ij A ′ (x) j > 0    = C ′ (x) i -s iwith s i = 1. Finally, if γ i = 0, then C i is identically 0, so we can choose γ ′ i = b ′ i = s i = 0. Notice that this construction also proves the base case l = 1 where a = 0.Corollary G.3. Let Θ ′ be the set of oBTN parameters such that for all θ ∈ Θ ′ , g θ : {0, 1} d0 → {0, 1} d L . Then there exists a BTN, h as in Lemma G.2 such that g θ ≡ h.Proof. Let θ ∈ Θ ′ . Since g θ (x) ̸ = -1 for all x, there exist parameters θ ′ ∈ Θ ′ such that g θ ′ ≡ g θ , and γ ′(L) ≥ 0. Hence, by Lemma G.2 there exists a BTN h such that h ≡ g θ ′ , i.e., with s = 0.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 4.2 and Theorem 4.4 only logarithmically, meaning that we can apply the results to Def. G.1 without qualitatively changing them.As long as it has no repeated data points with opposite labels. See our Def.2.5 of consistent datasets.When f (x) = ⋆, the interpretation is that f is "undefined" on x, i.e., f is a "partial" function.A variant of the pseudorandom generator (PRG) concept.N = o 1/ √Dmax 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/|X |), and the inconsistency probability corresponds to the well-known birthday problem.Specifically, ε (Q) such that 1 -Q -H(ε(Q)) ≤ 1/2.We note that in most papers, the required number of quantization levels is implicit in the constructions, and is not discussed explicitly.One can relax the width requirement by strengthening the depth requirement; see Remark D.7.As most of the appendix deals with the modified learning rule, we use Ã (S) for the original one and A (S) for the modified one.When f (x) = ⋆, the interpretation is that f is "undefined" on x, i.e., f is a "partial" function.P S (consistent S) -O(Cmin(N,d0,d ⋆ )) . 
min-size interpolators: 
 We consider min-size NN interpolators of a 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 a natural and well-understood approach. Indeed, in such cases, generalization follows directly from standard VC-dimension bounds [4, 75] . However, when interpolating noisy data, the size of the returned model increases with the number of samples (in order to memorize the noise; see e.g., Vardi et 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 S and a fixed depth L, a min-size NN interpolator, or min-#weights interpolator, is a binary threshold network h (see Def. 2.1) that achieves L S (h) = 0 using a minimal number of weights. Recall that w(d) = L l=1 d l d l-1 and define the minimal number of weights required to implement a given hypothesis h,w L (h) ≜ min d∈N L w (d) s.t. h ∈ H BTN d .The learning rule is then defined asA L (S) ∈ argmin h w L (h) s.t. L S (h) = 0 .Theorem 4.2 (Tempered overfitting of min-size NN interpolators). Let D be a distribution induced by a noisy teacher of depth L ⋆ , widths d ⋆ , n(d ⋆ ) neurons, and a noise level of ε ⋆ < 1 /2 (Assumption 2.4). There exists c > 0 such that the following holds. Let S ∼ D N be a training set such thatN = ω n (d ⋆ ) 4 H (ε ⋆ ) 3 log (n (d ⋆ )) c + d 2 0 log d 0 and N = o( 1/D max ).Then, for any fixed depth L ≥ max {L ⋆ , 14} + 2, the generalization error of the min-size depth-L NN interpolator satisfies the following.• Under arbitrary label noise,E S [L D (A L (S))] ≤ 1 -2 -H(ε ⋆ ) + o (1). • Under independent label noise, |E S [L D (A L (S))] -2ε ⋆ (1-ε ⋆ )| = o (1).Here, o (1) indicates terms that become insignificant when the number of samples N is large. We illustrate these behaviors in Figure 1 . 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.Recent empirical [87, 20] and theoretical [13] works have shown that, somewhat surprisingly, randomly sampled deep NNs that interpolate a 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 a tempered overfitting behavior.Prior distribution. A distribution over parameters induces a prior distribution over hypotheses byP (h) = P θ (h θ = h) .We focus on the prior induced by the uniform prior over the parameters of binary threshold networks. Specifically, for a fixed depth L and dimensions d, we consider θ ∼ Uniform Θ BTN (d) . In other words, to generate h ∼ P, each weight, bias, and neuron scalar in 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 p S ≜ P (L S (h) = 0). When p S > 0, define the posterior distribution P S asEQUATIONWhen p S = 0, use an arbitrary P S . Finally, the posterior sampling rule is A d (S) ∼ P S .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, p S > 0 and P S is defined as in (2).Theorem 4.4 (Tempered overfitting of random NN interpolators). Let D be a distribution induced by a noisy teacher of depth L ⋆ , widths d ⋆ , n(d ⋆ ) neurons, and a noise level of ε ⋆ < 1 /2 (Assumption 2.4). There exists a constant c > 0 such that the following holds. Let S ∼ D N be a training set such thatEQUATIONthe generalization error of posterior sampling satisfies the following.• Under arbitrary label noise,E S,A d (S) L D A d (S) ≤ 1 -2 -H(ε ⋆ ) + O n (d) • log (d max + d 0 ) N .• Under independent label noise,E S,A d (S) L D A d (S) -2ε ⋆ (1-ε ⋆ ) ≤ O n (d) • log (d max + d 0 ) N .The proof and a detailed description of the error terms are given in Appendix F.2.Remarkably, note that the interpolating NN in the theorem might be highly overparameterized, and that for such NNs good generalization is not guaranteed by standard generalization bounds [4, 75] . This theorem complements a similar result by Buzaglo et al. [13] for the realizable setting.The overfitting behaviors described in this section are illustrated in Figure 1 .Proof idea. We extend the information-theoretical generalization bounds from [58] to this paper's setting in which label collisions in the datasets have a non-zero probability. In particular, we bound the interpolator'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 error. From the other direction, we bound the model's complexity from above by (1) its size in 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 a memorizing network used to bound the complexity of the min-size interpolator. In the following Figure 3 we illustrate how the interpolation probability p S can be bounded to induce a meaningful generalization bound.Figure 3 : Interpolating a dataset with an overparameterized student. We build on the construction from Figure 2 that memorizes a dataset using a subset of the parameters (blue, yellow, and red edges). Then, redundant neurons (gray) can be effectively ignored by setting their neuron scaling parameters (γ) to 0, leaving the redundant weights (gray edges) unconstrained. Thus, the interpolation probability p S can be bounded by a quantity exponentially decaying in the number of neurons n (d) rather than in the number of weights w (d) = ω (N ).Following Remark 3.2, the assumption N = ω d 2 0 log d 0 can be relaxed in some related architectures. For example, with a single additional layer of width O √ d 0 • log N and ternary weights in the first layer Q W 1 = {-1, 0, 1}, the requirement can be relaxed to N = ω d 3/2 0 log d 0 .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, lettingQ W l such that Q W l = Q and {0, 1} ⊆ Q W l, under the appropriate assumptions, we get thatE (S,A(S)) [L D (A (S))] ⪅ 1 -Q -H(ε ⋆ ) ,which is a meaningful bound for noise levels ε ⋆ ≤ ε (Q) for some ε (Q) < 1 /2. 5 Tighter results would require utilizing the additional quantization levels to achieve smaller dimensions of the interpolating network, and are left to future work. 
related work: 
 Benign and tempered overfitting. 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, 11, 5, 65, 67, 21, 47, 93, 86, 98, 44, 90, 19, 3, 76, 31] , kernel regression [51, 61, 53, 57, 72, 10, 60, 8, 50, 99, 6] , and linear classification [18, 91, 14, 66, 64, 76, 52, 85, 92, 25] . Moreover, several works proved benign overfitting in classification using nonlinear NNs [28, 29, 15, 49, 94, 95, 62, 48, 30, 46] . All the aforementioned benign overfitting results require high-dimensional settings, namely, the input dimension is larger than the number of training samples.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 1 ). 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 [43] . Manoj and Srebro [58] proved tempered overfitting for a learning rule returning short programs in some programming language. Finally, tempered overfitting is well understood for the 1-nearest-neighbor learning rule, where the asymptotic risk is roughly twice the Bayes risk [23] .Circuit complexity. + O(d 0 ) gates [17] .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 a 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 space-bounded derandomization [38] , among other ingredients.Our construction shows how noisy data can be interpolated using a small threshold NN with binary weights. It essentially requires memorizing the noisy examples. The task of memorization, namely, finding a 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 R d with a two-layer NN can be achieved using O ⌈ N d ⌉ 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 three-layer networks, O( √ N ) neurons suffice, but the number of parameters is still linear in N [39, 96, 89, 71] . Using deeper networks allows for memorization with a sublinear number of parameters [68, 88] . For example, memorization with networks of depth √ N requires only Õ( √ N ) 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, 88] , the number of bits required to represent the network is ω(N ). As a result, in this work we cannot rely on 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, 84, 20, 13] . Theisen et al. [84] studied the generalization of interpolating random linear and random features classifiers. Valle-Perez et al. [87] , Mingard et al. [63] considered the Gaussian process approximation to random NNs which typically requires networks with infinite width. Buzaglo et al. [13] provided a method to obtain generalization results for quantized random NNs of general architectures -possibly deep and with finite width, under the assumption of a narrow teacher model. A 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. 
extensions, limitations, and future work: 
 In this work, we focused on binary (fully connected) threshold networks of depth L ≥ 16 (Section 2.1) with binary input features (Section 2.2), 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, to NNs with higher weight quantization (see Remark 4.5), or to ReLU networks (since any threshold network with binary weights can be computed by a 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 3 /4 , which might be deemed impractical for real datasets. 7 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-interpolating models, depending on the training error. In addition, it is interesting to relate the generalization to the training loss, and not just to the training accuracy. Such extensions will require either broadening our generalization results or deriving new ones.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 D to denote the joint distribution over a finite sample space X × {0, 1} of the features and labels, ν to denote the marginal distribution of the algorithm, and p to denote the joint distribution of a training set S ∼ D N and the algorithm A (S). Specifically, the training set is a random elementS = {(X 1 , Y 1 ) , . . . , (X N , Y N )} ∼ D N where (X i , Y i ) is reserved for the i-th example in S. That is (X i , Y i ) 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), dν (h) and dp (s, h) = dp ({(x 1 , y 1 ) , . . . , (x N , y N )} , h) to denote the corresponding probability mass functions. With some abuse of notation, we use dD (x) for the probability mass function of the marginal of D over X dD (x) = P (X,Y )∼D (X = x) , and dp ((x 1 , y 1 ) , h) for the marginal of the joint probability of a single point from S and the output of the algorithm, i.e.,dp ((x 1 , y 1 ) , h) = P (S,A(S))∼p (X 1 = x 1 , Y 1 = y 1 , A (S) = h) .Similarly, we use dp (x 1 , h), dp (y 1 | x 1 , h), 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 to the one introduced in Framework 1.Let Ã (S) be a learning rule satisfying Framework 1, and let ⋆ be some arbitrary token distinct from any hypothesis the algorithm may produce. We define a modified learning rule A (S)8 such that• If S is inconsistent then A (S) = ⋆.• Otherwise, if S is consistent then A (S) = Ã (S), so in particular L S (A (S)) = 0.Notice that since the A (S) = Ã (S) when S is consistentE [L D (A (S)) | consistent S] = E L D Ã (S) | consistent Sand therefore we can find bounds for the generalization error of Ã (S) by analyzing A (S). In addition, when it can be inferred from context we use A (S) to denote the min-size and posterior sampling interpolators (instead of A L (S) or A d (S), respectively).For ease of exposition, throughout the appendix, we rephrase the assumptions made in Section 4, namely, thatN = ω d 2 0 log d 0 and N = o 1/ √ D max , as follows. Assumption A.1 (Bounded input dimension). d 0 = o N/ log N . Assumption A.2 (Data distribution flatness). D max = o 1/N 2 .We start by citing several standard results from information theory and lemmas from Manoj and Srebro [58] which will be useful throughout our supplementary materials.A 1 , A 2 and B I ((A 1 , A 2 ) ; B) = I (A 2 ; B | A 1 ) + I (A 1 ; B) .Lemma A.4. Let A and B be any two random variables with associated marginal distributions p A , p B , and joint p A,B . Let q A|B be any conditional distribution (i.e. such that for any b, q A|B (•, b) is a normalized non-negative measure). Then:I (A; B) ≥ E A,B∼p A,B log dq A|B (A|B) dp A (A) .Lemma A.5. Let A 1 , A 2 , B be random variables where A 1 and A 2 are independent. ThenI ((A 1 , A 2 ) ; B) ≥ I (A 1 ; B) + I (A 2 ; B) .Lemma A.6 (Lemma A.4 from Manoj and Srebro [58] ). For C ≥ 0 and 0 ≤ α ≤ 1 it holds that1 -2 -H(α)-C ≤ 1 -2 -H(α) + C . Lemma A.7. Let ε ∈ 0, 1 2 and ϕ (t) ≜ ϕ ε (t) = ε t ε t + (1 -ε) t = 1 1 + 1 ε -1 t .Then, ϕ is monotonically decreasing as a function of t, and convex in (0, ∞).Proof. Denote α ≜ 1 ε -1 then ϕ (t) = 1 1 + α t ϕ ′ (t) = -ln (α) α t (1 + α t ) 2 = -ln (α) • α t 1 + 2α t + α 2t ϕ ′′ (t) = -ln (α) • ln (α) α t (1 + α t ) 2 -α t • 2 (1 + α t ) • ln (α) α t (1 + α t ) 4 = -ln (α) 2 • α t • (1 + α t ) -2α t (1 + α t ) 3 = ln (α) 2 • α t • α t -1 (1 + α t ) 3 .Notice that for any ε ∈ 0,1 2 , α = 1 ε -1 > 1 so for all t > 0 α t -1 > 0and ϕ ′′ (t) > 0 so the function is indeed convex, and -ln (α) < 0 so ϕ is decreasing.Corollary A.8. For all t > 0 it holds thatϕ (t) ≥ ϕ (1) + ϕ ′ (1) (t -1) = ε + ln 2 (ε log (ε) + εH (ε)) (t -1) . Proof. Substituting t = 1, ϕ (1) = ε ε + (1 -ε) = ε ϕ ′ (1) = -ln (α) • α (1 + α) 2 = -ln 1 ε -1 • 1 ε -1 1 + 1 ε -1 2 = -ln 1 -ε ε • 1 ε -1 1 ε 2 = -(ln (1 -ε) -ln (ε)) • ε -ε 2 = ε (1 -ε) ln (ε) -ε (1 -ε) ln (1 -ε) = ε ln (ε) -ε (ε ln (ε) + (1 -ε) ln (1 -ε)) = ε ln 2 (log (ε) -(ε log (ε) + (1 -ε) log (1 -ε))) = ε ln 2 (log (ε) + H (ε)) = ln 2 (ε log (ε) + εH (ε)) .The inequality then holds due to convexity.Finally, for completeness, we derive the relationship between the generalization error with respect to the noisy distribution L D (h), and the generalization error with respect to the clean distribution L D0 (h). Lemma A.9. Let D be a distribution as in Section 2.2, with independent noise with label flipping probability ε ⋆ ∈ 0, 1 2 . Let D 0 be the clean distribution, i.e., the distribution with label flipping probability 0. IfL D (h) = P (X,Y )∼D (h (X) ̸ = Y ) and L D0 (h) = P (X,Y )∼D0 (h (X) ̸ = Y ) = P (X)∼D (h (X) ̸ = h ⋆ (X)) then L D0 (h) = L D (h) -ε ⋆ 1 -2ε ⋆ .Proof. By definition,L D (h) = P (X,Y )∼D (h (X) ̸ = Y ) = P (X,Y )∼D (h (X) ̸ = Y | h ⋆ (X) ⊕ Y = 0) P (X,Y )∼D (h ⋆ (X) ⊕ Y = 0) + P (X,Y )∼D (h (X) ̸ = Y | h ⋆ (X) ⊕ Y = 1) P (X,Y )∼D (h ⋆ (X) ⊕ Y = 1) .Since we assume that the noise is independent,L D (h) = (1 -ε ⋆ ) P (X,Y )∼D (h (X) ̸ = Y | h ⋆ (X) ⊕ Y = 0) + ε ⋆ P (X,Y )∼D (h (X) ̸ = Y | h ⋆ (X) ⊕ Y = 1) = (1 -ε ⋆ ) P (X,Y )∼D (h (X) ̸ = h ⋆ (X)) + ε ⋆ P (X,Y )∼D (h (X) = h ⋆ (X)) = (1 -ε ⋆ ) L D0 (h) + ε ⋆ (1 -L D0 (h)) = ε ⋆ + (1 -2ε ⋆ ) L D0 (h) ,or equivalently,L D0 (h) = L D (h) -ε ⋆ 1 -2ε ⋆ .Remark A.10. In particular, under the assumptions of the lemma,L D (h) = 2ε ⋆ (1 -ε ⋆ ) is equivalent to L D0 (h) = ε ⋆ .Before moving on to 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) ≤ 1 2 N 2 D max .Proof. Using the union bound,P (inconsistent S) = P (∃i ̸ = j ∈ [N ] : X i = X j , Y i ̸ = Y j ) ≤ P (∃i ̸ = j ∈ [N ] : X i = X j ) ≤ i̸ =j P (X i = X j ) = N 2 P (X 1 = X 2 ) = N 2 x∈X P (X 1 = x) P (X 2 = x) ≤ N 2 x∈X D max P (X = x) = N 2 D max ≤ 1 2 N 2 D max .Hence, under Assumption A.2 we have P (inconsistent S) = o (1), i.e., the inconsistency probability is asymptotically small.We now focus on the case of independent label noise, i.e., Y ⊕ h ⋆ (X)| {X = x} ∼ Ber (ε ⋆ ) for any x ∈ X . Recall the noise level ε ⋆ = P (X,Y )∼D (Y ̸ = h ⋆ (X)) = P S (Y 1 ̸ = h ⋆ (X 1 ))and we define the "effective" noise level in a consistent training setEQUATIONWe relate εtr to ε ⋆ in the following lemma. Lemma B.2. In the independent noise setting, it holds that|ε tr -ε ⋆ | ≤ |ln 2 (ε ⋆ log (ε ⋆ ) + ε ⋆ H (ε ⋆ ))| • (N -1) D max P (consistent S), and moreover, εtr ≤ ε ⋆ .Proof. Conditioning on S being consistent (having no label "collisions"), all occurrences of x in S must have the same label soEQUATIONOn the other hand, defineK (S) ≜ |{i ∈ [N ] | X i = X 1 }| = N i=1 I {X i = X 1 } then E S [K (S) | consistent S] = 1 + N i=2 E S [I {X i = X 1 } | consistent S] = 1 + (N -1) P S (X 2 = X 1 | consistent S) .Next,P (X 2 = X 1 | consistent S) = P (X 2 = X 1 , consistent S) P (consistent S) ≤ P (X 1 = X 2 ) P (consistent S).Since dD (x) ≤ D max for all x ∈ X , as in the proof of Lemma B.1E S [K (S) | consistent S] ≤ 1 + (N -1) P (X 1 = X 2 ) P (consistent S) ≤ 1 + (N -1) D max P (consistent S).Then, using Lemma A.7 we get,εtr = N k=1 ε ⋆k ε ⋆k + (1 -ε ⋆ ) k • P (X 1 appears k times in S | consistent S) = N k=1 ϕ ε ⋆ (k) • P (X 1 appears k times in S | consistent S) = E S   ϕ ε ⋆ (K (S)) convex in k | consistent S   [Jensen] ≥ ϕ ε ⋆ (E S [K (S) | consistent S]) [decreasing] ≥ ϕ ε ⋆ 1 + (N -1) • D max P (consistent S).Corollary A.8 implies that εtr ≥ ϕ ε ⋆ 1 + (N -1) • D max P (consistent S) ≥ ε ⋆ + ln 2 (ε ⋆ log (ε ⋆ ) + ε ⋆ H (ε ⋆ )) • (N -1) D max P (consistent S).Combining the bounds we get|ε tr -ε ⋆ | ≤ |ln 2 (ε ⋆ log (ε ⋆ ) + ε ⋆ H (ε ⋆ ))| • (N -1) D max P (consistent S).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.1 (High consistency probability). Throughout the appendix we assume that the consistency satisfies P S (consistent S) ≥ 1 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.In this subsection, we provide a generalization bound for interpolating algorithms without any assumptions on the distribution of the noise Y⊕ h ⋆ (X) | {X = x}, other than L D (h ⋆ ) = ε ⋆ . Lemma C.2.For any interpolating learning algorithm A (S),-log 1 -E S,A(S) [L D (A (S)) | consistent S] ≤ I (S; A (S)) N • P S (consistent S).Proof. We rely on Lemma A.4. Specifically, we shall use the following suggested conditional distribution. For h ̸ = ⋆ letdq (s|h) = 1 Z h I {L s (h) = 0} dD N (s)whereZ h = s I {L s (h) = 0} dD N (s) = E S I {L S (h) = 0} = P S (L S (h) = 0) = (1 -L D (h)) N .For h = ⋆ let dq (s|⋆) = I {inconsistent s} dD N (s)s ′ I {inconsistent s ′ } dD N (s ′ ) = I {inconsistent s} dD N (s) P S (inconsistent S).Clearly, if h ̸ = ⋆ and dq (s|h) = 0 then either dD N (s) = 0 so dp (s, h) = 0 as well, or L s (h) ̸ = 0. So, since h ̸ = ⋆, s can be interpolated and dp (s | h) = 0. That is, the proposed conditional distribution is absolutely continuous w.r.t. the true conditional distribution. When h = ⋆, q is the true conditional distribution given that h = ⋆ so it is also absolutely continuous w.r.t. it. That is, the proposed distribution isdq (s | h) = I {inconsistent s} P S (inconsistent S) I {h = ⋆} dD N (s) + I {L s (h) = 0} (1 -L D (h)) N I {h ̸ = ⋆} dD N (s) .From Lemma A.4I (S; A (S)) ≥ E S,A(S) log dq (S|A (S)) dD N (S) = E S,A(S) log I{inconsistent S} P S ′ (inconsistent S ′ ) I {A (S) = ⋆} + I{L S (A(S))=0} (1-L D (A(S))) N I {A (S) ̸ = ⋆} .I {A (S) = ⋆} and I {A (S) ̸ = ⋆} are mutually exclusive soI (S; A (S)) ≥ E S,A(S) log I{inconsistent S} P S ′ (inconsistent S ′ ) I {A (S) = ⋆} + log I{L S (A(S))=0} (1-L D (A(S))) N I {A (S) ̸ = ⋆} .The first term is 0 when A (S) ̸ = ⋆ and positive when A (S) = ⋆ (and so always non-negative). Furthermore, whenever dp (S, A (S)) > 0 and I {A (S) ̸ = ⋆} = 1 hold together, they imply that I {L S (A (S)) = 0} = 1 so we haveI (S; A (S)) ≥ E S,A(S) log 1 (1 -L D (A (S))) N I {A (S) ̸ = ⋆} = -E S,A(S) [N log (1 -L D (A (S))) I {A (S) ̸ = ⋆}] .Using Jensen's inequality,-E S,A(S) [N log (1 -L D (A (S))) I {A (S) ̸ = ⋆}] = -N E S,A(S) [log (1 -L D (A (S))) | I {A (S) ̸ = ⋆}] P S,A(S) (A (S) ̸ = ⋆) ≥ -N log 1 -E S,A(S) [L D (A (S)) | I {A (S) ̸ = ⋆}] P S,A(S) (A (S) ̸ = ⋆) = -N log 1 -E S,A(S) [L D (A (S)) | consistent S] P S (consistent S) so I (S; A (S)) ≥ -N log 1 -E S,A(S) [L D (A (S)) | consistent S] P S (consistent S) .Rearranging the inequality-log 1 -E S,A(S) [L D (A (S)) | consistent S] ≤ I (S; A (S)) N • P S (consistent S)C.2 Independent Noise Lemma C.3. Assuming independent noise, the generalization error of interpolating learning rules satisfies the following.E S,A(S) [L D (A (S)) | consistent S] -2ε ⋆ (1 -ε ⋆ ) ≤ (1 -2ε ⋆ ) C (N ) + (N -1) D max 3 ,where C (N ) ≜ I(S;A(S))-N •(H(ε ⋆ )-P(inconsistent S))N (1-P(inconsistent S)).Proof. As in the proof of Lemma 4.2 in Manoj and Srebro [58] , since S is sampled i.i.d., we haveA.5EQUATIONUsing properties of conditional mutual information,EQUATION)For the first term in (7) , we employ the fact that for any x ∈ X , eitherY 1 | X 1 = x ∼ Ber (ε ⋆ ) or Y 1 | X 1 = x ∼ Ber (1 -ε ⋆ ) to get H (Y 1 | X 1 ) = E (X,Y )∼D [H (Y 1 | X 1 = X)] = E (X,Y )∼D [H (ε ⋆ )] = H (ε ⋆ ) .For the second term in (7) , we again employ the definition of conditional entropy,H (Y 1 | A (S) , X 1 ) = - x1∈X h∈H∪{⋆} dp ((x 1 , 0) , h) log dp ((x 1 , 0) , h) dp (x 1 , h) + dp ((x 1 , 1) , h) log dp ((x 1 , 1) , h) dp (x 1 ,When h ̸ = ⋆, the marginal distribution of a training data point and a hypothesis isdp ((x, y) , h) = dp (y | x, h) dp (x, h) = I {y = h (x)} dp (x, h) ,and the inner sum becomes a sum over expressions of the form:dp ((x 1 , h (x 1 )) , h) log dp ((x 1 , h (x 1 )) , h) dp (x 1 , h) = dp (x 1 , h) log dp (x 1 , h) dp (x 1 , h) =0 = 0 .Therefore, we have that,H (Y 1 | A (S) , X 1 ) = - x1∈X dp ((x 1 , 0) , ⋆) log dp ((x 1 , 0) , ⋆) dp (x 1 , ⋆) + dp ((x 1 , 1) , ⋆) log dp ((x 1 , 1) , ⋆) dp (x 1 , ⋆) Employing conditional probabilities (notice that dp((x1,0),⋆) dp(x1,⋆) = dp(0|x1,⋆)dp(x1,⋆) dp(x1,⋆) = dp (0 | x 1 , ⋆)), we get, H (Y 1 | A (S) , X 1 ) = - x1∈X dp (x 1 , ⋆) [dp (0 | x 1 , ⋆) log (dp (0 | x 1 , ⋆)) + dp (1 | x 1 , ⋆) log (dp (1 | x 1 , ⋆))] = x1∈X dp (x 1 , ⋆) H (dp (0 | x 1 , ⋆)) = dp (⋆) x1∈X dp (x 1 | ⋆) H (dp (0 | x 1 , ⋆)) = P (A (S) = ⋆) E (S,A(S))∼p H (dp (0 | X 1 , ⋆)) ≤1 | inconsistent S ≤ P S (inconsistent S) .Overall, the right term in ( 6) is lower bounded by,I (Y 1 ; A (S) | X 1 ) = H (Y 1 | X 1 ) -H (Y 1 | A (S) , X 1 ) ≥ H (ε ⋆ ) -P (inconsistent S) .For the left term, i.e., I (X 1 ; A (S)), we use the variational bound Lemma A.4 with the following suggested conditional distribution.• For h = ⋆, choose dq (x 1 | ⋆) = dp (x 1 ) (notice that x1∈X dq (x 1 | ⋆) = x1 dp (x 1 ) = 1.• Otherwise, if h ̸ = ⋆, denote q ε = Ber (ε), andεtr = P S (Y 1 ̸ = h ⋆ (X 1 ) | consistent S) εgen = E (S,A(S))∼p [P X∼D (A (S) (X) ̸ = h ⋆ (X)) | A (S) ̸ = ⋆] .Note that εtr may differ from ε ⋆ . We choose the following conditional distributiondq (x 1 | h) = 1 Z h • dq εtr (h (x 1 ) ⊕ h ⋆ (x 1 )) dq εgen (h (x 1 ) ⊕ h ⋆ (x 1 )) dp (x 1 ) .In total, we choose,dq (x 1 | h) = 1 Z h • dq εtr (h (x 1 ) ⊕ h ⋆ (x 1 )) dq εgen (h (x 1 ) ⊕ h ⋆ (x 1 )) • I {h ̸ = ⋆} dp (x 1 ) + I {h = ⋆} dp (x 1 ) ,where Z h is the corresponding partition function.Then, we use (A.4) and properties of logarithms and indicators to show that,I (X 1 ; A (S)) ≥ E S,A(S) log dq (X 1 |A (S)) dp (X 1 ) = E S,A(S)   log   1 Z A(S)dq εtr (h(X1)⊕h ⋆ (X1))dq εgen (h(X1)⊕h ⋆ (X1)) dp (X 1 ) I {A (S) ̸ = ⋆} + dp (X 1 ) I {A (S) = ⋆} dp (X 1 )     = E S,A(S) log 1 Z A(S) dq εtr (h (X 1 ) ⊕ h ⋆ (X 1 )) dq εgen (h (X 1 ) ⊕ h ⋆ (X 1 )) I {A (S) ̸ = ⋆} + I {A (S) = ⋆} = E S,A(S) log 1 Z A(S) dq εtr (h (X 1 ) ⊕ h ⋆ (X 1 )) dq εgen (h (X 1 ) ⊕ h ⋆ (X 1 )) I {A (S) ̸ = ⋆} + E S,A(S) log (1) I {A (S) = ⋆} =0 = E S,A(S) log 1 Z A(S) dq εtr (h (X 1 ) ⊕ h ⋆ (X 1 )) dq εgen (h (X 1 ) ⊕ h ⋆ (X 1 )) I {A (S) ̸ = ⋆} .Using the law of total expectation, the above becomes,= P (A (S) ̸ = ⋆) E S,A(S) log 1 Z A(S) • dq εtr (h (X 1 ) ⊕ h ⋆ (X 1 )) dq εgen (h (X 1 ) ⊕ h ⋆ (X 1 )) A (S) ̸ = ⋆ ,where we also use Jensen's inequality to show,E S,A(S) log 1 Z A(S) • dq εtr (h (X 1 ) ⊕ h ⋆ (X 1 )) dq εgen (h (X 1 ) ⊕ h ⋆ (X 1 )) A (S) ̸ = ⋆ = E S,A(S) log dq εtr (h (X 1 ) ⊕ h ⋆ (X 1 )) dq εgen (h (X 1 ) ⊕ h ⋆ (X 1 )) A (S) ̸ = ⋆ -E S,A(S) log Z A(S) A (S) ̸ = ⋆ ≥ E S,A(S) log dq εtr (h (X 1 ) ⊕ h ⋆ (X 1 )) dq εgen (h (X 1 ) ⊕ h ⋆ (X 1 )) A (S) ̸ = ⋆ -log E S,A(S) Z A(S) A (S) ̸ = ⋆ .The partition function satisfies for all h ̸ = ⋆,Z h = x1∈X dq εtr (h (x 1 ) ⊕ h ⋆ (x 1 )) dq εgen (h (x 1 ) ⊕ h ⋆ (x 1 )) dp (x 1 ) = E X∼D dq εtr (h (X) ⊕ h ⋆ (X)) dq εgen (h (X) ⊕ h ⋆ (X)) = P X∼D (h (X) = h ⋆ (X)) • 1 -εtr 1 -εgen + P X∼D (h (X) ̸ = h ⋆ (X)) • εtr εgen .Taking the expectation w.r.t. (S, A (S)) ∼ p, we getE (S,A(S))∼p Z A(S) | A (S) ̸ = ⋆ = 1 -εtr 1 -εgen • E S,A(S) [P (A (S) (X) = h ⋆ (X)) | A (S) ̸ = ⋆] =1-εgen + + εtr εgen • E S,A(S) [P (A (S) (X) ̸ = h ⋆ (X)) | A (S) ̸ = ⋆] =εgen = 1 .Combining the above, we have that,I (X 1 ; A (S)) ≥ P (A (S) ̸ = ⋆) E S,A(S) log dq εtr (A (S) (X 1 ) ⊕ h ⋆ (X 1 )) dq εgen (A (S) (X 1 ) ⊕ h ⋆ (X 1 )) | A (S) ̸ = ⋆ .Notice that(A (S) (X 1 ) ⊕ h ⋆ (X 1 ) | {A (S) ̸ = ⋆}) = (Y 1 ⊕ h ⋆ (X 1 ) | {consistent S}) , so A (S) (X 1 ) ⊕ h ⋆ (X 1 ) | {A (S) ̸ = ⋆} ∼ Ber (ε tr ), and thusI (X 1 ; A (S)) ≥ P (A (S) ̸ = ⋆) D KL q εtr ||q εgen = 1 -P (inconsistent S) D KL q εtr ||q εgen .Putting this all together, ( 6) is lower bounded by, I (S; A (S)) ≥ N 1 -P (inconsistent S) D KL q εtr ||q εgen + N H (ε ⋆ ) -P (inconsistent S) .Rearranging the inequalityD KL q εtr ||q εgen ≤ I (S; A (S)) -N • (H (ε ⋆ ) -P (inconsistent S)) N (1 -P (inconsistent S)) ≜ C (N ) .Using Pinsker's inequality, we have,|ε tr -εgen | ≤ 1 2 D KL q εtr ||q εgen ≤ C (N ) .We proceed to boundE S,A(S) [L D (A (S)) | consistent S] in terms of |ε tr -εgen |. Notice that E S,A(S) [L D (A (S)) | consistent S] = E S,A(S) P (X,Y )∼D (A (S) (X) ̸ = Y ) | consistent S = E S,A(S) P (A (S) (X) ̸ = Y | Y = h ⋆ (X)) P (Y = h ⋆ (X)) no label flip consistent S + + E S,A(S) P (A (S) (X) ̸ = Y | Y ̸ = h ⋆ (X)) P (Y ̸ = h ⋆ (X)) label flip consistent S = E S,A(S) P (A (S) (X) ̸ = h ⋆ (X)) (1 -ε ⋆ ) + P (A (S) (X) = h ⋆ (X)) ε ⋆ consistent S = (1 -ε ⋆ ) E S,A(S) [P (A (S) (X) ̸ = h ⋆ (X)) | consistent S] + + ε ⋆ E S,A(S) [P (A (S) (X) = h ⋆ (X)) | consistent S] = (1 -ε ⋆ ) εgen + ε ⋆ (1 -εgen ) .Then, using the triangle inequality,E S,A(S) [L D (A (S)) | consistent S] -2ε ⋆ (1 -ε ⋆ ) = |(1 -ε ⋆ ) εgen + ε ⋆ (1 -εgen ) -2ε ⋆ (1 -ε ⋆ )| = εgen -εgen ε ⋆ + ε ⋆ -εgen ε ⋆ -2ε ⋆ + 2ε ⋆2 = εgen -2ε gen ε ⋆ -ε ⋆ + 2ε ⋆2 = |ε gen (1 -2ε ⋆ ) -ε ⋆ (1 -2ε ⋆ )| = (1 -2ε ⋆ ) |ε gen -ε ⋆ | ≤ (1 -2ε ⋆ ) (|ε gen -εtr | + |ε tr -ε ⋆ |) .Combining with the result from Lemma B.2 and Remark C.1|ε tr -ε ⋆ | ≤ |ln 2 (ε ⋆ log (ε ⋆ ) + ε ⋆ H (ε ⋆ ))| • (N -1) D max P (consistent S) ≤ |ln 2 (ε ⋆ log (ε ⋆ ) + ε ⋆ H (ε ⋆ ))| • 2 (N -1) D max .we conclude thatE S,A(S) [L D (A (S)) | consistent S] -2ε ⋆ (1 -ε ⋆ ) ≤ (1 -2ε ⋆ ) C (N ) + ln 2 |(ε ⋆ log (ε ⋆ ) + ε ⋆ H (ε ⋆ ))| • 2 (N -1) D max .Finally, we can use the algebraic property that (1-2ε ⋆ ) |ln 2 (ε ⋆ log (ε ⋆ ) + ε ⋆ H (ε ⋆ ))| ≤ 1 6 , to get E S,A(S) [L D (A (S)) | consistent S] -2ε ⋆ (1 -ε ⋆ ) ≤ (1 -2ε ⋆ ) C (N ) + (N -1) D max 3 .We can now bound the expected generalization error without conditioning on the consistency of the training set. Lemma C. 4 . It holds that,E S,A(S) [L D (A (S))] -2ε ⋆ (1 -ε ⋆ ) ≤ E S,A(S) [L D (A (S)) | consistent S] -2ε ⋆ (1 -ε ⋆ ) + P S (inconsistent S) .Proof. Let X be an arbitrary RV in [0, 1] and Y be a binary RV. Then,E [X] = P (Y ) E [X|Y ] + P (¬Y ) E [X|¬Y ] E [X] -E [X|Y ] = P (Y ) E [X|Y ] -E [X | Y ] + P (¬Y ) E [X|¬Y ] = E [X|Y ] (P (Y ) -1) + P (¬Y ) E [X|¬Y ] = -E [X|Y ] P (¬Y ) + P (¬Y ) E [X|¬Y ] = P (¬Y ) (E [X|¬Y ] -E [X|Y ]) |E [X] -E [X|Y ]| = P (¬Y ) |E [X|¬Y ] -E [X|Y ]| ≤1 ≤ P (¬Y ) .E S,A(S) [L D (A (S))] -E S,A(S) [L D (A (S)) | consistent S] ≤ P S (inconsistent S) .Then, the required inequality is obtained by simply using the triangle inequality onE S,A(S) [L D (A (S))] -2ε ⋆ (1 -ε ⋆ ) .In this section, we prove Theorem 3.1. We begin with an informal outline of the proof idea. Inspired by Manoj and Srebro's analysis [58] , our proof of Theorem 3.1 is based on the concept of a pseudorandom generator, defined below. Definition D.1 (Pseudorandom generator). Let G : {0, 1} r → {0, 1} R be a function, let V be a class of functions V : {0, 1} R → {0, 1}, let D be a distribution over {0, 1} R , and let ϵ > 0. We say that G is an ϵ-pseudorandom generator (ϵ-PRG) for V with respect to D if for every V ∈ V, we haveP y∼D (V (y) = 1) -P u∈{0,1} r (V (G(u)) = 1) ≤ ϵ,where u is sampled uniformly at random from {0, 1} r .To connect Definition D.1 to Theorem 3.1, let R = 2 d0 . Let V be the class of all conjunctions of literals, such as V (y) = y 1 ∧ ȳ2 ∧ y 4 . Let X = f -1 ({0, 1}). There is a function V f ∈ V such that given the entire truth table of a NN h, the function V f verifies that h agrees with f on X . This function V f is a conjunction of N 1 many variables and (N -N 1 ) many negated variables.Let α = N 1 /N , and let D = Ber(α) R . Suppose G is an ϵ-PRG for V with respect to D, where ϵ < P y∼D (V f (y) = 1). Then P u∈{0,1} r (V f (G(u)) = 1) ̸ = 0, i.e., there exists some u ⋆ ∈ {0, 1} r such that V f (G(u ⋆ )) = 1. Therefore, if we let h be a NN that computes the functionEQUATIONthen 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 a number from 0 to R -1 represented by its binary expansion.There is a large body of well-established techniques for constructing PRGs. (See, for example, Hatami and Hoza's recent survey [35] .) Therefore, constructing a suitable PRG might seem like a promising approach to proving Theorem 3.1. However, this approach is flawed. The issue concerns the seed length (r). According to 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 (ϵ) must satisfyEQUATIONComparing (9) to Theorem 3.1, we see that we would need a PRG with seed lengthr = (1 + o(1)) • log(1/ϵ).But this is too much to ask. There is no real reason to expect such a 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/ϵ) [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} r → {0, 1} R be a function, let V be a class of functions V : {0, 1} R → {0, 1}, let D be a distribution over {0, 1} R , and let ϵ > 0. We say that G is an ϵ-hitting set generator (ϵ-HSG) for V with respect to D if for every V ∈ V such thatP y∼D (V (y) = 1) > ϵ, there exists u ⋆ ∈ {0, 1} r such that V (G(u ⋆ )) = 1.Definition D.2 is weaker than Definition D.1, but an HSG is sufficient for our purposes. Crucially, one can show nonconstructively that for every V, D, and ϵ, there exists an HSG with seed length1 • log(1/ϵ) + log log |V| + O(1),whereas the nonconstructive PRG seed length is 2 • log(1/ϵ) + • • • . To prove Theorem 3.1, we will construct an explicit HSG for conjunctions of literals with respect to Ber(α) R with a seed length of (1 + o(1)) • log(1/ϵ) + 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 r 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 ϵ, and then we apply an error reduction technique due to Hoza and Zuckerman [38] . Details follow.Before applying an HSG as outlined above, the first step of the proof of Theorem 3.1 is actually a preprocessing step that reduces the dimension to approximately 2 log N . This step is not completely essential, but it helps to improve the dependence on d 0 in Theorem 3.1. The preprocessing step is based on a standard trick, namely, we treat the input as a vector in F d0 2 and apply a random matrix, where F 2 denotes the field with two elements. That is:Definition D.3 (F 2 -linear and F 2 -affine functions). A function C : {0, 1} d → {0, 1} d ′ is F 2 -linear if it has the form C(x) = Wx,where W ∈ {0, 1} d ′ ×d and the arithmetic is mod 2. More generally, we say that C is F 2 -affine if it has the formC(x) = Wx + b, where W ∈ {0, 1} d ′ ×d , b ∈ {0, 1} d ′, 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 d 0 ∈ N, let X ⊆ {0, 1} d0 , and letN = | X |.There exists an F 2 -linear functionC 0 : {0, 1} d0 → {0, 1} 2⌈log N ⌉ that is injective on X .Proof. Pick W ∈ {0, 1} 2⌈log N ⌉×d0 uniformly at random and let C 0 (x) = Wx. For each pair of distinct points x, x ′ ∈ X , we haveP(Wx = Wx ′ ) = P(W(x -x ′ ) = 0) = 2 -2⌈log N ⌉ < 1/N 2 .Therefore, by the union bound over all pairs x, x ′ , there is a nonzero chance that C 0 is injective on X . Therefore, there is some fixing of W such that C 0 is injective on X .We will choose C 0 to be injective on the domain of f . That way, after applying C 0 to the input, our remaining task is to compute some other partial function f ′ : {0, 1} 2⌈log N ⌉ → {0, 1, ⋆}, namely, the function f ′ such that f ′ • C 0 = f . This function f ′ has the same domain size (N ), and it takes the value 1 on the same number of points (N 1 ), so the net effect is that we have decreased the dimension from d 0 down to 2⌈log N ⌉. This same technique appears in the circuit complexity literature, along with more sophisticated variants. For example, see Jukna's textbook [45, Section 1.4.2].To apply Lemma D.4 in our setting, we rely on the well-known fact that F 2 -linear functions, and more generally F 2 -affine functions, can be computed by depth-two binary threshold networks. More precisely, we have the following. Lemma D.5 (Binary threshold networks computing F 2 -linear functions).If C : {0, 1} d → {0, 1}is the parity function or its negation, then there exists a depth-one binary threshold network C 0 : {0, 1} d → {0, 1} (d+2) and a number b ∈ R such that for every x ∈ {0, 1} d , we haveC(x) = 1 T C 0 (x) + b,where 1 denotes the all-ones vector. Moreover, every affine function C : {0, 1} d → {0, 1} d ′ can be computed by a depth-two binary threshold network with d ′ • (d + 2) nodes in the hidden layer.Proof. First, suppose C is the parity function. For each i ∈ [d], let ϕ ≤i : {0, 1} d → {0, 1} be the functionϕ ≤i (x) = 1 ⇐⇒ d j=1 x j ≤ i,and similarly define ϕ ≥i : {0, 1} d → {0, 1} byϕ ≥i (x) = 1 ⇐⇒ d j=1 x j ≥ i. Then ϕ ≤1 (x) + ϕ ≥1 (x) + ϕ ≤3 (x) + ϕ ≥3 (x) + • • • = ⌈d/2⌉ + 1 if PARITY(x) = 1 ⌈d/2⌉ if PARITY(x) = 0,so we can take b = -⌈d/2⌉. Now, suppose C is the negation of the parity function. This reduces to the case of the parity function because 1 -PARITY(x) = PARITY(x, 1). Finally, the "moreover" statement follows because if C is F 2 -affine, then every output bit of C is either the parity function or the negated parity function applied to some subset of the inputs.Lemma D.5 can be generalized to the case 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] .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, r ∈ N, there is a family H of hash functions hash : {0, 1} a → {0, 1} r with the following properties.• |H| ≤ 2 O(a+r) .• H is pairwise independent. That is, for every two distinct w, w ′ ∈ {0, 1} a , if we pick hash ∈ H uniformly at random, then hash(w) and hash(w ′ ) are independent and uniformly distributed over {0, 1} r .• Each function hash ∈ H is F 2 -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 ∈ H can be computed by a depth-two binary threshold network with O(r 2 a + ra 2 ) 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 [24] , which can be implemented with wire complexity (a + r) 1+γ for any arbitrarily small constant γ > 0 [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 + γ. However, the downside of this approach is that the depth of the network would increase to a very large constant depending on γ.Another ingredient of our HSG will be a threshold network computing a "k-wise uniform generator," defined below.Definition D.8 (k-wise uniform generator). A k-wise uniform generator is a function G : {0, 1} r → {0, 1} R such that if we sample u ∈ {0, 1} r uniformly at random, then every k of the output coordinates of G(u) are independent and uniform. In other words, G is a 0-PRG for V with respect to the uniform distribution, where V consists of all Boolean functions that only depend on k 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 the construction to get sufficiently fine-grained bounds. In the remainder of this subsection, we will prove the following.Lemma D.9 (Constant-depth k-wise uniform generator). Let k, R ∈ N where R is a power of two. There exists a k-wise uniform generator G : {0, 1} r → {0, 1} R , where r = O(k • log R), such that for every F 2 -affine function hash : {0, 1} a → {0, 1} r , there exists a depth-5 binary threshold network C : {0, 1} a+log R → {0, 1} k•polylog R with widths d satisfying the following.1. For every w ∈ {0, 1} a and every z ∈ {0, 1} log R , we haveG(hash(w)) z = PARITY(C(w, z)),thinking of z as a number in {0, 1, . . . , R -1}.2. The maximum width d max is at most ak • polylog R. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: (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.

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

(c) I strongly recommend another round of refactoring to improve the readability of the paper, for example

 i) I think in the statement, the term $2^{H(\epsilon^\star)}$ should be  $2^{-H(\epsilon^\star)}$, given the usual definition of entropy.

 ii) the notations are heavy, which prevents potential audience. 

 iii) some inconsistency in notations. For example, it defines the weights in the notation section, but it uses ``edges'' in the theorem statement.
questions: 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?

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

(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: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: I wonder if there is any way one could empirically verify the tightness of the proven results, even for small networks.
limitations: limitations: Limitations are addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2) This paper could benefit from a more thorough discussion of the limitations and future directions of the research.
questions: 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: limitations: The authors addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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

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

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?

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. 

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

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)?
questions: 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: limitations: See weakness and questions above.

Comments: comment: We thank the reviewer for the response. Could the reviewer kindly let us know if there are any remaining concerns we should address?
Thanks for your response. I'll keep my score.
Thanks for your response. I'll keep my score.
Thanks for your detailed response. I am generally satisfied with your response, and I will raise the score to 6.
I have read the reviewers global and individual response and acknowledge their point about empirical results.