Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper concerns the Lipschitz constant of two-layer neural networks that fit "generic data sets" exactly.  A key contribution is the statement of two conjectures relating the number of hidden neurons in the network to the Lipschitz constant.  Roughly, to have $O(1)$ Lipschitz constant, the authors conjecture the number of hidden neurons should be on the order of the input dimension.  In a slogan, over-parameterization is needed for robustness.  Proofs are provided for various special cases, relying on results about real symmetric tensors and uniformly random points on the unit sphere.  Overall, this is a very interesting paper.  My main question surrounds the notion of generic data set that the authors use.  Itemized comments follow.

----------------------------------------------------------------

Page 2, definition of generic data set: Can the authors justify the relevance of fitting to such data sets?  Since the labels $y_i$ are iid uniform on $\{+1, -1\}$, one is fitting $f$ to a very unstructured data set in which nearby points x_i on the sphere (or from the Gaussian model) receive different labels.  For such data sets, it somehow does not surprise me so much the fitted function should have a high Lipschitz constant...  If possible, the authors could add intuition on why these data sets may have similar qualitative behavior to more structured data sets.

Page 2, notation: Typo, “where $|| \cdot ||$ denotes the Euclidean norm.

Page 3, Conjecture 1: Do the authors expect the Lipschitz constant needs to be similarly high if $f$ is only required to approximately fit the data?

Page 3, “Our results around Conjecture 2”: Can the authors comment on what role they imagine the activation $\psi$ plays?  Suppose I edit Conjecture 2 by fixing nonlinear $\psi$ satisfying some kind of reasonable conditions.  Should I believe the resulting conjecture?

Page 4, typo: double dot just before “This concludes the proof sketch of Conjecture 2…”

Pages 10-11, Appendix A, Lemma 2: I believe the precise result is that for $d \geq 5$ it suffices to take $k$ at least $\frac{2}{d} \binom{d+p-1}{p}$.  This is by Alexander-Hirschowitz and the result relating the maximum real rank in Blekherman, Grigoriy, and Zach Teitler. "On maximum, typical and generic ranks." Mathematische Annalen 362.3-4 (2015): 1021-1031.

Page 8, proxy for Lipschitz constant: Can the authors prove the “maximum random gradient” is close to the true Lipschitz with high probability for $T$ such as $1000$?

review_title: Concerns Lipschitz constant of two-layer neural networks that fit "generic data sets" exactly. Key contribution is conjectures (and proofs in special regimes) relating number of hidden neurons to Lipschitz constant.  Very interesting  

final_score: rating: 7: Good paper, accept
review_content: **Summary**: 
In this article, the authors investigated the fundamental trade-off between the size of a neural network and its robustness (measured by its Lipschitz constant), in the setting of a single-hidden-layer network with $k$ neurons and (approximately) Gaussian data, by proposing two conjectures, Conjecture 1 and 2, on the (lower and upper bound of the) network Lipschitz constant in perfectly fitting a given data set of size $n$ and data dimension $d$. Some weaker versions of the two proposed conjectures were proven, in Section 4 and 3, respectively. Empirical evidence for the proposed conjectures was shown in Section 5.

**Strong points**: This paper proposed a clear and promising mathematical conjecture to investigate the robustness in neural network models, and provided many examples and explanations on why such conjecture is reasonable. The paper is in general well written: the simple examples in Sec 3.1 and 3.2 make a clear sense of the proposed theory, and solid technical contribution is provided in e.g., the proof of Theorem 2.

**Weak points**: This paper is already in pretty good shape.

**Recommendation**: This is a good paper that made solid contributions to the theoretical understanding of the fundamental trade-off between model size and robustness. I recommend it for publication at ICLR.
review_title: A good paper in good shape

final_score: rating: 5: Marginally below acceptance threshold
review_content: SUMMARY
#######

The present paper proposes a study of the tradeoff between the number of neurons $k$ and the Lipschitz constant $L$ of a 2-layers neural network $f$ that fits a training dataset, i.e. $f(x_i) = y_i$ for all $(x_i, y_i)$ in the training set.

To that end, authors consider "generic datasets" such that the marginal distributions of the input random vector $X \in \mathbb{R}^d$ and the random label $Y$ are the uniform distributions over the $\mathbb{R}^d$ sphere with radius 1 and the set $\{-1, +1\}$ respectively.

Authors essentially formulate two conjectures (in the following constants are omitted for the sake of simplicity):

(1) If $f$ is a 2-layers NN with $k$ neurons fitting the data, then its Lipschitz constant $L$ satisfies (w.h.p.): $L \ge \sqrt{n/k}$.

(2) If $n/d \le k \le n$, then there exists an activation function such that w.h.p. there exists a 2-layers NN with this activation function that fits the data and satisfies $L \le \sqrt{n/k}$.

These two conjectures are not formally proved, but studied in restricted settings as follows.

Conjecture (2) is first proved in the case $k=1$, and $k=n$. For an intermediate value of $k$, only $L \le n \log(d) / k$ is proved. The proof technique builds upon the possibility to separate datapoints into different caps, and then uses the ReLU activation function to impose different values on the different parts of the space.

If one allows approximate fitting, i.e. $|f(x_i) - y_i| \le \epsilon$, then the activation function $t \mapsto t^p$ allows to construct a 2-layers NN with Lipschitz constant lower than $\sqrt{n/k}$.

As for conjecture (1), it is proved for the Lipschitz constant over $\mathbb{R}^d$ (which is by definition bigger than that over the sphere) in two particular cases: (a) $n=d$, activation function = ReLU, and no biases, and (b) activation function = $t \mapsto t^p$ and no biases.

Two synthetic experiments are finally provided.



OPINION
#######

As for positive aspects, I find that:
- the paper is globally clear and well written
- the mathematical aspects are thoroughly dealt with


However, I find this contribution insufficient with respect to the following points:

- my first main concern is about the assumption made on the architecture of the neural network. This 2-layers architecture seems very restrictive, all the more that the second layer is simply linear. Overparametrization is also thought in terms of number of layers, and I doubt that the analysis of shallow models (although they are universal approximators) could be extended to deeper ones in a straightforward fashion.

- my second concern is about the generic dataset assumption. Again, recent understanding on the generalization capacity of neural networks rather consider that inputs are very structured, and actually concentrated on a lower dimensional manifold. Hence, the uniform distribution assumption seems quite far away from this realistic setting.

- I perfectly understand that you have to start somewhere, but the above two limitations make me think that the proposed analysis is hardly transferable to real world interesting frameworks. This is all the more true that even with these assumptions on the architecture and the data distribution, conjectures are only partially validated.

- although the constructions of the data fitting predictors are interesting, Sections 3.1 and 3.2 seem to me a bit superfluous. The constructions could have simply been mentioned in a sketch of proof of Thm 1, the central result of this Section, that incidentally does not match the conjecture. In contrast, the cases $k=1$ and $k=n$ rather appear as curiosities, insufficient to support a conjecture.

- I am not convinced of the relevance of Thm 3. It basically proves nothing as it applies to an upper bound of the Lipschitz constant. This is not a positive contribution supporting conjecture (1), but rather a non-negative side result, from which it is (very) hard to gain intuition on whether the conjecture is true or not. Perhaps a discussion on how tight the first inequality is may help.

- as for Thms 4 et 5, the fact that biases are are not allowed appear to me as another example (with the fact that ReLU is always chosen) to dismiss the non-linearities that might appear in the NN studied. Although I agree it makes the analysis much easier (feasible), this fundamentally breaks with all that is thought to be responsible for the good NN learning capacity, making the subsequent study less convincing.

- this brings me to the next point, which is the comparison to kernel methods. Indeed, many elements in the paper suggest a tight connection with kernel functions, for which the Lipschitz constant is easily computable. Indeed, the reproducing property gives that it is essentially equal to the Lipschitz constant of the feature map multiplied by the RKHS norm of the function. For instance, eq. (1) may be viewed as the standard dual expansion of a kernel function, associated to the kernel $k\colon (x, y) \mapsto \psi(<x, y>)$ (the latter is a valid p.s.d. kernel if $\psi$ is polynomial, or the limit of polynomials for instance), with support vectors $[w_l, b_l]$, and applied to the point $[x, 1]$. Of course, eq. (1) differs from standard kernel methods in the sense that the support vectors are not the datapoints, but some weights to optimize, in addition to the coefficients $\alpha_l$. Yet, a comparison might be insightful. I stress that the parallel is even more striking in the function proposed in the proof of Thm 2, where support vectors are datapoints as in standard kernel methods. More generally, considering a potentially very large shallow network reminds the structure of a kernel function, with infinite dimensional feature map. The idea of considering one neuron/support vector per datapoint, as suggested by authors to ensure a $O(1)$ Lipschitz constant is also a key feature of these nonparametric method. Removing biases only makes both models closer, as one does not need to resort to the artificial reparametrization $x' = [x, 1]$ to explicit the similarity. The overall comparison might not be significant for the precise goal pursued by the authors, but so many similarities deserve to be mentioned at least in my opinion. Notice that disjoint caps would be equivalent, with a rbf kernel, to diminish the bandwidth until $k(x,y)$ is globally null when $x \ne y$.

- the experimental validation is quite rudimentary, and yet duplicated. Fig. 1 is totally redundant with Fig. 3, authors could make better use of the space gained by the deletion of Fig. 1

- a minor comment would be on the clarity of the vocabulary: sometimes authors speak about "robustness", sometimes it is "smoothness", but finally all is about the Lipschitz function. I feel that sticking with the latter would be less misleading, as very few is said about robustness, apart from that aspect.

- here is a list of things that could be better exposed:
a) it was not clear for me from eq. (2) and the definition of generic samples given in the 1st paragraph of page 2 if the $y_i$ where reals or binary labels.
b) about generic data, I had to assumed that authors were speaking about marginal distributions when referring to "with $x_i$ uniform", this should be better explicited.
c) more generally, the presentation of the realizations (the $x_i$'s), the underlying random variable, and its distribution was not very neat (e.g. "where $x_i$ is i.i.d. uniform" suggests that $x_i$ is the r.v. and not the realization)
d) in conjecture (2), are the $C$ constants the same for both inequalities? Despite the warning made in the notation paragraph, I found it confusing. The fact that $c$ and not $C$ is used in Sec. 3.1 also
e) the $\cdot$ is used for both scalar multiplication and dot product
f) maybe some references about results on the caps could be helpful

- here is a list of typos:
p.1 make prediction*s*
p.1 do*es* indeed help
p.2 the Euclidean *?*
p.2 whose value*s*
p.2 i*.*i*.*d*.*
p.4 \sqrt{2}*..*\|Y\|
p.4 in other word*s*
p.5 would be *to* use
p.6 missing absolute value for Lipschitzness in the proof of Thm 3



OVERALL EVALUATION
################


Although the subject is of interest, authors only propose partially validated conjectures, building upon assumptions that do not match the framework in which neural networks have been shown to perform well (deep architecture, structured data). Hence, I found the contribution (e.g. Sec. 3.1, 3.2, Thm 3) insufficient to warrant acceptance.



--- EDIT POST REBUTTAL ---

I thank the authors for their response. I have read other reviews and answers too. I have appreciated the revisions (especially the proof for ReLu with biases). I am still a bit concerned by the applicability due to the assumptions on the architecture/data generation process,  but will not fight acceptance if other reviewers feel strongly about it (I changed my score from 4 to 5 to reflect this position). I understand that authors do not want to present unfinished/ongoing work, but mentioning the parallel with kernel methods (at least as a research direction) would seem fair to me.
review_title: Partially validated conjectures with assumptions not matching "real world neural networks"

final_score: rating: 5: Marginally below acceptance threshold
review_content: This submission studies the relationship between the hidden-layer size of a two-layer neural network and its robustness, that is measured by its Lipschitz constant here. This paper first makes a conjecture that any two-layer neural network with k-neurons and Lipschitz activation functions that perfectly fit the data must have its Lipschitz constant larger than \sqrt(n/k) (with n being the number of data points and k the number of hidden neurons). An implication of this conjecture is that overparameterization can help improve the network robustness (namely, by making \sqrt(n/k) with sufficiently large k). Furthermore, a weaker version of this conjecture was proved by replacing the Lipschitz constant with an upper bound on the spectral norm of the weight matrix. The conjecture was further proved for ReLU activation function and polynomial activation function in different data regimes. These theoretical findings were finally evidenced with numerical results. 

This paper proposes interesting ideas and supported them with mathematical proofs, though lacking a bit rigor sometimes. The paper is also sufficiently well-written; at least the main technical ideas are easy to follow, but there are several grammatical errors, some of which are listed below along with several major comments.

i) What kind of robustness of this paper is referring to? against random noise/perturbation in the input data or adversarial attacks? Link between this notion of neural network robustness and the neural network Lipschitz constant is not clear. From what I understand, the results are more like quantifying the stability of the neural network output to random noise (e.g., generated from Gaussian distributions or spherical distributions considered in this paper; rather than robustness against purposefully constructed attacks); see also [Arora et al'2018, Stronger generalization bounds for deep nets via a compression approach] for related study; and please discuss the difference and relationship between this paper and this [Arora et al'2018]. 

ii) The probabilistic statements could be made more precise in the conjectures. What is deemed random here? What kind of data are generic data? See e.g., [Balan et al'2006, On signal reconstruction without phase] for “generic frame” in the context of phase reconstruction. But not always, generic data are random.  

iii) In the proof of Theorem 3, the ||is missing on the left. 

iv) Both "two-layers neural networks" and "two-layered neural networks" are used in the paper. Please unify and keep consistent. It seems more grammatically reasonable to use 'two-layer neural network.'

v) The major concern is some of the claims were made after relaxing a number of conditions; e.g., approximate fit rather than exact fit was proved for the two special cases, which is a bit different than the conjectures; as well as how to generalize to more "generic" data than the special ones studied. 
review_title: Interesting theoretical results and conjecture on robustness of two-layer neural networks

Meta-review: The paper studies the Lipschitz properties of neural networks — in particular, two layer neural networks that interpolate generic datasets. It conjectures a “size robustness tradeoff”: in this setting, the number of neurons required to interpolate with an O(1)-Lipschitz function is proportional to the number of data points n, while the number of neurons required for interpolation alone is proportional to n/d, where d is the data dimension. More precisely, the conjecture is that the best achievable Lipschitz constant is proportional to $\sqrt{n/k}$, where $k$ is the number of neurons. The paper proves weaker versions of both sides of this conjecture: it proves that a spectral upper bound on the Lipschitz constant is lower bounded by $\sqrt{n/k}$ and that there exist networks achieving this Lipschitz constant when $k ~ n/d$ and $k ~n$. The paper also provides experiments supporting its claims, with the caveat that the actual Lipschitz constant is a worst-case quantity that cannot be directly observed. 

Pros and cons:

[+] The paper identifies a novel (conjectured) phenomenon involving the dependence of the Lipschitz constant of an interpolating network on the degree of overparameterization. In words, Lipschitz interpolation requires significantly more neurons than mere interpolation. This observation seems likely to stimulate future work. 

[+] The paper provides relatively simple and rigorous proofs of simplified versions of its conjectures (both upper and lower bounds on the achievable Lipschitz constant). 

[+] The exposition is technically clean, and the paper is clear on the limitations of its analyses. 

[-] The setting of the paper’s analysis seems somewhat mismatched with the practice of deep learning. The data are assumed to be generic, where neural networks excel in fitting structured data. Several reviewers noted this mismatch and raised concerns about whether this conjectured/proved tradeoff on generic data carries over to structured datasets. 

[-] A technical limitation is the shallowness of the network: controlling the Lipschitz properties of deep networks is much more challenging at a technical level, because one needs to argue that for the worst input, features propagate in a “generic” fashion. It is technically challenging to avoid exponential dependence on depth. 

[-] The paper obtains only partial progress towards proving its conjectures — for example, it shows that it is possible to interpolate with a Lipschitz constant of $n \log n / k$, where the conjectured bound is $\sqrt{n/k}$. 

[-] Comparing to kernel methods would help to better contextualize the results, since in a similar setting, kernel methods could also potentially be analyzed via localization arguments. 

Overall, the paper conjectures a novel phenomenon around size/robustness tradeoffs in interpolating neural networks. While the paper's conjectures have the potential to stimulate further empirical and theoretical work, the reviewers (in particular R1 and R2) note a number of significant limitations to the paper’s analysis. In light of these issues, the paper falls below the par for acceptance. 
Decision: Reject