Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a second-order algorithm for training neural networks, in the L2 regression setting. It provides a theoretical analysis of its complexity in the over-parametrized regime. It does not provide empirical validation of the method, or an implementation.
main_review: This paper provides an algorithm for training neural networks in the over-parametrized regime. The authors go to great length to show that under good implementation which exploits various structural properties (low rank in particular), the runtime complexity of the algorithm should make it practical. It would be nice to provide empirical validation of the method. The results are not surprising: the gains come from careful attention to these structural properties, and extend Cai et al 2019. I consider this a strength for this paper: providing a precise practical guideline on implementation, while providing theoretical convergence guarantees, is a welcome contribution. The paper's diffusion would of course profit a lot from empirical validation + a code release. Do the authors have such an implementation handy?
I believe this paper is a good contribution to the field -- on the other hand, it would be made much stronger with such an implementation. I'm therefore on the fence on acceptance at this time: I want to encourage authors to provide this implementation.

Comments:
- Can you give the meaning of $m$, $n$, $L$, $\epsilon$ before they are used in the introduction?
- What definition of "over-parametrized" NN are you using? It seems that the rank of the jacobian is at most $n$ where $n$ is the size of the mini-batch, in practice? Is this correct?
- The paper (and in particular Theorem 1.1) uses the L2 error -- is this result extendable for any (convex? smooth?) loss function? Can you explain in the main text why the L2 error and Relu activations are necessary, and where the analysis/algorithm break in the more general case? 
- The limits of the method are hardly discussed in the main text.
- It might be easier for the reader to follow if the contributions were given before the informal theorem statements.
- Other practical second order methods have been proposed for neural network optimization. In particular, how does this method compare to AdaHessian? https://arxiv.org/pdf/2006.00719.pdf AdaHessian uses a diagonal approximation to the Hessian. How is it related to K-fac ? https://arxiv.org/pdf/1503.05671.pdf                                            
- This sentence "A smarter way is to instead of using the n × n Gram matrix for neural tangent kernel, however this would still incur a cost of O(nm2) per iteration, since each gradient is an m×m matrix and the Jacobian consists of n such gradients." isn't clear. What are you proposing here?
- There are many typos and sentences which are difficult to follow. e.g. Step 2 paragraph (page 6). "ethnic implications" rather than "ethics implications". It would benefit from an attentive proof-reading.

summary_of_the_review: I believe this paper provides good theoretical results on a new second order method for optimizing neural networks in the over-parametrized setting. Content-wise, I'd strongly appreciate empirical validation / implementation. On the formal side, the paper is a bit hard to follow, and contains many typos. It would benefit from careful proof-reading, and correction. I do not recommend acceptation in the current state of the paper, but could be convinced otherwise.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the training algorithms for multi-layer over-parameterized neural networks. In particular, this paper starts from gauss-newton-methods and incorporates tensor-based sketching techniques and preconditioning to improve the per-iteration computational complexity. As a result, the proposed algorithm can find the global solution within the time that is subquadratic in the network width.
main_review: My first concern is regarding the intuition of this paper. The author claims in the introduction that “it is increasingly evident that first-order methods are becoming a real bottleneck for many practical applications” because the convergence rate is typically slow, i.e., requiring $\mathrm{poly}(n, L, log(1/\epsilon))$ to converge, while second-order method enjoys a much faster convergence rate ($\log(1/\epsilon)$). This is true in terms of the iteration complexity, but it is also true that the per-iteration complexity of the first-order method is much lower (could be lower by $\mathrm{poly}(m)$, while $m$ itself is a high-degree polynomial of $n$), then it is hard to directly claim that first-order method is not as efficient as second-order method.

In order to demonstrate the efficiency of the second-order method, the authors may need to characterize the total computational complexity of both first-order and second-order algorithms, rather than the \textit{cost per iteration}. This could be a more fair comparison to justify the better performance of second-order methods.

It is known that when the data distribution is good, the neural network does not need to be that large to achieve perfect training accuracy. For example, [1,2] show that when the data are well separated by the neural tangent kernel, polylogarithmic widths are sufficient. My suggestion is that the analysis should not be restricted in the setting where $m$ is super large, but consider a wide range of different $m$, and identify under which conditions on $m$, the proposed algorithm could outperform previous ones and vice versa.

1. Ji and Telgarsky, Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks. ICLR 2020.
2. Chen et. al., How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?. ICLR 2021.


Minor comments:

Could you elaborate on why the update rule in Step 1 can be solved via minimizing the second equation after Step 1?

Can the same algorithm be applied to classification problems, like [3, 4]? 

3. Zou et al., Gradient descent optimizes over-parameterized deep ReLU networks. Machine Learning  2019
4. Cao and Gu, Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks, NeurIPS 2019


summary_of_the_review: This paper is theoretically sound but could be further improved based on my comments.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper aims to propose a second-order algorithm for training of neural networks with very large widths. The main claim is that the computation cost of each iteration of the proposed methods is sub-quadratic in terms of the network width.  
main_review: 1: [motivation and claims about the literature] 

> In the first paragraph of introduction, the authors claim that “most theoretical works focus on training on-hidden layer networks”. This is not the case. 
>>a), quite a few of the cited papers are theoretical analyses on *deep* neural networks. For example, Jacot et al (2018), Du et al (2019a), and Allen-zhu et al (2019 a, b), which are listed just above this claim in the paper. 

>>b), the paper misses several theoretical works on *deep* neural networks. For example, see the references: Lee et al (2019), Liu et al (2020 a,b).
There should be more works on deep neural networks, and I suggest the authors have a more complete query of the literature before making the claims.

> The authors claim in page 1 that “ convergence rate (of first-order methods) is typically slow in non-convex settings …”. I cannot agree with this. For example, in both Du et al (2019a) and Liu et al (2020a), exponential convergence rates on over-parameterized neural networks are obtained for gradient descent methods. Typically, the setting is non-convex, see Liu et al (2020a). For comparison, the proposed method in this paper does not have a faster rate than those two.

> I am not clear how the author got this claim: “it is increasingly evident that first-order methods are becoming a real bottleneck for many practical applications”. The authors should provide evidence. 

> The paper claims a running time of O(m^2) for first-order methods, like gradient descent. However, with parallelism this running time can be greatly reduced.

2: [Paper structure] 
One uncomfortable thing about this paper is that all the formal statements (e.g., theorems, assumptions) are not shown in the main text, but are deferred to the appendix. Even the formal version of the proposed algorithm is also not displayed in the main pages. In the first 9 pages, there are only informal statements and intuition. I strongly suggest the authors put the main theorems and algorithm, as well as key analysis, in the main text, and just put tedious proof or unimportant details into the appendix. 

3: [practicality]
In practical cases, the network width m is never too large, compared to the data size n. In these cases, the proposed algorithm seems to have no advantage compared to gradient descent methods, in terms of the computation cost. Moreover, the complicated design of this algorithm may make it not favorable to practitioners. 


References:

Lee, et al. Wide neural networks of any depth evolve as linear models under gradient descent. NeurIPS, 2019.

Liu, et al (a). Toward a theory of optimization for over-parameterized systems of non-linear equations: the lessons of deep learning, Arxiv: 2003.00307, 2020.

Liu, et al (b). On the linearity of large non-linear models: when and why the tangent kernel is constant. NeurIPS, 2020.
summary_of_the_review: The main text of the paper is not self-containing and not justifiable (suggest to reorganize the paper). 
Several claims about the literature are not accurate.
No advantage compared to gradient descent methods for practical scenarios.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 1. This paper proved that the second-order method can minimize the training loss in linea rate on multi-layer over-parameterized neural networks. This analysis relies on the connection between neural tangent kernel and over-parameterized neural networks.
2. This paper also reduced the per-iteration cost of second-order methods to $\widetilde{o}(m^2)$ where $m$ is the hidden layer width, by combining Gram-Gauss-Newton method, tensor-based sketching, and efficient data structures that maintain low-rank representations. 
3. This paper also designed an algorithm to efficiently solve a regression problem in which the matrix has its rows being tensor products of two vectors. This algorithm may be of general interest. 
main_review: This paper is clearly written. The detailed proofs are left in the appendix and the authors explained the high-level proof techniques in the main text. The pros and cons are as follows.

Pros. 
1. As far as I know, this paper is the first work that studied the convergence of second-order methods in multi-layer neural networks. Some of the analysis techniques can be useful in future studies. 
2. This paper reduced the per-iteration cost of second-order methods by combining the Gram-Gauss-Newton method, tensor-based sketching, and preconditioning. It's a crucial challenge in second-order methods to reduce the per-iteration cost. The ideas in this paper can inspire new algorithms that enjoy lower per-iteration costs.

Cons.
1. The convergence proof of second-order methods seems very similar to the NTK proof for first-order methods. I understand there are some differences in proof details, but I still wonder if there is any conceptual difference in the proof. 
2. The linear convergence has been established for first-order methods in similar settings. It seems to me that this paper does not show any benefits of second-order methods over first-order methods in this over-parameterized network setting.
3. The convergence analysis is restricted to the NTK regime. However, in practice, neural networks are not trained in the NTK regime and also achieved better performance in test data than the neural tangent kernel.
4. The reduction of the per-iteration cost relies on the assumption that $m\gg n$, which is hardly true in practice. Therefore, I am concerned about the practicability of the proposed algorithm. It can be helpful if there are empirical experiments that verifies the performance of the algorithms in standard architecture and realistic data set. 
summary_of_the_review: In general, I appreciate the technical depth of this work as a theory paper. And I think the techniques for reducing per-iteration cost can be useful in future studies. My main concern is the novelty of the convergence analysis and the practicability of the proposed algorithm. Above all, I think this paper is marginally above the acceptance threshold. 

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

Thanks for the response. After reading the response and other reviews, I decided to keep my original evaluation.
review_title: null

Meta-review: This paper studies the performance of second-order algorithms on training multi-layers over-parameterized neural networks. The authors propose an algorithm based on the Gram-Gauss-Newton method, tensor-based sketching techniques, and preconditioning to train such a network, whose runtime is subquadratic in the width of the neural network. While some reviewers provide some weak support, none of them are in strong support, even after the author's response. I think one of the reasons is the lack of empirical experiments. Since the main claim of this paper is an efficient second-order algorithm, some experiments are necessary to back up this claim. Unfortunately, the authors did not try to add such an experiment during the rebuttal. I would suggest the authors add such experiments in the revision.
Decision: Reject