Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
Authors: Spencer Frei
Quanquan Gu
Venue: NeurIPS 2021 Poster (2021)
Keywords: nonconvex optimization
deep learning
neural networks
gradient descent

Abstract: Although the optimization objectives for learning neural networks are highly non-convex, gradient-based methods have been wildly successful at learning neural networks in practice. This juxtaposition has led to a number of recent studies on provable guarantees for neural networks trained by gradient descent. Unfortunately, the techniques in these works are often highly specific to the particular setup in each problem, making it difficult to generalize across different settings. To address this drawback in the literature, we propose a unified non-convex optimization framework for the analysis of neural network training. We introduce the notions of proxy convexity and proxy Polyak-Lojasiewicz (PL) inequalities, which are satisfied if the original objective function induces a proxy objective function that is implicitly minimized when using gradient methods. We show that stochastic gradient descent (SGD) on objectives satisfying proxy convexity or the proxy PL inequality leads to efficient guarantees for proxy objective functions. We further show that many existing guarantees for neural networks trained by gradient descent can be unified through proxy convexity and proxy PL inequalities. 

Proxy Convexity; A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
Spencer Frei
Quanquan Gu Department of Computer Science University of California, Los Angeles gguccs. ucla.edu
Simons Institute for the Theory of Computing University of California, Berkeley frei frei@berkeley. edu
Abstract
Although the optimization objectives for learning neural networks are highly non- convex, gradient-based based methods have been wildly successful at learning neural networks in practice. This juxtaposition has led to a number of recent studies on provable guarantees for neural networks trained by gradient descent. Unfortunately, the techniques in these works are often highly specific to the particular setup each problem, making it difficult to generalize across different settings. To address this drawback in the literature, we propose a unified non-convex optimization framework for the analysis of neural network training. We introduce the notions proxy convexity and proxy Lojasik-ojsiiiiizz (PL) inequalities, which are satisfied if the original objective function induces proxy objective function that is implicitly minimized when using gradient methods. We show that stochastic gradient descent (SGD) on objectives satisfying proxy convexity the proxy PL inequality leads to efficient guarantees for proxy objective functions. We further show that many existing guarantees for neural networks trained by gradient descent can be unified through proxy convexity and proxy PL inequalities.
Introduction
Understanding the ability of gradient-based stochastic optimization algorithms find good minima of non-convex objective functions has become an especially important problem due to the success of stochastic gradient descent (SGD) in learning deep neural networks. Although there exist non-convex objective functions and domains for which SGD will necessarily lead to sub-optimal local minima, it appears that for many problems of interest in deep learning, across domains varied as natural language and images, these worst-case situations do not arise. Indeed, a number of recent works have developed provable guarantees for GD and SGD when used for objective functions defined in terms of neural networks over certain distributions, despite the non-convexity of the underlying optimization problem [5, 3, 6, 22, 14, 16). To date, however, there has not been framework which could unify the variegated approaches for guarantees in these settings.
In this work, we introduce the notion of proxy convexity and demonstrate that many existing provable guarantees for learning with neural networks trained by gradient-bart optimization fall into a problem satisfying proxy convexity. First, let define the learning problem over a distribution D, where the goal is to minimize the expected loss
min F(w) := E,nDf(u;2), weW
(1.1)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

where W is parameter domain and f(:;2) 2) is a loss function. We are interested in guarantees using the online SGD algorithm, which uses a set of i.i.d. samples 2t i.dd. D and has updates given by
Wr++1 Wi 1/ (W+;;)))))
where 1) > 0 is fixed learning rate. We now introduce the first notion of proxy convexity we will consider in the paper.
Definition 1.1 (Proxy convexity). We say that function f RP - R satisfies (g, proox comvexity there exist functions g, IP" E. such that for all w, v E IR,,
(VI(w), w - v) 2 g(w) - h(v).
Clearly, every convex function f satisfies (f. --rooy convexity. We next introduce the analogy of proxy convexity for the Dolyak-Lojasiewierr (PL) inequality [23].
Definition 1.2 (g-proxy, E-optimal PL inequality). We say that a function f f: RR" R satisfies g-proxy, ξ-optimal satisfies the (g,S, a. pu-PL. inequality) if there exists a function g = IRP" -> R and scalars & E IR, >> 0 such that for all E RP
Lojaseeojiiiiwccz inequality with parameters E (0,2) and μ > O (in short,
V 2 2" (g(we) - -)
As we shall see below, the proxy PL inequality is a natural extension of the standard PL inequality. Our main contributions are follows.
When f satisfies (g. h) -p-xx convexity, and is either Lipschitz or satisfies a particular smooth- ness assumption, then for any norm bound R >> 0, the online SGD algorithm run for polynomial (in 1/s and R) number of iterations satisfies the following in expectation over 21..... .......2. 2T ~ DT
min E (p)(;; K<T
min EE=Dl((;; =) + ||
When f satisfies a (g. a, prpproxy PL inequality and has Lipschitz gradients, SGD run for polynomial (in 1/e) number of iterations satisfies the following in expectation over . ......... 2T DJ.
min Ez-dg(wn =) $ <<
& +
We demonstrate that many previous guarantees for neural networks trained by gradient descent can be unified in the framework of proxy convexity.
As we will describe in more detail below, if a loss function is (g. --roxy convex or satisfies g-proxy PL inequality, then the optimization problem is straightforward and the crux of the problem then becomes connecting guarantees for the proxy g with approximate guarantees for f.
Notation. We use uppercase letters to refer to matrices, and lowercase letters will either refer to vectors or scalars depending on the context. For vectors w, we use ||w|] refer to the Euclidean norm, and for matrices W we use |[W]] to refer to the Frobenius norm. We use the standard (-), ((-) notations to hide universal constants, with Ö(-) and (i(-) additionally hiding logarithmic factors.
2 Proxy Convexity in Comparison to Other Non-convex Optimization Frameworks
In this section, we describe how proxy convexity and proxy PL-inequalities relate to other notions in non-convex optimization. In Section 6, will discuss additional related work. First, recall that function f is (g, -proxy convex if there exist functions and h such that for all w,
(V f(w), w v) 2 g(w) - h(v).
One notion from the non-convex optimization literature that is related to our notion of proxy convexity that of invexity [19]. function f is invex if differentiable and there exists a vector-valued function k(w, v) such that for any c,
(V f(w), k(w, v)) 2 f(w) f(v).
2

---

It has been shown that a smooth function f is invex if and only if every stationary point of f is global minimum [10]. However, for many problems interest involving neural networks, is not the case that every stationary point will be a global optimum, which makes invexity a less appealing framework for understanding neural networks. Indeed, we shall see in Example 4.2 below that one considers the problem of learning single ReLU neuron 2: H> max(0, (w,x)) under the squared loss, it is not hard to see that there exist stationary points which are not global minima (e.g. w = O assuming the convention o' (0) 0). By contrast, we shall see that the single ReLU neuron does satisfy a form of proxy convexity that enables SGD to find approximately (but not globally) optimal minima. Thus even the simplest neural networks induce objective functions which are proxy convex and non-invex. We shall see in Example 3.3 that proxy convexity appears in the objective functions induced by wide and deep neural networks well.
To understand how the proxy PI. inequality compares to other notions in the optimization literature, recall that an objective function f satisfies the standard PL. inequality [33, 27] if there exists fa > 0 such that
" [f(w)- - f*] Yw. Vf N 2
where f = min (w). Clearly, any stationary point of an objective satisfying the standard PL inequality is globally optimal. Thus, the presence of local minima among stationary points in neural network objectives makes the standard PL inequality suffer from the same drawbacks that invexity does for understanding neural networks trained by gradient descent. This further applies to any of the conditions which are known to imply the PL inequality, like weak strong convexity, the restricted secant inequality, and the error bound condition (Karimi et al. [23]).
In comparison, the (g. E, a, pproxy PL incquality is satisfied if there exists a function g and constants { >> 0, (0,2] and μ 0 such that
1 [o(w)) [ =
- Vw.
It is clear that if function f satisfies the standard PL inequality, then it satisfies the (f, 2, p)) proxy PL inequality. Stationary points wi of objective functions satisfying the proxy PL inequality have [VV[(wn) = which imply g(wn) S E. In the case that g [. the slack error term & allows for the proxy PL inequality framework to accommodate the possibility that stationary points may not be globally optimal (i.e. have objective value f min f(w)), ). but could be approximately optimal by, for example, having objective value at most { = C- f or & = C' vf" for some constant C' 2 1. When g * f. the proxy PL inequality allows for the possibility of analyzing proxy loss function g which is implicitly minimized when using gradient-basee optimization of the objective f.
At high level, proxy convexity and the proxy PL inequality well-suited to situations where stationary points may not be globally optimal, but may be approximately optimal with respect to a related optimization objective. The proxy convexity framework allows for one to realize this through developing problem-specific analyses that connect the proxy objective g to the original objective s. As we shall see below, rich function classes like neural networks are often more easily analyzed by considering a proxy objective function that naturally appears when one analyzes the gradient of the loss.
Finally, we note that [25] introduced a different generalization of the PL incquality, namely the PL and PL inequality, which relaxes the standard PL inequality definition so that the PL condition only needs to hold on a subset of the domain. In particular, a function f : R -> IR satisfies the PL inequality set S C R" if there exists μ > 0 such that
[[V((w)] 2 #f(w) Ve E S.
Likewise, ʃ satisfies the PL, inequality S if there exists a set S and E 2 such that the PL inequality holds on the set Se = {w E S : f(w) 2 E}. One can see that if f satisfies the PL; inequality on S, then the function g(w) == f(w) + e satisfies the g-proxy, e-optimal PL inequality on S.
We wish to emphasize the differences in the framing and motivation of the PL inequality by [25] and that of proxy convexity and the proxy PL inequality in this paper. [25] focus on the geometry of
Karimi et al. [23] shows that these conditions imply the PL inequality under the assumption that the objective function has Lipschitz-continn gradients.
3

---

optimization in the overparameterized setting where one has fixed set of samples ((z,, 34) p))3- and a parametric model class g(z; w) (for w E R", p > n) and the goal is to solve g( w) = ys for all i E [n]] In this setting one can view the optimization problem as a nonlinear least squares system with p unknowns and n equations, and [25] use geometric arguments to show that when p > n the PL." condition is satisfied throughout most of the domain. They extend the PI." condition to the PI. condition with the motivation that in underparameterized settings, or when performing early stopping. there may not exist interpolating solutions. By contrast, we focus on the stochastic optimization setting, where the goal is to minimize the expected loss over some distribution; is unclear how geometric arguments for minimizing the training loss can lead generalization guarantees in the overparameterized setting, especially when considering online SGD where samples are observed one-by-one and "overparameetriizatonn has a less clear meaning. Furthermore, in this work we not primarily interested in understanding how overparamettrivattoon affects optimization. Rather, our aim is to develop framework that allows for formal characterizations of optimization problems where stationary points are not globally optimal with respect to the original objective but are approximately optimal with respect proxy objective functions. We will demonstrate below that such framework can help unify number of works on learning with neural networks trained by gradient descent.
3 Proxy PL Inequality Implies Proxy Objective Guarantees
In this section, we show that for loss functions satisfying a proxy PL inequality, SGD2 efficiently minimizes the proxy. We leave the proofs for Section 5.
Theorem 3.1. Suppose F(w)= = Ez-DJ (w; 2) where f(-; satisfies the
[()), a, p))proxy
PL inequality for some function g(- ;2) R - R. for each z. Denote by G(w) = Eg (w; 2).
Assume that f is non-negative and has Lz-Lipschitz gradients. Then for any & > 0, provided n L22 online SGD with fixed step size v) and run for T = 2n 1 (ns/2 -2/a [(wo; zo) iterations results in the following guarantee in expectation over 20, , 21 D²
min G(w,, S BE)DE(2) + E. <<
(3.1)
To get a feel for how a proxy PL inequality might be useful for learning neural networks, consider classification problem with labels y {=1}, and suppose that ;(); is neural network function. A standard approach for learning neural networks is to minimize the cross-entropy loss Nyy (W; z)) log( (1 + (M: using gradient descent. Using the variational form of the norm, we have
[V sup (V())N(W:2)).
||||||
2 (((N(WW;))) (VVN(W;,).V)
(3.2)
where V is any matrix satisfying ||V]| = 1. Now, although the function - is not an upper bound for l (indeed, -f' < (), it is upper bound for constant multiple of the zero-one loss, and can thus serve as a proxy for the classification error." 3 This is because for convex and decreasing losses é, the function -f' is non-negative and decreasing, and hence by Markov's inequality,
IPu # (N x))) P(y N(W; a:) < 0) -P (yN x)) > (()))
R = ((NN(W:))))
S (0(
Thus, if one can bound the population risk under -L,, one has a bound for the classification error. Indeed, this property has been used in a number of recent works on neural networks [6, 13, 22, 16). This lets the -l' term in (3.2) represent the desired proxy g in the definition of the (g: E, or, p))-roxy PL inequality. Thus, for neural network classification problems, the problem of showing the neural network has small classification error is reduced to constructing a matrix V that allows for the quantity (WVN(W: +); V) to be large and non-negative. The quantity (VNNNN (W; 2z), V) can be thought of
2 We focus on online SGD in this paper for simplicity. Analogous optimization guarantees would hold for other variants of gradient descent that utilize samples in batches.
In fact, the function z + (2), is also proxy for the classification error; see [15, Appendix AJ.

---

as a margin function that is large when the gradient of the neural network loss points in a good direction. Although we shall see below that in some instances one can derive lower bound for (W; V' that holds for all W, I, and y. more general approach would be to show that along the gradient descent trajectory W(t), a lower bound for v(VN ;,) holds.*
In the remainder of this section, we will show that number of recent works on learning neural networks with gradient descent utilized proxy PL inequalities. In our first example, we consider recent work by Charles and Papailiopoulos [7] that directly used (standard) PL inequality.
Example 3.2 (Standard PL inequality for single leaky ReLU neurons and deep linear networks). Charles and Papalliopoulos [7] showed that the standard PL inequality holds in two distinct settings. The first is that of single leaky ReLU neuron + a(w,, x))), where o (=) max z) for Co # O. They showed that if Smin (X) is the smallest singular value of the matrix X R of n samples, then for a A-strongly convex loss f. the loss f(w) E(o ((w((w)))) satisfies the standard μ-PL inequality, i.c., the (f. fr 2, -ppoyy PL inequality for = Asmin Asmin(X) 2 (Charles and Papalliopoulos [7, Theorem 4.1)).
The same authors also showed that under certain conditions the standard PL inequality holds when the neural network takes the form N(W;z) W.. w, and the loss is the squared loss, f(W) = 1/2(y ;(W; In particular, they showed that if 8min (W;) 2 > 0 throughout the gradient descent trajectory, then f satisfies the standard p-PL. inequality for == = L, // |[XXXX)-XXX] (Charles and Papailiopoulos [7, Theorem 4.5)).
The standard PL inequality has been used by number of other authors in the deep learning theory literature, see e.g. Xie et al. [36, Theorem IJ, Hardt and Ma [20, Eq. 2.3], Zhou and Liang [40, Theorem 1]. Shamir [35, Theorem 3].
In our next example, we show that proxy PL inequality holds for deep neural networks in the neural tangent kernel (NTK) regime.
Example 3.3 (Proxy PL inequality for deep neural networks in NTK regime). Consider the class of deep, L-hidden-layee layer ReLU networks, either with without residual connections:
(W:;) = (W))),) N((W; = N + or NN 1= 2...., L,
m
N(W;x) = Σ a (W:N)=
where 81 = for fully-connected networks and 81 = for residual networks. Cao and Gu [6, Theorem 4.2], Frei, Cao, and Gu [13, Lemma 4.3), and Zou et al. [41, Lemma B.5] have shown that under certain distributional assumptions and provided the iterates of gradient descent stay close to their intialization, one can guarantee that for the cross-entropy loss f(W; (xx v)) = ((yN(W; (W;
(VW v)>1 2 Ci (()))(W;:))
(3.3)
By defining (W; = - (W;:(:)))) the loss of satisfies the (g. 0, (.1,2C1)-pron PL inequality. Since the ReLU is not smooth. the loss f will not have Lipsehitz gradients, and thus a direct application of Theorem 3.1 is not possible. Instead, the authors show that in the NTK regime, the loss obeys type of semi-smoothness that still allows for an analysis simliar that of Theorem 3.1.
Example 3.4 (Proxy PL inequality for one mee-hidden-lan layer networks outside NTK regime). Consider a one-hidden-layer network with activation function a.
m
N(W; (I, = Σ azo ((w,)))))))
(3.4)
where the second layer weights {a are randomly initialized and fixed at initialization, but the (w,
ym 1-=1 are trained. Assume a satisfies o' o'(2) 2 co 0 for all 2 (e.g.. the leaky ReLU activation). Frei, Cao, and Gu have shown [16, Lemma 3.1] that there exists matrix V E Raxd with [ = such that for distributions satisfying anti-concentrattin, for any x, y and W.
V (WW x), V) 2 Ci(co E(x, v)].
Although our results as stated would not immediately apply in this setting, the proof would be the same up trivial modifications.
5

---

where E[E(2, O(VOPT where OPT is the best classification error achieved by halfspace over Thus, when f(W: (z. y)) = ((yN (x, y)) is the cross-entropy loss,
V |
sup (Vf(W; (x,y)), 2)
2 -y((NN(W:)) V(VN(W:=).
2 Cicr (- -6
-(()))(W;z)), the loss f satisfies the (g, (, y), 1, 20 --roxxy PL inequality. Thus, provided
As Example 3.3, by defining g(W:2)
show that f(;==) has L2-
Lipschitz gradients for some constant L2 > 0, Theorem 3.1 shows that
E DI
((.) (gg K
I min KCT
[e((0)
S 2C2c 'E ((a +
=(VOPT)) +
Provided a is such that continuous and differentiable, then f has Lz-Lipschitz gradients and thus the guarantees will follow. In particular, this analysis follows if a is any smoothed approximation to the leaky ReLU which satisfies d'(z) 2 Co > 0.
Note that the above optimization analysis is an original contribution of this work we utilize completely different proof technique than that of [16]. In that paper, the authors utilize Perceptron- style proof technique that analyzes the correlation (W(#), V\ of the weights found by gradient descent and reference matrix V. Their proof relies crucially on the homogeneity of the (non-smooth) leaky ReLU activation, namely that (z) (=)) for z E I, and cannot accommodate more general smooth activations. By contrast, the proxy PL inequality proof technique in this example relies upon the smoothness of the activation function and more similar to smoothness beaeeeeess---eddddddd analyses of gradient descent.
4 Proxy Convexity Implies Proxy Objective Guarantees
In this section, show that f satisfies (g, h)-proxy convexity, we can guarantee that by minimizing with gradient descent, we find hypothesis for which ((w) is at least as small as the best norm- bounded predictor as measured by the loss h. We present two versions of our result: one that relies upon fewer assumptions on the loss f but needs small step size, and another that requires proxy smoothness assumption on f but allows for a constant step size. The proofs for the theorem are given in Section 5.
Theorem 4.1. Suppose that F(w) == REZD (wr; 2) and [1:; z) is (g(: 2), h[: =)) convex for each Denote H(w) = (1ewDh((;22 and G(w) = By~Do( ();
(a) Assume there exists L1 > 0 such that for all w, EE-DlIlSSus 2)]l"] S LT Then for any v E Re and any 8 > O, performing online SGD on F(w) from an arbitrary initialization wo with fixed step size I cI for T =n = I|w e1 iterations implies that, in expectation over 21.,2T-1 .0.....,T-- ~ DT,
min G(wi) S H(v) t t<T
(b) Assume there exists L2 > such that for all w, Eg= V [WW; < 222E2=D0(w; z). Then for any v E Ro and any E > performing online SGD on F(w) from an arbitrary initialization with fixed step size 1 < 1 /2 for T = . - l|wo 21 implies that, in expectation over (2o...., 211) DT
min G(w,) S (1 2mL (2)) +E. t<T
In order for (g. h>-proxy convexity to be useful, there must be way to relate guarantees for into guarantees for desired objective function f. In the remainder of this section, we will discuss two neural network learning problems which are non-convex and yet satisfy proxy convexity which leads to generalization guarantees. Our first example is the problem of learning a neural network with single nonlinear unit.

---

Example 4.2 (Single neuron satisfies proxy convexity). Consider the problem of learning a single neuron z H> a(w,, under the squared loss, where the ReLU activation. The objective function of interest is
F(w) ((xx))D\//((((( x)) y)²
Denote
min F(w). |
It is known that F is non-convex [37]. Under the assumption that learning sparse parities with noise is computationally hard, is known that no polynomial time algorithm can achieve risk F* exactly; moreover, it is known that (unconditionally)) the standard gradient descent algorithm cannot achieve risk F* [18]. However, Frei, Cao, and Gu [14] showed that although F' is non-convex and no algorithm can achieve risk F", F' does satisfy form of proxy convexity that allows for gradient descent to achieve risk O OVTT). They showed that the loss function
f(w; v)) 1/2(o((w,, 2)) - y)²
satisfies (g. h)) -proxy convexity, where
g(u; (z, y)) 2 20 -((u) ; x))1
of ((w,z)),
h(u; v)) = (o((w, - yl = / 2f; v),
where o" is the population risk minimizer of F(w) (see their Eq. (3.13)). Moreover, they showed (see their Eq. (3.9)
[V: 2) I 8g(w; 2).
Thus Theorem 4. L(b) implies that SGD with step size 17 S 1/8 and T -n- l|wo v=11 iterations will find a point wA satisfying
G(wr)= = 2T (2.)) (o((w), x)) o(lo" ,))))² ((10,,)))
< (1 + Sn) H(v") +
I (1+ + B/o 22)) - yl +e
< (1 + 8n) v Bl(o((v', ,x)) y) +e
O(VF')
The authors then show that under some distributional assumptions on D, G(w)) O(VF)) implies F(w)) = O(VF*) [14, Lemma 3.5]. Thus, the optimization problem for F induces proxy convex optimization problem defined in terms of G' which yields guarantees for G in terms H, and this in turn leads to approximate optimality guarantees for the original objective F.
In our next example, show that a number of works learning one-hidden-layer ReLU networks in the neural tangent kernel regime [21] can be cast as problems satisfying proxy convexity. Example 4.3 (Proxy convexity for see-hidden-llyeee ReL.U neural networks in the NTK regime). Consider the class of me-hidden-llayr ReLU networks consisting of m neurons,
N(W; (z, 9) Σ a,
where the {ag) are randomly initialized and fixed at initialization, but the {wy} are trained. Suppose consider binary classification problem, where y E (+11 and minimize the cross- entropy loss,
F(W)- = ED f(W: (z, v)), f(W; (z, v)) (yNNWW; (z, r))), {(x) = log log(1+exp(-2))
Ji and Telgarsky [22, Proof of Lemma 2.6] showed that there exists a function h(a W, V; (x. such that the iterates of gradient descent satisfy
(V (WWW; (z, v)), v) Z f(W; (z, v)) M(a, W, (x,
'This stands in contrast to learning single leaky ReLU neuron æ + max(ax, æ) for a a 0, which as we showed in Example 3.2 can be solved using much simpler techniques.
7

---

Under the assumption that the iterates of gradient descent stay close to the initialization (i.e., the neural tangent kernel regime), they show that h(a, W, V; (I. v)) S under distributional assumptions, and thus (ww) will satisfy (J. h = e) -rp-oxyy convexity. The cross entropy loss satisfies [=) < ((z),
and thus we can apply Theorem (b) to get guarantees of the form minker F(w)) E for the cross-entropy loss ((W) of SGD-trained neural networks in the NTK regime.
In another problem of learning mee-iddeen-ayye -aaee networks, Allen-Zhu, Li, and Liang [3. Proof of Lemma B.4] show that there exists proxy loss function g(a, W; (z. y)) such that provided the
neural network weights stay close to their initialized values, f(a, W; (x. y)) satisfies (g: 9 + +) proxy
convexity. Again using that the cross- cross-entropy loss satisfies [=)( I {(2). Theorem 4b1 shows
that SGD-trained neural networks the NTK regime satisfy milker G(W)) S miny G(V) + E. They further show that the proxy loss is close to the cross entropy loss, i.e. [B[g(a, W; (x, v)) [a W; (x, u))ll S E, implying a bound the form minkeT F(W,) S miny F(V) +
Proof of the Main Results
In this section provide the proofs of the theorems given in Sections and 4.
We first give the proof of Theorem 3.1 which provides guarantees for learning with objectives satisfying proxy PI. inequalities.
Proof of Theorem 3.1. Since f has Lz-Lipschitz gradients, we have for any w, w/ and fixed z,
La w| - w'1l?
f(w; 2) S f(w':2) + (Vf(w':2) w') + 2
Taking w1+1, w/ w4, and 2th
[(w4+1:)) S [(w); 1 [ (w);))))))))) 1/² L2
| [
2
= =[ww; - n/2 (w]; 21) =
(5.1)
Since < 1/L2, we have (1 - -122/22 - 2, and thus we can rearrange the above to get
[V/[(; 2111
11 - n22/22 [swe 24) - f f((++1;+))
2
< [ww 2,) f( =0]]
(5.2)
Summing the above from 0 = and using that f is non-negative, we get
T-1
f(w;,2))² 2f(wn: 20)
1/
Using the definition of proxy PL inequality, this implies
1 T Σ (p/2) (g(w;; {(z)))2 < 2f(wo; zo)
1/T
Taking the minimum over / T and re-arranging terms, this means
min min(g(w;;2) 2,) -((2))) < 2f(wo: 20) t
(T/22/22//
Therefore, we have
2 2f (wo: 20) μ
a/2
min g(we: =x) < E(ze) +
E<T
nT
Taking T = 2n 20) (us (2) 2/c -2)- and taking expectations over #0,..., 2T we get (3.1).
We next prove guarantees for SGD when the objective satisfies proxy convexity.

---

Proof of Theorem 4.1. By the definition of proxy convexity,
||w rl| |100 ull² 2n V (WW we v) ,/² V (w:: [+)=
2 2n)g( 24) - h(v; 24] - n/ I [
Conditional on the values of 20..... 2t-1 (and hence on the value of wy). taking expectations of both sides with respect to ~ DD results in
||w ell EZ,DD ||0++1 u|12 > 2n(G(wa) H(v)] T)²E [f( For case (a), this results in
(5.3)
l| u|| E ENDDD || u1| 2 2n(G((r) - H(u) n/2L
Dividing both sides by 2n/l' and summing from & = O,.... T - 1, we get
Σ
G(wn)=
1 T
Σ
H(v) +
nLi
2 +
11:00 - ril2 -ETTIND 1205y - el1
T 1=
2n/T
1=
Taking expectations over 20:t = (z0,...,
21-1 1-1
D'. we get
nL4
| w1
min E =o D D. G(w,) S
E Bso ~ G( S H(v) +
KT
T
2
2ny7
In particular, for 1) S = and T 1
|w/ ull2 we get
min E 2D G(w)) - H(v) +E.
KT
For case (b), (5.3) becomes
w u1l? - EaND |10141 - u11 27|G(ww)) - - G(w,)
2n (1 - (L,)) H(v))
Dividing both sides by 21)T(1 - [2)) and summing from t= .,.... ,
T - 1, we get
G(w)) s 1_ H(D) |w u1( E EID |WT- u11
1
T 1=
2n 11112)
(1+ + (1 + 2m)2) 11000 111
2T/T
where in the last line we have used that S T. /2 and that 1/(1 - S + 2x on 1/2]. Taking expectations over 20.t (20, ......., 2(-1) Dt. we get
T-1
min KT
Dr G(w)) S T
Bes Di G(we)
2 2|(w0 ml
(1 + 22 (())
2//T
In particular, for T === oo 1w0 - 0|| we get
min E EDo Gi(w:) S (1 22L2)) te. KT
We note that under additional assumptions D and the loss function, we could improve the results from holding in expectation over the draws of the sample to high probability guarantees by using standard concentration arguments. This easily done when the objective function satisfies proxy convexity: we can make a slight modification to the proof of Theorem 4.1 to argue inductively that
until we reach point with G(wz) < H(v) + L i +E, we have that that ||, - -||2-||[+++ - oll 2 E. This implies that the norm of the predictors remain bounded throughout the trajectory gradient descent until we reach the desired point with G(w,) < Hw)) + n + e, which can then be used in Rademacher complexity-tyee arguments [4]. This type of argument was previously used by e.g., Frei et al. [14].

---

Additional Related Work
The Polyak-Lon Lojassewwzz inequality can be dated back to the original works Polyak [33] and Lo- jasiewicz [27]. Recent work by Karimi et al. [23] proved linear convergence under the PL condition and showed that the PL condition is one the weakest assumptions under which linear convergence is possible. In particular, they showed that the error bound inequality [28], essential strong convex- ity [26], weak strong convexity [31], and the restricted secant inequality [38] are all assumptions under which linear convergence is possible and that each of these assumptions implies the PL inequality.
As we described in Section 2, the standard PL. condition was shown to hold under certain assumptions for neural network objective functions [20, 36, 40, 7]. In addition to those covered in this paper, there are a number of other provable guarantees for generalization of SGD-trained networks which rely on variety of different techniques, such tensor methods [24] and utilizing connections with partial differential equations by way of mean field approximations [29, 9, 30, 8].
In the optimization literature, recent work has shown that SGD can efficiently find stationary points and can escape saddle points [17, 12]. As the proxy PL inequality implies guarantees for the proxy objective function at stationary points of the original optimization objective, our framework can naturally be used for other optimization algorithms that are known to efficiently find stationary points, such as SVRG [2, 34), Natasha2 [1], SARAH/SPIDER [32, 11], and SNVRG [39].
7 Conclusion
In this paper we have introduced the notion of proxy convexity and proxy PL inequality and developed guarantees for learning with stochastic gradient descent under these conditions. We demonstrated that many recent works in the learning of neural networks with gradient descent can be framed in terms of optimization problems that satisfy either proxy convexity or a proxy PL inequality. While the proxy convexity framework cannot unify all existing analyses of learning neural networks, hope that it can reveal some of the principles underlying the success of SGD-trained neural networks.
Acknowledgments and Disclosure of Funding
QG is partially supported by the National Science Foundation CAREER Award 1906169, IIS- 1855099 and IIS-2008981. SF acknowledges the support of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-200 1883 and #814 1884939. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
[1] Z. Allen-Zhu. Natasha 2: Information Processing Systems (NeurIPS), 2018
Faster non-convex optimization than sgd. In Advances in Neural
[2] Z. Allen-Zhu and E. Hazan. Variance reduction for faster non-convex optimization. In Interna- tional Conference on Machine Learning (ICML), 2016.
[3] Z. Ahlen-Zhu, Y. Li, and Y. Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[4] P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research (JMLR), page 463-482, 2003.
[5] A. Brutzkus, A. Globerson, E. Malach, and S. Shalev-Shwartz, SGD learns over wer-parameterized networks that provably generalize on linearly separable data. In International Conference on Learning Representations (ICLR), 2018
[6] Y. Cao and Q. Gu. Generalization error bounds of gradient descent for learning over- parameterized deep relu networks. In AAAI Conference on Artificial Intelligence, 2020.
10

---

[7] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning (ICML), 2018.
[8] Z. Chen, Y. Cao, Q. Gu, and T. Zhang. A generalized neural tangent kernel analysis for two-layer neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[9] I. Chizat and F. Bach. On the global convergence of gradient descent for over-parameterizee models using optimal transport. Advances in Neural Information Processing Systems (NeurIPS), 2018.
[10] B. D. Craven and B. M. Glover. Invex functions and duality. Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics, 39(1):1-20, 1985.
[11] C. Fang, C. J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. Preprint, arXiv:1807.01695, 2018.
[12] C. Fang, Z. Lin, and T. Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. In Conference on Learning Theory (COLT), 2019.
[13] S. Frei, Y. Cao, and Q. Gu. Algorithm-dependen generalization bounds for overparameterized deep residual networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[14] S. Frei, Y. Cao, and Q Gu. Agnostic learning of a single neuron with gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[15] S. Frei, Y. Cao, and Q. Gu. Agnostic learning of halfspaces with gradient descent via soft margins. In International Conference on Machine Learning (ICML), 2021.
[16] S. Frei, Y. Cao, and Q. Gu. Provable generalization of egd-trained neural networks of any width in the presence of adversarial label noise. In International Conference on Machine Learning (ICML), 2021.
[17) R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Conference on Learning Theory (COLT), 2015.
[18] S. Goel, Karmalkar, and A. R. Klivans. Time/accuracy tradeoffs for learning a relu with respect to gaussian marginals. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[19] M. A. Hanson. On sufficiency of the wuhn-tucker conditions. Journal of Mathematical Analysis and Applications, (022):5455500 1981.
[20] M. Hardt and T. Ma. Identity matters in deep learning. In International Conference Learning Representations (ICLR), 2017.
[21] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[22] Z. Ji and M. Telgarsky. Polylogarithmic width suffices for gradient descent achieve arbi- trarily small test error with shallow relu networks. In International Conference on Learning Representations (ICLR), 2020.
[23] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal proximal-gradient methods under the and Knowledge Discovery Databases (ECML-KDD), 2016.
condition. In European Conference on Machine Learning
[24] Y. Li, T. Ma, and H. R. Zhang. Learning over wer-parametrized two-layer relu neural networks beyond ntk. In Conference on Learning Theory (COLT), 2020.
[25] C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Preprint, SKI1:20033000300 2021.
[26] Liu, S. Wright, C. Ré, V. Bittorf, and S. Sridhar. An asynchronous parallel stochastic coordinate descent algorithm. Journal of Machine Learning Research, 16(10))285-22, 2015.
11

---

[27] S. Lojasiewiczz A topological property of real analytic subsets. Colloques internationauex du C.N.R.S, 117, 1963.
[28] Z. Luo and P. Tseng. Error bounds and convergence analysis of feasible descent methods: general approach. Annals of Operations Research, 46-47(1):157-177, 1993.
[29] S. Mei, A. Montanari, and P.-M. Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences (PNAS), 116633):7766--7777, 2018.
[30] S. Mei, T. Misiakiewicz, and A. Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. Conference on Learning Theory (COLT), 2019.
[31] I. Necoara, Nesterov, and F. Glineur. Linear convergence of first order methods for non- strongly convex optimization. Mathematical Programming, (5(1-2))69-107, 2019.
[32] L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. Stochastic recursive gradient algorithm for nonconvex optimization. Preprint, arXiv: 705.07761 2017.
[33] B. T. Polyak. Gradient methods for the minimisation of functionals. Zhurnal Vychislitel not Matematiki Matematicheskot Fiziki, 3:643-653, 1963. ISSN 0044-4669.
[34] S. J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola. Stochastic variance reduction for nonconvex optimization. In International Conference on Machine Learning (ICML), 2016.
[35] O. Shamir. Exponential convergence time of gradient descent for one-dimensional deep linear neural networks. In Conference on Learning Theory (COLT), 2019.
[36] B. Xie, Y. Liang, and L. Song. Diverse neural network learns true target functions. In Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
[37] G. Yehudai and O. Shamir. Learning a single neuron with gradient methods. In Conference on Learning Theory (COLT), 2020.
[38] H. Zhang and W. Yin. Gradient methods for convex minimization: better rates under weaker conditions. Preprini, 1rX3::1303.4645 2013.
[39] D. Zhou, P. Xu, and Q Gu. Stochastic nested variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[40] Y. Zhou and Y. Liang. Characterization of gradient dominance and regularity conditions for neural networks. In NeurIPS Workshop Deep Learning Theory, 2017.
[41] D. Zou, Y. Cao, D. Zhou, and Q Gu. Gradient descent optimizes over- wer-parraeterrized deep ReLU networks. Machine Learning, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work seeking to develop a mathematical understanding of the non-convex optimization principles underlying neural network optimization. So don't think there is any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
12

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "cLSvt3Tfzh-", "reviewer": "Reviewer_q6Z4", "summary": "This papers introduces two notions, proxy convexity and proxy PL condition, in order to prove convergence results for non-convex functions, in particular for the analysis of neural network training. \n1. A function $f$ is $(g,h)$-proxy convex if $\\langle \\nabla f(w),w-v\\rangle \\geq g(w)-h(v)$ for all $w,v$. Under this condition, it's proved that the function value of $g$ will be decreased to the smallest value of $h$ after polynomial number of SGD updates. \n2. A function $f$ satisfies $(g,\\xi,\\alpha,\\mu)$-proxy PL condition if $\\lVert \\nabla f(w)\\rVert^\\alpha \\geq \\frac{1}{2}\\mu(g(w)-\\xi).$ Under this condition, it's proved that the function value of $g$ will be decreased to $\\xi.$\n\nThen the authors showed that many existing analyses of neural network training can be proved through proxy convexity or proxy PL condition. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposed two notions, proxy convexity and proxy PL condition, for non-convex optimization. Under these conditions, the authors proved certain convergence results on the proxy functions, which more or less follows from a standard analysis. It's interesting to see that this framework can indeed capture some seemingly pretty different analysis (deep net in the NTK regime and one-hidden-layer outside the NTK regime). So I think this framework provides a new perspective to understand the current analyses for neural network training and might be able to inspire new analysis in different settings.\n\nThat being said, my main concern for this paper is that no new neural net training results were proved under the prosed framework. I think in order to fully justify this framework, besides incorporating existing analyses to this framework, it would be more convincing if this framework allows new results to be proved in other settings. In some sense, this would mean this framework not only 'fits' the existing analyses, but also 'generalizes' to new settings. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "YFSCNf7WKdH", "reviewer": "Reviewer_pCxH", "summary": "The authors propose a generalization of the well established notions of convexity and PL inequalities, which they term proxy convexity and proxy PL inequalities correspondingly.  These generalizations are particularly well suited for studying non convex models like neural networks since they do not require all stationary points to be global optima. In fact the authors find that inequalities used in several prior works to prove bounds for neural nets trained with SGD can be unified under proxy convexity and proxy PL inequalities. ", "questions": "", "limitations": "", "rating": 7, "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": "To the best of my knowledge,  the authors are the first to study proxy convexity and proxy PL inequalities so their work is definitely novel. While the proofs in Section 5 are not very surprising given the definitions of the proxy inequalities, the main contribution of this work is identifying the unifying pattern in the proof techniques in the literature and its connections with the standard notions of convexity and PL inequalities.\n\nI believe that proxy convexity and proxy PL inequalities can have significant impact. Now that the unifying patterns are observed, it is easier to make the connections between lines of work that study seemingly disparate neural network architectures. Given the generality of the proxy inequalities, follow up work could strive to provide new instantiations of proxy inequalities. Last but not least, identifying powerful proxies that are implicitly minimized by SGD can lead to new loss functions or optimization procedures that minimize the proxies directly. \n\nOverall a strong and clearly written submission. I acknowledge the authors' responses to all reviewers. I believe highlighting the novel analysis of Example 3.4 will further improve the paper. Thus, I remain in favor of accepting this submission.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and negative social impact are adequately discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "X1kDLDM33We", "reviewer": "Reviewer_V96x", "summary": "The authors propose the notion of proxy convexity and proxy PL inequalities, which represent whether the original objective function induce a proxy function which is implicitly minimized with SGD. The authors show that many existing convergence guarantees for neural networks trained with SGD can be summarized through this framework of proxy convexity. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work in this paper is fundamentally sound and well written, and does a good job of unifying existing results in the literature, such as optimizing a  neural network with a single neuron, or single-layer networks in the NTK regime. \n\nMy main concern is with novelty. While the notion of proxy convexity is new and has utility in unifying existing results for SGD applied to neural network optimization, it would nice to have an idea of how this can be useful going forward, such as a new result, or a new setting which these results can be applied to. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "9Fl0bBpjJ3b", "reviewer": "Reviewer_qxiM", "summary": "The Polyak-Lojasiewicz (PL) inequality is a condition on a function that the gradient is lower bounded by the in terms of the gap between the functions value and the optimal value.  This paper presents a generalized conditioned with additional parameters, including a proxy function $g$ and a notion of proxy convexity using a similar proxy function $g$. Unlike the PL inequality, the new condition can be satisfied by functions having non-optimal local minima.  A theorem bounds the the error of gradient descent (with respect to the proxy convexity function $g$).  They give some examples where guarantees with respect to the desired function can be obtained from the guarantees on the proxy function $g$.\n\n", "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": "Neither the proxy convexity generalization nor the generalization of the PL inequality condition are surprising. The paper’s contribution is fitting the two together to obtain bounds on how GD approximately optimizes the proxy function $g$ (and examples where this implies good bounds with respect to the original function $f$).  \nThe authors show how previous results git into their generalize PL framework.\n\nThe formulation appears to be useful only when stationary points are “good”.  The bounds seem less less meaningful when there are bad unstable stationary points as in the ReLU example around line 73.  Therefore the approach may be good progress towards, but not a revolutionary step, in our understanding of neural network success for non-convex functions.\n\nAlthough the paper shows that many previous results fit into the proxy convexity framework, it was unclear to me if any of the examples represent new or better bounds than previously known.\n \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation is the obvious one of finding appropriate $g$ and $\\xi$ for the generalized PL inequality.  I don't think it needs to be addressed further.  \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces the notions of proxy convexity and proxy PL condition, to analyze convergence in optimization of non-convex functions. This is of particular interest in non-convex neural network training, for which a unified analysis is not yet available in the existing literature. The paper shows that these notions enable a unified analysis of convergence in various settings including the Neural Tangent Kernel (NTK), i.e., infinite-width regime, the fixed width regime in two-layer networks and learning a single ReLU neuron.

Overall, the paper is clearly written and provides good progress towards this direction, although most of the presented convergence results can be established via other methods. The reviewers all agree that the paper presents a nice framework, and expressed minor concerns and suggestions. Please take into account the updated reviews when preparing the final version to accommodate the requested changes. Thank you for your submission to NeurIPS.  
Decision: Accept (Poster)