# THE LAST-ITERATE CONVERGENCE RATE OF OPTIMISTIC MIRROR DESCENT IN STOCHASTIC
VARIATIONAL INEQUALITIES

Waïss Azizian∗ ∗ DI, ENS, Univ. PSL, 75005, Paris, France
<EMAIL_ADDRESS>,  Franck Iutzeler† † Univ. Grenoble Alpes, LJK,
Grenoble, 38000, France<EMAIL_ADDRESS>,
Jérôme Malick‡ ‡ Univ. Grenoble Alpes, CNRS, Grenoble INP, LJK, 38000
Grenoble, France<EMAIL_ADDRESS>and  Panayotis
Mertikopoulos♯ ♯ Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000,
Grenoble, France.  ⋄ Criteo AI Lab<EMAIL_ADDRESS>
###### Abstract.

In this paper, we analyze the local convergence rate of optimistic mirror
descent methods in stochastic variational inequalities, a class of
optimization problems with important applications to learning theory and
machine learning. Our analysis reveals an intricate relation between the
algorithm’s rate of convergence and the local geometry induced by the method’s
underlying Bregman function. We quantify this relation by means of the
_Legendre exponent_ , a notion that we introduce to measure the growth rate of
the Bregman divergence relative to the ambient norm near a solution. We show
that this exponent determines both the optimal step-size policy of the
algorithm and the optimal rates attained, explaining in this way the
differences observed for some popular Bregman functions (Euclidean projection,
negative entropy, fractional power, etc.).

###### Key words and phrases:

Legendre exponent; optimistic mirror descent; variational inequalities

###### Key words and phrases:

Variational inequalities; optimistic mirror descent; Legendre exponent

###### 2020 Mathematics Subject Classification:

Primary 65K15, 90C33; secondary 68Q25, 68Q32.

##  1\. Introduction

Variational inequalities – and, in particular, _stochastic_ variational
inequalities – have recently attracted considerable attention in machine
learning and learning theory as a flexible paradigm for “optimization beyond
minimization” – i.e., for problems where finding an optimal solution does not
necessarily involve minimizing a loss function. In this context, our paper
examines the local rate of convergence of _optimistic mirror descent_ (OMD), a
state-of-the-art algorithmic template for solving variational inequalities
that incorporates an “optimistic” look-ahead step with a “mirror descent”
apparatus relying on a suitably chosen Bregman kernel. Our contributions focus
exclusively on the stochastic case, which is of central interest to learning
theory. To put them in context, we begin with a general overview below and
discuss more specialized references in Section 5.

#### General overview.

Algorithms for solving variational inequalities have a very rich history in
optimization that goes back at least to the original proximal point algorithm
of Martinet (1970) and Rockafellar (1976); for a survey, see Facchinei & Pang
(2003). At a high level, if the vector field defining the problem is bounded
and strictly monotone, simple forward-backward schemes are known to converge –
and if combined with a Polyak–Ruppert averaging scheme, they achieve an
$\mathcal{O}(1/\sqrt{t})$ rate of convergence without the strictness caveat
(Bruck Jr., 1977, Passty, 1979, Nesterov, 2009, Bauschke & Combettes, 2017).
If, in addition, the problem’s defining vector field is Lipschitz continuous,
the extra-gradient (EG) algorithm of Korpelevich (1976) achieves trajectory
convergence without strict monotonicity requirements, while the method’s
ergodic average converges at a $\mathcal{O}(1/t)$ rate (Nemirovski, 2004,
Nesterov, 2007). Finally, if the problem is _strongly_ monotone, forward-
backward methods achieve an $\mathcal{O}(1/t)$ convergence speed; and if the
operator is also Lipschitz continuous, classical results in operator theory
show that simple forward-backward methods suffice to achieve a linear
convergence rate (Facchinei & Pang, 2003, Bauschke & Combettes, 2017).

The stochastic version of the problem arises in two closely related and
interconnected ways: the defining operator could have itself a stochastic
structure, or the optimizer could only be able to access a stochastic estimate
thereof. Here, the landscape is considerably different: For VI problems with a
monotone operator, the stochastic version of the EG algorithm achieves an
ergodic $\mathcal{O}(1/\sqrt{t})$ convergence rate (Juditsky et al., 2011,
Gidel et al., 2019). On the other hand, if the problem is _strongly_ monotone,
this rate improves to $\mathcal{O}(1/t)$ and it is achieved by simple forward-
backward methods, with or without averaging (Nemirovski et al., 2009).

In this context, the optimistic mirror descent algorithm has been designed to
meet two complementing objectives:  (it n) improve the dependence of the above
rates on the problem’s dimensionality in cases with a favorable geometry; and
(it n) minimize the number of oracle queries per iteration.  The first of
these objectives is achieved by the “mirror descent” component: by employing a
suitable _distance-generating function_ (DGF) – like the negative entropy on
the simplex or the log-barrier on the orthant) – mirror descent achieves
convergence rates that are (almost) dimension-free in problems with a
favorable geometry. This idea dates back to Nemirovski & Yudin (1983), and it
is also the main building block of the mirror-prox (MP) algorithm which
achieves order-optimal rates with two oracle queries per iteration
(Nemirovski, 2004).

The “optimistic” module then clicks on top of the MD/MP template by replacing
one of the two operator queries by already observed information. This
“information reuse” idea was originally due to Popov (1980), and it has
recently resurfaced several times in learning theory, cf. Chiang et al.
(2012), Rakhlin & Sridharan (2013b, a), Daskalakis et al. (2018), Gidel et al.
(2019), Hsieh et al. (2019, 2021), and references therein. However, the
quantitative behavior of the last-iterate in such mirror methods still remains
an open question.

#### Our contributions.

In view of the aove, the aim of our paper is to examine the local convergence
rate of optimistic mirror descent (OMD) in stochastic VI problems. For
generality, we focus on non-monotone VIs, and we investigate the algorithm’s
convergence to local solutions that satisfy a second-order sufficient
condition.

In this regard, our first finding is that the algorithm’s rate of convergence
depends sharply on the local geometry induced by the method’s underlying
Bregman function. We formalize this by introducing the notion of the _Legendre
exponent_ , which can roughly be described as the logarithmic ratio of the
volume of a regular ball w.r.t. the ambient norm centered at the solution
under study to that of a Bregman ball of the same radius. For example, the
ordinary Euclidean version of OMD has a Legendre exponent of $\beta=0$; on the
other hand, the entropic variant has a Legendre exponent of $\beta=1/2$ on
boundary points.

We then obtain the following rates as a function of $\beta$:

$\mathcal{O}\left(t^{-(1-\beta)}\right)~{}\text{ if
}~{}0\leq\beta<1/2\qquad\text{and}\qquad\mathcal{O}\left(t^{-\frac{1-\varepsilon}{2\beta}(1-\beta)}\right)~{}\text{
if }~{}1/2\leq\beta<1$ (1)

for arbitrarily small $\varepsilon>0$. Interestingly, these guarantees undergo
a first-order phase transition between the Euclidean-like phase
($0\leq\beta<1/2$) and the entropy-like phase ($1/2\leq\beta<1$). This
coincides with the dichotomy between steep and non-steep distance-generating
functions (i.e., DGFs that are differentiable only on the interior of the
problem’s domain versus those that are differentiable throughout). Moreover,
these rate guarantees are reached for different step-size schedules,
respectively $\gamma_{t}=\Theta(1/t^{1-\beta})$ and
$\Theta(1/t^{(1-\varepsilon)/2})$, also depending on the Legendre exponent.

To the best of our knowledge, the only comparable result in the literature is
the recent work of Hsieh et al. (2019) that derives an $\mathcal{O}(1/t)$
convergence rate for the Euclidean case (i.e., when $\beta=0$). Along with
some other recent works on optimistic gradient methods, we discuss this in
detail in Section 5, after the precise statement of our results.

##  2\. Problem setup and preliminaries

#### Problem formulation, examples, and blanket assumptions.

Throughout what follows, we will focus on solving (Stampacchia) variational
inequalities of the general form:

$\text{Find $x^{\ast}\in\mathcal{K}$ such that}\;\;\langle
v(x^{\ast}),x-x^{\ast}\rangle\geq 0\;\;\text{for all $x\in\mathcal{K}$}.$ (VI)

In the above, $\mathcal{K}$ is a closed convex subset of a $d$-dimensional
real space $\mathcal{X}$ with norm $\lVert\cdot\rVert$, $\langle y,x\rangle$
denotes the canonical pairing between $y\in\mathcal{Y}$ and $x\in\mathcal{X}$,
and the _defining vector field_ $v\colon\mathcal{K}\to\mathcal{Y}$ of the
problem is a single-valued operator with values in the dual space
$\mathcal{Y}\coloneqq\mathcal{X}^{\ast}$ of $\mathcal{X}$. Letting $\lVert
y\rVert_{\ast}\coloneqq\max\\{\langle y,x\rangle:\lVert x\rVert\leq 1\\}$
denote the induced dual norm on $\mathcal{Y}$, we will make the following
blanket assumption for $v$.

######  Assumption 1 (Lipschitz continuity).

The vector field $v$ is _$L$ -Lipschitz continuous_, i.e.,

$\lVert v(x^{\prime})-v(x)\rVert_{\ast}\leq L\lVert
x^{\prime}-x\rVert\quad\text{for all $x,x^{\prime}\in\mathcal{K}$}.$ (LC)

For concreteness, we provide below some archetypal examples of VI problems.

######  Example 2.1.

Consider the minimization problem

$\displaystyle\textrm{minimize}_{x\in\mathcal{K}}$ $\displaystyle\quad f(x)$
(Min)

with $f\colon\mathcal{K}\to\mathbb{R}$ assumed $C^{1}$-smooth. Then, letting
$v(x)=\nabla f(x)$, the solutions of (VI) are precisely the Karush–Kuhn–Tucker
(KKT) points of (Min), cf. Facchinei & Pang (2003). $\lozenge$

######  Example 2.2.

A _saddle-point_ – or _min-max_ – problem can be stated, in normal form, as

$\min_{x_{1}\in\mathcal{K}_{1}}\max_{x_{2}\in\mathcal{K}_{2}}\,\Phi(x_{1},x_{2})$
(SP)

where $\mathcal{K}_{1}\subseteq\mathbb{R}^{d_{1}}$ and
$\mathcal{K}_{2}\subseteq\mathbb{R}^{d_{2}}$ are convex and closed, and the
problem’s objective function
$\Phi\colon\mathcal{K}_{1}\times\mathcal{K}_{2}\to\mathbb{R}$ is again assumed
to be smooth. In the game-theoretic interpretation of von Neumann (1928),
$x_{1}$ is controlled by a player seeking to minimize $\Phi(\cdot,x_{2})$,
whereas $x_{2}$ is controlled by a player seeking to maximize
$\Phi(x_{1},\cdot)$. Accordingly, solving (SP) consists of finding a _min-max
point_
$(x_{1}^{\ast},x_{2}^{\ast})\in\mathcal{K}\coloneqq\mathcal{K}_{1}\times\mathcal{K}_{2}$
such that

$\Phi(x_{1}^{\ast},x_{2})\leq\Phi(x_{1}^{\ast},x_{2}^{\ast})\leq\Phi(x_{1},x_{2}^{\ast})\quad\text{for
all $x_{1}\in\mathcal{K}_{1}$, $x_{2}\in\mathcal{K}_{2}$}.$ (MinMax)

Min-max points may not exist if $\Phi$ is not convex-concave. In this case,
one looks instead for first-order stationary points of $\Phi$, i.e., action
profiles $(x_{1}^{\ast},x_{2}^{\ast})\in\mathcal{K}_{1}\times\mathcal{K}_{2}$
such that $x_{1}^{\ast}$ is a KKT point of $\Phi(\cdot,x_{2}^{\ast})$ and
$x_{2}^{\ast}$ is a KKT point of $-\Phi(x_{1}^{\ast},\cdot)$. Letting
$x=(x_{1},x_{2})$ and $v=(\nabla_{x_{1}}\Phi,-\nabla_{x_{2}}\Phi)$, we see
that the solutions of (VI) are precisely the first-order stationary points of
$\Phi$. $\lozenge$

The above examples show that not all solutions of (VI) are desirable: for
example, such a solution could be a local _maximum_ of $f$ in the case of
(Min) or a max-min point in the case of (MinMax). For this reason, we will
concentrate on solutions of (VI) that satisfy the following second-order
condition:

######  Assumption 2 (Second-order sufficiency).

For a solution $x^{\ast}$ of (VI), there exists a neighborhood $\mathcal{B}$
and a positive constant $\mu>0$ such that

$\langle v(x),x-x^{\ast}\rangle\geq\mu\lVert
x-x^{\ast}\rVert^{2}\quad\text{for all $x\in\mathcal{B}$}.$ (SOS)

In the context of (Min), Assumption 2 implies that $f$ grows (at least)
quadratically along every ray emanating from $x^{\ast}$; in particular, we
have $f(x)-f(x^{\ast})\geq\langle\nabla
f(x^{\ast}),x-x^{\ast}\rangle+(\mu/2)\lVert x-x^{\ast}\rVert^{2}=\Omega(\lVert
x-x^{\ast}\rVert^{2})$ for all $x\in\mathcal{B}$ (though this does not mean
that $f$ is strongly convex in $\mathcal{B}$). Likewise, in the context of
(MinMax), Assumption 2 gives $\Phi(x_{1},x_{2}^{\ast})=\Omega(\lVert
x_{1}-x_{1}^{\ast}\rVert^{2})$ and $\Phi(x_{1}^{\ast},x_{2})=-\Omega(\lVert
x_{2}-x_{2}^{\ast}\rVert^{2})$, so $x^{\ast}$ is a local Nash equilibrium of
$\Phi$. In general, Assumption 2 guarantees that $x^{\ast}$ is the unique
solution of (VI) in $\mathcal{B}$. (Indeed, any other solution $\hat{x}\neq
x^{\ast}$ of (VI) would satisfy $0\geq\langle
v(\hat{x}),\hat{x}-x^{\ast}\rangle\geq\mu\lVert\hat{x}-x^{\ast}\rVert^{2}>0$,
a contradiction.)

##  3\. The optimistic mirror descent algorithm

In this section, we recall the _optimistic mirror descent_ (OMD) method for
solving (VI). To streamline the flow of our paper, we first discuss the type
of feedback available to the optimizer.

###  3.1. The oracle model

OMD is a first-order method that only requires access to the problem’s
defining vector field via a “black-box oracle” that returns a (possibly
imperfect) version of $v(x)$ at the selected query point $x\in\mathcal{K}$.
Concretely, we focus on _stochastic first-order oracles_ of the form

$\displaystyle\operatorname{\mathsf{V}}(x;\theta)$
$\displaystyle=v(x)+\operatorname{\mathsf{Err}}(x;\theta)$ (SFO)

where $\theta$ is a random variable taking values in some abstract measure
space $\Theta$ and $\operatorname{\mathsf{Err}}(x;\theta)$ is an umbrella
error term capturing all sources of uncertainty in the model.

In practice, the oracle is called repeatedly at a sequence of query points
$X_{t}\in\mathcal{K}$ with a different random seed $\theta_{t}$ at each
time.111In the sequel, we will allow the index $t$ to take both integer and
half-integer values. The sequence of oracle signals
$V_{t}=\operatorname{\mathsf{V}}(X_{t};\theta_{t})$ may then be written as

$V_{t}=v(X_{t})+U_{t}$ (2)

where $U_{t}=\operatorname{\mathsf{Err}}(X_{t};\theta_{t})$ denotes the error
of the oracle model at stage $t$. To keep track of this sequence of events, we
will treat $X_{t}$ as a stochastic process on some complete probability space
$(\Omega,\mathcal{F},\operatorname{\mathbb{P}})$, and we will write
$\mathcal{F}_{t}\coloneqq\mathcal{F}(X_{1},\dotsc,X_{t})\subseteq\mathcal{F}$
for the _history of play_ up to stage $t$ (inclusive). Since the randomness
entering the oracle is triggered only _after_ a query point has been selected,
we will posit throughout that $\theta_{t}$ (and hence $U_{t}$ and $V_{t}$) is
$\mathcal{F}_{t+1}$-measurable – but not necessarily
$\mathcal{F}_{t}$-measurable. We will also make the blanket assumption below
for the oracle.

######  Assumption 3 (Oracle signal).

The error term $U_{t}$ in (2) satisfies the following properties:

$\displaystyle a)\quad$ Zero-mean:
$\displaystyle\operatorname{\mathbb{E}}[U_{t}\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{t}]=0.$
(3a) $\displaystyle b)\quad$ Finite variance:
$\displaystyle\operatorname{\mathbb{E}}[\lVert
U_{t}\rVert_{\ast}^{2}\nonscript\,|\nonscript\,\mathopen{}\mathcal{F}_{t}]\leq\sigma^{2}.\hskip
170.00026pt$ (3b)

Both assumptions are standard in the literature on stochastic methods in
optimization, cf. Polyak (1987), Hazan (2012), Bubeck (2015), and references
therein.

###  3.2. OMD

With all this in hand, the optimistic mirror descent algorithm is defined in
recursive form as follows:

$\displaystyle X_{t+1/2}$ $\displaystyle=P_{#1}(-\gamma_{t}V_{t-1/2})$ (OMD)
$\displaystyle X_{t+1}$ $\displaystyle=P_{#1}(-\gamma_{t}V_{t+1/2})$

In the above, $t=1,2,\dotsc$, is the algorithm’s iteration counter, $X_{t}$
and $X_{t+1/2}$ respectively denote the algorithm’s _base_ and _leading_
states at stage $t$, $V_{t+1/2}$ is an oracle signal obtained by querying
(SFO) at $X_{t+1/2}$, and $P_{#1}(y)$ denotes the method’s so-called “prox-
mapping”. In terms of initialization, we also take
$X_{1}=X_{1/2}\in\operatorname{ri}\mathcal{K}$ for simplicity. All these
elements are defined in detail below.

At a high level, (OMD) seeks to leverage past feedback to anticipate the
landscape of $v$ and perform more informed steps in subsequent iterations. In
more detail, starting at some base state $X_{t}$, $t=1,2,\dotsc$, the
algorithm first generates an intermediate, leading state $X_{t+1/2}$, and then
updates the base state with oracle input from $X_{t+1/2}$ – that is,
$V_{t+1/2}$. This is also the main idea behind the extra-gradient algorithm of
Korpelevich (1976); the key difference here is that OMD avoids making two
oracle queries per iteration by using the oracle input $V_{t-1/2}$ received at
the previous leading state $X_{t-1/2}$ as a proxy for $V_{t}$ (which is never
requested or received by the optimizer).

The second basic component of the method is the prox-mapping $P$, which,
loosely speaking, can be viewed as a generalized, proximal/projection operator
adapted to the geometry of the problem’s primitives. To define it formally, we
will need the notion of a _distance-generating function_ on $\mathcal{K}$:

######  Definition 1.

A convex lower semi-continuous function
$h\colon\mathcal{X}\to\mathbb{R}\cup\\{\infty\\}$ (with
$\operatorname{dom}h=\mathcal{K}$) is a _distance-generating function_ (DGF)
on $\mathcal{K}$ if

  1. (1)

The subdifferential of $h$ admits a _continuous selection_ , i.e., there
exists a continuous mapping $\nabla h\colon\operatorname{dom}\partial
h\to\mathcal{Y}$ such that $\nabla h(x)\in\partial h(x)$ for all
$x\in\operatorname{dom}\partial h$.

  2. (2)

$h$ is continuous and $1$-strongly convex on $\mathcal{K}$, i.e., for all
$x\in\operatorname{dom}\partial h,x^{\prime}\in\operatorname{dom}h$, we have:

$h(x^{\prime})\geq h(x)+\langle\nabla
h(x),x^{\prime}-x\rangle+\tfrac{1}{2}\lVert x^{\prime}-x\rVert^{2}.$ (4)

For posterity, the set $\mathcal{K}_{h}\coloneqq\operatorname{dom}\partial h$
will be referred to as the _prox-domain_ of $h$. We also define the _Bregman
divergence_ of $h$ as

$\displaystyle D(p,x)$ $\displaystyle=h(p)-h(x)-\langle\nabla
h(x),p-x\rangle,$ for all $p\in\mathcal{K}$, $x\in\mathcal{K}_{h}$ (5) and the
induced _prox-mapping_
$P\colon\mathcal{K}_{h}\times\mathcal{Y}\to\mathcal{K}_{h}$ as $\displaystyle
P_{#1}(y)$
$\displaystyle=\operatorname*{arg\,min}_{x^{\prime}\in\mathcal{K}}\\{\langle
y,x-x^{\prime}\rangle+D(x^{\prime},x)\\}$ $\displaystyle\text{for all
$x\in\mathcal{K}_{h}$, $y\in\mathcal{Y}$}.$ (6)

In the rest of this section we take a closer look at some commonly used DGFs
and the corresponding prox-mappings; for simplicity, we focus on one-
dimensional problems on $\mathcal{K}=[0,1]$.

######  Example 3.1 (Euclidean projection).

For the quadratic DGF $h(x)=x^{2}/2$ for $x\in\mathcal{K}$, the Bregman
divergence is $D(p,x)=(p-x)^{2}/2$ and the induced prox-mapping is the
Euclidean projector $\displaystyle P_{#1}(y)=[x+y]_{0}^{1}$. The prox-domain
of $h$ is the entire feasible region, i.e.,
$\mathcal{K}_{h}=\mathcal{K}=[0,1]$. $\lozenge$

######  Example 3.2 (Negative entropy).

Another popular example is the entropic DGF $h(x)=x\log x+(1-x)\log(1-x)$. The
corresponding Bregman divergence is the relative entropy
$D(p,x)=p\log\frac{p}{x}+(1-p)\log\frac{1-p}{1-x}$, and a standard calculation
shows that $P_{#1}(y)=xe^{y}/[(1-x)+xe^{y}]$. In contrast to Example 3.1, the
prox-domain of $h$ is $\mathcal{K}_{h}=(0,1)$. For a (highly incomplete) list
of references on the use of this DGF in learning theory and optimization, cf.
Auer et al. (1995), Beck & Teboulle (2003), Shalev-Shwartz (2011), Arora et
al. (2012), Coucheney et al. (2015), Bomze et al. (2019), Lattimore &
Szepesvári (2020). $\lozenge$

######  Example 3.3 (Tsallis entropy).

An alternative to the Gibbs–Shannon negentropy is the _Tsallis_ / _fractional
power_ DGF $h(x)=-\frac{1}{q(1-q)}\cdot[x^{q}+(1-x)^{q}]$ for $q>0$ (Tsallis,
1988, Alvarez et al., 2004, Mertikopoulos & Sandholm, 2016, 2018). Formally,
to define $h$ for $q\leftarrow 1$, we will employ the continuity convention
$t^{q}/(q-1)\leftarrow\log t$, which yields the entropic DGF of Example 3.2.
Instead, for $q\leftarrow 2$, we readily get the Euclidean DGF of Example 3.1.
The corresponding prox-mapping does not admit a closed-form expression for all
$p$, but it can always be calculated in logarithmic time with a simple binary
search. Finally, we note that the prox-domain $\mathcal{K}_{h}$ of $h$ is the
entire space $\mathcal{K}$ for $q>1$; on the other hand, for $q\in(0,1]$, we
have $\mathcal{K}_{h}=(0,1)$. $\lozenge$

The above examples will play a key role in illustrating the analysis to come
and we will use them as running examples throughout.

##  4\. The geometry of distance-generating functions

#### The Bregman topology.

To proceed with our analysis and the statement of our results for (OMD), we
will need to take a closer look at the geometry induced on $\mathcal{K}$ by
the choice of $h$. The first observation is that, by the strong convexity
requirement for $h$, we have:

$D(p,x)\geq\tfrac{1}{2}\lVert p-x\rVert^{2}\quad\text{for all
$p\in\mathcal{K}$, $x\in\mathcal{K}_{h}$}.$ (7)

Topologically, this means that the convergence topology induced by the Bregman
divergence of $h$ on $\mathcal{K}$ is _at least as fine_ as the corresponding
norm topology: if a sequence $x_{t}$ converges to $p\in\mathcal{K}$ in the
Bregman sense ($D(p,x_{t})\to 0$), it also converges in the ordinary norm
topology ($\lVert x_{t}-p\rVert\to 0$).

On the other hand, the converse of this statement is, in general, false:
specifically, the norm topology could be _strictly coarser_ than the Bregman
topology. To see this, let $\mathcal{K}$ be the unit Euclidean ball in
$\mathbb{R}^{d}$, i.e., $\mathcal{K}=\\{x\in\mathbb{R}^{d}:\lVert
x\rVert_{2}\leq 1\\}$. For this space, a popular choice of DGF is the
_Hellinger regularizer_ $h(x)=-\sqrt{1-\lVert x\rVert_{2}^{2}}$, which has
$\mathcal{K}_{h}=\operatorname{ri}\mathcal{K}=\\{x\in\mathbb{R}^{d}:\lVert
x\rVert_{2}<1\\}$ (Alvarez et al., 2004, Bauschke et al., 2017). Then, for all
$p$ on the boundary of $\mathcal{K}$ (i.e., $\lVert p\rVert_{2}=1$), the
Bregman divergence is

$D(p,x)=\frac{1-\sum_{i=1}^{d}p_{i}x_{i}}{\sqrt{1-\lVert x\rVert_{2}^{2}}}.$
(8)

Shadowing the Euclidean definition, a “Hellinger sphere” of radius $r$
centered at $p$ is defined as the corresponding level set of $D(p,x)$, i.e.,
$S_{p}(r)=\\{x\in\mathcal{K}_{h}:D(p,x)=r\\}$. Hence, by (8), this means that
a point $x\in\mathcal{K}_{h}$ is at “Hellinger distance” $r$ relative to $p$
if

$1-\sum\nolimits_{i}p_{i}x_{i}=r\sqrt{1-\lVert x\rVert_{2}^{2}}.$ (9)

Now, if we take a sequence $x_{t}$ converging to $p$ in the ordinary Euclidean
sense (i.e., $\lVert x_{t}-p\rVert_{2}\to 0$), both sides of (9) converge to
$0$. This has several counterintuitive consequences:

  1. (it n)

$S_{r}(p)$ is _not closed_ in the Euclidean topology; and

  2. (it n)

the “Hellinger center” $p$ of $S_{r}(p)$ actually belongs to the Euclidean
closure of $S_{r}(p)$.

As a result, we can have a sequence $x_{t}$ with $\lVert x_{t}-p\rVert_{2}\to
0$, but which remains at _constant_ Hellinger divergence relative to $p$.

From a qualitative standpoint, this discrepancy means that $D(p,x)$ is not a
reliable measure of convergence of $x$ to $p$: if $D(p,x)$ is large, this does
not necessarily mean that $p$ and $x$ are topologically “far”. For this
reason, in the analysis of non-Euclidean instances of Bregman proximal
methods, it is common to make the so-called “reciprocity” assumption

$D(p,x_{t})\to 0\quad\text{whenever}\quad x_{t}\to p.$ (10)

A straightforward verification shows that the DGFs of Examples 3.1, 3.2 and
3.3 all satisfy (10); by contrast, this requirement of course fails for the
Hellinger regularizer above. For a detailed discussion of this condition, we
refer the reader to Chen & Teboulle (1993), Kiwiel (1997), Beck & Teboulle
(2003), Alvarez et al. (2004), Mertikopoulos & Staudigl (2018), Mertikopoulos
& Zhou (2019), Zhou et al. (2020), Hsieh et al. (2021), and references
therein.

#### The Legendre exponent.

From a _quantitative_ standpoint, even if (10) is satisfied, the local
geometry induced by a Bregman DGF could still be significantly different from
the base, Euclidean case. A clear example of this is provided by contrasting
the Euclidean and entropic DGFs of Examples 3.1 and 3.2. Concretely, if we
focus on the base point $p=0$, we have:

  1. (1)

In the Euclidean case (Example 3.1): $D(0,x)=x^{2}/2=\Theta(x^{2})$ for small
$x\geq 0$;

  2. (2)

In the entropic case (Example 3.2): $D(0,x)=-\log(1-x)=\Theta(x)$ for small
$x\geq 0$.

Consequently, the rate of convergence of $x_{t}$ to $p=0$ is drastically
different if it is measured relative to the Euclidean divergence of Example
3.1 or the Kullback-Leibler divergence of Example 3.2. As an example, if we
take the sequence $x_{t}=1/t$, we get $D(0,x_{t})=\Theta(1/t^{2})$ in terms of
the Euclidean divergence, but $D(0,x_{t})=\Theta(1/t)$ in terms of the
Kullback-Leibler divergence.

This disparity is due to the fact that it might be impossible to invert the
inequality (7), even to leading order. To account for this, we introduce below
the notion of the _Legendre exponent_ of $h$.

######  Definition 2.

Let $h$ be a DGF on $\mathcal{K}$. Then the _Legendre exponent_ of $h$ at
$p\in\mathcal{K}$ is defined to be the smallest $\beta\in[0,1)$ such that
there exists a neighborhood $\mathcal{V}$ of $p$ and some $\kappa\geq 0$ such
that

$D(p,x)\leq\tfrac{1}{2}\kappa\lVert p-x\rVert^{2(1-\beta)}\quad\text{for all
$x\in\mathcal{V}\cap\mathcal{K}_{h}$}.$ (11)

Heuristically, the Legendre exponent measures the difference in relative size
between ordinary “norm neighborhoods” in $\mathcal{K}$ and the corresponding
“Bregman neighborhoods” induced by the sublevel sets of the Bregman
divergence. It is straightforward to see that the requirement $\beta\geq 0$ is
imposed by the strong convexity of $h$: since $D(p,x)=\Omega(\lVert
p-x\rVert^{2})$ for $x$ close to $p$, we cannot also have
$D(p,x)=\mathcal{O}(\lVert p-x\rVert^{2+\varepsilon})$ for any
$\varepsilon>0$. Note also that the notion of a Legendre exponent is only
relevant if $h$ satisfies the reciprocity requirement (10): otherwise, we
could have $\sup_{x\in\mathcal{U}}D(p,x)=\infty$ for any neighborhood
$\mathcal{U}$ of $p$ in $\mathcal{K}_{h}$, in which case we say that the
Legendre exponent is $1$ by convention.

To see the Legendre exponents in action, we compute them for our running
examples:

  1. (1)

_Euclidean projection_ (Example 3.1): $D(p,x)=(p-x)^{2}/2$ for all
$p,x\in\mathcal{K}$, so $\beta=0$ for all $p$.

  2. (2)

_Negative entropy_ (Example 3.2): If $p\in\mathcal{K}_{h}=(0,1)$, a Taylor
expansion with Lagrange remainder gives
$D(p,x)=h(p)-h(x)-h^{\prime}(x)(p-x)=\mathcal{O}((p-x)^{2})$ and thus
$\beta=0$. Now if $p=0$, $D(0,x)=-\log(1-x)=\Theta(x)$ which implies
$\beta=1/2$. Symmetrically, if $p=1$, $\beta=1/2$ too.

  3. (3)

_Tsallis entropy_ (Example 3.3): Assume that $q\neq 1$ (the case $q=1$ has
been treated above). We then have two cases: if $p\in\mathcal{K}_{h}=(0,1)$,
$h$ is twice continuously differentiable in a neighborhood of $p$ so that, as
previously, by the Taylor formula, $D(p,x)$ On the other hand, if $p=0$,

$D(0,x)=\frac{x^{q}}{q}-\frac{1}{q(1-q)}[1-(1-x)^{q}-q(1-x)^{q-1}x]\,,$ (12)

so $D(0,x)=\Theta(x^{\min(q,2)})$ when $x$ goes to zero. By symmetry, the
situation is the same at $p=1$, so the Legendre exponent of the Tsallis
entropy is $\beta=\max(0,1-q/2)$.

  4. (4)

_Hellinger regularizer:_ As we saw at the beginning of section, the Hellinger
divergence (8) does not satisfy (10), so $\beta=1$ by convention.

Of course, beyond our running examples, the same rationale applies when
$\mathcal{K}$ is a subset of a $d$-dimensional Euclidean space: If
$p\in\mathcal{K}_{h}$, then the associated Legendre exponent is typically $0$
(see Lemma A.7 for a precise statement), while if $p$ lies at the boundary of
$\mathcal{K}$, the exponent may be positive; we illustrate this below for the
important case of the simplex with the entropic DGF.

######  Example 4.1 (Entropy on the simplex).

Consider the $d$-dimensional simplex
$\mathcal{K}=\\{x\in\mathbb{R}_{+}^{d}:\sum_{i=1}^{d}x_{i}=1\\}$ and the
entropic regularizer $h(x)=\sum_{i=1}^{d}x_{i}\log x_{i}$. The associated
divergence (also called Kullback-Leibler divergence) can be decomposed as

$\displaystyle D(p,x)$ $\displaystyle=\sum_{i:p_{i}=0}(\log
x_{i}+1)x_{i}-x_{i}\log x_{i}$ $\displaystyle+\sum_{i:p_{i}\neq 0}p_{i}\log
p_{i}-x_{i}\log x_{i}-(\log x_{i}+1)(p_{i}-x_{i}).$ (13)

The first sum is simply $\sum_{i:p_{i}=0}x_{i}$ and the terms of the second
are bounded by $\mathcal{O}((p_{i}-x_{i})^{2})$, so

$\displaystyle D(p,x)$
$\displaystyle\textstyle=\sum_{i:p_{i}=0}x_{i}+\mathcal{O}\left(\sum_{i:p_{i}\neq
0}(p_{i}-x_{i})^{2}\right).$ (14)

If $p\in\mathcal{K}_{h}=\\{x\in\mathbb{R}_{++}^{d}:\sum_{i=1}^{d}x_{i}=1\\}$,
we get $\beta=0$. If $p\not\in\mathcal{K}_{h}$ there is at least one
$p_{i}=0$, $D(p,x)$ is not bounded by $\mathcal{O}(\lVert p-x\rVert^{2})$ but
by $\mathcal{O}(\lVert p-x\rVert)$ so that $\beta=1/2$ for such $p$.
$\lozenge$

##  5\. Analysis and results

###  5.1. Main result and discussion

We are finally in a position to state and prove our main result for the
convergence rate of (OMD). Since we make no global monotonicity assumptions
for the defining vector field $v$, this result is _de facto_ of a local
nature. We provide below the complete statement, followed by a series of
remarks and an outline of the main steps of the proof.

######  Theorem 1.

Let $x^{\ast}$ be a solution of (VI) and fix some confidence level $\delta>0$.
Suppose further that Assumptions 1, 2 and 3 hold and (OMD) is run with a step-
size of the form $\gamma_{t}=\gamma/(t+t_{0})^{\eta}$ with $\eta\in(1/2,1]$
and $\gamma,t_{0}>0$. Then, (OMD) enjoys the following properties:

Stochastic stability:

If $\gamma/t_{0}$ is small enough, $x^{\ast}$ is stochastically stable: for
every neighborhood $\mathcal{U}$ of $x^{\ast}$, there exists a neighborhood
$\mathcal{U}_{1}$ of $x^{\ast}$ such that the event

$\mathcal{E}_{\mathcal{U}}=\\{\text{$X_{t}\in\mathcal{U}$ for all
$t=1,2,\dotsc$}\\}$ (15)

occurs with probability at least $1-\delta$ if $X_{1}\in\mathcal{U}_{1}$.

Convergence:

$X_{t}$ converges to $x^{\ast}$ at the following rate:

  1. Case I::

If the Legendre exponent of $h$ at $x^{\ast}$ is $\beta\in(0,1)$ and
$\min\\{\gamma,1/t_{0}\\}$ is small enough, the iterates $X_{t}$ of (OMD)
enjoy the convergence rate

$\operatorname{\mathbb{E}}[D(x^{\ast},X_{t})\nonscript\,|\nonscript\,\mathopen{}\mathcal{E}_{\mathcal{U}}]=\begin{cases}\mathcal{O}\left((\log
t)^{-(1-\beta)/\beta}\right)&\quad\text{if $\eta=1$},\\\
\mathcal{O}\left(t^{-\min\\{(1-\eta)(1-\beta)/\beta,\eta\\}}\right)&\quad\text{if
$\frac{1}{2}<\eta<1$},\end{cases}$ (16)

provided that $\mathcal{U}$ is small enough and $X_{1}\in\mathcal{U}_{1}$. In
particular, this rate undergoes a phase transition at $\beta=1/2$:

     * •:

Euclidean-like phase: If $\beta\in(0,1/2)$ and $\eta=1-\beta$, we obtain the
optimized rate

$\operatorname{\mathbb{E}}[D(x^{\ast},X_{t})\nonscript\,|\nonscript\,\mathopen{}\mathcal{E}_{\mathcal{U}}]=\mathcal{O}\left(t^{-(1-\beta)}\right).$
(17)

     * •:

Entropy-like phase: If $\beta\in[1/2,1)$ and $\eta=(1+\epsilon)/2$ for any
small $\varepsilon>0$, we get

$\operatorname{\mathbb{E}}[D(x^{\ast},X_{t})\nonscript\,|\nonscript\,\mathopen{}\mathcal{E}_{\mathcal{U}}]=\mathcal{O}\left(t^{-\frac{1-\varepsilon}{2\beta}(1-\beta)}\right).$
(18)

  2. Case II::

If $\beta=0$ and $\gamma$ and $t_{0}$ are sufficiently large, the iterates
$X_{t}$ of (OMD) enjoy the rate

$\operatorname{\mathbb{E}}[D(x^{\ast},X_{t})\nonscript\,|\nonscript\,\mathopen{}\mathcal{E}_{\mathcal{U}}]=\mathcal{O}(t^{-\eta}),$
(19)

provided that $\mathcal{U}$ is small enough and $X_{1}\in\mathcal{U}_{1}$. In
particular, for $\eta=1$ we get

$\operatorname{\mathbb{E}}[D(x^{\ast},X_{t})\nonscript\,|\nonscript\,\mathopen{}\mathcal{E}_{\mathcal{U}}]=\mathcal{O}(t^{-1}).$
(20)

$\beta$$0$$1$$\frac{1}{2}$Rate exponent ($\nu$)$0$$1$$\frac{1}{2}$Euclidean-
like phaseEntropy-like phase (a) Predicted rate $\mathcal{O}(1/t^{\nu})$ vs.
Legendre exponent $\beta$

$\displaystyle{10^{0}}$$\displaystyle{10^{1}}$$\displaystyle{10^{2}}$$\displaystyle{10^{3}}$$\displaystyle{10^{4}}$$\displaystyle{10^{5}}$$\displaystyle{10^{-5}}$$\displaystyle{10^{-4}}$$\displaystyle{10^{-3}}$$\displaystyle{10^{-2}}$$\displaystyle{10^{-1}}$iteration$D(x^{\ast},X_{t})\times
t^{\nu}$ with $\nu$ predicted by Theorem 1Euclidean regularizer
($\beta=0$)Entropy ($\beta=0.5$)Tsallis entropy with $q=0.5$
($\beta=0.75$)Tsallis entropy with $q=1.5$ ($\beta=0.25$)

(b) Fit of the predicted rates with the simulation.

Figure 1. Illustration of the rates predicted by Theorem 1 (left: theory;
right: numerical validation). The dashed line in Fig. 1(a) indicates that the
rate prediction is only valid up to an arbitrarily small exponent or suitable
logarithmic factor. The experiments in Fig. 1(b) were conducted for a linear
vector field $v(x)=x$ on $\mathcal{K}=[0,+\infty)$ with the regularizer setups
of Examples 3.1, 3.2 and 3.3 (for more details, see Appendix D). We run OMD
with the stepsizes prescribed by Theorem 1 and plot $D(x^{\ast},X_{t})\times
t^{\nu}$ where $\nu$ is the predicted rate ($\nu=1,0.5,0.167,0.75$
respectively for Euclidean, entropy, Tsallis entropy with $q=0.5$ and
$q=1.5$). A horizontal line corresponds to a match between the theoretical and
observed rates.

#### Related work.

The rate guarantees of Theorem 1 should be compared and contrasted to a series
of recent results on the convergence speed of OMD and its variants. Most of
these results concern the deterministic case, i.e., when $U_{t}=0$ for all
$t$. In this regime, and focusing on the last iterate of the method, Golowich
et al. (2020a, b) showed that the convergence speed of the (optimistic) extra-
gradient algorithm in unconstrained, smooth, monotone variational inequalities
is $\mathcal{O}(1/\sqrt{t})$ in terms of $\lVert v(X_{t})\rVert$. If, in
addition, $v$ is _strongly_ monotone, it is well known that this rate becomes
linear; for a recent take on different (Euclidean) variants of (OMD), see
Malitsky (2015), Gidel et al. (2019), Hsieh et al. (2019), Mokhtari et al.
(2019a, b), and references therein.

Unsurprisingly, the stochastic regime is fundamentally different. In the
merely monotone case (i.e., neither strongly nor strictly monotone), we are
not aware of any result on the method’s last-iterate convergence speed:
existing results in the literature either cover the algorithm’s ergodic
average (Juditsky et al., 2011, Gidel et al., 2019, Cui & Shanbhag, 2016) or
are asymptotic in nature (Iusem et al., 2017). Because of the lack of
deterministic correlation between gradients at the base and leading states in
stochastic problems, smoothness does not help to achieve better rates in this
case – except for mollifying the requirement for bounded gradient signals
(Juditsky et al., 2011). By contrast, strong monotonicity – local or global –
_does_ help: as was shown by Hsieh et al. (2019), the iterates of the
_Euclidean_ version of (OMD) run with a $1/t$ step-size schedule converge
locally to solutions satisfying (SOS) at a $\mathcal{O}(1/t)$ rate in terms of
the mean square distance to the solution. This result is a special instance of
Case II of Theorem 1: in particular, for $\beta=0$, $\eta=1$, (19) indicates
that the $1/t$ step-size schedule examined by Hsieh et al. (2019) is optimal
for the Euclidean case; however, as we explain below, it is _not_ optimal for
non-Euclidean DGFs.

#### Step-size tuning.

A key take-away from Theorem 1 is that the step-size schedule that optimizes
the rate guarantees in Eqs. 17 and 18 is either
$\gamma_{t}=\Theta(1/t^{1-\beta})$ when $0\leq\beta<1/2$, or as close as
possible to $\Theta(t^{1/2})$ when $1/2\leq\beta<1$; in both cases, the
optimal tuning of the algorithm’s step-size _depends on the Legendre exponent
of $x^{\ast}$_. We feel that this is an important parameter to keep in mind
when deploying non-Euclidean versions of (OMD) in a stochastic setting – e.g.,
as in the optimistic multiplicative weights update (OMWU) algorithm of
Daskalakis & Panageas (2019). Theorem 1 suggests that the “best practices” of
the Euclidean setting do not carry over to non-Euclidean ones: Euclidean step-
size policy $1/t$ would lead to a catastrophic drop from $1/\sqrt{t}$ to
$1/\log t$ in the rate guarantees for (OMD).

#### Geometry-dependent rates.

One final observation for Theorem 1 is that the convergence speed of (OMD) is
measured in terms of the Bregman divergence $D(x^{\ast},X_{t})$. Since $\lVert
X_{t}-x^{\ast}\rVert=\mathcal{O}(\sqrt{D(x^{\ast},X_{t})})$, this rate
immediately translates to a rate on $\lVert X_{t}-x^{\ast}\rVert$. However,
this rate is _not_ tight, again because of the disparity between the Bregman
and norm geometries discussed in Section 4. Specifically, in many cases, a
non-zero Legendre exponent implies a sharper lower bound on the Bregman
divergence of the form $D(x^{\ast},X_{t})=\Omega(\lVert
X_{t}-x^{\ast}\rVert^{2-2\beta})$. Thus, for $\beta\in[0,1/2)$, Jensen’s
inequality applied to the optimized bound (17) gives
$\operatorname{\mathbb{E}}[\lVert
X_{t}-x^{\ast}\rVert]=\mathcal{O}(1/\sqrt{t})$. Importantly, this rate
guarantee is the same as in the Euclidean case ($\beta=0$), though it requires
a completely different step-size policy to achieve it. Determining when the
Legendre exponent also provides a lower bound is a very interesting direction
for future research, but one that lies beyond the scope of this work.

###  5.2. Main ideas of the proof

The heavy lifting in the proof of Theorem 1 is provided by Proposition 1
below, which also makes explicit some of the hidden constants in the statement
of the theorem.

######  Proposition 1.

With notation and assumptions as in Theorem 1, fix some $r>0$ and let

$\mathcal{U}=\mathbb{B}({x^{\ast}},{r})\cap\mathcal{K}\quad\text{and}\quad\mathcal{U}_{1}=\\{x:D(x^{\ast},x)\leq
r^{2}/12\\}.$

If $X_{1}\in\mathcal{U}_{1}$, then the event $\mathcal{E}_{\mathcal{U}}$
defined in (15) satisfies
$\operatorname{\mathbb{P}}(\mathcal{E}_{\mathcal{U}})\geq
1-\mathcal{O}\left({\rho^{2}}/{r^{2}}\right)$ where
$\rho^{2}=\sigma^{2}\gamma^{2}t_{0}^{1-2\eta}/(2\eta-1)$. Moreover, if $r$ is
taken small enough,
$\operatorname{\mathbb{E}}\left[D(x^{\ast},X_{t})\mid\mathcal{E}_{\mathcal{U}}\right]$
is bounded according to the following table and conditions:

Legendre exponent |  Rate $(\eta=1)$ |  Rate $(\tfrac{1}{2}<\eta<1)$
---|---|---
$\beta\in(0,1)$ | $\mathcal{O}\left((\log t)^{-\frac{1-\beta}{\beta}}\right)$ | $\mathcal{O}\left(t^{-\frac{(1-\eta)(1-\beta)}{\beta}}+t^{-\eta}\right)$
Conditions: | $\gamma^{1+1/\beta}\leq\frac{c(\eta,\alpha)\max(1,\Phi)}{4\sigma^{2}(\mu/\kappa)^{{1/\beta-1}}}$
$\beta=0$ | $\mathcal{O}(1/t)$ | $\mathcal{O}(1/t^{\eta})$
Conditions: | $\gamma>\kappa/\mu$ | —

where $\alpha=\beta/(1-\beta)$, $\Phi=r^{2}/12+8\rho^{2}$, and

$c(\eta,\alpha)=\begin{cases}\frac{1-\eta}{(1+\alpha)^{1+1/\alpha}}&\quad\text{if
$\eta\leq\frac{1+\alpha}{1+2\alpha}$},\\\\[3.0pt]
\alpha\left(\frac{1-2^{-(1+\alpha)}}{1+\alpha}\right)^{1+1/\alpha}&\quad\text{if
$\eta>\frac{1+\alpha}{1+2\alpha}$}.\end{cases}$ (21)

We outline here the main ideas of the proof, deferring all details to Appendix
C.

###### Sketch of proof.

Our proof strategy is to show that, under the stated conditions for $r$ and
the algorithm’s initialization, the iterates of (OMD) remain within a
neighborhood of $x^{\ast}$ where (SOS) holds with high probability. Then,
conditioning on this event, we use the Bregman divergence as a stochastic
potential function, and we derive the algorithm’s rate of convergence using a
series of lemmas on (random) numerical sequences. The step-by-step process is
as follows:

  1. (1)

The cornerstone of the proof is a descent inequality for the iterates of OMD,
which relates $D(x^{\ast},X_{t+1})$ to $D(x^{\ast},X_{t})$. As stated in Lemma
B.2, we have

$\displaystyle D(x^{\ast},X_{t+1})+\phi_{t+1}$ $\displaystyle\leq
D(x^{\ast},X_{t})+(1-\gamma_{t}\mu)\phi_{t}-\gamma_{t}\langle
V_{t+1/2},X_{t+1/2}-x^{\ast}\rangle$ (22)
$\displaystyle+\left(4\gamma_{t}^{2}L^{2}-\frac{1}{2}\right)\lVert
X_{t+1/2}-X_{t}\rVert^{2}+4\gamma_{t}^{2}\left[\lVert
U_{t+1/2}\rVert_{\ast}^{2}+\lVert U_{t-1/2}\rVert_{\ast}^{2}\right]$

where $\phi_{t}=\frac{\gamma_{t-1}^{2}}{2}\|V_{t-1/2}-V_{t-3/2}\|^{2}$ for all
$t\geq 2$, and $\phi_{1}=0$.

  2. (2)

The next step is to show that, with high probability and if initialized close
to $x^{\ast}$, the iterates of OMD remain in $\mathcal{U}$. This is a
technical argument relying on a use of the Doob-Kolmogorov maximal inequality
for submartingales (in the spirit of Hsieh et al. (2020)) and the condition
$\eta>1/2$ (which in turn guarantees that the step-size is square summable, so
the corresponding submartingale error terms are bounded in $L^{1}$). The
formal statement is Lemma B.4.

  3. (3)

To proceed, choose $r>0$ small enough so that the second order sufficiency
condition (SOS) holds and the Legendre exponent estimate (11) both hold. More
precisely, we take $r$ small enough so that
$\mathcal{U}=\mathbb{B}({x^{\ast}},{r})\cap\mathcal{K}$ is included in the
domains of validity of both properties ($\mathcal{B}$ and $\mathcal{V}$
respectively), and we will work on the event
$\mathcal{E}_{t}=\\{X_{s+1/2}\in\mathcal{U}\;\text{for all
$s=1,2,\dotsc,t$}\\}$. Then, conditioning on $\mathcal{E}_{t}$, Assumption 2
gives

$\langle
v(X_{t+1/2}),X_{t+1/2}-x^{\ast}\rangle\geq\frac{\mu}{2}\|X_{t+1/2}-x^{\ast}\|^{2}\,,$

and hence, by Lemma A.6, we get

$\langle
v(X_{t+1/2}),X_{t+1/2}-x^{\ast}\rangle\geq\frac{\mu}{2}\|X_{t}-x^{\ast}\|^{2}-\mu\|X_{t+1/2}-X_{t}\|^{2}\,.$

However, the descent inequality only involves $D(x^{\ast},X_{t})$ and not
$\lVert X_{t}-x^{\ast}\rVert^{2}$, so we need to relate the latter to the
former. This is where the Legendre exponent comes into play. More precisely,
Definition 2 with $1+\alpha=\frac{1}{1-\beta}$ gives

$D(x^{\ast},x)^{1+\alpha}\leq\tfrac{1}{2}\kappa\lVert x^{\ast}-x\rVert^{2},$

so, with $X_{t+1/2}\in\mathcal{V}$, we have

$\langle
v(X_{t+1/2}),X_{t+1/2}-x^{\ast}\rangle\geq\frac{\mu}{\kappa}D(x^{\ast},X_{t})^{1+\alpha}-\mu\|X_{t+1/2}-X_{t}\|^{2}\,.$

  4. (4)

Thus, going back to the descent inequality (22), employing the bound derived
above, and taking expectations ultimately yields (after some technical
calculations) the iterative bound

$\operatorname{\mathbb{E}}\left[(D(x^{\ast},X_{t+1})+\phi_{t+1})\mathds{1}_{\mathcal{E}_{t}}\right]\\\
\leq\operatorname{\mathbb{E}}\left[\left(D(x^{\ast},X_{t})-\frac{\mu\gamma_{t}}{\kappa}D(x^{\ast},X_{t})^{1+\alpha}+\left(1-\frac{\gamma_{t}\mu}{\kappa}\right)\phi_{t}\right)\mathds{1}_{\mathcal{E}_{t-1}}\right]+8\gamma_{t}^{2}\sigma^{2}$
(23)

where we used Assumption 3 to bound the expectations of
$\|U_{t+1/2}\|_{*}^{2}$ and $\|U_{t-1/2}\|_{*}^{2}$.

  5. (5)

We are now in a position to reduce the problem under study to the behavior of
the sequence
$a_{t}=\operatorname{\mathbb{E}}\left[(D(x^{\ast},X_{t})+\phi_{t})\mathds{1}_{\mathcal{E}_{t-1}}\right]$,
$t\geq 1$. Indeed, taking a closer look at $\mathcal{E}_{t}$ shows that

$\operatorname{\mathbb{E}}\left[D(x^{\ast},X_{t})\mid\mathcal{E}_{\mathcal{U}}\right]=\mathcal{O}(a_{t})\,.$

Consequently, the inequality (23) above can be rewritten as follows:

$\displaystyle a_{t+1}\leq
a_{t}-\frac{\mu\gamma_{t}}{\kappa}\operatorname{\mathbb{E}}\left[\left(D(x^{\ast},X_{t})^{1+\alpha}+\phi_{t}\right)\mathds{1}_{\mathcal{E}_{t-1}}\right]+8\gamma_{t}^{2}\sigma^{2}\,.$
(24)

  6. (6)

The behavior of this last sequence hinges heavily on whether $\alpha>0$ or
not. In detail, we have:

     * •

If $\alpha=0$, (24) gives

$a_{t+1}\leq\left(1-\frac{\mu\gamma}{\kappa(t+t_{0})^{\eta}}\right)a_{t}+\frac{8\gamma^{2}\sigma^{2}}{(t+t_{0})^{2\eta}}\,.$

The long-run behavior of this recursive inequality is described by Lemmas A.8
and A.9: as long as $\mu\gamma/\beta>1$ for $\eta=1$ (and only for $\eta=1$),
we have $a_{t}=\mathcal{O}(1/t^{\eta})$.

     * •

If $\alpha>0$, a series of further technical calculations in the same spirit
yields

$a_{t+1}\leq
a_{t}-\frac{\mu\gamma}{2^{\alpha}\max(1,\Phi^{\alpha})\kappa(t+t_{0})^{\eta}}a_{t}^{1+\alpha}+\frac{8\gamma^{2}\sigma^{2}}{(t+t_{0})^{2\eta}}$

The final step of our proof is to upper bound the behavior of $a_{t}$ based on
this recursive inequality. The necessary groundwork is provided by Lemmas A.11
and A.12, and hinges on whether $\eta\geq\frac{1+\alpha}{1+2\alpha}$ or not
(and is also where the value of $c(\eta,\alpha)$ comes in).

Putting everything together, we obtain the conditional rates in the statement
of the proposition. ∎

##  6\. Conclusion

In this work, we investigated the rate of convergence of optimistic mirror
descent for solving variational inequalities with stochastic oracle feedback.
Our results highlight the relationship between the rate of convergence of the
last iterate and the local geometry of the distance-generating function at the
solution. To capture this local geometry, we introduced the regularity
exponent of the divergence relative to the norm that we dubbed the Legendre
exponent. This quantity plays a central role in our results: the less regular
the Bregman divergence around the solution, the slower the convergence of the
last iterate. Furthermore, we show that that the step-size policy that
guarantees the best rates depends on the distance-generating function through
the associated Legendre exponent.

This work opens the door to various refinements and extensions diving deeper
into the geometry of the method’s DGF. A key remark is that the method’s
Legendre exponent seems to depend crucially on which constraints of the
problem are active at a given solution. Deriving a precise characterization of
the method’s convergence rate in these cases is a fruitful direction for
future research.

##  Appendix A Auxiliary lemmas

We gather in this section the basic results used in our proofs.

###  A.1. Bregman divergences

We recall here classical lemmas on Bregman divergences; see Juditsky et al.
(2011), Mertikopoulos et al. (2019). We complement them with two elementary
results Lemma A.6 on a specific bounding and Lemma A.7 which shows that the
Legendre exponent is typically trivial on $\mathcal{K}_{h}$.

######  Lemma A.1.

For $x\in\mathcal{K}$, $p\in\operatorname{dom}\partial h$,

$D({x,p})\geq\frac{1}{2}\lVert p-x\rVert^{2}\,.$

######  Lemma A.2.

For $x\in\operatorname{dom}\partial h$, $y,y^{\prime}\in\mathcal{Y}$,

$\|P_{#1}(y)-P_{#1}(y^{\prime})\|\leq\|y-y^{\prime}\|_{*}\,.$

######  Lemma A.3.

For $p\in\mathcal{K}$, $x\in\operatorname{dom}\partial h$, $y\in\mathcal{Y}$,
$y^{\prime}\in N_{\mathcal{K}}(p)$ and $x^{+}=P_{#1}(y)$,

$\displaystyle D(p,x^{+})$ $\displaystyle\leq D(p,x)+\langle
y-y^{\prime},x^{+}-p\rangle-D(x^{+},x)$ $\displaystyle\leq D(p,x)+\langle
y-y^{\prime},x-p\rangle+\frac{1}{2}\|y-y^{\prime}\|_{*}^{2}\,.$

######  Lemma A.4.

For $p\in\mathcal{K}$, $x\in\operatorname{dom}\partial h$,
$y,y^{\prime}\in\mathcal{Y}$ and
$x^{+}_{1}=P_{#1}(y)$,$x^{+}_{2}=P_{#1}(y^{\prime})$,

$D(p,x^{+}_{2})\leq D(p,x)+\langle
y^{\prime},x^{+}_{1}-p\rangle+\frac{1}{2}\|y^{\prime}-y\|_{*}^{2}-\frac{1}{2}\|x_{1}^{+}-x\|^{2}\,.$

######  Lemma A.5.

For $x\in\mathcal{K}_{h}$,

$\partial h(x)=\nabla h(x)+\operatorname{NC}_{\mathcal{K}}(x)\,.$

As a consequence, $x\in\mathcal{K}_{h}$, $x^{+}\in\mathcal{K}$,
$y\in\mathcal{Y}$,

$\displaystyle x^{+}=P_{#1}(y)$ $\displaystyle\iff\nabla h(x)+y\in\partial
h(x^{+})$ $\displaystyle\iff\nabla h(x)+y-\nabla
h(x^{+})\in\operatorname{NC}_{\mathcal{K}}(x^{+})\,.$

Moreover, $x^{+}=P_{#1}(y)$ implies that $x^{+}\in\mathcal{K}_{h}h$.

######  Lemma A.6.

If Assumption 2 holds, $x^{+}\in\mathcal{B}$, and $x\in\mathcal{K}$, then,

$\langle
v(x^{+}),x^{+}-x^{\ast}\rangle\geq\frac{\mu}{2}\|x-x^{\ast}\|^{2}-\mu\|x^{+}-x\|^{2}\,.$

###### Proof.

If $x^{+}\in\mathcal{B}$, then,

$\langle v(x^{+}),x^{+}-x^{\ast}\rangle\geq\mu\|x^{+}-x^{\ast}\|^{2}\,.$ (A.1)

However, we are interested in the distance between $x$ and $x^{\ast}$, not in
the distance between $x^{+}$ and $x^{\ast}$. To remedy this, we use Young’s
inequality,

$\|x-x^{\ast}\|^{2}\leq 2\|x-x^{+}\|^{2}+2\|x^{+}-x^{\ast}\|^{2}\,,$

which leads to,

$\|x^{+}-x^{\ast}\|^{2}\geq\frac{1}{2}\|x-x^{\ast}\|^{2}-\|x^{+}-x\|^{2}\,.$

Combined with Eq. A.1, we get,

$\langle
v(x^{+}),x^{+}-x^{\ast}\rangle\geq\frac{\mu}{2}\|x-x^{\ast}\|^{2}-\mu\|x^{+}-x\|^{2}\,.$

∎

######  Lemma A.7 (Trivial Legendre exponent on the interior).

Assume that $\nabla h$ is locally Lipschitz continuous on $\mathcal{K}_{h}$.
Then, for any $p\in\mathcal{K}_{h}$, the Legendre exponent of $h$ at $p$ is
$\beta=0$.

###### Proof.

Take $p\in\mathcal{K}_{h}$. As $\nabla h$ is assumed to be locally Lipschitz,
there exists $\mathcal{V}$ a neighborhood of $p$ and $\kappa>0$ such that, for
any $x\in\mathcal{V}\cap\mathcal{K}_{h}$,

$\lVert\nabla h(p)-\nabla h(x)\rVert_{\ast}\leq\frac{\kappa}{2}\lVert
p-x\rVert\,.$

Now, as $\nabla h(p)\in\partial h(p)$, for any
$x\in\mathcal{V}\cap\mathcal{K}_{h}$,

$\displaystyle D(p,x)$ $\displaystyle=h(p)-h(x)-\langle\nabla h(x),p-x\rangle$
$\displaystyle\leq\langle\nabla h(p)-\nabla h(x),p-x\rangle$
$\displaystyle\leq\lVert\nabla h(p)-\nabla h(x)\rVert_{\ast}\lVert
p-x\rVert\,.$

Using the local Lipschitz continuity of $\nabla h$, we get, for any
$x\in\mathcal{V}\cap\mathcal{K}_{h}$,

$D(p,x)\leq\frac{\kappa}{2}\lVert p-x\rVert^{2}\,,$

which reads $\beta=0$. ∎

###  A.2. Sequences

We recall results on sequences to transform descent-like inequalities into
rates; see the classical textbook Polyak (1987). We also need variants of
existing results (Lemma A.11 and Lemma A.12) that we state here.

######  Lemma A.8 (Chung (1954, Lem. 1)).

Let $(a_{t})_{t\geq 1}$ be a sequence of non-negative scalars, $q>1$,
$q^{\prime}>0$, $t_{0}\geq 0$. If, for any $t\geq 1$,

$a_{t+1}\leq\left(1-\frac{q}{t+t_{0}}\right)a_{t}+\frac{q^{\prime}}{(t+t_{0})^{2}}\,,$

then, for any $T\geq 1$,

$a_{T}\leq\frac{q^{\prime}}{q-1}\frac{1}{T+t_{0}}+o\left(\frac{1}{T}\right)\,.$

######  Lemma A.9 (Chung (1954, Lem. 4)).

Let $(a_{t})_{t\geq 1}$ be a sequence of non-negative scalars,
$q,q^{\prime}>0$, $t_{0}\geq 0$, $1>\eta>0$. If, for any $t\geq 1$,

$a_{t+1}\leq\left(1-\frac{q}{(t+t_{0})^{\eta}}\right)a_{t}+\frac{q^{\prime}}{(t+t_{0})^{2\eta}}\,,$

then, for any $T\geq 1$,

$a_{T}\leq\mathcal{O}\left(\frac{1}{T^{\eta}}\right)\,.$

######  Lemma A.10 (Polyak (1987, §2.2, Lem. 6)).

Let $(a_{t})_{1\leq t\leq T}$ be a sequence of non-negative scalars,
$(\gamma_{t})_{1\leq t\leq T}$ be sequence of positive scalars and $\alpha>0$.
If, for any $t=1,\dots,T$,

$a_{t+1}\leq a_{t}-\gamma_{t}a_{t}^{1+\alpha}\,,$

then,

$a_{T}\leq\frac{a_{1}}{\left(1+\alpha
a_{1}^{\alpha}\sum_{t=1}^{T-1}\gamma_{t}\right)^{1/\alpha}}\,.$

Though the next two lemmas allow for step-sizes of the form
$\gamma_{t}=\frac{\gamma}{(t+t_{0})^{\eta}}$, they do not exploit the term
$t_{0}$.

######  Lemma A.11.

Let $(a_{t})_{t\geq 1}$ be a sequence of non-negative scalars,
$(\gamma_{t})_{t\geq 1}$ be sequence of positive scalars of the form
$\gamma_{t}=\frac{q}{(t+t_{0})^{\eta}}$ with $q,\eta>0$, $t_{0}\geq 0$ and
$\alpha>0$, $q^{\prime}>0$ such that,

$a_{t+1}\leq
a_{t}-\gamma_{t}a_{t}^{1+\alpha}+\frac{q^{\prime}}{(t+t_{0})^{2\eta}}\,.$

If,

$\displaystyle 1\geq$
$\displaystyle\eta\geq\frac{1+\alpha}{1+2\alpha}>\frac{1}{2}\,,$
$\displaystyle q^{\prime}q^{1/\alpha}$ $\displaystyle\leq
c(\eta,\alpha)\coloneqq\alpha\left(\frac{1-2^{-(1+\alpha)}}{1+\alpha}\right)^{1+\frac{1}{\alpha}}\,,$

then, for any $T\geq 1$,

$a_{T}\leq\frac{a_{1}+b}{\left(1+\alpha(a_{1}+b)^{\alpha}2^{-\alpha}\sum_{t=1}^{T-1}\gamma_{t}\right)^{1/\alpha}}\,,$

where $b=\left(\frac{1-2^{1-2\eta}}{(1+\alpha)q}\right)^{\frac{1}{\alpha}}$.

###### Proof.

First, define $p=1+\alpha>1$ and note that
$\frac{1+\alpha}{1+2\alpha}=\frac{p}{2p-1}=\frac{1}{2-p^{-1}}\in(\frac{1}{2},1)$
so, in particular, the condition on $\eta$ is not absurd. Moreover, this means
that $\beta\coloneqq 2\eta-1$ belongs to $(0,1]$. Then, we have
$b=\left(\frac{1-2^{-\beta}}{pq}\right)^{\frac{1}{\alpha}}>0$ and, define, for
$t\geq 1$, $b_{t}\coloneqq\frac{b}{(t+t_{0})^{\beta}}$.

The first part of the proof consists in showing, that, for $t\geq 1$,

$\frac{q^{\prime}}{(t+t_{0})^{2\eta}}\leq
b_{t}-b_{t+1}-\gamma_{t}b_{t}^{p}\,.$

For this, we will need the following remark. As $\beta\leq 1$,
$x\mapsto(1+x)^{\beta}$ is concave. Hence, it is above its chords, and in
particular above its chord going from $0$ to $1$. Thus, for $0\leq x\leq 1$,
$(1+x)^{\beta}\geq 1+x(2^{\beta}-1)$.

We use this remark to lower bound $b_{t}-b_{t+1}$ for $t\geq 1$. Indeed,

$\displaystyle b_{t}-b_{t+1}$
$\displaystyle=\frac{b}{(t+t_{0})^{\beta}}-\frac{b}{(t+1+t_{0})^{\beta}}$
$\displaystyle=\frac{b}{(t+1+t_{0})^{\beta}}\left(\left(1+\frac{1}{t+t_{0}}\right)^{\beta}-1\right)$
$\displaystyle\geq\frac{b}{(t+1+t_{0})^{\beta}}\frac{2^{\beta}-1}{t+t_{0}}$
$\displaystyle\geq\frac{b}{(t+t_{0})^{\beta+1}}\frac{2^{\beta}-1}{2^{\beta}}\,.$

Therefore,

$b_{t}-b_{t+1}-\gamma_{t}b_{t}^{p}\geq\frac{b}{(t+t_{0})^{\beta+1}}(1-2^{-\beta})-\frac{qb^{p}}{(t+t_{0})^{\eta+p\beta}}\,.$

Now, by the definition of $\beta$, $\beta+1=2\eta$ and
$\eta+p\beta=(2p+1)\eta-p=2\eta+(2p-1)\eta-p\geq 2\eta$ by the assumption that
$\eta\geq\frac{1+\alpha}{1+2\alpha}=\frac{p}{2p-1}$. Hence,

$b_{t}-b_{t+1}-\gamma_{t}b_{t}^{p}\geq\frac{1}{(t+t_{0})^{2\eta}}(b(1-2^{-\beta})-qb^{p})\,,$

so that we only need to show that $q^{\prime}\leq b(1-2^{-\beta})-qb^{p}$.

Rearranging and replacing $b$ by its expression gives,

$\displaystyle b(1-2^{-\beta})-qb^{p}$
$\displaystyle=b((1-2^{-\beta})-qb^{\alpha})$
$\displaystyle=b\left((1-2^{-\beta})-\frac{1-2^{-\beta}}{p}\right)$
$\displaystyle=b(1-2^{-\beta})\frac{p-1}{p}$
$\displaystyle=(1-2^{-\beta})^{1+\frac{1}{\alpha}}\frac{p-1}{p^{1+\frac{1}{\alpha}}q^{\frac{1}{\alpha}}}\,.$

Therefore, with
$c(\eta,\alpha)=\alpha\left(\frac{1-2^{-(1+\alpha)}}{1+\alpha}\right)^{1+\frac{1}{\alpha}}=(1-2^{-\beta})^{1+\frac{1}{\alpha}}\frac{p-1}{p^{1+\frac{1}{\alpha}}}>0$
and $q^{\frac{1}{\alpha}}q^{\prime}\leq c(\eta,\alpha)$, we finally get that
$q^{\prime}\leq b(1-2^{-\beta})-qb^{p}$ and, for $t\geq 1$,

$\frac{q^{\prime}}{(t+t_{0})^{2\eta}}\leq
b_{t}-b_{t+1}-\gamma_{t}b_{t}^{p}\,.$

Recall that $(a_{t})_{t\geq 1}$ satisfies, for $t\geq 1$,

$a_{t+1}\leq
a_{t}-\gamma_{t}a_{t}^{p}+\frac{q^{\prime}}{(t+t_{0})^{2\eta}}\,.$

Therefore, putting these two inequalities together gives,

$a_{t+1}+b_{t+1}\leq a_{t}+b_{t}-\gamma_{t}(a_{t}^{p}+b_{t}^{p})\,.$

Finally, by convexity of $x\mapsto x^{p}$,

$a_{t+1}+b_{t+1}\leq a_{t}+b_{t}-\gamma_{t}2^{1-p}(a_{t}+b_{t})^{p}\,.$

Now, we can apply Lemma A.10 with $a_{t}\leftarrow a_{t}+b_{t}$ and
$\gamma_{t}\leftarrow\gamma_{t}2^{1-p}$. For any $T\geq 1$,

$a_{T}\leq a_{T}+b_{T}\leq\frac{1}{\left((a_{1}+b_{1})^{-\alpha}+\alpha
2^{-\alpha}\sum_{t=1}^{T-1}\gamma_{t}\right)^{1/\alpha}}\,.$

As the right-hand side is non-decreasing in $b_{1}$ and $b_{1}\leq b$, we get
the result of the statement. ∎

######  Lemma A.12.

Let $(a_{t})_{t\geq 1}$ be a sequence of non-negative scalars,
$(\gamma_{t})_{t\geq 1}$ be sequence of positive scalars of the form
$\gamma_{t}=\frac{q}{(t+t_{0})^{\eta}}$ with $q,\eta>0$, $b\geq 1$ and
$\alpha>0$, $q^{\prime}>0$ such that,

$a_{t+1}\leq
a_{t}-\gamma_{t}a_{t}^{1+\alpha}+\frac{q^{\prime}}{(t+t_{0})^{2\eta}}\,.$

If,

$\displaystyle 1>\frac{1+\alpha}{1+2\alpha}$
$\displaystyle\geq\eta>\frac{1}{2}\,,$ $\displaystyle q^{\prime}q^{1/\alpha}$
$\displaystyle\leq
c(\eta,\alpha)\coloneqq\frac{1-\eta}{(1+\alpha)^{\frac{1}{\alpha}+1}}\,,$

then, for any $T\geq 1$,

$a_{T}\leq\frac{a_{1}}{\left(1+\alpha
a_{1}^{\alpha}\sum_{t=1}^{T-1}\gamma_{t}\right)^{1/\alpha}}+\frac{1}{((1+\alpha)q)^{\frac{1}{\alpha}}{(T+t_{0})}^{\eta}}\,.$

###### Proof.

This proof is the “mirror” of the proof of the previous lemma. As before,
define $p=1+\alpha>1$ and note that
$\frac{1+\alpha}{1+2\alpha}=\frac{p}{2p-1}=\frac{1}{2-p^{-1}}\in(\frac{1}{2},1)$
so the condition on $\eta$ is not absurd. Moreover, this means that
$\beta\coloneqq\frac{\eta}{p}$ belongs to $(0,1)$. Then, define
$b~\coloneqq\left(\frac{1}{pq}\right)^{\frac{1}{\alpha}}>0$ and, define, for
$t\geq 1$, $b_{t}\coloneqq\frac{b}{(t+t_{0})^{\beta}}$.

Opposite to the proof of the previous lemma, the first part of the proof
consists in showing, that, for $t\geq 1$,

$\frac{q^{\prime}}{(t+t_{0})^{2\eta}}\leq
b_{t+1}+\gamma_{t}b_{t}^{p}-b_{t}\,.$

For this, we use the concavity of $x\mapsto(1+x)^{\beta}$, as $\beta\leq 1$,
so that, for $x\geq 0$, $(1+x)^{\beta}\leq 1+\beta x$.

This remark enables us to upper bound $b_{t}-b_{t+1}$ for $t\geq 1$. Indeed,

$\displaystyle b_{t}-b_{t+1}$
$\displaystyle=\frac{b}{(t+t_{0})^{\beta}}-\frac{b}{(t+1+t_{0})^{\beta}}$
$\displaystyle=\frac{b}{(t+1+t_{0})^{\beta}}\left(\left(1+\frac{1}{t+t_{0}}\right)^{\beta}-1\right)$
$\displaystyle\leq\frac{b}{(t+1+t_{0})^{\beta}}\frac{\beta}{t+t_{0}}$
$\displaystyle\leq\frac{\beta b}{(t+t_{0})^{\beta+1}}\,.$

Therefore,

$b_{t}-b_{t+1}-\gamma_{t}b_{t}^{p}\leq\frac{\beta
b}{(t+t_{0})^{\beta+1}}-\frac{qb^{p}}{(t+t_{0})^{\eta+p\beta}}\,.$

Now, by the definition of $\beta=\frac{\eta}{p}$, $\eta+p\beta=2\eta$ and
$\beta+1=2\eta+\frac{\eta}{p}+1-2\eta=2\eta+\frac{p-(2p-1)\eta}{p}\geq 2\eta$
by the assumption that $\eta\leq\frac{1+\alpha}{1+2\alpha}=\frac{p}{2p-1}$.
Hence,

$b_{t}-b_{t+1}-\gamma_{t}b_{t}^{p}\leq\frac{1}{(t+t_{0})^{2\eta}}(\beta
b-qb^{p})\,,$

so that,

$b_{t+1}+\gamma_{t}b_{t}^{p}-b_{t}\geq\frac{1}{(t+t_{0})^{2\eta}}(qb^{p}-\beta
b)\,.$

Again, we only need to show that $q^{\prime}\leq qb^{p}-\beta b$.

Rearranging and replacing $b$ by its expression gives,

$\displaystyle qb^{p}-b\beta$ $\displaystyle=b(qb^{\alpha}-\beta)$
$\displaystyle=b\left(\frac{1}{p}-\beta\right)$
$\displaystyle=\frac{1}{q^{\frac{1}{\alpha}}p^{\frac{1}{\alpha}}}\left(\frac{1}{p}-\beta\right)\,.$

Therefore, with
$c(\eta,\alpha)=\frac{1}{p^{\frac{1}{\alpha}}}\left(\frac{1}{p}-\beta\right)>0$
and $q^{\frac{1}{\alpha}}q^{\prime}\leq c(\eta,\alpha)$, we finally get that
$q^{\prime}\leq qb^{p}-\beta b$ and, for $t\geq 1$,

$\frac{q^{\prime}}{(t+t_{0})^{2\eta}}\leq
b_{t+1}+\gamma_{t}b_{t}^{p}-b_{t}\,.$

Putting this inequality together with the one on the sequence $(a_{t})_{t\geq
1}$ gives,

$a_{t+1}-b_{t+1}\leq a_{t}-b_{t}-\gamma_{t}(a_{t}^{p}-b_{t}^{p})\,.$

Now, let us discuss separately the case when $a_{t}>b_{t}$ and when $a_{t}\leq
b_{t}$.

More precisely, define $T_{0}=\min\\{t\geq 1:a_{t}\leq
b_{t}\\}\in\mathbb{N}^{*}\cup\\{+\infty\\}$, so that, for any $1\leq t<T_{0}$,
$a_{t}>b_{t}>0$. Note that, for $x,y>0$, as $p>1$, $x^{p}+y^{p}\leq(x+y)^{p}$.
For $1\leq t<T_{0}$, apply this with $x\leftarrow a_{t}-b_{t}$, $y\leftarrow
b_{t}$ gives $(a_{t}-b_{t})^{p}\leq a_{t}^{p}-b_{t}^{p}$ so that,

$a_{t+1}-b_{t+1}\leq a_{t}-b_{t}-\gamma_{t}(a_{t}-b_{t})^{p}\,.$

Lemma A.10 with $a_{t}\leftarrow a_{t}-b_{t}$ gives, for $1\leq T<T_{0}$,

$\displaystyle a_{T}$ $\displaystyle\leq
b_{T}+\frac{1}{((a_{1}-b_{1})^{-\alpha}+\alpha\sum_{t=1}^{T-1}\gamma_{t})^{\frac{1}{\alpha}}}$
$\displaystyle\leq
b_{T}+\frac{1}{(a_{1}^{-\alpha}+\alpha\sum_{t=1}^{T-1}\gamma_{t})^{\frac{1}{\alpha}}}\,,$

so the statement holds in this case.

We now handle the case of $T\geq T_{0}$. At $t=T_{0}$, we have $a_{T_{0}}\leq
b_{T_{0}}$. We show, by induction, that, for any $t\geq T_{0}$, $a_{t}\leq
b_{t}$. The initialization at $t=T_{0}$ is trivial. So, now, assume that
$a_{t}\leq b_{t}$ for some $t\geq T_{0}$. Recall that we have,

$a_{t+1}-b_{t+1}\leq a_{t}-b_{t}-\gamma_{t}(a_{t}^{p}-b_{t}^{p})\,,$

so we only need to show that,

$a_{t}-\gamma_{t}a_{t}^{p}\leq b_{t}-\gamma_{t}b_{t}^{p}\,.$

Define $\varphi_{t}:x\in\mathbb{R}_{+}\mapsto x-\gamma_{t}x^{p}$.
Differentiating this function shows that it is non-decreasing on
$\\{x\in\mathbb{R}_{+}:p\gamma_{t}x^{\alpha}\leq
1\\}=[0,(\gamma_{t}p)^{-\frac{1}{\alpha}}]$. But $a_{t}\leq b_{t}\leq
b_{1}\leq b$ by definition of $(b_{s})_{s~\geq 1}$ and, by definition of $b$
and $(\gamma_{s})_{s\geq 1}$,
$b=(pq)^{-\frac{1}{\alpha}}=(\gamma_{1}p)^{-\frac{1}{\alpha}}\leq(\gamma_{t}p)^{-\frac{1}{\alpha}}$.

Hence, both $a_{t}$ and $b_{t}$ belong to the interval on which $\varphi_{t}$
is non-decreasing so that $\varphi_{t}(a_{t})\leq\varphi_{t}(b_{t})$, which
implies that $a_{t+1}\leq b_{t+1}$. Therefore, we have shown that, for all
$T\geq T_{0}$, $a_{T}\leq
b_{T}=\frac{1}{(pq)^{\frac{1}{\alpha}}{(T+t_{0})}^{\eta}}$ which concludes the
proof. ∎

##  Appendix B Descent and stability of optimistic mirror descent

###  B.1. Descent inequality

The lemmas we present here link the divergence between two consecutive
iterates and the solution.

In particular, the first one only rely on i) the definition of one iteration
of optimistic mirror descent; and ii) the core properties of the Bregman
regularizer i.e., the $1$-strong convexity of $h$ (through Lemma A.1) and the
non-expansivity of the proximal mapping (Lemma A.2). It does not require any
assumption on the vector field $v$, on the noise in $V$, or additional
properties of the Bregman divergence (such as a Legendre exponent).

######  Lemma B.1.

If the stepsizes verify $\mu\gamma_{t}+4L^{2}\gamma_{t}^{2}\leq 1\,,$ then,
the iterates of optimistic mirror descent initialized with
$X_{1/2}\in\mathcal{K}$, $X_{1}\in\operatorname{dom}\partial h$ verify for all
$t\geq 1$,

$\displaystyle D(x^{\ast},X_{t+1})+\phi_{t+1}$ $\displaystyle\leq
D(x^{\ast},X_{t})+(1-\gamma_{t}\mu)\phi_{t}$
$\displaystyle~{}~{}~{}~{}~{}-\gamma_{t}\langle
V_{t+1/2},X_{t+1/2}-x^{\ast}\rangle+\left(2\gamma_{t}^{2}L^{2}-\frac{1}{2}\right)\|X_{t+1/2}-X_{t}\|^{2}$
$\displaystyle~{}~{}~{}~{}~{}+\gamma_{t}^{2}\Delta_{t+1}^{2}-\gamma_{t}^{2}\tau^{2}\|X_{t}-X_{t-1/2}\|^{2}\,,$

where
$\Delta_{t+1}^{2}=(\|V_{t+1/2}-V_{t-1/2}\|^{2}_{*}-L^{2}\|X_{t+1/2}-X_{t-1/2}\|^{2})_{+}$,
$\phi_{t}=\frac{\gamma_{t-1}^{2}}{2}\|V_{t-1/2}-V_{t-3/2}\|^{2}$ for all
$t\geq 2$, and $\phi_{1}=\frac{1}{2}\|X_{1}-X_{1/2}\|^{2}$.

###### Proof.

First, apply Lemma A.4 with
$(x,y_{1},y_{2})\leftarrow(X_{t},-\gamma_{t}V_{t-1/2},-\gamma_{t}V_{t+1/2})$
and $p\leftarrow x^{\ast}$,

$\displaystyle D(x^{\ast},X_{t+1})\leq D(x^{\ast},X_{t})-\gamma_{t}\langle
V_{t+1/2},X_{t+1/2}-x^{\ast}\rangle+\frac{\gamma_{t}^{2}}{2}\|V_{t-1/2}-V_{t+1/2}\|-\frac{1}{2}\|X_{t+1/2}-X_{t}\|^{2}\,.$
(B.1)

In order to upper-bound
$\frac{\gamma_{t}^{2}}{2}\|V_{t-1/2}-V_{t+1/2}\|-\frac{1}{2}\|X_{t+1/2}-X_{t}\|^{2}$,
we use the definition of
$\phi_{t+1}=\frac{\gamma_{t}^{2}}{2}\|V_{t+1/2}-V_{t-1/2}\|^{2}$ to see that

$\displaystyle\frac{\gamma_{t}^{2}}{2}\|V_{t-1/2}-V_{t+1/2}\|^{2}$
$\displaystyle={\gamma_{t}^{2}}\|V_{t-1/2}-V_{t+1/2}\|^{2}-\frac{\gamma_{t}^{2}}{2}\|V_{t-1/2}-V_{t+1/2}\|^{2}$
$\displaystyle={\gamma_{t}^{2}}\|V_{t-1/2}-V_{t+1/2}\|^{2}-\phi_{t+1}\,,$

and the definition of $\Delta_{t+1}$ to bound

$\displaystyle\gamma_{t}^{2}\|V_{t-1/2}-V_{t+1/2}\|^{2}$
$\displaystyle\leq\gamma_{t}^{2}L^{2}\|X_{t-1/2}-X_{t+1/2}\|^{2}+\gamma_{t}^{2}\Delta_{t+1}^{2}$
$\displaystyle\leq
2{\gamma_{t}^{2}L^{2}}\|X_{t-1/2}-X_{t}\|^{2}+2\gamma_{t}^{2}L^{2}\|X_{t+1/2}-X_{t}\|^{2}+\gamma_{t}^{2}\Delta_{t+1}^{2}\,,$

where we used Young’s inequality to get the last inequality line. Putting the
two equations together, we get that

$\displaystyle\frac{\gamma_{t}^{2}}{2}\|V_{t-1/2}-V_{t+1/2}\|^{2}-\frac{1}{2}\|X_{t+1/2}-X_{t}\|^{2}$
$\displaystyle\leq$
$\displaystyle{2\gamma_{t}^{2}L^{2}}\|X_{t-1/2}-X_{t}\|^{2}+\left({2\gamma_{t}^{2}L^{2}}-\frac{1}{2}\right)\|X_{t+1/2}-X_{t}\|^{2}-\phi_{t+1}+\gamma_{t}^{2}\Delta_{t+1}^{2}.$
(B.2)

For $t\geq 2$, we use the non-expansivity of the proximal mapping (Lemma A.2)
to bound $\|X_{t-1/2}-X_{t}\|$ by $\gamma_{t-1}\|V_{t-3/2}-V_{t-1/2}\|_{*}$ in
(B.2) to get

$\displaystyle\frac{\gamma_{t}^{2}}{2}\|V_{t-1/2}-V_{t+1/2}\|^{2}-\frac{1}{2}\|X_{t+1/2}-X_{t}\|^{2}$
$\displaystyle\leq{(2\gamma_{t}^{2}L^{2})}\gamma_{t-1}^{2}\|V_{t-3/2}-V_{t-1/2}\|_{*}^{2}+\left({2\gamma_{t}^{2}L^{2}}-\frac{1}{2}\right)\|X_{t+1/2}-X_{t}\|^{2}-\phi_{t+1}+\gamma_{t}^{2}\Delta_{t+1}^{2}$
$\displaystyle={(4\gamma_{t}^{2}L^{2})}\phi_{t}+\left({2\gamma_{t}^{2}L^{2}}-\frac{1}{2}\right)\|X_{t+1/2}-X_{t}\|^{2}-\phi_{t+1}+\gamma_{t}^{2}\Delta_{t+1}^{2}$
$\displaystyle\leq\left(1-\mu\gamma_{t}\right)\phi_{t}+\left({2\gamma_{t}^{2}L^{2}}-\frac{1}{2}\right)\|X_{t+1/2}-X_{t}\|^{2}-\phi_{t+1}+\gamma_{t}^{2}\Delta_{t+1}^{2}\,,$

where we used the definition of $\phi_{t}$ and the assumption on the
stepsizes. Combining this result with Eq. B.1 gives the first assertion of the
lemma for $t\geq 2$.

Now, if $t=1$, Eq. B.2 can be rewritten as,

$\displaystyle\frac{\gamma_{1}^{2}}{2}\|V_{1/2}-V_{3/2}\|^{2}-\frac{1}{2}\|X_{3/2}-X_{1}\|^{2}$
$\displaystyle\leq$ $\displaystyle
2\gamma_{1}^{2}L^{2}\|X_{1/2}-X_{1}\|^{2}+\left(2\gamma_{1}^{2}L^{2}-\frac{1}{2}\right)\|X_{3/2}-X_{1}\|^{2}-\phi_{2}+\gamma_{1}^{2}\Delta_{2}^{2}$
$\displaystyle=$ $\displaystyle
4\gamma_{1}^{2}L^{2}\phi_{1}+\left(2\gamma_{1}^{2}L^{2}-\frac{1}{2}\right)\|X_{3/2}-X_{1}\|^{2}-\phi_{2}+\gamma_{1}^{2}\Delta_{2}^{2}\,,$

which yields the assertion of the lemma for $t=1$ as $4\gamma_{1}^{2}L^{2}\leq
1-\gamma_{1}\mu$. ∎

We now use the properties of $V$ and $v$ to refine the bound of Lemma B.1 into
a descent inequality.

######  Lemma B.2.

Let Assumptions 1 and 2 hold. Consider the iterates of optimistic mirror
descent with:

  * i)

an unbiased stochastic oracle $V_{t}=v(X_{t})+U_{t}$ (see (2));

  * ii)

step-sizes $0<\gamma_{t}\leq\frac{1}{4L}$.

Then,

$\displaystyle D(x^{\ast},X_{t+1})+\phi_{t+1}\leq$ $\displaystyle
D(x^{\ast},X_{t})+(1-\gamma_{t}\mu)\phi_{t}-\gamma_{t}\langle
V_{t+1/2},X_{t+1/2}-x^{\ast}\rangle$ (B.3)
$\displaystyle+\left(4\gamma_{t}^{2}L^{2}-\frac{1}{2}\right)\|X_{t+1/2}-X_{t}\|^{2}+4\gamma_{t}^{2}(\|U_{t+1/2}\|_{*}^{2}+\|U_{t-1/2}\|_{*}^{2})\,$

where $\phi_{t}=\frac{\gamma_{t-1}^{2}}{2}\|V_{t-1/2}-V_{t-3/2}\|^{2}$ for all
$t\geq 2$, and $\phi_{1}=\frac{1}{2}\|X_{1}-X_{1/2}\|^{2}$.

###### Proof.

First, let us examine the choice of $\gamma_{t}$. The condition
$\gamma_{t}\leq\frac{1}{4L}$ is actually equivalent to,

$8\gamma_{t}^{2}L^{2}+2\gamma_{t}L\leq 1\,.$

As $\mu\leq L$, this implies that,

$8\gamma_{t}^{2}L^{2}+2\gamma_{t}\mu\leq 1\,.$ (B.4)

We first use the inequality of OMD provided by Lemma B.1 with
$(\mu,L)\leftarrow(\mu,\sqrt{2}L)$ (note that its assumption is satisfied
than4s to Eq. B.4) to get

$\displaystyle D(x^{\ast},X_{t+1})+\phi_{t+1}$ $\displaystyle\leq
D(x^{\ast},X_{t})+(1-\gamma_{t}\mu)\phi_{t}$ (B.5)
$\displaystyle~{}~{}~{}~{}~{}-\gamma_{t}\langle
V_{t+1/2},X_{t+1/2}-x^{\ast}\rangle+\left(2\gamma_{t}^{2}L^{2}-\frac{1}{2}\right)\|X_{t+1/2}-X_{t}\|^{2}$
$\displaystyle~{}~{}~{}~{}~{}+\gamma_{t}^{2}\Delta_{t+1}^{2}-\gamma_{t}^{2}\tau^{2}\|X_{t}-X_{t-1/2}\|^{2}\,,$

where
$\Delta_{t+1}^{2}=(\|V_{t+1/2}-V_{t-1/2}\|^{2}_{*}-L^{2}\|X_{t+1/2}-X_{t-1/2}\|^{2})_{+}$,
$\phi_{t}=\frac{\gamma_{t-1}^{2}}{2}\|V_{t-1/2}-V_{t-3/2}\|^{2}$ for all
$t\geq 2$, and $\phi_{1}=\frac{1}{2}\|X_{1}-X_{1/2}\|^{2}$.

We now have to bound
$\Delta_{t+1}^{2}=(\|V_{t+1/2}-V_{t-1/2}\|^{2}_{*}-2L^{2}\|X_{t+1/2}-X_{t-1/2}\|^{2})_{+}$
for $t\geq 1$. By using twice Young’s inequality,

$\displaystyle\|V_{t+1/2}-V_{t-1/2}\|^{2}_{*}$ $\displaystyle\leq
2\|v(X_{t+1/2})-v(X_{t-1/2})\|_{*}^{2}+2\|U_{t+1/2}-U_{t-1/2}\|_{*}^{2}$
$\displaystyle\leq
2\|v(X_{t+1/2})-v(X_{t-1/2})\|_{*}^{2}+4\|U_{t+1/2}\|_{*}^{2}+4\|U_{t-1/2}\|_{*}^{2}\,.$

Using the Lipschitz continuity of $v$ (Assumption 1), we obtain that

$\displaystyle\|V_{t+1/2}-V_{t-1/2}\|^{2}_{*}$ $\displaystyle\leq
2L^{2}\|X_{t+1/2}-X_{t-1/2}\|_{*}^{2}+4\|U_{t+1/2}\|_{*}^{2}+4\|U_{t-1/2}\|_{*}^{2}\,,$

so that,

$\Delta_{t+1}^{2}\leq 4\|U_{t+1/2}\|_{*}^{2}+4\|U_{t-1/2}\|_{*}^{2}\,.$

Plugging this inequality in (B.5), we obtain the claimed result. ∎

###  B.2. Stochastic local stability

In order to use the local properties of the Bregman divergence around the
solution, we need a local stability result that gives us that sufficiently
close iterates will remain in a neighborhood of the solution with high
probability. To show such a result, we will use the following lemma Hsieh et
al. (2020, Lem. F.1) for bounding a recursive stochastic process.

######  Lemma B.3 (Hsieh et al. (2020, Lem. F.1)).

Consider a filtration $(\mathcal{F}_{t})_{t}$ and four
$(\mathcal{F}_{t})_{t}$-adapted processes $(D_{t})_{t}$, $(\zeta_{t})_{t}$,
$(\chi_{t})_{t}$, $(\xi_{t})_{t}$ such that $\chi_{t}$ is non-negative and the
following recursive inequality is satisfied for all $t\geq 1$

$D_{t+1}\leq D_{t}-\zeta_{t}+\xi_{t}.$

For $C>0$, we define the events $A_{t}$ by $A_{1}\coloneqq\\{D_{1}\leq C/2\\}$
and $A_{t}\coloneqq\\{D_{t}\leq
C\\}\operatorname*{\bigcap}\thinspace\\{\chi_{t}\leq C/4\\}$ for $t\geq 2$. We
consider also the decreasing sequence of events $I_{t}$ defined by
$I_{t}\coloneqq\bigcap_{1\leq s\leq t}A_{s}$. If the following three
assumptions hold true

  1. (i)

$\forall t,\zeta_{t}\operatorname{\mathds{1}}_{I_{t}}\geq 0$,

  2. (ii)

$\forall
t,\operatorname{\mathbb{E}}[\xi_{t}\nonscript\,|\nonscript\,\mathopen{}{\mathcal{F}_{t}}]\operatorname{\mathds{1}}_{I_{t}}=0$,

  3. (iii)

$\sum_{t=1}^{\infty}\operatorname{\mathbb{E}}[(\xi_{t+1}^{2}+\chi_{t+1})\operatorname{\mathds{1}}_{I_{t}}]\leq\delta\epsilon\operatorname{\mathbb{P}}(A_{1})$,

where $\epsilon=\min(C^{2}/16,C/4)$ and $\delta\in(0,1)$, then
$\operatorname{\mathbb{P}}\left(\bigcap_{t\geq 1}A_{t}~{}|~{}A_{1}\right)\geq
1-\delta.$

######  Lemma B.4.

Let Assumptions 1 and 2 hold. Consider the iterates of optimistic mirror
descent with:

  * i)

an unbiased stochastic oracle $V_{t}=v(X_{t})+U_{t}$ with finite variance
$\sigma^{2}$ (see (2) and (3));

  * ii)

step-sizes $0<\gamma_{t}\leq\frac{1}{4L}$ with
$\sum_{t=1}^{\infty}\gamma_{t}^{2}=\Gamma<+\infty$.

Denote by $\mathcal{V}$ the neighborhood of $x^{\ast}$ on which Eq. 11 holds
with $p\leftarrow x^{\ast}$. Then, for any $r>0$ such that
$\mathcal{U}\coloneqq\mathbb{B}({x^{\ast}},{r})\cap\mathcal{K}$ is included in
both $\mathcal{V}$ and $\mathcal{B}$,

$\operatorname{\mathbb{P}}\left[{\left.\forall t\geq\frac{1}{2},\
X_{t}\in\mathcal{U}\right|D(x^{\ast},X_{1})+\phi_{1}\leq\frac{2r^{2}}{9}}\right]\geq
1-\frac{9(8+r^{2})\sigma^{2}\Gamma}{r^{2}\min(1,r^{2}/9)}\,,$

where $\phi_{1}=\frac{1}{2}\|X_{1}-X_{1/2}\|^{2}$.

###### Proof.

This proof mainly consists in applying Lemma B.3 indexed by
$t\in\frac{1}{2}\mathbb{N}^{*},\ t\geq 1$. Define $C=\frac{r^{2}}{2+1/4}$ and,
for $t\geq 1$, the following adapted processes,

$\displaystyle\zeta_{t}$ $\displaystyle\coloneqq 0$
$\displaystyle\zeta_{t+1/2}$ $\displaystyle\coloneqq\gamma_{t}\langle
v(X_{t+1/2}),X_{t+1/2}-x^{\ast}\rangle$ $\displaystyle\chi_{t+1/2}$
$\displaystyle\coloneqq 4\gamma_{t}^{2}\|U_{t}\|_{*}^{2}$
$\displaystyle\chi_{t+1}$ $\displaystyle\coloneqq
4\gamma_{t}^{2}\|U_{t+1/2}\|^{2}_{*}$ $\displaystyle\xi_{t+1/2}$
$\displaystyle\coloneqq 0$ $\displaystyle\xi_{t+1}$
$\displaystyle\coloneqq-\gamma_{t}\langle U_{t+1/2},X_{t+1/2}-x^{\ast}\rangle$
$\displaystyle D_{t}$ $\displaystyle\coloneqq D(x^{\ast},X_{t})+\phi_{t}$
$\displaystyle D_{t+1/2}$ $\displaystyle\coloneqq
D_{t}-\zeta_{t}+\chi_{t+1/2}+\xi_{t+1/2}\,.$

With these definitions, for any $t\in\mathbb{N}^{*},\ t\geq 1$,

$\displaystyle D_{t+1/2}$ $\displaystyle\leq
D_{t}-\zeta_{t}+\chi_{t+1/2}+\xi_{t+1/2}$ $\displaystyle D_{t+1}$
$\displaystyle\leq D_{t+1/2}-\zeta_{t+1/2}+\chi_{t+1}+\xi_{t+1}\,$

where the first inequality comes directly from the definition while the second
one comes from the descent inequality of Lemma B.2.

Now define the events, for $t\in\frac{1}{2}\mathbb{N}^{*},\ t\geq 1$,

$I_{t}=\\{D_{1}\leq C/2\\}\cap\bigcap_{s\in\frac{1}{2}\mathbb{N}:3/2\leq s\leq
t}\\{D_{s}\leq C\\}\cap\\{\chi_{s}^{2}\leq C/4\\}\,.$

We first show, by induction on $t\in\frac{1}{2}\mathbb{N}^{*},\ t\geq 1$,
that,
$I_{t}\subset\\{X_{s}\in\mathcal{U},s=\frac{1}{2},1,\dots,t-\frac{1}{2},t\\}$.

Initialization::

For $t=1$, the fact that $I_{1}\subset\\{X_{1/2}\in\mathcal{U}\\}$ comes from
the conditioning that $D(x^{\ast},X_{1})+\phi_{1}\leq C/2$ and by definition
of $\phi_{1}$ and the strong convexity of $h$ (Lemma A.1),

$\|X_{1/2}-x^{\ast}\|^{2}\leq
2(\|X_{1}-x^{\ast}\|^{2}+\|X_{1}-X_{1/2}\|^{2})\leq
4(D(x^{\ast},X_{1})+\phi_{1})\leq 2C\leq r^{2}.$

To show that $X_{1}\in\mathcal{U}$, use the strong convexity of $h$ (Lemma
A.1) to get that, on $I_{1}$,

$\|X_{1}-x^{\ast}\|^{2}\leq 2D(x^{\ast},X_{1})\leq 2D_{1}\leq C\leq r^{2}\,.$

Induction step for iterates::

Assume that, for some $t\geq 2$,
$I_{t-1/2}\subset\\{X_{s}\in\mathcal{U},s=\frac{1}{2},1,\dots,t-1,t-\frac{1}{2}\\}$.
By definition, the sequence of events $(I_{s})$ is non-increasing so that,
$I_{t}\subset\\{X_{s}\in\mathcal{U},s=\frac{1}{2},1,\dots,t-1,t-\frac{1}{2}\\}$.
Hence, we only have to show that $I_{t}\subset\\{X_{t}\in\mathcal{U}\\}$. But,
by definition, $I_{t}\subset\\{D_{t}\leq C\\}$. Again, using the strong
convexity of $h$ (Lemma A.1), on $I_{t}$,

$\|X_{t}-x^{\ast}\|^{2}\leq 2D(x^{\ast},X_{t})\leq 2D_{t}\leq
2C\leq{r^{2}}\,.$

Induction step for half-iterates::

Assume that, for some $t\geq 1$,
$I_{t}\subset\\{X_{s}\in\mathcal{U},s=\frac{1}{2},1,\dots,t-1,t\\}$. By
definition, the sequence of events $(I_{s})$ is non-increasing so that,
$I_{t+1/2}\subset\\{X_{s}\in\mathcal{U},s=\frac{1}{2},1,\dots,t-1,t\\}$. So we
focus on showing that $I_{t+1/2}\subset\\{X_{t+1/2}\in\mathcal{U}\\}$. For
this, apply the first statement of Lemma A.3 with
$(x,p,y,y^{\prime})\leftarrow(X_{t},x^{\ast},-\gamma_{t}(v(X_{t-1/2})+U_{t}),-\gamma_{t}v(x^{\ast}))$,

$D(x^{\ast},X_{t+1/2})\leq D(x^{\ast},X_{t})-\gamma_{t}\langle
v(X_{t-1/2})+U_{t}-v(x^{\ast}),X_{t+1/2}-x^{\ast}\rangle\,,$

and apply Young’s inequality twice to get

$\displaystyle D(x^{\ast},X_{t+1/2})$ $\displaystyle\leq
D(x^{\ast},X_{t})+\gamma_{t}^{2}\|v(X_{t-1/2})+U_{t}-v(x^{\ast})\|^{2}_{*}+\frac{1}{4}\|X_{t+1/2}-x^{\ast}\|^{2}$
$\displaystyle\leq
D(x^{\ast},X_{t})+2\gamma_{t}^{2}\|v(X_{t-1/2})-v(x^{\ast})\|^{2}_{*}+2\gamma_{t}^{2}\|U_{t}\|^{2}+\frac{1}{4}\|X_{t+1/2}-x^{\ast}\|^{2}\,.$

By the strong convexity of $h$ (Lemma A.1) and the Lipschitz continuity of $v$
(Assumption 1),

$\displaystyle\frac{1}{4}\|X_{t+1/2}-x^{\ast}\|^{2}$ $\displaystyle\leq
D(x^{\ast},X_{t})+2\gamma_{t}^{2}L^{2}\|X_{t-1/2}-x^{\ast}\|^{2}+2\gamma_{t}^{2}\|U_{t}\|^{2}\,.$

But, by definition, on $I_{t+1/2}$, $D(x^{\ast},X_{t})\leq C$, $X_{t-1/2}$ is
in $\mathcal{U}$ and $\chi_{t+1/2}=4\gamma_{t}^{2}\|U_{t}\|_{*}^{2}\leq C/4$.
Therefore,

$\displaystyle\frac{1}{4}\|X_{t+1/2}-x^{\ast}\|^{2}$
$\displaystyle\leq\left(1+\frac{1}{8}\right)C+2\gamma_{t}^{2}L^{2}r^{2}\,.$

Using the definition of $C$ and the bound on the step-size $\gamma_{t}\leq
1/(4L)$ ,

$\displaystyle\|X_{t+1/2}-x^{\ast}\|^{2}$
$\displaystyle\leq\frac{r^{2}}{2}+\frac{r^{2}}{2}=r^{2}\,,$

which concludes the induction step.

We now verify the assumptions needed to apply Lemma B.3:

  1. (i)

For $t\in\frac{1}{2}\mathbb{N}^{*},\ t\geq 1,\ \zeta_{t}\mathds{1}_{I_{t}}\geq
0$. If $t\in\mathbb{N}^{*}$, this is trivial as $\zeta_{t}=0$. Now, fix
$t\in\mathbb{N}^{*}$, $\zeta_{t+1/2}=\gamma_{t}\langle
v(X_{t+1/2}),X_{t+1/2}-x^{\ast}\rangle$. But, on $I_{t+1/2}$,
$X_{t+1/2}\in\mathcal{U}$ and so, by monotonicity of $v$ (Assumption 2),
$\langle v(X_{t+1/2}),X_{t+1/2}-x^{\ast}\rangle\geq 0$ on $I_{t+1/2}$.

  2. (ii)

For $t\in\frac{1}{2}\mathbb{N}^{*},\ t\geq 1,\
\operatorname{\mathbb{E}}\left[\left.\xi_{t+1/2}\,\right|\,\mathcal{F}_{t}\right]\mathds{1}_{I_{t}}=0$.
There is only something to prove when $t$ is of the form $t+\frac{1}{2}$ with
$t\in\mathbb{N}^{*}$. In this case, as $X_{t+1/2}$ is $\mathcal{F}_{t+1/2}$
measurable,

$\displaystyle\operatorname{\mathbb{E}}\left[\left.\xi_{t+1}\,\right|\,\mathcal{F}_{t+1/2}\right]$
$\displaystyle=-\gamma_{t}\langle\operatorname{\mathbb{E}}\left[\left.U_{t+1/2}\,\right|\,\mathcal{F}_{t+1/2}\right],X_{t+1/2}-x^{\ast}\rangle=0\,.$

  3. (iii)

$\sum_{t\in\frac{1}{2}\mathbb{N},\ t\geq
1}\operatorname{\mathbb{E}}\left(\left(\xi_{t+1/2}^{2}+\chi_{t+1/2}\right)\mathds{1}_{I_{t}}\right)\leq\delta\epsilon\operatorname{\mathbb{P}}(I_{1})$
with $\epsilon=\min(C^{2}/16,C/4)=\min(C/4,1)C/4$ and
$\delta=\frac{\sigma^{2}(8+r^{2})\Gamma}{\epsilon}$. For this let us first
bound each of the terms involved individually. For $t\in\mathbb{N}^{*}$, by
assumption on the noise and as $I_{t}$ is $\mathcal{F}_{t}$ measurable, and so
$\mathcal{F}_{t+1/2}$ measurable,

$\displaystyle\operatorname{\mathbb{E}}(\chi_{t+1/2}\mathds{1}_{I_{t}})$
$\displaystyle=4\gamma_{t}^{2}\operatorname{\mathbb{E}}\left(\|U_{t+1/2}\|_{*}^{2}\mathds{1}_{I_{t}}\right)$
$\displaystyle=4\gamma_{t}^{2}\operatorname{\mathbb{E}}\left(\operatorname{\mathbb{E}}\left[\left.\|U_{t+1/2}\|_{*}^{2}\,\right|\,\mathcal{F}_{t+1/2}\right]\mathds{1}_{I_{t}}\right)$
$\displaystyle\leq 4\gamma_{t}^{2}\sigma^{2}\operatorname{\mathbb{P}}(I_{t})$
$\displaystyle\leq
4\gamma_{t}^{2}\sigma^{2}\operatorname{\mathbb{P}}(I_{1})\,,$

where we used that the sequence of events $(I_{s})_{s}$ is non-increasing.
Likewise, $\operatorname{\mathbb{E}}(\chi_{t+1}\mathds{1}_{I_{t+1/2}})\leq
4\gamma_{t}^{2}\sigma^{2}\operatorname{\mathbb{P}}(I_{1})$. Now, by definition
of the dual norm,

$\displaystyle\operatorname{\mathbb{E}}(\xi_{t+1}^{2}\mathds{1}_{I_{t+1/2}})$
$\displaystyle=\gamma_{t}^{2}\operatorname{\mathbb{E}}\left(\langle
U_{t+1/2},X_{t+1/2}-x^{\ast}\rangle^{2}\mathds{1}_{I_{t+1/2}}\right)$
$\displaystyle\leq\gamma_{t}^{2}\operatorname{\mathbb{E}}\left(\|U_{t+1/2}\|_{*}^{2}\|X_{t+1/2}-x^{\ast}\|^{2}\mathds{1}_{I_{t+1/2}}\right)$
$\displaystyle\leq\gamma_{t}^{2}r^{2}\operatorname{\mathbb{E}}\left(\|U_{t+1/2}\|_{*}^{2}\mathds{1}_{I_{t+1/2}}\right)\,,$

where we used that $I_{t+1/2}\subset\\{X_{t+1/2}\in\mathcal{U}\\}$. Next, by
the law of total expectation and since $I_{t+1/2}$ is $\mathcal{F}_{t+1/2}$
measurable,

$\displaystyle\operatorname{\mathbb{E}}(\xi_{t+1}^{2}\mathds{1}_{I_{t+1/2}})$
$\displaystyle\leq\gamma_{t}^{2}r^{2}\operatorname{\mathbb{E}}\left(\operatorname{\mathbb{E}}\left[\left.\|U_{t+1/2}\|_{*}^{2}\,\right|\,\mathcal{F}_{t+1/2}\right]\mathds{1}_{I_{t+1/2}}\right)$
$\displaystyle\leq\gamma_{t}^{2}r^{2}\sigma^{2}\operatorname{\mathbb{P}}(I_{t+1/2})$
$\displaystyle\leq\gamma_{t}^{2}r^{2}\sigma^{2}\operatorname{\mathbb{P}}(I_{1})\,.$

Combining these bounds, we get,

$\displaystyle\sum_{t\in\frac{1}{2}\mathbb{N},\ t\geq
1}\operatorname{\mathbb{E}}\left(\left(\xi_{t+1/2}^{2}+\chi_{t+1/2}\right)\mathds{1}_{I_{t}}\right)$
$\displaystyle=\sum_{t\in\mathbb{N},\ t\geq
1}\operatorname{\mathbb{E}}\left(\xi_{t+1}^{2}\mathds{1}_{I_{t+1/2}}\right)+\sum_{t\in\mathbb{N},\
t\geq
1}\operatorname{\mathbb{E}}\left(\chi_{t+1/2}^{2}\mathds{1}_{I_{t}}\right)+\sum_{t\in\mathbb{N},\
t\geq
1}\operatorname{\mathbb{E}}\left(\chi_{t+1}^{2}\mathds{1}_{I_{t+1/2}}\right)$
$\displaystyle\leq\sigma^{2}(8+r^{2})\operatorname{\mathbb{P}}(I_{1})\sum_{t=1}^{+\infty}\gamma_{t}^{2}$
$\displaystyle\leq\underbrace{\frac{\sigma^{2}(8+r^{2})\Gamma}{\epsilon}}_{=\delta}\epsilon\operatorname{\mathbb{P}}(I_{1})\,,$

which corresponds to the statement.

Hence, Hsieh et al. (2020, Lem. F.1) gives that,

$\operatorname{\mathbb{P}}\left[\left.\bigcap_{t\in\frac{1}{2}\mathbb{N},\
t\geq 1}I_{t}\right|I_{1}\right]\geq 1-\delta\,,$

which implies our statement since $\bigcap_{t\in\frac{1}{2}\mathbb{N},\ t\geq
1}I_{t}\subset\\{\forall t\geq\frac{1}{2},\ X_{t}\in\mathcal{U}\\}$. ∎

##  Appendix C Convergence of optimistic mirror descent

###### Proof of Proposition 1.

  1. (1)

Start from Lemma B.2 which gives us the descent inequality

$\displaystyle D(x^{\ast},X_{t+1})+\phi_{t+1}\leq$ $\displaystyle
D(x^{\ast},X_{t})+(1-\gamma_{t}\mu)\phi_{t}-\gamma_{t}\langle
V_{t+1/2},X_{t+1/2}-x^{\ast}\rangle$ (C.1)
$\displaystyle+\left(4\gamma_{t}^{2}L^{2}-\frac{1}{2}\right)\|X_{t+1/2}-X_{t}\|^{2}+4\gamma_{t}^{2}(\|U_{t+1/2}\|_{*}^{2}+\|U_{t-1/2}\|_{*}^{2})\,$

where $\phi_{t}=\frac{\gamma_{t-1}^{2}}{2}\|V_{t-1/2}-V_{t-3/2}\|^{2}$ for all
$t\geq 2$, and $\phi_{1}=\frac{1}{2}\|X_{1}-X_{1/2}\|^{2}=0$ by assumption.

  2. (2)

The first part of the result comes the stochastic stability lemma Lemma B.4
(which relies on Hsieh et al. (2020)), where we use that the stepsize choice
is square-summable with

$\sum_{t=1}^{+\infty}\gamma_{t}^{2}=\gamma\leq\frac{\gamma^{2}}{(2\eta-1)t_{0}^{2\eta-1}}.$
(C.2)

  3. (3)

We now focus on proving the rates of convergence. Take $r>0$ small enough so
that $\mathcal{U}\coloneqq\mathbb{B}({x^{\ast}},{r})\cap\mathcal{K}$ is
included in both $\mathcal{V}$ and $\mathcal{B}$.

Define the event $\mathcal{E}_{t}=\\{\forall 1\leq s\leq t,\
X_{s+1/2}\in\mathcal{U}\\}$ for $t\geq 0$. Note that, except for $t=0$,
$\mathcal{E}_{t}$ is $\mathcal{F}_{t+1/2}$ is measurable. On this event, we
can apply Lemma A.6 with $x\leftarrow X_{t}$ to get,

$\langle
v(X_{t+1/2}),X_{t+1/2}-x^{\ast}\rangle\geq\frac{\mu}{2}\|X_{t}-x^{\ast}\|^{2}-\mu\|X_{t+1/2}-X_{t}\|^{2}\,.$

and using the Legendre exponent of $h$, we get

$\langle
v(X_{t+1/2}),X_{t+1/2}-x^{\ast}\rangle\geq\frac{\mu}{\kappa}D(x^{\ast},X_{t})^{1+\alpha}-\mu\|X_{t+1/2}-X_{t}\|^{2}\,.$

  4. (4)

Combining this with the descent inequality above Eq. C.1, and the fact that
$\kappa\geq 1$,

$\displaystyle(D(x^{\ast},X_{t+1})+\phi_{t+1})\mathds{1}_{\mathcal{E}_{t}}$
$\displaystyle\leq(D(x^{\ast},X_{t})-\frac{\mu\gamma_{t}}{\kappa}D(x^{\ast},X_{t})^{1+\alpha}+(1-\frac{\gamma_{t}\mu}{\kappa})\phi_{t})\mathds{1}_{\mathcal{E}_{t}}-\gamma_{t}\langle
U_{t+1/2},X_{t+1/2}-x^{\ast}\rangle\mathds{1}_{\mathcal{E}_{t}}$
$\displaystyle~{}~{}~{}~{}~{}+\left(4\gamma_{t}^{2}L^{2}+\mu\gamma_{t}-\frac{1}{2}\right)\|X_{t+1/2}-X_{t}\|^{2}\mathds{1}_{\mathcal{E}_{t}}+4\gamma_{t}^{2}(\|U_{t+1/2}\|_{*}^{2}+\|U_{t-1/2}\|_{*}^{2})\mathds{1}_{\mathcal{E}_{t}}\,.$

Now, the sequence of events $(\mathcal{E}_{s})_{s\geq 0}$ is non-increasing,
so $\mathds{1}_{\mathcal{E}_{t}}\leq\mathds{1}_{\mathcal{E}_{t-1}}\leq 1$. As
a consequence,

$\displaystyle\left(D(x^{\ast},X_{t})-\frac{\mu\gamma_{t}}{\kappa}D(x^{\ast},X_{t})^{1+\alpha}+(1-\frac{\gamma_{t}\mu}{\kappa})\phi_{t}\right)\mathds{1}_{\mathcal{E}_{t}}$
$\displaystyle\leq\left(D(x^{\ast},X_{t})-\frac{\mu\gamma_{t}}{\kappa}D(x^{\ast},X_{t})^{1+\alpha}+(1-\gamma_{t}\mu)\phi_{t}\right)\mathds{1}_{\mathcal{E}_{t-1}}\,.$

Note that the term between parenthesis is always non-negative even when
$\alpha>0$.

Moreover, by the choice of $\gamma$,
$4\gamma_{t}^{2}L^{2}+\mu\gamma_{t}-\frac{1}{2}\leq 0$. Therefore, the descent
inequality can be simplified to give,

$\displaystyle\left(D(x^{\ast},X_{t+1})+\phi_{t+1}\right)\mathds{1}_{\mathcal{E}_{t}}$
$\displaystyle\leq\left(D(x^{\ast},X_{t})-\frac{\mu\gamma_{t}}{\kappa}D(x^{\ast},X_{t})^{1+\alpha}+(1-\frac{\gamma_{t}\mu}{\kappa})\phi_{t}\right)\mathds{1}_{\mathcal{E}_{t-1}}-\gamma_{t}\langle
U_{t+1/2},X_{t+1/2}-x^{\ast}\rangle\mathds{1}_{\mathcal{E}_{t}}$
$\displaystyle~{}~{}~{}~{}+4\gamma_{t}^{2}(\|U_{t+1/2}\|_{*}^{2}+\|U_{t-1/2}\|_{*}^{2})\,.$

We now take the expectation of this inequality. For this, note that, as
$\mathcal{E}_{t}$ is $\mathcal{F}_{t+1/2}$ measurable,

$\displaystyle\operatorname{\mathbb{E}}\left[\langle
U_{t+1/2},X_{t+1/2}-x^{\ast}\rangle\mathds{1}_{\mathcal{E}_{t}}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\operatorname{\mathbb{E}}\left[\left.\langle
U_{t+1/2},X_{t+1/2}-x^{\ast}\rangle\mathds{1}_{\mathcal{E}_{t}}\,\right|\,\mathcal{F}_{t+1/2}\right]\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\langle\operatorname{\mathbb{E}}\left[\left.U_{t+1/2}\,\right|\,\mathcal{F}_{t+1/2}\right],X_{t+1/2}-x^{\ast}\rangle\mathds{1}_{\mathcal{E}_{t}}\right]$
$\displaystyle=0\,.$

As a consequence, and using the assumption on the noise,

$\displaystyle\operatorname{\mathbb{E}}\left[(D(x^{\ast},X_{t+1})+\phi_{t+1})\mathds{1}_{\mathcal{E}_{t}}\right]$
(C.3)
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\left(D(x^{\ast},X_{t})-\frac{\mu\gamma_{t}}{\kappa}D(x^{\ast},X_{t})^{1+\alpha}+\left(1-\frac{\gamma_{t}\mu}{\kappa}\right)\phi_{t}\right)\mathds{1}_{\mathcal{E}_{t-1}}\right]+8\gamma_{t}^{2}\sigma^{2}\,.$

  5. (5)

The final step will be to study the sequence $(a_{t})$ defined by
$a_{t}=\operatorname{\mathbb{E}}\left[(D(x^{\ast},X_{t})+\phi_{t})\mathds{1}_{\mathcal{E}_{t-1}}\right]$
for all $t\geq 1$. Indeed, a bound on
$a_{t}=\operatorname{\mathbb{E}}\left((D(x^{\ast},X_{t})+\phi_{t})\mathds{1}_{\mathcal{E}_{t-1}}\right)$
implies a bound on the quantity of interest,

$\operatorname{\mathbb{E}}\left(D(x^{\ast},X_{t})+\phi_{t}\mid\mathcal{E}_{\mathcal{U}}\right)\,.$

As $\mathcal{E}_{\mathcal{U}}\subset\mathcal{E}_{t}$,

$\displaystyle\operatorname{\mathbb{E}}\left[D(x^{\ast},X_{t})+\phi_{t}\mid\mathcal{E}_{\mathcal{U}}\right]$
$\displaystyle=\frac{\operatorname{\mathbb{E}}\left[(D(x^{\ast},X_{t})+\phi_{t})\mathds{1}_{\mathcal{E}}\right]}{\operatorname{\mathbb{P}}[\mathcal{E}_{\mathcal{U}}]}$
$\displaystyle\leq\frac{\operatorname{\mathbb{E}}\left[(D(x^{\ast},X_{t})+\phi_{t})\mathds{1}_{\mathcal{E}_{t}}\right]}{\operatorname{\mathbb{P}}[\mathcal{E}_{\mathcal{U}}]}\,$

Now, the inequality Eq. C.3 above can be rewritten as follows,

$\displaystyle a_{t+1}\leq
a_{t}-\frac{\mu\gamma_{t}}{\kappa}\operatorname{\mathbb{E}}\left[\left(D(x^{\ast},X_{t})^{1+\alpha}+\phi_{t}\right)\mathds{1}_{\mathcal{E}_{t-1}}\right]+8\gamma_{t}^{2}\sigma^{2}\,.$
(C.4)

  6. (6)

Now, the behavior of this sequence depends heavily on the Legendre exponent
$\alpha$:

     * •

If $\alpha=0$, (C.4) becomes

$\displaystyle
a_{t+1}\leq\left(1-\frac{\mu\gamma}{\kappa(t+t_{0})^{\eta}}\right)a_{t}+\frac{8\gamma^{2}\sigma^{2}}{(t+t_{0})^{2\eta}}\,.$

Then, for $\eta=1$, Lemma A.8 can be applied with the additional assumption
that $\gamma>\frac{\kappa}{\mu}$ to get that for any $T\geq 1$,
$a_{T}=\mathcal{O}(1/T)$.

For $\frac{1}{2}<\eta<1$, Lemma A.9 can be directly apply to obtain
$a_{T}=\mathcal{O}(1/T^{\eta})$.

     * •

If $\alpha>0$, a little more work has to be done before on (C.4) before
concluding. First, (C.4) implies that for any $t\geq 1$, $a_{t}\leq
a_{0}+8\sigma^{2}\sum_{t=1}^{\infty}\gamma_{t}^{2}$ and since we assume
$D(x^{\ast},X_{1})+\phi_{1}=D(x^{\ast},X_{1})\leq\frac{r^{2}}{12}$ we have
that

$\displaystyle\operatorname{\mathbb{E}}\left[\phi_{t}\mathds{1}_{\mathcal{E}_{t-1}}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[(D(x^{\ast},X_{t})+\phi_{t})\mathds{1}_{\mathcal{E}_{t-1}}\right]=a_{t}$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[(D(x^{\ast},X_{1})+\phi_{1})\mathds{1}_{\mathcal{E}_{0}}\right]+8\sigma^{2}\sum_{t=1}^{\infty}\gamma_{t}^{2}$
$\displaystyle\leq\underbrace{\frac{r^{2}}{12}+\frac{8\sigma^{2}\gamma^{2}}{(2\eta-1)t_{0}^{2\eta-1}}}_{:=\Phi}.$

As a consequence,
$-\operatorname{\mathbb{E}}\left[\phi_{t}\mathds{1}_{\mathcal{E}_{t-1}}\right]\leq-\operatorname{\mathbb{E}}\left[\phi_{t}\mathds{1}_{\mathcal{E}_{t-1}}\right]^{1+\alpha}/\Phi^{\alpha}$,
and thus (C.4) gives us

$\displaystyle a_{t+1}$ $\displaystyle\leq
a_{t}-\frac{\mu\gamma_{t}}{\kappa}\operatorname{\mathbb{E}}\left[\left(D(x^{\ast},X_{t})^{1+\alpha}+\frac{1}{\Phi^{\alpha}}\phi_{t}^{1+\alpha}\right)\mathds{1}_{\mathcal{E}_{t-1}}\right]+8\gamma_{t}^{2}\sigma^{2}$
$\displaystyle\leq
a_{t}-\frac{\mu\gamma_{t}}{2^{\alpha}\max(1,\Phi^{\alpha})\kappa}\operatorname{\mathbb{E}}\left[\left(D(x^{\ast},X_{t})+\phi_{t}\right)^{1+\alpha}\mathds{1}_{\mathcal{E}_{t-1}}\right]+8\gamma_{t}^{2}\sigma^{2}$
$\displaystyle\leq
a_{t}-\frac{\mu\gamma_{t}}{2^{\alpha}\max(1,\Phi^{\alpha})\kappa}a_{t}^{1+\alpha}+8\gamma_{t}^{2}\sigma^{2}$

where the second inequality comes from the fact that
$(x+y)^{1+\alpha}/2^{\alpha}\leq x^{1+\alpha}+y^{1+\alpha}$ for positive $x,y$
and the last one from Jensen inequality applied to the convex function
$x\mapsto x^{1+\alpha}$.

We will now apply one of Lemmas A.11 and A.12 to the sequence $(a_{t})$. To
make this step clear, let us introduce the same notations as these lemmas.
Define

$\displaystyle
q\coloneqq\frac{\mu\gamma}{2^{\alpha}\max(1,\Phi^{\alpha})\kappa}\quad\text{and}\quad
q^{\prime}\coloneqq 8\sigma^{2}\gamma^{2}\,.$

With these notations, the descent inequality can be rewritten as,

$a_{t+1}\leq
a_{t}-\frac{q}{(t+t_{0})^{\eta}}a_{t}^{1+\alpha}+\frac{q^{\prime}}{(t+t_{0})^{2\eta}}\,.$

Both Lemmas A.11 and A.12 require that,

$q^{\prime}q^{1/\alpha}\leq
c(\eta,\alpha)\iff\gamma^{2+\frac{1}{\alpha}}\leq\frac{c(1,\alpha)}{4\sigma^{2}(\mu/\kappa)^{{1/\alpha}}}\max(1,\Phi)\,.$

Finally, we distinguish two cases.

       * –

If $\eta\geq\frac{1+\alpha}{1+2\alpha}$, we apply Lemma A.11 to get that, for
any $T\geq 1$,

$a_{T}\leq\frac{a_{1}+b}{\left(1+\alpha(a_{1}+b)^{\alpha}2^{-\alpha}\sum_{t=1}^{T-1}\frac{q}{(t+t_{0})^{\eta}}\right)^{1/\alpha}}\,,$

where $b=\left(\frac{1-2^{1-2\eta}}{(1+\alpha)q}\right)^{\frac{1}{\alpha}}$.
Using asymptotic notations, this simply means that,

$a_{T}=\mathcal{O}\left(\left(\sum_{t=1}^{T-1}\frac{1}{(t+t_{0})^{\eta}}\right)^{-1/\alpha}\right)\,.$

The final bound on $a_{T}$ now comes from the fact that,

$\sum_{t=1}^{T-1}\frac{1}{(t+t_{0})^{\eta}}=\begin{cases}\Theta\left(T^{1-\eta}\right)&\text{
if }\eta<1\\\ \Theta\left(\log T\right)&\text{ if }\eta=1\,.\end{cases}$

       * –

If $\eta\leq\frac{1+\alpha}{1+2\alpha}$, we apply Lemma A.12 to get that, for
any $T\geq 1$,

$a_{T}\leq\frac{a_{1}}{\left(1+\alpha
a_{1}^{\alpha}\sum_{t=1}^{T-1}\frac{q}{(t+t_{0})^{\eta}}\right)^{1/\alpha}}+\frac{1}{((1+\alpha)q)^{\frac{1}{\alpha}}{(t+t_{0})}^{\eta}}\,.$

In other words, the sequence $(a_{t})$ satisfies, as $\eta<1$,

$a_{T}=\mathcal{O}\left(\frac{1}{T^{(1-\eta)/\alpha}}\right)+\mathcal{O}\left(\frac{1}{T^{\eta}}\right)\,.$

∎

##  Appendix D Numerical experiments

We describe here the setup used in the illustration of Theorem 1 and provide
additional plots.

We consider a simple $1$-dimensional example with $\mathcal{K}=[0,+\infty)$
and $v(x)=x$; the solution of the associated variational inequality is thus
$x^{\ast}=0$. It is direct to see that $v$ is $L=1$ Lipschitz continuous and
$\mu=1$ strongly monotone. We consider the three Bregman regularizers of our
running examples on $\mathcal{K}=[0,+\infty)$:

  * •

_Euclidean projection_ (Example 3.1): $h(x)=x^{2}/2$ for which
$D(x^{\ast},x)=x^{2}/2$, and $\beta=0$;

  * •

_Negative entropy_ (Example 3.2): $h(x)=x\log x$ for which $D(x^{\ast},x)=x$
and $\beta=1/2$ at $x^{\ast}$;

  * •

_Tsallis entropy_ (Example 3.3): $h(x)=-\frac{1}{q(1-q)}x^{q}$ for which
$D(x^{\ast},x)=x^{q}/q$ and $\beta=\max(0,1-q/2)$ at $x^{\ast}$. To show
different behaviors we consider $q=0.5$ ($\beta=0.75$) and $q=1.5$
($\beta=0.25$).

For each of these regularizers, we run OMD initialized with
$X_{1}=X_{1/2}=0.1$, $(U_{t})$ an i.i.d. Gaussian noise process with mean $0$
and variance $\sigma^{2}=10^{-4}$. We choose our stepsize sequence as
$\gamma_{t}=\frac{1}{t^{\eta}}$ with $\eta$ as prescribed by Theorem 1. We
display the results averaged over $100$ runs.

$\displaystyle{10^{0}}$$\displaystyle{10^{1}}$$\displaystyle{10^{2}}$$\displaystyle{10^{3}}$$\displaystyle{10^{4}}$$\displaystyle{10^{5}}$$\displaystyle{10^{-8}}$$\displaystyle{10^{-6}}$$\displaystyle{10^{-4}}$$\displaystyle{10^{-2}}$iteration$D(x^{\ast},X_{t})$Euclidean
Entropy Tsallis ($q=0.5$)Tsallis ($q=1.5$)

Figure 2. Convergence of OMD with different DGFs in terms of Bregman
divergence to the solution.

We find out that the observed rates match the theory:

Regularizer | $\beta$ | $\gamma_{t}$ | Theoretical rate | Observed rate (by regression)
---|---|---|---|---
A Euclidean | $0$ | $\frac{1}{t}$ | $\frac{1}{t}$ | $\frac{1}{t^{0.99}}$
A Entropy | $0.5$ | $\frac{1}{t^{0.5+\epsilon}}$ | $\frac{1}{t^{0.5+\epsilon}}$ | $\frac{1}{t^{0.48}}$
A Tsallis ($q=0.5$) | $0.75$ | $\frac{1}{t^{0.5+\epsilon}}$ | $\frac{1}{t^{0.1666}}$ | $\frac{1}{t^{0.13}}$
A Tsallis ($q=1.5$) | $0.25$ | $\frac{1}{t^{0.75}}$ | $\frac{1}{t^{0.75}}$ | $\frac{1}{t^{0.71}}$

## Acknowledgments

This research was partially supported by 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 grants ORACLESS (ANR-16-CE33-0004) and ALIAS
(ANR-19-CE48-0018-01).

## References

  * Alvarez et al. (2004) Felipe Alvarez, Jérôme Bolte, and Olivier Brahic.  Hessian Riemannian gradient flows in convex programming.  _SIAM Journal on Control and Optimization_ , 43(2):477–501, 2004.
  * Arora et al. (2012) Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: A meta-algorithm and applications.  _Theory of Computing_ , 8(1):121–164, 2012.
  * Auer et al. (1995) Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire.  Gambling in a rigged casino: The adversarial multi-armed bandit problem.  In _Proceedings of the 36th Annual Symposium on Foundations of Computer Science_ , 1995.
  * Bauschke & Combettes (2017) Heinz H. Bauschke and Patrick L. Combettes.  _Convex Analysis and Monotone Operator Theory in Hilbert Spaces_.  Springer, New York, NY, USA, 2 edition, 2017.
  * Bauschke et al. (2017) Heinz H. Bauschke, Jérôme Bolte, and Marc Teboulle.  A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications.  _Mathematics of Operations Research_ , 42(2):330–348, May 2017.
  * Beck & Teboulle (2003) Amir Beck and Marc Teboulle.  Mirror descent and nonlinear projected subgradient methods for convex optimization.  _Operations Research Letters_ , 31(3):167–175, 2003.
  * Bomze et al. (2019) Immanuel M. Bomze, Panayotis Mertikopoulos, Werner Schachinger, and Mathias Staudigl.  Hessian barrier algorithms for linearly constrained optimization problems.  _SIAM Journal on Optimization_ , 29(3):2100–2127, 2019.
  * Bruck Jr. (1977) Ronald E. Bruck Jr.  On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space.  _Journal of Mathematical Analysis and Applications_ , 61(1):159–164, November 1977.
  * Bubeck (2015) Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Foundations and Trends in Machine Learning_ , 8(3-4):231–358, 2015.
  * Chen & Teboulle (1993) Gong Chen and Marc Teboulle.  Convergence analysis of a proximal-like minimization algorithm using Bregman functions.  _SIAM Journal on Optimization_ , 3(3):538–543, August 1993.
  * Chiang et al. (2012) Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu.  Online optimization with gradual variations.  In _COLT ’12: Proceedings of the 25th Annual Conference on Learning Theory_ , 2012.
  * Chung (1954) Kuo-Liang Chung.  On a stochastic approximation method.  _The Annals of Mathematical Statistics_ , 25(3):463–483, 1954.
  * Coucheney et al. (2015) Pierre Coucheney, Bruno Gaujal, and Panayotis Mertikopoulos.  Penalty-regulated dynamics and robust learning procedures in games.  _Mathematics of Operations Research_ , 40(3):611–633, August 2015.
  * Cui & Shanbhag (2016) Shisheng Cui and Uday V. Shanbhag.  On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems.  In _CDC ’16: Proceedings of the 57th IEEE Annual Conference on Decision and Control_ , 2016.
  * Daskalakis & Panageas (2019) Constantinos Daskalakis and Ioannis Panageas.  Last-iterate convergence: Zero-sum games and constrained min-max optimization.  In _ITCS ’19: Proceedings of the 10th Conference on Innovations in Theoretical Computer Science_ , 2019.
  * Daskalakis et al. (2018) Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training GANs with optimism.  In _ICLR ’18: Proceedings of the 2018 International Conference on Learning Representations_ , 2018.
  * Facchinei & Pang (2003) Francisco Facchinei and Jong-Shi Pang.  _Finite-Dimensional Variational Inequalities and Complementarity Problems_.  Springer Series in Operations Research. Springer, 2003.
  * Gidel et al. (2019) Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien.  A variational inequality perspective on generative adversarial networks.  In _ICLR ’19: Proceedings of the 2019 International Conference on Learning Representations_ , 2019.
  * Golowich et al. (2020a) Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis.  Tight last-iterate convergence rates for no-regret learning in multi-player games.  In _NeurIPS ’20: Proceedings of the 34th International Conference on Neural Information Processing Systems_ , 2020a.
  * Golowich et al. (2020b) Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar.  Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems.  In _COLT ’20: Proceedings of the 33rd Annual Conference on Learning Theory_ , 2020b.
  * Hazan (2012) Elad Hazan.  A survey: The convex optimization approach to regret minimization.  In Suvrit Sra, Sebastian Nowozin, and Stephen J. Wright (eds.), _Optimization for Machine Learning_ , pp. 287–304. MIT Press, 2012.
  * Hsieh et al. (2019) Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos.  On the convergence of single-call stochastic extra-gradient methods.  In _NeurIPS ’19: Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , pp. 6936–6946, 2019.
  * Hsieh et al. (2020) Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos.  Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling.  In _NeurIPS ’20: Proceedings of the 34th International Conference on Neural Information Processing Systems_ , 2020.
  * Hsieh et al. (2021) Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos.  Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium.  In _COLT ’21: Proceedings of the 34th Annual Conference on Learning Theory_ , 2021.
  * Iusem et al. (2017) Alfredo N. Iusem, Alejandro Jofré, Roberto I. Oliveira, and Philip Thompson.  Extragradient method with variance reduction for stochastic variational inequalities.  _SIAM Journal on Optimization_ , 27(2):686–724, 2017.
  * Juditsky et al. (2011) Anatoli Juditsky, Arkadi Semen Nemirovski, and Claire Tauvel.  Solving variational inequalities with stochastic mirror-prox algorithm.  _Stochastic Systems_ , 1(1):17–58, 2011.
  * Kiwiel (1997) Krzysztof C. Kiwiel.  Proximal minimization methods with generalized Bregman functions.  _SIAM Journal on Control and Optimization_ , 35:1142–1168, 1997.
  * Korpelevich (1976) G. M. Korpelevich.  The extragradient method for finding saddle points and other problems.  _Èkonom. i Mat. Metody_ , 12:747–756, 1976.
  * Lattimore & Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit Algorithms_.  Cambridge University Press, Cambridge, UK, 2020.
  * Malitsky (2015) Yura Malitsky.  Projected reflected gradient methods for monotone variational inequalities.  _SIAM Journal on Optimization_ , 25(1):502–520, 2015.
  * Martinet (1970) B. Martinet.  Régularisation d’inéquations variationnelles par approximations successives.  _ESAIM: Mathematical Modelling and Numerical Analysis_ , 4(R3):154–158, 1970.
  * Mertikopoulos & Sandholm (2016) Panayotis Mertikopoulos and William H. Sandholm.  Learning in games via reinforcement and regularization.  _Mathematics of Operations Research_ , 41(4):1297–1324, November 2016.
  * Mertikopoulos & Sandholm (2018) Panayotis Mertikopoulos and William H. Sandholm.  Riemannian game dynamics.  _Journal of Economic Theory_ , 177:315–364, September 2018\.
  * Mertikopoulos & Staudigl (2018) Panayotis Mertikopoulos and Mathias Staudigl.  Stochastic mirror descent dynamics and their convergence in monotone variational inequalities.  _Journal of Optimization Theory and Applications_ , 179(3):838–867, December 2018.
  * Mertikopoulos & Zhou (2019) 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.
  * Mertikopoulos et al. (2019) Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras.  Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile.  In _ICLR ’19: Proceedings of the 2019 International Conference on Learning Representations_ , 2019.
  * Mokhtari et al. (2019a) Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil.  A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach.  https://arxiv.org/abs/1901.08511v2, 2019a.
  * Mokhtari et al. (2019b) Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil.  Convergence rate of $\mathcal{O}(1/k)$ for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems.  https://arxiv.org/pdf/1906.01115.pdf, 2019b.
  * Nemirovski (2004) Arkadi Semen Nemirovski.  Prox-method with rate of convergence ${O}(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems.  _SIAM Journal on Optimization_ , 15(1):229–251, 2004.
  * Nemirovski & Yudin (1983) Arkadi Semen Nemirovski and David Berkovich Yudin.  _Problem Complexity and Method Efficiency in Optimization_.  Wiley, New York, NY, 1983.
  * Nemirovski et al. (2009) Arkadi Semen Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on Optimization_ , 19(4):1574–1609, 2009.
  * Nesterov (2007) Yurii Nesterov.  Dual extrapolation and its applications to solving variational inequalities and related problems.  _Mathematical Programming_ , 109(2):319–344, 2007\.
  * Nesterov (2009) Yurii Nesterov.  Primal-dual subgradient methods for convex problems.  _Mathematical Programming_ , 120(1):221–259, 2009\.
  * Passty (1979) Gregory B. Passty.  Ergodic convergence to a zero of the sum of monotone operators in Hilbert space.  _Journal of Mathematical Analysis and Applications_ , 72(2):383–390, December 1979.
  * Polyak (1987) Boris Teodorovich Polyak.  _Introduction to Optimization_.  Optimization Software, New York, NY, USA, 1987.
  * Popov (1980) Leonid Denisovich Popov.  A modification of the Arrow–Hurwicz method for search of saddle points.  _Mathematical Notes of the Academy of Sciences of the USSR_ , 28(5):845–848, 1980.
  * Rakhlin & Sridharan (2013a) Alexander Rakhlin and Karthik Sridharan.  Online learning with predictable sequences.  In _COLT ’13: Proceedings of the 26th Annual Conference on Learning Theory_ , 2013a.
  * Rakhlin & Sridharan (2013b) Alexander Rakhlin and Karthik Sridharan.  Optimization, learning, and games with predictable sequences.  In _NIPS ’13: Proceedings of the 27th International Conference on Neural Information Processing Systems_ , 2013b.
  * Rockafellar (1976) Ralph Tyrrell Rockafellar.  Monotone operators and the proximal point algorithm.  _SIAM Journal on Optimization_ , 14(5):877–898, 1976.
  * Shalev-Shwartz (2011) Shai Shalev-Shwartz.  Online learning and online convex optimization.  _Foundations and Trends in Machine Learning_ , 4(2):107–194, 2011.
  * Tsallis (1988) Constantino Tsallis.  Possible generalization of Boltzmann–Gibbs statistics.  _Journal of Statistical Physics_ , 52:479–487, 1988.
  * von Neumann (1928) John von Neumann.  Zur Theorie der Gesellschaftsspiele.  _Mathematische Annalen_ , 100:295–320, 1928.  Translated by S. Bargmann as “On the Theory of Games of Strategy” in A. Tucker and R. D. Luce, editors, _Contributions to the Theory of Games IV_ , volume 40 of _Annals of Mathematics Studies_ , pages 13-42, 1957, Princeton University Press, Princeton.
  * Zhou et al. (2020) 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):687–716, 2020.

  *[OMD]: optimistic mirror descent
  *[EG]: extra-gradient
  *[VI]: variational inequality
  *[DGF]: distance-generating function
  *[MP]: mirror-prox
  *[MD]: mirror descent
  *[VIs]: variational inequality
  *[DGFs]: distance-generating function
  *[KKT]: Karush–Kuhn–Tucker
  *[OMWU]: optimistic multiplicative weights update