---
abstract: 'We aim to design adaptive online learning algorithms that take advantage of any special structure that might be present in the learning task at hand, with as little manual tuning by the user as possible. A fundamental obstacle that comes up in the design of such adaptive algorithms is to calibrate a so-called step-size or learning rate hyperparameter depending on variance, gradient norms, etc. A recent technique promises to overcome this difficulty by maintaining multiple learning rates in parallel. This technique has been applied in the MetaGrad algorithm for online convex optimization and the Squint algorithm for prediction with expert advice. However, in both cases the user still has to provide in advance a Lipschitz hyperparameter that bounds the norm of the gradients. Although this hyperparameter is typically not available in advance, tuning it correctly is crucial: if it is set too small, the methods may fail completely; but if it is taken too large, performance deteriorates significantly. In the present work we remove this Lipschitz hyperparameter by designing new versions of MetaGrad and Squint that adapt to its optimal value automatically. We achieve this by dynamically updating the set of active learning rates. For MetaGrad, we further improve the computational efficiency of handling constraints on the domain of prediction, and we remove the need to specify the number of rounds in advance.'
bibliography:
- 'biblio.bib'
title: Lipschitz Adaptivity with Multiple Learning Rates in Online Learning
---

Introduction
============

We consider *online convex optimization* (OCO) of a sequence of convex functions $f_1,\ldots,f_T$ over a given bounded convex domain, which become available one by one over the course of $T$ rounds [@ShalevShwartz2011; @HazanOCOBook2016]. Typically $f_t(\w) =
{\textsc{loss}}(\w,\x_t,y_t)$ represents the *loss* of predicting with parameters $\w$ on the $t$-th data point $(\x_t,y_t)$ in a machine learning task. At the start of each round $t$, a learner has to predict the best parameters $\w_t$ for the function $f_t$ before finding out what $f_t$ is, and the goal is to minimize the *regret*, which is the difference in the sum of function values between the learner’s predictions $\w_1,\ldots,\w_T$ and the best fixed oracle parameters $\u$ that could have been chosen if all the functions had been given in advance. A special case of OCO is prediction with expert advice [@cesa06], where the functions $f_t(\w) = \w^\top
\vloss_t$ are convex combinations of the losses $\vloss_t =
(\loss_{t,1},\ldots,\loss_{t,K})^\top$ of $K$ expert predictors and the domain is the probability simplex.

Central results in these settings show that it is possible to control the regret with almost no prior knowledge at all about the functions. For instance, knowing only an upper bound $G$ on the $\ell_2$-norms of the gradients ${\operatorname{grad}_}t = \nabla f_t(\w_t)$, the online gradient descent (OGD) algorithm guarantees $O(G \sqrt{T})$ regret by tuning its learning rate hyperparameter $\eta_t$ proportional to $1/(G\sqrt{t})$ [@Zinkevich2003], and in the case of prediction with expert advice the Hedge algorithm achieves regret $O(L\sqrt{T\ln K})$ knowing only an upper bound $L$ on the range $\max_k \ell_{t,k} - \min_k \ell_{t,k}$ of the expert losses [@FreundSchapire1997]. Here $G$ is the $\ell_2$-Lipschitz constant of the learning task[^1], and $L/2$ is the $\ell_1$-Lipschitz constant over the probability simplex.

The above guarantees are tight if we make no further assumptions about the functions $f_t$ [@HazanOCOBook2016; @CesaBianchiEtAl1997], but they can be significantly improved if the functions have additional special structure that makes the learning task easier. The literature on online learning explores multiple orthogonal dimensions in which tasks may be significantly easier in practice (see ‘related work’ below). Here we focus on the following regret guarantees that are known to exploit multiple types of easiness at the same time: $$\begin{aligned}
  \text{OCO:}& &O\left(\sqrt{V_T^\u d \log T}\right)
  \text{ for all $\u$,}
  \quad \text{with $V_T^\u = \sum_{t=1}^T ((\w_t - \u)^\top
  {\operatorname{grad}_}t)^2$,}\label{eqn:ourmetagradbound}\\
  \text{Experts:}& &O\left(\sqrt{\operatorname{\mathbb{E}}_{\rho(k)}[V_T^k]
  \operatorname{KL}(\rho\|\pi)}\right)
  \text{ for all $\rho$,}
  \quad \text{with $V_T^k = \sum_{t=1}^T ((\w_t - \e_k)^\top
  \vloss_t)^2$,}\label{eqn:oursquintbound}\end{aligned}$$ where $d$ is the number of parameters and $\operatorname{KL}(\rho\|\pi) = \sum_{k=1}^K
\rho(k) \ln \rho(k)/\pi(k)$ is the Kullback-Leibler divergence of a data-dependent distribution $\rho$ over experts from a fixed prior distribution $\pi$.

The OCO guarantee is achieved by the MetaGrad algorithm [@Erven2016], and implies regret that grows at most logarithmic in $T$ both in case the losses are curved (exp-concave, strongly convex) and in the stochastic case whenever the losses are independent, identically distributed samples with variance controlled by the Bernstein condition [@Erven2016; @koolen2016]. The guarantee for the expert case is achieved by the Squint algorithm [@koolen2015; @squintPAC]. It also exploits special structure along two dimensions simultaneously, because the $V_T^k$ term is much smaller than $L^2 T$ in many cases [@GaillardStoltzVanErven2014; @koolen2016] and the so-called *quantile bound* $\operatorname{KL}(\rho\|\pi)$ is much smaller than the worst case $\ln K$ when multiple experts make good predictions [@ChaudhuriFreundHsu2009; @ChernovVovk2010]. Squint and MetaGrad are both based on the same technique of tracking the empirical performance of *multiple learning rates* in parallel over a quadratic approximation of the original loss. A computational difference though is that Squint is able to do this by a continuous integral that can be evaluated in closed form, whereas MetaGrad uses a discrete grid of learning rates.

Unfortunately, to achieve and , both MetaGrad and Squint need knowledge of the Lipschitz constant ($G$ or $L$, respectively). Overestimating $G$ or $L$ by a factor of $c > 1$ has the effect of reducing the effective amount of available data by the same factor $c$, but underestimating the Lipschitz constant is even worse because it can make the methods fail completely. In fact, the ability to adapt to $G$ has been credited [@WardWuBottou2018] as one of the main reasons for the practical success of the AdaGrad algorithm [@DuchiHazanSinger2011; @McMahanStreeter2010]. Thus getting the Lipschitz constant right makes the difference between having practical algorithms and having promising theoretical results.

For OCO, an important first step towards combining Lipschitz adaptivity to $G$ with regret bounds of the form was taken by @cutkosky2017, who aimed for but had to settle for a weaker result with $G \sum_{t=1}^T \|{\operatorname{grad}_}t\|_2 \|\w_t - \u\|_2^2$ instead of $V_T^\u$. Although not sufficient to adapt to the Bernstein condition, they do provide a series of stochastic examples where their bound already leads to fast $O(\ln^4 T)$ rates. For the expert setting, @Wintenberger2017 has made significant progress towards a version of without the quantile bound improvement, but he is left with having to specify an initial guess $L_\text{guess}$ for $L$ that enters as $O(\ln \ln (L/L_\text{guess}))$ in his bound, which may yet be arbitrarily large when the initial guess is on the wrong scale.

#### Main Contributions

Our main contributions are that we complete the process began by @cutkosky2017 and @Wintenberger2017 by showing that it is indeed possible to achieve and without prior knowledge of $G$ or $L$. In fact, for the expert setting we are able to adapt to the tighter quantity $B \geq \max_k |(\w_t - \e_k)^\top \vloss_t|$. We achieve these results by dynamically updating the set of active learning rates in MetaGrad and Squint depending on the observed Lipschitz constants. In both cases we encounter a similar tuning issue as @Wintenberger2017, but we avoid the need to specify any initial guess using a new restarting scheme, which restarts the algorithm when the observed Lipschitz constant increases too much. In addition to these main results, we remove the need to specify the number of rounds $T$ in advance for MetaGrad by adding learning rates as $T$ gets larger, and we improve the computational efficiency of how it handles constraints on the domain of prediction: by a minor extension of the black-box reduction for projections of @cutkosky2018, we incur only the computational cost of projecting on the domain of interest in *Euclidean* distance. This should be contrasted with the usual projections in time-varying Mahalanobis distance for second-order methods like MetaGrad.

#### Related Work

If adapting to the Lipschitz constant were our only goal, a well-known way to achieve it for OCO would be to change the learning rate in OGD to $\eta_t \propto 1/\sqrt{\sum_{s\leq t} \|{\operatorname{grad}_}s\|_2^2}$, which leads to $O(\sqrt{\sum_{t\leq T} \|{\operatorname{grad}_}t\|_2^2}) = O(G \sqrt{T})$ regret. This is the approach taken by AdaGrad (for each dimension separately) [@DuchiHazanSinger2011; @McMahanStreeter2010]. In prediction with expert advice, Lipschitz adaptive methods are sometimes called and have previously been obtained by @cbms07 [@rooij14] with generalizations to OCO by @OrabonaPal2015. In addition, the first two of these works obtain a data-dependent variance term that is different from $V_T^k$ in , but no quantile bounds are known for the former. Results for the latter have previously been obtained by @GaillardStoltzVanErven2014 [@Wintenberger2014Arxiv] without quantile bounds, and with a slightly weaker notion of variance by @AdaNormalHedge. Quantile bounds without variance adaptivity were introduced by @ChaudhuriFreundHsu2009 [@ChernovVovk2010]. These may be interpreted as measures of the complexity of the comparator $\rho$. The corresponding notion in OCO is to adapt to the norm of $\u$, which has been achieved in various different ways, see for instance [@McMahanAbernethy2013; @cutkosky2018]. For curved functions, existing results achieve fast rates assuming that the degree of curvature is known [@HazanAgarwalKale2007], measured online [@BartlettHazanRakhlin2007; @Do2009] or entirely unknown [@Erven2016; @cutkosky2018]. Fast rates are also possible for slowly-varying linear functions and, more generally, optimistically predictable gradient sequences [@hazan2010extracting; @GradualVariationInCosts2012; @RakhlinSridharan2013].

We view our results as a step towards developing algorithms that automatically adapt to multiple relevant measures of difficulty at the same time. It is not a given that such combinations are always possible. For example, @CutkoskyBoahen2017Impossible show that Lipschitz adaptivity and adapting to the comparator complexity in OCO, although both achievable independently, cannot both be realized at the same time (at least not without further assumptions). A general framework to study which notions of task difficulty do combine into achievable bounds is provided by @FosterRakhlinSridharan2015. @FosterRakhlinSridharan2017 characterize the achievability of general data-dependent regret bounds for domains that are balls in general Banach spaces.

#### Outline

We add Lipschitz adaptivity to Squint for the expert setting in Section \[Squint2\]. Then, in Section \[MetaC\], we do the same for MetaGrad in the OCO setting. The developments are analogous at a high level but differ in the details for computational reasons. We highlight the differences along the way. Section \[MetaC\] further describes how to avoid specifying $T$ in advance for MetaGrad. Then, in Section \[four\], we add efficient projections for MetaGrad, and finally Section \[sec:conclusion\] concludes with a discussion of directions for future work.

section[Introduction]{} Any source on prediction with expert advice will start with the celebrated minimax regret bound of the following form $$R_T^k
  ~\le~
  \sqrt{\frac{T}{2} \ln K}
  \qquad
  \text{for each expert $k \in \{1,\ldots,K\}$}
  ,$$ and follow up with the remark that its multiplicative constant is optimal in the limit of large $T,K$ [@cesa06 Theorem 3.7]. Despite the mathematical strength and elegance, matching minimax algorithms are found to underwhelm in practice, whereas simple heuristics shine. This observation spurred multiple lines of research into adaptive algorithms with individual-sequence regret bounds with refined dependencies on the data and the comparator that hold under possibly relaxed assumptions.

Properties of bounds that have been identified as desirable are

-   **quantile** bounds improve when multiple experts are good, a necessity when dealing with continuous expert spaces. These bounds also typically allow guarantees that are non-uniform across experts (adapting e.g. to available prior knowledge)

-   **first-order** bounds improve when the loss $L^*$ of the comparator is small.

-   **second-order** bounds improve when some measure of variance is small. The literature distinguishes two flavours of variance, namely the variance of the loss [@hazan10] and the variance of the excess loss [@Gaillard2014]. The latter is particularly interesting because it can be shown that algorithms with guarantees for squared excess losses have constant regret in many statistical cases [@koolen2016].

-   **scale-free** bounds are for settings where no a-priori range of the losses can be assumed. Scale-free algorithms are unaffected by scaling the losses, while scale-free bounds scale along with any scaling of the losses imposed. @cbms07 call algorithms/bounds that are also invariant under translations of the losses **fundamental**.

-   **timeless** algorithms/bounds, as advocated by @rooij14, are unaffected when rounds are inserted with all-identical losses. Timelessness was proposed as a sanity-check to “protest” crudely measuring the complexity of the problem by its number of rounds. An algorithm can always be made timeless by simply ignoring any all-identical-loss round, but this is clunky and discontinuous, calling for prediction rules that are naturally smoothly timeless.

Taking stock (see Table \[tab:stock\]), we see that no algorithm currently has all desirable features. The closest candidates are <span style="font-variant:small-caps;">AdaHedge</span> by @rooij14, which is fundamental second-order timeless but not quantile, and the later <span style="font-variant:small-caps;">Squint</span> by @koolen2015 which is second-order quantile timeless but not scale-free.[^2] Moreover, second-order bounds are by nature fundamental and timeless. This strongly suggests that it is possible to obtain everything. However, this seems to require a new idea in terms of algorithm design.

That is where we come in.

  ----------------------- -------------------------------------------------------- ------------------------------------------------------ -------------------------------------------------------
                          <span style="font-variant:small-caps;">AdaHedge</span>   <span style="font-variant:small-caps;">Squint</span>   <span style="font-variant:small-caps;">Squint2</span>
                          @rooij14                                                 @koolen2015                                            this paper
  Quantile                                                                                                                                
  Second-order                                                                                                                            
  Scale-free                                                                                                                              
  Translation-invariant                                                                                                                   
  Timeless                                                                                                                                
  ----------------------- -------------------------------------------------------- ------------------------------------------------------ -------------------------------------------------------

  : State of algorithms on the above two dimensions.[]{data-label="tab:stock"}

  --------------------------------------------------------------------- -------------------------------------------------------- -------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------
                                                                        <span style="font-variant:small-caps;">MetaGrad</span>   <span style="font-variant:small-caps;">FreeRex-</span><span style="font-variant:small-caps;">Momentum</span>   [<span style="font-variant:small-caps;">MetaGrad+C</span>]{}
                                                                        @Erven2016                                               @cutkosky2017                                                                                                  this paper
  No prior knowledge of the gradient range                                                                                                                                                                                                      
  No prior knowledge of the horizon                                                                                                                                                                                                             
  Log. regret under exp-concavity                                                                                                                                                                                                               
  Log. regret under the Bernstein condition                                                                                      [^3]                                                                                                           
  Worst-case time complexity per round in the constrained OCO setting   $O(C_{\mathcal{U}}  \ln T$)                              $O(C_{\mathcal{U}})$[^4]                                                                                       $O(C_{\mathcal{U}} + d^2 \ln T)$
  --------------------------------------------------------------------- -------------------------------------------------------- -------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------

  : State of algorithms on the above two dimensions. $C_{\mathcal{U}}$ denotes the worst-case cost of performing a projection into the set $\mathcal{U}\subset \mathbb{R}^d$. []{data-label="tab:metagrad"}

Related Work
------------

### Adaptive Expert Algorithms

-   First-order adaptivity: Auer et al: $L^*$

-   Second-order: Adahedge/CBMS, modified prod (Gaillard,Stoltz,Van Erven)

-   Quantile bounds: NormalHedge, Chernov-Vovk, (precursor: Poland&Hutter for non-uniform prior)

-   Second-order+quantile: AdaNormalHedge, Squint

-   Optimistic (predictible/slowly varying/...)

### Adaptive OCO Algorithms

-   Lipschitz-adaptivity: GD with $\eta_t =
      \frac{D}{\sqrt{\epsilon + \sum_{s=1}^t \|\bm{g}_s\|^2}}$ \[Don’t know reference for this; @McMahan2017 discusses it for $d=1$\], diagonal version of AdaGrad [@DuchiHazanSinger2011; @McMahanStreeter2010] uses this per dimension. @McMahan2017 reviews data-dependent regularizers and has a good discussion of AdaGrad (explicitly interpreted as per-coordinate learning rates); he claims that you need an initial guess $\epsilon = G$ for the FTRL-version of AdaGrad, but you can get away with $\epsilon = 0$ for the Mirror-Descent version of AdaGrad; otherwise not much novelty in [@McMahan2017], so don’t cite too much. @WardWuBottou2018 (who call this AdaGrad even though it is not) prove Lipschitz-adaptivity for this method in non-convex stochastic optimization with a bound $c_G^2$ on the *expected* gradient norm squared. They actually get an extra term $\log \frac{c_G^2}{B_0}$ in their convergence rate. @cutkosky2018 cite [@SrebroEtAl2010] for the claim that a regret bound in terms of $\|\bm{g}_t\|^2$ implies fast rates for smooth losses. This is not precise: @SrebroEtAl2010 do not directly say anything about regret in this case, but their Lemma 3.1 says that for smooth, *non-negative* loss the dual norm of the gradients can be bounded in terms of the square root of the function value. This might be small if the algorithm is converging to the minimum function value and this minimum value is 0, but showing that takes some work that is not done in [@SrebroEtAl2010].

-   Adapt to $G$ and $D$ simultaneously: not possible [@CutkoskyBoahen2017Impossible] (actually, Manfred and Wojtek have a paper submitted to ICML where they show you can get around this impossibility result if you know $\bm{x}_t$ before making a prediction) @OrabonaPal2015 do have an “adaptive” bound $O(D^2\sqrt{\sum_{t=1}^T
      \|\bm{g}_t\|^2})$, which they achieve by generalizing AdaHedge to FTRL, but it has suboptimal dependence on $D$ (no square root) because they just omit it when tuning the learning rate. They also try to hide this suboptimality in their discussion, which is not good. They do give a table with overview of ‘scale-free’ algorithms: notably, AdaGrad is only scale-free in its MD version and not in its FTRL version.

-   [@cutkosky2017] adapt to $G$ and a class of stochastic settings. They say they would like to combine adaptivity to $G$ with the MetaGrad regret bound, but instead they settle for $R_T = O\left(\sqrt{G_T \sum_{t=1}^T
      \|\bm{g}_t\| \|\bm{w}_t - \bm{w}^*\|^2}\right)$, which implies “logarithmic regret” $O(\log^4(T))$ for “$\alpha$-acutely-convex” functions. $\alpha$-acutely convex is a stochastic condition, which implies the $(B,\beta)$-Bernstein condition with $B=G_T/\alpha$ and $\beta=1$, so even the constants are what we would expect (@cutkosky2017 have a factor $G_T$ in their regret bound, which we incur via the Bernstein constant).

-   Adapt to curvature: @BartlettHazanRakhlin2007 adapt to strong convexity (need to observe strong convexity per round); @cutkosky2018 adapt to strong convexity (in Banach spaces) without needing to observe strong convexity per round, but they lose logarithmic factors; MetaGrad adapts to exp-concavity and strong convexity without needing to observe the strong convexity per round, but loses a factor $d$ for strong convex losses \[this should be fixable, but we have not done it\]

-   Other well-known second-order methods in the mistake-bound model: AROW and the second-order perceptron

-   (Offset-) Rademacher complexity and its empirical versions.

Notes: if you need a reference showing that $O(DG \sqrt{T})$ is the optimal rate in some sense, then @cutkosky2017 refers to Jacob Abernethy, Peter L Bartlett, Alexander Rakhlin, and Ambuj Tewari, COLT 2008. I could check this out.

Problem Setting and Notation
============================

In OCO, a learner repeatedly chooses actions $\w_t$ from a closed convex set ${\mathcal{U}}\subseteq {\mathbb{R}}^d$ during rounds $t=1,\ldots,T$, and suffers losses $f_t(\w_t)$, where $f_t: {\mathcal{U}}\to {\mathbb{R}}$ is a convex function. The learner’s goal is to achieve small *regret* $R_T^\u = \sum_{t=1}^T f_t(\w_t) - \sum_{t=1}^T f_t(\u)$ with respect to any comparator action $\u \in {\mathcal{U}}$, which measures the difference between the cumulative loss of the learner and the cumulative loss they could have achieved by playing the oracle action $\u$ from the start. A special case of OCO is prediction with expert advice, where $f_t(\w) = \w^\top \vloss_t$ for $\vloss_t \in
{\mathbb{R}}^K$ and the domain ${\mathcal{U}}$ is the probability simplex ${\triangle}_K = \{(w_1,\ldots,w_K) : w_i \geq 0, \sum_i w_i = 1\}$. In this context we will further write $\p$ instead of $\w$ for the parameters to emphasize that they represent a probability distribution. We further define $[K] = \{1,\ldots,K\}$.

Adaptive Second-order Quantile Method for Experts {#Squint2}
=================================================

In this section, we present an extension of the <span style="font-variant:small-caps;">Squint</span> algorithm that adapts automatically to the loss range in the setting of prediction with expert advice.

Throughout this section, we denote $r^k_t \coloneqq {\langle{\widehat{\bm{p}}}_t- \bm{e}_k,\bm{\ell}_t\rangle}$ and $v^k_t \coloneqq (r^k_t)^2$, where ${\widehat{\bm{p}}}_t \in \triangle_K$ is the weight vector played by the algorithm at round $t$ and $\bm{\ell}_t$ is the observed loss vector. The cumulative regret with respect to expert $k$ is given by ${R}^k_t\coloneqq \sum_{s=1}^t r^k_s$. We use ${V}^k_t \coloneqq \sum_{s=1}^t v^k_s$ to denote the cumulative squared excess loss (which can be regarded as a measure of variance) of expert $k$ at round $t$. In the next subsection, we review the <span style="font-variant:small-caps;">Squint</span> algorithm.

The <span style="font-variant:small-caps;">Squint</span> Algorithm {#AdaptiveSquint}
------------------------------------------------------------------

We first describe the original <span style="font-variant:small-caps;">Squint</span> algorithm, as introduced by [@koolen2015]. Let $\pi$ and $\gamma$ be prior distributions with supports on $[K]$ and $\left]0,
\frac{1}{2}\right]$, respectively. Then <span style="font-variant:small-caps;">Squint</span> outputs predictions $$\begin{gathered}
\label{Squintforcaster}
  \p_{t+1} \propto \underset{\pi(k)\gamma(\eta)}{\mathbb{E}}\left[ \eta e^{-  \sum_{s=1}^t f_s(k,\eta)} \bm{e}_k \right],
\shortintertext{where $f_t(k,\eta)$ are quadratic \emph{surrogate losses} defined by}
\label{surrogatesquint0}
f_t(k,\eta) \coloneqq - \eta {\langle{\widehat{\bm{p}}}_t-\bm{e}_k,\bm{\ell}_t\rangle} + \eta^2 {\langle{\widehat{\bm{p}}}_t-\bm{e}_k,\bm{\ell}_t\rangle}^2.\end{gathered}$$ [@koolen2015] propose to use the *improper* prior $\gamma(\eta)
= \frac{1}{\eta}$ which does not integrate to a finite value over its domain, but because of the weighting by $\eta$ in the predictions $\p_{t+1}$ are still well-defined. The benefit of the improper prior is that it allows calculating $\p_{t+1}$ in closed form [@koolen2015]. For any distribution $\rho \in {\triangle}_K$, <span style="font-variant:small-caps;">Squint</span> achieves the following bound: $$\begin{aligned}
{R}^{\rho}_T = O\left(\sqrt{{V}^{\rho}_T\left( \operatorname{KL}(\rho || \pi ) +
\ln \ln T\right)}\right), \label{Squintbound}\end{aligned}$$ where $R_T^{\rho} = \mathbb{E}_{\rho(k)}\left[R_T^{k} \right]$ and $V_T^{\rho} = \mathbb{E}_{\rho(k)}\left[V_T^{k} \right]$. This version of Squint assumes the loss range $\max_k \ell_{t,k} - \min_k \ell_{t,k}$ is at most $1$, and can fail otherwise. In the next subsection, we present an extension of <span style="font-variant:small-caps;">Squint</span> which does not need to know the Lipschitz constant.

Lipschitz Adaptive Squint
-------------------------

|We first design a version of <span style="font-variant:small-caps;">Squint</span>, called [<span style="font-variant:small-caps;">Squint+C</span>]{}, that still requires an initial estimate $B > 0$ of the Lipschitz constant. The next section will be devoted to setting this parameter online. For now, we consider it fixed. In addition to this, the algorithm takes a prior distribution $\pi \in \triangle_K$. In a sequence of rounds $t = 1, 2, \ldots$ the algorithm predicts with $\hat\p_t \in \triangle_K$, and receives a loss vector $\vloss_t^k \in \mathbb R^K$. We denote the *instantaneous regret of expert $k$ in round $t$* by $r_t^k \df \tuple{\hat \p_t - \e_k, \vloss_t}$. We denote the observed Lipschitz constant in round $t$ at point $\hat \p_t$ by $
b_t
\df
\max_k \abs{r_t^k}$, and we denote its running maximum by $B_t \df B \lub \max_{s \le t} b_s$, and we use the convention that $B_0=B$. In addition, we will also require a clipped version of the loss vector $\scale{\vloss_t} = \frac{B_{t-1}}{B_t} \vloss_t$, and we denote by $\scale{r}_t^k = \tuple{\hat \p_t - \e_k, \scale \vloss_t}$ the rescaled instantaneous regret. We will use that $\abs{\scale r_t^k} \le B_{t-1}$. It suffices to control the regret for the clipped loss, because the cumulative difference is a negligible lower-order constant[^5]: $$\label{eq:ashok}
  R_T^k
  -
  \scale R_T^k
  ~\df~
  \sum_{t=1}^T \del*{r_t^k - \scale r_t^k}
  ~=~
  \sum_{t=1}^T \del*{B_t - B_{t-1}} \frac{r_t^k}{B_t}
  ~\le~
  B_T - B_0
  .$$ This means we can focus on regret for $\scale \vloss_t$, for which the range bound $\abs{\scale r_t^k} \le B_{t-1}$ is available *ahead* of each round $t$. To motivate [<span style="font-variant:small-caps;">Squint+C</span>]{}, we define the potential function after $T$ rounds by $$\label{eq:sq.pot}
  \Phi_T
  \df
  \sum_k \pi_k \int_0^\frac{1}{2 B_{T-1}} \frac{e^{\eta \scale{R}_T^k - \eta^2 \scale{V}_T^k} -1}{\eta} \dif \eta
  \quad
  \text{where}
  \quad
  \scale R_T^k \df \sum_{t=1}^T \scale r_t^k
  ~~
  \text{and}
  ~~
  \scale V_T^k \df \sum_{t=1}^T (\scale r_t^k)^2
  .$$ We also define $\Phi_0 = 0$ (due to the integrand being zero), even though it involves the meaningless $B_{-1}$ in the upper limit. The algorithm is now derived from the desire to keep this potential under control. As we will see in the analysis, this requirement uniquely forces the choice of weights $$\label{eq:sq.weights}
  \hat p_{T+1}^k
  ~\propto~
  \pi_k \int_0^\frac{1}{2 B_T} e^{\eta \scale{R}_T^k - \eta^2 \scale{V}_T^k} \dif \eta
  .$$ Like the original <span style="font-variant:small-caps;">Squint</span>, we see that the weights $\hat \p_{t+1}$ can be evaluated in closed form using Gaussian CDFs. The regret analysis consists of two parts. First, we show that the algorithm keeps the potential small.

\[lem:pot.is.small\] Given parameter $B\geq0$, [<span style="font-variant:small-caps;">Squint+C</span>]{} ensures $\Phi_T \le \ln \frac{B_{T-1}}{B}$.

The next step of the argument is to show that small potential is useful. The argument here follows [@koolen2015], specifically the version by [@squintPAC]. We have

\[lem:small.is.good\] Definition implies that for any comparator distribution $\rho \in \triangle_K$ the regret is at most $$\begin{gathered}
    \scale R_T^\rho
     ~\le~
    \sqrt{2     \scale V_T^\rho} \del*{
      1+
      \sqrt{2 C_T^{\rho}}
    }
    +
    5 B_{T-1}
    \del*{C_T^{\rho}+ \ln 2}, 
    \quad   \text{where,}  \\
    C^{\rho}_T ~\df~
    \operatorname{KL}\delcc*{\rho}{\pi}
    + \ln \del*{
      \Phi_T
      + \frac{1}{2}
      + \ln \left(2+  \sum_{t=1}^{T-1} \frac{b_t}{B_t} \right)
    }
  \end{gathered}$$

Keeping only the dominant terms, this reads $$\scale R_T^\rho
  ~=~
  O\del*{
    \sqrt{\scale V_T^\rho \del*{\operatorname{KL}\delcc*{\rho}{\pi} +
        \ln \Phi_T + \ln \ln T}}
  }
  .$$ The significance of , Lemmas \[lem:pot.is.small\] and  \[lem:small.is.good\] is that we obtain a bound of the form $$R_T^\rho
  ~=~
  O \del*{
    \sqrt{V_T^\rho \del*{\operatorname{KL}\delcc*{\rho}{\pi} +
   \ln    \ln \frac{TB_{T-1}}{B}}}
  +
  5 B_T \del*{\operatorname{KL}\delcc*{\rho}{\pi} +
  \ln   \ln \frac{TB_{T-1}}{B} }
}
  .$$ However, there does not seem to be any safe a-priori way to tune $B=B_0$. If we set it too small, the factor $\ln \ln \frac{B_{T-1}}{B}$ explodes. If we set it too large, the lower-order contribution $B_{T-1} \ge B$ blows up. It does not appear possible to bypass this tuning dilemma within the current construction. Fortunately, we are able to resolve it using restarts. Algorithm \[bb1alg\], which applies to both [<span style="font-variant:small-caps;">Squint+C</span>]{} and [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} (presented in the next section), monitors a condition of the sequences $(b_t)$ and $(B_t)$ to trigger restarts.

is either [[<span style="font-variant:small-caps;">Squint+C</span>]{}]{} or [[<span style="font-variant:small-caps;">MetaGrad+C</span>]{}]{}, taking as input parameter an initial scale $B$ Play $\w_1$ until the first time $t=\tau_1$ that $b_t
\neq 0$. \[line:runmetagrad\] Run [[<span style="font-variant:small-caps;">Alg</span>]{}]{} with input $B = B_{\tau_1}$ until the first time $t=\tau_2$ that $\displaystyle \frac{B_t}{B_{\tau_1}} >
\sum_{s=1}^t \frac{b_s}{B_s}$.\
Set $\tau_1 = \tau_2$ and goto line \[line:runmetagrad\].

\[blackboxreduction0\] Let [<span style="font-variant:small-caps;">Squint+L</span>]{} be the result of applying Algorithm \[bb1alg\] to [<span style="font-variant:small-caps;">Squint+C</span>]{} (as <span style="font-variant:small-caps;">Alg</span>). [<span style="font-variant:small-caps;">Squint+L</span>]{} guarantees, for any comparator $\rho\in \triangle_K$, $$\begin{aligned}
  R_T^\rho
    ~\le~
    2\sqrt{      V_T^\rho} \del*{
      1+
      \sqrt{2 \Gamma_T^{\rho}}
    }
    +
    10 B_{T}
    \del*{
      \Gamma_T^{\rho}
      + \ln 2} + 4 B_T,\end{aligned}$$ where $  \Gamma_T^{\rho} ~\df~\operatorname{KL}\delcc*{\rho}{\pi}+ \ln \del*{\ln \left(\sum_{t=1}^{T-1} \frac{b_{t}}{B_t}\right) + \frac{1}{2}+ \ln \left(2+\sum_{t=1}^{T-1} \frac{b_{t}}{B_t}\right)}$.

Theorem \[blackboxreduction0\] shows that the bound on the regret of [<span style="font-variant:small-caps;">Squint+L</span>]{} has a term of order $O(\ln \ln \sum_{t=1}^{T-1} \frac{b_{t}}{B_t})=O(\ln \ln T)$, which does not depend on the initial guess $B_0$ anymore.

Adaptive Method for Online Convex Optimization {#MetaC}
==============================================

We consider the Online Convex Optimization (OCO) setting where at each round $t$, the learner predicts by playing ${\widehat{\bm{u}}}_t$ in a closed convex set $\mathcal{U} \subset \mathbb{R}^d$, then the environment announces a convex function $\ell_t : \mathcal{U}\rightarrow [0,+\infty[$ and the learner suffers loss $\ell_t({\widehat{\bm{u}}}_t)$. The goal of the learner is to minimize the regret with respect to the single best action $\bm{u}\in \mathcal{U}$ in hindsight (after $T$ rounds); that is, minimizing ${R}^{\bm{u}}_T \coloneqq \sum_{t=1}^T \ell_t({\widehat{\bm{u}}}_t) - \sum_{t=1}^T \ell_t(\bm{u})$ for the worst case $\bm{u}\in \mathcal{U}$. Since the losses are convex, it suffices to bound the sum of linearized losses $\tilde{R}^{\bm{u}}_T \df \sum_{t=1}^T {\langle{\widehat{\bm{u}}}_t - \bm{u},\bm{g}_t\rangle}$, where $\bm{g}_t \coloneqq \nabla \ell_t({\widehat{\bm{u}}}_t)$. We will assume that the set $\mathcal{U}$ is bounded and let $D\in ]0,+\infty[$ be its diameter $$\begin{aligned}
 \label{rad}D \coloneqq \sup_{\bm{u}, \bm{v}\in \mathcal{U}} {\left\lVert\bm{u} - \bm{v}\right\rVert}_2.\end{aligned}$$

Our main contribution in this section is to devise a simple modification of <span style="font-variant:small-caps;">MetaGrad</span> — [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} — which, without prior knowledge of the maximum value of the gradient range $G \coloneqq \max_{t \le T} {\left\lVert\nabla \ell_t({\widehat{\bm u}}_t)\right\rVert}$, guarantees the following regret bound $$\begin{aligned}
   \forall \bm{u}\in \mathcal{U}, \quad  R_T^\u  \leq \tilde{R}^{\bm{u}}_T
   ~=~
   O \del*{\sqrt{{V}^{\bm{u}}_T d\ln T }  + B_T d \ln T}, \label{mresult}
 \end{aligned}$$ where ${V}^{\bm{u}}_T \coloneqq \sum_{t=1}^T {\langle{\widehat{\bm{u}}}_t - \bm{u},\bm{g}_t\rangle}^2$. Consequently, this algorithm inherits the fast convergence results of standard <span style="font-variant:small-caps;">MetaGrad</span> [@Erven2016]. In particular, it was shown that due to the form of the bound in , <span style="font-variant:small-caps;">MetaGrad</span> achieves a logarithmic regret when the sequence of losses are exp-concave [@Erven2016]. Furthermore, when the sequence of gradient functions $(\nabla \ell_t)$ are i.i.d distributed with common distribution $\mathbb{P}$ and satisfy the ($B, \beta$)-Bernstein condition for $B > 0$ and $\beta \in [0, 1]$ with respect to the risk minimizer $\bm{u}^* =\operatorname*{argmin}_{\bm{u}\in \mathcal{U}}\mathbb{E}_{f \sim \mathbb{P}}[f(\bm{u})]$, then <span style="font-variant:small-caps;">MetaGrad</span> (and thus [<span style="font-variant:small-caps;">MetaGrad+C</span>]{}) achieves the expected regret $$\begin{aligned}
  \mathbb{E}\left[{R}^{\bm{u}^*}_T\right]
  ~=~
O \del*{ (d  \ln T)^{\frac{1}{2-\beta}} T^{\frac{1-\beta}{2-\beta}} + d \ln T}.\end{aligned}$$ See [@koolen2016] for more detail.

The <span style="font-variant:small-caps;">MetaGrad</span> Algorithm
--------------------------------------------------------------------

The <span style="font-variant:small-caps;">MetaGrad</span> algorithm runs several sub-algorithms at each round; namely, a set of slave algorithms, which learn the best action in $\mathcal{U}$ given a learning rate $\eta$ in some predefined grid $\mathcal{G}$, and the master algorithm, which learns the best learning rate. The goal of <span style="font-variant:small-caps;">MetaGrad</span> is to maximize the sum of payoff functions $\sum_{t=1}^T f_t(\bm{u},\eta)$ over all $\eta \in \mathcal{G}$ and $\bm{u}\in \mathcal{U}$ simultaneously, where $$\begin{aligned}
\label{surrmeta}
f_t(\bm{u},\eta) \coloneqq - \eta {\langle{\widehat{\bm{u}}}_t -   \bm{u},\bm{g}_t\rangle}  +  \eta^2 {\langle{\widehat{\bm{u}}}_t -   \bm{u},\bm{g}_t\rangle}^2,\quad  t\in  [T],\end{aligned}$$ and ${\widehat{\bm{u}}}_t$ is the master prediction at round $t\geq 1$. Each slave algorithm takes as input a learning rate from a finite, exponentially-spaced grid $\mathcal{G}$ (with ${\lceil{\log_2 \sqrt{T}}\rceil}$ points) within the interval $\left[\frac{1}{5DG\sqrt{T}}, \frac{1}{5DG}\right]$, where $G$ is an upper bound on the norms of the gradients. In this case, the bound $G$ must be known in advance. In what follows, we let $\mathbf{M}_t \coloneqq \sum_{s=1}^t \bm{g}_s\bm{g}_s^{\operatorname{\intercal}}$, for $ t \geq 0$.

#### Slave predictions.

Every slave $\eta \in \mathcal G$ starts with ${\widehat{\bm{u}}}_1^\eta = \bm{0}$. At the end of round $t \ge 1$, it receives the master prediction ${\widehat{\bm{u}}}_t$ and updates the prediction in two steps $$\begin{gathered}
   {\bm{u}}^{\eta}_{{t+1}} \coloneqq {\widehat{\bm{u}}}^{\eta}_t - \eta \mathbf{\Sigma}^{\eta}_{{t+1}} \bm{g}_t  \left(1 + 2 \eta \left( {\widehat{\bm{u}}}^{\eta}_t -{\widehat{\bm{u}}}_t \right)^{\operatorname{\intercal}}\bm{g}_t\right) , \text{ where }\ \mathbf{\Sigma}^{\eta}_{{t+1}} \coloneqq \left( \tfrac{\mathbf{I}}{D^2} +2\eta^2\mathbf{{M}}_t \right)^{-1},
                            \label{quadprog0}\\
                            \label{gaussian}
   \text{ and } \ \ {\widehat{\bm{u}}}^{\eta}_{{t+1}} = \operatorname*{argmin}_{\bm{u}\in \mathcal{U}} \left(\bm{u}_{{t+1}}^{\eta}- \bm{u} \right)^{\operatorname{\intercal}}\left( \mathbf{\Sigma}^{\eta}_{{t+1}}\right)^{-1} \left(\bm{u}_{{t+1}}^{\eta}- \bm{u} \right) ,\end{gathered}$$

#### Master predictions

After receiving the slaves predictions, $\left({\widehat{\bm{u}}}^{\eta}_t\right)_{\eta \in \mathcal{G}}$, the master algorithm aggregates them and outputs ${\widehat{\bm{u}}}_t\in \mathcal{U}$ according to: $$\begin{aligned}
{\widehat{\bm{u}}}_{t} \coloneqq \frac{\sum_{\eta\in \mathcal{G}}  \eta w^{\eta}_t   {\widehat{\bm{u}}}^{\eta}_{t} }{\sum_{\eta \in \mathcal{G}}\eta w^{\eta}_t };\quad w^{\eta}_t \coloneqq e^{- \sum_{s=1}^{t-1} f_s({\widehat{\bm{u}}}^{\eta}_s,\eta)}, \label{masterpred}\end{aligned}$$

As mentioned earlier, the <span style="font-variant:small-caps;">MetaGrad</span> algorithm requires the knowledge of the maximum value of the gradient range $G$ and the horizon $T$ in advance. These are needed to define the grid of the slave algorithms. In the analysis of <span style="font-variant:small-caps;">MetaGrad</span>, it is crucial for the $\eta$’s to be in the right interval in order to invoke a Gaussian exp-concavity result for the surrogate losses in (see e.g. [@Erven2016 Lemma 10]). In the next subsection, we explore a natural extension of <span style="font-variant:small-caps;">MetaGrad</span> which does not require the knowledge of the gradient range or the horizon $T$.

An Extension of <span style="font-variant:small-caps;">MetaGrad</span> for Unknown Gradient Range and Horizon
-------------------------------------------------------------------------------------------------------------

We present a natural extension of <span style="font-variant:small-caps;">MetaGrad</span>, called [<span style="font-variant:small-caps;">MetaGrad+C</span>]{}, which does not assume any knowledge on the gradient range or the horizon. Contrary to the original <span style="font-variant:small-caps;">MetaGrad</span> which requires knowledge of the horizon $T$ to define the grid for the slaves, [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} circumvents this by defining an infinite grid $\mathcal{G}$, in which, at any given round $t\geq1$, only a finite number of slaves (up to $\log_2 t$ many) output a prediction (see Remark \[numslaves\]). Each slave $\eta$ in this grid receives a prior weight $\pi(\eta) \in[0,1]$, where $\sum_{\eta\in \mathcal{G}} \pi(\eta) =1$. The expressions of $\mathcal{G}$ and $\pi$ are given by $$\begin{aligned}
\mathcal{G}  \coloneqq \left\{ \eta_i \coloneqq   \tfrac{2^{-i}}{5 B}: i \in \mathbb{N}  \right\} \label{Ggrid} ;\quad 
\pi(\eta_i) \coloneqq  \tfrac{1}{(i+1)(i+2)},  \ i\in \mathbb{N}.\end{aligned}$$ where $B>0$ is the input to [<span style="font-variant:small-caps;">MetaGrad+C</span>]{}.

### Algorithm Description

#### Preliminaries.

As in the previous subsection, we let ${\widehat{\bm{u}}}_t$ and ${\widehat{\bm{u}}}^{\eta}_{t}$ be the predictions of the master and slave $\eta$, respectively, at round $t\geq1$ (we give their explicit expressions further below). Let $(b_t)$ and $(B_t)$ be the sequences in $\mathbb{R}_{\geq0}$ defined by $$\begin{aligned}
b_t \coloneqq D {\left\lVert\bm{g}_t\right\rVert}_2; \quad \quad  \quad B_t \coloneqq  B \vee \max_{s\in [t]} b_s, \quad  t\in[T], \label{littleb}\end{aligned}$$ where $B$ is the input of [<span style="font-variant:small-caps;">MetaGrad+C</span>]{}, and we use the convention that $B_0 = B$. Using the sequence $(B_t)$, we define the clipped gradients $\bar{\bm{g}}_t \coloneqq \frac{B_{t-1}}{B_t} \bm{g}_t$, and $\forall \bm{u}\in\mathcal{U},\forall t\geq 1, \forall \eta >0$, we let $$\begin{aligned}
\bar{r}^{\bm{u}}_t \coloneqq {\langle{\widehat{\bm{u}}}_t-\bm{u},\bar{\bm{g}}_t\rangle},\quad \quad \bar{f}_t(\bm{u},\eta)\coloneqq - \eta \bar{r}^{\bm{u}}_t + \left(\eta \bar{r}^{\bm{u}}_t\right)^2,\quad \quad \bar{\mathbf{M}}_t\coloneqq  \sum_{s=1}^t \bar{\bm{g}}_s \bar{\bm{g}}_s^{\operatorname{\intercal}}. \label{clippedstuff}\end{aligned}$$ For each slave $\eta\in \mathcal{G}$, we define the time $s_\eta$ to be $$\begin{aligned}
  \label{threshold}
  s_\eta
  ~\df~
  \min\setc*{t \ge 0}{
  \eta    \geq \frac{1}{D \sum_{s=1}^t {\left\lVert\bar{\bm{g}}_s\right\rVert}_2 + B_t}
  },\end{aligned}$$ and define the set $\mathcal{A}_t$ of “active” slaves by $$\begin{aligned}
\mathcal{A}_t \coloneqq \{ \eta \in \mathcal{G}_t : s_\eta <   t \}, \quad  \text{where} \quad \mathcal{G}_t \coloneqq \mathcal{G} \cap \left[0, \tfrac{1}{5B_{t-1}}\right] , \quad t\geq 1.\end{aligned}$$

#### Slaves’ predictions.

A slave $\eta \in \mathcal{A}_t$ issues its first prediction ${\widehat{\bm{u}}}_t^\eta = \bm{0}$ in round $t=s_\eta+1$. From then on, it receives the master prediction ${\widehat{\bm{u}}}_t$ as input and updates in two steps as $$\begin{gathered}
  \bm{u}^{\eta}_{{t+1}} \coloneqq {\widehat{\bm{u}}}^{\eta}_t - \eta \mathbf{\Sigma}^{\eta}_{{t+1}} \bar{\bm{g}}_t  \left(1 + 2 \eta \left( {\widehat{\bm{u}}}^{\eta}_t -{\widehat{\bm{u}}}_t \right)^{\operatorname{\intercal}}\bar{\bm{g}}_t\right),
                          \text{ where }\
  \mathbf{\Sigma}^{\eta}_{{t+1}} \coloneqq \left( \tfrac{\mathbf{I}}{D^2} +2\eta^2\left(\bar{\mathbf{M}}_t -\bar{\mathbf{M}}_{s_{\eta}}\right) \right)^{-1},
                          \nonumber
  \\
 \text{ and }\ \ {\widehat{\bm{u}}}^{\eta}_{{t+1}} = \operatorname*{argmin}_{\bm{u}\in \mathcal{U}} \left(\bm{u}_{{t+1}}^{\eta}- \bm{u} \right)^{\operatorname{\intercal}}\left( \mathbf{\Sigma}^{\eta}_{{t+1}}\right)^{-1} \left(\bm{u}_{{t+1}}^{\eta}- \bm{u} \right).
                          \label{quadprog}\end{gathered}$$ Slaves that are outside the set $\mathcal{A}_t$ at round $t$ are irrelevant to the algorithm[^6]. Note that restricting the slaves to the set $\mathcal{G}_t$ is similar to clipping the upper integral range in the [<span style="font-variant:small-caps;">Squint+C</span>]{} case.

#### Master predictions.

At each round $t\geq1$, the master algorithm receives the slaves predictions $({\widehat{\bm{u}}}_t^{\eta})_{t\in \mathcal{A}_{t}}$ and outputs the $\widehat{\bm{u}}_t$: $$\begin{aligned}
\label{newmaster}
{\widehat{\bm{u}}}_t = \frac{\sum_{\eta \in \mathcal{A}_{t}}\eta   w^{\eta}_t {\widehat{\bm{u}}}_t^{\eta}}{\sum_{\eta \in \mathcal{A}_{t}} \eta  w^{\eta}_t  }; \quad w^{\eta}_t \coloneqq \pi(\eta)  e^{- \sum_{s=s_{\eta}+1}^{t-1} \bar{f}_s({\widehat{\bm{u}}}^{\eta}_s,\eta)}, \quad t\geq 1.\end{aligned}$$

\[numslaves\] At any round $t\geq 1$, the number of active slaves is at most ${\left\lfloor{\log_2 t}\right\rfloor}$. In fact, if $\eta \in \mathcal{A}_t$, then by definition $\eta \geq 1/(D\sum_{s=1}^{s_{\eta}}{\left\lVert\bm{g}_s\right\rVert}_2 + B_{s_{\eta}}) \geq 1/(t B_{t-1})$ (since $s_{\eta}\leq t-1$), and thus $\mathcal{A}_t \subset [1/(tB_{t-1}), 1/(5B_{t-1})]$. Since $\mathcal{A}_t$ is an exponentially-spaced grid with base $2$, there are at most ${\left\lfloor{\log_2 t}\right\rfloor}$ slaves in $\mathcal{A}_t$.

### Analysis

To analyse the performance of [<span style="font-variant:small-caps;">MetaGrad+C</span>]{}, we consider the potential function $$\begin{aligned}
\label{masterpot}
 \Phi_t \coloneqq  \pi(\mathcal{G}_t\setminus \mathcal{A}_t) +  \sum_{\eta\in \mathcal{A}_t}  \pi(\eta)  e^{-\sum_{s=s_{\eta}+1}^t \bar{f}_s({\widehat{\bm{u}}}^{\eta}_s,\eta)}, \quad t\geq 0.\end{aligned}$$ For $\bm{u}\in \mathcal{U}$, we define the pseudo-regret $\tilde{R}^{\bm{u}}_T  \coloneqq \sum^T_{t=1} {\langle{\widehat{\bm{u}}}_t - \bm{u},{\bm{g}}_t\rangle}$ and its clipped version ${\bar{R}}^{\bm{u}}_T  \coloneqq \sum^T_{t=1} {\langle{\widehat{\bm{u}}}_t - \bm{u},\bar{\bm{g}}_t\rangle}$. The following analogue to relates these two regrets.

\[relatingtheregret\] Let $(b_t)$ and $(B_t)$ be as in , respectively, then for all $\bm{u}\in \mathcal{U}$, $$\begin{aligned}
\label{clippedrel}
\tilde{R}^{\bm{u}}_{T} \leq {\bar{R}}^{\bm{u}}_{T} +B_T.\end{aligned}$$

Similarly to the <span style="font-variant:small-caps;">Squint</span> case, one can use the prod-bound to control the growth of this potential function as shown in the proof of the following lemma (see Appendix \[MetaGrad2proofs\]):

\[lemmameta\] [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} guarantees that $\Phi_T \leq \dots \leq  \Phi_0 = 1$, for all $T \in \mathbb{N}$.

We now give a bound on the clipped regret ${\bar{R}}^{\u}_T$ in terms of the clipped variance ${\bar{V}}^{\u}_T \coloneqq \sum_{t=1}^T (\bar{r}^{\u}_t)^2$:

\[naivemeta\] Given input $B>0$, the clipped pseudo-regret for [[<span style="font-variant:small-caps;">MetaGrad+C</span>]{}]{} is bounded by $${\bar{R}}_T^\u\leq
3\sqrt{{\bar{V}}_T^\u C_T} + 15 B_T  C_T
\quad \text{for any $\u \in {\mathcal{U}}$,} \label{naivebound}$$ where $C_T \coloneqq  d\ln\left(1 + \frac{2  \sum_{t=1}^{T-1}
b_t^2 + 2 B^2_{T-1}}{25 d B^2_{T-1}}\right) +  2 \ln \left( \log^+_2
\frac{\sqrt{\sum_{t=1}^Tb^2_t }}{B} +3 \right) + 2$ and $\log_2^+ = 0 \vee \log_2 $.

\[truebound\] We can relate the clipped pseudo-regret to the ordinary regret via $R_T^\u \leq {\tilde{R}}_T^\u \leq {\bar{R}}_T^\u + B_T$ (see ) and on the right-hand side we can also use that ${\bar{V}}_T^\u \leq V_T^\u$.

An important thing to note from the result of Theorem \[naivemeta\] is that the ratio $\sqrt{\sum_{t=1}^Tb^2_t}/B$, could in principle be arbitrarily large if the input $B$ is too small compared to the actual regret range. To resolve this issue, one can use the same restart trick as in the <span style="font-variant:small-caps;">Squint</span> case:

\[blackboxreduction1\] Let [[<span style="font-variant:small-caps;">MetaGrad+L</span>]{}]{} be the result of applying Algorithm \[bb1alg\] to [[<span style="font-variant:small-caps;">MetaGrad+C</span>]{}]{}. Then the regret for [[<span style="font-variant:small-caps;">MetaGrad+L</span>]{}]{} is bounded by $$\begin{aligned}
   {\tilde{R}}_T^\u 
    \leq 3\sqrt{V_T^\u \Gamma_T} + 15 B_T \Gamma_T + 4 B_T
    \quad \text{for all $\u \in {\mathcal{U}}$,}\label{bbbound}\end{aligned}$$ where $\Gamma_T \coloneqq  2 d\ln\left(\frac{27}{25} + \frac{2}{25d}  \sum_{t=1}^{T} \frac{b_t^2}{B^2_{t}}\right) +  4 \ln \left( \log^+_2
\sqrt{\sum_{t=1}^T (\sum_{s=1}^t \frac{b_s}{B_s})^2} +3 \right)+ 4 = O(d
\ln T)$.

In Theorem \[blackboxreduction1\], we have replaced the ratio $\sqrt{\sum_{t=1}^Tb^2_t} /B$ appearing in the (clipped) pseudo-regret bound of [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} by the term $\sigma_T
\coloneqq \sqrt{\sum_{t=1}^T (\sum_{s=1}^t \frac{b_s}{B_s})^2}$ which is always smaller than $T^{\frac{3}{2}}$, but this is acceptable since $\sigma_T$ appears inside a $\ln \ln$. From the bound of Theorem \[blackboxreduction1\] on can easily recover an ordinary regret bound, i.e. a bound on $R^{\bm{u}}_t, \bm{u}\in \mathcal{U}$ (see Remark \[truebound\]).\

Efficient Implementation Through a Reduction to the Sphere {#four}
==========================================================

Using [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} (or <span style="font-variant:small-caps;">MetaGrad</span>), the computation of each vector ${\widehat{\bm{u}}}^{\eta}_t$ requires a (Mahalanobis) projection step onto an arbitrary convex set $\mathcal{U}$. Numerically, this typically requires $O(d^p)$ floating point operations (flops), for some $p \in
 \mathbb{N}$ which depends on the topology of the set $\mathcal{U}$. Since $p$ can be large in many applications, evaluating ${\widehat{\bm{u}}}^{\eta}_{t}$ at each grid point $\eta$ can become computationally prohibitive, especially when the number of grid points grows with $T$ — in the case or [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} there can be at most ${\left\lfloor{\log_2 T}\right\rfloor}$ slaves at round $T\geq1$ (see Remark \[numslaves\]).

An efficient implementation of [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} on the ball {#ballefficient}
-------------------------------------------------------------------------------------------------------

In this subsection, we assume that $\mathcal{U}$ is the ball of diameter $D$, i.e. $\mathcal{U}=\mathcal{B}_{D} \coloneqq \left\{\bm{u} \in \mathbb{R}^d \colon {\left\lVert\bm{u}\right\rVert}_2 \leq D/2 \right\}$. In order to compute the slave prediction ${\widehat{\bm{u}}}^{\eta}_{t+1}$, for $t\geq 1$ and $\eta \in \mathcal{A}_t$, the following quadratic program needs to be solved: $$\begin{aligned}
{\widehat{\bm{u}}}^{\eta}_{t+1} = \operatorname*{argmin}_{\bm{u}\in \mathcal{U}} \left(\bm{u}_{t+1}^{\eta}- \bm{u} \right)^{\operatorname{\intercal}}\left( \mathbf{\Sigma}^{\eta}_{t+1}\right)^{-1} \left(\bm{u}_{t+1}^{\eta}- \bm{u} \right), \label{quadprog2}\end{aligned}$$ where $\bm{u}^{\eta}_{t+1}$ (the unprojected prediction) and $\mathbf{\Sigma}^{\eta}_{t+1}$ (the co-variance matrix) are defined in . Since $\mathcal{U}$ is a ball, can be solved efficiently using the result of following lemma:

\[redquad\] Let $t\geq 1$, $\eta \in \mathcal{A}_t$, and $\bm{v}^{\eta}_{t+1}\coloneqq \left(\tfrac{\mathbf{I}}{D^2} +2\eta^2\left(\bar{\mathbf{M}}_t -\bar{\mathbf{M}}_{s_{\eta}}\right)\right) \bm{u}^{\eta}_{t+1}$. Let $\mathbf{Q}_t$ be an orthogonal matrix which diagonalizes $\bar{\mathbf{M}}_{t}$, and $\mathbf{\Lambda}_t \coloneqq \left[\lambda^i_t\right]_{i=1}^t$ the diagonal matrix which satisfies $\mathbf{Q}_t \bar{\mathbf{M}}_t \mathbf{Q}^{\operatorname{\intercal}}_t = \mathbf{\Lambda}_t$. The solution of is given by ${\widehat{\bm{u}}}^{\eta}_{t+1}=\bm{u}^{\eta}_{t+1}$, if $\bm{u}^{\eta}_{t+1} \in \mathcal{U}$; and otherwise, ${\widehat{\bm{u}}}^{\eta}_{t+1} = \mathbf{Q}_t^{\operatorname{\intercal}} (x_t^{\eta}\mathbf{I} +2 \eta^2 (\mathbf{\Lambda}_t- \mathbf{\Lambda}_{s_{\eta}} ))^{-1}  \mathbf{Q}_t  \bm{v}^{\eta}_{t+1}$, where $x_{t}^{\eta}$ is the unique solution of $$\begin{aligned}
\rho_t^{\eta}(x) \coloneqq \sum_{i=1}^{d} \frac{{\langle\bm{e}_i,\mathbf{Q}_t \bm{v}^{\eta}_{t+1}\rangle}^2}{(x+2\eta^2 (\lambda^i_t -\lambda^i_{s_{\eta}}))^2} =\frac{D^2}{4}, \label{proxyfun}\end{aligned}$$

The proof of the lemma is in Appendix \[fourproof\]. Note that since the matrix $\bar{\mathbf{M}}_t$ is symmetric for all $t\geq 1$, the existence of the matrices $\mathbf{Q}_t$ and $\mathbf{\Lambda}_t$ in Lemma \[redquad\] is always guaranteed. Since $\rho_t^{\eta}$ in is strictly convex and decreasing, one can use the Newton method to efficiently solve $\rho_t^{\eta}(x)=D^2/4$. Thus, since the computation of $\mathbf{Q}_t \bm{v}^{\eta}_{t+1}$ only involves matrix-vector products, Lemma \[redquad\] gives an efficient way of solving .

: A bounded convex set $\mathcal{U}\in \mathbb{R}^d$ with diameter $D$, and a fast [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} implementation on the ball $\mathcal{B}_{D}$, [<span style="font-variant:small-caps;">MetaGrad+C</span>]{}, taking input $B$. Get ${\widehat{\bm{u}}}_t$ from [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} Play ${\widehat{\bm{w}}}_t = \Pi_{\mathcal{U}}({\widehat{\bm{u}}}_t)$, receive $\mathring{\bm{g}}_t = \nabla \ell_t({\widehat{\bm{w}}}_t)$ Set $\bm{g}_t  \in \tfrac{1}{2} \left( \mathring{\bm{g}}_t +{\left\lVert\mathring{\bm{g}}_t\right\rVert}  \partial {\operatorname{d}}_{\mathcal{U}}({\widehat{\bm{u}}}_t)  \right)$ Send $\bm{g}_t$ to [<span style="font-variant:small-caps;">MetaGrad+C</span>]{}

#### Implementation on the ball.

At round $t\geq 1$, the implementation of [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} on the ball $\mathcal{B}_{D}$ keeps in memory the orthogonal matrix $\mathbf{Q}_{t-1}$ which diagonalizes $\bar{\mathbf{M}}_{t-1}$. In this case, since $\bar{\mathbf{M}}_t = \bar{\mathbf{M}}_{t-1}+ \bar{\bm{g}}_t \bar{\bm{g}}_t^{\operatorname{\intercal}}$ it is possible to compute the new matrices $\mathbf{Q}_t$ and $\mathbf{\Lambda}_t$ in $O(d^2)$ flops [@stor2015]. Note that this operation only needs to be performed once — the diagonalization does not depend on $\eta$. Therefore, computing $\mathbf{Q}_t \bm{v}^{\eta}_{t+1}$ (and thus ${\widehat{\bm{u}}}^{\eta}_{t+1}$) can be performed in only $O(d^2)$ flops. Thus, aside from the matrix-vector products, the time complexity involved in computing ${\widehat{\bm{u}}}_{t+1}^{\eta}$ for a given $\eta\in \mathcal{A}_t$ is of the same order as that involved in solving $\rho_t^{\eta}(x)=D^2/4$.

A Reduction to the ball
-----------------------

In this subsection, we make use of a recent technique by [@cutkosky2018] that reduces constrained optimization problems to unconstrained ones, to reduce any OCO problem on an arbitrary bounded convex set $\mathcal{U}\subset\mathbb{R}^d$ to an OCO problem on a ball, where we can apply [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} efficiently. Let $D$ be the diameter of $\mathcal{U}\in \mathbb{R}^d$ as in , so that the ball $\mathcal{B}_D$ of radius $D/2$ encloses $\mathcal{U}$. For $\bm{u}\in \mathcal{U}$, we denote ${\operatorname{d}}_{\mathcal{U}}(\bm{u}) = \min_{\bm{w} \in \mathcal U} {\left\lVert\bm{u}-\bm{w}\right\rVert}_2$ the *distance function* from the set $\mathcal{U}$, and we define $\Pi_{\mathcal{U}}(\u)\coloneqq \{\w\in \mathcal{U}: {\left\lVert\bm{w}-\u\right\rVert}_2 = {\operatorname{d}}_{\mathcal{U}}(\u) \}$.

Algorithm \[OCOGeneral\] reduces the OCO problem on the set $\mathcal{U}$ to one on the ball $\mathcal{B}_{D}$, where [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} is used as a black-box to solve it efficiently. As a result, Algorithm \[OCOGeneral\] (including its [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} subroutine) only performs a single Euclidean projection (as opposed to the projection in Mahalanobis distance as in ) onto the set $\mathcal{U}$, which is applied to the output of [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} — the [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} subroutine only performs projections onto the ball $\mathcal{B}_D$, which can be done efficiently as described in the previous subsection.

Let $\mathring{{R}}^{\bm{u}}_T \coloneqq \sum_{t=1}^T  {\langle{\widehat{\bm{w}}}_t - \bm{u},\mathring{{\operatorname{grad}}}_t\rangle}$ and $\mathring{{V}}^{\bm{u}}_T \coloneqq \sum_{t=1}^T {\langle{\widehat{\bm{w}}}_t - \bm{u},\mathring{{\operatorname{grad}}}_t\rangle}^2$ be the pseudo-regret and variance of Algorithm \[OCOGeneral\]. The following theorem, whose proof is in Appendix \[fourproof\], shows how the regret guarantee of [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} readily transfers to Algorithm \[OCOGeneral\]:

\[reductionbound\] Algorithm \[OCOGeneral\], which uses [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} as a black-box, guarantees: $$\begin{aligned}
\sum_{t=1}^T  \left(\ell_t({\widehat{\bm{w}}}_t) - \ell_t(\bm{u})\right) \leq \mathring{{R}}^{\bm{u}}_T \leq 3 \sqrt{\mathring{{V}}^{\bm{u}}_T {\Gamma}_T} +   24 B_T {\Gamma}_T +B_T,  \ \text{ for }\u\in \mathcal{U},  \label{alg1bound}\end{aligned}$$ where $ {\Gamma}_T \coloneqq  d\ln\left(\frac{27}{25} + \frac{2  \sum_{t=1}^{T-1}
{b}_t^2}{25 d{B}^2_{T-1}}\right) +  2 \ln \left( \log^+_2
\frac{\sqrt{\sum_{t=1}^T {b}_t^2}}{B} +3 \right) + 2= O(d \ln T)$, and $$\begin{aligned}
{b}_t \coloneqq D {\left\lVert{\bm{g}}_t\right\rVert}_2; \quad \quad  \quad {B}_t \coloneqq  B \vee \max_{s\in [t]} {b}_s, \quad  t\in[T]. \label{littlebbre}\end{aligned}$$

Note that Algorithm \[OCOGeneral\], guarantees the same type of regret as [<span style="font-variant:small-caps;">MetaGrad+C</span>]{}, and thus can also adapt to exp-concavity of the losses $(\ell_t)$ and the Bernstein condition.

Conclusion {#sec:conclusion}
==========

We present algorithms that adapt to the Lipschitz constant of the loss for OCO and experts. Stepping back, we see that an interesting combination of problem complexity dimensions can be adapted to, with hardly any overhead in either regret or computation. The main question for future work is to obtain a better understanding of the landscape of interactions between measures of problem complexity and their algorithmic reflection.

One surprising conclusion from our work, which provides a curious contrast with incompatibility of Lipschitz adaptivity with comparator complexity adaptivity in general OCO [@CutkoskyBoahen2017Impossible], is the following observation. Our results for the expert setting, which we phrased for a finite set of $K$ experts, in fact generalise unmodified to priors with infinite support. Considering a countable set of experts, we find a scenario where the comparator complexity $\operatorname{KL}(\rho\|\pi)$ is unbounded, yet our Squint strategy adapts to the Lipschitz constant of the loss without inflating the regret compared to an a-priori known complexity by more than a constant.

A final very interesting question is when it is possible to exploit scenarios with large ranges that occur only very infrequently. A example of this is found in statistical learning with heavy-tailed loss distributions. Martingale methods for such scenarios that are related to our potential functions suggest that it may be necessary to replace the “surrogate” negative quadratic term $f_t(\u,\eta)$ that our algorithms include in the exponent by another function appropriate for the specific distribution [@linecrossing Table 3]. It is not currently clear what individual sequence analogues can be obtained.

\[3\][\#3]{}

\[3\][\#2]{}

Proofs of Section \[Squint2\] {#proofssquint}
=============================

[**of Lemma \[lem:pot.is.small\]**]{} We proceed by induction on $T$. By definition $\Phi_0 = 0$. For $T \ge 0$, the definition gives $$\Phi_{T+1}
  ~=~
  \underbrace{
    \sum_k \pi_k \int_0^\frac{1}{2 B_T} \frac{
      e^{\eta \scale{R}_{T}^k - \eta^2 \scale{V}_{T}^k}
      \del*{
        e^{\eta \scale{r}_{T+1}^k - \eta^2 (\scale{r}_{T+1}^k)^2}
        -
        1}}{\eta} \dif \eta
  }_{\fd Q_1}
  +
  \underbrace{
    \sum_k \pi_k \int_0^\frac{1}{2 B_T} \frac{e^{\eta \scale{R}_{T}^k - \eta^2 \scale{V}_{T}^k} -1}{\eta} \dif \eta
    }_{\fd Q_2}
  .$$ To control the first term $Q_1$, we apply the “prod bound” $e^{x-x^2} \le 1+x$ for $x \ge -1/2$ to $x = \eta \scale r_{T+1}^k$, which we may do as $\eta \scale r_{T+1} \ge - \frac{1}{2 B_T} B_T$. Linearity and the definition of the weights further yield $$Q_1
  ~\le~
  \sum_k \pi_k \int_0^\frac{1}{2 B_T} \frac{
    e^{\eta \scale{R}_{T}^k - \eta^2 \scale{V}_{T}^k}
    \eta \scale{r}_{T+1}^k
  }{\eta} \dif \eta
  ~=~
  \tuple*{
  \sum_k \pi_k \int_0^\frac{1}{2 B_T}
  e^{\eta \scale{R}_{T}^k - \eta^2 \scale{V}_{T}^k}
  \del*{\hat \p_{T+1} - \e_k}
  \dif \eta
  , \scale \vloss_{T+1}}
~=~
0
.$$ To control the second term $Q_2$, we extend the range of the integral to find $$Q_2
  ~\le~
  \sum_k \pi_k \int_0^\frac{1}{2 B_{T-1}} \frac{e^{\eta \scale{R}_{T}^k - \eta^2 \scale{V}_{T}^k} -1}{\eta} \dif \eta
  + \ln \frac{B_T}{B_{T-1}}
  ~=~
  \Phi_T + \ln \frac{B_T}{B_{T-1}}
  .$$

[**of Lemma \[lem:small.is.good\]**]{} For any $\epsilon \in [0, \frac{1}{2 B_{T-1}}]$, we may split the potential as follows $$\Phi_T
    ~=~
    \underbrace{
      \sum_k \pi_k \int_0^\epsilon \frac{e^{\eta \scale{R}_T^k - \eta^2 \scale{V}_T^k} -1}{\eta} \dif \eta
      }_{\fd Q_1}
      +
      \underbrace{
        \sum_k \pi_k \int_\epsilon^\frac{1}{2 B_{T-1}} \frac{e^{\eta \scale{R}_T^k - \eta^2 \scale{V}_T^k} -1}{\eta} \dif \eta
      }_{\fd Q_2}
    .$$ For convenience, let us introduce $\scale b_t \df \max_k \abs{\scale r_t^k} = \frac{B_{t-1}}{B_t} b_t$ and abbreviate $\scale S_T \df \sum_{t=1}^T \scale b_t$. To bound the left term $Q_1$ from below, we use $e^x -1 \ge x$. Then combined with $\scale R_T^k \ge - \scale S_T$ and $\scale V_T^k \le \sum_{t=1}^{T-1} \scale b_t^2 \le B_{T-1} \scale S_T$ we find $$Q_1
    ~\ge~
    \sum_k \pi_k \int_0^\epsilon \scale{R}_T^k - \eta \scale{V}_T^k \dif \eta
    ~\ge~
    - \del*{\epsilon
      + \frac{\epsilon^2}{2} B_{T-1}} \scale S_T
    .$$ For the right term $Q_2$, we use KL duality to find $$\begin{aligned}
    Q_2
    &~=~
    \sum_k \pi_k \int_\epsilon^\frac{1}{2 B_{T-1}} \frac{e^{\eta \scale{R}_T^k - \eta^2 \scale{V}_T^k}}{\eta} \dif \eta
    +
      \ln \del*{2 B_{T-1} \epsilon}
    \\
    &~\ge~
    e^{-\operatorname{KL}\delcc*{\rho}{\pi}}
     \int_\epsilon^\frac{1}{2 B_{T-1}} \frac{e^{\eta \scale{R}_T^\rho - \eta^2 \scale{V}_T^\rho}}{\eta} \dif \eta
    +
    \ln \del*{2 B_{T-1} \epsilon}
  \end{aligned}$$ Way pick the admissible $\epsilon = \frac{1}{2(\scale S_T + B_{T-1})}$ for which $\del*{\epsilon + \frac{\epsilon^2}{2} B_{T-1}} \scale S_T \le \frac{1}{2}$, and find $$\Phi_T
    ~\ge~
    e^{-\operatorname{KL}\delcc*{\rho}{\pi}}
    \int_\epsilon^\frac{1}{2 B_{T-1}} \frac{e^{\eta \scale{R}_T^\rho - \eta^2 \scale{V}_T^\rho}}{\eta} \dif \eta
    - \frac{1}{2}
    - \ln \del*{1+ \frac{\scale S_T}{B_{T-1}}}$$ which we may reorganise to $$Q_3
    \df
    \ln
    \int_\frac{1}{2(\scale S_T + B_{T-1})}^\frac{1}{2 B_{T-1}} \frac{e^{\eta \scale{R}_T^\rho - \eta^2 \scale{V}_T^\rho}}{\eta} \dif \eta
    ~\le~
    \operatorname{KL}\delcc*{\rho}{\pi}
    + \ln \del*{
      \Phi_T
      + \frac{1}{2}
      + \ln \del*{1+ \frac{\scale S_T}{B_{T-1}}}
    }
    .$$ The argument to bound the integral in $Q_3$ splits in 3 cases. Let us abbreviate $R \equiv \scale R_T^\rho$ and $V \equiv \scale V_T^\rho$. Let $\hat \eta = \frac{R}{2 V}$ be the maximiser of $\eta \to \eta R - \eta^2 V$.

1.  First the important case, where $\intcc{\hat \eta - \frac{1}{\sqrt{2 V}}, \hat \eta} \subseteq \intcc{ \frac{1}{2(\scale S_T + B_{T+1})}, \frac{1}{2 B_{T-1}}}$. Then $$\begin{aligned}
          Q_3
          &~\ge~
          \ln
          \int_{\hat \eta - \frac{1}{\sqrt{2 V}}}^{\hat \eta} \frac{e^{\eta R - \eta^2 V}}{\eta} \dif \eta
          ~\ge~
          \ln
          \int_{\hat \eta - \frac{1}{\sqrt{2 V}}}^{\hat \eta} \frac{e^{(\hat \eta - \frac{1}{\sqrt{2 V}}) R - (\hat \eta - \frac{1}{\sqrt{2 V}})^2 V}}{\eta} \dif \eta
          \\
          &~=~
            (\hat \eta - \frac{1}{\sqrt{2 V}}) R - (\hat \eta - \frac{1}{\sqrt{2 V}})^2 V
            +
            \ln \ln \frac{\hat \eta}{\hat \eta - \frac{1}{\sqrt{2 V}}}
          \\
          &~=~
            \frac{R^2}{4 V}
            - \frac{1}{2}
            +
            \ln \ln \frac{1}{1 - \frac{\sqrt{2 V}}{R}}
            ~\ge~
            \frac{1}{2} \del*{\frac{R}{\sqrt{2 V}} -1}^2
        \end{aligned}$$ where the last inequality uses $\ln \ln \frac{1}{1 - \frac{1}{x}}
          \ge
          1 - x$ for $x \ge 1$, which can be easily verified by a one-dimensional plot. We conclude $$R
            ~\le~
            \sqrt{2 V} \del*{
              1+
              \sqrt{
                2 \operatorname{KL}\delcc*{\rho}{\pi}
                + 2 \ln \del*{
                  \Phi_T
                  + \frac{1}{2}
                  + \ln\del*{1+ \frac {\scale S_T}{B_{T-1}}}
                }
              }
            }
            .$$

2.  Then in the case where $\hat \eta - \frac{1}{\sqrt{2 V}} < \frac{1}{\scale S_T}$, we have $$R
            ~<~
            \sqrt{2 V} + \frac{2 V}{\scale S_T}
            ~\le~
            \sqrt{2 V} + 2 B_{T-1}$$ and we are done again.

3.  We come to the final case where $\hat \eta > \frac{1}{2 B_{T-1}}$, meaning that $R > \frac{V}{B_{T-1}}$. Here we use that for any $u \in \intcc{\frac{1}{2(\scale S_T + B_{T-1})}, \frac{1}{2 B_{T-1}}}$ $$Q_3
          ~\ge~
          \ln
          \int_u^\frac{1}{2 B_{T-1}} \frac{e^{u R - u^2 V}}{\eta} \dif \eta
          ~\ge~
          u R (1 - u B_{T-1})
          +
          \ln \ln \frac{1}{2 u B_{T-1}}$$ and hence $$R
          \le
          \frac{
            Q_3
            - \ln \ln \frac{1}{2 u B_{T-1}}
          }{
            u (1 - u B_{T-1})
          }
          .$$ Picking the feasible $u = \frac{5 - \sqrt{5}}{10 B_{T-1}}$ and using $        - \ln \ln \frac{5}{5 - \sqrt{5}} \le \ln 2$ results in $$R
          ~\le~
          5 B_{T-1}
          \del*{
            \operatorname{KL}\delcc*{\rho}{\pi}
            + \ln \del*{
              \Phi_T
              + \frac{1}{2}
              + \ln \del*{1+ \frac{\scale S_T}{B_{T-1}}}
            }
            + \ln 2
          }
          .$$ Finally, using the fact that $$\frac{\scale S_T}{B_{T-1}}=   \frac{1}{B_{T-1}} \sum_{t=1}^{T} \frac{B_{t-1}}{B_t} b_t  \leq 1+  \sum_{t=1}^{T-1} \frac{b_t}{B_t}$$ concludes the proof.

iin [1,...,10]{} [ (ni) at (i,0) ; ]{} (begin) at (-1,0); (dots) at (0,0)[$\dots$]{}; ; ; ; ;

(6.5,-1) – (6.5,+1) node\[above\] [final restart]{}; (3.5,-1) – (3.5,+1) node\[above\] [penultimate restart]{};

(6.5+.05,-1) – (10-.05,-1) node \[pos=0.5,anchor=north,yshift=-2em\] [$\sqrt{V}$ bound]{};

(3.5+.05,-1) – (6.5-.05,-1) node \[pos=0.5,anchor=north,yshift=-2em\] [$\sqrt{V}$ bound]{};

(-1+.05,-1) – (3.5-.05,-1) node \[pos=0.5,anchor=north,yshift=-2em\] [tiny]{};

(6.5,-1.5) to \[bend left=80\] (1.25,-2.5); at (3.5,-3) [implies]{};

[**of Theorem \[blackboxreduction0\]**]{} The idea of the proof is to analyse the rounds in three parts, as shown in Figure \[fig:bd.strategy\]. For comparator $\rho \in \triangle_K$, $B>0$ and $\tau_1,\tau_2 \in \mathbb{N}$ such that $\tau_1 < \tau_2$, we define the regret $R^{\rho}_{(\tau_1,\tau_2]}$ and variance $V^{\rho}_{(\tau_1,\tau_2]}$ of [<span style="font-variant:small-caps;">Squint+C</span>]{} started at round $\tau_1+1$ (with input $B_{\tau_1}$) and terminated after round $\tau_2$ by $$\begin{gathered}
R^{\rho}_{(\tau_1,\tau_2]}  \coloneqq \sum_{t=\tau_1+1}^{\tau_2}  \mathbb{E}_{\rho(k) } \left[r^{k}_t\right], \quad  V^{\rho}_{(\tau_1,\tau_2]}  \coloneqq \sum_{t=\tau_1+1}^{\tau_2}  \mathbb{E}_{\rho(k) } \left[(r^{k}_t)^2\right].
 \end{gathered}$$ We also define $$\begin{aligned}
\Gamma^{\rho}_{(\tau_1,\tau_2]} ~\df~
    \operatorname{KL}\delcc*{\rho}{\pi}
    + \ln \del*{
      \ln \sum_{t=1}^{\tau_2-1} \frac{b_t}{B_t}
      + \frac{1}{2}
      + \ln \left(2+  \sum_{t=\tau_1+1}^{\tau_2-1} \frac{b_{t}}{B_t} \right)
    }.
  \end{aligned}$$ If we assume that $\frac{B_{\tau_2-1}}{B_{\tau_1}} \leq \sum_{t=1}^{\tau_2-1} \frac{b_t}{B_t}$ (this corresponds to the case when the restart condition in line \[line:runmetagrad\] of Algorithm \[bb1alg\] is not triggered at round $\tau_2-1$), then from Lemma \[lem:pot.is.small\] the potential function $\Phi_{\tau_2}$, can be bounded by $$\begin{aligned}
\label{boundedpotent}
\Phi_{\tau_2} \leq \ln \frac{B_{\tau_2-1}}{B_{\tau_1}}\leq \sum_{t=1}^{\tau_2-1} \frac{b_t}{B_t}.\end{aligned}$$ Using this together with Lemma \[lem:small.is.good\] and , we get the following bound on the regret for [<span style="font-variant:small-caps;">Squint+L</span>]{} : $$\begin{gathered}
R^{\rho}_{(\tau_1,\tau_2]} \leq \sqrt{2    V_{(\tau_1,\tau_2]}^\rho} \del*{
      1+
      \sqrt{2 \Gamma_{(\tau_1,\tau_2]}^{\rho}}
    }
    +
    5 B_{\tau_2}
    \del*{\Gamma_{(\tau_1,\tau_2]}^{\rho}+ \ln 2} +B_{\tau_2}.
 \end{gathered}$$ Now assume without loss of generality that $b_1 \neq 0$. Then the regret of [<span style="font-variant:small-caps;">Squint+L</span>]{} in round one is bounded by $B_1 \leq B_T$, and [<span style="font-variant:small-caps;">Squint+C</span>]{} is started for the first time in round $t=2$ with input $B=B_1$.

Now suppose first that the restart condition in line \[line:runmetagrad\] of Algorithm \[bb1alg\] is never triggered, which means that $\frac{B_t}{B_1}\leq \sum_{s=1}^t
\frac{b_s}{B_s}$ for all rounds $t=2,\ldots,T$. Then for any comparator distribution $\rho \in \triangle_K$, the result follows from Lemma \[lem:small.is.good\] and the fact that $V^{\rho}_{(1:T]} \leq  V_T^{\rho}$ and the fact that $\Gamma^{\rho}_{(1:T]}  \leq  \Gamma_T^{\rho}$.

Alternatively, suppose there is at least one restart. Then let $1 \leq
\tau_1 < \tau_2< T$ be such that $(\tau_1,\tau_2]$ and $(\tau_2,T]$ are the two intervals over which the last two runs of [<span style="font-variant:small-caps;">Squint+C</span>]{} occurred. We invoke Theorem \[lem:small.is.good\] separately for both these intervals to bound $$\begin{aligned}
  R_{(\tau_1,T]}^{\rho}
    &\leq
      \sqrt{2    V_{(\tau_1,\tau_2]}^\rho} \del*{
      1+
      \sqrt{2 \Gamma_{(\tau_1,\tau_2]}^{\rho}}
    }
    +
    5 B_{\tau_2}
    \del*{\Gamma_{(\tau_1,\tau_2]}^{\rho}+ \ln 2} +B_{\tau_2}. \nonumber\\
     &\quad+ \sqrt{2    V_{(\tau_2,T]}^\rho} \del*{
      1+
      \sqrt{2 \Gamma_{(\tau_2,T]}^{\rho}}
    }
    +
    5 B_{T}
    \del*{\Gamma_{(\tau_2,T]}^{\rho}+ \ln 2} +B_{T}. \nonumber\\
    &\leq
     2 \sqrt{    V_{(\tau_1,T]}^\rho} \del*{
      1+
      \sqrt{2 \Gamma_{(\tau_1,T]}^{\rho}}
    }
    +
    10 B_{T}
    \del*{\Gamma_{(\tau_1,T]}^{\rho}+ \ln 2} +2B_T, \label{seclast} \\
    & \leq
     2 \sqrt{    V_T^\rho} \del*{
      1+
      \sqrt{2 \Gamma_T^{\rho}}
    }
    +
    10 B_{T} 
    \del*{\Gamma_T^{\rho}+ \ln 2} +2B_T.\nonumber\end{aligned}$$ where in we used the fact that $\sqrt{x} +\sqrt{y}\leq \sqrt{2x+2y}$.

If there is exactly one restart, then this implies the desired result. If there are multiple restarts, then the proof is completed by bounding the contribution to the regret of all rounds $2,\ldots,\tau_1$ by $$\begin{aligned}
  R_{(1,\tau_1]}^\u
    \leq \sum_{t=2}^{\tau_1} b_t
    \leq B_{\tau_1}\sum_{t=1}^{\tau_1} \frac{b_t}{B_t}
    \leq B_{\tau_1}\sum_{t=1}^{\tau_2} \frac{b_t}{B_t}
    < B_{\tau_2}
    \leq B_T,\end{aligned}$$ where the second to last inequality holds because there was a restart at $t=\tau_2$. Finally, by bounding the instantaneous regret from the first round by $B_T$, we obtain the desired result.

Proofs of Section \[MetaC\] {#MetaGrad2proofs}
===========================

[**of Lemma \[relatingtheregret\]**]{} Let $\bm{u} \in \mathcal{U}$, and denote $r^{\bm{u}}_t \coloneqq {\langle{\widehat{\bm{u}}}_t-\bm{u},{\operatorname{grad}_}t\rangle}$ and $\bar{r}^{\bm{u}}_t \coloneqq {\langle{\widehat{\bm{u}}}_t-\bm{u},\bar{\bm{g}}_t\rangle}$. We have $$\begin{aligned}
\label{eq:ashoknew} 
  \tilde{R}_T^{\bm{u}}
  -
  \scale R_T^{\bm{u}}
  ~\df~
  \sum_{t=1}^T \del*{r_t^{\bm{u}}- \scale r_t^{\bm{u}}}
  ~=~
  \sum_{t=1}^T \del*{B_t - B_{t-1}} \frac{r_t^{\bm{u}}}{B_t}
  ~\le~
  B_T - B_0
  .
  \end{aligned}$$ where to get to the last inequality we used Cauchy Schwarz inequality and the fact that $\mathcal{U}$ has diameter $D$, which imply that $|r^{\bm{u}}_t| \leq B_t$.

[**of Lemma \[lemmameta\]**]{} Let $t\geq 1$. To simplify notation, we denote $\bar{r}_s^{\eta} \coloneqq {\langle{\widehat{\bm{u}}}_s - {\widehat{\bm{u}}}^{\eta}_s,\bar{\bm{g}}_s\rangle}$, for $\bm{u}\in \mathcal{U}$ and $s\in \mathbb{N}$. By appealing to the prod-bound, we have $$\begin{aligned}
  \Phi_{t+1}
  &~=~
    \pi(\mathcal{G}_{t+1}\setminus \mathcal{A}_{t+1})
    +  \sum_{\eta\in \mathcal{A}_{t+1}}  w^{\eta}_{t+1} \del*{e^{\eta \bar{r}^{\eta}_{t+1} - \eta (\bar{r}^{\eta}_{t+1})^2}-1}
    +  \sum_{\eta\in \mathcal{A}_{t+1}}  w^{\eta}_{t+1}
  \\
  &~\le~
    \pi(\mathcal{G}_{t+1}\setminus \mathcal{A}_{t+1})
    +  \sum_{\eta\in \mathcal{A}_{t+1}}    w^{\eta}_{t+1} \eta \bar{r}^{\eta}_{t+1}
    +  \sum_{\eta\in \mathcal{A}_{t+1}}    w^{\eta}_{t+1}\end{aligned}$$ Now by $$\sum_{\eta\in \mathcal{A}_{t+1}} w^{\eta}_{t+1} \eta \bar{r}^{\eta}_{t+1}
~=~
\sum_{\eta\in \mathcal{A}_{t+1}} \eta w^{\eta}_{t+1} ({\widehat{\bm{u}}}_{t+1} - {\widehat{\bm{u}}}^{\eta}_{t+1})^{\operatorname{\intercal}} \bar{\bm{g}}_t
~=~
0.$$ Moreover, by definition of $\mathcal G_t$ and $\mathcal A_t$, $$\begin{aligned}
  &  \pi(\mathcal{G}_{t+1}\setminus \mathcal{A}_{t+1})
    +  \sum_{\eta\in \mathcal{A}_{t+1}}    w^{\eta}_{t+1}
  ~=~
    \pi(\set*{\eta \in \mathcal{G}_{t+1} : s_\eta > t})
    +  \sum_{\eta \in \mathcal G_{t+1} : s_\eta \le t}    w^{\eta}_{t+1}
  \\
  &~\le~
  \pi(\set*{\eta \in \mathcal{G}_{t} : s_\eta > t})
    +  \sum_{\eta \in \mathcal G_{t} : s_\eta \le t}    w^{\eta}_{t+1}
  ~=~
  \pi(\set*{\eta \in \mathcal{G}_{t} : s_\eta \ge t})
    +  \sum_{\eta \in \mathcal G_{t} : s_\eta < t}    w^{\eta}_{t+1}
  \\
  &~=~
  \pi(\mathcal{G}_{t} \setminus \mathcal A_t)
    +  \sum_{\eta \in \mathcal A_{t}}    w^{\eta}_{t+1}
    ~=~
    \Phi_t
    .\end{aligned}$$ Where we used that $w_{s_\eta+1}^\eta = \pi(\eta)$. Finally, as $\mathcal A_0 = \emptyset$ and $\mathcal G_0 = \mathcal G$, we find $\Phi_0 = \pi(\mathcal{G}) = 1$.

[**of Theorem \[naivemeta\]**]{} Throughout this proof we will deal with slaves $\eta \in \mathcal G_T \setminus \mathcal A_T$ that are provisioned but not active yet by time $T$, and we will interpret their $s_\eta = T$ for uniform treatment, even though technically all we know from is that $s_\eta \ge T$. First due to Lemma \[lemmameta\], we have $\Phi_T\leq 1$, where $\Phi_T$ is the potential defined in . Taking logarithms and rearranging, we find $$\begin{aligned}
 \forall \eta \in \mathcal{G}_T,\quad  -\sum_{t=s_{\eta}+1}^T \bar{f}_t({\widehat{\bm{u}}}^{\eta}_t,\eta)   \leq - \ln \pi(\eta).  \label{boundmaster}\end{aligned}$$ On the other hand, every slave $\eta\in \mathcal{G}_T$ guarantees the following regret for the rounds $t=s_\eta+1,\dots,T$ (see @Erven2016 [Lemma 5]): $$\begin{aligned}
 \sum_{t=s_\eta+1}^T \left( \bar{f}_t({\widehat{\bm{u}}}^{\eta}_t,\eta) -  \bar{f}_t(\bm{u},\eta) \right) & \leq   \ln \det\left(\mathbf{I} + 2 \eta^2 D^2 (\bar{\mathbf{M}}_T -\bar{\mathbf{M}}_{s_\eta}) \right) +\tfrac{{\left\lVert\bm{u}\right\rVert}^2}{2 D^2}, \nonumber \\ &\leq  d\ln\left( 1 +\tfrac{2 D^2}{25 d B^2_{T-1}}{\operatorname{tr}}{\bar{\mathbf{M}}_T} \right)+\tfrac{{\left\lVert\bm{u}\right\rVert}^2}{2 D^2},\label{boundslave}\end{aligned}$$ where in we used concavity of $\ln\det$, $\bar{\mathbf{M}}_{s_\eta} \succeq \bm{0}$ and the fact that $\eta \in \mathcal{G}_T \subset \left[0,\frac{1}{5 B_{T-1}}\right]$. We then invert the wakeup condition at time $s_\eta-1$ to infer $$\begin{aligned}
   -\sum_{t=1}^{s_\eta}    \bar{f}_t(\bm{u},\eta) &\le  \eta \sum_{t=1}^{s_\eta}  \bar r_t^\u
                                                      \le
                                                      \frac{
                                                      \sum_{t=1}^{s_\eta-1}   \bar r_t^\u
                                                      + \bar r_{s_\eta}^\u
                                                      }{D \sum_{t=1}^{s_\eta-1}
                                                      {\left\lVert\bar{\bm{g}}_t\right\rVert}_2 + B_{s_\eta-1}}
                                                      \leq 1. \label{eq:lowbound}
 \end{aligned}$$ Combining the bounds , , and , then dividing through by $\eta$, gives: $$\begin{aligned}
\forall \eta\in  \mathcal{G}_T,  \quad {\bar{R}}^{\bm{u}}_T \leq \eta {\bar{V}}^{\u}_T +\tfrac{1}{\eta} C_T(\eta),\label{gridpointregret}\end{aligned}$$ where $C_T(\eta) \coloneqq  d\ln\left( 1 +\tfrac{2D^2}{25 d B^2_{T-1}}{\operatorname{tr}}{\bar{\mathbf{M}}_T} \right) - \ln \pi(\eta)   + 2$.

Let $C_T$ be as in the theorem statement and let $\eta_*$ be the estimator defined by $\eta_*\coloneqq \sqrt{C_T/{\bar{V}}^{\u}_T}$. Suppose that $\eta_*\leq \frac{1}{5B_{T-1}}$. By construction of the grid, there exists $\hat{\eta} \in \mathcal{G}_T$ such that $\hat{\eta} \in \left[\eta_*/2, \eta_*\right]$. On the other hand, the estimator $\eta_*$ can be lower bounded by $1/\sqrt{{{\bar{V}}}^{\bm{u}}_T}$, since $C_T \geq 1$. From this lower bound on $\eta_*$ and the fact that there exists $ i\in \mathbb{N}$ such that $2^{- i}/(5B_0) =  \hat{\eta} \in \left[\eta_*/2, \eta_*\right]$, we have $2^{-i}/(5B_0) \geq \frac{1}{2\sqrt{{{\bar{V}}}^{\bm{u}}_T}}$. This implies that the prior weight on $\hat{\eta}$ satisfies $$\begin{aligned}
 \frac{1}{\pi(\hat{\eta})} = ( i +1)( i +2) \leq  \left( \log_2 \tfrac{2 \sqrt{ {{\bar{V}}}^{\bm{u}}_T}}{5B_0}+1 \right) \left( \log_2 \tfrac{2 \sqrt{ {{\bar{V}}}^{\bm{u}}_T}}{5B_0}+2\right) \leq \left(\log_2 \tfrac{ \sqrt{{{\bar{V}}}^{\bm{u}}_T}}{B_0}+3\right)^2. \label{priorbound}
 \end{aligned}$$ Note also that from the fact that $1/\sqrt{{{\bar{V}}}^{\bm{u}}_T} \leq  \eta_* \leq 1/(5B_{T-1})\leq 1/(5B_0)$, we have $\sqrt{{{\bar{V}}}^{\bm{u}}_T} /B_0 \geq 2$. This fact combined with , implies that $C_T(\hat{\eta})\leq C_T$, where $C_T$ is as in the statement of the theorem. Plugging $\hat{\eta}$ into and using the fact that $ \hat{\eta} \in\left[\eta_*/2, \eta_*\right]$, gives $$\begin{aligned}
\label{firstbound}
{\bar{R}}^{\bm{u}}_{T} \leq \hat{\eta}  {\bar{V}}^{\bm{u}}_T + \tfrac{1}{\hat{\eta}} C_T(\hat{\eta}) \leq \eta_*  {\bar{V}}^{\bm{u}}_T + \tfrac{2}{\eta_*} C_T =3 \sqrt{{\bar{V}}^{\bm{u}}_T C_T}.\end{aligned}$$ Now suppose that $\eta_*>\frac{1}{5B_{T-1}}$. Let $\hat{\eta} \coloneqq \max \mathcal{G}_T \geq \frac{1}{10B_{T-1}}$, where the last inequality follows by construction of $\mathcal{G}_T$. Note that in this case $\frac{1}{\pi(\hat{\eta})} \leq (\log_2 \frac{2B_{T-1}}{B_0}+1)(\log_2 \frac{2B_{T-1}}{B_0}+2)$, and thus, we still have $C_T(\hat{\eta})\leq C_T$. Plugging $\hat{\eta}$ into and using the assumption on $\eta_*$, we obtain $$\begin{aligned}
\label{secondbound}
{\bar{R}}^{\bm{u}}_{T} \leq \hat{\eta}  {\bar{V}}_T^{\bm{u}} + \tfrac{1}{\hat{\eta}} C_T(\hat{\eta}) \leq \hat{\eta}  {\bar{V}}_T^{\bm{u}} + \tfrac{1}{\hat{\eta}} C_T \leq 15 B_TC_T.\end{aligned}$$ By combining and , we get the desired result.

[**of Theorem \[blackboxreduction1\]**]{} \[naivemetarestartproof\] Assume without loss of generality that $b_1 \neq 0$. Then the regret of [[<span style="font-variant:small-caps;">MetaGrad+L</span>]{}]{} in round one is bounded by $B_1 \leq B_T$, and [[<span style="font-variant:small-caps;">MetaGrad+C</span>]{}]{} is started for the first time in round $t=2$ with parameter $B=B_1$.

Let $V_{(1:T]}^\u$ and $C_{(1:T]}$ represent the quantities denoted by $V^{\bm{u}}_T$ and $C_T$ in Theorem \[naivemeta\] but measured on rounds $2,\ldots,T$. Now suppose first that the restart condition in line \[line:runmetagrad\] of Algorithm \[bb1alg\] is never triggered, which means that $$\begin{aligned}
\frac{B_t}{B_1}\leq \sum_{s=1}^t
\frac{b_s}{B_s}, \quad \text{ for all rounds $t=2,\dots,T$} \label{norestart} \end{aligned}$$ Then the result follows from Theorem \[naivemeta\] and $$\begin{aligned}
 V_{(1:T]}^\u &\leq V_T^\u,\\
 C_{(1:T]},
  &= d\ln\left(\frac{27}{25} + \frac{2}{25d} \frac{\sum_{t=2}^{T-1} b_t^2 }{B^2_{T-1}}  \right) +  2 \ln \left( \log^+_2
    \frac{\sqrt{\sum_{t=2}^T b_t^2}}{B_1} +3  \right) + 2,\nonumber  \\
  &\leq d\ln\left( \frac{27}{25} + \frac{2}{25d} \frac{\sum_{t=2}^{T-1}
    b_t^2}{B^2_{T-1}}\right) +  2 \ln \left( \log^+_2
    \sqrt{\sum_{t=2}^T \left(\sum_{s=1}^t \frac{b_s}{B_s}\right)^2} +3 \right) + 2, \label{usethis}\\
 & \leq \Gamma_T,\nonumber\end{aligned}$$ where in , we used . Alternatively, suppose there is at least one restart. Then let $1 \leq
\tau_1 < \tau_2< T$ be such that $(\tau_1,\tau_2]$ and $(\tau_2,T]$ are the two intervals over which the last two runs of [[<span style="font-variant:small-caps;">MetaGrad+C</span>]{}]{} occurred. We invoke Theorem \[naivemeta\] separately for both these intervals to bound $$\begin{aligned}
  R_{(\tau_1,T]}^\u
    &\leq
      3\sqrt{V_{(\tau_1,\tau_2]}^\u C_{(\tau_1,\tau_2]}}
        + 15 B_T  C_{(\tau_1,\tau_2]} + B_{\tau_2}\\
     &\quad+ 3\sqrt{V_{(\tau_2,T]}^\u C_{(\tau_2,T]}}
        + 15 B_T  C_{(\tau_2,T]} + B_T\\
    &\leq
      3\sqrt{V_{(\tau_1,\tau_2]}^\u \Gamma_T/2}
      + 3\sqrt{V_{(\tau_2,T]}^\u \Gamma_T/2}
      + 15 B_T \Gamma_T + 2 B_T\\
    &\leq
      3\sqrt{V_{(\tau_1,T]}^\u \Gamma_T}
      + 15 B_T \Gamma_T + 2 B_T,\end{aligned}$$ where a subscript $(\tau_1,\tau_2]$ indicates a quantity measured only on rounds $\tau_1+1,\ldots,\tau_2$ and the last inequality uses $\sqrt{x} + \sqrt{y} \leq \sqrt{2x + 2y}$.

If there is exactly one restart, then this implies the desired result. If there are multiple restarts, then the proof is completed by bounding the contribution to the regret of all rounds $2,\ldots,\tau_1$ by $$\begin{aligned}
  R_{(1,\tau_1]}^\u
    \leq \sum_{t=2}^{\tau_1} b_t
    \leq B_{\tau_1}\sum_{t=1}^{\tau_1} \frac{b_t}{B_t}
    \leq B_{\tau_1}\sum_{t=1}^{\tau_2} \frac{b_t}{B_t}
    < B_{\tau_2}
    \leq B_T,\end{aligned}$$ where the second to last inequality holds because there was a restart at $t=\tau_2$. Finally, by bounding the instantaneous regret from the first round by $B_T$, we obtain the desired result.

Proofs of Section \[four\] {#fourproof}
==========================

[**of Lemma \[redquad\]**]{} We use the Lagrangian multiplier to solve . To this end let $$\begin{aligned}
\mathcal{L}(\bm{u},\mu) \coloneqq \left(\bm{u}_{t+1}^{\eta}- \bm{u} \right)^{\operatorname{\intercal}}\left( \mathbf{\Sigma}^{\eta}_{t+1}\right)^{-1} \left(\bm{u}_{t+1}^{\eta}- \bm{u} \right) +\mu (\bm{u}^{\operatorname{\intercal}} \bm{u} -D^2).  \end{aligned}$$ Setting $\frac{\partial \mathcal{L}}{\partial \bm{u}} =0$ implies that $2 \left( \mathbf{\Sigma}^{\eta}_{t+1}\right)^{-1} \left( \bm{u}-\bm{u}_{t+1}^{\eta} \right) +2\mu \bm{u}=0$. After rearranging, this becomes $$\begin{aligned}
\bm{u} &=  \left( \left(\mu + \tfrac{1}{D^2} \right) \mathbf{I} + 2 \eta^2 (\bar{\mathbf{M}}_t - \bar{\mathbf{M}}_{s_{\eta}})   \right)^{-1}  \left(\mathbf{\Sigma}^{\eta}_{t+1}\right)^{-1} \bm{u}^{\eta}_t, \label{solution} \\
& = \mathbf{Q}^{\operatorname{\intercal}}_t \left(x \mathbf{I} +2 \eta^2 (\mathbf{\Lambda}_t-\mathbf{\Lambda}_{s_{\eta}})  \right)^{-1} \mathbf{Q}_t  \bm{v}^{\eta}_{t+1}, \nonumber\end{aligned}$$ where we set $x\coloneqq \mu +\frac{1}{D^2}$. The result follows by observing that $\bm{u}^{\operatorname{\intercal}} \bm{u} = D^2/4 \iff \rho_t^{\eta}(x)=D^2/4$.

[**of Theorem \[reductionbound\]**]{} Let $\mathring{R}^{\bm{u}}_T \coloneqq \sum_{t=1}^T {\langle{\widehat{\bm{u}}}_t - \bm{u},\mathring{\bm{g}}_t\rangle}$ and $\mathring{V}^{\bm{u}}_T \coloneqq \sum_{t=1}^T {\langle{\widehat{\bm{u}}}_t - \bm{u},\mathring{\bm{g}}_t\rangle}^2$ be the pseudo-regret and variance of Algorithm \[OCOGeneral\]. From Theorem \[naivemeta\], the bound on the pseudo-regret $\tilde{R}^{\bm{u}}_T =\sum_{i=1}^T {\langle{\widehat{\bm{u}}}_t -\bm{u},{\bm{g}}_t\rangle}$ with respect to ${V}_T^{\bm{u}} =\sum_{t=1}^T {\langle{\widehat{\bm{u}}}_t -\bm{u},{\bm{g}}_t\rangle}^2$ for the [<span style="font-variant:small-caps;">MetaGrad+C</span>]{} subroutine in Algorithm \[OCOGeneral\], can be written as $$\begin{aligned}
\forall \bm{u}\in \mathcal{U}, \forall \eta >0, \quad \eta {\tilde{R}}^{\bm{u}}_T - \eta^2 {V}^{\bm{u}}_T \leq \tfrac{9}{4}{\Gamma}_T + 15 \eta B_T \left(   {\Gamma}_T  + \tfrac{1}{15} \right), \label{compbound}\end{aligned}$$ where ${\Gamma}_T^\u \coloneqq  d\ln\left(\frac{27}{25} + \frac{2  \sum_{t=1}^{T-1}
{b}_t^2}{25d {B}^2_{T-1}}\right) +  2 \ln \left( \log^+_2
\frac{\sqrt{\sum_{t=1}^T {b}^2_t}}{B} +3 \right) + 2$.

As in the proof of [@cutkosky2018 Proposition 1], we have $$\begin{aligned}
\label{cutkow} {\langle{\widehat{\bm{w}}}_t - \bm{u},\mathring{\bm{g}}_t\rangle} \leq 2 \mathring{\ell}_t({\widehat{\bm{u}}}_t) - 2\mathring{\ell}_t(\bm{u}),\end{aligned}$$ where ${\widehat{\bm{w}}}_t = \Pi_{\mathcal{U}}({\widehat{\bm{u}}}_t)$ is the prediction of Algorithm \[OCOGeneral\] at round $t$ and $\mathring{\ell}_t$ is the function defined by $\mathring{\ell}_t(\bm{u}) \coloneqq \frac{1}{2}\left( {\langle\mathring{\bm{g}}_t,\bm{u}\rangle} + {\left\lVert\mathring{\bm{g}}_t\right\rVert} {\operatorname{d}}_{\mathcal{U}}(\bm{u})\right)$. By the convexity of $\mathring{\ell}_t$ and the fact that ${\bm{g}}_t \in \partial \mathring{\ell}_t({\widehat{\bm{u}}}_t)$, we have $$\begin{aligned}
{\langle{\widehat{\bm{u}}}_t-\bm{u},{\bm{g}}_t\rangle} \geq  \mathring{\ell}_t({\widehat{\bm{u}}}_t) - \mathring{\ell}_t(\bm{u})\geq \tfrac{1}{2}{\langle{\widehat{\bm{w}}}_t - \bm{u},\mathring{\bm{g}}_t\rangle},\label{useful} \end{aligned}$$ where the right-most inequality follows from . Since the function $x\mapsto x - x^2$ is strictly increasing on $]-\infty, \frac{1}{2}[$, implies $$\begin{aligned}
 \tfrac{\eta}{2}{\langle{\widehat{\bm{w}}}_t - \bm{u},\mathring{\bm{g}}_t\rangle} - \tfrac{\eta^2}{4}{\langle{\widehat{\bm{w}}}_t - \bm{u},\mathring{\bm{g}}_t\rangle} ^2  \leq  \eta {\langle{\widehat{\bm{u}}}_t - \bm{u},{\bm{g}}_t\rangle} - \eta^2 {\langle{\widehat{\bm{u}}}_t - \bm{u},{\bm{g}}_t\rangle}, \nonumber
 \end{aligned}$$ for all $\eta \in \left]0, \frac{1}{2B_{T}} \right]$. Summing over $t=1..T$ and using the bound , we get $$\begin{aligned}
\forall \eta \in \left]0, \tfrac{1}{2B_T} \right],\quad \mathring{R}^{\bm{u}}_T-\tfrac{\eta}{2} \mathring{V}^{\bm{u}}_T  \leq   \tilde{R}^{\bm{u}}_T- {V}^{\bm{u}}_T \leq     \tfrac{9}{4\eta}{\Gamma}_T + 15  B_T \left(   {\Gamma}_T  + \tfrac{1}{15} \right),\label{compbound11}\end{aligned}$$ which leads to, for all $\eta \in \left]0, \tfrac{1}{2B_{T}} \right]$, $$\begin{aligned}
 \mathring{R}^{\bm{u}}_T \leq  \tfrac{\eta}{2} \mathring{V}^{\bm{u}}_T+   \tfrac{9}{4\eta}{\Gamma}_T + 15  B_T \left(   {\Gamma}_T + \tfrac{1}{15} \right),\label{compbound2}\end{aligned}$$ The $\eta$ which minimizes the right-hand side of is given by $\eta_*\coloneqq \sqrt{\frac{9{\Gamma}_T}{2\mathring{V}^{\bm{u}}_T}}$. We consider two cases; suppose first that $\hat{\eta}\leq \frac{1}{2B_T}$. Then, by setting $\eta =\eta_*$, we have $$\begin{aligned}
\label{firstbound2}
 \tfrac{\eta}{2} \mathring{V}_T^{\bm{u}} + \tfrac{9}{4\eta} {\Gamma}_T =3 \sqrt{\mathring{V}^{\bm{u}}_T {\Gamma}_T}.\end{aligned}$$ Now suppose that $\eta_*>\frac{1}{2B_T}$. Then for $\eta = \frac{1}{2B_T}$ we have $$\begin{aligned}
 \tfrac{\eta}{2} \mathring{V}_T^{\bm{u}} + \tfrac{9}{4\eta} {\Gamma}_T \leq 9 B_T {\Gamma}_T. \label{secondbound2}\end{aligned}$$ Combining - yields the desired result.

[^1]: We slightly abuse terminology here, because the standard definition of a Lipschitz constant requires an upper bound on the gradient norms for any parameters $\w$, not just for $\w = \w_t$, and may therefore be larger.

[^2]: Note that <span style="font-variant:small-caps;">AdaHedge</span> is timeless, and so are its refined bounds. Similarly, <span style="font-variant:small-caps;">Squint</span> is timeless (regardless of the prior on the learning rate $\eta$), and so is its CV bound but not its improper bound (which features a $\ln \ln T$).

[^3]: @cutkosky2017 show that their algorithm still achieves a regret of order $O(\ln^4 T)$ under a condition they name $\alpha$-acute convexity. The link of the latter to the more common Bernstein condition is unclear.

[^4]: While the original algorithm is designed for unbounded OCO, their algorithm can still be used for bounded $\mathcal{U}$ via a simple reduction proposed by [@cutkosky2018]

[^5]: We learned this technique from Ashok Cutkosky

[^6]: The predictions of the slaves outside $\mathcal{A}_t$ do not appear anywhere in the description or analysis of the algorithm. Alternatively, we may think of each slave $\eta$ as operating with $\eta_t=0$ in the first $s_\eta$ rounds and with $\eta_t=\eta$ afterwards. The presence of the factor $\eta$ in renders the master oblivious to inactive slaves.
