Optimization, Learning, and Games with Predictable Sequences

Introduction

Recently, no-regret algorithms have received increasing attention in a variety of communities, including theoretical computer science, optimization, and game theory . The wide applicability of these algorithms is arguably due to the black-box regret guarantees that hold for arbitrary sequences. However, such regret guarantees can be loose if the sequence being encountered is not “worst-case”. The reduction in “arbitrariness” of the sequence can arise from the particular structure of the problem at hand, and should be exploited. For instance, in some applications of online methods, the sequence comes from an additional computation done by the learner, thus being far from arbitrary.

One way to formally capture the partially benign nature of data is through a notion of predictable sequences . We exhibit applications of this idea in several domains. First, we show that the Mirror Prox method , designed for optimizing non-smooth structured saddle-point problems, can be viewed as an instance of the predictable sequence approach. Predictability in this case is due precisely to smoothness of the inner optimization part and the saddle-point structure of the problem. We extend the results to Hölder-smooth functions, interpolating between the case of well-predictable gradients and “unpredictable” gradients.

Online Learning with Predictable Gradient Sequences

Let us describe the online convex optimization (OCO) problem and the basic algorithm studied in . Let $\mathcal{F}$ be a convex set of moves of the learner. On round $t=1,\ldots,T$, the learner makes a prediction $f_{t}\in\mathcal{F}$ and observes a convex function $G_{t}$ on $\mathcal{F}$. The objective is to keep regret

small for any $f^{*}\in\mathcal{F}$. Let $\mathcal{R}$ be a $1$-strongly convex function w.r.t. some norm $\|\cdot\|$ on $\mathcal{F}$, and let $g_{0}=\arg\min_{g\in\mathcal{F}}\mathcal{R}(g)$. Suppose that at the beginning of every round $t$, the learner has access to $M_{t}$, a vector computable based on the past observations or side information. In this paper we study the Optimistic Mirror Descent algorithm, defined by the interleaved sequence

where $\mathcal{D}_{\mathcal{R}}$ is the Bregman Divergence with respect to $\mathcal{R}$ and $\{\eta_{t}\}$ is a sequence of step sizes that can be chosen adaptively based on the sequence observed so far. The method adheres to the OCO protocol since $M_{t}$ is available at the beginning of round $t$, and $\nabla G_{t}(f_{t})$ becomes available after the prediction $f_{t}$ is made. The sequence $\{f_{t}\}$ will be called primary, while $\{g_{t}\}$ – secondary. This method was proposed in for $M_{t}=\nabla G_{t-1}(f_{t-1})$, and the following lemma is a straightforward extension of the result in for general $M_{t}$:

where $R\geq 0$ is such that $\mathcal{D}_{\mathcal{R}}(f^{*},g_{0})\leq R^{2}$ and $\nabla_{t}=\nabla G_{t}(f_{t})$.

When applying the lemma, we will often use the simple fact that

In particular, by setting $\rho=\eta$, we obtain the (unnormalized) regret bound of $\eta^{-1}R^{2}+(\eta/2)\sum_{t=1}^{T}\left\|\nabla_{t}-M_{t}\right\|_{*}^{2}$, which is $R\sqrt{2\sum_{t=1}^{T}\left\|\nabla_{t}-M_{t}\right\|_{*}^{2}}$ by choosing $\eta$ optimally. Since this choice is not known ahead of time, one may either employ the doubling trick, or choose the step size adaptively:

with $R_{\max}^{2}=\operatorname*{\vphantom{p}sup}_{f,g\in\mathcal{F}}\mathcal{D}_{\mathcal{R}}(f,g)$. Then regret of the Optimistic Mirror Descent algorithm is upper bounded by

These results indicate that tighter regret bounds are possible if one can guess the next gradient $\nabla_{t}$ by computing $M_{t}$. One such case arises in offline optimization of a smooth function, whereby the previous gradient turns out to be a good proxy for the next one. More precisely, suppose we aim to optimize a function $G(f)$ whose gradients are Lipschitz continuous: $\|\nabla G(f)-\nabla G(g)\|_{*}\leq H\|f-g\|$ for some $H>0$. In this optimization setting, no guessing of $M_{t}$ is needed: we may simply query the oracle for the gradient and set $M_{t}=\nabla G(g_{t-1})$. The Optimistic Mirror Descent then becomes

which can be recognized as the Mirror Prox method, due to Nemirovski . By smoothness, $\|\nabla G(f_{t})-M_{t}\|_{*}=\|\nabla G(f_{t})-\nabla G(g_{t-1})\|_{*}\leq H\|f_{t}-g_{t-1}\|$. Lemma 1 with Eq. (3) and $\rho=\eta=1/H$ immediately yields a bound

which implies that the average $\bar{f}_{T}=\frac{1}{T}\sum_{t=1}^{T}f_{t}$ satisfies $G(\bar{f}_{T})-G(f^{*})\leq HR^{2}/T$, a known bound for Mirror Prox. We now extend this result to arbitrary $\alpha$-Hölder smooth functions, that is convex functions $G$ such that $\|\nabla G(f)-\nabla G(g)\|_{*}\leq H\|f-g\|^{\alpha}$ for all $f,g\in\mathcal{F}$.

where $R\geq 0$ is such that $\operatorname*{\vphantom{p}sup}_{f\in\mathcal{F}}\mathcal{D}_{\mathcal{R}}(f,g_{0})\leq R$.

This result provides a smooth interpolation between the $T^{-1/2}$ rate at $\alpha=0$ (that is, no predictability of the gradient is possible) and the $T^{-1}$ rate when the smoothness structure allows for a dramatic speed up with a very simple modification of the original Mirror Descent.

Structured Optimization

In this section we consider the structured optimization problem

where $G(f)$ is of the form $G(f)=\operatorname*{\vphantom{p}sup}_{x\in\mathcal{X}}\phi(f,x)$ with $\phi(\cdot,x)$ convex for every $x\in\mathcal{X}$ and $\phi(f,\cdot)$ concave for every $f\in\mathcal{F}$. Both $\mathcal{F}$ and $\mathcal{X}$ are assumed to be convex sets. While $G$ itself need not be smooth, it has been recognized that the structure can be exploited to improve rates of optimization if the function $\phi$ is smooth . From the point of view of online learning, we will see that the optimization problem of the saddle point type can be solved by playing two online convex optimization algorithms against each other (henceforth called Players I and II).

Specifically, assume that Player I produces a sequence $f_{1},\ldots,f_{T}$ by using a regret-minimization algorithm, such that

and Player II produces $x_{1},\ldots,x_{T}$ with

where $\bar{f}_{T}=\frac{1}{T}\sum_{t=1}^{T}f_{t}$ and $\bar{x}_{T}=\frac{1}{T}\sum_{t=1}^{T}x_{t}$. By adding (4) and (5), we have

which sandwiches the previous sequence of inequalities up to the sum of regret rates and implies near-optimality of $\bar{f}_{T}$ and $\bar{x}_{T}$.

Suppose both players employ the Optimistic Mirror Descent algorithm with, respectively, predictable sequences $M^{1}_{t}$ and $M^{2}_{t}$, $1$-strongly convex functions $\mathcal{R}_{1}$ on $\mathcal{F}$ (w.r.t. $\|\cdot\|_{\mathcal{F}}$) and $\mathcal{R}_{2}$ on $\mathcal{X}$ (w.r.t. $\|\cdot\|_{\mathcal{X}}$), and fixed learning rates $\eta$ and $\eta^{\prime}$. Let $\{f_{t}\}$ and $\{x_{t}\}$ denote the primary sequences of the players while let $\{g_{t}\},\{y_{t}\}$ denote the secondary. Then for any $\alpha,\beta>0$,

where $R_{1}$ and $R_{2}$ are such that $\mathcal{D}_{\mathcal{R}_{1}}(f^{*},g_{0})\leq R_{1}^{2}$ and $\mathcal{D}_{\mathcal{R}_{2}}(x^{*},y_{0})\leq R_{2}^{2}$, and $\bar{f}_{T}=\frac{1}{T}\sum_{t=1}^{T}f_{t}$.

The proof of Lemma 4 is immediate from Lemma 1. We obtain the following corollary:

$\|\nabla_{f}\phi(f,x)-\nabla_{f}\phi(g,x)\|_{\mathcal{F}^{*}}\leq H_{1}\|f-g\|^{\alpha}_{\mathcal{F}},~{}~{}~{}\|\nabla_{f}\phi(f,x)-\nabla_{f}\phi(f,y)\|_{\mathcal{F}^{*}}\leq H_{2}\|x-y\|^{\alpha^{\prime}}_{\mathcal{X}}$

and $\|\nabla_{x}\phi(f,x)-\nabla_{x}\phi(g,x)\|_{\mathcal{X}^{*}}\leq H_{4}\|f-g\|^{\beta}_{\mathcal{F}},~{}~{}~{}\|\nabla_{x}\phi(f,x)-\nabla_{x}\phi(f,y)\|_{\mathcal{X}^{*}}\leq H_{3}\|x-y\|^{\beta^{\prime}}_{\mathcal{X}}$.

Let $\gamma=\min\{\alpha,\alpha^{\prime},\beta,\beta^{\prime}\}$, $H=\max\{H_{1},H_{2},H_{3},H_{4}\}$. Suppose both players employ Optimistic Mirror Descent with $M^{1}_{t}=\nabla_{f}\phi(g_{t-1},y_{t-1})$ and $M^{2}_{t}=\nabla_{x}\phi(g_{t-1},y_{t-1})$, where $\{g_{t}\}$ and $\{y_{t}\}$ are the secondary sequences updated by the two algorithms, and with step sizes $\eta=\eta^{\prime}=(R_{1}^{2}+R_{2}^{2})^{\frac{1-\gamma}{2}}(2H)^{-1}\left(\frac{T}{2}\right)^{\frac{\gamma-1}{2}}$. Then

As revealed in the proof of this corollary, the negative terms in (7), that come from an upper bound on regret of Player I, in fact contribute to cancellations with positive terms in regret of Player II, and vice versa. Such a coupling of the upper bounds on regret of the two players can be seen as leading to faster rates under the appropriate assumptions, and this idea will be exploited to a great extent in the proofs of the next section.

Zero-sum Game and Uncoupled Dynamics

The notions of a zero-sum matrix game and a minimax equilibrium are arguably the most basic and important notions of game theory. The tight connection between linear programming and minimax equilibrium suggests that there might be simple dynamics that can lead the two players of the game to eventually converge to the equilibrium value. Existence of such simple or natural dynamics is of interest in behavioral economics, where one asks whether agents can discover static solution concepts of the game iteratively and without extensive communication.

More formally, let $A\in^{n\times m}$ be a matrix with bounded entries. The two players aim to find a pair of near-optimal mixed strategies $(\bar{f},\bar{x})\in\Delta_{n}\times\Delta_{m}$ such that $\bar{f}^{\scriptscriptstyle\mathsf{T}}A\bar{x}$ is close to the minimax value $\min_{f\in\Delta_{n}}\max_{x\in\Delta_{m}}f^{\scriptscriptstyle\mathsf{T}}Ax$, where $\Delta_{n}$ is the probability simplex over $n$ actions. Of course, this is a particular form of the saddle point problem considered in the previous section, with $\phi(f,x)=f^{\scriptscriptstyle\mathsf{T}}Ax$. It is well-known (and follows immediately from (6)) that the players can compute near-optimal strategies by simply playing no-regret algorithms . More precisely, on round $t$, the players I and II “predict” the mixed strategies $f_{t}$ and $x_{t}$ and observe $Ax_{t}$ and $f_{t}^{\scriptscriptstyle\mathsf{T}}A$, respectively. While black-box regret minimization algorithms, such as Exponential Weights, immediately yield $\mathcal{O}(T^{-1/2})$ convergence rates, Daskalakis et al asked whether faster methods exist. To make the problem well-posed, it is required that the two players are strongly uncoupled: neither $A$ nor the number of available actions of the opponent is known to either player, no “funny bit arithmetic” is allowed, and memory storage of each player allows only for constant number of payoff vectors. The authors of exhibited a near-optimal algorithm that, if used by both players, yields a pair of mixed strategies that constitutes an $\mathcal{O}\left(\frac{\log(m+n)(\log T+(\log(m+n))^{3/2})}{T}\right)$-approximate minimax equilibrium. Furthermore, the method has a regret bound of the same order as Exponential Weights when faced with an arbitrary sequence. The algorithm in is an application of the excessive gap technique of Nesterov, and requires careful choreography and interleaving of rounds between the two non-communicating players. The authors, therefore, asked whether a simple algorithm (e.g. a modification of Exponential Weights) can in fact achieve the same result. We answer this in the affirmative. While a direct application of Mirror Prox does not yield the result (and also does not provide strong decoupling), below we show that a modification of Optimistic Mirror Descent achieves the goal. Furthermore, by choosing the step size adaptively, the same method guarantees the typical $\mathcal{O}(T^{-1/2})$ regret if not faced with a compliant player, thus ensuring robustness.

In Section 4.1, we analyze the “first-order information” version of the problem, as described above: upon playing the respective mixed strategies $f_{t}$ and $x_{t}$ on round $t$, Player I observes $Ax_{t}$ and Player II observes $f_{t}^{\scriptscriptstyle\mathsf{T}}A$. Then, in Section 4.2, we consider an interesting extension to partial information, whereby the players submit their moves $f_{t},x_{t}$ but only observe the real value $f_{t}^{\scriptscriptstyle\mathsf{T}}Ax_{t}$. Recall that in both cases the matrix $A$ is not known to the players.

Consider the following simple algorithm. Initialize $f_{0}=g^{\prime}_{0}\in\Delta_{n}$ and $x_{0}=y^{\prime}_{0}\in\Delta_{m}$ to be uniform distributions, set $\beta=1/T^{2}$ and proceed as follows:

On round $t$, Player I performs $\displaystyle\text{Play}~{}~{}~{}~{}~{}f_{t}\text{ and observe }Ax_{t}$ $\displaystyle\text{Update}~{}~{}~{}g_{t}(i)\propto g^{\prime}_{t-1}(i)\exp\{-\eta_{t}[Ax_{t}]_{i}\},~{}~{}~{}g^{\prime}_{t}=\left(1-\beta\right)g_{t}+\left(\beta/n\right){\mathbf{1}}_{n}$ $\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}f_{t+1}(i)\propto g^{\prime}_{t}(i)\exp\{-\eta_{t+1}[Ax_{t}]_{i}\}$ while simultaneously Player II performs $\displaystyle\text{Play}~{}~{}~{}~{}~{}x_{t}\text{ and observe }f_{t}^{\top}A$ $\displaystyle\text{Update}~{}~{}~{}y_{t}(i)\propto y^{\prime}_{t-1}(i)\exp\{-\eta^{\prime}_{t}[f_{t}^{\scriptscriptstyle\mathsf{T}}A]_{i}\},~{}~{}~{}y^{\prime}_{t}=\left(1-\beta\right)y_{t}+\left(\beta/m\right){\mathbf{1}}_{m}$ $\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}x_{t+1}(i)\propto y^{\prime}_{t}(i)\exp\{-\eta^{\prime}_{t+1}[f_{t}^{\scriptscriptstyle\mathsf{T}}A]_{i}\}$

Let $A\in^{n\times m}$, $\mathcal{F}=\Delta_{n}$, $\mathcal{X}=\Delta_{m}$. If both players use above algorithm with, respectively, $M_{t}^{1}=Ax_{t-1}$ and $M_{t}^{2}=f_{t-1}^{\scriptscriptstyle\mathsf{T}}A$, and the adaptive step sizes

respectively, then the pair $(\bar{f}_{T},\bar{x}_{T})$ is an $O\left(\frac{\log m+\log n+\log T}{T}\right)$-approximate minimax equilibrium. Furthermore, if only one player (say, Player I) follows the above algorithm, her regret against any sequence $x_{1},\ldots,x_{T}$ of plays is

In particular, this implies the worst-case regret of $\mathcal{O}\left(\frac{\log(nT)}{\sqrt{T}}\right)$ in the general setting of online linear optimization.

We remark that (9) can give intermediate rates for regret in the case that the second player deviates from the prescribed strategy but produces “stable” moves. For instance, if the second player employs a mirror descent algorithm (or Follow the Regularized Leader / Exponential Weights method) with step size $\eta$, one can typically show stability $\|x_{t}-x_{t-1}\|=\mathcal{O}(\eta)$. In this case, (9) yields the rate $\mathcal{O}\left(\frac{\eta\log T}{\sqrt{T}}\right)$ for the first player. A typical setting of $\eta\propto T^{-1/2}$ for the second player still ensures the $\mathcal{O}(\log T/T)$ regret for the first player.

Let us finish with a technical remark. The reason for the extra step of “mixing in” the uniform distribution stems from the goal of having an adaptive and robust method that still attains $\mathcal{O}(T^{-1/2})$ regret if the other player deviates from using the algorithm. If one is only interested in the dynamics when both players cooperate, this step is not necessary, and in this case the extraneous $\log T$ factor disappears from the above bound, leading to the $O\left(\frac{\log n+\log m}{T}\right)$ convergence. On the technical side, the need for the extra step is the following. The adaptive step size result of Corollary 2 involves the term $R_{\max}^{2}\geq\operatorname*{\vphantom{p}sup}_{g}\mathcal{D}_{\mathcal{R}_{1}}(f^{*},g)$ which is potentially infinite for the negative entropy function $\mathcal{R}_{1}$. It is possible that the doubling trick or the analysis of Auer et al (who encountered the same problem for the Exponential Weights algorithm) can remove the extra $\log T$ factor while still preserving the regret minimization property. We also remark that $R_{\max}$ is small when $\mathcal{R}_{1}$ is instead the $p$-norm; hence, the use of this regularizer avoids the extraneous logarithmic in $T$ factor while still preserving the logarithmic dependence on $n$ and $m$. However, projection onto the simplex under the $p$-norm is not as elegant as the Exponential Weights update.

2 Partial Information

We now turn to the partial (or, zero-th order) information model. Recall that the matrix $A$ is not known to the players, yet we are interested in finding $\epsilon$-optimal minimax strategies. On each round, the two players choose mixed strategies $f_{t}\in\Delta_{n}$ and $x_{t}\in\Delta_{m}$, respectively, and observe $f_{t}^{\scriptscriptstyle\mathsf{T}}Ax_{t}$. Now the question is, how many such observations do we need to get to an $\epsilon$-optimal minimax strategy? Can this be done while still ensuring the usual no-regret rate?

The specific setting we consider below requires that on each round $t$, the two players play four times, and that these four plays are $\delta$-close to each other (that is, $\|f_{t}^{i}-f_{t}^{j}\|_{1}\leq\delta$ for $i,j\in\{1,\ldots,4\}$). Interestingly, up to logarithmic factors, the fast rate of the previous section is possible even in this scenario, but we do require the knowledge of the number of actions of the opposing player (or, an upper bound on this number). We leave it as an open problem the question of whether one can attain the $1/T$-type rate with only one play per round.

Let $A\in^{n\times m}$, $\mathcal{F}=\Delta_{n}$, $\mathcal{X}=\Delta_{m}$, let $\delta$ be small enough (e.g. exponentially small in $m,n,T$), and let $\beta=1/T^{2}$. If both players use above algorithms with the adaptive step sizes

respectively, then the pair $(\bar{f}_{T},\bar{x}_{T})$ is an

-approximate minimax equilibrium. Furthermore, if only one player (say, Player I) follows the above algorithm, her regret against any sequence $x_{1},\ldots,x_{T}$ of plays is bounded by

We leave it as an open problem to find an algorithm that attains the $1/T$-type rate when both players only observe the value $e_{i}^{\scriptscriptstyle\mathsf{T}}Ae_{j}=A_{i,j}$ upon drawing pure actions $i,j$ from their respective mixed strategies $f_{t},x_{t}$. We hypothesize a rate better than $T^{-1/2}$ is not possible in this scenario.

Approximate Smooth Convex Programming

In this section we show how one can use the structured optimization results from Section 3 for approximately solving convex programming problems. Specifically consider the optimization problem

where $\mathcal{G}$ is a convex set and each $G_{i}$ is an $H$-smooth convex function. Let the optimal value of the above optimization problem be given by $F^{*}>0$, and without loss of generality assume $F^{*}$ is known (one typically performs binary search if it is not known). Define the sets $\mathcal{F}=\{f:f\in\mathcal{G},c^{\top}f=F^{*}\}$ and $\mathcal{X}=\Delta_{d}$. The convex programming problem in (10) can now be reformulated as

This problem is in the saddle-point form, as studied earlier in the paper. We may think of the first player as aiming to minimize the above expression over $\mathcal{F}$, while the second player maximizes over a mixture of constraints with the aim of violating at least one of them.

Fix $\gamma,\epsilon>0$. Assume there exists $f_{0}\in\mathcal{G}$ such that $c^{\top}f_{0}\geq 0$ and for every $i\in[d]$, $G_{i}(f_{0})\leq 1-\gamma$. Suppose each $G_{i}$ is $1$-Lipschitz over $\mathcal{F}$. Consider the solution

We then have that $\hat{f}_{T}\in\mathcal{G}$ satisfies all $d$ constraints and is $\frac{\epsilon}{\gamma}$-approximate, that is

Lemma 8 tells us that using the predictable sequences approach for the two players, one can obtain an $\frac{\epsilon}{\gamma}$-approximate solution to the smooth convex programming problem in number of iterations at most order $1/\epsilon$. If $T_{1}$ (reps. $T_{2}$) is the time complexity for single update of the predictable sequence algorithm of Player I (resp. Player 2), then time complexity of the overall procedure is $\mathcal{O}\left(\frac{T_{1}+T_{2}}{\epsilon}\right)$

We now apply the above result to the problem of finding Max Flow between a source and a sink in a network, such that the capacity constraint on each edge is satisfied. For simplicity, consider a network where each edge has capacity $1$ (the method can be easily extended to the case of varying capacity). Suppose the number of edges $d$ in the network is the same order as number of vertices in the network. The Max Flow problem can be seen as an instance of a convex (linear) programming problem, and we apply the proposed algorithm for structured optimization to obtain an approximate solution.

For the Max Flow problem, the sets $\mathcal{G}$ and $\mathcal{F}$ are given by sets of linear equalities. Further, if we use Euclidean norm squared as regularizer for the flow player, then projection step can be performed in $\mathcal{O}(d)$ time using conjugate gradient method. This is because we are simply minimizing Euclidean norm squared subject to equality constraints which is well conditioned. Hence $T_{1}=\mathcal{O}(d)$. Similarly, the Exponential Weights update has time complexity $\mathcal{O}(d)$ as there are order $d$ constraints, and so overall time complexity to produce $\epsilon$ approximate solution is given by $\mathcal{O}(nd)$, where $n$ is the number of iterations of the proposed procedure.

Once again, we shall assume that we know the value of the maximum flow $F^{*}$ (for, otherwise, we can use binary search to obtain it).

Applying the procedure for smooth convex programming from Lemma 8 to the Max Flow problem with $f_{0}=\mathbf{0}\in\mathcal{G}$ the flow, the time complexity to compute an $\epsilon$-approximate Max Flow is bounded by

This time complexity matches the known result from , but with a much simpler procedure (gradient descent for the flow player and Exponential Weights for the constraints). It would be interesting to see whether the techniques presented here can be used to improve the dependence on $d$ to $d^{4/3}$ or better while maintaining the $1/\epsilon$ dependence. While the result of has the improved $d^{4/3}$ dependence, the complexity in terms of $\epsilon$ is much worse.

Discussion

We close this paper with a discussion. As we showed, the notion of using extra information about the sequence is a powerful tool with applications in optimization, convex programming, game theory, to name a few. All the applications considered in this paper, however, used some notion of smoothness for constructing the predictable process $M_{t}$. An interesting direction of further research is to isolate more general conditions under which the next gradient is predictable, perhaps even when the functions are not smooth in any sense. For instance one could use techniques from bundle methods to further restrict the set of possible gradients the function being optimized can have at various points in the feasible set. This could then be used to solve for the right predictable sequence to use so as to optimize the bounds. Using this notion of selecting predictable sequences one can hope to derive adaptive optimization procedures that in practice can provide rapid convergence.

Acknowledgements: We thank Vianney Perchet for insightful discussions. We gratefully acknowledge the support of NSF under grants CAREER DMS-0954737 and CCF-1116928, as well as Dean’s Research Fund.

References

Proofs

Any update of the form $a^{*}=\arg\min_{a\in A}\left\langle a,x\right\rangle+\mathcal{D}_{\mathcal{R}}(a,c)$ satisfies for any $d\in A$

Combining, $\left\langle f_{t}-f^{*},\nabla_{t}\right\rangle$ is upper bounded by

where in the last step we used strong convexity: for any $f,f^{\prime}$, $\mathcal{D}_{\mathcal{R}}(f,f^{\prime})\geq\frac{1}{2}\left\|f-f^{\prime}\right\|^{2}$. Summing over $t=1,\ldots,T$ yields, for any $f^{*}\in\mathcal{F}$,

Appealing to convexity of $G_{t}$’s completes the proof. ∎

Let us re-work the proof of Lemma 1 for the case of a changing $\eta_{t}$. Eq. (15) and (16) are now replaced by

Summing over $t=1,\ldots,T$ yields, for any $f^{*}\in\mathcal{F}$,

Using this step size in Equation (20) and defining $\eta_{1}=1$, $\sum_{t=1}^{T}\left\langle f_{t}-f^{*},\nabla_{t}\right\rangle$ is upper bounded by

where we used (3) with $\rho=\eta_{t+1}$ and dropped one of the positive terms. The last two terms can be upper bounded as

Let $\nabla_{t}=\nabla G(f_{t})$ and $M_{t}=\nabla G(g_{t-1})$. Then by Lemma 1 and by Hölder smoothness,

We can re-write the middle term in the upper bound as

by Hölder’s inequality with conjugate powers $1/p=(1-\alpha)/2$ and $1/q=(1+\alpha)/2$. We further upper bound the last term using AM-GM inequality as

Setting $\eta=R^{1-\alpha}H^{-1}(1+\alpha)^{-\frac{1+\alpha}{2}}(1-\alpha)^{-\frac{1-\alpha}{2}}T^{-\frac{1-\alpha}{2}}$ yields an upper bound of

Using $\|a+b\|^{2}\leq 2\|a\|^{2}+2\|b\|^{2}$ and the smoothness assumption yields

As in the proof of Lemma 3, we use Hölder inequality to further upper bound by

Setting $\eta=\eta^{\prime}$ we get an upper bound of

Finally picking step size as $\eta=(R_{1}^{2}+R_{2}^{2})^{\frac{1-\gamma}{2}}(2H)^{-1}\left(\frac{T}{2}\right)^{\frac{\gamma-1}{2}}$ we conclude that

Let $\mathcal{R}_{1}(f)=\sum_{i=1}^{n}f(i)\ln f(i)$ and, respectively, $\mathcal{R}_{2}(x)=\sum_{i=1}^{m}x(i)\ln x(i)$. These functions are strongly convex with respect to $\|\cdot\|_{1}$ norm on the respective flat simplex. We first upper bound regret of Player I, writing $\nabla_{t}$ as a generic observation vector, later to be chosen as $Ax_{t}$, and $M_{t}$ as a generic predictable sequence, later chosen to be $Ax_{t-1}$. Observe that $\|g^{\prime}_{t}-g_{t}\|_{1}\leq 1/T^{2}$. Let $f^{*}=e_{i^{*}}$ be a vertex of the simplex. Then

We conclude that $\left\langle f_{t}-f^{*},\nabla_{t}\right\rangle$ is upper bounded by

Using strong convexity, the term involving the four divergences can be further upper bounded by

Using the above in the bound on $\left\langle f_{t}-f^{*},\nabla_{t}\right\rangle$ and summing over $t=1,\ldots,T$, and using the fact that the step size are non-increasing, we conclude that

where $R_{1,\max}^{2}$ is an upper bound on the largest KL divergence between $f^{*}$ and any $g^{\prime}$ that has all coordinates at least $1/(nT^{2})$. Since $f^{*}$ is a vertex of the flat simplex, we may take $R_{1,\max}^{2}\triangleq\log(nT^{2})$. Also note that $1/\eta_{t}\leq c\sqrt{T}$ and so $\frac{2}{T^{2}}\sum_{t=1}^{T}\frac{1}{\eta_{t}}\leq\frac{c}{T^{1/2}}\leq 1$ for $T$ large enough. Hence we conclude that a bound on regret of Player I is given by

With this, the upper bound on Player I’s unnormalized regret is

Adding the regret of the second player who uses step size $\eta^{\prime}_{t}$, the overall bound on the suboptimality, as in Eq. (6), is

By over-bounding with $\sqrt{c}\leq c+1$ for $c\geq 0$, we obtain an upper bound

Since each entry of the matrix is bounded by $1$,

and similar inequality holds for the other player too. This leads to an upper bound of

Similarly we also have that $\left\|y^{\prime}_{t}-x_{t}\right\|^{2}-\left\|y_{t}-x_{t}\right\|^{2}\leq\frac{4}{T^{2}}$. Using these in Eq. (28) we conclude that the overall bound on the suboptimality is

This proves the result for the case when both players adhere to the prescribed algorithm. Now, consider the case when Player I adheres, but we do not make any assumption about Player II. Then, from Eq. (27) and Eq. (3) with $\rho=\eta_{t}$, the upper bound on, $\sum_{t=1}^{T}\left<f_{t}-f^{*},\nabla_{t}\right>$, the unnormalized regret of Player I’s is

Now, using the definition of the stepsize,

Using the same line of proof as the one used to arrive at Eq. (27) in Proposition 6, we get that the unnormalized regret for Player I can be upper bounded as,

Since $\left\|g_{t}-f_{t}\right\|^{2}\leq 4$, we upper bound the above by

the upper bound on Player I’s unnormalized regret is

We first consider the case when both players play the prescribed algorithm. In this case, a similar regret bound holds for Player II. Adding the regret of the second player who uses step size $\eta^{\prime}_{t}$, the overall bound on the suboptimality, as in Eq. (6), is

Similarly we have $\left\|\hat{b}_{t}-\bar{b}_{t-1}\right\|_{*}\leq m\left\|f_{t}-f_{t-1}\right\|$. Hence using this, we can bound the sub-optimality as

Using the fact that $\sqrt{c^{2}}\leq c^{2}+1$ we further bound sub-optimality by

Hence we can conclude that sub-optimality is bounded by

Just as in the proof of Proposition 6 we have $R_{1,\max}\leq\sqrt{\log(nT^{2})}$ and $R_{2,\max}\leq\sqrt{\log(mT^{2})}$ and so overall we get the bound on sub-optimality :

Player II deviates from algorithm :

Now let us consider the case when the Player 2 deviates from the prescribed algorithm. In this case, note that starting from Eq. (30) and simply dropping the negative term we get,

As we noted earlier, $\left\|\hat{a}_{t}-\bar{a}_{t-1}\right\|_{*}\leq n\left\|x_{t}-x_{t-1}\right\|$ and so,

Further noting that $R_{1,\max}\leq\sqrt{\log(nT)}$ and $R_{2,\max}\leq\sqrt{\log(mT)}$ we conclude that

Noting that the constraints are all $H$-strongly smooth and that the objective is linear for the maximizing player, we can apply Lemma 4 to the optimization problem with $\mathcal{R}_{1}(\cdot)=\frac{1}{2}\left\|\cdot\right\|_{2}^{2}$ and $\mathcal{R}_{2}$ the entropy function to obtain that

(Strictly speaking we have used a version of Lemma 4 where the first term coming from (12) in Lemma 1 is kept as a linear term.) Here, $\mathbf{G}(f)$ is the vector of the values of the constraints for $f$. We then write

where we used the fact that each $\|\nabla G_{i}(f)\|\leq 1$. Combining, we get an upper bound of

Picking $\beta\geq 0$ such that $\tfrac{1}{\eta}-H\geq\beta\geq\eta^{\prime}$ we get an upper bound of

Of course, for this choice to be possible we need to pick $\eta$ and $\eta^{\prime}$ such that $\frac{1}{\eta}-H\geq\eta^{\prime}$. Therefore, picking $\eta^{\prime}=\frac{1}{\eta}-H$ and $\eta\leq 1/H$ we obtain

Now since $T$ is such that $T\geq\frac{1}{\epsilon}\operatorname*{\vphantom{p}inf}_{\eta\leq H^{-1}}\left\{\frac{B^{2}}{\eta}+\frac{\eta\log d}{1-\eta H}\right\}$ we can conclude that

Observe that for an optimal solution $f^{*}\in\mathcal{G}$ to the original optimization problem (10) we have that $f^{*}\in\mathcal{F}$ and $\forall i,G_{i}(f^{*})\leq 1$. Thus,

We conclude that $\bar{f}_{T}\in\mathcal{F}$ is a solution that attains the optimum value $F^{*}$ and almost satisfies the constraints. Now we have from the lemma statement that $f_{0}\in\mathcal{G}$ is such that $c^{\top}f_{0}\geq 0$ and for every $i\in[d]$, $G_{i}(f_{0})\leq 1-\gamma$. Hence by convexity of $G_{i}$, we have that for every $i\in[d]$,

Thus for $\alpha=\frac{\epsilon}{\epsilon+\gamma}$ and $\hat{f}_{T}=(1-\alpha)\bar{f}_{T}+\alpha f_{0}$ we can conclude that $\hat{f}_{T}\in\mathcal{G}$ and that all the constraints are satisfied. That is for every $i\in[d]$, $G_{i}(\hat{f}_{T})\leq 1$. Also note that

and, hence, $\hat{f}_{T}$ is an approximate maximizer, that is

Thus we obtain a $(1+\frac{\epsilon}{\gamma})$-optimal solution in the multiplicative sense which concludes the proof. ∎

As mentioned, for both players, the time to perform each step of the optimistic mirror descent in the Max Flow problem is $O(d)$. Now further note that Max Flow is a linear programming problem and so we are ready to apply Lemma 8. Specifically for $f_{0}$ we use the $\mathbf{0}$ flow which is in $\mathcal{G}$ (though not in $\mathcal{F}$) and note that for $f_{0}$ we have that $\gamma=1$. Applying Lemma 8 we get that number of iterations $T$ we need to reach an $\epsilon$ approximate solution is given by

Since each iteration has time complexity $O(d)$, the overall complexity of the algorithm is given by