A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise

Introduction

For convex minimization problems, the operator $F$ is simply the subgradient operator, while for convex-concave saddle-point problems, the operator $F$ is composed of the subgradient with respect to the primal variable, and the negative supergradient with respect to the dual variables (see a detailed description in Section 2.3). In these two classical cases, solving the variational inequality corresponds to the usual notion of solution for these two problems. While our main motivation is to have a unique framework for these two subcases, the variational inequality framework is more general (see e.g. Nemirovski, (2004) and references therein).

In this paper we are interested in algorithms to solve the inequality in Eq. (1), while only accessing an oracle for $F(x)$ for any given $x\in\mathcal{K}$, or only an unbiased estimate of $F(x)$. We also assume that we may efficiently project onto the set $\mathcal{K}$ (which we assume compact throughout this paper) using Bregman divergences. In terms of complexity bounds, this problem is by now well-understood with matching upper and lower bounds in a variety of situations. In particular the notion of smoothness (i.e., Lipschitz-continuity of $F$ vs. simply assuming that $F$ is bounded) and the presence of noise are the two important factors influencing the convergence rates. For example, the “Mirror-Prox” algorithm of Nemirovski, (2004) and Juditsky et al., (2011), given the correct step-size (that depends heavily on the properties of the problem, see Section 2), attains the following bounds:

For non-smooth problems where the operator (and its unbiased estimates) is bounded by $G$, the rate $O(GD/\sqrt{T})$ is attained after $T$ iterations, where $D$ is the proper notion of diameter for the set $\mathcal{K}$.

For smooth problems with $L$-Lipschitz operators, and a noise variance of $\sigma^{2}$, the convergence rate is $O(LD^{2}/T+{\sigma}D/\sqrt{T})$.

These rates are actually optimal for this class of problemsThe class of problems indeed includes convex optimization with lower bounds in $O(1/\sqrt{T})$ (Nemirovskii and Yudin,, 1983) and bilinear saddle-point problems with lower bound in $O(1/T)$ (Nemirovsky,, 1992).. However, practitioners may not know in which class their problem lies or know all the required constants needed for running the algorithms. Thus universal (sometimes called adaptive) algorithms are needed to leverage the potentially unknown properties of an optimization problem. Moreover, locally, the problem could be smoother or less noisy than globally, and thus classical algorithms would not benefit from extra local speed-ups.

In this paper we make the following contributions:

We present a universal algorithm for variational inequalities based on the Mirror-Prox algorithm, for both deterministic and stochastic settings. Our method employs a simple adaptive choice of the step-size that leads to optimal rates for smooth and non-smooth variational inequalities. Our algorithm does not require prior knowledge regarding the smoothness or noise properties of the problem.

This is done in the general set-up of arbitrary norms and compatible Bregman divergences.

For convex minimization and convex-concave saddle-point problems, this leads to new adaptive algorithms. In particular, our new adaptive method can be seen as extension of AdaGrad (McMahan and Streeter,, 2010; Duchi et al.,, 2011), that is more appropriate to handling constrained problems.

On the technical side, our work combines the Mirror-Prox method with a novel adaptive learning rate rule inspired by online learning techniques such as AdaGrad (McMahan and Streeter,, 2010; Duchi et al.,, 2011), and optimistic OGD (Chiang et al.,, 2012; Rakhlin and Sridharan,, 2013).

Algorithms for solving variational inequalities date back to Korpelevich, (1976) who was the first to suggest the extragradient method. The key idea behind this method is the following: in each round $t$ we make two updates. First, we take a gradient step from the current iterate $y_{t}$, which leads to a point $y_{t+1/2}$. Then, instead of applying another gradient step starting in $y_{t+1/2}$, we go back to $y_{t}$ and take a step using the gradient of $y_{t+1/2}$, which leads to $y_{t+1}$.

The work of Korpelevich, (1976) was followed by Korpelevich, (1983); Noor, (2003), who further explored the asymptotic behaviour of such extragradient-like algorithms. The seminal work of Nemirovski, (2004) was the first to establish non-asymptotic convergence guarantees of such a method, establishing a rate of $O(LD^{2}/T)$ for smooth problems. Nemirovski’s method named Mirror-Prox was further explored by Juditsky et al., (2011), who analyze the stochastic setting, and present a Mirror-Prox version that obtains a rate of $O(LD^{2}/T+\sigma D/\sqrt{T})$, where $\sigma^{2}$ is the variance of the noise terms. It is also known that in the non-smooth case, Mirror-Prox obtains a rate of $O(GD/\sqrt{T})$ (Juditsky and Nemirovski,, 2011). Note that the Mirror-Prox versions that we have mentioned so far require prior knowledge about the smoothness/non-smoothness and on the noise properties of the problem (i.e., $\sigma$), in order to obtain the optimal bounds for each caseFor the special case of bi-linear saddle-point problems, Juditsky et al., (2013) designed an algorithm that is adaptive to noise, but not to non-smoothness (which is irrelevant for bi-linear problems).. Conversely, our method obtains these optimal rates without any such prior knowledge. Note that Yurtsever et al., (2015); Dvurechensky et al., (2018) devise universal methods to solve variational inequalities that adapt to the smoothness of the problem. Nevertheless, these methods build on a line search technique that is inappropriate for handling noisy problems. Moreover, these methods require a predefined accuracy parameter as an input, which requires careful hyperparameter tuning.

In the past years there have been several works on universal methods for convex optimization (which is a particular case of the variational inequalities framework). Nesterov, (2015) designed a universal method that obtains the optimal convergence rates of $O(LD^{2}/T^{2})$ and $O(GD/\sqrt{T})$ for smooth/non-smooth optimization, without any prior knowledge of the smoothness. Yet, this method builds on a line search technique that is inappropriate to handling noisy problems. Moreover, it also requires a predefined accuracy parameter as an input, which requires careful tuning.

Levy, (2017) designed alternative universal methods for convex minimization that do not require line search, yet these methods obtain a rate of $O(1/T)$ rather than the accelerated $O(1/T^{2})$ rate for smooth objectives. Moreover, their results for the smooth case only holds for unconstrained problems. The same also applies to the well known AdaGrad method (McMahan and Streeter,, 2010; Duchi et al.,, 2011). Recently, Levy et al., (2018) have presented a universal method that obtains the optimal rates for smooth/non-smooth and noisy/noiseless settings, without any prior knowledge of these properties. Nevertheless, their results for the smooth case are only valid in the unconstrained setting. Finally, note that these convex optimization methods are usually not directly applicable to the more general variational inequality framework.

Methods for solving convex-concave zero-sum games or saddle-point problems (another particular case of the variational inequality framework) were explored by the online learning community. The seminal work of Freund et al., (1999) has shown how to employ regret minimization algorithms to solve such games at a rate of $O(1/\sqrt{T})$. While the Mirror-Prox method solves such games at a faster rate of $O(1/{T})$, it requires communication between the players. Interestingly, Daskalakis et al., (2011) have shown how to achieve a rate of $O(1/{T})$ without communication. Finally, Rakhlin and Sridharan, (2013) have provided a much simpler algorithm that obtains the same guarantees.

Variational Inequalities and Gap Functions

Here we present our general framework of variational inequalities with monotone operators, and introduce the notion of associated convex gap function. In Section 2.2 and 2.3, we show how this framework captures the settings of convex optimization, as well as convex-concave minimax games.

Note that $\mathcal{D}_{f}(\cdot,\cdot)$ is always non-negative. For more properties, see, e.g., Nemirovskii and Yudin, (1983) and references therein.

1 Gap functions

And we are usually looking for a strong solution $x^{\ast}\in\mathcal{K}$ of the variational inequality, that satisfies

When $F$ is monotone, as discussed by Juditsky and Nemirovski, (2016), a strong solution is also a weak solution, that is, $\sup_{x\in\mathcal{K}}\ (x^{\ast}-x)\cdot F(x)\leq 0$. Note that we do not use directly the monotonicity property of $F$; we only use the existence of a compatible gap function with respect to $F$, which is an adapted notion of merit function to characterize convergence, that we define in Def. 2.1. We show below that this definition captures the settings of convex optimization and convex-concave games.

We assume to have an access to an oracle for $F$, i.e., upon querying this oracle with $x\in\mathcal{K}$, we receive $F(x)$. Our goal is to find a solution such that its duality gap is (approximately) zero. We also consider a stochastic setting (similarly to Juditsky et al., (2011)), where our goal is to provide guarantees on the expected duality gap. Next we present the central definition of this paper:

and $x^{\ast}\in\mathcal{K}$ is a solution of Eq. (1) if and only if ${\rm DualGap}(x^{\ast}):=\max_{y\in\mathcal{K}}\Delta({x}^{\ast},y)=0$.

Note that given the notion of solution to the variational inequality in Eq. (1), the function $(x,y)\mapsto F(x)\cdot(x-y)$ is a good candidate for $\Delta$, but it is not convex in $x$ in general and thus Jensen’s inequality cannot be applied.

Throughout this paper we will assume there exists a bound $G$ on the magnitude of $F$ (and all of its unbiased estimates), i.e.,

We will sometimes consider the extra assumption that $F$ is $L$-smooth w.r.t. a given norm $\|\cdot\|$, i.e.,

Next we show that the setting that we described in the section (see Def. 2.1) captures two important settings, namely convex optimization and convex-concave zero-sum games.

2 Convex Optimization

We assume that we may query (sub)gradients of $f$. Next we show how this setting is captured by the variational inequality setting. Let us define a gap function and an operator $F$ as follows,

Then by the (sub)gradient inequality for convex functions, it immediately follows that $\Delta$ is a compatible gap function with respect to $F$. Also, it is clear that $\Delta(x,y)$ is convex with respect to $x$. Finally, note that the duality gap in this case is the natural sub-optimality measure, i.e.,

Moreover, if $f$ is $L$-smooth w.r.t. a norm $\|\cdot\|$, then $F$ is smooth with respect to the same norm.

3 Convex-Concave Zero-sum Games

The performance measure for such games is the duality gap which is defined as,

The duality gap is always non-negative, and we seek an (approximate) equilibrium, i.e., a point $(u^{*},v^{*})$ such that ${\rm DualGap}(u^{*},v^{*})=0$.

This setting can be classically described as a variational inequality problem. Let us denote,

It is immediate to show that this gap function, $\Delta$, induces the duality gap appearing in Eq. (3), i.e., ${\rm DualGap}(x):=\max_{x_{0}\in\mathcal{K}}\Delta(x,x_{0})$. Also, from the convex-concavity of $\phi$ it immediately follows that $\Delta(x,x_{0})$ is convex in $x$. The next lemma from Nemirovski, (2004) shows that $\Delta$ is a gap function compatible with $F$ (for completeness we provide its proof in Appendix A.1).

The following applies for any $x:=(u,v),x_{0}:=(u_{0},v_{0})\in\mathcal{U}\times\mathcal{V}$:

Assume that the separate mirror-maps are $1$-strongly convex w.r.t. norms $\|\cdot\|_{\mathcal{U}}$ and $\|\cdot\|_{\mathcal{V}}$, and let $\|\cdot\|_{\mathcal{U}}^{*}$ and $\|\cdot\|_{\mathcal{V}}^{*}$ be the respective dual norms. Also, define $D_{\mathcal{U}}^{2}:=\max_{u\in\mathcal{U}}\mathcal{R}_{\mathcal{U}}(u)-\min_{u\in\mathcal{U}}\mathcal{R}_{\mathcal{U}}(u)$, and similarly define $D_{\mathcal{V}}^{2}$. Juditsky and Nemirovski, (2011) suggest to employ,

In this case $\mathcal{R}_{\mathcal{K}}$ is $1$-strongly-convex w.r.t. $\|\cdot\|_{\mathcal{K}}$. Also, the dual norm of $\|\cdot\|_{\mathcal{K}}$ in this case is,

It can be shown that if the gradient mapping $\nabla_{u}\phi(u,v)$, and $\nabla_{v}\phi(u,v)$ are Lipschitz-continuous with respect to both $u$ and $v$, then the monotone operator $F$ defined through $F(x):=(\nabla_{u}\phi(u,v),-\nabla_{v}\phi(u,v))$ is also smooth. Concretely, let $\|\cdot\|_{\mathcal{U}}$, and $\|\cdot\|_{\mathcal{V}}$ be norms over $\mathcal{U}$ and $\mathcal{V}$, and let $\|\cdot\|_{\mathcal{U}}^{*}$, and $\|\cdot\|_{\mathcal{V}}^{*}$ be their respective dual norms. Juditsky and Nemirovski, (2011) show that if the following holds $\forall u,u^{\prime}\in\mathcal{U},v,v^{\prime}\in\mathcal{V}$,

Then it can be shown that $\forall x,x^{\prime}\in\mathcal{K}$

where $\|\cdot\|_{K}$, and $\|\cdot\|_{\mathcal{K}}^{*}$ are defined in Equations (4) and (5), and,

Universal Mirror-Prox

This section presents our variational inequality algorithm. We first introduce the optimistic-OGD algorithm of Rakhlin and Sridharan, (2013), and present its guarantees. Then we show how to adapt this algorithm together with a novel learning rate rule in order to solve variational inequalities in a universal manner. Concretely, we present an algorithm that, without any prior knowledge regarding the problem’s smoothness, obtains a rate of $O(1/T)$ for smooth problems (Thm. 3.1), and an $O(\sqrt{\log T/T})$ rate for non-smooth problems (Thm. 3.2). Our algorithm can be seen as an adaptive version of the Mirror-Prox method (Nemirovski,, 2004).

We provide a proof sketch of Thm. 3.1 in Section 3.3. The full proofs are deferred to the Appendix.

Here we introduce the optimistic online gradient descent (OGD) algorithm of Rakhlin and Sridharan, (2013). This algorithm applies to the online linear optimization setting that can be described as a sequential game over $T$ rounds between a learner and an adversary. In each round $t\in[T]$,

the learner picks a decision point $x_{t}\in\mathcal{K}$,

the learner incurs a loss of $g_{t}\cdot x_{t}$, and gets to view $g_{t}$ as a feedback.

The performance measure for the learner is the regret which is defined as follows,

and we are usually interested in learning algorithms that ensure a regret which is sublinear in $T$.

where $\mathcal{R}(\cdot)$ is a $1$-strongly-convex function over $\mathcal{K}$ w.r.t. a given norm $\|\cdot\|$, and $\mathcal{D}_{\mathcal{R}}$ is the Bregman divergence of $\mathcal{R}$. The following guarantees for optimistic OGD hold, assuming that the learning rate sequence is non-increasing (see proof in Appendix C.1) ,

where $D^{2}=\max_{x\in\mathcal{K}}\mathcal{R}(x)-\min_{x\in\mathcal{K}}\mathcal{R}(x)$, and $\|\cdot\|_{*}$ is the dual norm of $\|\cdot\|$ .

2 Universal Mirror-Prox

Here we describe a new adaptive scheme for the learning rate of the above mentioned optimistic OGD. Then we show that applying this adaptive scheme to solving variational inequalities yields an algorithm that adapts to smoothness and noise.

Rakhlin and Sridharan, (2013) suggest to apply the following learning rate scheme inside optimistic OGD (Equation (6)),

They show by employing this rule with a version of optimistic OGD yields an algorithm that solves zero-sum matrix games at a fast $O(1/T)$ rate, without any communication between the players. While the Mirror-Prox algorithm (Nemirovski,, 2004) achieves such a fast rate, it requires both players to communicate their iterates to each other in every round.

Our goal here is different. We would like to adapt to the smoothness and noise of the objective, while allowing players to communicate. To do so, we suggest to use the following adaptive scheme,

with the same definition of the diameter $D$ as in Lemma 3.1, and $G_{0}>0$ is an arbitrary constant. Note that the best choice for $G_{0}$ is a tight upper bound on the dual norms of the $g_{t}$’s and $M_{t}$’s, which we denote here by $G$, i.e., $G:=\max_{t\in[T]}\max\{\|g_{t}\|_{*},\|M_{t}\|_{*}\}$. Nevertheless, even if $G_{0}\neq G$ we still achieve convergence guarantees that scales with

In this work we assume to know $D$, yet we do not assume any prior knowledge of $G$.

Finally, note that $Z_{\tau}\in[0,G]$ for any $\tau\geq 1$; this immediately follows by the next lemma.

Let $G$ be a bound on the dual norms of $\{g_{t}\}_{t},\{M_{t}\}_{t}$. Then the above holds for $y_{t-1},x_{t},y_{t}$, that are used in Optimistic OGD (Eq. (6)),

These choices correspond to the extragradient (Korpelevich,, 1976) and to Mirror-Prox (Nemirovski,, 2004) methods.

In Alg. 1 we present our universal Mirror-Prox algorithm for solving variational inequalities. This algorithm combines the Mirror-Prox algorithm (i.e., combining Eq. (9) inside the optimistic OGD of Eq. (6)), together with the new adaptive scheme that we propose in Eq. (8).

Before stating the guarantees of Alg. 1, let us give some intuition behind the learning rate that we suggest in Eq. (8). Note that the original Mirror-Prox algorithm employs two extreme learning rates for the non-smooth and smooth cases. In the smooth case the learning rate is constant, i.e., $\eta_{t}\propto 1/L$, and in the non-smooth case it is decaying, i.e., $\eta_{t}\propto D/(G\sqrt{t})$. Next we show how our adaptive learning rate seems to implicitly adapts to the smoothness of the problem.

For simplicity, let us focus on the convex optimization setting, where our goal is to minimize a convex function $f(\cdot)$, and therefore $F(x):=\nabla f(x)$. Also assume we use $\mathcal{R}(x):=\frac{1}{2}\|x\|_{2}^{2}$. In this case, optimistic OGD (Eq. (6)) is simply, $x_{t}\leftarrow\Pi_{\mathcal{K}}(y_{t-1}-\eta_{t}M_{t})$, and $y_{t}\leftarrow\Pi_{\mathcal{K}}(y_{t-1}-\eta_{t}g_{t})$, where $\Pi_{\mathcal{K}}$ is the orthogonal projection onto $\mathcal{K}$. Now, let $x^{*}=\operatorname*{arg\,min}_{x\in\mathcal{K}}f(x)$, and let us imagine two situations: (i) If $f(\cdot)$ is non-smooth around $x^{*}$, then the norms of the gradients are not decaying as we approach $x^{*}$, and in this case the $\|Z_{t}\|$’s are lower bounded by some constant along all rounds. This implies that $\eta_{t}$ will be proportional to $1/\sqrt{t}$. (ii) Imagine that $f(\cdot)$ is smooth around $x^{*}$. If in addition $\nabla f(x^{*})=0$, this intuitively implies that the magnitudes $\|g_{t}\|$ and $\|M_{t}\|$ go to zero as we approach $x^{*}$, and therefore $\|Z_{t}\|$’s will also go to zero. This intuitively means that $\eta_{t}$ tends to a constant when $t$ tends to infinity. However, note that this behaviour can also be achieved by using an AdaGrad-like (Duchi et al.,, 2011) learning rate rule, i.e., $\eta_{t}\propto(\sum_{\tau=1}^{t}\|g_{\tau}\|^{2}+\|M_{\tau}\|^{2})^{-1/2}$. The reason that we employ the more complicated learning rate of Eq. (8) is in order to handle the case where $f(\cdot)$ is smooth yet $\|\nabla f(x^{*})\|>0$. In this case, the norms of $\|g_{t}\|$ and $\|M_{t}\|$ will not decay as we approach $x^{*}$; nevertheless the norms of $\|Z_{t}\|$’s will intuitively go to zero, implying $\eta_{t}$ tends to a constant. Thus, in a sense, our new learning rate rule can be seen as the appropriate adaptation of AdaGrad to the constrained case.

We are now ready to state our guarantees. We show that when the monotone operator $F$ is smooth, then we minimize the duality gap in Eq. (2) at a fast rate of $O(1/T)$. Conversely, when the monotone operator is non-smooth, then we obtain a rate of $O(\sqrt{\log T/T})$. This is achieved without any prior knowledge regarding the smoothness of $F$. The next result addresses the smooth case (we provide a proof sketch in Sec. 3.3; the full proof appears in App. A.3),

Assume that $F$ is $L$-smooth, and $G$-bounded. Then Alg. 1 used with the learning rate of Eq. (8) implies the following bound,

Recall that $\alpha:=\max\{G/G_{0},G_{0}/G\}$ measures the quality of our prior knowledge $G_{0}$ regarding the actual bound $G$ on the norms of $F(\cdot)$. Next we present our guarantees for the non-smooth case.

Assume that $F$ is $G$-bounded. Alg. 1 used with the learning rate of Eq. (8) implies,

Up to logarithmic terms, we recover the results from Juditsky et al., (2011), with a potential extra factor $\alpha$, which is equal to $1$ if we know a bound $G$ on the norms of the values of $F$ (but we do not require this value to obtain the correct dependence in $T$). The proof of Thm. 3.2 appears in App. A.4.

3 Proof Sketch of Theorem 3.1

We shall require the following simple identity (see Rakhlin and Sridharan, (2013)),

Using the above with $\rho=1/L$, together with $g_{t}:=F(x_{t}),M_{t}=F(y_{t-1})$, and using the $L$-smoothness of $F$ gives,

Combining this inside the regret bound of Eq. (7) and re-arranging we obtain,

where we have used, $Z_{t}^{2}:=\left(\|x_{t}-y_{t}\|^{2}+\|x_{t}-y_{t-1}\|^{2}\right)/{5\eta_{t}^{2}}$. Let us define $\tau_{*}:=\max\{t\in[T]:~{}{1}/{\eta_{t}}\leq 2L\}$, and divide the last term of the regret as follows,

where in the second line we use $2L\leq\frac{1}{\eta_{t}}$ which holds for $t>\tau_{\star}$; implying that $L-\frac{1}{\eta_{t}}\leq-\frac{1}{2\eta_{t}}$. Plugging the above back into Eq. (10) we obtain,

Next we bound terms $\rm{(A)}$ and $\rm{(B)}$ above. To bound $\rm{(A)}$ we will require the following lemma,

For any non-negative numbers $a_{1},\ldots,a_{n}\in[0,{a}]$, and $a_{0}\geq 0$, the following holds:

Recalling that $\eta_{t}=D/\sqrt{G_{0}^{2}+\sum_{\tau=1}^{t-1}Z_{\tau}^{2}}$ (see Eq. (8)), and also recalling that $Z_{\tau}\in[0,G]$ we can use the above lemma to bound term $\rm{(A)}$,

where we have used the definition of $\tau_{*}$ which implies $1/\eta_{\tau*}\leq 2L$.

In the full proof (Appendix A.3) we show that ${\rm{(B)}}\leq{O}(LD^{2}\log(LD/G_{0}))$.

Combining the bounds on $\rm{(A)}$ and $\rm{(B)}$ into Eq. (11) and using $\eta_{1}=D/G_{0}$ implies,

where we used the definition $\alpha:=\max\left\{{G}/{G_{0}},{G_{0}}/{G}\right\}$. Combining the above with the definition of $\bar{x}_{T}$ and using Jensen’s inequality (recall $\Delta$ is convex in its first argument), as well as with the fact that $\Delta$ is a compatible gap function w.r.t. $F$ concludes the proof. ∎

Stochastic Setting

In this section we present the stochastic variational inequality setting. Then we show that using the exact same universal Mirror-Prox algorithm (Alg. 1) that we have presented in the previous section, enables to provide the optimal guarantees for the stochastic setting. This is done without any prior knowledge regarding the smoothness or the stochasticity of the problem.

1 Proof Sketch of Theorem 4.1

Recalling the definition of $\bar{x}_{T}$, and using Jensen’s inequality implies that for any $x\in\mathcal{K}$,

To establish the proof we are left to show that $\mbox{\bf E}\sum_{t=1}^{T}\zeta_{t}\cdot x^{*}\leq O(GD\sqrt{T})$. This is challenging since $x^{*}$, by its definition, is a random variable that may depend on $\{\zeta_{t}\}_{t}$, implying that $\zeta_{t}\cdot x^{*}$ is not zero-mean. Nevertheless, we are able to make use of the martingale difference property of $\{\zeta_{t}\}_{t}$ in order to bound $\mbox{\bf E}\sum_{t=1}^{T}\zeta_{t}\cdot x^{*}$. This is done using the following proposition,

We stress that the proposition applies for random vectors $X$ which might even depend on $(Z_{i})_{i=1}^{n}$. ∎

Conclusion

In this paper, we have presented a universal algorithm for variational inequalities, that can adapt to smoothness and noise, leading, with a single algorithm with very little knowledge of the problem to the best convergence rates in all these set-ups (up to logarithmic factors). There are several avenues worth exploring: (a) an extension to a Matrix-AdaGrad-like algorithm (McMahan and Streeter,, 2010; Duchi et al.,, 2011) where a matrix gain is employed rather than a scalar step-size, (b) an extension that could handle composite problems through additional proximal operators, (c) extensions of adaptivity to all Hölder-continuous mappings (Dvurechensky et al.,, 2018), and finally (d) the inclusion of deterministic error terms to allow biased operator evaluations.

We would like to thank Nicolas Flammarion for fruitful discussions related to this work.

We acknowledge support from the European Research Council (grant SEQUOIA 724063), as well as from the ETH Zürich Postdoctoral Fellowship and Marie Curie Actions for People COFUND program.

References

In Appendix A, we provide the missing proofs related to the Deterministic Setting (Section 3): the proofs of Thm. 3.1 and Thm. 3.2 appear in App. A.3 and A.4. We also provide the proofs of Lemma 2.1 (see App A.1), and Lemma Lemma 3.2 (see App. A.2).

In Appendix B, we provide the missing proofs related to the Stochastic Setting (Section 4): the proofs of Thm. 4.1 and Thm. 4.2 appear in App. B.1 and B.2. And we also prove Proposition B.1 (see App. B.3), which is a central tool in the proofs of the stochastic case. In Appendix C we provide the remaining proofs for the paper.

Appendix A Proofs for the Deterministic Setting (Section 3)

Using convexity we get for any $u_{0}\in\mathcal{U},v\in\mathcal{V}$,

Similarly, using concavity we get for any $u\in\mathcal{U},v_{0}\in\mathcal{V}$,

Summing both of the above equations gives for any $x:=(u,v),x_{0}:=(u_{0},v_{0})$,

where we used $F(x):=(\nabla_{u}\phi(u,v),-\nabla_{v}\phi(u,v))$. This concludes the proof. ∎

A.2 Proof of Lemma 3.2

Here we show that $\|x_{t}-y_{t-1}\|/\eta_{t}\leq G$; the proof of $\|y_{t}-y_{t-1}\|/\eta_{t}\leq G$ follows the exact same steps.

Before we start, note that the following holds for Bregman Divergences,

Now, the following applies for any $x\in\mathcal{K}$ by the definition of $x_{t}$ in Eq. (6),

Combing this with $\mathcal{R}$ being $1$-strongly-convex w.r.t. $\|\cdot\|$ we obtain,

Using Cauchy-Swartz immediately implies that,

Dividing the above equation by $\|x_{t}-y_{t-1}\|$ concludes the proof. ∎

A.3 Proof of Theorem 3.1

We shall require the following simple identity (see Rakhlin and Sridharan, (2013)),

where the last line uses the $L$-smooth of the operator $F$, i.e., $\|F(x_{t})-F(y_{t-1})\|_{*}\leq L\|x_{t}-y_{t-1}\|$. Combining the above inside the regret bound of Eq. (7) we obtain,

where we have used, $Z_{t}^{2}:=\left(\|x_{t}-y_{t}\|^{2}+\|x_{t}-y_{t-1}\|^{2}\right)/{5\eta_{t}^{2}}$.

Now let us define $\tau_{*}:=\max\{t\in[T]:~{}{1}/{\eta_{t}}\leq 2L\}$. We can now divide the last term of the regret according to $\tau_{*}$,

where in the second line we use $2L\leq\frac{1}{\eta_{t}}$ which holds for $t>\tau_{\star}$, implying that $L-\frac{1}{\eta_{t}}\leq-\frac{1}{2\eta_{t}}$. Plugging the above back into Eq. (A.3) we obtain,

Next we bound terms $\rm{(A)}$ and $\rm{(B)}$ above,

We will require the following lemma which we prove in Appendix C.2,

For any non-negative numbers $a_{1},\ldots,a_{n}\in[0,{a}]$, and $a_{0}\geq 0$, the following holds:

Recalling the learning rate rule that we use, $\eta_{t}=D/\sqrt{G_{0}^{2}+\sum_{\tau=1}^{t-1}Z_{\tau}^{2}}$ (see Eq. (8)), and also recalling that $Z_{\tau}\in[0,G]$ we can use the above lemma to bound term $\rm{(A)}$,

where we have used the definition of $\tau_{*}$ which implies $1/\eta_{\tau*}\leq 2L$.

We will require the following lemma (proof is found in Appendix C.4),

For any non-negative real numbers $a_{1},\ldots,a_{n}\in[0,{a}]$, and $a_{0}\geq 0$,

Recalling the learning rate rule that we use, $\eta_{t}=D/\sqrt{G_{0}^{2}+\sum_{\tau=1}^{t-1}Z_{\tau}^{2}}$ (see Eq. (8)), and also recalling that $Z_{\tau}\in[0,G]$ we can use the above lemma to bound term $\rm{(B)}$,

where we have used the definition of $\tau_{*}$ which implies $1/\eta_{\tau*}\leq 2L$.

Combining Equations (A.3) and (A.3) into Eq. (16) and using $\eta_{1}=D/G_{0}$ implies the following regret bound for Alg. 1,

where we used the definition $\alpha:=\max\left\{{G}/{G_{0}},{G_{0}}/{G}\right\}$. Combining the above with the definition of $\bar{x}_{T}$ and using Jensen’s inequality implies,

where we also used the fact that $\forall x_{t},x\in\mathcal{K}$ the following holds,

A.4 Proof of Theorem 3.2

Next we separately bound each of the above terms,

Recalling the learning rate that we employ (see Eq. (8)) we have,

Recalling Lemma A.1 we may bound this term as follows,

where the second line uses $Z_{t}^{2}:=\left(\|x_{t}-y_{t}\|^{2}+\|x_{t}-y_{t-1}\|^{2}\right)/{5\eta_{t}^{2}}$.

For any non-negative real numbers $a_{1},\ldots,a_{n}\in[0,{a}]$, and $a_{0}\geq 0$,

Recalling that $Z_{t}\in[0,G]$ we may use the above lemma to bound term $\rm{(C)}$,

where the second line uses the bound $G$ on the magnitude of the gradients (in the dual norm). The third line uses $Z_{t}^{2}:=\left(\|x_{t}-y_{t}\|^{2}+\|x_{t}-y_{t-1}\|^{2}\right)/{5\eta_{t}^{2}}$.

Combining Equations (20) (A.4) and (A.4) into Eq. (19) implies the following regret bound for Alg. 1,

Combining the above with the definition of $\bar{x}_{T}$ and using Jensen’s inequality implies,

where we used the notation $\alpha:=\max\left\{{G}/{G_{0}},{G_{0}}/{G}\right\}$. We also used the fact that $\forall x_{t},x\in\mathcal{K}$ the following holds,

Appendix B Proofs for the Stochastic Setting (Section 4)

Now following the exact steps as in the proof of Theorem 3.2 implies the following holds w.p. 1,

Recalling the definition of $\bar{x}_{T}$, and using Jensen’s inequality we obtain for any $x\in\mathcal{K}$,

where we have used the following notation,

and clearly we have $\mbox{\bf E}[\zeta_{t}|x_{t}]=0$, and $\{\zeta_{t}\}_{t}$ is a martingale difference sequence.

Let $x^{*}:=\operatorname*{arg\,max}_{x\in\mathcal{K}}\Delta(\bar{x}_{t},x)$. Taking $x=x^{*}$ and taking expectation over Eq. (B.1) gives,

Thus, to establish the proof we are left to show that $\mbox{\bf E}\sum_{t=1}^{T}\zeta_{t}\cdot x^{*}\leq O(GD\sqrt{T\log T})$. We will require the following proposition (its proof appears in Appendix B.3),

where $\|\cdot\|_{*}$ is the dual norm of $\|\cdot\|$.

We stress that the theorem applies for random vectors $X$ which might even dependend of the martingale difference sequence $(Z_{i})_{i=1}^{n}$.

Applying the above lemma with $Z_{t}\leftrightarrow\zeta_{t}$, and $X\leftrightarrow x^{*}$ we obtain,

B.2 Proof of Theorem 4.2

Recall Equation (A.3) from the proof of Theorem 3.1 which states (see Section A.3),

Using the above together with the triangle inequality we get,

Now, following the exact same analysis as in the proof of Theorem 3.1 (see Section A.3) shows the following applies to any $x\in\mathcal{K}$ when using Alg. 1,

Now similarly to the proof of Theorem 4.1 we can show the following to hold for $x^{*}:=\operatorname*{arg\,max}_{x\in\mathcal{K}}\Delta(\bar{x}_{t},x^{*})$ (see Eq. (B.1) and (B.1)),

Next we show that the sum in the second root is bounded by $O(\log T)$. Recalling the definition of $Z_{t}$ we get,

where we used $\eta_{t}=D/\sqrt{G_{0}^{2}+\sum_{\tau=1}^{t-1}Z_{\tau}^{2}}$, we have also used $\forall t;\;Z_{t}\in[0,G]$ together with Lemma A.2, which we remind below.

For any non-negative real numbers $a_{1},\ldots,a_{n}\in[0,{a}]$, and $a_{0}\geq 0$,

Thus, combining Eq. (B.2) inside Eq. (28), and taking expectation we conclude that,

where we have used Jensen’s inequality with respect to the $H(u):=\sqrt{u}$, as well as $\mbox{\bf E}\|\xi_{t}\|_{*}^{2}\leq 4\sigma^{2}$. We also used $\alpha:=\max\{G/G_{0},G_{0}/G\}$.

Using Proposition B.1 (see section B.1), and taking $Z_{t}\leftrightarrow\zeta_{t}$, and $X\leftrightarrow x^{*}$ we obtain,

Using the bounds in Eq. (B.2) and (31), inside Eq. (B.2) gives,

B.3 Proof of Theorem B.1

Let us denote by $\mathcal{R}^{*}$ the Fenchel dual of $\mathcal{R}$. Thus the $1$-strong-convexity of $\mathcal{R}$ w.r.t. $\|\cdot\|$ implies that $\mathcal{R}^{*}$ is $1$-smooth w.r.t. $\|\cdot\|_{*}$.

Using this inequality and taking $y=s\sum_{i=1}^{n}Z_{i}$ and $x=X$, we have,

Next we bound the two terms in the above inequality. Bounding $\rm{(A)}$: Using $\mathcal{R}(x_{0})=0$ together with the boundedness of $\mathcal{R}$, gives,

Bounding $\rm{(B)}$: To bound this term we first require the following lemma that can be found in Juditsky and Nemirovski, (2008); Kakade, (2010) (for completeness we provide a proof in Appendix B.3.1),

Applying the above lemma with $f\leftrightarrow\mathcal{R}^{*}$, and $M_{i}\leftrightarrow sZ_{i}$ gives,

Combining the bounds on $\rm{(A)}$ and $\rm{(B)}$ inside Eq. (33) and taking expectation gives,

Taking $s=\frac{D}{\sqrt{\sum_{i=1}^{n}\mbox{\bf E}\|Z_{i}\|_{*}^{2}}}$, we get,

We will prove the lemma by induction over $n$. For the base case $n=1$, we may use the smoothness of $f$ to get,

Taking expectation and using $\mbox{\bf E}Z_{1}=0$ the lemma follows.

Now for the induction step, assume that $\mbox{\bf E}f(\sum_{i=1}^{n-1}Z_{i})\leq\frac{L}{2}\sum_{i=1}^{n-1}\mbox{\bf E}\|Z_{i}\|_{*}^{2}$. Using the smoothness of $f$ gives,

Taking expectation and using $\mbox{\bf E}[Z_{n}|Z_{1},\ldots,Z_{n-1}]=0$, as well as the induction assumption establishes the lemma. ∎

Appendix C Additional Proofs

Also, any update of the form $a^{*}=\operatorname*{arg\,min}_{a\in A}a\cdot z+\mathcal{D}_{\mathcal{R}}(a,c)$, satisfies for any $b\in A$,

Combining this with the Optimistic OGD learning rule (Eq. (6)) gives, (taking $a^{*}\leftrightarrow x_{t},\;b\leftrightarrow y_{t},\;c\leftrightarrow y_{t-1},\;z\leftrightarrow M_{t}$),

as well as (taking $a^{*}\leftrightarrow y_{t},\;b\leftrightarrow x^{*},\;c\leftrightarrow y_{t-1},\;z\leftrightarrow g_{t}$),

Combining Equations (35)-(37) inside Eq. (C.1) we obtain,

where the last line uses the $1$-strong-convexity of $\mathcal{R}$, implying that $\forall x,y\in\mathcal{K};\;\mathcal{D}_{\mathcal{R}}(x,y)\geq\frac{1}{2}\|x-y\|^{2}$. Summing over $t\in[T]$ we obtain that for any $x^{*}\in\mathcal{K}$,

where in the second inequality we use the fact that $\eta_{t}$ is monotonically non-increasing and thus $\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}\geq 0$, as well as $\forall x\in\mathcal{K};\;\mathcal{D}_{\mathcal{R}}(x,y_{0})\in[0,D^{2}]$. This concludes the proof.

C.2 Proof of Lemma A.1

First direction: Here we actually prove a stronger result which is the following,

The above combined with $a_{n}\geq 0$ immediately implies the first part of Lemma A.1.

We will prove this Eq. (38) by induction. The base case, $n=1$, holds since in this case,

which is holds true since $a_{1},a_{0}\geq 0$.

For the induction step assume that the Eq. (38) holds for $n-1$ and let us show it holds for $n$. By the induction assumption,

where we denote $x:=a_{n}$ and $Z=a_{0}+\sum_{i=1}^{n}a_{i}$ (note that $x<Z$). Thus, in order to prove the lemma it is sufficient to show that,

Looking at the function $H(x):=\sqrt{Z-x}+\frac{x}{\sqrt{Z-x}}$ it is immediate to validate that $H(\cdot)$ is monotonically increasing for any $x\in[0,Z]$ (since its derivative is non-negative in this line segment) and therefore for any $x\in[0,Z]$ we have,

This establishes Eq. (38) which in turn concludes the first part of the proof.

For this part of the proof we will need the following lemma which we prove in Section C.3,

For any non-negative numbers $a_{1},\ldots,a_{n}\in[0,{a}]$, the following holds:

Now let us divide into two cases. Assume $a\leq a_{0}$, in this case it is clear that,

where the second inequality holds by Lemma C.1. We are therefore left to analyze the case where $a_{0}\leq a$. In this case, let us denote the following,

Next we divide the relevant sum according to $N_{0}$,

where we used $\sum_{j=1}^{N_{0}-2}a_{j}\leq{a}$, as well as $\forall i\geq N_{0};~{}\sum_{j=1}^{i-1}a_{j}\geq{a}$. Both follow by the definition of $N_{0}$. The last line uses ${a}\leq\sum_{j=1}^{N_{0}-1}a_{j}$, and the line before last (i.e., the fifth line) uses Lemma C.1. This concludes the second part of the proof. ∎

C.3 Proof of Lemma C.1

We will require the following lemma from McMahan and Streeter, (2010) (appear as Lemma $7$ therein).

For any non-negative numbers $a_{1},\ldots,a_{n}$ the following holds:

Using the above lemma together with $\forall i;~{}a_{i}\leq{a}$ we have,

where we used $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ which hold $\forall a,b\geq 0$. This concludes the second part of the proof. ∎

C.4 Proof of Lemma A.2

Next we divide the relevant sum according to $N_{0}$,

where we used $\sum_{j=1}^{N_{0}-2}a_{j}\leq{a}$, as well as $\forall i\geq N_{0};~{}\sum_{j=1}^{i-1}a_{j}\geq{a}$. Both follow by the definition of $N_{0}$. And the fourth line uses the following lemma which we borrow from Levy et al., (2018) (appears as Lemma A.3 therein),

For any non-negative real numbers $b_{1},\ldots,b_{n}$,

where the third line uses $\forall x\geq 0,~{}\log(1+x)\leq x$, and the last line uses $a_{n}\leq{a}$. Combining Equations (C.4) and (C.4) concludes the proof. ∎