Convergence of adaptive algorithms for constrained weakly convex optimization
Authors: Ahmet Alacaoglu
Yura Malitsky
Volkan Cevher
Venue: NeurIPS 2021 Poster (2021)
Keywords: adaptive gradient algorithms
weakly convex optimization
AMSGrad
Adam

Abstract: We analyze the adaptive first order algorithm AMSGrad, for solving a constrained stochastic optimization problem with a weakly convex objective. We prove the $\mathcal{\tilde O}(t^{-1/2})$ rate of convergence for the squared norm of the gradient of Moreau envelope, which is the standard stationarity measure for this class of problems. It matches the known rates that adaptive algorithms enjoy for the specific case of unconstrained smooth nonconvex stochastic optimization. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly unbounded optimization domains. Finally, we illustrate the applications and extensions of our results to specific problems and algorithms.

Convergence of adaptive algorithms for constrained weakly convex optimization
Ahmet Alacaoglu
Yura Malitsky Linköping University yurii mal malitskyi@liu.se
Volkan Cevher EPFL
University of Disconsin-MMadion alacaoglu@visc.een
volkan www.:eceeheee...ccomm
Abstract
We analyze the adaptive first order algorithm AMSGrad, for solving constrained stochastic optimization problem with a weakly convex objective. We prove the O(t-1/3) rate of convergence for the squared norm of the gradient of Moreau envelope, which is the standard stationarity measure for this class of problems. It matches the known rates that adaptive algorithms enjoy for the specific case of unconstrained smooth nonconvex stochastic optimization. Our analysis works with mini-batch size of constant first and second order moment parameters, and possibly unbounded optimization domains. Finally, we illustrate the applications and extensions of our results to specific problems and algorithms.
Introduction
Adaptive first order methods have become mainstay of neural network training in recent years. Most of these methods build on the AdaGrad framework [14) which modification of online gradient descent by incorporating the sum of the squared gradients in the step size rule. Based on the practical shortcomings of AdaGrad for training neural networks, RMSprop [22 and Adam (21 proposed to use exponential moving averages for gradients and squared gradients (also known as moment estimations) with parameters B1 and B2, respectively. These methods have seen a huge practical success.
The recent work (8 identified technical issue that affects Adam and RMSprop and proposed new Adam-variant called AMSGrad that does not suffer from the same problem. Theoretical properties of AMSGrad, AdaGrad and their variants for nonconvex optimization problems are studied number of recent papers 4 24 34 37). These works focus on unconstrained smooth stochastic optimization, where the standard analysis framework of the stochastic gradient descent (SGD) [T8] can be used. Convergence of adaptive methods for the more general setting of constrained and/or nonsmooth stochastic nonconvex optimization has remained open, while these settings have broad
practical upplications 7 13 20
25
27 33).
In this work, we take step towards this direction and establish the convergence of AMSGrad for solving the problem
min (f(x) Eg-P (f(x; zex
where f: Rd + is p-weakly convex, X' C R closed convex, and & is a r.v. following a fixed unknown distribution P. This template captures the setting of previous analyses when f is I-smooth, as this implies L-weak convexity, and X' = d However, there exist many applications when X o I2
20 25
33 27
or when f is not L-smooth 7 Section 2. 15).
Constrained stochastic minimization with nonconvexity presents challenges not met in convex setting 19) In particular, until the recent work (7), even for SGD, increasing mini-batch sizes were required for convergence in constrained nonconvex optimization. To study the behavior of AMSGrad for solving (I) build on the analysis framework of [
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Constraints
B1
mini-batch size
Diagonal
Adaptive
L-smooth
x
const.
L-smooth
V
Vt
p-weak. cvx.
0
X
p-weak, evx.
const,
X
This work
p-weak. cvx.
const.
Table 1: Comparison with adaptive methods for smooth nonconvex optimization and SGD-based methods for weakly convex optimization, Column "diagonal" refers to coordinatewise step sizes and "adaptive" refers to step sizes depending on observed gradients á la AdaGrad.
Contributions, We show that AMSGrad achieves (log(T)) (T) rate for near-stationarity, for solving (T. Key specifications for this result are the following:
We can use mini-batch size of 1.
We
constant moment parameters 31, B2 which used in practice 1 4
28
We do not assume boundedness of the domain X.
Next, we particularize our results for constrained optimization with L-smooth objectives and for variant of RMSprop. We also extend our analysis for the scalar version of AdaGrad with first order moment estimation. For easy reference, we compare our results with state-of-the-art in Table Finally, in numerical experiment for robust phase retrieval, we observe that AMSGrad more robust to variation of initial step sizes, compared to SGD and SGD with momentum.
Algorithm AMSGrad (2
Input: 31 E X, 04
0 Vi
for 2 1, 0,
81 < 82 < 1,
my - 1/ = 0, 0n- 0d, 2200
fort 1,2... do
Sample & ~ P iid and set go such that Eg, [9d] E (x())) (see Assumption !
m, -1m--1
B1)g
0. = 320,1 + (1 32)9(
6 max 11
1/2
(xt a, 1/2 1
Te+1 Px
end for
Output: Te, where is selected uniformly at random from {1...., T}.
1.1 Examples of weakly convex problems
The class of problems we consider in this paper include constrained problems with L-smooth objectives which are, for example, studied in [5] in the context of adversarial attacks and adaptive methods. Other important examples with weak convexity are composite objectives h(c(=:),, where convex Lipschitz continuous function and is smooth map with Lipschitz continuous Jacobian. Concrete examples of weakly convex problems are listed in 7 Section 2.1], which include robust phase retrieval, sparse dictionary learning, Conditional Value-at-Rine Risk, and many others.
1.2 Related work
are classically analyzed in online optimization framework with convex objective functions. Recent works studied the behavior of these methods for nonconvex optimization 4 II 24 results is that they are based on the well established proof templates of SGD [8 that only works in simplest case of unconstrained smooth stochastic minimization. Moreover, as mentioned in [[] unconstrained optimization makes it easier to use constant B1 parameter in Adam-type methods. In particular, many results for constrained optimization require fast diminishing schedule for 3, parameter, while constant parameter is used in practice [ 21 28).
Adaptive algorithms based on AdaGrad 14 and Adam
34 37] The common characteristic of these

---

The specific case of (1) with L-smooth f is studied by [5], where the authors proposed zeroth order variant of AMSGrad. This result applies for the specific case of 31 which corresponds variant of RMSprop 28 32 More importantly, since its analysis follows the one of [9] increasing
mini-batch sizes of the order Vt are required [
Theorem 2J.
As also mentioned in 7. analysis of SGD for constrained problems introduces specific difficulties
that are not observed in the convex case. Due to this, classical works analyzing SGD for nonconvex constrained optimization used large
ensure convergence [19]. Showing convergence for SGD for constrained optimization with a single sample had been an open question until ? gave a positive answer in the framework of weakly convex stochastic optimization, which includes constrained smooth stochastic optimization as a special case.
Recent work by 22). considers momentum SGD for solving ( However, this algorithm (i) does not use momentum with 32 and (ii) uses non-adaptive, scalar, fixed step size: in the notation of Algorithm D 8 = 1, 0g a/ VT. These make the algorithm less practical, while simpler for analysis. Moreover the original work of Davis and Drusvyatskiy (7] analyzed standard SGD with no momentum or adaptive step sizes. As incorporating these mechanisms introduce more error terms, we need tighter estimations (for example see (9) and techniques to handle time-dependent adaptive and diagonal step sizes.
Weakly convex optimization is well studied with SGD based methods 10 15
The difficulty of handling the combination of nonconvexity, adaptive step sizes, momentum and constrained sets is mentioned [5] Section 4.3]. In particular, in terms of our analysis, (i) adaptive step size introduces coupling between the step sizes, iterates, and the proximal point defined in 4 (ii) time-dependent diagonal step size requires an analysis framework based on variable metrics. Both of these issues were not the case in earlier works for weakly convex optimization (7,26), and are among the key aspects of our analysis. For details, please see Lemma Lemma and discussions
therein.
Another promising direction of research concerns nonsmooth nonconvex problems under more general assumptions. For instance, tameness and Hadamard mimi-iffferetiabbiityy are used in [8] and [55] respectively, where convergence guarantees are established for SGD-based methods. Because of the generality of the problem class in these works, the algorithms studied there are simpler than the Adam-type algorithms considered in this paper, and the stationarity measures are less standard (35]
1.3 Notation
We adopt the convention of using the standard operations ab, a², a/b, a1/2, 1/a, max fa, b} as element-wise, given two vectors a, b E gd. To denote 7th element of the vector d, E Rd, we use the notation at,i. All-ones vector is denoted 1. Given a vector E Rd, we define the matrix diag(a) ) Rdd as the diagonal matrix with elements of a in the diagonal. For any set X, indicator function Ix is given by Ix = if æ E X' and (x(x) = +oo otherwise.
Given the elements v 0, i 1,....d. d, we define weighted norm || = (x, diag(e)x). The weighted projection operator onto X' is defined as (x(xx) = argmin yex lly x a1... A standard property of this operator is nonexpansiveness: Vx, E R2d | (x) (z))l.. < ||y x||.-
Due to nonconvexity, we cannot use standard definition of subgradients to form global under- estimator. Regular subdifferential, denoted as af. for nonconvex functions (30 Ch. 8] is defined as the set of vectors g RRd such that, Vz, y E RR q E 0f(z) if
f(v) f(x) (y x, 9) + +(lly =l)),
as
(2)
When f is convex, this reduces standard definition of subdifferential and when f is differentiable, this set coincides with { (x)}. We say that f is p-weakly convex w.r.t. || [1. if f(x) + -|
is convex. An equivalent representation for weakly convex functions is that, Vxx, y E Rd, where q E (z(z) 7 Lemma 2.1],
f(y) 2 f(x) + (y x.q) P - 2012.
(3)
2
Moreover, we say ʃ L-smooth if it holds that, Vx, E Rdd [V/((x) - vf(y)) S L| vll- Given random iterates æ ....... It. we denote the filtration generated by these realizations as F, (#1...., ..,., Ft), and the corresponding conditional expectation as [. = [... By the law of total expectation, E [E]]-]]- = [E-] We also sometimes use Ee to denote expectation w.r.. randomness of ç.
3

---

We now present the assumptions of our analysis.
Assumption 1. f: _R
+ R is p-weakly convex with respect to norm ||
The set X Rd is convex and closed.
We can obtain iid samples & ~ P, and such that Eg, len] E Of())) and l1 S G, VI.
lower bounded: f S f()), Vx X.
A few remarks are in order for Assumption] T First, do not require boundedness of the domain X. Second, weak convexity assumption is weaker than smoothness assumption on I and the assumption of bounded gradients is standard for adaptive algorithms B
4 11 In principle, it is possible to
relax the bounded stochastic subgradient assumption to the weaker requirement g 1 I G as in [37 Remark 6. (ii)] with slightly worse and complicated convergence rate. For simplicity, use Assumption [ The third item in Assumption I concerning sampling a stochastic oracle is standard in the weakly convex optimization literature 7 Assumption A2], (26) Assumption A1].
Remark 1. We note that when f is p-weakly convex w.F.t. ll. then it is
v8 weakky convex w.r.f.
aay Vt, since , 2 8 > 0 (see Algorithm Tv. We denote ý
V8
It is easy to verify this remark by noticing that r + f(x) + [||>=|| is convex and f11x1 6//2 2 2211 21
2 Algorithm
We analyze the algorithm AMSGrad (see Algorithm T proposed (28). On top Adam (21]
includes a step to ensure monotonicity of the exponential moving average of squared gradients. It standard in stochastic nonconvex optimization to output a randomly selected iterate [8] [9] which we also adopt. We next define the composite objective
xxx) = f(x) + Ix(x).
For nonsmooth problems, the standard stationarity measures such as the norm of (sub)gradients are no longer applicable, see 77 26) and [13] Section 4]. This motivates the following definitions that, as we show below, relate to a relaxed form of stationarity. Based on and a parameter p >> 0, we define the proximal point of 2, and the Moreau envelope, respectively as
1/2 â, prox p/p (xx) = argminn (p()) + _.ll xell
(4)
( = min { (v)) _ 1el 1, y
We compare the definitions with that of 77. Due to the use of variable metric 0; in adaptive methods, we have time dependent Moreau envelope, where the corresponding vector ig used for defining the norm. Important considerations for these quantities of / As we shall see now, choice of f is critical for ensuring these. In light of Remark [ selecting ' and by using the arguments in 7 for example, Lemma 2.2], (29 Theorem 31.5), it
the uniqueness of 2t, and the smoothness
follows é; unique and piyp smooth with the gradient (z)),p(z))> = /o (x, (x))
Near stationarity. Near-stationarity conditions follow from the optimality condition of ă,: 0 Og((t)) + pot 1/2 / xtt), where we also use úz,; S G2:
|| &e &ell ( 2-10 dist (0, ((p)))()))) S GIl 4/ V (x:)
(5)
( _ ppx:)).
Consistent with previous literature for weakly convex optimization 7 26 we state the convergence guarantees terms of the norm of the gradient of Moreau envelope. Given (5), this means that the iterate 2; is near stationary: it is close to its proximal point &, and &, is approximately stationary.

---

3 Convergence
3.1 Main result
We start with our main theorem that shows that the norm of the gradient of Moreau envelope converges to at the claimed rate, resulting in near-stationarity of x+. as in (5), see Remark foo definition of p.
si < p 2p. Then, for iterate d;-
Theorem 1.
Let Assumption hold. Let B1 < 1, 32 < 1, y=
32
generated by Algorithm 1
it follows that
2dG
E| EIIVii 1l av avoT(1 -31)
C1 + (1 log C)C CCs
where C = SpaG + to (F))p(x1) - 5r). C2 C2= V(1-8)((-)
2002
10G
C3
8Q Σ E0T+,,
The bound in Theorem has complicated constants as it usual for adaptive algorithms in nonconvex case [3 4. These constants are slightly simplified and the proof of Theorem D in Appendix A includes the non-simplified version. Next, we explain and interpret the bound in terms dependence to key parameters.
3.2 Discussion on Theorem 1
In the context of near-stationarity
Theorem | states that to have in Algorithm 1 such that 1V (xx- 1/ S C, we require Ó(c-t) iterations. This matches the known complexities for adaptive methods in unconstrained smooth stochastic optimization SGD-type methods in weakly convex optimization 77 26).
and
Our first remark is about the metric of the norm used for the gradient of Moreau envelope in Theorem We then discuss the dependence of our bound w.r.t. important quantities.
Remark By 5) one has / (2x 111 1= p211 12.22 note that || - -t. - 2
V8| te- 2|2 D1 2 8. also holds that 0z S G2. Therefore, one can convert our guarantees to ||-.- -.- 112 or V| (x+-)]l by multiplying the right hand side by appropriate quantities depending on d or G. We leave the result with the metric, as ô and G are the worst case bounds.
Knowledge of p. To run the algorithm, one does not need to know the weak convexity parameter p. The parameters á and ğ are merely for analysis purposes [8] 226,, and the convergence rate holds for any choice of step size as, independent of p.
Dependence w.n.t 31. Comparing with the previous work, the scaling of our bound in terms of (1 is (1 - 31)-1 matching the dependence for the unconstrained setting [I].
Dependence w.r.t. d. Standard dependence in the convergence rates of Adam-type algorithms for unconstrained case is d/ VT
Even though in Theorem the constant C3 has worst case dependence d' this is merely due to assumptions. The main reason is that we do not assume boundedness of the sequence Ht, instead we prove the necessary result for the analysis in Lemma [ However, this result gives a bound for ||z, - dell. which is naturally dimension dependent. We used this bound in (TO). where we need to bound || &t lloc-
In particular, if we had assumed a bound for ||æ, fellooo then in 10) we could have used it instead of Lemma 1 to have standard d/ /T in C3. Boundedness assumption also would remove factor of 1 V8 the bound, as those terms appear the steps where we avoid boundedness assumption. However, for generality, we do not assume boundedness.
Dependence w.r.t. 8. Our bound has polynomial dependence of 1/8 similar to [34 4) In M.].
more refined technique from [4 used to have a logarithmic dependence of 1/8. This technique, used on the case of smooth unconstrained problems in these works, did not to apply to setting.
We note that in 3 better dependence is obtained by using step sizes in the order of va which do consider.
5

---

3.3 Analysis
In this section, we will flesh out the main ideas of our proof with four lemmas. We will continue with a proof sketch to show how the pieces come together.
3.3.1 Preliminary results
We start with result showing that under [ssumption[] the quantity -xte from (5) stays bounded. We remark that third term on RHS in ( arises as a spurious term due to time-dependent diagonal step sizes, which
not the case in previous works weakly convex optimization with scalar step sizes [26]. Our result in the next lemma is the main tool for us to avoid assuming boundedness of X. The proof of this lemma given in Appendix A the definition of i, with weak convexity.
Lemma 1. Let Assumption 7 hold. Let > P. and it 20
6 > 0 (see Algorithm 7 It follows that
4dG²
||2, -ell s D 8p--D}
A key aspect in the analysis of adaptive algorithms is the dependence of úg and that couples & and Sr (see (4). preventing taking expectation of (z+ $t,gt) that we use to obtain the stationarity measure in the proof. As this was not the case in prior works 26]., we need more refined analysis.
[g E (x()) then it follows that Lemma 2. Let Assumption Thold. Let qt
aa)aaDG P-P
agEc(Er - 9t) 2 ar(p-pp)Eellaz +) Eelly//2 -(ar-1
- -aa---
Eellit 1-2--1111
11-111120
4p
$/29
p p- P ) (
of
0r-1 E, m4 0,11/2
Bellgel1 v8
Interpreting Lemma We review the terms in this bound to gain some intuition. The first term in the RHS is the stationarity measure (see (5)), second term will sum to a constant, fourth and fifth terms will sum log(T') by Lemma Handling the third term in RHS is not as obvious, but we can show that we can cancel it using the contribution from another part of the analysis that we detail in the full proof (see )
One critical issue for Adam-type algorithms is to obtain results with constant 31 parameter. recent work [1] studied this problem for constrained convex problems. The following lemma also plays important role in our analysis.
Lemma 3. / Lemma 1] Let my -1m--1 + (1 B1)9t. Then for any vectors At-1, At.
B1 1 1- 31 (Ai-1
(A,, 1- ((Ar, (Al-1, m)-1)) (Al-1, m-11)
A m)-1)
This lemma derives a decomposition for handling constant B1 parameter in the beginning of the analysis. As explained in Section 3.1 of the abovementioned paper, using a decomposition for m later in the analysis results in a requirement of decreasing 31, especially for constrained problems, which we would like avoid.
Next lemma is a standard estimation used for the analysis of Adam-based methods, dating back to 21 For easy reference point out to [1 where this bound is included as separate lemma with tighter estimations than previous works, due to using a constant 31_ It bounds the sum of the norms of first moment vectors multiplied by the step size sequence.
82
Lemma 4. Let 3 < 1, B2 < 1, 7=
< 1, then it holds that
32
(1 - 32
<
dG(L log T').
v(1 82)(1 -7)
3.3.2 Proof sketch of Theorem
The proof sketch of the theorem is careful combination of the preliminary results mentioned in the previous section. The sketch includes the necessary bounds, but omits the tedious estimations required in some steps. The full proof with the details given in Appendix

---

Proof sketch of Theorem 7 We sum the result of Lemma 3 and use A = Ag. with my = 0. We note that we have A, pa, 2t), for 2 1.
B1 (Ar, mT) + (Ae, +
B1
T-1
Σ 9t)
Σ t=1
(A
Ae+1,m). (6)
- B1
31
t=1
After plugging in the value of Ac, 6 becomes
POTT
par (xe -2..9)) 1 1 B1
(or - Br, mm)
+
pan (os m,)
T-
(0n( .4)) 00+1 -.41). mz)- (7)
1 31
LHS of this bound is suitable for applying Lemma 2 to obtain the stationarity measure. We have to estimate the three terms on the RHS. It is easy to bound the first term using Cauchy- Schwarz Other two terms require longer estimations which we sketch below.
inequality and Lemma I
Bound for P1 1-8 (a it) a441 -f+1),, m)) in
Decomposing this term gives
(ar(z; - 21) ac+1 - fe+1), (at a141)(4141 2.41, me) + ai( I1+1, mi)
+ +of(it+1 - fe,, mi).
For the first term, we use that de 2 04+1 and
inequality
Σ (ai- (1-004))(041 84)1,,) S on DvdG.
For the second term we deduce by Sww.-wwaaazzeeuuuliii and nonexpansiveness of the projection
(x It+1, m²) S aall 1|
For the third term, we use Young's inequality to obtain the bound
31p B
B1p
31
(ar(xt-
21)
a041111110 - S
DvDvG
dG
|me
mmel?
1- B
31
Σ 1=1
T è
p
|+++1 - -6 +
57
T
0
me
11/3
(8)
(0 P) (1 - 31
Bound for Et= (xx - Rt, m.) in
We proceed similar to 7 with tighter estimation (resulting in the negative term on RHS) to obtain
++1 1172 (m++1) S (x1) + pa, Iz, m²)
P Iz+1
2 1.,
112
p - P
1
112
1//2
-212
2
+
p
a
|
12--1/a-
(9)
2
67
Then we manipulate the fourth term on RHS with standard
| < 2||a||2 + 2
and Lemmal
p
Gp v8
// b1 - 2e+1l12
0/12
I p - xx
6//2 -2//2
+
|r, xe 1/42
S pD²
1/2
- 1/22
+
Gp
2
mz 6- 112-1/0-
(10)
v8
im1

---

We use this estimation in ( and sum to get
T
G
pazt T - H4, m²) s pl)p(ar) - -11/ (oT+1)
T+1
+
Σ
pai
||
2
vo
1=1
+ pD
2
d
1/2 T+1
T
P 1 2
Ee41 payz (11)
t=1
We collect (8) and 11] in 77. Finally, we have to obtain the stationarity criterion on the LHS of (7)
by taking conditional expectation. This is not immediate due to coupling of êt, ot, and gt- We
use Lemma to handle this issue and the negative
in (TT is utilized cancel the third term in Then, we use (). plug in Lemma 4 and ş = 2p to conclude. O
the RHS of the result of Lemma 2
Applications & Extensions
4.1 Applications
RMSprop.
The counterexamples presented in (28 show that RMSprop, similar Adam might diverge in simple problems. Setting 31 = in AMSGrad [28] results an algorithm similar to RMSprop, with the difference of having as the output of the max step. Therefore, our analysis also applies to this version of RMSprop with similar guarantees.
Corollary 1. Let 31 = 0. Then, for a variant of RMSprop 128), Theorem
Theoremaapplies applies.
is easy to see that 81 = 0 gives a better bound in Theorem I This is in fact common for the bounds of Adam-type algorithms even in the convex case (8 Setting nonzero momentum parameters 31, 82 do not predict improvement, however, in practice they are routinely observed to improve performance.
SGD with momentum. When é, = 1. vt, AMSGrad reduces to an algorithm similar to SGD with momentum, Lack of diagonal step sizes in this case simplifies the analysis as weighted projections not used in the algorithm. This specific case is studied in the recent work [26), with a slightly different way to set my, Our analysis can be seen as an alternative derivation of convergence for method similar to (26..
Constrained smooth optimization. A special case of ( is when f is L-smooth. In this case, standard convergence measure is the gradient mapping [19] which is used in [5]: Gx (x) 2//4 x-
pot/2 2//2 (rr - 1/2 f(x))). It is instructive to observe that when X' = Rd4. then ||xx(=)]
[V)((>)) 2 which is the stationarity measure for smooth unconstrained problems. probleeemss.....sss....m
When X * Rd, gradient mapping is used as the stationarity measure 7 26
As illustrated in 77) for the specific case of constrained smooth minimization, norm of the Moreau envelope is of the same order as the norm of the gradient mapping, therefore, the results can be converted to guarantees on gradient mapping norms. Using similar ideas as in [12] Theorem 3.51, (7). one can show that || < Cg.m V ( (de))l for a constant Cg.m (see Appendix B. b.
4.2 Extension: Scalar AdaGrad with momentum
An alternative adaptive algorithm is AdaGrad 14] and its variants with first order moment estimation are referred to as AdamNC 28 or AdaFOM In unconstrained smooth stochastic optimization, has been observed that the same proof structure applies to AMSGrad and AdaGrad-based methods simultaneously [4] []. However, in our setting, the analysis we developed for AMSGrad does not directly apply to AdaGrad-based methods.
The main reason is that U, in the case of AdaGrad does not admit a lower bound separated from unlike AMSGrad where 0 < < éz. The uniform lower bound is necessary for converting regular weak convexity assumption w.r.t. norm || the one w.r.t. the weighted norm || ||,y/ in the sense of Remark I Naively assuming the existence of ý in Remark D is not consistent, since is not separated from zero due to v. 2 Vi
in AdaGrad, and hence, the norm || l|, is not well-defined.

---

In this section, we provide partial results on this direction. In particular, we show that the scalar version of AdaGrad, that used in [2 24 34], along with its variant with first order moment estimation also has the same convergence rate. In the framework of Algorithm of these methods iterate as, for iid sampled & ~ P. Eg. [9c] af(z)).
[ scalar (non-diagonal) version
my = -1mp-1 + (1 B1
82 (6 دコ= |19)1
(12)
Fe+1 Px Vot me),
where Px denotes standard Euclidean projection. The factor of d'1 in front of gradient norms is to normalize the step size, as f--norm is dimension dependent. This factor only affects the dimension dependence of the bound. In this case, one does not need the time-dependent definitions for Moreau envelope and ăy: 2, = //ox1//(21) and (P1/p(z) weighted projection. The proof then is similar to 7 with AdaGrad step sizes. The difficulties arising
minyex f(v + 21l 2|| due to lack of
due to adaptive step sizes and existence of 31, are handled using Lemmas
3 and
Theorem 2. Lel Assumption 7 hold. Then, for the method sketched in (2p with B1 < 1, a, -
B| (x==))
2G
Ci (1+ (1+log aVT
(G2
8 +111
+1))
C2
where C1 = (m)) - f
12ndG² 18(1-11)' C2 = (1-81)2*
8pa
The terms in the bound are simplified as Theorem T and their non-simplified variants are in the proof in Appendix|p A Our analysis takes care of the coupling between the AdaGrad step sizes and iterates of the algorithm. However, unlike our results with AMSGrad, in this case the analysis does not cover the diagonal case, where the step sizes set by using elementwise squared gradients of We leave as an open question to derive similar results for AdaGrad-bart methods with diagonal step sizes.
400
accurayy
300
SGD
300
300
AMSCraa
200
SHIP-UL
200
200
SHB-0.01
100
100
10
10
10
100
10a
10
intial step size
Inttia step size
Inttlll step size
Figure I: left-right: {1, 10, 100}. Number of epochs to f(x) - 0.1 vs. initial step size
Numerical experiment
This section illustrates the potential advantages of adaptive algorithms, in particular AMSGrad, for solving a prototypical weakly convex problem, compared to SGD and SGD with momentum (also referred in [26] stochastic heavy ball: SHB). As popular in the literature of weakly convex stochastic optimization methods 8 I0 26). we will compare the algorithms in terms of their robustness to initial step sizes. We note that "robustness funing" of algorithms also investigated in the context of deep learning in the literature and the advantage of adaptive algorithms such as Adam/AMSGrad is observed [6] 31. In particular, we solve the robust phase retrieval problem [9] [6
17]: min 1 Σ (a;, x:)² bil. where A [a],.... ag E Boxd n = 300, = 50. Weak
convexity of this problem well-known
9
We briefly recall the setup from (26] that considered SGD with momentum for solving this problem. The data is generated as A QD, with standard normal distributed matrix nxd and D = linspace (1/acce(1//.))) k, 1, d), where x > 1 controls the conditioning. We generate the solution x" as a standard normal random vector with unit norm. The observations generated as b Ax + 8n
We make the "effective initial step sizes" of algorithms equal. In particular pick SGD a MSGD AMS
since the initial step size of AMSGrad is ap
925 max, (o).)

---

where elements of E IR' have distribution (0, 25) and ó = diag(ő1..... 5a) is such that Hi E [m]: : 6, = 13/n 0.2, which means that 20% of the observations are corrupted.
With this setup, it is proven 1 Lemma 12] that only solutions of the problem are {x* ===> Therefore, for the algorithms, we will use (xx) - f(x*) S the stopping criterion. We run stochastic subgradient method (SGD) 77. momentum SGD (SHB) 266 and AMSGrad that we analyzed in this paper. For all algorithms, the step size is chosen as Olg oo/Vii /v. We varied the initial step size² between 0.01 and 10 for all algorithms, and we plotted the number of epochs that the algorithms take to reach to fzx f(**) both 3 = 0.1 and 0.01 for SHB, as in 26 and 31 = B2 0.99 popular, for AMSGrad.
) I 0.1. In terms of other algorithmic parameters, we use
We present the results in Figure 1 for varying values of k. = {1, 10, 100), where each setup is run for 50 times, medians are drawn as lines and the region between 20th and 80th percentiles are shaded. has been observed in [26] that SHB improves the robustness of SGD to initial step sizes. We observe in Figure I that AMSGrad shows a more robust behavior to initial step size compared to both algorithms. We note that our findings indicate the potential of AMSGrad and adaptive methods for weakly convex optimization. Moreover, our findings about robustness of adaptive algorithms to tuning is consistent with the findings from deep learning literature 6 31
Acknowledgments and Disclosure of Funding
Most of the work was done while Ahmet Alacaoglu and Yura Malitsky were at EPFL.
This project received funding from NSF Award 2023239; DOE ASCR under Subcontract 8F-30039 from Argonne National Laboratory: the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, with the project number 305286; the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no 725594- timedata); the Swiss National Science Foundation (SNSF) under grant number 100021_178865/1 the Department of the Navy, Office of Naval Research (ONR) under grant number N62909-17-1-2111 and the Hasler Foundation Program: Cyber Human Systems (project number 16066).
References
[1] Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher. A new regret analysis for Adam-type algorithms. In International Conference on Machine Learning, 2020.
[2] Anas Barakat and Pascal Bianchi. Convergence analysis of a momentum almentumaagorrtthnn algorithm with adaptive step size for non convex optimization. arXiv preprint arXiv: 19Xiv:/911.055000 2019.
[3] Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang. Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. In 29th International Joint Conference Artificial Intelligence, 2020.
[4] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong- On the convergence of class of adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019.
[5] Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. ZO- AdaMM: Zeroth-orde adaptive momentum method for black-box optimization. In Advances in Neural Information Processing Systems, pages 7202-7213, 2019.
[6] Dami Choi, Christopher Shallue, Zachary Nado, Jaehoon Lee, Chris Maddison, and George E Dahl. On empirical comparisons of optimizers for deep learning. arXiv preprint 110.54991. 2019.
[7] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, (1)):277-239 2019.
[8] Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on tame functions. Foundations of computational mathematics, 20(1):115 199 154, 2020.
10

---

[9] Damek Davis. Dmitriy Drusvyatskiy, and Courtney Paquette. The nonsmooth landscape of phase retrieval. IMA Journal of Numerical Analysis, 40(4):2652-2666 2020.
[10] Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal Optimization, 29(3):1908-1999 2019.
[11]
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. On the convergence of Adam and Adagrad. arXiv preprint arXiv:2003.02395, 2020.
[12] Dmitriy Drusvyatskiy and Adrian Lewis. Error bounds, quadratic growth, and linear conver- genee of proximal methods. Mathematics of Operations Research, 43(3):919-946 2018.
[13] Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178(1-2):503-555)) 558, 2019.
[14] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul):121-2215) 2011.
[15] John C Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimization problems. SIAM Journal on Optimization, (((4):3229-322)) 2018.
[16] John C Duchi and Feng Ruan. Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval. Information and Inference: A Journal of the IMA, 8(3):471-529, 2019.
[17] Yonina C Eldar and Shahar Mendelson. Phase retrieval: Stability and recovery guarantees. Applied and Computational Harmonic Analysis, 36(3):473-494, 2014.
[18] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, (3(4):2341-2366) 2013.
[19] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1- 2):267-305, 2016.
[20] Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International Conference on Machine Learning, pages 2137-2146, 2018.
[21] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2015.
[22] Kfir Levy. Online to offline conversions, universality and adaptive minibatch sizes. In Advances in Neural Information Processing Systems, pages 1613-1622, 2017.
[23] Kfir Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceleration. In Advances in Neural Information Processing Systems, pages 6500-6509, 2018.
[24] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 983-992, 2019.
[25] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In International Conference on Learning Representations, 2018.
[26] Vien V Mai and Mikael Johansson. tum for nonsmooth nonconvex optimization. In International Conference on Machine Learning. 2020.
Convergence of a stochastic gradient method with momen-
[27] Pablo Márquez-Neila, Mathieu Salzmann, and Pascal Fua. Imposing hard constraints on deep networks: Promises and limitations. arXiv preprint arXiv: 02025, 2017.
[28] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018.
11

---

[29] R Tyrell Rockafellar. Convex analysis. Princeton university press, 1970.
[30] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science Business Media, 2009.
[31] Prabhu Teja Sivaprasad, Florian Mai, Thijs Vogels, Martin Jaggi, and François Flcuret. Opti- mizer benchmarking needs to account for hyperparameter tuning. In International Conference on Machine Learning, pages 9036-9045. PMLR, 2020.
[32] Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-RMSprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning. 4(2):26-31, 2012.
[33] Nino Vieillard, Olivier Pietquin, and Matthieu Geist. On connections between constrained optimization and reinforcement learning. arXiv preprint arXiv: 1910.08476 2019.
[34] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In International Conference on Machine Learning, pages 6677-6686,
2019.
[35] Jingzhao Zhang, Hongzhou Lin, Suvrit Sra, and Ali Jadbabaie. On complexity of finding stationary points of nonsmooth nonconvex functions. In International Conference on Machine Learning, 2020.
[36] Fangyu Zou, Li Shen, Zequn Jie, Ju Sun, and Wei Liu. Weighted adagrad with unified momentum. arXiv preprint arXiv:1808.034400 2018.
[37] Fangyu Zou, Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of Adam and RMSprop. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 11127-11135, 2019.
12


Reviews:
[{"review_id": "uaHsjjOx901", "reviewer": "Reviewer_NSxc", "summary": "This paper analyzes AMSGrad when applied to a broad family of nonsmooth, nonconvex, stochastic, constrained optimization problems. Convergence rates based on the norm of the Moreau envelope's gradient (although in a rescaled norm) are presented. The rates nearly match the O(1/T^{1/4}) rate of the subgradient method, off by a logarithmic term. The primary innovation in this work is tackling technical barriers to handle first and second order moment parameters that complicate analysis.", "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 terminology used for describing convergence rates is somewhat inconsistent. The abstract uses the more modest description of a O(1/T^{1/4}) rate in the gradient norm whereas the main text consistently frames itself as a O(1/\\sqrt{T}) rate in terms of the near stationarity condition (5), which hides a factor of two.\n\n-Algorithm 1 currently does not define $\\xi_t$ which is presumably sampled i.i.d. at each iteration.\n\n-The analysis implicitly uses a sum rule for nonconvex nonsmooth calculus that requires additional regularity assumptions to be assumed. Namely, it need not be the case that selecting $g_t\\in \\partial f(x_t,\\xi_t)$ for each realization of $\\xi_t$ produces an unbiased estimator of a element $q_t$ in $\\partial f(x_t)$ (as is claimed in Lemma 2). Regularity conditions on each $f(x,\\xi)$ are needed. It would suffice to additionally assume that each $f(x,\\xi)$ is locally Lipschitz everywhere on an open set containing $X$.\n\n-Remark 2 currently claims $\\|x_t-\\hat x_t\\|^2_{v_t^{1/2}} \\geq \\sqrt{\\delta}\\|x_t-\\hat x_t\\|^2$. I believe the $\\sqrt{\\delta}$ should be $\\delta$.\n\n-Relaxing the $\\|\\cdot\\|_\\infty$ norm subgradient constraint to instead be a bound on the expected norm seems more difficult than the work suggests. Doing so would remove the uniform upper bound on the size of $v_t$, which would then make converting guarantees back to the original norm $\\|\\cdot\\|$ much harder.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The convergence guarantee's given in the rescaled norm based on $v_{t}$ and based on the rescaled Moreau/proximal operator using $v_t$. As a result (and as the paper acknowledges in remark 2), extra care is needed to understand the results in the given norm $\\|\\cdot\\|$. Particularly, the best guarantee given from the proposed analysis is worse by a non-negligible factor of $1/\\delta$. Establishing some lower bounding theory for $v_t$ may overcome this current limitation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "T-DEI4lCWcd", "reviewer": "Reviewer_SLqj", "summary": "This paper presents an adaptive gradient descent method for a convex set-constrained weakly convex (hence, nonconvex and possibly nonsmooth) optimization problem. ", "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 authors used AMSGrad proposed by Reddi et al. [2018] for showing their results. AMSGrad was a modification of ADAM that exhibited provable convergence. The authors also used Moreue envelop-based analysis in Davis et al. [2018] where the norm is suitably weighted for the adaptive procedure. The bounds provided in Theorem 1 are very similar to state-of-the-art results for adaptive algorithms like Adam, AMSGrad, RMSProp, etc. \nThe Paper was quite easy to read and the authors did a good job in providing key insights into the proof techniques.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Boundedness assumption on the stochastic gradient, even though standard in adaptive optimization, is quite strong for unbounded domain set. Many works get around this difficulty by assuming compactness of set \\mathcal{X}. Since the paper also briefly discussed bounded domains, I believe that this is not a major issue. \nOverall, I think the paper makes a good contribution. Given that this is the first paper looking into an adaptive procedure for nonsmooth nonconvex problems, the authors could have done a better job in highlighting the key aspect of the analysis which allowed for providing convergence. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "-TtW6cG-Kov", "reviewer": "Reviewer_kQU3", "summary": "The paper provides a convergence analysis for the AMSGrad algorithm for the more general class of functions that are weakly convex. The convergence guarantee is comparable to existing results for SGD, and the main advantage is that the AMSGrad algorithm does not require knowledge of the weak convexity parameter and it automatically adapts to it. The paper extends the convergence analysis to other algorithms, such as SGD with momentum and the AdaGrad algorithm with scalar step sizes.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Significance:\nAdaptive methods in the AdaGrad/Adam family are widely used in practice, in both the convex and non-convex setting. Prior analyses for these algorithms in the non-convex setting assume smoothness. This paper extends this line of work by considering weakly convex functions, which are more general than smooth functions. In addition to adapting to the weak convexity parameter, another strength of the analysis is that it works for constant beta_1 and beta_2 parameters, which is in line with how Adam is used in practice.\n\nOne of the weaknesses of the analysis is that it strongly relies on the value delta used to initialize the preconditioner, which is crucial for bounding key error terms, resulting in a dependence of 1/sqrt(delta) in the convergence. This limits the applicability of the analysis approach and it does not allow for arbitrarily small initializations as used in practice.\n\nThe computational evaluation shows the benefits of using AMSGrad compared to using non-adaptive methods such as SGD. However, the experiments consider small synthetic instances and thus the experimental evaluation is limited. Overall, this is a good contribution to this line of work.\n\nNovelty/originality: The paper builds on prior analyses of SGD for weakly convex functions as well as an an analysis of AMSGrad for convex functions that works for constant beta_1 and beta_2 parameters. The non-convexity together with the adaptive and stochastic step sizes poses some additional challenges in the analysis compared to prior work, and the main novelty in this work is to bound the new error terms that arise. Overall, there is sufficient novelty but it is perhaps somewhat limited.\n\nClarity: The paper is reasonably clear. ", "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": "I did not track the hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces an adaptive method for weakly convex optimization, which generalizes the setting of smooth nonconvex optimization. A particularly important aspect of the introduced method is that it automatically adapts to the weak convexity parameter, without any prior knowledge. The paper makes a good contribution to the literature on adaptive gradient methods (similar to the very popular AdaGrad) and all the reviews expressed support in seeing this paper published at NeurIPS. 
Decision: Accept (Poster)