A Sublinear Adversarial Training Algorithm
Authors: Yeqi Gao
Lianke Qin
Zhao Song
Yitan Wang
Venue: ICLR 2024 poster (2024)
Keywords: Adversarial training
Primary area: learning theory

Abstract: Adversarial training is a widely used strategy for making neural networks resistant to adversarial perturbations. For a neural network of width $m$, $n$ input training data in $d$ dimension, it takes $\Omega(mnd)$ time cost per training iteration for the forward and backward computation. In this paper we analyze the convergence guarantee of adversarial training procedure on a two-layer neural network with shifted ReLU activation, and shows that only $o(m)$ neurons will be activated for each input data per iteration. Furthermore, we develop an algorithm for adversarial training with time cost $o(m n d)$ per iteration by applying half-space reporting data structure.

Published as a conference paper at ICLR 2024
A SUBLINEAR ADVERSARIAL TRAINING ALGORITH
Yeqi Gao
Lianke Qin
Tsinghua Univeristy
UC Santa Barbara Santa Barbara, CA, USA 1 Lianke@uesb.edu
Beijing, China (0oyg23mmails...mmmmmmm tsinghua, edu. cn
Zhao Song
Yitan Wang
Adobe Research
Yale University
Seattle, WA, USA
New Haven, CT, USA yitan. wangeyale.
zsongladobe..omm com
ABSTRACT
Adversarial training a widely used strategy for making neural networks resistant to adversarial perturbations. For a neural network of width n input training data in dimension, it takes (mmdd) time cost per training iteration for the forward and backward computation. In this paper analyze the convergence guarantee of adversarial training procedure on a two-layer neural network with shifted ReLU activation, and shows that only o(m) neurons will be activated for each input data per iteration. Furthermore, we develop an algorithm for adversarial training with time cost ((mdd per iteration by applying half-space reporting data structure.
INTRODUCTION
After modest adversarial input perturbations, gradient-trained deep neural networks have tendency to change their prediction results in an incorrect manner (Szegedy et al., 2013). Numerous steps have been taken to build deep neural networks immune to such malicious input. Among such efforts, adversarial training with a min- max object is most effective (Madry al., 2018) to obtain a robust neural network against perturbed input according to Carlini & Wagner (2017); Athalye et al. (201 8). Adversarial training usually yields small robust training loss practice. The min-max formulation can be viewed as a two-player game. One player is the learner of neural network and the other player is an adversary allowed to arbitrarily perturb the input up to some norm constraint. For every round, the adversary creates adversarial inputs against the existing neural network. Then, the learner adjusts the parameters of neural network by taking a gradient descent step to reduce its prediction loss evaluated by adversarial inputs.
In the past few years, convergence analysis for training neural network on original input has been established. The seminal work of Jacot et al. (2018) initiates the study of neural tangent kernel (NTK), which is a very useful analytical model in the deep learning theory area. By ever-parameterizing the neural network that the network width is relatively large (m 2 (p)oy(nn)) one can show that the training dynamic on neural network is almost the same as that on an NTK. Analyzing the convergence guarantee via over-paramettrizzaion has been broadly studied (Li & Liang, 2018; Jacot et al., 2018; Du et al., 2019b; Allen- et al., 2019b;e; Du et al., 2019a; Song & Yang, 2019; Zou al., 2020; Oymak & Soltanolkotabi, 2020; Lee et al., 2020; Brand et al., 2021; Song et al., 202 10; Huang et al., 2021; Song et al., 2021b: Chen & Xu, 2021; Munteanu et al., 2022; Hu et al., 2022; Zhang, 2022). Inspired by the over- wre-pparaeterized neural network convergence theory, (Zhang et al., 2020) applies similar analysis to adversarial training, i.c., training with perturbed input.
Training such adversarial neural networks usually done via gradient descent, whose time is determined by the product of a number of training iterations and time cost spent every training iteration. Many previous papers focus on accelerating the time cost per training iteration via nearest neighbor search (Chen et al., 2020; 2021; Daghahhi et al., 2021). For example, SLIDE Chen et al. (2020) speeds up the forward computation by efficiently retrieving activated neurons with the maximum inner product via locality-sensine hashing data structure. Using data structure to speed

---

Published as a conference paper at ICLR 2024
up optimization algorithms has made much progress for problems like linear programming (Cohen et al., 2021; Lee et al., 2019; Ye, 2020; Song & Yu, 2021; Dong et al., 2021: Jiang et al., 2021). 1), semi-definite programming (Jiang et al., 2020; Huang al., 2022), sum-of- -quurue (Jiang et 2022). non-convex optimization (Song et al., 2021a; Brand et al., 2021; Song et al., 2021b), reinforcement learning (Shrivastava et al., 2021a), frank-wolfe method (Shrivastava et al., 2021b; Song al., 2022a) and discrepancy (Song et al., 2022b; Zhang. 2022). Following this line, we will also strive to reduce the time required for each training iteration by designing an algorithm identify the activated neurons during each training iteration efficiently via high dimensional search data structure.
In this paper, we study a two-layer fully connected neural networks with shifted ReLU o, :R: R activation. We first define the two-layer ReLU activation neural network
m
(ax) = Σ ar o, ((w,, + b,)) r=1
where m is the number of hidden neurons and (x) (=)x====))) := 1(x > r] x is the shifted ReLU activation function with threshold {w,)m= Rd is the weight vector, {ar-m= C R is the output weight vector, and x E I&d is the input vector. The total number of inputs is n. Therefore, in each training iteration, we need compute the forward pass for each input vector which requires m vector inner product of dimension. This implies a (mmdd) cost per training iteration. One question arises:
Can we design adversarial training algorithm only requires o(mdd) cost per iteration?
The answer is affirmative. We outline our contributions as follows:
We analyze the convergence of adversarial training for two-layer neural network with shifted ReLU activation, and show that in each iteration only o(m) of neurons are activated for single input.
We have designed an adversarial training algorithm for two-layer fully-connected neural network with shifted ReLU activation. We leverage half-space reporting data structure of weights to identify sparsely activated neurons, enabling a sublincar training time cost per iteration.
1.1 MAIN RESULT
We give formal statement of our main result in Theorem 1.1.
Theorem 1.1 (Time complexity). Given data points in I&d and neural network model defined in (2). there exists an adversarial training algorithm (Algorithm 1) whose expected time cost per-iteration is o(mnd).
Roadmap. We present a brief overview of our techniques in Section 2. We present notations and approximate the target
preliminary tools Section We prove the existence pseudo-netwond f in Appendix B. We provide the convergence analysis in Appendix C. And we provide some key results in Section We will conduct a time complexity analysis of our adversarial algorithm in Section 5. We conclude the contribution of this paper in Section 6.
2 TECHNIQUE OVERVIEW
In this section, we briefly present overview of the techniques used in this paper.
Technique I: Approximation via pseudo-network. An important fact about over-parameterized neural network used many recent papers that if highly over-paranen ver-parameterized neural network f(; W) = Em 0r a. ((w, .T) + by,o) has weight close to its random initialization, then by the a pseudo-network g(:; W), fx; W) could be approximated, where g(:; W) is defined
0( W) = Σ a, (w,- wr.. 11(Wr,,, x) + by,0 2 7]
2

---

Published as a conference paper at ICLR 2024
We show that ze (2; W) g( W)] is very small with a probability 2 -e. We decompose f() into three components f(x) = A(x) B(x) + C(z). A(x), ((x) and ((x) are represented as follows:
A(r) = Σ
0r,0 A Wi, Pa.
B(x)= =
an.o ar,0((ur.0..)) + b..0)
m
C(+) ar (,.((w,r,, (..0)( 4
It follows from triangle inequality that [xx;; W) -(;;
- | (C(x))
Par and ( are defined in Definition 3.6. Then we derive upper bounds for the three terms on the right-hand side respectively. With the exponential failure probability, we could construct e-net of X' where e poly(m) and apply union bound on this e-net. Then we prove the stability of f and
where we get the bound of (f; W) - (x; W)l as O(K2 m 1/10 with Prob. 1 1- 81/5- And we also give the perturbation analysis for f fa: W) and g(x; W) by choosing perturbation μ with ||ll|2 S " and ( (.) The upper bound of (9(x μc; W) (o-WW)g(ce -xx)) and [f(x + μn; - W) can be bounded by O(K m 1/2) and O(K m- 11/m separately with Pro. 21- With the pseudo-network hand, we can give further analysis of the gradient descent of the [(x;; W). In this paper, the convergence of our network fæ; W) is established with the analysis above whereby choosing proper learning rate (17 = ((em-1/5)) 1/5)) and training iterations (I" = >(<=> with W near the initialization, can attain
LA Cx-(fw-)+e +
1 T
Σ Ca(fw.) t=1
And then, we can show that with Prob. 2 1- 00/5 and t ( ) the existence of W* near the initialization where
K
[W - W ||2.00 <
3/5
and small enough loss where AA- (fw.) < e, is established.
Technique II: Shifted ReLU activation. The second technique is based on the observation that, shifted ReLU activation function two-layer neural network, the number of activated neurons for each training data point is sublinear in the network width m. The Shifted ReLU activation o, is defined as
ox (x) = 1sx 7|
By choosing т properly here, we can attain o(m) activated neurons initialization. Therefore, we first prove that at initialization, the number of activated neurons is upper bounded by Qo O(m²)) with probability 2 1 exp(-S(( exp(- K² 175 ))). Then we analyze the size of neuron set which has different signs at each training iteration compared to the neuron weights at initialization. it can be upper bounded by (nm?7/8) with probability at most exp(-Q(m!/5)) We can use them to derive the upper bound of activated neurons per training iteration via triangle inequality.
2m exp(((2m;17)) K²
For the correctness of our paper, we also give the analysis of the approximation, the convergence, and the perturbation of our network based the shifted ReLU function we proposed. Base on the
Theorem A.3, we make a bridge between 1 [[,,,, +b, > 7] with 7 O 1 and [(w,,, +b, > 0). which is used in the prior work. And with this bridge, we can finish the proof of the analysis above. By
choosing O 1 we show that 19(x; W) f(; W) < O(K² m 11/10) with Prob. 2 1 01/5-
m
According to such statement, the prediction loss can also be compressed to any E (0, 1) with the
We define 0_ := (Pp(-((mm)).
3

---

Published as a conference paper at ICLR 2024
same requirement = = as well as the probability 1- -1/55- For the perturbation analysis. we also give the bound of |g(x + μr; W) g(x) and [f(x + μ4; W) - [(z; W with Pro. 2 1//
and the Shifted ReLU activation we choose.
In total, in this paper by using Shifted ReLU activation, we attain o(mnd) time complexity per training iteration and give the convergence analysis and the perturbation analysis to make sure the existence of such a network (2; W*) which leads to small enough prediction loss.
Technique III: Half-space reporting. We leverage the data structure designed by Agarwal et al. (1992) to implement the half-space range reporting functionality. The half-space range reporting problem requires us to maintain a data structure to store a finite point set P Rd In addition to storing P. half-space range problem also has queries. Each query can be denoted by (a, b) IR x IR For the query (a, b), the data structure should report a subset Pa,6 6 C where Pa,6 defined as
Pa.: = fI Rd E P, P, ((a, x)
b) 2 0}
One brute force implementation for the half-space range reporting problem is to maintain P in an array and enumerate all points in P to determine which points are contained in Pa,b- As we hope do adversarial training with lower time cost, we introduce tree data structure to organize points in P. With the tree data structure, we could report Pa,6 efficiently. And we assume that the o, and b, are not updated in this paper. In this structure, we use function query(æ. (r b,)) to find satisfied wy- And we use Pa (b,()-b,) as follows
P (2,(r-b.) = (w, E RR W. E P,sgu((w,,) - (T b,)) 2 0}
We preprocess the network weights to construct half-space range reporting (HSR) data structure for wy's 's in order that we can efficiently identify the set of activated neurons Qe,i for each of the adversarial input F; By Agarwal et al. (1992), we can also attain the time complexity of the functions in the data structure for half-space reporting including init, query, update (See details in Section 5), which is presented as follows
Tmie(n d) Oggnlogn), Touery (n, kt) Oa(n Oz(n!-1/(d/2 + k), amortized Tupdate Oa(log2(1)) (n:).
Ta,e(n14//2+9) Tauery (n, d) (2(log(n) + k). amortized Tupdate Os(nLd/2] 1).
To get the running time of training per iteration, we compute the time spent on querying the active neuron set for adversarial training data points, forward and backward computation with the activated neuron set, and updating the HSR search data structure respectively. Based on the number of activated neurons at the initialization (where the number of activated neurons is proved to be o(m) by us) and during training, by summing all parts we obtain an algorithm whose running time per iteration is Ō(m -01144)
PRELIMINARIES
3.1 NOTATIONS
In this paper, ||ж||p denotes the lp norm and mainly focuses on = 1, or oo for a vector x.
T R denotes the transpose of a matrix B kkxn, And we use | as the entry-wise L norm, || ||| as the spectral norm and [ || as the Frobenius norm. B, denotes the j-th column of
B where j E [n)) [B]|2,1 denotes Σ --11 1 B2 And || denotes maxje(n) mx] [ We use
((, to represent a Gaussian distribution where o is a covariance and is mean. We use 0. = exp((s((mm), We define || o0 as follows
|l = sup lf(x)),
(1)
ZE
where f:X R.
4

---

Published as a conference paper at ICLR 2024
3.2 NETWORK FUNCTION
We consider a neural network f which is parameterized by (a, b, W) E Rm x R x Rdxm;
f(x) Σ a, or b.)
(2)
Note that this neural network is two-layer, and also called one-hidden layer. The activation function consider here is shifted ReLUU F represent the class of the function above. Because R and b E R remain constant throughout adversarial training and only W Rdxm is updated, we will also use f(x; W) denote the network. And with T > or
Rz0 defined as follows
(x) = 1/2 > 7| .
Let S C Rd x R be the training data with element (xz, 3/) where E [n]. There are some standard assumptions our paper regarding the training set. While maintaining generality, we set for every I; Ed wherei E [n]] that Fi,d 1/2 and ||z:||2 1. Therefore, set X' := {o E R Z 1/2, | }} is defined. We also define X1 as maximal -net of X' where E R. is a constant. We set 134| - where i [n] for simplicity.
Definition 3.1 (Initialization of a, W. b). We define the initialization of ao I whose entries are uniformly sampled 1-mt/s + mi75 J. Wo E Idx= whose entries are i.i.d. sampled from (O, 1), bu II. whose entries are i.i.d. sampled from N(0, ).).
3.3 ROBUST AND ADVERSARY LOSS
We take into account the following loss function for analysing the neural nets.
Definition 3.2 (Lipschitz convex regression loss). If loss function &. x meets the below criteria, it is regression loss (Convex and Lipschitz): ((z, x) for every E. positive, 1 Lipshciitz and convex in the second argument.
Definition 3.3 (p-Bounded adversary). With (z(u, == e 1 p)n n Suppose > O. For adversary A F X x R - X, we claim A is p-bounded, if A(f, x. v) E (2 p).
And then against loss function A defined as the worst-case p-bounded adversary as follows:
A (f, (f, == argmax ((F)) SeB2(z.p)
Given neural net represent adversarial dataset generated by A with respect to it as
A(J = ((A(s y:) y:))
Then give formal definition of robust loss function. Definition 3.4 (Robust loss and training loss). For raw data set S = U:) with n training points and prediction model f. the training loss is
L(S. f) = n Σ f(:)))
The robust training loss is defined for p-bounded adversary A
CA()) =
Elm, S(A(f, 24 vi)))
TI
In addition, the worst-case of the above loss is defined similarly
==
max Elys, ((t)
Definition 3.5 (Chi- Shhire distribution). If ffa1.... an independent, standard normal random variables, then the sum of their squares, Q = Σm ar is distributed according to the chi-squared
distribution with m degrees of freedom.
5

---

Published as a conference paper at ICLR 2024
Algorithm Sublinear adversarial training
1:
procedure FASTADDERRARIAATRRANNNGG... b)
2:
Adversary A
3:
Learning rate 77.
4:
Training set S [ y.)
5:
Initialization ag. bo. Wo-
6:
Data Structure for Half-space reporting ds (S),
7:
8:
for t in [T] do
9:
5(0)
10:
for i in [n] do
11:
2 A(fw., 2i, 91)
12:
Qr t ds. A...QEEY(()) (a)
13:
Qt, C [m]. it is set of indices such that j-th neuron is activated
14:
5(0) = st) u 31)
15:
end for
16:
Qi + Use(nj Qu
17:
Forward pass for x/ only on neurons in Qt.; for i [n]
18:
Calculate gradient for x. only neurons in Qt, for E [n]
Gradient update W(t+ 1) ((t) 17- (w S(t)) for the neurons in Qr
20:
DELEET (w,, (t)) for Qu
21:
Ass.ADD(,((C 1)) for E Qr
22:
end for
23:
return {W()))
end procedure
Definition 3.6 (Boolean function for activated neurons). For [m], we define Aw,, dar and 4 as follows:
Aw, = Wy Wr
@ prr 1[( Awr, 2)) br.a 2 T]
(0) = 1[(wr,0, x) + br,0 2 T|
3.4 WELL-SEPARATED TRAINING SETS
commonly made assumption in the literature on over-parameen over-parameterized neural network assume the training set is well-separated. There are several variants of separability defined in related literature. We give the formal definition of the s-sparrability adopted in this paper.
Definition 3.7 (7-separabilitty. for all + j [n], 7 S e(e 2p) and ||x; x;ll2 2 e, training dataset X will be 7-separable for p-bounded udversary.
3.5 SUBLINEAR ADVERSARIAL TRAINING ALGORITHM
Associated with an adversary A, the algorithm can be used to describe training a network in an adversarial way. The adversary creates adversarial samples against the present neural network in the inner loop. To reduce its loss on the new adversarial samples, the neural network's parameter undergoes gradient descent step in the outer loop.
Remark 3.8. We assume that ((t) and W, are independent, when calculating the Vw L(S(), fw.) so that we don't need differentiating over A.
3.6 ACTIVATED NEURON SET
In the analysis of our algorithm, we pay attention to the activated neurons. We give the formal definition of activated neuron set in Definition 3.9.

---

Published as a conference paper at ICLR 2024
Definition 3.9 (Activated neuron set). For all t 10.1, T), >>>>> 0 and [n], we define the
set which has activated neurons at time as Qt := {r E [m] (Wre. + b, > T} The number of activated neurons time is also defined the size of Q1,
k = 1Qu.i
(3)
ANALYSIS OF OUR ALGORITHM
In this section, we will provide an analysis from two perspectives. Firstly, will delve into the convergence analysis when employing the Shifted ReLU activation function. Secondly, we will establish the upper bound of activated neurons during each iteration, crucial step in our algorithm's time complexity analysis. Now, let's shift our focus to the convergence analysis.
4.1 CONVERGENCE ANALYSIS OF ADVERSARIAL TRAINING WITH SHIFTED RELU ACTIVATION
In this section, we provide essential components of the correctness proof. Due to space constraints, we have included the complete proof in the appendix. Here, we offer overview of approach to demonstrating the convergence of the training process, considering both adversarial data and the shifted ReLU activation function.
For analyzing the gradient descent of [a;; W). a fake-network g(:; W) is defined in this paper. And we show that by choosing W near the initialization and 0 () with Prob. 01s the neuron network (a; W) can be approximated by g(x; W) properly. The proof is given in Appendix C.I.
Theorem 4.1 (Approximation of (x; W)). With K 2 1, T = 0 ( for every m 2 poly(d), and every W E d where ||Wn - W S
ma75 with probability at most 1/ exp(S((m over the Snitialization(See Definition 3. 3, we have that
K
sup (9 W) f(x;W) 2 O(K² 1m0m-mm//// m-1/10) =EX
We do perturbation analysis for fæ; W) and g(x; W) with shifted ReLU activation in the following lemma when the perturbation μ satisfies that ||l|| < and x + μ E X. We obtain the perturbation upper bound for [f + μ; W) - f(;; W)I and 1g(x + pl: W) g(æ; W) with the shifted ReLU activation threshold set as 7 O(1/m), which is proved in Appendix C.9.
Lemma 4.2 (Perturbation analysis of f(x; W) and g(æ; W)). For every x E X,, every E TR' where ||al|2 S 1 and x + E X. with r O ! and probability at least 1 - 1/ exp(X((m (2)), we have
Ig(x + W g(:; W) < O(K m m-122)
(4)
and
[(++;; - f (z; W\ S O(K m -1 1/m
(5)
The convergence of our neural network f(z; W) with shifted ReLU is stated as follows:
Theorem 4.3 (Optimal weights versus the initialization). For all K O, (0. 1), and for every m larger than poly(n, K, 1/e), we set n = (em (1/5) and T ( -2))) in Algorithm 1. For every W* Bdxm with W. W* < K
m355. Algorithm outputs weights (W.)t=1 such that
CA-(Sw-) +e + Callw)
with succeed probability at least 1 01/5- The randomness is from random initialization (See Definition 3.1).
In the following statement, we show that by choosing proper - = O 1 and m as a large enough constant, W around the initialization and small enough worst-case robust loss can be attained by us. The proof is given in Appendix B.8.
Theorem 4.4 (Convergence of Algorithm 1). For all e E (0, 1), we can get K poly((n/e)) and let m be larger than some poly (/) we can find, with probability 2 0155 and T = O 222), there will be a W E _dxm such that
I e and [[, W0 S K ma75.
The randomness is because of the selection of Wo, by, og-
7

---

Published as a conference paper at ICLR 2024
4.2 THE UPPER BOUND OF ACTIVE NEURONS DURING TRAINING
For the purpose of getting the time complexity of per training iteration, we propose the following two statements, Lemma 4.5 and Claim 4.6. And their proofs given Appendix C.I3 and C.12. By applying shifted ReLU activation o in neural network and choosing K/ K/m3/5 attain o(m) activated neurons here. With o(m) activated neurons, we can attain the running time per training iteration.
can
Lemma 4.5 (Number of activated neurons during initialization). Let eQ E (0, denote a fixed K²
constant. Let Qo 2m exp(- V (I,,)) is defined as (,(x,)) 11) (1 x) bnool 2 n). With succeed probability at least
(mm77)) ((.²)). For every 1) E R4, E X and r E [m]]
1 - -n/ exp(I((m exp( 4m-77 ))}, it holds that
Σ rEJm]
V,(e,K/m22 S Qu-
Besides the activated neurons during initialization bounded, also give the bound of activated neurons versus the initialization. The proof given in Appendix C.12 is based on the shifted ReLU activation d, with > O. The sublinear activation of neurons, along with the limitation number of neurons versus the initialization which is the primary focus of our computations during the training, provides us with an opportunity employ the Half-Space Data Structure introduced in the following section. This allows us to maintain a time complexity of o(wmd).
the
Claim 4.6 (Bound for activated neurons versus the initialization). For any || 12 S m -1521 and any subset (xx) S X. Then holds with succeed probability least 01 that
1[3 E [n], agn((an wro + Awy) + by.0 -) sgn( 0) + 6,,0 - -]] O(rm²/$))
Wi [m]: l E [m], sgn((as, 1ro0 Awr) + br.0 7) sgn(( Wr,o) br.0 - 7) < 0m0mmmmm/
The randomness is from initialized states (See Definition 3.1).
TIME COMPLEXITY
For the identification of activated neurons at each iteration, we will introduce half-spacc data structure. This section 5 analyzes the adversarial training algorithm's 's time complexity. In section 5.1, provide the Half-space reporting data structure at first. In Section 5.2, examine the time complexity of our sublinear time adversarial training algorithm.
5.1 DATA STRUCTURE FOR HALF-SPACE REPORTING
We formally give the definition of the problem of the half-space range reporting, which is of importance in the field of computational geometry, And we give the data-structure in Agarwal et al. (1992) whose functions outlined in Algorithm 2 and complexity is given in Corollary 5.2.
Definition 5.1 (Half-space range reporting). For set of m points P C Rdd, three operations are supported:
QUERY(W'): find each point in P. W with W C IRd as a half-space.
. INSERT(p) add point p to P.
REMOVE(()) remove point p. from P.
We address the problem (See Definition 5.1) with the data-structure in Agarwal et al. (1992) which has the functions outlined in Algorithm 2. Because the data-structure partitions the set P recursively as well as uses a tree data-structure to organizes the points. Given a query (b, c), all the points 2 Id from P which satisfy (b. 2) e 2 0 can be quickly found from P. And in our paper. the problem finding all E [m] such that (w,, 2) + b, > 0. The Space (See Definition 5.1.) in our algorithm defined by (z, (7- for [m] and the QUERY (b, e) holds for QUERY (7-b,)).
8

---

Published as a conference paper at ICLR 2024
Algorithm 2 Data Structure For Half Space Reporting
1:
data structure
2:
INIT(P: n,
Construct our data structure via P C R |P
3:
QUERY (b, c) INSERT(2)
D bb,cE RR. Find all the points E P which satisfies sgn( (b, z) c) 2 0
4:
b Insert point E Rd to
5:
REMOVE(2)
Remove point E F from P
6: end data structure
Corollary 5.2 (Agarwal et al. (1992)). Considering n points in Rd set, we can solve the half- space reporting problem with the complexity as follows, where TisTe indicates the time to construct the data structure, TQUERY represent the time spent on each query and T Tupdate represent the time on each update:
Tima(n, d) = Oo(nlogn), Tquery (n,d, k) O2(n2-1/14/22 + k), amortized Tupdate Oa(log((n)) Ta..(nl4/2)to), Tauery (n, d, k) = Oz(log(n) + k), amortized Tupdote = Da(nld/22 1).
5.2 WEIGHTS PREPROCESSING
We offer adversarial training algorithm with sublinear time in this part. The foundation of our algorithm (Algorithm 1) is the construction of a search data structure (in high dimensional space) for neural network weights. To avoid needless calculation, the activated neurons can be identified quickly by using the Half-Space reporting technique. We provide an algorithm with preprocessing procedure for w, where r [m]. which widely used (see Chen al. (2020); Kitaev et al. (2020); Chen et al. (2021)). The two-layer ReLU network is given in section 3.2 as f(x) = >m (r o- ((wr, + by-). We can rapidly identify a collection of active neurons Qt.i for every (which is the adversarial training sample 2;) by building HSR data structure. Pseudo-code is shown in Algorithm 1. The time complexity analysis of the algorithm is the major topic of the remaining portion this section.
5.3 TIME COMPLEXITY PER TRAINING ITERATION
Since we leverage the Half-Space Data Structure, the training time complexity is inherently linked to activated neurons, as elaborated Section 4.2. Given that the number of activated neurons sublinear during each iteration, the following conclusion naturally ensues.
Lemma 5.3 (Time complexity). Given two-layer ReLU network defined in E2. Assume there are n data points. Say those points are from d-dimensional space. Then, the expected time cost for each iteration of our adversarial algorithm (Algorithm 1) runs in time (mm² (m12-)(1d)))mm nd).
The detailed proof is deferred to Appendix C.16.
CONCLUSION
Making neural networks more resilient to the impact adversarial perturbations is a common application of adversarial training. The usual time complexity of training neural network of width m, and n input training data in d dimension is M(mmd) per iteration for the forward and backward computation. We show that only a sublinear number of neurons are activated for every input data during every iteration when we apply the shifted ReLU activation layer. To exploit such characteristics, we leverage a high-dimensional search data structure for half-space reporting to design an adversarial training algorithm that only requires Õ( 1-m (1//)/))//))))- nd) time for every training iteration. To the best of our knowledge, our work does not result in adverse effects society. We also emphasize that the training procedure proposed this paper is equivalent to applying adversarial training to neural network. Although there is no extra negative societal impact introduced by method, to make sure the neural network model is properly used, the user needs extra attention, which goes beyond the scope of this paper.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
Yitan Wang gratefully acknowledges support from ONR Award N00014200-1-2335 and a Simons Investigator award from the Simons Foundation to Daniel Spielman.
REFERENCES
Pankaj K Agarwal, David Eppstein, and Jiri Matousek. Dynamic half-space reporting, geometric optimization, and minimum spanning trees. In Anmual Symposium on Foundations of Computer Science, volume 33, pp. 80-80. IEEE COMPUTER SOCIETY PRESS, 1992.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In NeurIPS. arXiv preprint arXiv: 181..04911. 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In ICMI,, 2019b.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In NeurlPS, 2019c.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Cireumventing defenses to adversarial examples. arXiv preprint arXiv: 2018.
Sergei Bernstein. On 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.
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (overparametrized) neural networks in near-linear time. In ITCS, 2021.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pp. 39-57. IEEE, 2017.
Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, et al. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. Proceediiggs of Machine Learning and Systems, 2:291-306, 2020.
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 International Conference Learning Representations, 2021.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. In ICLR, 2021.
Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals Mathematical Statistics, pp. 493-507, 1952.
Michael Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021.
Shabnam Daghaghi, Nicholas Meisburger, Mengnan Zhao, and Anshumali Shrivastava. Accelerating slide deep learning modern cpus: Vectorization, quantizations, memory optimizations, and more. Proceedings of Machine Learning and Systems, 3: 3:156-166, 2021.
Sally Dong, Yin Tat Lee, and Guanghao Ye. A nearly- nearly-linear time algorithm for linear programs with small treewidth: A multiscale representation robust central path. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory Computing, pp. 1784-1797, 2021.
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In ICML, 2019a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In ICLR, 2019b.
10

---

Published as a conference paper at ICLR 2024
Roy Frostig, Cameron Musco, Christopher Musco, and Aaron Sidford. Principal component projec- tion without principal component analysis. In International Conference on Machine Learning, pp. 2349-2357, 2016.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. ISSN 01621459.
Hang Hu, Zhao Song, Omri Weinstein, and Danyang Zhuo Training overparametrizee neural networks sublinear time. In arXiv preprint arXiv: 2208.042822 2308005508, 2022.
Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. Fl-ntk: A neural tangent kernel-based framework for federated learning analysis. In International Conference Machine Learning, pp.
4423-4434. PMLR, 2021.
Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang, Solving sdp faster: A robust ipm framework and efficient implementation. In FOCS, 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018.
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In 2020 IEEE 6lst annual symposium on foundations of computer science (FOCS), pp. 910-918. IEEE, 2020.
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general 1ps. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pp. 823 832, New York, NY, USA, 2021. Association for Computing Machinery.
Shunhua Jiang, Bento Natura, and Omri Weinstein. A faster interior-point method for sum-of-squares optimization. arXiv preprint arXi::2202.08488 2022.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.044: 2020.
B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 2335 2000.
Jason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang. and Zheng Yu. Generalized leverage score sampling for neural networks. In NeuriPS, 2020.
Yin Tat Lee. Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. Conference on Learning Theory, pp. 2140-2157. PMLR, 2019.
Wenbo V Li and Q-M Shao. Gaussian processes: inequalities, small ball probabilities and applications.
Handbook of Statistics, 19:533-5977 2001.
Yuanzhi Li and Yingyu Liang. Learning overparameterrized neural networks via stochastic gradient descent on structured data. In NeurlPS, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR. arXiv preprint arXiv:1706.00083, 2018.
Alexander Munteanu, Simon Omlor, Zhao Song, and David Woodruff. Bounding the width of neural networks via coupled initialization a worst case analysis. In International Conference on Machine Learning, pp. 16083-16122. PMLR, 2022.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameteriizttoo:: Global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84-005, 2020.
Sushant Sachdeva, Nisheeth Vishnoi, et al. Faster algorithms via approximation theory, Foundations and Trends in Theoretical Computer Science, 92):125-210, 2014.
11

---

Published as a conference paper at ICLR 2024
Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu. Sublinear least-squares value iteration via locality sensitive hashing. arXiv preprint arXiv:2105.08285, 2021a.
Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu. Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures. Advances Neural Information Processing Systems (NeurIPS), 34, 2021b.
Zhao Song and Xin Yang. Quadratic suffices for over-parametriizaioon via matrix chernoff bound. arXiv preprint arXiv: (906.:39990339999 2019.
Zhao Song and Zheng Yu. Oblivious sketching- central path method for linear programming. In International Conference on Machine Learning, pp. 1035-9885777 PMLR, 2021.
Zhao Song, Shuo Yang, and Ruizhe Zhang. Does preprocessing help training wer-parameeerrize neural networks? Advances in Neural Information Processing Systems, 34, 2021a.
Zhao Song, Lichen Zhang, and Ruizhe Zhang. Training multi-layer over-parametrized neural network in subquadratic time. arXiv preprint 1rXiv:2112.07628, 2021b.
Zhao Song, Zhaozhuo Xu, Yuanyuan Yang, and Lichen Zhang. Accelerating frank-wolfe algorithm using -ow-dimeniional and adaptive data structures. arXiv preprint 1xXiv:2207.09002, 2022a.
Zhao Song, Zhaozhuo Xu, and Lichen Zhang. Speeding up sparsification using inner product search data structures. arXiv preprint arXiv:2204.03209 2022b.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint 131.v:131..6/99 2013.
Guanghao Ye. Fast algorithm for solving structured convex programs. The University of Washington, Undergraduate Thesis, 2020.
Lichen Zhang. Speeding up optimizations via data structures: Faster search, sample and maintenance. Master's 's thesis, Camegie Mellon University, 2022.
Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse of dimensionality. Advances in Neural Information Processing Systems, 33:679 (68896688,996 2020.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Mach. Learn., 2020.
12

---

Published as a conference paper at ICLR 2024
APPENDIX
Roadmap. We first present some useful tools from previous work in Section A, then demonstrate the existence of pseudo-networt which approximate f in Section B. We then present convergence analysis in Section C.
A MORE TOOLS FROM PREVIOUS WORK
Lemma A.1 (Corollary 5.4 Frostig al. (2016)). With k
1/² In (2/a) and x E [-11, (n, (x<(=)] S c1/2, where Pı (z) := Ei -- 2i=1
we have sgn(2) (z)
Theorem A.2 (Theorem 3.3 from Sachdeva et al. (2014)), With X1,..., X. as independent #1
random variables, Xm = E X; and 2 0. for all m,t which are positive integers and all 2 E 11-,,,, 1]. we have
EX (T.m (2) 1m I t]] 1 S 2c f /(2m)
Theorem A.3 (Theorem 3.1 from Li & Shao (2001)). Suppose that rj > 0 and T > 0. We obtain,
cxp(-1f/2)
Pr [| S 7| (m.11
Pr [| m1 S r N1011) (~,,1,
Pr
||] S r).
The following results will be used in proof. Definition A.4 (Lipschitz continuity). A function f
is called C-Lipschitz continuous if. for each 1 22 E X it holds that d(f(x)), (x2)) S C ((I1,T2)) where stands for the distance.
Lemma A.5. With X is sampled from (0, o²), we have |r[[X| S n) ( )
Lemma A.6 (Hoeffding bound Hoeffding (1963)). For {X;}] H where X; bounded by (ct, d,] inde- pendently, = (d) and U Σie(n) X1, it holds that Pr[ [[ 2 n| S 2 expl Eieta of
2n
Lemma A.7 (A Sharper Bound for a Chi-square Variable), Let X be chi-square with degrees of freedom. For any positive t, the tail of X can be bounded by Pr[X- - n 2 2 + 2t] I and Pr[X- - n S -2vnt) I et
Lemma A.8 (Chernoff bound Chernoff (1952)). With Y Σ Y, where Pr(Y, 1] pa and for all i [n]. and Y; are independent, and E[y] =E= Pi, it holds that
Pr[y, 0]
* 44 < c 1 Pr(Y & j(1 c)] S exp(-221/2),
. Ve > 0, Pr|y 2 (01 + ++) S exp(-t²)u33)
Lemma A.9 (Bernstein inequality Bernstein (1924)). We use YI,... Yn to represent independent
random variables whose mean are O. Assume that [Y,] < M almost certainly. We have for every
7 >
1 1
Pr P Y2 S exp
ΣØ= E + 1
Claim A.10. Let w, b be sampled from (0, Ta) and (O, respectively. Suppose rj 2 0 and for every x. E X, it holds that Pr[l(w, æ)) + S 7) = O(r).
B EXISTENCE OF PSEUDO-NETWORK TO APPROXIMATE f"
In this section, complexity measure's definition for polynomials is given first in Section B.1. In Section B.2, state tool from previous work. We demonstrate the existence of function f* that reliably fits the training dataset and has "low complexity" in Section B.3. We prove that there exists univariate polynomial qe, (2) estimate the step function in Section B.4. We provide stronger version the polynomial approximation guarantee in Section B.5. An upper bound of the coefficients of C₁ (x) is given in Section B.6.
Then we demonstrate that by using a them together prove Theorem B.10 in Section B.8.
we can approximate f in Section B.7. We put
13

---

Published as a conference paper at ICLR 2024
B.1 DEFINITIONS
In the beginning, we define a complexity measure of polynomials according to Allen-Zhu et al. (2019a) with K == in this work.
Definition B.1. With parameter e1 > O, c as large enough constant and univariate polynomial ((=) = Ej=o azz) with any degree-ki, the following two complexity measures are what we define
k c(o,e))= := Σ d. (L(L+(W(((/))))))
logl
1=0
and
C(o) = c. Σ ( 1) 1.75
aayl
1=0
B.2 TOOLS FROM PREVIOUS WORK
We state a tool from previous work (Laurent Massart, 2000).
Lemma B.2 (Laurent-Massart (Laurent & Massart, 2000)). Let 01 be nonegative, and set
|0/30 sup la,1. iE|n]
For Li. Z3 1), let X = En 21=1 ai (7 1). Then the following inequalities hold for any positive
Pr|X 2 2/al3 v 2/a/ Se-
Pr[X S -
Lemma B.3 (Lemma 6.2 from Allen-Zhu al. (2019a)). Let C be defined as Desinition B.I. For every 62 E (0, 1/C()). Let á - IR be a univariate polynomial. There will be a function the following
h: 2 (- C(o, e2)) so that for all y, w Bd where 1|al|2 ||
Blh((w" 3) 1( 3 0}] - (0(((((w00 S E2. holds. In the above equation, 3 ~ (0, 1), n~ N(O, Ia).
B.3 ROBUST FITTING WITH POLYNOMIALS
The purpose of this section is give the proof of Lemma B.4.
Lemma B.4 (Lemma 6.2 in Zhang et al. (2020)). With M = 24- In(48n/e), we have a polynomial q: K. + IR where the upper bound of its coefficients is 1266M) and the upper bound of its degree M, such that for every 3 E B2(x,,)) p) and j E [n].
Σ V/ (((2,, y1 S c/3.
B.4 EXISTENCE OF STEP FUNCTION ESTIMATION
In the following claim, prove the existence of univariate polynomial qe, (2) to roughly estimate step function.
Claim B.5 (Lemma 6.4 in Zhang et al. (2020)). With M 241n(16/c1) and 61 E (0, there will be
univariate polynomial ge, (z) with the bound of coefficients is O 20M and degree at most M, such that
1. |e,, (2)) S c, for all such that -15=<1- (2 2)2/22
2. (g,(()) (z) 1| e1. for all such that 2
14

---

Published as a conference paper at ICLR 2024
B.5 STRONGER POLYNOMIAL APPROXIMATION
According to Frostig et al. (2016), we need a more robust version of the sgn function's 's polynomial approximation result in the following lemma.
Lemma 6.6 (Lemma 6,4 in Zhang et al. (2020)). Let M In and 11,11 E (0, 1). There will be a univariate polynomial
Pei (x)
Σ
(E(
with layl S 24M and degree & S M, which the sgn function' <1-approximation in [-1, 1 (-7. such that
1. Va E 11-1,-1] Pe, (z) + + Se.
2. Vo E [7, 11, [Pe, (z) - Sc.
B.6 UPPER BOUND OF SIZE OF COEFFICIENTS OF Cx(z)
In the following we get the upper bound of coefficients of Cn (ar)'s size.
Proposition B.7 (Proposition A.13 in Zhang et al. (2020)). We define Cz(2) as follows:
[0.5k]
() 2-1) jE(O...,) .3
Cx(x)= == Σ
Σ
2i
2
The size of the coefficients of C& (x) is at most 2
The following outcome is a direct result of the Proposition B.7: Corollary B.8 (Corollary A.14 in Zhang et al. (2020)). With s 0, M, = Eis X,, M 2 and
X1,..., Xg iid #1 random variables, Ps.M (x) is defined (s. Exx...,x [CMr (x) 1[M S M]].
The upper bound of Ps.M (z) degree is M and the upper bound of its coefficients is 2
B.7 FAKE-NETWORK APPROXIMATES f*
Suppose m > poly(d, (n)c)1/7). For a matrix W E Rddm, with fake-networt g(;; W*), f can be approximated uniformly across X. Compared Zhang al. (2020), our neuron network here is based on the shifted ReLU activation whose threshold is T.
Lemma B.9 (A variation of Lemma 6.5 in Zhang al. (2020)). For all (0, there will be K (oly((n/e) so that let 0 ).), m larger than some poly(d, (n/e) we can find and then with probability 2 1 - 1/ cxp(S((( (m) ())))) there will be W E Rdxm such that
sup [g(x; W*) fz(x)) $ e/3
and
K
| Woll2,0 S
3335
Recall that the randomness due to initialization (See Definition 3.1).
Proof. With q(2) as the polynomial constructed from Lemma B.4 for every E [n]] its complexities C(g) and C(q, Ea) (See Definition B. can be bounded now, where we will set ćy after C(g) bounded (E3 1/C(g) according to Lemma C.18).
Next, we explain how to upper bound the C(g). one can get
C(g) Sc 0 E 1) 1.75 2
20M
15

---

Published as a conference paper at ICLR 2024
(M + 1)2.75
26Mr
<c. 02
where the 1st inequality is due Definition B.1 and M is the upper bound of the degree of and C2 2 is the upper bound the size of its coefficients, where C2 E R, is a constant and
M = 24 1n(48n/e), the second step is due to (M + 1)2.75 E5=o + 1)1.70.
By E3 (c 02 (M+1)2.7 )
get:
(M + 1)2.78 26h,
In(1/es) = In(c.
7
{M
(6)
Then discuss about how to upper bound C(q. c3),
M S 02
Clg.
26M
c11 /In(1/e3)/j)
i=0
< 0(1)
26M (M + 1)c eV M/1ess
?
s =0(1) (M + 1)c ev MMO(M)
1 20M
<2
where the first step is due Definition B.1 and M is the upper bound of the degree of q and 02 26M the upper bound of the size of its coefficients, the second step comes from the geometric sum formula, the third step comes from Eq. (6), and the fourth step follows that C e M-M(() < (0(M)
With regard to the selection of and the random variables, we now describe how to carry out the n use of the lemma.
We define
B [a (0
We have that nB d(" (0/00/7 < m with a large enough chosen. We use the Lemma C.18 with for E [n - 1ʃ and with k: = m - (n - 1)1 for = n.
For the i-th datapoint, we use the (m 1/2 (1- (1-1) m 1/2 (10 ((- as (wr,0, br,0, ao) in the Lemma C.18.
By using union bound over n different terms, we can recompute the probability, which is
2 1 - 11-n/cpplf cmmpc(((((mmmm) = 1/ (xw((((/pmmmm)))mcc
Recall the movement of weight,
AW = (A ... (W(")) E dmd
Then we can obtain the following upper bound for |AW 2,,0
Cla C e33m2/3
m AW 1 2. s 50(
O(m 4/5 C(g, 6z) n)
S 0mm 3/5 Clg. 63) n)
0mm 3/5 ((r 11
16

---

Published as a conference paper at ICLR 2024
where the reason behind the first inequality is Lemma C.18, the second inequality is due to simplifying the terms, the third step is due m=77 And
and the final step comes from Bn & (n/c)e/7d s m.
m 375
m
Vx E X,
Σ 1(( 2) + 6n,0 2 rlano(Au,,
Σ (ua((at S ne3 E/3,
where the final inequality serves as a rough but adequate bound.
B.8 PUTTING IT ALL TOGETHER
When we construct function the Ja:W- and (z; W). we bring the new shifted RELU activated function. And existence problem is base on the new function constructed compared Zhang et al. (2020). Put everything in this section together we can prove the following theorem:
Theorem B.10 (A variation of Theorem 5.3 in Zhang et al. (2020)). For all e E (0, 1), we can get K = (nly((n/e) and let m be larger than some poly(d, (n/e)//) we can find and t = (
with probability 2 1 - 01/5, there will be W E &Rd so that the following inequality holds:
CA (fw.) S
and
K
IW W 12,00 I
m335
The randomness is because of selection of Wo, bo, Og-
Proof. To prove Theorem B.10, we shall make use of Lemmas B.4, B.9, and Theorem C.I. f is the result of Lemma B.4.
As result of integrating Theorem C.I with Lemma B.9 and m 2 poly(d)) we obtain with prob.
1 1/ exxx((((m2/5)) 1/ exp(((( (m/))),
there will be a W* Rdxx such that
K2
Vx E E X1 (²) - f(x; 0
and [g(x; - s e/3. (7)
1/110
and
K
[Wo - W/ 12,00 <
3/5
Therefore, for every 3; E B(x,, 0), E [n].
(y,, f(ā,; W*))
- [ī W*) - yul
< - - W*)
yıl
2c
K2
+ 0
1/10
<e
where the first step follows from the 1-Lipschitz defined in Definition 3.2 the second step is because of triangle inequality and the third step is due to Eq. (7) and the final step comes from e/3 2 O K² m ). poly(d, (n) I m, given sufficiently big polynomial. Therefore. we can get L. (f*) S.
We get -1/ exxp(((mmm//)) the bound of probability by choosing 2 n²
17

---

Published as a conference paper at ICLR 2024
C OUR ANALYSIS
We demonstrate the stability of and g in Section C.1 and the upper bound of the sum of F, in Section C.2. In Section C.3, we upper bound V, In Section C.12, we analyze the upper bound of number of activated neurons during initialization. In Section C.4, we define several helper functions A(z). and (z)). In Section C.5, we first prove the upper bound of [A(x) g(x)). Then we upper bound (x) in Section C.6. We further upper bound [C(x)) in Section C.7. We can obtain the overall upper bound for [f(z) ((x) in Section C.8. We provide some perturbation analysis in Section C.9. We prove the convergence of our algorithm in Section C.10. We analyze the gradient coupling of our algorithm in Section C.I1I We upper bound the number of activated neurons for every iteration in Section C.13. We prove the pseudo-network network approximation guarantee in Section C.14. We analyze the stability of S and S2 in Section C.15.
C.I PROOF OF STABILITY OF f AND
Note that when we prove the stability of f and g. our definition of f and g is differennt from Zhang et al. (2020) because of the introduced shifted ReLU operation. With selection of T = O ) we prove a different upper bound for supzex [z; W) g(:; W)), where f(z; W) = Er= a,,0(W,r, - Aw,, Z²) + ) and g( W) Em 20 a, (Aw,, x) compared with Zhang et al. (2020).
Theorem C.1 (A variation of Theorem 5.1 in Zhang et al. (2020)). With K 2 1, = 0 ( for K
every 2 poly and every W E Rdxm where l|Wo W1 I
m37 with probability at most
1/ exp((((mm/))) (5)) over the imitialization(See Definition 3.1), we have that
sup 19(2; W) f(;; 2 O(K² . m m1/10) =ex
Proof. We have IW- Wo 2, limitation is enough get the upper bound of [ gw llo (See Definition 1).
335. which coincides randomly with the Wo, do bo. The above
We will take W into consideration now. For simplicity, f(x; W), g(æ; W) are written as f, separately. Now, can get
f(x) = Σ ano((uro + Awr. + br.0)
m
g(x)
0r (oo(AAi Wr, x) ( 2.
We represent (z, 17) as follows for any x E Nn 17 E R, and r e [m].
0,(,, 1)) = 1[kwn,,, + bn,o - 5|
(8)
With Claim A.10, we can get
Pr(V,(I,n) = 1] Pri](u,,o, 2) br,ol S O(nmm).
We define
F, (0 x.r # .r,).
Now, we can get the bound of the size of En F, in Claim C.2. With probability at least 1 1/ (xp(0)
F, S O(K m m/10), Vx X.
18

---

Published as a conference paper at ICLR 2024
What needs be done now is union bounding above inequality across each E X. Obviously, the issue that is not countable still remains. Therefore, across a net X with an extremely fine grain, will get union bound first and then discuss how f and g have changed as x X input have changed slightly.
With X as maximal m net X, we can have that |x1] S (1)) By Lemma C.8 and union bound across x E Li. we can know that for m 2 (dd").
(1/ exp(((m exp(OOd m)) -0115:
one can obtain the following guarantee:
Ye X1, lø(x; ([);W)- - [(;; W) S OK2 1-100
The perturbation analysis comes last. We leverage Lemma C.9 which works for fixed inputs to apply union bound across x E X,. By m 2 Mdd for all æ E Xi and μ E Rd where || S and x + μt E X, we can have that with probability at most (1/ exp((((m (2))) exg(O(dlog = 1/ exp((((m2 the Eq. (15) and Eq. (14) fail.
Now, with prob. 2
- 1/ ex/x(((((((m)))) - 1/ exp(((()) = - 10/5
One can further upper bound [| W) ol by:
11 W) - f(;; W) - O(K2 11/10
1/10 + 1/5 + K 112 + K -mm" -m=))
=(K2 m m11100
where the first step comes from combining Eq. (9), Eq. (15) and Eq. (14), and applying a union bound, and the second step is due to combining the terms.
The proof is complete.
C.2 UPPER BOUND OF SUM OF F,
The sum of F, is to be upper bound this section.
Recall that F. 1 p.r + ( and our definitions of dz,r and 400 are based on the shifted ReLU activation. Note that _x=1 F, represents the number of neurons whose outputs have different signs between the initialized weights w,,0 and the updated weights w,,0 + Aw,. And we obtain a different upper bound of sum F, compared with Zhang et al. (2020).
Claim C.2 (A variation of Claim A.3 Zhang et al. (2020)). For each æ X,
m
Pr
2/20]] 2 1 100/00 SOKK
Proof.
With an x E X' fixed,
|&W < K/m²// and || = 1, we can get F, < 1 ||llw ||2 2 x) br.o -1] < (z, K m nn-3/)).
where the first step comes from the definition of (0) and (See Definition 1.), and the second step comes from Eq. (8) and ||W||a |2.00 - K/ K/53/5
With Gaussian anticconcentration from Lemma A.5, we can have that for all r [m]]
Pr[V,(a, K/m3/5) < Pr((wr,,,, x) br.ol S K 3/5
19

---

Published as a conference paper at ICLR 2024
<O 1/11)
By fixing x, there will m Bernoulli random variables that are independent. With Bernstein inequality from Lemma A.9, with probability at most 1/ exp((((m9/10)) attain that
Σ v (a, K m 3/00 2 O(K 1/
We also have
v x K m 3/5), Σ F -
rm
which implies
m
Σ F S O(K .m. m/10).
The proof is complete now.
C.3 UPPER BOUND OF V
In this section, we want to prove the upper bound of ,,
Lemma C.3 (Upper bound of v), For x X. E [m]] n E R4 and T > 0, we define V Mr(x, n) as follows:
(I = 1[( x) + broo 7| S n).
with probability at least 09/10
Σ U, K/m3/) - O(K m9/10).
Proof. We decompose f into three functions A(x). B(x), C(x) in Definition C.4. Then the proof comes from Lemma C.5, Lemma C.6 and Lemma C.7.
C.4 DEFINITIONS OF HELP FUNCTIONS
We split the fz) into the following three sub subffunctions for future analysis purpose.
Definition C.4. The following is how A(x), B(x), C(z) are defined:
A(r) = o Aur 2)
m
B(x)= Σ (,o((Wr,,,0)) br.0)(
m
C(x) Σ ar.o 0r.0((wr,,,,)) (r,
(1))
We will acquire the upper bound of [A(x) g(x)), (B() and (C(x)) to upper bound [g(x) - f(x),,
because fz) the summation of A(x), (xx) and C(z).
Recall that our definitions of ! and 2 are based on shifted ReLU activation with a threshold set T, which is different from Zhang et al. (2020).
$ 1k xr) br.0 2
$ a.r 1/(Wr,0 + Aw,, by r].
20

---

Published as a conference paper at ICLR 2024
C.5 UPPER BOUND OF [A(x) g(x)]
First, we want to obtain the upper bound of IA(x) - g(=)|- We obtain a different upper bound based on the shifted ReLU activation compared with Zhang al. (2020) because definitions of $ and Pa. are different due to the shifted ReLU activation.
Claim C.5 (A variation of Claim A.5 in Zhang et al. (2020)). We have that
Pr(lg(>) A(x) 2 O(K² m 1//00 I 08/10
Proof. We can easily have that
AA(x) - 9(x)(( =
Σ
ar ( - -41.)) 2)
r=1
m
2
|arl Pr 1 ((Aus,
K
Fr
m
where the 1st equality due the Def. of A(x) and g(x), the 2nd inequality is because 10ar K
P a.r S F, and the definition of F,, and the last step is because |,, I ma/o ar f mi/o }.
1
By Claim C.2, we can have that:
Pr[l(()) A(x) 2 O(K2 m 1/100] s 1/ (xxx)(((((/110) = 09/10-
The proof is complete now.
C.6 UPPER BOUND [Bx)]
Then we want to upper bound Bxx). We obtain a different upper bound O(1/m3/19) and different failure probability 01/5 = 11/exp(S (xmmm((m))))) based on the shifted ReL.U activation whose threshold is compared to Zhang et al. (2020).
Claim C.6 (A variation of Claim A.6 in Zhang et al. (2020)). With probability at most 0155. it gives
B(x) 2 O(m 01110)
Proof. Note that
m
B(x) Σ
ag , ((wr,0s x) + br,).
With or = 1[x > T/E, we can have
m
(Ww 2) + br.o) < > (ww 2) + by.0)
(10)
We can obtain that with probability I S0,
m
Σ ((wn,, 2)) br.0)
Σ (wwr,0 x)) br
=0(1)
21

---

Published as a conference paper at ICLR 2024
where the first step is because of Eq. (10), and the second step is because the random variable (Wr,0. 2) + by,0 is sampled from (0, 2/m) independently where r [m]]
Now, because or,00, ((wr.o, æ) + 6,,0) for [m]] are independence and are Chi-Square random
variables(Sce Definition 3.5.), by using Hoeffding's concentration inequality from Lemma A.6, for some large constant O,
Pril Σ
0r,00, (1Ur,, 0,,00r((Ur,0.
2) + br,00l 2
c
bo. Wul
m\/10
1/55
< exp( -
m2275 r=1 07 (W x) + br,0) )),
By utilizing the bound above, with probability at most 1/ 1/x)((((m))))), have
[(x) 2 O0m-1/10
The proof is complete.
C.7
UPPER BOUND OF [C(x)]
Finally, we want to obtain a new upper bound [C(x) based on shifted ReLU in the following Claim C.7. Because definition of C(x) is different from Zhang al. (2020), we obtain a different upper bound O(K² O(K2/m3//p 3/10 and failure probability exp(-S((m*/6) compared with Zhang al. (2020).
Claim C.7 (A variation of Claim A.7 in Zhang et al. (2020)). With a, and probability at most (xp(-S(m9910)) we have
[C(x) 2 O(K2. (0KK.mm11// m-110)..
Proof.
IC(x)]
Σ an.0 (#a,
) x) + br,
an.ol d 2z,r
(0011( x) + b
s 100 + b..ol
1/5
1/5
where the first step is because of the definition of C(x), the second step is due to triangle inequality, and the third step due to jar.ol m775-
We have that
(0)
Per S Fr z,r
I vv, K. m 33/3..
(II)
And then recall that
(x, K. m m3/5) #0 - ((rro, + broa S K m 3355
(12)
which implies that
(Wr.u, x)) + by.ol [0 $ Pzrl
< (wr,n, br.ol Vr(ar, K -3/5
22

---

Published as a conference paper at ICLR 2024
K
(,
K
m 3//)
m3/5
where the first step becasue of Eq. (11), the final step is due to Eq. (12).
Now we can have,
K
IC(x)) -
Σ
V,(x, K. m 3/6).
rE[m]
As we' 'v already demonstrated, with Pr]] at most 09/10-
m
Σ
v (x, K. m -/3) 2 O(K m m/11))
Therefore, with Pr[ at most 09/10-
IC(x) 2 O(K² m m -
The proof is complete now.
C.8 UPPER BOUND OF (5(z) - g(x:)
With Claim C.S, Claim C.6 and Claim C.7 in hand, We prepared demonstrate that, [f W) g(:; W)] is tiny for every fixed æ E X' with high degree of probability. Recall that our definition of Axx), (xx) and C(x) are different from Zhang et al. (2020) and we obtain different upper bounds in Claim C.5, Claim C.6 and Claim C.7. Consequently, we obtain a different upper bound for [f(x) g(x) compared with Zhang al. (2020).
Lemma C.8 (A variation of Lemma 4 in Zhang et al. (2020)). For each x E X, with probability
S 01/5.
(a W) g(x; W) 2 O(K² m -1/10)
Proof. With Lemma C.5, Lemma C.6 and Lemma C.7 aggregated together and union bound, for Vx E X, with succeed probability
1- 09/10 01/5 1 00/5:
it provides
If W) g(:; W\l < AA(z) - g(xx]] + 1B(x)) [C(x)]
$ <K(? //K2/m2/10) 1/10
(13)
where the first step is due to triangle inequality and f(x) = A(x) ) + B(x) + C(x). and the second step the result of Claim C.5, Claim C.6 and Claim C.7.
This completes the proof.
C.9 PERTURBATION ANALYSIS
We do perturbation analysis for fx) and g(x) with shifted ReLU activation in the following lemma when the perturbation j satisfies that ||/1|/2 Σ and x + E X. We obtain different perturbation upper bound for [[x + (1) - f(x)) with the shifted ReLU activation threshold
0(1/m)
compared with Zhang et al. (2020).
Lemma C.9 (A variation of Lemma A.8 Zhang et al. (2020)). For every x X1, every μ Rd where ||ll| S m and x + μ E X, with O and probability least exp(f(
we have
Ig(x + + W) - g( w < O(K m -1/2).
(14)
and
(s + W; ((x; W) < O(K m1 1/m)/33
(15)
23

---

Published as a conference paper at ICLR 2024
Proof. We define j small perturbation of which depends a(0) R Wo Ruxd by R arbitrarily and has properties listed in the statement of Lemma.
If(z + p: k: f(z; W)
Σ ano or ((W,,0 + Aw,, x + uu) + br,u) - o-((wr,0 + Awr, 2) + brul)
lar,ol (Kuwn, + Aw,, p1) T)
Cooollwrr + Awr + Σ ln,olT
| + Aw, 2|2 + Tm 2/5
m
1+15
m
1
m
1
|
Aw ll2 + O
m 6/5
6/5
m 118
K
|w0,ol12
+
0
6/5
1/5
m
K
0
m
where the first step is due to the definition of fax; W). the second step follows is due to triangle inequality, the third step follows ||사||2 S 1. the fourth step comes from |a,,ol m775. the fifth step is due to triangle inequality, and the sixth inequality is due to Σre(m) ||Aw, S K m/5 and the final step follows that for any r [m]. with probability < 1/ exp((((m2)))))mp)ee)p) (mm2md)) /d)), we have |olB 2 O(1).
By concentration (See Lemma A.6.) of the sum of set of x² random variables which are independent and with union bound over E [m]] and m 2 d,
Pr(O(1) < |Woll,,0o] s 01.
(16)
And then we take into account.
1g(x + μи W) g(x; W
[Wrro, + ni bno 2 r),,o(Aw,, x +)
Σ [( bno 2 r)a,o((w,,
Aurll2
1[ x + 14) + br,0 2 r| -1((rr,, + br,0 2 T|| lay,ol (Aw,,
K
m
1(( x bn 2 7| - 1[ x) + br.0 2 r/|
where the first step is due to the definition of 9(;; W), the second step follows from triangle inequality, and the third step is because that Σm- ||Aw, _ K 1/5 and la,,ol .,.
About the last sum, from Eq. (16), we have ||ooll,,0 I 0(1). And the we can attain that
m
Σ
1ewoo. n) bno 7] I[w,,o:>) 2) + br.0 2 T] S Σ (x,
By Claim A. with probability at most O ,,, ) we can get (z, 0(m 1. With fixed, (I, Omm-1) where E [m]] can be seen independent Bernoulli random variables. Therefore,
24

---

Published as a conference paper at ICLR 2024
by Chernoff bound (See Lemma A.8), with probability at least 1/ (1pmm)))//)) have
(z (mm=)) - Omm!/3).
The proof of Eq. (14) is finished now.
1. CONVERGENCE ANALYSIS
We first define the || 1|2,1 and 12,,c norms in the following definition.
Definition C.10. Let W E Rdxo and w, Rd denote the r-th column the matrix W. We define
[Wll2,1 = Em ||0,112
|W == max+e[m] ||w,]12
We define the gradient of real net gradient and pseudo-net gradient follows:
Definition C.11. The two notions of gradients are represented as convenient notations in the following:
Gradient of pseudo-net (g) V g(()) Rdxm
Gradient of real net (J)= = (orL(si E Rdxm
In the following theorem analyze the convergence of our neural network fw with shifted ReLU and choose a different parameter:
m 2 (2(max((n' 300/31
900/331
(Kn/e)24/15 (K3//e)30
7/ / 0(m-1/6,
compared with Zhang et al. (2020).
Theorem C.12 (A variation of Theorem 4.1 Zhang et al. (2020)). all K O, and E (0, 1), for every which is larger than some poly(n, K, 1/e). We set
= ==(cm 1/5 and = (cc
Running Algorithm for every W Rddxm with IWo (Wa) E mdxm such that
W* 12,00 S m376. there will be weights
C.. (fw.) + T Σ Ca(ww)
The succeed probability - 01/5- The randomness is coming from initialized states (See Defini- tion 3.1).
Proof. As for and y,, we will give them value in the proof later. We define various distances as follows
D max = max
W, Woll2,00
(17)
(E[T]
and
Dw- = I Woll2,co
(18)
where Dw- O( O(KKK)))) m,
By Lemma C.14, with high probability Dmax and Dw- will be coupled, if W, remains near initiation (D Duax < m 15/24..
(7 ((lll) Onmm2/500
25

---

Published as a conference paper at ICLR 2024
Remark C.13. We assume max I m 11122 first. Finally, we will set 17, T and the appropriate values to ensure that it occurs.
We can bound the size of gradient for all r E [m]]
n or ((((,,, mi) + br,0) -17al12)) |arl
(frll) S
(19)
m/55
where the first step is because the loss is I-Lipschitz, and the second step is due to aa = 1/m
and ((wr,, 2i) + b,,o) || I O(1).
The C(S. (g(W)) is convex function with respect to W E d because is linear with respect to W E Rdxm.
We express the inner product of two two identically sized matrices B and C' as
= := cj
And then we have:
g(5))) ((()) - C(S ((W'))
)(W"))
<()()()) ((0))))))(()),))) W, W + (f)
$ () - (01l2, |[,
1V + (V, W. W*)
(20)
where the first step due to triangle inequality, and the second step because the inner product and the definition of || 112.1 and || 112.00
For simplicity, we define att) E R and B(t) E E follows:
a(1) = (V) W. W*)
B(t) (g) (f)l2) W|, - W 12..
Therefore, we have:
L(S ((()) - c(S"),(W"))
,(W")) S +(1)+ 8()
(t) and ((t) terms will be dealt with separately.
As for (t),, we can have:
[ W0 |[, (
| - W' + 2nja(t)
where the first step us due to Wi+1 = W. ())) and the second step because of rearranging the terms.
And then by reorganizing the terms, we can have
at) - " 2
+
1
(IIW, - wr1 | -
2n
By summing over t, we have
T
T
1
Σ
Ca(1)
+
(IIW, W | W
2
2n
1=1
E-
mm
1/5
m Dip.
(21)
2n
26

---

Published as a conference paper at ICLR 2024
where the first inequality is due to the upper bound of a(t), and the second inequality is because
|| Wolls - m mm- Woll2, = mD and ( m
|
S m 1/5
For the s())ss
p(t) - W. 12, (7/32
(Dw- Dmax) Onmm27/50
(22)
where the 1st inequality is because Lemma C.14, and the 2nd inequality is due to triangle inequality and the definition of Dax and Dw- in Eq. (17) and Eq. (18).
Additionally, may get the bound of Daxx 's size using the bound of gradients.
Dmax
max
W
Well2,00
EE(T]
| (f)rl2
rE(m)
t=1
nT
m/5
where the first equality is due the value of D max- the second inequality replies accumulating T iterations, and the final inequality due to Eq. (19).
Combining it with the preexisting condition Dw O( K we arrive to the following:
m
CSS ((W))
Σ
((S(),(())))
Σ (tt) + Σ 3(t)
K²
nKTn
$ {m)) 15 nT +
m m²
+
nI
nm
31/150
m 29/150
where the first step is due to Eq. (20), and the second step due to the upper bound in Eq. (21) and Eq. (22).
Then.
Σ Σ ,(W.))
+ Σ C(S ((W")) < O(e).
1
T
SE[T]
SE(T]
The following values were chosen for the hyper-parameterss 7), m, and T:
" = /f +0m 00mm-//6))
fmmax 2000331
( (K02))300/29))
T k()
where m is required to satisfy 7/ nm 31/150 + TKTn 25/
< O(e,, Diax S m 115/24 and to fulfill the
prerequisite for using the Theorem C.1, we have for all E [T] that
sup Ig(x; W.) - fx: W.) < O(e) *EX
27

---

Published as a conference paper at ICLR 2024
Therefore, have
T Σ C(S fw.)
1 T
Σ T t=1
f(.) S c.
T
where e R4 is large constant. With C(5(), fw:) La(Jw, and ((S fw-) ((W)) S if we replace with e. the proof will hold for all e >> O. We finish the proof now.
LA (fw-).
C.11 GRADIENT COUPLING
In this section, we show that (g) (f)l,, (II 1l2.1 is from Definition C.10) can be upper bounded with high probability for all iterations t. Due to the new shifted ReLU activation with threshold the new upper bound is (mm227/50) which is different from Zhang et al. (2020).
Lemma C.14 (A variation of Lemma A.10 in Zhang et al. (2020)). For every t E [T] let [[, Woll2, S 0(m-15/22)
Then
(r(l (fIla) S (nmm7/500) 2 01/5-
Proof. For every t [T], by Claim C.16 and Dmax = 1| Woll2,00 we have,
Pr
1 1
( Ommm 21-1 1 01/5.
(23)
For r E [m] where v # (1))
n
V (2)
2
|a,1 Σ
|| 1 ((,,,, ;.) + br,0 r] - 1[ + +6.0 2 r]
1
1( 3z) + bb,0 2 r] 1( + br,0 2 7]
m 1/5
(24)
m/5
where the first step is because that the loss is 1-Lipschitz, and the second step because that 1/5 and the third step is because that 1( + b,.0 2 -| 1 [wroo 22) +
a, E 1/5:
1
br,o 2 +] 11
Thus, we conclude
m
= (f(
Σ | vi0
(nm
m/5
O 27/50
where the first step due to the definition of ||- Il,.1. the second step is due to Eq. (23) and Eq. (24), and the final step is the result of merging the terms.
1. UPPER BOUND OF NUMBER OF ACTIVATED NEURONS AT INITIALIZATION
We prove the upper bound of number of activated neurons with shifted ReLU activation whose threshold 7 at initialization. We will use the below lemma to compute the time cost per training iteration.
28

---

Published as a conference paper at ICLR 2024
Lemma C.15 (Restatement of Lemma 4.5, Number of activated neurons during initialization). Let (m.*). For every n R+,
eQ E (0, 1) denote a fixed constant. Let Qo 2m exp(-( K²
(m (it)))))
X and r E [m]. v (z. 17) defined as follows:
V V 17) = (ur,,, by,ol 2 77).
with succeed probability 2 1 n/ exp(S((m expl- (mm1/)))
Σ rmmm
(z (/m2///m//5) I Qu.
Proof. Fix x,(w,,,, .t + b,,o No, ) due to the reason that bo and Wo are random variables from (0, 1 independently. By Gaussian tail bounds and replacing (w,,o, æ)) b,,0 with 2, the
probability that each initial neuron is activated is
Pr((wr,,, 2) br.u K m nn-3/11=
Pr N0 1
2 K
-3/6
K²
S exp( (-(
4m
By using 1 we have
K²
11 S exp(-
4/5 ))
By Bernstein inequality from Lemma A.9, with > 0
t2/2
Pr[Qr, + exp(
Vt >> 0
1) 1 1/3
where 7) exp(- K2 47 (xmp1((mm173)) ))-
By choosing t = 1), we can have:
Pr[Qr,o > 2n] S exp(-3n/8)
By applying union bound across E [n]. we can attain that for each n; X with at least probability
K2
1 1 n 1/ exp(9(mm exp(- the upper bound of Qi, (See definition 3.9.) is 2m exp(- 4m
4m-/5 })),
R²
C.13 UPPER BOUND OF THE SIZE OF ACTIVATED NEURON SET
We have obtained the upper bound of the size of activated neuron set at initialization. In this section, we want upper bound the size of neuron set which has different signs compared to the neuron weights at initialization under shifted ReLU activation sign, we need to take the activation threshold r into account compared with Zhang al. (2020).
training iteration. When computing the
Claim C.16 (A variation of Claim A.11 in Zhang et al. (2020)). For any | S m m112/21 and any subset {æ, 3 C X. Then we have
Σ 1[ E [n], sgn((ar, W0,0 Wro0 + Awr) + by.0 - 7) o sgn((1;, wr.o) + br - -]] < (/m
and
Vi E [m], 1[3 E [n], sga(( wro + Awr) + br.0 - T) + sgn((a; wr.)) + bro - 7)] < O(am 01mm11/8) 1/88)
The succeed probability is 01/5-
The randomness is from initialized states (See Definition 3.
29

---

Published as a conference paper at ICLR 2024
Proof. We first give proof of Claim C.16 with points in the set fixed. At last get the final result by using a union bound across all the sets.
With ( Fn } S X' where i's are fixed, we have the following definition:
C = D E [n], sgu((wr: mz) by,0 + sgg((wrroo. xx:) + b,,0 -)]
Now will focus on bounding the size of E C,. By Claim A.I0, for x; X we have that
Pr(l(urr,a, + br.0 7| m 15/224] < (.) + bnoo S 15/224
< 0 1/8
By a union bound across E [n], we have
Pr|Bi E [n] s.t. [Wr,o, xz) + b - -rl S m -15/24
1 00 n
m/
such that
Pr(C, 1] Pr(Fi E [n] s.t. (wro, + b,,0 2 15/24
< <0 m 1/8
With v; X's fixed, C,'s will be m Bernoulli random variables which are independent where r E [m]] Therefore, by Chernoff bound from Lemma A.8,
Pr Σ C, 2m s /1/expp//// exp((((m 7/8 rE(m
We will only amplify by just exp(O(nd log m)) on the failure probability with big enough m when over product space X", we assume union bound over -nnet.
Remark C.17. In each training iteration we only use Qo + (mm 7/8) activated neurons to do the computatiion to save training cost. We will use the second upper bound compute the time eventually. Qo is the activated neuron set size during initialization.
C.14 PROOF OF PSEUDO-NETWORK APPROXIMATION
We will first demonstrate how individual components of f" may be approximated by pseudo-networks and combine them create sizable pseudo-network by which f" is approximated.
Lemma C.18 (A variation of Lemma A.16 in Zhang al. (2020)). Let q R R univariate (q, For every r E [k], polynomial, i E [n],, ei be a large constant, ea E (0, ट(q) and k 2 ci cg with independent random variables Wr.n. br,0 and a,,0, where Wr.0
d-dimentional standard
Gaussian random variable, br,u standard normal variable and 0,,0 -{- 1 /-m//5, m²ys uniformly at random. With T = O(k 11/2) and probability at least 1 - 1/ exp() there will be (1 Rd such that
Vx X,
Σ
(Aw, 1(10,,002) br 2 7| nd((,,, 5 3eg
and
C(g,cs)
Aw
12,00
22,00 S 0
20
m 1/5)
k
30

---

Published as a conference paper at ICLR 2024
Proof. Notice that (w,, + b, (0, 2), and then by claim A.10, we can have Pr(1[[w,)) + 7]] = O And then there will a function defined as I2 + [-C(q, (s) C(g 6x) which satisfies
that:
b- [1, 2) + < T] M( w) b)] _ ((()) ea)
(25)
We use Lemma B.3 by setting ((=) (z and Note that |ux| 0()),, db will have an equal complexity q, with some constant. Therefore, we have a function h R2 C(y, eg) Cla eg)l t. for every in set X'
b N.. (o. [ w). b) [w, x) + 2 r] n. (x3, at)| x))
-
(0 [ w), 6) 1[( σ) + 2 0]] - ( x))
E
(M (w, + < +1
$ E3 + (()))(
I 63 + 0 C(q,
(26)
k1/2
where the first step is due to triangle inequality, and the second step is because of Lemma B.3 and (25), the last step comes from r = Okk-1/2).
With an X fixed and by Hoeffding's inequality (Lemma A.6), with probability at least 1 1/ exp(S1( ( )), we have
[w,,o, 2) + bn,o 2 1;),
E (o
[ww + bbb 2 7] h((w, bi]
Sea
(27)
Let
(1) = 0r,o k
22( 2h((W b,,0)
where é is a vector whose only the last element is 1 and otherwise is O, we can obtain the following upper bound:
A 2,m0 00( 50(( m 2/5)
Clg,
k
For every E X, because za 1/2, with probability at most exp(-S2( (3(g,e)
kc )), we have
1(Wwro, x) + bro 2 (Aw,
E b-N10.1) [h((2i, b) I[ x) + bb 7]] 2 E3
(28)
With X2 as a maximal &e
1 net of and c R. as a large enough constant, we all understand that |& < (id)) With union bound over Xi for Eq. (28) and significant constant, we have that for aa (4),))))
&
Pr Σ
1 [ww,,, 2) + bn.0 2 (J
31

---

Published as a conference paper at ICLR 2024
E
[h((w,,))) Ri), [[ + b 2 7]]
> 63. Vo E e
b=.110.1,...00....
kt
$ (1/exp(12)
exp(O(c
(g E3
ke
= =1/cXp(S( C (g. c3)
(29)
where the first step is due to (2), the second step is because of adding terms, and the last step demonstrate that for each E Xi, with high probability, if is adjusted by more than go in Ez. the LHS of Eq. (28) only slightly changes.
After showing that given E X is stable, union bound will be performed.
Indeed, with a large enough c and combining Eq. (26), (29) and Claim C.19, with probability at least 1 1/ exp((((22/21 1/ exp(II (c(0,0))
ke
)) we attain that
Yo E X,1 Σ (AwoaAwr,, a) (( x) 1r,0 2 yol((,, x))1 0k-11/2 C((,, + 263
since k 42 ci 2 63) for large constant the proof is complete.
C.15
STABILITY OF S₁ AND S2
In this section, we'll talk about the stability of S1 and S2 based on the shifted ReLU activation with a threshold set т. When bound S1 and S2, need to bound the sum of independent Bernoulli random variables [[,,,, x) + 6,,0 - T| S Vel which is different from Zhang et al. (2020).
Claim C.19 (A variation of Claim A.17 in Zhang al. (2020)). For T >> and every X,, ler be large enough and μ. E B. such that || S &-- and x + fa X With independent random variables wro by,0 and Gr,0, where wr.0 is d-dimentional standard Gaussian random variable, by,0 a standard normal variable, and probability 2 1 - 1/ )x)(()(2223)) we have
& Σ r=1
S
0 (Aw, (1), p) 1((,,,,0 + u) + b,.0 2 r]
Σ
a,,o( (1), x)) I[( x) + bro 2 r=1
< 0(k 1/2 C(g, ta))
and
S2 bo
[h((1, 1w, + n) b2222 +]]]
w001 h((w,x,)),
1[ x) b 2 -]]
Proof. The upper bound of D2 will be given first. Note that AW rf 0 for j < d- - based on how we generated (W And (1w,(i) pu) = 0 when dy = 0.
With conditions as follows:
and (AW0022 0 Clg. Clg..a)m ao.ol 11/5
k
will have
Clg. E3)
k
Si < 0
Σ
1k x + +1) + bbo T
-1(00r, x) + bno 27
h:
32

---

Published as a conference paper at ICLR 2024
$ 0 C(q. E3)
1 [sgn(( + +1) + 6r.0 - -7) + sgu( (wn0 x) + 6v.0 - T)
k
r=1
Clg. C3) O k
(1[[(u,,0 + 6r,0 7| k- 1/3]+ +[]lwr,olle 02 12).))
where the first step due to [h(+)) I C(g. C3), the second step the result of the value of 11(
b,,0 2 7] is determined by the number of differences between the sign u)) + 0n.0 2 -] 1 [( o. 2)
of (wy,0 +1) +r, and (w,,0. x² + +,,00 and the third step follows that only when (wr,0, x+++) +b,0 and (wr,0. . - 6r,0 have different sign. 1[( v + p)) + br,0) o
x) + b..0]] .)] is which is decided by wr,0 and where || S F (0,, La) and |||2,,,|l2 > c2k 2 0.
can choose a large enough constant 02 if sufficiently large constant is chosen.
And then we demonstrate that with probability at least 1 - 1/ exp(S(k))) for every r E [k), llu,,oll & (()2/2).
By the concentration property sum set of independent Chi-Square random variables from Lemma B.2 and Lemma A.7, for alllll E [k]. with probability < 1/ (xpp(S(22/aala (A)//)))) we have ||W,,ol1ž >
O(k). By applying union bound over all r e [k] we can complete the proof with 2
Therefore, by selecting C correctly, can obtain the following bound:
S O0k Clg. E3))
1 IKw,,, 2) + b,,0 -|
(30)
The succeed probability is 2 / cxp(s)()))
Now, (1r,o,,, + by,0 - T| k 1/2| can be seen as k independent Bernoulli random variables.
We have
Pr|l(Wr,,, + by.0 - 7| S k 1-12 $ Pr[l(w,,, x) + b,,ol S k --121
< Okk 1/2).
where the first step is due to Theorem A.3, the second step is due to Claim A.10.
The corresponding probability of 1[K(,,,; + b,,0 7| < k 1-11-////- 1/] = 1 is bounded by O(k OKk-)/3).
Therefore, by Chernoff bounds (Lemma A.8) with probability at least 1 1/ 2x)() we have
(er,o x) + br.0 -
O(K1/2).
(31)
With a union bound over two bounds in Eq. (30) and Eq. (31). One can obtain the following bound for S1:
S < 0(k-1/2 1/2 C(g, 6)))
The succeed probability of above equation is
- (x/pee((((())) - 1/(xp((((k)) = - 1/xx(((((())
And now we will focus on getting the bound of Sz. We have
S2 S C(g. 63)
E
[1 [ + ()) + +b 7| - 1( (1,, +b> 7]]
33

---

Published as a conference paper at ICLR 2024
S Clg. 63)
E (.11 (1, + s - +1k //
where the first step is because 1h(-) - C(g, Cz), and the second step is because [[ x μ1) +
[]_ x) 2 r] is decided by the sign of [(w, x+ト)++ 2 7] and [[ x) +b 2 7]. The above
difference decided by the value of || I E= and w ~ (O, Ia). and 1 [k/1/2 c2 < || 2 0. The constant 0g is the same previously.
Still,
Pr (11
[k: 1/22 2 ((v, x) +b--l] s
Pr w-N
Ak: 1/22 2 (ww + bl]
S O(k 1/22)
where the first step is due to Theorem A.3, the second step is due to Lemma A.10. Then we have
Pr N00
[,2/2. 62 < [|w112] expe(((())).
Therefore,
S2 S C(q, es))
This completes the proof.
C.16 PROOF OF TIME COMPLEXITY PER TRAINING ITERATION
We give the proof of Lemma 5.3 in this section.
Proof. The complexity for Algorithm each iteration can be decomposed as follows:
Querying the active neuron set for adversarial training data points 2, takes Õ(m (m(1)()/))) time: > (query(21))) d, ks,e) (-1/4)) according to Corol- lary 5.2.
Forward computation takes O(d (Qo + 7/8) time: Σ Old k.s) = (Qo + nm///)) according to Lemma 4.5 and Claim 4.6.
Backward computation involving computing gradient AW and updating W takes O(d (Qo nm/ time: O(d anz(P)) O(d (Qu nm?/8)) according to Lemma 4.5 and Claim 4.6.
Updating the weight vectors takes O((Qo + nm7 log (ogg(2mm) time.
Tupdate
(1Qr,al + (Q1+1,s))
O (2m)) Σ ki, k1,41)
O(log² (2m)) (Qo + (nm
O((Q0 -um 7/8) (ogg((mm)
where the first step is according to Corollary 5.2, the second step is the result of Lemma 4.5 and Claim 4.6, and the third step is the result of aggregating the terms.
Summing over all the quantities in four bullets gives the per iteration cost (e(44m(
34


Reviews:
[{"review_id": "eQXU9WAf6G", "reviewer": "Reviewer_yRgF", "summary": "The paper tries to address the computational complexity of adversarial training in neural networks, which is an active research area.\nThe work addresses training efficiency by trading off extra memory for computation and incorporating an additional half-space data structure, efficiently identifying only the active neurons for computation. The key insight is that not all neurons are active for every input data point, enabling the computation of the dot product exclusively with the active neurons. While the method of initially identifying active neurons is not novel, the application of efficient geometric data structures is both new and promising. The research introduces an algorithm designed for this purpose; although it does not include experimental results, it does offer convergence proofs for two-layer networks.", "questions": "To translate the theoretical advantages into practical scenarios, the paper should present at least some toy experiments.\n\nIt is important to explore how reducing training time affects the model's robustness performance, as the trade-off between efficiency and robustness is crucial for practical use cases.\n\nThe same consideration should be given to the trade-off between memory usage and efficiency. It would be beneficial for the paper to comment on memory requirements. While the impact on only a two-layer network might be minor, understanding this trade-off is essential, and could be tested using neural networks with extremely high widths in practical scenarios.\n\nIn short, a toy experiment featuring a two-layer network that showcases practical, minimal use cases by comparing memory usage, computational efficiency, and robustness performance would be a valuable addition to the work.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The approach is novel where adversarial training that leverages geometric data structures at the expense of extra space. It extends the direction of first identifying the active neurons and then only taking dot product with those neurons. \n\nThe paper is well written and however, without empirical results or illustrative examples, the clarity of the paper's practical implications could be enhanced.  \n\nThe work is significant as it has a potential to further improve the direction of efficient adversarial training of robust neural networks.\n\nI have not conducted an exhaustive review of the convergence proofs; however, upon initial examination, they appear to be correct.", "weaknesses": "The study lacks experiments, even on toy datasets, to determine whether its findings are applicable in practical scenarios.\n\nFurthermore, it has not been compared with existing works. Although it is primarily theoretical, clarity on how it measures up against established methods is missing.\n\nThe paper does not discuss how reducing training time might impact the robustness performance of the model. This trade-off between efficiency and robustness is crucial for practical use cases.\n\nLikewise, the trade-off between memory usage and efficiency warrants discussion. While the paper could comment on memory requirements, it may be that for only two-layer networks, the difference is minimal. However, it would still be beneficial to understand this aspect, perhaps by employing very wide neural networks to confirm it in a practical scenario.\n\nIt is also unclear whether the proposed methods can be effectively translated into actual GPU computations. If the approach results in underutilized GPUs, it might still be valuable but may not reduce the overall wall time. Some commentary on this feasibility would be constructive.", "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": "", "extra_scores": {}}, {"review_id": "gaHxjw1ok4", "reviewer": "Reviewer_Wuuy", "summary": "The authors propose an adversarial training algorithm designed for two-layer ReLU networks. Combining multiple techniques, they manage to prove that their algorithm runs in time sublinear in the size of the network.", "questions": "- Is there any assumption on the adversarial example oracle A in Algorithm 1? I don't seem be able to find any reference to its complexity analysis in the main paper. Usually adversarial examples are found by iterative projected gradient descent (on the input x) and their runtime should also be taken into account. \n\n- If we take away the adversarial example generation in Algorithm 1 and just use the input x_i as training example, we should then obtain a sublinear training algorithm for a two-layer ReLU network. I am wondering why the authors are focusing on adversarial training, or if there are any parts of the algorithm that are specific to the problem of adversarial examples. The 3 techniques listed in Section 2 are not specific to adversarial training.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The authors propose an interesting algorithm and manage to show that per iteration cost is sublinear in the size of the network for a two-layer ReLU network. The paper is very clearly written with detailed proofs in the appendix.  \n\n- The use of the techniques such as half-space reporting data structures and shifted ReLU in the design of the algorithm are interesting and instructive.", "weaknesses": "- The current result seems to be more of a theoretical interest than a practical algorithm. The limitation of two-layer network, well-separation for adversarial loss are both severe limitations in practice. \n\n- There are also some unclear or missing details that need to be addressed in the Questions section below.", "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": "", "extra_scores": {}}, {"review_id": "thC8xtsDhA", "reviewer": "Reviewer_RwpB", "summary": "The paper proposes an adversarial training algorithm for 2-layer neural networks with ReLU activation that has sublinear o(mnd) per-iteration time complexity, compared to standard Ω(mnd). The result mainly relies on the insight that only o(m) neurons will be activated for each input data per iteration.", "questions": "Could authors provide some discussions on and thoughts on if the activation sparsity could generalize to deeper nets?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents some interesting result on analyzing per-iteration complexity of adversarial training of a special setting of 2-layer neural networks. Theoretical analyses are solid and insightful.\n2. Complexity of adversarial training is less analyzed compared with standard training, the work would be interesting to some researchers.", "weaknesses": "1. Just like in many other works on 2 layer neural nets, it is unclear if the insight can generalize to the more common setting of deeper neural nets.\n2. It seems only optimal adversaries are analyzed (e.g., in theorem 4.4), but most cases it is impractical to have an optimal adversary.", "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": "", "extra_scores": {}}, {"review_id": "2uzSC29lw2", "reviewer": "Reviewer_5dfS", "summary": "The authors consider fully connected one hidden layer neural networks with shifted ReLU activations and develop an adversarial training algorithm with cost $o(mnd)$ per iteration by applying half-space reporting data structure. To do that, the authors rely on three main techniques:\n1. approximation via pseudo-network sufficiently precise with high probability\n2. using shifted ReLU functions instead of standard ones to attain $o(mnd)$ time complexity per training iteration\n3. use a tree data structure to find the neurons that need updating more quickly (Half-space reporting)\n\nThe algorithm consists of a loop that first calculates the adversarial training set and the indices of the activated neurons for each element of the training set, then doing a gradient update for all active neurons. A series of theorems and lemmata are presented, analyzing the proposed algorithm, which is followed by a time complexity analysis. The reviewer did not check the proofs in the appendix.", "questions": "- Are the contributions of the paper mainly of theoretical or also practical interest? Can the algorithm be efficiently parallelized? Are efficient vectorized/GPU implementations possible? What are the memory requirements of the algorithm? \n- Page 3: what is the definition for an $\\epsilon$-net?\n- What about deeper networks? On an intuitive level, the reviewer does not see a reason that the complexity should worsen there.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- Adversarial training algorithms and their analysis is an important problem in the field of adversarial robustness. \n- The assumptions seem reasonable.", "weaknesses": "- The relevance of the paper remains unclear. Is it theoretically relevant or also practically?\n- The restriction to 1 hidden layer networks is strong. \n- The Paper is hard to read, the reasoning jumps back and forth. The reviewer recommends a thorough rewrite. It would be good if the authors first introduce concepts and then use them. An example is the \"query, insert, remove\" from the data structure in Algorithm 1 (Page 6) that gets introduced in Section 5 (Page 8). Similarly, Theorem 1.1 (Page 2) has a reference to Equation 2 (Page 4). The paper seems to be rushed, also reads that way. \n\nTypos:\n\t- 3.1 the typesetting of $\\ell_p$ \n\t- The inequality in Theorem 4.1 seems to be the wrong way round. \n\t- In theorem 4.3: \"$T = \\Theta(\\epsilon^{-2} K^2)$. in Algorithm\"", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)