Adaptive First-Order Methods Revisited: Convex Optimization without Lipschitz Requirements
Year: 2021

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. 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 of problems with singular objectives that cannot be treated with standard first-order methods for Lipschitz continuous/smooth problems – such as Fisher markets, Poisson tomography problems, D-optimal 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 – which we call 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.

heading: 1 Introduction
text: Owing to their wide applicability and flexibility, first-order methods continue to occupy the forefront of research in learning theory and continuous optimization. Their analysis typically revolves around two basic regularity conditions for the problem at hand: (i) Lipschitz continuity of the problem’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 are Θ(1/ √ T ) and Θ(1/T 2) after T gradient queries, and they are achieved by gradient descent and Nesterov’s fast gradient algorithm respectively [36, 37, 48]. By contrast, if the optimizer only has access to stochastic gradients (as is often the case in machine learning and distributed control), the corresponding lower bound is Θ(1/ √ T ) for both classes [14, 34, 37].
This disparity in convergence rates has led to a 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 al. [24]: both algorithms concurrently achieve an O(1/ √ T ) value convergence rate in non-smooth problems, an O(1/T 2) rate in smooth problems, and an O(1/ √ T ) average rate if run with bounded, unbiased stochastic gradients (the smoothness does not affect the rate in this case). In this regard, UNIXGRAD and ACCELEGRAD both achieve a “best of all worlds” guarantee which makes them ideal as off-theshelf solutions for applications where the problem class is not known in advance – e.g., as 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 domain
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
is bounded, the objective function exhibits singularities at the boundary, so it cannot be Lipschitz continuous or smooth. As a 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 et al. [7] and Lu et al. [29], who considered a “Lipschitz-like” gradient continuity condition for problems with singularities.1 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 a 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 an O(1/ √ T ) value convergence rate in relatively continuous problems [2, 28], an O(1/T ) rate in relatively smooth problems [7, 10], and an O(1/ √ T ) average rate if run with stochastic gradients in relatively continuous problems [2, 28]. Importantly, the O(1/T ) rate for relatively smooth problems does not match the O(1/T 2) rate for standard Lipschitz smooth problems: in fact, even though [20] proposed a tentative path towards faster convergence in certain non-Lipschitz problems, Dragomir et al. [17] recently established an Ω(1/T ) lower bound for problems that are relatively-but-not-Lipschitz smooth.
Our contributions. Our aim in this paper is to provide an adaptive, parameter-agnostic method that simultaneously achieves order-optimal rates in the above “non-Lipschitz” framework. By design, the proposed method – which we 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(1/ √ T ) and O(1/T ) for
relatively continuous and relatively smooth problems respectively. 2. When run with stochastic gradients, the method attains anO(1/ √ T ) 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 objective is relatively continuous/smooth; other than that, we assume no prior information on the problem’s regularity class / modulus and/or the oracle model being accessed (deterministic or stochastic).2 The enabling apparatus for these properties is an adaptive step-size policy in the spirit of [6, 18, 30]. However, a major difference – and technical difficulty – is that the relevant definitions cannot be stated in terms of global norms, because the variation of nonLipschitz function explodes at the boundary of the problem’s domain (put differently, gradients may be unbounded even over bounded domains). For this reason, our policy relies on the aggregation of a suitable sequence of “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 a 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 et al. [18] and McMahan and Streeter [30] was recently shown to interpolate between an O(1/ √ T ) and O(1/T ) rate of convergence [26, 27]. More precisely, Li and Orabona [27] showed that a specific, “one-lagbehind” variant of ADAGRAD with prior knowledge of the smoothness modulus achieves an O(1/T )
1This condition was first examined by Birnbaum et al. [10] in the context of Fisher markets. The analysis of Bauschke et al. [7] and Lu et al. [29] is much more general, but several ideas are already present in [10].
2The reference function has to do with the type of gradient singularities that develop at the boundary of the problem’s domain. For example, the Fisher market models that we discuss later in the paper always exhibit Θ(log x) gradient singularities at the boundary, so the appropriate choice for such models is the negative entropy, and this is true whether the specific market model is everywhere differentiable or not. Likewise, Poisson inverse problems always exhibit Θ(1/x) gradient singularities at the boundary of the positive orthant, which means that the log-entropy is the appropriate reference function for such problems.
rate in smooth, unconstrained problems; concurrently, Levy et al. [26] obtained the same rate in a parameter-agnostic context. In either case, ADAGRAD achieves an O(1/ √ T ) 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 ACCELEGRAD [26] and UNIXGRAD [24]: these methods both achieve an O(1/T 2) value convergence rate in Lipschitz smooth problems, and an O(1/ √ T ) rate in stochastic problems with bounded gradient noise. By employing an efficient line-search 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 as 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 relative smoothness modulus, but it does not otherwise interpolate between the relatively smooth and relatively continuous classes. Moreover, GMP requires knowledge of a “domain of interest” containing a solution of the problem; in 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 that are closely related – but not equivalent – to the relatively continuous/smooth setting of our paper. Moreover, neither of these papers covers the stochastic case; to the best of 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 in Table 1 above.

heading: 2 Problem setup and preliminaries
text: Problem statement. Throughout the sequel, we will focus on convex minimization problems of the general form
minimize f(x), subject to x ∈ X . (Opt)
In the above, X is a convex subset of a normed d-dimensional space V ∼= Rd, and f : V → R ∪ {∞} is a proper lower semi-continuous (l.s.c.) convex function with dom f = {x ∈ V : f(x) <∞} = X . Compared to standard formulations, we stress that X is not assumed to be compact, bounded, or even closed. This lack of closedness will be an important feature for our analysis because we are interested in objectives that may develop singularities at the boundary of their domain; for a class of relevant examples of this type, see [1, 2, 7, 9–11, 22, 29, 49] and references therein.
To formalize our assumptions for (Opt), we will write ∂f(x) for the subdifferential of f at x, and X◦ ≡ dom ∂f = {x ∈ X : ∂f(x) ̸= ∅} for the domain of subdifferentiability of f . Formally, elements of ∂f will be called subgradients, and we will treat them throughout as elements of the dual space V∗ of V . By standard results, we have riX ⊆ X◦ ⊆ X , and any solution x∗ of (Opt) belongs to X◦ [42, Chap. 26]; to avoid trivialities, we will make the following blanket assumption.
Assumption 1. The solution set X ∗ ≡ argmin f ⊆ X◦ 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 > 0 such that
|f(x′)− f(x)| ≤ G∥x′ − x∥ for all x, x′ ∈ X . (LC)
2. Lipschitz smoothness: there exists some L > 0 such that
f(x′) ≤ f(x) + ⟨v, x′ − x⟩+ L 2 ∥x′ − x∥2 for all x, x′ ∈ X and all v ∈ ∂f(x). (LS)
Remark. For posterity, we note that the smoothness requirement (LS) does not imply that ∂f(x) is a singleton.3 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)/(LS) 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 a stochastic first-order oracle (SFO) [37]. This means that, at 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 x ∈ X , an SFO is assumed to return a random (dual) vector g(x;ω) ∈ V∗ where ω belongs to some (complete) probability space (Ω,F ,P). In practice, the oracle will be called repeatedly at a (possibly) random sequence of points Xt ∈ X generated by the algorithm under study. Thus, once Xt has been generated at stage t, the oracle draws an i.i.d. sample ωt ∈ Ω and returns the dual vector:
gt ≡ g(Xt;ωt) = ∇f(Xt) + Ut (1) with Ut ∈ V∗ denoting the “measurement error” relative to some selection ∇f(Xt) of ∂f(Xt). In terms of measurability, we will write Ft for the history (natural filtration) of Xt; in particular, Xt is Ft-adapted, but ωt, gt and Ut are not. Finally, we will also make the statistical assumption that
E[Ut | Ft] = 0 and ∥Ut∥2∗ ≤ σ2 for all t = 1, 2, . . . (SFO) where ∥·∥∗ denotes the dual norm on V∗. This assumption is standard in the analysis of parameteragnostic adaptive methods, cf. [6, 24, 26, 46] and references therein. For concreteness, we will refer to the case σ = 0 as deterministic – since, in that case, Ut = 0 for all t. Otherwise, if lim inft∥Ut∥∗ > 0, the noise will be called persistent and the model will be called stochastic.

heading: 3 Relative Lipschitz continuity and smoothness
text: 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 geometry-adapted measure of divergence on X . This is defined as follows: Definition 1. A convex l.s.c. function h : V → R ∪ {∞} is a Bregman function on X , if 1. dom ∂h ⊆ X◦ ⊆ domh. 2. The subdifferential of h admits a continuous selection∇h(x) ∈ ∂h(x) for all x ∈ dom ∂h. 3. h is strongly convex, i.e., there exists some K > 0 such that
h(x′) ≥ h(x) + ⟨∇h(x), x′ − x⟩+ K 2 ∥x′ − x∥2 (2)
for all x ∈ dom ∂h, x′ ∈ dom ∂h. 3For example, the function f : R2 → R with f(x1, 0) = x1 and f(x1, x2) = ∞ for x2 ̸= 0 is perfectly
smooth on its domain (x2 = 0); however, ∂f(x1, 0) = {(1, v2) : v2 ∈ R}, and this set is never a singleton.
The induced Bregman divergence of h is then defined for all x ∈ dom ∂h, x′ ∈ domh as
D(x′, x) = h(x′)− h(x)− ⟨∇h(x), x′ − x⟩. (3)
Remark. The notion of a 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 ∥·∥2.
Then, the Euclidean regularizer on X is defined as h(x) = ∥x∥22/2 and the induced Bregman divergence is the standard square distance D(x′, x) = ∥x′ − x∥22 for all x, x′ ∈ X
• Entropic regularizer: LetX = {x ∈ Rd+ : ∑d
i=1 xi = 1} be the unit simplex of Rd endowed with the L1-norm ∥·∥1. Then, the entropic regularizer on X is h(x) = ∑ i xi log xi and the induced
divergence is the relative entropy D(x′, x) = ∑
i x ′ i log(x ′ i/xi) for all x ′ ∈ X x ∈ riX . • Log-barrier: Let X = Rd++ denote the (open) positive orthant of Rd. Then, the log-barrier on X
is defined as h(x) = − ∑d
i=1 log xi for all x ∈ Rd++. The corresponding divergence is known as the Itakura-Saito divergence and is given by D(x, x′) = ∑d i=1(xi/x ′ i − log(xi/x′i)− 1) [15].
3.2. Relative continuity. With this background in hand, we proceed to discuss how to 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 a recent paper by Zhou et al. [49]: Definition 2. A convex l.s.c. function f : V → R ∪ {∞} is said to be relatively continuous if there exists some G > 0 such that
f(x)− f(x′) ≤ ⟨∇f(x), x− x′⟩ ≤ G √ 2D(x′, x) for all x′ ∈ domh, x ∈ 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 2. ▶ Example 1 (W[f, h] continuity). This notion intends to single out sufficient conditions for the convergence of “proximal-like” methods like mirror descent. Specifically, following Teboulle [45], f is said to be W[f, h]-continuous relative to h on X (read: “f is weakly h-continuous”) if there exists some G > 0 such that, for all t > 0, we have
t⟨∇f(x), x− x′⟩ −D(x′, x) ≤ t 2
2 G2 for all x′ ∈ domh, x ∈ dom ∂h. (W)
By rearranging the above quadratic polynomial in t, we note that its discriminant is ∆ = [⟨∇f(x), x− x′⟩]2 − 2G2D(x′, x), so it is immediate to check that (RC) holds.
▶ Example 2 (Riemann–Lipschitz continuity). Concurrently to the above, Antonakopoulos et al. [2] introduced a Riemann-Lipschitz continuity condition extending (LC) as follows. Let ∥·∥x be a family of local norms on X (possibly induced by an appropriate Riemannian metric), and let ∥v∥x,∗ = max∥x′∥x≤1⟨v, x′⟩ denote the corresponding dual norm. Then, f is Riemann–Lipschitz continuous relative to ∥·∥x if there exists some G > 0 such that:
∥∇f(x)∥x,∗ ≤ G for all x ∈ X . (RLC)
As we show in the paper’s supplement, (RLC) =⇒ (RC) so (RC) is more general in this regard.
3.3. Relative smoothness. As discussed above, the notion of relative smoothness (RS) was introduced by [10] and independently rediscovered by [7, 29]. It is defined as follows: Definition 3. A convex l.s.c. function f : V → R ∪ {∞} is said to be relatively smooth with respect to h 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 are equivalent for all x, x′ ∈ dom ∂h:
1. f satisfies (RS). 2. f satisfies the inequality f(x) ≤ f(x′) + ⟨∇f(x′), x− x′⟩+ LD(x, x′), 3. f satisfies the inequality ⟨∇f(x)−∇f(x′), x− x′⟩ ≤ L [D(x, x′) +D(x′, x)] .
A close variant of Proposition 1 appears in [7, 10, 29], so we do not prove it here. Instead, we discuss below a different extension of (LS) that turns out to be a special case of (RS).
▶ Example 3 (Metric smoothness). Similar in spirit to (RLC), Antonakopoulos et al. [3] introduced an extension of (LS) that replaces the global norm ∥·∥ with a local norm ∥·∥x, x ∈ X◦. In particular, given such a norm, we say that f is metrically smooth (relative to ∥·∥x) if
∥∇f(x)−∇f(x′)∥x,∗ ≤ L∥x− x′∥x′ for all x, x′ ∈ dom ∂f. (MS) An observation that seems to have been overlooked by [3] is that (MS) =⇒ (RS), so (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.

heading: 4 Adaptive mirror descent
text: We are now in a position to define the proposed adaptive mirror descent (ADAMIR) method. In abstract recursive form, ADAMIR follows the basic mirror descent template
x+ = Px(−γg), (MD) where P is a generalized Bregman proximal operator induced by h (see below for the detailed definition), g is a search direction determined by a (sub)gradient of f at x, and γ > 0 is a 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
Px(v) = argminx′∈X {⟨v, x− x′⟩+D(x′, x)} for all x ∈ dom ∂h, v ∈ V∗, (4) where D(x′, x) denotes the Bregman divergence of h. Of course, in order for (4) to be well-defined, the argmin must be attained in dom ∂h. Indeed, we have: Proposition 2. The recursion (MD) satisfies x+ ∈ dom ∂h for all x ∈ dom ∂h and all g ∈ V∗.
To streamline our discussion, we postpone the proof of Proposition 2 to 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 Xt ∈ X .
4.2. The method’s step-size. The next important element of (MD) is the method’s step-size. In the unconstrained case, a popular adaptive choice is the so-called “inverse-sum-of-squares” policy
γt = 1 /√∑t s=1∥∇f(Xs)∥2∗, (5)
where Xt 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 at 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 γt do not vanish as 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 ∥x+ − x∥ must always vanish near a solution (even near the boundary), so we can use it as a proxy for ∇f(x) in constrained problems. This idea is formalized by the notion of the gradient mapping [37] that can be defined here as
δ = ∥x+ − x∥ / γ. (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 x of (MD) could be very small relative to the oracle signal that was used to generate the update. As a result, the Euclidean residual (6) could lead to a 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
δ = √ D(x, x+) +D(x+, x) / γ. (7)
Obviously, when h(x) = (1/2)∥x∥22, 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.
4.3. The ADAMIR algorithm. We are finally in a 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-of-squares” approach discussed above, we will consider the recursive policy Xt+1 = PXt(−γtgt) (8) with gt, t = 1, 2, . . . , coming from a generic oracle model of the form (SFO), and with γt defined as
γt = 1√∑t−1 s=0 δ 2 s
with δ2s = D(Xs, Xs+1) +D(Xs+1, Xs)
γ2s . (ADAMIR)
In the sequel, we will use the term “ADAMIR” to refer interchangeably to the update Xt ← Xt+1 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 a Fisher market model.

heading: 5 Deterministic analysis and results
text: We are now in a position to state our main convergence results for ADAMIR. We begin with the deterministic analysis (σ = 0), treating both the method’s “time-average” as well as the induced trajectory of query points; the analysis for the stochastic case (σ > 0) is presented in the next section.
5.1. Ergodic convergence and rate interpolation. We begin with the convergence of the method’s “time-averaged” state, i.e., X̄T = (1/T ) ∑T t=1 Xt. Theorem 1. Let Xt, 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. If f satisfies (RC), we have:
f(X̄T )−min f ≤ √ 2G
[ D1 + 8G 2/δ20 + 2 log(1 + 2G 2T/δ20) ] √ T + 3 √ 2G+ 4G2/δ20 T . (9)
2. If f satisfies (RS), we have f(X̄T )−min f = O(D1/T ).
3. If f satisfies (RS) and (RC), we have: f(X̄T )−min f ≤ [ f(X1)−min f + ( 2 + 8G2
δ20 + 2 log
4L2
δ20
) L ]2 D1 T . (10)
Theorem 1 shows that, up to logarithmic factors, ADAMIR achieves the min-max optimal bounds for functions in the RC ∪RS oracle complexity class.4 The starting point of the proof (which we detail in the supplement), is the following regret bound: Proposition 3. With notation as in Theorem 1, ADAMIR enjoys the regret bound
T∑ t=1 [f(Xt)− f(x∗)] ≤ D1 γT + ∑T t=1 γ 2 t δ 2 t γT + T∑ t=1 γtδ 2 t . (11)
4We recall here that, in contrast to (LS), the O(1/T ) rate is optimal in (RS), cf. Dragomir et al. [17].
The proof of Proposition 3 hinges on the specific definition of ADAMIR’s step-size, and the exact functional form of the regret bound (11) plays a crucial role in 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 δt of ADAMIR is bounded as δ2t ≤ 2G2 for all t ≥ 1. Lemma 2. Under (RS), the sequence of the Bregman residuals δt of ADAMIR is square-summable, i.e., ∑ t δ 2 t <∞. Consequently, the method’s step-size converges to a strictly positive limit γ∞ > 0.
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.5 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.6
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 as O(G √ T ),
O(log(G2T ) √ T ), and O(G √ T ). As a result, we obtain an Õ(1/ √ T ) rate of convergence.
2. Under (RS), all terms in the RHS of (11) can be bounded as O(1), so we obtain an O(1/T ) convergence rate for X̄T .
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 Xt converges to argmin 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) ∪ (RS), the iterates of ADAMIR have lim inf f(Xt) = min f ; we show this in Proposition C.1. Now, given the existence of a convergent subsequence, the rest of our proof strategy branches out depending on whether f satisfies (RC) or (RS). Under (RS), the analysis relies on arguments that involve a quasi-Fejér argument as in [12, 16]. However, under (RC), the quasi-Fejér property fails, so we prove the convergence of Xt 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 a sufficiently small step-size; we provide the relevant details in the supplement.
Non-convex objectives. 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]
inf{⟨∇f(x), x− x∗⟩ : x∗ ∈ argmin f, x ∈ K} > 0 (SI)
for every closed subsetK of X that is separated by neighborhoods from argmin 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 1 shows that min1≤t≤T δ2t = O(1/T ) without requiring any
5The 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 a global norm. The specific bound of Lemma 1 is only possible thanks to the exact form of γt: since the gradient of f can become arbitrarily large in terms of global norms, bounding δt would not have been possible otherwise.
6In 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(1/ √ T ) rate in their respective contexts, but this does not translate to a step-size stabilization result. Under (RC)/(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 in any of the previous works on adaptive methods for ordinary Lipschitz problems.
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 O(1/T ). This fact partially generalizes a similar result obtained in [27, 46] for ADAGRAD applied to non-convex problems; however, an in-depth discussion of this property would take us too far afield, so we do not attempt it.

heading: 6 Stochastic analysis
text: In this last section, we focus on the stochastic case (σ > 0). Our main results here are as follows. Theorem 3. Let Xt, t = 1, 2, . . . , denote the sequence of iterates generated by ADAMIR, and let D1 = D(x ∗, X1) and Gσ = G+ σ/ √ K. Then, under (RC), we have
E [ f(X̄T )− f(x∗) ] ≤ (D1 +H) √ δ20 + 2G 2 σ
T (12)
where H = 8G2σ/δ 2 0 + 2 log(1 + 2G 2 σT/δ 2 0).
Finally, if (RS) kicks in, we have the sharper guarantee: Theorem 4. With notation as above, if f satisfies (RS), ADAMIR enjoys the bound
E[f(X̄T )− f(x∗)] ≤ (2 +D1 +H) [ A
T + Bσ√ T
] (13)
where: a) A = δ0 + 2[f(X1)−min f ] + L ( 2 + 8G2σ / δ20 + 2 log(4L 2/δ20) ) . (14a)
b) B = √ (4 + 2H)/K. (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 δ2t ≤ 2G2σ (a.s.). Step 2: With this at hand, the workhorse for our analysis is the following boxing bound for the mean
“weighted” regret ∑T
t=1 E[γt⟨∇f(Xt), Xt − x∗⟩]:
E [ γT
T∑ t=1 [f(Xt)− f(x∗)]
] ≤ E [ T∑
t=1
γt⟨∇f(Xt), Xt − x∗⟩ ] ≤ D1 + E [ T∑
t=1
γ2t δ 2 t ] We prove this bound in the supplement, where we also show that E[ ∑T t=1 γ 2 t δ 2 t ] = O(log T ).
At this point the analysis between Theorems 3 and 4 branches out. First, in the case of Theorem 3, we show that the method’s step-size is bounded from below as γt ≥ 1/ √ (δ20 + 2G 2 σ)t; 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 γt ≥ 1/(A+Bσ √ t). The bound (13) then follows by combining this lower bound for γt with the regret boxing bound above.
In the supplement, we also conclude a series of numerical experiments in random Fisher markets that illustrate the method’s adaptation properties in an archetypal non-Lipschitz problem.

heading: 7 Fisher markets: A case study
text: 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], a Fisher market consists of a setN = {1, . . . , n} of n buyers – or players – that seek to share a setM = {1, . . . ,m} of m perfectly divisible goods (ad space, CPU/GPU runtime, bandwidth, etc.). The allocation mechanism for these goods follows a proportionally fair price-setting rule that is sometimes referred to as a Kelly auction [25]: each player i = 1, . . . , n bids xik per unit of the k-th good, up the player’s individual budget; for the sake of simplicity, we assume that this budget is equal to 1 for all players, so ∑m k=1 xik ≤ 1 for all i = 1, . . . , n. The price of the k-th good is then set to be the sum of the
players’ bids, i.e., pk = ∑
i∈N xik; then, each player gets a prorated fraction of each good, namely wik = xik/pk.
As was observed by Shmyrev [43] (and discussed in more detail in the paper’s supplement), the equilibrium points of a Fisher market can be obtained by solving the convex problem
minimize F (x; θ) ≡ ∑ k∈M pk log pk − ∑ i∈N ∑ k∈M xik log θik
subject to pk = ∑ i∈N xik, ∑ k∈M xik = 1, and xik ≥ 0 for all k ∈M, i ∈ N , (Opt)
where θik 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
f(x) = E[F (x;ω)]. (15)
Because of the logarithmic terms involved, F (and, a 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 ∈ Rnm+ : ∑ k∈M xik = 1} relative to the negative entropy function
h(x) = ∑
ik xik log xik. As a result, mirror descent methods based on this Bregman function are natural candidates for solving (15).
In Fig. 1, we report the performance of the (non-adaptive) entropic gradient descent and proportional response algorithms studied by Birnbaum et al. [10], and we compare it to 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 in the paper’s supplement.

heading: 8 Concluding remarks
text: 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 smoothness/continuity 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 a first step along the way, but many questions and problems remain open in this direction, especially regarding the convergence of the method’s “last iterate” in stochastic, non-convex settings. We defer these questions to future work.
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’avenir” program (ANR-15-IDEX-02), the LabEx PERSYVAL (ANR-11-LABX-0025-01), MIAI@Grenoble Alpes (ANR-19-P3IA-0003), and the grant ALIAS (ANR-19-CE48-0018-01).

Review summaries:
- In the paper, the authors propose an adaptive parameter agnostic algorithm AdaMir for online and stochastic convex optimization problems. - AdaMir is essentially like the popular Adagrad algorithm with Bregman distances involved in controlling the step-size. - Their setting involves non-Lipschitz gradients, contrary to the traditional Lipschitz smooth setting. 

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.