Adaptive First-Order Methods Revisited: Convex Minimization without Lipschitz Requirements
Authors: Kimon Antonakopoulos
Panayotis Mertikopoulos
Venue: NeurIPS 2021 Poster (2021)
Keywords: convex optimization
non-Lipschitz
adaptive methods

Abstract: We propose a new family of adaptive first-order methods for a class of convex minimization problems that may fail to be Lipschitz continuous or smooth in the standard sense. Specifically, motivated by a recent flurry of activity on non-Lipschitz (NoLips) optimization, we consider problems that are continuous or smooth relative to a reference Bregman function – as opposed to a global, ambient norm (Euclidean or otherwise). These conditions encompass a wide range ofproblems with singular objective, such as Fisher markets, Poisson tomography, D-design, and the like. In this setting, the application of existing order-optimal adaptive methods – like UnixGrad or AcceleGrad – is not possible, especially in the presence of randomness and uncertainty. The proposed method, adaptive mirror descent (AdaMir), aims to close this gap by concurrently achieving min-max optimal rates in problems that are relatively continuous or smooth, including stochastic ones.

Adaptive First-Order Methods Revisited: Convex Optimization without Lipschitz Requirements
Kimon Antonakopoulos
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG 38000 Grenoble, France & Criteo Al Lab kimon, k ianoonannttonkkoouloeeeiria..... fr panayotis. mtr.oissoemetiiooooooseeeeeeee fr
Abstract
We propose a new family of adaptive first-order methods for a class of convex mini- mization problems that may fail to be Lipschitz continuous smooth. Specifically, motivated by a recent flurry of activity on non-Lipschitz (NoLips) optimization, we consider problems that continuous smooth relative reference Bregman function as opposed to a global, ambient norm (Euclidean or otherwise). These conditions encompass wide range of problems with singular objectives that not be treated with standard first-order methods for Lipschitz continuous/smooth problems such Fisher markets, Poisson tomography problems. D-optimal design, and the like. In this setting, the application of existing order-optimal adap- tive methods like UNIXGRAD ACCELEGRAD the presence of randomness and uncertainty. The proposed method which we call adaptive mirror descent (ADAMIR) aims close this gap by concurrently achieving min-max optimal rates in problems that are relatively continuous or smooth, including stochastic ones.
possible, especially
Introduction
Owing to their wide applicability and flexibility, first-order methods continue to occupy the forefront of research learning theory and continuous optimization. Their analysis typically revolves around two basic regularity conditions for the problem at hand: (?) Lipschitz continuity of the problem's s objective, and/ or (ii) Lipschitz continuity of its gradient (also referred to as Lipschitz smoothness). Depending on which of these conditions holds, the lower bounds for first-order methods with perfect gradient input (1/ /T) and ((1/T²) after T' gradient queries, and they achieved by gradient descent and Nesterov's ' fast gradient algorithm respectively [36, 37, 48]. By contrast, if the optimizer only has access stochastic gradients (as is often the case in machine learning and distributed control), the corresponding lower bound is ((1/VT) for both classes [14, 34, 37).
This disparity in convergence rates has led to surge of interest in adaptive methods that can seamlessly interpolate between these different regimes. Two state-of-the-art methods of this type are the ACCELEGRAD and UNIXGRAD algorithms of Levy et al. [26) and Kavis et [24]: both algorithms concurrently achieve an (IIVTT) value convergence rate in non-smooth problems, an (1/T²²) rate in smooth problems, and an ((/VVT) average rate run with bounded, unbiased stochastic gradients (the smoothness does not affect the rate this case). In this regard, UNIXGRAD and ACCELEGRAD both achieve a "best of all worlds" guarantee which makes them ideal as off-the- shelf solutions for applications where the problem class is not known in advance e.g., in online traffic routing, game theory, etc.
At the same time, there have been considerable efforts in the literature to account for problems that do not adhere to these Lipschitz regularity requirements such as Fisher markets, quantum tomography, D-design, Poisson deconvolution / inverse problems, and many other examples [7, 10, 11, 28, 29, 45]. The reason that the Lipschitz framework fails in this case is that, even when the problem's 's domain
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is bounded, the objective function exhibits singularities at the boundary, so it cannot be Lipschitz continuous or smooth. As result, no matter how small we pick the step-size of a standard gradient method (adaptive or otherwise), the existence of domains with singular gradients can and typically does lead to catastrophic oscillations (especially in the stochastic case).
A first breakthrough in this area was provided by Birnbaum et al. [10] and, independently, Bauschke al. [7] and Lu al. [29], who considered a "Lipschitz-like" gradient continuity condition for problems with singularities. At around the same time, Lu [28] and Teboulle [45] introduced a "relative continuity" condition which plays the same role for Lipschitz continuity. Collectively, instead of using global norm as a metric, these conditions employ a Bregman divergence as a measure of distance, and they replace gradient descent with mirror descent [14, 34].
In these extended problem classes, non-adaptive mirror descent methods achieve 0(I/VT) value convergence rate in relatively continuous problems [2, 28), an O(1/T) rate in relatively smooth problems [7. 10]. and an O(1/VT) average rate if run with stochastic gradients in relatively continuous problems [2, 28]. Importantly, the OL/"T) rate for relatively smooth problems does not match the () rate for standard Lipschitz smooth problems: in fact, even though [20] proposed a tentative path towards faster convergence in certain non-Lipschitz problems, Dragomir al. [17] recently established an (2(1/T) lower bound for problems that are relatively-but-nn Sott--buuttot--isseeee Lipschizz smooth.
Our contributions. Our aim in this paper is to provide adaptive, parmmeter-agmosticc method that simultaneously achieves order-optimal rates in the above "non-L.pschitzz framework. By design, the proposed method which call adaptive mirror descent (ADAMIR)- has the following desirable properties:
1. When run with perfect gradients, the trajectory of queried points converges, and the method's rate of convergence in terms of function values interpolates between O(1v/T) and (1/TT) for relatively continuous and relatively smooth problems respectively.
2. When run with stochastic gradients, the method attains an O(I/VT) average rate of convergence.
3. The method applies to both constrained and unconstrained problems, without requiring a finite Bregman diameter or knowledge of a compact domain containing a solution.
The only thing we assume known in the above is the reference Bregman function with respect to which the problem's 's objective is relatively continuous/smooth; other than that, we assume no prior information on the problem's 's regularity class / modulus and/or the oracle model being accessed (deterministic or stochastic). The enabling apparatus for these properties is adaptive step-size policy in the spirit of [6. 18. 30J. However, a major difference and technical difficulty - is that the relevant definitions cannot be stated in terms of global norms, because the variation of non- Lipschitz function explodes at the boundary of the problem's 's domain (put differently, gradients may be unbounded even over bounded domains). For this reason, our policy relies the aggregation of a suitable sequence of "B "Bregman residuals" that stabilizes seamlessly when approaching a smooth solution, thus enabling the method to achieve faster convergence rates.
Related work. Beyond the references cited above, problems with singular objectives were treated in recent series of papers in the context of online and stochastic optimization [2, 49]; however, the proposed methods are not adaptive, and they do not interpolate between different problem classes.
In the context of adaptive methods, the widely used ADAGRAD algorithm of Duchi al. [18] and McMahan and Streeter [30] was recently shown interpolate between an OLL (T/ and (1/TT) rate of convergence [26, 27]. More precisely, Li and Orabona [27] showed that a specific, "one-lag- behind" variant of ADAGRAD with prior knowledge of the smoothness modulus achieves an ((1TT)
1 'This condition was first examined by Birnbaum et al. [10] in the context of Fisher markets. The analysis of
Bauschke al. [7] and Lu et al. [29] much more general, but several ideas are already present [10].
"The reference function has do with the type of gradient singularities that develop at the boundary of the problem's 's domain. For example, the Fisher market models that discuss later in the paper always exhibit (log z) gradient singularities at the boundary, so the appropriate choice for such models the negative entropy. and this is true whether the specific market model is everywhere differentiable or not. Likewise, Poisson inverse problems always exhibit (11xx) gradient singularities at the boundary of the positive orthant, which means that the log-entropy is the appropriate reference function for such problems.

---

Constr. / Uncon.
Stoch. (L)
RC
RS
Stoch. (R)
ADAGRAD
[18]
1/4
X
X
ACCELEGRAD
[26]
X/ /
X
X
X
UNIXGRAD
[24]
V X
V
x
X
X
UPGD
[39]
V1V
X
X
GMP
[44]
41
X
1/T
X
ADAPROX
[3]
4/v
X
partial
partial
X
ADAMIR
[ours]
4/4
1/VT
1/T
1/VT
Table 1: Overview of related work. For the purposes of this table, (L) refers "Lipschitz" and (R) to "relative" continuity or smoothness respectively. In the case of ADAPROX, "partial" means that the non-Lipschitz conditions under which it guarantees convergence form a subset of the RC/RS conditions. Logarithmic factors are ignored throughout; we also note that the (1/TT) rate in the RS column is, in general, unimprovable [17].
rate in smooth, unconstrained problems; concurrently, Levy et al. [26] obtained the same rate in parameter-agnostic context. In either case, ADAGRAD achieves O(1/VT rate of convergence in stochastic problems (though with somewhat different assumptions for the randomness).
In terms of rate optimality for Lipschitz smooth problems, ADAGRAD is outperformed by ACCELE- GRAD [26] and UNIXGRAD [24]: these methods both achieve O value convergence rate Lipschitz smooth problems, and an ((1/vT) rate in stochastic problems with bounded gradient noise. By employing efficient line-scarch step, the universal primal gradient descent (UPGD) algorithm of Nesterov [39] achieves order-optimal guarantees in the wider class of Hölder continuous problems (which includes the Lipschitz continuous and smooth cases extreme cases); however, UPGD does not cover stochastic problems or problems with relatively continuous smooth objectives.
As far as we are aware, the closest works to our own are the generalized mirror-prox (GMP) algorithm of [44] and the ADAPROX method of [2], both designed for variational inequality problems. The GMP algorithm can achieve interpolation between different classes of Hölder continuous problems and can adapt to the problem's 's relative smoothness modulus, but does not otherwise interpolate between the relatively smooth and relatively continuous classes. Moreover, GMP requires knowledge of "domain of interest" containing a solution the problem; this regard, it is similar to ACCELEGRAD [26] (though it does not require an extra projection step). The recently proposed ADAPROX method of Antonakopoulos et al. [3] also achieves a similar interpolation result under a set of assumptions the relatively continuous/smooth setting of paper. Moreover, neither these papers covers the stochastic case; to the best our knowledge, ADAMIR is the first method in the literature capable of adapting to relatively continuous/ smooth objectives, even under uncertainty. For convenience, we detail these related works Table above.
that are closely related but not equivalent
2 Problem setup and preliminaries
Problem statement. Throughout the sequel, will focus convex minimization problems of the general form
minimize f(x),
(Opt)
subject to X.
In the above, X' is convex subset of normed d-dimensional space V Rd, and V:V a proper lower semiicontinuous (l.s.c) convex function with dom = {=) x3) X. Compared to standard formulations, stress that X' is not assumed to be compact, bounded, closed. This lack of closedness will an important feature for our analysis because we are interested in objectives that may develop singularities at the boundary of their domain; for class of relevant examples of this type, see [1, 2, 7, 9-11,,11222210011 22, 29, 49] and references therein.
To formalize our assumptions for (Opt), we will write (z for the subdifferential of f at and X. = dom 0ʃ (ar E (=(x) + Ø) for the domain of subiifferentiability elements of 0ʃ will be called subgradients, and we will treat them throughout as elements of the dual space V of V. By standard results, we have ri X C X, C X, and any solution x" (Opt) belongs to Nr [42, Chap. 26]: to avoid trivialities, we will make the following blanket assumption.
f. Formally,
3

---

Assumption 1. The solution set X arg min f S N. of (Opt) is nonempty.
Two further assumptions that are standard in the literature (but which we relax in the sequel) are:
1. Lipschitz continuity: there exists some G > such that
| - f(x) s G||æ' =||| for all x, E X.
(L.C)
2. Lipschitz smoothness: there exists some L > 0 such that
L
f(x') S +
22' =|| for all a, x,
X' and all E 0f(z).
(LS)
Remark. For posterity, we note that the smoothness requirement (LS) does not imply that of is singleton. The reason for this more general definition is that we want to concurrently treat problems with smooth and non-smooth objectives, and also feasible domains that are contained in lower-dimensional subspaces of V. We also note that we will be mainly interested in cases where the above requirements all fail because f and/or its derivatives blow up at the boundary of X. By this token, we will not treat (LC)/LSS) as "blanket assumptions"; we discuss this in detail in the sequel.
The oracle model. From an algorithmic point of view, we aim to solve (Opt) by using iterative methods that require access to stochastic first-order oracle (SFO) [37]. This means that, each stage of the process, the optimizer can query a black-box mechanism that returns an estimate of the objective's gradient (or subgradient) at the queried point. Formally, when called at æ E X, an SFO is assumed to return a random (dual) vector g(1; w) E V* where w belongs to some (complete) probability space (Ω, F, P).. In practice, the oracle will be called repeatedly a (possibly) random sequence of points X, E X' generated by the algorithm under study. Thus, once X, has been generated at stage t. the oracle draws an i.i.d sample W/ 12 and returns the dual vector:
(1) with U, E V* denoting the "measurement error" relative to some selection (XX,,) of Ofx,). In terms of measurability, we will write J. for the history (natural filtration) of X in particular, X, is Fe-adapted, but Wt. It and U2 not. Finally, will also make the statistical assumption that
= ((x:u)) = (X(,)) +.+
EIU Fi] = 0 and || o² for all l = 1, 2,
(SFO)
where ||-I|+ denotes the dual norm on V This assumption is standard in the analysis of parameter- agnostic adaptive methods, cf. [6. 24, 26, 46] and references therein. For conereteness, we will refer to the case = 0 as deterministic - since, in that case, U, = 0 for all t. Otherwise, if lim infi:|/Ullll (Ull= O, the noise will be called persistent and the model will be called stochastic.
3 Relative Lipschitz continuity and smoothness
3.1. Bregman functions. We now proceed to describe a flexible template extending the standard Lipschitz continuity and Lipschitz smoothness conditions- (LC) and (LS) to functions that are possibly singular at the boundary points of X. The main idea of this extension revolves around the non-Lipschitz (NoLips) framework that was first studied by Birnbaum et al. [10] and then rediscovered independently by Bauschke et al. [7] and Lu et al. [29]. The key notion in this setting is that of a suitable "reference" Bregman function, which is assumed known to the optimizer. and which provides a ccometry-adapteer measure of divergence on X. This is defined as follows:
Definition 1. A convex l.s.c. function h: V + R U {co} is Bregman function on X, if
dom 0h C X. C dom h.
2. The subdifferential of l admits a continuous selection Vh(x) E 0h(x) for all x E dom Oh.
3. h is strongly convex, i.e., there exists some K such that
K h(x') > h(x) + (Vh(z), x) || xx|2
for all x E dom 0h, x' dom Oh.
For example, the function f: 1 + IR with f(21, 0) = 21 and f(11, x2) = 20 for 32 * 0 perfectly smooth on its domain (z2 0); however, (f(1) 0) = {(1, ez R). and this is never singleton.

---

The induced Bregman divergence of h is then defined for all dom dh, x' E dom h
D(a', 2) h(2')( h(x) (Vh()),
Remark. The notion of Bregman function was first introduced by Bregman [13]. Our definition follows [5, 23, 35, 38] and leads to the smoothest presentation, but there are variant definitions where h is not necessarily assumed strongly convex, cf. [8, 15] and references therein.
Some standard examples of Bregman functions are as follows:
Euclidean regularizer: Let X be a convex subset of Rd endowed with the Euclidean norm 11.112- Then, the Euclidean regularizer on X' is defined as h(()) = | 2 and the induced Bregman divergence is the standard square distance D( x) = || - x 2 for all x, E
Entropic regularizer: Let X {ar E R E I; 1} be the unit simplex of IR endowed with the L' noom ||-||1- Then, the entropic regularizer X' is h(x) E, I, log 2; and the induced divergence is the relative entropy D( x) = Σ. xf log(z)// for all x' E E x E Eri
Log-barrier: Let X' = R24 denote the (open) positive orthant of TRed. Then, the log-barrier on X defined as h(x) - Di= loga; vi for æ E R44 The corresponding divergence is known as the Itakura-Saito divergence and is given by D Ei (x./22 log(x;/=²) 1) [15].
3.2. Relative continuity. With this background in hand, we proceed to discuss how extend the Lipschitz regularity assumptions of Section 2 to account for problems with singular objective functions. We begin with the notion of relative continuity (RC), as introduced by Lu [28] and extended further in recent paper by Zhou et al. [49]:
Definition 2. A convex l.s.c. function f: V + R U {oo} is said to be relatively continuous if there exists some G >> 0 such that
f(x) - f(²) < (Vf(z), S GV22(c' for all x' E dom h æ E dom Ōh.
(RC)
In the literature, there have been several extensions of (LC) to problems with singular objectives. Below we discuss some of these variants and how they can be integrated in the setting of Definition
Example 1 hW continuity). This notion intends to single out sufficient conditions for the convergence of "proximal-like" methods like mirror descent. Specifically, following Teboulle [45], f said be W[f, hi co--iininuuuus relative h on X (read: "f is weakly h--cotinuous")) if there exists some G > 0 such that, for all > 0, we have
2 (V)(),,, x²) D(d', x0) - G2 for all x' E dom h, dom Oh.
(W)
By rearranging the above quadratic polynomial in i, note that its discriminant is A [(V(()), - 2G D(x' (ao',") v)), so is immediate check that (RC) holds.
Example 2 (Riemann Lipschitz continuity). Concurrently to the above, Antonakopoulos et al. [2] introduced a Riemann- Lippschitz continuity condition extending (LC) as follows. Let Il- be family of local norms on X' (possibly induced by an appropriate Riemannian metric), and let [|u||,,- max | (1 (v. .²) denote the corresponding dual norm. Then, f is Rieman--lipsehit continuous relative to I| if there exists some 0 such that:
[VV((>) S G for all x E X.
(RLC)
As we show in the paper's supplement, (RI.C = (RC) so (RC) is more general in this regard.
3.3. Relative smoothness. As discussed above, the notion of relative smoothness (RS) was intro- duced by [10] and independently rediscovered by [7, 29]. It is defined follows:
Definition 3. A convex l.s.c. function f: V R U } is said to be relatively smooth with respect to f if
Lh - f is convex for some L > 0.
(RS)
The main motivation behind this elegant definition is the following variational characterizations:: Proposition 1. The following statements equivalent for all x, x' dom Oh:
5

---

1. f satisfies (RS).
2. f satisfies the inequality f(x) < f(=') (Vf(=))) x') (D(z,x)) L (2x,
3. f satisfies the inequality (Vf(x) Vf(='),--r)
(()',x))
close variant Proposition appears in [7, 10, 29]. so we do not prove it here. Instead, we discuss below different extension of (LS) that turns out to be special case of (RS).
Example 3 (Metric smoothhess). Similar in spirit to (RLC), Antonakopoulos et al. [3] introduced an extension of (LS) that replaces the global norm |I-Il with local norm ||-11 I E Xg In particular, given such a norm, we say that f is metrically smooth (relative to ||-11z) if
[V(x) V fa)) S - -''l=>''|l> for all x' E dom Of
(MS)
An observation that seems have been overlooked by [3] that (MS) (RS), (RS) is more general. We prove this observation in the appendix.
3.4. More examples. Some concrete examples of problems satisfying (RC), (RS) or both (but not
their Euclidean counterparts) are Fisher markets [10, 43], Poisson inverse problems [2, 7], support vector machines [28, 49], D-design [11, 29]. etc. Because of space constraints, we do not detail these examples here; however, we provide an in-depth presentation of a Fisher market model in the appendix, along with a series of numerical experiments used to validate the analysis to come.
4 Adaptive mirror descent
We are now a position to define the proposed adaptive mirror descent (ADAMIR) method. In abstract recursive form, ADAMIR follows the basic mirror descent template
= Pa(-~99)
(MD)
where P is a generalized Bregman proximal operator induced by h (see below for the detailed definition), is search direction determined by a (sub)gradient of at x. and 7 >> 0 is step-size parameter. We discuss these elements in detail below, starting with the prox-mapping P.
4.1. The prox-mapping. Given a Bregman function h, its induced prox-mapping is defined as
(v) = arg ming (oex(((,,, (1, x') + D(I',))) for all x E dom Ôh, v V*, (4)
where D(x', æ) denotes the Bregman divergence of h. Of course, in order for (4) to be well- the arg min must be attained dom Oh. Indeed, we have:
Proposition 2. The recursion (MD) satisfies x+ E dom for all dom Öh and all E V".
To streamline our discussion, we postpone the proof of Proposition 2 the supplement. For now, we only note that it implies that the abstract recursion (MD) is well-posed, i.e., it can be iterated for all t 1,2,... to generate a sequence X, E X.
4.2. The method's step-size. The next important element of (MD) the method's step-size. In the unconstrained case, popular adaptive choice is the so-called -invers--sum-o--saeee policy
= / E
(x()) \
(5)
where X, is the series of iterates produced by the algorithm. However, in relatively continuous/smooth problems, this definition encounters two crucial issues. First, because the gradient of f is unbounded (even over a bounded domain), the denominator of (5) may grow an uncontrollable rate, leading to a step-size policy that vanishes too fast to be of any practical use. The second is that, if the problem is constrained, the extra terms entering the denominator of 7/ do vanish the algorithm approaches a solution, so the (5) may still be unable to exploit the smoothness of the objective.
We begin by addressing the second issue. In the Euclidean case, the key observation is that the difference ||a - xIl must always vanish near a solution (even near the boundary), so we can use it as proxy for Vf(x)) in constrained problems. This idea is formalized by the notion of the gradient mapping [37] that can be defined here as
1 xl1/7.
(6)

---

On the other hand, in a Bregman setting. the prox-mapping tends to deflate gradient steps, so the norm difference between two successive iterates x and z of (MD) could be very small relative the oracle signal that was used to generate the update. As result, the Euclidean residual (6) could lead to disproportionately large step-size that would be harmful for convergence. For this reason, we consider a gradient mapping that takes into account the Bregman geometry of the method and we set
8 = + ,(=*,x)/7
(7)
we readily recover the definition of the Euclidean gradient mapping (6). In general however, by the strong convexity of h, the value of this "Bregman residual" exceeds the corresponding Euclidean definition, so the induced step-size exhibits smoother variations that are more adapted to the framework in hand.
Obviously, when h(x) (1/2)|[z)] |
4.3. The ADAMIR algorithm. We are finally in position to put everything together and define the adaptive mirror descent (ADAMIR) method. In this regard, combining the abstract template (MD) with the Bregman residual and "inverse-sum" sum-of--------o----oo saree--ssmooo----ua-ae -fuar-r-ss-uss""" approach discussed above, we will consider the recursive policy
X(+1 = (x,(-799)
(8)
with gt, 1,,,.... coming from generic oracle model of the form (SFO), and with 7r defined as
with 8 D(X,, X.+1) + D(X x+11 X.)
7t
(ADAMIR)
7
In the sequel, we will use the term "ADAMIR" to refer interchangeably to the update X, < X++11 and the specific step-size policy used within. The convergence properties of ADAMIR are discussed in detail in the next two sections (in both deterministic and stochastic problems); in the supplement, we also perform a numerical validation of the method in the context of Fisher market model.
5 Deterministic analysis and results
We now in position to state main convergence results for ADAMIR. We begin with the deterministic analysis (a = 0), treating both the method's "time-average" as well as the induced trajectory of query points; the analysis for the stochastic case (o 0) is presented in the next section.
5.1. Ergodic convergence and rate interpolation. We begin with the convergence of the method's averrged" state, i.., Xy = (1/T) Σi=1 Xt.
Theorem 1. Let X,, t == 1, 2... denote the sequence of iterates generated by ADAMIR, and let D1 = D(x", X1). Then, ADAMIR simultaneously enjoys the following guarantees:
1. I satisfies (RC), we have:
((Xr) min S + + log 2G2T/88)) 3/2G + 4G /
(9)
VT
T
2. If satisfies (RS), we have f(XT) min ODDITT)
If satisfies (RS) and (RC), we have:
1(8r) - -xin) f < [((x)) - min f
8G2
4L
2
D T
2
+ 2 log
L
(10)
o3
Theorem shows that, up to logarithmic factors, ADAMIR achieves the min-max optimal bounds for functions in the RC' U RS oracle complexity class.* The starting point of the proof (which we detail the supplement), is the following regret bound:
Proposition 3. With notation as in Theorem 1, ADAMIR enjoys the regret bound
D1 Einio
Σ(((x) f(x)))
TT +
Σ 2
(11)
PT
WWe recall here that, in contrast to (LS), the O(1/l) rate is optimal in (RS), ef. Dragomir al. [17].
7

---

The proof of Proposition hinges on the specific definition of ADAMIR's step-size, and the exact functional form of the regret bound (11) plays a crucial role the sequel. Specifically, under the regularity conditions (RC) and (RS), we respectively obtain the following key lemmas:
Lemma 1. Under (RC), the sequence of the Bregman residuals óe of ADAMIR is bounded as 63 & 2G for all 2
Lemma 2. Under (RS), the sequence of the Bregman residuals òt of ADAMIR is square-summable ie. Σ, o7 < oc. Consequently, the method's 's step-size converges to a strictly positive limit "oo0 > O.
As we explain below, the boundedness estimate of Lemma 1 is necessary to show that the iterates of the method do not explode; however, without further assumptions, it is not possible to sharpen this bound. The principal technical difficulty and an important novelty of our analysis is the stabilization of the step-size to a strictly positive limit in Lemma 2. This property of ADAMIR plays a crucial role because the method is not slowed down near a solution. To the best of our knowledge, there is no comparable result for the step-size of parameter-agnostic methods in the literature.
Armed with these two lemmas, we obtain the following series of estimates:
1. Under (RC), the terms in the RHS of (11) can be bounded respectively O(GVT), (Iog(G*T))TT) and OTG As result, we obtain an Ö(IvVT) rate of convergence.
2. Under (RS), all terms in the RHS of (11) can be bounded as (1), so we obtain an O(1TT) convergence rate for Xr.
For the details of these calculations (including the explicit constants and logarithmic terms that appear in the statement of Theorem 1), we refer the reader to the supplement.
5.2. Other modes of convergence. In complement to the analysis above, we provide below a spinoff" result for the method's "last iterate", i.e., the actual trajectory of queried points. The formal statement is as follows.
Theorem 2. Suppose that f satisfies (RC) or (RS). Then X, converges to arg min f.
The main idea of the proof (which we detail in the appendix) consists of two steps. The first key step is to show that, under (RC) U (RS), the iterates of ADAMIR have lim inf f(x)) = min f: we show this in Proposition C.I. Now, given the existence of a convergent subsequence, the rest of our proof strategy branches out depending on whether of satisfies (RC) or (RS). Under (RS), the analysis relies on arguments that involve quasi-Fejér argument as in [12, 16]. However, under (RC), the quasi-Fejér property fails, so we prove the convergence of X, via a novel induction argument that shows that the method's iterates remain trapped within a Bregman neighborhood of x if they enter it with sufficiently small step-size; we provide the relevant details in the supplement.
We close this section with two remarks on non-convex objectives. First, Theorem 2 applies verbatim to non-convex functions satisfying the "secant inequality" [12, 32, 33, 50]
Non-convex objectives.
inf (nV(((())), x x²); x² arg f, KC} > 0
(SI)
for every closed subset K of X' that is separated by neighborhoods from arg min f. In the supplement, our results have all been derived based on this more general condition (it is straightforward to verify that (SI) always holds for convex functions).
Even more generally, Lemma 2 also allows us to derive results for general non-convex problems. Indeed, the proof of Proposition shows that minigesT 57 = (1/TT) without requiring any
'The only comparable result that we are aware of in the literature is Lemma 3.2 of [6] which, however. concerns a mirror- prox algorithm with two gradient queries per iteration, functions with bounded gradients, and a step-size defined in terms of global norm. The specific bound of Lemma I is only possible thanks to the exact form of "/: since the gradient of can become arbitrarily large in terms of glohal norms, bounding & would not have heen possible otherwise.
In more detail, Levy et al. [26], Li and Orabona [27] and Kavis et al. [24] establish the summability of a suitable residual sequence to sharpen the O(Iv/T) rate their respective contexts, but this does not translate to a step-size stabilization result. Under (RCV(RS), controlling the method's step-size is of vital importance because the gradients that enter the algorithm may be unbounded even over a bounded domain: this crucial difficulty does not arise any of the previous works adaptive methods for ordinary Lipschitz problems.
8

---

properties on f other than relative smoothness. As a result, we conclude that the "best iterate" of the method i.e., the iterate with the least residual decays as OL1/T). This fact partially generalizes similar result obtained in [27, 46] for ADAGRAI AD applied to non-convex problems; however, an in-depth discussion of this property would take us too far afield, so we do not attempt
Stochastic analysis
In this last section, we focus on the stochastic case (o 0). Our main results here are as follows.
Theorem 3. Let Xs, 1. = 1, ......., denote the sequence of iterates generated by ADAMIR, and let D1 D(x", X1) and G. = G (G+o/vR Then, under (RC), we have
[f(x)) - s (D1 (Dr+ + HNV % + 2G
(12)
T
where = /6 + log(1 (1 + /
Finally, if (RS) kicks in, we have the sharper guarantee:
Theorem 4. With notation as above, if satisfies (RS), ADAMIR enjoys the bound
A
Bo
E[f(Xr) f(x))
H)
(13)
T
VT
where:
a) A = 50 + 2[f(()) min + L(+ / + 2 (log(422/55))
(14a)
b) B V
(14b)
The full proof of Theorems 3 and 4 is relegated to the supplement, but the key steps are as follows:
Step 1: We first show that, under (RC), the method's residuals are bounded as o < 2G (a.s.).
Step With this at hand, the workhorse for our analysis is the following boxing bound for the mean "weighted" regret Σ/= (V)(). X. x²}]:
T Σ N (V - x²) $ D1 +
T
-i((x)-(aa YI
E
S
1=1
(=1
We prove this bound in the supplement, where we also show that B T -m 72
720
Ollog T).
At this point the analysis between Theorems 3 and 4 branches out. First, in the we show that the method's step-size bounded from below as 7/- 2 1/ (63 + 2G the guarantee (12) then follows by the boxing bound. Instead, in the case of Theorem 4, the analysis is more involved and relies crucially on the lower bound Y/ 2 1/(A + Bov't. The bound (13) then follows by combining this lower bound for 7i with the regret boxing bound above.
of Theorem
In the supplement, we also conclude a series of numerical experiments in random Fisher markets that illustrate the method's 's adaptation properties in archetypal non-Lipschitz problem.
7 Fisher markets: A case study
In this last section, we illustrate the convergence properties of ADAMIR in a Fisher equilibrium problem with linear utilities both stochastic and deterministic. Following [40], Fisher market consists of set W (1, (1...., n.) of buyers or players that seek to share set M = {I....,m) m) of m perfectly divisible goods (ad space, CPU/GPU runtime, bandwidth, etc.). The allocation mechanism for these goods follows proportionally fair price-setting rule that is sometimes referred to as a Kelly auction [25]: each player 1, individual budget; for the sake of simplicity,
bids da per unit of the k-th good, up the player's assume that this budget is equal to for all players, so Em Zik Σ for all é 1,..., n. The price of the k-th good is then set to be the sum of the players bids, i.c., Pk EieN Fiki then, each player gets prorated fraction of each good, namely wi Itt/Pk.

---

Value convergence (stochastic; last iterate)
convergence (stochastic; ergodic average)
10.
0.01
0.1
Entropic Descent: sample mean 'n
Patrppc Dosore:: cample
Entropic Descen:: sample minj mux
Entrpic Desornt: sample mir'max
Propoctional Response: simple meom
Propectional Respaise: sample
0.0001
Propoctional Response: sample minymmax
Proportional Response: sample min/mmx
AdaMir sample
0.00
sample
AdaMir. sample min/max
sample
10*
10
Last-iterate convergence
(h) Ergadic convergence
Figure 1: Statistics for the convergence speed of entropic gradient descent, the proportional response algorithm and ADAMIR in stochastic Fisher market with marginal utilities drawn i.i.d. at each epoch. The marked lines the observed means from $ 50 realizations, whereas the shaded represent 95% confidence interval.
As was observed by Shmyrev [43] (and discussed in more detail in the paper's supplement), the equilibrium points of Fisher market can be obtained by solving the convex problem
minimize
F(x;0)=
Σ KEM
Pke log pk
-E
Ju log 0%x
iEN REM
(Opt)
subject to Pk
Tik
Σ
Tik = 1, and Ey 2 0 for all M,iEN,
IEN
KEM
where 6% denotes the marginal utility of the i-th player per unit of the k-th good. Accordingly, if these utilities fluctuate stochastically over time, the corresponding optimization problem involves the mean objective
fxx = [F)
(15)
Because of the logarithmic terms involved, F (and, fortiori, f) cannot be Lipschitz continuous or smooth in the standard sense. However, as was shown by Birnbaum et al. [10], the problem satisfies (RS) over X' {x TR.m "KEM oik }} relative to the negative entropy function h(x)= = Σn Zik log Tak- As result, mirror descent methods based this Bregman function are natural candidates for solving (15).
In Fig. 1, we report the performance of the -ddaaadattive) entropic gradient descent and proportional response algorithms studied by Birnbaum et al. [10], and we compare it the performance of ADAMIR, which consistently outperforms both methods, in terms of both last-iterate and ergodic value convergence rates. We provide a more detailed analysis the paper's supplement.
Concluding remarks
Our theoretical analysis confirms that ADAMIR concurrently achieves optimal rates of convergence in relatively continuous and relatively smooth problems, both stochastic or deterministic, constrained or unconstrained, and without requiring any prior knowledge of the problem's ''s smoothness/continuiy parameters. These appealing properties open the door to several future research directions, especially regarding the method's convergence properties in non-convex problems. The "best-iterate" discussion of Section 5 is first step along the way, but many questions and problems remain open in this direction, especially regarding the convergence the method's "last iterate" in stochastic, non-convex settings. We defer these questions to future work.
10

---

Acknowledgments and Disclosure of Funding
This research was partially supported by the COST Action CA16228 "European Network for Game Theory" (GAMENET) and the French National Research Agency (ANR) in the framework of the "Investissements d' "venir"" program ANRR-55-DEX-002, the LabEx PERSYVAL (ANR- 11-LABX-022-001 MIAI@Grenoble Alpes (ANR-19-P31A-0003), and the grant ALIAS (ANR-19-CF448-0018..)
References
[1] Kimon Antonakopoulos. E. Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror-pre algorithm for variational inequalities with singular operators. In NeurIPS 'I9: Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
[2] Kimon Antonakopoulos, E. Veronica Belmega, and Panayotis Mertikopoulos. Online and stochastic optimization beyond Lipschitz continuity: A Riemannian approach. In ICLR '00 Proceedings of the 2020 International Conference on Learning Representations, 2020.
[3] Kimon Antonakopoulos, E. Veronica Belmega. and Panayotis Mertikopoulls. Adaptive extra-gradient methods for min-max optimization and games. In ICLR '21: Proceedings of the 2021 International Conference on Learning Representations, 2021.
[4] Peter Auer, Nicolò Cesa- Besa-Bianchi, and Claudio Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48-75, 2002.
[5] Waiss Azizian, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. The last-iterate convergence rate of optimistic mirror descent in stochastic variational inequalities. In COLT '11: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[6] Francis Bach and Kfr Yehuda Levy. universal algorithm for variational inequalities adaptive smoothness and noise. COLT 19: Proceedings of the 32nd Annual Conference on Learning Theory, 2019.
[7] Heinz H. Bauschke, Jérôme Bolte, and Mare Teboulle. A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications. Mathematics of Operations Research, 42(2): 330-346 May 2017.
[8] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 317))16771775 2003.
[9] Mario Bertero, Patrizia Boccacci, Gabriele Desiderå, and Giuseppe Vicidomini. Image deblurring with Poisson data: from cells galaxies. Inverse Problems, 25(12): 123006. November 2009.
[10] Benjamin Birbaum, Nikhil R. Devanur, and Lin Xiao, Distributed algorithms via gradient descent for Fisher markets. In EC' 11: Proceedings of the 12th ACM Conference on Electronic Commerce, 2011.
[11] Jérôme Bolte, Shoham Sabach, Mare Teboulle, and Yakov Vaisbourd. First order methods heyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM Journal Optimization, 28(3)2131-2255, 2018
[12] Léon Bottou. Online learning and stochastic approximations. On-line learning in neural networks, 17(9): 142, 1998.
[13] Lev M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200-217, 1967.
[14] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-355 2015.
[15] Gong Chen and Mare Teboulle. Convergence analysis of a proximal-like like minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):538 543, August 1993.
[16] Patrick I.. Combettes. Qujsi-Fejérian analysis of some optimization algorithms. In Dan Butnariu, Yair Censor, and Simeon Reich, editors, Inherently Parallel Algorithms Feasibility and Optimization and Their Applicution, pages 1 115-152. Elsevier, New York, NY, USA, 2001.
[17] Radu-Alexandru Dragomir, Adrien B. Taylor, Alexandre d' Aspremont, and Jérôme Bolte. Optimal complexity and certification of Bregman first-order merthods. https://arxiv org/pdf/ http//ff/9111/1 109.///1118811 pdf, November 2019.
[18] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Leurning Research, 12:2121-2159, 2011.
[19] Pierre Gaillard, Gilles Stoltz, and Tim van Erven. A second-order bound with excess losses. In COLT '4: Proceedings of the 27th Annual Conference Learning Theory, 2014.
11

---

[20] Filipp Hanzely, Peter Richtárik, and Lin Xiao. Accelerated Bregman proximal gradient methods for relatively smooth convex optimization. https://arxiv. org. http//b/s/....///
2018.
[21] Amélie Héliou, Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Online non-convex optimization with imperfect feedback. In NeurlPS '20: Proceedings of the 34th International Conference
on Newrol Information Processing Systems, 2020.
[22] Amélie Héliou. Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Zeroth-order non-convex learning via hierarchical dual averaging. In ICML '21: Proceedings of the 38th International Conference on Machine Learning, 2021.
[23] Anatoli Juditsky, Arkadi Semen Nemirovski, and Claire Tauvel. Solving variational incqualities with stochastic mirxor-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[24] Ali Kavis, Kfir Yehuda Levy, Francis Bach, and Volkan Cevher. UnixGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. In NeurlPS '19 Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
[25] Frank P. Kelly, Aman K. Maulloo, and David K. H. Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Sociery, 49(3):237-2522 March 1998.
[26] Kfrr Yehuda Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and accelera- tion. In Neur!PS '18: Proceedings of the 32nd International Conference of Neural Information Processing Systems, 2018.
[27] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In AISTATS '19: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019.
[28] Haihao Lu. "Relative-continitty" for non-Lipschitz non-smooth convex optimization using stochastic (or deterministic) mirror descent. INFORMS Journal on Optimization, 1(4):288-303, June 2019.
[29] Haihao Lu, Robert M. Freund, and Yurü Nesterov. Relatively-smoot convex optimization by first-order methods and applications. SIAM Journal Optimization. 28(1):333 354, 2018
[30] H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. In COLT I0: Proceedings of the 23rd Annual Conference on Learning Theory, 2010.
[31] Panayotis Mertikopoulos and William H. Sandholm. Riemannian game dynamics. Journal of Economic
Theory, 177:315-364, September 2018
[32] Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173(1-2):465 507, January 2019.
[33] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan- Shean-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR 'I9: Proceedings of the 2019 International Conference on Learning Representations. 2019.
[34] Arkadi Semen Nemirovski and David Berkovich Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, NY, 1983.
[35] Arkadi Semen Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-160, 2009.
[36] Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of convergence (1/Kk²). Proceedings of the USSR Academy of Sciences, (543543-447) 1983.
[37] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Number 87 in Applicd Optimization. Kluwer Academic Publishers, 2004.
[38] Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Progranming, 120 (1):221-259, 2009.
[39] Yurii Nesterov. Universal gradient methods for convex optimization problems. Mathematical Programming. 152(1-2):381444 4044, 2015.
[40] Noam Nisan, Tim Roughgarden, Éva Tardos, and V. V. Vazirani, editors. Algorithumic Game Theory. Cambridge University Press, 2007.
[41] Boris Teodorovich Polyak. Introduction to Optimization. Optimization Software, New York, NY, USA, 1987.
[42] Ralph Tyrelll Rockafellar. Convex Analysis. Princcton University Press, Princeton, NJ, 1970.
[43] Vadim Ivanovich Shmyrev. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. Journal of Applied and Industrial Mathematics, 3:505-518, 2009.
[44] Fedor Stonyakin, Alexander Gasnikov, Alexander Tyurin, Dmitry Pascchnyuk, Artem Agafonov, Pavel Dvurechensky, Darina Dvinskikh, Alexey Kroshnin, and Victorya Piskunova. Inexact model: framework
12

---

for optimization and variational inequalities.
wttp:b//////...... /tb.b///99...0...... 2019.
[45] Mare Teboulle. A simplified view of first order methods for optimization. Mathematical Programming. 170:67- 967,996,22 2018.
[46] Rachel Ward, Xiaoxia Wu, and Léon Bottou. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. In ICML '19: Proceedings of the 36th International Conference on Machine Learning, 2019.
[47] Fang Wu and Li Zhang. Proportional response dynamics leads to market equilibrium. In STOC '07: Proceedings of 39th annual ACM sympositm
Theory of Computing, 2007.
[48] Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11:2543-2596, October 2010.
[49] Yihan Zhou. Victor S. Portella, Mark Schmidt, and Nicholas J. A. Harvey, Regret bounds without Lipschitz contimuity: Online learning with relative Lipschitz losses. In NeurlPS '20: Proceedings the 34th International Conference on Neural Information Prucessing Systems, 2020.
[50] Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen P. Boyd, and Peter W. Glynn. On the convergence of mirror descent beyond stochastic convex programming. SIAM Journal on Optimization, 30(1) 30(1):687-716, 2020.
13


Reviews:
[{"review_id": "d3VPAjb__uT", "reviewer": "Reviewer_xpRJ", "summary": "This paper studies convex minimization problems lacking Lipschitz continuity of the objective and compactness of the feasible set. They assume access to a standard stochastic subgradient oracle with mean-zero noise and bounded variance. The main contribution of the paper is to propose an adaptive method based on Mirror descent and a clever step-size rule that attains optimal convergence rates under several regularity assumptions beyond standard Lipschitz continuity.", "questions": "", "limitations": "", "rating": 8, "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 paper is well-written and easy to follow. It was a pleasure to read. The authors did a good job explaining the problem, the motivating limitations from the literature, and the connections to other methods. The use of examples and the clarifying remarks were very insightful.\n\nThe proposed method combines Mirror descent with a generalized version of the adaptive step-size rule popularized by AdaGrad. The method is simple and somewhat natural. The core innovation is the analysis of these algorithmic solutions under weaker conditions. The theoretical analysis appears to be mathematically sound. However, I did not check all the details.\n\nHere are some points that the authors should address before publication:\n\n- The column \"Order-optimal\" in Table 1 is slightly misleading. This column is not comparable among the rows because the classes of functions are different. Consider dropping the column or including the class explicitly.\n- I would like to see how AdaMir performs against other methods in the literature; the paper would greatly benefit from a few numerical experiments.\n- What does \"partial\" mean in Table 1?\n- L98: adaptiving -> adapting.\n- L121: Move the footnote to the previous sentence where you make the claim.\n- L131: Delete one \"sample.\"\n- L134: Clarify this is the dual norm on V^*.\n- L229: Typo double in the inline equation.\n- L259: It is odd to present all the other statements explicitly and use the big-O notation for this one. Consider writing an explicit bound.\n- L301: I cannot find (SI) defined anywhere. I am assuming you refer to (12)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations were addressed. The paper studies a theoretical question with no direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "RZ1uDMJ6Pf8", "reviewer": "Reviewer_T495", "summary": "The paper proposed an adaptive mirror descent for convex optimization problems where Lipschitz continuity or smoothness may be not available, both deterministic and stochastic settings are discussed.\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": "The paper provides a detailed literature review on the considered problem. The study is well motivated and the results obtained are clearly stated and discussed. \n\nPlease be clear about the $O(1/T^\\alpha) $ convergence rates appeared in the paper. For Nesterov’s accelerated gradient, the $O(1/T^2)$ rate is on the objective function value at the last iterate, while for some other methods mentioned in the paper, $O(1/T^2)$ rate is for ergodic averaged point. \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above for limitations and no negative societal impact.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "OOjEhQCkDRw", "reviewer": "Reviewer_J6WU", "summary": "- In the paper, the authors propose an adaptive parameter agnostic algorithm AdaMir for online and stochastic convex optimization problems.\n- AdaMir is essentially like the popular Adagrad algorithm with Bregman distances involved in controlling the step-size.\n- Their setting involves non-Lipschitz gradients, contrary to the traditional Lipschitz smooth setting. ", "questions": "", "limitations": "", "rating": 5, "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": "Positives:\n- The paper is well written, clear to read and the theory seems to be sound. I did not check the proofs though.\n- Authors provide a good introduction to various concepts involved in the paper, for example, Bregman distances, relative smoothness and many others.\n- AdaMir combines the best of two worlds, adaptive gradient methods and Mirror Descent based methods.\n- In the deterministic setting, the ergodic convergence rates of AdaMir for both RC and RS settings are given in Theorem 1. Notably, optimal rates are obtained in both the settings.\n- The stochastic setting is also considered, for which convergence rates are provided for AdaMir. Brief discussion on non-convex setting is also provided.\n\n\nNegatives:\n- The paper considers many settings which contributed to too much packed content in the paper. I wish authors focussed on just online setting itself, while relegating the stochastic setting to the supplementary material.\n- No experiments were provided in the main paper. I would suggest moving the experiment from the supplement to the main paper.\n- Example 1, 2, 3 can be moved to supplementary material. I think it is better to focus more on the AdaMir algorithm.\n- The authors use a strongly convex $h$, which makes the definition of $\\delta$ not so appealing.\n- In my opinion, the main novelty lies in the definition of $\\delta$ which makes use of two Bregman distance evaluations. However, I think the novelty in the rest of paper is not significant.\n- More discussion on remark starting at line 118 is needed.\n- A closely related work seems to be [45]. I think more discussion on this is needed preferably before just before the AdaMir algorithm. Also, discussion on regret bounds based on Proposition 3 is missing (please refer to [45]).\n- What is the connection of your Definition of a Bregman function to the other standard definition using Legendre functions?\n- There is no numerical evidence for the proposed method.\n\nOther comments:\n- In line 334, change \"eay\" to \"easy\".\n- Typo in equation in line 229.\n", "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": "4"}, "extra_text": {}}, {"review_id": "8a28hy9SJcf", "reviewer": "Reviewer_jyep", "summary": "The paper proposes an adaptive mirror descent method for solving relative smooth optimization problems. The idea of using adaptive stepsize for first-order methods is not new in the literature, but the proposed adaptive stepsize in this paper is new. ", "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": "The paper is well-written and the obtained convergence rate in this paper is nice. My main concern is the well-definedness of the proposed algorithm. Proposition 2 proves that $x^+ \\in dom  \\partial h$ for all $x\\in dom  \\partial h$ and $g\\in \\mathcal V^*$. But it is not clear if $x^+$ belongs to $dom \\partial f$ or not. This is crucial to guarantee the existence of the next $g$.  \n\nSome minor comments:\n\n1. Provide the strongly convex constant $K$ for the examples in lines 157-165.\n2. Typo in (RC) (see line 171): $x\\in dom \\partial h, x' \\in dom h$. \n3. Definition 3: it should be \"relative smooth to $h$\".\n4. Proposition 1: provide where $x$ and $x'$ belong in each inequality. \n5. Section 4.1: is it \"prox-mapping\" or \"prox-gradient/subgradient-mapping\"? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "18"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall the reviewers liked the paper and found the contributions strong enough for NeurIPS. I have read the paper, and while I have an issue with the claim of the authors that their algorithm is adaptive, while it requires the specification of the "smoothing function" h(), I still appreciate the overall technical contribution provided in the analysis and obtained results.

Decision: Accept (Poster)