Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing

Summary

The paper presents a new preprocessing method for training shallow overparametrized sparse neural networks. It significantly improves the preprocessing time yet achieves same performance on query time. They also show that their algorithm is very close to optimal.

Strengths

1. Clearly written. Easy to understand. Well structured. 2. Story is rather complete. Lower bound is included showing that their result is close to optimal. 3. Connect ideas from applied algorithms (LSH etc.) to deep learning, insightful

Weaknesses

1. Not all assumptions appear in the statement of theorem 1.1. Expect a more detailed description of the sparsity assumption.

Questions

1. Does your work have applications in domains other than deep learning?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

1. The setting is limited. Overparametrization is currently largely a theoretical assumption for the convenience of proving things, rarely used in practice. Shallow network is also too limited for characterizing deep learning. Also neural networks are commonly run on parallel machines like GPU with some complications for sparsity processing, so it's hard to say whether data structures would be really helpful. But it's very common, due to the nature of things, to have these limitations in a theoretical work, so it's not a serious flaw. Maybe it's better to design the algorithm for a general problem and put deep learning as a possible use case. They have addressed the limitation of their work in terms of shallowness.

Summary

This paper analyzes a specific neural network setting: two-layer neural networks with $m$ neurons in the hidden layer and a ReLU activation. Given input data of dimension $d$ and $n$ training examples, it normally requires O(mnd) operations to compute the hidden activations. This paper follows prior work in showing that this can be asymptotically reduced to $O(m^{4/5}n^2d)$, which is better in the overparameterized (large m) regime. Improving on the previous work, the proposed algorithm requires polynomial instead of exponential time preprocessing. The core technical contribution is the Correlation Tree data structure, which is a collection of binary trees that store inner products between datapoints and neurons, and allows efficiently updating based on the sparsity of activated neurons.

Strengths

- The paper analyzes an interesting theoretical setting, and provides an original data structure and algorithm for this problem of efficient computation. The main result that training with sublinear cost per iteration is novel. - The paper is well-structured and written well. The problem setting is clear and the contributions are clearly decribed. Overall it is high quality.

Weaknesses

The main weakness of this submission is the empirical practicality of the method. The authors are transparent about these weaknesses, and it is not the intended focus of this direction of research, so I think this weakness does not significantly detract from the paper. It might be interesting to comment more on the technical challenges behind extending it to more complex settings (e.g. beyond 2 layer, or other activation functions).

Questions

N/A

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

The authors discuss most of the prominent limitations, but I think it is not completely clear how practical the algorithm is. It seems like it should be relatively straightforward to implement, which could strengthen the paper.

Summary

In the paper, the authors proposed fast optimization algorithm for over-parameterized two-layer networks. They proved that by using the sparsity firing feature from the neural network, the proposed method requires only O(nmd) time in preprocessing and still achieves o(nmd) time per iteration.

Strengths

1. A thorough theoretical analysis is provided and prove the statement of the paper.

Weaknesses

1. The proposed method require O(nm) space for storing, which is a lot when n and m is big. 2. No experimental results shown in the paper. A toy experiment can show empirical impact of this work.

Questions

1. The space required by the proposed method is high, 2. Is there any possibility to do a toy experiment?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

1. The space required by the proposed method is high. 2. There are few works training a two-layer network and showed competitive performance with deep NN. It is non-trivial to simplify the problem and prove the convergence of NN. However, why we need to do training based on an un-empirical structure? I hope at least a tory experiment should be provided to show that this training method is viable in deep NN.

Summary

This paper investigate the efficient training methods than the usual training protocol which requires the complexity $O(nmd)$ for 2-Layer ReLU networks. The authors improve the complexity in the previous study [SYZ21] by proposing the preprocessing method utilizing the tree data structure for both data and weights. Moreover, the authors successfully provide the upper bound/lower bound (for lb, the authors assume some conjecture) for their proposed preprocessing complexity. Unlike in previous study [SYZ21], this paper is the first presentation for the lower bound.

Strengths

1. The authors efficiently improve the preprocessing time from exponential complexity $O(2^d)$ (in previous research [SYZ21]) to polynomial $O(nmd)$ (in this paper) for both data and weight parameters using the tree data structures which is popular in general computer science. 2. For the tree data structure preprocessing, both the upper bound/lower bound are provided in a solid theory under the NTK regime and the theory basically depends on the previous study [SYZ21]. 3. Unlike in previous study [SYZ21], the authors also provide the lower bound for their proposed method (although assume some conjecture), so the tree-based preprocessing method is nearly optimal.

Weaknesses

Actually, I'm not an expert in this field, but I have carefully read this paper along with the previous study [SYZ21]. Here are my main concerns: 1. Based on my understanding, the authors have successfully reduced the complexity of preprocessing from $O(2^d)$ to $O(nmd)$ and from $O(n^d)$ to $O(nmd)$. However, it seems that the per-iteration time in this paper (for example, in Theorem 4.1, the time per-iteration is $O(m^{4/5}n^2d)$, but it is $O(m^{4/5} n d)$ in previous study [SYZ21]) has actually increased compared to the previous study [SYZ21]. In fact, if preprocessing time constitutes a significant portion of the neural network's training process, this research would have more significance. Therefore, it seems that an (empirical) analysis of the portion that preprocessing takes in neural network training, in computational terms, is necessary. 2. As this study presents more advanced preprocessing techniques compared to the previous research [SYZ21], there should be experimental analysis on how much the actual preprocessing time is reduced and its impact on per-iteration time (under quite theoretical settings or even for synthetic data/architecture). This analysis seems to be necessary, even for simple neural network models and simple datasets, to further validate the improvements made by the proposed preprocessing methods. 3. In the theoretical perspective, it is necessary to provide remarks on what is the challenging points of the theory in this paper compared to the previous study [SYZ21]. When I was examining the supplementary material, it is not clear which aspects have significantly changed compared to the theoretical analysis in the previous study [SYZ21].

Questions

Please see the weaknesses part.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors have adequately addressed the limitations and potential negative societal impact of their work.

Response to the authors

I appreciate the authors for their response. I agree that the contribution of this paper focus on theoretical results, but I still think that the empirical studies even on toy architecture should be needed to insist the efficiency compared to regular network training. In this sense, the authors could not resolve my concern on empirical study, hence I decided to keep my original score.