Acceleration through Optimistic No-Regret Dynamics
Jun-Kun Wang Jacob Abernethy



On the feedback number of 3-uniform hypergraph
    Zhuo Diao ^aCorresponding author. E-mail: diaozhuo@amss.ac.cn  Zhongzheng Tang ^b,c,d

    
 ^a School of Statistics and Mathematics, Central University of Finance and Economics
Beijing 100081, China

^b Academy of Mathematics and Systems Science, Chinese Academy of Sciences

 Beijing 100190, China

 ^c School of Mathematical Sciences, University of Chinese Academy of Sciences

 Beijing 10049, China

 ^d Department of Computer Science, City University of Hong Kong

 Hong Kong, China 

==================================================================================================================================================================================================================================================================================================================================================================================================================




We consider the problem of minimizing a smooth convex function by reducing the optimization to computing the Nash equilibrium of a particular zero-sum convex-concave game. Zero-sum games can be solved using online learning dynamics, where a classical technique involves simulating two no-regret algorithms that play against each other and, after T rounds, the average iterate is guaranteed to solve the original optimization problem with error decaying as O(log T/T).
In this paper we show that the technique can be enhanced to a rate of O(1/T^2) by extending recent work <cit.> that leverages optimistic learning to speed up equilibrium computation.
The resulting optimization algorithm derived from this analysis coincides exactly with the well-known <cit.> method, and indeed the same story allows us to recover several variants of the Nesterov's algorithm via small tweaks. We are also able to establish the accelerated linear rate for a function which is both strongly-convex and smooth. This methodology unifies a number of different iterative optimization methods: we show that the algorithm is precisely the non-optimistic variant of , and recent prior work already established a similar perspective on <cit.>.




§ INTRODUCTION


One of the most successful and broadly useful tools recently developed within the machine learning literature is the no-regret framework, and in particular online convex optimization (OCO) <cit.>. In the standard OCO setup, a learner is presented with a sequence of (convex) loss functions ℓ_1(·), ℓ_2(·), …, and must make a sequence of decisions x_1, x_2, … from some set  in an online fashion, and observes ℓ_t after only having committed to x_t. Assuming the sequence {ℓ_t } is chosen by an adversary, the learner aims is to minimize the average regret R̅_T := 1/T( ∑_t=1^T ℓ_t(x_t) - min_x ∈∑_t=1^T ℓ_t(x) ) against any such loss functions. Many simple algorithms have been developed for OCO problems—including , , , etc.—and these algorithms exhibit regret guarantees that are strong even against adversarial opponents. Under very weak conditions one can achieve a regret rate of R̅_T = O(1/√(T)), or even R̅_T = O(log T/T) with required curvature on ℓ_t.

One can apply online learning tools to several problems, but perhaps the simplest is to find the approximate minimum of a convex function _x ∈ f(x). With a simple reduction we set ℓ_t = f, and it is easy to show that, via Jensen's inequality,  the average iterate x̅_T := x_1 + … + x_T/T satisfies

    f(x̅_T) ≤1/T∑_t=1^T f(x_t) = 1/T∑_t=1^T ℓ_t(x_t) ≤min_x ∈1/T∑_t=1^T ℓ_t(x) + R̅_T = min_x ∈ f(x) + R̅_T

hence R̅_T upper bounds the approximation error. But this reduction, while simple and natural, is quite limited. For example, we know that when f(·) is smooth, more sophisticated algorithms such as and achieve convergence rates of O(1/T), whereas the now-famous algorithm achieves a rate of O(1/T^2). The fast rate shown by Nesterov was quite surprising at the time, and many researchers to this day find the result quite puzzling. There has been a great deal of work aimed at providing a more natural explanation of acceleration, with a more intuitive convergence proof <cit.>. This is indeed one of the main topics of the present work, and we will soon return to this discussion.

Another application of the no-regret framework is the solution of so-called saddle-point problems, which are equivalently referred to as Nash equilibria for zero-sum games. Given a function g(x,y) which is convex in x and concave in y (often called a payoff function),
define V^*=inf_x ∈sup_y g(x,y). An ϵ-equilibrium of g(·, ·) is a pair x̂, ŷ such that such that

    V^* - ϵ≤inf_x ∈ g(x, ŷ)  ≤ V^* ≤sup_y g(x̂, y) ≤ V^* + ϵ.


 an ϵ equilibrium of g(·, ·) is a pair x̂, ŷ such that

    sup_y g(x̂, y) - ϵ≤ g(x̂, ŷ) ≤inf_x g(x, ŷ) + ϵ.

Can we say this instead? 
Define V^*=inf_x sup_y g(x,y). An ϵ equilibrium of g(·, ·) is a pair x̂, ŷ such that such that
V^* - ϵ≤inf_x g(x, ŷ) + ϵ≤ V^* ≤sup_y g(x̂, y) ≤ V^* + ϵ.
Reason:  Then, in fenchel game, sup_y g(x̂, y ) = sup_y⟨x̂, y ⟩ - f^*(y) = f(x̂) and V^* = min_x f(x). So, from the last inequality of the sandwich-like definition, we get f(x̂) ≤min_x f(x) + ϵ. I think below-average readers may have difficulty in seeing the connection (e.g why x̂ is an ϵ-optimal solution to the offline problem. We should explicitly say this either in the introduction here or section 2.2


One can find an approximate saddle point of the game with the following setup:  implement a no-regret learning algorithm for both the x and y players simultaneously, after observing the actions { x_t, y_t }_t=1… T return the time-averaged iterates (x̂, ŷ) = (x_1 + … + x_T/T, y_1 + … + y_T/T). 

A simple proof shows that (x̂, ŷ) is an approximate equilibrium, with approximation bounded by the average regret of both players (see Theorem <ref>). In the case where the function g(·, ·) is biaffine, the no-regret reduction guarantees a rate of O(1/√(T)), and it was assumed by many researchers this was the fastest possible using this framework. But one of the most surprising online learning results to emerge in recent years established that no-regret dynamics can obtain an even faster rate of O(1/T). Relying on tools developed by <cit.>, this fact was first proved by <cit.> and extended by <cit.>. The new ingredient in this recipe is the use of optimistic learning algorithms, where the learner seeks to benefit from the predictability of slowly-changing inputs {ℓ_t }.

We will consider solving the classical convex optimization problem min_x f(x), for smooth functions f, by instead solving an associated saddle-point problem which we call the Fenchel Game.
Specifically, we consider that the payoff function g of the game to be

    g(x,y) = ⟨ x, y ⟩ - f^*(y).

where f^*(·) is the fenchel conjugate of f(·). This is an appropriate choice of payoff function since, 
V^* = min_x f(x) and 
sup_y g(x̂, y ) = sup_y⟨x̂, y ⟩ - f^*(y) = f(x̂).
Therefore, by the definition of an ϵ-equilibrium, we have that
 
  If (x̂, ŷ) is an ϵ-equilibrium of the Fenchel Game (<ref>), then f(x̂) - min_x f(x) ≤ϵ.




as is easy to show, ϵ-equilibrium of this game provides an ϵ-optimal minimizer of f(·). 
I think below-average readers may have trouble in seeing why x̅ from the game satisfies
 f(x̅) ≤min_x f(x) + ϵ.
It is better for us to explicitly draw the connection between the game and the offline optimization so that below-average readers can fully appreciate the value.

One can imagine computing the equilibrium of the Fenchel game using no-regret dynamics, and indeed this was the result of recent work <cit.> establishing the algorithm as precisely an instance of two competing learning algorithms. 

In the present work we will take this approach even further. 

  
  * We show that, by considering a notion of weighted regret, we can compute equilibria in the Fenchel game at a rate of O(1/T^2) using no-regret dynamics where the only required condition is that f is smooth. This improves upon recent work <cit.> on a faster method, which required strong convexity of f (see Appendix <ref>).
  
  * We show that the secret sauce for obtaining the fast rate is precisely the use of an optimistic no-regret algorithm, <cit.>, combined with appropriate weighting scheme.
  
  * We show that, when viewed simply as an optimization algorithm, this method is identically the original method. In addition, we recover several variants of (see <cit.>) using small tweaks of the framework.
  
  * We show that if one simply plays without optimism, the resulting algorithm is precisely the . The latter is known to achieve a suboptimal rate in general, and our analysis sheds light on this difference.
  
  * Under the additional assumption that function f(·) is strongly convex, we show that an accelerated linear rate can also be obtained from the game framework.
  
  * Finally, we show that the same equilibrium framework can also be extended to composite 
  optimization and lead to a variant of Accelerated Proximal Method. 







Related works:
In recent years, there are growing interest in giving new interpretations of Nesterov’s accelerated algorithms. For example, <cit.> gives a unified analysis for some Nesterov’s accelerated algorithms
<cit.>, using the standard techniques and analysis in optimization literature.
<cit.> connects the design of accelerated algorithms with dynamical systems and control theory. <cit.> gives a geometric interpretation of the Nesterov’s method for unconstrained optimization, inspired by the ellipsoid method.
<cit.> studies the Nesterov’s methods and the method for quadratic non-strongly convex problems by analyzing the eigen-values of some linear dynamical systems.
<cit.> proposes a variant of accelerated algorithms by mixing the updates of gradient descent and mirror descent and showing the updates are complementary.
<cit.> connect the acceleration algorithms with differential equations.
In recent years there has emerged a lot of work where learning problems are treated as repeated games <cit.>, and many researchers have been studying the relationship between game dynamics and provable convergence rates <cit.>.

We would like to acknowledge George Lan for his excellent notes titled “Lectures on Optimization for Machine Learning” (unpublished). In parallel to the development of the results in this paper, we discovered that Lan had observed a similar connection between and repeated game playing (Chapter 3.4). A game interpretation was given by George Lan and Yi Zhou in Section 2.2 of <cit.>.



§ PRELIMINARIES
 



  
Convex functions and conjugates.
A function f on ^d is L-smooth w.r.t. a norm · if f is everywhere differentiable and
it has lipschitz continuous gradient
∇ f(u) - ∇ f(v) _* ≤ L  u - v,
where ·_* denotes the dual norm.
Throughout the paper, our goal will be to solve the problem of minimizing an L-smooth function f(·) over a convex set . 
We also assume that the optimal solution of x^* := _x ∈ f(x) has  finite norm.



For any convex function f, its Fenchel conjugate is f^*(y) := sup_x ∈dom(f) ⟨ x, y ⟩ - f(x). 
If a function f is convex, then its conjugate f^* is also convex.
Furthermore,
when the function f(·) is strictly convex,
we have that ∇ f(x) = _y⟨ x, y ⟩ - f^*(y). 

Assuming that f is closed and convex,
a nice property is called Fenchel-Young inequality:  f(x) + f^*(y) ≥⟨ x , y ⟩,
in which the equality holds when y ∈∂ f(x) or equivalently x ∈∂ f^*(y) 
(see e.g. <cit.>). 
We also have that
f is L-smooth w.r.t. · if and only if f^∗ is 1/L-strongly convex 
with respect to the dual norm ·_* (<cit.>).


Suppose we are given a differentiable function ϕ(·), then 
the Bregman divergence V_c(x) with respect to ϕ(·) at 
a point c is defined as V_c(x):= ϕ(x) - ⟨∇ϕ(c), x - c  ⟩  - ϕ(c). Let · be any norm on ^d. When we have that V_c(x) ≥σ/2 c - x ^2 for any x,c ∈dom(ϕ), we say that ϕ(·) is a σ-strongly convex function with respect to ·. Throughout the paper we assume that ϕ(·) is 1-strongly convex.








Assume that we have convex and compact sets ⊂^n and ⊂^m, which are the action spaces for the x-player and the y-player respectively. 
We also have a payoff function g: × for both players, in which g(·, y) is convex in its first argument for every y ∈, and g(x,·) is concave in its second argument for every x ∈. A pair (x̂, ŷ) ∈× is an ϵ-equilibrium for g(·, ·) if sup_y ∈ g(x̂, y) - inf_x ∈ g(x, ŷ) ≤ϵ.
In this paper, we consider that the payoff function g to be

    g(x,y) = ⟨ x, y ⟩ - f^*(y).

Note that the minimax value of the game satisfies V^* := min_xmax_y{⟨ x, y ⟩ - f^*(y)   } = min_x f(x) by the duality of Fenchel conjugation. This suggests that computing the equilbrium of this game is equivalent to solving the optimization min_x f(x). Indeed, for an approximate equilibrium we have the following.
 
  If (x̂, ŷ) is an ϵ-equilibrium of the Fenchel Game (<ref>), then f(x̂) - min_x ∈≤ϵ.

The statement is true almost by definition, as

    f(x̂) - min_x ∈ f(x) = sup_y g(x̂, y) - V^* ≤sup_y ∈ g(x̂, y) - inf_x ∈ g(x, ŷ),

and the right hand side defines the approximation ϵ.
We sometimes use inf, sometimes use min.
But the key result of the lemma is that we can reduce the optimization problem to finding an ϵ-equilibrium of the Fenchel Game.

Need to move these two sentences somewhere else The payoff function has been considered in <cit.> for designing and analyzing some existing and new variants of optimization methods <cit.>. In this paper, we go beyond method and propose a meta-algorithm that can generate several accelerated optimization algorithms for smooth convex problems. 





  
No-regret zero-sum game dynamics. Let us now consider the process of solving a zero-sum game via repeatedly play by a pair of online learning strategies. The sequential procedure is described in Algorithm <ref>. 



In this paper, we consider Fenchel game with weighted losses depicted in Algorithm <ref>, following the same setup as <cit.>. In this game, the y-player plays before the x-player plays
and the x-player sees what the y-player plays before choosing its action.
The y-player receives loss functions α_tℓ_t(·) in round t, in which ℓ_t(y):= f^*(y)- ⟨ x_t, y ⟩,
while the x-player see its loss functions α_t h_t(·) in round t, in which h_t(x):= ⟨ x, y_t ⟩ - f^*(y_t).
Consequently, we can define the weighted regret of the x and y players as

    y    :=    ∑_t=1^T  α_t  ℓ_t(y_t) - min_y∑_t=1^T  α_t  ℓ_t(y)
    x    :=    ∑_t=1^T  α_t  h_t(x_t) - ∑_t=1^T  α_t  h_t(x^*)


Notice that the x-player's regret is computed relative to x^* the minimizer of f(·), rather than the minimizer of ∑_t=1^T  α_t  h_t(·). Although slightly non-standard, this allows us to handle the unconstrained setting while Theorem <ref> still holds as desired.

At times when we want to refer to the regret on another sequence y_1', …, y_T' we may refer to this as (y_1', …, y_T').
We also denote A_t as the cumulative sum of the weights A_t:=∑_s=1^t α_s and the weighted average regret := /A_T.

Finally, for offline constrained optimization (i.e. min_x ∈ f(x)), we let the decision space of the benchmark/comparator in the weighted regret definition to be =; for offline unconstrained optimization, we let the decision space of the benchmark/comparator to be a norm ball that contains the optimum solution of the offline problem (i.e. contains min_x ∈^n f(x)), which means that  of the comparator is a norm ball. We let = ^d be unconstrained.
 <cit.>
  Assume a T-length sequence  are given. Suppose in Algorithm <ref> the online learning algorithms ^x and ^y have the -weighted average regret x and y respectively. Then the output  (x̅_T,y̅_T) is an ϵ-equilibrium for g(·, ·), with
ϵ = x + y.
 


Actually, I think it is here for addressing the concern:  If the offline optimization problem is a constrained one. We let the comparator in =. If it is an unconstrained optimization problem, we let the comparator in  be a ball that contained the min_x f(x) and min_x R(x) where R(x)
is the strongly convex function used in . 
It seems that the analysis of MirrorDescent does not have such concern.




§ AN ACCELERATED SOLUTION TO THE FENCHEL GAME VIA OPTIMISM
 

We are going to analyze more closely the use of Algorithm <ref>, with the help of Theorem <ref>, to establish a fast method to compute an approximate equilibrium of the Fenchel Game. In particular, we will establish an approximation factor of O(1/T^2) after T iterations, and we recall that this leads to a O(1/T^2) algorithm for our primary goal of solving min_x ∈ f(x).












 §.§ Analysis of the weighted regret of the y-player (i.e. the gradient player)




Recall the y-player receives loss functions α_tℓ_t(·) in round t, in which ℓ_t(y):= - ⟨ x_t, y ⟩ + f^*(y).
But, before that, let us introducing some notations.
We denote L_1:t(y) = ∑_s=1^t α_s ℓ_s(y) as the cumulative loss functions up to (and including) t. We write x̅_t := ∑_s=1^t α_s x_s/A_t 
and x̃_t := ∑_s=1^t-1α_s x_s + α_t x_t /A_t. 

The update of Be-the-Leader is

    y_t^* = _y  L_1:t(y) = 
    _y∑_s=1^t α_s ( -x_s^⊤ y + f^*(x)) = ∇ f( x̅_t ).

The update of Optimisitc-FTL is

    ỹ_t = _y  L_1:t-1(y) + m_t(y)
    = _y∑_s=1^t-1α_s ( -x_s^⊤ y + f^*(y)) + α_t ( -x_t-1^⊤ y + f^*(y)) 
        = ∇ f( x̃_t ).













A very natural online learning algorithm is , which always plays the point with the lowest (weighted) historical loss

    _t     :=    _y {∑_s=1^t-1α_s ℓ_s(y) }.

is known to not perform well against arbitrary loss functions, but for strongly convex ℓ_t(·) one can prove an O(log T/T) regret bound in the unweighted case. For the time being, we shall focus on a slightly different algorithm that utilizes “optimism” in selecting the next action:



    _t     :=    _y {α_t ℓ_t-1(y) +  ∑_s=1^t-1α_s ℓ_s(y)}.

This procedure can be viewed as an optimistic variant of since the algorithm is effectively making a bet that, while ℓ_t(·) has not yet been observed, it is likely to be quite similar to ℓ_t-1. Within the online learning community, the origins of this trick go back to <cit.>, although their algorithm was described in terms of a 2-step descent method. This was later expanded by <cit.> who coined the term optimistic mirror descent (OMD), and who showed that the proposed procedure can accelerate zero-sum game dynamics when both players utilize OMD. , defined as a “batch” procedure, was first presented in <cit.> and many of the tools of the present paper follow directly from that work.

For convenience, we'll define δ_t(y) := α_t (ℓ_t(y) - ℓ_t-1(y)). Intuitively, the regret will be small if the functions δ_t are not too big. This is formalized in the following lemma.
 
	For an arbitrary sequence {α_t, ℓ_t }_t=1… T, the regret of satisfies
y(_1, …, _T)  ≤∑_t=1^T δ_t(_t) - δ_t(_t+1).


	Let L_t(y) := ∑_s=1^tα_s ℓ_s(y) and also L̃_t(y) := α_t ℓ_t-1(y) +  ∑_s=1^t-1α_s ℓ_s(y).


(_1:T) ∑_t=1^T  α_t  ℓ_t(_t) - L_T(_T+1)
=   ∑_t=1^Tα_t  ℓ_t(_t) - L̃_T(_T+1) - δ_T(_T+1) ≤∑_t=1^Tα_t  ℓ_t(_t) - L̃_T(_T) - δ_T(_T+1) 
    =   ∑_t=1^T-1α_t  ℓ_t(_t) - L_T-1(_T) + δ_T(_T) - δ_T(_T+1)  
   ≤∑_t=1^T-1α_t  ℓ_t(_t) - L_T-1(_T) + δ_T(_T) - δ_T(_T+1)
    = (_1:T-1) + δ_T(_T) - δ_T(_T+1).(_1:T)     :=    ∑_t=1^T  α_t  ℓ_t(_t) - L_T(_T+1) =  ∑_t=1^Tα_t  ℓ_t(_t) - L̃_T(_T+1) - δ_T(_T+1) 
       ≤   ∑_t=1^Tα_t  ℓ_t(_t) - L̃_T(_T) - δ_T(_T+1) 
        =    ∑_t=1^T-1α_t  ℓ_t(_t) - L_T-1(_T) + δ_T(_T) - δ_T(_T+1)  
       ≤   ∑_t=1^T-1α_t  ℓ_t(_t) - L_T-1(_T) + δ_T(_T) - δ_T(_T+1)
        =    (_1:T-1) + δ_T(_T) - δ_T(_T+1).

	The bound follows by induction onT. 
  
  


The result from Lemma <ref> is generic, and would hold for any online learning problem. But for the Fenchel game, we have a very specific sequence of loss functions,ℓ_t(y) := -g(x_t, y) = f^*(y) - ⟨x_t, y ⟩. With this in mind, let us further analyze the regret of theyplayer.

For the time being, let us assume that the sequence ofx_t's is arbitrary. We define

    _t := 1/A_t∑_s=1^t α_s x_s      and     _t := 1/A_t(α_t x_t-1 + ∑_s=1^t-1α_s x_s ).

It is critical that we have two parallel sequences of iterate averages for thex-player. Our final algorithm will output_T, whereas the Fenchel game dynamics will involve computing∇fat the reweighted averages_tfor eacht=1, …, T.

To prove the key regret bound for they-player, we first need to state some simple technical facts.

    _t+1    =    _y ∑_s=1^t α_s ( f^*(y) - ⟨ x_s, y ⟩) = _y  ⟨_t, y ⟩ - f^*(y) = ∇ f(_t) 
    _t     =    ∇ f(_t)                  (following same reasoning as above), 
    _t - _t     =    α_t/A_t(x_t-1 - x_t).

Equations <ref> and <ref> follow from elementary properties of Fenchel conjugation and the Legendre transform <cit.>. Equation <ref> follows from a simple algebraic calculation.


Suppose f(·) is a convex function that is L-smooth with respect to the the norm · with dual norm ·_*. Let x_1, …, x_T be an arbitrary sequence of points. Then, we have

    y(_1, …, _T) ≤ L ∑_t=1^T α_t^2/A_tx_t-1 - x_t ^2.

 Following Lemma <ref>, and noting that here we have δ_t(y) = α_t ⟨ x_t-1 - x_t, y ⟩, we have
 
 
 
 
 
 
 
    ∑_t=1^Tα_t ℓ_t(_t) - α_t ℓ_t(y^*) 
               ≤   ∑_t=1^T δ_t(_t) - δ_t(_t+1) = ∑_t=1^T α_t ⟨ x_t-1 - x_t, _t - _t+1⟩
    (Eqns. <ref>, <ref>)        =    ∑_t=1^T α_t ⟨ x_t-1 - x_t, ∇ f(_t) - ∇ f(_t) ⟩
    (Hölder's Ineq.)       ≤   ∑_t=1^T α_t  x_t-1 - x_t∇ f(_t) - ∇ f(_t) _* 
    (L-smoothness of f)       ≤      L ∑_t=1^T α_t  x_t-1 - x_t_t - _t 
    (Eqn. <ref>)        =      L ∑_t=1^T α_t^2/A_t x_t-1 - x_tx_t-1 - x_t

    ∑_t=1^Tα_t ℓ_t(_t) - α_t ℓ_t(y^*) 
          ≤   ∑_t=1^T δ_t(_t) - δ_t(_t+1) 
        =    ∑_t=1^T α_t ⟨ x_t-1 - x_t, _t - _t+1⟩
    (Eqns. <ref>, <ref>)        =    ∑_t=1^T α_t ⟨ x_t-1 - x_t, ∇ f(_t) - ∇ f(_t) ⟩
    (Hölder's Ineq.)       ≤   ∑_t=1^T α_t  x_t-1 - x_t∇ f(_t) - ∇ f(_t) _* 
    (L-smoothness of f)       ≤      L ∑_t=1^T α_t  x_t-1 - x_t_t - _t 
    (Eqn. <ref>)        =      L ∑_t=1^T α_t^2/A_t x_t-1 - x_tx_t - x_t-1

as desired.


 §.§ Now this is Jun-Kun's version.


For the y-player, it receives loss functions α_tℓ_t(·) in round t, in which ℓ_t(y):= - ⟨ x, y ⟩ + f^*(y).
The loss functions α_tℓ_t(·) are α_t/L-strongly convex,
	since the function f(·) is L smooth, which implies that f^*(·) is 1/L-strongly convex.
Now let us analyze 	y := ∑_t=1^Tα_t ℓ_t(y_t) - α_t ℓ_t(y^*).

 
Suppose f(·) is a L-smooth convex function. Let α_t:=t. Then, we have

    y  := ∑_t=1^Tα_t ℓ_t(y_t) - α_t ℓ_t(y^*) ≤α_t^2/A_t 2 L x_t-1 - x_t ^2.

	
	The y-player chooses y_t based on Optimistic-FTL:
	y_t = _y ∈∑_s=1^t-1α_s ℓ_s(y) + m_t(y),
	where m_t(y) = α_tℓ_t-1(y).
	To analyze the regret of the y-player, let us first denote 
	the update of the standard  as
    z_t = _y∑_s=1^t-1α_s ℓ_s(y).

	Denote y^* := _y ∈∑_t=1^T  α_t  ℓ_t(y).[The following analysis actually holds for any y^*∈.]
	Now we are going to analyze the -weighted regret of the y-player, which is 

	
    y    := ∑_t=1^Tα_t ℓ_t(y_t) - α_t ℓ_t(y^*)
      = ∑_t=1^Tα_t ℓ_t(y_t)  - α_t ℓ_t(z_t+1) - m_t(y_t) + m_t(z_t+1)
    	
        + ∑_t=1^T m_t(y_t) - m_t(z_t+1)
    	  + ∑_t=1^T α_t ℓ_t(z_t+1) - α_t ℓ_t(y^*).
    	
       ≤∑_t=1^Tα_t ∇ℓ_t(y_t) - ∇ m_t(z_t+1) y_t - z_t+1
    	+ ∑_t=1^T m_t(y_t) - m_t(z_t+1)
    	
             + ∑_t=1^T α_t ℓ_t(z_t+1) - α_t ℓ_t(y^*) - 2 α_t/L y_t - z_t+1^2,

	where the last inequality uses strong convexity of ℓ_t(·) so that 
	α_t ℓ_t(y_t)  - α_t ℓ_t(z_t+1) ≤α_t ∇ℓ_t(y_t)y_t- z_t+1 - α_t/L y_t - z_t+1^2
	and that 
	- m_t(y_t) + m_t(z_t+1)
	≤∇ m_t(z_t+1)z_t+1-y_t - α_t/L y_t - z_t+1^2.
	Using the fact that m_t(·) := α_tℓ_t-1(·),
	each term in the first sum in (<ref>) is actually
	
    ⟨α_t ∇ℓ_t(y_t) - ∇ m_t(z_t+1), y_t - z_t+1⟩    = α_t ⟨∇ℓ_t(y_t) - ∇ℓ_t-1(z_t+1) , y_t - z_t+1⟩
        = α_t ⟨ - x_t + ∇ f^*(y_t) + x_t-1 - ∇ f^*(z_t+1) , y_t - z_t+1⟩


Let us denote vector '_1:t-1 such that  α'_s = α_s for s = 1,...,t-2 and α'_t-1 = α_t-1 + α_t.
Notice

    y_t := _y ∑_s=1^t-1α_s ( -x_s^⊤ y + f^*(y)) + α_t ( -x_t-1^⊤ y + f^*(y))   = ∇ f( x̅_'_1:t-1).
 
Therefore, by Fenchel-Young inequality, we have 
	
    ∇ f^*(y_t) = x̅_'_1:t-1,

	where x̅_'_1:t-1 is the '-weighted average of x_1, …, x_t-1.
Furthermore, since

    z_t+1 = _y∑_s=1^tα_s ℓ_s(y)
    = _y ∑_s=1^t α_s ( -x_s^⊤ y + f^*(x)) = ∇ f(x̅__1:t),

where x̅__1:t is the -weighted average of x_1, …, x_t,
by Fenchel-Young inequality again, we have

    ∇ f^*(z_t+1) = x̅__1:t.

Using (<ref>) and (<ref>),  (<ref>)
becomes

    ⟨α_t ∇ℓ_t(y_t) - ∇ m_t(z_t+1), y_t - z_t+1⟩
    	 = α_t ⟨ - x_t + ∇ f^*(y_t) + x_t-1 - ∇ f^*(z_t+1) , y_t - z_t+1⟩
        = α_t ⟨ - x_t + x̅_'_1:t-1 + x_t-1 - x̅__1:t , y_t - z_t+1⟩
       ≤α_t (  x_t - x_t-1 y_t - z_t+1_* + x̅_'_1:t-1 - x̅__1:t y_t - z_t+1_* ).

Let us analyze x̅_'_1:t-1 - x̅__1:t in (<ref>).
	
    x̅__1:t -  x̅_'_1:t-1^2
    	= 1/A_t^2∑_s=1^t α_s x_s - ∑_s=1^t-1α_s' x_s  ^2 = 1/A_t^2α_t-1 x_t-1 + α_t x_t - α'_t-1 x_t-1^2
    	
        = 1/A_t^2α_t ( x_t-1 - x_t ) ^2
    	 = α_t  /A_t^2 x_t-1 - x_t ^2.

Combining (<ref>), we have

    ⟨α_t ∇ℓ_t(y_t) - ∇ m_t(z_t+1), y_t - z_t+1⟩≤α_t ( 1 + α_t/A_t )  x_t-1 - x_t   y_t - z_t+1_*.
	
Now let us analyze 
y_t - z_t+1_*.
Notice we have
y_t = ∇ f( x̅_'_1:t-1) from (<ref>) and
z_t+1 = ∇ f(x̅__1:t) from (<ref>).
Thus,

    y_t- z_t+1^2_*  = ∇ f(x̅__1:t) -  ∇ f(x̅_'_1:t-1) ^2_* 
    	≤ L^2 x̅__1:t -  x̅_'_1:t-1^2
    
       	= L^2/A_t^2∑_s=1^t α_s x_s - ∑_s=1^t-1α_s' x_s  ^2 
    
        = L^2/A_t^2α_t-1 x_t-1 + α_t x_t - α'_t-1 x_t-1^2
    	 = L^2/A_t^2α_t ( x_t-1 - x_t ) ^2
    	 = α_t L /A_t^2 x_t-1 - x_t ^2.

Combining (<ref>) and (<ref>), 

    ⟨α_t ∇ℓ_t(y_t) - ∇ m_t(z_t+1), y_t - z_t+1⟩≤α_t ( 1 + α_t/A_t )  x_t-1 - x_t   y_t - z_t+1_*,
    
       ≤α_t ( 1 + α_t/A_t ) ( α_t L/A_t)  x_t-1 - x_t ^2
     =  α_t^2/A_t ( 1+ α_t/A_t ) L x_t-1 - x_t ^2
    ≤α_t^2/A_t 2 L x_t-1 - x_t ^2.
	
That is, we have shown that the first sum in y (c.f. (<ref>)) is upper bounded by 
α_t^2/A_t 2 L x_t-1 - x_t ^2.
Lemma 15 in <cit.> shows that 
the other two sums in total is non-positive,
∑_t=1^T m_t(y_t) - m_t(z_t+1) + ∑_t=1^T α_t ℓ_t(z_t+1) - α_t ℓ_t(y^*) ≤ 0. For completness, we replicate the proof in the appendix. This concludes that
y≤α_t^2/A_t 2 L x_t-1 - x_t ^2.
We notice that a similar bound is given in <cit.> for the gradient player using 
, yet the above result is a stict improvement as the previous work relied on the additional assumption thatf(·)is strongly convex. The above lemma depends only on the fact thatfhas lipschitz gradients.



 §.§ Analysis of the weighted regret of the x-player


In the present section we are going to consider that thex-player uses 

 for updating its action, which is defined as follows. 



    x_t  :=  _x ∈α_t h_t(x) +  1/γ_t V_x_t-1(x) 
       =  _x ∈γ_t ⟨ x, α_t y_t ⟩  + V_x_t-1(x),

where we recall that the Bregman divergenceV_x(·)is with respect to a 1-strongly convex regularizationϕ. Also, we note that thex-player has an advantage in these game dynamics, sincex_tis chosen with knowledge ofy_tand hence has knowledge of the incoming lossh_t(·).








  Let the sequence of x_t's be chosen according to . Assume that the Bregman Divergence is uniformly bounded on , so that D = sup_t=1, …, T V_x_t(x^*), where x^* denotes the minimizer of f(·).
   Assume that the sequence {γ_t}_t=1,2,… is non-increasing. Then we have
x≤D/γ_T - ∑_t=1^T1/2 γ_t x_t-1 - x_t ^2.
The proof of this lemma is quite standard, and we postpone it to Appendix <ref>.
We also note that the benchmarkx^*is always within a finite norm ball by assumption. We given an alternative to this lemma in the appendix, whenγ_t = γis fixed, in which case we can instead use the more natural constantD = V_x_1(x^*).


 §.§ Analysis of the weighted regret of the x-player (i.e. the iterate player) (Option (B)) 
Move this elsewhere, to later in paper?

	
Recall the update of the x-player using BTRL is 
    x_t = _x ∈∑_t=1^T⟨ x_t , α_t y_t ⟩ + 1/η R(x).
Define, z = min_x ∈ R(x).
     Form <cit.>, it shows that  
    BTRL has regret
    [For completeness, we elaborate it in Appendix <ref>.]
    Regret:= ∑_t=1^T⟨ x_t - x^*, α_t y_t ⟩≤ R(x^*) - R(z)  - 1/2∑_t=1^T x_t - x_t-1^2/η.


 §.§ Convergence Rate of the Fenchel Game



Let us consider the output (_T, _T) of Algorithm <ref> under the following conditions: (a) the sequence {α_t} is positive but otherwise arbitrary (b) ^y is chosen , (c) ^x is  with any non-increasing positive sequence {γ_t}, and (d) we have a bound V_x_t(x^*) ≤ D for all t. Then the point _T satisfies

    f(_T) - min_x ∈ f(x)
      ≤1/A_T( D/γ_T 
        + ∑_t=1^T(α_t^2/A_t L - 1/2 γ_t)
              x_t-1 - x_t ^2    ).

  We have already done the hard work to prove this theorem. Lemma <ref> tells us we can bound the error of _T by the ϵ error of the approximate equilibrium (_T, _T). Theorem <ref> tells us that the pair (_T, _T) derived from Algorithm <ref> is controlled by the sum of averaged regrets of both players, 1/A_T(x + y). But we now have control over both of these two regret quantities, from Lemmas <ref> and <ref>. The right hand side of (<ref>) is the sum of these bounds.


Theorem <ref> is somewhat opaque without a specifying the sequence{α_t}. But what we now show is that the summation term vanishes when we can guarantee thatα_t^2/A_tremains constant! This is where we obtain the following fast rate.

  Following Theorem <ref> with α_t = t and for any non-increasing sequence γ_t satisfying 1/CL≤γ_t ≤1/4L for some constant C > 4, we have
f(_T) - min_x ∈ f(x) 
  ≤2 C L D/T^2.
  Observing A_t := t(t+1)/2, the choice of {α_t,γ_t} implies D/γ_t≤ cDL and Lα_t^2/A_t = 2Lt^2/t(t+1)≤ 2L ≤1/2 γ_t, which ensures that the summation term in (<ref>) is negative. The rest is simple algebra.

A straightforward choice for the learning rateγ_tis simple the constant sequenceγ_t = 1/4L. The corollary is stated with a changingγ_tin order to bring out a connection to the classical  in the following section.

Remark: It is worth dwelling on exactly how we obtained the above result. A less refined analysis of the  algorithm would have simply ignored the negative summation term in Lemma <ref>, and simply upper bounded this by 0. But the negative terms x_t - x_t-1 ^2in this sum happen to correspond exactly to the positive terms one obtains in the regret bound for they-player, but this is true only as a result of using the  algorithm. To obtain a cancellation of these terms, we need aγ_twhich is roughly constant, and hence we need to ensure thatα_t^2/A_t = O(1). The final bound, of course, is determined by the inverse quantity1/A_T, and a quick inspection reveals that the best choice ofα_t = θ(t). This is not the only choice that could work, and we conjecture that there are scenarios in which better bounds are achievable for differentα_ttuning. We show in Section <ref> that a linear rate is achievable whenf(·)is also strongly convex, and there we tuneα_tto grow exponentially intrather than linearly.


====================================================================================================


 §.§ Jun-kun old version

  Let α_t=t and that A_t=∑_s=1^t s =  t(t+1)/2.
The output (x̅_,y̅_) of Algorithm <ref> with x-player using MirrorDescent with non-decreasing γ_t≤1/4L is an
ϵ = O( L Θ/T^2 ) equilibrium,
where Θ is the upper bound of V_x_0(x^*).
Furthermore,
the output (x̅_,y̅_) of Algorithm <ref> with x-player using BTRL with η≤1/4L is an
ϵ = O( L (R(x^*) - R(z) )  /T^2 ) equilibrium,
where z = min_x ∈ R(x).




By combining (<ref>) and (<ref>)
we have that

    x + y/A_T 
    = 1/γ_1 V_x_0(x^*) + ∑_t=1^T (α_t^2/A_t L - 1/2 γ_t  )  x_t-1 - x_t ^2  /A_T
    = 1/γ_1 V_x_0(x^*) + ∑_t=1^T (t^2/t(t+1) 2 L - 1/2 γ_t  )  x_t-1 - x_t ^2 /A_T
       ≤ 4L V_x_0(x^*) /A_T
    = O( L V_x_0(x^*)/T^2 ) = O( L Θ/T^2 ),

where the last inequality is because γ_t≤1/4L so that the distance terms cancel out.

Now we prove the second statement.
By combining (<ref>) and (<ref>),
we get that

    x + y/A_T 
    =  R(x^*) - R(z)/η + ∑_t=1^T (α_t^2/A_t L - 1/2η )  x_t-1 - x_t ^2  /A_T≤ O( L (R(x^*) - R(z) )  /T^2 ),

where the last inequality is because η≤1/4L so that the distance terms cancel out.
Remark:
From the proof of Theorem <ref>, we can see that does α_t not need to be t.
As long as we choose non-decreasing {γ_t}, η, and {α_t} so that they satisfy A_T = O(T^2), α_t^2/A_t L - 1/2 γ_t≤ 0  
and α_t^2/A_t L - 1/2η≤ 0 for each t, we get O(1/T^2) rate.
=======================================================================================================


§ NESTEROV’S METHODS ARE INSTANCES OF OUR ACCELERATED SOLUTION TO THE GAME


Starting from 1983, Nesterov has proposed three accelerated methods for smooth convex problems
(i.e. <cit.>. In this section, we show that our accelerated algorithm to the Fenchel game can generate all his methods with some simple tweaks.



 §.§ Recovering Nesterov’s (1983) method for unconstrained smooth convex problems <cit.>


In this subsection, we assume that the x-player’s action space is unconstrained.
That is,= ^n. 
Consider the following algorithm.

 
Let α_t=t. 
Assume = ^n.  
Algorithm <ref> is actually the case
the x-player uses MirrorDescent. 

Therefore, x̅_T is an O(1/T^2)-approximate optimal solution of min_x f(x)
by Theorem <ref> and Corollary <ref>.

For the unconstrained case, we can let the distance generating function of the Bregman divergence to be the squared of L2 norm, i.e.
ϕ(x):=1/2 x ^2_2.
Then, the update becomes x_t = _xγ_t ⟨ x, α_t y_t ⟩  + V_x_t-1(x) = _xγ_t ⟨ x, α_t y_t ⟩  + 1/2 x ^2_2 - ⟨ x_t-1, x - x_t-1⟩ - 1/2 x_t-1^2_2. 
Differentiating the objective w.r.t x and setting it to zero, one will get
x_t = x_t-1 - γ_t α_t y_t.

For the unconstrained case,
BTRL with the squared of L2 norm as the regularization term (i.e. R(x)=1/2x^2_2) is exactly equivalent to online gradient descent.
To see this, for the BTRL objective x_t = _x ∑_s=1^t ⟨ x , α_s y_s ⟩ + 1/2 η x ^2_2, differentiating the objective w.r.t x and setting it to zero, one will get
x_t = - η∑_s=1^tα_s y_s,
which implies that x_t = x_t-1 - ηα_t y_t.


Having shown that Algorithm <ref> is actually our accelerated algorithm to the
Fenchel game.
We are going to show that Algorithm <ref> 
has a direct correspondence with Nesterov’s first acceleration method (Algorithm <ref>) <cit.> (see also <cit.>).




To see the equivalence, let us re-writex̅_t := 1/A_t ∑_s=1^t α_s x_sof Algorithm <ref>.

    x̅_t = A_t-1x̅_t-1 + α_t x_t    /A_t
                = A_t-1x̅_t-1 + α_t ( x_t-1 - γ_t α_t ∇ f( _t) ) /A_t
                    = A_t-1x̅_t-1 + α_t (  A_t-1x̅_t-1 - A_t-2x̅_t-2/α_t-1 - γ_t α_t ∇ f( _t) )/A_t
                 = x̅_t-1 ( A_t-1/A_t + α_t (α_t-1 + A_t-2 ) / A_t α_t-1   ) - x̅_t-2 ( α_t A_t-2/ A_t α_t-1   ) - γ_t α_t^2/A_t∇ f( _t )
    
                  = x̅_t-1 - γ_t α_t^2/A_t∇ f(_t) + ( α_t A_t-2/ A_t α_t-1   ) (x̅_t-1 -  x̅_t-2 ) 
    
        = x̅_t-1 - 1/4L∇ f(_t) + ( t-2 / t+1    ) (x̅_t-1 -  x̅_t-2 ) ,

whereα_t=tandγ_t= (t+1)/t 1/8L.
 
Algorithm <ref> with θ=1/4L is equivalent to Algorithm <ref> with  γ_t = (t+1)/t1/8L in the sense that they generate equivalent sequences of iterates:

    for all  t=1,2,…,T,          w_t = _t    and    z_t-1 = _t.






First, let us check the base case to see if w_1= x̅_1. We have that w_1 = z_0 -θ∇ f(z_0) from line 3 of Algorithm <ref>,
while x̅_1 = x̅_0 - 1/4L∇ f(_1) in (<ref>).
Thus, if the initialization is the same: w_0=z_0=x_0=x̅_0 = _1, then w_1=x̅_1.

Now assume that w_t-1 = x̅_t-1 holds for a t≥ 2.
Then, from the expression of line 4 that 
z_t-1 = w_t-1 + t-2/t+1 (w_t-1 - w_t-2),
we get z_t-1 = x̅_t-1 + t-2/t+1 (x̅_t-1 - x̅_t-2).
Let us analyze that the r.h.s of the equality.
The coefficient of x_t-1 in 
x̅_t-1 + t-2/t+1 (x̅_t-1 - x̅_t-2)
is (t-1) + t-2/t+1(t-1)/A_t-1 = 2(1+t-2/t+1)/t = 2 (2t-1)/t(t+1), while the coefficient of each x_τ for any τ≤ t-2 in x̅_t-1 + t-2/t+1 (x̅_t-1 - x̅_t-2)
is ( 1 + t-2/t+1 ) τ/A_t-1 - t-2/t+1τ/A_t-2
= {2(2t-1)/(t-1)t(t+1) - 2/(t+1)(t-1)}×τ 
= {2/(t-1)(t+1)( 2t-1/t  - 1 )   }×τ
=  2 τ/t(t+1).
Yet, 
the coefficient of x_t-1 in x_t is t+(t-1)/A_t = 2 (2t-1)/t(t+1)
and the coefficient of x_τ in x_t is τ/A_t = 2 τ/t(t+1) for any τ≤ t-2. Thus, z_t-1= x_t.
Now observe that if z_t-1= x_t, we get w_t = x̅_t.
To see this,
substituting  z_t-1 = w_t-1 + t-2/t+1 (w_t-1 - w_t-2) of line 4
into line 3,
we get 
w_t  = w_t-1 + t-2/t+1 (w_t-1 - w_t-2) - θ∇ f(z_t-1).
By using z_t-1= x_t and w_t-1 = x̅_t-1, we further get w_t = x̅_t-1 + t-2/t+1 (x̅_t-1 - x̅_t-2) - θ∇ f(x_t) = x̅_t.
We can repeat the argument to show that the correspondence holds for any t,
which establishes the equivalency.

Notice that the choice of decreasing sequence {γ_t} here can still make the distance terms in 
(<ref>) cancel out. So, we get O(1/T^2) rate by the guarantee.


Let us switch to comparing the update of Algorithm <ref>, which is (<ref>),
with the update of the  algorithm.
We see that (<ref>) has the so called momentum term (i.e. has a(x̅_t-1 -  x̅_t-2) term). But, the difference is that the gradient is evaluated at_t = 1/A_t(α_t x_t-1 + ∑_s=1^t-1 α_s x_s ), notx̅_t-1 = 1/A_t-1 ∑_s=1^t-1 α_s x_s, which is the consequence that the y-player plays .
To elaborate, let us consider a scenario (shown in Algorithm <ref>) such that they-player plays  instead of .



Following what we did in (<ref>), we can rewritex̅_tof Algorithm <ref> as

    x̅_t =x̅_t-1 - γ_t α_t^2/A_t∇ f(x̅_t-1) + (x̅_t-1 -  x̅_t-2 ) ( α_t A_t-2/ A_t α_t-1   ),

by observing that (<ref>) still holds except that∇f( _t )is changed to∇f(x̅_t-1)as the y-player uses  now,
which give us the update of the Heavy Ball algorithm as (<ref>). Moreover, by the regret analysis,
we have the following theorem. The proof is in Appendix <ref>.
 
Let α_t=t. Assume = ^n. Also, let γ_t =O(1/L).
The output x̅_T of Algorithm <ref> is an O(1/T)-approximate optimal solution of min_x f(x).

To analyze the guarantee of x̅_T of Algorithm <ref>, we use the following lemma about  for strongly convex loss functions.

Let ℓ_1, . . . ,ℓ_T be a sequence of functions such that for all t ∈ [T], ℓ_t is σ_t-strongly convex. Assume that  runs on this sequence and for each t ∈ [T], let θ_t be in ∇ℓ_t(y_t). Then,
∑_t=1^T ℓ_t(y_t) - min_x ∑_t=1^T ℓ_t(y) ≤1/2∑_t=1^T θ_t^2/∑_τ=1^tσ_τ
Observe that the y-player plays  on the loss function sequence
α_t ℓ_t(y) := α_t ( - ⟨ x_t, y ⟩ + f^*(y) ),
whose strong convexity parameter is α_t/L
(due to f^*(y) is 1/L-strongly convex by duality).
Also,
 ∇ℓ_t(y_t)  = - x_t  + ∇ f^*(y_t) = - x_t  + x̅_t-1,
 where the last inequality is due to that if 
y_t = _y ⟨1/A_t-1∑_s=1^t-1α_s x_s, y ⟩ - f^*(y) = ∇ f(_t-1), then x̅_t-1 = ∇ f^*(y_t) by duality.
So, we have 
yLemma <ref>≤1/ 2 A_T∑_t=1^T α_t^2 x̅_t-1 - x_t  ^2 /∑_τ=1^t α_τ (1/L) = 
    1/2 A_T∑_t=1^T α_t^2 L x̅_t-1 - x_t  ^2 / A_t =
    O( ∑_τ=1^T  L x̅_t-1 - x_t  ^2 /A_T).
For the x-player, it is an instance of MirrorDescent, so  
x := 1/A_T∑_t=1^T⟨ x_t - x^*,  α_t y_t⟩≤1/γ_1 V_x_0(x^*) - ∑_t=1^T1/2 γ_t x_t-1 - x_t ^2 /A_T
Therefore, x̅_T of Algorithm <ref> is an x + y = O(L ∑_t=1^T (x̅_t-1 - x_t  ^2 - x_t - x_t-1^2  )/A_T) -approximate optimal solution.
Since the distance terms may not cancel out, one may only bound the differences of the distance terms by a constant, which leads to the non-accelerated O(1/T) rate.


To conclude, by comparing Algorithm <ref> and Algorithm <ref>,
we see that Nesterov‘s (1983) method enjoysO(1/T^2)rate since its adopts, while the  algorithm which adoptsFTLmay not enjoy the fast rate, as the distance terms may not cancel out. The result also conforms to empirical studies that the  does not exhibit acceleration on general smooth convex problems.





 §.§ Recovering Nesterov’s (1988) 1-memory method <cit.> and Nesterov’s (2005) ∞-memory method  <cit.>


In this subsection, we consider recovering Nesterov’s (1988) 1-memory method  <cit.>
and Nesterov’s (2005)∞-memory method <cit.>.
To be specific, we adopt the presentation of Nesterov’s algorithm given in Algorithm 1 
and Algorithm 3 of <cit.> respectively.


 
Let α_t=t. 
Algorithm <ref> with update by option (A) is the case when the y-player uses 
and the x-player adopts  with γ_t = 1/4L in Fenchel game. Therefore, w_T is an O(1/T^2)-approximate optimal solution of min_x ∈ f(x).
 
The proof is in Appendix <ref>, which shows the direct correspondence of Algorithm <ref> using option (A) to our accelerated solution in Section <ref>.
 
Let α_t=t. 
Algorithm <ref> with update by option (B) is the case when the y-player uses 
and the x-player adopts  with η = 1/4L in Fenchel game.
Therefore, w_T is an O(1/T^2)-approximate optimal solution of min_x ∈ f(x).
 
The proof is in Appendix <ref>, which requires the regret bound of .



 §.§ Nesterov’s (2005) ∞-memory method <cit.>


In this subsection, we consider Nesterov’s (2005) ∞-memory method  <cit.>.
Specifically, we adopt the presentation given in Algorithm 3 of <cit.>.


[t]7cm
[t]7cm

 §.§ Accelerated linear rate


Nesterov observed that, whenf(·)is bothμ-strongly convex andL-smooth, one can achieve a rate that is exponentially decaying inT(e.g. page 71-81 of <cit.>). It is natural to ask if the zero-sum game and regret analysis in the present work
also recovers this faster rate in the same fashion. We answer this in the affirmative.
Denoteκ:= L/μ.

A property off(x)beingμ-strongly convex is that
the functionf̃(x) := f(x) - μ x^2_2/2 is still a convex function.
Now we define a new game whose payoff function isg̃(x,y):= ⟨x, y ⟩- f̃^*(y) +μ x^2_2/2.

Then, the minimax vale of the game isV^* := min_x max_y g̃(x, y) = min_x f̃(x) + μ x^2_2/2 = min_x f(x).
Observe that, in this game, the loss of the y-player in roundtisα_t ℓ_t(y): =   α_t( f̃^*(y)  -⟨x_t, y ⟩),
while the loss of the x-player in roundtis a strongly convex functionα_t h_t(y):= α_t ( ⟨x, y_t ⟩+ μx^2_2/2 ) .
The cumulative loss function of the x-player becomes more and more strongly convex over time,
which is the key to allowing the exponential growth of the total weightA_tthat leads to the linear rate.
In this setup, we have a “warmup round”t=0, and thus we denoteÃ_t:= ∑_s=0^t α_swhich incorporate the additional step into the average. The proof of the following result is in Appendix <ref>.


For the game
g̃(x,y):= ⟨ x, y ⟩ - f̃^*(y) + μ x^2_2/2
, if the y-player plays OptimisticFTL
and the x-player plays BeTheRegularizedLeader:
x_t ←min_x ∈∑_s=0^t α_sℓ_s(x),
where α_0 ℓ_0(x):= α_0μ x^2_2/2, then 
the weighted average points (_T, _T) would be an O(exp(-T/√(κ)))-approximate equilibrium
of the game, where the weights α_0, α_1, … are chosen to satisfy α_t/Ã_̃t̃ = 1/√(6 κ).
This implies that f(_T) - min_x ∈ f(x) = O(exp(-T/√(κ))).



§ ACCELERATED PROXIMAL METHOD

In this section, we consider solving composite optimization problemsmin_x ∈^n f(x) + ψ(x),wheref(·)is smooth convex butψ(·)is possibly non-differentiable convex (e.g.·_1).
We want to show that the game analysis still applies to this problem.
We just need to change the payoff functiongto account forψ(x).
Specifically, we consider the following two-players zero-sum game,min_x max_y { ⟨x, y ⟩- f^*(y) + ψ(x)  }.Notice that the minimax value of the game ismin_x f(x) + ψ(x), which is exactly the  optimum value of the composite optimization problem.

Let us denote the proximal operator asprox_λψ (v) = _x ( ψ(x)+ 1/2λ  x - v ^2_2 ).[It is known that for some ψ(·), their corresponding proximal operations have closed-form solutions
(see e.g. <cit.> for details).]


Clearly, Algorithm <ref> is an instance of our accelerated solution. 
Its x̅_T enjoys the guarantee of being O(1/T^2)-approximate optimal solution. 
Now we explain the update of line 4 in Algorithm <ref>.
Since BTRL is used with the squared of l_2 norm as regularization,

    x_t =  _x ∑_s=1^t α_s h_s(x) + η/2x^2_2 
    =  _x ∑_s=1^t α_s {⟨ y_s, x ⟩ + ψ(x) } + η/2x^2_2
    
         
    =  _x ψ(x) + η/2 A_t x + 1/η∑_s=1^t α_s y_s ^2_2.
     = prox_ A_t/ηψ ( - 1/η∑_s=1^t α_s y_s).


We notice that the loss function of the x-player here,α_t h_t(x) = α_t ( ⟨x , y_t ⟩+ ψ(x) ), is possibly nonlinear.
Yet, we can slightly adapt the analysis in Section <ref> to 
show that the weighed averagex̅_Tis still anO(1/T^2)approximate optimal solution of the offline problem. Please see Appendix <ref> for details.
One can view Algorithm <ref> as a variant of the so called “Accelerated Proximal Gradient”in <cit.>.
Yet, the design and analysis of our algorithm is simpler than that of <cit.>.




§ ACCELERATED 
For space concern, I guess we can just totally remove this section to the appendix. 
We already talk about it on Contribution 1 in Introduction.<cit.> proposed a  like algorithm (which only requires a linear oracle) that enjoys O(1/T^2) rate on all the known examples 
of strongly convex constraint sets that contains the origin, like l_p ball and Schatten p ball with p ∈ (1,2].
However, their analysis requires that the function f(·) is strongly convex too.
We’ve shown in Section <ref> that the strong convexity assumption of f is not necessary 
for getting an O(1/T^2)-approximate saddle point solution. Thus, we’ve improved their analysis and shown that their algorithm does not need strong convexity of f.
This also means that their algorithm is actually optimal for smooth convex problems on the strongly convex constraint sets. Due to the space limit, we elaborate it more in Appendix <ref>.

Acknowlegement: We would like to thank Kevin Lai and Kfir Levy for helpful discussions leading up to the results in this paper. This work was supported by funding from the Division of Computer Science and Engineering at the University of Michigan, from the College of Computing at the Georgia Institute of Technology, NSF TRIPODS award 1740776, and NSF CAREER award 1453304.


plain

§ TWO KEY LEMMAS
Lemma <ref>
  Let the sequence of x_t's be chosen according to . Assume that the Bregman Divergence is uniformly bounded on , so that D = sup_t=1, …, T V_x_t(x^*), where x^* denotes the minimizer of f(·).
   Assume that the sequence {γ_t}_t=1,2,… is non-increasing. Then we have
x≤D/γ_T - ∑_t=1^T1/2 γ_t x_t-1 - x_t ^2.
The key inequality we need, which can be found in Lemma 1 of <cit.> (and for completeness is included in Appendix <ref>) is as follows: let y, c be arbitrary, and assume
x^+ =  _x ∈⟨ x, y ⟩ + V_c(x),  
then for any x^* ∈,

⟨ x^+ - x^*, y ⟩≤ V_c(x^*) - V_x^+(x^*) - V_c(x^+).
Now apply this fact for x^+ = x_t, y=γ_t α_t y_t and c = x_t-1,
which provides

    ⟨ x_t - x^*,  γ_t α_t y_t ⟩≤ V_x_t-1(x^*) - V_x_t(x^*) - V_x_t-1(x_t).
 
So, the weighted regret of the x-player can be bounded by

    x :=  
    ∑_t=1^Tα_t ⟨ x_t - x^*, y_t ⟩(<ref>)≤∑_t=1^T1/γ_t( V_x_t-1(x^*) - V_x_t(x^*) - V_x_t-1(x_t) ) 
    
       
    =  1/γ_1 V_x_0(x^*) - 1/γ_T v_x_T(x^*)  + ∑_t=1^T-1 ( 1/γ_t+1 - 1/γ_t ) V_x_t(x^*) - 1/γ_t V_x_t-1(x_t) 
    
       (a)≤1/γ_1 D + ∑_t=1^T-1 ( 1/γ_t+1 - 1/γ_t ) D - 1/γ_t V_x_t-1(x_t) 
    = D/γ_T -  ∑_t=1^T1/γ_t V_x_t-1(x_t) 
    
       (b)≤D/γ_T - ∑_t=1^T1/2 γ_t x_t-1 - x_t ^2,

where (a) holds since the sequence {γ_t} is non-increasing and D upper bounds the divergence terms, and (b) follows from the strong convexity of ϕ, which grants V_x_t-1(x_t) ≥1/2 x_t - x_t-1^2.


The above lemma requires a boundDon the divergence termsV_x_t(x^*), which might be large in certain unconstrained settings – recall that we do no necessarily require thatis a bounded set, we only assume thatf(·)is minimized at a point with finite norm. On the other hand, when thex-player's learning rateγis fixed, we can define the more natural choiceD = V_x_0(x^*).

Lemma <ref> [Alternative]:
  Let the sequence of x_t's be chosen according to , and assume γ_t = γ for all t. Let D = V_x_0(x^*), where x^* denotes the benchmark in x. Then we have
x≤D/γ - ∑_t=1^T1/2 γ x_t-1 - x_t ^2.
  The proof follows exactly as before, yet γ_t = γ_t+1 for all t implies that 1/γ_t+1 - 1/γ_t = 0 and we may drop the sum in the third line of (<ref>). The rest of the proof is identical.
Lemma 1 of <cit.>:

Let x' =  min_x ∈⟨ x, y ⟩ + V_c(x). 
Then, it satisfies that for any x^* ∈,

    ⟨ x' - x^*, y ⟩≤ V_c(x^*) - V_x'(x^*) - V_c(x').


Recall that the Bregman divergence with respect to the distance generating function ϕ(·) at 
a point c is: V_c(x):= ϕ(x) - ⟨∇ϕ(c), x - c  ⟩  - ϕ(c). 

Denote F(x):= ⟨ x, y ⟩ + V_c(x).
Since x' is the optimal point of 
min_x ∈ K F(x),
by optimality,
⟨ x^* - x' ,  ∇ F(x') ⟩≥ 0,
for any x^*∈ K.



So, 

    ⟨ x^* - x' ,  ∇ F(x') ⟩
    =  ⟨  x^* - x', y ⟩ + ⟨ x^* - x', ∇ϕ (x') - ∇ϕ(c) ⟩
        = ⟨  x^* - x', y ⟩  + {ϕ(x^*) - ⟨∇ϕ(c), x^* - c  ⟩  - ϕ(c) }
    - {ϕ(x^*) - ⟨∇ϕ(x'), x^* - x'  ⟩  - ϕ(x') }
        - {ϕ(x') - ⟨∇ϕ(c), x' - c  ⟩  - ϕ(c) }
         = ⟨  x^* - x', y ⟩ + V_c(x^*) - V_x'(x^*) -  V_c(x')
    ≥ 0.

The last inequality means that 

    ⟨ x' - x^*, y ⟩≤ V_c(x^*) - V_x'(x^*) - V_c(x').


§ PROOF OF THEOREM <REF>
Theorem <ref>
Algorithm <ref> with θ=1/4L is equivalent to Algorithm <ref> with  γ_t = (t+1)/t1/8L in the sense that they generate equivalent sequences of iterates:

    for all  t=1,2,…,T,          w_t = _t    and    z_t-1 = _t.

First, let us check the base case to see if w_1= x̅_1. We have that w_1 = z_0 -θ∇ f(z_0) from line 3 of Algorithm <ref>,
while x̅_1 = x̅_0 - 1/4L∇ f(_1) in (<ref>).
Thus, if the initialization is the same: w_0=z_0=x_0=x̅_0 = _1, then w_1=x̅_1.

Now assume that w_t-1 = x̅_t-1 holds for a t≥ 2.
Then, from the expression of line 4 that 
z_t-1 = w_t-1 + t-2/t+1 (w_t-1 - w_t-2),
we get z_t-1 = x̅_t-1 + t-2/t+1 (x̅_t-1 - x̅_t-2).
Let us analyze that the r.h.s of the equality.
The coefficient of x_t-1 in 
x̅_t-1 + t-2/t+1 (x̅_t-1 - x̅_t-2)
is (t-1) + t-2/t+1(t-1)/A_t-1 = 2(1+t-2/t+1)/t = 2 (2t-1)/t(t+1), while the coefficient of each x_τ for any τ≤ t-2 in x̅_t-1 + t-2/t+1 (x̅_t-1 - x̅_t-2)
is ( 1 + t-2/t+1 ) τ/A_t-1 - t-2/t+1τ/A_t-2
= {2(2t-1)/(t-1)t(t+1) - 2/(t+1)(t-1)}×τ 
= {2/(t-1)(t+1)( 2t-1/t  - 1 )   }×τ
=  2 τ/t(t+1).
Yet, 
the coefficient of x_t-1 in x_t is t+(t-1)/A_t = 2 (2t-1)/t(t+1)
and the coefficient of x_τ in x_t is τ/A_t = 2 τ/t(t+1) for any τ≤ t-2. Thus, z_t-1= x_t.
Now observe that if z_t-1= x_t, we get w_t = x̅_t.
To see this,
substituting  z_t-1 = w_t-1 + t-2/t+1 (w_t-1 - w_t-2) of line 4
into line 3,
we get 
w_t  = w_t-1 + t-2/t+1 (w_t-1 - w_t-2) - θ∇ f(z_t-1).
By using z_t-1= x_t and w_t-1 = x̅_t-1, we further get w_t = x̅_t-1 + t-2/t+1 (x̅_t-1 - x̅_t-2) - θ∇ f(x_t) = x̅_t.
We can repeat the argument to show that the correspondence holds for any t,
which establishes the equivalency.

Notice that the choice of decreasing sequence {γ_t} here can still make the distance terms in 
(<ref>) cancel out. So, we get O(1/T^2) rate by the guarantee.


§ PROOF OF THEOREM <REF>
Theorem <ref>
Let α_t=t. Assume = ^n. Also, let γ_t =O(1/L).
The output x̅_T of Algorithm <ref> is an O(1/T)-approximate optimal solution of min_x f(x).


To analyze the guarantee of x̅_T of Algorithm <ref>, we use the following lemma about  for strongly convex loss functions.

Corollary 1 from <cit.>
Let ℓ_1, . . . ,ℓ_T be a sequence of functions such that for all t ∈ [T], ℓ_t is σ_t-strongly convex. Assume that  runs on this sequence and for each t ∈ [T], let θ_t be in ∇ℓ_t(y_t). Then,
∑_t=1^T ℓ_t(y_t) - min_x ∑_t=1^T ℓ_t(y) ≤1/2∑_t=1^T θ_t^2/∑_τ=1^tσ_τ

Observe that the y-player plays  on the loss function sequence
α_t ℓ_t(y) := α_t ( - ⟨ x_t, y ⟩ + f^*(y) ),
whose strong convexity parameter is α_t/L
(due to f^*(y) is 1/L-strongly convex by duality).
Also,
 ∇ℓ_t(y_t)  = - x_t  + ∇ f^*(y_t) = - x_t  + x̅_t-1,
 where the last inequality is due to that if 
y_t = _y ⟨1/A_t-1∑_s=1^t-1α_s x_s, y ⟩ - f^*(y) = ∇ f(_t-1), then x̅_t-1 = ∇ f^*(y_t) by duality.
So, we have 
yAbove Cor.≤1/ 2 A_T∑_t=1^T α_t^2 x̅_t-1 - x_t  ^2 /∑_τ=1^t α_τ (1/L) = 
    1/2 A_T∑_t=1^T α_t^2 L x̅_t-1 - x_t  ^2 / A_t =
    O( ∑_τ=1^T  L x̅_t-1 - x_t  ^2 /A_T).
For the x-player, it is an instance of MirrorDescent, so  
x := 1/A_T∑_t=1^T⟨ x_t - x^*,  α_t y_t⟩≤1/γ_T D - ∑_t=1^T1/2 γ_t x_t-1 - x_t ^2 /A_T
Therefore, x̅_T of Algorithm <ref> is an x + y = O(L ∑_t=1^T (x̅_t-1 - x_t  ^2 - x_t - x_t-1^2  )/A_T) -approximate optimal solution.
Since the distance terms may not cancel out, one may only bound the differences of the distance terms by a constant, which leads to the non-accelerated O(1/T) rate.


§ PROOF OF THEOREM <REF>
Theorem <ref>
Let α_t=t. 
Algorithm <ref> with update by option (A) is the case when the y-player uses 
and the x-player adopts  with γ_t = 1/4L in Fenchel game. Therefore, w_T is an O(1/T^2)-approximate optimal solution of min_x ∈ f(x).


We first prove by induction showing that w_t in Algorithm <ref> is ∑_s=1^tα_s/A_t x_s
for any t>0.
For the base case t=1, we have
w_1    = (1-β_1) w_0 + β_1 x_1    = x_1 = α_1/A_1 x_1.
Now suppose that the equivalency holds at t-1, for a t ≥ 2.
Then,

    w_t  = (1-β_t) w_t-1 + β_t x_t(a) = (1-β_t) ( ∑_s=1^t-1α_s/A_t-1 x_s   ) + β_t x_t
         =  (1 - 2/t+1) ( ∑_s=1^t-1α_s/t(t-1)/2 x_s   ) + β_t x_t = ∑_s=1^t-1α_s/t(t+1)/2 x_s +  α_t/A_t  x_t
     = ∑_s=1^tα_s/A_s x_s,

where (a) is by induction. So, it holds at t too.
Now we are going to show that
z_t = 1/A_t(α_t x_t-1 + ∑_s=1^t-1α_s x_s ) = _t.


We have that
z_t  = (1-β_t) w_t-1 + β_t x_t-1
= (1-β_t) ( ∑_s=1^t-1α_s/A_t-1 x_s   ) + β_t x_t-1 =  (1 - 2/t+1) ( ∑_t=1^t-1α_t/t(t-1)/2 x_t   ) + β_t x_t-1 = ∑_s=1^t-1α_s/t(t+1)/2 x_s +  β_t x_t-1
 = ∑_s=1^t-1α_s/ A_t x_s +  α_t/A_t x_t-1
 = _t.

The result also means that ∇ f(z_t) = ∇ f(_t) = y_t
of the y-player who plays  in Algorithm <ref>.
Furthermore, it shows that line 5 of Algorithm <ref>:
x_t = _x ∈γ_t'  ⟨∇ f( z_t), x ⟩  + V_x_t-1(x)
is exactly (<ref>) of  in Fenchel game.
Also, from (<ref>), the last iterate w_T in Algorithm <ref>
corresponds to the final output of our accelerated solution to Fenchel game, 
which is the weighted average point that enjoys the guarantee by the game analysis.


§ PROOF OF THEOREM <REF>
Theorem <ref>
Let α_t=t. 
Algorithm <ref> with update by option (B) is the case when the y-player uses 
and the x-player adopts  with η = 1/4L in Fenchel game.
Therefore, w_T is an O(1/T^2)-approximate optimal solution of min_x ∈ f(x).

Consider in Fenchel game that the y-player uses  while the x-player plays according to BTRL:
     x_t = _x ∈∑_t=1^T⟨ x_t , α_t y_t ⟩ + 1/η R(x),
where R(·) is a 1-strongly convex function.
Define, z = min_x ∈ R(x).
     Form <cit.> (also see Appendix <ref>), it shows that  
    BTRL has regret
  
    Regret:= ∑_t=1^T⟨ x_t - x^*, α_t y_t ⟩≤ R(x^*) - R(z)  - 1/2∑_t=1^T x_t - x_t-1^2/η,

  where x^* is the benchmark/comparator defined in the definition of the weighted regret (<ref>).


By combining (<ref>) and (<ref>),
we get that

    x + y/A_T 
    =  R(x^*) - R(z)/η + ∑_t=1^T (α_t^2/A_t L - 1/2η )  x_t-1 - x_t ^2  /A_T≤ O( L (R(x^*) - R(z) )  /T^2 ),

where the last inequality is because η = 1/4L so that the distance terms cancel out.
So, by Lemma <ref> and Theorem <ref> again,
we know that x̅_T is an O(1/T^2)-approximate optimal solution of min_x ∈ f(x).

The remaining thing to do is showing that x̅_T is actually w_T of Algorithm <ref> with option (B). But, this follows the same line as the proof of Theorem <ref>.
So, we have completed the proof.


§ PROOF OF ’S REGRET


For completeness, we replicate the proof in <cit.>
about the regret bound of  in this section.


Theorem 10 of  [<cit.>]

Let θ_t be the loss vector in round t. 
Let the update of BTRL be
x_t  = min_x ∈⟨ x , L_t⟩ + 1/η R(x),
where R(·) is β-strongly convex.
Denote z = min_x ∈ R(x).
Then, BTRL has regret

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z)  - β/2∑_t=1^T x_t - x_t-1^2/η.




To analyze the regret of , 
let us consider  first.

Letθ_tbe the loss vector in roundtand let the cumulative loss vector beL_t = ∑_s=1^t θ_s.
The update of  is

    x_t  = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x),

wherem_tis the learner's guess of the loss vector in roundt,R(·)isβ-strong convex with respect to a norm ( ·) andηis a parameter. 
Therefore, it is clear that
the regret of  will be the one when ’s guess of the loss vectors exactly match the true ones, i.e.m_t = θ_t.


Theorem 16 of  [<cit.>]

Let θ_t be the loss vector in round t. 
Let the update of  be
x_t  = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x),
where m_t is the learner’s guess of the loss vector in round t and R(x) is a β-strongly 
convex function.
Denote the update of standard FTRL as
z_t  = min_x ∈⟨ x , L_t-1⟩ + 1/η R(x).
Also, z_1 = min_x ∈  R(x).
Then,
 (<ref>) has regret

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z_1) - D_T /η +
    ∑_t=1^Tη/βθ_t - m_t^2_* ,

where D_T = ∑_t=1^Tβ/2 x_t - z_t^2 
+ β/2 x_t - z_t+1^2,
z_t = _x ∈⟨ x, L_t-1⟩ + 1/η R(x),
and x_t = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x).


Recall that the update of  isx_t  = min_x ∈ ⟨x , L_t  ⟩+ 1/η R(x),
Therefore, we have thatm_t = θ_tandx_t= z_t+1in the regret bound of  indicated by the theorem.
Consequently, we get that 
the regret of  satisfies

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z) - β/2∑_t=1^T x_t - x_t-1^2/η.


§ PROOF OF ’S REGRET


For completeness, we replicate the proof in <cit.>
about the regret bound of  in this section.




Theorem 16 of  [<cit.>]

Let θ_t be the loss vector in round t. 
Let the update of  be
x_t  = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x),
where m_t is the learner’s guess of the loss vector in round t and R(x) is a β-strongly 
convex function.
Denote the update of standard FTRL as
z_t  = min_x ∈⟨ x , L_t-1⟩ + 1/η R(x).
Also, z_1 = min_x ∈  R(x).
Then,
 (<ref>) has regret

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z_1) - D_T /η +
    ∑_t=1^Tη/βθ_t - m_t^2_* ,

where D_T = ∑_t=1^Tβ/2 x_t - z_t^2 
+ β/2 x_t - z_t+1^2,
z_t = _x ∈⟨ x, L_t-1⟩ + 1/η R(x),
and x_t = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x).



Define z_t= _x ∈⟨ x, L_t-1⟩ + 1/η R(x)
as the update of the standard Follow-the-Regularized-Leader.
We can re-write the regret as

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩
    = ∑_t=1^T⟨ x_t - z_t+1 , θ_t - m_t ⟩ + 
     ∑_t=1^T⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 - x^*, θ_t ⟩

Let us analyze the first sum

    ∑_t=1^T⟨ x_t - z_t+1 , θ_t - m_t ⟩.

Now using Lemma 17 of <cit.> (which is also stated below)
with x_1=x_t, u_1=∑_s=1^t-1θ_s + m_t and x_2=z_t+1, 
u_2=∑_s=1^tθ_s in the lemma,
we have 

    ∑_t=1^T⟨ x_t - z_t+1 , θ_t - m_t ⟩≤∑_t=1^T  x_t - z_t+1θ_t - m_t_* 
    ≤∑_t=1^Tη/βθ_t - m_t ^2_*.

For the other sum,

    ∑_t=1^T⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 - x^*, θ_t ⟩,

we are going to show that, for any T≥0, it is upper-bounded by
R(x^*) - R(z_1) - D_T /η,
which holds for any x^* ∈, where D_T = ∑_t=1^Tβ/2 x_t - z_t^2 
+ β/2 x_t - z_t+1^2.
For the base case T=0, we see that

    ∑_t=1^0⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 - x^*, θ_t ⟩ 
    = 0 
    ≤  R(x^*) - R(z_1) - 0 /η,

as z_1 = min_x ∈ R(x).



Using induction,
assume that it also holds for T-1 for a T ≥ 1.
Then, we have

    ∑_t=1^T⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 , θ_t ⟩
       (a)≤⟨ x_T - z_T+1, m_T ⟩ + ⟨ z_T+1, θ_T ⟩
    +  R(z_T) - R(z_1) - D_T-1/η + ⟨ z_T, L_T-1⟩
       (b)≤⟨ x_T - z_T+1, m_T ⟩ + ⟨ z_T+1, θ_T ⟩
    +  R(x_T) - R(z_1) - D_T-1 - β/2 x_T - z_T^2 /η + ⟨ x_T, L_T-1⟩
        = ⟨ z_T+1, θ_T - m_T ⟩ 
    +  R(x_T) - R(z_1) -D_T-1 - β/2 x_T - z_T^2 /η + ⟨ x_T, L_T-1 + m_T ⟩
       (c)≤⟨ z_T+1, θ_T - m_T ⟩ 
    +  R(z_T+1) - R(z_1) - D_T-1 - β/2 x_T - z_T^2 
    - β/2 x_T - z_T+1^2
    /η
        + ⟨ z_T+1, L_T-1 + m_T ⟩
        = ⟨ z_T+1, L_T ⟩ 
    +  R(z_T+1) - R(z_1) - D_T/η
       (d)≤⟨ x^*, L_T ⟩ 
    +  R(x^*) - R(z_1) - D_T/η,

where (a) is by induction such that the inequality holds at T-1 for any x^*∈ including x^* = z_T,
 (b) and (c) are by strong convexity so that

    ⟨ z_T, L_T-1⟩ + R(z_T)/η≤⟨ x_T, L_T-1⟩ + R(x_T)/η - β/2 η x_T - z_T  ^2,

and

    ⟨ x_T, L_T-1 + m_T ⟩ + R(x_T)/η≤⟨ z_T+1, L_T-1 + m_T ⟩ + R(z_T+1)/η - β/2 η x_T - z_T+1^2,

and (d) is because z_T+1 is the optimal point of 
_x ⟨ x , L_T ⟩ + R(x)/η. We’ve completed the induction.



Lemma 17 of [<cit.>] 

Denote x_1 = _x⟨ x, u_1 ⟩ + 1/η R(x)
and x_2 = _x⟨ x, u_2 ⟩ + 1/η R(x)
for a β-strongly convex function R(·) with respect to a norm ·.
We have x_1 - x_2≤η/β u_1 - u_2_*.

§ PROOF OF THEOREM <REF>
Theorem <ref>
For the game 
g(x,y):= ⟨ x, y ⟩ - f̃^*(y) + μx^2_2/2, if the y-player plays OptimisticFTL
and the x-player plays BeTheRegularizedLeader:
x_t ←min_x ∈∑_s=0^t α_sℓ_s(x),
where α_0 ℓ_0(x):= α_0μ x^2_2/2, then 
the weighted average (_T, _T) would be O(exp(-T/√(κ)))-approximate equilibrium
of the game,
where the weights α_t/Ã_̃t̃ = 1/√(6 κ).
This implies that f(_T) - min_x ∈ f(x) = O(exp(-T/√(κ))).

From Lemma <ref>,
we know that the y-player’s regret by OptimisticFTL is 
    
    ∑_t=1^Tα_t ℓ_t(_t) - α_t ℓ_t(y^*) 
               ≤   ∑_t=1^T δ_t(_t) - δ_t(_t+1) 
        =    ∑_t=1^T α_t ⟨ x_t-1 - x_t, _t - _t+1⟩
    (Eqns. <ref>, <ref>)        =    ∑_t=1^T α_t ⟨ x_t-1 - x_t, ∇f̃(_t) - ∇f̃(_t) ⟩
    (Hölder's Ineq.)       ≤   ∑_t=1^T α_t  x_t-1 - x_t∇f̃(_t) - ∇f̃(_t) 
    
                =    ∑_t=1^T α_t  x_t-1 - x_t∇ f(_t) -μ_t - ∇f̃(_t) + μ_t 
    (triangle inequality)       ≤   ∑_t=1^T α_t  x_t-1 - x_t ( ∇ f(_t) - ∇f̃(_t)  +  μ_t - _t  ) 
    (L-smoothness and L≥μ)       ≤     2 L ∑_t=1^T α_t  x_t-1 - x_t_t - _t 
    (Eqn. <ref>)        =     2 L ∑_t=1^T α_t^2/A_t x_t-1 - x_tx_t-1 - x_t


Therefore,

    y≤ 2 L ∑_t=1^T α_t^2/A_tx_t-1 - x_t ^2.


For the x-player, its loss function in round t is α_tℓ_t(x):= α_t ( μϕ(x) + ⟨ x, y_t ⟩), where ϕ(x):= 1/2x^2_2.
Assume the x-player plays BeTheRegularizedLeader,

    x_t ←min_x ∈∑_s=0^t α_sℓ_s(x),

where α_0 ℓ_0(x):= α_0μϕ(x).
Denote 

    Ã_t:= ∑_s=0^tα_s.

Notice that this is different from A_t:= ∑_s=1^tα_s. 
Then, its regret is (proof is on the next page)

    x := ∑_t=1^T α_t ℓ_t(x_t) - α_t ℓ_t( x^*)
    ≤α_0 μ L_0  x^* - x_0  - ∑_t=1^T μÃ_t-1/2x_t-1 - x_t ^2,
 
where L_0 is the Lipchitz constant of the 1-strongly convex function ϕ(x)
and x_0 = min_xϕ(x).


Summing (<ref>) and (<ref>), we have

    y + x≤α_0 μ L_0  x^* - x_0 + ∑_t=1^T ( 2 L α_t^2/A_t - μÃ_t-1/2 ) x_t-1 - x_t ^2.

We want to let the distance terms cancel out.

    2 L α_t^2/Ã_̃t̃ - a_0 - μÃ_t-1/2≤ 0,
 
which is equivalent to 

    4 L α_t^2 ≤μÃ_̃t̃Ã_t-1 - μα_0 Ã_t-1.
    
        4 L α_t^2/Ã_̃t̃^2 ≤μÃ_t-1/Ã_̃t̃ 
    -  μα_0 Ã_t-1/Ã_̃t̃1/Ã_̃t̃
        4 L α_t^2/Ã_̃t̃^2 ≤μ ( 1 - α_0/Ã_̃t̃ ) 
    (1 -α_t/Ã_̃t̃)

Let us denote the constant θ := α_t/Ã_̃t̃ > 0.

    θ^2 + μ/4L ( 1 - α_0/Ã_̃t̃ ) θ
    - μ/4L( 1 - α_0/Ã_̃t̃  ) ≤ 0.

Notice that 0 < α_0/Ã_̃t̃≤  1.  It suffices to show that

    θ^2 + μ/4L ( 1 - α_0/Ã_̃t̃ ) θ
    - μ/4L≤ 0.

Yet, we would expect that α_0/Ã_̃t̃ is a decreasing function of t, so
it suffices to show that 

    θ^2 + μ/4L ( 1 - α_0/Ã_̃1̃ ) θ
    - μ/4L≤ 0,

which is equivalent to

    θ^2 + μ/4Lα_1/Ã_̃1̃θ - μ/4L≤ 0
    
       θ^2 ( 1 + μ/4L) - μ/4L≤ 0.

It turns out that θ= √(μ/6L) = 1/√(6 κ) satisfies the above inequality, combining the fact that 
μ/L≤ 1.



Therefore, the optimization error ϵ after T iterations is

    ϵ≤y + x/A_T≤1/A_1A_1/A_2⋯A_T-1/A_T
    ( α_0 μ L_0  x^* - x_0   ) 
    
        =  1/A_1 (1 - α_2/A_2 ) ⋯ (1 - α_T/A_T )
    ( α_0 μ L_0  x^* - x_0   ) 
    
       ≤1/A_1 (1 - α_2/Ã_2 ) ⋯ (1 - α_T/Ã_T )
    ( α_0 μ L_0  x^* - x_0   ) 
    
       ≤ (1- 1/√(6 κ) )^T-1α_0 μ L_0/A_1 x^* - x_0 .

which is O( (1 - 1/√(6κ))^T) = O( exp( - 1/√(6κ) T)). 

 (of (<ref>))

First, we are going to use induction to show that

    ∑_t=0^τα_t ℓ_t(x_t) - α_t ℓ_t( x^*) ≤ D_τ,

for any x^*∈,
where D_τ:= - ∑_t=1^τμÃ_t-1/2x_t-1 - x_t ^2.


For the base case t=0, we have

    α_0 μϕ(x_0) - α_0 μϕ(x^*)  ≤ 0 = D_0,

where x_0 is defined as x_0 = min_x ∈α_0 μϕ(x).

Now suppose it holds at t= τ-1.

    ∑_t=0^τα_t ℓ_t(x_t) 
       (a)≤ D_τ-1 + α_τℓ_τ (x_τ)
    + ∑_t=0^τ-1α_t ℓ_t(x_τ-1)
    
       (b)≤ D_τ-1 + α_τℓ_τ (x_τ)
    + ∑_t=0^τ-1α_t ℓ_t(x_τ) - Ã_τ-1μ/2 x_τ-1 - x_τ^2
    
        = D_τ-1 + ∑_t=0^τα_t ℓ_t(x_τ) - Ã_τ-1μ/2 x_τ-1 - x_τ^2
    
        = D_τ +  ∑_t=0^τα_t ℓ_t(x_τ) 
    
       ≤ D_τ +  ∑_t=0^τα_t ℓ_t(x^*),

for any x^*∈,
where (a) we use the induction and we let the point x^*= x_τ-1
and (b) is by the strongly convexity and that 
x_τ-1 = min_x∑_t=0^τ-1α_t ℓ_t(x)
so that ∑_t=0^τ-1α_t ℓ_t(x_τ-1) 
≤∑_t=0^τ-1α_t ℓ_t(x_τ) - Ã_τ-1μ/2 x_τ-1 - x_τ^2 as ∑_t=0^τ-1α_t ℓ_t(x) is at least Ã_τ-1μ/2-strongly convex. We have completed the proof of (<ref>).
By (<ref>), we have

    x := ∑_t=1^T α_t ℓ_t(x_t) - α_t ℓ_t( x^*)
    ≤α_0 μϕ(x^*) - α_0 μϕ(x_0) - ∑_t=1^T μÃ_t-1/2x_t-1 - x_t ^2.
    
       ≤α_0 μ L_0  x_0 - x^* - ∑_t=1^T μÃ_t-1/2x_t-1 - x_t ^2,
 
where we assume that ϕ(·) is L_0-Lipchitz.


§ ANALYSIS OF ACCELERATED PROXIMAL METHOD


First, we need a stronger result.  


Lemma [Property 1 in <cit.>] 

For any proper lower semi-continuous convex function θ(x),
let x^+ =  _x ∈θ(x) + V_c(x). 
Then, it satisfies that for any x^* ∈,

    θ(x^+) - θ(x^*) ≤ V_c(x^*) - V_x^+(x^*) - V_c(x^+).

The statement and its proof has also appeared in
<cit.> and <cit.>.
For completeness, we replicate the proof here.
Recall that the Bregman divergence with respect to the distance generating function ϕ(·) at 
a point c is: V_c(x):= ϕ(x) - ⟨∇ϕ(c), x - c  ⟩  - ϕ(c). 

Denote F(x):= θ(x) + V_c(x).
Since x^+ is the optimal point of 
_x ∈ K F(x),
by optimality,

    ⟨ x^* - x^+ ,  ∇ F(x^+) ⟩ =  
    ⟨ x^* - x^+ , ∂θ(x^+) + ∇ϕ (x^+) - ∇ϕ(c) ⟩≥ 0,

for any x^*∈ K.




Now using the definition of subgradient, we also have

    θ(x^*) ≥θ(x^+) + ⟨∂θ(x^+) , x^* - x^+ ⟩.

By combining (<ref>) and (<ref>), we have

    θ(x^*)    ≥θ(x^+) + ⟨∂θ(x^+) , x^* - x^+ ⟩.
    
       ≥θ(x^+) + ⟨ x^* - x^+ , ∇ϕ (c) - ∇ϕ(x^+) ⟩.
    
        = θ(x^+) - {ϕ(x^*) - ⟨∇ϕ(c), x^* - c  ⟩  - ϕ(c) }
    + {ϕ(x^*) - ⟨∇ϕ(x^+), x^* - x^+  ⟩  - ϕ(x^+) }
        + {ϕ(x^+) - ⟨∇ϕ(c), x^+ - c  ⟩  - ϕ(c) }
         = θ(x^+) - V_c(x^*) + V_x^+(x^*) +  V_c(x^+)


Recall ’s updatex_t = _x   γ_t ( α_t h_t(x) ) + V_x_t-1(x),
whereh_t(x) = ⟨x,  y_t ⟩+ ψ(x).
Using the lemma withθ(x) = γ_t ( α_t h_t(x) ),x^+= x_tandc=x_t-1we have that

    γ_t ( α_t h_t(x_t) ) - γ_t ( α_t h_t(x^*) ) =  θ(x_t) - θ(x^*) ≤ V_x_t-1(x^*) - V_x_t(x^*) - V_x_t-1(x_t).

Therefore, we have that

    x := ∑_t=1^T  α_t  h_t(x_t) - min_x ∈∑_t=1^T  α_t  h_t(x)
    
       (<ref>)≤∑_t=1^T1/γ_t( V_x_t-1(x^*) - V_x_t(x^*) - V_x_t-1(x_t) ) 
    
       
    =  1/γ_1 V_x_0(x^*) - 1/γ_T v_x_T(x^*)  + ∑_t=1^T-1 ( 1/γ_t+1 - 1/γ_t ) V_x_t(x^*) - 1/γ_t V_x_t-1(x_t) 
    
       (a)≤1/γ_1 D + ∑_t=1^T-1 ( 1/γ_t+1 - 1/γ_t ) D - 1/γ_t V_x_t-1(x_t) 
    = D/γ_T -  ∑_t=1^T1/γ_t V_x_t-1(x_t) 
    
       (b)≤D/γ_T - ∑_t=1^T1/2 γ_t x_t-1 - x_t ^2,

where(a)holds since the sequence{γ_t}is non-increasing andDupper bounds the divergence terms, and(b)follows from the strong convexity ofϕ, which grantsV_x_t-1(x_t) ≥1/2  x_t - x_t-1^2. Now we see that following the same lines as the proof in Section <ref>.
We get thatx̅_Tis anO(1/T^2)approximate optimal solution.






§ ACCELERATED 
<cit.> proposed a  like algorithm that not only requires a linear oracle but also enjoysO(1/T^2)rate on all the known examples 
of strongly convex constraint sets that contain the origin,
likel_pball and Schattenpball withp ∈(1,2].
Their analysis requires the assumption that the underlying function is also strongly-convex to 
get the fast rate.
To describe their algorithm, denotebe any closed convex set that contains the origin.
Define “gauge function” ofas(x) := inf{ c ≥0: x/c ∈}.
Notice that, for a closed convexthat contains the origin,= { x ∈^d: (x)≤1 }. Furthermore, the boundary points onsatisfy(x)=1.

<cit.> showed that the squared of a gauge function is strongly convex on the underlyingfor all the known examples of strongly convex sets that contain the origin.
Algorithm <ref> is the algorithm.

Clearly, Algorithm <ref> is an instance of the meta-algorithm.
We want to emphasize again that our analysis does not need the functionf(·)to be strongly convex 
to showO(1/T^2)rate. We’ve improved their analysis.


==================================================================================================
For safety, I decide not to include it. 
==================================================================================================



§ (NEW VERSION FOR ADAPTING LEARNING RATE) PROOF OF ’S REGRET


Assume that {η_t } is non-increasing.
Let θ_t be the loss vector in round t. 
Let the update of BTRL be
x_t  = min_x ∈⟨ x , L_t⟩ + 1/η_t R(x).
Also, let z = min_x ∈ R(x). 
Then, BTRL has regret

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ 2( R(x^*) - R(z) ) /η_T  -  ∑_t=1^Tβ/2 η_t x_t - x_t-1^2.



To analyze the regret of Be-the-Regularized-Leader, 
let us consider  first.

Let θ_t be the loss vector in round t and let the cumulative loss vector be
L_t = ∑_s=1^t θ_s.
The update of  is

    x_t  = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η_t R(x),

where 
m_t is the learner's guess of the loss vector in round t,
R(·) is β-strong convex with respect to a norm (·) and η_t is a parameter. 
Therefore, it is clear that
the regret of  will be the one when ’s guess of the loss vectors exactly match the true ones, i.e. m_t = θ_t.


  
Assume that {η_t } is non-increasing.
Let θ_t be the loss vector in round t. 
Let the update of  be
x_t  = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η_t R(x),
where m_t is the learner’s guess of the loss vector in round t and R(x) is a β-strongly 
convex function.
Denote the update of standard FTRL as
z_t  = min_x ∈⟨ x , L_t-1⟩ + 1/η_t R(x).
Also, let z = min_x ∈ R(x). 
Then,
 (<ref>) has regret

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z) /η_T + C_T - D_T +
    ∑_t=1^Tη_t/βθ_t - m_t^2_* ,
    
       ≤ 2( R(x^*) - R(z) ) /η_T
    - D_T +
    ∑_t=1^Tη_t/βθ_t - m_t^2_*.

where C_T = ∑_t=1^T R(x^*) -R(z) /η_t+1 -  R(x^*) -R(z)  /η_t and D_T = ∑_t=1^Tβ/2 η_t x_t - z_t^2 
+ β/2 η_t x_t - z_t+1^2,
z_t = _x ∈⟨ x, L_t-1⟩ + 1/η_t R(x),
and x_t = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η_t R(x).


Recall that the update of  is 
x_t  = min_x ∈⟨ x , L_t⟩ + 1/η_t R(x),
Therefore, we have that m_t = θ_t and x_t= z_t+1 in the regret bound of  indicated by Theorem <ref>.
Consequently, we get that 
the regret of  satisfies

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ 2( R(x^*) - R(z) )/η_T  - ∑_t=1^Tβ/2 η_t x_t - x_t-1^2.


§ (NEW VERSION FOR ADAPTING LEARNING RATE) PROOF OF OPTIMISTICFTRL’S REGRET

  
Assume that {η_t } is non-increasing.
Let θ_t be the loss vector in round t. 
Let the update of  be
x_t  = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η_t R(x),
where m_t is the learner’s guess of the loss vector in round t and R(x) is a β-strongly 
convex function.
Denote the update of standard FTRL as
z_t  = min_x ∈⟨ x , L_t-1⟩ + 1/η_t R(x).
Also, let z = min_x ∈ R(x). 
Then,
 (<ref>) has regret

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z) /η_T + C_T - D_T +
    ∑_t=1^Tη_t/βθ_t - m_t^2_* ,
    
       ≤ 2( R(x^*) - R(z) ) /η_T
    - D_T +
    ∑_t=1^Tη_t/βθ_t - m_t^2_*.

where C_T = ∑_t=1^T R(x^*) -R(z) /η_t+1 -  R(x^*) -R(z)  /η_t
and D_T = ∑_t=1^Tβ/2 η_t x_t - z_t^2 
+ β/2 η_t x_t - z_t+1^2,
z_t = _x ∈⟨ x, L_t-1⟩ + 1/η_t R(x),
and x_t = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η_t R(x).


We can re-write the regret as

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩
    = ∑_t=1^T⟨ x_t - z_t+1 , θ_t - m_t ⟩ + 
     ∑_t=1^T⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 - x^*, θ_t ⟩



Let us analyze the first sum

    ∑_t=1^T⟨ x_t - z_t+1 , θ_t - m_t ⟩.

Now using Lemma <ref>
with x_1=x_t, u_1=∑_s=1^t-1θ_s + m_t and x_2=z_t+1, 
u_2=∑_s=1^tθ_s in the lemma,
we have 

    ∑_t=1^T⟨ x_t - z_t+1 , θ_t - m_t ⟩≤∑_t=1^T  x_t - z_t+1θ_t - m_t_* 
    ≤∑_t=1^Tη_t/βθ_t - m_t ^2_*.


Now let us analyze the other terms

    ∑_t=1^T⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 - x^*, θ_t ⟩,

we are going to show that, for any T≥0, it is upper-bounded by
R(x^*) - R(z) /η_T + C_T - D_T,
which holds for any x^* ∈, where D_T = ∑_t=1^Tβ/2 η_t x_t - z_t^2 
+ β/2 η_t x_t - z_t+1^2.

For the base case T=0, we see that

    ∑_t=1^0⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 - x^*, θ_t ⟩ 
    = 0 
    ≤ R(x^*) - R(z) /η_t + 0 - 0,

as z = min_x ∈ R(x)



Using induction, we see that 
the base case T=0 clearly is true.
Assume that it also holds for T-1.
Then, we have

    ∑_t=1^T⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 , θ_t ⟩
       (a)≤⟨ x_T - z_T+1, m_T ⟩ + ⟨ z_T+1, θ_T ⟩
    +  R(z_T) - R(z) /η_T-1 + C_T-1- D_T-1 + ⟨ z_T, L_T-1⟩
        = ⟨ x_T - z_T+1, m_T ⟩ + ⟨ z_T+1, θ_T ⟩
    +  (  R(z_T) - R(z)  /η_T-1 -  R(z_T) - R(z) /η_T )
    
        +  R(z_T) - R(z) /η_T  -  D_T-1 + ⟨ z_T, L_T-1⟩
       (b)≤⟨ x_T - z_T+1, m_T ⟩ + ⟨ z_T+1, θ_T ⟩
    +  R(z_T) - R(z) /η_T + C_T-1 -  D_T-1 + ⟨ z_T, L_T-1⟩
       (c)≤⟨ x_T - z_T+1, m_T ⟩ + ⟨ z_T+1, θ_T ⟩
    +  R(x_T) - R(z) /η_T + C_T-1 - D_T-1 - β/2 η_T x_T - z_T^2  + ⟨ x_T, L_T-1⟩
        = ⟨ z_T+1, θ_T - m_T ⟩ 
    +  R(x_T) - R(z) /η_T + C_T-1 - D_T-1 - β/2 η_T x_T - z_T^2  + ⟨ x_T, L_T-1 + m_T ⟩
       (d)≤⟨ z_T+1, θ_T - m_T ⟩ 
    +  R(z_T+1) - R(z) /η_T + C_T-1 - D_T-1 - β/2 η_T x_T - z_T^2 
    - β/2 η_T x_T - z_T+1^2
    
        + ⟨ z_T+1, L_T-1 + m_T ⟩
     = ⟨ z_T+1, L_T ⟩ 
    +  R(z_T+1) - R(z) /η_T + C_T-1- D_T
        =
    ⟨ z_T+1, L_T ⟩ 
    +  R(z_T+1) - R(z) /η_T+1 +  (  R(z_T+1) - R(z) /η_T -  R(z_T+1) - R(z) /η_T+1  ) + C_T-1 - D_T
       (e)≤⟨ x^*, L_T ⟩ 
    +  R(x^*) - R(z) /η_T+1 +
    (  R(z_T+1) - R(z) /η_T -  R(z_T+1) - R(z) /η_T+1  ) 
     + C_T-1
     - D_T,
     
       (f)≤⟨ x^*, L_T ⟩ 
    +  R(x^*) - R(z) /η_T+1 + C_T-1 - D_T,
     
        = 
    ⟨ x^*, L_T ⟩ 
    +  R(x^*) - R(z) /η_T + (   R(x^*) - R(z) /η_T+1 -   R(x^*) - R(z) /η_T ) +   C_T-1 - D_T,
     
        = 
    ⟨ x^*, L_T ⟩ 
    +  R(x^*) - R(z) /η_T + C_T - D_T,

where (a) is by induction such that the inequality holds at T-1 for any x^*∈ including x^* = z_T,
(b) is due to 
that R(z_T) - R(z) is non-negative
and {η_T } is non-increasing.
(c) and (d) are by strong convexity so that

    ⟨ z_T, L_T-1⟩ + R(z_T)/η_T≤⟨ x_T, L_T-1⟩ + R(x_T)/η_T - β/2 η_T x_T - z_T  ^2,

and

    ⟨ x_T, L_T-1 + m_T ⟩ + R(x_T)/η_T≤⟨ z_T+1, L_T-1 + m_T ⟩ + R(z_T+1)/η_T - β/2 η_T x_T - z_T+1^2,
(e) is because z_T+1 is the optimal point of 
_x ⟨ x , L_T ⟩ + R(x)/η_T+1, 
and (f) is the same reason as (b).






Denote x_1 = _x⟨ x, u_1 ⟩ + 1/η R(x)
and x_2 = _x⟨ x, u_2 ⟩ + 1/η R(x)
for a β-strongly convex function R(·) with respect to a norm ·.
We have x_1 - x_2≤η/β u_1 - u_2_*.
==================================================================================================


§ PROOF OF THEOREM <REF>


For completeness, we replicate the proof by <cit.> here.

Theorem <ref>
  Assume a T-length sequence  are given. Suppose in Algorithm <ref> the online learning algorithms ^x and ^y have the -weighted average regret x and y respectively. Then the output  (x̅_T,y̅_T) is an ϵ-equilibrium for g(·, ·), with
ϵ = x + y.
Suppose that the loss function of the x-player in round t is α_t h_t(·) : →, where h_t(·) := g(·, y_t). The y-player, on the other hand, observes her own sequence of loss functions α_t  ℓ_t(·) : →, where ℓ_t(·) := -  g(x_t, ·).



    1/∑_s=1^T α_s∑_t=1^T α_t g(x_t, y_t) 
          =    1/∑_s=1^T α_s∑_t=1^T  - α_t  ℓ_t(y_t)  
         =     
        - 1/∑_s=1^T α_sinf_y ∈{∑_t=1^T  α_t  ℓ_t(y) } - y/∑_s=1^T α_s 
         =    sup_y ∈{1/∑_s=1^T α_s∑_t=1^T  α_t g( x_t , y ) } - y
    (Jensen)    ≥   sup_y ∈ g(1/∑_s=1^T α_s∑_t=1^T  α_t x_t , y )  - y
         =    sup_y ∈ g(_T , y )  - y
       ≥   inf_x ∈sup_y ∈ g( x , y ) - y


Let us now apply the same argument on the right hand side, where we use the x-player's regret guarantee.

    1/∑_s=1^T α_s∑_t=1^T  α_t g(x_t, y_t)     =    1/∑_s=1^T α_s∑_t=1^T  α_t h_t(x_t) 
        =    {∑_t=1^T 1/∑_s=1^T α_sα_t h_t(x) } + x/∑_s=1^T α_s 
        =    {∑_t=1^T 1/∑_s=1^T α_sα_t g(x^*, y_t) } + x
       ≤      
        g(x^*,∑_t=1^T 1/∑_s=1^T α_sα_t y_t) + x
        =     
        g(x^*,_T) + x
       ≤   sup_y ∈  g(x^*,y) + x

Note that sup_y ∈  g(x^*,y) = f(x^*) be the definition of the game g(·,·) and by Fenchel conjugacy, hence we can conclude that sup_y ∈ g(x^*,y) = inf_x ∈sup_y ∈ g(x,y) = V^* = sup_y ∈inf_x ∈  g(x,y).
Combining (<ref>) and (<ref>), we see that:

    sup_y ∈ g(_T, y )  - y≤inf_x ∈  
    g(x,_T ) + x

which implies that (x̅_T, y̅_T) is an ϵ =x + y equilibrium.


§ TWO KEY LEMMAS
(of Lemma <ref>)
The key inequality we need, which can be found in Lemma 1 of <cit.> (and for completeness is included in Appendix <ref>) is as follows: let y, c be arbitrary, and assume
x^+ =  _x ∈⟨ x, y ⟩ + V_c(x),  
then for any x^* ∈,

⟨ x^+ - x^*, y ⟩≤ V_c(x^*) - V_x^+(x^*) - V_c(x^+).
Now apply this fact for x^+ = x_t, y=γ_t α_t y_t and c = x_t-1,
which provides

    ⟨ x_t - x^*,  γ_t α_t y_t ⟩≤ V_x_t-1(x^*) - V_x_t(x^*) - V_x_t-1(x_t).
 
So, the weighted regret of the x-player can be bounded by

    x :=  
    ∑_t=1^Tα_t ⟨ x_t - x^*, y_t ⟩(<ref>)≤∑_t=1^T1/γ_t( V_x_t-1(x^*) - V_x_t(x^*) - V_x_t-1(x_t) ) 
    
       
    =  1/γ_1 V_x_0(x^*) - 1/γ_T v_x_T(x^*)  + ∑_t=1^T-1 ( 1/γ_t+1 - 1/γ_t ) V_x_t(x^*) - 1/γ_t V_x_t-1(x_t) 
    
       (a)≤1/γ_1 D + ∑_t=1^T-1 ( 1/γ_t+1 - 1/γ_t ) D - 1/γ_t V_x_t-1(x_t) 
    = D/γ_T -  ∑_t=1^T1/γ_t V_x_t-1(x_t) 
    
       (b)≤D/γ_T - ∑_t=1^T1/2 γ_t x_t-1 - x_t ^2,

where (a) holds since the sequence {γ_t} is non-increasing and D upper bounds the divergence terms, and (b) follows from the strong convexity of ϕ, which grants V_x_t-1(x_t) ≥1/2 x_t - x_t-1^2.

Let x' =  min_x ∈⟨ x, y ⟩ + V_c(x). 
Then, it satisfies that for any x^* ∈,

    ⟨ x' - x^*, y ⟩≤ V_c(x^*) - V_x'(x^*) - V_c(x').


Recall that the Bregman divergence with respect to the distance generating function ϕ(·) at 
a point c is: V_c(x):= ϕ(x) - ⟨∇ϕ(c), x - c  ⟩  - ϕ(c). 

Denote F(x):= ⟨ x, y ⟩ + V_c(x).
Since x' is the optimal point of 
min_x ∈ K F(x),
by optimality,
⟨ x^* - x' ,  ∇ F(x') ⟩≥ 0,
for any x^*∈ K.



So, 

    ⟨ x^* - x' ,  ∇ F(x') ⟩
    =  ⟨  x^* - x', y ⟩ + ⟨ x^* - x', ∇ϕ (x') - ∇ϕ(c) ⟩
        = ⟨  x^* - x', y ⟩  + {ϕ(x^*) - ⟨∇ϕ(c), x^* - c  ⟩  - ϕ(c) }
    - {ϕ(x^*) - ⟨∇ϕ(x'), x^* - x'  ⟩  - ϕ(x') }
        - {ϕ(x') - ⟨∇ϕ(c), x' - c  ⟩  - ϕ(c) }
         = ⟨  x^* - x', y ⟩ + V_c(x^*) - V_x'(x^*) -  V_c(x')
    ≥ 0.

The last inequality means that 

    ⟨ x' - x^*, y ⟩≤ V_c(x^*) - V_x'(x^*) - V_c(x').


§ PROOF OF THEOREM <REF>
Theorem <ref>
Let α_t=t. Assume = ^n. Also, let γ_t =O(1/L).
The output x̅_T of Algorithm <ref> is an O(1/T)-approximate optimal solution of min_x f(x).


To analyze the guarantee of x̅_T of Algorithm <ref>, we use the following lemma about  for strongly convex loss functions.

Let ℓ_1, . . . ,ℓ_T be a sequence of functions such that for all t ∈ [T], ℓ_t is σ_t-strongly convex. Assume that  runs on this sequence and for each t ∈ [T], let θ_t be in ∇ℓ_t(y_t). Then,
∑_t=1^T ℓ_t(y_t) - min_x ∑_t=1^T ℓ_t(y) ≤1/2∑_t=1^T θ_t^2/∑_τ=1^tσ_τ
Observe that the y-player plays  on the loss function sequence
α_t ℓ_t(y) := α_t ( - ⟨ x_t, y ⟩ + f^*(y) ),
whose strong convexity parameter is α_t/L
(due to f^*(y) is 1/L-strongly convex by duality).
Also,
 ∇ℓ_t(y_t)  = - x_t  + ∇ f^*(y_t) = - x_t  + x̅_t-1,
 where the last inequality is due to that if 
y_t = _y ⟨1/A_t-1∑_s=1^t-1α_s x_s, y ⟩ - f^*(y) = ∇ f(_t-1), then x̅_t-1 = ∇ f^*(y_t) by duality.
So, we have 
yLemma <ref>≤1/ 2 A_T∑_t=1^T α_t^2 x̅_t-1 - x_t  ^2 /∑_τ=1^t α_τ (1/L) = 
    1/2 A_T∑_t=1^T α_t^2 L x̅_t-1 - x_t  ^2 / A_t =
    O( ∑_τ=1^T  L x̅_t-1 - x_t  ^2 /A_T).
For the x-player, it is an instance of MirrorDescent, so  
x := 1/A_T∑_t=1^T⟨ x_t - x^*,  α_t y_t⟩≤1/γ_1 V_x_0(x^*) - ∑_t=1^T1/2 γ_t x_t-1 - x_t ^2 /A_T
Therefore, x̅_T of Algorithm <ref> is an x + y = O(L ∑_t=1^T (x̅_t-1 - x_t  ^2 - x_t - x_t-1^2  )/A_T) -approximate optimal solution.
Since the distance terms may not cancel out, one may only bound the differences of the distance terms by a constant, which leads to the non-accelerated O(1/T) rate.


§ PROOF OF THEOREM <REF>
Theorem <ref>
Let α_t=t. 
Algorithm <ref> with update by option (A) is the case when the y-player uses 
and the x-player adopts  with γ_t = 1/4L in Fenchel game. Therefore, w_T is an O(1/T^2)-approximate optimal solution of min_x ∈ f(x).


We first prove by induction showing that w_t in Algorithm <ref> is ∑_s=1^tα_s/A_t x_s
for any t>0.
For the base case t=1, we have
w_1    = (1-β_1) w_0 + β_1 x_1    = x_1 = α_1/A_1 x_1.
Now suppose that the equivalency holds at t-1, for a t ≥ 2.
Then,

    w_t  = (1-β_t) w_t-1 + β_t x_t(a) = (1-β_t) ( ∑_s=1^t-1α_s/A_t-1 x_s   ) + β_t x_t
         =  (1 - 2/t+1) ( ∑_s=1^t-1α_s/t(t-1)/2 x_s   ) + β_t x_t = ∑_s=1^t-1α_s/t(t+1)/2 x_s +  α_t/A_t  x_t
     = ∑_s=1^tα_s/A_s x_s,

where (a) is by induction. So, it holds at t too.
Now we are going to show that
z_t = 1/A_t(α_t x_t-1 + ∑_s=1^t-1α_s x_s ) = _t.


We have that
z_t  = (1-β_t) w_t-1 + β_t x_t-1
= (1-β_t) ( ∑_s=1^t-1α_s/A_t-1 x_s   ) + β_t x_t-1 =  (1 - 2/t+1) ( ∑_t=1^t-1α_t/t(t-1)/2 x_t   ) + β_t x_t-1 = ∑_s=1^t-1α_s/t(t+1)/2 x_s +  β_t x_t-1
 = ∑_s=1^t-1α_s/ A_t x_s +  α_t/A_t x_t-1
 = _t.

The result also means that ∇ f(z_t) = ∇ f(_t) = y_t
of the y-player who plays  in Algorithm <ref>.
Furthermore, it shows that line 5 of Algorithm <ref>:
x_t = _x ∈γ_t'  ⟨∇ f( z_t), x ⟩  + V_x_t-1(x)
is exactly (<ref>) of  in Fenchel game.
Also, from (<ref>), the last iterate w_T in Algorithm <ref>
corresponds to the final output of our accelerated solution to Fenchel game, 
which is the weighted average point that enjoys the guarantee by the game analysis.


§ PROOF OF THEOREM <REF>
Theorem <ref>
Let α_t=t. 
Algorithm <ref> with update by option (B) is the case when the y-player uses 
and the x-player adopts  with η = 1/4L in Fenchel game.
Therefore, w_T is an O(1/T^2)-approximate optimal solution of min_x ∈ f(x).

Consider in Fenchel game that the y-player uses  while the x-player plays according to BTRL:
     x_t = _x ∈∑_t=1^T⟨ x_t , α_t y_t ⟩ + 1/η R(x),
where R(·) is a 1-strongly convex function.
Define, z = min_x ∈ R(x).
     Form <cit.> (also see Appendix <ref>), it shows that  
    BTRL has regret
  
    Regret:= ∑_t=1^T⟨ x_t - x^*, α_t y_t ⟩≤ R(x^*) - R(z)  - 1/2∑_t=1^T x_t - x_t-1^2/η,

  where x^* is the benchmark/comparator defined in the definition of the weighted regret (<ref>).


By combining (<ref>) and (<ref>),
we get that

    x + y/A_T 
    =  R(x^*) - R(z)/η + ∑_t=1^T (α_t^2/A_t L - 1/2η )  x_t-1 - x_t ^2  /A_T≤ O( L (R(x^*) - R(z) )  /T^2 ),

where the last inequality is because η = 1/4L so that the distance terms cancel out.
So, by Lemma <ref> and Theorem <ref> again,
we know that x̅_T is an O(1/T^2)-approximate optimal solution of min_x ∈ f(x).

The remaining thing to do is showing that x̅_T is actually w_T of Algorithm <ref> with option (B). But, this follows the same line as the proof of Theorem <ref>.
So, we have completed the proof.


§ PROOF OF ’S REGRET


For completeness, we replicate the proof in <cit.>
about the regret bound of  in this section.


Let θ_t be the loss vector in round t. 
Let the update of BTRL be
x_t  = min_x ∈⟨ x , L_t⟩ + 1/η R(x),
where R(·) is β-strongly convex.
Denote z = min_x ∈ R(x).
Then, BTRL has regret

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z)  - β/2∑_t=1^T x_t - x_t-1^2/η.




To analyze the regret of , 
let us consider  first.

Let θ_t be the loss vector in round t and let the cumulative loss vector be
L_t = ∑_s=1^t θ_s.
The update of  is

    x_t  = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x),

where 
m_t is the learner's guess of the loss vector in round t,
R(·) is β-strong convex with respect to a norm (·) and η is a parameter. 
Therefore, it is clear that
the regret of  will be the one when ’s guess of the loss vectors exactly match the true ones, i.e. m_t = θ_t.


Let θ_t be the loss vector in round t. 
Let the update of  be
x_t  = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x),
where m_t is the learner’s guess of the loss vector in round t and R(x) is a β-strongly 
convex function.
Denote the update of standard FTRL as
z_t  = min_x ∈⟨ x , L_t-1⟩ + 1/η R(x).
Also, z_1 = min_x ∈  R(x).
Then,
 (<ref>) has regret

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z_1) - D_T /η +
    ∑_t=1^Tη/βθ_t - m_t^2_* ,

where D_T = ∑_t=1^Tβ/2 x_t - z_t^2 
+ β/2 x_t - z_t+1^2,
z_t = _x ∈⟨ x, L_t-1⟩ + 1/η R(x),
and x_t = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x).


Recall that the update of  is 
x_t  = min_x ∈⟨ x , L_t⟩ + 1/η R(x),
Therefore, we have that m_t = θ_t and x_t= z_t+1 in the regret bound of  indicated by Theorem <ref>.
Consequently, we get that 
the regret of  satisfies

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z) - β/2∑_t=1^T x_t - x_t-1^2/η.


§ PROOF OF ’S REGRET


For completeness, we replicate the proof in <cit.>
about the regret bound of  in this section.




Let θ_t be the loss vector in round t. 
Let the update of  be
x_t  = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x),
where m_t is the learner’s guess of the loss vector in round t and R(x) is a β-strongly 
convex function.
Denote the update of standard FTRL as
z_t  = min_x ∈⟨ x , L_t-1⟩ + 1/η R(x).
Also, z_1 = min_x ∈  R(x).
Then,
 (<ref>) has regret

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩≤ R(x^*) - R(z_1) - D_T /η +
    ∑_t=1^Tη/βθ_t - m_t^2_* ,

where D_T = ∑_t=1^Tβ/2 x_t - z_t^2 
+ β/2 x_t - z_t+1^2,
z_t = _x ∈⟨ x, L_t-1⟩ + 1/η R(x),
and x_t = min_x ∈⟨ x , L_t-1 + m_t ⟩ + 1/η R(x).


Define z_t= _x ∈⟨ x, L_t-1⟩ + 1/η R(x)
as the update of the standard Follow-the-Regularized-Leader.
We can re-write the regret as

    Regret:= ∑_t=1^T⟨ x_t - x^*, θ_t⟩
    = ∑_t=1^T⟨ x_t - z_t+1 , θ_t - m_t ⟩ + 
     ∑_t=1^T⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 - x^*, θ_t ⟩

Let us analyze the first sum

    ∑_t=1^T⟨ x_t - z_t+1 , θ_t - m_t ⟩.

Now using Lemma <ref>
with x_1=x_t, u_1=∑_s=1^t-1θ_s + m_t and x_2=z_t+1, 
u_2=∑_s=1^tθ_s in the lemma,
we have 

    ∑_t=1^T⟨ x_t - z_t+1 , θ_t - m_t ⟩≤∑_t=1^T  x_t - z_t+1θ_t - m_t_* 
    ≤∑_t=1^Tη/βθ_t - m_t ^2_*.

For the other sum,

    ∑_t=1^T⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 - x^*, θ_t ⟩,

we are going to show that, for any T≥0, it is upper-bounded by
R(x^*) - R(z_1) - D_T /η,
which holds for any x^* ∈, where D_T = ∑_t=1^Tβ/2 x_t - z_t^2 
+ β/2 x_t - z_t+1^2.
For the base case T=0, we see that

    ∑_t=1^0⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 - x^*, θ_t ⟩ 
    = 0 
    ≤  R(x^*) - R(z_1) - 0 /η,

as z_1 = min_x ∈ R(x).



Using induction,
assume that it also holds for T-1 for a T ≥ 1.
Then, we have

    ∑_t=1^T⟨ x_t - z_t+1 , m_t ⟩ + ⟨ z_t+1 , θ_t ⟩
       (a)≤⟨ x_T - z_T+1, m_T ⟩ + ⟨ z_T+1, θ_T ⟩
    +  R(z_T) - R(z_1) - D_T-1/η + ⟨ z_T, L_T-1⟩
       (b)≤⟨ x_T - z_T+1, m_T ⟩ + ⟨ z_T+1, θ_T ⟩
    +  R(x_T) - R(z_1) - D_T-1 - β/2 x_T - z_T^2 /η + ⟨ x_T, L_T-1⟩
        = ⟨ z_T+1, θ_T - m_T ⟩ 
    +  R(x_T) - R(z_1) -D_T-1 - β/2 x_T - z_T^2 /η + ⟨ x_T, L_T-1 + m_T ⟩
       (c)≤⟨ z_T+1, θ_T - m_T ⟩ 
    +  R(z_T+1) - R(z_1) - D_T-1 - β/2 x_T - z_T^2 
    - β/2 x_T - z_T+1^2
    /η
        + ⟨ z_T+1, L_T-1 + m_T ⟩
        = ⟨ z_T+1, L_T ⟩ 
    +  R(z_T+1) - R(z_1) - D_T/η
       (d)≤⟨ x^*, L_T ⟩ 
    +  R(x^*) - R(z_1) - D_T/η,

where (a) is by induction such that the inequality holds at T-1 for any x^*∈ including x^* = z_T,
 (b) and (c) are by strong convexity so that

    ⟨ z_T, L_T-1⟩ + R(z_T)/η≤⟨ x_T, L_T-1⟩ + R(x_T)/η - β/2 η x_T - z_T  ^2,

and

    ⟨ x_T, L_T-1 + m_T ⟩ + R(x_T)/η≤⟨ z_T+1, L_T-1 + m_T ⟩ + R(z_T+1)/η - β/2 η x_T - z_T+1^2,

and (d) is because z_T+1 is the optimal point of 
_x ⟨ x , L_T ⟩ + R(x)/η. We’ve completed the induction.




Denote x_1 = _x⟨ x, u_1 ⟩ + 1/η R(x)
and x_2 = _x⟨ x, u_2 ⟩ + 1/η R(x)
for a β-strongly convex function R(·) with respect to a norm ·.
We have x_1 - x_2≤η/β u_1 - u_2_*.

§ ANALYSIS OF ACCELERATED PROXIMAL METHOD


First, we need a stronger result.  


For any proper lower semi-continuous convex function θ(x),
let x^+ =  _x ∈θ(x) + V_c(x). 
Then, it satisfies that for any x^* ∈,

    θ(x^+) - θ(x^*) ≤ V_c(x^*) - V_x^+(x^*) - V_c(x^+).

The statement and its proof has also appeared in
<cit.> and <cit.>.
For completeness, we replicate the proof here.
Recall that the Bregman divergence with respect to the distance generating function ϕ(·) at 
a point c is: V_c(x):= ϕ(x) - ⟨∇ϕ(c), x - c  ⟩  - ϕ(c). 

Denote F(x):= θ(x) + V_c(x).
Since x^+ is the optimal point of 
_x ∈ K F(x),
by optimality,

    ⟨ x^* - x^+ ,  ∇ F(x^+) ⟩ =  
    ⟨ x^* - x^+ , ∂θ(x^+) + ∇ϕ (x^+) - ∇ϕ(c) ⟩≥ 0,

for any x^*∈ K.




Now using the definition of subgradient, we also have

    θ(x^*) ≥θ(x^+) + ⟨∂θ(x^+) , x^* - x^+ ⟩.

By combining (<ref>) and (<ref>), we have

    θ(x^*)    ≥θ(x^+) + ⟨∂θ(x^+) , x^* - x^+ ⟩.
    
       ≥θ(x^+) + ⟨ x^* - x^+ , ∇ϕ (c) - ∇ϕ(x^+) ⟩.
    
        = θ(x^+) - {ϕ(x^*) - ⟨∇ϕ(c), x^* - c  ⟩  - ϕ(c) }
    + {ϕ(x^*) - ⟨∇ϕ(x^+), x^* - x^+  ⟩  - ϕ(x^+) }
        + {ϕ(x^+) - ⟨∇ϕ(c), x^+ - c  ⟩  - ϕ(c) }
         = θ(x^+) - V_c(x^*) + V_x^+(x^*) +  V_c(x^+)


Recall ’s update
x_t = _xγ_t ( α_t h_t(x) ) + V_x_t-1(x).
Here. h_t(x) = ⟨ x,  y_t ⟩ + ψ(x).
Using Lemma <ref> with θ(x) = γ_t ( α_t h_t(x) ), x^+= x_t and c=x_t-1  we have that

    γ_t ( α_t h_t(x_t) ) - γ_t ( α_t h_t(x^*) ) =  θ(x_t) - θ(x^*) ≤ V_x_t-1(x^*) - V_x_t(x^*) - V_x_t-1(x_t).

Recall the definition of x.

    x := ∑_t=1^T  α_t  h_t(x_t) - min_x ∈∑_t=1^T  α_t  h_t(x)
    
       (<ref>)≤∑_t=1^T1/γ_t( V_x_t-1(x^*) - V_x_t(x^*) - V_x_t-1(x_t) ) 
    
       
    =  1/γ_1 V_x_0(x^*) - 1/γ_T v_x_T(x^*)  + ∑_t=1^T-1 ( 1/γ_t+1 - 1/γ_t ) V_x_t(x^*) - 1/γ_t V_x_t-1(x_t) 
    
       (a)≤1/γ_1 D + ∑_t=1^T-1 ( 1/γ_t+1 - 1/γ_t ) D - 1/γ_t V_x_t-1(x_t) 
    = D/γ_T -  ∑_t=1^T1/γ_t V_x_t-1(x_t) 
    
       (b)≤D/γ_T - ∑_t=1^T1/2 γ_t x_t-1 - x_t ^2,

where (a) holds since the sequence {γ_t} is non-increasing and D upper bounds the divergence terms, and (b) follows from the strong convexity of ϕ, which grants V_x_t-1(x_t) ≥1/2 x_t - x_t-1^2. Now we see that following the same lines as the proof in Section <ref>.
We get that x̅_T is an O(1/T^2) approximate optimal solution.





§ ACCELERATED 
<cit.> proposed a  like algorithm that not only requires a linear oracle but also enjoys O(1/T^2) rate on all the known examples 
of strongly convex constraint sets that contain the origin,
like l_p ball and Schatten p ball with p ∈ (1,2].
Their analysis requires the assumption that the underlying function is also strongly-convex to 
get the fast rate.
To describe their algorithm, denote  be any closed convex set that contains the origin.
Define “gauge function” of  as (x) := inf{ c ≥ 0: x/c∈}.
Notice that, for a closed convex  that contains the origin, 
= { x ∈^d: (x)≤ 1 }. Furthermore, the boundary points on  satisfy (x)=1.

<cit.> showed that the squared of a gauge function is strongly convex on the underlying 
for all the known examples of strongly convex sets that contain the origin.
Algorithm <ref> is the algorithm.

Clearly, Algorithm <ref> is an instance of the meta-algorithm.
We want to emphasize again that our analysis does not need the function f(·) to be strongly convex 
to show O(1/T^2) rate. We’ve improved their analysis.




§ PROOF OF THEOREM <REF>


For completeness, we replicate the proof by <cit.> here.

Theorem <ref>
  Assume a T-length sequence  are given. Suppose in Algorithm <ref> the online learning algorithms ^x and ^y have the -weighted average regret x and y respectively. Then the output  (x̅_T,y̅_T) is an ϵ-equilibrium for g(·, ·), with
ϵ = x + y.
Suppose that the loss function of the x-player in round t is α_t h_t(·) : →, where h_t(·) := g(·, y_t). The y-player, on the other hand, observes her own sequence of loss functions α_t  ℓ_t(·) : →, where ℓ_t(·) := -  g(x_t, ·).



    1/∑_s=1^T α_s∑_t=1^T α_t g(x_t, y_t) 
          =    1/∑_s=1^T α_s∑_t=1^T  - α_t  ℓ_t(y_t)  
         =     
        - 1/∑_s=1^T α_sinf_y ∈{∑_t=1^T  α_t  ℓ_t(y) } - Regret_T^y /∑_s=1^T α_s 
         =    sup_y ∈{1/∑_s=1^T α_s∑_t=1^T  α_t g( x_t , y ) } - y
    (Jensen)    ≥   sup_y ∈ g(1/∑_s=1^T α_s∑_t=1^T  α_t x_t , y )  - y
       ≥   inf_x ∈sup_y ∈ g( x , y ) - y


Let us now apply the same argument on the right hand side, where we use the x-player's regret guarantee.

    1/∑_s=1^T α_s∑_t=1^T  α_t g(x_t, y_t)     =    1/∑_s=1^T α_s∑_t=1^T  α_t h_t(x_t) 
        =    inf_x ∈{∑_t=1^T 1/∑_s=1^T α_sα_t h_t(x) } + Regret_T^x /∑_s=1^T α_s 
        =    inf_x ∈{∑_t=1^T 1/∑_s=1^T α_sα_t g(x, y_t) } + x
       ≤   inf_x ∈  
        g(x,∑_t=1^T 1/∑_s=1^T α_sα_t y_t) + x
       ≤   sup_y ∈inf_x ∈  g(x,y) + x

Since V^*= inf_x ∈sup_y ∈ g(x,y) = sup_y ∈inf_x ∈  g(x,y),
combining (<ref>) and (<ref>), we see that:

    sup_y ∈ g(x̅_, y )  - y≤inf_x ∈  
    g(x,y̅_) + x

which implies that (x̅_, y̅_) is an ϵ =x + y equilibrium.