<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Online Learning Algorithms</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>2021</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10208409</idno>
					<idno type="doi">10.1146/annurev-statistics-040620-035329</idno>
					<title level='j'>Annual review of statistics and its application</title>
<idno>2326-8298</idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>Nicolò Cesa-Bianchi</author><author>Francesco Orabona</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[Online learning is a framework for the design and analysis of algorithms that build predictive models by processing data one at the time. Besides being computationally efficient, online algorithms enjoy theoretical performance guarantees that do not rely on statistical assumptions on the data source. In this survey, we describe some of the most important algorithmic ideas behind online learning and explain the main mathematical tools for their analysis. Our reference framework is online convex optimization, a sequential version of convex optimization within which most online algorithms are formulated. More specifically, we provide an in-depth description of Online Mirror Descent and Follow the Regularized Leader, two of the most fundamental algorithms in online learning. As the tuning of parameters is a typically difficult task in sequential data analysis, in the last part of the survey we focus on coin-betting, an information-theoretic approach to the design of parameter-free online algorithms with good theoretical guarantees.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.">INTRODUCTION</head><p>The growing success of technologies based on machine learning is driven by the availability of massive data sets in digital format. Processing these large amounts of data poses computational challenges that are not always properly addressed by traditional statistical learning methods. For this reason, online or sequential learning, a framework specifically designed to cope with big data scenarios, has become a key tool in machine learning applications. Online algorithms go through the data points sequentially, using each new data point to adjust their predictive model or estimator. Typically, this adjustment is "local", as it only involves the current model and the new data point. As each data point is often processed in constant time, this results in an overall running time scaling linearly with the number of data points. Besides the computational advantage, there are more reasons for which sequential learning may be preferred over other approaches. In many application domains-such as online advertising, digital markets, sensor networks, mobile user applications-new data are generated at high rates. In these cases, the sequential adaptation process of online learning has the potential of capturing subtle nonstationary features of the unknown data source.</p><p>A fundamental issue in machine learning is what mathematical assumptions on data sources are reasonable to make. Online learning advocates an approach in which the source is viewed as an arbitrary and unknown deterministic process. This is a radical departure from classical statistical approaches to sequential decision-making-such as Bayesian decision theory <ref type="bibr">(Berger 2013)</ref> or Markov decision processes <ref type="bibr">(Puterman 2014</ref>)-and finds its roots in the pioneering works on repeated games by <ref type="bibr">Robbins (1951)</ref>, <ref type="bibr">Hannan (1957)</ref>, and <ref type="bibr">Blackwell (1956)</ref>, where the data source consists of the opponent's plays in a two-person game. The theme of predicting individual, deterministic sequences also surfaced in other disciplines, including information theory <ref type="bibr">(Cover 1965</ref><ref type="bibr">, Feder et al. 1992)</ref>, and computer science <ref type="bibr">(Borodin &amp; El-Yaniv 2005)</ref>. More recently, some of the online learning techniques-like exponential weighted aggregation-have also appeared in the statistical literature (see, e.g., <ref type="bibr">Dalalyan &amp; Tsybakov 2008</ref><ref type="bibr">, Dalalyan et al. 2012</ref><ref type="bibr">, Rigollet et al. 2012)</ref>.</p><p>Stripping the data source of any statistical assumption allows to define a crisp, minimalistic framework for investigating the notion of algorithmic learning, where only the empirical properties of the observed data sequence matter. A substitute for the notion of statistical risk must then be introduced to define a notion of minimax optimality over the sequence of losses in a mathematically rigorous way. In view of that, one should note that in online learning we never measure the predictive power of a single model, but rather consider the ensemble of models sequentially generated by the online learner while processing a data sequence. The notion of risk that we use to evaluate this ensemble is appropriately called sequential risk, and measures the extent to which each model generated by the algorithm is able to predict the next element in the sequence. Sequential risk is thus associated with the behavior of an algorithm on an individual data sequence. Based on sequential risk, we then derive the notion of regret, which can be viewed as the online counterpart of the statistical excess risk measured with respect to a class of predictive models. The control of regret is the main goal in the analysis of online learning algorithms.</p><p>In the rest of this survey, we introduce and describe some of the most fundamental online learning algorithms. Our goal is to explain the behavior of these algorithms through the analysis of their regret. Therefore, rather than going through as many as possible of the existing approaches to online learning, we prefer to focus on the conceptual foundations and the main proof techniques. We believe this is a more effective way to keeping alive the interest of someone who wants to know more about this exciting field of research.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.1.">Online convex optimization</head><p>The standard framework for the study of parametric online learning with convex losses<ref type="foot">foot_0</ref> is known as Online Convex Optimization, or OCO (see, e.g., Shalev-Shwartz 2012, <ref type="bibr">Hazan 2016</ref><ref type="bibr">, McMahan 2017</ref><ref type="bibr">, Orabona 2019</ref>). While it is also possible to design and study nonparametric online learning algorithms, (e.g., <ref type="bibr">Hazan &amp; Megiddo 2007</ref><ref type="bibr">, De Rosa et al. 2015</ref><ref type="bibr">, Kuzborskij &amp; Cesa-Bianchi 2017)</ref>, we focus here on the more common parametric setting.</p><p>As we said earlier, the data-generating mechanism of online learning is an unknown and deterministic process. In OCO, the data process is replaced by a deterministic sequence of unknown and convex loss functions &#8467;t, evaluating the performance of the models incrementally generated by the algorithm. For example, if we want to cast linear regression in the OCO framework, then the loss functions &#8467;t take the form &#8467;t(w) = w &#8868; xt -yt 2 , where w &#8712; R d is a linear prediction model and (x1, y1), (x2, y2), . . . &#8712; R d &#215; R is the underlying deterministic data sequence.</p><p>Throughout the paper, the model space X is a convex, closed, and nonempty subset of R d , while a loss function is any nonnegative and convex function &#8467;t : X &#8594; R. For any sequence &#8467;1, &#8467;2, . . . of loss functions, an online learner A is a sequence A1, A2, . . . of mappings with range X. The learner's model at time t is wt = At-1(&#8467;1, . . . , &#8467;t-1), where w1 = A1 &#8712; X is the default initial model, and the learner's loss at time t is &#8467;t(wt). While the notation wt = At-1(&#8467;1, . . . , &#8467;t-1) highlights the fact that wt+1 can depend on all the past losses, we are especially interested in cases where the update wt &#8594; wt+1 can be done efficiently based only on wt and &#8467;t. Also, for certain applications it makes sense to consider special cases of this framework, where additional assumptions besides convexity are made on the loss functions.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.2.">Regret and sequential risk</head><p>The performance of the learner is measured according to the regret</p><p>Online learning is concerned with the design of algorithms for which RT (u) grows sublinearly in T for all u &#8712; X and irrespective to the loss sequence (the so-called no-regret property).</p><p>The quantity 1 T T t=1 &#8467;t(wt) is sometimes called sequential risk (as opposed to the classical statistical risk), thus sublinear regret implies that the excess sequential risk</p><p>converges to zero for any u &#8712; X.</p><p>Algorithms that enjoy the no-regret property can also be used to solve convex optimization problems min w&#8712;X f (w), which are viewed as instances of OCO with &#8467;t = f for all t. Indeed, Jensen's inequality shows that</p><p>where w = 1 T w1 + &#8226; &#8226; &#8226; + wT is the average of the iterates wt and w &#8902; is the minimizer of f in X. Similarly, we may also consider stochastic optimization problems min w&#8712;X E F (w, &#969;) , where the random variable F (w, &#8226;) is the stochastic objective and F (&#8226;, &#969;) is convex for all &#969; &#8712; &#8486;. Given access to i.i.d. draws &#969;1, &#969;2, . . ., we can solve stochastic optimization problems using a no-regret algorithm run with &#8467;t(w) = F (w, &#969;t). Let w &#8902; &#8712; argmin w&#8712;X E F (w, &#969;) and observe that, using Jensen's inequality once more,</p><p>In machine learning, stochastic optimization is typically used to solve empirical risk minimization problems</p><p>where z1, . . . , zm is a dataset and F (w, zi) measures the loss of w on the data point zi. If F (&#8226;, z) is convex for all z, then we may set &#8467;t = F (&#8226;, Zt), where Z1, Z2, . . . are i.i.d. uniform draws from the dataset.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.3.">Lower bounds</head><p>Consider the easy case when X is a bounded 2 set with diameter D and all losses &#8467;t are Lipschitz on X, how well can we control the regret RT in this scenario? It turns out that the worst case for OCO occurs when all loss functions are linear. Interestingly, the proof uses a stochastic rather than deterministic loss process. More specifically, let v1, v2 &#8712; X such that v1 -v2 2 = D and define z0</p><p>. Stochastic losses L1, L2, . . . are defined by Lt(w) = &#949;tL z &#8868; 0 w, where &#949;1, &#949;2, . . . are independent Rademacher random variables, i.e., P(&#949;t = 1) = P(&#949;t = -1) = 1 2 , and L &gt; 0 is the Lipschitz constant for all the losses. Now, fix any algorithm for OCO. Clearly, its regret satisfies max</p><p>where the expectation is with respect to the random draw of &#949;1, . . . , &#949;T . Moreover, since E Lt(w) = 0 for all w, we have</p><p>Now, using the elementary identity max{a, b} = 1 2 a + b + |a -b| and Khintchine inequality (see, e.g., <ref type="bibr">Cesa-Bianchi &amp; Lugosi 2006, Lemma 8.2)</ref> we obtain that the right-hand side of ( <ref type="formula">2</ref>) is equal to</p><p>where the equality is proven using z &#8868; 0 (v1 -v2) = D due to our choice of z0. This shows that we cannot expect the regret to grow slower that LD &#8730; T -where D is the Euclidean diameter of X and L is the Lipschitz constant of the loss-unless the two main parameters of our setting, that is the model space X and the loss process &#8467;1, &#8467;2, . . ., enjoy some additional properties.</p><p>Lower bounds arguments based on the Khintchine inequality are rather common in online learning, see <ref type="bibr">Luo et al. (2016, Theorem 1)</ref> for an example close to the one presented here. The effectiveness of stochastic loss sequences to prove tight lower bounds in OCO settings in not accidental. To gain a better understanding of the connections between stochastic and online learning, see <ref type="bibr">Rakhlin &amp; Sridharan (2014)</ref> who study online learning as a minimax problem.</p><p>The game-theoretic roots of OCO are described by <ref type="bibr">Cesa-Bianchi &amp; Lugosi (2006)</ref>. Since then, the interface between sequential optimization, game theory, and statistics has been intensively explored in many works, see the tutorial and surveys by <ref type="bibr">Shalev-Shwartz (2007)</ref>, <ref type="bibr">Hazan (2016</ref><ref type="bibr">), McMahan (2017</ref><ref type="bibr">), Orabona (2019)</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">ONLINE MIRROR DESCENT</head><p>We now introduce the most popular algorithm for OCO, Online Mirror Descent (or OMD for short). OMD is the online version of the Mirror Descent algorithm of <ref type="bibr">Nemirovsky &amp; Yudin (1983)</ref> for convex optimization. Mirror Descent is based on a generalization of projected gradient descent in which distances in the model space X are not necessarily measured using the Euclidean norm. This allows to take advantage of specific geometrical properties that X may have. To see how this is done, we start from the iterates wt+1 = &#928; X wt -&#951;t&#8711;F (wt) of projected gradient descent on a convex and differentiable objective F : R d &#8594; R, where &#928; X denotes the Euclidean projection onto X and &#951;t &gt; 0 is the step size at time t. The expression defining the iterates can be rewritten in an equivalent optimization form,</p><p>Mirror Descent replaces the Euclidean norm in the above equation with a generalized distance, or divergence D,</p><p>Following <ref type="bibr">Beck &amp; Teboulle (2003)</ref>, the divergences used by Mirror Descent are parameterized by mirror map functions &#968; : X &#8594; R that are strictly convex and continuously differentiable on the interior of X. Given such a &#968;, the Bregman divergence</p><p>Note that D &#968; is not necessarily symmetric and, since &#968; is strictly convex, is always nonnegative and equals zero only when w = u. When &#968; is also twice differentiable, then Taylor's theorem shows that</p><p>for some z on the line segment joining u and w. In other words, for &#968; that are twice differentiable the divergence locally behaves like a squared Mahalanobis distance. Just like in the Euclidean case, we can also write the Mirror Descent update (4) using a Bregman projection (see, e.g., Bubeck 2015, Section 4).</p><p>The online version of Mirror Descent is now straightforward to obtain. In order to avoid considering iterates wt on the boundary of X, where D &#968; (&#8226;, wt) is not defined, we restrict the argmin in (4) to a convex and nonempty subset V &#8838; int X and, consequently, measure the regret RT (u) only for u &#8712; V. Let w1 &#8712; V and fix a sequence &#951;1 &#8805; &#951;2 &#8805; &#8226; &#8226; &#8226; &gt; 0 of step sizes. Now, for any sequence &#8467;1, &#8467;2, . . . of differentiable loss functions, the iterates of OMD are defined by</p><p>where gt = &#8711;&#8467;t(wt). The differentiability assumption for the losses &#8467;t can be relaxed to subdifferentiability, in which case gt is any element of the subdifferential of &#8467;t at wt. This is useful because some popular loss functions, like the hinge loss &#8467;t(wt) = max 0, 1-ytw &#8868; xt for binary classification (yt &#8712; {-1, 1}), are not everywhere differentiable. In the rest of this survey, we use the same notation gt to denote &#8711;&#8467;t(wt) or any subgradient of &#8467;t at wt, according to whether &#8467;t is differentiable or only subdifferentiable. One might wonder why using a linear approximation w &#8868; gt instead of the loss &#8467;t(w) in the update of OMD. Indeed, the variant where &#8467;t(w) replaces w &#8868; gt is called proximal point method in the convex optimization literature and implicit update in the online learning literature, see <ref type="bibr">Kivinen &amp; Warmuth (1997)</ref>, <ref type="bibr">Kulis &amp; Bartlett (2010)</ref> and also <ref type="bibr">McMahan (2017, Section 6)</ref>. Connections between implicit updates and optimistic updates in saddle point optimization problems were investigated by <ref type="bibr">Mokhtari et al. (2019)</ref>, see also Section 3 of this survey. We now look at two important choices for the mirror map.</p><p>2 and the OMD update become the online version of gradient descent (OGD) with Euclidean projection, wt+1 = &#928; V (wt -&#951;tgt).</p><p>Entropic. If X is the simplex of probability distributions over {1, . . . , d} and &#968; is the negative entropy &#968;(w) = i wi ln wi, then D &#968; (u, w) = i ui ln u i w i is the Kullback-Leibler divergence (or cross-entropy) and the OMD update becomes the Exponentiated Gradient (EG) algorithm of <ref type="bibr">Kivinen &amp; Warmuth (1997)</ref>,</p><p>where gt,i are the components of the gradient gt. As in this case lim</p><p>where bd X is the boundary of X, we can measure the regret RT (u) against u &#8712; X instead of restricting to u &#8712; V &#8838; int X. In fact, under the latter condition the update rule of OMD will never return a point on the boundary of X. For instance, when losses are linear, t &#8467;t is always minimized at a u located on a corner of the simplex, and we can show that EG (OMD with entropic mirror map) has vanishing regret with respect to any u in the simplex X, including the corners.</p><p>We now look at a different interpretation of the update rule of OMD. First, let a differentiable function f :</p><p>Mirror maps &#968; that are &#181;-strongly convex with respect to a norm &#8226; define Bregman divergences that grow faster than the square of the same norm, i.e., D &#968; (u, w) &#8805; &#181; 2 uw 2 . For strongly convex mirror maps, an equivalent way of writing ( <ref type="formula">5</ref></p><p>Strong convexity ensures that &#968; &#8902; V is differentiable and that &#8711;&#968; &#8902; V is the functional inverse of &#8711;&#968; V . The function &#968; V maps the iterates wt to the dual space of gradients where a gradient step is performed. The inverse function &#968; &#8902; V maps back to the primal space of iterates. See Figure <ref type="figure">1</ref> for a picture illustrating the OMD update. Going back to the previous examples, we see that &#968; = 1 2 &#8226; 2 2 = &#968; &#8902; . When &#968; is the negative entropy we instead have that</p><p>We now move on to analyze the regret of OMD, and show us how the change of geometry caused by the choice of the strongly convex mirror map &#968; affects the algorithm's performance. The first step in bounding the regret RT (u) consists in linearizing the loss using convexity, &#8467;t(wt) -&#8467;t(u) &#8804; g &#8868; t wtu , recall that gt = &#8711;&#8467;t(wt) for differentiable losses. We call linearized regret the resulting upper bound on RT (u). Next, using the properties of the optimization form for the OMD iterates (4), and the &#181;-strong convexity of the mirror map with respect to &#8226; , it takes a few steps to prove that</p><p>where &#8226; &#8902; is the dual norm of &#8226; . Now, dividing both sides by &#951;t &gt; 0 and summing over Next, consider EG, where V is the probability simplex and &#968;(w) = i wi ln wi, which is 1-strongly convex with respect to &#8226; 1 . Here, we run into a problem because the diameter of the simplex is unbounded when measured using the cross-entropy (i.e., the Bregman divergence D &#968; corresponding to the entropic mirror map). This prevents us from obtaining a constant upper bound D 2 on maxt D &#968; (u, wt). We can fix this by choosing a constant step size &#951;, which allows us to transform the regret guarantee (8) into the following alternative bound,</p><p>Under the same assumption gt &#8734; &#8804; G as before, we get</p><p>Using the squared Euclidean norm in the same setting would instead give RT (u) &#8804; 2G &#8730; dT . Note that for linear losses the quantity G (T ln d)/2 is asymptotically minimax, including constants (see <ref type="bibr">Cesa-Bianchi &amp; Lugosi 2006, Corollary 8.3)</ref>. This shows the importance of matching the mirror map to the geometry of the model space. From a practical point of view, the logarithmic dependence on d in the regret guarantees that EG is robust to a large number of irrelevant features.</p><p>When the convex losses &#8467;t are induced by pairs (xt, yt), as in &#8467;t(w) = w &#8868; xt -yt 2 , then loss gradients &#8711;&#8467;t(w) are proportional to data points xt. In this case, bounds on RT (u) for OGD and EG depend on different products of dual norms: maxt xt 2 u 2 for OGD and</p><p>, neither bound dominates. However, for sparse u, u 1 approaches u &#8734; and EG performs better than OGD.</p><p>The analysis of OGD can be easily adapted to derive a regret bound for the Perceptron algorithm of <ref type="bibr">Rosenblatt (1958)</ref> for binary classification, without need of assuming linear separability of the data sequence (see <ref type="bibr">Freund &amp; Schapire 1999)</ref>. In the special case of separable data sequences, the regret bound reduces to the result originally proven in the well-known Perceptron Convergence Theorem <ref type="bibr">(Block 1962</ref><ref type="bibr">, Novikoff 1963)</ref>.</p><p>If the loss functions are known to be &#181;-strongly convex and L-Lipschitz in V, then the step size of OGD can be set more aggressively to &#951;t = 1 &#181;t so to exploit the curvature. The resulting bound on the regret is</p><p>Note that there is no dependence on the diameter of the model space in this bound, but only on the gradients of the losses (through the Lipschitz constant L). Many machine learning algorithms, including Support Vector Machines <ref type="bibr">(Cortes &amp; Vapnik 1995)</ref>, can be trained using stochastic optimization over a training set of data points z1, . . . , zm to minimize a strongly convex functional F , see (1). A prime example of a stochastic gradient descent algorithm is OGD run on the sequence of strongly convex losses &#8467;t = F (&#8226;, Zt), where Zt is drawn at random from the dataset. The regret analysis of OGD with strongly convex losses can be used to obtain rates of convergence to the minimum of F in (1). This is done, for example, to analyze the Pegasos algorithm of Shalev-Shwartz et al. ( <ref type="formula">2011</ref>).</p><p>The EG algorithm is an instance of the multiplicative update method, a technique that found applications in computer science <ref type="bibr">(Littlestone &amp; Warmuth 1994)</ref>, game theory <ref type="bibr">(Fudenberg &amp; Levine 1995)</ref>, information theory, statistics, and other disciplines (see, e.g., <ref type="bibr">Cesa-Bianchi &amp; Lugosi 2006</ref><ref type="bibr">, Arora et al. 2012b</ref>). In the special case of linear losses with uniformly bounded coefficients, EG is known as the Hedge algorithm <ref type="bibr">(Freund &amp; Schapire 1997)</ref> and the corresponding setting is known as prediction with expert advice <ref type="bibr">(Cesa-Bianchi et al. 1997)</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1.">The AdaGrad algorithm</head><p>A variant of OMD that has become of widespread use as a stochastic gradient descent algorithm for training neural networks is the AdaGrad algorithm, independently introduced by <ref type="bibr">McMahan &amp; Streeter (2010)</ref> and <ref type="bibr">Duchi et al. (2011)</ref>. For simplicity, we look at the socalled diagonal version of AdaGrad, which uses a coordinate-dependent step size.</p><p>Let</p><p>and Di = bi -ai for i = 1, . . . , d. AdaGrad runs OMD with mirror map &#968; = 1 2 &#8226; 2 and projection onto V. The iterates, including the projection step, can be written as wt+1,i = max min{wt,i -&#951;t,igt,i}, ai for i = 1, . . . , d and an arbitrary initial point w1 &#8712; V. The components of the step size are chosen as</p><p>The regret analysis is straightforward: after linearizing the losses so that &#8467;t(wt) -&#8467;t(u) &#8804; g &#8868; t wtu , one can simply perform the standard OMD analysis independently for each coordinate. By applying the bound (9) on each coordinate, and then summing over coordinates, we obtain</p><p>We can compare this bound to (9) with &#181; = 1 and &#8226; &#8902; = &#8226; 2 . For simplicity, we take V to be the hypercube with Di = 1, so that D in ( <ref type="formula">9</ref>) is equal to</p><p>gt 2 2 where (9) appears in the right-hand side and (11) appears in the middle. Hence, ignoring the fact that the sequence of realized subgradients gt is different for the two algorithms, with this choice of V AdaGrad can gain up to a factor of &#8730; d in the regret bound with respect to plain OMD. Compared to the EG algorithm, which uses an entropic mirror map on the probability simplex, here the advantage is brought by a coordinate-dependent step size, which exploits the decomposability of the regret across the d coordinates granted by the geometry of V.</p><p>Note that the specific choice of the step size makes the algorithm independent with respect to rescalings of the coordinates <ref type="bibr">(Orabona &amp; P&#225;l 2018)</ref>. This property is especially useful in neural network training, where the range of gradient components may vary a lot across the different layers.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">FOLLOW THE REGULARIZED LEADER</head><p>A very natural online learning strategy for the OCO setting is Follow the Leader (FTL), which corresponds to predicting with the model minimizing the sum of the losses observed so far,</p><p>Here w1 &#8712; V is any convex, closed, and nonemtpy subset of R d . When losses are strongly convex and Lipschitz in V, FTL achieves RT (u) = O(ln T ) for all u &#8712; V (McMahan 2017, Section 3.7). However, the curvature of each loss function is necessary to obtain a nontrivial performance. When losses are linear, FTL provably incurs a regret that grows linearly in T (see, e.g., Shalev-Shwartz 2012, Example 2.2). This is caused by the intrinsic instability of the algorithm: in a nonstochastic setting, one can design the loss sequence so that the trajectory w1, w2, . . . of FTL models oscillates wildly in V, a behavior that the adversary can exploit to increase the regret. Similarly to OMD, which achieves stability by forcing wt+1 to be not too far away from wt, see ( <ref type="formula">5</ref>), FTL can be stabilized by adding a strictly convex regularization function. The resulting algorithm, appropriately called Follow the Regularized Leader (FTRL), is a close relative of OMD. Indeed, the regularization functions used by FTRL are formally equivalent to OMD's mirror maps &#968;. As FTRL is not formulated as a gradient descent method, we replace OMD's step sizes &#951;t with time-dependent regularizers &#968;t. For any sequence &#968;1, &#968;2, . . . of strictly convex regularizers, FTRL iterates are defined by</p><p>where &#8467;1, &#8467;2, . . . is an arbitrary sequence of convex losses. From the viewpoint of regret minimization, we know that &#8467;s(w) can be replaced by g &#8868; s w (recall the linearization step in Section 2), where gs is the gradient (or subgradient) of &#8467;s(ws). If we do that in (12), we obtain</p><p>This is the version of FTRL we study in the rest of this section. Let &#968; V,t be the restriction of &#968;t to V (see Section 2). If the regularizers &#968; V,t are all strongly convex, then wt+1 in (13) has the closed form</p><p>gs where &#968; &#8902; V,t+1 is the Fenchel conjugate of &#968; V,t+1 (differentiability of &#968; &#8902; V,t+1 is guaranteed by the strong convexity of &#968; V,t+1 ). By letting &#952;t+1 = -(g1 + &#8226; &#8226; &#8226; + gt), the FTRL iterates can be written as wt+1 = &#8711;&#968; &#8902; V,t+1 &#952;t+1 , see Figure <ref type="figure">2</ref>. By comparison, the OMD iterates for strongly convex mirror maps are written as wt+1 = &#8711;&#968; &#8902; V &#952; &#8242; t+1 ) where &#952; &#8242; t+1 = &#8711;&#968; V (wt)&#951;tgt.</p><p>Note that FTRL keeps a state variable &#952;t in the dual space of gradients. This is mapped to the primal space of iterates every time a prediction is needed. On the other hand, OMD keeps its state wt in the primal space of iterates. This is then mapped to the dual space of gradients every time an update must be computed. Another difference is that gradients are all equally weighted in FTRL, whereas in OMD each gradient gt is weighted by a potentially different step size &#951;t.</p><p>FTRL was originally introduced by <ref type="bibr">Abernethy et al. (2008)</ref>, although the key ideas are already contained in <ref type="bibr">(Shalev-Shwartz 2007)</ref>. The version with linearized losses and &#968;t = &#968; = &#951; 2 &#8226; 2 2 was introduced by Zinkevich (2004) as a "lazy update" variant of OMD.</p><p>divergence. When FTRL is applied to the same setting, the regret bound specializes to</p><p>where, we recall it, G upper bounds gt &#8734; for all t. Taking &#946;t = (ln d)/(G 2 t) then gives RT (u) &#8804; 2G &#8730; T ln d. Up to constants, this is the same as the bound we obtain for OMD when the step size is tuned with prior knowledge of the number of rounds T .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1.">Online Newton Step</head><p>As mentioned at the beginning of this section, strongly convex losses are an easy case for online learning. A simple algorithm like FTL achieves logarithmic regret on any sequence of such losses whenever the strong convexity coefficients in the loss sequence are bounded away from zero. A natural question is then whether logarithmic regret is possible for convex loss functions that are not strongly convex but also not linear.</p><p>For any symmetric and positive semidefinite matrix M , introduce the semi-norm &#8226; M such that w 2 M = w &#8868; M w. As it turns out, the right curvature property sufficient to guarantee logarithmic regret is the following:</p><p>for some &#955; &gt; 0, where g = &#8711;&#8467;t(w) (or any subgradient if &#8467;t is only subdifferentiable). In words, we require &#8467;t to be strongly convex only in the direction of its gradient (or in the direction of some of its subgradients). For example, the square loss &#8467;t(w) <ref type="bibr">Hazan et al. 2007</ref>, Lemma 3). Also, the logistic loss &#8467;t(w) = ln 1 + exp(-w &#8868; xt) satisfies property (15) when w belongs to an Euclidean ball of fixed radius. More in general, any loss &#8467;t such that e -&#945; &#8467; t is concave in V for some &#945; &gt; 0 satisfies property (15) with &#955; &#8804; 1 2 min 1 GD , &#945; , where D is the Euclidean diameter of V and G is a bound on max w&#8712;V &#8711;&#8467;t(w) . Such losses are said to be &#945;-exp-concave in V <ref type="bibr">(Kivinen &amp; Warmuth 1999)</ref>. If &#8467;t is twice differentiable, then &#945;-expconcavity in V is equivalent to &#8711; 2 &#8467;t(w) -&#945;&#8711;&#8467;t(w)&#8711;&#8467;t(w) &#8868; being positive semidefinite for all w &#8712; V. <ref type="bibr">Hazan et al. (2007, Theorem 6</ref>) prove a O(d ln T ) regret bound on FTL for all sequences of loss functions &#8467;t satisfying (15) for some &#955; &gt; 0. They do so by introducing the quadratic approximation of each loss function &#8467;t(w) = &#8467;t(wt)</p><p>, where gt = &#8711;&#8467;t(wt) and w1, w2, . . . &#8712; V are defined by</p><p>(w1 can be defined arbitrarily). Observe that ( <ref type="formula">16</ref>) is just FTL run on the losses &#8467;t. Moreover, &#8467;t(wt) = &#8467;t(wt) and, because of (15), &#8467;t(u) &#8804; &#8467;t(u) for all u &#8712; V. This implies that the regret of FTL with respect to the original losses &#8467;t satisfies</p><p>The rest of the proof uses the special properties of the functions &#8467;t to derive the desired O(d ln T ) bound on the regret. <ref type="bibr">Hazan et al. (2007, Lemma 4</ref>) also prove that ( <ref type="formula">16</ref>) is equivalent to</p><p>where S + t denotes the Moore-Penrose pseudoinverse of</p><p>A similar O(d ln T ) bound can be proven through a more general proof, this time using the FTRL framework with linearized losses. Define the regularizers &#968;1, &#968;2, . . . given by</p><p>where gt = &#8711;&#8467;t(wt) and the wt are the FTRL iterates defined in ( <ref type="formula">13</ref>),</p><p>An equivalent and more explicit form for the iterates ( <ref type="formula">19</ref>), which brings out the similarity with ( <ref type="formula">17</ref>), is</p><p>where where A0 = I and At = At-1 + &#955;gtg &#8868; t . Each regularizer &#968;t of the form ( <ref type="formula">18</ref>) is 1-strongly-convex with respect to the norm &#8226; A t-1 . Using this property, and the special recursive form of these regularizers, one can prove for this algorithm a regret bound of the following form: for any sequence &#8467;1, &#8467;2, . . . of losses satisfying (15),</p><p>where maxt gt 2 &#8804; G and we used a standard majorization for bounding the sum of terms gt 2</p><p>A -1 t (see, e.g., <ref type="bibr">Cesa-Bianchi &amp; Lugosi 2006, Lemma 11.11 and Theorem 11.7</ref>). One may also wonder whether the same logarithmic regret bound for losses satisfying (15) could be achieved using OMD instead of FTL/FTRL as we did in this section. Noting that, for M symmetric and positive definite, the divergence associated with &#968;</p><p>where A0 = I, At = At-1 + &#955;gtg &#8868; t , and gt = &#8711;&#8467;(wt). The closed-form expression is</p><p>Note that this algorithm is rather different from both ( <ref type="formula">17</ref>) and (20). Its regret analysis is relatively simple, although it is not derived as a special case of the general OMD analysis (which uses constant mirror maps). Fix any sequence &#8467;1, &#8467;2, . . . of loss functions satisfying (15). Since wt+1 is the projection of w &#8242; t+1 onto V, the update ( <ref type="formula">22</ref>) ensures that</p><p>for all u &#8712; V. By the curvature property (15), we then have that</p><p>(using the definition of At)</p><p>Now note that the the above is exactly equivalent to the bound (21) which we proved for FTRL.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2.">Online linear regression</head><p>An important special case of online learning is (unconstrained) online linear regression, where V = R d and the losses &#8467;t(w) =  <ref type="bibr">(Vovk 2001, Theorem 4)</ref>. Luckily, there is a better fix which does not require any preliminary knowledge about maxt |yt|: simply add to the objective function in (24) an extra loss term associated with the data point xt+1 and the value yt+1 = 0. As we see next, this has the effect of shrinking (towards zero) the linear predictions w &#8868; t xt, thus adding stability to the algorithm. <ref type="bibr">Cesa-Bianchi &amp; Lugosi (2006)</ref> call the resulting algorithm VAW, after <ref type="bibr">Vovk (2001)</ref> and <ref type="bibr">Azoury &amp; Warmuth (2001)</ref> who independently introduced it. VAW iterates are defined by wt+1 = argmin</p><p>The closed form expression is simply wt+1 = A -1 t+1 y1x1 +&#8226; &#8226; &#8226;+ytxt . In order to appreciate how predictions are shrunk by the addition of the term 1 2 w &#8868; xt+1 2 , let y RR t+1 = w &#8868; t+1 xt+1 be the Ridge Regression prediction computed via (24). Then, the VAW prediction y VAW t+1 = w &#8868; t+1 xt+1 computed via (25) satisfies</p><p>.</p><p>Clearly, y VAW t+1 &lt; y RR whenever xt+1 2 &gt; 0. It is interesting to compare VAW to a Gaussian Process (GP) for regression <ref type="bibr">(Rasmussen &amp; Williams 2005)</ref>. It is known that GP predicts with y RR t+1 , however it also returns an estimate of the variance of the prediction that depends on x &#8868; t+1 A -1 t xt+1. Hence, VAW shrinks more the points that are assigned a high variance estimate by a GP. The regret analysis of WAV shows that</p><p>Note that this bound simultaneously holds for any sequence (x1, y1), (x2, y2), . . . &#8712; R d &#215; R, for any time horizon T , and for any linear comparator u &#8712; R d . Moreover, as proven in <ref type="bibr">Vovk (2001, Section 3.3)</ref>, the bound ( <ref type="formula">26</ref>) is asymptotically optimal, including the leading constant.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.3.">Optimistic updates</head><p>The iterates of VAW are computed by adding to the expression in the argmin an extra loss term 1 2 w &#8868; xt+1 2 that "predicts" the next label yt+1 to be zero. where gs = &#8711;&#8467;s(ws), gt+1 is a guess for &#8711;&#8467;t+1(wt+1), and &#968;1, &#968;2, . . . are arbitrary &#181;strongly convex regularizers with respect to a norm &#8226; . One can show that, for all u &#8712; V,</p><p>We now describe two concrete and simple examples. First, consider gt+1 = 1 t t s=1 gs with g1 = 0 and-for the sake of simplicity-assume the convex losses are 1-Lipschitz in V, so that gt 2 &#8804; 1 for all gt generated in ( <ref type="formula">27</ref>). Take &#968;t = &#181; 2 &#8226; 2 2 for all t. Then, for all u &#8712; V,</p><p>Now note that &#8467;t = 1 2 gt -&#8226; 2 2 is a 1-strongly convex loss, and g1, g2, . . . correspond to the predictions of FTL on the sequence &#8467;1, &#8467;2, . . . of such losses. Therefore, using the FTL analysis for strongly convex losses mentioned at the beginning of this section we have that</p><p>It is easy to see that the minimizer in the above expression is g = 1 T t gt. So, we conclude</p><p>Hence, the regret is bounded in terms of the cumulative empirical variance of the loss gradients. Using more sophisticated time-dependent regularizers, the regret can be bounded by an expression sublinear in the cumulative variance. We mention a similar result in the next example, where we choose gt+1 = gt. In other words, we guess the next loss gradient to be similar to the current one. This is only beneficial under the additional assumption that losses are smooth, which is equivalent to assume that gradients are Lipschitz. Then, choosing regularizers &#968;t = &#946;t&#968;, where &#968; is a base 1-strongly convex regularizer with respect to a norm &#8226; and &#946;t &gt; 0 is a scaling factor, one can prove that the regret is bounded by an expression of the order of (see Orabona 2019)</p><p>Bounds of this form were first proven by <ref type="bibr">Chiang et al. (2012)</ref>. Optimistic updates have been also applied to show fast rates for regret minimization problems in game theory by <ref type="bibr">Syrgkanis et al. (2015)</ref>, <ref type="bibr">Foster et al. (2016)</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.">UNCONSTRAINED ONLINE CONVEX OPTIMIZATION</head><p>As discussed in previous sections, both Online Mirror Descent (OMD) and Follow the Regularized Leader (FTRL) enjoy a regret of order O D &#8730; T for convex and Lipschitz losses, where D bounds the diameter of V according to the divergence D &#968; (for OMD) or to the range of the base regularizer &#936; (for FTRL), see ( <ref type="formula">8</ref>) and ( <ref type="formula">14</ref>). If V is unbounded, say V = R d , and losses are convex Lipschitz, we can still run OGD with w1 = 0 and fixed stepsize &#951; = &#945;/ &#8730; T for &#945; &gt; 0. Using (10) we get the following upper bound on the regret</p><p>By tuning &#945; optimally with respect to u 2 2 we could get the bound RT (u) &#8804; u 2 &#8730; T . This is equivalent to what we would get by running OGD with projection in the Euclidean ball of radius U = u 2 . However, this bound cannot be simultaneously achieved for all u because the algorithms must be run with only one choice of their parameters. The problem we study in this section is whether we can get a bound better than (28) in the unconstrained setting. In order to answer this question, we explore the connection between online convex optimization and the problem of sequentially betting on the elements of a deterministic sequence of values.</p><p>The fact that certain instances of online learning could be phrased as a gambling problem is known since the works of <ref type="bibr">Kelly (1956)</ref>, <ref type="bibr">Cover (1974), and</ref><ref type="bibr">Feder (1991)</ref>. It was only recently, however, that <ref type="bibr">Orabona &amp; P&#225;l (2016)</ref> realized that certain betting strategies could be used to derive OCO algorithms with no parameters to tune, which could be also used for solving unconstrained OCO in an optimal way.</p><p>The betting game we are interested in is parameterized by an unknown deterministic sequence x1, x2, . . . &#8712; [-1, 1] of real numbers. The bettor starts out with an initial wealth of C0 = &#949; &gt; 0. In each round t = 1, 2, . . . of the game, 1. The bettor bets &#945;t &#8712; [-1, 1], whose absolute value is the fraction of their current wealth Ct-1 they are betting, and whose sign indicates which sign we bet xt will have;</p><p>Note that the bettor's wealth changes in each step t according to Ct = (1 + &#945;txt)Ct-1.</p><p>In order to show how to apply a betting strategy to any OCO problems, we first consider the 1-dimensional case with losses &#8467;1, &#8467;2, . . . defined on R and having uniformly bounded derivatives &#8467; &#8242; t &#8804; 1 for all t. First of all, recall that, because of the convexity of losses, for any u &#8712; R the regret RT (u) of any online algorithm predicting with w1, w2, . . . &#8712; R is upper bounded by T t=1 (wt -u)gt, where gt is the derivative of &#8467;t at wt. In order to use a betting strategy to solve the online problem, we set wt = &#945;tCt-1. We then have Ct = Ct-1 + wtxt, which implies CT = &#949; + T t=1 wtxt. If we now set xt = -gt &#8712; [-1, 1] (by our assumption on the losses), we get</p><p>Next, we prove that a lower bound on the wealth CT can be used to upper bound RT (u) for all u &#8712; R. In particular, assume that we have a betting strategy &#945;1, &#945;2, . . . &#8712; R such that</p><p>for some convex real function &#966;. Then, for any u &#8712; R we have</p><p>gt + &#949; (by our assumption on CT )</p><p>Now that we established a formal connection between online prediction (in the 1-dimensional case) and betting, we must pick a good betting strategy, one that has a small regret in the betting game. We measure this regret against the class of strategies that always bet the best constant &#945; &#8712; [-1, 1]. After T steps, the final wealth of each such strategy is CT (&#945;) = &#949; T t=1 (1 + &#945;xt). Since wealth changes multiplicatively, it is natural to define the regret of a betting strategy &#945;1, &#945;2, . . . using the logarithm of the wealth,</p><p>In the special case of Boolean values xt &#8712; {-1, 1}, the optimal regret RT (&#945;) was very precisely determined (including constants) by <ref type="bibr">Shtarkov (1987)</ref>, who established that</p><p>Unfortunately, Shtarkov's strategy is not efficiently computable. A more efficient (and nearly optimal) strategy was introduced a bit earlier by <ref type="bibr">Krichevsky &amp; Trofimov (1981)</ref>.</p><p>The Krichevsky-Trofimov (KT) strategy has a regret of</p><p>which is optimal only up to constants. When xt &#8712; [-1, 1], the KT strategy takes the simple form &#945;1 = 0 and &#945;t = (x1 + &#8226; &#8226; &#8226; + xt-1) t. <ref type="bibr">Orabona &amp; P&#225;l (2016)</ref> proved that the wealth of the KT strategy satisfies</p><p>for some universal constant c &gt; 0.</p><p>Going back the the 1-dimensional online convex optimization case, recalling ( <ref type="formula">29</ref>) and xt = -gt &#8712; [-1, 1], we see that the KT strategy generates predictions of the form</p><p>Using (30) and our bound RT (u) &#8804; &#966; &#8902; (u) + &#949; on the regret, we can compute &#966; &#8902; for our case and derive the bound</p><p>where, for simplicity, we set &#949; = 1. Recall that this bound holds, simultaneously for all u &#8712; R, under the condition that &#8711;&#8467;t &#8804; 1 for all t. Under the same conditions, OGD guarantees a bound on the regret RT (u) of worse order u 2 &#8730; T , see (28). This result has been extended to R d (and more generally to Banach spaces) by <ref type="bibr">Cutkosky &amp; Orabona (2018)</ref> using a simple trick: in order to bound the regret RT (u) against any u &#8712; R d we use the 1-dimensional KT strategy to learn the length u of u and OMD with model space V &#8801; u &#8712; R d : u &#8804; 1 to learn the direction u u of u, where &#8226; is any desired norm. This is done as follows: let wt the prediction (31) of KT and let vt be the prediction of OMD. Then, the combined algorithm predicts wtvt and, upon receiving the gradient gt = &#8711;&#8467;t (wtvt), feeds the derivative g &#8868; t vt to KT and the gradient gt to OMD. To analyze the regret of this combined KT-OMD strategy, note that vt &#8804; 1 for all t because OMD projects onto V. Therefore, g &#8868; t vt &#8804; g &#8902; . So, by linearizing the regret, we can write</p><p>Now note that the first sum is the linearized regret of KT against u , where g &#8868; t vt are the loss derivatives. The second sum (ignoring the u factor) is instead the linearized regret of OMD against u u with loss gradients gt.</p><p>Since KT requires the loss derivatives to belong to [-1, 1], we can apply the above bound when g &#8868; t vt &#8712; [0, 1], which holds when &#8467;t is 1-Lipschitz for all t. Assuming that, and in view of comparing to (28), we consider OGD run on the unit Euclidean ball with step size &#951;t = 1 &#8730; t and KT run with &#949; = 1. Then using (9) for OGD and (32) for KT we obtain that the regret of KT-OGD satisfies</p><p>Note that, except for the logarithmic factor ln u 2 2 T + 1 + 1, this bound matches the bound u 2 &#8730; T for OGD tuned with the unknown knowledge of u . Indeed, this logarithmic term is the price we have to pay for the adaptivity of the algorithm to u , as <ref type="bibr">Streeter &amp; McMahan (2012)</ref> showed it to be unavoidable in the unconstrained setting.</p><p>Note that parameter-free algorithms like KT-OMD are useful also when u lives in a bounded subset V &#8834; R d , but the Bregman divergence D &#968; is unbounded in V. The prime example for this scenario is the entropic mirror map &#968; on the simplex V, where D &#968; is the cross-entropy. The regret bound (10) for the corresponding instance of OMD (which we called EG) has the form</p><p>for any fixed choice of the stepsize &#951;. In the setting of prediction with expert advice (a special case of OCO), an implicitly defined parameter-free version of EG for linear losses called NormalHedge was introduced by Chaudhuri et al. <ref type="bibr">(2009)</ref>. The bound was later improved by <ref type="bibr">Chernov &amp; Vovk (2010)</ref> with another implicitly defined algorithm. Using a different reduction to betting strategies, <ref type="bibr">Orabona &amp; P&#225;l (2016)</ref> proved a bound of order (D &#968; (u, w1) + 1) T for all u in the simplex using a closed form update. Note that, as before, this bound is equal to the bound which one would get by tuning EG using the (unknown) knowledge of D &#968; (u, w1). Further improvement were obtained by <ref type="bibr">Koolen &amp; Van Erven (2015)</ref>, who introduced an algorithm called Squint.</p><p>One of the nice features of ( <ref type="formula">33</ref>) is that RT (0) does not depend on T . So we can then run multiple instances of the combined KT-OMD strategy using a different mirror map for each OMD instance. This allows to bound the regret as if we ran the algorithm using the best mirror map in hindsight (where best is relative to the linearized regret). Suppose for example we run two instances of KT-OMD and predict using the sum wt = w</p><p>(1) t + w</p><p>(2) t of their predictions. Then, linearizing the regret, we obtain</p><p>For instance, if we run OMD using the p-norm<ref type="foot">foot_3</ref> mirror map &#968; = 1 2 &#8226; 2 p for 1 &lt; p &#8804; 2, which is (p -1)-strongly convex with respect to the same norm, then RT (u) is bounded in terms of u p and gt q , where q is the conjugate coefficient of p, satisfying 1 p + 1 q = 1. Interestingly, one can show <ref type="bibr">(Gentile &amp; Littlestone 1999</ref>) that choosing p = 2 ln d (2 ln d -1) (for d &#8805; 3) gives a regret bound of the form u 2 1 /&#945; + &#945; G &#8730; T ln d for all u &#8712; R d and for maxt gt &#8734; &#8804; G. As this is very similar to the bound obtained by EG when V is the simplex, we see that by choosing p &#8712; (1, 2] we can interpolate between OGD and EG. By running multiple instances of KT-OMD, where the OMD instances use different values of p, one can derive a regret bound almost as good as the p-norm OMD run with the best value of p.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.">OTHER NOTIONS OF REGRET</head><p>Bounding the regret RT (u) for all u &#8712; V may not be crucial in some practical applications. For example, if the loss sequence &#8467;1, &#8467;2, . . . is such that no u &#8712; V achieves a small cumulative loss &#8467;1(u) + &#8467;2(u) + &#8226; &#8226; &#8226; , then regret bounds may not be at all helpful in telling good algorithms from bad ones. This lack of a single good minimizer in V of the cumulative loss is likely to occur when the loss sequence is generated by a highly nonstationary data sequence, possibly affected by seasonalities and other disturbances. In this case, regret should be replaced by more robust measures, allowing better comparators than fixed elements of V. In what follows, D2 is the Euclidean diameter of V and L is the Lipschitz constant of the convex loss functions in the sequence &#8467;1, . . . , &#8467;T . Herbster &amp; Warmuth (1998b)-see also <ref type="bibr">Cesa-Bianchi &amp; Lugosi (2006, Theorem 11.4</ref>)prove upper bounds on the dynamic regret of OMD run with the p-norm mirror map (for 1 &lt; p &#8804; 2) of the form</p><p>where Dp is the diameter of V measured using the p-norm, and Lq is the Lipschitz constant (with respect to the dual q-norm) of the loss functions in the sequence &#8467;1, . . . , &#8467;T -see also Zinkevich where D is the Euclidean diameter of V and L is the Lipschitz constant (with respect to the Euclidean norm) of the loss functions in the sequence &#8467;1, . . . , &#8467;T . This result is improved by <ref type="bibr">Jun et al. (2017)</ref>, who show the better bound R ada &#964;,T (u) = O DL + &#8730; ln T &#8730; &#964; using the betting framework described in Section 4. Most of the online algorithms for minimizing adaptive regret work by combining several instances of an online algorithm for the standard notion of regret. Each instance is run in a specific interval of time, where the set of intervals is carefully designed so that the overall number of instances to be run is O(ln T ). These instances are then combined using an algorithm based on the framework of prediction with expert advice <ref type="bibr">(Cesa-Bianchi et al. 1997)</ref> where each instance is viewed as an expert. As instances typically run for less than T time steps, <ref type="bibr">Jun et al. (2017)</ref> combine the betting framework with the sleeping experts model <ref type="bibr">(Freund et al. 1997)</ref>, which allows only for a subset of the experts to be active at any point of time.</p><p>Although the algorithm of <ref type="bibr">Jun et al. (2017)</ref> is designed to minimize adaptive regret, <ref type="bibr">Zhang et al. (2018b)</ref> show that the same algorithm can be also used to prove the following dynamic regret result is the path length over the interval I. However, when combined with known bounds on the dynamic regret, this bound does not give the optimal bound O L2 (D2 + &#928;2,T )D2T for dynamic regret. <ref type="bibr">Zhang et al. (2020)</ref> also derive algorithms simultaneously minimizing adaptive and dynamic regret. Some of these notions of regret were originally introduced in the setting of prediction with expert advice (i.e., OCO with linear losses, where V is equal to the probability simplex and regret is measured against the corners of the simplex, where linear functions are minimized). In that framework, dynamic regret is known as tracking or shifting regret <ref type="bibr">(Herbster &amp; Warmuth 1998a)</ref>. Other notions of regret, instead, are mostly studied in the experts framework. For example, policy regret <ref type="bibr">(Arora et al. 2012a</ref>) applies to settings where the loss function &#8467;t at each time t depends not only on the current model wt, but also on the past models wt-s, where s spans a window in the past (whose size H could potentially depend on t). These loss functions can be used to model natural scenarios, such as the "switching cost" scenario where H = 1 and &#8467;t(wt, wt+1) = c whenever wt = wt-1 <ref type="bibr">(Kalai &amp; Vempala 2005)</ref>. Swap regret <ref type="bibr">(Blum &amp; Mansour 2007)</ref>, instead, measures regret against a set of modification rules. Each modification rule F is an operator on the set {1, . . . , d} of coordinates. The instantaneous regret at time t against F of an algorithm choosing w in the simplex is &#8467;t(w) -&#8467;t w (F ) , where w (F ) i = j : F (j)=i wj. Note that when F (j) = i for all j = 1, . . . , d, swap regret against F reduces to standard regret against the i-th corner ei of the simplex, that is &#8467;t w (F ) = &#8467;t(ei) for all w. Swap regret is especially important when using online learning algorithms to approximate equilibria in games <ref type="bibr">(Cesa-Bianchi &amp; Lugosi 2006)</ref>.</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="1" xml:id="foot_0"><p>Partial extensions of online learning to nonconvex losses have been recently considered by Agarwal et al. (2019).www.annualreviews.org &#8226; Online Learning Algorithms</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="2" xml:id="foot_1"><p>This can be a plausible assumption in many practical cases. For instance, in online linear regression when upper bounds on maxt xt 2 and maxt |yt| are known in advance.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" xml:id="foot_2"><p>www.annualreviews.org &#8226; Online Learning Algorithms</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="3" xml:id="foot_3"><p>Recall the definition of p-norm of a vector u &#8712; R d , u p = (|u 1 | p + &#8226; &#8226; &#8226; + |u d | p ) 1/p .www.annualreviews.org &#8226; Online Learning Algorithms</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" xml:id="foot_4"><p>N. Cesa-Bianchi and F. Orabona   </p></note>
		</body>
		</text>
</TEI>
