Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides a lower bound on the *global* Lipschitz constant (with respect to the 2-norm) of any function within a parameterized function class that fits data below the noise level that scales inversely in the number of parameters p, showing that overparameterization is *necessary* to ensure a smooth fit of noisy training data. These lower bounds hold under the following assumptions/caveats:

- the d-dimensional input data satisfies the assumption of c-isoperimetry, which includes the Gaussian measure, strongly log-concave measures and distributions over d-dimensional manifolds with a positive Ricci curvature.

-- the parameters ("weights") of the function class are polynomially bounded in (n,d).

-- the training data has positive label noise, and the function is constrained to fit below the noise level (which includes the case of interpolation of training data).

-- the smoothness (Lipschitz) constant is evaluated with respect to the 2-norm.

The paper contextualizes these results in the context of deep neural networks and provides two lower bounds on the Lipschitz constant that (in addition to the scaling given in n, d, and p) scale inversely either in the depth or the product of spectral norms of layers. The latter is a well-known upper bound on the Rademacher complexity of deep neural networks. Both results show an additional dependence on the number of parameters p that is required to ensure small Lipschitz constant --- such a dependence is not present in typical Rademacher complexity bounds used to upper bound clean generalization error.
main_review: Strengths of submission:

-- Establishing fundamental limits on adversarial robustness of function classes is an important open problem. This paper makes progress towards this mathematically challenging goal (albeit by lower bounding the global Lipschitz constant, whose precise relationship to the adversarial error remains unclear).

-- The proof technique is relatively elementary, but innovative. In particular it makes elegant use of the isoperimetry property (which by definition is connected to Lipschitz-ness). Because of the ultimate application of parameter counting, it is also very generally applicable to arbitrary parametric function classes and shows insightfully that the number of parameters fundamentally bottlenecks a smoothness guarantee subject to fitting a non-zero amount of noise.

-- This proof technique could be useful to study the generalization error of interpolating solutions for generic function classes beyond the adversarial examples problem.

Weaknesses of submission:

-- As discussed in Section 1.1 of the paper, it is very unclear whether the global Lipschitz constant is fundamentally related to the adversarial generalization error: intuitively, their relationship would depend on more fine-grained quantities such as the *distribution* of the Lipschitz constant over the data domain. In fact one can construct toy scenarios using 1-D data and polynomial features for which the global Lipschitz constant could worsen with overparameterization, but generalization error (clean or adversarial) might improve depending on the overall distribution of the local Lipschitz constants. Question for authors: do you think there is any possibility of studying these more fine-grained properties in the future, that might be more reflective of adversarial error, as a consequence of this approach?

-- The results would also be stronger if matching, or at least close upper bounds could be provided, i.e. *there exists* a function within the function class that has sufficiently small Lipschitz constant that decays with overparameterization. This would be required to make the definitive case that overparameterization actually allows us to find functions with a small global Lipschitz constant (which is in fact sufficient for low adversarial error). Alternatively, this would shed light on whether a low Lipschitz constant is reasonable to expect and *necessary* for adversarial robustness; either way, it would be of interest. Perhaps this is possible via an anti-concentration approach, but it would also require characterizing the size of the set of globally L-smooth functions in the function class (which is not needed for the lower bound as one can simply upper bound this by the size of the function class itself). Do the authors think their techniques could be used for an upper bound in the future for the same problem; if so, how?

-- The techniques are currently presented for Lipschitz constant with respect to l2-norm: the more standard quantity in the adversarial robustness literature is the infinity-norm. The authors mention in Section 1.1 that they believe that a variant of the law of robustness would also hold for the infinity-norm, but they do not provide details on this (in particular I am not sure if the techniques will be similar for the case of distributions over manifolds).

Minor caveats/additional context that could be added in the paper:
-- Because of the centrality of the union bounding approach to the proof, the techniques appear unlikely to shed light on the smoothness of specific functions that interpolate training data and arise in practice (e.g. variously regularized neural nets such as minimum-norm, minimum-path-norm, etc). 

-- The results critically constrain the function class to be fitting a non-zero amount of noise, which may not always be the case in practice. A short discussion on whether these results might imply a small Lipschitz constant on regularized function classes and/or noiseless data might be a good addition to the paper.

---- after response ---- 
thanks to the authors for their detailed and well-thought-out response. I've increased my score accordingly. Please see comments below for details.
limitations_and_societal_impact: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work. One suggestion: the authors are encouraged to provide a contextualization of their results with the following work, e.g. in the broader discussion in Section 1.1:

"Rademacher complexity for adversarially robust generalization", by Dong Yin, Kannan Ramchandran and Peter L Bartlett. 

This paper takes a different approach and upper bounds the Rademacher complexity of adversarially robust generalization error for specific functions (and also uncovers extra dimension dependencies).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper describes a universal law of robustness via isopemitry, which states that smooth interpolation requires d times more parameters than usual interpolation. The authors then include a discussion of their results for the MNIST and ImageNet datasets, and go through the proof of the main results. The authors conclude with a discussion of their results for deep learning.
main_review: 1. Originality

The tasks and/or methods are not new. The work is a direct follow-up of [BLN21] and the proof techniques regarding isometry and concentration are not new. Nevertheless, the main result is new and fairly interesting.

2. Quality

The submission is technically sound and the main theorems make sense. A part that may need more explanation or refinement is the speculative discussion with MNIST and ImageNet. The main results are stated with constants, and even though the law of robustness "predicts any such model must have at least nd parameters", it is not clear if it is 100nd or 0.1nd; perhaps some additional clarification on the constant would be helpful. Another part that I feel can be beneficial to add in the paper is a discussion on cases where the main results are tight; i.e., conditions where an if and only if result holds. Additional discussion on the weaknesses of the work would also be helpful. 

3. Clarity

The paper is nicely written and organized. I would think it would be more beneficial to use more of the pages to discuss the implications/significance of the results and put the proof in the supplementary (since the proof takes up almost half of the main text). Some additional comments regarding typos are included in the Section 5 of this main review. Two minor comments on clarity:

a. In Theorem 1, where perhaps it would be nice to add the dependence of epsilon in the equation.

b. In the abstract, particularly the last two sentences, "We prove this universal law of robustness... this law was conjectured in prior work by Bubeck, Li and Nagaraj" gave me the impression that the work confirmed this conjecture for 2-layer NNs and Gaussian covariates, however, in Section 1.2 the authors clarify that "Our results does not actually prove their conjecture,...". I think it may be a good idea to change the text in the abstract to prevent this kind of subtle misinterpretation.

4. Significance

The results continues work on conjectures from prior work due to Bubeck, Li and Nagaraj, and from this theoretical perspective the results are important. However, due to the pure theoretical nature of this work and plenty of the main text occupied by the proof, practical significance is a bit lacking, and perhaps this may be addressed in further revisions.

5. Typos

A minor typo is in Line 36, "theoreof" perhaps should be "thereof".

Update after reviewing comments: Increasing score to 6.
limitations_and_societal_impact: No discussions on societal impact is available.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper shows that if one wants to interpolate the data smoothly, the number of parameters required is $d$ times more than mere interpolation. More precisely, they show that for any function class smoothly parametrized by $p$ parameters, and for any $d$-dimensional dataset satisfying mild regularity conditions, any function in this class that fits the data below the noise level must have its (Euclidean) Lipschitz constant larger than $\sqrt{nd/p}$. 

To demonstrate this, the authors show that for random labels, if the distribution satisfies isoperimetry then either the 0 level or 1 level set has probability upper bounded by $\exp(-d/C^2)$ where $C$ is the Lipschitz constant of $f$. A union bound then gives an upper bound on the probability of a function fitting the data. 

main_review: I think this is a good paper and vote to accept it. I find the result interesting and the paper proves a prior conjecture in the case of polynomially bounded weights. I think the proof is intuitive and clearly presented. 
limitations_and_societal_impact: This is a theoretical paper and of limited social impact.
review_title: null

final_score: rating: 10: Top 5% of accepted NeurIPS papers, seminal paper
review_content: summary: It is generally possible to interpolate train data as long as the number of parameters of our model exceeds the number of training points. The present paper asks how many parameters do we need if we want to interpolate in a smooth manner. If the smoothness is measured by Lipschitzness, the paper proves that one needs at least n d parameters to do so, where d is the ambient dimension (Theorem 1). The main assumptions are i) Lipschitz parametrization of the model with bounded parameters, ii) isoperimetric distribution of the train data, iii) positive noise level. This result, in particular, settles a conjecture by Bubeck, Li, and Nagaraj modulo assumption iii). 
main_review: ***Pros***

 - the proposed result is beautiful and truly interesting for the community. If indeed overparametrization (by a factor d) is necessary for smooth interpolation, this could have practical incidence on the type of model one tries to train on real datasets. This needs, of course, to be supported by other theoretical results and further experimental evidence. Note that such speculative discussion is extensively detailed in the paper (Section 1.1).
 - the theoretical framework is sound and simple enough so that one can imagine building upon it. 
 - the exposition of the paper is very clear.

***Cons***

 - there seems to be a slight inaccuracy in the proof of Lemma 2.1. At the end of p. 5, when lower bounding \norm{Z}^2+2\langle Z,G-F\rangle + \norm{G-F}^2, I find \sigma^2 - \epsilon/6 + 2(-\epsilon/6)-2\langle Z,F\rangle + 0 (using l. 207 and \norm{G-F}^2\geq 0). Therefore the lower bound is \sigma^2-\epsilon/2-2\langle Z,F\rangle. The above display thus reads \langle F,Z\rangle \geq \epsilon /4, not \epsilon /3 and same thing in the statement of the lemma. I did not echo further, but it seems to change the way \epsilon has to be cut before using Lemma 2.1 in the subsequent derivations. To be clear: this is not a major mistake, the proof certainly still holds, but the numerical constants could change. I will increase my score if the rebuttal makes the changes to be made precise (or if I missed something here).
 
***Minor comments and typos***

 - l. 149: missing 2 in the definition of sub-Gaussian. Also t is not defined in this definition.
 - l. 206: comma inside the parenthesis in the definition of G
limitations_and_societal_impact: yes
review_title: null

Meta-review: This paper adds an interesting ingredient to the substantial literature on interpolating / memorizing data using neural networks by asking how things change if the neural network is required to be smooth (Lipschitz). The results essentially show that there is a cost to smoothness, appearing as a multiplicative factor of d in the number of parameters of the model. Smoothness of the model loosely corresponds to robustness against adversarial examples, and thus, the results shed light on the empirically observed phenomenon that sufficiently large models can be made more robust. Significantly, they give fairly precise numerical predictions that may help to guide the practice of deep learning. 
Decision: Accept (Oral)