- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper shows that stability condition for gradient descent in terms of the Hessian () bounds the ability for an overparameterized neural network to interpolate noisy training data. It follows a line of work by Liang et al. to identify a "deep" region in the feature space where the stability condition on the Hessian implies that the "weight" of kinks in this region cannot be too large. The main result of this work is Theorem 5, which is a lower bound for L^2 training error in this deep region assuming the true labels correspond to a teacher network that satisfies the stability condition. This lower bound is the sum of the added label noise, the training error against teacher, and a negative term representing a remainder. The paper extends this result by considering logistic loss and teacher networks outside of the class. It also considers a concrete data distribution (uniform on the sphere) and shows that the deep region is non-empty with high probability in this region.
Critical strengths
The question under study is interesting. The technical results are clearly stated.
Critical weaknesses
The main result of the paper is extremely constrained and not properly contextualized. The claim made by the title is not supported by the text of the paper. The authors only bound the training loss on the deep region, which results in the following limitations not considered by the paper:
- The deep region is a subset of the interior of the convex hull of the training point. It is shown (Proposition 6) that this region is nonempty given where is the dimension, but in the proof it is shown that is exponential in . This is not an artifact of the proof, as it is known that in general exponentially many points can be sampled uniformly in the ball before one will lie in the convex hull of the rest. This dependence is not made explicit in the paper, and can only be seen by looking at the proofs.
- There are multiple competing constraints on the quantity that defines the deep region, and the authors do not consider how these constraints interact. Two such constraints are as follows.
- The bound on in Proposition 6 is vacuous unless . For an appreciable fraction of the points to remain in the deep set, must be even smaller.
- Proposition 6 says that g^\min_{\mathcal{D}} may be as small as . The reciprocal of g^\min_{\mathcal{D}} appears in the upper bound for the remainder in Theorem 5. If is too small, this bound can be larger than and the result of Theorem 5 is vacuous.
The authors do correctly identify that these terms involve little dependence on . If is large enough relative to , then there is a that can be found to produce a non-vacuous bound that covers an appreciable fraction of the dataset. However, it is unclear in what regimes relating and that this is true, and what value of needs to be selected. As stated, it appears that needs to grow as , which is a very strong condition even for modest dimensions. The experiments do not address these concerns, as they only ever consider data with intrinsic dimension 1.
Questions for authors
In the setting where data is drawn uniformly from the ball:
- How does the bound in Theorem 5 look with the dimension dependence made specific?
- What is the tradeoff between the bound in Theorem 5 and the size of the deep set?
Additionally, I suggest that future work might consider settings where the tradeoffs involved in selecting can be analyzed directly other than data drawn uniformly from the ball.