Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling

Introduction

A major obstacle in the training of GAN is the lack of an implementable, strongly convergent method based on stochastic gradients. The reason for this is that the coupling of two (or more) neural networks gives rise to behaviors and phenomena that do not occur when minimizing an individual loss function, irrespective of the complexity of its landscape. As a result, there has been significant interest in the literature to codify the failures of GAN training, and to propose methods that could potentially overcome them.

Perhaps the most prominent of these failures is the appearance of cycles and, potentially, the transition to aperiodic orbits and chaos . Surprisingly, non-convergent phenomena of this kind are observed even in very simple saddle-point problems such as two-dimensional, unconstrained bilinear games . In view of this, it is quite common to examine the convergence (or non-convergence) of a gradient training scheme in bilinear models before applying it to more complicated, non-convex/non-concave problems.

A key observation here is that the non-convergence of standard gradient descent-ascent methods in bilinear saddle-point problems can be overcome by incorporating a “gradient extrapolation” step before performing an update. The resulting algorithm, due to Korpelevich 1976, is known as the EG (EG) method, and it has a long history in optimization; for an appetizer, see Facchinei & Pang 2003, Juditsky et al. 2011, Nemirovski 2004, Nesterov 2007, and references therein. In particular, the EG algorithm converges for all pseudomonotone VI (a large problem class that contains all bilinear games, cf. ), and the time-average of the generated iterates achieves an $\bigoh(1/t)$ rate of convergence in monotone problems .

The above concerns the application of EG methods with perfect, deterministic gradients and a non-vanishing stepsize. By contrast, in the type of saddle-point problems that are encountered in machine learning (GAN, robust reinforcement learning, etc.), there are two important points to keep in mind: First, the size of the datasets involved precludes the use of full gradients (for more than a few passes at least), so the method must be run with stochastic gradients instead. Second, because the landscapes encountered are not convex-concave, the method’s last iterate is typically preferred to its time-average (which offers no tangible benefits when Jensen’s inequality no longer applies). We are thus led to the following questions: 1. are the superior last-iterate convergence properties of the EG (EG) algorithm retained in the stochastic setting?And, if not, 2. is there a principled modification that would restore them?

To motivate our analysis, we first analyse a counterexample to show that the last iterate of stochastic EG fails to converge, even in bilinear min-max problems where deterministic EG methods converge from any initialization. We then consider a class of DSEG (DSEG) methods with an exploration step evolving more aggressively than the update step and prove it enjoys better convergence guarantees than standard EG in stochastic problems. In more detail:

We show that the DSEG (DSEG) algorithm converges with probability $1$ in a large class of problems that contains all monotone saddle-point problems.

We derive explicit convergence rates for the algorithm’s last iterate under an error bound condition. This is the first time that such condition is considered in the analysis of stochastic EG methods, albeit its popularity in the optimization community.

For bilinear min-max problems in particular, our analysis establishes that stochastic DSEG methods converge at a $\bigoh(1/t)$ rate. Prior to our work, last-iterate convergence rate for bilinear min-max games had only been studied in the deterministic setting. Let us still mention the work of Loizou et al. 2020 which appeared on arxiv a few weeks after the submission of our manuscript: it proved that stochastic Hamiltonian methods applied to (sufficiently) bilinear games ensures also a $\bigoh(1/t)$ convergence rate. Nonetheless, Hamiltoninan gradient descent is not guaranteed to converge to a solution in monotone games and in general when it converges, it may converge to an unstable stationary point.

To account for non-monotone problems, we also provide local versions of these results that hold with (arbitrarily) high probability. Importantly, thanks to the use of a local error bound condition, we can obtain local convergence rates even if the Jacobian at a solution contains purely imaginary eigenvalues.

Related works.

The approaches that have been explored in the literature to ensure the convergence of stochastic first-order methods, in monotone problems and beyond, include variance reduction with increasing batch size and schemes with vanishing regularization (or “anchoring”). In regard to the former, Iusem et al. 2017 showed that using increasing batch size can ensure convergence in pseudomonotone VI. As for the latter, Koshal et al. 2012 and Ryu et al. 2019 regularized the problem via the addition of a strongly monotone term with vanishing weight; by properly controlling the weight reduction schedule of this regularization term, it is possible to show the method’s convergence in monotone problems.

In contrast to the above, our approach is based on a modification of the choice of the stepsizes, which has only been studied theoretically in the deterministic setting. Zhang & Yu 2020 recently examined the convergence of several gradient-based algorithms in unconstrained zero-sum bilinear games with deterministic oracle feedback. Interestingly, they show that the optimal (geometric) rate of convergence in bilinear games is recovered for asymptotically large “exploration” parameters $\gamma\to\infty$ and infinitesimally small “update” parameters $\eta\to 0$. Even though the setting there is quite different from our own, it is interesting to note that the principle of a smaller update stepsize also applies in their case – see also Liang & Stokes 2019 and Mishchenko et al. 2020 for a concurrent series of results, and Ryu et al. 2019 for an empirical investigation into the stochastic setting.

Regarding convergence counterexamples, in a recent paper, Chavdarova et al. 2019 showed that if EG is run with a constant stepsize and noise with unbounded variance, the method’s iterates actually diverge at a geometric rate. Motivated by this, they proposed a SVRG-type variance reduced EG method for finite-sum problems and proved a geometric convergence of the algorithm when the involved operator is strongly monotone. Compared to this situation, our counterexample illustrates that the non-convergence persists for any error distribution with positive variance (no matter how small) and any stepsize sequence (constant, decreasing, or otherwise). In particular, if EG is run with noisy feedback, its trajectories remain non-convergent even if the noise is almost surely bounded and a vanishing stepsize schedule is employed.

Finally, to make our paper’s position clear with respect to the large corpus of work on stochastic EG methods, we further provide an overview of the most relevant results in Table 1 and refer the interested reader to the supplement for further discussion.

Preliminaries

In this section, we briefly review some basics for the class of problems under consideration – namely, saddle-point problems and the associated vector field formulation.

Vector field formulation.

In most cases of interest, the objective $\mathcal{L}$ is differentiable and is usually accessed through a first-order oracle returning values of the vector field $V(\theta,\phi)=(\nabla_{\theta}\mathcal{L}(\theta,\phi),-\nabla_{\phi}\mathcal{L}(\theta,\phi)).$ As usual for gradient-based methods, we will frequently (though not always) assume that $V$ is Lipschitz continuous:

The importance of the above is that (SP) is often intractable, so it is natural to examine instead the first-order stationarity conditions for $V$, i.e., the problem:

This “vector field formulation” is the unconstrained case of what is known in the literature as a VI (VI) problem – see e.g., Facchinei & Pang 2003 for a comprehensive introduction. In what follows, we will not need the full generality of the VI (VI) framework and we will develop our results in the context of (Opt) above; our only blanket assumption in this regard is that the set of solutions $\mathcal{X}^{\star}$ of (Opt) is nonempty.

Feedback assumptions

The noise term $Z_{t}$ of SFO (SFO) satisfies

where $\sigma,\varcontrol\geq 0$ and $\mathcal{F}_{t}$ denotes the history (natural filtration) of $X_{t}$.

It is important to note that in (1b), $\sigma$ and $\varcontrol$ play different roles. When $\varcontrol=0$, the condition corresponds to the classic bounded variance assumption on the noise. At the other end of the spectrum, $\sigma=0$ implies that the noise vanish on the solution set. This kind of condition has been popularized recently in the machine learning community under the name of interpolation . In the most general case, we have both $\sigma>0$ and $\varcontrol>0$; then condition (1b) allows the variance of the noise to exhibit quadratic growth with respect to the distance to the solution set. For example, for a stochastic oracle of the form $\hat{V}_{t}=\hat{V}(\xi,X_{t})$ where $\xi$ is a random variable and $\hat{V}$ is a Carathéodory function, That is, $\hat{V}(\xi,\cdot)$ is continuous for almost all $\xi$ and $\hat{V}(\cdot,x)$ is measurable for all $x$. this is trivially satisfied if $\hat{V}(\xi,\cdot)$ is Lipschitz and the variance of the noise is bounded on $\mathcal{X}^{\star}$. Therefore, 2 is fairly weak and verified by most relevant problems.

The EG method and its limitations

As discussed earlier, the go-to method for saddle-point problems and VI is the EG (EG) algorithm of Korpelevich 1976 and its variants. Formally, in the general setting of the previous section, the EG algorithm can be stated recursively as:

where $\gamma_{t}>0$ is a variable stepsize sequence. Heuristically, the basic idea of the method is as follows: starting from a base state $X_{t}$, the algorithm first performs a look-ahead step to generate an intermediate – or leading – state $X_{t+\frac{1}{2}}$; subsequently, the oracle is called at $X_{t+\frac{1}{2}}$, and the method proceeds to a new state $X_{t+1}$ by taking a step from the base state $X_{t}$. Hence, the generation of the leading state can be seen as an exploration step while the second part is the bona fide update step.

One of the reasons for the widespread popularity of (EG) is that it achieves convergence in all monotone problems, without suffering from the non-convergence phenomena (limit cycles or otherwise) that plague vanilla one-step gradient algorithms . However, this guarantee requires the method to be run with deterministic, perfect oracle feedback (i.e., $Z_{t}=0$ for all $t$); if the method is run with genuinely stochastic feedback, the situation is considerably more complicated.

To understand the issues involved, it will be convenient to consider the following elementary example:

Trivially, the vector field associated to (2) is $V(\theta,\phi)=(\phi,-\theta)$ and the problem’s unique solution is $(\theta^{\star},\phi^{\star})=(0,0)$. Given the problem’s simple structure, one would expect that (EG) should be easily capable of reaching a solution; however, as we show below, this is not the case.

Suppose that (EG) is run on the problem (2) with oracle feedback $\hat{V}_{t}=V(\theta_{t},\phi_{t})+(\xi_{t},0)$ for some zero-mean random variable $\xi_{t}$ with variance $\sigma^{2}>0$. We then have $\liminf_{t\to\infty}\ex[\theta_{t}^{2}+\phi_{t}^{2}]>0$, i.e., the iterates of (EG) remain on average a positive distance away from $0$.

Importantly, Proposition 1 places no restrictions on the algorithm’s stepsize sequence and the variance of the noise could be arbitrarily small. Relegating the details to the appendix, the key to showing this result is the recursion

from which it follows that $\liminf_{t}\ex[\theta_{t}^{2}+\phi_{t}^{2}]>0$. In turn, this implies that the iterates of (EG) remain on average a positive distance away from the origin. This behavior is illustrated clearly in Fig. 2 which shows a typical non-convergent trajectory of (EG) in the planar problem (2).

Extragradient with stepsize scaling

At a high level, Proposition 1 suggests that the benefit of the exploration step is negated by the noise as the iterates of (EG) get closer to the problem’s solution set. To rectify this issue, we will consider a more flexible, DSEG (DSEG) method of the form

with $\gamma_{t}\geq\eta_{t}>0$. The key idea in (DSEG) is that the scaling of the method’s stepsize parameters affords us an extra degree of freedom which can be tuned to order. In particular, motivated by the failure of (EG) described in the previous section, we will take a stepsize scaling schedule in which the exploration step evolves at a more aggressive time-scale compared to the update step. In so doing, the method will keep exploring (possibly with a near-constant stepsize) while maintaining a cautious update policy that does not blindly react to the observed oracle signals.

For illustration and comparison, we plot in Fig. 2 an instance of this method with a fairly aggressive exploration schedule and a respectively conservative update policy. In contrast to (EG), the iterates of (DSEG) now converge to a solution. We encode this as a positive counterpart to Proposition 1 below:

Suppose that (DSEG) is run on the problem (2) with oracle feedback $\hat{V}_{t}=V(\theta_{t},\phi_{t})+(\xi_{t},0)$ for some zero-mean random variable $\xi_{t}$ with variance $\sigma^{2}>0$. If the method’s stepsize policies are of the form $\gamma_{t}=1/t^{r_{\gamma}}$ and $\eta_{t}=1/t^{r_{\eta}}$ for some $r_{\eta}>r_{\gamma}\geq 0$ with $r_{\gamma}+r_{\eta}\leq 1$, we have $\lim_{t\to\infty}\ex[\theta_{t}^{2}+\phi_{t}^{2}]\to 0$.

From an analytic viewpoint, what distinguishes (EG) from (DSEG) is the following refined bound:

Under 1 and 2, for all $t=1,2,\dotsc$ and all $x^{\star}\in\mathcal{X}^{\star}$, it holds

with constant $C_{t}=4\gamma_{t}^{2}\eta_{t}\beta+2\gamma_{t}^{3}\eta_{t}\beta^{2}+4\eta_{t}^{2}+16\gamma_{t}^{2}\eta_{t}^{2}\varcontrol^{2}$.

The proof of Lemma 1, which we defer to the supplement, relies on a careful analysis of the update between successive iterates to separate the deterministic and the stochastic effects. Analyzing the bound of Lemma 1 term-by-term gives a clear picture of how an aggressive exploration stepsize policy can be helpful:

The term $\gamma_{t}\eta_{t}(1-\gamma_{t}^{2}\beta^{2}-8\gamma_{t}\eta_{t}\varcontrol^{2})\lVert V(X_{t})\rVert^{2}$ provides a consistently negative contribution as long as $\sup_{t}\gamma_{t}<1/3\max(\beta,\varcontrol)$.

The term $C_{t}$ is antagonistic and needs to be made as small as possible.

The term $\ex[\langle V(X_{t+\frac{1}{2}}),X_{t+\frac{1}{2}}-x^{\star}\rangle\nonscript\>|\nonscript\>\mathopen{}\mathcal{F}_{t}]$ plays a lesser role since it is non-negative for variational stable problems (see upcoming 3) and is even identically zero in bilinear problems.

Therefore, to obtain convergence, one needs the coefficient $\gamma_{t}\eta_{t}$ to be as large as possible and, concurrently, each of the terms $\gamma_{t}^{2}\eta_{t}$, $\gamma_{t}^{3}\eta_{t}$, $\eta_{t}^{2}$ and $\gamma_{t}^{2}\eta_{t}^{2}$ that appear in $C_{t}$ should be as small as possible. Formally, this would lead to the requirement $\sum_{t}\gamma_{t}\eta_{t}=\infty$ and $\sum_{t}\gamma_{t}^{2}\eta_{t}+\eta_{t}^{2}<\infty$. These conditions can be simultaneously achieved by a suitable choice of $\gamma_{t}$ and $\eta_{t}$ (cf. Proposition ′ above), but they are mutually exclusive if $\gamma_{t}=\eta_{t}$. This observation is the key motivation for the scale separation between the exploration and the update mechanisms in (DSEG), and is the principal reason that (EG) fails to converge in bilinear problems.

Convergence analysis

We now proceed with our main results for the DSEG algorithm. We begin in Section 5.1 with an asymptotic convergence analysis for (DSEG); subsequently, in Section 5.2, we examine the algorithm’s rate of convergence; finally, in Section 5.3, we zero in on affine problems. Given our interest in non-monotone problems, we make a clear distinction between global results (which require global assumptions) and local ones (which apply to more general problems).

​​Our assumption for global convergence is a variational stability condition.

3 is verified for all monotone operators but it also encompasses a wide range of non-monotone problems; for an overview see e.g., and references therein.

To leverage this assumption, we will further need the algorithm’s update step to decrease sufficiently quickly relative to the corresponding exploration step. Formally (and with a fair degree of hindsight), this boils down to the following:

The stepsizes of (DSEG) satisfy $\sum_{t}\gamma_{t}\eta_{t}=\infty$, $\sum_{t}\eta_{t}^{2}<\infty$, and $\sum_{t}\gamma_{t}^{2}\eta_{t}<\infty$.

4 essentially posits that $\eta_{t}/\gamma_{t}\to 0$ as $t\to\infty$, so it reflects precisely the principle of “aggressive exploration, conservative updates”. In particular, 4 rules out the choice $\gamma_{t}=\eta_{t}$ which would yield the vanilla EG algorithm, providing further evidence for the use of a double stepsize policy. A typical stepsize policy for (DSEG) is

for some $\gamma,\eta,b>0$ and exponents $r_{\gamma},r_{\eta}\in$. 4 then translates as $r_{\gamma}+r_{\eta}\leq 1$, $2r_{\eta}>1$, and $2r_{\gamma}+r_{\eta}>1$ as represented in Fig. 2. With this in mind, we have the following convergence result.

Let 1, 2, 3 and 4 hold and $\sup_{t}\gamma_{t}<1/3\max(\beta,\varcontrol)$, then the iterates $X_{t}$ of (DSEG) converge almost surely to a solution $x^{\star}$ of (Opt).

As far as we are aware, this is the first result of this type for stochastic first-order methods: almost sure convergence typically requires stronger hypotheses guaranteeing that $\langle V(x),x-x^{\star}\rangle$ is uniformly positive when $x\notin\mathcal{X}^{\star}$ . In particular, Theorem 1 implies the almost sure convergence of the algorithm for bilinear problems like (2) where EG and standard gradient methods do not converge.

Local convergence.

To extend Theorem 1 to fully non-monotone settings, we will consider the following local version of 1, 2 and 3 near a solution point $x^{\star}$:

The field $V$ is $\beta$-Lipschitz continuous near $x^{\star}$, i.e., for all $x,x^{\prime}$ near $x^{\star}$,

Let $x^{\star}\in\mathcal{X}^{\star}$ and $U$ be a neighborhood of $x^{\star}$. The noise term $Z_{t}$ of SFO satisfies

for some $q>2$ and $\sigma,\varcontrol\geq 0$.

The operator $V$ satisfies $\langle V(x),x-x^{\star}\rangle\geq 0$ for all $x$ near $x^{\star}$.

Notice that (5b) is slightly stronger than (1b) in the sense that we now require to control the $q^{th}$ moment of the noise for some $q>2$. Nonetheless, this condition as well as the unbiasedness assumption only need to be satisfied in a neighborhood of $x^{\star}$. Our next result shows that, with these modified assumptions, the DSEG algorithm converges locally to solutions with high probability:

Fix a tolerance level $\delta>0$ and suppose that ′ ‣ Sections 5.1, ′ ‣ 5.1 and ′ ‣ 5.1 hold for some isolated solution $x^{\star}$ of (Opt). Assume further that (DSEG) is run with stepsize parameters of the form (4) with small enough $\gamma$, $\eta$ and proper choice of $r_{\gamma},r_{\eta}$ (cf. Fig. 2). If the algorithm is not initialized too far from $x^{\star}$, its iterates converge to $x^{\star}$ with probability at least $1-\delta$.

The first step towards proving Theorem 2 is to show that the generated iterates stay close to $x^{\star}$ with arbitrarily high probability. To achieve this, one needs to control the total noise accumulating from each noisy step, a task which is made difficult by the fact that the norm of the SFO feedback can only be upper bounded recursively and thus depends on previous iterates. In the supplement, we dedicate a lemma to the study of such recursive stochastic processes, and we build our analysis on this lemma.

2 Convergence rates

To study the algorithm’s convergence rate, we will require the following error bound condition:

This kind of error bound is standard in the literature on VI for deriving last iterate convergence rates [21, 41, 6, 40, 22, see e.g., ]. In particular, ′ ‣ Section 5.2 is satisfied by

Strongly monotone operators: here, $\tau$ is the strong monotonicity modulus.

Affine operators: for $V(x)=Mx+v$ where $M$ is a matrix of size $d\times d$ and $v$ is a $d$-dimensional vector, $\tau$ is the minimum non-zero singular value of $M$.

In this sense, ′ ‣ Section 5.2 provides a unified umbrella for two types of problems that are typically considered to be poles apart. Our first result in this context is as follows:

Suppose that 1, 2, 3 and ′ ‣ 5.2 hold and assume that $\gamma_{t}\leq c/\beta$ with $c<1$. Then:

If (DSEG) is run with $\gamma_{t}\equiv\gamma$, $\eta_{t}\equiv\eta$, we have:

with constants $C=(2\gamma^{2}\eta\beta+\gamma^{3}\eta\beta^{2}+\eta^{2})\sigma^{2}$ and $\Delta=\gamma\eta\tau^{2}(1-c^{2})$. For better readability, these constants are stated for the case $\varcontrol=0$. On the other hand, if $\sigma=0$ (and $\varcontrol\geq 0$), a geometric convergence can be proved. The same arguments apply to Theorem 5.

If (DSEG) is run with $\gamma_{t}=\gamma/(t+b)^{1-\nu}$ and $\eta_{t}=\eta/(t+b)^{\nu}$ for some $\nu\in(1/2,1)$, we have:

where $r=\min(1-\nu,2\nu-1)$ and we further assume that $\gamma\eta\tau^{2}(1-c^{2})>r$. In particular, the optimal rate is attained when $\nu=2/3$, which gives $\ex[\dist(X_{t},\mathcal{X}^{\star})^{2}]=\bigoh(1/t^{1/3})$.

The first part of Theorem 3 shows that, if (DSEG) is run with constant stepsizes, the initial condition is forgotten exponentially fast and the iterates converge to a neighborhood of $\mathcal{X}^{\star}$ (though, in line with previous results, convergence cannot be achieved in this case). To make this neighborhood small, we need to decrease both $\gamma$ and $\eta/\gamma$; this would be impossible for vanilla (EG) for which $\eta/\gamma=1$.

The second part of Theorem 3 provides an $\bigoh(1/t^{1/3})$ last-iterate convergence rate. In Section 5.3, we further improve this rate to $\bigoh(1/t)$ for affine operators by exploiting their particular structure.

Local rate.

To study the algorithm’s local rate of convergence, we will focus on solutions of (Opt) that satisfy the following Jacobian regularity condition:

$V$ is differentiable at $x^{\star}$ and its Jacobian matrix $\Jac_{V}(x^{\star})$ is invertible.

The link between ′ ‣ Sections 5.2 and ′ ‣ 5.2 is provided by the following proposition:

If a solution $x^{\star}$ satisfies ′ ‣ Section 5.2, it satisfies (EB) in a neighborhood of $x^{\star}$.

The proof of Proposition 2 follows by performing a Taylor expansion of $V$ and invoking the minimax characterization of the singular values of a matrix; we give the details in the supplement. For our purposes, what is more important is that (EB) has now been reduced to a pointwise condition; under this much lighter requirement, we have:

Fix a tolerance level $\delta>0$ and suppose that ′ ‣ Sections 5.1, ′ ‣ 5.1 and ′ ‣ 5.1 and ′ ‣ 5.2 hold for some isolated solution $x^{\star}$ of (Opt) with $q>3$. Assume further $x^{\star}$ satisfies ′ ‣ Section 5.2 and (DSEG) is run with stepsize parameters of the form $\gamma_{t}=\gamma/(t+b)^{1/3}$ and $\eta_{t}=\eta/(t+b)^{2/3}$ with large enough $b,\eta>0$. Then, there exist neighborhoods $U$, $U^{\prime}$ of $x^{\star}$ and an event $E_{U}$ such that:

$\prob(E_{U}\nonscript\>|\nonscript\>\mathopen{}X_{1}\in U)\geq 1-\delta$.

\prob(X_{t}\in U^{\prime}\;\text{for allt}\nonscript\>|\nonscript\>\mathopen{}E_{U})=1.

$\ex[\lVert X_{t}-x^{\star}\rVert^{2}\nonscript\>|\nonscript\>\mathopen{}E_{U}]=\bigoh\left(1/t^{1/3}\right)$

In words, if (DSEG) is not initialized too far from $x^{\star}$, the iterates $X_{t}$ remain close to $x^{\star}$ with probability at least $1-\delta$ and, conditioned on this event, $X_{t}$ converges to $x^{\star}$ at a rate $\bigoh(1/t^{1/3})$ in mean square error.

Taken together, Theorems 1 and 4 show that for all monotone stochastic problems with a non-degenerate critical point, employing the suggested stepsize policy yields an asymptotic $\bigoh(1/t^{1/3})$ rate. In more detail, the last point of Theorem 4 shows that, with the same kind of stepsizes as in the second part of Theorem 3, we can retrieve a $\bigoh(1/t^{1/3})$ convergence rate provided that the iterates stay close to the solution. Note that this rate is not a localization of Theorem 3 because, after conditioning, the unbiasedness of the noise is not guaranteed. To overcome this issue, our proof draws inspiration from Hsieh et al. 2019 but the use of double stepsizes requires a much more intricate analysis which is reflected in the stronger noise assumption.

3 A case study of affine operators

We terminate our analysis with a dedicated treatment of affine operators which are commonly studied as a first step to understand the training of GAN . The following result improves the $\bigoh(1/t^{1/3})$ rate of Theorem 3 to $\bigoh(1/t)$ for affine operators.

If the update stepsize is constant $\eta_{t}\equiv\eta\leq\gamma$, then:

with $C=\eta^{2}(1+c^{2})\sigma^{2}$ and $\Delta=\gamma\eta\tau^{2}(1-c^{2})$.

If the update stepsize is of the form $\eta_{t}=\eta/(t+b)$ for $\eta>1/(\tau^{2}\gamma(1-c^{2}))$ and $b>\eta/\gamma$, then:

The proof of this theorem relies on the derivation of another descent lemma similar to Lemma 1 but tailored to affine operators. Note also that 1 and ′ ‣ 5.2 are automatically verified in this case.

Theorem 5 mirrors Theorem 3; however, in Part 1 of Theorem 5, the final precision is only determined by $\sigma^{2}$ and $\eta/\gamma$. Thus, compared to Theorem 3, there is no need to decrease $\gamma$ to obtain an arbitrarily high accuracy solution. The weaker dependence on $\gamma$ is further confirmed by Part 2, which shows a $\bigoh(1/t)$ rate with $\gamma_{t}$ constant. As far as we are aware, this result gives the best convergence rate for stochastic affine operators compared to the literature, and it gives yet another motivation for the use of a double stepsize strategy.

Numerical experiments

This section investigates numerically the benefits of double stepsizes. We run (DSEG) with stepsize of the form (4) on three different problems: i) a bilinear zero-sum game, ii) a strongly convex-concave game and iii) a non convex-concave linear quadratic Gaussian GAN model . We examine their behavior when $r_{\gamma}$ and $r_{\eta}$ vary. The exact description of the problems and the experimental details are deferred to the supplement.

Conclusion

In this paper, we examined the benefits of employing a DSEG method for which the exploration step is more aggressive than the update step. This additional flexibility turns out to be both necessary and sufficient for the method to achieve superior convergence properties relative to vanilla stochastic EG methods in a large spectrum of problems including bilinear games and some non convex-concave models.

Our results constitute a first attempt towards designing an algorithm that provably avoids cycles and similar non-convergent phenomena in a fully stochastic setting. Several interesting future directions include an extended analysis with relaxation of the variational stability assumption as well as the design of a fully adaptive and/or universal method on the basis of our results.

Broader impact

This work does not present any foreseeable societal consequence.

Acknowledgments

This work has been partially supported by MIAI@Grenoble Alpes, (ANR-19-P3IA-0003).

References

Appendix A Additional related work

The first analysis of EG (EG) with stochastic feedback traces back to the work of Juditsky et al. 2011, where a $\bigoh(1/\sqrt{t})$ ergodic convergence was shown for monotone problems, and this rate is known to be optimal without further assumptions . Precisely, the results of concern the more general MP algorithm, which generalized EG to the Bregman setting. Since then, a large number of works have been dedicated to studying the convergence behavior of stochastic EG-type algorithms, either for better understanding of the algorithm itself or in the hope of finding a better way to incorporate EG with stochasticity.

Almost sure convergence of stochastic EG was first investigated in Kannan & Shanbhag 2019. In the said paper, almost convergence was shown for pseudomonotone plus operators and by additionally assuming that the map is strongly pseudomonotone or monotone and weak-sharp, the authors managed to prove a $\bigoh(1/{t})$ convergence of the iterate produced by the algorithm. In , the pseudo-monotonicity-plus assumption is relaxed to show that stochastic EG still enjoys last-iterate convergence in strict coherent problems. Nonetheless, these results fail to justify the use of EG for stochastic monotone problems, as illustrated in Section 3. Therefore, to improve the convergence behavior of EG in stochastic problems, several modifications to the original stochastic EG have been proposed . In addition to the ones discussed in Section 1, Mishchenko et al. 2020 advocated a repeated sampling strategy and illustrated numerically its better performance when applied to GAN training. They also showed that their proposed algorithm retain the same convergence guarantee as traditional stochastic EG.

In order to reduce the overall computational cost, another line of research aims at designing optimization methods that solve variational problems with a single oracle call per iteration (instead of the two in EG). Algorithms of this family include for example OG (OG) and PEG (PEG) . See Hsieh et al. 2019 for a recent overview and corresponding treatment in the stochastic setting. Very recently, the convergence of stochastic OG (OG) are further improved in two different ways. In , the authors introduced a multistage version of OG for stochastic strongly monotone problems to optimize the dependence of convergence speed on initial error and noise characteristics. On the other hand, inspired by the success of adaptive methods in deep learning, Liu et al. 2020 designed an adaptive variant of OG and showed that it enjoyed an adaptive complexity that varies according to the growth rate of the cumulative stochastic gradient. To complete the list, also in the goal of reducing overall computation though under a quite different perspective, Jelassi et al. 2019 analyzed a randomized version of stochastic EG in multiplayer game to make the extrapolation step amenable to massive multiplayer settings.

Appendix B Generalized optimistic gradient

Considering the similarity between EG and its single-call variants, we believe our analysis on (DSEG) also suggests essential modifications in terms of stepsizes that should be carried out for these algorithms in the face of stochasticity. As an example, we investigate the OG method of Daskalakis et al. 2018, and find out that some surprising conclusions can be drawn after applying the double stepsize rule. The generalized OG recursion is commonly stated as follows :

where $\gamma_{t}$ is sometimes called the optimism rate. Similarly to our conclusions, it has been empirically observed that taking large optimism rate often yields better convergence in stochastic problems .

Hsieh et al. 2019 pointed out that OG is equivalent to the modified Arrow-Hurwitz method introduced by Popov 1980 and also referred to as PEG (PEG) by Gidel et al. 2019. Using a double stepsize policy, PEG becomes:

Hence, leading states can be recursively written as

We thereby see that (OG) and (DSPEG) are almost equivalent and they mostly differ in the choice of vectors that the method outputs at the end: OG suggests outputting $X_{t}$ while PEG instead looks at $X_{t}+\gamma_{t-1}\hat{V}_{t-1}$. This nuance turns out to be of importance when generalized OG is applied to stochastic problems. By analogy with our analysis for (DSEG), we reasonably conjecture that taking $\eta_{t}<\gamma_{t}$ guarantees the convergence of $X_{t}+\gamma_{t-1}\hat{V}_{t-1}$, and this may occur even if $\gamma_{t}$ is set to constant. Nonetheless, this also implies that if the noise is not vanishing at the solution, $X_{t}$, which corresponds to the exploration state in PEG, might exhibit much slower convergence or even not converge at all.

To summarize, when running (OG) for stochastic problems, we should look at the residual iterate $X_{t}+\gamma_{t-1}\hat{V}_{t-1}$ instead of the optimistic iterate $X_{t}$. Interestingly, this conclusion is consistent with the ODE analysis of OG by Ryu et al. 2019, and explains some experimental results of said work. Furthermore, taking an aggressive exploration step $\gamma_{t}$ and a more conservative update step $\eta_{t}$ may be very beneficial both in theory (for the last iterate convergence and rate) and in practice as confirmed by our experiments just below.

Appendix C Experimental details and additional experiments

We provide here a detailed explanation of the problems that we consider in our experiments and elucidate the used parameters. Additional experimental results are also presented.

The bilinear zero-sum game takes the form

where $C$ is a $50\times 50$ invertible matrix in our experiment; in that case, $(\theta^{\star},\phi^{\star})=(0,0)$ is the only equilibrium point. We simulate the stochastic oracle by adding a Gaussian noise $Z\sim\mathcal{N}(0,\sigma I)$ with $\sigma=0.5$ to the vector field.

Strongly convex-concave game.

To understand the effect of aggressive exploration in strongly convex-concave problems, we inspect the following example

where $A_{1}$, $A_{2}$, $B_{1}$, $B_{2}$ are $50\times 50$ positive definite matrices so $(\theta^{\star},\phi^{\star})=(0,0)$ is again the only solution of the problem. We take the same noise distribution to construct the stochastic oracle.

Linear Quadratic Gaussian GAN.

Finally, to examine the convergence of (DSEG) in stochastic non convex-concave problems, we consider the following problem from Daskalakis et al. 2018 and Nagarajan & Kolter 2017:

This saddle-point problem corresponds to the WGAN formulation without clipping when data are sampled from a normal distribution with covariance matrix $\Sigma$, i.e., $x\sim\mathcal{N}(0,\Sigma)$, and the generator and the discriminator are respectively defined by $G(z)=Yz$, $D(x)=x^{\top}\!Wx$. The stochasticity is induced by the sampling of $x$ and $z$. For the experiments we take a mini-batch of size $128$ and $x$ and $z$ of dimension $10$. As the game may possess multiple equilibria, the squared norm of $V$ is traced as the convergence measure.

Results for (DSEG) and (OG).

Following the discussion of Appendix B, we complement the illustration of our method (DSEG) by a comparison with (OG) with properly chosen outputs. In the experiments, both (DSEG) and (OG) are run with stepsize of the form (4) with various $r_{\gamma}$ and $r_{\eta}$. In order to start with the same value for different exponents, we fix $b,\gamma_{1},$ and $\eta_{1}$ as indicated in Table 2, from which we deduce $\gamma=\gamma_{1}(1+b)^{r_{\gamma}}$ and $\eta=\eta_{1}(1+b)^{r_{\eta}}$.

Regarding (OG) with the residual iterates, the algorithm has roughly the same convergence behavior as for (DSEG). In contrast, the optimistic iterates tend to converge much slower. In particular, choosing a constant exploration step gives the fastest convergence of the residual iterate though the optimistic iterate does not converge, in line with our discussion in Appendix B.

Additional discussions for bilinear games.

and it is proved to converge in all stochastic monotone problems for $\gamma>0$ and $r,\nu\in(1/2,1)$. Since no explicit rate is proven for this algorithm when stochastic gradients are used,

we run hyperparameter optimization to search for the best $\gamma,r$ and $\nu$, and end up with $\gamma=1,r=0.7,\nu=0.9$.

Fig. 5 confirms that asymptotically both DSEG and SHGD converge in $\bigoh(1/t)$ as predicted by the theory. SHGD converges slightly faster than DSEG for the first few iterations as it circumvents the rotational dynamics by directly performing stochastic gradient descent on $\lVert V(\cdot)\rVert^{2}$, which turns out to be a positive definite quadratic form when $V$ is linear. This however comes at the cost of the use of second-order information. In fact, SHGD requires access to an unbiased estimator of $\Jac_{V}^{\top}V$ at every iteration. Finally, anchoring converges much slower compared to these two methods. Without further theoretical investigation we do not know if this kind of algorithms can achieve the same $\bigoh(1/t)$ convergence rate in this problem.

Appendix D Technical lemmas

In this section we recall several important lemmas that are frequently used in the analysis of stochastic iterative methods. The first three lemmas on numerical sequences are useful for deriving convergence rates of the algorithms. See e.g., Polyak 1987 for an abundance of results of this type.

The above lemma comes into play when an algorithm is run with constant stepsize sequences, whereas we resort to the following two lemmas in case of decreasing stepsize sequences of the form (4).

where $1>\nu>0$ and $r,q,q^{\prime}>0$. Then,

To establish almost sure convergence of the iterates, we rely on the Robbins–Siegmund theorem which apply to non-negative almost-supermatingales.

Appendix E Proofs for global convergence results

We then start with the proofs of the global results to highlight the effect of double stepsize, before tackling the more challenging local convergence analysis.

For sake of simplicity, let us denote $a_{t}=\ex[\theta_{t}^{2}+\phi_{t}^{2}]$. We consider two scenarios:

Case 1: $\gamma_{t}^{2}\geq 1$. We have $1-\gamma_{t}^{2}+\gamma_{t}^{4}\geq 1$ and consequently $a_{t+1}\geq a_{t}$.

We then set $\nu_{t}=(1+\gamma_{t}^{2})/(1-\gamma_{t}^{2})$. Since $1-\gamma_{t}^{2}+\gamma_{t}^{4}<1$, $a_{t+1}$ gets closer to $\nu_{t}\sigma^{2}$ than $a_{t}$. In particular, if $a_{t}<\nu_{t}\sigma^{2}$, we have $a_{t}<a_{t+1}<\nu_{t}\sigma^{2}$; otherwise, $a_{t}\geq a_{t+1}\geq\nu_{t}\sigma^{2}$. As $\nu_{t}\geq 1$, the above implies $a_{t+1}\geq\min(a_{t},\nu_{t}\sigma^{2})\geq\min(a_{t},\sigma^{2})$.

To conclude, in the two cases we have $a_{t+1}\geq\min(a_{t},\sigma^{2})$, showing $\liminf_{t\to\infty}\ex[\theta_{t}^{2}+\phi_{t}^{2}]>0$.

With different stepsizes, the updates of the algorithm write

Taking $\gamma_{t}=\frac{1}{t^{r_{\gamma}}}$ and $\eta_{t}=\frac{1}{t^{r_{\eta}}}$, we get

where the inequality comes from $1-2/t^{(r_{\gamma}+r_{\eta})}+1/{t}^{2r_{\eta}}+1/t^{2(r_{\gamma}+r_{\eta})}\leq 1-1.5/t^{(r_{\gamma}+r_{\eta})}$ for large enough $t$ and the last part is an application of either Lemma D.2 or Lemma D.3 with $q=1.5>r=r_{\eta}-r_{\gamma}>0$ (starting at large enough $t$).

Hence, $\ex[\theta_{t}^{2}+\phi_{t}^{2}]\to 0$, i.e. we can find a double stepsize choice, with an aggressive extrapolation step and a conservative update step ($r_{\gamma}<r_{\eta}$) such that $(\theta_{t},\phi_{t})\to(0,0)$ in mean squared error. ∎

E.2 Proof of Lemma 1

We would then like to bound the different terms appearing on the RHS (RHS) of the equality. With the zero-mean assumption (1a), conditioning on $\mathcal{F}_{t}$ leads to

On the other hand, $\ex_{t}[\langle\hat{V}_{t+\frac{1}{2}},V(X_{t})\rangle]=\ex_{t}[\langle V(X_{t+\frac{1}{2}}),V(X_{t})\rangle]$ and $\ex_{t}[\lVert\hat{V}_{t+\frac{1}{2}}\rVert^{2}]=\ex_{t}[\lVert V(X_{t+\frac{1}{2}})\rVert^{2}]+\ex_{t}[\lVert Z_{t+\frac{1}{2}}\rVert^{2}]$. By $\eta_{t}\leq\gamma_{t}$, Lipschitz continuity of $V$ and $X_{t}-X_{t+\frac{1}{2}}=\gamma_{t}\hat{V}_{t}$, we get

Similar to before we may write $\ex_{t}[\lVert\hat{V}_{t}\rVert^{2}]=\ex_{t}[\lVert V(X_{t})\rVert^{2}]+\ex_{t}[\lVert Z_{t}\rVert^{2}]$. Therefore, combining (E.1), (E.2), (E.3), (E.4), we deduce the following

To finish the proof, we would like to bound the noise terms. Using (1b) and Jensen’s inequality (recall that $q\geq 2$), we have

Substituting (E.7) and (E.6) in (E.5), we obtain

We recover (3) by using $2\eta_{t}^{2}\sigma^{2}\leq 4\eta_{t}^{2}\sigma^{2}$. ∎

E.3 Proof of Theorem 1

The proof is divided into three key steps.

(1) With probability $1$, $\liminf_{t\rightarrow\infty}\lVert V(X_{t})\rVert=0$. Let $x^{\star}\in\mathcal{X}^{\star}$. Using Lemma 1 and 3, we get the following

In effect, taking an arbitrary $z$ from $\mathcal{Z}$, from (i) we know that

(3) Conclude. Combining the points (1) and (2), we get

To conclude, we have proved that that $X_{t}$ converges to some $x^{\star}\in\mathcal{X}^{\star}$ almost surely. ∎

E.4 Proof of Theorem 3

Suppose that 1, 2, 3 and ′ ‣ 5.2 hold and assume that $\gamma_{t}\leq c/\beta$ with $c<1$. Then:

If (DSEG) is run with $\gamma_{t}\equiv\gamma$, $\eta_{t}\equiv\eta$, we have:

with constants $C=(2\gamma^{2}\eta\beta+\gamma^{3}\eta\beta^{2}+\eta^{2})\sigma^{2}$ and $\Delta=\gamma\eta\tau^{2}(1-c^{2})$.

If (DSEG) is run with $\gamma_{t}=\gamma/(t+b)^{1-\nu}$ and $\eta_{t}=\eta/(t+b)^{\nu}$ for some $\nu\in(1/2,1)$, we have:

where $r=\min(1-\nu,2\nu-1)$ and we further assume that $\gamma\eta\tau^{2}(1-c^{2})>r$. In particular, the optimal rate is attained when $\nu=2/3$, which gives $\ex[\dist(X_{t},\mathcal{X}^{\star})^{2}]=\bigoh(1/t^{1/3})$.

For the sake of readability, the involved constants are stated for the case $\varcontrol=0$. On the other hand, if $\sigma=0$ and $\varcontrol\geq 0$, a geometric convergence can be proved.

We first consider the case $\varcontrol=0$ so that $\ex[\lVert Z_{t}\rVert^{2}]\leq\sigma^{2}$ and $\ex[\lVert Z_{t+\frac{1}{2}}\rVert^{2}]\leq\sigma^{2}$. Since $\gamma_{t}\leq c/\beta$, from (E.5) we deduce

By concavity of the minimum operator, we then obtain

Using ′ ‣ Section 5.2 and the law of total expectation, this gives

Points 1 and 2 are obtained respectively by applying Lemma D.1 and Lemma D.2.

For the case $\varcontrol\neq 0$, the term before $\ex[\dist(X_{t},\mathcal{X}^{\star})^{2}]$ is replaced by $1+C_{t}\varcontrol^{2}-\rho_{t}\tau^{2}$ where $\rho_{t}=\gamma_{t}\eta_{t}-\gamma_{t}^{3}\eta_{t}\beta^{2}-8\gamma_{t}^{2}\eta_{t}^{2}\varcontrol^{2}$ is defined in the proof of Theorem 1. In point 1, the term $1+C_{t}\varcontrol^{2}-\rho_{t}\tau^{2}$ can be made in $(0,1)$ for $\gamma$ and $\eta$ properly chosen. Precisely, we need

To prove point 2, notice that the conditions of Lemma D.2 are still verified when $\gamma,\eta$ and $b$ are large enough. For example, if it holds for all $t$

and $\gamma\eta\tau^{2}/2>r$ then Lemma D.2 can be applied. Finally, if $\sigma=0$, the key inequality becomes

We therefore obtain geometric convergence for $1+C_{t}\varcontrol^{2}-\rho_{t}\tau^{2}\in(0,1)$. ∎

E.5 Proof of Theorem 5

If the update stepsize is constant $\eta_{t}\equiv\eta\leq\gamma$, then:

with $C=\eta^{2}(1+c^{2})\sigma^{2}$ and $\Delta=\gamma\eta\tau^{2}(1-c^{2})$.

If the update stepsize is of the form $\eta_{t}=\eta/(t+b)$ for $\eta>1/(\tau^{2}\gamma(1-c^{2}))$ and $b>\eta/\gamma$, then:

For the sake of readability, the involved constants are stated for the case $\varcontrol=0$.

To focus on the most important points of the proof, we shall consider the case $\varcontrol=0$, while it is straightforward to derive the same kind of result when $\varcontrol>0$ by following the reasoning of previous proofs. The crucial step here is then the derivation of a stochastic descent inequality in the form of (3). This is again based on (E.1). Writing $V(x)=Mx+v$, we can expand

Proceeding as in the proof of Theorem 3, we get

Since $V$ is affine, it verifies the error bound condition (EB). Writing $\gamma$ in the place of $\gamma_{t}$ and applying the law of total expectation, we obtain

We conclude with help of Lemma D.1 and Lemma D.2. ∎

Appendix F Proofs for local convergence results

For sake of clarity, we recall here the local assumptions that will bu used in the local convergence results.

For ′ ‣ Section 5.1 in particular, when the neighborhood $U$ is bounded, the term $\varcontrol\lVert X_{t}-x^{\star}\rVert$ is also bounded and therefore, by choosing a larger $\sigma$ if needed, (5b) can be simplified to

We will consider (5b) under this form in the sequel.

F.2 Preparatory lemmas

The proofs of the local statements are much more demanding. The principle pillar of our analysis is a stability result formally stated in Section F.3. To prepare us for the challenge, we start by introducing the following lemma for bounding a recursive stochastic process.

$\forall t,\ex[\xi_{t+1}\nonscript\>|\nonscript\>\mathopen{}{\mathcal{F}_{t}}]\one_{I_{t}}=0$,

$\sum_{t=1}^{\infty}\ex[(\xi_{t+1}^{2}+\chi_{t+1})\one_{I_{t}}]\leq\delta\varepsilon\prob(A_{1})$,

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

Subsequently, we define an auxiliary sequence of events

which is also decreasing. With this at hand, we are ready to start our proof.

(1) Inclusion $H_{t}\subset I_{t}$. We prove the inclusion by induction. The statement is true when $t=1$ as $H_{1}=I_{1}=A_{1}$. For $t\geq 2$, we write

By induction hypothesis, $H_{t-1}\subset I_{t-1}$, and thus for all $s\leq t-1$, we have $H_{t}\subset I_{t-1}\subset I_{s}$. Combining with (i) we deduce that for any realization of $H_{t}$, $\sum_{s=1}^{t-1}\zeta_{s}\geq 0$. On the other hand, by definition of $H_{t}$, it holds $Q_{t}\one_{H_{t}}\leq\varepsilon$. This implies

Finally as $H_{t}\subset A_{1}$ we have $D_{1}\one_{H_{t}}\leq C/2$. Therefore, for any realization of $H_{t}$, using (F.1) gives

In the meantime (F.2) ensures as well $\chi_{t}\one_{H_{t}}\leq C/4$ and we have thus proven $H_{t}\subset A_{t}$. Using $H_{t}\subset H_{t-1}\subset I_{t-1}$, we conclude $H_{t}\subset I_{t}$.

(2) Recursive bound on $\ex[Q_{t}\one_{H_{t-1}}]$. Since $H_{t-1}\subseteq H_{t-2}$, it holds $H_{t-1}=H_{t-2}\setminus(H_{t-2}\setminus H_{t-1})$. We can therefore decompose

From the law of total expectation, $H_{t-1}\subset I_{t-1}$ and (ii) we have

As $\xi_{t}^{2}+\chi_{t}$ is non-negative, using again $H_{t-1}\subset I_{t-1}$, we get

By definition for any realization in $H_{t-2}\setminus H_{t-1}$, it holds $Q_{t-1}>\varepsilon$ and thus

Combining the above we deduce the following recursive bound

(3) Conclude. Summing (F.4) from $t=3$ to $T$ we obtain

where in the second line we use $Q_{2}=\xi_{2}^{2}+\chi_{2}$, $H_{1}=I_{1}=A_{1}$ and $H_{1}\setminus H_{T-1}=\dot{\bigcup}_{3\leq t\leq T}(H_{t-2}\setminus H_{t-1})$ with $\dot{\bigcup}$ denoting the disjoint union (true since $(H_{t})_{t\geq 1}$ is a decreasing sequence of events). By repeating the same arguments that are used before and using the fact that $Q_{T}$ is non-negative,

With $H_{T}\subset I_{T}$ this also gives $\prob(I_{T}\nonscript\>|\nonscript\>\mathopen{}{A_{1}})\geq 1-\delta$. We notice that $\bigcap_{t\geq 1}I_{t}=\bigcap_{t\geq 1}A_{t}$. As $(I_{t})_{t\geq 1}$ is decreasing, by continuity from above we conclude

To apply Lemma F.1, we establish another quasi-descent lemma which holds without taking expectation values.

We further develop the second term on the RHS of the equality

F.3 A stability result

occurs with probability at least $1-\delta$, i.e., $\prob(E_{\infty}^{\rho}\nonscript\>|\nonscript\>\mathopen{}{X_{1}\in U_{\rho}})\geq 1-\delta$.

(a.2) Assumption (ii). Immediate from (5a), (a.0) and the law of the total expectation.

By similar arguments and in particular by invoking $I_{t+\frac{1}{2}}\subset\{D_{t}\leq C\}$ and the definition of $C$, it follows

Combining the above with $\ex[\chi_{t+\frac{1}{2}}\one_{I_{t}}]\leq\gamma_{t}^{q}\sigma^{q}$, we have

We can thus pick $\Gamma$ small enough to make (iii) verified.

F.4 Proof of Theorem 2

Applying the Cauchy–Schwarz inequality leads to

Then, by using (F.11), (F.12) and $E_{t+\frac{1}{2}}\subset E_{t}$,

On the other hand, the last two terms of (F.8) can be bounded similarly as in (F.10) and the antepenultimate term can now be bounded thanks to (F.13). We then obtain

Without loss of generality we may suppose $\gamma_{t}\beta\leq 1/2$. To simplify the notation, we set

As $\lVert X_{t}-x^{\star}\rVert^{2}-\zeta_{t}\geq 0$ and $E_{t+\frac{1}{2}}\subset E_{t-\frac{1}{2}}$, this implies

Invoking the Robbins–Siegmund theorem (Lemma D.4) gives the almost sure convergence of $\sum_{t}\zeta_{t}\one_{E_{t-\frac{1}{2}}}$ and $\lVert X_{t}-x^{\star}\rVert^{2}\one_{E_{t-\frac{1}{2}}}$. We use $\prob(E_{\infty}^{\rho})>1-\delta$ and deduce that

F.5 Proof of Proposition 2

If a solution $x^{\star}$ satisfies ′ ‣ Section 5.2, then for every $\varepsilon>0$, there is a neighborhood $U$ of $x^{\star}$ such that the error bound condition (EB) is satisfied on $U$ with constant $\tau=\sigma_{\min}-\varepsilon$ where $\sigma_{\min}$ denotes the smallest singular value of $\Jac_{V}(x^{\star})$.

By the min-max principle of singular value it holds

Since $V(x^{\star})=0$, combining (F.15) and (F.16) gives

We conclude by noticing $\dist(x,\mathcal{X}^{\star})=\lVert x-x^{\star}\rVert$ when $U$ is small enough. ∎

F.6 Proof of Theorem 4

By using $E_{t+\frac{1}{2}}\subset E_{t-\frac{1}{2}}$, we get

Therefore, with the specified stepsize policy and the condition $\gamma\eta\tau^{2}(1-\gamma_{1}\beta)>1/6$, applying Lemma D.2 yields $\ex[\lVert X_{t+1}-x^{\star}\rVert^{2}\one_{E_{t+\frac{1}{2}}}]=\bigoh(1/t^{1/3})$. Finally

which proves $\ex[\lVert X_{t}-x^{\star}\rVert^{2}\nonscript\>|\nonscript\>\mathopen{}E_{\infty}^{\rho}]=\bigoh(1/t^{1/3})$. ∎