Restricted Strong Convexity of Deep Learning Models with Smooth Activations
Authors: Arindam Banerjee
Pedro Cisneros-Velarde
Libin Zhu
Misha Belkin
Venue: ICLR 2023 poster (2023)

Abstract: We consider the problem of optimization of deep learning models with smooth activation functions. While there exist influential results on the problem from the ``near initialization'' perspective, we shed considerable new light on the problem. In particular, we make two key technical contributions for such models with $L$ layers, $m$ width, and $\sigma_0^2$ initialization variance. First, for suitable $\sigma_0^2$, we establish a $O(\frac{\text{poly}(L)}{\sqrt{m}})$ upper bound on the spectral norm of the Hessian of such models, considerably sharpening prior results. Second, we introduce a new analysis of optimization based on Restricted Strong Convexity (RSC) which holds as long as the squared norm of the average gradient of predictors is $\Omega(\frac{\text{poly}(L)}{\sqrt{m}})$ for the square loss. We also present results for more general losses. The RSC based analysis does not need the ``near initialization" perspective and guarantees geometric convergence for gradient descent (GD). To the best of our knowledge, ours is the first result on establishing geometric convergence of GD based on RSC for deep learning models, thus becoming an alternative sufficient condition for convergence that does not depend on the widely-used Neural Tangent Kernel (NTK). We share preliminary experimental results supporting our theoretical advances.

Published as a conference paper at ICLR 2023
RESTRICTED STRONG CONVEXITY OF DEEP LEARNING MODELS WITH SMOOTH ACTIVATIONS
Arindam Banerjee
Pedro Cisneros- Velarde
Department of Computer Science
Department of Computer Science
University of Illinois at Urbana- Champaagnn ar arindamb@l illinos innisii..... .ddu
University of Illinois at Urbana-Champaign pacis pacisnelee gmail. 11.11.. coo
Libin Zhu
Mikhail Belkin
Department of Computer Science University of California, San Diego 155hh@ucscd
Haliciouglu Data Science Institute University of California, San Diego mbel 1 k inuucdd.ed:
ABSTRACT
We consider the problem of optimization of deep learning models with smooth activation functions. While there exist influential results on the problem from the "near initialization" perspective, we shed considerable new light on the problem. In particular, we make two key technical contributions for such models with L. layers, m width, and of initialization variance. First, for suitable of. we establish (
vm (P))y(L)) upper bound on the spectral norm of the Hessian of such models,
considerably sharpening prior results. Second, we introduce a new analysis optimization based on Restricted Strong Convexity (RSC) which holds long
the squared norm of the average gradient predictors is 9 poly(L) for the square loss. We also present results for more general losses. The RSC based analysis does not need the "near initialization" perspective and guarantees geometric convergence for gradient descent (GD). To the best of our knowledge, ours is the first result on establishing geometric convergence of GD based on RSC for deep learning models, thus becoming an alternative sufficient condition for convergence that does not depend on the widely-used Neural Tangent Kernel (NTK). We share preliminary experimental results supporting our theoretical advances.
ym
INTRODUCTION
Recent years have seen advances in understanding convergence of gradient descent (GD) and variants for deep learning models (Du et al., [2119] |0191//llen-1 Allen-Zhu et 2019 Zou & Gul [019 Zou et al. 2020 Liu et al. 2022 Ji & Telgarsky| 2019 Oymak & Soltanolkotabi [020|Nguyeen 2021). Despite the fact that such optimization problems are non-convex, a series of recent results have shown that GD has geometric convergence and finds near global solution "near initialization" for wide networks. Such analysis is typically done based on the Neural Tangent Kernel (NTK) (Jacot et al. 2018). in particular by showing that the NTK is positive definite "near initialization," in turn implying the optimization problem satisfies a condition closely related to the which in turn implies geometric convergence the global minima (Liu et al. 2022 Nguyen 202T).
(PL) condition,
Such results have been generalized to more flexible forms of "lazy learning" where similar guarantees hold (Chizat et al. (019).. However, there are concerns regarding whether such "near initialization" or "lazy learning" truly explains the optimization behavior in realistic deep learning models (Geiger cct al. 2020 Yang & Hu 2020 Fort et al. 2020 Chizat et al. 2019).
Our work focuses optimization of deep models with smooth activation functions, which have become increasingly popular in recent years (Du et al. 2019 Liu et al. 2022 Huang & Yau 2020). Much of the theoretical convergence analysis of GD has focused on ReLU networks (Allen-Zhu et al.) 2019; Nguyen 202I). Some progress has also been made for deep models with smooth activations, but existing results are based variant of the NTK analysis, and the requirements the width of

---

Published as a conference paper at ICLR 2023
such models are high (Du et al. 2019: Liu et al. 2022). Based on such background and context, the motivating question behind our work is: Are there other (meaningful) sufficient conditions beyond NTK which lead to (geometric) convergence of GD for deep learning optimization?
Based on such motivation, we make two technical contributions in this paper which shed light on optimization of deep learning models with smooth activations and with I. layers, m width, and of initialization variance. First, for suitable oZ. we establish a O ( upper bound on the spectral norm of the Hessian of such models (Section 4. The bound holds over large layerwise spectral norm (instead of Frobenius norm) ball B (6a) around the random initialization Bu. where the p.m radius p < /m, arguably much bigger than what real world deep models need. Our analysis builds on and sharpens recent prior work on the topic (Liu et al., 2020). While our analysis holds for Gaussian random initialization of weights with any variance o.. the poly(L) dependence happens when of S 4+c(1) m
1 I (we handle the scaling explicitly).
Second, based on our Hessian spectral norm bound, we introduce optimization of deep models with smooth activations based on the concept of Restricted Strong Con- vexity (RSC) (Section 55 (Wainwright, 2019 Negahban et al.] 2012 Negahban & Wainwright 2012
approach to the analysis of
Banerjee et al. 2014 Chen & Banerjee 2013). While RSC has been core theme in high-dimensional statisties especially for linear models and convex losses ( (Wainwright 2019). to the best of our knowl- edge, RSC has not been considered in the context of non-convex optimization of overparameteriiee deep models. For a normalized total loss function [()) = Σi Élyi, ūz): f/ = [(0; xx) with predictor or neural network model parameterized by vector 0 and data points (x:, y1 ) = when & corresponds to the square loss we show that the total loss function satisfies RSC on a suitable restricted
set 0% C RP (Definition 5.2 in Section 5) at step l as long as || Σ VeJ x.) )12 Ω ).)) We also present similar results for general losses for which additional assumptions needed. We show that the RSC property implies Restricted Polyak-Lojasiewe implying a geometric one-step decrease of the loss towards the minimum in Q and subsequently implying geometric decrease of the loss towards the minimum in the large (layerwise spectral norm) ball S (0u). The geometric convergence due to RSC is a novel approach the context of deep P.P1 learning optimization which does not depend on properties of the NTK. Thus, the RSC condition provides an alternative sufficient condition for geometric convergence for deep learning optimization to the widely-used NTK condition.
(RPL) condition on Q in turn
The rest of the paper is organized as follows. We briefly present related work in Section 2 and discuss the problem setup in Section 3 We establish the Hessian spectral norm bound in Section 4 and introduce the RSC based optimization analysis in Section We experimental results corresponding to the RSC condition in Section 6 and conclude in Section 7 All technical proofs are in the Appendix.
2 RELATED WORK
The literature gradient descent and variants for deep learning is increasingly large, and we refer the readers to the following surveys for an overview of the field (Fan et al. [202]] Bartlett et al. 2021). Among the theoretical works, we consider (Du et al., 2019 Allen-Zhu et al.) 2019 Zou & Gu 2019 Zou et al. 2020 Liu et al. 2022) as the closest to our work in terms of their study of convergence on multi-layer neural networks. For literature review on shallow and/or linear networks, we refer to the recent survey (Fang et al. 20221). Due to the rapidly growing related work, we only refer to the
most related recent work for most parts.
Du et al. 2019); Zou & Gu (2119); Allen-Zhu et al. (2019); Liu et al, (2022) considered optimization of square loss, which we also consider for our main results, and we also present extensions to more general class of loss functions, Zou & Gu 20 Zou et al. (202);; Allen et al. (2019); (2019):N
Mondelli (2020); |guuyen (2021): Nguyen et al. (2021) y) analyzed deep ReL.U networks. Instead, we consider smooth activation functions, similar to (Du et al. 2019 Liu et al. 2022). The convergence analysis of the gradient descent in (Du et al. 2019 Allen- -Zhn--Zuuee et al. 2019 Zou & Gu 2019 Zou
et al. 2020 Liu et al.) 2022) relied on the near constancy of NTK for wide neural networks (Jacot et al. 2018 Lee et al. 2019 Arora et al., 2019 Liu et al. 2020), which yield certain desirable properties for their training using gradient descent based methods. One such property is related to the PL condition (Karimi et al. 2016 Nguyen 202T). formulated as PL condition in (Liu et al. (022).
Our work uses different optimization analysis based RSC (Wainwright] 2019
Negahban et al.
2

---

Published as a conference paper at ICLR 2023
2012 Negahban & Wainwright 2012) related to restricted version of the PL condition. Furthermore,
Du et al. (2019); Allen- Zhu et al. (2019); ; Zou & Gu (2019); Zou et al. (2020) showed convergence in value global minimizer of the total loss, as we also do.
3 PROBLEM SETUP: DEEP LEARNING WITH SMOOTH ACTIVATIONS
Consider training set D = {xi, 1 E X C R 9/ E E S IR We will denote by X E R the matrix whose ith row is x; For suitable loss function f, the goal is to minimize the empirical loss: L( = A > {y,, 04) + -. {(y,, [0; x,)), where the prediction 0; == f=; x,) is from deep model, and the parameter vector 0 E IR, In our setting is feed-forware multi-layer (fully-connected) neural network with depth L and widths mi, E [4] == {I...., L given by
a (x) = =x (x) =
1 1= I.,...,,
/mm-1
f(0:x) = (x)+ = VLL
(x))
where W E R [L] are layer-wise weight matrices, v E R the last layer vector, Φ(-) the smooth (pointwise) activation function, and the total set of parameters
0 (vec(W())). ,..., veo (e)( TT E TR mmm 1tmp
with mg = d. For simplicity, we will assume that the width of all the layers is the same, i.e., my = mt,
1 E [Z]. and so that 0 E IR. Lmm++mm For simplicity, we also consider deep models with only one output,
ie.. f((:x)
as in (Du al. 2019), but our results can be extended multi-dimension outputs as in Zou & Gu 2019). using V E VER T x for k outputs at the last layer; see Appendix C
Define the pointwise loss E, : E(yi, R + R, and denote its first- and second-derivative as &. :=
de(y..ū.) and e.' d' d. The particular case of square loss is Ely,, Ut) (i/ 0:)² We dif
dÿ.
denote the gradient and Hessian of f(;;x,,= TRP - R V.J == af(0.x:) and V == 8 f(xx).)
20
The neural tangent kernel (NTK) Kntk( (-; E | corresponding to parameter 0 is defined as Kmn(X; (x,, Xj; 0) = ff, f) ). By chain rule, the gradient and Hessian of the empirical loss w.r.t. are given by 8C(6)
a0 n E V and 0²C())
E VVV.VV EV Let || lle
862
denote the spectral norm for matrices and L2-norm for vectors
We make the following assumption regarding the activation function Φ
Assumption (Activation function). The activation à 1-Lipschitz, ie., |
1, and B -moohh,
i.e, |01 S 3g-
Remark 3.1. Our analysis holds for any <a-Lipchitz smooth activations, with dependence on &o on most key results. The main (qualitative) conclusions stay true if ss < 1 o(1) or Sø = poly(L) L). which is typically satisfied for commonly used smooth activations and moderate values of L.
We define two types of balls over parameters that will be used throughout our analysis.
Definition 3.1 (Norm balls). Given 0 e IP of the form with parameters w() ,, ,1E [L], we define
BSpec (0) = { R as in [[ W 112 S ( P.Pi
sp) s (3)
Euc (8) == {0 E R as
| 0
S ppp
(4)
Remark 3.2. The layerwise spectral norm ball P.P, plays a key role in our analysis. The last layer radius of P1 gives more flexibility, and we will usually assume P1 S p; e.g., could choose the desirable operating regime of p < /m and # = O(1). Our analysis in fact goes through for any choice of p. Pi and the detailed results will indicate specific dependencies both p and p1. n
3

---

Published as a conference paper at ICLR 2023
4 SPECTRAL NORM OF THE HESSIAN OF THE MODEL
We start with the following assumption regarding the random initialization of the weights.
Assumption 2 (Initialization weights and data normalization). The initialization weights Wo.3j (N og) for 1 [T.] where do 2(1+
(1)
> 0, and Vo random unit vector with 01
Vlog in vam
||vol12 1. Further, we assume the input data satisfies: ||x|||2 = Vd, E [m].
We focus on bounding the spectral norm of the Hessian [ā; for 0 E BSpec (8o) and any input x E TRd with ||x|| = vd. The assumption ||*|| = v is for convenient scaling, such assumptions are common in the literature (Allen-Zhu et al. 2019) Oymak Soltanolkotabi 2020)] Nguyen et al. 2021). Prior work (Liu et al. 2020) has considered a similar analysis for 0 E Be (oo). effectively the layerwise Frobenius norm ball, which is much smaller than p-p= ( the layerwise spectral norm ball. We choose a unit value for the last layer's weight norm for convenience, since results hold under appropriate scaling for any other constant in O(1). All missing proofs are in Appendix A
Theorem 4.1 (Hessian Spectral Norm Bound). Under Assumptions 7 and for 0 BSper (0o). P.PI
2
with probability at least (1 2(L+1) ), for any xx, i [m]]. we have
m
(0:(0xx;) S
CH
(5)
vm
with си = O(L p1)) where 7
Vm
Remark 4.1 (Desirable operating regimes). The constant y needs careful scrutiny as cn depends on 702 Let us choose = Opolyy (L)). For any choice of the spectral norm radius < vm, we choose 01 S vmm ensuring 7 S 1 and hence eи O(poly(T.) If = 0(1,, we can keep
T1 = so that y = 1 + ymm
_m1, and си = ((poly(L)) as long as L < mm, which is common. Both of these give good choices for 01 and desirable operating regime for the result. If we choose d > 1, an undesirable operating regime, then Cи = (())())) > 1, and we will need m = (()())) for the result be of interest.
L
Remark 4.2 (Recent Related Work). In recent work. Liu et al. (2020) analyzed the Hessian spectral
norm bound and showed that Cи Ö(p3L)) for 0 E B Our analysis builds on and sharpens the result in (Liu al. 2020) three respects: (a) we have
Eue (p)) (logarithmic terms hidden in Ó(-))
cи (p) (1)((++))4))))) +254) for P1 (polyy()) where we can choose 0 to make y S 1 and thus obtain си (poly(L)) instead of the worse cи = Opp%)) Liu et al. (2020 1 (b) even for the same p. our results hold for a much larger spectral norm ball [Spee(0) compared to their Euclidean P.P1 norm ball (Fu((Bu) in (Liu et al. 2020); and (c) to avoid an exponential term, the bound in (Liu et al. 2020) needs S 1 whereas our result can use radius p < /m for all intermediate layer matrices and P1 = (ppoly(L), L)) for the last layer vector. Moreover, as a consequence of (b) and (c), our results hold for a larger (spectral norm) ball whose radius can increase with unlike the results in Liu et al. (000)) which hold for a smaller (Euclidean) ball with constant radius, i.e., "near initialization."
Remark 4.3 (Exact constant cH). For completeness, we show the exact expression of the constant cH Theorem so the dependencies on different factors clear. Let (((I) : -= (0()) E -11
Then,
CH = 22 + +1) (1+P1) VH max 1-1 p + +2L1" max hil), [E[L)
(6)
[E[L]]
where
(b((()))) h(l1)
Bo (B0 ()+
Boy M()
WH =
max 15h S..g..
(7)
The source of the terms will be discussed shortly. Note the dependence on Pl, the radius for the last layer in SSec (fo), and why P1 = (Tpoly(.)) is desirable operating regime.
P.P
See the end of Appendix A for quick note about the network architecture in our work and the one in Liu 2020
4

---

Published as a conference paper at ICLR 2023
Next, we give high level outline of the proof of Theorem 4.1
Proof sketch. Our analysis follows the structure developed in Liu al. (222)) but is considerably
sharper as discussed in Remark 4.2 We start by defining the following quantities: 20x
maxisis4
{1l Ball)
af (a
E R", @2(f) = maxisIgL @w
aa
w == voc(W())
(a
E Rmxm" and 22, (f) is the maximum over S 1 <22
< la S L among the three quan-
Swit
(a
and (a (ww
(a
tities
@w(hh3
2,2,1
(w((t)
1,2,11
(w
0a
2,2,1
where for an order-3 tensor T E Rd xd2 xda
we define the (2, 2, 1) -orm as | 222,11 ==
da
E Σj=
TizA212 x E R z E R The following result in (Liu
| x 1 ||
k=1
al.
2020 provides an upper bound the spectral norm of the Hessian.
Theorem 4.2 (Liu et al. (2020), Theorem 3.1). Under Assumptions assuming there is 6 such that
S 6, with C1 < 1.222 + L8 + L and C2 S L80, we have
17
2 / C222() Vm
vaf(0xx)]1
(8)
In order to prove Theorem 4.1 we prove that Theorem 4.2 holds with high-probabilityy where d =
22(f) = (LL(1+))) 22).1 ( and Q (f) O
(1+x")(+pp)) Thus we
vm
obtain that the upper bound (4.2) becomes O ((Pol(()) " (1 providing a benign polynomial
vm dependence on L when < 1, rather than an exponential dependence on the radius as in (Liu et al. 2020).
The analysis for bounding the spectral norm of the Hessian can be used to establish additional bounds, which we believe are of independent interest, some which will be used later Section First, we bound the norms of gradient of the predictor and the loss w.r.t the weight vector 0 and the input data X.
Lemma 4.1 (Predictor gradient bounds). Under Assumptions and for BSpec (fo). with
probability at least (1 2(I++1) we have
7 vm (1 +p))
|Vo[(0;x)|12 se and
|0x <
with 0² (MLL 1))² + 21 p1) Σ [o(0) E
(1(0),2211)) 01 vm
h(1)
711
Remark 4.4. Our analysis in Lemma 4. provides a bound the Lipschitz constant of the predictor, quantity which has generated interest in recent work on robust training (Salman et al. 2019
Cohen
al. 2020 Bubeck & Sellke 2021).
Under the assumption of square losses, further bounds can be obtained.
Lemma 4.2 (Loss bounds). Consider the square loss. Under Assumptions 7 and 2 for -1 fm
each of the following inequalities hold with probability at least (1 2(++)) (((v)) S cu.o.
and L(0) < Cpir a for 0 E BSpec (Oo), where Ca.b 2 Er vi 2(1 + l)²1)(1)2 and g(a) =
_ + +0(0)) a² for any a, E.bER
Corollary 4.1 (Loss gradient bound). Consider the square loss. Under Assumptions and for 0
(Spec(0o),
P.Ph (0o), with probability at least (1- 2(L+1) we have VeC(0)]la < 22/C(0) < C
with e in Lemma 4.1 and Gpi in Lemma 4.2
5

---

Published as a conference paper at ICLR 2023
5 OPTIMIZATION GUARANTEES WITH RESTRICTED STRONG CONVEXITY
We focus on minimizing the empirical loss (()) over 0 E (00) the layerwise spectral norm ball in 3 Our analysis is based on Restricted Strong Convexity (RSC) (Negahban et al. 2012 Banerjee et al. 2014] Chen & Banerjee, 2015; Wainwright 2019), which relaxes the definition of strong convexity by only needing strong convexity in certain directions or over subset of the ambient space. We introduce the following specific definition of RSC with respect to a tuple (S,0), 0).
Definition 5.1 (Restricted Strong Convexity (RSC)). A function L. is said satisfy a-restricted strong convexity (a-RSC) with respect to the tuple (S, 0) for any O' E S C IR and some fixed 0 E I we have C(0"= 2 [(0) + +0'
(0' -, 0, V (0) + % 0 with a > 0.
Note that L being a- RSC w.r.t. (5,0) does not need L to be convex on Rr. Let us consider sequence of iterates (0,) IR. Our RSC analysis will rely on the following Qi--sets at step I, which avoid directions almost orthogonal to the average gradient of the predictor. We define the following notation: for two vectors π and x. COS(IT, #) denotes the cosine of the angle between π and म.
Definition 5.2 (Q) sets). For iterate 02 E RP, let gt = D (of(0;;x;). For any K E (0, define Qx == {0 IP | cos(( f2, gi)
2 17.
We define the set Bg = Qh n BSpec
(fo) n (0.). We focus on establishing RSC w.r.t. the tuple
(Be, 0z), where BSpec ball around the current iterate.
p.p. (0n) becomes the feasible set for the optimization and B (0,) is a Euclidean
Assumption (Loss function). The loss Eg E [n]]. is (i) strongly convex, ie., e 2 a > and (ii) smooth, i... e S 6.
Assumption Iss satisfied by commonly used loss functions such as square loss, where a 2. We state the RSC result for square loss; the result for other losses and proofs of all technical results in this section are in Appendix B
Theorem 5.1 (RSC for Square Loss). For square loss, under Assumptions 7 aad
2
with probability
least (1 2(L+1) v0 E Q% BSpec (0n) BBuc(O, with O, &Sppe (0o).
m
pips
C(0') 2 [().) 10' O2, voL(O.) + at 0
0, 12 with 04 ci ||:
1
(10)
2
mm
where g1 Σ = (of(0:));) a 2x² and C2 2CH (20p2 (Cp. with ch as in The- orem 4.1 2 as in Lemma 4.1 and Cpr.y as in Lemma 4.2 Consequently, L satisfies RSC Q SSer (fo) n BB (0.). 0t) whenever a > O.
w.E.t
Remark 5.1. The RSC condition or > 0 is satisfied at iteration I as long as || crym where
C C2 are exactly specified in Theorem 5.1 Indeed, if (and so d₁ and p) is chosen according to the desirable operating regimes (see Remark 4.1 1.. P1 = (poly(L)) and P2 = (poly(L)) then we can use the bounds from Lemma 4.2 and obtain that the RSC condition is satisfied when || > O(poly(L))
v/m The condition is arguably mild, does not need the NTK condition Amin Amin(Knnn (Kenk (=;0.) > and is expected to hold till convergence (see Remark 5.3) Morcover, it is local condition at step t and has dependence being "near initialization" in the sense of 0, BB for p 0(1) as in (Liu et al. 2020 2022).
For the convergence analysis, we also need to establish a smoothness property of the total loss.
Theorem 5.2 (Local Smoothness for Square Loss). For square loss, under Assumptions and with probability at least (1 - 2(L+1) ), V0, 0' E BSSpe((o)),
B 10'0
2CH CeHnCoprs
L(0') < C()) + - C))()
+ 2 012
with B = 20² +
(1I)
vm
with Cи in Theorem 4.1 o as in Lemma 4.1 and Cp.. as in Lemma 4.2 Consequently, L is locally
B-smooth. Moreover, oं i (and so oi and p) is chosen according to the desirable operating regimes (see Remark 4. and P1 = (pooy((.)) then ( = Oppoyy (T.))

---

Published as a conference paper at ICLR 2023
Remark 5.2. Similar to the of the standard strong convexity and smoothness, the RSC and smoothness parameters respectively in Theorems 5.1 and 5.2 satisfy at < 3. To see this note that
a, < 2 g 1B < 2g² < 3, where the second inequality follows since k S 1, and | 12 o² using
Lemma 4.1
Next, we show that the RSC condition w.rt. the tuple (B,, 02) implies restricted Polyak- -ojisaawe (RPL) condition w.r.t. the tuple (Bt, Bt), unlike standard PL which holds without restrictions (Krimi
al. 2016
Lemma 5.1 (RSC = RPL). Let B, == Q% n Bpee (6o) n (B). the setting of Theorem 5.1 if oz > O, then the upple (Be. 0&) satisfies the Restricted
(RPL) condition, i.e.,
[(0.) inf ((0) 1 20t [VoL(0))1
(12)
with probability at least (1 2(4+1) m
For the rest of the convergence analysis, we make the following assumption where I' can be viewed as the stopping time the convergence analysis holds given the assumptions are satisfied.
Assumption 4 (Iterates' conditions). For iterates {f.l=o......: (A4.1) > 0: (A4.2) 0: BSpec (6o).
Remark 5.3 (Assumption (A4.1)). From Remark 5.1 (A4.1) is satisfied as long as l
/
where cı, C2 in Theorem 5.T which is arguably mild condition. In Section 6 we will present some empirical findings that show that this condition on ||g behaves well empirically.
We now consider the particular case of gradient descent (GD) for the iterates: 01+1 02 To VL):;)
where π is chosen so that 0,+1 E P.P1
BSpee (0g) and P2 is chosen so that 8.+1 E B BFuc(()) which
p2
sufficient for the analysis of Theorem 5.1 Remark 5.4).
specify suitable choices in the sequel (see
Given RPL w.r.t. (B,, 0t), gradient descent leads to strict decrease of loss in Be.
Lemma 5.2 (Local Loss Reduction Bi). Let au, B be as in Theorems 5 and 5.2 respectively, and B, Q% Spee (0o) BEue((s Consider Assumptions) / and and gradient descent
with step size = B we E 20, Then,for for any 0zt1 E arginf BEB, L(0), we have with probability at least (1 2(L+1)) m
we
Ogwe ((0(41) -(0 S
(2 (2-wi) we) 3 (1-
(C((.) (2)
L(0++1))
(13)
Building on Lemma 5.2 we show that GD in fact leads to geometric decrease in the loss relative to the minimum value L(-) in the set BSpec(()))
P.P1
Theorem 5.3 (Global Loss Reduction in BSpec Let aq, B be as in Theorems P.p.
5.1 and 5.2
respectively, and B, Q% 0 (Spec((u))
(Bu) n B (Bi). Let 0" E arginf Spec (0n) (()), o
arginf BB [()), and 7/t and B, = Q% n BSpec (0o) n BEue (0t). Consider Assumptions 7 2 and and gradient descent
C(0.)2((0- Let az be as in Theorems 5.1 and 5.2 respectively,
with step size 1hs _, we E (0, 2). Then, with probability at least (1 2
m ), we have we have
Tt. E [0, 1) and
-(0") < (1 Crehit (1- (L(0.) (1-7))(2ww) (w)) wi)
-((0)))((00))
(14)
As long as the conditions in Theorem 5.3 are kept across iterations, there will be a geometric decrease in loss. For Assumption 4 have discussed (A4.1) in Remark 5.1 and discuss (A4.2) next.
7

---

Published as a conference paper at ICLR 2023
Remark 5.4 (Assumption (A4.2)). Consider run gradient descent iterations until some stopping time > 0. Given radius < ym. Assumption (A4.2) 0g E (p t = O..... T, can be verified empirically. Alternatively, can choose suitable step sizes 77 to ensure the property using the geometric convergence from Theorem 5.3 Assume that our goal is to get [(Or) L())) < Then, with XT mi] 0:22
(2 we), Assumption (A4.1) along with Remark 5.2
1 1 (log !)) Then, ensures XT < 1. Then, it suffices to have = Nog( -(0))=((0)) log 1-xx
to ensure 0, E 1BSpec (fo), /. E [7], in the case of the square loss, since [V S e for some constant e (see Corollary 4. it suffices to have v/ S 6(log !) Moreover, we point out that having
min(p-0L).
P2 2 C ensures ||0c+1 8 ll S P2 + Bu+1 E p2 (0.). which in this case can be guaranteed if P2 2 min(p.p1h,
(log The argument above is informal, but illustrates that Assumption (A4.1) along with suitable constant step sizes 7)e would ensure (A4.2). Thus, Assumption (A4.1), which ensures the RSC condition, is the main assumption behind the analysis.
The conditions in Assumption 4
(see Remarks 5.1 and 5.4p along with Theorem 5.3 imply that the RSC based convergence analysis holds for much larger layerwise spectral radius norm ball 1SSec((0) P.P1 (0o) with any radius p < vm and p1 = (ppoly (L)).
Remark 5.5 (RSC and NTK), In the context of square loss, the NTK condition for geometric convergence needs Amin mu (:; 0.)) co for every i.e., uniformly bounded away from 0 by a constant cu > 0. The NTK condition can also be written as
inf a: et||oo| 1
Σ V.Vo
200 0.
(15)
In contrast, the proposed RSC condition (Theorem 5.1) needs
n V (0.x)
8o
(16)
T1
vm
where m the width and ãg 02 where c1, C2 are constants defined in Theorem 5.1 As a quadratic
Gj form on the NTK, the RSC condition can be viewed as using a specific in (15 i.c. 8q- Vn for
i E [m). since the RSC condition is Σ I Vof(0;x;)
For m ?(n2), the RSC
V
condition is more general since NTK + RSC, but the converse is not necessarily true.
O
Remark 5.6 (RSC covers different settings than NTK). The NTK condition may be violated in
certain settings, e.g., (0f = 1, ,,. N. are linearly dependent, x; ~ X; for some i A j. layer widths are small my < ni, etc., but the optimization may work in practice. The RSC condition provides way to analyze convergence in such settings. The RSC condition gets violated when DE (ff; x O, which does not seem to happen in practice (see Section 6). and future work will focus understanding the phenomena. Finally, note that it is possible to construct a set of gradient vectors which satisfy the NTK condition but violates the RSC condition. Our perspective is to view the NTK and the RSC as two different sufficient conditions and geometric convergence of gradient descent (GD) is guaranteed as long as one of them is satisfied in any step.
6 RSC CONDITION: EXPERIMENTAL RESULTS
In this section, we present experimental results verifying the RSC condition 1....,T, T, on standard benchmarks: CIFAR- 10, MNIST, and Fashion-MNIST. For simplicity, as before, we use g: = + (0,)
1 D (0;xx))) = Ω poly(L)
In Figure [ aa), we consider CIFAR-10 and show the trajectory of [Bll2 over iterations t, for different values of the network width m. For any width, the value of |g [|2 stabilizes to a constant value over iterations, empirically validating the RSC condition || ((poly(L)/ /m). Interestingly, the smallest value of | seems to increase with the width. To study the width dependence further, in Figure 1b), we plot min:e[T] |grll2 as a function of width for several values of the width.
8

---

Published as a conference paper at ICLR 2023
The plot shows that g l|ge l2 increases steadily with m illustrating that the RSC condition is empirically satisfied more comfortably for wider networks. In Figure [c) and (d), we show similar plots for MNIST and Fashion-MNIST illustrating the same phenomena of m with m.
|g increasing
For the experiments, the network architecture used had 3-layer fully connected neural network with tanh activation function. The training algorithm is gradient descent (GD) width constant learning rate, chosen appropriately to keep the training in NTK regime. Since are using GD, we 512 randomly chosen training points for the experiments. The stopping criteria is either training loss 10-3 or number of iterations larger than 3000.
0.30
until convergence
width 1024
0.29
width 2048
0.24
0.25
Minimum
0.20
0.26
0.18
250
300
750
1000
1250
2001
1000
1500
2000
Iteration
Network width
(a) 10:: | over iterations.
(b) CIFAR-10 10: Minimum ||Bell width.
Minimum [8g] until convergence
0.50
Minimum lis until convergence
0.35
0.40
0.30
0.35
0.26
0.25
0220
0.15
500
1000
1500
3000
500
1000
1500
2000
Network width
Network width
(c) MNIST: Minimum ||g:|2 2 vs. width.
(d) Fashion-MNIST: Minimum
|gg ll vs. width.
Figure 1: Experiments CIFAR-10: (a) ||g: ll over iterations for different network widths (b) minimum lg l2 over iterations, i.e., min ||gr|12- as a function of network width m. Experiments (c) MNIST and (d) Fashion-MNIST. The experiments validates the RSC condition empirically, and illustrates that the condition is more comfortably satisfied for wider networks. Each curve is the average of 3 independent runs.
CONCLUSIONS
In this paper, we revisit deep learning optimization for feedforward models with smooth activations, and make two technical contributions. First, we bound the spectral norm the Hessian over large layerwise spectral norm radius ball, highlighting the role of initialization in such analysis. Second, we introduce new approach to showing geometric convergence in deep learning optimization using restricted strong convexity (RSC). Our amalysis sheds considerably new light deep learning optimization problems, underscores the importance of initialization variance, and introduces a RSC based alternative to the prevailing NTK based analysis, which may fuel future work.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
AB grateful for support from the National Science Foundation (NSF) through awards IIS 21-31335, OAC 21-30835, DBI 20-21898, as well as C3.ai research award. MB and LZ are grateful for support from the National Science Foundation (NSF) and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning2 through awards NSF IIS-181 and the TILOS institute (NSF CCF-21 126-2..
1883 and 814639 as well as
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
A. Banerjee, Chen, F. Fazayeli, and V. Sivakumar. Estimation with norm regularization. In Advances in Neural Information Processing Systems (NIPS), 2014.
Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta Numerica, 30:87-201, 2021.
Sebastien Bubeck and Mark Sellke. universal law of robustness via isoperimetry. In Neural Information Processing Systems (NeurIPS), 2021.
S. Chen and A. Banerjee. Structured estimation with atomic norms: General bounds and applications.
In Advances in Neural Information Processing Systems (NIPS), 2015.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (ICML), 2020.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1675-1685. PMLR, 09-15 Jun 2019.
Jianqing Fan, Cong Ma, and Yiqiao Zhong. A selective overview of deep learning. Statistical Science, 36(2):264 - 290, 2021.
Cong Fang, Hanze Dong, and Tong Zhang. Mathematical models of overparameterized neural networks. Proceedings of the IEEE, 109(5):683-703, 2021.
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy. and Surya Ganguli. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. Advances in Neural Information Processing Systems, 33:5850-5861, 2020.
Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy training deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2020 (LI):113301) 2020.
Jiaoyang Huang and Homg-Tzer Yau. Dynamics of deep neural networks and neural tangent hierarchy. In International conference on machine learning, pp. 4542-4551, PMLR, 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kemne:: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
10

---

Published as a conference paper at ICLR 2023
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. International Conference on Learning Representations, 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-Lojasiewin condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811 811. Springer, 2016.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in over- pee-pparamtterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-116, 2022.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems, 2020.
Sahand Negahban and Martin Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. The Journal of Machine Learning Research, 13(I): 1665-1697, 2012.
Sahand Negahban, Pradeep Ravikumar, Martin Wainwright, and Bin Yu. A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. Statistical Science, 27 (4), 2012.
Q. Nguyen and M. Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In Neural Information Processing Systems (NeurIPS), 2020.
Quynh Nguyen. On the proof global convergence gradient descent for deep relu networks with linear widths. In International Conference on Machine Learning (ICML), 2021.
Quynh Nguyen, Marco Mondelli, and Guido Montufar. Tight bounds the smallest eigenvalue of the neural tangent kernel for deep relu networks. In International Conference on Machine Learning (ICML), 2021.
S. Oymak and M. Soltanolkotabi. Towards moderate overparameterivatton:: global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
Hadi Salman, Greg Yang. Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sébastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. In Neural Information Processing Systems (NeurIPS), 2019.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing: Theory and Applications, pp- 210-268. Cambridge University Press, 2012.
Martin Wainwright. High-Dimensionul Statistics: Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi:
10.101779781 108622771..
Greg Yang and Edward J Hu. Feature learning in infinite-width neural networks. arXiv preprint arXiv:2011 144522 2020.
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 109:467-492, 2020.
11

---

Published as a conference paper at ICLR 2023
A SPECTRAL NORM OF THE HESSIAN
We establish the main theorem from Section in this Appendix.
Theorem 4.1 (Hessian Spectral Norm Bound). Under Assumptions and 2 for 9
BSpec P.P1
(6p).
with probability at least (1 2( for any Xi, [n]], we have m
Vof(0xx))11
CH
(5)
mm
with =
+ pı)) where y + Am
A.I ANALYSIS OUTLINE
Our analysis follows that of Liu al. (2020) and sharpens the analysis to get better dependence on the depth L of the neural network.
We start by defining the following quantities:
0f
Of da!!)
(fo = max ISISL
ERM
(17)
{
0a (1)
da
22()) = max
w(1)
veo(l()))
Owl1) E mRm
(18)
1
(1)
(c)
(1)
fallta))
22), = max
(19)
1sh <
Ow((1)²
2,2,1
Ow((1)
Oallz 11 (12)
2,2,1
(1)
(2)
(as)ss)
(20)
(w(
(w
(b)
0a
2,2,1
where for an order-3 tensor
IRd xd xds we define the (2 -norm as follows,
ds
d
d2
|T
sup ||x
x x R2d Rg
(21)
-
We will also use the notation ((L+1)
key result established Hessian:
Liu et al. (2020) provides an upper bound the spectral norm of the
Theorem 4.2 (Luu et al. (2020), Theorem 3.1). Under Assumptions 7
assuming there 8 such that < 8, with C1 1,2 + L88h + L and O2 S I we have
Ball-
2
v2](0x))]1 < 222,
-cs2(()
(8)
Vm
In order to prove Theorem 4.1 we prove that Theorem 4.2 holds with high-probability where
8 = follows from Lemma A.3
(2(J) 0(L(1 + +)) follows from Lemma A.4
Q2),(()) = O + 33)) follows from Lemma A.4 and Lemma A.5 and
(x()= ((ut)")nt follows from Lemma A.7
while also establishing precise constants get a proper form for the constant eи in Theorem 4.1 result, cи O 1.2(1 (0 (1++))) )
vm
12

---

Published as a conference paper at ICLR 2023
A.2 SPECTRAL NORMS OF W AND L2 NORMS OF a
We start by bounding the spectral norm of the layer-wise wise matrices at initialization.
Lemma A.I. Consider any [T]. If the parameters initialized (1)
Wo,if No0, oz)) where
as in Assumption 2 then with probability at least (1 - 2.). we have
00 2(1 2m
||W] ll S Soym.
(22)
( Proof. For a (my X m random matrix ( with i.dd. entries Wo, E (O oî), with probability at least (1 - (xxp(-t2/2oj)) the largest singular value of Wo is bounded by
max (w) S collvm + vm--1) + L.
(23)
This concentration result can be easily derived follows: notice that Wo To ( where W ((0, 1), thus we can use the expectation W ( = on W
(E)
|o ( = oolyme + m
from Gordon's Theorem for Gaussian matrices (Vershynin, 2012 Theorem 5.32) in the Gaussian
concentration result for Lipschitz functions (Vershynin) [202]] Proposition 3.4) considering that
B |oo Bll is -n-Liscchitz function when the matrix B is treated vector. Let us choose
t dov log that 23 holds with probability at least (1 2). Then, to obtain
Case 1: 1. With mo = d and mi = m,
| ll2 S aolva vm + 2lggm) S 500(2mm+
V log m)
since we are the over-parameterized regime m 2 d.
Case 2: 2 < 1 L. With m4-1 m,
I 11) ll2 s co(2mm + /2 log m)
Now, using du 2(1+ Los
in both cases completes the proof.
Next we bound the spectral norm layerwise matrices.
Proposition A.1. Under Assumptions for 0 E BSper (fo), with probability at least (1-
2
|W0 + Vm
I [Z].
Proof. By triangle inequality, for E [T.].
(a)
|| 112 < ||W! [| w S σ1 m + P,
where (a) follows from Lemma A. This completes the proof.
Next, we show that the output a of layer has an La norm bounded by (vvm).
Lemma A.2. Consider any l E [L]. Under Assumptions and for 0 E BSpec (fo), with probability
least (1 21), have
1o(0)) (x/+ [1++(001 Σ Edd vm.
|| m ++ _ mm/
+ vmm) Σ
01 mm
13

---

Published as a conference paper at ICLR 2023
Proof. Following AAllen Zhu al. (2019): Liu et al.
(2020). prove the result by recursion. First,
recall that since | d, we have ||
2 v d. Then, since mo d and Φ is 1-Lipschitz
0
w (0)) )11- (0)())122 -
0 dd
6(0)
w vd
1
so that
|a00
1
W w
|1 -
1 w (2
|0(1))2
2
Vd
Va
|
12/|a (0)
1|2 (0(0)/m
+ )
Vm + (6(0))
V
where we used Proposition A.1 the last inequality, which holds with probability least For the inductive step, we assume that for some 1 - 1, we have
|| S vm
01
vm
m
1o(0))
1=1
which holds with the probability at least
2(1-1)
Since & is I-Lipschitz, for layer I, we have
1 m
w
- -l0((0))22 - ② m
- (0))
1
so that
lla
||2 =
1
w
|
$
w (1-1)) a
+ ||((0)l2
m
2
VA
1|2
vml)(00)
m
(a)
p
10 + vmlx(0)
01 +
mml
f-1
(b)
m
01 + vm
+ m 01+
P m
(o(0)).
where (a) follows from Proposition A. and (b) from the inductive step. Since we have used Proposition A.1 times, after union bound, our result would hold with probability at least 1 - 2 This completes the proof.
2g ( AND
a it-1y
A.3 SPECTRAL NORMS OF
Da
Recall that in setup, the layerwise outputs and pre-activations respectively given by:
(! = 1 = (a
W (1-1)
(24)
Vm--1
Lemma A.3. Consider any E ( L.. L}. Under Assumptions and 2 probability at least (1 2).
for O E (00), with
ia (a1(-1]]
2
P 2
5
σ
+
= =
(25)
m
2
14

---

Published as a conference paper at ICLR 2023
Proof. By definition, we have
0a
1
((a
(1) w
(26)
drll--1
Vm
i.j
Since
|All2 = s || |v|22, so that
||
supp|w//2=1 (a v)2, we have that for 2 s
L,
0a
2
1 m
m
Φ¹(a; (0)
Σ
w Ej
(l-(1-))
=
sup
Uj
2
IIv 1a=
m 1=1
1=1
||W0vll2
sup
||v|a 1 m
|
m
(6)
722
where (a) follows from & being I-Lipschitz by Assumption and (b) from Proposition A.1 completes the proof.
This
Lemma A.4. Consider any l E [L]. Under Assumptions and 2 for O E BSpx (0o), with probability
at least (1 21 )
Oa ( iw())
2
1
P
1-1
1-1
P
i-1
|o(()]
S
mm
σ1
+
m11
01
m
Vm
Vm
i=1
(27)
1-1
2
7--1 + lm(0)
Σ
4-1
Proof. Note that the parameter vector (1) vec(W(l)) and can be indexed with j [m] and
j' E [d] when = 1 and j' E [m]] when 1 2 2. Then, we have
!!
1 vm
)ay a1
||=)
(28)
(w
a
1.53'
For 1 E (2...., L). noting that O5
R
mm
and ||V| ||vec(V)]2 for any matrix V, we have
2
(!) ?
1 m
m
(w())
sup rIV|===
(a
(1)
aj 1 |ر=ن V38*
a1 (1-1) 1)
m
j.y==1
1 -
(a
< sup
||V|===1
1 sup
||V
(1
m
[
(1
(6)
Vm
01
+ Vm
σ1
+
.mm
10(01]
m
mm
H-1
+ (0)))
Σ
)ー
1=1
15

---

Published as a conference paper at ICLR 2023
where (a) follows from | & |IVI for any matrix V, and (b) from Lemma A.2
The case follows in a similar manner:
Oa!!) Ow(1))
1 La1a 10
1 |x|
d
which satisfies the form for ( 1. That completes the proof.
A.4 (2,2, NNORRS OF ORDER TENSORS
Lemma A.5. Under Assumptions and 2 for O E p.p1 (fo), each of the following inequalities hold with probability at least (1
m/
(1
S B
(29)
(1))
2,2.1
@a
Bp
72 +
7 + +1((0)
Σ x)))
+1.
(30)
(all-1)o(()))
2
2,2,1
forl= = 2..... L; and
8a
[-1 7 (0(0)
S 30
Σ i-1
(31)
(aW0)2
2,2,1
for E [L].
8Po (Ball 1772
Proof. For the inequality
29 note that
from
26
obtain
1 (a ik
(10 () and so
aa
1
8" (a (1) ( (W. ())
(0a(1-1332
sup
2,2,1
m :=1
IVB V7
sup
1
3
(w (w(WW)))WWWV)))
[|v1ll2 -||_///2l 11
==1
m
sup
B
v1)? + (WWVv2)
[|vill== |vall==1
2m
i=1
1
<
8,
sup
2m
||v=|b==1vval.=11
$ 2m
Bo
30 + p/ 2m)2 B
(32)
where (a) follows from 2ab < a² + b² for a, b E R, and (b) from Proposition A.1 with probability at 2
least 1 m
For the incquality 30 carefully following the chain rule in 28 we obtain
aa
1
"((a!")
(1) aj
fm o'(a!") (1)
(1=s)
(0(--)a
ij
16

---

Published as a conference paper at ICLR 2023
Then, have
a (1)
0a ((W1-1)aW()) @W(())
2,2,1
m
m
M
sup
Σ
(a
W
1 aj
(1-1)
1==
Iv
m
1
+ Vm
2 (ā)
]1
[t |
Vi V25r
T/
m
m Σ
(a; )a
W Vi,k
sup
1vill -
m
m
(a (1)
V V2.u
m
sup
1
3&
(W V1 (V2a
1
V1.k V2,ik
Ivill==|Vaall
171
k=
sup
3
(w ((V2a
1 V2.,,
Iv |vsl]==I[va 1== 2m
1=1
1 B
1 + V2a
sup
+
V2..:
vill==I[Val =1 2m
i=1
360 [ 1 + 1110001-1//
+ +11V2l1
2m
(b)
333
7² ( (0(0)
Σ )11)
2
where (a) follows from (2a(111 1)
2 Σ |/22 ||a--1 s V22lp
||a-_||6 1|2 ||o² and
EMh V2... 112 vm Em
2.c. 2- and (b) follows from Proposition A. and Lemma A.2
with altogether holds with probability at least
For the last inequality in (28) obtain
(1]) we start with the analysis for 2 2. Carefully following the chain rule
8a
1 ""aa(")
)a
(1-1) (t-1)
a.
18-
(aWwr)
i.53" Akk"
m
17

---

Published as a conference paper at ICLR 2023
Then, have
ial
(oW 22221
sup [Vill
(a
(á;
(aa
Jak
(1-1)
a (1-1)
aj
1يz= [R=1] V
Viss 22,
Valle
1=1 DJ'
R, =1
(a,
V1-1)
11-1) V 2,
sup
1,33"
ak
I
=1 V2
==
===1
k==1
1
(12 ( V2a (1-1))
sup
m
sup
1
8$
(V2a + (V2a"
-Vill==lvval
2m
sup
2m B
1
V2a
(111) V22
// / |
IIVil - VV
2m 3a( 0-
+ (1-1)
S 3r
1-1 (6)
which holds with probability at least 2(1-1), For the case
1, it is easy to show that
20 )x |== (x=)]] and so
S Bg- This completes
6.8 AKK
2,2,1
the proof.
L
A.5
af 1.o0 NORM Dalli
Let ((0 we have
of Satl
R for any E [L]. Let by
denote (1) initialization. By direct calculation,
b
Of
II
L
0f dalL)
da!!)
dall-I)
|-+++
II
(W(()) D(C))
mm
where (('') is diagonal matrix of the gradient of activations, i.e., D o'(a,') also have the following recursion:
Note that
b 10) af @a 0f
O da!!) Oa(+1
(Wil+1)) D((+1)
Lemma A.6. Consider any I [L]. Under Assumption and for BSpec (0o), with probability at least 1 2(L-I+1)
P.P
m
L-1
1
[ 1|
+
Vm (1+
(33)
Vm
and
bb
11
1| <
v
(34)
mm
vm
18

---

Published as a conference paper at ICLR 2023
Proof. First, note that [bb0)]2
|vll S J. (1lvol22 + 1|v voll)) Ji (1 + p1), where
vm
ym
the inequality follows from from Proposition
A.1 Now, for the inductive step, assume ||b")||2 S
(01
L-!
Vm (1 + p1) with probability at least 1 Then,
vm
(1-1)
b
600
10(1-1)
D
2
L-1
01
p
01
P
(1
p1)
m
m
m
L-1+1
p
(1 + PI)
m
where the last inequality follows from Lemma A.3 with probability at least 1 - _ + 1). Since we
use Proposition AA.lonee layer L and then Lemma A.3 [L 1) times at layer L, then we have that everything holds altogether with probability at least (L-1+1). We have finished the proof by induction.
Lemma A.7. Consider any 1 E [L]. Under Assumptions and 2 for O E BBpr (Po), with probability at least
2(--))
|b00
(1 p1).
(35)
vm
Proof. For any / e [L], by definition i-th component of ((0, i.., bl",
takes the form
b10h da(L) 0f 0a(4)
da!") dalt)
da
mm
Then, with W:
denoting the i-th column of the matrix w(),
(4) o' o'(a!"!
(a)
(w:()) T
II
dall"
dall)
0a 1
m
17
11(
F=1+2
=12
W
mm
1-1-1
(36)
where (a) follows from
da da!" σ)
vm o'a (wW))
1
(1) (b) from o being 1-Lipschitz, (c) from
Lemma A.3 and (d) from probability (L I).
w!lll 1
S ||W0|| and Proposition A.1 which altogether holds with
Therefore, for every e [m].
da
b
<
m da (1)
da (L)
<
||v||2
/
m
da (1)
2
7 (-1( + p1).
/ /m
where the last inequality follows from the proof.
36 and
||v||2 < ||volla + flv 10--vin voll2 I 1+ This completes
19

---

Published as a conference paper at ICLR 2023
A.6 USEFUL BOUNDS
Lemma 4.1 (Predictor gradient bounds). Under Assumptions
andd for E B with
probability at least (1- 2(L+1) we have
V2f(0:x)|l 1 7 vm
[Vo S and
(1 p1)
(9)
with e² (M 1))2 + (1 p1) (1 7 01 + vm
71-1 h(1)
16(0)) -
Proof.
We first prove the bound on the gradient with respect to the weights. Using the chain rule,
0s
II
dall
0s
(wl)
Ow!()
Oa 1] (a(1)
1'=+11
and so
0
!!!
2
L
0f
2
(0)
(1)
1
<
7
((--1)
- (1 (1+ pi)² pi)
(v)(1)
Owill
Da(L)
Ow
2
1=1+1
2
(b)
+-+ (0(0)
1-1
2((1-1)
1
(1 p1)
m
forl E [Z], where (a) follows from Lemma
A.6
(b) follows from Lemma A.4 Similarly,
0ʃ
2 1
2 (z)
7" + (0))
S
Ow (Lo(
1)
2
m
where we used Lemma A.2
for the inequality. Now,
++1
Σ
Owlli
1=1
(a)
L + (6(0)
2
+ +- (1+ + p1)
1000)
|600)
1-1
2
22(0-1)
where (a) follows with probability - (L + 1) using union bound from all the previously used results.
We now prove the bound on the gradient with respect to the input data. Using the chain rule,
0f
0f
(1
I.
ia?"))
II
0x
0a
(0
Da
11
(a.))
1'=
and so
Of
da
oall)
0f
0x
Oa
-a(('-1]
da(L)
2
(1)
(a)
Of
0a
-a(
1==
(a)
(1 p1)
Vm
(1 + P1)
m
where (a) follows from Lemma A.3 and Lemma A.6 with probability at least 21 due to union bound, This completes the proof.
20

---

Published as a conference paper at ICLR 2023
Lemma 4.2 (Loss bounds). Consider the square loss. Under Assumptions
/ and 2 for 01t
P. vm
each of the following inequalities hold with probability at least
(1 2(++
[(00) S C0.0.
and (()) I Cpr. for 0 E B where Ca.b 2 > vi 2(1 + a) (o(b) and g(a) = a² + 10(0)) Et= a² for any a, b E R.
Proof. We start by noticing that for (pSpe((0)). P.Pi
1 Σ yi x0)x
1
(())
(20) (1;(00x)))²)
(37)
Now, let consider the particular case On and generic ||x||| vd. Let (1) be the layerwise output of layer at initialization. Then,
(f(0o: x)1
vo
Vm
1
Ivoll2
|| |a!
Vm
WVE
11 (x)
Vm
2
(6)
of + (0(0)
Σ
o mm
Vm
where (a) follows by assumption and (b) follows from following the same proof as in Lemma A.2 with the difference that we consider the weights at initialization. Now, replacing this result back (37) we obtain L(0)) S 60,7s
Now, let consider the general case of 9 E BSpec (Bo).
P.p:
[f(
T (1(1(x))
Vm
1
|v||2
(x()
Vm
2
1
(1 + pi) 10 (x)
mm
1
(1 (1+pi) pi)
(7'
v
Vm
(1 (1+1))((7))
where (a) follows from ||0/|2 S ||vol12 + ||v volla 1 + Pr. and (b) follows from Lemma A.2 Now, replacing this result back in (37 we obtain L(0)) - CpLiT
In either case, a union bound let us obtain the probability with which the results hold. This finishes the proof.
Corollary 4.1 (Loss gradient bound). Consider the square loss. Under Asssuppiinn/ and 2 for
BSpec with probability at least (1- 2(L+1) we have VoL(()) S 2() < 2 Cpr
with e as in Lemma 4.1 and cp as in Lemma 4.2
Proof. We have that |V =
<
Σ 1 V
ef
28 Σ 18:
0:l < 20y (()) Po170 where (a) follows from Lemma 4.1 and (b) from Lemma
4.2
17
21

---

Published as a conference paper at ICLR 2023
A.7 REGARDING THE NETWORK ARCHITECTURES IN OUR WORK AND LIU ET AL.
(2020) 's
A difference between the neural network used in our work and the one in (Liu et al. 2020 is that we normalize the norm of the last layer's ' weight at initialization, whereas (Liu et al.
2020) does
not. However, if we did not normalize our last layer, then our result the Hessian spectral norm
bound would still hold with Ô instead of O: consequently, our comparison with (Liu et al. 2020) on the dependence on the network's 's depth L (our polynomial dependence against their exponential dependence) would still hold as stated Remark 4.2
B RESTRICTED STRONG CONVEXITY
We establish the results from Section | in this appendix.
B.1 RESTRICTED STRONG CONVEXITY AND SMOOTHNESS
Theorem 5.1 (RSC for Square Loss). For square loss, under Assumptions 7
Hand 2
with probability
least (1 2(L+1)) Ao' E 0% PiP1 (6o) BBuo (0.) with 0₂ BSpee (0o). p.P1
m
C(0') 2 [(0,) + 10' 02 vol(O.)) + at 0100 -0
Oz 11
with a2 = E 1
C2
(10)
2
vm
where g. - VoJ(O.xx)), = 2x² and 2e (2pp2 + (onn) with cH as in The- orem Q as in Lemma 4.. and Cpy.y as Lemma 4.2 Consequently, L satisfies RSC w.r.t.
BSpee (0n) BEue (0c), PiP1
(E)) 0,) whenever 04 >
P2
Proof. For any 0 E 02/2 n BEe (Oo). by the second order Taylor expansion around 0,, we have
[(0') L(O+) + (0' 02, VoL(O)) 1 -0 -0.)T
L((.))
(0' 66),
002
where 8, = = + +11- - -) for some & E [0, 1]. We note that 0g BSpec (f0) since,
1 - w0 = <w' (1) - - + + - [1- - - (1-E1) (
< <|lw'0 w:'ll (1 $) w/ w!60 1|2 S p, for any E [L]. where the last
inequality follows from our assumption O' O2 (sSpec(0o); and
[ -ig+t) = || -2-voal volla S Pr. by following a similar derivation as in the previous point.
Focusing on the quadratic form in the Taylor expansion and recalling the form of the Hessian, we get
C(..)
00' - 0,)
(0' - -.)
002
= (0' 81) 1
(f x;)
(f())x;;)
82 {((;x))))))
+ C.
(8'-0)) 0c)
n2
00
00
ag2
0 x;)
0'''' 0,) 02 f (0r;x;))
g
0' Oz.
(0' 0z)
00
202
1=1
11
12
22

---

Published as a conference paper at ICLR 2023
where 4; Uyy. (Or, x:)), -== 86(v..e)
and E"
((c( 0=
Now, note that
d=
==(()x))))
== (())
0' 0, 0f x,)
11
71
00
2 B
0f((xx.)
Of(Oxxx))
af(O(;x:)
0' 002 00
71
00
00
00 05(0, x()
2
0' O,, a[(0;;x,) x,)
as(0g; x.)
0'
09
00
00
0f(0g;x,)
0' O2, 0f(,xx,,
(0;
+
0'
O2,
00
00
00
1=1
(a) 2
0' O2, xf(Oxxx.)
4
0f(0(x)) x
0f(((xx))
xf(0)xx.)
00
00
00
00
X 100 0.112
N
2
8 0
Of(0xx))
00
4
Σ
0
Vm
CH
110 0
1211
02
i=1
2
Of x;)
4OCH
8
110' 0el1
n1
00
m
2
af(;;x;;
40CH
2x
110'
0
100 0.112 mm
00
2
2
0.(0,; x;)
40cH 110'
0cll2
2x²
110' - 100--.112.
00
Vm
2
where (a) follows by Cauchy- Schwartz inequality; (b) follows by Jensen's inequality (first term)
and the use of Theorem 4.1 and Lemma 4.1 due to 0 B (60); (c) follows from 0 6g 2
I150' + (1 - {), - 0ell2 = E 110' - 0.ll S T 00 2 (d) follows since O' E Q and from the fact that p q = cos(p. 9) |||l| ||q|| for any vectors p.
For analyzing I2, first note that for square loss, Cy, = 2(Urr, - y1) with Th.e = f(,;; x,), so that for the vector 1lr,lii, we have 1 [1(2,,liil2 = -i=1(ie yv)2 = 4L(0.). Further, with
Qi,i (0' -0,)T f(0,x))) (0' 0z), we have
00
02 p00(0; xi)
02 0² x.)
< CH 0 - 0
Qu.el = (0' - -0))
(0' - 0,)
s 110' 0,11
002
002
v Vm
Now, note that
12
1
)
(#))
L
Vn
(0)
( 111.
1/2
1
1/2
1=1
CH 11'
0r112
2 22 (().)
Vm
23

---

Published as a conference paper at ICLR 2023
where (a) follows by Cauchy-Schie Schwar-S inequality, Putting the lower bounds on I1 and Iy back, with g:
1/4 n
Di=
0f(0,x.)
we have
86
(0' 0.) 0 C(.,))
4ocH 110
0ell2 + 2CH v c(0,) 110' 0,112
(0' -0,)
2x |B
002
vm
Now, since O' E
B
(E,) 110 1100-000 0 S p2, so we have
Pz
8 ((0))
40CHP2 + 2CH V C(b))
(0' - 0,)
(0' - 0,) 2 2x² |g::12
110' 0c112
002
Vm
2k 40CHP2 + 2CH /Cp..7
110' - 0.112 101--.
vm
where the last inequality follows from Lemma 4.2
That completes the proof.
Next, we state and prove the RSC result for general losses.
Theorem B.1 (RSC of Loss). Under Assumptions and
with probability at least (1 2(L+1)
VO' 2% n PSpe (0o) n (BBuc(O.).
oh ((00) 2 L(0.) + 10' Oc voL(O.)) + O1 110' 0c112, with
1
C4 + C4.t
(38)
2
vm
- Vol(0;;x;), C1 an², c4 Pa on is as in Theorem and Ca. CH where Ei (e,,)² with Eú )f(u
where Br
and 0 E BSpec being some point in xb)()x))))
az
p.p.
the segment that joins 8' and dg. Consequently, C satisfies RSC w.r.t. (Q), BSee (B))nBB (ft), Bs) whenever 0₁ > O.
Pa
Proof. For any 0' E 022/ n p.p. (On). by the second order Taylor expansion around 6,, we have
[(0') ((0.) + (0' Or, voL(O.) 1 -0 0.) L(.,)
(0' -.),,
202
where 0, = 50' + (1 - E), for some & E [0, 1]. We note that o, BSpec (0o) since.
w/ w:
|| = (w' (1) - -Ew (1 (1- () (1 k)
< <|w''0 w. (1 5) | ( p, for any E [L], where the last
inequality follows from our assumption 0²,0, E P.P (0)); and
[
1 voll2 S Pt. by following similar derivation as in the w/ -w0h+)))-((-++/)/
previous point.
Focusing on the quadratic form in the Taylor expansion and recalling the form of the Hessian, we get
00' 0,) 82 C(..)
(0' - -.)
002
= (0' 01) 1
af x;)
(f(;);;;)
82 ((,;x(;);)
+ C.
(0' (8'-0)) 0c)
n2
00
00
ag2
0 x;)
0'''' 0,) 02 (0r;xx))
g
0' Oz.
(0' -z))
00
202
i=1
11
12
24

---

Published as a conference paper at ICLR 2023
where e; Uyyi ((,r, xi)), -== 86(v..e)
and E"
((c( 0=
Now, note that
0=
==((0x))))
2= (().)x)))
x..
11
0' O2. 00
8
a (0 x4)
Os(6xxi,)
0 0::
11
00
00
00
2
( x;)
2
( x;)
(f(0;; x:)
8
02:
8'
l:: 00
09
11 1=1
00
4
05(0r;x;)
0f(0;;x,)
(0(;
0'
O2:
0' O2. 00
00
00
(a)
0s(0;; x.)
8'
1. 09
1=1
Of xi)
0s Os x.)
0f(0r; xx)
110' 0.11
00
00
00
2
0
0'
O5
0f(0;; x.)
4
CH
100,
Og 1121100
0z 112
00
71
t=1
2
n Of(0;;x x:)
20QCH
0
110'
0.11
00
m
1
Of(0:: x.)
2agch 110' - 0211
110'
0 12
a0
vm
2
(f((;:x,)
20 0
0cll2 110 0.112.
a0
vm
where (a) follows by Cauchy-Schie Schwartz incquality; (b) follows by Jensen's inequality (first term) and the use of Theorem 4.1 and Lemma 4.1 due to O, SSpe (c) follows from 0g 6: l
2
llgo' + (1 - E) 0ell2 E 110' 0.ll S TTO Oellz: (d) follows since 0' E Q and from the fact. that p q = cos(p, 4) ||p|| |aal| for any vectors p.
For analyzing I2. let A 1. Σt (2,,)) As before, with Qt,i (0' - 0,)T have
0 f(0ex))) 08
(0' 0,),
Qu.al = (6'- (6'- 02 f(0,; x;)
(0' - 01) s 010' 0.12
8 f(o;; xx)
CH 0
0
002
0g2
/ m
2
Now, note that
12
1
(1 )
(#))
Vn
(0)
( 111.
1/2
1 12
1/2
1=1
CH 110
0.112
vm
25

---

Published as a conference paper at ICLR 2023
where (a) follows by Cauchy-Schwarle inequality. Putting the lower bounds on I1 and Iz back, with
g: 1 n
Di=1
0)(0,x.)
we have
86
0 ((),)
20ge 110 - 02l12 + CHH CHVd 110 - 0g l1
(0' 01)
(0' - 01) 2 ar. |gell2
002
vm
Now, since 0' E B (0t), 110' - 0 p2, so we have
(0' - 0,) 8 ((o))
200ch P2 + CH
(0' - -0,) 2 ax B 12
110' - -0el12
002
Vm
That completes the proof.
Theorem 5.2 (Local Smoothness for Square Loss). For square loss, under Assumptions 7 andd with probability at least (1 2)) 40, 0' E (Spee(0o).
(8o).
- 1100
8
2CH v Cpp.
[(0') S (()) + (0' 0, VoL())
0112
with B ==20² +
(11)
2
vm
with си as in Theorem 4.1 as in Lemma J.1 and c as in Lemma 4.2 Consequently, L is locally 3-smooth. Moreover, if (and so σ1 and p) is chosen according the desirable operating regimes (see Remark 4.1) and p1 = (L)) then B = O(poly(44 (L)).
Proof. By the second order Taylor expansion about 0 BSpec (0o); we have L(0') = =((0) + (0' p.P1
0, VoL(O)) + (0' - 0)
(0' 0), where 0 = =00- + (1 - E)0 for some & E [0, 1]. Then,
88
00' 0 C()
(0'
002
n
2 OF x.) 00(0;x))
8 P xi)
= (0' 0)
+
(0'-0)
00
00
002
1=1
n
05(0; x:)
2
n
( 0) T 82 [(;; xi)
0' 0,
(0' 0)
n
00
n
002
12
where l, U(y6, [0,,xx)) 6-=
and Cy
8 ((v 0=*
Now, note that
8=
(0.x.))
== (00,x))
0s x:)
T1
8" 0' 0.
00
I=1
2
(0)
0s (Ō; x.)
Σ
110' - 011
00
2e 110 013.
where (a) follows by the Cauchy-Schward inequality and (b) from Lemma 4.1
For Ig. first note that for square loss, & = 2( y:) with ÿ. = f(0; x.). so that for the vector
[e],, we have + 11 = Em (it y;)² AC((). Further, with
Q₂ (0' 0) 82 f(0;;xs))
(0' 00--)). 0),
002
we have
10:1 = 00) 02 f xx)
02 (()))))
CH 0 - 013
(0' 0)
< 0 012
002
002
26

---

Published as a conference paper at ICLR 2023
Then, have
1 1
Σ
8,00'
01
8 =(0x0xx))
(0'
0)
202
1=1
(1:0))
1
4
Vn
(2)
1/2
1/2
< 2/ 2(0) CH 10'
011
vm
where (a) follows by
Putting the upper bounds on I and Ig back, we have
(0' - 0)) (())
2Ch V [())
002 (0' - 0)
2Ø² +
110' -01
vm
2CH v Cor.y
2Ø²
+
100 012
mm
where the last inequality follows from Lemma 4.2 This proves the first statement of the theorem. Now, the second statement simply follows from the fact that by choosing 7 (and so p and σ1) according to the desirable operating regimes (see Remark 4.1) and by choosing P1 according to Cи = O(poly(L)), p² = O(poly(L)) and Cp..7 = O(poly(L)) This
Theorem 4.1 we obtain
completes the proof.
Next, we state and prove the smoothness result for general losses.
Theorem B.2 (Local Smoothness of Loss). Under Assumptions
3 and 2 with probability least
(1 2(I++1), L(0), E (0o). is 3-smooth with B lbe A - (2)2 with Ey (f().2)
C vm
with as in Lemma 4. and
and Ô BSpec being some point in the segment x(,,xx))))
0=
that joins O' and 0 as in
Proof. By the second order Taylor expansion about 6, we have L(0') = [(0) + (6' 8, VoC(O))
(0' 0)T 82 ((0)
(0' A), where 0 = g0' (1 0) for some [0, 1]. Then,
02 (())
(0' 0)
(0' Ø)
002
2 ff(xx,,
0f():x;)
T
02 f(0 x0)
(0'
0)
e 00
+ Ey
(0' (0'-0)
00
002
i=1
1
d (f x1)
n
(0''' - 0) 02 ff000000 x,)
0' - 0,
(0' 0)
00
002
I
12
where l, = E(y,, f(0, x:)), C,
a((y..)
and E
8 (()())))
Now, note that
Oz
0z
((0xx)))
2= ((0.x.))
@ x.)
71
0' - 0.
00
1=1
0s (Ō; x;)
110' 011
00
2
b 110' 012
27

---

Published as a conference paper at ICLR 2023
where (a) follows by the Cauchy-Schwand inequality and (b) from Lemma 4.1
For 12, let d = -1 Further, with Qr,5 = (6' - -8)
2² f(0x..)
(0'
f), we have
00
10u (6' (8' 0 s00(0 xi) (0' 0) I 110' 013
00 f [0,s x.)
CH 0
002
002
m
Then, we have
1 n
00 f(00; x1)
1
Σ
(
8)
(0' 8)
71
082
Qi
n
Vn
1/2
1/2
Q
72
CH 1
0 0
mm
where (a) follows by Seuchy-Schwand Putting the upper bounds on I and Iz back, we have
LL)) 002
CH Ae
(0' - 8)
(0'
0
bo²
+
|10' 012
vm
This completes the proof.
Lemma 5.1 (RSC- RPL). Let B; = 0% (8p) BBac
the setting of Theorem 5.1
P.P1
foo then the tuple (Be, 0e) satisfies the Restricted Polyak- Lojass-io (RPL) condition, i.e.,
C(0.) inf (()) I |VoC(0.)13 B:
(12)
20
with probability at least (1 2(L+1)). m
Proof. Define
(0) = :(00)) + (0 -r. VoL(Oe) + at
"2 10 -0,122
By Theorem 5.1 VO'
Br, we have
C((') 2 La, (0')
(39)
Further, note that Lo, (0) is minimized :.t1 0, voL( and the minimum value is:
inf Lo, (0) Co, [((,) 204
voL(0.)
Then, we have
(a) C(0)
inf
inf La. 2 inf Lo. (0) [(0,)
BEB,
BEB,
8
204
where (a) follows from 39 Rearranging terms completes the proof.
B.2 CONVERGENCE WITH RESTRICTED STRONG CONVEXITY
Lemma 5.2 (Local Loss Reduction in B,). Let ar, B be as in Theorems 5.1 and 5.2 respectively, and B, := 0% n BSpec (0o) n BBEu((s, (0t). Consider Assumptions 7 and and gradient descent with step size P.P1
B E (0, Then, for any 0,41 E &arginf BER, L(0), we have with probability
at least (1 2(+1)) )
[(0(41) L(0 < aswe (2 (1--0u
wi)) (C(0,) L(0
(13)
28

---

Published as a conference paper at ICLR 2023
Proof. Since C is 8-smooth by Theorem 5.2 have
8
[(0++1) S [(0.) + (0c+1 Oc, VoL(O.))
2 1:100+1
-0.l2
=(0,) - TN vol 1812
(VoC(0,)11
(40)
C(O,) TL (1 3Tc |(,C(()))
2
Since 8.41 E arginfØes, (()) and ar > 0 by assumption, from Lemma 5.1 we obtain
- -IVooC(0)113 - - 20, - c(0++1)).
Hence
31%
[(0+41) [(0++1) - 2(6)) [(B++2)
VoL(0))1
2
(a)
[(0,) [(Oc+1) -1]t (1
20,(C(0))) - [(0++1))
2
1 2007): (1- 8T7
(C(0,) [()++1))
2
where (a) follows for any 4i 3 because this implies
An 2 0. Choosing T Wr ,, (0,
- -(0r-1)-
- (1- anh'
B -1-0
(2 wr) (C((.)) C(0++1))
This completes the proof.
Theorem 5.3 (Global Loss Reduction in BSpec Let at, B be as in Theorems 5.1 and 5.2
respectively, and B, Qt n 13Spcc (0o) n. BBuc BB)). Let 0" arginf D n Spce (Bo)
(()), 0st1
P.P.
arginl BEB, (()), and 7h ((0
[(0,) [(0") Let ou, 3 be as in Theorems 5.1 and 5.2 respectively,
and B, = Qt n Spec (0o) (E.). Consider Assumptions) 7 and 4 and gradient descent
p.Pl
with step size The 3 Wr E (0, 2). Then, with probability at least (1 20 2.I+1)
we have we have
Tt E [0, and
[(0++1) - L(0*) < (1- Ortitt 11-
(1- wi) (R(0,) - L(0"))
3 -
(14)
Proof. We start by showing %
[(6.41)-L(0) [(0,) 2(6-)
satisfies S 7t. Since 0 arginf L(0)
se B (9))
and l14 E BSpec (0o) by the definition of gradient descent and Assumption 4 we have
(0) ((0') < C(0++1) S ((O.) B
We (1 Wi (Vo((0))11 L(O.),
where (a) follows from 40 Since L(0,+1) 2 L(8") and [(O,) > L(0"), we have 2 0. Further, we have [(0(+1) < (0.), ). and so we have 7t 1. To see this, consider two cases: (i) 0 B and (ii) 0++1 B, When l++1 E Br, we have L(0++1) I L(0 < L(O.). When 6 & B we only consider the case [(0++1) < L(0++1); otherwise, if [(0++1) > L(0+1)) then follows [(0++1) < L(O,) by (40). So, let us consider level sets of the loss between L(0,+1) and C(),). Because of the definition of Q' (which defines cone), the RSC property due to 8' E B,, and the smoohtness of the loss, we will have some 6' B, living in one of those level sets such that ((0,41) & C(8') < L(O,), but then ((8++1) & L(8') by definition, implying ((0,+1) < C(0.). Hence, 76
29

---

Published as a conference paper at ICLR 2023
Now, with W/ (0, have
[(0++1) - -(0)))
=[(0++1) - ((0(+1) [(0(+1) - C()*)
=
apWo
(2 wi) (C(()) - ((0(+1)) + (1- aaub (2 (wi) (C(B1+1) - (())))
B
B
aww (2 -wi) wi)) c(0cti) ((0)))(((()))) (C(07) -(1 (1-22)
(((++1)
a (2 wo) ((07)
B
(2 wi)
(C(()) - [(8")) + anw
(2 - (w) - [(f"))
B
B
agle
B (2 wi) (C(0)) - [(8")) + awt
(2 - - w))r C(0*))
B
(1 (2 - we) (E((1) - L(8*))
B
That completes the proof.
C ANALYSIS FOR MODELS WITH & OUTPUTS
In this section, we illustrate that our results can be extended neural models with & outputs.
C.1 OPTIMIZATION SETUP WITH & OUTPUTS
Consider training set D fx, y.l E X E E 1. We will denote by X E Rgad the matrix whose ith row is x! The goal is to minimize the square loss:
1 y. 3.112
((0)
(un (n(xxx,))
1=
where the prediction y; = x(0;xx)) R is from deep model, fn (0: x0)) output, and E R denotes the parameter vector. In our setting is a feed-forward multi-layer (fully-comnected) neural network with depth L and widths m,/ E [L] == {l..... L} given by
denotes the h
(x) =x,
(x)= =
1
w0l (x))) 1 I....,,
(41)
f(0;x) = (x+
VmL L (x)
where (()) E mm;; 1,1 E [L] are layer-wise weight matrices, V E mu.k matrix, 2(.) is the smooth (pointwise) activation function, and the total set of parameters
xk is the last layer
= (v) (ec( TVTT
IR Ele, mimi-t
(42)
with ma = d. Note that the total number of parameters is Σt_ 1,m-1 + kmzg, For simplicity, we will assume that the width of all the layers is the same, i.c., my = m, l [Z].
Define the pointwise loss lsp. (ymh Sen) )² and denote its first- and second-derivatiin -derivative w.r.t. D.h. as C == -= 2(thh - Iia) and 4% := 2. Let fr (0;x), h E [k] denote the th output, and let the gradient
and Hessian of fi. (6: (3:xx x;) w.r.t. 0 be denoted
(0;
V = 0² f2;
V St
and
00
002
30

---

Published as a conference paper at ICLR 2023
By chain rule, the gradient and Hessian of the empirical loss w.r.t 0 are given by
AC(0)
00
h=1
CC
F. fihh V.
ag2
im h=1
For the last layer, note that
(0;x;) = 1 - a (2) (xx)
Vm
where Va Rn is the last layer vector corresponding to output fa and = [v,]] gm*k the last layer matrix. For the analysis, we update the definition of the spectral norm ball to work with each last layer vector Vy:
Spec (0) = ( IRP as in 42
IW
S SpLE (4), - vall2 s pl, E [R]
(43)
Similarly, we update the initialization so each of the last layer vectors are unit norm.
Assumption 5 (Initialization). The initialization weights w ((0, for I E [T] where 0i 0, and Vo, h E [k] are random unit vectors with || 1. Further, assume the input data satisfies; ||x:||2 = Vd, i [n]].
0
2(1+
V22m
Based on the setup, following Theorem 4.1 we get the following result for the Hessian of each fn:
Theorem C.1 (Hessian Spectral Norm Bound). Under Assumptions and 5 for O E BSpe (0n) as in 43 P1 = (ppo)y(T)), with probability at least (1 2(1+1) ), for any x,, 8 E [n]. we have
[[
CH
(44)
Vm
with = (ppo)((p))))L) + 224) where 7 + mm
C.2 RESTRICTED STRONG CONVEXITY AND SMOOTHNESS
Let assume have sequence of iterates (0e from gradient descent. Our RSC analysis will rely on the following - step t, which avoids directions almost orthogonal to the average gradient of the predictor.
(ofi(00;);) For any Definition C.I (Ộ. sets). For iterate 0, E IRP, let nk Li=1 1=
(0, 1), define Q' = {6 c/css( 0r, gt)l 2 n).
We define the B, = Qt SSScc (06) B Bu (0.). We focus on establishing RSC w.r.t. the tuple
p.P.
(Be, fe). where BSper(Bo) becomes the feasible set for the optimization and Euc (0, is an Euclidean ball around the current iterate.
Pa
Theorem C.2 (RSC for k-output Square Loss). For square loss, under Assumptions 7 and with probability at least (1 2(I++1) 40' E Q BSpec (0o) n B (0t).
C((') ((0.) + (0' O., voL(O.) + at 110 0.112
kcz
(45)
with a: c 1ig
Vm
where g: nk 4.1 0 as in Lemma 4.1 and Cpin in Lemma 4.2 Consequently, L satisfies RSC as in Theorem (¹) 0 BSpec (0n) BEuc (0.) 0z) whenever 04, >
E Vofn (fxx;;) ei = 2x² and 02 2ch (2pp2 kkep with eh
PiP1
31

---

Published as a conference paper at ICLR 2023
Proof. For any 8' E Q% n (p(()), by the second order Taylor expansion around 8,, we have
1 22100 -0,)² 0 ((0,) [(0') ((0,) + (0' 0,, VoC(O.))
(0' 02)
002
where 0. =88 + (1 -) for some & E [0, 1]. We note that Og Spec (fo) since,
pips
( (0) - -50(0 (1 -)0!! (1 _)08²
- + (1
S p. for any [T.]. where the last inequality follows from our assumption
0
0 E
Spec Sppe p.p.
(fo); and
01(++) 0( -1Vv-w -Voll S kpi, by following similar derivation in the
previous point.
Focusing on the quadratic form in the Taylor expansion and recalling the form of the Hessian, we get
LL..) (0' - O S
(0' 0.)
802
0 (0, (0,;))
0 (m(;xx)))
(0' 01)
Cip
(0' (0' 0.)
00
00
002
0. (ft:
1
C (0' 0,) 02 fn (0e:
0'
0.,
(0' 02)
00
002
1=1
i=1
A=1
12
where ln = C(yin, x:)), C. 8f(ga..)
and 8% (2
1== fn (0...))
32

---

Published as a conference paper at ICLR 2023
Now, note that
0Sn (O,;0x;x.) x.)
0' 02,
ih
00
h=1
2
(0((0)))))
O.I((0xxx))
(0;; x1)
0' O2. 00
+
00
00
1=
h=1
2
(f((0.:)))
2
2
n
k
35 0fn(0,;; x.)
3.h (0,;
0 O,,
00
00
00
i=1 h=1
4
(fx(0(:4))
(.:(0(:
(f;(%)
0'
O2,
0' Os,
00
00
00
i=1
h=1
(1)
2 7
(f;(0);).)
2
T
Of (0
5 xi)
0 (fn(0(;x,))
0'
0::
110' - -0112
00
TI
00
00
00
(6)
2h
0'
0.:
&
O0( X1)
k
CH
110,
0:112110' - 0e113
nk
00
n
m
h=1
(c)
a f (0 X.)
4kgcH
2k
0'
110' - 0
vuk
00
vm
(d)
k
(fe x;)
4hoCH
2
2x² k
110' 0
110' - -0213
niki
00
mm
(0p;
40CH 1|0 -0e112 110 0z 12
k
2x²
nk
00
vm
1=1
where (a) follows by Cauchy-Schward inequality; (b) follows by Jensen's inequality (first term)
and the use of Theorem 4.1 and Lemma 4.1 due to 02 BSpec (c) follows from 0. 0z 2
p.PL
1150' + (1 -) 0el12 E 110' 0el ll T'' Gellzi (d) follows since 0' Q4 and from the fact that p 9 cos(p. 9) IIpll [aall for any vectors p.
For analyzing I2, first note that for square loss, Gn, = 2(gin,t - yan) with Jih, = fn x.). so that for the vector 1 we have 1/ 11 _ ΣT= E (Drin - yin)2 4L(0,). Further, with
Quh = (0' - 02) 8² (.,0xx)) (0' - 0z), we have
842
82 (n x;) (0' - 0.) s $110' -10'--011 0.112
88 [1((((;
crrl0 - 0el13
1Qth.el = (8' 0T)
0g2
002
vm
Now, note that
1
Ta
C Qih.t
n
(2
1
Vn
Vn
1/2
k
1/2
I=1
h=1
i=1
h=1
k k 1'
Og 12
2/ C(0.)
Vm
33

---

Published as a conference paper at ICLR 2023
where (a) follows by Cauchy- Souchy-Schwartz inequality.
Putting the lower bounds on I and 12 back, with g: ni
1
2i 2 (0;x0));;))
have
(0' 01) 8 ((0e)
(0' 06) 2 2n² ll::l22 40CH 100 Og2
0g112 + 2011 v ((0:)
110 0.112
v m
Now, since lf E Buu (0,)) (0,), 110' - 0 S P2. so we have
(0' - 0.) 0 (0,))
40CHP2 + 2CH V C(O()
(0' 0,) 2 k
2x |
110' -0.12
002
vm
40c + 2CH v /kppn
2 k
2k²
12
110' 0.112
vm
where the last inequality follows from Lemma
4.2
That completes the proof.
Theorem C.3 (Local Smoothness for k-output Square Loss). Under Assumptions 7 and with
probability at least (1 2(L+1)) vB, 0' E (3Spe((0)).
3 110' 012 with 3 3= =k2k? +
2kch v kcpir
C(0'= S (()) (0' VoC(()
(46)
2
m
with си in Theorem 4.1 @ as Lemma and Cp,, as Lemma Consequently, C. is locally 3-smooth.
Proof. By the second order Taylor expansion about E (eSpec(9o) we have [(0') = [(0) + (8' P.Pt
0, Vo((O)) + (0' - 0)
(0' 0). where 0 = + (1 - t)o for some & E [0, 1]. Then,
a02
(0' 0) T (())
(0'
0)
002
12
0 (0; x,) 05 (0;x,)
8 (0;x;;)
(6'
+ Ca
(8' (8'-0)
71
09
00
002
2
f (0; x;)
8)T 02 fn(0; xi)
8'
0
Cn (0'
(0' 0)
n1
th
00
002
11
where ln = U(yi, (0,0, (.)), C/p ae(g.h.x)
8 (lgin...))
and 4/
82
Gz
(0,x))
(0xx.)))
Now, note that
afr (f: xx.
11
- Ō,
ih
00
i=1 h=1
(a) 2 n
(f )
110'
011
00
1
< 2ke 10 - 0
where (a) follows by the Cauchy-Schwand inequality and (b) from Lemma 4.1
For 1g, first note that for square loss, Cy 2( yun) with Uıa fa (0:x)) that for the vector
[.,,, we have [1 = Σー Σk=
(jin - yya)² 4L(0). Further, with
Qih = (6' 8)T 02 (n, (@' - 8).
ag2
34

---

Published as a conference paper at ICLR 2023
have
02 fi fn x:) Qui (8' (8'- -0)
(6' -0) S 110' 012
8 fn (0; x,)
CH
0
062
002
/
Then, have
3n (0' 8)T 0 fn; x1)
(0' 0)
082
&
(1
Qih
VT
h=1
1/2
1/2
(9)
n2
h=1
i=
1am
kcH
0' 01
s 2 C())
vm
where (a) follows by Cauchy-Schwarc Putting the upper bounds on /1 and 12 back, we have
(6' 0) -) C()
2kcn / C())
(0' 0) =
2k.a +
||0' 0113
002
mm
2kcn v kCpus
2k
110' 012
vm
where the last inequality follows from Lemma 4.2 That completes the proof.
Note that we now have the RSC and smoothness results for the k-output case similar to the single output case. With these properties, the rest of the convergence analysis for the k-output case stays the same as before.
35


Reviews:
[{"review_id": "_THLzeuUjJw", "reviewer": "Reviewer_uzLy", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper provides another sufficient condition besides NTK to ensure geometric convergence of deep learning.", "summary_of_the_review": "This is seemingly a good paper, but too heavy to review for a ML conference with so short review periods. Hence, you should not consider my recommendation as meaningful.", "strength_and_weaknesses": "The paper provides a good litterature review. It is well written and easy to follow. However, it is a dense paper with lots of theoretical proof to check. The ICLR review period is too short to allow a careful theoretical review. It would be better as a journal paper.\n\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DLQA-AiKFN", "reviewer": "Reviewer_GhrZ", "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": "", "summary_of_the_paper": "This paper analyzes the convergence of gradient descent on overparameterized neural networks with smooth activation functions. The authors show that the Hessian of the neural network has a small spectral norm within a special ball of the initialization, and this ball is allowed to be significantly larger than those allowed by prior works, such as those that use the NTK framework. \n\nThe authors then show that the square loss is strongly convex within a restricted set around the initialization (under certain assumptions). This along with the spectral norm bound (which implies smoothness for the loss function) gives a geometric convergence rate for gradient descent.", "summary_of_the_review": "This result gives a poly-time (almost) geometric convergence for gradient descent on deep neural nets with smooth activations, and does not rely on the NTK framework.\n\nThe reasons for my score are:\n1. the GD iterates are allowed to lie in a significantly larger set than prior work.\n2. the paper has the added benefit that it closely resembles empirical observations -- it is well known that Hessians of neural nets have many directions in which the eigenvalues are zero, and the use of RSC implies that these directions can be accounted for.\n3. the analysis is much sharper than prior work in Liu et al, and obtains poly factors wherever prior work obtains exponential factors.", "strength_and_weaknesses": "_Strengths_:\n- This paper considerably improves the results in Liu et. al. with polynomial factors wherever the prior work had exponential factors.\n\n- The use of RSC matches empirical observations that the Hessian of neural networks have many flat directions with eigenvalues $=0$.\n\n- The gradient descent iterates are allowed to be in a much larger ball when compared to prior work.\n\n_Weaknesses_:\n- The flow of the paper is a little confusing. The authors first show an upper bound on the spectral norm of the Hessian (in an appropriate ball around the initialization), and then in the second paragraph of page 2, say that this will be used to show Restricted Strong Convexity. This doesn't make much sense when phrased this way, since RSC would require a lower bound on the smallest eigenvalue of the Hessian within the restricted set. My understanding of the paper is that the Hessian spectral bound has nothing to do with RSC, and is instead used for showing smoothness of the loss function, as in Theorem 5.2. \n\n- In Theorem 4.1, the role of $\\sigma_1$ is not clear. What stops you from choosing an extremely small $\\sigma_1$? It seems like this would give a good value for $\\gamma$. Assumption 2 requires it to bounded away from 0, but its significance in Theorem 4.1 is unclear.\n\n- I'm a little concerned about the connections between the Lipschitz properties of the network (via the Lipschitz activations in Assumption 1) and the Restricted Strong Convexity properties. These two are conflicting properties, and the choice of $\\rho, \\rho_1$ would dictate whether the Lipschitz bound in Assumption 1 can be satisfied. Any clarification on this point would be appreciated.\n\n- The geometric convergence in Theorem 5.3 should also come with the disclaimer that the loss cannot be made arbitrarily small. In order for A4.1 to hold, the average gradient needs to be sufficiently large, which implies that the algorithm cannot be arbitrarily close to the minimum (in which case the gradient would be arbitrarily close to zero). THis would also contradict the claim in Remark 5.4, where the authors say that there exist parameters that can drive the loss to an arbitrary $\\epsilon$.\n\n- Assumption A4.1 should appear before Theorem 5.1. Currently it is buried in the last sentence of Theorem 5.1.\n\n_Clarifications_:\n\n- This is not a complaint, but perhaps the choice of $\\sigma_0$ can be compared with common initialization schemes, such as, Xavier initialization.\n\n- The line below Assumption 3 says that cross-entropy is strongly convex. Is this true? (the loss in logistic regression for e.g. is certainly not strongly convex) If your results in Theorem 5.1 are for the square loss, why mention cross-entropy at all?\n\n_Minor comments_:\n- Para above lemma 4.1; \"to established\" -> \"to establish\"", "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": "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": "BHunqILRWE", "reviewer": "Reviewer_Qo6j", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "In the paper, the authors analyze the convergence of gradient descent (GD) on training a deep learning model with smooth activation function. The paper is presented for fully connected neural network with linear last layer, output dimension of 1, and equal layer width for all layers. Under reasonable assumptions on the loss function, activation function, randomness of the initialization, etc., the authors show that GD will converge (geometrically) to the minimizer in the neighborhood around the initialization. The analysis establishes an upper bound on the Hessian of the loss function in the neighborhood and then using Restricted Strong Convexity of the loss function to argue for convergence to the minimizer. The approach for showing convergence differs from NTK approaches which are generally restricted to wide networks.\n", "summary_of_the_review": "The stated problem is interesting and the authors provide an insight on the behavior of gradient descent for neural networks without large width. Overall, the paper is easy to read but contains some unclear parts.", "strength_and_weaknesses": "Overall the paper provides a new approach to analyze the behavior of gradient descent when training deep learning models. Below I highlight my concerns and include some minor comments.\n\n**Weakness**\n\n-  The analysis presented is for NN with same width for all layers and with the output dimension of 1. The authors point to another paper for extension to multidimensional output. It would be beneficial to provide a remark, at the least, on the central steps required for extending the result. \n-  Another restriction to the network is the activation function. Does the analysis extend to networks with smooth activation in last layer? Does it extend to non-smooth activation function?\n- In my understanding, the result presented is for convergence to a neighborhood near the initialization. The main point made in the paper is that the networks does not have to be as wide for convergence to hold, unlike for NTK approaches. A comparison between the two methods on the required width size is missing. \n- The experimental result presented is very limited. Following the results presented in the paper, the average gradient satisfies $\\bar{g}_t = \\Omega(\\frac{L}{\\sqrt{m}})$. However, figure 1b shows that the norm of the average gradient grows with network width. What accounts for this difference in theoretical vs experimental results.\n- In the abstract, the authors state \"...norm of the Hessian of such models...\". This should be reworded to indicate that Hessian is of the loss function.\n- In page 2, the authors state the set $Q_k^t$ without an explanation of what the set is (or referencing to where it is defined).\n- In assumption 2, the initialization for $v_0$ is stated in a roundabout way. I believe it is simply sampled uniformly at random from a unit sphere.\n- In Theorem 4.1, the bound on the maximum of the Hessian should either depend on $n$ or the bound holds for all $x_i$. This should be made clear.\n- In Definition 5.2, missing inner product in $\\cos(\\theta -\\theta_t, \\bar{g}_t)$.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1qI2B6ZqAG-", "reviewer": "Reviewer_oVua", "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": "", "summary_of_the_paper": "The paper makes two contributions for single-output deep learning models with smooth activations:\n1) Upper bounds the spectral norm of the model's Hessian over a layer-wise spectral norm, which is larger than the euclidean ball that was studied in previous work. Hence, the result holds with relaxed conditions on how close it is to initialization.\n2) proves a restricted strong convexity property along the path of GD iterates that avoid directions orthogonal to the average gradient and that stay close to initialization with respect to the layer-wise spectral norm.\n\n", "summary_of_the_review": "Disclaimer: I am not super familiar with the details of some of the closely related works, but the authors appear to have done a good job in comparing their results to them and clarifying the novelties in a way that is convincing. Also, given the reviewing load, I was unable to go through the proofs. Because of these hesitations, I recommend 'marginal accept' for now, but I am willing to improve my score further down in the discussion period.", "strength_and_weaknesses": "Strengths:\n\n- The paper is generally well-written. The authors make particular effort to make the presentation less 'dry' with several remarks on intuitions and interpretations of their results\n- The contributions are made clear and it is clarified what the novelties are compared to previous works\n- Thm 1 improves on a previous result by (Liu et al.)\n- Thm 5.2 provides an alternative a criterion for linear convergence that is different compared to the now common uniform minimum eigenvalue bound of the NTK\n\nWeaknesses: \n\n- The two contributions of the paper are not well connected. Have I missed something on this? Perhaps the authors can clarify how the content of Sec. 4 informs that of Sec. 5\n- How is Lemma 5.1 different from what is already shown in Karimi et al. that RSC=>RPL other than here you are talking about restricted PL?\n- The result on RSC requires (essentially) two assumptions. \n(a)The first is that GD travels a path in which iterates are not orthogonal to the average gradient. While it is mentioned, that this is something observed in practice, no further evidence is given. Also, it would be useful to add some intuition on why this is needed. \n(b) The second needed condition is that the squared norm of the average gradient is greater than c/\\sqrt{m}, where m is the network's width. Remark 5.5 is nice, but it would strengthen the argument if the authors could show an example of concrete architecture where (20) holds but (19) does not.\n- In Remark 5.6 they authors mention: \"our perspective is to view the NTK and RSC as two different sufficient conditions ...\". This remark is somewhat contradictory to the flavor of comment in the rest of the paper, e.g. Remark 5.5 also earlier that the layer-wise spectral ball does not require to be in NTK regime\n- In the experiments: what does it mean, step-size is chosen appropriately to keep training in NTK regimes?\n- minor: above Thm 1, cross-entropy is not strongly convex\n\n\n\n\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster