Does Preprocessing Help Training Over-parameterized Neural Networks?
Authors: Zhao Song
Shuo Yang
Ruizhe Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: NTK
training neural network
sparsity
geometric search

Abstract: Deep neural networks have achieved impressive performance in many areas. Designing a fast and provable method for training neural networks is a fundamental question in machine learning. 

The classical training method requires paying $\Omega(mnd)$ cost for both forward computation and backward computation, where $m$ is the width of the neural network, and we are given $n$ training points in $d$-dimensional space. In this paper, we propose two novel preprocessing ideas to bypass this $\Omega(mnd)$ barrier:

* First, by preprocessing the initial weights of the neural networks, we can train the neural network in $\widetilde{O}(m^{1-\Theta(1/d)} n d)$ cost per iteration.

* Second, by preprocessing the input data points, we can train neural network in $\widetilde{O} (m^{4/5} nd )$ cost per iteration.

From the technical perspective, our result is a sophisticated combination of tools in different fields, greedy-type convergence analysis in optimization, sparsity observation in practical work, high-dimensional geometric search in data structure, concentration and anti-concentration in probability. Our results also provide theoretical insights for a large number of previously established fast training methods.

In addition, our classical algorithm can be generalized to the Quantum computation model. Interestingly, we can get a similar sublinear cost per iteration but avoid preprocessing initial weights or input data points.

Does Preprocessing Help Training Over-parameterized Neural Networks?
Zhao Song Adobe Research zsongGadobe. com
Shuo Yang
Ruizhe Zhang The University of Texas at Austin ruizhe@utexas.edd
The University of Texas at Austin Langshuo_ut@utexxn edu
Abstract
Deep neural networks have achieved impressive performance in many areas. De- signing a fast and provable method for training neural networks is a fundamental question in machine learning.
The classical training method requires paying ((mmd) cost for both forward com- putation and backward computation, where m the width of the neural network, and we are given n training points in d-dimensional space. In this paper, we pro- pose two novel preprocessing ideas bypass this (2mmdd) barrier:
First, by preprocessing the initial weights of the neural networks, train the neural network in (mm1=8(1/d))) rd) cost per iteration.
Second, by preprocessing the input data points, we can train the neural net- work in (mm+/nnd) cost per iteration.
From the technical perspective, our result is sophisticated combination tools in different fields, greedy-type convergence analysis in optimization, sparsity ob- servation in practical work, high-dimensional geometric search in data structure, concentration and anti-concentration in probability. Our results also provide theo- retical insights for a large number previously established fast training methods. In addition, our classical algorithm can be generalized to the Quantum compu- tation model. Interestingly, we can get a similar sublinear cost per iteration but avoid preprocessing initial weights or input data points.
Introduction
Over the last decade, deep learning has achieved dominating performance over many areas, e.g., computer vision [LBBH99, KSH12, SIJ+ HZRS16). natural language processing [CWB+1] 11, DCLT118, game playing [SHM+ 16, SSS+ 17] and beyond. The computational resource requirement for deep neural network training grows very quickly. Designing a fast and provable training method for neural networks is, therefore, a fundamental and demanding challenge.
Almost all deep learning models are optimized by gradient descent (or its variants). The total training time can be split into two components, the first one is the number of iterations and the second one is the cost per spent per iteration. Nearly all the iterative algorithms for acceleration can be viewed as two separate lines of research correspondingly, the first line is aiming for an algorithm that has as small as possible number of iterations, the second line is focusing on designing as efficient as possible data structures to improve the cost spent per iteration of the algorithm [Vai89, CL.S19, LSZ.19, SLS20, J JSW721]. In this paper, our major focus is on the second line.
There are a number practical works trying use nearest neighbor search data structure to speed up the per-step computation of the deep neural network training (CMF+20, LXI 20, CLP*21, DMZS21]. However, none of the previous work is able give provable guarantee. In this paper,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

our goal is to develop training algorithms that provably reduce per step time complexity. Let us consider the ReLU activation neural network and two-layer neural network'. Let n denote the number of training data points. Let d denote the dimension of each data point. Let m denote the number of neurons.
each iteration of gradient descent (GD), we need to compute prediction for each point in the neural network. Each point Z; E R requires to compute m inner product in d dimension. Thus, (mmdd) a natural barrier for cost per iteration in training neural networks (in both forward computation and backward computation).
A natural question ask is
Is it possible improve the cost per iteration of training neural network algorithm? E.g., o(mnd) possible?
We list our contributions as follows:
We provide new theoretical framework for speeding up neural network training by: 1) adopting the shifted neural tangent kernel; 2) showing that only a small fraction (o(m) of neurons are activated for each input data in each training iteration; 3) identifying the sparsely activated neurons via geometric search; 4) proving that the algorithm can minimize the training loss to zero in linear convergence rate.
We provide two theoretical results 1) our first result (Theorem 6.1) builds a dynamic half-space report data structure for the weights of neural network, train neural networks in sublinear cost per iteration; 2) our second result (Theorem 6.2) builds a static half-space report data-structure for the input data points of the training data set for training neural network in sublinear time.
Acceleration via high-dimensional search data-structure. High-dimensional search data struc- tures support efficiently finding points in some geometric query regions (e.g.. half-spaces, simplices, etc). Currently, there are two main approaches: one is based on Locality Sensitive Hashing (LSH) [IM98], which aims to find the close-by points (i.e., small & distance [DIIM04, AR15, AlL 15, ARN17, Raz17, AIR18 18, BIW19, DIRW20] or large inner product [SL14, SL15b, SL15aJ) of a query g E Rd in given set of points S C IR. This kind of algorithms runs very fast in practice, but most of them only support approximate queries. Another approach is based on space partitioning data structures, for example, partition trees [Mat22a, Mat92b, AEM92, AC09, Chal2], k-d trees / range trees [CT17, TOG17, Chal9], Voronoi diagrams [ADBMS98, Cha00]. which can exactly search the query regions. Recent works have successfully applied high-dimensional geometric data structure to reduce the complexity of training deep learning models. SLIDE [CMF+20 20] accelerates the forward pass by retrieving neurons with maximum inner product via an LSH-based data structure; Reformer [KKL20] similarly adopts LSH to reduce the memory usage for processing long sequence; MON- GOOSE [CLP*21] 21] accelerates the forward pass by retrieving neurons with maximum inner products via a learnable LSH-based data structure [Cha02] and lazy update framework [CIS19]] Despite the great empirical success, there is no theoretical understanding of such acceleration.
The goal of our paper is to theoretically characterize the acceleration brought by the high- dimensional geometric data structure. Specifically, our algorithm and analysis are built upon the HSR data structures [AEM92] which can find all the points that have large inner products and sup- port efficient data update. Note that HSR comes with stronger recovery guarantee than LSH, in the sense that HSR, whereas LSH is guaranteed to find some of those points.
Convergence via over-parameterizzaion. Over the last few years, there has been tremendous work studying the convergence result of deep neural network explicilty or implicitly based on neural tangent kernel (NTK) [JGH18], e.g. [LLI8, 17P AZISS1a, AZLS19b,, DLLL+ 19, ADH 19a, ADH 19b, SY19, CGH 19, ZMG19, CG19, ZG19, OS20, LSS JT20, ZPD 20, HLSY21, BPSW21J. It has been shown that (S)GD can train a sufficiently wide NN with random initialization will converge to small training error in polynomial steps.
An alternative name of the two-layer neural network is "one-hidden layer neural network".

---

2 Challenges and Techniques
Empirical works combine high-dimensional search data structures (e.g., LSH) with neural network training, however, they do not work theoretically due to the following reasons:
Without shifting, the number of activated (and therefore updated) neurons is (m). There is no hope to theoretically prove o(m) complexity (See Challenge 1).
Approximate high- nigh-dimensional search data structures might miss some important neurons, which can potentially prevent the training from converging (see Challenge 2).
Our solutions are:
We propose shifted ReLU activation that is guaranteed have o(m) number of activated neurons. Along with the shifted ReLU, we also propose a shifted NTK to rigorously provide convergence guarantee (see Solution 1).
We adopt an exact high-dimensional search data structure that better couples with the shifted NTK. It takes o(m) time to identify the activated neurons and fits well with the convergence analysis as it avoids missing important neurons (see Solution 2).
Challenge 1: How to sparsify an over--vvemreeee parameterized neural network? To speed up the training process, we need the neural network be "sparse", that is, for each training data x E R the number of activated neurons is small. Then, in the forward computation, we can just evaluate a small subset of neurons. However, in the previous NTK analysis (e.g., [DZPS19]), the activation function o (2) max (w., 0}, and the weights vectors w,- are initially sampled from standard d- dimensional Gaussian distribution. Then, by the symmetry of Gaussian distribution, we know that for every input data x, there will be about half of the neurons being activated, which means that we can only obtain a constant- factton speedup.
The problem actually comes from the activation function. In practice, people use shifted ReLU function (s(x)) max x), by] to train neural networks. The main observation of our work is that threshold implies sparsity. We consider the setting where all neurons have unified threshold parameter b. Then, by the concentration of Gaussian distribution, there will be O(exp(-b²) m) activated neurons after the initialization.
Solution 1
The next step to show that the number of activated neurons will not blow up too much in the following training iterations. In [DZPS19, SY191, they showed that the weights vectors are changing slowly during the training process. In our work, we open the black box of their proof and show a similar phenomenon for the shifted ReLU function. More specifically, prove that for each training data, a large fraction of neurons will not change their status (from non-activated to activated and vice versa) in the next iteration with high probability. To achieve this, they showed that this is equivalent to the event that a standard Gaussian random variable in a small centered interval [-R, RJ. and applied the anti-concentration inequality to upper-bound the probability. our setting, we need to upper-bound the probability of ~ No 1) a shifted interval R, b + R]. On the one hand, we still apply the coteeconcettration inequality by showing that the probability is at most Pr[z E [- R. R]]- On the other hand, this probability is also opper-bounder by Pr[z b - R). and for small R, we can apply the concentration inequality for a more accurate estimation. In the end, by some finer analysis of the probability, we can show that with high probability, the number of activated neurons in each iteration is also ((exp(- -b²). m) for each training data. If we take i = (Vlog m). we only need to deal with truly sublinear in m of activated neurons in the forward evaluation.
key component is to
How to find the small subset of activated neurons? A linear scan of the neurons will lead to time complexity linear in m, which we hope to avoid. Randomly sampling or ing LSH for searching can potentially miss important neurons which are important for a rigorous convergence analysis.
Challenge 2:
Solution Given the shifted ReLU function (p((,, .)) = max{ (w,, x) b, 0}. the active neu- rons are those with weights w, lying in the half space of (w,, - b > 0. Finding such neurons is equivalent to computational geometry problem: given points in Rdd in each query and half space H. the goal is to output the points contained in H. Here we use the Half-Space Reporting (HSR) data structure proposed by [AEM92]: after proper initialization, the HSR data structure can
3

---

return all points lying in the queried half space with complexity as low (nlog(n) + k), where the number of such points. Note that the HSR data structure well couples with the shifted ReLU, as the number of activated neurons k is truly sublinear in m as the setting of b = O Vlog m).
3 Preliminaries
Notations For an integer n,, we use [n] denote the set {1, (1, For a vector and p {0, 2, oo}. we use ||æ||p to denote the entry-wise Ep norm of vector. We use La to denote d- dimensional identity matrix. We use M(,, (²) to denote Gaussian distribution with mean mu and variance o², We use O to hide the polylog factors.
n).
This section is organized follows. Section 3.1 introduces the neural network and present problem formulation. Section 3.2 presents the half-space report data-structure, Section 3.3 proposes our new sparsity-based Characterizations.
3.1 Problem Formulation
In this section, we introduce the neural network model we study in this work. Let us consider a two-layer ReLU activated neural network that has width and &g loss function. 2 Definition 3.1 (Prediction function and loss function), Given R. x E IR, E Rdxm and E R"
f(W,,,a) 1
a, aorl(wr;;)))
mm
L(W) = E (J(W, xx, 2
We say function is 2N, b) for simplicity.
Here W are weights that connect input nodes with hidden nodes, 01 am are the weights
that connect hidden nodes with output node. The ReLU function dz(x) == max(x b, 0}, where b is the threshold parameter. Following the literature, we mainly focus on optimizing W E Rdxm. For weights R we will never change a during the training after we randomly choose them the initialization."
Definition 3.2 (Weights at initialization). We use the following initialization,
For each r, we sample w.) ~ ~N Ia)
For each r, we sample or from {-1, +1] uniformly at random
Next, we can calculate the gradient
Fact 3.3 (Gradient the prediction function and loss function), For each r E [m]
@f,, 20
(1)
Ow,
V
and
OL(W) 1
Σ
(2)
Ow,
Vm
To update the weights from iteration iteration &s + 1. we follow the standard update rule of the GD algorithm,
GD: W(k + 1) W( (W()), where AW(k) (L))
(3)
OW(k)
"This very standard formulation in the literature, e.g., see [DZPS19, SY19, BPSW21] 3 We remark, in some previous work, they do choose shift, but their shift is random shift, In our application, it is important that the same b fixed for all neurons and never trained.

---

The ODE of the gradient flow is defined as
dw, (t) #L(W)
(4)
di
Owr
Definition 3.4 (Error of prediction), For each t E (0,1,... T. we define err(t) E IR" to be the error of prediction err(t) y u(t), where u(t) == f(W((), x) E IR"
3.2 Data Structure for Half-Space Reporting
The half-space range reporting problem is an important problem in computational geometry, which formally defined as following:
Definition 3.5 (Half-space range reporting). Given a set S of points in Rd. There are two opera-
lions:
QUERY(H): given half-space H C Rd,, output all of the points S that contain i.e., S H.
. UPDATE: add or delete a point in S.
- -INSERT(Q): insert into S
- DEELETE( delete q from
Let Tinit denote the pre-processing time to build the data structure, Tquery denote the time per query and Tupdate time per update.
We use the data-structur proposed in [AEM92] to solve the half-space range reporting problem, which admits the interface summarized Algorithm Intuitively, the data-structure recursively partitions the set S and organizes the points in tree data-structure. Then for given query (a, b), all points of with sgn( (a, - b) 2 0 are reported quickly. Note that the query (a,b) b) here defines the half-space H in Definition 3.5.
Algorithm Half Space Report Data Structure
1: data structure HALFSPAACRREPOT
2:
procedures:
3:
INIT(S, n, d)
Initialize the data structure with set of n points Rd a, Rdd. Output the set {xr E S sgn((a, b) 2 0}
4: QUERY(a,
5: ADD(x)
b Add point E R to S
6:
DELETE(2)
Delete point a Rdd from
7: end data structure
Adapted from [AEM92], the algorithm comes with the following complexity:
Corollary 3.6 ([AEM92]). Given a set of points Rd, the salf-space reporting problem can be solved with the following performances:
Part 1. Tquery (n, d, k) Og(ni-1/Ld/2) k), amortized Tupdate Oa(log((n)).
Part 2. Tquery (n, d, k-) = Oa(log(n) + k), amortized Tupdate = Oa(nld/2)-1
We remark that Part will be used in Theorem 6.1 and Part will used Theorem 6.2.
3.3 Sparsity-based Characterizations
In this section, we consider the ReLU function with a nonzero threshold: (T(2) max maax(0,2x b), which is commonly seen in practise, and also has been considered theoretical work [ZPD-2 20].
We first define the set neurons that are firing at time t. Definition 3.7 (fire set). For each E [n], for each t E {0, 1o.1,...TTT) ler St,rro(t C [m] denote the set of neurons that are "fire" time i.e.
(t) = fr E [m] (t), b). We define k. (t)), for all t in {0, 1, ... ,T}.
5

---

We propose a new "sparsity" lemma in this work. It shows that d gives the desired sparsity.
Lemma 3.8 (Sparsity after initialization). Let > 0 be tunable parameter. If we use the σh as the activation function, then after the initialization, with probability least 1 - n exp(-S((m exp(-b² /2))), it holds that for each input data the number of activated neurons ks,0 is at most O exp(- 1op(-12/10 /2)), where m. the total number of neurons.
Proof. By the concentration of Gaussian distribution, the initial fire probability of single neuron is Pr[cs((us (w, (0), > 0]
[= > bj s exp(-b²/2)) 20,(0,1)
Pr
Hence, for the indicator variable (0)) we have
nnr) S exp(-bb/22)
By standard concentration inequality (Lemma B.1),
12/2
Pr (ire > ko + + S exp
14 >
(5)
ku + t/3
where ko (xp(-b2/22 12) If we choose ko, then we have:
Pr [[ (0)) 2kol S exp (13ku/8)
Then, by union bound over all i E [n]] we have that with high probability
exp( ( exp(-b2/2))),
the number of initial fire neurons for the sample x; is bounded by k,, S 2m cxp((-b/2).
The following remark gives an example of setting the threshold b, and will be useful for showing the sublinear complexity the next section.
Remark 3.9. If we choose v0.4 then kn = ma/5, For m/5 Eq. (5) implies that
S exx lesp-mming (-min(mR, 0m14/1)))
Pr (re 2m
4 Training Neural Network with Half-Space Reporting Data Structure
In this section, we present two sublinear time algorithms for training over parameterized neural net- works. The first algorithm (Section 4.1) relies on building a high-dimensional search data-structure for the weights of neural network. The second algorithm (Section 4.2) is based building data structure for the input data points the training set. Both of the algorithms use the HSR to quickly identify the fired neurons avoid unnecessary calculation. The time complexity and the sketch of the proof are provided after each of the algorithms.
4.1 Weights Preprocessing
We first introduce the algorithm that preprocesses the weights w, for r E [m], which com- monly used in practice [CLP*21, CMF+20. KKI.20J. Recall 2NN(m, b) is f(W, w, a) = vm Em a, (4w0)((,,,))))) a)). By constructing HSR data-structure for w, 's, we can quickly find the set of active neurons Si.ie for each of the training sample v4. See pseudo-code in Algorithm 2.
In the remaining part of this section, we focus on the time complexity analysis of Algorithm 2. The convergence proof will be given in Section
Lemma 4.1 (Running time part of Theorem 6.1). Given n data points in d-dimensional space. Running gradient descent algorithm (Algorithm 2) on 2NN b 00.4 log m.) (Definition 3. the expected cost per-iteratio iteration of the gradient descent algorithm
1- ( nd).

---

Algorithm 2 Training Neural Network via building data structure of weights of the neural network
WEIGHTS(( (z,, Mc) hefn) (n(,.)))).mdd))) > Theorem 6.1 2: Initialize wy, for E [m] and according to Definition 3.2 and Remark 3.9
1: procedure
3: HALFSPACERRPPORT (NSR.NIT((w,H))) (O) m,
Algorithm
4: for fort=11 T do
5:
Si HSR. QUERY b) for E [n]]
6:
Forward pass for only on neurons in Si,ire for i [n]
7:
Calculate gradient for z; only on neurons in SyAre for E [n]
Gradient update for the neurons in nir 9: H.R.DELLTEEW,,Ch for r E Usefm] Sire
8:
10:
HSR.ADD(w,,CC 1)) for r E UsEjn] St,fr end for
12: return Trained weights wo (T" + 1) for r E [m]]
13:
end procedure
Algorithm 3 Training Neural Network via building data-structure of the input data points
procedure TraininGW TTRRoCEESDRRRCCAAAAAAAC (zt, (e))
Theorem 6.2
2: Initialize wy, o, for E [m]] and according to Definition 3.2 and Remark 3.9 d)
3: HALfSPACEREPORT HSS.. INS..NII((Z))eeee))
> Algorithm for r E [m]] Sy,fre are samples which neuron r fires for
4: Sr.Are -- HSR. HSS.HUER.SERE (UE
5: Si,tr +- (r i E Sp,tmo)
b Sim is the set of neurons, which fire for 2;
6:
for t T- do
7:
Forward pass for only on neurons in Stare for i [n]]
8:
Calculate gradient for z; only on neurons in Sy,r for E [n]]
9:
Gradient update for the neurons in (iftreS
for r E UsE Sire do
11:
St.fre-DEL for E Sp,fre
Sy,ire HSR. QUERY 1),b)
13:
ADD((r) for i E Sp,fir end for end for
15:
return Trained weights we (T + for r E [m]
17:
end procedure
Proof. The per-step time complexity is
TQUERY (m, ka,)) + (TDELETE + TINSeRt) Uie(n) (t.) +
Σ higt iE(n)
The first term En TQUERY (mn, d, ks,)) corresponds to the running time of querying the active neuron set (t. for all training samples i [n)]. With the first result in Corollary 3.6, the complexity is bounded by ((m2-8(1/d)
The second term (TDILETE TINSERT) Use(m) (t)) corresponds updating w, in the high- dimensional search data-structure (Lines and 10). Again with the first result Corollary 3.6, we have TDELETE + TINSERT = (log² m). Combining with the fact that Usein] (t,)ro(t]] < [sejm] Syare (0)l < (mmm4/5), the second term is bounded by (nnm445 log2m). m))
The third term is the time complexity of gradient calculation restricted the set (t.. With the bound Eie(s) ki (Lemma C.))), we have d Eie(n) ki, < 4/5m4/5d))
Putting them together completes the proof.

---

4.2 Data Preprocessing
While the weights preprcessing algorithm is inspired by the common practise, the dual relationship between the input 2; and model weights w, inspires us to preprocess the dataset before training (i.e., building HSR data-structure for z4). This largely improves the per-iteration complexity and avoids the frequent updates of the data structure since the training data is fixed. More importantly, once the training dataset is preprocessed, it can reused for different models or tasks, thus one does not need to perform the expensive preprocessing for each training.
The corresponding pseudocode is presented in Algorithm 3. With 24 preprocessed, can query HSR with weights wy and the result Sy.rr is the set of training samples x, for which wy fires for. Given Sye for r E [m]) we can easily reconstruct the set Sirere, which is the set of neurons fired for sample zę. The forward and backward pass can then proceed similar to Algorithm
At the end of each iteration, will update frre based the new w, estimation and update Strre accordingly. For Algorithm 3, the HSR data-structure is static for the entire training process. This the main difference from Algorithm 2, where the HSR needs to be updated every time step to account for the changing weights Wr.
We defer the convergence analysis to Section 5 and focus on the time complexity analysis of Algo- rithm 2 in the rest this section. We consider being a constant for the rest of this subsection.
Lemma 4.2 (Running time part of Theorem 6.2). Given data points in d-dimensional space. Running gradient descent algorithm (Algorithm 2) on 2NN(m, expected per-iteration running time of initializing Sy,re St,ir for r E [m], E [n] is O(m log n + mA/6n), n). The cost per iteration of the training algorithm is O log n).
v0.4 log (Definition 3. I), the
Proof. We analyze the initialization and training parts separately.
Initialization
In Lines 4 and 5, the sets Si,fre Sire for E [m], E [n]] are initialized. For each E [m]] need query the data structure the of data points wts such that (0) 0. Hence, the running time of this step is
m
m
querry (n, d, kr,0) (m log n +
kn,0)
0 log +
k3,0)
= 0m logn + m 4/5
where the second step follows from > Re,
Σm ki.0-
Training Consider training the neural network for steps. For each step, first notice that the forward and backward computation parts (Line 7 9) are the same previous algorithm. The time complexity is Om14/5 log n))
We next show that maintaining Sq.fre:"' E [m] and Siaro: i E [n] (Line 10 14) takes O log n) time. For each fired neuron [m]. we first remove the indices of data in the sets Si,free which takes time
m
0(1)
Σ 0(1) Σ hy, = O(m SE.
Then, we find the new set of x's such that ((w(utt + 1).x))
> 0 by querying the half-space
reporting data structure. The total running time for all fired neurons is
Σ Tquery d, dd, d, kp.41) S m 4/5 log +
Σ
k = O(m 4/5 n
rEUicIn/SE.ne
SE
Then, we update the index sets Sieie in time Omm4/ Therefore, each training step takes (5 log n) time, which completes the proof.
8

---

5 Convergence of Our Algorithm
We state the result of our training neural network algorithms (Lemma 5.2) can converge certain steps. An important component in our proof is to find out a lower bound on minimum eigenvalue of the continuous Hessian matrix Xmin (Hot)). It turns out to be an anti-concentration problem of the Gaussian random matrix. In [OS20], they gave lower bound Amin for ReLU function with b = O, assuming the input data are separable. One of our major technical contribution generalizing it to arbitrary b 2 0.
Proposition 5.1 (Informal version of Theorem F.1). Given n (normalized) input data points (21,,22,"" In. S IRd such that Vi [n], ||aa|l Let parameter == mineys y { [1x ar 22ll2 | + 2z 1 denote the data separability. For any shift parameter 2 0. we define shifted NTK Hess Tgnx as follows
E H ((, [o), (m. 1(naa)200 [n], [m].
Then
Amiu (H 2 0.01e 12/8///2
With proposition 5.1, we are ready to show the convergence rate of training an over-parameterized neural network with shifted ReLU function.
Lemma 5.2 (Convergence part Theorem 6.1 and Theorem 6.2). Suppose input data-points are 8 6-separable, i.e., 8 == min [|,; 2yl12, l2, || + 22 Let m poly(n, 1/5, log(n/p) and O(N/²²). Let b = O( (lvg m). Then
Pr [err(())112 s (1 (1--n/p n\/2)* |[er((0)1,,, vk 10,1, ,T}] 2 11-p p.
Note that the randomness over initialization. Eventually, we choose T x 2 log(n/e) where e is the final accuracy.
This result shows that despite the shifted ReLU and sparsely activated neurons, we can still retain the linear convergence. Combined with the results on per-step complexity in the previous section, it gives our main theoretical results of training deep learning models with sublinear time complexity (Theorem 6.1 and Theorem 6.2).
Main Classical Results
We present two theorems (under classical computation model) of work, showing the sublinear running time and linear convergence rate of our two algorithms. We leave the quantum application into Appendix G. The first algorithm is relying building high-dimensional geometric search data-structure for the weights of a neural network.
Theorem 6. (Main result informal of Theorem E.2). Given n data points in d-dimensional space. We preprocess the initialization weights of the neural network. Running gradient descent algorithm (Algorithm 2) on a two-layer m-width, over-paren parameterrze ReLU neural network will minimize the training loss zero, and the expected running time of gradient descent algorithm (per iteration) is
The second algorithm is based on building data structure for the input data points of the training Our second algorithm can further reduce the cost per iteration from m--1/d truly sublinear in m, c.g. m/5
Theorem 6.2 (Main result II, informal of Theorem E.2). Given n data points in d-dimensional
space. We preprocess all the data points. Running gradient descent algorithm (Algorithm 3) on two-layer, m-width, over ner-parameterized ReLU neural network will minimize the training loss to zero, and the expected running time of gradient descent algorithm (per iterationn is
0mm² (5m)). nd).

---

7 Discussion and Limitations
In this paper, propose sublinear algorithms train neural networks. By preprocessing the weights of the neuron networks or preprocessing the training data, we rigorously prove that it is possible train neuron network with sublinear complexity, which overcomes the (2(mnd) barrier in classical training methods. Our results also offer theoretical insights for many previously established fast training methods.
Our algorithm is intuitively related to the lottery tickets hypothesis [FCI8]. However, our theoretical results can not be applied to explain lottery tickets immediately for two reasons: 1) the lottery ticket hypothesis focuses on pruning weights; while our results identify the important neurons. 2) the lot- tery ticket hypothesis identifies the weights that need to be pruned after training (by examining their magnitude), while our algorithms accelerate the training via preprocessing. It would be interesting see how our theory can be extended to the lottery ticket hypothesis.
One limitation of our work is that the current analysis framework does not provide a convergence guarantee for combining LSH with gradient descent, which is commonly seen in many empirical works. Our proof breaks as LSH might miss important neurons which potentially ruins the conver- gence analysis. Instead, refer to the HSR data structure, which provides stronger theoretical guarantee of successfully finding all fired neurons.
Acknowledgments and Disclosure of Funding
SY's research is supported by NSF grants 1564000 and 1934932. RZ's research is supported by NSF Grant CCF-1648771 and Scott Aaronson's Vannevar Bush Faculty Fellowship from the US Department of Defense.
References
[AC09] Peyman Afshani and Timothy M Chan. Optimal halfspace range reporting in three di- mensions. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 180-186. SIAM, 2009.
[ADBMS98] Pankaj K Agarwal, Mark De Berg, Jiri Matousek, and Otfried Schwarzkopf. Con- structing levels in arrangements and higher order voronoi diagrams. SIAM journal on computing. 27(3):654 667, 1998.
[ADH+ 19a] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332, 2019.
[ADH+ 19b] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In NeurIPS, 2019.
[AEM92] Pankaj K Agarwal, David Eppstein, and Jiní Matousek. Dynamic half-space report- ing, geometric optimization, and minimum spanning trees. In Annual Symposium on Foundations of Computer Science (FOCS), volume 33, pages 80-80, 1992.
[AHKZ20] Jonathan Allcock, Chang-Yo Hsieh, Iordanis Kerenidis, and Shengyu Zhang. Quan- tum algorithms for feedforward neural networks. ACM Transactions Quantum Computing, 1(1):1-24, 2020.
[5]L+15] Alexandr Andoni, Piotr Indyk, TMM Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. In Advances in Neural Infor- mation Processing Systems (NIPS), pages 1225-1233 Curran Associates, 2015.
[AIR18] Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. arXiv preprint 17Xiv:1806.09823, 7, 2018.
[AR15] Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approx- imate near neighbors. In Proceedings of the serty-seventh annual ACM symposium on Theory of computing (STOC), pages 793-801, 2015.
10

---

[ARN17] Alexandr Andoni, Ilya Razenshteyn, and Negev Shekel Nosatzki. Lsh forest: Practical algorithms made theoretical. Proceedings of the Eightt Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 67-78. SIAM, 2017.
[AZIS199a] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learn- ing via over-paramettrrizaton. In ICMI,, 2019.
[AZLS19b] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In NewrIPS, 2019.
[Ber24] Sergei Bernstein. a modification of chebyshev's inequality and of the error formula of laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):38 49, 1924.
[BHМТ02] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002.
[BIW19] Arturs Backurs, Piotr Indyk, and Tal Wagner. Space and time efficient kernel density estimation in high dimensions. In NeurlPS, pages 15773-15782, 2019.
[BPSW21] Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (over- parametrized) neural networks in near-linear time. In /2th Innovations in Theoretical Computer Science Conference (ITCS), 2021.
[CG19] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In NeurIPS, pages 10835-10845, 2019.
[CGH* 19] Tianle Cai, Ruiqi Gao, Jikai Hou, Siyu Chen, Dong Wang, Di He, Zhihua Zhang, and Liwei Wang. Gram-gauss-newwe method: Learning overparameterized neural networks for regression problems. arXiv preprint arXiv: 1675, 2019.
[Cha00] Timothy M Chan. Random sampling, halfspace range reporting, and construction of (S k))levels three dimensions. SIAM Journal on Computing, 30(2):561-55) -575, 2000.
[Cha02] Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Pro- ceedings of the thiry-fourth annual ACM symposium on Theory of computing (STOC), pages 380-388, 2002.
[Cha12] Timothy M Chan. Optimal partition trees. Discrete & Computational Geometry, 47(4):661-690, 2012.
[Cha19] Timothy M Chan. Orthogonal range searching in moderate dimensions: kd trees and range trees strike back. Discrete & Computational Geometry, 61())8899 92299999922229999 2019.
[CLP*21] Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. Mongoose: A learnable Ish framework for efficient neural network training. In ICLR oral, 2021.
[CLS19] Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In STOC, 2019.
[CMF+20] Beidi Chen, Tharun Medini, James Farwell, Sameh Gobriel, Charlie Tai, and Anshu- mali Shrivastava. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. In In Proceedings of the 3rd Conference on Machine Learning and Systems (MLSys), 2020.
[CT17] Timothy M Chan and Konstantinos Tsakalidis. Dynamic orthogonal range search- ing the ram, revisited. Leibniz International Proceedings in Informatics, LIPles, 77:281 2213, 2017.
[CWB+11] Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. Natural language processing (almost) from scratch. Journal of machine learning research, 22ARTICLEE;299--553 101
11

---

[DCLT18] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- training of deep bidirectional transformers for language understanding, arXiv preprint WrXiv:1810.04805, 2018.
[DIIM04] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni. Locality- sensitive hashing scheme based on p-stable distributions. In Proceedings of the twen- lieth annual symposium on Computational geometry (SoCG), pages 253-262, 2004.
[DIW200] Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In ICLR. arXiv preprint arXiv:1901.08555 2020.
[DLL*19 19] Simon Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In ICML, 2019.
[DMZS21] Shabnam Daghaghi, Nicholas Meisburger, Mengnan Zhao, and Anshumali Shrivas- tava. Accelerating slide deep learning on modern cpus: Vectorization, quantizations, memory optimizations, and more. Proceedings of Machine Learning and Systems, 3, 2021.
[DZPS19] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In ICLR, 2019.
[FC18] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In ICLR, 2018.
[Gro96] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceed- ings of the twenty-eighth annual ACM symposium on Theory of computing (STOC), pages 212-219. 1996.
[HLSY21] Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. Fl-ntk: A neural tangent kemee-baaeed framework for federated learning convergence analysis. In ICML, 2021.
[HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), pages 770-778, 2016.
[IM98] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC), pages 604-613, 1998.
[JGH88] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Con- vergence and generalization in neural networks. Advances neural information processing systems, pages 8571-8580, 2018.
[JK++00] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In FOCS, 2020.
[JLWW00] Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games and its appli- cations. In STOC, 2020.
[JSW221] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. Faster dynamic matrix inverse for faster lps. In Proceedings of the 53rd Annual ACM SIGACT Sym- posium on Theory of Computing (STOC). arXiv preprint arXiv:2004.07470, 2021.
[JT20] Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. In ICLR, 2020.
KKI.0 Nikita Kitaev, tukasz Kaiser, and Anselm Levskaya. Reformer: The efficient trans- former. arXiv preprint arXiv:2001.04451, 2020..
KLPP19] Iordanis Kerenidis, Jonas Landman, and Anupam Prakash. Quantum algorithms for deep convolutional neural networks. arXiv preprint arXiv:1911.01117, 2019.
12

---

Discrete & Computational Geometry, [KSH12] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances neural information processing systems, 25: 2012.
[LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Pruceedings of the IEEE, 86(1 1):2278 2324, 1998.
[LL18] Yuanzhi Li and Yingyu Liang. Learning overparameterrzzed neural networks via stochastic gradient descent on structured data. In NewrlPS, 2018.
[LSO1] W.V. Li and Q.-M. Shao. Gaussian processes: Inequalities, small ball probabilities and applications. In Stochastic Processes: Theory and Methods, volume 19 of Handbook of Statistics, pages 533-597. Elsevier, 2001.
20] Jason D) Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, and Zheng Yu. Generalized leverage score sampling for neural networks. In NeurIPS, 2020.
[LSZ19] Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. In Conference on Learning Theory (COLT), pages 2140-2157. PMLR, 2019.
[LX]+20] Zichang Liu, Zhaozhuo Xu, Alan Ji, Jonathan Li, Beidi Chen, and Anshumali Shrivastava. Climbing the wol: Training for cheaper inference. arXiv preprint urXiv:2007.01230, 2020.
[Ma[92a] Jifí Matoušek. Efficient partition trees. 8(3):11--34, 1992.
[Mat92b] Jiri Matousek. Reporting points in halfspaces. Computational Geometry, 2(3):169- 186, 1992.
[OS20] Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterizzatoo:: Global convergence guarantees for training shallow neural networks. IEEF Journal on Selected Areas in Information Theory, 1(1):84-105, 2020.
[Raz17] Ilya Razenshteyn. High-dimensional similarity search and sketching: algoritiums and hardness. PhD thesis, Massachusetts Institute of Technology. 2017.
[Sch11] J. Schur. Bemerkungen zur theorie der beschränkten bilinearformen mit unendlich vielen veränderlichen. Journal für die reine und angewandte Mathematik, 140:1-28, 1911.
[SHM+ + 16] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche. Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvant Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[SL14] Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maxi- mum inner product search (mips). Advances in Neural Information Processing Sys- tems (NIPS), pages 2321-2329, 2014.
[SL15a] Anshumali Shrivastava and Ping Li. Asymmetric minwise hashing for indexing bi- nary inner products and set containment. In Proceedings of the 24th international conference on world wide web (WWW), pages 981-991, 2015.
[SL15b] Anshumali Shrivastava and Ping Li. Improved asymmetric locality sensitive hashing (alsh) for maximum inner product search (mips). In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence (UAI), pages 312-821, 2015.
[SLJ+15] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vi- sion and pattern recognition, pages 2015.
13

---

[SSS 17] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker. Matthew Lai, Adrian Bolton, et al. Mas- tering the game of go without human knowledge. nature, 550(7676):354359, 2017.
[SY19] Zhao Song and Xin Yang. Quadratic suffices for over-parametrization via matrix chernoff bound. arXiv preprint arXiv: 03593, 2019.
[TOG17] Csaba D Toth, Joseph O' O'Rourke, and Jacob Goodman. Handbook of discrete and computational geometry. CRC press, 2017.
[Tro15] Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends Machine Learning. 1(1-2):1-230, 2015.
[Vai89] Pravin Vaidya. Speeding-up linear programming using fast matrix multiplication. In FOCS, 1989.
[ZG19] Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. In NeurIPS, pages 2053-2062, 2019.
[ZMG1]] Guodong Zhang, James Martens, and Roger B Grosse. Fast convergence of natu- ral gradient descent for over- per--aaameterized neural networks. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
IZPD 220] Yi Zhang, Orestis Plevrakis, Simon Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over-parameteen adversarial training: An analysis overcoming the curse of dimen- sionality. In NeurIPS. arXiv preprint arXiv:2002.06668, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
A: [Yes].
(b) Did you deseribe the limitations of your work?
A: [Yes] See Section 7.
(c) Did you discuss any potential negative societal impacts of your work?
A: [N/A]. Our theoretical work does not have explicitly negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
A: [Yes], we conformed.
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results?
A: [Yes], we explictly stated the assumptions.
(b) Did you include complete proofs of all thcoretical results?
A: [Yes], we provided the complete proofs in supplementary materials.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)?
A: [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?
A: [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)?
A: [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)?
A: [N/A]
14

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasng new assets...
(a) your work uses existing assets, did you cite the creators?
A: [N/A]
(b) Did you mention the license of the assets?
A: [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL?
A: [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data
you're re using/curating?
A: [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content?
A: [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable?
A:
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable?
A: [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation?
A: [N/A]
15


Reviews:
[{"review_id": "k3xP7ElHLOk", "reviewer": "Reviewer_ZsjG", "summary": "The authors propose a variant of the over-parameterized two-layer RELU network where the original RELU activation is shifted so that fewer neurons are activated. The advantage of such modification is that since fewer neurons are activated one may carefully design techniques to only update and carry out computation on the weights related to the activated neurons. In particular there exist algorithms/data structures such as HSR to efficiently search for the activated neurons. One could either build HSR data structures on the data and query the sample or vice versa, producing two variants of the algorithms. Both variants are able to improve the computational dependency on m, the number of hidden neurons, to sub-linear. Convergence guarantees are also provided for the proposed algorithm. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The setting of the paper is both interesting and limited. \n\nIt is interesting since usually it is considered impossible to reduce the dependency on the number of hidden neurons to sublinear, and this seems the first work on this effort. Even though the technique itself seems like a combination of several tools, I feel those techniques are combined in an organic and natural fashion so that rigorous guarantees and claims can be made. \n\nOn the other hand, the limitation of this work is also obvious. I understand this two-layer RELU setting with a fixed second layer is very popular in the NTK literature. However, the over-parameterized two-layer RELU networks are in general not working well in real applications. One particular issue is, even though the over-parameterised two layer RELU networks are able to fit the data (while the weights are only slightly changed during the training), they tend not to generalize well. This is perhaps one major reason that in applications people still tend to use networks with limited width but more layers. There seems to be more stuff that we do not understand why neural networks generalize so well beyond the two-layer over-parameterized setting. \n\nOne question regarding Lemma 4.2: Is there a dependency on d hidden in the big O notation there?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " the authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "VyvamRohth", "reviewer": "Reviewer_NBXy", "summary": "This paper proposed two preprocessing algorithms that can reduce the computation cost per iteration on two layer ReLU neural networks. Suppose the network has width $m$, input dimension $d$, and number of training points $n$. The first proposed algorithm preprocessed the initial weights of the neural network and can reduce the cost per iteration from $\\Omega(mnd)$ to $\\widetilde{O}(m^{1-\\Theta(1/d)}nd)$. The second algorithm preprocessed the input data points and reduce the cost per iteration to  $\\widetilde{O}(m^{4/5}nd)$. The analysis is done in the NTK regime and the authors also proved linear convergence result under the preprocessing. \n\nThe algorithm fixed the bias term to a relatively large value so that given any input the number of active neurons is only $o(m).$ The algorithm only needs to do forward and backward computation on these active neurons, which saves the computation cost. In order to efficiently identity the active neurons at each iteration, the authors adopted a dynamic half-space report data structure for the weights in one algorithm and used a static half-space report data structure for the inputs in the other. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Reducing the computation cost per iteration is an important topic and there are many heuristic algorithms, but there are very few theoretical guarantees for these algorithms. This paper made a good step in this direction by designing two preprocessing algorithms that can provably reduce the computation cost and also guarantees global convergence, for a two layer ReLU nets in the lazy training regime.\n\nMy main concerns for this paper is as follows:\n1. Since the analysis is done in the lazy training regime and we know the NTK techniques also applies to multi-layer nets. I wonder if the results in this paper can extend to multi-layer setting. If not, it's also good to discuss what's the challenges.\n2. The theory in this paper is restricted in the lazy training regime, but we know that in practice the neural network training usually does not happen in lazy training regime and the trained network outperforms a neural tangent kernel. So I am not sure if these preprocessing algorithms work in practice or not. It might be good to verify the performance of these algorithms in practice and compare with the previous preprocessing algorithms. \n3. If I understand correctly, Lemma 4.1 and Lemma 4.2 holds as long as the active neurons are sparse, not necessarily in the NTK regime. The sparsity on activations is probably still true beyond the lazy training regime. So it's indeed possible to get a provable reduction on per-iteration cost beyond lazy training regime assuming the activations are sparse.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "K0ipJfkNzf", "reviewer": "Reviewer_gr3M", "summary": "This paper studied the problem of training 2-layer over-parameterized neural networks. The commonly used backpropagation algorithm has a running time of O(mnd) per iteration, which is also the running time for neural network evaluation. In this paper, the authors study if the traning could be done in o(mnd). They give affirmative answers and show two main contributions:\n1. They proposed a framework for speeding up the training algorithm, where they observed that after the randomized initialization, the activated neurons are sparse. They also gave a convergence analysis for their framework.\n2. They provide an instance of the framework by using half-space report data structures to select and update the weights of neurons during the training process. Their first algorithm uses a dynamic data structure to maintain the weights and achieves sublinear cost per iteration. By the dual relation between input data and neuron weights, their second algorithm uses a static data structure to store the training data and achieves a truly sublinear cost.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The framework and methods mentioned in this paper is new. The idea of utilizing half-space report data structure to speed up the training of neural networks is novel.\n\nQuality: This paper is of high quality. The authors provides detailed proof of their theorems. \n\nClarity: This paper is written clearly. The proof is organized professionally and easy to verify.\n\nSignificance: Accelerating neural networks is certainly an important topic. I would consider the following points as the strengths of this paper:\n1. Their algorithms achieve sublinear cost per training iteration, which is a surprising result that breaks a long-standing barrier. And it revealed a connection between deep learning and computational geometry. It may also provide some theoretical insights for previous practical fast training algorithms. \n2. They adapted the previous analysis of over-parameterized neural networks to the “shifted ReLU” setting via a nontrivial concentration and anti-concentration analysis. In particular, they used some new techniques in concentration of measure to upper bound the number of activated neurons in each iteration.\n3. Authors have an interesting observation on the initialization of over-parameterized neural networks. They showed that the threshold of ReLU function can affect the number of activated neurons for each training data, making the neural network sparse.  This is not known before, and it may have more applications in deep learning theory..\n4. Their speedup framework demonstrates that sparsity can help design more efficient algorithms. It may be further generalized and solve other machine learning problems.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have following questions about this work:\n\n1. The recent work of Lottery Ticket Hypothesis (Frankle et al., 2019) also exploits the sparsity of the neural network. How to compare this work with LTH?\n\n2. Can the results be generalized to neural networks with more layers? Also, can the algorithms be adapted to the stochastic gradient descent setting?\n\n\n    Frankle, J., & Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks. ICLR 2019.\n\n-----------------------------------\n\nTypos\n\n* Line 26: “the cost per spent per iteration” should remove the first “per”\n* Line 46: “only a small fraction (o(m))”, it should be o(1) since the fraction is defined as (#activated neurons/#neurons)\n* Line 75: “in the sense that HSR”, the sentence is incomplete\n* Line 128: the definition of shifted ReLU is inconsistent with the definition in Line 104. max{<w_r,x>-b,0} \\neq max{<w_r,x>,b}\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives new insights into pre-processing in training over-parameterized neural networks. All reviewers recommend acceptance.
Decision: Accept (Poster)