Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies square loss theoretically in the NTK regime. In this particular regime, authors find indications that square loss might lead to (adversarially) robust models and good calibration. Authors then run experiments outside of the NTK regime, on CIFAR-10 and CIFAR-100, to compare the robustness and calibration performance of square loss with cross-entropy.   
main_review: My main concern about this submission is its relevance and importance. Most realistic experiments in this paper is on CIFAR-10/100, however I am not sure if the experiments included in the submission are convincing. Let me first describe my concern about the robustness experiments. 

Authors measure the robustness of the square loss and cross entropy models using two kinds of adversarial attacks, PGD and AutoAttack. In general results using white-box adversarial attacks can be hard to interpret, as the performance of white-box attacks depend heavily on implementation details and attack hyperparameters. This was one reason historically that adversarial defense papers would get published in leading conferences only to be broken in less than a month. For the purposes of this submission, adversarial attacks are further concerning since the hyperparameters of these attacks were designed and optimized for cross-entropy loss, but the authors apply them to square loss here without re-optimizing them. I acknowledge that AutoAttack contains black-box attacks, such as SquareAttack, which may not suffer as much from this problem. However, it is not clear to me how much of the improvement of square loss on AutoAttack robustness is due to its improvement of SquareAttack. Furthermore, it is not clear to me if an improvement from 1% to 3% accuracy is significant, both of them seem low enough to be effectively useless. For robustness evaluation, I would recommend a simpler black-box noise such as Gaussian noise on the input with several noise scales. Another interesting experiment would be to evaluate CIFAR-10-C performance, which contains lots of noise-based corruptions that relate to the definition of robustness used in this submission.   

Next concern is about the calibration results. It is nice to see that on the models tried by the authors, SL leads to an improved ECE. To evaluate the significance of this improvement, I would suggest including comparisons to ECE measures reported by published papers for the same model. This way the reader can see if the SL can lead to an improvement on ECE relative to the implementation of the same neural networks implemented by others. I think it would also be more helpful to train a more conventional and performant model such as WRN-28-10, for which there are plenty of available comparisons in literature.    
summary_of_the_review: Theoretical analysis is limited to toy models. Empirical studies should be improved demonstrate that square loss leads to more robust and calibrated models.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a theoretical analysis of the squared loss for classification where cross-entropy loss is often the standard choice in both theory and practice. The authors show under some assumption of the data and the NTK regime, GD on squared loss enjoys fast convergence, strong robustness and good calibration. They also provide empirical results.

main_review: Pros:
+ New convergence results and insights of squared loss for classification. 
+ The results hold for a non-separable case using the Tsybakov noise condition.
+ Additional insights on the robustness and model calibration.

Cons:
- The analysis under the NTK regime is somewhat standard and may not be practical. For example, when mu=0, GD operates under the kernel regime, which do not explain some phenomenon observed in practice such implicit bias.
- There are a number of restrictive assumptions, for example, C.1, C.2 and C.3. In linear regression (Du et al., 2019), C.1 is sufficient, and C.2 seems to be sufficient for logistic regression (Ji et al. 2020). 
- The experimental results on real data reinforce but perhaps repeat previous work.


Questions:
1. When is the definition of separability (when \eta only takes either 0 or 1 in two separate sets) more general than the linear separable case?
2. How does this result compare to other results of implicit biases of gradient descent for separable and non-separable data? Similarly, how does the convergence rate compare to that of Ji et al., 2020, which uses logistic loss and seems to assume less restrictive assumptions? A discussion would be helpful for readers.
3. It looks like the regularization term is a crucial part in the analysis important for this analysis. Does the analysis carry over if \mu is exactly zero?
4. Paragraph under Theorem 3.1: where is the (d-1)\kappa that you’re mentioning?
5. Assumption C.1: why does delta_n depend on n? When n=1, Eq. (A.3) implies that it is positive, right? Also, \lambda_0 scales with poly(1/n), when n -> infty, is \lambda_0 = 0?
6. Can you say anything about the robustness of squared loss to outliers? Empirical evidence is sufficient. Assumption C.3 seems to be related to that.

Minor:

1. Equation (2.1): the first expectation is taken over both (X, Y) ~ P? What does expectation over f(X) >= 1 mean? It can be re-written over X in a more precise way.
2. Please consider using \mathbf{a} instead of capital A for the second layer weight because the latter can be easily confused with a matrix. The objective in (2.2) gives the impression that A is optimized, but it is not. The analysis would be very different with a joint optimization over both W and A.
3. The color bar in Figure 1: how probability P[y=1] can be negative? I don’t see any color difference in each of the plots.
summary_of_the_review: See above
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a theoretical guarantee for square loss in the neural tangent kernel (NTK) regime. Whether classes are separable or not, the convergence rate is proved to be improved. 
main_review: Strengths:
1.	The theoretical analysis of this paper is rich, including generalization and robustness theory.
2.	It fully verifies the theoretical advantages of square loss in several perspectives and provides the corresponding experimental verification for theoretical results in the neural tangent kernel (NTK) regime.

Weaknesses:
1.	When introducing the theoretical results, we should make a detailed comparison with the existing cross-entropy loss results. The current writing method cannot reflect the advantages of square loss.
2.	The synthetic experiment in a non-separable case seems to be a problem. Considering the nonlinear expression ability of neural networks, how to explain that the data distribution illustrated in Figure 1 is inseparable from the network model?
3.	This paper presents that the loss functions like hinge loss don’t provide reliable information on the prediction confidence. In this regard, there is a lack of references to some relevant literature. [Gao, 2013] has given a detailed analysis of the advantages and disadvantages between the entire margin distribution and the minimum margin. Based on this, [Lyu, 2018] designed a square-type margin distribution loss to improve the generalization ability of DNN.

[Gao, 2013] W. Gao and Z.-H. Zhou. On the doubt about margin explanation of boosting. Artificial Intelligence 203:1-18 2013.

[Lyu, 2018] Shen-Huan Lyu, Lu Wang, and Zhi-Hua Zhou. Improving Generalization of Neural Networks by Leveraging Margin Distribution. http://arxiv.org/abs/1812.10761


summary_of_the_review: In a word, I agree with the argument put forward in this paper and think its theoretical conclusion is correct. If the author can provide the theoretical comparison between SL and CL and supplement some missing citations of related work, I will more recognize the integrity of the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the non-parametric convergence rate of neural network (NTK regime) under tsybakov's noise condition (low noise with large margin) and discussed the potential application of the theoretical result on the robustness of neural network and calibration results. 
main_review: Pros:
- The non-parametric fast rate under the Tsybakov noise condition in the NTK Regime.
- Results of model calibration are impressive.
- some theory and experiment have gap

Weakness:
- No comparison between L2 and cross-entropy loss
- lack of reference

Detailed comments:

**In terms of theory** The paper investigated standard setting of low noise condition (theorem 3.1) and achieves the exponential convergence rate for the separable case. The most interesting part is Theorem 3.4 (Calibration error). However, Theorem 3.4 doesn't have the tsybakov's noise condition kappa in the final convergence bound. Is it standard in this setting? Is it tight? It's slower than the convergence rate of the Excess risk?

**Simplex label coding** I guess most of the prove have been done by the neural collapse literature [7,8] , and it's also true for the CE loss [9].

The paper gives positive results for L2 losses,however, the paper didn't show any results that the cross-entropy loss is not good. The convergence of CE loss can be slow in the terminal phase of deep learning training [6] (O(1/log t)), but if you train longer, maybe all the properties you proved can appear. I hope the author can provide that why CE loss is not good enough.

**Adversarial robustness** The gain of SL interms of the adversarial loss is actually not significant, I would to suggest the author to try more norms(l2 norm robustness as example) can be tried in this setting. In the experiment I can't see what's the norm the author is using for PGD.(The number here looks like l_inf norm, but in theory theorem 3.3. it's l2 norm. I see a mismatch here.) For l2 robustness, you can further try randomized smoothing [5].


**Missing Reference** Optimal rate for NTK for regression [1,2] and outof NTK regime (but no optimization)[3,4], both of the papers using l2 loss.

[1] Nitanda A, Suzuki T. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime[J]. arXiv preprint arXiv:2006.12297, 2020.

[2] Hu T, Wang W, Lin C, et al. Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2021: 829-837.

[3] Schmidt-Hieber J. Nonparametric regression using deep neural networks with ReLU activation function[J]. The Annals of Statistics, 2020, 48(4): 1875-1897.

[4] Farrell M H, Liang T, Misra S. Deep neural networks for estimation and inference[J]. Econometrica, 2021, 89(1): 181-213.

[5] Cohen J, Rosenfeld E, Kolter Z. Certified adversarial robustness via randomized smoothing International Conference on Machine Learning. PMLR, 2019: 1310-1320.

[6] Lyu K, Li J. Gradient descent maximizes the margin of homogeneous neural networks[J]. arXiv preprint arXiv:1906.05890, 2019.

[7] Fang C, He H, Long Q, et al. Layer-peeled model: Toward understanding well-trained deep neural networks[J]. arXiv preprint arXiv:2101.12699, 2021.

[8] Zhu Z, Ding T, Zhou J, et al. A Geometric Analysis of Neural Collapse with Unconstrained Features[J]. arXiv preprint arXiv:2105.02375, 2021.

[9] Ji W, Lu Y, Zhang Y, et al. An Unconstrained Layer-Peeled Perspective on Neural Collapse[J]. arXiv preprint arXiv:2110.02796, 2021.


summary_of_the_review: my main two concern:
- missing discussion of the relationship between line of research of using NN as a non-parametric estimator.
- I don't see any discussion of the specialty of the l2 loss. The paper don't answer the question of how l2 loss and CE loss is different.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies wide neural networks trained with the square loss in the neural tangent kernel regime from a theoretical perspective. In particular, it provides generalization error bounds, robustness and calibration results and makes a connection to supervised contrastive learning. Furthermore, an empirical comparison between cross entropy and square loss is provided.
main_review: **Pros**
+ The paper improves on previous results on the convergence of neural networks, by deriving a faster convergence rate (however under stronger assumptions). 

+ In contrast to prior work, which assumes data to be linearly separable, the paper studies the more general and much more realistic setting of separable data (and also of unseparable data).


**Cons** (see also detailed comments below)
- The presentation of the theoretical results is superficial and crucial information can only be found in the appendix (see detailed comments below)

- The content and setting of the experiments differs from the theoretical contributions and thus they do not corroborate them.

- There are some claims in the paper, which need more backing.


**Detailed comments:**
- Presentation of the results:

  - Crucial information is missing from the main text and can only be found in the supplementary material, most importantly, the assumptions under which the theorems hold. Furthermore, these assumptions are only stated, but not discussed. In consequence, it remains unclear, whether these assumptions are, for example, fulfilled in practice, might be loosened, or and where they come from.

  - The theoretical results are not properly stated as they do not specify what the respective variables mean. This becomes a real issue, when the variables have not been defined in the text so far (or at any later point).  
For example, Theorem 3.1 is a asymptotic equality for some function $\hat f$, which is not specified in the main text. In fact, $\hat f$ is only defined in the passing, somewhere in the supplementary material as a solution of some minimization problem stated one page earlier. However, then one needs to look up the function space on which the minimization occurs, which in turn is specified two pages earlier. But this is only helpful, if the reader already knows, what the "reproducing hilbert space generated by the neural tangent kernel on $\mathbb S^{d-1}$" is.  This is clearly suboptimal.  
Similarly, Theorem 3.2 contains a summand $\delta$, which is not defined anywhere, and appears to can be chosen $=0$ anyway.
Theorem 3.6 contains  the imprecise formulation "no matter how complicated $\Omega_1 \cup \Omega_2$ are". Does this mean for any $\Omega_1 \cup \Omega_2 \subset \Omega$?. It would also improve the readability, if the definitions of $\Omega_1$ and $\Omega_2$ are restated in the theorem or in its proximity.

- Experiments:
  - The experiments are somewhat disconnected from the theoretical part. In the experiments, a comparison between the squared loss and the cross entropy loss is made, similar to the empirical study [1]. However, the theory exclusively covers properties of the square loss, and thus does not make any statement or prediction whether training with either of these loss functions is preferable. From my perspective, a comprehensive on the extent to which the theoretical predictions hold would have been more valuable.

  - Similarly, the experiments are not designed according to the presented theory. The theory mainly treats  1-hidden-layer networks, whereas experiments use either 2-hidden layer experiments (5.1) or ResNets (5.2). Furthermore, the 500 hidden neurons in (5.1) do not seem to be wide enough, such that the assumptions of the theorem are fulfilled.

- Not sufficiently supported claims:
  - Remark following Theorem 3.4  
"Under {0,1} coding, the estimator would be $f_{W,A}$ itself. The ${L_\infty}$ consistency doesn’t hold for cross-entropy trained neural networks, due to the form of the optimal solution $\log(\frac\eta{1-\eta})$. With limited capacity, the network’s confidence prediction is bounded away from 0 and 1."
This needs to be discussed in more detail, as Theorem 3.4 is of asymptotic nature (infinite width), but the presented argument only rules out networks with limited capacity.

  - Regarding the simplex label coding  
  "The one-hot coding forces the features for each class to be orthogonal in the unit sphere, which is problematic for large K since the representations are all cramped into the corner (positive direction in each dimension) taking only $2^{-K}$ of the entire sphere.
In comparison, maximally separated K points on the unit sphere is the better choice, which coincides
with the vertices of a (K-1)-simplex in K-1 dimensions."  
From my understanding, this not an issue. As has already been shown in the neural collapse literature, the one-hot encoding leads (at optimum) to a simplex coding in the penultimate layer. See for example [2].


- Misc.
  - Proposition 4.2 has already been proven in [3] and in a more general case in [4]. Furthermore, here the proof appears to only cover the special case of 2 instances per class.

  - The train and test data in Figure 1 are very difficult to distinguish.

References:  
[1] Like Hui and Mikhail Belkin, Evaluation of neural architectures trained with square loss vs cross-
entropy in classification task, ICLR 2021  
[2] DG Mixon, H Parshall, J Pi, Neural collapse with unconstrained features. arXiv:2011.11619  
[3] C. Fang, H. He, Q. Long, and W. Su, Exploring deep neural networks via layer-peeled model: Minority  
collapse in imbalanced training, Proceedings of the National Academy of Sciences, 2021  
[4] Florian Graf, Christoph Hofer, Marc Niethammer, and Roland Kwitt, Dissecting supervised contrastive
learning, ICML 2021  
summary_of_the_review: I am not very familiar with the related work and thus cannot really evaluate the papers significance and potential impact. That being said, the paper is difficult to navigate, as crucial information lies in the appendix and the experiments do, from my perspective, not really corroborate the theoretical contribution. Therefore I cautiously give a score of 5.
review_title: null

Meta-review: The paper contributes a theoretical understanding of training over-parametrized deep neural networks using gradient descent with respect to square loss in the NTK regime. Besides giving guarantees on the classification accuracy using square loss, authors reveal several interesting properties in this regime including robustness and calibration. 

The problem studied here is exciting and very relevant. The current version, unfortunately, has some shortcomings. For example, under a margin assumption, the authors show that the least-squares solution finds something with the margin and, therefore, it yields “robustness.” There is no quantification of how “robust” is the trained model, what is the threat model, what if the noise budget is larger than the attained margin. In general, the analysis lacks any careful finer characterization or quantification of the claimed properties. Besides, as was pointed out, the setting of the neural tangent kernel regime is somewhat limited and to some extent impractical. The assumptions under which the results hold further make the setting of the paper significantly restrictive. 

The writing can be improved with more emphasis on the novelty and significance of the contributions. Currently, all of the assumptions are buried in the appendix and the main paper is not even self-contained. I believe the comments from the reviewers have already helped improve the quality of the paper. I encourage the authors to further incorporate the feedback and work towards a stronger submission.
Decision: Reject