Provable Tempered Overfitting of Minimal Nets and Typical Nets

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.

Strengths

The authors considered the quantized networks, and gave theoretical results on the tempered overfitting in DNNs without requiring the data dimension to be very low or very high.

Weaknesses

a) I am concerned about the claim made in your contribution (Line 40) that "any noisy dataset can be interpolated using a neural network of constant depth with threshold activations and binary weights." Doesn't this only hold under specific data settings? I would appreciate it if the authors could comment on this point. 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

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.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

See weakness and questions above.

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.

Strengths

1) This paper presents innovative research on the overfitting behavior of DNNs with binary weights, which adds to the existing literature on the generalization capabilities of neural networks. 2) The analysis is based on a new bound on the size of a threshold circuit consistent with a partial function, which provides a theoretical foundation for the results. 3) This paper provides a clear and well-structured explanation of the research problem and methodology, making it easy for readers to follow.

Weaknesses

1) This work focuses on the learning theory and presents the first theoretical results on benign or mitigated overfitting. It would be better if authors could provide necessary evaluation studies to support theoretical results. 2) This paper could benefit from a more thorough discussion of the limitations and future directions of the research.

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.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors addressed the limitations.

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.

Strengths

The paper proves tempered overfitting for minimum size and random interpolators in the presence of label noise. This can be seen as an extension of previous analysis, which considers settings without label noise, or other learning rules (e.g. shortest description length of Turing machines). The proof of the results relies on a new construction of a relatively small neural network that can learn arbitrary label noise. The paper is well-written and easy to follow.

Weaknesses

The derived bounds require some additional constraints on the width of the network and the number of examples due to the presence of label noise. Such requirements may not always be satisfied in practice.

Questions

I wonder if there is any way one could empirically verify the tightness of the proven results, even for small networks.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are addressed.

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.

Strengths

(a) The paper presents a novel theoretical analysis of overfitting behaviors in neural networks with binary weights. The new approximation result Theorem 3.1 and generalization result Theorem 4.1 are all novel to some extent. (b) The paper is well-structured, with clear definitions and thorough explanations of the models and assumptions used.

Weaknesses

(a) I'm not sure how the theoretical results derived in this paper will provide any insights into how people understand interpolated neural networks even in theory. It seems that this paper just plugged in the new approximation result Theorem 3.1 in the framework of (Manoj & Srebro, 2023). In other words, the paper provides marginal new information in this regard. The main theorem Theorem 4.1 is somewhat can be expected. (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

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

Rating

5

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors have adequately addressed the limitations.