Optimal Strategies and Minimax Lower Bounds for Online Convex Games

Jacob Abernethy UC Berkeley jake@cs.berkeley.edu Alexander Rakhlin UC Berkeley rakhlin@cs.berkeley.edu

Peter L. Bartlett UC Berkeley bartlett@cs.berkeley.edu Ambuj Tewari TTI Chicago ambuj@cs.berkeley.edu the literature, this framework has been referred to as Online Convex Optimization (OCO), since our goal is to minimize a global function, i.e. f1 + f2 + · · · + fT , while this objective is revealed to us but one function at a time. Online Convex Optimization has attracted much interest in recent years [4, 9, 6, 1], as it provides a general analysis for a number of standard online learning problems including, among others, online classification and regression, prediction with expert advice, the portfolio selection problem, and online density estimation. While instances of OCO have been studied over the past two decades, the general problem was first analyzed by Zinkevich [9], who showed that a very simple and natural algorithm, online gradient descent, elicits a bound on the regret  that is on the order of T . Online gradient descent can be described simply by the update xt+1 = xt -  ft (xt ), where  is some parameter of the algorithm. This regret bound only required that ft be smooth, convex, and with bounded derivative.  A regret bound of order O( T ) is not surprising: a number of online learning problems give rise to similar bounds. More recently, however, Hazan et al. [4] showed that when F consists of curved functions, i.e. ft is strongly convex, then we get a bound of the form O(log T ). It is quite surprising that curvature gives such a great advantage to the player. Curved loss functions, such as square loss or logarithmic loss, are very natural in a number of settings. Finding algorithms that can guarantee low regret is, however, only half of the story; indeed, it is natural to ask "can we obtain even lower regret?" or "do better algorithms exist?" The goal of the present paper is to address these questions, in some detail, for several classes of such online optimization problems. We answer both in the negative: the algorithms of Zinkevich and Hazan et al. are tight even up to their multiplicative constants. This is achieved by a game-theoretic analysis: if we pose the above online optimization problem as a game between a Player who chooses xt and an Adversary who chooses ft , we may consider the regret achieved when each player is playing optimally. This is typically referred to as the value VT of the game. In general, computing the value of zero-sum games is difficult, as we may have to consider exponentially many, or even uncountably many, strategies of the Player and the Adversary. Ultimately we will show that this value, as well as the optimal strategies of both the player and the adversary,

Abstract
A number of learning problems can be cast as an Online Convex Game: on each round, a learner makes a prediction x from a convex set, the environment plays a loss function f , and the learner's long-term goal is to minimize regret. Algorithms have been proposed by Zinkevich, when f is assumed to be convex, and Hazan et al., when f is assumed to be strongly convex, that have provably low regret. We consider these two settings and analyze such games from a minimax perspective, proving minimax strategies and lower bounds in each case. These results prove that the existing algorithms are essentially optimal.

1 Introduction
The decision maker's greatest fear is regret: knowing, with the benefit of hindsight, that a better alternative existed. Yet, given only hindsight and not the gift of foresight, imperfect decisions can not be avoided. It is thus the decision maker's ultimate goal to suffer as little regret as possible. In the present paper, we consider the notion of "regret minimization" for a particular class of decision problems. Assume we are given a set X and some set of functions F on X . On each round t = 1, . . . , T , we must choose some xt from a set X . After we have made this choice, the environment chooses a function ft  F . We incur a cost (loss) ft (xt ), and the game proceeds to the next round. Of course, had we the fortune of perfect foresight and had access to the sum f1 + . . . + fT , we would know the optimal choice T x = arg minx t=1 ft (x). Instead, at time t, we will have only seen f1 , . . . , ft-1 , and we must make the decision xt with only historical knowledge. Thus, a natural long-term goal is to minimize the regret, which here we define as tT
=1

ft (xt ) - inf

tT
=1

xX

ft (x).

A special case of this setting is when the decision space X is a convex set and F is some set of convex functions on X . In
 

Division of Computer Science Division of Computer Science, Department of Statistics


can be computed exactly and efficiently for certain classes of online optimization games. The central results of this paper are as follows: · When the adversary plays linear loss functions, we use a known randomized argument to lower bound the value VT . We include this mainly for completeness. · We show that indeed this same linear game can be solved exactly for the case when the input space X is a ball, and we provide the optimal strategies for the player and adversary. · We perform a similar analysis for the quadratic game, that is where the adversary must play quadratic functions. We describe the adversary's strategy, and we prove that the well-known Follow the Leader strategy is optimal for the player. · We show that the above results apply to a much wider class of games, where the adversary can play either convex or strongly convex functions, suggesting that indeed the linear and quadratic games are the "hard cases".

where D := maxx,yX x - y and G is some positive constant. · Hazan et al. [4]: If L1 = . . . = LT = F consist of continuous twice differentiable functions f , where f  G and 2f I, then 1 G2 log T , 2 where G and  are positive constants. RT  · Bartlett et al. [1]: If Lt consists of continuous twice ifferentiable functions f , where d f  Gt and 2f t I , then T 1t G2 t RT  , t 2 =1 s=1 s where Gt and t are positive constants. Moreover, the algorithm does not need to know Gt , t on round t. w All three of these games posit an upper bound on f hich is required to make the game nontrivial (and is natural in most circumstances). However, the first requires only that the second derivative be nonnegative, while the second and third game has a strict positive lower bound on the eigenvalues of the Hessian 2f . Note that the bound of Bartlett et al recovers the logarithmic regret of Hazan et al whenever Gt and t do not vary with time. In the present paper, we analyze each of these games with the goal of obtaining the exact minimax value of the game, defined as: VT (G (X, {Lt })) = T
x1 X f1 L1

2 Online Convex Games
The general optimization game we consider is as follows. We have two agents, a player and an adversary, and the game proceeds for T rounds with T known in advance to both agents. The player's choices will come from some convex set X  Rn , and the adversary will choose functions from the class F . For the remainder of the paper, n denotes the dimension of the space X . To consider the game in full generality, we assume that the adversary's "allowed" functions may change on each round, and thus we imagine there is a sequence of allowed sets L1 , L2 , . . . , LT  F . Online Convex Game G (X, {Lt }): 1: for t = 1 to T do 2: Player chooses (predicts) xt  X . 3: Adversary chooses a function ft  Lt . 4: end for 5: Player suffers regret RT = tT
=1

inf

sup . . . inf

xT X fT LT

sup

t
=1

ft (xt ) - inf

tT
=1

. ft (x)

xX

ft (xt ) - inf

tT
=1

xX

ft (x).

From this general game, we obtain each of the examples above with appropriate choice of X, F and the sets {Lt }. We define a number of particular games in the definitions below. It is useful to prove regret bounds within this model as they apply to any problem that can be cast as an Online Convex Game. The known general upper bounds are as follows: · Zinkevich [9]: If L1 = . . . = LT = F consist of continuous twice differentiable functions f , where f G and 2f 0, then1  1 RT  D G T . 2
This bound can be obtained by a slight modification of the analysis in [9].
1

The quantity VT (G ) tells us the worst case regret of an optimal strategy in this game. First, in the spirit of [1], we consider VT for the games where constants G and  , which respectively bound the first and second derivatives of ft , can change throughout the game. That is, the Adversary is given two sequences before the game begins, G1 , . . . , GT and 1 , . . . , T . We also require only that the gradient of ft is bounded at the point xt , i.e. ft (xt )  Gt , as opposed to the global constraint ft (x)  Gt for all x  X . We may impose both of the above constraints by carefully choosing the sets Lt  F , and we note that these sets will depend on the choices xt made by the Player. We first define the Linear and Quadratic Games, which are the central objects of this paper. Definition 1 The Linear Game Glin (X, Gt ) is the game G (X, {Lt }) where Lt = {f : f (x) = v
(

x-xt )+c, v  Rn , c  R; v  Gt }.

Definition 2 The Quadratic Game Gquad (X, Gt , t ) is the game G (X, {Lt }) where t x - xt 2 + c, Lt = {f : f (x) = v (x - xt ) + 2 v  Rn , c  R; v  Gt }.


The functions in these definitions are parametrized through xt to simplify proofs of the last section. In Section 4, however, we will just consider the standard parametrization f (x) = w · x. We also introduce more general games: the Convex Game and the Strongly Convex Game. While being defined with respect to a much richer class of loss functions, we show that these games are indeed no harder than the Linear and the Quadratic Games defined above. Definition 3 The Convex Game Gconv (X, Gt ) is the game G (X, {Lt }) where Lt = {f : f (xt )  Gt , 2f 0}.

Definition 4 The Strongly Convex Game Gst-conv (X, Gt , t ) is the game G (X, {Lt }) where Lt = {f : f (xt )  Gt , 2f - t I 0}.

We write G (G ) instead of G ( Gt ) when all values Gt = G for some fixed G . This holds similarly for G ( ) instead of G ( t ). Furthermore, we suppose that 1 > 0 throughout the paper.

3 Previous Work
Several lower bounds for various online settings are available in the literature. Here we review a number of such results relevant to the present paper and highlight our primary contributions. The first result that we mention is the lower bound of Vovk in the online linear regression setting [8]. It is shown that there exists a randomized strategy of the Adversary such ( that the expected regret is at least n - )G2 ln T - C for any > 0 and C a constant. One crucial difference between this particular setting and ours is that the loss functions of the form (yt - xt · wt )2 used in linear regression are curved in only one direction and linear in all other, thus this setting does not quite fit into any of the games we analyze. The lower bound of Vovk scales roughly as n log T , which is quite interesting given that n does not enter into the lower bound of the Strongly Convex Game we analyze. The lower bound for the log-loss functions of Ordentlich and Cover [5] in the setting of Universal Portfolios is also logarithmic in T and linear in n. Log-loss functions are parameterized as ft (x) = - log(w ·x) for x in the simplex, and these fit more generally within the class of "exp-concave" functions. Upper bounds on the class of log-loss functions were originally presented by Cover [3] whereas Hazan et al. [4] present an efficient method for competing against the more general exp-concave functions. The log-loss lower bound of [5] is quite elegant yet, contrary to the minimax results we present, the optimal play is not efficiently computable. The work of Takimoto and Warmuth [7] is most closely related to our results for the Quadratic Game. The authors consider functions f (x) = 1 ||x - y||2 corresponding to the 2 log-likelihood of the datapoint y for a unit-variance Gaussian with mean x. The lower bound of 1 D2 (ln T - ln ln T + 2 O(ln ln T / ln T )) is obtained, where D is the bound on the norm of adversary's choices y. Furthermore, they exhibit the

minimax strategy which, in the end, corresponds to a biased maximum-likelihood solution. We emphasize that these results differ from ours in several ways. First, we enforce a constraint on the size of the gradient of ft whereas [7] constrain the location of the point y when ft (x) = 1 ||x - y||2 . 2 With our slightly weaker constraint, we can achieve a regret bound of the order log T instead of the log T - log log T of Takimoto and Warmuth. Interestingly, the authors describe the "- log log T " term of their lower bound as "surprising" because many known games "were shown to have O(log T ) upper bounds". They conjecture that the apparent slack is due to the learner being unaware of the time horizon T . In the present paper, we resolve this issue by noting that our slightly weaker assumption erases the additional term; it is thus the limit on the adversary, and not knowledge of the horizon, that gives rise to the slack. Furthermore, the minimax strategy of Takimoto and Warmuth, a biased maximum likelihood estimate on each round, is also an artifact of their assumption on the boundedness of adversary's choices. With our weaker assumption, the minimax strategy is exactly maximum likelihood (generally called "Follow The Leader"). All previous work mentioned above deals with "curved" functions. We now discuss known lower bounds for the Linear Game. It is well-known that in the expert setting, it is im possible to do better than O( T ). The lower bound in CesaBianchi and Lugosi [2], Theorem 3.7, proves an asymptotic bound: in the limit of T  , the value of the game be( haves as ln N )T /2, where N is the number of experts. We provide a similar randomized argument, which has been sketched in the literature (e.g. Hazan et al [4]), but our additional minimax analysis indeed gives the tightest bound possible for any T . Finally, we provide reductions between Quadratic and Strongly Convex as well as Linear and Convex Games. While apparent that the Adversary does better by playing linear approximations instead of convex functions, it requires a careful analysis to show that this holds for the minimax setting.

4 The Linear Game
In this section e begin by providing a relatively standard w proof of the O( T ) lower bound on regret when competing against linear loss functions. The more interesting result is our minimax analysis which is given in Section 4.2. 4.1 The Randomized Lower Bound Lower bounds for games with linear loss functions have appeared in the literature though often not in detail. The rough idea is to imagine a randomized Adversary and to compute the layer's expected regret. This generally produces an P O( T ) lower bound yet it is not fully satisfying since the analysis is not tight. In the following section we provide a much improved analysis with minimax strategies for both the Player and Adversary.   Theorem 5 Suppose X = [-D/(2 n), D/(2 n)]n , so that the diameter of X is D. Then T t D VT (Glin (X, Gt ))   G2 t 22 =1


Proof: Define the scaled cube   Ct = {-Gt / n, Gt / n}n . Suppose the Adversary chooses functions from ^ Lt = {f (x) = w · x : w  Ct }. ^ Note that f = wt = Gt for any f  Lt . Since we are restricting the Adversary to play linear functions with restricted w, ^ ^ VT (Glin (X, Gt ))  VT (G (X, L1 , . . . , LT )) = T t tT = inf sup . . . inf sup ft (xt ) - inf ft (x)
x1 X ^ f1 L1 xT X ^ fT LT =1 xX =1

Hence, =

T Gt Dt i,t  VT (Glin (X, Gt ))  -E{ i,t } - 2 n =1 n =1 T T  t t D D  E{ i,t } i,t Gt G2 , t 2 22 =1 =1 in

where the last inequality follows from the Khinchine's inequality [2]. 4.2 The Minimax Analysis While in the previous section we found a particular lower bound on VT (Glin ), here we present a complete minimax analysis for the case when X is a ball in Rn (of dimension n at least 3). We are indeed able to compute exactly the value VT (Glin (X, Gt )) and we provide the simple minimax strategies for both the Player and the Adversary. The unit ball, while a special case, is a very natural choice for X as it is the largest convex set of diameter 2. For the remainder of this section, let ft (x) := wt · x where wt  Rn with wt  Gt . Also, we define Wt = t s=1 ws , the cumulative functions chosen by the Adversary. Theorem 6 Let X = {x : x 2  D/2} and suppose the Adversary chooses functions from Lt = {f (x) = w · x : w Then the value of the game T VT (Glin (X, Gt )) = D 2 t
=1 2


x1 X w1 C1

T inf sup . . . inf
xT X wT CT

sup

t
=1

wt · xt - inf x ·
xX

tT
=1

wt ,

T
x1 X

inf Ew1 . . . inf EwT
xT X

t
=1

wt · xt - inf x ·
xX

tT
=1

wt

where Ewt denotes expectation with respect to any distribution over the set Ct . In particular, it holds for the uniform  distribution, i.e. when the coordinates of wt are ±Gt / n with probability 1/2. Since in this case EwT wT · xT = 0 for any xT , we obtain VT (Glin (X, Gt ))  inf Ew1 . . . inf EwT -1 inf x1 X xT -1 X xT X = T tT t wt EwT wt · xt - inf x ·
=1 x1 X xX =1

 Gt }.

inf Ew1 . . .

xT -1 X

inf

=

EwT -1 inf xT X T -1 tT t wt wt · xt - EwT inf x ·
=1 xX =1

G2 . t

x1 X

inf Ew1 . . .

xT -1 X

inf

EwT -1

T -1 t
=1

wt · xt - EwT inf x ·
xX

tT
=1

, wt

Furthermore, the optimal strategy for the player is to choose   -D  Wt . W xt+1 =  T 2 2 + s=t+1 Gs t To prove the theorem, we will need a series of short lemmas. Lemma 7 When X is the unit ball B = {x : x  1}, the value VT can be written as T t inf sup . . . inf sup wt · xt + WT (1)
x1 B w1 L1 xT B wT LT =1

where the last equality holds because the expression no longer depends on xT . Repeating the process, we obtain VT (Glin (X, Gt ))  -Ew1 ,...,wT inf x ·
xX

tT
=1

wt ,

x = -E{
i,t } on n D D x - 2n , 2n

min

·

tT
=1

wt

 where wt (i) = i,t Gt / n, with i.i.d. Rademacher variables i,t = ±1 with probability 1/2. The last equality is due to the fact that a linear function is minimized at the vertices of the cube. In fact, the dot product is minimized by matching T the sign of x(i) with that of the ith coordinate of t=1 wt .

In addition, if we choose a larger radius D, the value of the game will scale linearly with this radius and thus it is enough to assume X = B . Proof: The last term in the regret t inf ft (x) = inf WT · x = - WT
xB xB


WT since the infimum is obtained when x = WT . This implies equation (1). The fact that the bound scales linearly with D/2 follows from the fact that both the norm WT will scale with D/2 as well as the terms wt · xt .

For the remainder of this section, we simply assume that X = B , the unit ball with diameter D = 2. Lemma 8 Regardless of the Player's choices, the Adversary can always obtain regret at least T t G2 (2) t
=1

whenever the dimension n is at least 3. Proof: Consider the following adversarial strategy and assume X = B . On round t, after the Player has chosen xt , the adversary chooses wt such that wt = Gt , wt · xt = 0 and wt · Wt-1 = 0. Finding a vector of length Gt that is perpendicular to two arbitrary vectors can always be done when the dimtension is at least 3. With this strategy, it is guaranteed that wt · xt = 0 and we claim also that T t WT = G2 . t
=1

Figure 1: Illustration for the proof of the minimax strategy for the ball. We suppose that xt is aligned with Wt-1 and depict the plane spanned by Wt-1 and wt . We assume that wt has angle  with the line perpendicular to Wt-1 and show that  = 0 is optimal.

T 2 where xt is as defined in (3) and 1 is t=1 Gt . Let T t bVt (w1 , . . . , wt-1 ) = sup . . . sup wt · xt + WT
wt wT =1

This follows from a simple induction. Assuming Wt-1 = t
-1 s=1

G2 , then s

Wt = Wt-1 + wt = implying the desired conclusion.

W

t-1

2 + wt 2,

e the optimum payoff to the adversary given that he plays w1 , . . . , wt-1 in the beginning and then plays optimally. The player plays according to (3) throughout. Note that the value of the game is V1 . We prove by backward induction that, for all t  {1, . . . , T }, Vt (w1 , . . . , wt-1 )  t (w1 , . . . , wt-1 ) The base case, t = T + 1 is obvious. Now assume it holds for t + 1 and we will prove it for t. We have Vt (w1 , . . . , wt-1 ) = sup Vt+1 (w1 , . . . , wt )
wt

The result of the last lemma is quite surprising: the adversary need only play some vector with length Gt which is perpendicular to both xt and Wt-1 . Indeed, this lower bound has a very different flavor from the randomized argument of the previous section. To obtain a full minimax result, all that remains is to show that the Adversary can do no better! Lemma 9 Let w0 = 0. If the player always plays the point xt = then T sup sup . . . sup
w1 w2 wT

(induc.)  sup t+1 (w1 , . . . , wt )
wt

= L ()

t s-1 =1

-Wt-1 W
t-1

xs · ws + x
t

(3) T
2 s=t Gs

2+

sup
wt

· wt +

W
t-1

+ wt 2 + 2+1 t

T wt · xt + WT  t
=1

t
=1

G2 t

et us consider the final supremum term above. If we can show that it is no more than W 2 (4) t-1 2 + t then we will have proved Vt  t thus completing the induction. This is the objective of the remainder of this proof. We begin by noting two important facts about the expression (*). First, the supremum is taken over a convex function of wt and thus the maximum occurs at the boundary, i.e. where wt = Gt exactly. This is easily checked by computing the Hessian with respect to wt . Second, since xt is chosen parallel to Wt-1 , the only two vectors of interest are

i.e., the regret can be no greater than the value in (2). t Proof: As before, Wt = s=1 ws . Define 2 = t the forward sum, with T +1 = 0. Define t (w1 , . . . , wt-1 ) =
t s-1 =1

T

s=t

G2 , s

xs · ws +

W
t-1

2 + 2 t


wt and Wt-1 . Without loss of generality, we can assume that Wt-1 is the 2-dim vector F, 0 , where F = Wt-1 , and that wt = -Gt sin , Gt cos  for any . Plugging in the choice of xt in (3), we may now rewrite (*) as F F Gt sin  2 + G 2 + 2 sup F + t t+1 - 2F Gt sin   2 + G 2 + 2 t t+1 
()

and note that this expression has no dependence on the size of X . We would thus ideally like to consider the case when X = Rn , for this would seem to be the "hardest" case for the Player. The unbounded assumption is problematic, however, not because the game is too difficult for the Player, but the game is too difficult for the Adversary!. This ought to come as quite a surprise, but arises from the particular restrictions we place on the Adversary. Proposition 5.1 For G ,  > 0, if maxx,yX x - y = D > 4G / , there is an  > 0 such that VT (Gquad (X, G ,  ))  -T . Proof: Fix xo , xe  X with xo - xe > 4G / . Consider a player that plays x2k-1 = xo , x2k = xe . Then for any x  X,  f2k-1 (x)  f2k-1 (xo ) - G x - xo + x - xo 2, 2 And similarly for f2k and xe . Summing over t (assuming that T is even) shows that Vt (Gquad (X, G ,  )) is no more than tT
=1

We illustrate this problem in Figure 1. Bounding the above expression requires some care, and thus we prove it in Lemma 16 found in the appendix. The result of Lemma 16 gives us that, indeed, W F 2 2 + G 2 + 2 ()  t-1 2 + t . t t+1 = Since (*) is exactly sup (), which is no greater than F 2 + 2 , t we are done. We observe that the minimax strategy for the ball is exactly the Online Gradient Descent strategy2 of Zinkevich [9]. The value of the game for the ball is exactly the upper bound for the proof of Online Gradient Descent if the initial point is the center of the ball. The lower bound of the randomized argument in the previous section dfers from the upper bound if for Online Gradient Descent by 2.

ft (xt ) -

tT
=1

ft (x) 

 TG x - xo 2 x - xo - 2 2 .  x - xe 2 +G x - xe - 2

5 The Quadratic Game
As in the last section, we now give a minimax analysis of the game Gquad . Ultimately we will be able to compute the exact value of VT (Gquad (X, Gt , t )) and provide the optimal strategy of both the Player and the Adversary. What is perhaps most interesting is that the optimal Player strategy is the well-known Follow The Leader approach. This general strategy can be defined simply as xt+1 = arg min
xX

But by the triangle inequality, any x  X has x - xo + x - xe  D. Subject to this constraint, plus the constraints 0  x - xo  D, 0  x - xe  D shows that Vt (Gquad (X, G ,  ))  T (G D -  D2 /4)/2  -T for some  > 0, since D > 4G / . As we don't generally expect regret to be negative, this example suggests that the Quadratic Game is uninteresting without further constraints on the Player. While an explicit bound on the size of X is a possibility, it is easier for the analysis to place a slightly weaker restriction on the Player. Assumption 5.1 Let x-1 be the minimizer of Ft-1 (x). We t assume that the Player must choose xt such that t xt - x-1 < 2Gt . t

st
=1

fs (x);

that is, we choose the best x "in hindsight". As has been pointed out by several authors, this strategy can incur (T ) regret when the loss functions are linear. It is thus quite surprising that this strategy is optimal when instead we are competing against quadratic loss functions. t For this section, define Ft (x) := s=1 fs (x) and x := t t arg minx Ft (x). Define  1:t = s=1 s . We assume from the outset that 1 > 0. We also set  1:0 = 0. 5.1 A Necessary Restriction Recall that the upper bound in Hazan et al. [4] is 1 G2 RT  log T 2
This does require some work to show, and more information will be available in the full version of this paper.
2

This restriction is necessary for non-negative regret. Indeed, it can be shown that if we increase the size of the above ball by only , the method of Proposition 5.1 above shows that the regret will be negative for large enough T . 5.2 Minimax Analysis With the above restriction in place, we now simply write the game as Gquad ( Gt , t ), omitting the input X . We now proceed to compute the value of this game exactly. Theorem 10 Under Assumption 5.1, the value of the game VT (Gquad ( Gt , t )) = tT
=1

G2 t . 2 1:t

With uniform Gt and t , we obtain the harmonic series, giving us our logarithmic regret bound. We note that this is exactly the upper bound proven in [1, 4], even with the constant.


Corollary 11 For the uniform parameters of the game, G G log(T + 1)  VT (Gquad (G ,  ))  (1 + log T ). 2 2 The main argument in the proof of Theorem 10 boils down to reducing the multiple round game to a single round game. The following lemma gives the value of this single round game. Since the proof is somewhat technical, we postpone it to the Appendix. Lemma 12 For arbitrary Gt , t ,  1:t-1 > 0, inf
:||||

Then = Vt := inf sup . . . inf sup
x1 f1 xt ft

t s
=1

fs (xs ) - inf Ft (z)
z

= inf sup . . . inf sup
x1 f1 xt ft ,z

t s
=1

fs (xs ) - Ft (z) t s-1
=1

+ inf sup . . . inf sup
x1 f1 xt-1 ft-1

fs (xs ) - Ft-1 (x-1 ) t - z) - 1 t z - xt 2 2 .

inf sup
xt ft ,z

f

t (xt )(xt

- 1  1:t-1 z - x-1 2 t 2
2

2Gt t

=G 1 1 sup t  -  - 2 t  -  2 - 2  1:t-1 


G2 G2 t t = , 2 1:t 2 1:t and indeed the optimal strategy pair is  = 0 and  any G vector for which  = 1tt . : We now show how to "unwind" the recursive inf sup definition of VT (Gquad ( Gt , t )), where the final term we chop off is the object we described in the above lemma. Proof: [Proof of Theorem 10] Let x-1 be the minimizer t of Ft-1 (x) and z  X be arbitrary. Note that Ft is  1:t quadratic, so Ft (z) = Ft-1 (z) + ft (z) = Ft-1 (x-1 + (z - x-1 )) + ft (z) t t = Ft-1 (x-1 ) + t + 2  1:t-1 z - = Ft-1 (x-1 ) t
1 1

However, we can simplify the final inf sup as follows. We note that the quantity ft (xt )(xt - z) is maximized when ft (xt ) = Gt xt -z . Second, we can instead use the varixt -z ables  = xt - x-1 and  = z - x-1 in the optimization. t t G Recall from Assumption 5.1 that xt -x-1 =   2tt . t Then, + t s-1 Vt = inf sup . . . inf sup fs (xs ) - Ft-1 (x-1 ) t
x1 f1 xt-1 ft-1 =1

inf
:||||

2Gt t

sup (Gt- - 

1 2

= inf sup . . . inf
x1 f1 xt-1

t  -  2 - 1  1:t-1  2

2

= sup
ft-1

t s-1
=1

+ fs (xs ) - Ft-1 (x-1 ) t

Ft-1 (x-1 )(z - x-1 ) t t 2 + ft (z)

G2 t 2 1:t

x-1 t

+ 2  1:t-1 z - x-1 2 + ft (z), t

G2 t Vt-1 + , 2 1:t where the second equality is obtained by applying Lemma 12. Unwinding the recursion proves the theorem.

where the last equality holds by the definition of x-1 . Hence, t st
=1

+ fs (xs ) - Ft (z) = f
t (xt )

t s-1
=1

fs (xs ) - Ft-1 (x-1 ) t .

Corollary 13 The optimal Player strategy is to set xt = x-1 on each round. t Proof: In analyzing the game, we found that the optimal choice of  = xt - x-1 was shown to be 0 in Lemma 12. t

- ft (z) - 1  1:t-1 z - x-1 2 t 2

Expanding ft around xt , ft (xt ) - ft (z) = - ft (xt )(z - xt ) - 1 t z - xt 2. 2 Substituting, + st
=1

6 General Games
While the minimax results shown above are certainly interesting, we have only shown them to hold for the rather restricted games Glin and Gquad . For these particular cases, the class of functions that the Adversary may choose from is quite small: both the set of linear functions and the set quadratic functions can be parameterized by O(n) variables. . It would of course be more satisfying if our minimax analy2 ses held for more richer loss function spaces.

fs (xs ) - Ft (z) = f
t (xt )(xt

t s-1
=1
1

fs (xs ) - Ft-1 (x-1 ) t

1 - z) - 2 t z - xt 2 - 2  1:t-1 z - x-1 t


Indeed, we prove in this section that both of our minimax results hold much more generally. In particular, we prove that even if the Adversary were able to choose any convex function on round t, with derivative bounded by Gt , then he can do no better than if he only had access to linear functions. On a similar note, if the Adversary is given the weak restriction that his functions be t -strongly convex on round t, then he can do no better than if he could only choose t -quadratic functions. Theorem 14 For fixed X, Gt , and t , the values of the Quadratic Game and the Strongly Convex Game are equal3 : VT (Gst-conv (X, Gt , t )) = VT (Gquad (X, Gt , t )). For a fixed X and Gt , the values of the Convex Game and the Linear Game are equal: VT (Gconv (X, Gt )) = VT (Glin (X, Gt )). We need the following lemma whose proof is postponed to the appendix. Define the regret function R(x1 , f1 , . . . , xT , fT ) = tT
=1

Acknowledgments We gratefully acknowledge the support of DARPA under grant FA8750-05-2-0249 and NSF under grant DMS-0707060.

Appendix
Proof:[Proof of Lemma 12] We write Pt (,  ) := Gt  -  - 1 t  -  2 - 1  1:t-1  2 2 and Qt () := sup Pt (,  ),
 2

then our goal is to obtain

inf
:  

2Gt t

Qt (). We now pro-

ft (xt ) - min
xX

tT
=1

ft (x).

Lemma 15 Consider a sequence of sets {Ns }T=1 and M  s Nt for some t. Suppose that for all ft  Nt and xt  X there exists ft  M such that for all (x1 , f1 , . . . , xt-1 , ft-1 , xt+1 , ft+1 , . . . , xT , fT ), R(x1 , f1 , . . . , xt , ft , . . . , xT , fT )  R(x1 , f1 , . . . , xt , ft , . . . , . . . , xT , fT ). Then inf sup . . . inf sup . . . inf sup R(x1 , f1 , . . . , xT , fT )
x1 f1 N1 xt ft Nt xT fT NT

ceed to show that the choice  = 0 is optimal. For this choice, G2 t Qt (0) = sup Gt  - 1  1:t  2 = . 2 2 1:t  Here the optimal choice of  is any vector such that  = Gt  1:t . Now let us consider the case that  = 0. First, suppose  =  . Note that the optimum sup Pt (,  ) will be obtained when the gradient with respect to  is zero, i.e. - t ( - ) -  1:t-1  = 0 -Gt - - implying that  is a linear scaling of , i.e.  = c. The second case,  =  , also implies that  is a linear scaling of . Substituting this optimal form of  , Qt () = sup [Gt |1 - c| ·  cR . 1 - 2 t (1 - c)2  2 - 1  1:t-1 c2  2 2 We now claim that the supremum over c  R occurs at some c  1 for any choice of . Assume by contradiction that c > 1 for some . Then c = -c + 2 achieves at least the ~ same value as c since |1 - c | = |1 - c| while (c )2 > (c)2 , ~ ~ making the last term larger, which is a contradiction. Hence, c  1 and, collecting the terms, + G 1 2 Qt () = sup t  - 2 t 
c1

= inf sup . . . inf sup . . . inf sup R(x1 , f1 , . . . , xT , fT ).
x1 f1 N1 xt ft M xT fT NT

Proof:[Proof of Theorem 14] Given the sequences Gt , t , let Lt (xt ) be defined as for the Strongly Convex Game (Definition 3) and L (xt ) be defined as for the Quadratic Game t (Definition 2). Observe that L  Lt for any t. Moreover, t for any ft  Lt and xt  X , define ft (x) = ft (xt ) + 1 ft (xt ) (x - xt ) + 2 t x - xt 2. By definition, ft (xt ) =  ft (xt ) and ft (xt ) = ft (xt ). Hence, ft  L . Furthert more, ft (x)  ft (x) for any x  X , and x in particular. Hence, for all (x1 , f1 , . . . , xt-1 , ft-1 , xt+1 , ft+1 , . . . , xT , fT ), R(x1 , f1 , . . . , xt , ft , . . . , xT , fT )  R(x1 , f1 , . . . , xt , ft , . . . , . . . , xT , fT ). The statement of the first part of the theorem follows by Lemma 15, applied for every t  {1, . . . , T }. The second part is proved by analogous reasoning.
3 We note that the computation of VT for the Quadratic Game required a particular restriction on the player, Assumption 5.1, where here we only consider a fixed domain X .

c·



t



2

- Gt 

-

c2 ·

1

 1:t  2

2

.

Since we now assume  = 0, we see that the supre2 mum is achieved for c = t 1:t -Gt2  = t 1 -Gt  1    :t  and  2 2 - Gt  t Qt () = + (Gt  - 1 t  2 ) 2 2 1:t  2 2 2 2   -  t  Gt + Gt =t 2 1:t + (Gt  - 1 t  2 ) 2 1 + t 2 =  t  -  Gt  1:t 2 G2 t (Gt  - 1 t  2 ) + 2 2 1:t  G2  1:t-1 G G2 1 t t > , = + t - 2 t   1:t 2 1:t 2 1:t


G where the last inequality holds by because   2tt . Hence, the value Qt () is strictly larger than G2 /(2 1:t ) t whenever  > 0 and is equal to this value if  = 0. Hence, the optimal choice for the Player is to choose  = 0.

which implies that either cos  = 0 or sin  = 0, i.e.   {- /2, 0,  /2}. Taking the second derivative, we get  () = -  F G sin  F 2 + G2 + K 2 - F G sin   - 2 + G2 + K 2 - 2F G sin  F (F G cos )(F G cos ) + 2 + G2 + K 2 - 2F G sin )3/2 (F

Proof:[Proof of Lemma 15] Fix ft  Lt and xt  X . Let ft  M be as in the statement of the lemma. Define h1 (x1 , f1 , . . . , xt-1 , ft-1 , xt+1 , ft+1 , . . . , xT , fT ) := R(x1 , f1 , . . . , xt , ft , . . . , xT , fT ) h2 (x1 , f1 , . . . , xt-1 , ft-1 , xt+1 , ft+1 , . . . , xT , fT ) := R(x1 , f1 , . . . , xt , ft , . . . , xT , fT ). By assumption, h1  h2 . Hence, we can inf/sup over the variables xt+1 , ft+1 , . . . , xT , fT , obtaining
xt+1 ft+1 Nt+1

.

Thus,  (0) < 0. We conclude that the optimum is attained at  = 0 and therefore F 2 + G2 + K 2 () 

inf

sup

. . . inf
xT

References
[1] Peter Bartlett, Elad Hazan, and Alexander Rakhlin. Adaptive online gradient descent. In J.C. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20. MIT Press, Cambridge, MA, 2008. ` ´ [2] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. [3] T.M. Cover. Universal portfolios. Mathematical Finance, 1(1):1­29, January 1991. [4] Elad Hazan, Adam Kalai, Satyen Kale, and Amit Agarwal. Logarithmic regret algorithms for online convex optimization. In COLT, pages 499­513, 2006. [5] Erik Ordentlich and Thomas M. Cover. The cost of achieving the best portfolio in hindsight. Math. Oper. Res., 23(4):960­982, 1998. [6] Shai Shalev-Shwartz and Yoram Singer. Convex re¨ peated games and Fenchel duality. In B. Scholkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems 19. MIT Press, Cambridge, MA, 2007. [7] Eiji Takimoto and Manfred K. Warmuth. The minimax strategy for gaussian density estimation. pp. In COLT '00: Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, pages 100­ 106, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. [8] V. Vovk. Competitive on-line linear regression. In NIPS '97: Proceedings of the 1997 conference on Advances in neural information processing systems 10, pages 364­ 370, Cambridge, MA, USA, 1998. MIT Press. [9] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, pages 928­936, 2003.

sup R(x1 , f1 , . . . , xt , ft , . . . , xT , fT )
fT NT

 inf

xt+1 ft+1 Nt+1

sup

. . . inf
xT

fT NT

sup R(x1 , f1 , . . . , xt , ft , . . . , xT , fT )

for any (x1 , f1 , . . . , xt-1 , ft-1 ). Hence, since ft  M
ft Nt xt+1 ft+1 Nt+1 fT NT

sup inf

sup

. . . inf
xT

sup R(x1 , f1 , . . . , xt , ft , . . . , xT , fT )  sup inf
ft M xt+1 ft+1 Nt+1 fT NT

sup

. . . inf
xT

sup R(x1 , f1 , . . . , xt , ft , . . . , xT , fT ) for all (x1 , f1 , . . . , xt-1 , ft-1 , xt ). Since M  Nt , the above is in fact an equality. Since the two functions of the variables (x1 , f1 , . . . , xt-1 , ft-1 , xt ) are equal, taking inf 's and sup's over these variables we obtain the statement of the lemma. Lemma 16 The expression F F G sin  2 + G2 + K 2 - 2F G sin   + F 2 + G2 + K 2  is no more than F 2 + G2 + K 2 for constants F, G, K > 0 and any . Proof: We are interested in proving that the supremum of F F G sin  2 + G2 + K 2 - 2F G sin  () =  + 2 + G2 + K 2 F over [- /2,  /2] is attained at  = 0. Setting the derivative of () to zero,  F G cos  F G cos  - =0 F 2 + G2 + K 2 F 2 + G2 + K 2 - 2F G sin