Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations

Introduction

The online learning framework provides a scalable and flexible approach for modeling a wide range of prediction problems, including classification, regression, ranking, and portfolio management. Online algorithms work in rounds, where at each round a new instance is given and the algorithm makes a prediction. Then the environment reveals the label of the instance, and the learning algorithm updates its internal hypothesis. The aim of the learner is to minimize the cumulative loss it suffers due to its prediction error.

Research in this area has mainly focused on designing new prediction strategies and proving theoretical guarantees for them. However, recently, minimax analysis has been proposed as a general tool to design optimal prediction strategies [Rakhlin et al., 2012, 2013, McMahan and Abernethy, 2013]. The problem is cast as a sequential multi-stage zero-sum game between the player (the learner) and an adversary (the environment), providing the optimal strategies for both. In some cases the value of the game can be calculated exactly in an efficient way [Abernethy et al., 2008a], in others upper bounds on the value of the game (often based on the sequential Rademacher complexity) are used to construct efficient algorithms with theoretical guarantees [Rakhlin et al., 2012].

While most of the work in this area has focused on the setting where the player is constrained to a bounded convex set [Abernethy et al., 2008a] (with the notable exception of McMahan and Abernethy ), in this work we are interested in the general setting of unconstrained online learning with linear losses in Hilbert spaces. In Section 4, extending the work of McMahan and Abernethy , we provide novel and general sufficient conditions to be able to compute the exact minimax strategy for both the player and the adversary, as well as the value of the game. In particular, we show that under these conditions the optimal play of the adversary is always orthogonal or always parallel to the sum of his previous plays, while the optimal play of the player is always parallel. On the other hand, for some cases where the exact minimax strategy is hard to characterize, we introduce a new relaxation procedure based on a Normal approximation. In the particular application of interest, we show the relaxation is strong enough to yield an optimal regret bound, up to constant factors.

In Section 5, we use our new tools to recover and extend previous results on minimax strategies for linear online learning, including results for bounded domains. In fact, we show how to obtain a family of minimax strategies that smoothly interpolates between the minimax algorithm for a bounded feasible set and a minimax optimal algorithm in fact equivalent to unconstrained gradient descent. We emphasize that all the algorithms from this family are exactly minimax optimal,In this work, we use the term “minimax” to refer to the exact minimax solution to the zero sum game, as opposed to algorithms that only achieve the minimax optimal rate up to say constant factors. in a sense we will make precise in the next section. Moreover, if you are allowed to play outside of the comparator set, we show that some members of this family have a non-vacuous regret bound for the unconstrained setting, while remaining optimal for the constrained one.

When studying unconstrained problems, a natural question is how small we can make the dependence of the regret bound on $U$, the $L_{2}$ norm of an arbitrary comparator point, while still maintaining a $\sqrt{T}$ dependency on the time horizon. The best algorithm from the above family achieves $\operatorname{Regret}(U)\leq\frac{1}{2}(U^{2}+1)\sqrt{T}$. Streeter and McMahan and Orabona show it is possible to reduce the dependence on $U$ to $\mathcal{O}(U\log UT)$. In order to improve on this, in Section 6 we apply our techniques to analyze a strategy, based on a Normal potential function, that gives a regret bound of \mathcal{O}\Big{(}U\sqrt{T\log(U\sqrt{T}\log^{2}T+1)}\Big{)} where $U$ is the $L_{2}$ norm of a comparator, and both $T$ and $U$ are unknown. This bound is optimal up to $\sqrt{\log\log T}$ terms. Moreover, when $T$ is known, we propose an algorithm based on a similar potential function that is optimal up to constant terms. This solves the open problem posed in those papers, matching the lower bound for this problem. Table 1 summarizes the regret bounds we prove, along with those for related algorithms.

Our analysis tools for both known-$T$ and unknown horizon algorithms rest heavily on the relationship between the reward (negative loss) achieved by the algorithm, potential functions that provide a benchmark for the amount of reward the algorithm should have, the regret of the algorithm with respect to a post-hoc comparator $u$, and the conditional value of the game. These are familiar concepts from the literature, but we summarize these relationships and provide some modest generalizations in Section 3.

Notation and Problem Formulation

We consider a version of online linear optimization, a standard game for studying repeated decision making. On each of a sequence of rounds, a player chooses an action $w_{t}\in\mathcal{H}$, an adversary chooses a linear cost function $g_{t}\in\mathcal{G}\subseteq\mathcal{H}$, and the player suffers loss $\langle w_{t},g_{t}\rangle$. For any sequence of plays $w_{1},\dots w_{T}$ and $g_{1},\dots,g_{T}$, we define the regret against a comparator $u$ in the standard way:

We write $\theta_{t}\equiv-g_{1:t}$, where we use the compressed summation notation $g_{1:t}\equiv\sum_{s=1}^{T}g_{s}$.

It will be useful to consider a full game-theoretic characterization of the above interaction when the number of rounds $T$ is known to both players. This approach that has received significant recent interest [Abernethy et al., 2008a, 2007, Abernethy and Warmuth, 2010, Abernethy et al., 2008b, Streeter and McMahan, 2012].

In the constrained setting, where the comparator vector $\boldsymbol{u}\in\mathcal{W}$, we have that the value of the game, that is the regret when both the player and the adversary play optimally, is

We define inductively the conditional value of the game after $g_{1},\dots,g_{t}$ have been played by

Thus, we can view the notation $V$ for the value of the game as shorthand for $V_{0}(\mathbf{0})$. Under minimax play by both players, unrolling the previous equality, we have $\sum_{s=1}^{t}\langle g_{s},w_{s}\rangle+V_{t}(-g_{1:t})=V,$ or for $t=T$,

We also have that, given the conditional value of the game, a minimax-optimal strategy is

McMahan and Abernethy [2013, Cor. 2] showed that in the unconstrained case, $V_{t}$ is a smoothed version of $B$, where the smoothing comes from an expectation over future plays of the adversary. In this work, we show that in some cases (Theorem 4) we can find a closed form for $V_{t}$ in terms of $B$, and in fact the solution to (3) will simply be the gradient of $V_{t}$, or equivalently, an FTRL algorithm with regularizer $V_{t}^{*}$. On the other hand, to derive our main results, we face a case (Theorem 6) where $V_{t}$ is generally not expressible in closed form, and the resulting algorithm does not look like FTRL. We solve the first problem by using a Normal approximation to the adversary’s future moves, and we solve the second by showing (3) can still be solved in closed form with respect to this approximation to $V_{t}$.

Potential Functions and the Duality of Reward and Regret

These views are of course closely connected, but can lead to somewhat different analysis techniques. Following the last view, suppose we interpret $q_{t}(\theta_{t})$ as the desired reward at the end of round $t$, given the adversary has played $\theta_{t}=-g_{1:t}$ so far. Then, if we can bound our actual final reward in terms of $q_{T}(\theta_{T})$, we also immediately get a regret bound stated in terms of the Fenchel conjugate $q_{T}^{*}$. Generalizing Streeter and McMahan [2012, Thm. 1], we have the following result (all omitted proofs can be found in the Appendix).

First we consider the minimax setting, where we define the game in terms of a convex benchmark $B$. Then, (2) gives us an immediate lower bound on the reward of the minimax strategy for the player (against any adversary), and so applying Theorem 1 with $\Psi=B$ gives

The fundamental point, of which we will make much use, is this: even if one only cares about the traditional definition of regret, the study of the minimax game defined in terms of a general comparator benchmark $B$ may be interesting, as the minimax algorithm for the player may then give novel bounds on regret. Note when $B$ is defined as in (1), the theorem implies $\forall u\in\mathcal{W},\ \operatorname{Regret}(u)\leq V$. More generally, even for non-minimax algorithms, Theorem 1 states that understanding the reward (equivalently, loss) of an algorithm as a function of the sum of gradients chosen by the adversary is both necessary and sufficient for understanding the regret of the algorithm.

Now we consider the potential function view. The following general bound for any sequence of plays $w_{t}$ against gradients $g_{t}$, for an arbitrary sequence of potential functions $q_{t}$, has been used numerous times (see Orabona [2013, Lemma 1] and references therein). The claim is that

where we take $\theta_{0}=\vec{0}$, and assume $q_{0}(\vec{0})=0$. In fact, this statement is essentially equivalent to the argument of (4) and (5). For intuition, we can view $q_{t}(\theta_{t})$ as the amount of money we wish to have available at the end of round $t$. Suppose at the end of each round $t$, we borrow an additional sum $\epsilon_{t}$ as needed to ensure we actually have $q_{t}(\theta_{t})$ on hand. Then, based on this invariant, the amount of reward we actually have after playing on round $t$ is $q_{t-1}(\theta_{t-1})+\langle w_{t},-g_{t}\rangle$, the money we had at the beginning of the round, plus the reward we get for playing $w_{t}$. Thus, the additional amount we need to borrow at the end of round $t$ in order to maintain the invariant is exactly

recalling $\theta_{t}=\theta_{t-1}-g_{t}$. Thus, if we can find bounds $\hat{\epsilon}_{t}$ such that for all $t$, $\theta_{t-1}$, and $g\in\mathcal{G}$,

we can re-state (7) as exactly (5) with $\Psi=q_{T}$ and $\hat{\epsilon}=\hat{\epsilon}_{1:T}$. Further, solving (8) for the per-round reward $\langle w_{t},-g_{t}\rangle$, summing from $t=1$ to $T$ and canceling telescoping terms gives exactly (4). Not surprisingly, both Theorem 1 and (7) can be proved in terms of the Fenchel-Young inequality.

When $T$ is known, and the $q_{t}$ are chosen carefully, it is possible to obtain $\hat{\epsilon}_{t}=0$. On the other hand, when $T$ is unknown to the players, typically we will need bounds $\hat{\epsilon}_{t}>0$. For example, in both Streeter and McMahan [2012, Thm. 6] and Orabona , the key is showing the sum of these $\hat{\epsilon}_{t}$ terms is always bounded by a constant. For completeness, we also state standard results where we interpret $q^{*}_{t}$ as a regularizer.

The updates of many algorithms are based on a time-varying version of the FTRL strategy,

where we view $q_{t}^{*}$ as a time-varying regularizer (see Orabona et al. and references therein). Regret bounds can be easily obtained using (7) when the regularizers $q^{*}_{t}(w)$ are increasing with $t$, and they are strongly convex w.r.t. a norm $\|\cdot\|_{*}$, using the fact that the potential functions $q_{t}$ will be strongly smooth. Then strong smoothness and particular choice of $w_{t}$ implies

where the last inequality follows from the fact that if $f(x)\leq g(x)$, then $f^{*}(y)\geq g^{*}(y)$ (immediate from the definition of the conjugate).

When the regularizer $q^{*}$ is fixed, that is, $q_{t}=q$ for all $t$ for some convex function $q$, we get the approach pioneered by Grove et al. and Kivinen and Warmuth :

where $D_{q}$ is the Bregman Divergence with respect to $q$, and we predict with $w_{t}=\nabla q(\theta_{t-1})$.

Admissible relaxations and potentials

We extend the notion of relaxations of the conditional value of the game of Rakhlin et al. to the present setting. We say $v_{t}$ with corresponding strategy $w_{t}$ is a relaxation of $V_{t}$ if

for constants $\hat{\epsilon}_{t}\geq 0$. This definition matches Eq. (4) of Rakhlin et al. if we force all $\hat{\epsilon}_{t}=0$, but if we allow some slack $\hat{\epsilon}_{t}$, (13) corresponds exactly to (8) and (9).

Note that (13) is invariant to adding a constant to all $v_{t}$. In particular, given an admissible $v_{t}$, we can define $q_{t}(\theta)=v_{t}(\theta)-v_{0}(\vec{0})$ so $q_{t}(\vec{0})=0$ and $q$ satisfies (9) with the same $\hat{\epsilon}_{t}$ values for which $v_{t}$ satisfies (13). Or we could define $q_{0}(\vec{0})=0$ and $q_{t}(\theta)=v_{t}(\theta)$ for $t\geq 1$, and take $\hat{\epsilon}_{1}\leftarrow\hat{\epsilon}_{1}+v_{0}(\vec{0})$ (or any other way of distributing the $v_{0}(\vec{0})$ into the $\hat{\epsilon}$). Generally, when $T$ is known we will find working with admissible relaxations $v_{t}$ to be most useful, while for unknown horizons $T$, potential functions with $q_{0}(\vec{0})=0$ will be more natural.

For our admissible relaxations, we have a result that closely mirrors Theorem 1:

Let $v_{0},\dots,v_{T}$ be an admissible relaxation for a benchmark $B$. Then, for any sequence $g_{1},\dots,g_{T}$, for any $w_{t}$ chosen so (13) and (12) are satisfied, we have

For the first statement, re-arranging and summing (13) shows $\operatorname{Reward}_{t}\geq v_{t}(\theta_{t})-\hat{\epsilon}_{1:t}-v_{0}(0)$ and so final $\operatorname{Reward}\geq B(\theta)-v_{0}(0)-\hat{\epsilon}_{1:T}$; the second result then follows from Theorem 1. ∎

The regret bound corresponds to (6); in particular, if we take $v_{t}$ to be the conditional value of the game, then (12) and (13) hold with equality with all $\hat{\epsilon}_{t}=0$. Note if we define $B$ as in (1), the regret guarantee becomes $\forall u\in\mathcal{W},\ \operatorname{Regret}(u)\leq v_{0}(0)+\hat{\epsilon}_{1:T},$ analogous to [Rakhlin et al., 2012, Prop. 1] when $\hat{\epsilon}_{1:T}=0$.

Deriving algorithms

Consider an admissible relaxation $v_{t}$. Given the form of the regret bounds we have proved, a natural strategy is to choose $w_{t+1}$ so as to minimize $\hat{\epsilon}_{t+1}$, that is,

following Rakhlin et al. [2012, Eq. (5)], Rakhlin et al. , and Streeter and McMahan [2012, Eq. (8)]. We see that $v_{t+1}$ is standing in for the conditional value of the game in (3). Since additive constants do not impact the argmin, we could also replace $v_{t}$ with a potential $q_{t}$, say $q_{t}(\theta)=v_{t}(\theta)-v_{0}(0)$.

Minimax Analysis Approaches for Known-Horizon Games

In general, the problem of calculating the conditional value of a game $V_{t}(\theta)$ is hard. And even for a known potential, deriving an optimal solution via (14) is also in general a hard problem. When the player is unconstrained, we can simplify the computation of $V_{t}$ and the derivation of optimal strategies. For example, following ideas from McMahan and Abernethy ,

where $\Delta(\mathcal{G})$ is the set of probability distributions on $\mathcal{G}$. McMahan and Abernethy shows that in some cases is possible to easily calculate this maximum, in particular when $\mathcal{G}=[-G,G]^{d}$ and $q_{t}$ decomposes on a per-coordinate spaces (that is, when the problem is essentially $d$ independent, one-dimensional problems).

In this section we will state two quite general cases where we can obtain the exact value of the game, even though the problem does not decompose on a per coordinate basis. Note that in both cases the optimal strategy for $w_{t+1}$ will be in the direction of $\theta_{t}$.

where $\theta\in\mathcal{H}$ is a fixed parameter. For results regarding this game, we let $H(w,g)=\langle w,g\rangle+h(\|\theta-g\|)$, $w^{*}=\operatorname*{arg\,min}_{w}\max_{g\in\mathcal{G}}H(w,g)$, and $g^{*}=\operatorname*{arg\,max}_{g\in\mathcal{G}}H(w^{*},g)$. Also, let $\hat{\theta}=\frac{\theta}{\|\theta\|}$ if $\|\theta\|\neq 0$, and $\vec{0}$ otherwise.

Note that $f_{t}(\|\theta\|)$ can be viewed as a smoothed version of $B(\theta)$, since $\sqrt{\|\theta\|^{2}+C}$ is a smoothed version of $\|\theta\|$ for a constant $C>0$. Moreover, $f_{0}(\|\theta\|)=B(\theta)$.

Let the adversary play from $\mathcal{G}=\{g:\|g\|\leq G\}$ and assume all the $f_{t}$ satisfy

Then the value of the game is $f(G\sqrt{T})$, the conditional value is $V_{t}(\theta)=f_{t}(\|\theta\|)=f_{t+1}(\sqrt{\|\theta\|^{2}+G^{2}})$, and the optimal strategy can be found using (14) on $V_{t}$.

Further, a sufficient condition for (16) is that $d>1$, $f$ is twice differentiable, and $f^{\prime\prime}(x)\leq f^{\prime}(x)/x$, for all $x>0$. In this case we also have that the minimax optimal strategy is

In this case, the minimax optimal strategy (20) is equivalent to the FTRL strategy in (10) with the time varying regularizer $V^{*}_{t}(w)$. The key lemma needed for the proof is the following:

Consider the game of (15). Then, if $d>1$, $h$ is twice differentiable, and $h^{\prime\prime}(x)\leq\frac{h^{\prime}(x)}{x}$ for $x>0$, we have:

Any $g^{*}$ such that $\left\langle\theta,g^{*}\right\rangle=0$ and $\|g^{*}\|=G$ is a minimax play for the adversary.

We defer the proofs to the Appendix (of the proofs in the appendix, the proof of Lemmas 5 and 8 are perhaps the most important and instructive). Since the best response of the adversary is always to play a $g^{*}$ orthogonal to $\theta$, we call this the case of the orthogonal adversary.

2 The case of the parallel adversary, and Normal approximations

We analyze a second case where (15) has closed-form solution, and hence derive a class of games where we can cleanly state the value of the game and the minimax optimal strategy. The results of McMahan and Abernethy can be viewed as a special case of the results in this section.

First, we introduce some notation. We write $\tau\equiv T-t$ when $T$ and $t$ are clear from context. We write $r\sim\{-1,1\}$ to indicate $r$ is a Rademacher random variable, and $r_{\tau}\sim\{-1,1\}^{\tau}$ to indicate $r_{\tau}$ is the sum of $\tau$ IID Rademacher random variables. Let $\sigma=\sqrt{\pi/2}$. We write $\phi$ for a random variable with distribution $N(0,\sigma^{2})$, and similarly define $\phi_{\tau}\sim N(0,(T-t)\sigma^{2})$. Then, define

and note $B(\theta)=f_{T}(\|\theta\|)=\hat{f}_{T}(\|\theta\|)$ since $\phi_{0}$ and $r_{0}$ are always zero. These functions are exactly smoothed version of the function $f$ used to define $B$. With these definitions, we can now state:

then $V_{t}(\theta)=f_{t}(\|\theta\|)$ is exactly the conditional value of the game, and (14) gives the minimax optimal strategy:

Similarly, suppose the $\hat{f}_{t}$ satisfy the equality (19) (with $\hat{f}_{t}$ replacing $f_{t}$). Then $q_{t}(\theta)=\hat{f}_{t}(\|\theta\|)$ is an admissible relaxation of $V_{t}$, satisfying (13) with $\hat{\epsilon}_{t}=0$, using $w_{t+1}$ based on (14). Further, a sufficient condition for (19) is that $d=1$, or $d>1$, the $f_{t}$ (or $\hat{f}_{t}$, respectively) are twice differentiable, and satisfy and $f_{t}^{\prime\prime}(x)\geq f_{t}^{\prime}(x)/x$ for all $x>0$.

Contrary to the case of the orthogonal adversary, the strategy in (20) cannot easily be interpreted as an FTRL algorithm. The proof is based on two lemmas. The first provides the key tool in supporting the Normal relaxation:

The latter two terms vanish, giving the stated inequality. ∎

The second lemma is used to prove the sufficient condition by solving the one-round game; again, the proof is deferred to the Appendix. Note that functions of the form $h(x)=g(x^{2})$, with $g$ convex always satisfies the conditions of the following Lemma.

Consider the game of (15). Then, if $d=1$, or if $d>1$, $h$ is twice differentiable, and $h^{\prime\prime}(x)>\frac{h^{\prime}(x)}{x}$ for $x>0$, then

Any $g^{*}$ that satisfies $|\langle\theta,g^{*}\rangle|=G\|\theta\|$ and $\|g^{*}\|=$G is a minimax play for the adversary.

The adversary can always play $g^{*}=G\frac{\theta}{\|\theta\|}$ when $\theta\neq\mathbf{0}$, and so we describe this as the case of the parallel adversary. In fact, inductively this means that all the adversary’s plays $g_{t}$ can be on the same line, providing intuition for the fact that this lemma also applies in the 1-dimensional case.

A Power Family of Minimax Algorithms

We analyze a family of algorithms based on potentials $B(\theta)=f(\|\theta\|)$ where $f(x)=\frac{W}{p}|x|^{p}$ for parameters $W>0$ and $p\in$, when the dimension is at least two. This is reminiscent of $p$-norm algorithms [Gentile, 2003], but the connection is superficial—the norm we use to measure $\theta$ is always the norm of our Hilbert space. Our main result is:

Let $d>1$ and $W>0$, and let $f$ and $B$ be defined as above. Define f_{t}(x)=\frac{W}{p}\big{(}x^{2}+(T-t)G\big{)}^{p/2}. Then, $f_{t}(\|\theta\|)$ is the conditional value of the game, and the optimal strategy is as in Theorem 4. If $p\in(1,2]$, letting $q\geq 2$ such that $1/p+1/q=1$, we have a bound

where the second inequality comes by taking $W=(G\sqrt{T})^{1-p}$. For all $u$, the bound \big{(}\tfrac{1}{p}+\tfrac{1}{q}\|u\|^{q}\big{)}G\sqrt{T} is minimized by taking $p=2$. For $p=1$, we have

Let $f(x)=\frac{W}{p}|x|^{p}$ for $p\in$, Then, $f^{\prime\prime}(x)\leq f^{\prime}(x)/x$, in fact basic calculations show $\frac{f^{\prime}(x)/x}{f^{\prime\prime}(x)}=\frac{1}{p-1}\geq 1$ when $p\leq 2$. Hence, we can apply Theorem 4, proving the claim on the $f_{t}$. The regret bounds can then be derived from Corollary 2, which gives $\operatorname{Regret}(u)\leq f^{*}(u)+f(G\sqrt{T}),$ noting $f^{*}(u)=\frac{W}{q}|\frac{u}{W}|^{q}$ when $p>1$. The fact that $p=2$ is an optimal choice in the first bound follows from the fact that $\frac{d}{dp}\left(\tfrac{1}{p}+\tfrac{1}{q}\|u\|^{q}\right)\leq 0$ for $p\in(1,2]$ with $q=\frac{p}{p-1}$. ∎

The $p=1$ case in fact exactly recaptures the result of Abernethy et al. [2008a] for linear functions, extending it also to spaces of dimension equal to two. The optimal update is $w_{t+1}=\triangledown f_{t}(\|\theta_{t}\|)=W\theta_{t}/\sqrt{\|\theta_{t}\|^{2}+G^{2}(T-t)}$. In addition to providing a regret bound for the comparator set $\mathcal{W}=\{u:\|u\|\leq W\}$, the algorithm will in fact only play points from this set.

for any $u$. In this case we see $W=\eta$ is behaving not like the radius of a comparator set, but rather as a learning rate. In fact, we have $w_{t+1}=\nabla V_{t}(\theta_{t})=\eta\theta_{t}=-\eta g_{1:t},$ and so we see this minimax-optimal algorithm is in fact constant-step-size gradient descent. Taking $\eta=\frac{1}{G\sqrt{T}}$ yields $\frac{1}{2}(\|u\|^{2}+1)G\sqrt{T}$. This result complements McMahan and Abernethy [2013, Thm. 7], which covers the $d=1$ case, or $d>1$ when the adversary plays from $\mathcal{G}=^{d}$.

Comparing the $p=1$ and $p>1$ algorithms reveals an interesting fact. For simplicity, take $G=1$. Then, the $p=1$ algorithm with $W=1$ is exactly the minimax optimal algorithm for minimizing regret against comparators in the $L_{2}$ ball (for $d>1$): the value of this game is $\sqrt{T}$ and we can do no better (even by playing outside of the comparator set). However, picking $p>1$ gives us algorithms that will play outside of the comparator set. While they cannot do better than $\sqrt{T}$, taking $G=1$ and $\|u\|=1$ shows that all algorithms in this family in fact achieve $\operatorname{Regret}(u)\leq\sqrt{T}$ when $\|u\|\leq 1$, matching the exact minimax optimal value. Further, the algorithms with $p>1$ provide much stronger guarantees, since they also give non-vacuous guarantees for $\|u\|>1$, and tighter bounds when $\|u\|<1$. This suggests that the $p=2$ algorithm will be the most useful algorithm in practice, something that indeed has been observed empirically (given the prevalence of gradient descent in real applications). This result also clearly demonstrates the value of studying minimax-optimal algorithms for different choices of the benchmark $B$, as this can produce algorithms that are no worse and in some cases significantly better than minimax algorithms defined in terms of regret minimization directly (i.e., via (1)).

The key difference in these algorithms is not how they play against a minimax optimal adversary for the regret game, but how they play against non-worst-case adversaries. In fact, a simple induction based on Lemma 5 shows that any minimax-optimal adversary will play so that $\sqrt{\|\theta_{t}\|^{2}+G^{2}(T-t)}=G\sqrt{T}$. Against such an adversary, the $p=1$ algorithm is identical to the $p=2$ algorithm with learning rate $\eta=\frac{1}{G\sqrt{T}}$. In fact, using the choice of $W$ from Corollary 9, all of these algorithms play identically against a minimax adversary for the regret game.

Tight Bounds for Unconstrained Learning

In this section we analyze algorithms based on benchmarks and potentials of the form $\exp(\|\theta\|^{2}/t)$, and show they lead to a minimal dependence on $\|u\|$ in the corresponding regret bounds for a given upper bound on regret against the origin (equal to the loss of the algorithm).

First, we derive a lower bound for the known $T$ game. Using Lemma 14 in the Appendix, we can show that the $B(\theta)=\exp(\|\theta\|^{2}/T)$ benchmark approximately corresponds to a regularizer of the form $\|u\|\sqrt{T\log(\sqrt{T}\|u\|+1)}$; there is actually some technical challenge here, as the conjugate $B^{*}$ cannot be computed in closed form—the given regularizer is an upper bound. This kind of regularizer is particularly interesting because it is related to parameter-free sub-gradient descent algorithms [Orabona, 2013]; a similar potential function was used for a parameter-free algorithm by [Chaudhuri et al., 2009]. The lower bound for this game was proven in Streeter and McMahan for 1-dimensional spaces, and Orabona extended it to Hilbert spaces and improved the leading constant. We report it here for completeness.

Fix a non-trivial Hilbert space $\mathcal{H}$ and a specific online learning algorithm. If the algorithm guarantees a zero regret against the competitor with zero norm, then there exists a sequence of $T$ cost vectors in $\mathcal{H}$, such that the regret against any other competitor is $\Omega(T)$. On the other hand, if the algorithm guarantees a regret at most of $\epsilon>0$ against the competitor with zero norm, then, for any $0<\eta<1$, there exists a $T_{0}$ and a sequence of $T\geq T_{0}$ unitary norm vectors $g_{t}\in\mathcal{H}$, and a vector $u\in\mathcal{H}$ such that

Consider the game with fixed known $T$, an adversary that plays from $\mathcal{G}=\{g\in\mathcal{H}\mid\|g\|\leq G\}$, and

for constants $a>1$ and $\epsilon>0$. We will show that we are in the case of the parallel adversary, Section 4.2. Both computing the $f_{t}$ based on Rademacher expectations and evaluating the sufficient condition for those $f_{t}$ appear quite difficult, so we turn to the Normal approximation. We then have

where we have computed the expectation in a closed form for the second equality. One can quickly verify that it satisfies the hypothesis of Theorem 6 for $a>G^{2}\pi/2$, hence $q_{t}(\theta)=\hat{f}_{t}(\|\theta\|)$ will be an admissible relaxation. Thus, by Corollary 2, we immediately have

and so by Lemma 14 in the Appendix, we can state the following Theorem, that matches the lower bound up to a constant multiplicative factor.

Let $a>G^{2}\pi/2$, and $\mathcal{G}=\{g:\|g\|\leq G\}$. Denote by $\hat{\theta}=\frac{\theta}{\|\theta\|}$ if $\|\theta\|\neq 0$, and $\vec{0}$ otherwise. Fix the number of rounds $T$ of the game, and consider the strategy

Then, for any sequence of linear costs $\{g_{t}\}_{t=1}^{T}$, and any $u\in\mathcal{H}$, we have

2 AdaptiveNormal: an adaptive algorithm for unknown T𝑇T

Our techniques suggest the following recipe for developing adaptive algorithms: analyze the known $T$ case, define a potential $q_{t}(\theta)\approx V_{T}(\theta)$, and then analyze the incrementally-optimal algorithm for this potential (14) via Theorem 1. We follow this recipe in the current section. Again consider the game where an adversary that plays from $\mathcal{G}=\{g\in\mathcal{H}\mid\|g\|\leq G\}$. Define the function $f_{t}$ as

where $a>\frac{3\pi G^{2}}{4}$, and the $\beta_{t}$ is a decreasing sequence that will be specified in the following. From this, we define the potential $q_{t}(\theta)=f_{t}(\|\theta\|^{2}).$ Suppose we play the incrementally-optimal algorithm of (14). Using Lemma 8 we can write the minimax value for the one-round game,

Using Lemma 17 in the Appendix and our hypothesis on $a$, we have that the RHS of this inequality is maximized for $\|\theta_{t}\|=0$. Hence, using the inequality $\sqrt{a+b}\leq\sqrt{a}+\frac{b}{2\sqrt{a}},\forall a,b>0$, we get

Thus, choosing $\beta_{t}=\epsilon/\log^{2}(t+1)$, for example, is sufficient to prove that $\epsilon_{1:T}$ is bounded by $\epsilon\frac{\pi G^{2}}{a}$ [Baxley, 1992]. Hence, again using Corollary 2 and Lemma 14 in the Appendix, we can state the following Theorem.

Let $a>3G^{2}\pi/4$, and $\mathcal{G}=\{g:\|g\|\leq G\}$. Denote by $\hat{\theta}=\frac{\theta}{\|\theta\|}$ if $\|\theta\|\neq 0$, and $\vec{0}$ otherwise. Consider the strategy

Then, for any sequence of linear costs $\{g_{t}\}_{t=1}^{T}$, and any $u\in\mathcal{H}$, we have

References

Appendix A Proofs

Suppose the algorithm provides the reward guarantee (4). First, note that for any comparator $u$, by definition we have

Then, applying the definitions of Reward, Regret, and the Fenchel conjugate, we have

For the other direction, assuming (5), we have for any comparator $u$,

Alternatively, one can prove this from the Fenchel-Young inequality. ∎

A.2 Proof of Lemma 3

We have $B^{*}(u)=\sup_{\theta}\left\langle u,\theta\right\rangle-f(\|\theta\|)$. If $\|u\|=0$, the stated equality is correct, in fact

Hence we can assume $\|u\|\neq 0$, and by inspection we can take $\theta=\alpha u/\|u\|$, with $\alpha\geq 0$, and so

A.3 Proof of Theorem 4

First we show that if $f$ satisfies the condition on the derivatives, the same conditions is satisfied by $f_{t}$, for all t. We have that all the $f_{t}$ have the form $h(x)=f(\sqrt{x^{2}+a})$, where $a\geq 0$. Hence we have to prove that $\frac{xh^{\prime\prime}(x)}{h^{\prime}(x)}\leq 1$. We have that $h^{\prime}(x)=\frac{xf^{\prime}(\sqrt{x^{2}+a})}{\sqrt{x^{2}+a}}$, and $h^{\prime\prime}(x)=\frac{x^{2}f^{\prime\prime}(\sqrt{x^{2}+a})+\frac{a}{\sqrt{x^{2}+a}}f^{\prime}(\sqrt{x^{2}+a})}{x^{2}+a}$, so

where in the inequality we used the hypothesis on the derivatives of $f$.

We show $V_{t}$ has the stated form by induction from $T$ down to 0. The base case for $t=T$ is immediate. For the induction step, we have

The sufficient condition for (16) follow immediately from Lemma 5. ∎

A.4 Proof of Theorem 6

First, we need to show the functions $f_{t}$ and $\hat{f}_{t}$ of (18) are even. Let $r$ be a random variable draw from any symmetric distribution. Then, we have

where we have used the fact that $|\cdot|$ is even and the symmetry of $r$.

We show $f_{t}(\|\theta\|)=V_{t}(\theta)$ inductively from $t=T$ down to $t=0$. The base case $T=t$ follows from the definition of $f_{t}$. Then, suppose the result holds for $t+1$. We have

where the last two lines follow from the definition of $f_{t}$ and $f_{t+1}$. The case for $\hat{f}_{t}$ is similar, using the hypothesis of the Theorem we have

where in the inequality we used Lemma 7, and in the second equality the definition of $\hat{f}_{t}$. Hence, $q_{t}(\theta)=\hat{f}_{t}(\|\theta\|)$ satisfy (13) with $\hat{\epsilon}_{t}=0$. Finally, the sufficient conditions come immediately from Lemma 8. ∎

A.5 Analysis of the one-round game: Proofs of Lemmas 5 and 8

In the process of proving these lemmas, we also show the following general lower bound:

Under the same definitions as in Lemma 5, if $d>1$, we have

We now proceed with the proofs. The $d=1$ case for Lemma 8 was was proved in McMahan and Abernethy .

Before proving the other results, we simplify a bit the formulation of the minimax problem. For the other results, the maximization wrt $g$ of a convex function is always attained when $\|g\|=G$. Moreover, in the case of $\|\theta\|=0$ the other results are true, in fact

Hence, without loss of generality, in the following we can write $w=\alpha\frac{\theta}{\|\theta\|}+\hat{w}$, where $\left\langle\hat{w},\theta\right\rangle=0$. It is easy to see that in all the cases the optimal choice of $g$ turns out to be $g=\beta\frac{\theta}{\|\theta\|}+\gamma\hat{w}$, where $\gamma\geq 0$. With these settings, the minimax problem is equivalent to

By inspection, the player can always choose $\hat{w}=\mathbf{0}$ so $\gamma\|\hat{w}\|^{2}=0$. Hence we have a simplified and equivalent form of our optimization problem

For Lemma 13, it is enough to set $\beta=0$ in (22).

For Lemma 5, we upper bound the minimum wrt to $\alpha$ with the specific choice of $\alpha$. In particular, we set $\alpha=\frac{\|\theta\|}{\sqrt{\|\theta\|^{2}+G^{2}}}h^{\prime}\left(\sqrt{\|\theta\|^{2}+G^{2}}\right)$ in (22), and get

The derivative of argument of the max wrt $\beta$ is

We have that if $\beta=0$ the first derivative is 0. Using the hypothesis on the first and second derivative of $h$, we have that the second term in (23) increases in $\beta$. Hence $\beta=0$ is the maximum. Comparing the obtained upper bound with the lower bound in Lemma 13, we get the stated equality.

For Lemma 8, the second derivative wrt $\beta$ of the argument of the minimax problem in (22) is

that is non negative, for our hypothesis on the derivatives of $h$. Hence, the argument of the minimax problem is convex wrt $\beta$, hence the maximum is achieved at the boundary of the domains, that is $\beta^{2}=G^{2}$. So, we have

The argmin of this quantity wrt to $\alpha$ is obtained when the the two terms in the max are equal, so we obtained the stated equality.

A.6 Lemma 14

Define $f(\theta)=\beta\exp{\frac{\|\theta\|^{2}}{2\alpha}}$, for $\alpha,\beta>0$. Then

From the definition of Fenchel dual, we have

where $\theta^{*}=\operatorname*{arg\,max}_{\theta}\langle\theta,w\rangle-f(\theta)$. We now use the fact that $\theta^{*}$ satisfies $w=\nabla f(\theta^{*})$, that is

in other words we have that $\theta^{*}$ and $w$ are in the same direction. Hence we can set $\theta^{*}=qw$, so that $f^{*}(w)\leq q\|w\|^{2}-\beta$. We now need to look for $q>0$, solving

Using the elementary inequality $\log x\leq\frac{m}{e}x^{\frac{1}{m}},\forall m>0$, we have

We set $m$ such that $\sqrt{\frac{e}{2m}}\frac{\|w\|\sqrt{\alpha}}{\beta}=\sqrt{e}$, that is $\frac{1}{2}\left(\frac{\|w\|\sqrt{\alpha}}{\beta}\right)^{2}=m$. Hence we have $\log\sqrt{\frac{e}{2m}}\frac{\|w\|\sqrt{\alpha}}{\beta}=\frac{1}{2}$ and $\frac{\frac{\|w\|\sqrt{\alpha}}{\beta}}{\sqrt{2m}}=1$, and obtain

A.7 Lemma 17

Let $f(x)=b\exp\left(\frac{x^{2}}{a}\right)-\exp\left(\frac{x^{2}}{c}\right)$. If $a\geq c>0$, $b\geq 0$, and $b\,c\leq a$, then the function $f(x)$ is decreasing for $x\geq 0$.

The proof is immediate from the study of the first derivative. ∎

Let $f(t)=\frac{a^{\frac{3}{2}}\,t\,\sqrt{t+1}}{(a\,(t+1)-b)^{\frac{3}{2}}}$, with $a\geq 3/2b>0$. Then $f(t)\leq 1$ for any $t\geq 0$.

The sign of the first derivative of the function has the same sign of

hence from the hypothesis on $a$ and $b$ the function is strictly increasing. Moreover the asymptote for $t\rightarrow\infty$ is 1, hence we have the stated upper bound. ∎

Let $f_{t}(x)=\beta_{t}\exp\left(\frac{x}{2at}\right)$, $\beta_{t+1}\leq\beta_{t},\ \forall t$. If $a\geq\frac{3\pi G^{2}}{4}$, then

The function is even, so we have a maximum in zero iff the function is decreasing for $x>0$. Observe that, from Lemma 16, for any $t\geq 0$

Hence, using Lemma 15, we obtain that the stated result. ∎