Optimization and Adaptive Generalization of Three layer Neural Networks
Authors: Khashayar Gatmiry
Stefanie Jegelka
Jonathan Kelner
Venue: ICLR 2022 Poster (2022)
Keywords: deep learning theory
adaptive kernel
robust deep learning
neural tangent kernel
adaptive generalization
non-convex optimization

Abstract: While there has been substantial recent work studying  generalization of neural networks, 
the ability of deep nets in automating the process of feature extraction still evades a thorough mathematical understanding.  
As a step toward this goal, we analyze learning and generalization of a three-layer neural network with ReLU activations in a regime that goes beyond the linear approximation of the network, and is hence not captured by the common Neural Tangent Kernel. We show that despite nonconvexity of the empirical loss, a variant of SGD converges in polynomially many iterations to a good solution that generalizes. In particular, our generalization bounds are adaptive: they automatically optimize over a family of kernels that includes the Neural Tangent Kernel, to provide the tightest bound.  

Published as a conference paper at ICLR 2022
ADAPTIVE GENERALIZATION AND OPTIMIZATION OF THREE-LAYER NEURAL NETWORKS
Khashayar Gatmiry MIT
Stefanie Jegelka MIT
Jonathan Kelner MIT
ga tatiis ry@mi edu
f t.
ke 1 neln @errrmi edu
ABSTRACT
While there has been substantial recent work studying generalization of neural networks, the ability of deep networks in automating the process of feature extrac- tion still evades thorough mathematical understanding. As a step toward this goal, we analyze learning and generalization of three-layer neural network with ReLU activations in a regime that goes beyond the linear approximation of the network and is hence not captured by the common Neural Tangent Kernel. We show that despite nonconvexity of the empirical loss, a variant of SGD converges in polynomially many iterations our generalization bounds are adaptive: they automatically optimize over a family of kernels that includes the Neural Tangent Kernel to provide the tightest bound.
good solution that generalizes. In particular,
INTRODUCTION
The ability of overparameterized neural networks trained by (stochastic) gradient descent gener- alize well on test data (Krizhevsky et all, 2012: Silver all 2016; Hinton et all, 2012), even if they perfectly fit the the training data, has intrigued theoretical researchers and led to many approaches for generalization bounds (Neyshabur el all 20LY Bartlett et all 2017 Neyshabur et al, 2018; Dzr ugaite Roy, 2017 Wer et all, 2019; Golowich all, 2018 Arora et all 20186; Zhou all, 2018 Konstantinos et all 2). This generalization ability is tied to the optimization procedure, i.e., the trajectory of the training algorithm in a non-convex loss landscape, and the structure of the data.
Hence, several recent works study the training of neural networks. For instance, Satren & Shami (2018) address the role of overparametrization avoiding bad local minima, and Zhang et al, (201)) empirically show that overparametrized networks trained by SGD can even perfectly fit to random labels. Within the popular framework of the Neural Tangent Kernel (NTK) et 203), which uses linear approximation of the network at initialization, several works analyze the optimization trajectory and show global convergence of GS)GD to global optimum of the empirical loss (Allen Zhu et all MUD: L1 & Liang 2018: Zou et all 20T8 Du et all 2018). Extending the viewpoint to generalization, Arora et all (201 exploit the kernel-like behaviour of two-layer networks close their initialization to prove generalization for the final network, showing that two-layer neural networks generalize as well as Kernel Ridgeless Regression (KRLR) with the NTK. Caa Go (2OL) show tighter bound with Neural Tangent Random Feature Model. The kernel approach, however, has two main limitations: First, while KRLR can generalize well in specific high dimensional regimes (Liang et al, 2020), there is theoretical and empirical evidence that can be inconsistent with noise (Rakhlin & Zhai, 2019). Is there an approach for analyzing neural networks that shows they perform at least as well as KRLR, but is also robust to noise?
Second, importantly, neural networks are known to outperform traditional statistical methods in many regimes as they are able to automate the process of feature extraction from data, as opposed to kernel methods that work with a fixed feature representation. This poses the question of other, adaptive, regimes beyond the linear network approximation. In this realm, Wi (2018) show generalization bounds that, instead of the NTK norm, scale with respect to another functional norm. This norm corresponds to the minimum RKHS norm of the function among a family of kernels, ie., their method in sense picks the best kernel in this family. However, this result ignores the computational aspect of the problem. Are there particular nonlinear regimes beyond NTK for which gradient-type polynomial- algorithm, in way, adaptively chooses a suitable kernel?

---

Published as a conference paper at ICLR 2022
Going beyond the NTK view, a line of work convexifies the optimization problem via approxi- mation of SGD dynamics with a continuous time gradient flow in the space of probability measures on the hidden units of the network, equipped with the Wasserstein metric (Mei et all 2018 Chizat & Bachi 2018; Mei et all, 2012 Wei et all 2018: Sirignano & Spiliopoulos 2020 Jayanmard et all 2019; Lu et all 2020). Taking another perspective, Allen-Zhu et all (2018) consider three-layer network model that is not captured by the NTK approximation. and learn an underlying concept class by exploiting saddle-point escape theory for nonconvex SGD (Ge et all 2015a). However, evaluating the complexity measure of AAllen-hhu et all (2018) is rather involved, and only aligns well with functions that are described by particular network. Whether one can recover the NTK bound (e.g. the NTK norm) from these results is not clear. For the NTK setting, in contrast, Aroral et all (A)) develop a purely data dependent generalization bound. Going beyond two layers, is it possible to prove data-dependent complexity measure beyond the NTK regime that recovers the NTK result (Arora al (0119) as a special case?
In this work, we address the above questions:
We consider regime for 3-layer neural networks that is not captured by the NTK approximation and show that, despite nonconvexity. a variant of projected SGD finds good solution, as measured by the regularized empirical loss, importantly, after polynomially many iterations.
We introduce new function norm ||-IIc the minimum RKHS norm with respect to family of kernels IC, which is upper bounded by the NTK norm up to constants. We show that for an arbitrary function J, the generalization gap of the trained network scales by [|]l This makes our generalization bound adaptive, in the sense that it scales with the best kernel in IC, As byproduct, our bounds are comparable with kernel regression bounds simultaneously with all kernels in A.. We hope that our techniques motivate researchers to prove such adaptive generalization bounds for deeper networks, which can potentially result in stronger depth separation.
We show generalization bounds with a new data-dependent complexity measure that generalizes the NTK-based complexity in (Arrora el all, 2019)). Up to logarithmic factors, our bounds are upper bounded by those NTK-based bounds and hence improve over them (if one substitutes their Lipschitz loss with a smooth one)- see Appendix A. for a simple explicit example. Importantly, our bound can also handle noisy distributions as opposed to (Arora et ell 20195).
Further Related work. While the idea of a learning algorithm that combines multiple kernels has been employed for a while in the community (Sonnenburg et all, 2006; Rakotomamonjy et al,, 2007 Duan et all 20112), our understanding of the connections between deep learning and multiple kernel learning is yet in its infancy. Recently, Dou & Liang (2022) define time-varying kernel based on the network weights and show that the limit of the gradient flow converges to a suitable dynamic kernel, in the sense that the residual of the link function onto its RKHS could be in smaller ranked space compared to the orthogonal complement of the RKHS. Ghorbani atal (2UTg) analyze the difference between training a two layer ReLU network and its NTK or random feature simplifications, for mixture of Gaussians input distribution and quadratic target functions. Ignoring the computational hardness imposed by nonconvexity, Bach (2077) prove a dimension dependent generalization bound beyond NTK. In another line of work, Chizat & Bach (2020) study gradient flow on losses with exponential tail and its relation the max margin solution. Wei et all (2011) show interesting separation between the learning power of two layer ReLUU networks and their NTK approximation, by showing a sample complexity gap for an artificially constructed distribution.
With a different approach, Allen-Zhu & (2020) analyze multi-layer networks with quadratic ac- tivations, and prove generalization bounds polynomial in the dimension and precision by assuming an underlying teacher network, which shows a remarkable algorithmic depth separation. The prob- lem of depth separation for neural networks and more generally their expressive power has been investigated by several rescarchers before (Raghu et all 2017: Daniely, 2017: Barron, 1994; Funac hashi, 1989; Safran Shamii, 2016; Satran et all, 2019). The assumption of an underlying teacher network that one seeks to recover is common, too (Li & Yuan, 2017 Zhong et al], 2017:: Brutzkus Globerson, 2017)). Other works focus mainly on the algorithm and use other techniques, such as tensor factorization, to find global optimum (Taan 201G: Baksh ata 2010; Danzamın etll 2015
Zhong et all 20T7)). Finally, many authors study the loss landscape under various assumptions (Free
man & Brumal 2016: Nguyen & Hein, 2017: Soudry & Carmon, 2016 Soltanol kotabi et all, 2018
Ge et all 2012), some of them consider the simplified case of deep linear networks (Arora et Saxe all 2013: Bartlett et all 2018; Kawaguchi, 2016).
201
2

---

Published as a conference paper at ICLR 2022
2 SETUP AND APPROXIMATION BY KERNELS
We analyze 3-layer ReLu neural network from inputs I E R to outputs y E R of the form Vtigaa fve,((x) - a ((V + V'WW" (( + W')x)),
(I)
Vm,
where a E R is a vector of random signs, ( E Rmaxma and W( E Rm are ran- dom weight initializations with iid Gaussian entries ViJte ~O KG), W NO, kÿ), and W Rmaaxm is random sign matrix, which roughly a random projection and change of coor- dinates into lower dimensional space. We refer to W "a/=",aa000 ((W()) W')x) as the first layer and Vm;
1 L vm,
as the second layer. The algorithm trains weight matrices V and W and
W are fixed. We assume that the outputs are a.s. bounded by constant, |aA S. and ||=;/|| 1. As loss .)..,, we use the squared loss. We denote the training (empirical) loss of a function on our data {z, 11 {y:) / and the expected loss with respect to the data distribution (population loss) by
= Th e(S(a.), and R()) R((s(x)))).
respectively. Sometimes, we refer to the vector of labels (w:)==1 1 by y. Finally, H is the space of functions with bounded RKHS-norm of kernel K, and the notation Ô hides log factors.
2.1 KERNEL APPROXIMATIONS DECOMPOSITION AND ADAPTIVITY
Kernel approximations neural networks play an important role in our analysis. First, common approximation is the NTK. The Neural Tangent kernel for 2-layer ReLu network is
H (11, (11, Fg (a (21, (2) 11 for F2(1)
aresin(z))(2T)). (2)
To introduce adaptivity, key part of analysis is to approximate the second layer in the 3-layer network by a product kernel K @ G that decomposes into a "fixed" part K and an "adaptive" part G. To define these kernels, for every E [n]. let (x,) be the output of the first layer of the network at initialization, (00)) (x;) = vm, (Wo(((()))) 1.), and (:0) (x.) + of (xx;) be that output for weights ( + "'"'The adaptive kernel G captures the dot product between the learned weights:
G(r,, = (o' (x+), (((2))).
(3)
This form of G motivates the complexity measure we define in the next section, if one thinks of the entries of d' as bounded NTK- functions of the input. Next, consider the second layer, where the part K arises from roughly stable activations. To formalize this stability, let Sgn(Vx) be the diagonal matrix whose diagonal contains the coordinate-wis signs of the vector Vr. If assume that Sgn( (g)((V(0) + V')((()) (xx) + d' (zx))) x (o(()))) (I:)) prove rigorous statement in Appendix A. then
fw
La LaT(vi) (v(0) + (6(00)
(z:) + 0'(x)))
(4)
Vmg
(v + , Sgn
Sgn (1))s oz))))
t
(5)
Focusing on the adaptive part ('xx) of the first layer, we write
(v V', y a" and can then view the second layer
an Sgn y (())) (z:)) -v(0) T(:))
(6)
function in the RKHS of the product kernel This defines the new kernel R which we simplify into the kernel K that is independent of initialization (K is defined in Equation (E)). To do so,
(T,),, T(x,)) =: k R< (,),,,
we first observe that K concentrates around
( (6)0)) (a:). (()) (xx1) (x;) (111)((0((x)))))))))))0))))))))
Ew ( (2.)]1(u (00) (10)
[ =F2(1100)
3

---

Published as a conference paper at ICLR 2022
Moreover, the Gaussian initialization and assumption ||||| imply that (z,). concentrates around maFasl ( 2z)) for F3 [[-, [0, defined as
Fa( = 2 v x² + f 2n arcsin(x))
1
(7)
SO
K (x, ~ (2Fa my))) =: K Iz),
(8)
For general T1, 22 not necessarily unit norm, we define -' ( 22) K (1//||=11,, D)
It is easy check that the coefficients in the Taylor series of F22 and F3 are nonnegative. Combining this with Schur's Product Theorem implies k is PSD (Appendix A4). We also denote the data kernel matrix on (zz) by ~ and l Like Arora etall (2()19)) we assume the data distribution is (Ao, 6, 12) nt)-non--egeee non-degenerate with respect to Hd and K i..., with probability at least 1 - 6, the smallest eigenvalues of H and 8 are least Ag > 0.
DATA DEPENDENT COMPLEXITY MEASURE AND GENERALIZATION
The emergence of G @ k above gives rise adaptive kernel-like complexity measure that will determine generalization bounds. Intuitively, this complexity measure reflects the two layers. Here, view G as the Gram matrix of some "ideal" first-layer feature functions Ok- We measure the complexity of the prediction function via the RKHS of A = G o K and allow a flexible choice of the features 9k- The gk may be viewed feature representation of ø' in Equation (E): G(I,, 2z) = Σ gk(x;; (z,)) To regularize this choice, we penalize the complexity of the features Ie via the NTK norm. Alternatively, the features Ik are flexible but have bounded NTK norm.
For a labeling f E F= of the data points and fixed G, this leads to the complexity
((",G)- 1r'A-1s" (H 1
A-'A-1 Σ ms k= | A Go
where my is the number of intermediate features. The choice of my is discussed in Appendix A. Our data-dependent complexity measure implicitly selects the G (or equivalently the feature vectors gx) that leads to the tightest bound, trading off data fit and function complexity:
E'ER" S 3(<x))= (v1)² min (2nRm(F)) + Gzo (( G.).
(10)
where we use a log factor w = Ollog(n) + log(1/Au)).
To make the relation to adaptive kernel spaces more explicit, assume that the ghe bounded as Σx || I 1. Then we define a family IC of corresponding kernels of the form
K (o) (2), = K (21, E ( ((z1)g(Z2)),
(11)
ie., KC (K{ {o} finite, Eye(o) 11 S 1}. With this notation, the complexity measure is ((xx)), (v:)) min _"E8"
Rn ( + w min p* {'
(12)
KeK
Hence, this measure may be understood as searching for the most efficient and effective feature representation within a family of RKHSs.
We may also relate this complexity measure to the NTK-based complexity measure yh H (Arora all 2019a). For any labeling f let f Hu~ be the function with minimum NTK norm that maps 24's Jt's, || px H -" If show (Appendix A.
set {g} /1I then one can
pe K-1 (V S" S
x 12- 411 4 4 Hoo-1
(13)
which implies
3 < min (n ( f"E
One can further set === above and obtain
S < (4w1) -
(14)
4

---

Published as a conference paper at ICLR 2022
3.1 GENERALIZATION
With the complexity 3 in hand, we can now state our generalization result. It assumes optimization by a Projected Stochastic Gradient Descent (PSGD), described in detail in Section
Theorem Suppose we run Projected Stochastic Gradient Descent (PSGD) on the regularized
pirical risk with parameters as in Section A and 19i Σ B a.s.. Then, with high probability (e.g. 0.99) over the randomness of data, initialization and noise of the gradient steps, PSGD converges in Poly( V 1/ n) iterations to a solution (WPSGD, VPSGD) with population risk bounded as
(((2)))) (1))=n)
B²
R(SWreon Veecn)
(15)
n
n
As a side remark, the factor 2 in front of R,, in the definition of S in (12) not special and similar generalization bound can be obtained for any 7 > 1. Substituting the upper bound on the complexity in Equation (IE), one recovers an NTK-based generalization bound that scales with y -000 H00-yy/n in et 2019R). The reason for the faster squared rate here is that we are considering smooth losses, while they work with a bounded Lipschitz loss. Indeed, is not hard to apply a more rigorous uniform convergence analysis from (Srebro et all, 2010) to also obtain faster squared rate for the approach used in (Arora et all 2019A)
y/n h up to log factors, which is roughly the square of the generalization bound presented
(E4 is upper bound on our complexity, our result generalizes and tightens the NTK bound (Arora ct all, 2019%). To illustrate the flexibility of our complexity measure, we show in Appendix A. simple explicit example of functions represented polynomial series where bound improves upon the NTK bound. Notably, we only substitute low-rank matrices G in our complexity measure for this construction. We leave further investigation of our complexity measure for arbitrary G's to future work.
Since Equation
3.2 UNDERLYING CONCEPT CLASS
Instead of data dependent generalization bounds, one may study the generalization gap with respect some concept class. The complexity measure 3 implicitly uses the following adaptive norm on the space of functions from Rd, the infimum of the RKHS norms for the family of kernels K::
1l = inf [l K (K)
(16)
It is not hard to check that II-Ilc is in fact norm, and that the inf is achieved by particular set {g} Similar to the derivation of the upper bound on the complexity measure in Equation (IE), by setting {o) [[]]"|>>>>> we obtain the following NTK upper bound:
lllk S ||
(17)
This leads to a funetion-dependent generalization bound which bounds the risk of the learned net- work against an arbitrary function f with l|flls < cc.
Theorem 2 For any measurable function f Rdd - R. in the same setting Theorem M the population risk of the trained network can be bounded as
R[ Vesco S <2RJ) + + 1
(18)
As in the data-dependent case, the factor 2 R() can be reduced to any constant 7 1.
3.3 INTERACTION OF LAYERS BEYOND THE LINEAR APPROXIMATION
Here, we give high level intuition on how the adaptivity is achieved in our regime compared to NTK. In the NTK approach, for every input x, the neural net (w.((1) is approximated by its linear approximation at (W( (()) (the initialized network), (w.v(x) = (V (Vw.v fwo., v (x), (W W()), V ((0))). The NTK approximation works as long as (W, V) are close enough to their
5

---

Published as a conference paper at ICLR 2022
initialization that the linear approximation remains accurate and the interaction of weights be- tween layers is negligible. Specifically, the features o' (2²) behave almost linearly with respect to W - W as || - W is taken to be small and the sign pattern Sgn( (g(((()) + W')x.) is proven not to change much compared to Sgn (w.(). Additionally, the NYK-type analysis needs the following two conditions to be satisfied: (1) the sign pattern of (z:) + o (ax;) with respect to V(0) V" remains almost the same the sign pattern of (x)) with respect to V and (2) the weight changes W" and V' should not interact, which means the "interaction" term, v (V()) (a:) (z) R 0, should be negligible. Therefore, the non-negligible terms for the NTK are: (1) Vm²
vm=
I a Sgn (( (1000(0()))) (z.)) y (Zzz, which is almost linear in W' (recall
that (x;),) depends on W"), and (2) ymg a" Sgn (10)s (xz)) V ((00) (2x) which is linear in V This approach has two important implications: (1) it convexifies the optimization (for convex loss), as the approximation is now linear in W; and (2) it simplifies proving generalization, as it works with the class of functions in the RKHS space of some fixed kernel. However, this simplification leaves no room for the ability of the neural network to learn intermediate feature representations.
In our regime, in contrast, we enforce the condition Vj ; V T (xx) (+), which implies the sec- ond (2) above is zero, while the interaction term is not negligible any more and the network behaves similar to a quadratic function with respect to (W", V') (for fixed (.)). Condition (+) is critical both in proving the convergence of the algorithm as well as bounding the Rademacher complexity of the class of networks with bounded weights. Rather than working with a fixed kernel, the interaction term enables us to use the first layer for representing the input in suitable feature space, which can be interpreted as picking suitable kernel, then use the second layer to describe the output based on those features. This is also indirectly encoded in our complexity measure. In addition to enforcing the orthogonality condition (+) (in the SGD variant), conditions for entering our regime are that the overparameterizztion m1, M2, my and K2, f2 are within a specific range with respect to each other. We listed these relations in Appendix ATH.
To illustrate the benefit of going to this more involved regime, denote the class of neural networks with bounded Frobenius norms ||W'|| S h, ||V'|| S 72 by Gr (and bit more structure which we elaborate upon in the proofs); turns out that g7.11 roughly includes Hx (0(7)2) for every kernel K E K. in the sense that each f E Hx (2) is well-approximated within Gric to arbitrarily small error on fixed input (the error goes down with the size of the network). On the other hand, we show that the Rademacher Complexity (RC) of G behaves similar to the RC of the NTK class * (0(7)72)) As our algorithm guarantees finding a network with sufficiently small empirical risk within Gr this phenomenon underlies our adaptive generalization bounds.
Compared to previous work that provides an adaptive kernel analysis still for a two layer model (Don & Liang. 202)) (although their analysis is for the gradient flow and non-algorithmic), our model requires an additional layer so it can, in a sense, "simulate" the process of feature extraction in one layer to be used in the next layer.
3.4 COMPARISON WITH KERNEL FITTING
We compare our generalization bounds with some kernel fitting rates. Given a kernel K with K(x, x:) < 1 for every x : || 1, suppose we want fit function from Hx (B'), i.e. having K- RKHS norm bounded by B'. In the realizable setting, when there is an underlying f E Hx (B)) with zero risk, Empirical Risk Minimization (ERM) enjoys a fast rate using the smoothness of the loss (Srebro et all 2010). The Rademacher Complexity bound R(Hx S S B then implies
FRM) < Ō(B²/n
(19)
for the squared loss, which is minimax optimal up to log factors. To compare to the neural network,
we substitute fre into Theorem Ø To relate the B in our bound B¹, assume for simplicity of
exposition that ||/llc = || for some K* E IC (otherwise we can use convergent sequence).
Observing that K ((o) (I) & 1 for every kernel (g) E K, we obtain that [f**(x)) S [|ff*"[x- ||]**| (Appendix (.G). Combining this fact with the realizability assumption,
then upper

---

Published as a conference paper at ICLR 2022
bound the parameter B in Theorem @ by | ll.. and obtain
R(fwrsaw Wisss Ó(1 (
(20)
If we further take K to be in K,, then Equation (211) combined with |If S II s B' implies:
RJWWess.Veee Ö(B² /n), /n),
that is, for every kernel K E K., our deep learning approach almost achieves the conventional kernel bound in Equation (I
Repeating the uniform risk bound stated in Theorem I in (Srehro all 2010) for H (B²) where B3 is all powers of two, followed by union bound, one can easily obtain a fast rate of
R(FKRLR) < =ō 10 K K-
B
(21)
71
for the solution of KRLR in the general case (not realizable) for the squared loss. On the other hand, for B-bounded Lipschitz. loss, we instead get a slow rate for KRLR:
R(SKRLR) S =0( yTK-
B
Vn
where B is an a.s. bound on ly| as before. This bound is similar to crora (2)) Note that our data dependent generalization bound in Theorem M already achieves the fast rate for KRLR in (EII
for any K E K. Finally, in the non-realizable case, we still have the following fast rate for ERM regarding the hypothesis class Hx (B') (Srebro et all, 2010):
R(fERM) S Ō(R(f*)) + B"+B*), B"*B""
where now ft argmin (B.) R(f), (B)
while Theorem D also implies (again for every K E IC):
R(JWesco Visco S &Ó((((**) + 1 = Ō(R(S*)) + B²+
4 ALGORITHM: PROJECTED STOCHASTIC GRADIENT DESCENT
In this section, we describe our algorithm PSGD, presented as pscudocode in Figure which is roughly Stochastic Gradient Descent modified project out low-dimensional random subspace from the second-layer weights. PSGD approximately runs SGD on a smoothed version of the fol- lowing loss function (V1, 22 are defined in Appendix A.
L (W', V*) = Rx (Jw.vv) + 1i | ['|] Vill.'
Compared to standard SGD, algorithm makes two modifications: (1) it uses randomized smooth- ing to alleviate the non-smoothness of the ReI.Us, (2) it ensures that the weights in the second layer are orthogonal to the data features ((0) (x) computed by the first layer at initialization. This helps to control layer interactions pointed in Section B.3. For smoothing, we add Gaussian smoothing matrices We and VP to the weights with i.i.d. entries drawn from (0, 32/m) and (O0 / m22) 31 = Op (m3 /222//2///////// (K1 (/iymm plify the exposition, (-(-) is hiding the dependencies the basic parameters B, n, 1/Ao and log factors. Our convergence proof uses the loss with respect to this smoothed network.
respectively, for 32 = (K( /m, (k2
To sim-
For the projection, let -- Rm be the subspace of weights of the second layer whose rows orthogonal to the first-layer data representations (00) (z.)'s
(0)))s Vi [n] at initialization:
V' E x- Vj [mz], Vi [n] ( (x;) 0.
(22)
In summary, at point (W", V*), the algorithm samples a random (z,, v1) from the data, well as smoothing matrices Wo.1 Vo.1, Wo.2 Vo.2_ It then computes an unbiased estimate for the gradient (v w. Vv), adds additional normalized Gaussian noise matrices E,, and moves in this direction with step size 1/poly(n,, 1/B, 1/20):
(W", V' (W'.V" W + E1/(ym, [Ell), Proie- (vv + E E>
(23)
7

---

Published as a conference paper at ICLR 2022
Parameters. Our results apply to the overparameterized regime, when the size of the network, ie. parameters m,, 22, my are polynomially large in n, B V 1/B, 1/>g. This guarantees that the network has suitable function representation capacity, and PSGD is able to find good local direction at every iteration. The regularization coefficients 4/,, 4/2 can be set with respect to any candidate (J", G) for our complexity measure (H). In Appendix A.2.,
introduce simple doubling trick that handles the case when we do not have access to an optimal candidate solution. With such an f*, as we describe in Remark 0. define v max{ R., (22, B² /n), and set t0 = v/44, 1/2 // (4C() G)), where f* is the projection of f* along the span of eigenvectors of A with eigenvalue as large as (2(1/n 2 We list the suitable regime for overparameterizaaion in Appendix
Algorithm PSGDDProjecter Stochastic Gradient Descent)
Input: network architecture m,, m2, ma, initialization parameters K1, smoothing parameters B1, training set (5t, 36 )= label parameter B, (J", from the complexity measure
1: Gaussian initialization J. <- (N0 K1). V + (0,
2: Define parameters 1/1, 2/2, V, 7), subspace & and objective Li as described in Section !!
3: while Li (W", V') > (f* + 2 do
) vo.1 VA2 + N(O, m2 4: Gaussian matrices W W + (0, my d.b j.k
"..' j.k
5: Sample data (xi, y:) uniformly at random
6: Compute gradient estimates
(z:), 36 V fw www.w + 2 Vv (ffw+walw++ (I.),, www.wywwwww.................... + 24/2
Vw = +Ufw+wWo.ve
7:
8: Move as (W", VV) < (W", V') Vw + / / Proje: (vv + E2/ 12
9:
Return (W',
HIGH LEVEL IDEA OF THE PSGD ANALYSIS
The reason for considering a Frobenius norm regularizer in PSGD that we want the weights to remain close to their initialization so the final network is in the class gy for suitably chosen Y1, 72: while still reducing the nonconvex empirical loss R,, (fw....). We prove convergence for PSGD by building on ideas from Allen-Zhu et all (2018), with a framework based on the classic result that SGD can escape saddle points for nonconvex functions. Compared to them, we take a different approach driven by our purely data-dependent complexity measure. We augment this by careful Rademacher complexity analysis of the class gm,,2 in Appendix A.
Construction of good Network To study the loss landscape, similar to (Allen-Zhu ctall, 2018). we show the existence of good local update at reasonable points (W', V'), using the ideal pair (W*VV") that we carefully construct from our complexity measure. Here, we sketch our proof for constructing (W*, V*). Let (W", V') be the current weights of the algorithm. Fix sample i E [n]. In Appendix A we use G to construct V* for the first layer weights with decomposition W* Em' W and (1) bounded norm, such that o" (1;)) = /mm W (W + W")x;) W',,
This decomposition ensures for every k, k' [ma], negating Wi only negates o² "xxx)))) when k'' and has no effect on o² (I:) for k' * k. This way, we can easily generate any arbitrary sign flip of the entries of ø' (I:). We use this property to generate a suitable random descent direction.
Next, we construct a suitable weight matrix V for the second layer which maps the features x²(x:) (z;) into f (recall the definition of the complexity measure). The key here is that we consider a regime where the norm of (0)) (a:) is typically larger than that of ø' d((x;) and o² (ax), so it is very likely that the sign pattern in the second layer is determined by (00) (zx) in most rows. In such a scenario, the condition V 1 (0)) becomes vital as the interaction of V with (xx,) problematic for both generalization and optimization. From the standpoint of generalization, without excluding this interaction, one can exploit the large size of ((0) (a:) and build network within the class G corresponding to complex function that overfits the data, Indeed, we utilize the large magnitude of (F()) and its orthogonality to the rows of V in the RC bound. On the other hand, since the weights
8

---

Published as a conference paper at ICLR 2022
of the first layer does not affect (z,), the interaction of V and (z,) is problematic for the algorithm's 's convergence, particularly in proving the existence of a local descent direction. This is the rationale behind our orthogonality constraint (22)).
Finally, the 6 (az)'s, the above control on the signs, and the fact that (6 (ri, ) (00) (raz)) concen- trates around my (00 () Zi, (o Fig) which recovers the structure of the kernel K (Section 2). give rise to the kernel Go K in the second layer. Using this structure, we construct V that maps 6 (z,)'s to fi's "s, which has additional good properties, including O(f O(f*" (GOK)) f*)- bounded norm, and rows that are orthogonal to (I;))s ss. For more details, see Appendix
Nonexistence of Bad Saddle Points Next, we want exploit (W*, V*) to prove the existence of a good direction along which the objective decreases locally. Moving along (W*, V*) is the first idea, which fails the cross terms created between W V and V', W cannot be bounded effectively. Instead, we randomly perturb W and V in a coupled way and prove reduction in expectation. We elaborate more on this suitable random direction. Multiplying random signs Eg onto Wx. we define the sum W = -==1 Eg W.. We also multiply the same signs to the columns of V and project it back onto h- to obtain Vg. Then, we move in the random direction (VTWS- - r///2, V - v/V22); this update creates additional cross terms in the objective that we must bound to prove a local reduction argument. A key point here is that we prove with high probability the norm of the weights is always bounded. This norm restriction enables us to substitute terms that we do not have control over by their worst-case supremum. We refer to Appendix A. for similar techniques.
Convergence of PSGD Finally, we use the fact that SGD escapes good saddle points (Gie et all 20156).. For proving the existence of good random direction escape saddle points above, we use that the norm of weights is uniformly bounded along all iterations; this bound, in fact, is looser than the bound that we show for the final weights of the network. Yet, this additional restriction cannot be addressed by the classical nonconvex theory of SGD. Consequently, we refine and adapt the proof of (Ge 201 to incorporate this additional constraint. At a high level, ee (201555) work with supermartingale based on the loss value. To guarantee the additional norm restriction, it is initially tempting to apply Azuma- Hoeffding concentration to bound the upward deviations this process. However, this fails as the process has two-fold behavior, depending gradient is. At the core of our refinement proof here, we instead directly bound the MGF of the martingale using Doobs maximal inequality. We refer to Section I. for more details.
how large the
ACGNOWLEDGMENTS
The work was supported in part by NSF awards SCALE MoDL 2134108, CCF-2112665 (TILOS AI Research Institute). CCF-1155211 CCF- CCF-1565235, and DMS DMS-2022448. We would like also thank Sasha Rakhlin and Elchanan Mossel for fruitful discussions.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning, arXiv preprint arXiv:2001.04411 2020.
Zeyuan Allen-Zhu Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. arXiv preprint 1tt.://8110049111. 2018.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis gradient descent for deep linear neural networks. arXiv preprint arXiv:1810.02281, 2018
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pp. 254-263. PMLR, 2018b.

---

Published as a conference paper at ICLR 2022
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 322-332 PMLR, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net, arXiv preprint arXiv: 1004..1150 11955, 2019b.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, ((1))622-681, 2017.
Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, pp. 195-268. PMLR, 2019.
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14(1):115-133, 1994.
Peter Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally margin bounds for neural networks. arXiv preprint arXiv: / 776600898, 2017.
Peter Bartlett, Dave Helmbold, and Philip Long. Gradient descent with identity initialization effi- ciently learns positive definite linear transformations by deep residual networks. In International conference on machine learning, pp. 521-530. PMLR, 2018.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with gaussian inputs. In International conference on machine learning, pp. 605-614. PMLR, 2017.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. arXiv preprint arXiv:/805.0955: 2018.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pp. 1305-1338. PMLR, 2020.
Amit Daniely. Depth separation for neural networks. In Conference Learning Theory, pp. 690- 696. PMLR, 2017.
Xialiang Dou and Tengyuan Liang. Training neural networks as learning data-adaptive kernels: Provable representation and approximation benefits. Journal of the American Statistical Associa- tion, pp. 1-14, 2020.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizee neural networks. arXiv preprint arXi::1810.02054 2018.
Lixin Duan, Ivor W Tsang, and Dong Xu. Domain transfer multiple kernel learning. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 34(3):465-479, 2012.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, arXiv preprint arXiv: 1008, 2017.
C Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. arXiv preprint arXiv: 1.01500, 2016.
Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural networks, ((3):18-1192 1989.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle pointsonline stochastic gradient for tensor decomposition. In Conference on learning theory, pp. 797-842. PMLR, 2015a.
Rong Ge. Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Peter Grünwald, Elad Hazan, and Satyen Kale Learning Theory, volume 40 of Proceedings
(eds.), Proceedings of The 28th Conference of Machine Learning Research, pp. 797-842 Paris, France, 03-06 Jul 2015b. PMLR htttp://procediini nas r.esss v40//e htmll
URL
10

---

Published as a conference paper at ICLR 2022
Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-laye neural networks with landscape design. arXiv preprint arXiv:1711.00501, 2017.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural networks. arXiv preprini urXiv:/906.088 2019.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pp. 297-299. PMLR, 2018.
Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic modeling speech recognition: The shared views of four research groups. IEEE Signal processing magazine, 29(6) 2012.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gener- alization in neural networks. arXiv preprint arXiv: 180.00720 2018.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non-convexity; Guar- anteed training of neural networks using tensor methods. arXiv preprint WoXiv:1506008733 2015.
A. Javanmard, M. Mondelli, and A. Montanari. Analysis of a two-layer neural network via displace- ment convexity. ArXiv, abs/1901 991101375, 2019.
Kenji Kawaguchi. Deep learning without poor local minima. In nips, 2016.
Pitas Konstantinos, Mike Davies, and Pierre Vandergheynst. Pac-bayesian margin bounds for con- volutional neural networks-technical report. arXiv preprint 1000000/000
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data, arXiv preprint arXiv: /808.0/200 2018
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. arXiv preprint 1705:01700008855 2017.
Tengyuan Liang, Alexander Rakhlin, et al. Just interpolate: Kernel ridgeless regression can general- ize. Annals of Statistics, 48(3):1329-1347) 2020.
Yiping Lu, Chao Ma, Yulong Lu, Jianfeng Lu, and Lexing Ying. A mean-field analysis of deep resnet and beyond: Towards provable optimization via overparameterization from depth. In icml, 2020.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115633):7665-1777, 2018.
Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension- free bounds and kernel limit. In Conference on Learning Theory, pp. 2388- 2464. PMLR, 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally normalized margin bounds for neural networks. In International Conference on Learn- ing Representations, 2018.
Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In Interna- lional conference machine learning, pp. 2603-2612. PMLR, 2017.
11

---

Published as a conference paper at ICLR 2022
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In Doina Precup and Yee Whye Teh (eds.), Pro- ceedings of the 34th International Conference Machine Learning, volume 70 of Proceed- ings of Machine Learning Research, pp. 2847-2854. PMLR, 06-11 Aug 2017. URL http: //proceedings
I.
Alexander Rakhlin and Xiyu Zhai Consistency of interpolation with laplace kernels is a high- dimensional phenomenon. In Conference on Learning Theory, pp. 2595-2623, PMLR, 2019.
Alain Rakotomamonjy, Francis Bach, Stéphane Canu, and Yves Grandvalct. More efficiency in mul- tiple kernel learning. In Proceedings of the 24th international conference on Machine learning. pp. 775-782, 2007.
Itay Safran and Ohad Shamir. Depth separation in relu networks for approximating smooth non- linear functions. arXiv preprint arXiv:1610.09887 14, 2016.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, pp. 4433 4441. PMLR, 2018.
Itay Safran, Ronen Eldan, and Ohad Shamir. Depth separations in neural networks: what actually being separated? In Conference on Learning Theory, pp. 2664-2666. PMLR, 2019.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6120. 2013.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwweserr, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications,
2020.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterizee shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018
Sören Sonnenburg, Gunnar Rätsch, Christin Schäfer, and Bernhard Schölkopf. Large scale multiple kernel learning. The Journal of Machine Learning Research, 7:1531-1565, 2006.
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. arXiv preprint arXiv:1605.08880 2016.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Lafferty, Williams, J. Shawe Taylor, R. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 23. Curran Asso- ciates, Inc., 2010. URL https://proceeeee .tw.rmeeseseeess.cccooeeeeeeeeee 76cF99d36 bee./aabbbbb667777444443333
Yuandong Tian. Symmeery-breakkng convergence analysis of certain two-layered neural networks with relu nonlincarity. Network, 100(1):1-1, 2016.
Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma. On the margin theory of feedforward neural networks. 2018.
Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets their induced kemel.. 2019.
Lei Wu. Chao Ma, and Weinan E. A priori estimates of the generalization error for two-layer neural networks. 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 16/ 16/ 1.03500, 2016.
12

---

Published as a conference paper at ICLR 2022
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for one-hidden -ayer neural networks. In International conference on machine learning, pp. 4140- 4149. PMLR, 2017.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz. Non-vacuous gen- eralization bounds at the imagenet scale: a pac-bayesian compression approach. arXiv preprint WwXiv::804005822, 2018.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over- parameterized deep relu networks. arxiv e-prints, art. arXiv preprint arXiv:/81 1.08888, 2018.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
This appendix contains the different main sections of the proof. Lower-level lemmas may found in Appendix
CONTENTS
Stronger Generalization bounds for polynomals
15
The Doubling Trick
16
Amount of Overnarameeterizatoo
17
PSD property of K
18
A.5
Complexity upper bound
18
A.6
Complexity measure and the ( norm
18
A
Core Generalization Resuli
20
A.8
Structure the prool, setling ma, and further de delinitions
................................
22
A
9
Proof of Theorem
24
................................
Optimization
25
Rademacher Complexity
28
Constructing W
34
A.12.1
First Layer, Construction of W
34
A. 12.2 Second Layer, Construction of
39
A..3 Construction of
45
Existence good direction
48
A 14 Existence of a good direction Helper Lemmas
53
IS Bounding the worst-case Senario
65
A. 16 Convergence
73
17 Process from higher view: definition of the (X) sequence
................................
77
A. 18 Bounding the MGF of X,
79
A 19 Proof of Theorem
80
20 Gaussian Smoothing
A.20.1 Setting 31 and
................................
86
Basic Tools
87
A.21.1 Delining the rare events
91
A.21.2 Bounding the value of
1.21.3 Bounding the difference between Original and Smoothed Functions
94
14

---

Published as a conference paper at ICLR 2022
A.1 STRONGER GENERALIZATION BOUNDS FOR POLYNOMIALS
In this section, we prove an explicit generalization bound for functions represented as a polynomial sum. Note that the bounds in Arora etll (2019)) for polynomials assume the monomials with degree larger than one to have even powers, while here we do not impose this restriction. In addition, different from Arora et al (20195). our bounds remain meaningful in the noisy case (recall our Theorem 2).
More specifically, bound the ( norm of such functions. Consider the target function s with the following power series formula:
s(x)
ap (u x),,
(24)
where Up E R and wp Rd, We can write
d s s(x) = 9n (v) + Σ (
(25)
where Fą denotes the kth entry of vector here and
(1(x)=
E
ap ap(w x))²
PEA: p p even)
and for all [d]:
(x) =
Σ
Upp ap(2 x
(EA2=(p>2, p odd}
Then, using the Taylor series of x(] aresin(a))
Epm 2220 for |x|| S the RKHS H(H))) of
the NTK can be identified by square- square-summable sequences of reals (a, > with dot product
((r)))=1) =)))
where X(r): Z20 - Zzo such that it maps zero to zero, the first d positive integers are mapped to one, the next df ones are mapped to 2, etc. Moreover, the RKHS mapping L : Rd + H(H from the Euclidean space is:
V (x) = ||=||| (z',,..,22 L'a. (o',, They (o) (1%, 2/e, ...%,, (,,)) R,
where x' = ||=||| and in the notation above are presenting sequence of sequences, by which we mean the inner sequences simply unfold. Using this identification, one can see using the linear representations of , in H:
11 11
Tpa 1e0gl1epll 11 Σ ped,
(26)
1
=
No wp 2 2(p-1)
(27)
PEΛ
Summing above and noting the linear representation of g:
l191 11 +
I = Σ
uupl? +
22 = 7p 1up1? = 1
PEA:
PE
(28)
Now for {g} ( (gr
1 we consider the kernel K(o)- Expanding the tai-
lor series of (2(2)))(x) Exn Mpx", we find the identification (h )ee(++1),r cs with dot product
80
d+1
Σ
(X
Σ
h
===0
15

---

Published as a conference paper at ICLR 2022
with RKHS map
V2(x) = (01 (x), 1eihh.....4411660 (0)) (1), (oaf(())).,,,,.
2'ala (2)), (2%, 2 Ih (z)) x2e((] ................................ (2 the ... Tha....,,,,
Now, we compute the nomn of function with respect to (g)) combining the above representation and dot product with Equation (AA) and the fact that we work with unit norm æ, so x' x:
|| (() no + (d 1)
(29)
Plugging the above and Equation (2 into the definition of |I-IIç in (LG), we conclude
|| S ||>|) (llen I1:
1 S (no + (d + 1)m) Σ p
(30)
Note that if the odd exponents (except possibly one) in the definition of s in (!e)) are zero, then we could consider only the function 9i and kernel Kg which would have implied bound of
140 Ep=1 Tpa up 1|2""
A.2
THE DOUBLING TRICK
For the SGD optimization, set the regularization coefficients in the loss L1 as
1 v/4,
1 = ==/(<((f"" G)),
(31)
with v ==
B²/n// /nj. This assumes we know the I' and G that minimize the adapta- tion within the complexity measure (I2). To achieve generalization bound in Theorem II here, we explain how to use a simple doubling trick to get over the fact that we might not know these optimal
solutions f and G. The proof here is based on the generalization result in Theorem
Theorem Without explicitly knowing the exact value of the complexity measure, i.e., the optimal solution of Equation (T22, one can still achieve the generalization bound in Theorem I1
Proof of Theorem II
Our core generalization result is in Theorem R The proof of Theorem M is simply adding doubling trick on top of the argument of Theorem B. We also prove Theorem E as consequence of Theorem 11 in Appendix D In the rest of the proofs, for simplicity, we refer to (WPSGD, VESGD) by (W', V'). Let f G be the optimal solution to (II)) With a simple rescaling of G we can (Note that the complexity does not change by such rescaling). Now one can exploit the condition ||ы, < B, and consider the setting f 0 to get the following trivial upper bound on the complexity measure:
assume (11=11 )*) =
3((x.)())) 2nB
Therefore,
2n 2n + f (d'=) I 2nB
(32)
Using Equation (32)) and the optimality of (f*,
(f**) S B
<= (((""""")) $ 2nB
(33)
Combining the first equation above with the definition of in Equation (I)), get
B²/n<uSBB
(34)
To initialize 1/ and dy. use Equations (II) for any f and G, and result get general- ization bound as in Equation (A5).. However, to achieve the best possible rate characterized by our complexity measure in Theorem without explicitly computing the answer of (I2), we simple
16

---

Published as a conference paper at ICLR 2022
doubling trick; for every pair (S' 1/) such that ç" is a power of 2 between B and 2n.²², and v/ is power of two between B²/ /n and B², we initialize 2/1, 4/2 as in Equation (5II) and run the algorithm. then return the network which minimizes the empirical loss after the required polynomial number of steps. This is to make sure that the value of the loss will go at some point below the PSGDstopping threshold on the loss, since the stopping threshold depends of. Another way to resolve this issue, to have an early stop when the value of the loss pass the threshold to again run doubling trick on the value of Rn (f**)) for every fixed value of v and S, and run PSGD with stop threshold R,, (f*)) + 2v (here, R,, (f*t) is set using the doubling trick variable). This approach works because our final upper bound on the risk ignores the constants (note that the doubling trick introduce additional constants). Moreover, since 2 B² /n by definition, we don't need to run (f*)) over values smaller than S2 12BB//1 /n), since does not change the order
(f*) which
not aware
B²/n
of R2 (J***) + 2v. Particularly, combining this with the upper bound on (f*)) we only need to
run the doubling trick for R., (f**) in the interval (S2(B² /n), (BB)). Now let v' be the power of within v(G', ff' < v < v(G", f(*). If we are in the case
far A pm B², then for ç" equal to the smallest power of two larger than B², when we run PSGD with pair (v',')) by Theorem B
(35)
2B + B² 3((x))=1 (1))E1)
B
R(fw.v) S 2R,
(36)
n Because return the minimum upper bound on the risk (the tighter lower bound of Equa- tion (EED) among all such powers of two, we certainly achieve the above rate in (5G). Otherwise, A 2 B², let Ç' be the power of two within f A-1 I 5" < A then again easy to check that conditions of Theorem B are satisfied, hence we get the following generalization bound:
n
R(fw.v)) S (R²) + d" B2)
22 + d' 2C( G*) B²
(37)
n
n1
( +
Bww
(38)
n
which proves the bound of Theorem II.
A.3 AMOUNT OF OVERPARAMETERRIATTON
In this section, to provide high-level insight, we indicate the right order of magnitude that our over- parameterization should be in, with respect to one another. Note that the exact coefficients these inequalities would depend the basic parameters B, 1/ n, which we have avoided here for sake of simplicity. We refer the reader to our main proof (mostly Appendix parts details.
for more
K1K2M << 1,
K2 K2v m2 >> 1,
Kiymg m3 >> K2v m2
mi >> m3.
61/m1 >> m3
3/2
82 << 1/ /m3
Viyk22 << 1/ mg
Vm2 >> ma Ki K2
3/2
m²(K2 << K1 m
m1, M2, My, 1/ 1/B2 = B 1/ 1/20).
In addition, we set the smoothing parameters as
B2 = :==
81 = (
17

---

Published as a conference paper at ICLR 2022
where O only shows polynomial dependencies the overparameteriiation.
A.4 PSD PROPERTY OF K
The Schur product theorem states that for PSD matrices and B, A @ B also PSD. Now given an analytic function F whose tailor series coefficients are all nonnegative, Suppose we apply F on some PSD matrix A entrywise, denoted by F(A), under the condition that the entries of A are in the radius of convergence of F, then using Schur product theorem, is straightforward that ((A) is also PSD.
Using the above property, one then check that the tailor series of the defined functions F2 and F3 are nonnegative, hence, the application of the function F (2FF((z) on the gram matrix of (rz) is
a PSD matrix, note that (1), indeed kemnel
S 1 is in the convergence radius of (2)2F)(z))) thus K is
A.5 COMPLEXITY UPPER BOUND
First we mention a simple fact that hadamard product respects matrix orderings. Given PSD matrices A, B, C' 'such that A z B, the fact that A = B C is an easy consequence of the Schur Product Theorem; indeed, B A is PSD by definition, so (B A) @ C = B @ C A o C' is also PSD.
Next, is easy to check that the tailor series of aresin( has all nonnegative coefficients. Therefore, for a PSD matrix X, as we discussed in Appendix A.4. applying aresin entrywise on X, namely aresin X, is also PSD. Setting X equal to the entrywise application of 2F3 the gram matrix of
datapoints (2=) realize the matrix arcsin (2Fs ((r,, igi)s.)) is also PSD. Noting
the definition of R Equation (8), we conclude that for the data kernel matrix 8 we have
111
1
K
4
where 1 is the all ones n-dimensional vector.
Combining the two mentioned facts, we can lower bound the matrix K = K O G for any matrix
G as
1 11 oG=
== GG
Substituting the rank one matrix f f-t for the n-dimensional vector f³ in Equation (
K (P- K = S k /
(39)
The inequality used in (L3) then follows from Equation (39))
A.6 COMPLEXITY MEASURE AND THE Ç-NORM
This is a brief section regarding some basic properties of S and ||-1Iç-
First, note that the two versions of the complexity measure in Equations (IC) and (LII) are equivalent, as for any finite set of functions {g]. we can define the gram matrix with respect to the feature vectors of these functions on data, and for an arbitrary nonzero PSD G we can consider a Cholesky factorization for G as G XT X, then define the functions {ox} } as the minimum-NTK norm functions which map the input to the features corresponding to X. This observation further implies can suppose the factor matrix X is in guxn, and there is set of at most functions { in which corresponds to this G.
Next, we show that for an arbitrary function f. its sup norm over the unit ball is bounded by its norm:
sup |f(z)) S ll/lke ||
(40)
18

---

Published as a conference paper at ICLR 2022
Note that for kernel K which satisfies (2x 2) S 1, using Cauchy Schwarz simply obtain
f(x) & [ x) S llflk.
where recall that ||-I|x is the norm corresponding to the RKHS space of K. Hence, to show (HL), suffice to show that for all kernels K E K. and unit norm x we have K (x, I 1. To see this fact, note that the norm of each æ E g in the NTK-space is /º (a, x) = 3.2 Therefore, for each function g with bounded-NTK norm, again using Cauchy Schwarz:
1ø(x)) 1 2 -
H
As result, for a family of functions (9) with Ege(s) 1191 I 1, we have every unit norm x:
Σ g(0)² 1
(E(
On the other hand, it is easy to check that for every unit norn x, we have (x, x) S 2/2 so for every such {g), have by definition
K ( (x) S 1,
which completes the proof of Equation (+l)
19

---

Published as a conference paper at ICLR 2022
A.7 CORE GENERALIZATION RESULT
In this section, we prove our core generalization result for the trained network, Theorem B, which underlies our generalization bounds in Theorems II and @ Recall that in the rest of the proofs, refer to the solution (WPSGD, VPSGD) returned by PSGD simply by (W",
Theorem Suppose we have a good candidate pair (f", G) regarding our complexity measure in (VA) that satisfies (H S 1, f f- S (recall A = G & H ). and that f has zero smaller than (1/nn²) (the
projection onto the directions of eigenvectors of A whose eigenvalues last condition can be relaxed, see the next remark). Then, for
max RR, (f //4, B² /n).
(41)
if we are given v/2 S d S v, and we set
//
11 4
(42)
v' 1/2 Aç"
(43)
then for the solution (W', V*) returned by PSGD we have the the following generalization bound:
R(fwrv)) < Rn (fw'.v)) v+ + c"d (5 B²)
5
(44)
4
n
5
Rn (f*) + c" w B2)
S 3
(45)
for constants c", c, and log factor w = log(n)² 3 + log (1/An).
S JTT the directions that are along the eigenvectors of A with eigenvalues smaller than (2(1/22) to obtain f*, then use the pair (f", G) in Theorem G This way, the third condition mentioned in Theorem G also becomes true. As we show in Lemma FA by switching f to f the quantity fz A f does not increase, and the quantity Re (J*) is multiplied by a constant e > arbitrarily close to one, then adds up with O ( /n). This means that the bounds in Theorem G. for the pair (f*, ,G) translates into similar bounds for (f", G) albeit with a bit worse contants. It is straightforward to see that with small enough choice of c and careful AM-GM inequality that we apply inthe proof of Theorem one can end up with the same constants regarding the pair (f" G) as declared in Theorem B. For more careful discussion on this, we refer the reader to the proof of Lemma W.
Remark 1 Given a pair (J", G) satisfying (Ho-- G) <
one can project out
Proof of Theorem
Almost all of our proofs in the rest are in the aim of proving Theorem Crucially, prove this Theorem, we need to establish two big results:
We need to show that the final network has small training loss, and within the class Gy for some suitable 72- This is handled by Theorem M in Appendix A.M We define the class 97.m roughly the class of networks with norm bounds || W()) <
71. [V |[ I 72 where the rows of V [0) are orthogonal the subspace + plus an additional structure defined Appendix A. This task, on its own, has three main steps in our proof:
(a) construct "good" underlying network, Appendix
(b) find "good" random direction and study the landscape of the objective, Ap- pendix A.
(c) we prove the convergence, Appendix A.
2. The Rademacher Complexity of the class Gn.c2 needs to be suitably bounded. This handled by Theorem El in Appendix A
With access to these results, here we show how Theorem & follows by a simple application of the generalization bound in (Srebro all 2010). Specifically, for fixed constants 21, 23 and every integer
20

---

Published as a conference paper at ICLR 2022
i 12 O, we Theorem of (Srebro all 200) for the class Gan. 7 2' B/2s with confidence probability 1 - 2- which, with union bound, implies that with probability at least 1 - 83. for every i and fwi.v' E Garmi
(log(1/(2-i6g)
R(fw(v.)) S Ra(Sw + Klv Ba(Sw: Ba(fwwsv)))
(46)
(1og(1/(2 163))
+ +log(n)
(47)
Y1
where ((Jw y (x:), y) is a.s. bounded by b for function within the class Gz and a universal constant. In the following, we aim to further bound the Rademacher complexity R and parameter b.
Applying the AM-GM inequality with respect to ratio 24 for the second term:
b blog (lg((1(22-80)) (5)))
R(Jw(v)) < (1 + ([w,, K2/ / (og(())- R(G +
+ (R)) b blog(1/(2-o8g)
n
b blog(1 (lg((1(22(00))
$ (1 + 24) ( +K2/2/ (og(())">R(=nnn)) +
n
6 (log(1/(2-ba))
+ +log(n) R( )2
R(Geix)) (2K3 (log(1((2-15))
s (f)
n1
(48)
Now let 7² be the smallest number of the form 2' B/2 (for some i) which smaller than 22vÇ.
This definition implies
S max B/za) Now Theorem B in Appendix bounds the Rademacher complexity:
(49)
2217"
R(G s vn
(50)
On the other hand, from Theorem by setting 22 V40, get fwi.y E I2
Moreover, from Lemma 60 for fwi.v' E I we have for every ||||| $ 1:
[/)r 2217",
(51)
so the loss E(fw',y vv ()),)) can be bounded by (B 221 using the 1 smoothness property. Therefore, for the class G we can set b (B + )2 Combining this with Equation (5I) and plugging into Equation
R(fw'v)) & (1 + 2.) (fwr..) + (2K3/2 /24 + +1) In)(n)3 42f7*2 Furthermore, by definition of we have 2 < 222
+ (2K2/24 + 1) (B 2217" (ooglo((222)) 8a))
n
7
R(Swiv))) $ (1 + 24) 24) + (2K + ()og(())((n) + 2log(22223 (/B) 427702
(52)
+ +22K2/2 /2K3/24+1 +1) 2B log (22223/////
(53)
Now applying the upper bound on y":
42 4 V + 2B/222))
R(fw.v))) < (1 2. + (2K2/21 + (log(()) + 22log(22)23 (/B))
(54)
+(2K2/24 + +1) 2B² log 222233
(55)
21

---

Published as a conference paper at ICLR 2022
( B², in the third term above substitute B by Vs. Finally, similar to the bound we stated in Equation (I4), note that we have the following trivial bound for Ç:
< < 1 S 4nB²//uu
(56)
Le. there is no point in considering larger ('s, which implies log(22233v\/B) (log(() +
lo))) Plugging this above and picking 24 1/3 show the proof of Equation (H
Further-
more, applying Equation (b in Theorem to the R. (J.. term in Equation (!=) further gives
the second Equation (
Remark In the same setting of Theorem B. if we have v/22 S v/ but not generally upper bounded by then PSGD leads to the following generalization bound:
R(fw S (n((5)) + c (5 + B²)
n1
using a similar argument as we did for Theorem 3
A.8 STRUCTURE OF THE PROOF, SETTING m3, AND FURTHER DEFINITIONS
Throughout the proof, (W", V*) represents the pair of matrices of the current iteration of PSGD, (W*, V*) are the "ideal" matrices that we construct in Appendix A. (WP, VP) and refers to the gaussian smoothing matrices. Importantly, note that our squared loss {(f, y) is zero at f We have tried to make the lower level proofs into sub-lemmas and create manageable hierarchy as much as we could, to make the document more clear and readable.
Similar to the conditions in Theorem B, through out most of the proofs assume that we given a pair (f", G) with slightly more general setting of Theorem B
fat A A-1ff fr S C2, for A = G (G, H S G.
Particularly, Ç1, S2 appear in Appendix A. Because we are allowed to rescale G, we do not really gain much by assuming this more general setting, though we pick to work with the general setting as the abstraction makes the proof more straightforward to understand.
We refer to the parameters B, 1/A0, n as the "basic parameters". m, m2, ma, 1/ki, K2 as the "over- parameterization" and 31, ,32 the "smoothing parameters." " By the phrase "having enough overpa- rameterization" we mean it suffices to pick the overparameterization m1, m2, my 1/K1. 1/K2 only polynomially large in the basic parameters.
Throughout the proof, we denote the change in the output of the first layer at W W WP compared to the initialization value by gf (x;),
(xx) = 1 W (Wo((((0) + W' + WP)x;) (xx). Vmn
while recall that ø' (I:) has similar definition except without the smoothing matrix WP Although our model is three layer network, throughout the proof, we refer to the parts W* -
Vm,
W')x) and mm L aT ((V(0) + +V)))) as the "first layer" and "second layer," respectively.
Also, we sometimes refer to the binary sign pattern of vector x multiplied matrix W by Dw (Dw.e == Sgn(Wx)),, i.e. the jth diagonal entry of Dw., is one if WT. 2 0, and zero otherwise. To refer to the jth row of W as vector, we sometimes drop the comma in W,, and write it as W,.
For brevity, we denote the Frobenius norm [[]]| of matrix by |[]], and the Euclidean norm of a vector by ||a|]]. For matrices Wi, W2 we denote their natural dot product by (W1, W2) = tr(w7''s W2). We refer to the smallest eigenvalue of a matrix by (.).().. We write R(.) for the Rademacher complexity of function class. We refer to the smoothed version of the network by fir, yo (x), defined by Sw.v www.v/Swww..wwvvll.
22

---

Published as a conference paper at ICLR 2022
In the proof, we mainly work with the loss over the smoothed network f', defined as
L(W", V*) R2 (w.,,.) + d'lll"'|? I/?
(57)
Our algorithm, PSGD can be regarded roughly as an SGD over
g= be some feature representation whose gram matrix is equal to G and ( G) Ek=1 1 x In such setting, it is not hard
Similar to what we discussed in section B, let the functions (9x |g=
check that we can assume each 9k is the minimum norm NTK function which maps (z+) to
(yx (#:))]== s. Indeed, if this is not the case for some ye, we can project the RKHS representation of gi onto the span of the representations of (r:) which can only decrease the complexity measure.
Hence represent 9k E Hy= as linear combination of basic functions H (24,.) data
points:
vk E [ma], (x) =
Σ Vk,
(58)
Here, the sum of squared- n norms of V4 is bounded as
Σ
1M Σ 11allip>= 1H ,) S C1.
(59)
&
For each i E [n]. we refer to the feature representation vector (gx (2:))) on By as T,. Note that we have the relationship
2. = (HG yms
(60)
where H. is the ith row of H In the analysis, we work with a bound & on the quantity max; | which should be bounded polynomially by other basic parameters; in particular, it is defined in Lemma I and is used to bound a cross term in Lemma 14. However, max; ||Vill might not be effectively bounded for arbitrary feature representation. Fortunately, we can remedy this by simple trick; for every natural number s, one can substitute every Js by s copies of gu /s, without changing the gram matrix G. Therefore, for any d, one can increase the multiset of functions (gx) to bigger set (īx), by adding at most (S1/8) functions, making sure of the following for the new functions:
Wk : V H = 1ix 86.
(61)
(This is because Σn 11 -0 I 1). Furthermore, observe that for each gram matrix G, we have an n-dimensional feature representation (gx) for G' according to the Cholesky factorization. Com- bining these facts, we conclude, to guarantee Equation (bII), in the worst case, we need my to be as large as n + (5)/
Finally, observing the following inequality
|| < IPallar~Ao S
11āx 11
(62)
in order to guarantee max; || < need take my large as O(5s/(5 Ao)). which is indeed bounded polynomially by the basic parameters because of the same condition for 1/g. This computation also brings into sight important point:
"Although each gram matrix G is representable by features, in order for the algorithm to be able find suitable network, my might need to be larger than n."
Moreover, for every 1 < k, i S. n, we define the matrices 2 E Bgd as
z 1/1mm m [W (W [T. j=1"
(63)
where in the above notation, j is enumerating the columns of the matrix. We also define the following matrices which we use in our construction later:
W+7 Wk+
V V Zi:
(64)
and W+ as
M/ W+
W++
k=
23

---

Published as a conference paper at ICLR 2022
Finally, to avoid unnecessary complication, we often argue high probability bounds without an represetttnnn of their dependency on the chance of failure (which is a negligible logarithmic factor). We also ignore all constants and log factors, and mainly work with the notation X which ignores constants; we write a X b + c as a short form for h - (c) S S + O(c). As there several hierarchies of new parameters that are defined based on lower-level ones, we rename the new parameters and continue viewing them as black-box. This makes the proofs more readable, since we also do care about the exact dependency of the underlying parameters most of the time, rather we are interested in their orders of magnitude, for example that given parameter goes to zero polynomially fast with respect the overparameterization, etc. Due to the large number of symbols that we have to work with, we might use a symbol more than once, of course when it is clear from context which one we are refering to.
A.9 PROOF OF THEOREM
In this section, we prove Theorem D. stated below.
Theorem 2 For any function f. :: IR - R. in the same setting as Theorem W1 the population risk of the trained network (W', V') can be bounded as
R(Jw(vv)) S 22(()) +0 11W 1 + B²
(65)
Proof of Theorem
Theorem R is simple consequence of Theorem II for the given function f, we apply Theo- rem with the smaller coefficient 7 3 for R., (f*), regarding the complexity upper bound, by setting f = (f(z)))=
f K 1-
Baaw
R(wwvv)) s [f( ) + (aw)
min KEK
+
n
n BLaw
fxll K K-15" fr
(n( (aw)
min
KER
n
On the other hand, because f fo is the minimum-RKHS norm of a function with respect to kernel K which maps x, 's to f", and f is one such function, we have fz K K-1 S fl This inequality implies
min f K K- llf Kek
so we obtain
|| +
R(fw.v))) < = Rr (f)++ (aw)
(66)
3
Therefore, remains to bound R2 (f) by R(f).
As we showed in Appendix A.G. for every input x have f(x) S [1[] for every data (s, v). by the fact that 1yl < B a.s. and smoothness of the loss, have ([f()).)) v) S a(Ifl + B) Moreover, note that the random variable {(f(x).)) y) has mean R()). setting, the variance of {(f(x) y) is most R(f)a(I)f By². Therefore, application of the Bernstein inequality, we have with high probability over the dataset
(. It is easy to check that this
RR < R(f)+() + (v R(faall B)²
a(IIfllc + B)²
3 R(f) +0 R(f)+0
(alllsile (Ilfill++)) B)²
+B)
+
n
n
n
Plugging this back to Equation (Tr) completes the proof. As a result, the learned network can compete with any function that has reasonably small [I/l
R(fw.v.)) S min { (2()) + O(ow II B
24

---

Published as a conference paper at ICLR 2022
A.10 OPTIMIZATION
In this section, we glue together
the existence of a good random direction that we prove in Appendix A.E
the convergence analysis of PSGD that we do based on the work Ge et all (2015b) in Ap- pendix If.
Theorem the same setting of Theorem & assume the network (W', V') returned by PSGD, has sufficient polynomially large "overparaaetterizatio:: Then, for the solution (W', V") returned by PSGD we have
((W,V') S (f* +
(67)
which further implies
(f S (f*()*) 2v, | S 40, || < 40Ç.
(68)
(69)
Moreover, for every i E jn],j E [ma]j] & for P defined in MI we have that sign((W} + ())x,,))
and sign sign(W;(0) (w z4) are the same.
Proof of Theorem !
Let T E [i be matrix whose rows orthonormal basis for the space of matrices whose rows orthogonal span (z.) i.c. Φ defined in (D2). Then, we consider linear change of coordinates for the subspace o regarding the second layer weights, as o' = (Ve" where vec(.) splits out the vectorized version of a matrix. For consistent notation, we also denote w' W", so we now have a new coordinate system (w', x²) E IR (m -n) xm,d for pairs of weights (W', V*) such that V We also define the loss function
I." (w == (w', ((,,'')) L(W", V'),
with respect to the change of coordinate.
Now it is easy to see that running PSGD on L in the normal coordinates is equivalent to running stochastic gradient descent on I." with respect to (w', v'). Moreover, because multiplying to matrix T is an orthonormal change of coordinates for & and because V is already in o at each step of PSGD, then ||v'|| = ||V'|], so the conditions ||W'|| S C1, | V < C2 are equivalent to ||w|]| < C1 ||l'|| < C2. Furthermore, by construction, the random matrix Vş is in the subspace $- so the norm bounds ||W*|| & (1, [V*]] I Ç2 are equivalent to | I (1. ||'"|| I C2 for w² = WE and 8-' Tvec(V*).
Now we apply the result of Theorem f on " with parameter v set as 1/ (recall the definition of 1/' from Theorem B), Ç2 = and (
and A == Rn(J"), as defined in Theorem E More specifi- cally, based on our arguments above regarding the natural isometry in the change of coordinate, any
pair (w', v') in the domain ||w'|| < C1, ||o' < Cz. L'ww,, v') (f()*) ) + v/ translates into pair (W', V") in the domain ||W'|| < C1, IV < C2. L(W", V" Z R. Rf( + v', for which by
Theorem there exists (W5, Vi5) such that
L n/2w" VTW V n/2V + VTVE) S L(W", ((W.v') /
(70)
Translating back to the change of coordinates:
ExL - nn/2w' + Viwst, n/2n' + vTos) & L(w', o') mp/ /
(71)
Now apply Lemma B0 to translate this into argument about the landscape of I As result, applying the bounds in Equations ((U)) and (I26), we obtain that for (w', v') such that
L 1 o')
25

---

Published as a conference paper at ICLR 2022
should either have
v/4
VL"
(''''')112
4 W 12 + |0||3
v/4
16 16
or
v/4
Amin (wd,,))
s 2 ming (1/20(/100 112 | + ||0113))
2 ming (1 V 2)
S 16(C1 + (2)
16(1 + ()
Next, we want to apply Theorem D by setting
16(1 + C) N, Rn( +
and Lipschitz parameters Pl, P2, P3 poly( B, C1, C2, mi, M22, ma) set as described in Ap- pendix B. Theorem g. Also, note that as prescribed by Theorem D. we set
N + 41
C ==
11
C2 = N + 41
(72)
2/2
where 1 = O(1) depends our desired chance of success for the algorithm, specified in Theorem M Finally, note that Theorem @ needs to work with a bounded noise on the gradient whose covariance matrix is bounded between two multipliers of identity. The point of injecting extra noise SGD in PSCD is in fact because of this covariance condition that we need in Theorem D. On the other hand, note that in general, because of the gaussian smoothing that we use, the noise vector is not supported on bounded domain, which makes it a bit harder to apply Hoeffding type concentration. To remedy this, we introduce a coupling between our unbounded noise vector for L(W", V') and another noise random variable whose support is bounded, which with high probability is equal to the real noise, along all iterations. In Corollary, we further translate this coupling for the objective " after change of cooridnates, and write down the exact dependencies of the parameters Q, 0 and 22 which are all polynomial in the basic parameters and the overparamettriizatin..
Hence, the conditions of Theorem M are satisfied, poly(P1 (P1, P2, Ps. Q. C2, C2, 1/7, log(o1/02))
conclude that after at most poly( B, m1, M2, my, C1, C2, S1. (2)
poly(n, B 1/B, 1/70) number of iterations, PSGD reach point wi in some iteration & with L ( < Rr.
Translating back this wi (wh, vf) by multiplying the vi part TT, we get pair (W7, V?) with objective value bounded as
L(W", V/) S Rf(())++) +v'.
(73)
But note that we obviously have the condition ||']| S Ci |V S C2 through the whole iterations. for the choice of C1, C2 in Equation (Z)). Therefore, using Lemma for every e [n]:
( = OC11, C2), Ifw (2:) = OCC1, Cz)
(74)
(75)
26

---

Published as a conference paper at ICLR 2022
From Equations (75), also stated in Theorem H. we know that for all [n]] {(., Uc) is (())C2) + Lipssccciitz at points fwi.v((a)) and fw (wrvv((a)) (T;), so we can bound the difference Je(frr y (1:). Ui) ((fw vx (x;), Ut)l by (O(C)C2) + B') ( (x,)), 9:) fw", v (2:)], which turn can become arbitrarily small having enough overparameterization using Lemma 655) partic- ular, we force it to be smaller than O C2)) (recall v 2 v/2 2 B B2)(2n)) As result, we get (eS'". (xx) y:) (T:):, (1:)) = O for every
[n]. which in turn implies [L(,", V*) - L1 (W", V*I - by picking small constants, where recall that the objective L1 the
same as L but without the smoothing. Now applying this bound to Equation (773,, we get
L1WW, V( S R. (f*) +2''.
Therefore, as PSGD check the values of L1 in the loop, it terminates at such pair (W, V2). From this point onward, we refer to the returned (W,, V7)) as just (W", V*).
Opening the definition of L1 (W', V*), we clearly get
R Rn vi) & La (W', V*) z (n( 2 (n" + 2v.
(76)
Furthermore, noting the setting of th tt2 in Theorem El and the fact that v/ 2 v/2 (n get
|W] & 4f +2v') || < (f() + 22/) < 406.
400
(77)
V/
(78)
which completes the proof. The fact that for every E [n], E [mi].] $ P we have that sign((W])) wy) vx) and sign(W) x;) are the same follows from Lemma M
27

---

Published as a conference paper at ICLR 2022
A.11 RADEMACHER COMPLEXITY
In this section we show the proof for our Rademacher Complexity bound, which is used in Theo- rem B
Theorem Lef G n2 be the class of neural nets with weights (W,V) in our three layer setting, such that IW - || V 7t. I V V0 I Y2. where for every E [mg], i [m]] Vj 1 (())), and for every E [m], E [mi].j & P for P S [mi] defined in Lemma 01 it satisfies W))x)) sign((W;
sign(W(") Then, for large enough overparameterization, we have the following bound on the Rademacher complexity:
2 vn
R(G
Proof of Theorem -
Here, we do not have the smoothing matrices Wo, V anymore. In this section, unlike the optimization section that we used {- denote the output of the first layer by incorporating also the smoothing matrices, here we define it without them:
x
W ((Wo( W)),,).
m
Now define the matrices
Z 1//m22 aj (V, x 2 0}u;) ma
j=1
zz- 1/ 1/ 4j (1 (V 2 0)
x4 2))
To bound the 2 part, note that substituting C1 by 71 in lemma B and assuming conditions
(mm4)
m.
20///2 n n2m3 1/4 < 71
VF
m1
(we can use this result because we do not have the smoothing matrix W here), we get with high probability over the initialization for every E [n]:
(z,)) = ||l| Φ (0) (x))) $ n
(79)
Therefore, write
|trace(V V (VZ (
1
Σ aj 1 (iign(( A sign(V, <,)VV,='1
/mz
1
Σ
(iggn( v,,z,) * sign V VVHVl
m
2 S (V,, )=1 (I(V, - 1/10)) Ju' + 11,001111
m2
J.
x < (V. )411) (2((V, v
Vmz i
J.
1(V 21 1V, - )aو| < 72
2/3 K2 11/ min(n bx(l)) (2((V, - v/!0)aa)
mm 3
1[(VV - )00)4/1 2
2/3
K2 1/3 min(m, || (2((V) - )/00)a1))
72
m2
28

---

Published as a conference paper at ICLR 2022
Now using the fact that V v/
is orthogonal to g) (w:) Y's:
212"
2/3
N2 111371
v LHS
mz2
Σ
5.
(0)
x/ S
72
2/3 1//8
/mz
m2
8
2
Σ 1[lls, - " |||| 2zx
2/3
/ ) 70 V
-vo00 I1lx, -z.)
+
72
Vm2
m2
Next, using the upper bound on | - (x:));
2/3 K2 311371
27/
LHS
2
mm²"
Σ (1 10)
+1 S
12
2/3
(
K2 1
|2
Mm
m2
71
- 11 ス
2/3
K2
3/33, 1
72
/22
m2
2/3
1/3711
72
Σ (n (1 (0) xf1l S
2/3
K2 1/3 [
72
m2
m2
11l1, 1000 12 72
1/3
R2 )2/33
Σ Il(.. D1
m2
m12
72
2/3
mm
///3/11
Σ 1I
J.
2/1l
72
2/3
+
23.1
mm²2
x
m2
K2
1/3
722
2/3
1
Then, applying the first argument of Lemma PM we have with high probability over the randomness of (0):
2/3 K2
/1/3 1/311
LHS
22
ma
m2
R2 )
1/3,2/13
2/3
32 21
m2 )1
1/3
Vm2
122
m2
\/m22
K22
72
2/3
7/2 7/1
4/3
72
4/3
( / 1/33 1//3
(N2v/m2) 1/3
4/3
7/2 7/
(A2v/m2))15
29

---

Published as a conference paper at ICLR 2022
Therefore, write:
E,, E. sup
<lv;w(x;;
n v.WES
1 - E sup v.WES
Era Th a(1
= Ee sup
Ga a (11/m22Vr,
n V.WES
1 E, sup sup
trtaae (traceeV(ZZ) + zi²))
n WES VES i=1
4/3
1 E. sup
t,trace (VZ;)
7/2 71
n W.VES
(162 ( m
4/3 72
1 E. sup sup (vace(V(
7/2
n WESVES
(x2V/m2) 1//3
1
- E. sup sup trace((V - V(0)) )( eiZi))
π wes ves
1=1
4/3
+ E, sup trace (V (ZZz)
7/2
71
(80)
(K22 (o2y/myy)11 1/3
WES
For the first term, for every E [m2], define H, to be the set of i's in [x] where the jth column of Z non-zero, i.e.
H, = (i [n] v 2 2 0}.
Here, we use the crucial assumption that (V V(O)) (z,) 0, so we can drop the (0) term when xf is multiplied to V(0), Using this trick and applying Cauchy Schwarz, we bound the first term as:
E, sup trace((V - v(0)
G (2,)
n W,VES
1
< E. V -v
sup WES
m2
iEH,
Further using Jensen's inequality:
E, sup trace((V- - )()) Σ 222,)) W.YSs
IV
|
1
E.
sup
Σ
(x:)11
(81)
m2
WES
Using Equation (I of Lemma (note that we do not have the smoothing matrix W here, so we are allowed to use this result), we obtain
20/3/2 Vkn
ndmp 1/4
[I (0 2 - (x:)) S
mm
where S are defined in Equation (317)
Plugging this back in (II):
30

---

Published as a conference paper at ICLR 2022
E. sup WES
Σ (x)))1 fE
20
n'm3 1111) 2
< R, sup WeS
G(W W ;
mi 20
iEH,
C
n n2ma 11/2
S E, sup WeS
(W 1 11,
K1
m2
He
E. sup WES
mg
trace((W - w (
Σ
2
+
C
2 m 1/2
(82)
Ki
mi Ao
iEH
Now for every fixed dataset, with high probability over the randomness of W for every 1 # hiz:
Σ
k1
Σ
<
Σ
( )
VEH,
Σ
W W kiJ k2. (as, Fio 11W xs, 2 03 It2 2 03
H 1=1
But note that because (p1,, S 1, the variables W W (2t, T. 1 (W 10) (3
J. 24 >
J. 2t, 2 0} are subgaussian with parameter one with respect the randomness of W Hence, with high probability over the randomness of W we get
< iEH,
Σ Ez sEH;
Σ 11,
mm S
n² m
(83)
mi
Therefore, with high probability over the randomness of W( and W and the dataset, we get Equation (83). In order to get rid of the high probability argument the dataset,
the stronger Equation (6I8) in Lemma HM which uniformly bounds (7k, (I), 7xg (x')) by log(m1)d/m for any
ar which in gives
n log(m))
Σ iEH,
Σ SEH,
Σ
S
vmz
EH,
with high probability, independent of the choice of dataset. This bounds is slightly worse comapred to (83), but still efficient for our purpose.
Furthermore, similar bound to Equation (X3) can be obtained in more adversarial situation when we also take maximum against the choice of the dataset.
Note that the entries of EiEh, e, for 1 k S mg can differ only in a sign. Therefore, their norms are all equal. Now suppose that Cj the random variable of the norm of these variables:
C
1
iEH
Then, by substituting Fh = t Eien, &Z in Lemma 20 we get
mg
Σ < (3 + m n2 nodlog(mi)
(W
- (84)
Cm,
VEH,
n² n2m3d log(1)))))
= =C² +
mlll w.
(85)
mm
Now recall from Equation (7)), we have
1 (x:))l) S n.
(86)
31

---

Published as a conference paper at ICLR 2022
Hence, apply Corollary 5.10 with (z)) and C1 substituted by (z(z)) and n respectively, argue with high probability the initialization, there exists set P. such that for every [n] and & P., sign of V T xt is the same as V/ T (00) (xz). and moreover,
P (m3r7T
1/3 m2.
Now let
= (ie Vj 100) (x,) 2 0}.
Note that for j P - we have 11 Hy Now note that the norm of each LiEH, c is at most one. for each index 1 S l S m1d, as the random variables Eien, <i(z)); ) are Dien, (Z%) < Eigln (2 subgaussian, we have with probability at least over the randomness of e,'s, for every < l S m,d d and every S S m2:
Σ
(Z log(m1
iEH,
iE|m
which implies for every j E [m2]:
|| Σ aZ 1|
(z log(mod) S log(m1dmzz))
i
8 #E|n]
Name this event B,
P( < -
Note that although H, might depend on the randomness of e, 's H2 does not, and if j & P, obtain
C -1 Σ az / n /ngggmm dmzn).
iEH;
Moreover, note that also have the following worse case bound:
C = Σ a
S Σ | S.. n.
i,
Applying the last two incqualities into Equations (297) and (35)
E,
sup
|1 Σ
m2
WES
KEH,
C
n m 3
m2 E. sup WES 1=1
ms trace((W - ((0)){
1/2
Σ e, c,2tt)))
11
m Ao
m2 j=1
EEM
C
n m'
1/2
1
E, 1BB)
Σ(C² +
n² n²mzdlog(mm))
}|| }| - -w
m.
m2
Vm,
jeP
1 E. (B3)
n² ndmzdlog(m
[C3 Σ(C)
|| -
m2
vm,
jEp
1
m2
n nmmz a log(m))
+
E. E.
(C2
}[[ - -
m22
Vm
1=1
CH
n mm
1/2 + W - (0)
PP|
n2 +
n² n²mmd log(m))
+ +2(n+
n²
16
mi
mm2
Vmn
Vm
C3
n² n'mp
C2
C²
1/3 1/ log(m1)
n² n2mzdloggme
K6
mi
1
1/2
n
(mzn?))
1/3
(mgret)
Vm
22
Vm
+ 2n
(87)
32

---

Published as a conference paper at ICLR 2022
Next, analyze the term E. sspwes trace(V(()) (E= i==1 eZ,)).
Noting that || (x;)1 x
Ki mmy with high probability and using Equation (NG):
| - Σ (2:)(( + (z²0)) & m(ymgki + +n). (88)
i=1
i=1
Hence
2
E. sup trace( V(0) Σ
e (Z
Ex sup WES
E t,taace( (aaacee(V() (1) zi)
T
WES
Y1
1=1
i=1
m2
ag V 4. 1V 4, 2 03)
(0)
(0)
E, sup 7 WES
Ej
M2
n
1
1 a² ((V()))))
Ex sup
Ei
L "V(( x1) S sup
(0))
n
WES
m2
wes mm
But using Lemma KT%
LHS S Ko / ||
Applying a similar bound as we did in Equation [ا on |
| [] (a:)] + 1 (z+)l S Ni vma 71-
Substituting above, we get
E, sup trace (0) Z() S SaymglHivmy + 71).
n Wes
Finally, Substituting Equations (87) into (8I), then combining it with (89) into (SL). we obtain bound on Rademacher complexity which holds w.h.p over both the randomness of the initialization and the dataset:
C n²ma
R(G S
V
11/2
(90)
K1
m1d0
712
n
n
(mzk?)
C7
1/3
(mati))
C7 1/3n9m3dlog(mm
v m
+2
n log(m1)
mm
+ 2n
(91)
4/3 (R2 )1/3"
7/2
m
+ Ke +1)+ +
Having enough overparamettrizaaton,, we have for every dataset v) (i.e. worst-case Rademacher complexity):
R(Gm,,x) S 2//22//n.
(92)
Note that for the bound (52) to hold, the overparameterization should be picked poly large in 71, 72. as well in other basic parameters. However, noting Equations (89) and (bG) in the proof of Theorem 3 we set 71 1, 72 2 Q(B,n, 1 //20) in Theorem R. so 71 is at most poly in the basic parameters. Therefore, again the overparameterization can picked polynomially large in the basic only parameters (i.e. independent of 71, 72 or ().
33

---

Published as a conference paper at ICLR 2022
A.12 CONSTRUCTING W", V
This section consists of two subsections; First, we prove a structural result for the first layer weights (W", V") that the algorithm visits, then construct weight matrix W for the first layer with some good properties, Second, we do the same thing for the second layer (however, the structure of the first and second layers are completely different). Through this section, we assume we have the norm bounds ||'|| & C1, C1. & C2.
Notably, rely on a number of basic Lemmas more related the representation power of the network, which we defer their proof into a later Appendix B2 and refer to them here as needed.
A.12.1 FIRST LAYER, CONSTRUCTION OF W
Lemma Suppose m. 2 16n2m3//B \B. Let P. {i [mi]] [
x.1 S c2/ me// and P UP: During SGD iterations, suppose we have ||W]|| S C₁. Then, for value e2 satisfying
201 smm/n v S 02 S /m1domm1/221
with high probability Vi:
PI c2vm,/nn
for & P. during the whole algorithm we have
|[W]]| /nmaCr + c2/(m/)) S (2/(m)))),
Vm1AA
02/ m S [ xzl.
So the signs of neurons outside P never changes. In particular, we can set C2 as small as C2 C1 //mm// Vdg- In the rest of the proof (i.e. other sections), we set 02 to this value.
Proof of Lemma
Define the matrix
1 (W (i W x; 2 c2/Vm//33 Vm
2%
Let P. be the set of indices j such that 1[W (T x, 2 02/ m zero. First of all, note that by Bernstein inequality:
P. 120/m// + O(y (ll/ev/mm) c2/mi//i + 1) S c2v c2/m,
Now suppose that until the current iteration of the algorithm the assumption has been true, i.e. the signs of the neurons outside of P have never changed. As a result, due to the specific update of the and || if we define W'|p be the restriction
SGD for both of the terms Ez (z), y) of W' to indices that are not in P (i.e. the columns in P are equal to zero), then we can write
W Σ
(93)
An issue here is that we also have some injected noise by PSGD into W' which violates Equation (К3) To handle the injected noise as well, we define the subspace क' of Rm xe matrices be the set of vectors with arbitrary rows for j E [m,] with j E P. while restricted to the other rows j & P in should be in the span of (.)),.. Then, decompose W" into subspaces o' and s' respectively
as W = (1) + (2()), where (r((1) Φ', w2(2) E क/1, Here, we want to prove || <
c2/(44/m)) We handle the || || part in Appendix 45 So instead of W' in Equation 1 we consider W1(1))
mg
will]
OR
Zi
(94)
34

---

Published as a conference paper at ICLR 2022
We handle the other part W in Appendix g5 we can state with high probability
Now exactly similar to the drivation in Lemma BX
Cf z || 2 p1 z ||
mg
0u 2,11 O(mma/ Haam///m) Vm,) Σ 11ax|12
(95)
k=1
Note that we are exploiting the fact that the norm ||'|| remains bounded by C1. Now using Hoeffding bound for matrix 1/ defined below, we write:
H oo/ 11 = 20 1 |w" æi 2 02/ pe/Vmija,,ee Jz (1(w"x; In 2 201f Iis 2 0})
= =Eu.N(o.Re) (1 f 2ú, 2 0) Iı, 2 20))=TT0. 212
+ 0 {3: Iwo T nil S ca/Vmn)(( {w on 2 031 012 2 03))aT,01
= - + ( m,
ki) ||, I,11
= - + O ()),
(96)
Now opening Equation (55) and using the property 02 S /1 we get
LHS ΣΣ
2 - ( h/mms///mm Σ akii 0 (2)
||
k 21.
ΣΣ
Oi 0 (H 81,42 - O(1/vmm,) - (1mm///mmvvvmmmm/ / m1 Σ llxxl3))
h 11,62
Σ
Σ
ak 0K H = | (1002/ / - ( mm Σ |laxe1?)
k 11.82
Σ
Og
H
as 0 m2)i) Σ | lli O / /
|| 1?)
2
Σ
og
T H
H0 ak O /mm k1) Σ |aal12 -mmmm/ / Σ ||xx
(Ao ((nna///mmii - /MM
Σ |aall
k
2 2 Σ 1|ax11
For the last line to hold, we need enough overparameteriiation. This implies
Σ
||al| $ 02/20-
Now again, exactly similar to the derivation in Lemma 6% for $ P
we have
j & /nmss/ ym
|aull S /mgnC1///mm Vmzdo Σ
which completes most of the proof. For the rest, we are left to show that for the other part Wr(2) we have || || I (4/m4), which we do in Appendix ES
Lemma Under condition mgn/ m S Ao/4, there exist matrices {W:]ms mg every ht o k' E [ma] and i [n]:
Tk=1 E R xd s.s. for
(WE. 43/) = 0,
I - w S ny m/ma
| H
A mm
ni /V
KWE, % (Wit / S
|| ix.
do doyma
35

---

Published as a conference paper at ICLR 2022
Furthermore, for 1 # lz
vma
vmg mm
KW
Wh
S
+
Via H~
11
(97)
Xg mm
Proof of Lemma
Let
W = Σ Va
want compute the norm of the projection P(W))) of W onto the subspace spanned by all Z for k' + k and i [n]:
|P(WT II (WW Z (Z) zK:) )
(M (00 (WW Ziz) x (e)
(98)
where the first and third terms vectors and the middle term is matrix. Now note that for each k, ki, 122 + k, by Hoeffding inequality:
( 233)
H0 + (+1 /ml ( (2(m))
(99)
(Wit 21,)
> Vk. Zzz
2
Σ
vm,
Vn
||Vall
vm
vn
H
(100)
v Vm
Therefore,
I Di #R.se
S s
m3
|[ H
H
(101)
Now Equation (99) implies for small enough mi
Amsn (1Z Z
2 00/2,
(102)
as long as No 2 2n/n m2. Moreover, define Á to be the block version of
A' = ( (42t))00tas4)(emma-0cxxxxx
i.c. for k = 12 they are the same but for Kn + K2 A is zero. Then
Amin (ain(A) (A) 2 An/2,
because the cigenvalues of each block is at least Ao/2 2 using Equation (102). But note that
IA' Ālla & A|' Allr S mzn/ /mn.
So as long as m3n/Vm, & Xo/4, we have Amin (A) 2 0o/4. Combining this fact with Equa- tion (IεεI) and plugging into Equation (MK), obtain
n² ms
P(W k 11
S
mi A
36

---

Published as a conference paper at ICLR 2022
Now define W3 W - ). Then
nymy V
| W || |P -
m m1
nV
kWT - W x - P(W |||
Aumma
Furthermore, note that W is orthogonal to W for l # k2
kW W = 1( - )( W
((P(W)) W P\
s (IP(W IIl )(WE))
s IP
(IP(W
(103)
But note that
| = Σ Va,
2 S Σ 1 Σ
Valil S Vnl/Vll2 S v
Melll
An
Therefore, we can bound Equation (103)) as:
KWE W y
S T
(1
+
Ii, 10 |V
X
Vm
Lemma There exists a matrix 2 such that for every j E P. W = 0, and
|race(W 2 Fiaal S Ciymann (Agki mm) Vi 1,
Proof of Lemma
Define W to be equal to Wr for j & P and equal to zero vector otherwise, Then, by
Lemma (note that P. S C /nmay/mm (V/(())
(race(W," 2 trace(W, 22 1/Vm,
W Jay
m
v /nms/ (mi / Ao) |ll
S Cyman (ongn?/(((an) ((0o11/m))) [elll
Combining this with Lemma 37 the desired result follows.
Lemma Under condition m3n/Vm, S >a/4, 4, there exist matrix W 's exactly satisfying the same conditions in Lemma but with respect to W instead of W and moreover, for P we have W = 0.
Proof of Lemma 4
We repeat the exact procedure of Lemma 2 for W Using the bound in Equa- tion (27),, we have
(1Z2) ((3) (n.2
10000 + +0(+1//m1)) mi)
0 (#noz/ (mmna +0+1/
00 (#noz\ M
37

---

Published as a conference paper at ICLR 2022
long n2o2/VmiKi n² Cii/na//(e (K1 v mm1 S 20/2.
with similar argument as in Lemma 21 we get
Amin (2 222) 11,62E(n]
2 10/2.
Moreover,
(W+2. - =
Vk. Zi Zid) x Vm
E Va.l
|
vm,
vn
Vm120
Thus, using the same argument before the proof is complete.
Lemma Suppose
my 2 n² n/ma// Ao-
During SGD, suppose are currently at (V', W') with W < C1. For any matrix Wi, we denote the signs of the first layer imposed by W1 by Dw Then with high probabilit, there exists
W Eke[mal W such that W 's is orthogonal to all other Tie 's for k + k, and for every
i [n]. we have:
W W* Dwo W'x, - 22:l000 S Vm
113
1 +
nC1
[ = 1/
Vm do
Moreover, we have
|W7]| S Vnmag/ (V
|1 |1
nymy
11a1l110=) = ev
m3
(104)
/
Particularly, for any diagonal sign matrix E Rmaxmm we have
W n n
mg
mmg
+ (1 (nn
n² n²m3, 1))
Σ 1 12
(105)
13mi
m1
mm
which, by having enough overparameterizatioon, implies
Well S
$22
2
Velli = V25,,
(106)
k
where
W
Σg W
(107)
1=1
Moreover, we have
1
W D W(0 WSx; = Σ
W Dwio W"
(108)
m
Vm
Proof of Lemma 5
From Lemma g we have
Tiik trace(W:+2
Ciman? (Aars /m1) Delll n=.
38

---

Published as a conference paper at ICLR 2022
Combining this with the result of Lemma RI get:
mvm3
Cimgn
Fi. trace (race(W
V
\
Aghi yin
nmng
1
nOI
(109)
On the other hand, based on the property that W for j E P and its orthogonal property from Lemma Ml for we get
W F&Dwown ww W'x;
W WrDon W'x; Iz trace(W" % trace W %
m
Vmn,
WfDw 2. WiT,,
Vm,
which combined with Equation (IU9) completes the proof. From the above, Equation ((OS) is also clear. Finally, that by Lemma GS have
[ bll z Vnmaa/( mi Ao)
Σ 1|
which Combined with Lemma @ implies
|Wy]l & /nma/ m1do) Ao)
Σ IM
nymy A
[| = -
mm m2
while the other claims follows from Lemma and Lemma ! combined with Equation (977):
Σ 1 Σ
IWW
W
k o
Vmg
Vmg mm
1
1 )²
X3 m
Vml
Vmn
1
(1
V
1
AB m
mm
/ Vml
Vml
1
[[
X mm
mm
n/n Vmg
Vm
n²m3
(1+
S4 +
||
Σ ||
XB
Vm
mm1
nvn vmg
Vma
SC +
W
n n²mm
Σ ||
mm
Vm
k
*
n
VTll
Vml
n²mm3
Ci (1 + O Om/
13mm ))
X mm
mm
Next, to construct V for the second layer.
12.2 SECOND LAYER CONSTRUCTION OF V
In this section, we present couple of lemmas that step by step lead the construction of V*, remind the reader that ((() (I;) is the output of the first layer at initialization weights, o' (x:)) and (xx) are the changes in the output of the first layer when W and W + We are added,
39

---

Published as a conference paper at ICLR 2022
respectively, and finally Ø (2:4 is the optimal features that are generated by the matrix W but with the sign pattern of (()) W i..
6 (z,))
W DWoo W',,
Vm,
We also define x/ as
1
2 = 0 00) (I.) + t (x,)
W o(W(( + w + W))z))
=
Vm,
To begin, we state a lemma to bound the magnitude of [z(()) given that the norm of W is bounded by C1 and the sign pattern Sgn Sgn(( (( W') satisfies condition stated for the set of indices Lemmall MI Later on, we exploit this Lemma Lemma 3 state bounds for ())))) (x:)]l
Lemma 6 Let the matrix W with norm bound [W'|| S C1, such that the signs of (Wj + W))a: and w w(0),; can be different only for P. for P defined in Lemma I (Note that for W every step of the algorithm, this is automatically satisfied by Lemma ( Then
20
n'm²
(0:((
1/4 + +1 O //mg///m))CC.. An
VF,
Particularly for large enough my compared to n, m3, So 1i, C1, we have
[()((x)) S C1.
Proof of Lemma f
We write
(d)()))) (W", 2b>1 2/ Vm/
Waar S 22/mm1
jEP
jEP
20
n m3 1/4 m1 Ao
$
2 htPP//mmllW/ m W'
(110)
Vkz
where the last line follows from the bound on P| from Lemma III On the other hand, because by Hoeffding we know that (Zi, Zi,) S 1/ 1/mm, by Lemma !i
we get
mg
Σ (W' < (1 (1m < (1 + /
A=1
Combining this with Equation (II)), we get
( S
(ax) (W', (W' +
Σ (W", Ew", z3)2
V
x <
20 n n'm3
11/4 + (1 + /
(111)
Vkz
m1 Ao
Next, we prove structural lemma regarding the sign pattern in the second layer when feed in of it, with the important message that the dominance of sign patterns are specified by ((0) (x:).
Lemma 7 Suppose we have maK 2 CR. K2yT2 C2 and my satisfies the condition Lemma Z If we have the condition (I:)) S C₁, which happens under the high probability event E defined in Lemma 33, then for every i [ni), there exist subset P; which might depend on W(0), ((0), W V", such that
1P:1 S (1
1/3 + (c3 + 3mgng ((mggt))
C7
C²
)(
C2
1
1/3
m2
125m2
40

---

Published as a conference paper at ICLR 2022
Moreover. for every i E for j & P..:
3 1 ( (mx)
1V, d (1:)) + (v)(0(0))
(z,) + (z:)))
(
K2 )
2/3
03 (x,))l
m2
1 10
(z.)
1/3
2 03 |
m2
Proof of Lemma
By assumption, we know that during the algorithm, we have |V|| & Cz. Also, we know by Lemma 33 that under E
(x))ll 2C2.
Define the set
P (0)
(x;)) Sa
K2
1// C2
2/3 16
(2:)1l}
(112)
m2
and Pt UP/. We have
P(IV (x,) S cz
K2 1/3
C
2/3
(0) (x:)))
S c3(
K2 y 1/3 2/33 /62
m2
so by Bernstein, with high probability:
122 1/// IP S C2 cal so with high prob.
/ /w2 +
m2 2/3
/ R2 12 c,m2 c3 22/3 (22 22/3 1//31p1 182.
K2
cs(
m2
m12
1712
IP S Ca
2/3
m222/33
m2
(113)
182
On the other hand, Note that
171
(1r4)
Σ f=1
1/ Wi, x:))
(114)
subGaussian with parameter 0² 011mm, E, (W, 22) Furthermore, note that if we com- pute the variance of o% (a:) with respect to the randomness of W*:
(0)
Eob (0)
(z:)²= (xx)² = 1/m² (w (0) x3
a, N
which itself concentrates around 1/2m | 1/2x3 by another Bernstein, i.e. N 1/2xf(1 + 0(1 fmm) )). Therefore, by concentration of subexponential variables (Bernstein), it is not hard to see that the squared norm of the vector (0)) (I;) is (mant, N2) -ubexponxnolll and concentrates around M i.e.
()) 12 = maN + ((k m O(ma MMm,) + OkI
(115)
with high probability. Combining this with the fact that (x:)) S Ci implies with high proba- bility:
(,(00)
vmzK1
(116)
(x;)) C₁
Now define P." = (il [V/=a1|
2 | (0) 1 (x:) If j E P. P. then by Equation (L.)) with
high probability
= (0) (..) 21 |V
41

---

Published as a conference paper at ICLR 2022
2 1 00 (m:)1/33 ca(
R2 2//3, 16)0 (3:)ll
m2
or
A2 2/3 /33 M3ni
1 ス
m2
Cf
But note that | v C2 by our assumption, which implies
IP" - P.
42
4/3 mahi
C2
22/3
C7
m
m2
(117)
C9
m2
R2
Now combining Equations (TTE) and (ITZ)), we finally obtain
C2
IP'| = IP." P +
S (es +
)02
( )
G3mant
2
K2
Now define the set
= (il ( 2 IV; (0)
(100 (rx)1/33.
(118)
Note that for every j [ma], 1 1100 (I;) is gaussian with variance ( (x:)ll over the randomness of (0) so
P(V, (1) 1 (x,) 20 Sa.
Therefore, if we define the set
Q₂ Lie [me]] 1 (0) (xx) < (x)
then for large enough m2, by Bernstein with high prob.:
10 S amz.
(119)
Now note that (00) (1:) is fixed during the algorithm. On the other hand, by random matrix the- ory, know that with high probability, the eigenvalues of the matrix V are in (Kz(Vm,
( + /) Therefore, even if the vector (x;) is picked adversarialy (because it keeps changing during the algorithm), we get that with high probability over the randomness of (0))
[v (z)) S (V + lo (x:) X (x)))
(120)
Moreover, because (x))) & C2 and from Equation (15), with high probability over the ran- domness of (
(x;))
Migh1
( (z:))l
Ci
This means that for j P!" Q. combining these inequalities we conclude with high probability
Mmgki
(c)) 1 (1)) (x:)1/3 2 aN2 (xx))l 2 an2
Ci
which combined with (2)) implies
m2 m2C
P
S m
Balancing this term with the one in Equation (I14)
we set
2/3
=
1/3 2/3
m3 K1
which implies
C7
|P' S |P"
Qil 1 1Qi1
(mgN??
1/3
m2.
Defining P: PM U P!", we finally get
Cf
|P (myx?)
1/3
(cs
Emar
2/3
k3m2
1/3
m2-
Clearly by the definition of PM" and P." the proof is complete.
42

---

Published as a conference paper at ICLR 2022
Corollary 5.1 Under the condition
| (2.)l E C1 (which happens under the event E defined in
Lemma 55), setting Cg
C2/3
MA
1/3 in the previous Lemma, we obtain Vi E [n]]
mg
175
2
IP S
1/3 m2-
m
Also for j & Ps, the conditions in 112 and
(T becomes the same as
C
()) (x4)
62
1/3 2/3
(0)00)
(s:))l-
m3
K
Hence, for every i [n] and for j & P., with high probability:
2 | 10)) (x:)] 2 |w 20 (x:))
(w) + (x:))
(121)
3
C 2/3
(x;))
1 (x;)) 2 <2(v ,
(z;)
(122)
1/3 2/3
mg
2/3
w 0 (x:)
(123)
1/3 2/3
mg
K2
Next, we state concentration result for the gram matrix of & (wi)'s
Lemma 8 For every in, i2 E [n). with high probability over the randomness of ( and V(0) we have
(0(0) (Ii, ) (0) (Ii,)) (xx,)) mg sı, 3o,)oo(W (W,") xin) + O(m3n// + vmghi).
Proof of Lemma 8
First, we compute the expectation:
((d( (x:,), (0) (Iiz)) = 1/m
Σ
Σ
EW Wk (WW xs, )o ( j2 vis)
f1.22((mll kE[ma]
=1/mi ΣEΣ Who, W2 (W Ii, (o
j2 xi.) m3/mi
(0)
o( Ii, )or (0 z1z)
i kE/ms]
jE(ml
But (W (0)
Ji Ti, (W 10) xia) is (mInt, -ub--uub--xpoonntiil so
(W ns )o (w) xi,)) m. m (W vi, )o (w) xig) + OlVm,ng)
jE[mu]
which means with high probability:
((d (xt ), (0) (xix)) mW oi JoW x22)) + O(man//
On the other side, we know that (0) (rin) is subgaussian with parameters a² 1/mz (W,))) )2, = Ri and o² = 1/m1 Σ, (w x22,) = N₂ respectively. On the other hand, we know that by Bernstein w.h.p
N1 = 1/2m3(1 + 0(1/mm))), N₂ = 1/2n](1 0(Lvmm,))
(0) Hence, ox (Ir, j0x (I:,)) is (N, subxxpoonbei and so (6(0 (00) (xx,)),,,) is NMgNiN2, J subexponntial.. Therefore, applying another Bernstein on the top, we get (0(00) (Zi, ), (0)0) (xx,)) (x,,)), E( (00) (I;,)) + O0VmgV/n, Nx,
(2)
(0) z 0 /m/)= + Myz msEo (W, 10) 24, )o (W
(1 + 0(1 vm,))
2
malBo(W (0) Nn, (W
(0) xi.) + 0m1a3// Vmn + vmgns).
43

---

Published as a conference paper at ICLR 2022
Now define the matrix L; E R mm
with its jth column L, equal to
aj ( (xx) 2 (x)).
mm
First, we state the following lemma which characterize a concentration result for the gram matrix of (Lo)=r
Lemma 9 With high probability, we have the following approximation:
(Li, Lid) = (6" ) x (xi,)) Fb (F (F
+ 0(m
10m,1114 + m2 m/
1/4 + my 1//1
Proof of Lemma 9
By Hoeffding:
(Tr Lia) 1/mz Σ ('(a)) ( "z) 2 () (x:z) 2 20}
JEm2
1V, (1:n)) 2 03 (011/vm))) = -x) 1i 0* (Itz F2 (z(, Φ0 ) (2 )) (z,,
= (wi )a 00 (1it)
[E1 (V, (V (xa) 2
= =0(1/ (12))m)))
where recall
(2 1/4 arcsin(x)/22
measures the angle between two unit vectors based on their dot product. Now notice that according to Lemma & with high probability:
(Lig Liz) /00 (xi,), o² (1iz))
5 in (W xia) + (((ms/ m + mmz)m() (malEo (0) Mi )2 O( Vmh (mag) (W,, xig) + O(..)
myRoo (W, (0)
=F2
- 0(11 (11/m/)))
Fa Fa( (.,,) + O(L /m, + 1/1 + =011V\ma))
F2
1/2 + (1/0 + +1//mg
where recall F3 + 1-1/2, 1/2] is defined as:
-1- x x rarcsina xt
F2(x)=
2m
2x
It is easy to see F3 has the property that for unit vectors æ1, 22 and sampled as standard normal:
Pa((x1)22) = Ea(w" x1 (1)
But because |Fa(-) = O(),, we have
(x;;). 0" (xx,)) = F2 (FFF(((r,, x.,,) + + +1//m² + +1//mg))
Now notice that the derivative of F2, i.e. 1/2n x is increasing in the interval (0, 1), so for a fixed 8, the maximum of [F2(x)) - F2(x (ar 8)1 happens
1. On the other hand, by writing the first order approximation of aresin - (2) around = and upper bounding its derivative in the
interval [0, 1]. we get that for s 8 <
arcsin(1 8) > arcsin(1) 228.
Therefore, F2 = = F2(x) + 0(V6). Hence:
(z)) (2.,)) = F2 2FF m(,1)) + 10010111mm + +1/mm, + 1/ mm3)) = F2 2F (Ti, Fing)) + 0(mi -1/4 + m2 + m3 1/4),
which completes the proof.
Finally, we ready construct the weights V for the second layer.
44

---

Published as a conference paper at ICLR 2022
A.12.3 CONSTRUCTION OF V*
Lemma 10 Ler
nym3
1 nC1
R
Vm,
Suppose have the condition that for every & [ma]]
max
| S E,
(124)
where recall the definition of V4 in Equation (58). sure R < 1. Recall for the matrix A defined by
We assume enough overparameterizattion make
A = ( Fi. =ta)))
(125)
ishiiSn"
we have
(()))) S
Then, there exists weight matrix V* which only depends the random initializations W v (e.g. not on and W') for the second layer, such that having enough overparameterization
| 11 262.
(126)
for every j E (m2]:
(1 R+RRaynk
11 _
c 035/ mmz
(127)
Vml
Ce Ex || | = m2/
n(1 + B
(128)
Vm2
do
and further under the high probability event E defined in Lemma
B3
1 | at Dyo -x, -f'(x;)
Ci (
1/3 1/3 + R)
52 2
Mell
Rg.
mm
(129)
Proof of Lemma ItI
Let
V Σ y Lii
be the minimum norm vector which maps L3 f (zx)'ss As result, for the matrix
L (Lis Lizi 61d2
it is easy to see
| =ff (
Now combining Lemmas B and Aill we get
| (2:)) $ <(1 (1+ (1+A))
(130)
[x:)) 5 (1+ R)
Σ
(131)
and
(1o"(x;) 0² (x(x)))) - (ii, Rig>l s (2 x2 Σ
45

---

that one pick choice of constants along the way such that end up with Published as a conference paper at ICLR 2022
Now by Lemma 9:
[Li, Lia) Ann S (2R + Re) Σ
1D (/r=)) F2 (Z)( ( + m2
-14
+ mg 1/4
&
+ other cross term.
By applying (o Fta) - ||:s, | we get
LHS <
| (2 + n2.) F2 2F ( mitll) + (m² 1m4 + m,
1/1 + my 111))
k
Vell m 1/4 + m
m.g 1/4)
k
Therefore,
11A - ((Lis Liz))
S 1|A S ml
(LLi, L 61
||F
Mull =0)= ) R + m²
1/4 + m2 + 114) = R2.
1/4
Note that R2 naturally goes to zero (with poly dependence) as R + 0 and m1, m2, my are large enough. Now if all of the eigenvalues of the matrix A are 12(1/n2), then if we overparameterize enough such that R2 = O(1/n²) with small enough constant so that R2 is less than half of the smallest eigenvalue of A, then for the ith eigenvalue A, of A and L we write
ALL 2 (AAA R2 2 A(A/22.
so
$ S(L-1)32X(A4 22
which implies the property
13 S 2C2-
(132)
However, A might have very small eigenvalues. To remedic this, use Lemma 17 tute fr with some for such that
substi-
Ra( S (R* B A- A-'S""
(133)
n
(134)
where fo on the subspace of eigenvectors of whose eigenvalues are larger than Ω2 But it is easy to check that in the context of Theorem such substitution results in f-TA " f S
feT A-1 < ( and o(f") parameter (as defined in (EII) with respect f" which satisfies 0/2 S Note that the algorithm is with respect to the setting v, however we want to exploit generalization bound with respect fo whose parameter is
enables to use our analysis this Lemma. Furthermore, note that using Equation (IK)) we can further upper bound the empirical risk of f with that of f", which makes it straightforward with respect to f", of course with change of constants. Note that f is just the sum of A-eigenbasis directions in f" whose eigenvalues are larger than 2(1/n²). Hence, given a pair (f*, G), we also point out in remark II, we can construct the suitable pair (f*, G') algorithmically and then use that pair to initialize the parameters of the algorithm (namely Ç and v/). Otherwise, if are not explicitly given a pair (f*,G) and instead want to run the doubling trick described in Theorem M. do not even have any additional computation; since using Theorem II. within the framework of the doubling trick, the risk of the final network is competitive with respect to any choice of (f", G). Note that as we mentioned in Lemma [2 the constant is arbitrary and can be reduced to any number less than and it is easy a factor two behind the risk (first) term in the definition of our complexity measure.
derive similar generalization bound in (BS)
Therefore, without loss of generality we can substitute f by f and still obtain Equation (132)
46

---

Published as a conference paper at ICLR 2022
On the other hand, the definition of V implies
a Dvw s.
mmz
But note that by Corollary B.I. under the high probability event F defined Lemma [R Ov and +V can only be different in the index set P, and
C7
|Pa| - (mantt)
1/3
122
Therefore, for all i E [n]:
1 a Dv:0++Vi, (3)' (x:)
a
Vod'
mm
mmz
$1/ Σ (x:))
jEP
<1/vm2 Σ
jEP
[V + -R)
Σ 1iVellarr
mm²
1/3
[e( + 9)),
Σ V 11
VmgKi
which proves the first claim. On the other hand, get:
2G2 2 || v 1| 2 vJ LV.
But because Amin (D) E 1/n2, we get
LV Z 11/3/12
which implics
11lla 5 n\//2.
But now using Equation (130), we can write
1 S
Σ MillLighl S /mz
(x:)) Σ M3
(1 + Ri
24
11l (1+ R)VVnlVVl//Vm
v mmz
(1 + R)ny g,
24
Vmz
which proves the other part. Moreover,
11/112 & 24a2
Σ
11 (x)) < Vmz
n(1 + 38)
Co
Σ
|1 11
(135)
mm²
k
47

---

Published as a conference paper at ICLR 2022
A.13 EXISTENCE OF GOOD DIRECTION
Our aim in this section is to show that if the objective value is above certain threshold, there exists good random direction which reduces the objective in expectation. Particularly our aim is to prove the following theorem (informal):
Theorem For a given pair (f* G) with
(H G) Si, 8 (K oG) " S C2,
SA,
recall the ideal random matrices (W V3) constructed in Appendix A.12 where E. is random diagonal sign matrix. Specifically, W is defined in Equation (TO4), and V is the projection of the rows of matrix V onto the orthogonal subspace spanned by (6 (I:)) )=
Using the parameter setting for 1,2
4/.
(136)
4Ci
with respect to an arbitrary parameter v > 0, then for every pair (W', V') such that |[W'|| I
C₁, [[V C2 and
L(W", (W',V)2AM A
(137)
for parameters m1, m2, ma, 1/81, 1/12 polynomially large enough in B, 1/7o, n, C1, C2 and small enough step size n), have
ExL(W' - n/2WW + WWW V' - n/2v' + VTV:)) S L(W", V*) mp//4. (138)
In order to prove the above theorem, we first state and prove the following lemma which is the core of Theorem
Lemma 11 For matrices (W*, V*) constructed Appendix 1.72 specifically for their random coupling (Ws, Vg) as denoted above, we have:
(21). 1) (t.)))((ww....)))). ( + no.
where goes to zero with polynomially large overparameterization (the exact dependence is re- vealed via the proof).
Proof of Lemma
For brevity, we use the notation D.pp here to refer to the diagonal binary sign matrix when the input is multiplied by the sum of weight and smoothing matrices. It will be clear in the context of the equation that what the "input" and the "weight" matrices are. This notation is also defined and used in Lemma 2 Here, we bound multiple cross terms that created as result of moving in the random direction. To simplify the presentation and avoid confusing recursions in the proof, we have made sublemma for each of these cross terms and has deferred its proof to Appendix A. We use difference sub-indices of the symbol to illustrate terms that go to zero by growing the overparameterization in our architecture.
48

---

Published as a conference paper at ICLR 2022
We start by using Lemma 2X.
Ex B::l:/---AN----00.2---------,000
Exe (B.((BWe,,va ( (1- + V' VD + (1 n/2)W" + W vnWE)a
+ (i
-Ey -Eze(Ewe,ys a D: (V(()) + (1-n/22 Vo) D. (W + n/2) + W>)
na² Di Di VE Wi:m + +vßBwr,v aa D. Di + ///3/V VVD D,
a D. D' (w + (1 n/2/ + Wo)
Rgn. 11
Now using the notation introduced in Lemma we have
D (W + + -1- (1-n/2)W" WP)x; "0) + 2 (x))
By Lemma I8 we have the following bound for (z;))(x;)
Ewe.vo mmz az Dvoo + VP + (1 - (1-n/2)VV))dll (z) (d)
S (K2ym2ms + m2 + C2)
Therefore, Combining this with Lemma 2 we get
= =Ext (Bs.((Bw.yv (V. (1-n/2)V (o)W'(((00x;) +1 -1-1/2)00 1/2)
na² W + VTBWrr, aa" D. (V (1-n/22)V &o
a D. VW (1()) + (1 - n///W" + Wo)a;
=0((F2 + 33 + C2) = O(Rm))
-Egl(Ewe.vs (1 1))a" (v(0) + +V VO' (z:)+ (x:))
+
+ D. D' WV W5x: + V.BWervv d (V(O) + - n/2 + V. W5r
+ +aTD. VV D. (0) (0) + (1 (11-n22))W 1/2)W' + W')a;
+ OO((W, + R4 + (Vmnztz + 32)(C1 + Vmy + O(K22/mm2m + Vmy32 + R2) + O(Rs)) vi).
-Bre(11 ( (z;) +
D. p Vr:*
+ VTTWwa.ve [a_ (V, n/2/V' + V'
+ a D'D.,,V (W + n/2) + WP)a;
+ OOn(R, + R. (Vmgtiz + (2) Vm) + O((Kay/m2ms + Vm332 C2) + O(Rs)) v.).
49

---

Published as a conference paper at ICLR 2022
Moreover, using the notation (x;) introduced in Lemma 1 and the bound in Lemma M rewrite the second term as:
LHS = 1..,
( (v + TyEEa,,va (ip + (xi))
+ VitEwo,ve vo aa D. .e (v + +11 - 111-n/22VV/ D. Wia
+ DD VV (W + - n/2) W
+ =0((3l's + R4 + (V (2) vTm = + vm3 + C2) + O(Rss)) w:)
- (1=(((1n)
+ + Da (z)')( "iB
+ VTEWw. a- Di Di + - -/22)1/ D. Wia
+ a" VV (W + (1-n/2)W + W
= O + On + Rs + (Vm3ka + B2) vm3 + O(K22mmmmm + vm3 + C2) Rsn)
0 O(Rsn).
(139)
Now we write the gradient-lipshitz inequality for l at point
Ps = (1 - -n/ww,
-).'wrv (m:) + nBEwevedd Di V V (n:) + n01,
and regarding the following vector, where for is the sum of all the noise terms above and goes to zero by over parameterization:
(2) Ps
VnlBwrr No [a Di + (1 n/2)V' ve W
a D.
D. (WW00) + (1-1/ Wo)
Hence, using the smoothness of E(., V:):
LHS <. Exl ps
(1)
1 + (p)(p) /Tpps (2) + 2 =ク (2))
(140)
But note that
0. On the other hand, using the notation Lemma B and the result of Lemma IT
Ex((p) TT 2) = h
(141)
2
Es (Ewe.vaa") D. (V(0)) + (1 - n/2)V' + ve)W"D,, Wia::
(142)
EE
Di (V, (1 n/2)V' + V2)(2>" (I:) + +0's o0's(x))))
(143)
S 4Ex (Ewe,veu D. (Ew + - 1/2)1' (1-n/22J
voJ (x:)
(144)
+ 4Es Ewe.voa" D. (V( + - (1-n/2)V' V9)0 (0;;)))))))
(145)
$ 222 + R2
(146)
Moreover, using again the result on (xx) from Lemma and the fact that (xx) is orthogonal the rows of VA::
Ew D. , D (w + (1 2/22 + WP)a; = aa (0 (x:) + +(1 - (2
+ TTTTT T D. VV (x)
2
(1
"
D)a"
T
D: s V (x)
2
1 T
a
D.
V
$
0 (x))
2
$ (1
aa'
T
D. n
V (2) (2:) + Ry
2
50

---

Published as a conference paper at ICLR 2022
Combining the last Equation with Lemma
4
Ey Ewr.vaa' D. VE Dep.vaaaDDD (w + -1-1 + Wo)xx))
3 (1 ))²a" D: K. ( - R2
x R2 + Rs.
(147)
Combining Equations (14G) and (177
Es (p 2 < # R22 + RD R 92.
(148)
Combining Equations (141) and (48). plugging into (140), and reopening the definition of ps
(1)
LHS & Ey (1 1)) fw. w (x:) + r) voa Di Vi (ara) + 1191, v1) 7712822-
(149)
Now note that we can easily bound the magnitude of the term nBwe, " Di VIO as:
Ewa,yea T D. - (zt)) & Ewe,vele T D. (=
$ [| = | (z))) - 262(1 R)
Σ
| |
while using Lemma F9
Iw (w)w(())) s (k2//m3- B2) (Vm3ks C1 + vm33i) + C2 + VmzBr),
which is (2))02 for enough overparameterization and smoothing parameters B1, 32 as defined in A 10 Furthermore, from Equations (I3II and (126), casily that
Ewe,ved op Vo S 2C2(1++ + N0,,
Σ [illl
Now taking 7) small enough so that the bound n/ 222 R) V 11 and np1 both also be bounded of order C2), we observe that the term inside the argument of {(,,))) 8:) Equa- tion in (149) is O2), Hence, we can use the Lipschitz parameter of & in the interval (,,C,,)),OCCCC
given by Lemma B to take out the noise term:
LHS S Eye (1 fw (2x) nBeae V V v.) + not + nO(C1 + B)p2-
(150)
Now by applying Lemma 19 and writing the Lipchitz property of at point (1 (8--1) (-)) = O(),
LHS & Ext Bst((1 w) v (2x) + 1 (xre) + n/Ro, v/ + non + mO(CiC2 + B)
Ese (1 11) m) + (z:) (x;) + Rg 7p1 + O0(C + B)p2
=((( (1-1)) (i--n)ww..vlle +nf" mp.
where the last line is just definition. Now Convexity finishes the proof.
Next, using Lemma
prove Theorem R
Restating Theorem In the same setting Theorem f and having enough overparameterrizatio such that 3 < 5/ (p defined Lemma (I]) and polynomially small enough step size 7,, we have
Ex nnW + VTW V VV' VVVE) < L(W", VV) nu/4.
51

---

Published as a conference paper at ICLR 2022
Proof of Theorem f
First, note that taking expectation w.r.t Σ:
Bg - (/2)W""+ + v+W3ll = Es(1 -1//)////'II++++22 2 2/2) Σ
W. + mll
Σ E
1=1
= =(1 - (1-n/2)/|w'1)+++ + Σ |
which by orthogonality of Wg's:
LHS = (1 - n/2) -11-///2||"(||=//|"""
- -1- 7
Similarly for V':
Now using Lemma II:
ExL(W' - n1//w' + Wn V' -1/2V' + VVVS)
$ (1 -1-11 () + (E
(1 7) [ + w/2 111) 17 4/2 |W11 + th (1111 + ( 69 + ?[1 + (elllll
S L(W", .V' - 1/ ((WW', Vn) A +1 -v222a n -
which by the choice of s/y 's is equal
LHS S L(W", V' 77 (L(W" V\) A -1/2) + + + 1(1 )
1 LHS S T(WW, V') 1 / [//[/++++|V/))))
Moreover, using the condition
v/8
and picking r as small as
WWW S nCi + C3) S 5v/8,
we finally get
LHS LLWW' L(WW.V'-- V-V-V')))
- mp/4
52

---

Published as a conference paper at ICLR 2022
A.14 EXISTENCE OF GOOD DIRECTION HELPER LEMMAS
In this section, we state and prove the core lemmas that are used in the proof of Lemma T Notably, through all of this section, we assume the norm bounds ||W||| I C1, IV - C2 and that as our usual assumption, the rows V are orthogonal σ( (ax)'s "'s for all E [n]. notation that we use throughout the proofs is V which refers to the projectiono of V onto the orthogonal subspace to (6(0) (z, (x;));==
Lemma Let P(.) be the projection operator onto the subspace spanned by (e) (2r)) (r.))==1 Also, we denote the projection of rows of V onto the orthogonal subspace (Φ (x;)) )-)) by V Then
Ex - V2 e35 n/m2,
with high probability
e35Vn
IIVE, Vy x
mmz
Proof of Lemma 1P
By Equation we have lV I e3t/ mmz. Now suppose that u1 u..... Un are an orthonormal basis for the subspace span( (x;)) Then
Eg [V
v Es|| Es
ΣΣ
VJ V2 11 S e3
Also, by Hoeffding, with high probability:
k=1
which implies the second part.
Lemma 13 The first cross term goes away because of the definition of Vš. (inside the expectations zero almost surely)
Ex
E
Cvewwel a" Dv (2000(2)))) (z) 0.
mm
Lemma 14 Second cross term:
1 a" D DV004ve--11 (2) (151)
Ey Eve, Eve,w, wo Vm,
3 5 + R)2 + 2 m33 ny
(152)
Proof of Lemma 1
53

---

Published as a conference paper at ICLR 2022
This time use Equation (128) in Lemma I0 and Lemma
Eg (Bve,wol
Vmz a Dewo-vetV'. (x:))
- Bs Evo.wol/Vm, E VE. (()))()())))
1 Wg,vo,We
V [15 Σ
m2
< EveewoBs Er. Σ
(1);)(
x Fve,wo Fsz
Σl I(V3, Vy (x:)) Σ 1V E2) (3:))2
(x,))
2 Eve,wo Es. Σ |1V - V (x;))] + Σ 1V (x)))
< ((1 + ((L+R) RC + o Evr, 11 10 (x:)
Now according to Lemma 33, have
(po. S + m3313
which completes the proof.
Lemma 15 We get additional term (x;)); as result of smoothing which we define as
o" (2x)
V DWo W - -0' sx().
(153)
vm
Then
P( (2x)) 0 my exp (-82(
Moreover, we have the following inequality almost surely (over the randomness of WP):
| (z;)(x S
Σ |i
Proof of Lemma 15
According to Lemma for j & for every i [n] we have
(w))) (0) + w))x c2/2vm1
Now note that long as the sign patterns for j P does not change, d² (x:) will be zero. Therefore by union bound
mi
P()
(x:)
Σ
P(sign change in m/((W(W)))) + Wf)as/
IWfa..)
MmP((WF2: 2 m2)mm)
But (WF) is Gaussian with variance 87 /mm. Hence
LHS S m2 exp ( (-22/
which proves the first part. For the second part, according to Equation (103) in Lemma E for every k E [ma]:
(x+)) <
W D Wio +w W* x2l + 10 (x;))
(154)
mm
< 2/ m Σ
|W51l s 2 x
| 11
(155)
which implies the second part.
54

---

Published as a conference paper at ICLR 2022
Lemma 16 Fourth Extra term: Bee,yol 1 Vmz
a" (v + ve + (1 - -//2/V'' "o (xx))
S (Kaym2mm + C2 + vmg mi exp exp (
Σ 112al12 = R11-
Proof of Lemma I6
Note that with high probability over the randomness of V(00,, we have || 2 v Mmgmzkg. Now according to Lemma ISS and using the fact that | I C2:
S Bwe.v
|| [a + V + (1 77) V V1212 112110 (x:)]
vm
Ew.,ve 1 + VV (1 /22
I V Ev + +(1 - / //2) + |V ) mi exp { (222/288)))
Σ
1
1100 + || + m333 mn exp (-23/1887)
Σ 1 1 12
S (22 + C2 + mmg mi exp (-22/(88))
| 1l Σ
k
Lemma 17 Fifth extra term:
Ewe.vol mmz
a" D'Dro (x:)) S V exp (
Σ
1i Pa = R10.
k
Proof of Lemma
Similar to the previous Lemma, the inner expectation can be bounded as:
E |a
[[VV)) < E| (z:)1l 2 Vi.m ml exp x (-22/189))
Σ
mm
k
Lemma 18 We have another extra term as a product of the movement - /1/2W' in the first layer:
2
622)
(/1- (1r-))))))))) (2) (xx))
m
Then
Ewr, vo Vm²
a" Dyoo4vee (x)
87
C2
$ v Gama
+ m exp (-22 = -Rs.
(156)
mi
Ew
D'DDooooee (V1)) + VP + (1 - (d=m)2)"))))))a;))
Vmz
S (K2v/22m3 + Vm + C2)
(157)
Proof of Lemma I8
First we prove the following approximation argument (for all & E [mg]):
82
CgC?
( <
1 (z.)ao12
mi exp (222)/((83))))
(158)
mi
Vmiki ki
55

---

Published as a conference paper at ICLR 2022
We have
1
1
W D W( x. W(0) ,
LHS Bw
W D +wo+ (W + W/)
Vm
vm]
W Py W(0) 12
x Ew
W D Dwoo+we. (W (W Wo),;
Vm
vm
W WW (W WD) 2
+
Ewo
W wwo (W WT)
m
m
By the independence of Wf'ss the first term can be upper bounded as
1 Σ ==1
(ww
Wf),,1 ((W, + Wif)a 2 0} w (0) 1 2 01)²
= Eww mi
m!
32
Ew afaii m1 m1
m1
m
For the second term, note that for every j & P. the jth entries of + and Dwio +wo++ are different only if Wy can make sign change in the jth row, i.e. 1(W))) Wo)all S Wfr x. should happen. We denote this event for every j & P by Eg. Furthermore, if this happens for some j. then the value of (W>()) + ya) is upper bounded by [Wjrs), Now similar to our discussion in Lemma 15 and using the result of Lemma MI
Bg) Pssign change in some j j& P)
P(sign change in j)
jEP
S <mP WJ)ara S Wffx:) S m. P( > c2/(2vm,)) But note that (Wf)),; )x, is Gaussian with variance / Hence
LHS S mi exp { (-22/
So finally write
84
Ewe
1
Σ
[ )² + Fw mn
1 (1 (UUgepEE))
Σ WW)a,))2
my
m1
jEP
jer
0
P
+
m1
m1
3
c2
+ mi exp (-62
m1
Vm,ki
Kl
which completes the proof for Equation (158).
This immediately implies
37
0207
Ew ((o=)(((M(((x))) S V Ews (x:))) & ma
+ + (
m Vm,Ki
Now first prove Equation (1566)
1 a" Dvv0 a. Vi (2)) (x:)]
Ewe,vel
< Ew Vm
Pall|Proo (2)
Vm²
s = 10 (x:)]ll
< II (2)))
87
c2C7
Gemis
+ m
+ m2 exp ( (
mi
56

---

Published as a conference paper at ICLR 2022
To prove Equation (157).
Ewe.Vo
1
a D (V Va v1(11n/3))))0
Vmz
2 Ev
vol.0 (V + Vp + ( =1=1)))))0111(0000)))
mm²
2 Ewe,ve
|a
4P + / (x))))))))))
mm2
|||||
Evo
E
|| + [[1 2) 2 1 (2) (x,))l
ma
R2 S (K2v m2m + m23 + C2) (13m2m3 + m3
Lemma 19 Closeness condition:
Es Ewa.vol
(xx) a" Dv VgO" r(=)]] - s No.
/m²
where
Rg =
Σ 11 + R3
(159)
+ m2 exp (Mgp(((m))333))/12283)) + mmeepppccf/Smmpp VT2(1 + m0)/
Σ 1 1
(160)
Proof of Lemma 1Y
Note that by Corollary 5.ll and according to the proof of Equation 129 in Lemma IT0. if for every j & P we don't I have sign change veto+ V* (I;), then get
a" DV (o) (x:) R3.
m
Also, note that we need the event E (defined in Lemma ( to happen order to be able to use Corrolary 5. Hence, given a WP for which E happens,
upper bound the probability of sign change with respect to the randomness of Vo, We define the following event with respect to the We for which E happens (P, defined in Lemma Z):
randomness of Ve when conditioned
SC = Ejj & P s.t. V x4
R2 C/ ||]|]])-
M2
Now from the result in Corollary we have < 1 {sign change in j $ P.) - ((SC). Therefore,
E1 siign change] < 1(SC) <
Σ P(VV<11
f2 1/3 C 2/3 111111<111)
m22
j4P
K2 1/3 C
2/3
|
m2
But note that (V/))'' is Gaussian with variance 3 | m2, Hence
LHS S m2 exp (- (252))
(161)
Now let D be sign matrix random variable such that if E and SC both happens, then it is equal to the valid sign matrix D +ye and otherwise it is equal to an arbitrary valid sign matrix in the case when both F and SC happen. Now using Equation (T have with high probability
57

---

Published as a conference paper at ICLR 2022
over the initialization:
Ex: Ewa,ve
a" Dy s(;))] ((o - (wa))
Vmz
< Ey Bwo,v vol
aa DVOO (V - 1"E)Ø>><<
mmz
1
Eg E Ewr,
a" D'Doooov V'O'' (z,)] (z))
mm²
a DV a (V. - '''''' 2x())
mm²
1
+ Ex Ewre
a" VV -
Vm²
< Ewe,veEs
Σ
I1VE,
x
m2
1
EE Ewe.vel
a DV DV*
(x;)
(
Vm²
D..Dvo++ V=d'))) D]
+1SSCUR UE)
Vm²
1 EweevoRs Rx
IVE Vy'illl x
m2
+ Es Ew (
a DV ('*00(x))) (I,) - ((x))
Vm² La" DV (0;
_a² DDV DV (x;))
EEyEwe, ((SCUE)
mmz
< Ewe,y
Σ
By IVs, [1::)
mm
RRa 2F(SCU max
a D'V
mm²
Now note that for any sign matrix D', we have the following bound:
1 |L a D'V D'V (Z))
[=]]V""== $ vGe(+ + R),
Σ V 1
mmz
Also, applying a union bound and using Lemmas
PPSCU F)) S P(SC) PPF)
exxp (m))(((()) + mi exp(-CG((Mm333)
Hence, also applying Lemma A0. we further write
LHS & e R),
Σ |illl + Rs
+ +mz exp C1) (233)) + m. (xpp-CG/(SSmp5)))) V + R)),
Lemma 20 Suppose we have my 2 C.. Then, for the following basic term we have:
Ewr.vol mmz
aT Dv (V()) + V2 (1 (1 (x:)
n/2) (x:))
S (1 - - 1 a Dy + +V + V') (xx) + (x:))
mm
58

---

Published as a conference paper at ICLR 2022
by Ri + Ri + (Vmgk2 + 32) + vmg3i)).
where
C2
R4 = C2 Vm cxpp C2 (Vm2xi2)(33 /8/3)
(Vm,k2) C2(Ci VmzBi),
Rg = my (mmll) + B2) + Ro.
(8mg
and Rg is defined in Lemma P
Proof of Lemma 21
First, note that by orthogonality of (I:) the rows of V
LHS - m/2/E vol
1
2 (V00
(V10) VP) (o)
mm²
LHS - 7/ 22E
a (V (V + -V- - -11-n/2)V")
Vml
(1 n/2)
T DyooAVoV (V + +V- (1-nn/2)')) (xt) 60 (x:))
Vmz
(1 2
a" "UVO (V /2 (') (x:))]
Vmz
+ (1 - n/2))(1/) mmz
a" Droovetv' + (19) 2 (1)
(162)
But note that for the second term:
Ewe.vel 1 at Dv (V + (2)()))) (1
mm
S Ewr.vl mm²
a" D'Dioo (V + V2) (x:) + (z)))
Σ
+ (z) (x)9)
mmz j: sign change
Evo Vmz a Dyoo (V()) + (2) + (x:))
Σ
(a))
(163)
sign change
Now conditioned on v/e by the result of Lemma RI we know there exists set of indices O C [m²2].
C2/3
|0| S (VMyNo8278822 and for j & O have
22/3 (Vmgkt2)1)
1/001 1/1 2
||~;|||
vm2
and
2 (
(m 1/3
|2/11-
2/m²
Now for j [mz). define the event
22/3 (Vmnna))33
R = 11
| 1],
2/mL
and R = UyRy. First, note that using Gaussian tail bound, a rare event:
PRR) s Σ P(R)) m2 expl-C2 (V/2xa)
2/3 /882).
59

---

Published as a conference paper at ICLR 2022
Now for j $ O and under At clearly we have that the signs of (V, Joy and (V, +V +VVV4 are the same. Therefore, applying Lemma B3, we can argue under rt:
Bwe.Ve Vm
Σ sign change
Ew 1
(z
mmz JEO
C2 C2(Ci + vmz3i).
V" Bw. (1o)
(Vmgn2)2/3
m2
Hence, overall, using Cauchy-Shie -Shartz
C/
V Vma j: sign change
Σ
S
|V Er [x)
(W1z C2(C1+vmm.31)
s C2(C1 + Vm331 mm expl-Ca (mm +
C2(C1 + vm331) R4.
(Vm,nz)) 1/3
(164)
On the other hand, using Lemma M we have with high probability over the randomness of initial- ization
a" d'Dvoo x. ( (mgrzllo!
mm,
Hence:
1 a" DDio (V(0) + (z)))
Eyel
Vmz
1 a Dv (x)) + mmz
$ Ewoovol
(2.
mmz
1 a Dv x v (z.) + Bw (x:(1)
< Ew
mm²
(V + 32) B2) (xx))
(V + (C) 31)
(165)
Combining Equations (164 and (65) into Equation (633)
Evel - at Dy (V + (x))) $ Ra + (Vigki + 32) + v 31331).
Mm
(166)
Moreover, for the first in (162), using Equation (165) and Lemmas 3 and Lemma 50 we have
EEv'
a DVio v (V + vp + (') (x:))l
mm
Eweeve
La D 20))(1 Ew vo Vmz
1 a
Σ Vg (x)
Σ
Vm,
mmz
+ + (1vm)))))))))))) (C2 + 32) El (xx)]
K2 + + (C2 (21 vm331).
(167)
60

---

Published as a conference paper at ICLR 2022
Substituting Equations (1 and (1672) into Equation (1662). finally get
LHS - 7/2/E vol
a DDDylos Dyw0+ve4V' (V + (P) (x;)
mmz
_ -'-"Dvoovrtvaa (V + V2 (2)
5 11/2) 11/2)
Vml
+ 2
R4 + (Vmgkiz + B + vm33i)
(1 Evrl mmz
a" DrIo (V()) V0 (2)
+ 1²
Evel a" DVI (V(0) + VP + V') (I:)]
4
Vmz
1 2
R4 + (Vmgh2 (C) + vm33i)
1 - D'DDDDooveV... (V(0) + V² + +V')o!
$ (1 Bvo
ViTaz
1 1/ (C1 + B1 (lVmg)) + (C2 + B2) vmngi))
# n| R4 (V + (2) + Vmz31)).
(168)
Now by picking v) small enough so that the second term is dominated by the third term we get:
LHS - n/2Ewe,vo
T - Divoo (V10), (2))
(169)
mmz
$ Tyr mm
a² Dyvo4vo-Va (V10) (V10) Ve (2))))
(170)
+ π Rs + (Vm3k1g (2) + vmggi)).
(171)
Now we aim bound the term Ewe,v> vo Vmg
- a= Dy1o) .z (V (P) First assume
that we are in the event E defined Lemma M3 i.c. we have (1)(9) S C2. Conditioned on
such WP, we now work with the randomness of the initialization and VP. Note that the random matrix (00)) + VP jointly over the randomness of V and the initialization also Gaussian, and its variance is
33
2 < 2
<
2n
(172)
m2
where the inequality follows from the fact that R2
m and B3 S Therefore, applying Lemma for the random matrix (0) in the Lemma as V00) VP here, the bound does not change
up to constants because of the inequality (I72).. Hence, with high probability, lets say with prob. 1 81 this time over both the randomness of initialization and VP:
L
- Dym (V(0) + V (x:)) S Rs Mz
(173)
This means that with probability at least V8, over the random initialization, then we have ( with prob. at least 1 1- over the randomenss of VP. We name the latter high probability statement (x). Moreover, note that by Lemma 32 and assuming my log(ma) m2, have the following
61

---

Published as a conference paper at ICLR 2022
almost surely bound (also note that V 1 (z:) is Gaussian with std 3n
16 (x+))l)
vm,
Eve
a"
D Diioo (VO) + VO) (Ii)
(174)
Vmz
= EEv
1
a" DVI0+ve4 (V + V
(O)
(175)
Vmz
1
m2
V
(0)
(z:)) + Eve
1
m2
1000 (z:)
(176)
m
vm2
m2
m222
x (xii)
sup
x'|
(0)
(x:)]
(177)
|==||==1
m
m
m
j=1
j=1
x (.: + B2)
(178)
Furthermore, note because each variable 1V (0) (z:)) is Ving
(0)00 (z:)) subGaussian. Therefore,
f. is subGaussian with parameter (x:) (1:) with respect the randomness of VP. Now the point is that the high probability argument in (+) is much stronger than what one can get from the subGaussian ineqaulity with parameter [[](
(with the corresponding expectation term (1)(0) (z:))l + 82)). However, the disadvantage of (+) is that it only works for a fixed é1. In other words, at least it is not obvious from this argument that why for a fixed W in a high probaiblity region of the random initialization, whether we can send 8n to zero by growing the constant behind Rg with logarithmic rate log(1/5). This makes our job hard for bounding the expectation with respect VP if we only wish to rely on (+). Therefore, we combine it with the inequality that we get from the subGaussian parameter that we introudced above. More rigorously. we define the thresholding parameter
U = (0 (x:))) m² + 82) + (6 (ux)) 31 log (1 (x:))((V m2 + (R6)
= =0(110 (c:) + B2 log( (
(s:))l( (x:)) B22) (22/BRa)) Ro)))
for which we have
R [ < - PPU < L) S Ro.
we divide the range of values for L into three parts:
E[C] = E
CI C < x P(C < Ro)
+ E
L] R. < C < U
//P0pP/PL P Ro S L s.)
1 < $
+ E
< E c Rol + PRR S S < U)+ Ro
S Rs + V81u.
Now by choosing 61 S 1/U, we conclude with high probability over initialization and conditioned on WP's such that E happens we have
L a" 4 (V(0) + VP) (0) (x.) = E|C] S Rg- mm2
Eve
Finally, we integrate also with respect to WP To control the random variable when E happens, we use the bound in (172) and the fact that E is rare event due Lemma K3
1 a" D Dvoo az mz
Ew
(V + VP ( (0) (mxa) $
S mi ( / (VT2 + B2) + Ro Ry
Substituting this into (I7II) the proof is finally complete.
62

---

Published as a conference paper at ICLR 2022
Lemma 21 Third cross term: with high probability over initialization, we have
Es Ewr.vol 1 a² Dyio+VvrV'' (V VP + (1())))))) mmz
{m) cxp(-Cf/(8m,3))) + fRm²) + +R703)) = 32
Proof of Lemma 21
Note that the way we defined the matrix W and as a result o² (*(x;) only depends on the ran- domness of W(O), not on W" or the randomness of V Now using Equation ((B)) and Jensen inequality write (for vector the notation 20 is another vector with each entry as the second power of the corresponding entry in v):
1 a" D'Dy Dyoo-V-VV (V + V2 + (1- +1-1((11)))))))) n)
By Ewn.vol
mm,
_ a" Dvio (V + VP + +(1 1)) ")\a">>>> (x:))
< Ey.Ewo.V'
Vmllz
Ewe,rvoRy,
(
a DVvo (VO) + V" + (1 (--))/)), EΦ Es((i))) 2
mmz
=Ewrrvo
1
a "DVoOVVAVVI (V10) (V +V² +(1 r)
mm2
1
a" DVIoo (V v0 ['-))V') 2
0 (E>))
< Eweeve
mmz
1
a" DV (V()) + ve + (1- ---111 n)/ | ?
mmz
$ Eweev
DV (V(0) + V2)
12 + Ewe
a² Dro0 - v) (1-1)
vm²
mmz
1
< <<eEwovee
a DV (V() vo)
+ + - --)
/mz
<
aT
a Dyoo (V() Vo)
+ < C).
mm²
2
Now under the event E defined in Lemma 33 we get that (2,2) S C₁, so we can bound the above
< EVv
Σ a, ([((( = Vi, + 17)00 + +x') 2 O3( +
v3)
sup LO
ISC, m22
(179)
+ +1=(1-1)2CC
(180)
Now defining
1 Σ aay +V + (7) (z:) + +x) 2 03(1,00) + v m2
L2
to bound the first term, want to apply Lemma 2E using the same trick that we did in the proof of Lemma 20 Note that L2 is the same term as 12 v' in Lemma mh except that it is defined with
respect to (0)) + De instead of (0)) On the other hand, note that ( + ve has Gaussian entries with variance R + _2
and we know 23 < n +
< 2N which means the argument of Lemma P
my
holds true here up to constants:
La R$.
sup | ( (a:) 5c
This holds with probability say 62 over the randomness of both V(0) and VO, Therefore, with probability 1 - Vo2 over the initialization, then with probability at least 1 Vo2 over the randomness
63

---

Published as a conference paper at ICLR 2022
of VP we have the above. Moreover, with simple Cauchy-Swuun Swuartz get the following almost surely bound:
L2 S | + !.
(181)
Now the variable || is subexponential with parameter (8tm B(ms). Furthermore, with high probability we have || [[(0)) | & mym3kg. Therefore, taking
U2 θ k3mmms + Rm log ((3mmmm + Rims)/ /Brr)
then easily see by the suhexponential tail:
E[Cal L2 U2] + (U2))
PC 2 U2) S /U52
Hence, we can apply the same trick as Lemma 20
B[C2] = E
C2 L2 < 22 P(C2 S J27
E
C2l
R L2 02
P R8 - C2 s 02))
E
C2l U2 23
P(U2 S f2)
2 C2l L2 - n2
P( S L2 - + R2
S R2 + Vo2U2.
Now taking 62 S /22, we finally get that conditioned on WP's where E happens, then
Eve L2 < R2
On the other hand, to handle the case when E' happens, we can use the bound in (XII as it does not depend on the occurrence of E as well:
Ewe,voL2 C2 I P(E) <((E)
S m2 exp( - (633 + ffma) + R2?
Plugging this back into (180) we finally get
LHS x (m expl (CtlCCC/mmmm)))((mmmmm + +88m)) + * + C²
64

---

Published as a conference paper at ICLR 2022
A.15 BOUNDING THE WORST-CASE SENARIO
Lemma 22 Suppose ma 2 log(mz) and vight Z C₁. We define the sign matrices +V and Divos i with respect to the multipiccations
(V(0) + (')(0))) (xi) + x').
and
(1000) + x')
Then, with high probability:
a De
+V ( 10 (27))
sup |
Vm
(G
(C102)2/5m))
mg
2/3
(K1K2) 2//3 log(m2)
(1 log(m2)
C//3 (
(Vmz (V
1/3
C2 (N1 vmy)
2/3
m2
3/2 m3
(log(m))) + log(log(m2))) + 1i K2 v mg log(m2) == Ro- /m,
K1
Proof of Lemma 2
Consider cover for the euclidean ball of radius C1 in Rm with precision c, i.c. Bg, (c).
So for every x' E Rmm,, there exists an E Be, (E) such that || - x'll s and |Be, (e)l s (2) Now fix x' and æ. We have
T = _az D vio) (x:) mm,
(xi)
Σ a,
(0) + (0)0 o (x.).
(z.).
mm
Now by union bound, because each variable v (10) (x,)) is Gaussian with parameter K2 (2) (x:)) and using Equation (IIS), with high probability we have for every j E [m²]:
1 (ara) S kall (ar))l /lo((12) S / log(m2).
(182)
Therefore, by Hoeffding over the randomness of the Bernoulli variables az, for fixed x' with high probability:
m2
P On the other hand, We know that the VC-dimension of the class of binary functions with respect to halfspaces in Rm my + 1. Therefore, the set of different sign patterns in matrices Di is i.e. for
( +x)))++)))))) 2 03v,
(0) (xx) S K1K2 V my log(m2).
2
bounded by m² ms+1
D = (D m. x' E R'
we have
|D] S m² ma-1
Therefore, by taking union bound over all sign matrices in D, we get with high probability
sup aar S KI m3 log(m2) / log(mo ms+ Kikgmng log(m)).
(183)
Now for threshold which satisfies
r 2/
(184)
define
Jz. (j E [m²]] 1 (0 (xx) + x) S r). Now by Equation (1 the assumption of the Lemma might1 2 C1, we have
(xx)) xx1 < (0) (x:) ||^||| Vm + C1.
(185)
65

---

Published as a conference paper at ICLR 2022
10 (2:) 2|| 2 (x:)) - ||>|| 2 Vm3K1 C1 2 Vm3K1. Hence, v (6
(186)
x) is Gaussian with standard deviation at least (K22)m3Hi). Therefore, (x:) (b(0))
P(VV))) (0) (6 (x4) + +))l S <r) S
This implies
E J2.
m2.
(187)
V VMgKi
On the other hand, note that [T,,| is the sum of m2 Bernuuli random variables, so is subGaussian with parameter m2. Therefore, with high probability
Ja S
Vm3NiK2 m2 + V m2.
Now taking maximum over all a E Bc, (t) and exploiting the subGaussian tail of the random variables, get with high probability
max weBc, (6) JJarl S M2gKiK2
m2 + m2 log (o,((( 2
Mmg m2 + v mmmg log (1/e).
(188)
Moreover, consider a threshold indices
< 0, such that -02/8 I m2/ms, and define the following set of
2' Uا E [ma]]
10 x'1 Ox2Ci).
Then, using Lemma and noting the fact that the standard deviation of Gaussians in /(0) is R2 and that (xx))l S Ci, with high probability:
sup af: ||=1
Jo S ma(log(ms)) log(log(m2)))-
(189)
Now note that for each E [mz]. means that with high probability:
1 1|2 is subexponential with parameters (mgtg K2), which
max [ m3n + vmyh2 / log(m2) + n log(m2).
But with condition my 2 log(m2), we can further upper bound it as
max (1 S myn
Now for fixed x, xx, for j E Jz.r we have
( (z:) 2')1
s 11, (010) x)) + -1V (x' -x]]
< 1V (0) (000 + +x) + 11 ||||= - x||
3 + /mghzee
On the other hand, for $ J(2).
1 2'1 S BrgC1.
(190)
Therefore, for j Ja,r ((2)
(0) (x:)) < V (0. (xt) + + 1/ 2'1 Vmgnze + On2C1.
(191)
In a similar fashion, j & Ja.r, then using assumption (184)):
1 (z)) + 2') 2 1 (x)) + x)) 1 (x x') 2 VmgRzE 2 2/2. (192)
66

---

Published as a conference paper at ICLR 2022
Hence, using the fact that (x;) is orthogonal to Vj:
[[(y))0 + (2))
(0 (xx) + x') 2 0}
<
$ " (1),,) + x')1
< "III ||| 2 (1:) + +''|]
< <IIII ス 1 (Ix)) + z²)}
V2 (s (mx) + )
4C1 }. 201
(193)
Now by triangle inequality and Equations 19
and the fact that | S C2. we can
write:
T - F2.v
1((y))) + 22)
0)
20 (z))
Vml
jEJznr- J
1
[((VV,0)
2 13 ())))
03
Vmz
1((1 (0) +
m
(EJ
|Je,r
J
(2)
max
1V (0) (x)))
(z;))
Vml
JEJ..- J.
V (0 (3ta) + x')l
1
K|VI
+ r
10) (
m
201
101
JE(Jo.-UT())
21.0)
1
(0) (x:))
21
max JEmZ
Vml
$
JJz.r
max jEJr,r- -
[V (000 (a:))
Vm2
r (0 (x::) + +')l
Σ
+ r
-(11 (b(0(..) (s:) + x²)1 + 01)2C)
Vmly
201
40
jE(Jo,
1
(
max
(0)
(00) (2:))
V
2
jEma
<
JJzrr
max
3 (0)0 (xx))
TT
jEJ.,r -3
1
Σ
1 7 |1 + C1)
mmz
(
1
()(2)
[0) 000) (z;))
+
200
max
1
mm2
jEm
JJ
J
Vmgnze + 0k2
Vm,y V ((6
Ci
|1 2'' ~ IV?
M2
67

---

Published as a conference paper at ICLR 2022
(j: | 7/ 0r + /mz
(x;)
max
mm
gemg
Cic²
IJ.r Jotpl(r + VmgK2e + (n2
mm2
mmzr
CiC3
0k2 + 1
1 [
(0 00 (x:))
V12 x
max
jEmp
Now using Equations (207))
(12)) and (T44)) and the bound on | (2) from Lemma 29
write
CiC mmz
Jarr((r + +122C() +
T x' K1 my log(m2)
+
v
m
m
1
VMzNi112 m2
m2m3 (1/()))) +x2CCi
Vm2
CC
C9C
ma((og(ma)) + log(log(m2))) Ki V moggog
0162.
mm2
r/m2
mm
1
m2 V V log (1/e)) 0k2Ci)
Vmz
mg
3/2
K2
(log(m))()o(((m)) log(log(m2))) r/m2
C90
C.C. Vm,r²
0k2-
(194)
Vm²
Now setting
1/6
(kIR2)
r" = =C m3
1/3
m2
By this choice, from (1944) we obtain
(C/C2)4/a
(C1C2) 2/3
m
2/3
(k1
1/3 1/3
Tog(1/e)
C1/3 (
[T - To $ (( (2 (//3 (V/Tg)))))
[+0
m2
2
(K1 (
3/2 mg K1K2
Mog(m2)(log(mm) + log(log(ma))).
mm2
Now we set
0t = 3 log (og(m)),
which also satisfies the condition of Lemma A and combining with Equation ( we get that with high probability
|r S [T W
Pall +
|
(C/C2)4/3
(C1C2)2/3m 2/3
(K1 1/3 / /Tog(1/o)
(K22/mm))
(1 log(m2)
(Vmzk22)1/8 (V
1/3
C
2/3
(16 (11//my)1
m²
3/2 m3 KiK2 K2
(0gg + log(lo((m2))) + K6 Ki / mg log(mz),
Vmg
where ||~'ll S C2 and || S C2. Vj : (z, = 0. We also need to satisfy condition (I44)
which regarding this choice for 0 = 0* becomne
(C,C2) my 1/G
(11
2/
(195)
1/3
m2
for which suffices to set
1/3
E" = (//3
(196)
2 2 11/3 2/3
Substituting this choice of e above and picking the overparameterization large enough to dominate the magnitude of C1, C2 that log(1/e") S log(ma), the proof is complete.
68

---

Published as a conference paper at ICLR 2022
Lemma 23 Under the following condition
(Vm2z (VTTgr))) 2 (ma
with high probability we have
[(V)
(0) (z) + 2
sup ||x MCI a00) mmz
S Woggkllo(ma)) + (Vmg 1/3
(C, (0gg))///////)) (m22) =- R7.
(VmgN1) 22/3
Proof of Lemma X
Similar to Lemma
M define the helper functions F and T as
Σ
a n ((V) (0) + (x) + 0
(197)
Mm2
j
Σ
aa (x,) (,))) ,
(198)
Vmz
First we bound sup 1',, To this end, note that because v E Rs and the VC-dimension of half-planes my + 1, then by Sauer's Lemma, the set
D= (D xy a' E R ||'1| 1ISC
of all sign pattern matrices has cardinality at most
[D] S m2 ma-1
Now note that with high probability, the entries of the matrix V are all less than Okk2 (oggmm))a)). On the other hand, for each fixed sign pattern D Vios, we have for the sum with respect to this sign pattern:
Σ E0,1iV (0 (x:)+<) +x)) 2 10
(199)
mml
is (manÿ log" (m2m3), n3 log(m)mss) sub- sub-exponential with respect to the randomness of a, be- cause each entry of the vector vin E, a, (1 (x)) + +x') 2 o)v)()) (n2 (Ne/log(m)m))) subGaussian. Therefore, with high probability we have
Σ 2allv//0 (z.))z))
(200)
m
Eall Vm
Σ a, 1 (V (0) (x:) +x') 2 0)v, [|
deviation
(201)
man log(mmms))) + mynn k2 log (m)ms) + R log(m))s.)
(202)
Similarly, if we take a union bound over all sign matrices in and using the fact that m2 > my:
sup 2 = sup 1 Ea (0 (6(0)) (1.) + x') 10
(203)
E'ERmB
Vm2
myng log(mams) + mmg log(m2ma) V (logmmma++) nig log (og(m)))))))))))))))))))))))))) log(m ma+1)
(204)
S mang log mogg which implies
(m2), (122)
(205)
supTa Tu S Vmigiia log(m2).
(206)
69

---

Published as a conference paper at ICLR 2022
Moreover, defining Ju similar to Lemma 22 and using the similar approach get with high probability 1Jz.rl S VmgKiK2
max =EBo,
m2 + my log (c, (c)) 2 VmgKiK2
+ Mymy (1/c)..
(207)
Now for simplifying the analysis, we assume that for indices jE Ja. we can change the sign pattern with no cost on V', i.e. we can pick any subset of them. Therefore, we first compute a high probability upper bound on the following quantity:
sup m S.
EΣ ~
(208)
JES
we form the matrix V be the matrix which only keeps the rows with indices in Ja.r. then the above quantity can be computed as
1
sup
EΣ JES
sup Vmz DE (0.1, - 11p
| (u''vo) (Ja,))
(209)
Mm S..
mmx ( sup ||a|| S Amax (V (Ja,)))
(210)
mm2
mmz
where Amaz is the maximum singular value of the matrix. Now by random matrix theory, we know for fixed and arbitrary t 0, the following argument holds:
F(Amax (Ja.))) Z /mg + ViJa.rl + S 2e a
(211)
Therefore, as [D] S m m1+1 we get with high probability
max BB (c)
Amax
E 1e(Vmm, + v VIJarl + v log(m
(212)
S 12 K22 Voggloggmms + N2V (Jarl
(213)
Therefore, with high probability
sup ze (c) mm SCJ...
sup
S
K2
(v
log(m))mms Ja,rl + (T,rr)).
(214)
mm
jES
On the other hand, as in Equation (122) in the proof Lemma for j & Ja.r we have:
1 (0) (0 (0) (x,) + +2)2 17, (0) (o (0) (xx) + x)1 - (7 (x 2')l ス Vmgkze. (215)
Picking
c" = 2 mg
we get for j & Jz.r
10) (0 (z.) + 2') RT.
Now similar to the derivation in we have
[ + (x))
(0) (x)))))
(216)
< < 2 21, (0 (r,)+x()) +z')}
(217)
r < <HIV T
(218)
Hence, because || S C2, the number of indices for which 1((V + vo)l)) + +x) >
0} * (0 (x.) + x') > 0} is at most (c)C,) Therefore, we bound the following
quantity to use the analysis:
sup Esings
Σ 1
(219)
SC(ma) & [S|
jES
70

---

Published as a conference paper at ICLR 2022
But if we define for m2 <j I 2mg
(0) -V, jmm
then
Σ +1 1| sup 2m & |s|
v 1-
sup SC[ma] & |s| St, ssigns
JES
JES
Now note that each entry of Ejes v100 is vina subGaussian. Hence, the quantity || ||Eses 1/ is (mal² xd. Ixÿ) subexponential. Therefore, we have with high probability
sup [
Σ JES
(0) 1 SPSB E
111 + vmglneg log
(2mzz
+ In log
(2m²)
jES
(2m²)
(2m²)
S maln2 + vmgln2// log
+ 1n3 log
1
1
S mzln vmgg 18/2 23 1/33//////nmmmmm lo)(mm2) + 12 n log(m2)-
Hence
1 S Vmg VingVnng + Iii ll)(m2)).
sup [
JES
Now using Equation, we can write
[ 12
|| Σ (1((V))) +
1
$
mm2 jEJu.r
+ 1
Σ (1((V))) (0) + -11100 2
/mz jæJ,,r
$ Mmz ,r,
sup
jES
1
Σ 1
sup mmz SC|mal & 110
JES
K2
(v
Voogmm))mosJarrl + (1 + mmz
(ViigV + Iuz / (log(m2)
mm
$
12
Vm3K1K2 V
rm2
m2myllog mmzhi 1/2
(v (Vogmm2)m) + (Tarrl)
m
1
(Vng(CCCg/T)m + (C/C2/T)² Reg hecli///e///geee log(m22)
mm
K2
rm2
V m2m3 log( /m3322
mm, VmyKk1k2
1
(m//CCCaa/rmaa + )
Vm,
Combining this with (206):
[T Tx,voS S V2 log(m2)
(220)
mm k2 V mg log( Vm3N2
1 (/mm log(ms)
/myKt1
Vm,
(221)
Now setting
r"
my
1/6
(KI82)
1/3
(C/
1/3
m2
71

---

Published as a conference paper at ICLR 2022
get
LHS S Vmgk2 log(m)) (Vm,k22) 1/3
(Vmgk1) )2/3 (Ci log (m2)
(222)
Nym3 1/2 log 1/2 (3111((m)) (m2) + my 1/3 2/3 (C)C2)
K2
(223)
m//00 K1 log" 1// (m2)
(Vmgk2) 1/3
I Vmzki log(2))
(Vmgk1) 2/3 (C1 2//3 log (m2)
(224)
m3 1 H2 (2(
(225)
1/0 (m2)
Now under the condition
(Vmogti2 ) (Vm3k1) 2/3 2 log 7/6 (C
-7/6
The final term dominated by the first term, which finally completes the proof.
72

---

Published as a conference paper at ICLR 2022
A.16 CONVERGENCE
The goal of this section is to prove Theorem R
have L (0) S N. We define the domain Di == [Ilw'l S C1 == 8+11 |1'61 S C2 = N- For a large enough constant 1 = (1) and Vi function ( = 2w", - R. Moreover, suppose L TI is p1 Lipschitz, P2 gradient Lipschitz, and p3 hessian Lipschitz the domain Di (pl, P2.03 03 2 1), in the sense that their first, second, and third directional derivatives in an arbitrary unit direction is bounded by the corresponding parameters. Suppose we have access the gradient of I. at each point in Dr plus a zero mean noise vector & such that of < EELL S 022 and || < Q almost surely. Also, suppose for threshold Ne S R. if LL""(() Z Ne and w E Di, then we have at least one of the following conditions holds:
Theorem 7 Letting N 4B2, by Corollary
222
(1) (L (w)l
V
(226)
16 16
C C2
(2) Amin (V2L (w))
7
(227)
Then starting from poly(pt, P2, P3: Q, N. C1, C22 1/7, log(o1/02)) number of iterations, we reach a point we
= 0. with probability at least 0.999 after at most
such that L (we) S Ne.
Proof Our proof here a refined version of that in el (2015a). As we mentioned section E the key fact that we are using in the other parts of our proof is a uniform upper bound || < Ci.
||''l| < C2 which is unjustified by only naively using Ge et all (201LT)) Here, first we restate a refined version of Lemmas 14 and 16 in ct (20155)) in Lemmas [4] and 26 respectively, and
then use them to also bound the upward deviations of L. Moreover, to avoid writing repeated proofs and overwhelm the reader, we mostly treat the arguments in Lemma 16 of Ge et all (2015a) as blackbox and use them for our purpose here. A point to mention before we start, unlike Lemma 14 of Ge aal (2015a) where the dependency on other parameters than the step size v) more explicit, Lemma 16 hides the dependencies on all the other parameters (which is polynomial). Here, we follow the same style.
We refer to the trajectory of the steps of algorithm by (w) (22) In Lemmas of this section, To avoid introducing new notation and complicating things, we refer to the current point of the algorithm by Wo. while for the next point of the algorithm we use W1 (in Lemma 224), and wy (in Lemma (7) respectively. Also, similar to al (2015a). Ô and f below means we are looking at the depen- dency on n7.
Lemma 24 Suppose L (wo) I 21 and consider parameter x > 1 which can be set arbitrarily.
For every point wn such that L (ww) < R 21, (w)'())) 2 2 + ppap (2x + 4), then for w1 wo n (VVL" (wa) + Y) and random variable R, (depending on wo) defined as EL" (w1)) - tl (wo) = -1 ????
(228)
we have Ri- = 5((1) a.s., and almost surely:
(w())) - (woo) S /
VP2X.
(the expectation is over the randomness of E).
Proof This lemma is a tuned version of Lemma 14 in all (2015a)). First, note that the condition (wo)) & & + 2/ assures the smoothness coefficients Pi,P2 and P3 for I by Corollary ??. We follow similar Gi et all (2015a) (picking 17 1/(2p))):
" V (wo) + 1/ 'Po3p2N
EL" - I (wo) <
2
2
< VIL"( - (2 + Q3) 13) 2) N'oRPEN
2
S 4
-222 m/²x.
(229)
73

---

Published as a conference paper at ICLR 2022
where used the fact that pi 1. On ther other hand, L is p1 Lipeshitz, we have almost surely
(w)) I. (wo)) S prn((IVL. + E1) S (In( + ++1) - [1n[[VV + Q)-
(230)
(To be completely precise, should justify that write the Lipschitz inequality at point wo- we also need to make sure that wi remains in the domain that we have the Lipschitz parameter in, i.e. Dj. To see why this is true, see the next Corollary).
Therefore
(pex) L (wwwo)
s 2n (1x + 2p2x1 ptQ².
(231)
Taking
n S (8p1
(232)
we get from Equation (229):
EL (wr) (wo) 1 2nn² p2 // (wo))? -
(233)
Combining Equations (231l) and (25%) see that
(02x) I (wi) - I. (wn) |² S (wI, (wo)).
Hence, if we define
EL (wi) (10)))(1((m (woo) = -1?
get
(ww))-L"((n S //122/ /P2X.
(234)
and from Equation (233), that
R² > 2p VI." (w=))1 2p2xpi 202xpi0²= = =
Moreover, because the function is p LLipshit at the domain point wo, we get from Equation (M31))
1
ー ELL(ww) L (wo))= 2 -1p- ( (I (wo) + + 2 n (pr + Q) 2
p2x
by taking
S (p((p) + Q))2x)
which implies
n
Vp2x
This, combined with Equation ( and triangle incquality implics:
(w1) (w1) ET. (w.)())) I
ot 2npR1/ VP2X-
(235)
Lemma 25 As long as the value of the function at some w is bounded by N. 21 (L" N + 21), then 17 can be picked small enough (polynomially in other parameters), namely 1 W 1/([VL" (wo)]l + Q), so that the change of the function by a step is bounded by
Proof Let // = min(wi, 32 First, note that the function is bounded by N + 21, we have the Lipschitz parameter Pl. hence ( || I P1. Therefore, the change in w in step is bounded as
VVL (w) + Ell S Q Pl.
So by picking
N + 31
N + 21 +
(1
/(Q p1).
74

---

Published as a conference paper at ICLR 2022
we guarantee that the value of to after a step remains in the ball of radius the smoothing parameters even after one step. Therefore, now we can use the Lipeshitz parameter pi to bound the value of the function after one step as it is written in Equation Equation (253 Using this Equation, it is enough to pick 17 as small as:
N+ hence we still have
7 S 1/(ll (WoV""(Wo)) + Q),
(236)
so that the change in the function would be at most as desired.
Lemma 26 For a fixed point wo s.t. L (wo)) & + + 21, suppose we pick small enough such that
8(n) = 2/ 102 + N3N + 2 16 +
Then, note that for (V.."(wo)) s 5(n), condition 227 implies:
( (v=L"(wo)) 57
Amin
Then, using the notation T for the high probability event corresponding to Equations (36) and (44) in Ge ald (20150), for small enough 17 (polynomially small w.r.t other parameters), for R2 defined as
(wr) - L (ww))](((Er -R2n?
(237)
we have almost surely
[r. - r. (wo)) ( S R2n/ R2n/VP2x- VP2X.
(238)
Note that in the expectations above wy is assumed fixed. Furthermore, we can assume P(Er) 2 1 - Ö(1²).
Proof This Lemma is tuned version of Lemma 16 in Ge etl (20155a). We change couple of things here. First, we consider an implicit coupling that if w, exits Dj we do not move it anymore, ie. Wy Wt. Vt' 2 f, which means the noise vectors also becomes zero, i.e. Lr 0, Vt' > t. This way, the sequence of noise vectors remain bounded by Q, because if wy is inside Dt. then by assumption || Eell I Q. while otherwise &,- O. We denote the event that the sequence wu.... WT remain in Dj by Ex. where T is defined in Lemma 16 of Gie ci all (2015a)..
Note that we also have the smoothing parameters P1 P2, P3 for all (w)) because of this coupling. In fact, we will use a more strict coupling; we consider the event E to be the high probability event corresponding to the bounds in Equations (44) and (36) of Ge all (2(E)) holding for all t s T; We will see that G S ET at the end of this proof, but for now we assume it is true. An important point to note here is that in Ge (M0) E5a), IP( (TT) bounded by O(1²). However, the exponent dependency of 1) in this bound comes from Equations (60) and (42) in Ge 5.), in which by considering larger constants one can easily get higher exponents. For our analysis, a bit stronger dependence of 17 is required.
type inequalities, particularly used in
Also, because the distribution of our noise depends on the point w, our sequence of noise vectors inequality instead of the
(Et) is a martingale instead of being i.i.d, so we apply Azuma-Hoeffdit simple Hoeffdings in Lemma 16 of Ge all (2015a). (because we are also sampling a random (z,, 34) to compute the estimate of the gradient, this could be simplified to the case where com- pute the actual gradient and then inject an i.i.d noise vector in each step, but it is an overhead to compute the actual gradient, so here we choose to analyze the more complicated case.)
Next, notice the definition of A and Á right after Equation (66) in Ge et all (20155)) which in our notation translates to
À = (wo
8T'H 78 + 8T 1 8r Hō, (wo) + / 8+
200 2
P3 1 8 81..
(239)
where
ur Wo: 5 WT ÜT;
75

---

Published as a conference paper at ICLR 2022
for (w²) which is coupled sequence with (wy as defined in et (20158). Note that apply the coupling for the sequence ti as well, i.. if wt-1 = Wt, we also set w1+1 wtt-
To show Equation (237)), we want to use Equation (67) in Cal (20155)) though we only the expansion for the first term which is under 1(Er). i..
E FLL" (wT) L" (un)))) | er EÂI er + EAI
(240)
First of all, as it is mentioned in Lemma 16 of (Ge D0LTa), in the case where the noise vector 0121= < ELLL" S 0-² instead of having ELL." = o² for a fixed o, in order to still get a negative term of order in Equation (68) of (Ge 2015E) we just need the size of max to be as large as O "n (log
log };)), and it does not change the order of r in any other part of Lemma 16.
Now similar to Equation (68) of eLll 2015a), w.l.o.g we assume the smallest eigenvalue "P corresponds to 1:
N EÅLe, 2
A
(1-
(241)
1=1
1
[A.220 (1 - 27 (1-))))1
(242)
1=1
T=0
"1
N -
7oP)P(Er) Σ (1 + mo) )2|
T-1
S --
$ 2
(243)
2
2
where in the last line we use the fact that P(GT) S 1/2 plus the additional log(o2/01) factor. Second, note that our threshold {(n) for the size of gradient in Lemmas 24 and 26 has the same order of compared to that of Lemmas 14 and 16 in Ge (20155). Therefore, the arguments in Lemma 16 that considers the order of 1) and treat the other parameters as constants is true here as well. Hence, we still have Equation (69) of Ge et all (2015a) which is under the event Ey, Applying it to Equation (22!).
Hence, finally by similar derivation of Equation (67) in Ge ct all (201
ELL"(wr) -
< (m)))
(244)
Next, turn prove the second bound (238). Combining Equations (36) and (44) in (Ge all 2015a), we get with high probability (we use the final high probability parameter of Lemma 16 which is the result of union bound over all the high probability arguments which is equivalent to the occurrence of Er), i.e. when E happens,
||w woll s Ö( log + "
(245)
Picking 77 small enough such that for the bound above have
O log 1 π
N + 31
N + 21
+b
+b
get for every w in the line connecting wo wr :
N + 31
which implics that " has the smoothing parameters Pl, P2, P3 along wo to wr. Therefore, by the P2-gradient smoothness property of n!;
VVL - V (wo)) S Pallw0 w|| Oppon2 log 1 n
Combining the assumption of the Lemma \VL"((w))) S Ö we get
V [1 || = Ö(1) log(1 /n))
76

---

Published as a conference paper at ICLR 2022
(The last Ô also hides the dependency on P2). Now integrating over the derivative along the direction from Wo to wr:
L'(w)) (wo) + [ VL" + (1 ())))) wo)dt.
==-
Therefore, using (245) one more time, under the event Ey:
|1 (w"(wr) L ("(ww) - / ( + (1 ())o))) ( (wr wo)
! IVI." (twp + (1 - t) -orllllurr-- wolldt
- (1 log 1/ ///rllurrrr--- woll (1 log² 1/n).
Hence
(= s Ön log" 1/n).
(246)
which
Now comparing Equations ((44)) and (241). it is clear that one can pick small enough (again polynomially small in the other parameters) such that for some random variable R2, which also depends on 1/, so that equations (2371) and (2KS) hold.
remains show Er S Cr. This desirable as up until now we have only proved (LXVI) and (EK
for the coupled sequence (which does not move outside the ball Di), but we know that under the event E,, the coupled sequence and the original sequence are the same, which automatically implies the conclusion for the original sequence. Notice that the bound in (22fd) is an a.s. upper bound on the change of the function value under the event & for every 1 S 1 S T. Therefore, by picking 7 small enough (polynomially) s.t. the quantity (1 log((/n)²) in Equation (EET)) is bounded by I, again make sure that the value of function during these steps changes by at most / compared to wo. i.e. for every 1tS T:
(r.) - (.oo))) 1
(247)
hence, remains bounded by + 31. This implies Er S Ey as promised.
A.17 PROCESS FROM A HIGHER VIEW: DEFINITION OF THE (X) SEQUENCE
The goal here is find w" with L (ww)) S N₃ using Lemmas A and &G (recall the definition of N, from Theorem M. The main result of this section is Lemma 27 For this purpose we define a
useful coupling: to begin, as done Ge all (20155)), define sequence of times т; inductively in
the following way: To define Ti+1 based on T;, if the condition
Ne S T, T." (w((w.+)) S R 2/
(248)
does not hold, then just set T++1 = T3 (1). Otherwise, using the conditions (22.1), we are either in the situation of Lemma e2 or Lemma Ed by setting the value of wo in these Lemmas wo Wr, In the first case, define T++1 = т; + +2)) In the latter case, Let E be the same high probability event that consider in Lemma (276). which happens when the aggregate behavior of the noise vectors is normal, as a result of which w remains close to the starting point wh. Note that from Lemma Mi. we know IP(ET) > O(n)). Now if the event E happens, define T T; + T (3). for T also from Lemma MG and defined originally in Lemma 16 of Ge et all (2015a) while otherwise, define 7++1 = T; (4). Moreover, Er does not happen, define the rest of TV equal to Ti = Ti for every i' 2 i. At the same time, we define the monotone increasing events }. where 9; happens in the case *(4), and Gi+1 happens in case *44). Also, G, happens any of the previous Gr 's happen for i' < i; in other words, G; is included in Gi+1. We use these events to bound the probability that the process remains above Ng, Moreover, define the sequence of random variables (X;) X; == 2.,(w,,). Note that by Lemma 25 and Equation (REV) in Lemma 2R we have N₂ - X, < N + 31. The key idea behind defining X,'s 's is that we want to bound the MGF of ['((),,,, without worrying about falling out of the assumptions of Lemmas ( and 2G. With the definition of (X₂) and G, we are ready to state the theorem which roughly says the sequence т; will most likely stop after number of steps.
77

---

Published as a conference paper at ICLR 2022
Lemma 27 Let QR = U ( ( Then, for some
+ 31)
R
(249)
0Tj²
we have ((QR) S 81. In other words, after R iterations of PSGD, the defined sequence (X;) above has either been in situation *(1) or x4). Here, 0 depends polynomially the other parameters.
Proof By Equations (228) and (249) in Lemmas 22 and 20. there exist a constant 0 depending polynomially on all parameters except 77 such that
E|X++1 - X,| 9.] I -0(T++1- - -T))
(250)
Now for some constant C' that we specify later, define the random time i as the largest i where T S C/n². Using the fact that -;-1 S 9., for every we have a.s.:
X 1411(96 [G:} X = I [(;; - (i-1(--x,) + (X++1- (
Now summing this for i 1, taking expectation from both sides and using (250))
EX (G.) Xo
E1 ---1((--1
(X,41 - (1222.()))
B(1 - 1[(--)))(XX))
+ Σ E(X i+ X ā (x 1)) (2 ())
$ sup sup X
+ 0
B(- (Ti+1 T))r? (
= sup sup X - 17² Σ B(TH11 - 1, n f2 2 1t}.
Now using Lemma PR we know that in except when & happens (in which we stop the time se- quence T;), the increments of X, are at most I. Therefore, the value of X,'s 's always remain bounded by R 31, hence:
LHS N Onj² Σ B(Te1 (1
Also, by restricting the integration of the second term to the part U G 2 2C/12)) of the sample space, we know that under the event (2 2 i}. G automatically happens when T1+1 # T3 (it is easy to check). Therefore:
LHS < N 31 E1 U
(Gnlm2C/1)) Σ
T (1-1 i}}
i=1
= - B BI
Σ
(T-1- 1
1=1
# - 0n² 2 E1
g ( Σ
(T--1-1 Ti)
= N 3/ - 0r E1
(g (/1n)) Tr+..
78

---

Published as a conference paper at ICLR 2022
Now by the definition of 1, T++1 C/1/². Hence, can write
LHS S 8 31 B1 BUU
(c. (antt2//?))100))
i=1
N 3 ( (C
But note that Xy's are a.s. bounded between 0 and N + 31, which implies the LHS above is at least
- -NN + 31). Therefore, we finally get:
PU (Gnfn
2N + 6l
C8
i=1
Picking C C= =C = 2(2N + 60)/0:
P
(U(nnf2c//1))
S
1
(251)
Note that the differences between T; 's is at most Tmax = (l/n)) et (20155)) Hence, again for " polynomially small in other parameters, (25I) implies that for R 2C"/1f there exists R poly(.) such that after R iterations on the main sequence (wa). the corresponding sequence (T:) has either been in +(1) or (4) with chance at least 1/2. Repeating this argument log(1/6;) times (using the markov property of the process) we conclude the proof.
A.18 BOUNDING THE MGF OF X;'s
Next, want exploit X;'s bound the upward deviation of (ww). For fix 0 the goal here is to bound [0X,]] (this is a different 0!). More precisely, let F; be the sub-sigma field generated by variables wa from time zero to t, and Fi Fr, be the sigma field of the stop time т. Then, obviously, X; is measurable w.r.t Fy. We prove the following theorem:
Theorem For any > 0, the sequence (Ee"(X, (xxx; )2 a supermartingale with respect to the filteration (Fi).
Proof We proceed inductively by jointly conditioning on the previous X, and whether G. has hap-
pened or not, and whether we are situation (2) or * (3). We have
E(cxp(0(XH+1 Xo)H Fil
= (o(xp(0(X++>))) X;+ + X; (o)
+ #lexp(0((x++1 X,+ X; (0))1((()+())4
+
X, X; xx))1(((++(3)15
Now by the a.s. bounds of Lemmas M4] and 2G:
E[X+11 - X₁| G, W, s.L. (2) = RZ,1?
E E - X21 9, w, s.t. * (3)) -
(X++1 1G.) = 0. (a.s.)
Where Ri and Ri are r.v. defined in Lemmas 24 and 26 and are clearly F; measurable, This implies
B[(X++1 (9,, W+,
s.t. s.t.st
(2)) Fi] R2, (9,, w s.t. w.t..t. (2)),
BI(X,+1- (9,, wr, wr,st. s.t. (3)) Fi] R3n 1 wr s.t. (3)).
Now we mention the following fact:
Fact For subGaussian random variable X we have E[exp I exp(
Using the bounds of Lemmas 2 and 26 get that conditioned on (Gi, Wr, s.l. (2)).
79

---

Published as a conference paper at ICLR 2022
X,41 EX is a.s. bounded by 2m02)1/(p2X) and conditioned on {9i, Wr: s.t. (3)).
X,4 -EX,+1 is bounded by 2 (P2X). Therefore, using the above fact
E exp(((XX41 E(X++1| Gr Wy, s.t. * (2)))} Gs wr, s.t. (2) - 9
(252)
(x - EE(++1| Gi, Wr, s.t. * (3))) Gi wn s.1. (3)} s
E
(253)
which implics the notation of conditional expectation on sigma field:
exp(0(X1+1 -((X+1 (2)) s (=pp44/f000/((2x0) x2)), (254)
E
E
= <esp(m/000//002)))16 *3)). (255)
Now we write:
LHS & Bjexp(0(X - (
+E (expe((((X.)) - [[X F.l) (xp( - x,) exp( x FI
[Ejexp(0(X,+1 [[X F..)) exp( F expp - (0))1(((
s exp(O(X, {
+ - Xo) /1
+ exp(8(Xx - 200 Fi
& exp(0(X, xo) (1(9)
+ exp(0">))1? (p2x) -
(2))
+ e (p2x) - 0(9))) (3)
Now setting == 1 and picking X 2 1/p2:
LHS < exp Xx)) +1))+)+)+))) R...
= exp(X, - Xo).
Now by hypothesis of Induction we have
Ejexp(X.4r - -ooJ E[Elexp(X.+11 - F.I < EXexp[X; - XoHl S 1,
which finishes the proof of step of induction.
Now using Doob's Maximal inequality for positive supermartingales and R defined in (249)
P( sup (X; - (xx) 2 2)
I
P sup exp(X: Xo} 2 exp(z)) < Elexp[Xx [xllexp(=) Se == ISIRR
(256)
A.19 PROOF OF THBOREM? 7
Finally with the developed tools, we are ready to prove Theorem
Proof of Theorem 7 Starting from wy with L (ww)) < N, F(supi exp(X; - X,) 2 ((log(1/6.) < 81- Therefore, setting / = (log and a union bound implies with probability at least 28; we should have gotten into situation +(1) or (4) without the value of X, exceeding 2I. On the other hand, using Lemma Ae we know that G happens with probability least Ö(7²) for every t < R which is equal to 7; for some i
Equation (256) to get
80

---

Published as a conference paper at ICLR 2022
and when are in the situation of Lemma 26 along R iterations at most
As result, the chance that of Ey 's happen
RO(1)) = = ((log(166)))( +1)
0
But picking v small enough with respect to log(ō;) and other parameters, we conclude that with probability least 1-6,, after rounds, we should have gotten into situation *(1) and not x(4) and not exceeding N + 21, which means that X; = L"(w,, has gotten under the threshold 8g, Note that as soon as that happens, we terminate the algorithm. We claborate on this more in Appendix A..1
A.20 GAUSSIAN SMOOTHING
In this section, we describe our smoothing scheme and the approximation that provides which enables to keep the signs from the case O. Recall that we use Gaussian smoothing matrices Vi. ~ (0, /m/m) and W ~ N0, 3m2)) Here, we will particularly specify lower bounds for 31 and 32 in order for our sign approximation to be precise. On the other hand, we normally prefer the smoothing noise to be as low possible the primary and smoothed functions are close, so we set 31, B2 equal to their lower bounds, and use this setting in the other parts.
To begin fix one of the imputs 2,. In order to reduce and simplify the amount of notations, refer to the sign pattern matrix (diagonal sign matrix) of both the first and second layers by with the appropriate indices. More specifically, for the first layer, we refer to Sgn(W/(0) + W + Wo)a; by Di, and Sgn(W((") + (1 - 2/2 + W + vī7W")æ; by Dr, Similarly, for the second layer, of course depending on the input vector, we refer to the sign matrix with respect to the matrices ( + V' + V and y( + (1 n/2) + VP + /n/l by by Dr,p and D. .p.ry respectively. We introduce two new notations as well for the output of the first layer with respect to different matrix and sign patterns:
(1) = W'D, dp (W()) + +(1 -1-1)) W) + W + VTV*)z
(257)
/ W*D, .nn (W(0) + W W VTV* Jar.
(258)
For further brevity, we sometimes refer to (2) by x'.
Now we are ready to mention our approximation theorem regarding the smoothing and the sign changes.
Lemma 28 Under the conditions K1 m Z C1 + 81 m and m2 2 my log(m2), then for every e [n]:
Ee a dD.
pm (V(0) + (1 n) + V2 + VTV*> p. (W(0) + W"" + W + vTV*)
- -a -a (V,0)) (1-n) V2 + Vn D. (w + (1 (1-1)W' + W + /nV*)z,
< nozgo! [C= +
/m3) + Vmmmm Ci] - 1
C
exp { ( 2/3
+ (2/3
+ + R2/m2 + ci) ( 2xxpff2//322)) (2/(3239))
C2
e'may My = 17
(259)
xlym,
81
Proof of Lemma
81

---

Published as a conference paper at ICLR 2022
We can bound the Left hand side above as
LHS S
Ewe,vea" T D. (n + (1- n)v' + V + VTV") .. (W + [[-nn)Wa + W + vTW
-' + (1- VV /
//V) ... (W + (1-n)) + W + vnW*)
+ (1 -n) + +W //W-)m + Bwe.vo a² D. p((() + --'''' + V + +VVV" 2. (W
7)V' / + V2 + DW + +1 - 1)' + W + V1l )m: -a -a_Di,,(VV0) (1 (1-
== A1 + A2.
(260)
We bound A and A separately. First, we start with A
Let P; be the set of indices j for which (((2))) + Vj)a'l S R R² happens. Then, from Lemma BT we have [P| S R m2, Now for j E [m2], we write
{sign change in ith neuron} |amount of changel
(261)
I < x' + =VV Viz¹
E
vmz (11 IVTVTa'))
(262)
Moreover, note that
1Vja' 17((=' - ob00
IVj'l VV (00) (z.))l-
Also, because |!V||| < | < 2C²s plus using Equation (28). can further upper bound the
above indicator as:
1VfK E (-V / Vj (1 + / min ( (,0
1
(nll V + < (x))l
x
mm
S 1VVVr E (-v,00 x' V'VV''' Vja²
2 htt///////mmpm min ( (z))) - 2'
1
x mm² (2n - /nez\ mz M2 10 ol (x.)).
Taking V e/(2C2/ we can further upper bound as
< 111Ff E (-1 x' Vjsl 2 min - ( 1/ V32')}
x /V/ne//m2llzt' (00 (I:)].
Therefore, conditioned on x':
Eve [1 (sign change in thejihh neuron} lamount of changel
| |
P(Vf'' E (-V, o' Vjs' 2 min σ (zx) |=111) -V,0
x' -V/ Vj
(VTez/m2)lle - o (0) (x:)]l.
Now notice that for j & P.,, we have
- (0) -V 12 K
Also, note that the variable Vf is gaussian with variance |/// Vm, Therefore, conditioned on
x¹, for j & P.,, we have (note that x does not depend on the randomness of VP):
P(Vfa' E (- x' ViSl 2/ min min 200) (x+)). 1=/11) / -'/00''- V/d'))
82

---

Published as a conference paper at ICLR 2022
X exp {min() Vi Vjs'
1 - ///11///2//=111 1132/ / mm
x ((1x21)) (/22///2)=+ x (yTee (|ln - 2f (xx)ll, [12111)//))//////))l ml)))
This equation follows from the fact that
P(a SONNNDE la bj bl min miinniaan fa,b//o²
(263)
On the other hand, note that for V C² (Vm
we have:
C2 (v
2//3
(Vmg
R 12
|لl|| 2 2/neallz'11 Mm2
2/m²
which implies
S exp (R x2| 1F
S expp- cc ( (8,3)) (v722/BB)
On the other side, for j E P., we can write
P(Vfa' (-V,
r' - Vja 2/nee
min (z)') (4) 11'211// -' -Vz'))
2 (11=1113// m22) ( (e min
min (1|=' - 600) (x:)ll ||'|||// mm2) = min |2 - 110)
Therefore, overall using the fact that ||V & /2/ ml we can write
A
Σ exp (-//// (
(2) (000 || -c00
(x.))
JEP
Σ (Vnez/32) o/ (/nes/ma)le'
+
jEP
m2 x exp { 0//33 1- (V
2/3 2/3 (v /2) x (vnez/mm))
IP:l
+ n033221
min faln (0)) (z: ||= -
m2
C2
S ne 1
minfl=' -
(10) / 11 (x.))) exp ( (VT2gk22)/3/ +
(Vmgkkz))/3 )//3
(264)
Next, we bound Ag. First we bound Ew ||x - 212)) ||. Recalling the setting C2 21/ /vAo and the definition of in P from Lemma II, we obtain that for j & P. we have for all E [n]]
w x. 2 c2/Vmi,
WWaz.1 S c2/(2
which means for j E P:
[w + Wf)a;1 2 (2/(2
(265)
Also, we have
P S C2 /
(266)
Now using Equation (1044) in Lemma E we can write for every i E [n]:
val; = 1 (sign change in thejth neuron) x amount of change
1 (Wfa, E (-w)0) Wjs: W/ VTWJ mi, -w,
(0) x:
Wfr:))
1 +nW
X vm,
83

---

Published as a conference paper at ICLR 2022
Using the fact that [[W||| S [|"|| |r S C1, and Equation (IC)9) (|WW11 I e
ma mi
and picking
eym we obtain
Civm,
I[ E (-W; I2- W -o - -w x33 Wjz+)}
1
x
(vilW3 + 1ll
Vm1
I 1[ E - x; Wi - -
m3
- - x, - Wjax))
mm
2
m3 (vne
V m
mi
Now for j P. because Wf,r; 2; is Gaussian with std
8
ym,
Ewe [ual,] S P(Wf vi E (-W," x4 Wjst: 2/700
m1 3
1
vne Vmg
x
vm
vm
\m
exp fmin - W (0) x; Wfs: - 2
mg
w x' (333/)/(/223///mmm)
vm
mg
1
Vmg
(BI//mm))* x (v me mm
Vnee vml
mm
Now from Equation (265)) and by picking
/I S
so that
u/
Vma
2 1
S
mm
then
e emmg
LHS S expl
(267)
3imi
On the other hand, for j E P we have
Eval, S <PWWfx; (-W;
Wjaa 2/
Vmg
-W x; Wjass) x
1
vie Vmg
vm
\m
mm
Vm3
Vm3 emm3
x (B1/Vm,)
Th vm
vhe
(268)
my
3.m1
Now define the following random variable with respect to the randomness of WP:
m
Val
1 (sign change thejth neuron} x |amount of change
then for every ls E [ma]. we have
Fk 2b S Val,
(1) [12)
which implies
[1x) (011)=z()) 111) S vm3Van Vol.
But Combining Equations (267)) and (268):
P
e² mm
EV S hupf-c2/(32))) (3233)
"
my
3
< eepp (xp(-=2/(3233))
C2
0 ms
Ri m
3
which implies
E Ew ||/(1] - -2((3)1 <
+
C2
)n
o²
m2 v mg
(269)
kiym,
11
84

---

Published as a conference paper at ICLR 2022
Now can write
T D. (V(0) +(1- - Vo + + (クV*)=()) - -a (o(10 +(1- + vo + (クV")="0)
1V (0) + (1 - ,) + V2 + (VV;)(=/13) -
mm2 1=1
(1 (2) 00 (1 (2(00 - 210) + (V9(2(0)) - x002 + volli + - 2((0)1
mm j=1
(x 11) (2 - x(10) + vmz j=l
Σ ((1 n)][ +, 111111 - x 2011
mm
m2
(1) Vf x((0) + (11 (1-m)) -)>-)>>\'' +"
|1/ x000
Now by Equation (12)) in Lemma III (i.e. | 2 v and the fact that || S C2. and by taking
C2
vī s VC2²
we have
2 C₁
(270)
so we can bound the above as
72 Σ
LHSS
+ -V (18(6(1))-(1111) -1 2000
V m
Furthermore, using Lemma 32 and noting the fact that the entries of (0) are normal with standard deviation K2, we get with high probability over the randomness of (());
/m2 Vf(x"()) (1)) R2
+ Log(logmm))))++0 ||2/(0) -210
Now note that V (2.12) (2(()) is normal with standard deviation expectation with respect to VP:
Ag Vm,
-2(0))
Hence, taking
Evel a Dr (v + (1 V) + VP + v1)V")=2 - a² D' + +(1 + VP VnV*)a''))
$ [Ray/m2 K2 mm/lmloomms)) log(log(m2)) + C2 [|o/ - 2010
(271)
Finally, Combining Equation (2624) and (27l) and applying it to Equation ((61) implies with high probability over the random initialization:
Ewe.ve ot D. Di + (1 V' + ve + vnV*)
-a D.D,,,(VO (v 1)- ve kVV
A1 A
C
A
" 1 - exp ( (- (v/2 +
-000
(Vmg
Ew (R2/ma + RaV (log(mma)) + log (22)) C2 (12/12) - 2013
85

---

Published as a conference paper at ICLR 2022
Now notice that under E using the assumption K1 KIvm3 2 C1 vmy and Lemma 33
have
|| 2 10 (x:) - || 6 (z:)
2 K1 Vmg - (CI + vmz3i)
2 Ki m3
and
000 - (C1 + vm33i)²
(272)
which implies:
Ewn min | - (0)) (s:)) 11. || (.0)
< Ewo - 00 (x:)]l / +
(z;)] (C1 + 31 (81 /m Ew- (FF の0
(z) (x:)l
x (C1 + 3m (1i m
V 31 Ci expl-Ci/
Substituting this above and further applying the result of Lemma ix and Equation assumption that m2 2 my log(m2):
26
and the
A1 + A2 S no333
[C1 + Vm33r) /111 + [ Gi] expl (S/(8m)))))
C2/3
x exp
(Vmgkko)273
+ ( (xxemmm/()(exp////////
(exp(= +
C2
@2may mg
KIvm
B1
which completes the proof.
A.20.1 SETTING 31 AND $2
As we mentioned, to minimize the amount deviation of the smoothed function compared to the original one, we prefer to choose 31, B2 small possible. (The benefit of such choice, indeed, can be observed more explicitly in other parts of the proof, e.g. Appendix A. Observing the bound in Equation (259) and noting that can easily make the exponential terms orders of magnitude smaller than the poly terms, it easy to find the following optimal setting for the smoothing parameters:
B3 = 0, (p((F) (Vmottt)
B1 = O, mma/m// ((I1m/m)))))
Using this setting, we still can make Rg arbitrarily small. Here, we remind the reader that Op only cares about the non-logarithmic dependencies on the overparametterizatin,, i.e. mi, m2, my, Kiy K2-
86

---

Published as a conference paper at ICLR 2022
A.21 BASIC ToOLS
In this section, we introduce and prove some lemmas that we use in our analysis as basic tools.
Lemma 29 Suppose V(O) E Rm has standard normal entries and a is random sign vector. Suppose thela 1, R < 1 are given thresholds, such that
m2lt Z ma(log(1/ + log(ma) + log(log(m2)),
18 x mmmmm/
Then, for the following quantities:
(2(( = # #(j [m] 11 = R)
(z # #ij [m] 1 (0) 21 2 2).
with high probability we have
sup N S m2R, ||
2 m)((og(ma) + (gg(lo(mm2))) ||
sup
Proof of Lemma RA
Suppose B1 (c) is cover for the Euclidean ball in R with precision We know
[e) & (1/e)m².
Now for fixed ||>||| 1, we have
P( x < 2R) $ R.
Therefore, using Bernstein, with high probability we have
# (j E [ma] ( x| 2R) S + v VmrR+ 1.
Hence, using union bound, we have with high probability
sup (E
# #(1E E [m]: 1V
s 22) S R2 Vlog (i(c) V m2R
log (c)
my = =m2R + /m, Rmg log (1/)) my log(1/)).
By picking
6 $ RR(V my log(mama)).
The assumption implies m2R 2 my (1e)) which implies
LHS S m2R
On the other hand, note that with high probability we have
sup JE(ma)
J. S
V1og(m2ma).
(273)
Now for ||,'| || = 1 which is not in the cover, if is the closest point to it in the cover, i.e. x: E B1 (c)
and x z'1 < 6, then for every j E [my] we have
| 02 1 (0) x'1l < I |||
x'll S /mg log(myms)c & R.
by picking small enough constant. Therefore, for j that |V 2R, then
1 (0) x 2R R R.
87

---

Published as a conference paper at ICLR 2022
Therefore, get that with high probability, for every ||,|| 1: |V
# (j [ma]]
x S R) Z m2R.
sup ||=|||=
For the second part, note that for ||>||| 1, by the tail bound for normal vars:
PW
(0) x 2 0/2) e -0//
Hence, again using Bernstein, we have with high probability
# Hi E [mz]
1 x 2 0/2) x m2e m /8/8
Vlog B1 m22-0//8 + log [1] (e)
02/8 -0/8
sup (eBi(e)
S m2e /8
m2e-0115 m3 log([//))) mge 02/8 + m3 log
By picking
S 1/(v my log(m?mss))
0818 S m3, all terms are dominated by the third term so we can and using the assumption mae bound the above as
sup # j E [ma] 1 x| 0/2) & ma(log(ma) + log(log(m2))).
(e)
Now for ||>1|| 1 not in the cover, for the new write
||V, (0) xx| ( 2''' | ||| x'l v mmg log(m2ma)e S 1/2 0/2.
Hence, with high prob.
# #ij [jE E [ma]
1 x| 2 0) S ma(log(ma) + log(log(m22)))
sup
|||||=1
Lemma 30 For E &d and W E Rmxd which has standard normal entries (and a is a random sign vector), we have with high probability:
sup [(x) ||||=1
TT o(W())) s Vd.
Vm
Proof of Lemma 30
For the first part, first compute upper bound
E sup Lat
La"o(W("), |=||=1 Vm
To do so, we use Dudley's chaining. Note that the for I1, E Rd, the variable a ( x1) a (W x2) is subGaussian with parameter ||z] #2|1. the variable f(x1) f(x2) is also sub- Gaussian with parameter || z2ll. Hence, by Dudley's integral:
E sup La" ((W()))) S L/' Viog(N(B(.e) Va.
|=||=1 mm
Now for a fixed x, note that
m W1, W2 S [W W2llE.
_ Lo (W1x) Vm
_aT a (W2x) vm
S
j=1
Hence, the function fx) is 1-lipchitz with respect W and /2 norm, so is the function sup f(x). Hence, by Gaussian concentration, sup f(x) is 1-subGaussian around its mean, so we finally get with high probability
sup f(x) Vd +14+111 11
88

---

Published as a conference paper at ICLR 2022
Lemma 31 For
C2 2/3
R
(Mm2k2)2/33 22/3
have with high probability over the randommess of V
# #(1 E [m2] 1(V,)) + Vj)a²l s R & R R2.
sup v/,"% 1s
Proof of Lemma 31
Note that obviously the condition of Lemma P is satisfied with this choice of R = R². Therefore, with high probability we have for an arbitrary x':
# (1v, 2'1 S 21 2 xellz'l) I) 2 m2lt.
On the other hand, note that for E [122] such that [Vj''l 2 Rea||='],, we have
|||= 2 1Vjz' 2 Regl|='1,
which implies
|V Rs2.
C² of j's, for the rest we have
Therefore, there are at most
Therefore, setting aside m2 +
R2
((V + VJ)=' 2 1V - Vi 2R Rig ||, = R
C² R
Setting Re as defined above balances the terms m2 and
which completes the proof.
Lemma 32 If v(0)
mmx xms is matrix with standard normal entries, then with high probability
V 2'1 \mz + Vms(log(ma) + log(lo((ma))).
sup |
m
Proof of Lemma
Let B1 (c) be a cover for the unit Euclidean ball with precision c, for which we have [c] S m))
Now for fixed [i()), note that because v is standard normal variable, the random variable 1 x'
! s' is O11)-subGaassiinn which means m E (IV, - V x'))
is also ((1) SuGausiannn Now from the tail of maximum of subGaussian variables:
Σ ( x - (")
=|) S /
v m3 log(1/e))
BE (c)
1 1=1
On the other hand, note that BIV x') O(), which implies w.h.p:
10 æ S v mm + v mg log 1/ee).
sup (E
mm
1=1
Moreover, note that again by the tail of subGaussian variables, have w.h.p:
|V: S Vlog(moma),
which implies with high prob for every j E [mg]:
|| S Vmg log(m2m3).
89

---

Published as a conference paper at ICLR 2022
Now by picking
(Vms log(m2mas)
-1
we get with high probability
(0) x S mmz + (mmg(og(mma) log log(l)(()2))).
sup (e) m
(274)
On the other hand, for an arbitrary I' with ||>||| = 1, i (i(e) the representative of x', we have by definition || xl1 S which combined with (A.21) implies
| 00) 2'1 2-1- 20 21| = 1 =)1 |1 (0) ||| - z||,
X v my log ( V m3 log(m)
1 1.
Therefore
x S mmz.
(275)
m2 j=1
m
j=1
Combining Equations (2.74) and (275
we conclude the result.
90

---

Published as a conference paper at ICLR 2022
A.21.1 DEFINING THE RARE EVENTS Ej
Lemma 33 For x²(2) defined in Equation 258 we have
Ewellx/(2) - Φ00) (xx) Ew Bwollll (a))) E C1 + vmyBi,
Ew- (2) (x:)] x Ci + m333.
Moreover, for the events
Ej = (WWf. 2 C1/ mm/m3/ E= U,}
we have under E
- 1100 [1=
(2+)l Cc.
Furthermore, E happens rarely:
P(E) S my expl-Ch/(8mp))
Ew Ew.1(EHll)(0 (a:)1 - Vmgmm + Ci expl-Ct/ (8mmmm)))))
Ew 1 (EH]l// - -000 (xx)] S [Vigmi B1 + Ci exp(-Ca (8m
Finally, we have the following almost surely bound:
[x.12 s S + m3
Wfzzl.
m
Proof of Lemma cx
We start by writing
m7 >
1
WF + +(1 mn) + V/ S
WF zzl.
(276)
vm,
Vm
j=1
Now notice that by Lemma we know for every j $ P:
( xıl 2 02/ /22.
(277)
(11 W 02/ (2
(278)
In addition, by Equations in ([144 from Lemma B. for every j E [m1]:
m3
|Wj]l s 1i
mi
so by picking
11 S (2e
we obtain
n/W xi1 <
C2
(279)
A
Combining this with Equations in (278), we see that the signs of (W! + (1 n)W; + JTWj) ). and w/ x4 are the same for j P.
Moreover, the matrix (1 W² + VTW satisfies
[1(1 w' VnW* (1 - n)C + vT/2 Ct,
by picking v S Ci/VLz Hence, the conditions of Lemma R are satisfied and we get:
1 W' + (1 - n)W" + vnW")=, (z))ll S Ct.
(280)
Vm,
91

---

Published as a conference paper at ICLR 2022
Combining Equations (276) and (280)
|| - 1 (1:) S Ci + m3
Wfaal-
(281)
1
In exactly similar fashion, one can derive
(x:)) S C1 + vmg
Wfaal
(282)
vm
j
Now first of all, note
Bw
Wf 24 - 31,
m
which proves the first part of the claims. For the second part, note that by the Gaussian tail bound
P([Wfa 2 C1/ /m/mm) exp( exp(-Ci/(SmgBff
Therefore,
P(E) S P(E)) I ma expp-ctpppp -c)
Moreover
1721 Ew 1 m
Wfaxl S Eiv Vm,
1
ΣΣ
118 + Vin Σ Ew (E;H|[/
da s710
mm Σ Σ
E Ew WFfxs + vm
Ew [[ff::]
E5] P(E,)
$2 j&12
x m1B: + C1/Vmg expl-Ci -P (8m²
Plugging this into (2 finishes the proof. Also, under E by Equation (281) we have
| (0) (1)) c..
Finally, exploiting Equation 282)
Ew (2) (x
S C + mg mi
Ewe Σ Wfxxi12 s S + mmBwe EiWfai
< C7 mg8f.
92

---

Published as a conference paper at ICLR 2022
A.21.2 BOUNDING THE VALUE OF f'
The following Lemma provides a reasonable bound on the value the smoothed function.
Lemma 34 We have the following general bound the values of the smoothed function: With high probability over the initialization, for ||W'|| & C1 |V||| S C2 and vi E [n] (having small enough
choices of B1, B2 described in Appendix 2020
& (K2Vmg + 82) Vmzki Ci + + vmz3i) ) + C2(Ci + vm33i),
which is O(C, C2) for large enough overparameterization as described Appendi Moreover, we have the following almost surely bound (with respect to the randomness of W and Vo):
& (K2v/m + [[V)[l=) /mggt + C1 + /mal vm,
Σ [Wgaal)
+ C2((C + Vma( mm
Ewwfail).
Notably, with slightly higher overparameterization, the high probability bound in (53) holds even if we take supremum over x.
Proof of Lemma
Using Lemmas 60 and 33 and using the fact that (I;) is orthogonal to the rows of V
(recall x. 100) (a;) + (x²)
IfW tWe
a" "V((10)s)))
vmz IVVY + vf)a1
Vmz
(noVmg)llzi1++
Vm, Σ IVfzll + (x:))
(K2vm3 + ||V + (211)(2
$ (k2 + [[) (iigh + Ci + /mal vm
Σ
[Wfail) + C2(Ci + /mal
Σ [WFxx1l)
mm
(283)
Note that above, if apply the stronger worst-case norm bound of the first layer's output presented in Lemma MR we would get supr,/[=r [r]||/|=] |=1 Ifw (=- is bounded by the RHS, which in turn proves stronger uniform bound on f'
Similarly, this time by taking expectation with respect to W and VP:
1fw Viv.v..z (x:) = Swe.vofwr,vrlae
< Eww.velfwr.ee (z:)
= Ew Ewa / + 82)1|a;11 + - (x,)l
S (K22/mg B2) Vmggh C. + vm3B) + +2 + vmgBi).
Corollary 8.1 If we set C₁ = =C2 = 0 above, we get
1%,(( < (N2vmm3 m3 + B2) Vmyki + vmz8i).
the point being these terms go to zero by an order of ((( Therefore, taking (Mm2)t2)33 << B, make sure that Ifr < B, by the 1 smoothness of l and B bound- edness of the labels we get ((6,o((.))))) < 4B2.
93

---

Published as a conference paper at ICLR 2022
A.21.3 BOUNDING THE DIFFERENCE BETWEEN ORIGINAL AND SMOOTHED FUNCTIONS
The following Lemma bounds the difference between the smoothed function and original function of the network.
Lemma 35 Bound on the smoothing change under the assumption m2 ma log(m2): with high
probability over the initialization, for any (W) with [|W'|| & C1, IV I C2:
(w:) - -fw.,v(x;))]
S 5/ m + C1 + vmz3i) + (C2 + K2 m2 (ei))//g.. vmzB.
Proof of Lemma
We write
(fwr, - (x:)) (f Eww.wafwwwwywwvdc..)
= -|Bwerv (fwr (w-.wo-wvre.))
S Ev (f fw-+w.w-vv
In the following, means apply Relu activation the vector in front of it (entrywise):
LHS S Ewe.yo
Vmz a" (V(()
V VP)
1
W oo W'o(W) + W' + WP)x;
mm o + Vn)
W Woo(Wo) w' + Wo)x;
m
+Ewe.ve
a ( (0) + v²) Vm
W (WW()) + +W + WP)
mm2
mml o (V (0) +
W W'O(W =W')a
Vm,
Now for the first term above, using the previous notation of a! representing the output of the first layer and using Lemma B3
1
Ewe.v
mmz a" (V +V' + VP)
W W''(W(") + W" W mm
1
a ( + Vy
W Woo(H(1) W + Wº)
Vmz
vm
Σ VVfa/1
< Ewe,vo
mm²
S B2 ||rgl
< B2EWe, vo (2)) + (x(2)
$ B2 /my + C1 + vm
(284)
For the second term, by starting off with a simple triangle inequality:
Ewe,vo
Vmz at (V(()) + V')a
at (v + (ob + (12))(
mmz
mg (V + +V))(a² (x)) - ((2)((1))
< Ew
Vmz j=l
v (a! -,10 (12)))))) + V3 - (xx) (122
< Ewe,Vo mm2 1=1
< <CZEwella' - <CBBwrll((o(((+))) - (x:))(x:))1
+ Ewe mm2
1 (2)) (0)) (2,) - (z2))))))))
94

---

Published as a conference paper at ICLR 2022
Now using Lemma 32
C2 K2v mmz Ew Ew-llzt (x,) (x)))
C2 + /22 /mg Ewr E vm, W
C2 + K2y mm
(285)
Combining Equations
BIE
and
conclude the proof.
95

---

Published as a conference paper at ICLR 2022
B APPENDIX
CONTENTS
Smoothness coetierents
96
B.I.I
Computing the Lipschitz Coetficients of Jw
98
3.2
Representation Lemmas
104
B.2.1
Representation Toolbox
104
B.2.2
Some Linear Algebra
105
B.2.3
Bound on the of
................................
106
B.3
Coupling for w.
108
B.
Handling the Injected Noise by PSGE
113
B.4.1
Bounding the Norm of the first Layer's Oulput in the Worst Casc
114
B. SMOOTHNESS COEFFICIENTS
Recall that for a function I' E C on Rd, we say it is ln Lipschitz, 122 gradient Lipschitz, and μ43
hessian Lipschitz point if for every unit direction v. 4 f Av) s pMo f xw) p2,
d² and ax2 f(z / + Xu) A33-
The aim of this section is to bound the Lipschitz coefficients of the loss {(,z) and objective L(W", V\) in bounded domain ||W'| < Ci, [I'| I C2. The following is our main Theorem this regard:
Theorem For given values C₁ C2 > O, in the domain ||'|| & CI,IV'II S Cz. for any label lyv S B, the loss function E(.. y) O((CiC2 + -2)))Lipschhit. (having enough overpa- rameterization) and 1 gradient-Lipschit x = fw. Moreover, the loss function L(W", V') is (0(C)C2) + By 2(C1 + C2) Lipschitz. &2+ (O(C)C2) B) 4 gradient Lipschitz, and 3 + (O( + By hessian Lipschitz, where 1 22 V are defined in Lemma 50
Proof of Lemma g
As in the proof of Lemma 36. let (W, V) be unit direction, i.e. | + 1iP = 1. Then, using Lemma 62) we know that for every E [n]: (ww.yv- = O(G.C2), so by 1-smoothness of the loss and (B-boundedness of the labels, we get that ((.3) is (O(CiC2) - B) lipshcitz point fw..y.. The gradient smoothness parameter of the square loss f. is bounded by
and its third derivative is zero. Now using these coefficients, we can easily compute the coefficients for L well by simple differentiation:
d I' (O(CiC2) + B)U
dA ((FW+ V (1:), vi = jē(f", vi) dx
d. (( (U (UW.AA
&
(T:), 1ē(', mi)( dx
11) i(' wi) dx
I'1 S V (O(C)C)) + BY
axb d W (2:) [ vi)l - 5 30 v1)
&²
I' d
J + "(' d'
dx3
ax
dx
+VV.VVV + (O(CiC2) B)
Moreover, note that
d
W + A 2(W' + +AW, W) 1=0
2(W", NeW..i w) < 2||W"|| 2C1.
dA
d²
|
+ AW = (W, W) = 2,
dx2
|[W
+ =
dx3
96

---

Published as a conference paper at ICLR 2022
and similarly for ||V + x Combining these results finishes the proof.
Above, we used parameters 11 22 33 the Lipschitz coefficients of f in domain ||| s C1, [[V||| C2, which we bound in Lemma BG below.
97

---

Published as a conference paper at ICLR 2022
B.1.1 COMPUTING THE LIPSCHITZ COEFFICIENTS OF fwr.v"
In this section, we bound the Lipschitz coefficients of fiv. in the domain [WI|| S Ci, S S2 by poly(m1, m2, ma, 31, (2) functions.
Lemma 36 For every point (W', V") in the domain [ & C1, II'I S O2. we have the following bounds on the Lipschitz coefficients of yw ((W, V) is a unit direction with |[]] + |V]2 = 1):
W.
dx
+AW
A=0
<
m2
B2
Vms(ki
+0 + +c2+31) (22 mev/mg + +22)
32
Vmg
(Mi N1 + Ci ((++11))
B2
mm2
vml
my
Vmlg
B1
K1
+.i
B
) (KaVm) + C2) 32 (
Ki + +1)
+
B8
)) 1
mm
vm
mm
mm
d
+WW, VV (xi))
dxa
W
2=
<
W1
m2
11(p)
|ms (NaVmm O2) + 833 (m1 + C22 +B8] 1/2
32
d3
d13 W" - XW, V A (I:))
1=
W 2 +
m2
111))
V ma (K2V/ C2)²
C2)2 + BB3) [mmI+ + 01)2 +3P]] = =Va
32
(286)
Proof of Lemma
Let
||
||V211
pWP, VP) = (v2n ma m mm (B2/ /m,) m2m )
expl
}
2,3//m1
2,3
be the density function of the law of 9 and Ve which is joint Gaussian. Then to compute the derivative and second derivative of the function in the unit direction (W. V), s.t. | + || we can write the value of the smoothed function as an integration with density p. change variable, and then take derivatives:
dA W www. +A A=D
dA Www.vefw-ww-wwwwww....
/ //W.A/-W. (W)))))) VP),(WP, VP)
dx
dx / ( (W' + AW), V+ - (V' + xV))d(W, V+).
d
But one can easily see that for fixed V and V. the set of functions fwi.y (x:) (W"- AW), V+ - (V' + AV)) for a small neighborhood can simultancously be upper bounded by an integrable function. Hence, the Leibnitz rule holds here because of dominated convergence theorem,
98

---

Published as a conference paper at ICLR 2022
and we can change the order of integration and derivation:
= fwi (zi) di <(W*+
- (W' +
AWW, V+ (V' + A v+)
=-f ff
[STA.+ (xi) (xx) ((VVV). (1 8
- 1 ( W++ - -(W' + -ir))
- V++ - -(V'
-
+ +1B1))
-
m1
m2
p(W+ - (W" + + V+ /-- 10---V -(V- + A))) v*))
= -/ [W+,V+(1s)) (1i) (W, ;);
m1
T2 vP) D(WE, vo)( Vo)
Wo,
By
EE
m1
m2
V vP)
B
83
A=0
m1 (W, Wo)
m2
v, vo) ) (ww.w.-+vHe))()))
Ewe,vo
+
(287)
BP
83
Similarly we can compute the second derivative:
& dx2 Swesi. A=0
d - I fw (a:) (W. 8
( (w+ (W''= ( ) -V+--V'+
+ ( +XD)))
ml
1/1
p(W+ (W' + +WW), V+ -(V' +X v+)
=/ [w+t (1:) ( ( V), ((
11 (W+ - -(W" + AW))
32
-1 (v+ - (V' + +
m1
1722
(IV, D.. m
89 j-,,
)) >} p(W -(W- + AW))
- (V' + v+
+X v+)
1122
= / [ (2:)
((V, V),
M1 Wr, ; m2
//))²²++ + (1V M). mm W. / أ) D ve)d vo)
=Ewarvo (
Bp
mi (W, WD) + m2 V vo)) 2 -
mm
||ع1 +
mz || |7| }) f (w-.A
33
A=0
Eweevo
( m1 (W, Wo) + m2 V vo)) 2
| +
m2
| www..awwww...
33
(288)
Similarly for the third derivative:
de
dA3 Sn d
w
+Nw (A. 2=0
ax / (ww- (1V 1), (1
(W- - (W" + xir)..
_
1 (vt - (V' + +)
m1
m2
(wV, (( 89
- -
B3 ) v))
p(W+ - (W" + +XW), V+ -
(V' + --
+X,))d(W+ v+)
m1
m2
= [fwII (I:) { (W, V), ((
B
-1 (w+ -(W' + +
32
1 (v+ - (v' + x1))
--++
mi
m2
-3( V). (( 82 -1
-1(w (W+
(W'+ + +Xi7):
82
-1 -v+ -(V' + -V*'
x17)) (w, ( ( - W.
-
32
m.
m722
m2
p(W+ - (W + AW), V+ (V'+ + + V+)
=Ewe,vo (05
mm (W, Wo) + m2 (V, v,)) -3 3
mi
( Woy +
m2 (V. vo)
m1
|| +
m2
32
B
32
B3
82
99

---

Published as a conference paper at ICLR 2022
Now for first derivative, exactly similar to the derivation in (28
can write
Ewe.vo
m
W,
W
+
m2
V. vo))
[ www
33
< Bwe.ve
m1
W W
+
m2
V, v0) >
[87
< E
mi
W. WP)
m2
V. vo)
(
|| |1. |2 (2)
Ev
Σ
88
BB
mmz
Ewe.vo
mh
W, w
+
ma
V. (/vr)))
( | + ||
||
|| 1111
(
B3
32
Vmll2
m2
EV vo) |,=112x(?11
wwnasy + [IV'll) Ew mmz
(v. (V.
Σ
IV
33
+
m1
(BBrella? (22)
1| ( W. (.wm))) Saveee + +11")==) + Ew
(W,Wo))
Byy
Σ
87
mm²
m2
Evvl (v) Ew (2)) ( + C2) + Ew mml
(v. v
Σ 1V3 x (111e)
52
+
mi
(Ewwellaf
1| ( (w, wo) ( ( + C2) + Ews ( (W, wP)
|
Eve Vmn
Σ 12211011)
]
where the last line follows because V X C2. But notice that because || S 1, || S I,
then ( (V. Ve) and ( (W, We) are Gaussian variables with variances at most 33/m and 3 /m
Hence
Eve V. v. - V
(289)
Ewa (w, ) - B1 /m
(290)
Similarly, using the same derivation as in ((33), one can also get the following a.s. bound (over the randomness of Wo):
| 11 S Vmig( mm Ci + vm]
Σ WFfaa).
(291)
therefore
Ewo (w/.l1/(2) ||x1
S vmg Ki + +C + +Ew"
1
Σ I
(292)
/m,
E Vmgg ki + C1 + t1)
(293)
Moreover, for every j E [ma]:
Eve (V) (2 (2)
Eva (v, vo) )²
V Evel 12)
B2
B2
32
1
(12)
1
(2)
Vmly vmlz
m12
Ew (w. ( we) Wf x11 v
88
(294)
m
Similarly, using Equation (2911) we bound
Ew ||:;; ( /1/ ( (,, w z Vma Eww= < (.) >
K1 [k]+Cii)
+
Ew Vm
Σ
W, we)
|IW
B1 S S
Ki +C;
{
(295)
mm
100

---

Published as a conference paper at ICLR 2022
Now applying these bounds (290).
(293)
and (295) to (289) and using the fact that
Ey,
VV (2)
S 8211= (2) 1|.
m
we get
LHS
m2
82
/m + C1 +
C1+ 31)
(NaVm3 + +C2) + Ew 83
|| 12
mm2
mm²
m1
31
11 + +GG +
39
(22Vmg + (22) + Ewr ( (w, wre) (21la, 1)
02
mg
Vm
/m,
72
32
/m + C1 + 31) (1) (12V/1g + +c) + \mz
B3
Vrng
Ks - C1 + 81))
1
Vmz
(Vmss
81
Ki + +i)
- Villl
39
(naviTs (Navms + +C2) + B2 m
31 vm
ki +
ci)
vmn _
B7
))
mm
To make it easier for handling the second and third derivatives, we first bound the expectations of Swowe www.e.//VVe... VV... (1²) which enables us to use Cauchy-schwand Again using similar derivation
as in (83 and Equation (291)):
Ewe, vo P ww
< Be (2 (2) + C2ll,, 10 1
Σ
1V )²
mmz
(K2y + C2) |0 11 + Ew Ev
1
VV [012((111
m2
3 (k2Vmg + C2) E Ew., | 11 Ew 1
Byy
12) I
x
Ewe m2 $1
Σ
Eve
(2) Evy (2))
IV x
m2
33
11 + Ewe333 11/ 1,,,,,111 mmm - 1)
2 (62 + Ew 1, 112 + Er
|
m2
m2
3 (
+ c2)² + 32 E 12
x (NaVmy+ +22² 83) Ew 19 +C
Σ
WFfxi) 2:1 2
mm,
j
x ( +2)² + 33) m3 (KI +0,]²
1
Bry
W xr, 1
Σ
Ewy,
WW x. IB WWF m.l
m
m
j1
x
C2)² C 38 m3 (M +())+
B7
mmm
m,
m2
ms (RaVmyg + C2)² + 23) (m1 + +
(296)
101

---

Published as a conference paper at ICLR 2022
Now for the second derivative, can proceed by applying Cauchy-Swarde
df
di2
I V
(m) (W, W'")
+
m2 (V, vor) 2 - (m) B
I
+
m2
ww.
87
32
m2
(W, W
3 11 + m3
(V, vo13
m2
1
2m m2 (W, WP) (V, vol
32
33
fw WW..W--oo (x:)
m (W, wpy=
m1 3
W
m
(V,
VV
m2
12 +
2m1m2
(W, WP) (V, voj
31
32
33.33
V Bw WW+toev++Veure
Now note that the cross terms have expectation zero, so we get
Eweevo
m (W, we)²
B
11 (W,
B
+
(V, voj2
m2
32
[1111))
4m² 2
3/
B Bwe, vo (W, WV),(V, voya
Ew www.wwwwww..-rr
m²
m3
4m, m2
www. 2
Vil
|| [WIIIV y /B
B1
32
B3:3
m1
12 プラ
Ewe,v- www..reew/..................))
<
V
Now applying Cauchy-shwartz and Equation (296) to above and combining it with Equations (288):
d
(3Ta) 1
m2 B2
1111))
+ C2)² V m3 ((e)Vm3+C2)++++
+2)2++ (8) [( + 01)² + +
Similarly for the third derivative:
d3
dA3 S
Sw -=
(x:))
-Bwerre
(W, WP)
m2
(V, vo) 3 -3 3
m1
(
WP)
m2
(V. Vo)
m
11 +
m2
32
3
33
B3
V
(m7) m1 (W, WP)
(
B
+
m2
32
3 - (V. vD))
3
m1
(,, WP)
m2 32
(V, vo))
3
m1
m2
33
[1
2
V Eweevo [w=+w.vivrr(x)))
(297)
But note that
Ewe.vo
(m
(W,
WP) + m2 (V. Vo,) 3
- 3 ml
( WP) + m2 (V. vo))
(T))
|||1 2 +
m2
]
2
32
$2
B
32
83
82
mi
( Wo) + m2 (V. vP))
2EWr,vp
87
B2
+ 18
my
W
2
m2
E Vv
mc 3
(,, wP> + ma
(v, veev))
32
33
33
102

---

Published as a conference paper at ICLR 2022
Now note that of (W, W + my (V, V*) is normal variable with variance Therefore, by the bound on the moments of normal random variables:
35
[
P
LHS S
W
12
(298)
32
Plugging this into Equation (29 and also using Equation (299))
d3
dA3 W.
+AW, (TI) 2=0l
m1
||
+ $2
m2
[/19))
3/2
V ms (122/m3 + C222 + 33) [11 + c12² + 18
8
103

---

Published as a conference paper at ICLR 2022
B.2 REPRESENTATION LEMMAS
In this section, we prove lemmas mostly related to the representation power of the network, which we mainly use in Appendix A
B.2.1 REPRESENTATION TOOLBOX
Lemma 37 Recall the definitions of W and T from Equations (b-)) and (DDA) For all k. E [n]:
[ii trace(W Z S /n/(ma>olllV<lll>>>
Proof of Lemma 57.
a Vk. Z3) Σ
ma,e trace 2
VA (Ziz 7h)-
(299)
/=1
But note
(Zk 2x = 1/mi
W 2 [[ (0)
[ (0)
xn x (x)
(ov, v31)
m O x; ([ 0) 2z}.
m
Now note that (Iv, xx) < 1. and 1 (T x, (
(T) xạ. } is Bernoulli with
E1 [ 1 (T xx 1/4 aresin (xz //m
Therefore, by Hoeffding inequality we get
[7 2 H 0(1 (m1)
Hence, because obviously || [|2 S we get
trace(W; ( (W)
Σ Va H + (LLLV//L
Σ #=1
VA. 3,, + O(L/vm,) Σ VA.e
which implies
[trace (W,ce) - S (01///T)
<O(vn/(Vm, 11l))
S (m VallH
Lemma 38 (Bounding the rows norm) For every S S m1, we have
|W/tll S Vnm/a/ (v mmndo) /
Σ | |1
Furthermore, for every [ma), we have
|| 5 vnl / A
(300)
For the ease of notation, because here we want to work with row sub indices of the matrix W we refer to by W Proof of Lemma 38
104

---

Published as a conference paper at ICLR 2022
For fixed 1 j I my have with high probability the randomness of the sign matrix W
| mgg
mg
WR
Vk V 11 ( x4 0}l
mg
S /ms\/ Vmn
aa 1 (W x; 2 0]11
S /m/l/ Vmiy
E /m/l Vmz
1|
$ S/mg//V (ymado)
Σ
1elll
Furthermore, for every [ma], we have
|| I 1/1 m
(VT/ (Vn/ V domm) )/V>)>>>>ll>>>>>
Lemma 39 With high probability over the initialization, we have
| 13 +1 41++0mmmmmmmm)m) 2
Proof of Lemma 39
Recall from the definition of W in Equation
(6_)
11
n
n
W 1
V4 2
22
VR Vr.e (2, 2/
Vk. VA, + =
H ((I)))))))0((I))))/)/)//>>>
i=1 p=1
1| O(n/
B.2.2 SOME LINEAR ALGEBRA
Lemma 40 For S let ......, I' be s-dimensional vectors that approximately normalized and orthogonal to one another, i.e. given some 5 > 0, for every i j S n:
-8 (Fa.T)) 88, |r.11 < 6
Then, for any vector e we have
Σ (u, < (1+ n(n 1)8(1+))3 11)3)
Proof of Lemma 4I
Define
01 = Σ n,n,,, 0/ = v U1.
105

---

Published as a conference paper at ICLR 2022
First, note that
" ru, s (1+ 8)
Σ 1|me|1
i=1
= -1+ 8)1
Σ
(0, ri)rr:l -((1+
Σ (u.r))(
ISiFiS"
= (1 01 2(1+
Σ
Next, we write
(11,0- 01) = (c, Σ (,, (orrire)) Σ (o, riro a
I(,,ra) - E(0, (0,re)) ( - > ((n
2 Σ (o.r)))
Therefore
Σ
(u, (1+ + (|[bo] + 11v-
2(1+ +
Σ
1=1
151#55"
(1 +1]0 12 + ||| v2 v((,,
+ Σ
ISi$j5n
S + +1]1||112 2(1 + 6)
Σ
S1 + +1|+0|1011 + 2(1
Σ
[1+
(1 5)||0/1 + + - 1)6(1 1)8 1)
(1 5 + nn - +) ||1)
which completes the proof.
In the following lemma, we state trivial bound on the norm of o; based on E1-
B.2.3 BOUND ON THE NORM OF 2, S
Lemma 41 For every E [n),, we have
| S 1
Σ
|| = VG.
Proof of Lemma 41
By definition:
x.. = (H
ms
k=1
Now consider the Cholskey factorization 1 K KKT, Because of the assumption ||x||| = we know that the diagonal of H is all 1/2. Hence, for the ith row of K we have |K = 1/2. Now by Cauchy-Swartz we have
Σ K,,KK,
Σ Vn, K, IP 1/2l|VA|12
Summing i and noting Equation (59 completes the proof.
106

---

Published as a conference paper at ICLR 2022
Lemma 42 In the context of Lemma M. for Ç2 S 2nB², can substitute f by f such that
B
Rn(())) S (f) n " A"A
and furthermore, f is in the subspace of eigenvectors of A with eigenvaue larger than D 2 ). Moreover, the constant 2 is arbitrary and can be changed to any constant more than one, with the cost of additional constant behind the second term.
Proof of Lemma 2
For an arbitrary i [n]] and some given vector for (we will specify later), we define
i 8= fil.
and suppose the slope of (s) ) at point f is equal to Then, using the convexity, the fact that E(y,, vt) = 0, and the 1-smoothness E(., Ma), it not hard to see the following poincare inequality between the value and derivative of {(., yi) point f(:
c cs 20 21) == 28.
(301)
where from now on, for brevity, refer ((S,, mi) by t. Also, from the definition of â and again using 1 smoothness property, it is easy to see that
ElFT v:) - (c + 5)0 + E(ST 9:) = (c + 5)
(302)
Plugging Equation (50II)
HI2 and using AM-GM inequality:
e S 02 + + 62 + 2260 +
6 +
+22+35212
Summing above for E [n]. we obtain
Rn( < 2f*)
111//2
(303)
Now write an eigendecomposition for A A = E;= Au, for orthonormal basis {u]). and let f = E, you be the representation of f in this basis. Then, from our assumption, for arbitrary
f-t - s 4nB².
which implies
1
Σ
2t < 4nB²
8: A:5W
or equivalently
Σ S.Sw
7o < 4nB
(304)
where notice that En. A 72 is the squared norm the projection of f* onto the directions whose eigenvalue is at most w. Now taking 1 T2nz and defining f* by keeping only the directions in the expansion of f in the eigenbasis of A, for which X; > w, completes the proof.
107

---

Published as a conference paper at ICLR 2022
B.3 COUPLING FOR Vw, Vv
In general, because the gaussian smoothing matrices (WP, VV) can become unbounded, the gradi- ent estimates (V W.. Vv)= = ww.r&(fwr v. 9:) also become unbounded. However, in analyzing the stochastic behavior of SGD and showing that it can escape saddle points, is conve- nient to assume the gradient's 'ss noise vector is almost surely bounded. The goal of this section is to introduce a coupling between (WP, VP) and another random variable that a.s. bounded polynomi- ally in other parameters. As that the coupled random variables take different values is exponentially small while the number iterations in our algorithm is only polynomially large, without any con- cern instead work with this new random varaible, and with an overload of notation also denote it by (.).
Lemma 43 For an arbitrary parameter X 1, On any pair for (W.V), with ||W'|| C1. || S C2. there exist a mean zero random vector with respect to the randonness of the uniformly picked data point (3i, Vi) and the smoothing matrices We,,, WP22, V0.1, and Vo.2 which define Vw vv (meaning is a function of those variables), such that with probability at least
1 1-2expl-(X 11)dm/44) eexpl1(x 1) /4} 1-0 81,
we have
V Vw Vw V') + +A,
(305)
finally A is a.s. polynomially bounded, i.e. almost surely have
||| S poly(mi, m2, ma, C1, C2 B, X).
Proof of Lemma E
Remember that oy was the output of the first layer (by considering the smoothing matrix WP). Now with high probability over the initialization.
D(a)) dW'
ww.
=IVV, ww
D(x1))
IV www.W//w...... (x:)1ll
dW'
1 a Dv (V(0) V' +' +v))ll Vm2
mg D
mm
1
<
+ 1 ||V*)1=)
||iiag DW of{ (1pl)))))
mm
S (k2 + C + ||||||)
S (k2 C2 + p|)
(306)
On the other hand, using the final bound in Lemma
33
Vv. www.w/....wv>x.....
diag(a) ||41||
Vmz
Ki KIVM C + vmg Σ
Wfaz;
m
<iimm + Ci + //'
(307)
Denoting ł(fw44w.1 y+vve yi Vw,, v. voll(ww m ( (z:) vi) by Vw,.y, then combin- ing Equations (500) and (50%) and using the 1 gradient lipschitzness property of the square loss,
= d(e(f.g)) df
+ www (2.)
(I (2x) (BI) (kIvm Ci + m W /2/ + C2 1
(308)
108

---

Published as a conference paper at ICLR 2022
Finally, applying Cauchy-Swarts to the second a.s. bound in Lemma C
have:
(w
I (N2vm + [1 (mmgki (VV)g)))
C1 + /msslWel) + C2(C + <msl|W?lI)
Combining this with (308):
| w.lll
B + (K22/m + [[V (mggks + Ci + /ma/|waa + C2(Ci Wo.l1 [I]
(kIVm3 Ci + V 1 m2mmm + C2 ||
Therefore, using the Lipschitz bound in Theorem 9
Ww.r. - www. ut)l
Vwr.yr + [| V www.w:wwwwwwwwwwwwww.... v:)ll
B (,2 + || p [| Vmy C1 mm v Welll) C2(C + (
x (IImm + -c + / W ||
12 mmgms C2 + | + (0(C))2) + B)
(309)
Now we define the following events
E = { || 2 xVd31 V | 2 XVd31}.
E = [|| 2 8V V ||P||| 2 XV
where recall we assume X >> 1. Then, as we know the variable || has mean døf and is subexponential with parameters (d3t/m1, B0/, ff/m)). Hence, by union bound and Bernstein (Note that Wo.,, Wo.2 are independent):
P(E))
2P([1 2 XBiVd)
2P([] 2 2d
S 4max
expl eexp=<x22 (x2 (AdB5///m) exp(-(x2 ())88//443///11)
s 2expl- -xx 11)dm1/43 max (exp(- 2) 2 2exp(-(x (
Similarly for ||V|||:
F(E2)= = =(IVV'' x32Vmgg) S 4expp-(x 1)mgmz/4).
Moreover, because of the subexponential tails of || [} and || for each of Well VP, or VP*;
WPs,
B(I Et) & xVd3, B / x3d
B[| Ez) S XVm382, E(IV E₂) S 3m,33
Now Defining E = E, 23 and combining the above equations:
{(I[W>||(()) E WP (1 + 1
B[| E,) I(IW>)))(())
exVd (x2 1)dm, 22
=2VdB1(xexp) -xpxxxxxppxxx 1)dm + expl -
1)m3mz/44),
109

---

Published as a conference paper at ICLR 2022
and
E| 1 = |
s 2d expl-(x² 1)dm1/44 /4].
Similarly
[(I)) & 2/ (xx2 1002--1dm/1440 1)dm1/4) + +t xexpl- (x2 1)mam²/44)
and
B B( - 2m expl -x² 1)m3m²244)
with Cauchy-Schwarrd to get the upper bounds [ and (Ew- [W(l) < TEw |WeI|2 (for terms with only one W or VP', we simply write them as W and VP):
Applying these equations to (6
EI (E ) || s EI (1)
Bwe, Vo V W
(Sw vo (zi), wi) (=)1
(e
B (K2Vmg ||
||
(mggst + Ci + > + C2(C vmallWell))
(IVmg C1 Vmg W" k2 m2mll + a
B + (K2V (K2V (V + C1) +
(kimm C1 + mym + C2 + 1 Ev (
+ B + (VmgKi + Ci) + (#2m3 + C2v mg + mmg + C + K2 / + C2)
(
+ +B+ +
+ C,mn
+ wwwp:h/wEE|lll/y//////////111111
+ V (3, H[
BB)
(exp(-(x) - e 1)mmm2/ poly) m2, ma) = negligible.
(310)
But note that
V.r. = Vw +
Vww.' V²)
E( (fwv, y (x:), vi) + (WilW'1 + + (
Applying this to Equation (6II),, we get that if we define
A =
- -w. LW V(W.V'),
then
E [| s -esp(-(221))m//)) + eexp(=(x"
1)mmma/44)pol(mm) m2, ma).
On the other hand, note that using again Equation (HU9), have the following a.s. bound:
|||| (mly(m,, m2, myg C1, C2, x).
Defining
A₁ = A1
Ag (E)
A= A A2
110

---

Published as a conference paper at ICLR 2022
get that with probability at least P(E))
Vw Vw..v V*) +
and also note that
EA = EA 0.
Finally by the a.s. bound for A1, we have a.s.:
||||| I Bww.ve.......lAAAEEE [| ||
< (cxpf - 1)dm1/44 poly(m1, m2; ma, C1, C22 B, x):
-1)mmm(421)dm//4) - exxpf- 1)mamy/44)poly(mm m2, ms) + poly(m1, m2, ms)
which completes the proof.
Corollary 9.1 It is easy to check that running PSGD with unbiased gradient estimate V equivalent to running SGD after our change of coordinates, with unbiased gradient estimate V W' TV w v where T is the matrix for our change of coordinate, which is equal Y defined in Appendix A.J0 for the coordinates in V and simply identity for the coordinates in W Therefore, projecting both sides Equation (EI of Lemma E3 onto h- by multiplying " implies that with high probability for all iterations of the algorithm
wo oor TV (W', V') + YÀ
- Wy' T. (w', v') + TA,
(311)
where Σ. == YA (using the properties of Å in Lemma 85 is mean zero noise vector with almost surely bounded norm, i.e. || S Q' for some Q' poly(m1, m2, ma, C1, C22). (we dropped the x parameters by considering constant high probability argument).
Finally, note that injecting noise zero mean noise (z), = (TE,/ / (Vmi(/)) to the gradient V w (w',,, v'). Therefore, overall rumning SGD on I (which is equivalent to PSGD on L) observe an unbiased noise vector defined as = + ( Ez). Now it is easy to check that the moment matrix of E and En are 22 and o/2 for
E by PSGD results adding an extra
0, mfd
(312)
M2 m2 (m3 n)
02
(313)
m
which implies the moment matrix of f is upper bounded by
T= = (000/(mmmm + m)d) +
and lower bounded by
0,1 mi2
i.e.
HIELE < I
(Note that we look at the new coordinates (w', v') as a vectors, so the term E.L. makes sense.)
Moreover, || = 1//m, | S 1 almost surely, which implies the following almost surely bound for L:
| < Q = Q' + +1+1/
111

---

Published as a conference paper at ICLR 2022
Lemma 44 Let g(x) be second order differentiable function over BN such that point there exist a random direction and deterministic direction and fixed positive real r with:
Ey = O, E Bg + oF v1y) S g(z) mpr.
Then, for the gradient and Hessian at point x, we have either
VV((a]1 2 r
4||=||
or
Amin (Vgg(a)) S 2 2
Proof of Lemma
We write the second order tailor approximation of g around æ:
g( w) g(x) Vg(z)" u+ 2 w" ((g()) +
Now substituting with nE= + Vry and taking expectation with respect y, as send + 0 and using the fact that Ey = 0:
Ex + +z /ng) g(x)
By Vg(x)) (nz + V1t) +
2 (nz + V v1y) + o(llnz + /nyll
R.g(4)++VVg<))++ "" 2 - (()==)))=>>>)))))))))))))) (x)
(x))))))++++ " +(vluul))
1
- T g o(n).
Combining the assumption with the above Equation, we get that for small enough we have
(Vg(z) 2 1 x " V 11/
S
i.c.
Vg(x) + 2 Ey V2g v²g(z)y S -r/2.
which means we should either have
Vg(x) T2 S -r/4,
which implies
Vo(z)) 2 T
A||=||
Eyy"" g5r() S -r/2,
which implies
Amin (Vo((x))
maxxessppon(z) 2
112

---

Published as a conference paper at ICLR 2022
B.4 HANDLING THE INJECTED NOISE BY PSGD
In this section, we prove that having SGD injecting noise into our gradient estimates mostly does not change the sign pattern of the first layer, namely among the of rows in P defined in Lemma II
Lemma 45 Having enough overparameterization, with high probability, every iteration of the PSGD for Will) defined in the proof of Lemma I we have for every [ma]:
[W"] c2/(4m/))
Proof of Lemma 35
Let Ø' be the subspace of the first layer weight matrices which is zero in rows j P (P defined in Lemma W. while in other rows it is the span of 2 i.c. using our notation Z introduced in the proof of Lemma MI we can write 4' is span )i
Recall from Lemma that we decompose the first layer weight W as W + Wr(2), namely the parts in the subspace E' and subspace Φ/t respectively. Moreover, let E, 1= { + (2) be the decomposition of the injected noise at some iteration of PSGD into subspaces '' and d respectively.
Now recall that the current W' is the value of the previous iteration moved by the gradient plus the injected noise:
W' = W ( + + =))
W - / V + 2 W (0-00 + 2th1 W" (2)
+ + + +
where W is the weight of the previous iteration and WI w*- are again its decomposition to op and $/1, where V "ww,pu w defined in Lemma [ Applying Lemma 24 for the previous iteration of the algorithm, we get V w' E Ø' since the bad events E defined in Lemma 6 occurs only with probability exponentially small (hence union bound across all the iterations rules it out). Hence, the decomposition for the current iteration becomes
( W/ m V. + 2 W W"- -00+00)+))))))))) +
(314)
(2 (1 22m12)1)))) 2mm))w''(0 + (2)
(315)
We handle the (1(() part in Lemma M and prove that long || 112 < |[W]|| remains bounded by CP. then the sign pattern the first layer, when only considering the wr()) part, is specified by the initialization except within set P: here handle the w=(() part as well.
is with mean 1/m1. Therefore, with probability bounded by 0(1/m).. It is not hard to the same argument holds for the projection of E onto - i.c. E(²), Applying union bound for all iterations, again using the fact that we run PSGD for poly iterations while the chance of error is exponentially small in mi, noise of gradients, at every iteration and for every j E [mi]:
Note that for every row j E [m]]. the variable ((E//\/mm()))))
that is exponentially small in m1, (E
then argue that with high probability over the
|= = Ō(1/mi).
(316)
But applying trinagle inequality Equation (5155 and writing in telescope form, particularly for the jth row, and further using the assumption BTG we get that || grows at most to ((1((m))) 21 )); as we set 1/2h = O(poly(n)), assuming polynomially large enough m, concludes the claim.
113

---

Published as a conference paper at ICLR 2022
B.4.1 BOUNDING THE NORM THE FIRST LAYER'S OUTPUT IN THE WORST CASE
Lemma 46 Suppose W' satisfies the assumption of Lemma W i.e. [[ C₁, and [[ S
(2/(2)/ except possible for indices in P, also defined in Then, with high probability over inilialization
c n n'ms, 1/4 Vky
sup [1)(()) 2 (1 (1+ Omm3d log(m)) (og mm))m + Vms a,||=||=1
m1
which is O(Ci) for large enough overparameterization..
Proof of Lemma 36
Note the because the VC-dimension of the class of binary functions with respect to halfs- paces in IRd is d + 1, the number of different sign patterns Dw for different can be at most d+1 Now similar to Equation (3T7), for l E [ms] define mi
( (x(x) = 1/ m1 W 1 x
(317)
j=1
Then, for 1i F 12, as |,0|| = 1:
(x), Zxe (x)) =
1
W ky W kg.j 1(
(0)T x}
mi
1
sup
D Dwo mis W ki W k2.s'
m1
But for each fixed D Ow pe using Hoeffding bound, we have with probability 1 - 5:
m73
log(1/6)
a W
m1
Applying the above for all possible sign patterns with & < ((1/m/ and a union bound, we have
with high probability
sup s. | |=1
(1), 7s,
(x))
sup
D Dwn .ii Wh Wh S dllo((m)) /mi-
m
We can even state the following stronger bound with respect to two adversarially picked vectors x, r':
1
mi
sup [||||1]|[=|11==
(Z (I). Zkg Zkg (x')) S sup
D Dwoo mis a Wh W S dllo((11) /m,.
mi
1=1
(318)
because each aw i. has at most m d+1 cases as we discussed above, then Dwon anj Dwo,, ju has at most m4+1 possible cases, and applying similar Hoeffding bound for each of them and union bound as we did will imply (BI)). We will use this generalized version in another section.
Now combining Equation (HIS) with the fact that ||W'|| C₁ and applying Lemma Af
my
sup
W" Zx(x))² < (1 (omm
(319)
s.
On the other hand, setting ma high probability
m1, M3 d. and R 02/ c2/ K2) in Lemma 2g
get with
#(je [m] 1 c2/(2/m1)) < m2 vm1cs/(2k1)
114

---

Published as a conference paper at ICLR 2022
Noting that ||W||| v (2/(2/m,) for j & P. conclude that with high probability, for any 2, ((((()) + W 2 0} and 1 2 0} can be different in at most /mie2/ (2x1) of the j's outside of [m]]] \ P. Therefore, as have also [P] S ne2y/m /Ki from Lemma II we conclude that with high probability, for any I, there are at most ((ne2 m/ sign changes by adding W to W This further implies:
(z)(2) - (W', (x(x)) S 2/
Σ
WWaz
S T (
| (il Sgn( + Sgn( + W)fx)}//
Ci SCV /t/////////////////////
0/22 n n²m3 1/4
Combining this with (L9), we conclude with high probability:
C n ms 1/4 VKy
=.||=||=1 [0'( < (1+0 logmm)) (og(mm))mmm)))))))) + vmg
sup
mi A
which completes the proof.
115


Reviews:
[{"review_id": "ytpVZP7d6Ta", "reviewer": "Reviewer_NvLr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 motivation of the paper is very clear and convincing. The analysis of neural networks using the NTK is known to have its limits, and the effort to provide generalization and optimization results beyond this regime is one of the main challenges of the theoretical machine learning community when studying deep learning. Furthermore, the techniques used in the paper can be of independent interest, and can benefit others trying to study optimization of neural networks. However, I have a few concerns regarding the results introduced in the paper.\n\nThe paper suggests three possible improvements on NTK analysis:\n1. Faster rates, with 1/n dependence on the number of examples instead of 1/sqrt(n) as in e.g. Arora et al. 2019.\n2. Relaxation of the realizability assumption that is sometimes made in NTK results, allowing for generalization bounds in the presence of noise.\n3. A better complexity measure of the data/target, that allows the rate to be adaptive to some data-dependent complexity.\n\nIt seems to me that the first two improvements can be achieved by a more careful analysis of the NTK case (specifically, the authors acknowledge that using a smoothed loss the same fast-rate can be achieved in Arora et al 2019a). So, the main reason to go through the effort of analyzing the network beyond the NTK regime (and also analyzing a somewhat non-standard version of SGD), is to get the third point. Namely, the main contribution of the paper is in presenting a complexity measure that gives generalization bounds that are better than those that can be obtained by the complexity measure of the NTK (the RKHS norm of the NTK).\n\nHowever, it is not clear to me why the new complexity measure offered in the paper improves over the NTK. Indeed, the authors show that it is upper bounded by the NTK-based complexity, but showing that this measure is \"better\" requires some case where the error of NTK can be lower-bounded, to show a gap between the two methods. In other words, can you show some example of data/function/distribution where your method yields an upper bound on the loss that is significantly smaller than the best possible bound obtained by the NTK? or even better, by any kernel method? If so, this should be emphasised in the paper.\n\nRelated to this point, I believe that the discussion on adaptivity of the kernel is a little misleading. The authors claim that the difference between their analysis and the NTK analysis is that in the later the kernel is fixed while in the former the kernel can be chosen depending on the data. However, the kernel cannot be chosen freely, but from some restricted family of kernels. But it is not clear exactly how this family of kernels is restricted, and whether this does not end up being equivalent to learning with some fixed kernel that is different from the NTK. So, please clarify whether this adaptivity truly goes beyond the regime of learning with kernels, or just improves by using a \"better\" (but fixed) kernel.\n\nAnother point that could be improved is the technical introduction of the complexity measure. I found it hard to follow all the different kernels that were introduced, and how these were derived from the architecture. I think that working with some concrete example of a function (possibly some function that is \"beyond the NTK regime\") and calculating its complexity, will make it easier to understand the exact notion of complexity.\n\nOverall, I believe the paper makes worthy contributions, and I am willing to raise my score if my concerns are answered.\n\n===========================================================\n\nAfter discussion with the authors, I still believe the results could be much stronger if the authors would show a clear gap between NTK and their analysis. However, the paper does offer new bounds and novel analysis techniques which are important contributions, and therefore I am raising my score.", "summary_of_the_paper": "The paper introduces novel results on the optimization and generalization of three-layer networks, optimized with a variant of gradient-descent. The goal of the analysis introduced in the paper is to obtain bounds that improve over the bounds obtained using the well-studied NTK framework. Namely, the aim is to go beyond the \"lazy training\" regime to allow for better bounds on learning more complex functions/distributions.", "summary_of_the_review": "The paper provides novel results analyzing optimization and generalization of three-layer neural networks. However, my main concern is that the paper does not provide theoretical evidence that the bounds are indeed strictly and significantly stronger than what can be obtained by learning with the NTK, or more generally using kernels. I am willing to raise my score if my concerns are answered.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "VI31vXxNjT", "reviewer": "Reviewer_nxBT", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 1, "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 paper present quite an interesting analysis and packs a lot of material in 9 page of main text and 101 pages of Appendix material. While it is generally well written, it is not very accessible for a casual ICLR reader with no background in theoretical computer science. Since I'm not an expert in this, I'll defer to the other reviewers to check the significance and correctness of this paper. Below I provide only some superficial comments that hopefully help authors improve the paper a little.\n\n$K^{\\infty}$, $\\tilde K^{\\infty}$ is never properly defined and can be implied only from the context. Generally, the paper defines _quite a lot_ of notation during its length, I think it would benefit a lot from proper definition of the terms being used, at least in the Appendix\n\nFeatures $g_k$ in section 2 appear without definition and it is not clear its relation with $G$. When it is used in eq.9 it is not clear what is the number of intermediate features and how it is defined.\nnit: some of the acronyms might not be familiar to a typical ICLR reader\n- a.s. \n- ' symbols are used as vars (e.g. \\phi'), but are confusing as they have same notation as a partial derivatives. This can be easily avoid by ~ or \\hat symbols.\n- population risk", "summary_of_the_paper": "The paper presents a theoretical analysis of a 3 layer neural network with ReLU activations. The main result is introduction of adaptive generalization bounds that are defined for a modified SGD algorithm. These bounds are robust to noise and data dependent. \n\nThe idea is to define a product kernel for the second layer of the form $K^{\\infty}\\odot G$, where $$K^{\\infty}$ is fixed and $G$ is adaptive and can be modified so that $g_k$ has minimum possible norms. This leads to a definition of a complexity measure that together with a simple modification to the SGD algorithm defines a bound on the population risk.", "summary_of_the_review": "Theoretical paper defining a a novel bound for a 3-layer network. Since I'm not an expert in this field, I can provide only superficial comments to the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "VF77oK2aoY4", "reviewer": "Reviewer_MU3r", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Main review:\n1. Strength:\n    1. The results obtained here, especially on the proposed function norm (minimum RKHS norm) is interesting. It would be better if the authors can provide further comments on the key difference between the data-dependent complexity measure bound and the function-norm based bound. \n    2. The paper is well written. I appreciate the author’s efforts in making the presentation clear, consider the paper itself is fairly technical in nature. \n    3. The discussion with related work is sufficient and difference with prior work are pointed out clearly, as section 3.3 and 3.4 the authors discuss in details how the results differs with kernel learning and NTK regime results.\n2. Weakness: \n    1. The training objective in (1) is clearly not the standard loss in practice, considering the additional $W^{(0)}, V^{(0)}, W^s$ that  are not optimized during training, the authors should comment more on why this additional terms are introduced and what’s their implication for analysis.\n    2. The proposed algorithm has an additional projection step that makes $V_j’ \\perp \\phi^{(0)}(x_i)$, it is unclear to me why this projection step is necessary (is it essential in establishing convergence beyond NTK regime?). This technical requirement is not sufficiently motivated in the current version. \n\n", "summary_of_the_paper": "This paper makes contributions into two main category:\n\n1. Algorithmically, it propose a projected SGD algorithm that can, in polynomial number of iteration, reaches a solution that generalizes.\n2. In terms of generalization, it proposes a new generalization bound with data-dependent complexity measure that goes beyond NTK regime. Another generalization bound, based on a new function norm (minimum RKHS norm w.r.t. a family of kernels) is proposed. The proposed bound shows *adaptivity* nature of the generalization results. \n\n", "summary_of_the_review": "Summary of Review:\n1. The paper makes a fairly interesting technical contribution: the proposed generalization bound poses adaptive nature, it improves the current kernel based bound (NTK) by selecting the best kernel that tradeoff data fitting and complexity.\n2. The presentation is mostly clear, and the author clearly make efforts to compliment technical results with rich discussions. However, some technical conditions imposed in the loss and algorithm are not sufficiently motivated or explained. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UkfvQNW0uhl", "reviewer": "Reviewer_aHSb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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 theory of NTK provides a beautiful theoretical tools to analyze the convergence of generalization of neural network models in highly over-parameterized regime. Yet, essentially a linear analysis, NTK cannot characterize feature learning of neural networks, and practice neural networks work out of the NTK regime. Hence, theoretical study of neural network dynamics beyond the NTK regime is crucial for the understanding of the success of neural networks. This work tries to explore the beyond-NTK regime in a special case. Though both the model and the algorithm are specifically designed for theoretical analysis, the work done in this paper is still meaningful, because it provides an approach to analyze the feature learning effect of neural networks. \n\nThe major comment from the reviewer is about the comparison of the setting with NTK. The reviewer hope the authors can make it clearer why the studied setting is different from NTK. Is it because the neural network is less wide than required by NTK, or because the network structure makes go beyond NTK, or because the project SGD algorithm prevent the network from entering the NTK regime? ", "summary_of_the_paper": "This paper studies the behavior of a three-layer neural network trained by a projected SGD algorithm. The authors theoretically show that, in this setting the neural network has more complicated behavior than in the NTK regime. Instead of sticking at one kernel, now the neural network explores different kernels decided by the features learned by the first layer. Therefore, the generalization error is bounded by a minimum of many RKHS norms, and is proven to be smaller than the single NTK norm. The proposed generalization error bound outperforms the NTK bound. For target functions in the NTK, the proposed bound is no bigger than the NTK bound. The model and the algorithm are close to commonly used ones, while there are components specially designed for the theoretical analysis. ", "summary_of_the_review": "The paper studies the optimization and generalization of a three-layer neural network trained by a projected SGD algorithm. In this setting, the network runs beyond the NTK regime. Hence, it can achieve feature learning, and better generalization performance than NTK. Specifically, the generalization error is bounded by a complexity depending on the minimum of a family of RKHS norms. This paper explores the behavior of neural networks out of the NTK regime, which is important due to 1) the existence of feature learning, and 2) closer settings to practice.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper goes beyond the NTK setting in analyzing optimization and generalization in ReLU networks. It nicely generalizes NTK by showing that generalization depends on a family of kernels rather than the single NTK. The reviewers appreciated the results. One thing that is missing is a clear separation between NTK results and the ones proposed here. Although it is ok to defer this to future work, a discussion of this point in the paper would be helpful.
Decision: Accept (Poster)