A second order regret bound for NormalHedge Yoav Freund, Nicholas J. A. Harvey, Victor S. Portella, Yabing Qi, Yu-Xiang Wang Abstract We consider the problem of prediction with expert advice for “easy” sequences. We show that a variant of NormalHedge enjoys a second-order ϵ \epsilon -quantile regret bound of O ⁡ ( V T ​ log ⁡ ( V T / ϵ ) ) O\big(\sqrt{V_{T}\log(V_{T}/\epsilon)}\big) when V T > log ⁡ N V_{T}>\log N , where V T V_{T} is the cumulative second moment of instantaneous per-expert regret averaged with respect to a natural distribution determined by the algorithm. The algorithm is motivated by a continuous time limit using Stochastic Differential Equations. The discrete time analysis uses self-concordance techniques. 1 Introduction Prediction with expert advice is a classic topic in online learning, for which numerous generalizations of the model have been extremely well studied ( 7 ) . For example, several bounds involving variance of the losses have been known for two decades ( 8 ) , whereas bounds that compare to a quantile of the experts have been known for over 15 years ( 9 ) . Ten years ago, 16 posed an open question of developing an algorithm that simultaneously achieves quantile- and variance-based bounds. Moreover, he conjectured that NormalHedge ( 9 ) achieves this bound. The main contribution of this work is a positive answer to this question. We confirm the conjecture that NormalHedge does indeed have a regret bound that is simultaneously quantile- and variance-based. The intuition for our proofs comes from a continuous time viewpoint of online learning that has been explored in various prior work, e.g., ( 15 ; 13 ; 17 ; 19 ; 39 ; 20 ; 21 ) . One advantage of this approach is that it ushers in the helpful viewpoint of differential equations. A key challenge, however, is discretizing the continuous-time solutions without sacrificing performance ( 17 ) . Our main technical contribution is a technique to prove perturbation bounds on derivatives of the NormalHedge potential function via self-concordance . This is a well-studied concept in continuous optimization ( 30 ; 35 ) that has also been explored in theoretical statistics ( 2 ; 32 ) and more recently in online learning ( 4 ) . The notions of self-concordance of which we are aware have a global nature that makes them ineffective in our setting. To overcome that obstacle, we introduce a notion of local self-concordance that is crucial to our analysis. Related work. Many existing algorithms adapt to easy sequences with “small variance” ( 18 ; 23 ; 12 ) . Others enjoy quantile regrets ( 9 ; 10 ; 27 ) , but depend explicitly on the iteration number T . 26 proved quantile regret bound with no T dependence, but only adapts to “small absolute deviation” – a first order bound. 23 were the first to prove a second-order quantile bound that depends on “variance over time”. To our knowledge, the only other existing result that enjoys second-order quantile regret with a “variance over action” is the work of ( 29 ) , though their stated result has a suboptimal dependence on \log(1/\epsilon) . Interestingly, five years ago, 28 proved that adaptive second-order quantile regret \sqrt{V_{T}\log(1/\epsilon)} with a particular version of V_{T} is not possible. The construction does not cover our results because: (1) our definition of V_{T} is different; and (2) our result only achieves \sqrt{V_{T}\log(1/\epsilon)} for V_{T}>\log N , a regime that their construction does not cover. We defer a more detailed review of the associated literature to Appendix A . 2 Problem Setup Symbols and notation. We use standard probability and linear-algebra notation. Boldface letters (e.g., \bm{p},\bm{x},\bm{\ell} ) denote vectors (often in \mathbb{R}^{N} ), and plain letters (e.g., x,t,N,T ) denote scalars; (\cdot)^{\textsf{T}} is transpose and [N]=\{1,\dots,N\} . The inner product is \langle\bm{a},\bm{b}\rangle=\sum_{i=1}^{N}a_{i}b_{i} , and \|\cdot\|_{p} denotes the \ell_{p} norm (by default \|\cdot\|=\|\cdot\|_{2} ). For random variables we write, e.g., i\sim\bm{p} with \bm{p}\in\Delta^{N-1} (the probability simplex), and use \mathbb{P}[\cdot],\mathbb{E}[\cdot] (and conditional/subscripted versions) as usual. For a differentiable f:\mathbb{R}^{d}\to\mathbb{R} , \nabla f and \nabla^{2}f denote the gradient and Hessian; we let \nabla^{2}f(\bm{x})[\bm{a},\bm{b}]=\bm{a}^{\textsf{T}}\nabla^{2}f(\bm{x})\bm{b} . For vector variables, \nabla_{\bm{x}}f and \nabla^{2}_{\bm{x},\bm{x}}f denote partial derivatives with respect to \bm{x} . Learning from Expert Advice. Consider a slight variation on the game of prediction with expert advice 7 . Given number of experts N and a constant B>0 For each iteration j=1,2,3,... . 1. Player chooses the weights as a probability vector \bm{p}_{j}\in\Delta^{N-1} . 2. Nature reveals a loss vector \bm{\ell}_{j}\in\mathbb{R}^{N} satisfying that \max_{i,i^{\prime}\in[N]}\left|\ell_{j,i}-\ell_{j,i^{\prime}}\right|\leq B . 3. Player incurs a loss \langle\bm{p}_{j},\bm{\ell}_{j}\rangle=\mathbb{E}_{i\sim\bm{p}_{j}}[\ell_{j,i}] . The regret vector at step j is \bm{x}_{j}=\sum_{k=1}^{j}(\langle\bm{p}_{k},\bm{\ell}_{k}\rangle\mathbf{1}-\bm{\ell}_{k})\in\mathbb{R}^{N} . We focus on minimizing the \epsilon -quantile regret (against the \lfloor N\epsilon\rfloor -th best expert), defined in iteration T as \mathrm{Regret}_{\epsilon}(T):=x_{T,(\lfloor N\epsilon\rfloor)}\qquad\text{where}~x_{T,(i)}~\text{denotes the $\left\lfloor i\right\rfloor$-th largest coordinate of $\bm{x}_{T}$.} 3 Hedge algorithms using potential functions We focus on hedging algorithms based on potential functions \phi(y,t) , where y=x_{i} is the regret coordinate and t\geq 0 is a continuous “time” variable. Definition 1 . Let \mathcal{D}=\mathbb{R} or \mathcal{D}=[y_{0},\infty) . A function \phi:\mathbb{R}\times[0,\infty)\to\mathbb{R} is a good potential function on \mathcal{D} if it is (1) jointly strictly convex, (2) three-times differentiable, and satisfies: (3) \partial_{y}\phi\geq 0 ; (4) \partial_{t}\phi\leq 0 ; (5) \lim_{t\to\infty}\phi(y,t)=\inf_{y,t}\phi(y,t)\geq 0 , and (6) \phi(\Pi_{\mathcal{D}}(\bm{x}),t)\leq\phi(\bm{x},t) for all x\in\mathbb{R} . Furthermore, we assume (7) the backwards heat equation \partial_{t}\phi=-\frac{1}{2}\partial^{2}_{yy}\phi . Properties (1-6) are natural, while the motivation for property (7) might not be apparent at this point. We discuss the motivation for property (7) in Section 5 . Each good potential function \phi (with domain \mathcal{D} ) induces a hedge algorithm CP ( \phi,\mathcal{D} ) (see the pseudocode in Figure 1 ). The key idea of the algorithm is to maintain a constant total potential \Phi(\bm{x},t)=\sum_{i=1}^{N}\phi(x_{i},t). (1) CP ( \phi , \mathcal{D} ) algorithm Initialize t=t_{0},x_{0,i}=0\;\forall i\in[N],V_{0}=0. Let \Pi_{\mathcal{D}} be the projection to \mathcal{D} , and \tilde{\bm{x}}_{0}\leftarrow\Pi_{\mathcal{D}}(\bm{x}_{0}). For j=1,...,T 1. The algorithm plays probability \bm{p}_{j} where p_{j,i}\propto\frac{\partial}{\partial x}\phi(\tilde{x}_{j-1,i},t_{j-1}) for i\in[N] . 2. Nature reveals loss \ell_{j,i} for every expert i\in[N] . 3. Algorithm incurs instantaneous regret \Delta x_{j,i}:=\mathbb{E}_{k\sim\bm{p}_{j}}[\ell_{j,k}]-\ell_{j,i} for i\in[N] . 4. Algorithm updates \bm{x}_{j}\leftarrow\bm{x}_{j-1}+\Delta\bm{x}_{j} ; \tilde{\bm{x}}_{j}\leftarrow\Pi_{\mathcal{D}}(\bm{x}_{j}) . 5. Algorithm finds \Delta t_{j}\geq 0 s.t. \Phi(\tilde{\bm{x}}_{j},t_{j-1}\!+\!\Delta t_{j})=\Phi(\tilde{\bm{x}}_{j-1},t_{j-1}) and sets t_{j}\leftarrow t_{j-1}+\Delta t_{j} . 6. Algorithm sets V_{j}\leftarrow V_{j-1}+\mathbb{E}_{i\sim\bm{q}_{j}}\left[\Delta x_{j,i}^{2}\right] where \bm{q}_{j}\in\Delta^{N-1} is s.t. q_{j,i}\propto\partial_{xx}\phi(\tilde{x}_{j-1,i},t_{j-1}) Return V_{T} . Figure 1: The Constant Potential Algorithm CP is well-defined for good potentials. Properties (1)-(5) in Definition 1 ensure that the algorithm is well-defined. Properties (1) and (3) imply non-negativity of \phi ’s first and second partial derivatives in y such that \bm{p}_{j} and \bm{q}_{j} are valid probability distributions. The only exception is when \frac{\partial}{\partial x}\phi(x_{i},t)=0\;\;\forall[N] , in which the algorithm can choose an arbitrary \bm{p}\in\Delta^{N-1} to play. Properties (1), (2), (4), and (5) imply that we can always find \Delta t\geq 0 such that the total potential stays constant (this is proven in Lemma 9 ). Efficient computation for \Delta t . \Delta t can be chosen as a function of x,t,\Delta x — information available to the algorithm. Since \Phi is monotonically decreasing with t (Property (4) of Defintion 1 ), \Delta t can be obtained efficiently using bisection. As a result of line 5 of the algorithm, the total potential is kept constant throughout: \Phi(\Pi_{\mathcal{D}}(\bm{x}_{T}),t_{T})=\Phi(\Pi_{\mathcal{D}}(\bm{x}_{T-1}),t_{T-1})=...=\Phi(\Pi_{\mathcal{D}}(\bm{x}_{1}),t_{1})=\Phi(\Pi(\bm{0}),t_{0}). (2) The constant total potential implies a generic bound on the quantile regret of CP ( \phi,\mathcal{D} ) as a function of t (rather than the more common iteration index T ). Lemma 2 (Generic regret bound template) . Assume \phi,\mathcal{D} satisfies Definition 1 . Let t be the time variable that CP encounters at any iteration j . Then the corresponding quantile regret at that iteration can be bounded as follows. \mathrm{Regret}_{\epsilon}~\leq~y\quad\text{where $y$ is the unique solution to}\quad(\epsilon N)\cdot\phi(y,t)=\Phi(\Pi_{\mathcal{D}}(\bm{0}),t_{0}). (3) Proof. The solution y exists and is unique since \phi(\Pi_{\mathcal{D}}(\bm{0}),t)\leq\phi(\Pi_{\mathcal{D}}(\bm{0}),t_{0}) by property (4) of Definition 1 , and since y\mapsto\phi(y,t) is continuous and diverges by (1), (2) and (3). Let the corresponding regret vector at time t be \bm{x} . By ( 2 ) and non-negativity of \phi , \Phi(\Pi_{\mathcal{D}}(\bm{0}),t_{0})=\Phi(\Pi_{\mathcal{D}}(\bm{x}),t)=\sum_{i=1}^{N}\phi(\Pi_{\mathcal{D}}(x_{i}),t)\geq(\epsilon N)\cdot\phi(\Pi_{\mathcal{D}}(x_{(\epsilon N)}),t). Thus (\epsilon N)\cdot\phi(y,t)\geq(\epsilon N)\cdot\phi(\Pi_{\mathcal{D}}(x_{(\epsilon N)}),t) . Thus, using property (3) again, y\geq\Pi_{\mathcal{D}}(x_{(\epsilon N)})\geq x_{(\epsilon N)}=\mathrm{Regret}_{\epsilon}, since z\mapsto\Pi_{\mathcal{D}}(z) is non-decreasing. ∎ Meaning of V_{T} as an output of the algorithm. Note the variable V_{T} that is incremented at each iteration by \langle\bm{q},\Delta\bm{x}^{2}\rangle , similarly to the total loss of the algorithm that is incremented by \langle\bm{p},\bm{\ell}\rangle . V does not need to be computed in the actual implementation of the algorithm, but will be used in our second-order regret bounds. 3.1 Two prominent instances of CP We consider two potentials satisfying Definition 1 : the exponential potential ( 10 ) with \eta>0 , and a variant of NormalHedge ( 9 ) modified by a factor t^{-1/2} to satisfy the backward heat equation: \displaystyle\phi_{\mbox{\tiny exp}}(y,t) \displaystyle=\exp(\sqrt{2}\eta\,y-\eta^{2}t), \displaystyle\mathcal{D} \displaystyle=\mathbb{R}; (4) \displaystyle\phi_{\mbox{\tiny NH}}(y,t) \displaystyle=t^{-1/2}\exp(y^{2}/2t), \displaystyle\mathcal{D} \displaystyle=[0,\infty). (5) Applying ( 3 ) yields the following regret bounds: Lemma 3 (Exponential potential) . For ( 4 ) with t_{0}=0 , the \epsilon -quantile regret satisfies \mathrm{Regret}_{\epsilon}\leq\frac{\eta t}{\sqrt{2}}+\frac{\log(1/\epsilon)}{\sqrt{2}\eta}. Proof. Solving N\epsilon\phi_{\mbox{\tiny exp}}(y,t)=\Phi(\bm{0},0)=N for y implies \sqrt{2}\eta y-\eta^{2}t=\log(1/\epsilon) . The result follows by Lemma 2 . ∎ Lemma 4 (Normal potential) . For ( 5 ) with t_{0}>0 , the \epsilon -quantile regret satisfies \mathrm{Regret}_{\epsilon}\leq\sqrt{t(\log(t/t_{0})+2\log(1/\epsilon))}. Proof. Solving N\epsilon\phi_{\mbox{\tiny NH}}(y,t)=\Phi(\bm{0},t_{0})=Nt_{0}^{-1/2} for y implies y^{2}/2t-\frac{1}{2}\log t=\log(t_{0}^{-1/2})-\log(1/\epsilon) . Rearranging for y yields the bound via Lemma 2 . ∎ Remarks. The bounds above are iteration-free (e.g., invariant to vacuous rounds where \ell_{j,i}=\ell_{j,i^{\prime}} for all i,i^{\prime} , that increase T but not the regret) and hold uniformly for all \epsilon . We refer to the algorithm in Lemma 4 as NormalHedge.BH ; unlike the potential of 9 , it satisfies the backward heat equation , has no hyperparameter, and adapts to the accumulated time parameter t . These lemmas reduce the regret analysis to bounding t ( 9 ) . Our main contribution is connecting t to the cumulative second moment V_{T} . In Section 4 we present these results, followed by a continuous-time interpretation in Section 5 , and finally an overview of the proofs in Section 6 . More discussion of the related work is deferred to Appendix A . 4 Results Our main contribution is to establish CP ( \phi,D ) as a family of online learning algorithms and V_{T} as a measure of the complexity of input sequences. The following three theorems encapsulate our results. Theorem 5 provides a regret upper bound for CP ( \phi_{\mbox{\tiny exp}},\mathbb{R} ), Theorem 6 provides a regret upper bound for CP ( \phi_{\mbox{\tiny NH}},\mathbb{R}_{+} ) and Theorem 7 provides a lower bound that holds for all online algorithms that define V_{T} with respect to a distribution q . Theorem 5 (Exponential Weights) . CP ( \phi_{\mbox{\tiny exp}},\mathbb{R} ) with parameter \eta>0 returns V_{T} , such that \mathrm{Regret}_{\epsilon}(T)\leq\frac{e^{2\sqrt{2}\eta B}\eta}{\sqrt{2}}V_{T}+\frac{\log(1/\epsilon)}{\sqrt{2}\eta}\quad\text{ for any }0<\epsilon\leq 1. Choosing \eta\asymp\min\left\{\sqrt{\log(1/\epsilon)/V_{T}},1/B\right\} yields \mathrm{Regret}_{\epsilon}(T)=O\left(B\log(1/\epsilon)+\sqrt{V_{T}\log(1/\epsilon)}\right). Adaptivity and the Open Problem. This bound involves the cumulative variance V_{T} (which can be \ll T ) but requires tuning \eta based on the unknown V_{T} . 16 conjectured that NormalHedge could achieve this adaptively. The following theorem confirms this; the proof is in Appendix F . Theorem 6 (NormalHedge.BH) . Let t_{0}=\max\{512e^{2}B^{2}\log N,1\} . CP ( \phi_{\mbox{\tiny NH}},\mathbb{R}_{+} ) returns V_{T} such that for all \epsilon\in(0,1) and T\geq 1 : \mathrm{Regret}_{\epsilon}(T)\leq\sqrt{(t_{0}+2V_{T})(\log(t_{0}+2V_{T})+2\log(1/\epsilon))}. Resolution & “Impossibility”. Theorem 6 resolves the COLT’16 open problem ( 16 ) modulo (1) we allow a mild additive O\big(\sqrt{\log N\cdot(\log(1/\epsilon)+\log(V_{T}+\log N))}\big) term (via t_{0} ), and (2) our V_{T} is defined via the potential’s second derivative \bm{q} rather than \bm{p} . These two differences suffice to invalidate the lower bound construction of 28 (see Appendix I for details). When is \bm{q} different from \bm{p} ? For Exponential Weights, \bm{p}=\bm{q} . For NormalHedge.BH, \displaystyle p_{i} \displaystyle\propto\partial_{x}\phi(x_{i},t)=\frac{x_{i}}{t}\phi(x_{i},t)\propto\sqrt{\frac{x_{i}^{2}}{t}}\phi(x_{i},t) \displaystyle q_{i} \displaystyle\propto\partial^{2}_{xx}\phi(x_{i},t)=(\frac{1}{t}+\frac{x_{i}^{2}}{t^{2}})\phi(x_{i},t)\propto\left(1+\frac{x_{i}^{2}}{t}\right)\phi(x_{i},t). Here x_{i} is the i th coordinate of \bm{x}_{j} , indicating the cumulative per-expert regret [\mathrm{Regret}_{i}(j)]_{+} (clipped to 0 ). For all i , \sqrt{\frac{x_{i}^{2}}{t}}=\tilde{O}(1) , so for those leading experts where p_{i} are large, q_{i} is also proportionally large. It is for experts with negative regret when the biggest differences between p and q occur. In this case, x_{i}=p_{i}=0 . While q_{i} remains non-zero, it is still small because \phi(x_{i},t) for the leading experts is exponentially larger than those with negative regrets. In Section 5 we give some intuiton on why a variance measure depending on \bm{q} may be considered the more “natural” one for CP . Theorem 7 (Lower Bound) . Consider a “random walk” adversary where each loss is chosen independently as \ell_{j,i}\in\{-\sigma_{j},\sigma_{j}\} with equal probability (where \sigma_{j}\leq B/2,\sum\sigma_{j}^{2}\to\infty ). There is an explicit constant \epsilon_{0} such that, for any algorithm and 0<\epsilon<\epsilon_{0} , there exists N=N(\epsilon)=\Theta(1/\epsilon^{2}) and T=T(\epsilon) such that \frac{\mathrm{Regret}_{\epsilon}(T)}{\sqrt{\sum_{j=1}^{T}\sigma_{j}^{2}}}\geq\sqrt{2\log(1/\epsilon)}-6. This result is proven in Appendix H . This immediately implies that for any algorithm that outputs \bm{p}_{1:T},\bm{q}_{1:T} , we have \mathrm{Regret}_{\epsilon}(T)/\sqrt{V_{T}/4}\geq\sqrt{2\log(1/\epsilon)}-6 , due to the bound V_{T}\leq\sum_{j=1}^{T}(2\sigma_{j})^{2} . Thus Theorem 7 implies an algorithmic-dependent lower bound \sqrt{V_{T}\log(1/\epsilon)/2} , which certifies that NormalHedge.BH is adaptively optimal up to a multiplicative \log V_{T} factor. We leave as an open problem whether such a factor is necessary. The lower bound improves to \sqrt{2V_{T}\log(1/\epsilon)} (using Popoviciu’s inequality) for all algorithms that define V_{T} with \bm{q}=\bm{p} , which matches our upper bound in Theorem 5 exactly. 5 A stochastic calculus perspective Our algorithm and its analysis are motivated by previous work on the problem of combing expert advice in continuous time using stochastic differential equations (SDEs) ( 15 ; 20 ; 21 ) . A rigorous analysis of the SDE-based analysis is beyond the scope of this paper. However, by providing an informal analysis we justify two choices that might otherwise be bewildering, namely, the requirement that the potential function obeys the backwards heat equation, and the weighting of the variance using the second derivative of the potential function. SDE’s are typically defined over time (a scalar t ) and space (a vector \bm{x} ). SDEs are studied in the diffusion scaling where B\to 0 , \|\Delta\bm{x}\|_{\infty}\leq B and \Delta t\leq B^{2} . Diffusion scaling is formally captured by Itô’s Lemma ( 22 ) , the stochastic calculus analogue of the fundamental theorem of calculus. Similarly to the {\sf CP} algorithm, consider a learner aiming to maintain a constant total potential \Phi(\bm{x},t) as in ( 1 ). In a given round with a regret vector \bm{x} changing by \Delta\bm{x} , the learner must advance the time t by some \Delta t>0 such that \Phi(\bm{x}+\Delta\bm{x},t+\Delta t)\leq\Phi(\bm{x},t). A Taylor expansion yields \Phi(\bm{x}+\Delta\bm{x},t+\Delta t)-\Phi(\bm{x},t)\approx\langle\nabla_{x}\Phi(\bm{x},t),\Delta\bm{x}\rangle+\partial_{t}\Phi(\bm{x},t)\Delta t+\frac{1}{2}(\Delta\bm{x})^{\textsf{T}}\nabla^{2}_{x}\Phi(\bm{x},t)\Delta\bm{x}. (6) As we are operating in the diffusion scaling limit the terms \partial_{t}\Phi\cdot\Delta t and \partial_{x_{i}x_{i}}\Phi\cdot(\Delta x_{i})^{2} are of the same order of magnitude, while higher-order terms are negligible in the limit. Our discrete time analysis essentially controls these higher-order terms via self-concordance. The role of the Backwards Heat Equation. Since the learners pick probabilities \mathbf{p}\propto\nabla_{x}\Phi(\bm{x},t) , one can show that the first term \langle\nabla_{x}\Phi(\bm{x},t),\Delta\bm{x}\rangle in ( 6 ) vanishes. Moreover, since \Phi=\sum_{i=1}^{N}\phi(x_{i},t) , the last term in ( 6 ) simplifies to \tfrac{1}{2}\sum_{i=1}^{N}\partial_{x_{i}x_{i}}\Phi(\bm{x},t)(\Delta x_{i})^{2} . One can think of this term as the increase in potential due to the variance in the regret. Thus, to keep the potential non-increasing it suffices to choose \Delta t large enough such that \partial_{t}\Phi(\bm{x},t)\Delta t+\frac{1}{2}\sum_{i=1}^{n}\partial_{x_{i}x_{i}}\Phi(\bm{x},t)(\Delta x_{i})^{2}\leq 0. The Backwards Heat Equation (Property (7) in Definition 1 ) guarantees that this holds with equality as \Delta t\rightarrow 0 . Definition of the weights used to define V_{j} . We can plug \partial_{t}\Phi(\bm{x},t)=-\frac{1}{2}\sum_{i=1}^{n}\partial_{x_{i}x_{i}}\Phi(\bm{x},t) into above, yielding \Delta t\leq\frac{\sum_{i=1}^{n}\partial_{x_{i}x_{i}}\Phi(\bm{x},t)(\Delta x_{i})^{2}}{\sum_{j=1}^{n}\partial_{x_{j}x_{j}}\Phi(\bm{x},t)}=\mathbb{E}_{i\sim\mathbf{q}}[(\Delta x_{i})^{2}],\text{~ where ~}q_{i}=\frac{\partial_{x_{i}x_{i}}\Phi(\bm{x},t)}{\sum_{j=1}^{n}\partial_{x_{j}x_{j}}\Phi(\bm{x},t)}. These q_{i} values are the probabilities used to calculate V_{j} in line 6 of the CP algorithm. 6 Analysis To prove a regret bound for CP , we need to bound the growth of t . We will do so by showing that \Delta t=O(\mathbb{E}_{i\sim\mathbf{q}}[(\Delta x_{i})^{2}]) in each iteration. This requires analyzing the total potential function with perturbed inputs and calculating how much \Delta t needs to be for \Phi(\widetilde{\bm{x}}+\widetilde{\Delta\bm{x}},t+\Delta t)=\Phi(\widetilde{\bm{x}},t) . Recall that in the asymptotic analysis, a critical insight due to the choice of p_{i}\propto\partial_{x}\phi(x_{i},t) in CP is that \langle\nabla_{x}\Phi(\bm{x},t),\Delta\bm{x}\rangle=0 . This is a property that we need for the discretized analysis too. However, we first need to deal with a subtle problem. Due to the projection to \mathcal{D} , \widetilde{\Delta\bm{x}} is not necessarily equal to \Delta\bm{x} , which results in instances when \langle\nabla_{x}\Phi(\tilde{\bm{x}},t),\widetilde{\Delta\bm{x}}\rangle\neq 0 . The next lemma solves this problem. Specifically, it allows us to bound the algorithmic choice of \Delta t_{j} in CP by calculating \breve{\Delta t_{j}} such that \Phi(\widetilde{\bm{x}}_{j-1}+\breve{\Delta\bm{x}_{j}},t_{j-1}+\breve{\Delta t_{j}})=\Phi(\widetilde{\bm{x}}_{j-1},t_{j-1}) for any \breve{\Delta\bm{x}_{j}} such that \widetilde{\bm{x}}_{j}=\Pi_{\mathcal{D}}(\widetilde{\bm{x}}_{j-1}+\breve{\Delta\bm{x}_{j}}) . Notice that this equation is slightly different from Line 5 of CP . This is a convenient reduction because if we choose \breve{\Delta\bm{x}_{j}} carefully such that \langle\nabla_{\bm{x}}\Phi(\tilde{\bm{x}}_{j-1},t_{j-1}),\breve{\Delta\bm{x}_{j}}\rangle=0 . Observe that \breve{\Delta\bm{x}_{j}}=\Delta\bm{x}_{j} is a valid choice 1 1 1 when we specialize to NormalHedge.BH, there is a smarter choice that allows us to get more adaptive bounds. . We defer the proof of the next Lemma to Appendix B . Lemma 8 . Let \phi be a good potential. Let \widetilde{\bm{x}}\in\mathcal{D} , \breve{\Delta\bm{x}}\in\mathbb{R}^{N} . Define \widetilde{\Delta\bm{x}}:=\Pi_{\mathcal{D}}(\widetilde{\bm{x}}+\breve{\Delta\bm{x}})-\widetilde{\bm{x}} . We define \Delta t and \breve{\Delta t} by ( \Delta t definition) \displaystyle\Phi(\widetilde{\bm{x}}+\widetilde{\Delta\bm{x}},t+\Delta t)=\Phi(\widetilde{\bm{x}},t) ( \breve{\Delta t} definition) \displaystyle\Phi(\widetilde{\bm{x}}+\breve{\Delta\bm{x}},t+\breve{\Delta t})=\Phi(\widetilde{\bm{x}},t). Then \Delta t\leq\breve{\Delta t}. Simplifying notation. To avoid notational clutter, for the remainder of this section (and all of the deferred proofs in the appendix), we will take (\bm{x},t) and (\bm{x}^{\prime},t^{\prime}) to be, respectively, consecutive iterates (\widetilde{\bm{x}}_{j-1},t_{j-1}) and (\widetilde{\bm{x}}_{j-1}+\Delta\bm{x}_{j},t_{j}+\Delta t_{j}) of CP (\phi,\mathcal{D}) with good potential function \phi clear from context. Moreover, throughout we shall denote by \Phi the total potential function ( 1 ). First, we prove in Appendix C that \Delta t_{j} as in line 5 of CP exists and is non-negative. Lemma 9 (Existence and nonnegativity of \Delta t ) . There exists a unique \Delta t>0 such that \Phi(\bm{x}+\Delta\bm{x},t+\Delta t)=\Phi(\bm{x},t) . The proof (given in Appendix C ) uses the fact that the first-order term w.r.t. \Delta\bm{x} vanishes and several properties of a good potential function, including that \phi is strictly convex. 6.1 Log-potential and explicit formula of \Delta t In Section 5 , we sketched how to analyze the change in potential using Taylor expansions. We formalize this idea by analyzing the logarithm of the total potential function \log\Phi(\bm{x},t) , since it will allow us to control the discretization error using self-concordance. Similarly to Section 5 , the next lemma shows a formula for \Delta t using the second-order Taylor expansion of \log\Phi together with the backwards heat equation. We defer the proof to Appendix C . Lemma 10 (Second-order Expansion of Log-Total-Potential) . Define \bm{\Delta}\coloneqq(\Delta\bm{x},\Delta t) . Then there is a mid-point (\bar{\bm{x}},\bar{t}) on the line segment between (\bm{x},t) and (\bm{x}^{\prime},t^{\prime}) such that \log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t)=-\frac{\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t)\Delta t}{\Phi(\bm{x},t)}+\frac{1}{2}\nabla^{2}\log\Phi(\bar{\bm{x}},\bar{t})[\bm{\Delta},\bm{\Delta}]. In particular, if \Delta t is such that \log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t)=0 , then \Delta t=\frac{\Phi(\bm{x},t)\nabla^{2}\log\Phi(\bar{\bm{x}},\bar{t})[\bm{\Delta},\bm{\Delta}]}{\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t)}. (7) A Formula for \Delta t with \mathbb{E}_{i\sim\mathbf{q}}[\Delta\bm{x}_{i}^{2}] . Our goal is to upper bound the numerator in ( 7 ) so as to obtain a bound on \Delta t depending on \mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}] . Indeed, we could obtain such a result as an equation if we had (\bar{\bm{x}},\bar{t})=(\bm{x},t) by simply expanding the Hessian of {\log\Phi} in terms of the derivatives of \Phi and the backwards-heat equation. As stated in the next lemma, we can still follow these steps assuming the Hessian of {\log\Phi} does not change too much from (\bm{x},t) to (\bar{\bm{x}},\bar{t}) . We defer the proof to Appendix C . Lemma 11 . Define \mathbf{\Delta}\coloneqq(\Delta\bm{x},\Delta t) and assume there is C\geq 1 such that for any (\bar{\bm{x}},\bar{t}) in the line segment between (\bm{x},t) and (\bm{x}^{\prime},t^{\prime}) , we have \nabla^{2}\log\Phi(\bar{\bm{x}},\bar{t})[\mathbf{\Delta},\mathbf{\Delta}]\preceq C\cdot\nabla^{2}\log\Phi(\bm{x},t)[\mathbf{\Delta},\mathbf{\Delta}]. (8) Then, \Delta t\leq C\cdot\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+C\Delta t^{2}\cdot\DErr_{\Phi}(\bm{x},t), where \DErr_{\Phi}(\bm{x},t)\coloneqq\frac{\sum_{i=1}^{N}\frac{\partial^{4}}{\partial x^{4}}\phi(x_{i},t)}{4\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t)}-\frac{1}{4\Phi(\bm{x},t)}\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t). We call the last definition above the discretization error of \Phi at (\bm{x},t) . This term would not appear in a derivation in the continuous-time setting discussed in Section 5 since \Delta t^{2} vanishes in continuous time. Note that the behavior of the discretization error depends on the choice of \phi . Lemma 12 . For \phi=\phi_{\mbox{\tiny exp}} , we have \DErr_{\Phi}(\bm{x},t)=0 . Proof. Computing the derivatives, \frac{1}{\Phi(\bm{x},t)}(\sum_{i}\partial_{xx}\phi(x_{i},t))^{2}=\sum_{i}\frac{\partial^{4}}{\partial x^{4}}\phi(x_{i},t)=4\eta^{4}\Phi(\bm{x},t) . ∎ Thus, if we can control the Hessian of the exponential weights potential, then \Delta t=O(\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]) . For the NormalHedge potential, we can show that the discretization error is small if we assume that the regret is small, that is, if x_{i}=\tilde{O}(\sqrt{t}) . The proof, given in Appendix F.2 leverages a variance bound due to 3 . Lemma 13 . If \phi=\phi_{\mathrm{NH}} , then \DErr_{\Phi}(\bm{x},t)\leq(\max_{i}x_{i}^{2}/t+4)/4t . Note that a non-discretization error raises a circular problem: the bound on \Delta t depends on \Delta t itself. Later we shall see how we can first provide a crude bound on \Delta t to finally apply Lemma 11 . Finally, to reason about the behavior of the Hessian, we will use tool from self-concordance. 6.2 Local Generalized Self-Concordant Analysis Self-concordance is a classical tool for analyzing Newton methods ( 30 ; 35 ) and statistical estimators ( 2 ) . We introduce a local variant for multivariate functions depending on an arbitrary norm \|\cdot\|_{*} . Definition 14 (Local Generalized Self-Concordance) . Let \mathrm{dom}(f)\subset\mathbb{R}^{p} be open. A C^{3} function f satisfies (M,2) -generalized self-concordance in norm \|\cdot\|_{*} on \mathcal{C}\subset\mathrm{dom}(f) if \forall\bm{x}\in\mathcal{C},\mathbf{u},\mathbf{v}\in\mathbb{R}^{p} : \bigl|\nabla^{3}f(\bm{x})[\mathbf{u},\mathbf{u},\mathbf{v}]\bigr|\;\leq\;M\,\|\mathbf{v}\|_{*}\mathbf{u}^{\textsf{T}}\nabla^{2}f(\bm{x})\mathbf{u}. (9) Remark. This definition generalizes 2 ; 35 in two ways: (1) it allows a general norm \|\cdot\|_{*} rather than Euclidean; and (2) it restricts the property to a local set \mathcal{C} . The standard global self-concordance is a special case where \mathcal{C}=\mathrm{dom}(f) and \|\cdot\|_{*}=\|\cdot\|_{2} . These extensions are essential for handling functions that are not globally self-concordant or where perturbations scale with non-Euclidean norms (e.g., \ell_{\infty} ). Self-concordance controls the Hessian’s change via a “sandwich” bound. The following lemma extends the standard bound to our local, general-norm setting (Proof in Appendix E.1 ). Lemma 15 (Semidefinite ordering under (M,2) -GSC) . If f satisfies (M,2) -generalized self-concordance in norm \|\cdot\|_{*} on a convex set \mathcal{C} , then for any x,y\in\mathcal{C} , we have the semidefinite ordering: e^{-M\|y-x\|_{*}}\,\nabla^{2}f(x)\;\preceq\;\nabla^{2}f(y)\;\preceq\;e^{M\|y-x\|_{*}}\,\nabla^{2}f(x). (10) 6.3 Proof of Theorem 5 : Self-Concordant Analysis of Hedge Recall from Section 6 that our goal is to bound \Delta t in each iteration of {\sf CP} . The standard idea is to apply Taylor’s theorem on the total potential \Phi at (\bm{x},t) , as in ( 18 ), then bound the perturbation. However, \Phi does not satisfy self-concordance with meaningful parameters. It turns out if we take the logarithm of \Phi , then the log-total-potential does satisfy generalized-self concordance with \nu=2 . This is the technical reason why we developed Section 6.1 . We will now show that {\log\Phi} for \Phi being the total potential of exponential weights satisfies generalized self-concordance. Global Self-concordance of Log-total-Potential for Hedge. By the definition of \phi_{\mbox{\tiny exp}} , {\log\Phi}(\bm{x},t)=\log\sum_{i}\phi(x_{i},t)=-\eta^{2}t+\log\sum_{i}\exp(\sqrt{2}\eta x_{i})=-\eta^{2}t+\Psi(\bm{x}), where \Psi(\bm{x})\coloneqq\log\sum_{i}\exp(\sqrt{2}\eta x_{i}) is the standard log-sum-exp function. Proposition 16 . The functions \Psi and \Phi satisfy (2\sqrt{2}\eta,2) -global GSC (as in Definition 14 ) with respect to \|\cdot\|_{\infty} and \|\cdot\|_{*} respectively, where \|(\bm{x},t)\|_{*}=\|\bm{x}\|_{\infty} for any (\bm{x},t)\in\mathbb{R}^{N+1} . The proof, which uses standard calculus on log-sum-exp function \Psi , is presented in Appendix E.2 . The 2-GSC of {\log\Phi} follows because it is decomposable into \Psi(\bm{x}) and a linear function in t , and the latter satisfies self-concordance trivially with M=0 . We are now in place to prove Theorem 5 . In Appendix D , we give an alternative proof using only Taylor’s Theorem and GSC of \Psi . Theorem 5 . By (2\sqrt{2}\eta,2) -GSC, (Proposition 16 and Lemma 15 ), the bound on the Hessian ( 19 ) from Lemma 11 is satisfied with C=2\sqrt{2}\eta\|\bm{x}-\bar{\bm{x}}\|_{\infty}\leq 2\sqrt{2}\eta B . Moreover, \DErr_{\Phi}(\bm{x},t)=0 by Lemma 12 . Therefore, Lemma 11 yields \displaystyle\Delta t \displaystyle\leq e^{2\sqrt{2}\eta B}\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}], where \mathbf{q}\in\Delta^{N-1} is such that q_{i}\propto\partial_{xx}\phi(x_{i},t) . Since \mathbf{q}=\mathbf{p} for exponential weights (where \mathbf{p} is as in {\sf CP} ), we have \mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]=\mathrm{Var}_{i\sim\mathbf{p}}[\ell_{j,i}] . Summing over T iterations (and recalling from Lemma 8 that the bound on \Delta t holds for \Delta t_{j} from CP ) we have \sum_{j=1}^{T}\Delta t_{j}\leq e^{2\sqrt{2}\eta B}V_{T} , and since t=t_{0}+\sum_{j=1}^{T}\Delta t_{j} , plugging this into Lemma 3 completes the proof. ∎ 6.4 Proof Sketch of Theorem 6 : A Local Self-Concordant Analysis of NormalHedge General idea and challenges. While the analysis of NormalHedge is more involved, the method to bound \Delta t follows a similar line of arguments as in Section 6.3 . First, we establish self-concordance for the log total potential {\log\Phi} , which us to locally control the Hessian (Lemma 15 ). Finally, this allows us to use Lemma 11 to bound \Delta t by the desired term plus some discretization error. One issue is that {\log\Phi} does not satisfy global self-concordance in this case, so we need to carefully design the local region \mathcal{C} for each step of the algorithm to be the line-segment between consecutive iterates (\bm{x},t) and (\bm{x}+\Delta\bm{x},t+\Delta t) . As a result, the self-concordance parameters (choice of the norm \|\cdot\|_{*} ) will depend on the current t and the choice of \Delta t . This is problematic since our goal with self-concordance is to control \Delta t itself! Thus, we proceed in “two phases” after showing self-concordance. First, we will show a crude \Delta t=O(B^{2}) bound. This will allow us to both bound the self-concordance of the potential and to derive the desired second order bound \Delta t=O(\mathbb{E}_{i\sim q}[(\Delta x_{i})^{2}]) . Local Self-concordance of Log-Total-Potential for NormalHedge Let us define the local neighborhood \mathcal{C} of interest as per Definition 14 . Define the line segment and parameters by \displaystyle(\bm{x}(s),t(s))=(\bm{x},t)+s(\Delta\bm{x},\Delta t),\qquad s\in[0,1], (11) \displaystyle t_{\star}:=\min_{s\in[0,1]}t(s)=t,\qquad K_{\rm seg}:=\sup_{s\in[0,1]}\ \max_{1\leq i\leq N}\ \frac{x_{i}(s)^{2}}{t(s)}. (12) The above definitions imply the following bounds: \frac{|x_{i}(s)|}{t(s)}\ \leq\ \sqrt{\frac{K_{\rm seg}}{t_{\star}}}\qquad\forall\,i\in[N],\ \forall\,s\in[0,1],\qquad\text{and}\qquad\frac{|\Delta t|}{t(s)}\ \leq\ \frac{|\Delta t|}{t_{\star}}\qquad\forall\,s\in[0,1]. (13) Proposition 17 (Local \nu=2 GSC for NormalHedge) . The function {\log\Phi} satisfies local generalized self-concordance with M=1 , \nu=2 and \mathcal{C} as the line-segment in ( 11 ) with respect to the norm \|(\bar{\bm{x}},\bar{t})\|_{*}=A_{x}(t_{\star},K_{\rm seg})\|\bar{\bm{x}}\|_{\infty}+A_{t}(t_{\star},K_{\rm seg})|\bar{t}| where \displaystyle A_{x}(t_{\star},K_{\rm seg})=\frac{8\sqrt{K_{\rm seg}\vee 1}}{\sqrt{t_{\star}}},\quad\text{ and }\quad A_{t}(t_{\star},K_{\rm seg})=\frac{16(K_{\rm seg}\vee 1)}{t_{*}}. (14) The proof is deferred to Appendix E.3 . To ease notation in what follows, define \Lambda:=A_{x}(t_{\star},K_{\rm seg})\,\|\Delta\bm{x}\|_{\infty}+A_{t}(t_{\star},K_{\rm seg})\,|\Delta t|. (15) Proposition 17 together with Lemma 15 implies the following semidefinite ordering. Corollary 18 . For any (\bar{\bm{x}},\bar{t}) in the line-segment ( 11 ) we have e^{-\Lambda}\,\nabla^{2}{\log\Phi}(\bm{x},t)\preceq\nabla^{2}{\log\Phi}(\bar{\bm{x}},\bar{t})\preceq\ e^{+\Lambda}\,\nabla^{2}{\log\Phi}(\bm{x},t). (16) Crude bound on \Delta t . The key idea is that if we can find s\geq 0 such that \Phi(\bm{x}+\Delta\bm{x},t+s)\leq\Phi(\bm{x},t) (assuming t is large enough, a “burn-in” condition), then we know \Delta t\leq s since \Phi is decreasing in the second argument. The next lemma shows s=O(B^{2}) works. Lemma 19 (Crude bound of \Delta t ) . If K>0 is such that \max_{i\in[N]}\frac{x_{i}^{2}}{t}\leq K , then t\geq 256e^{2}B^{2}\max\{K,1\}\implies\Delta t\leq 2eB^{2}. Proof sketch. Since s\mapsto\Phi(\bm{x}+\Delta\bm{x},t+s) is decreasing, and by some properties of \Phi \Delta t should be the smallest s such that \Phi(\bm{x}+\Delta\bm{x},t+s)\leq\Phi(\bm{x},t) , it suffices to prove that for s=2eB^{2} this inequality hold. To prove this lemma we use a second order Taylor expansion of {\log\Phi}(\bm{x}+\Delta\bm{x},t+s) and apply the sandwich formula from self-concordance (Corollary 18 ) to control the Hessian, leading to a formula very similar to the one of Lemma 11 , yielding \frac{\Phi(\bm{x},t)(\log\Phi(\bm{x}^{\prime},t+s)-\log\Phi(\bm{x},t))}{\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t)}+\frac{s}{2}\leq e^{\Lambda}\Big(\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+s^{2}\DErr_{\Phi}(\bm{x},t)\Big). By Lemma 13 and by assumption of Lemma 19 , we know the discretization error is at most (K+3)/4T . Thus, since \Phi(\bm{x},t)/\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t)\geq 0 , to have the pontential \Phi(\bm{x}^{\prime},t+s) is smaller than \Phi(\bm{x},t) , it suffices to have s\geq e^{\Lambda}\left(B^{2}+\frac{K+4}{4t}s^{2}\right). One issue is that e^{\Lambda} defined on ( 15 ) also depends on s (taking \Delta t=s in the GSC result). Luckily, we show that for t\geq\Omega(B^{2}K) we have e^{\Lambda}\leq 1 . With that, one can verify that s=2eB^{2} satisfies the above inequality. The detailed proof for this crude bound is presented in Appendix F.3 . ∎ Defining K and Bounding \Lambda . Lemma 19 assumes K is such that K/t is small and \max_{i\in[N]}\frac{x_{i}^{2}}{t}\leq K . This is exactly what having a constant potential guarantees. Namely, we show we can take K(t)\coloneqq\log(t/t_{0})+2\log N. Lemma 20 . For t>t_{0} we have \max_{i}x_{i}^{2}/t\leq K(t) and K_{\mathrm{seg}}\leq\log(1+t/t_{0})+2\log N\leq 2K(t) To use this bound on Lemma 19 we need to guarantee need to guarantee that K(t)/t\leq O(B^{2}) . Since K(t) grows slowly in t , it suffices to pick t_{0} large enough such that K(t_{0})/t_{0}\leq O(B^{2}) . Finally, we the above lemma and taking t_{0} large implies \exp(\Lambda)<0.414 . Refined bound of \Delta t . Lemmas 12 and 20 imply \DErr_{\Phi}(\bm{x},t)\leq(K(t)+4)/t\leq 5K(t) . Therefore, by Lemma 11 we have \displaystyle\Delta t \displaystyle\leq e^{\Lambda(t)}(\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+\Delta t^{2}\DErr_{\Phi}(\bm{x},t))\leq e^{\Lambda(t)}\Big(\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+\Delta t^{2}\frac{5K(t)}{4t}\Big). (17) Since t_{0}\geq\Omega(B^{2}K(t_{0}))\leq\Omega(B^{2}\log N) , we can plug the crude bound \Delta t=O(B^{2}) from Lemma 19 to get \Delta t^{2}\leq 2eB^{2}\Delta t . Moreover, t_{0} large implies K(t)/t\leq(256e^{2}B^{2})^{-1} . Thus \Delta t\leq e^{\Lambda}\Big(\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+\Delta t\cdot\frac{(\tfrac{5}{4})\cdot 2eB^{2}}{256e^{2}B^{2}}\Big)\implies\Big(e^{-\Lambda}-\frac{1}{64e}\Big)\Delta t\leq\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]. Since \Lambda\leq 0.414 , we have e^{-0.414}-\frac{1}{64}\geq 0.64>0.5 and \Delta t\leq 2\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]. Putting things together. Finally, we can apply our bound for every iteration j . First, recall from the discussion on notation early in Section 6 that \Delta t we analyzed is slightly different from \Delta t_{j} used in the algorithm, but from Lemma 8 we know \Delta t serves as an upper bound \Delta t_{j} from CP . Thus, t=t_{0}+\sum_{j=1}^{T}\Delta t_{j}\leq t_{0}+2V_{T} , where the last bound used the refined bound on \Delta t_{j} . This completes the proof of Theorem 6 when we plug the bound into Lemma 4 . Remark on Sparsity While for a generic potential function \phi we invoke Lemma 8 with \breve{\Delta\bm{x}}=\Delta\bm{x}_{j} , for \phi_{\mbox{\tiny NH}} and \mathcal{D}=\mathbb{R}_{+} , we can actually choose \breve{\Delta\bm{x}} such that \breve{\Delta x_{j,i}}=\widetilde{\Delta x_{j,i}} for all i such that \tilde{x}_{j,i}=0 , and \breve{\Delta x_{j,i}}=\Delta x_{j,i} otherwise. This remains a valid choice because \langle\nabla_{x}\Phi(\tilde{\bm{x}_{j-1}},t_{j-1}),\breve{\Delta x_{j,i}}\rangle=0 since \partial_{x}\phi(\tilde{x}_{i},t)=0 if \tilde{x}_{i}=0 . Notice that \breve{\Delta x_{j,i}}=\widetilde{\Delta x_{j,i}} almost for all j,i . The only exceptions are when x_{j-1,i}>0 and x_{j,i}<0 — zero-crossings from positive to negative regret. Notice that \widetilde{\Delta x_{j,i}}=0 if both x_{j,i} and x_{j-1,i} are negative. The consequence of this more advanced analysis is that NormalHedge.BH also enjoys a regret with V_{T}=\sum_{j=1}^{T}\mathbb{E}_{j\sim\bm{q}_{j}}[\breve{\Delta x}_{j,i}^{2}]=\sum_{j=1}^{T}\mathbb{E}_{j\sim\bm{q}_{j}}[\Delta x_{j,i}^{2}\mathbf{1}(p_{j,i}\neq 0)]\approx\sum_{j=1}^{T}\mathbb{E}_{j\sim\bm{q}_{j}}[\widetilde{\Delta x}_{j,i}^{2}]. 7 Open Problems and future directions 1. Our regret upper-bound for NormalHedge.BH, has the form \sqrt{2V_{T}(\log(2V_{T})+2\log(1/\epsilon))} (ignoring t_{0} ), whereas the lower-bound has the form \sqrt{2V_{T}\log(1/\epsilon)} . It would be interesting to reduce the gap between the upper and lower bound. A constant factor improvement is worked out in Appendix G , giving a bound \sqrt{V_{T}(\log(2V_{T})+2\log(1/\epsilon))} with a correct asymptotic leading constant when \log(1/\epsilon)\gg\log(V_{T}) . But the \log(V_{T}) factor appears to be needed for NormalHedge.BH. It comes from the 1/\sqrt{t} factor in the potential (see Lemma 4 ). 2. One interpretation of the SDE based analysis is that we are designing an algorithm that has minimal regret against the Ito process, which is a continuous-time stochastic process. On the other hand, our upper bounds hold for arbitrary sequences in discrete time. This same phenomenon occurs in other work, e.g., ( 15 ; 19 ; 20 ) . We would like to better understand the relationship between the Ito Process and the game of prediction with expert advice. 3. SDEs play a prominent role in a variety of fields, such as finance and stochastic control. We would like to find applications of the theory we developed to those fields. Appendix A More discussion on the related Work The problem of online learning and predictions have its origin in classical work in statistics and information-theory [ 33 , 5 , 11 ] . The “expert advice” problem was first proposed by [ 25 ] and has since been studied extensively [ 24 , 37 , 7 ] . It is known that the minimax regret with N experts and T rounds is of \Theta(\sqrt{T\ln N}) . As a result, subsequent work focuses on adaptive regret bounds that replaces T or \log N with sequence-dependent or comparator-dependent quantities that could be much smaller than the worst-case when the sequences are “easy”. First and second order regret bounds. In these adaptive regret bounds, T is typically replaced with a quantity that depends on the loss vector \ell_{j} or the instantaneous regret vector \Delta\bm{x}_{j}=\langle p_{j},\bm{\ell}_{j}\rangle\bm{1}-\bm{\ell}_{j} . \Delta\bm{x}_{j} is also known as “excess loss (vector)” [ 18 , 23 ] . Broadly speaking, first order (“small loss”) regret bounds uses L_{T}(i)=\sum_{j=1}^{T}|\ell_{j,i}| and can be improved to S_{T}(i):=\sum_{j=1}^{T}|\Delta x_{j,i}| when comparing with expert i . Second order (“small variance”) regret bound uses V_{T}(i)=\sum_{j=1}^{T}(\Delta x_{j,i})^{2} or V_{T}^{\mathrm{avg},q}=\sum_{j=1}^{T}\mathbb{E}_{i\sim\bm{q}_{j}}[(\Delta x_{j,i})^{2}] . When q=p where p is the weights being selected by the algorithm, we recover V_{T}^{\mathrm{avg}}=\sum_{j=1}^{T}\mathrm{Var}_{i\sim p_{j}}[\ell_{j,i}] due to 8 . It turns out that other choices of \bm{q}_{j} might be natural in an algorithm-dependent manner [ 29 ] . Second order bounds are stronger than first order bounds. Among second order bounds, it has been a focal point of debate whether the comparator-dependent V_{T}(i) or the algorithm-dependent V_{T} (such as V_{T}^{\mathrm{avg}} or V_{T}^{\mathrm{avg},q} ) are more natural. Our results (Theorem 5 and 6 ) are of the latter type. Quantile regret bounds. Along a different dimension, \log N can often be replaced with \log(1/\epsilon) where regret is measured relative to the (\epsilon N)^{th} best expert [ 9 , 26 ] . This is referred to as “quantile regrets” and is a strict-generalization if the algorithm enjoys such quantile bounds for all 0<\epsilon<1 . Quantile regrets are closely related to PAC-Bayesian-style regret bounds for algorithms that take a prior \pi as input. When we are comparing to the average performance of a subset \mathcal{I}\subset[N] of the experts over the prior, the corresponding regret bound often replaces T with L^{\pi}_{T}(\mathcal{I}) , S^{\pi}_{T}(\mathcal{I}) or V^{\pi}_{T}(\mathcal{I}) and also replaces \log N with the Kullback-Liebler divergence \mathrm{KL}(\pi_{\mathcal{I}},\pi) [ 23 , 26 ] . Here \pi_{\mathcal{I}} denotes the restriction of \pi to set \mathcal{I} , and V^{\pi}_{T}(\mathcal{I})=\sum_{i\in\mathcal{I}}\pi_{\mathcal{I}}(i)V_{T}(i) . The special case when \pi=\mathrm{Uniform}([N]) and \mathcal{I} chosen to be the best-performing \epsilon -fraction of the experts is particularly relevant because in it provides a \epsilon -quantile regret bound parameterized by \log(1/\epsilon) , S_{T}(\epsilon) or V_{T}(\epsilon) . Work Cumulative variance Regret bound Adaptive Minimax? Hedge [ 8 ] V_{T}^{\mathrm{avg}}:=\sum_{j=1}^{T}\mathbb{E}_{i\sim p_{j}}[(\Delta x_{j,i})^{2}] \sqrt{V_{T}^{\mathrm{avg}}\log N} No Hedge [ 8 ] V_{T}(i):=\sum_{j=1}^{T}(\Delta x_{j,i})^{2} \sqrt{V_{T}(i)\log N} No NormalHedge [ 9 ] T \sqrt{T\log(1/\epsilon)} Yes Squint [ 23 ] V_{T}(\epsilon):=\mathbb{E}_{i\sim\text{Unif}(\mathrm{Top}_{\epsilon})}\left[V_{T}(i)\right] \sqrt{V_{T}(\epsilon)\log(1/\epsilon)} Yes Ada-Normal-Hedge [ 26 ] S_{T}(\epsilon):=\mathbb{E}_{i\sim\text{Unif}(\mathrm{Top}_{\epsilon})}[\sum_{j=1}^{T}|\Delta x_{i}|] \sqrt{S_{T}(\epsilon)\log(1/\epsilon)} Yes AdaHedge [ 12 ] V_{T}^{\mathrm{avg}}:=\sum_{j=1}^{T}\mathbb{E}_{i\sim p_{j}}[(\Delta x_{j,i})^{2}] \sqrt{V_{T}^{\mathrm{avg}}\log N} Yes Adapt-ML-Prod [ 18 ] V_{T}(i) \sqrt{V_{T}(i)\log N} Yes FTRL [ 29 ] V_{T}^{\mathrm{avg},q}:=\sum_{j=1}^{T}\mathbb{E}_{i\sim\bm{q}_{j}}[(\Delta x_{j,i})^{2}] \log(1/\epsilon)\sqrt{V_{T}^{\mathrm{avg},q}} Yes Hedge (Theorem 5 this paper ) V_{T}^{\mathrm{avg}} \sqrt{V_{T}^{\mathrm{avg}}\log(1/\epsilon)} No NormalHedge (Theorem 6 this paper ) V_{T}^{\mathrm{avg},q} \sqrt{V_{T}^{\mathrm{avg},q}\log(1/\epsilon)} Yes Lower bound (Theorem 7 this paper ) V_{T}^{\mathrm{avg},q} for any q^{1:T} \sqrt{V_{T}^{\mathrm{avg},q}\log(1/\epsilon)} not applicable Table 1: Summary of instance-dependent regret bounds. For those that depends on priors, e.g., 23 , we choose the prior to be uniform, so as to be comparable to quantile regret bounds. For clarity, we omit multiplicative \log(V_{T}) factors and additive \mathrm{poly}\log(N) factors. Also, note that V_{T}^{\mathrm{avg},q} in 29 is different from the V_{T}^{\mathrm{avg},q} in our Theorem 6 due to different choices of q^{1:T} , both are natural for the algorithm under consideration. Adaptively minimax algorithms. Finally, if the algorithm achieves optimal regret simultaneously for many input sequence classes or comparator classes, then we call them adaptively minimax. These algorithms are also referred to as “parameter-free” [ 9 , 31 ] . In the expert-advice setting, this means that the algorithm achieves smaller regret parameterized by L_{T},V_{T} or \log(1/\epsilon) simultaneously for all possible values of L_{T},V_{T} , or \epsilon . Among adaptive algorithms, 18 , 12 adapts to variants of V_{T} . 9 , 27 adapts to \epsilon . 26 adapts to both L_{T}(i) and \epsilon . The work of 23 enjoys an adaptive second-order quantile regret of \sqrt{V_{T}(\epsilon)\log(1/\epsilon)} where V_{T}(\epsilon):=\mathbb{E}_{i\sim\text{Unif}(\mathrm{Top}_{\epsilon})}\left[\sum_{j=1}^{N}(\Delta x_{j,i})^{2}\right] . The main difference from ours is that their \bm{q} is uniform over the top \epsilon quantile of experts throughout while ours has a different \bm{q}_{j} per iteration and our V_{T} is decoupled from the choice of \epsilon . To the best of our knowledge, we are the first to obtain adaptive second-order quantile regret bounds of the form \tilde{O}(\sqrt{V_{T}^{\mathrm{avg,q}}\log(1/\epsilon)}) ( \tilde{O}(\cdot) , hiding a condition that requires V_{T}^{\mathrm{avg,q}}>\log N and a logarithmic factor of \log(V_{T}^{\mathrm{avg,q}}) ). The closest to us is 29 , who obtained a bound that reads \tilde{O}(\log(1/\epsilon)\sqrt{V_{T}^{\mathrm{avg,q}}}) for a Follow-the-Regularized Leader (with adaptively chosen regularizer). They wrote that the suboptimal dependence on \log(1/\epsilon) might be required for their algorithm. However, a private communication with a subset of the authors of 29 reveals that a different variant could enjoy a \sqrt{V_{T}^{\mathrm{avg,q}}\log(1/\epsilon)} -type regret similar to what we obtained for NormalHedge.BH, although such a result was not published in the paper or any of their subsequent work. Open problem and impossibility results. 28 resolved the open problem by 16 on the negative by proving that there is no adaptive algorithm that achieves O(\sqrt{V_{T}^{\mathrm{avg}}\log(1/\epsilon)}) for all \epsilon for V_{T}^{\mathrm{avg}} defined as the “variance over actions” in 8 verbatim. 28 poses no contradiction with our results due to the nuanced differences that we discussed in the remark after Theorem 6 . This has been confirmed via a private communication with the authors of 28 . For completeness, we include a self-contained discussion on 28 ’s construction in Appendix I . Appendix B Handling projection onto \mathcal{D} Proof of Lemma 8 . By Property (6) in Definition 1 , \Phi(\Pi_{\mathcal{D}}(\bm{x}),t)\leq\Phi(\bm{x}) for any \bm{x} , thus \displaystyle\Phi(\widetilde{\bm{x}}+\breve{\Delta\bm{x}},t+\Delta t) \displaystyle\geq\Phi(\Pi_{\mathcal{D}}(\widetilde{\bm{x}}+\breve{\Delta\bm{x}}),t+\Delta t) \displaystyle\underset{\mathclap{\overset{\uparrow}{\text{Def. of }\widetilde{\Delta\bm{x}}}}}{=}\Phi(\widetilde{\bm{x}}+\widetilde{\Delta\bm{x}},t+\Delta t)\underset{\mathclap{\overset{\uparrow}{\text{Choice of }\Delta t}}}{=}\Phi(\widetilde{\bm{x}},t)\underset{\mathclap{\overset{\uparrow}{\text{Choice of }\breve{\Delta t}}}}{=}\Phi(\widetilde{\bm{x}}+\breve{\Delta\bm{x}},t+\breve{\Delta t}) This shows that t+\Delta t\leq t+\breve{\Delta t} , since \Phi monotonically decreases as t increases, due to property (4) of Definition 1 . Thus \Delta t\leq\breve{\Delta t} . ∎ Appendix C Properties of Log-Total-Potential of {\sf CP} Proof of Lemma 9 . By Taylor’s theorem (with Lagrange-form of the remainder) and the twice differentiability of \Phi , there exists (\bar{\bm{x}},\bar{t}) on the line segment between (\bm{x},t) and (\bm{x}+\Delta\bm{x},t+\Delta t) such that \Phi(\bm{x}+\Delta\bm{x},t+\Delta t)=\Phi(\bm{x},t)+\left\langle\nabla\Phi(\bm{x},t),\begin{bmatrix}\Delta\bm{x}\\ \Delta t\end{bmatrix}\right\rangle+\frac{1}{2}\begin{bmatrix}\Delta\bm{x}\\ \Delta t\end{bmatrix}^{\textsf{T}}\nabla^{2}\Phi(\bar{\bm{x}},\bar{t})\begin{bmatrix}\Delta\bm{x}\\ \Delta t\end{bmatrix}. (18) By the algorithmic choice of p_{i}\propto\nabla_{x_{i}}\Phi(\bm{x},t)=\frac{\partial}{\partial x}\phi(x_{i},t), we have \left\langle\nabla_{\bm{x}}\Phi(\bm{x},t),\Delta\bm{x}\right\rangle=\left\langle\mathbf{p},\Delta\bm{x}\right\rangle=\sum_{i}p_{i}(\ell_{i}-\bm{\ell}^{\textsf{T}}\bm{p})=0. Plugging this into ( 18 ) we get \Phi(\bm{x}+\Delta\bm{x},t+\Delta t)=\Phi(\bm{x},t)+\left\langle\nabla_{t}\Phi(\bm{x},t),\Delta t\right\rangle+\frac{1}{2}\begin{bmatrix}\Delta\bm{x}\\ \Delta t\end{bmatrix}^{\textsf{T}}\nabla^{2}\Phi(\bar{\bm{x}},\bar{t})\begin{bmatrix}\Delta\bm{x}\\ \Delta t\end{bmatrix}. First, observe that at \Delta t=0 , \Phi(\bm{x}+\Delta\bm{x},t+\Delta t)=\Phi(\bm{x},t)+\Delta\bm{x}^{\textsf{T}}\nabla_{\bar{\bm{x}},\bar{\bm{x}}}^{2}\Phi(\bar{\bm{x}},\bar{t})\Delta\bm{x}\geq\Phi(\bm{x},t). The inequality is strict since \Phi is strictly convex, which is implied by the strict convexity of \phi . Second, by the backwards heat equation assumption and the convexity in x \partial_{t}\Phi=-\frac{1}{2}\sum_{i}\partial_{xx}\phi(x_{i},t)\leq 0, thus the total potential is monotonically decreasing (and strictly decreasing if strictly convex) in t anywhere. These two facts ensure that if the equalizing \Delta t exists, it must be non-negative. Lastly, the existence follows from the intermediate value theorem using the continuity of \phi , as well as the assumptions that \lim_{t\rightarrow\infty}\phi(x,t)=\inf_{x,t}\phi(x,t) and \Phi(\bm{x},t)>\inf_{x,t}\phi(x,t) . ∎ Proof of Lemma 10 . By the second order Taylor’s theorem of \log\Phi(\bm{x}^{\prime},t^{\prime}) at (\bm{x},t) , there exists (\bar{\bm{x}},\bar{t}) on the line segment between (\bm{x},t) to (\bm{x}^{\prime},t^{\prime}) such that \displaystyle\log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t)= \displaystyle\frac{\langle\nabla\Phi(\bm{x},t),\Delta\rangle}{\Phi(\bm{x},t)}+\frac{1}{2}\nabla^{2}\log\Phi(\bar{\bm{x}},\bar{t})[\bm{\Delta},\bm{\Delta}] \displaystyle= \displaystyle\frac{\frac{\partial}{\partial t}\Phi(\bm{x},t)\Delta t}{\Phi(\bm{x},t)}+\frac{1}{2}\nabla^{2}\log\Phi(\bar{\bm{x}},\bar{t})[\bm{\Delta},\bm{\Delta}] \displaystyle= \displaystyle-\frac{\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t)\Delta t}{2\Phi(\bm{x},t)}+\frac{1}{2}\nabla^{2}\log\Phi(\bar{\bm{x}},\bar{t})[\bm{\Delta},\bm{\Delta}] Where the choice of p_{i} in the algorithm ensures that \langle\nabla_{x}\Phi(\bm{x},t),\Delta\bm{x}\rangle=0 . The reverse heat equation allows us to write \partial_{t}\Phi(\bm{x},t)=-\frac{1}{2}\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t) . In particular, if \Delta t is such that \log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t)=0 , then rearranging the above gives the Z expression for \Delta t . ∎ Lemma 21 (Restatement of Lemma 11 ) . Define \mathbf{\Delta}\coloneqq(\Delta\bm{x},\Delta t) and assume there is C\geq 1 such that for any (\bar{\bm{x}},\bar{t}) in the line segment between (\bm{x},t) and (\bm{x}^{\prime},t^{\prime}) , we have \nabla^{2}\log\Phi(\bar{\bm{x}},\bar{t})[\mathbf{\Delta},\mathbf{\Delta}]\preceq C\cdot\nabla^{2}\log\Phi(\bm{x},t)[\mathbf{\Delta},\mathbf{\Delta}]. (19) Then, \Delta t\leq C\cdot\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+C\Delta t^{2}\cdot\DErr_{\Phi}(\bm{x},t), where \DErr_{\Phi}(\bm{x},t)\coloneqq\frac{\sum_{i=1}^{N}\frac{\partial^{4}}{\partial x^{4}}\phi(x_{i},t)}{4\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t)}-\frac{1}{4\Phi(\bm{x},t)}\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t). Proof. By Lemma 10 , there is (\bar{\bm{x}},\bar{t}) in the line segment between (\bm{x},t) and (\bm{x}^{\prime},t^{\prime}) such that \Delta_{t}=\frac{\Phi(\bm{x},t)\nabla^{2}\log\Phi(\bar{x},\bar{t})[\bm{\Delta},\bm{\Delta}]}{\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t)}\stackrel{{\scriptstyle\eqref{eq:hessian_comparison_assumption}}}{{\leq}}C\cdot\frac{\Phi(\bm{x},t)\nabla^{2}\log\Phi(\bm{x},t)[\bm{\Delta},\bm{\Delta}]}{\sum_{i=1}^{N}\partial_{xx}\phi(x_{i},t)}. (20) Moreover, note that \displaystyle\nabla^{2}\log\Phi(\bm{x},t)[\bm{\Delta},\bm{\Delta}]=\frac{\nabla^{2}\Phi(\bm{x},t)[\bm{\Delta},\bm{\Delta}]}{\Phi(\bm{x},t)}-\frac{\bm{\Delta}^{\textsf{T}}\nabla\Phi(\bm{x},t)\nabla\Phi(\bm{x},t)^{\textsf{T}}\bm{\Delta}}{\Phi(\bm{x},t)^{2}} \displaystyle= \displaystyle\frac{1}{\Phi(\bm{x},t)}\left(\nabla^{2}_{xx}\Phi(\bm{x},t)[\Delta\bm{x},\Delta\bm{x}]+\frac{\partial^{2}}{\partial t^{2}}\Phi(\bm{x},t)\Delta t^{2}+2\frac{\partial}{\partial t}\underbrace{\nabla_{x}\Phi(\bm{x},t)^{\textsf{T}}\bm{\Delta}x}_{=0\text{ by our algorithm.}}\Delta t\right) \displaystyle\quad-\frac{1}{\Phi(\bm{x},t)^{2}}\left({\underbrace{\langle\nabla_{x}\Phi(\bm{x},t),\Delta\bm{x}\rangle}_{=0\text{ by our algorithm.}}}^{2}+(\frac{\partial}{\partial t}\Phi(\bm{x},t)\Delta t)^{2}\right) \displaystyle= \displaystyle\frac{\nabla^{2}_{xx}\Phi(\bm{x},t)[\Delta\bm{x},\Delta\bm{x}]}{\Phi(\bm{x},t)}+\Delta t^{2}\left(\frac{\frac{\partial^{2}}{\partial t^{2}}\Phi(\bm{x},t)}{\Phi(\bm{x},t)}-\frac{(\frac{\partial}{\partial t}\Phi(\bm{x},t))^{2}}{\Phi(\bm{x},t)^{2}}\right) \displaystyle= \displaystyle\frac{1}{\Phi(\bm{x},t)}\sum_{i}\partial_{xx}\phi(x_{i},t)\Delta x_{i}^{2}+\Delta t^{2}\left(\frac{1}{4\Phi(\bm{x},t)}\sum_{i}\frac{\partial^{4}}{\partial x^{4}}\phi(x_{i},t)-\frac{1}{4\Phi(\bm{x},t)^{2}}(\sum_{i}\partial_{xx}\phi(x_{i},t))^{2}\right) \displaystyle= \displaystyle\frac{\sum_{i}\partial_{xx}\phi(x_{i},t)}{\Phi(\bm{x},t)}\left(\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+\Delta t^{2}\left(\frac{\sum_{i}\frac{\partial^{4}}{\partial x^{4}}\phi(x_{i},t)}{4\sum_{i}\frac{\partial^{2}}{\partial x^{2}}\phi(x_{i},t)}-\frac{1}{4\Phi(\bm{x},t)}\sum_{i}\frac{\partial^{2}}{\partial x^{2}}\phi(x_{i},t)\right)\right) \displaystyle= \displaystyle\frac{\sum_{i}\partial_{xx}\phi(x_{i},t)}{\Phi(\bm{x},t)}\left(\Delta x_{i}^{2}+\Delta t^{2}\DErr_{\Phi}(\bm{x},t)\right) (21) Plugging the above into ( 20 ) concludes the proof. ∎ Appendix D Simple alternative proof of Theorem 5 : Exponential weights. This section presents a simple and self-contained argument for bounding \Delta t for the exponential potential in Example 3 . This does not require using more abstract results about a generic potential \phi such as Lemma 10 , 11 , and Lemma 12 . We continue from the part of Section 6.3 after Proposition 16 (self-concordance of \Psi ). Taylor’s Theorem on \Psi . Start by taking the difference of the log-total-potential {\log\Phi} of each step of the algorithm (recall {\log\Phi}(\bm{x},t)=\Psi(\bm{x})-\eta^{2}t ): \displaystyle{\log\Phi}(\bm{x}+\Delta\bm{x},t+\Delta t)-{\log\Phi}(\bm{x},t) \displaystyle=-\eta^{2}\Delta t+\Psi(\bm{x}+\Delta\bm{x})-\Psi(\bm{x}) \displaystyle=-\eta^{2}\Delta t+\langle\nabla\Psi(\bm{x}),\Delta\bm{x}\rangle+\frac{1}{2}\Delta\bm{x}^{\textsf{T}}\nabla^{2}\Psi(\bar{x})\,\Delta\bm{x} (22) where the last step applies the second-order Taylor’s theorem with \bar{\bm{x}}=\bm{x}+\tau\Delta\bm{x} for a \tau\in[0,1] . By Proposition 16 which states that \Psi -is (M,2) -global self-concordant and the sandwich formula in Lemma 15 that gives a semidefinite ordering \nabla^{2}\Psi(\bar{x})\preceq\exp(M\tau\|\Delta\bm{x}\|_{\infty})\,\nabla^{2}\Psi(\bm{x})\preceq\exp(M\|\Delta\bm{x}\|_{\infty})\,\nabla^{2}\Psi(\bm{x}). Substituting the above inequality with M=2\sqrt{2}\eta into ( 22 ) yields \displaystyle\underbrace{{\log\Phi}(\bm{x}+\Delta x,\,t+\Delta t)-{\log\Phi}(\bm{x},t)}_{=0} \displaystyle\leq\langle\underbrace{\nabla\Psi(\bm{x}),\Delta\bm{x}\rangle}_{=0}-\eta^{2}\,\Delta t+\frac{1}{2}\,e^{2\sqrt{2}\eta B}\,\underbrace{\Delta\bm{x}^{\textsf{T}}\nabla^{2}\Psi(\bm{x})\,\Delta\bm{x}}_{=2\eta^{2}\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]}. (23) Observe that by Lemma 22 , \nabla\Psi(\bm{x})=\sqrt{2}\eta\bm{p} where p is the algorithm’s choice of the probability (thus the linear term vanishes) and \Delta x^{\textsf{T}}\nabla^{2}\Psi(\bm{x})\,\Delta x=2\eta^{2}\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]=2\eta^{2}\mathrm{Var}_{i\sim\mathbf{p}}[\ell_{i}]. Moreover, by our algorithmic choice of \Delta t , the LHS is 0 . Move \Delta t to the left hand side, we obtain \Delta t\leq e^{2\sqrt{2}\eta B}\mathrm{Var}_{i\sim\mathbf{p}}[\ell_{i}]. (24) Appendix E Detailed Proofs for Generalized Self-Concordance E.1 Proof of Lemma 15 : the “Sandwich” Formula Proof of Lemma 15 . Let \Delta\coloneqq y-x and define x_{\lambda}\coloneqq x+\lambda\Delta for \lambda\in[0,1] . By convexity of \mathcal{C} , we have x_{t}\in\mathcal{C} . Fix any u\in\mathbb{R}^{p} and define the scalar function q(t):=u^{\textsf{T}}\nabla^{2}f(x_{t})u\ \geq 0. Since f\in C^{3} , the funciton t\rightarrow\nabla^{2}f(x_{t}) is differentiable and thus q is differentiable with q^{\prime}(\lambda)=\left\langle\frac{d}{d\lambda}\nabla^{2}f(x_{\lambda})\,u,\;u\right\rangle=\langle\nabla^{3}f(x_{\lambda})[\Delta,\cdot,\cdot]\,u,\;u\rangle. Applying local self-concordance as in ( 9 ) at x_{\lambda} with u=\Delta yields |q^{\prime}(\lambda)|\;\leq\;M\,\|\Delta\|_{*}\,q(\lambda). Therefore, q^{\prime}(\lambda)-M\|\Delta\|_{*}q(\lambda)\leq 0 and, thus \displaystyle\frac{\mathrm{d}}{\mathrm{d}\lambda}\big(e^{-M\|\Delta\|_{*}\lambda}q(\lambda)\big)=e^{-M\|\Delta\|_{*}\lambda}\big(q^{\prime}(\lambda)-M\|\Delta\|_{*}q(\lambda)\big)\leq 0, We conclude that e^{-M\|\Delta\|_{*}\lambda}q(\lambda) is non-increasing in \lambda , and therefore e^{-M\|\Delta\|_{*}}q(1)\leq q(0). Similarly, one can verify that e^{M\|\Delta\|_{*}\lambda}q(\lambda) is non-decreasing in \lambda , which implies e^{M\|\Delta\|_{*}}q(1)\geq q(0). Therefore, e^{-M\|\Delta\|_{*}}\,q(0)\ \leq\ q(1)\ \leq\ e^{M\|\Delta\|_{*}}\,q(0). Substituting back q(0)=u^{T}\nabla^{2}f(x)u and q(1)=u^{T}\nabla^{2}f(y)u , we obtain for all u , e^{-M\|y-x\|_{*}}\,u^{T}\nabla^{2}f(x)u\leq u^{T}\nabla^{2}f(y)u\leq e^{M\|y-x\|_{*}}\,u^{T}\nabla^{2}f(x)u. Since the inequality holds for every u\in\mathbb{R}^{p} , it is equivalent to ( 10 ). ∎ E.2 Proof of Proposition 16 : Self-Concordance of log-total-potential for Hedge We will start with two lemmas concerning function \Psi in Section 6.3 . Lemma 22 (Gradient and Hessian of \Psi ) . For all x\in\mathbb{R}^{n} , a>0 . Let \Psi(\bm{x})=\log\sum_{i=1}^{n}\exp(ax_{i}) and that p_{i}(x)\;=\;\frac{e^{ax_{i}}}{\sum_{j=1}^{n}e^{ax_{j}}},\qquad p(x)=(p_{1},\ldots,p_{n}). Then \displaystyle\nabla\Psi(\bm{x}) \displaystyle=a\,p(x), \displaystyle\nabla^{2}\Psi(\bm{x}) \displaystyle=a^{2}\big(\mathrm{diag}(p(x))-p(x)\,p(x)^{T}\big). Consequently, for any h\in\mathbb{R}^{n} , h^{\textsf{T}}\nabla^{2}\Psi(\bm{x})\,h\;=\;a^{2}\!\left(\sum_{i=1}^{n}p_{i}(x)\,h_{i}^{2}-\Big(\sum_{i=1}^{n}p_{i}(x)\,h_{i}\Big)^{2}\right)\;=\;a^{2}\,\mathrm{Var}_{p(x)}(H), where H is the discrete r.v. taking values h_{i} with probabilities p_{i}(x) . Proof. Let Z(x):=\sum_{j}e^{ax_{j}} . Then \Psi(\bm{x})=\log Z(x) and \partial_{x_{i}}\Psi=ae^{ax_{i}}/Z=a\,p_{i}(x) , proving the gradient formula. For the Hessian, \partial_{x_{j}}p_{i}(x)=a(\mathbf{1}_{i=j}p_{i}-p_{i}p_{j}) , hence \partial_{x_{j}}\partial_{x_{i}}\Psi=a\,\partial_{x_{j}}p_{i}=a^{2}(\mathbf{1}_{i=j}p_{i}-p_{i}p_{j}) , which yields the stated matrix form. Plugging the Hessian into h^{T}(\cdot)h gives the variance identity. ∎ This are the standard identities of log-sum-exp function. Lemma 23 (Moment/covariance identities along a path) . Fix x\in\mathbb{R}^{n} and \Delta\in\mathbb{R}^{n} . For t\in\mathbb{R} define p^{(t)}:=p(x+t\Delta) and let expectations be w.r.t. p^{(t)} . For any fixed v\in\mathbb{R}^{n} , set the r.v. V to take values v_{i} , and W to take values \Delta_{i} . Then \displaystyle\phi_{v}(t) \displaystyle:=v^{\textsf{T}}\nabla^{2}\Psi(\bm{x}+t\Delta)\,v\;=\;a^{2}\,\mathrm{Var}_{p^{(t)}}(V), \displaystyle\phi_{v}^{\prime}(t) \displaystyle=D^{3}\Psi(\bm{x}+t\Delta)[v,v,\Delta]\;=\;a^{3}\,\mathrm{Cov}_{p^{(t)}}\!\big((V-\mathbb{E}V)^{2},\,W\big). Proof. The first identity is Lemma 22 applied at x+t\Delta . For the second, note p^{(t)}_{i}\propto e^{a(x_{i}+t\Delta_{i})} , so \frac{d}{dt}\mathbb{E}_{p^{(t)}}[F]=a\,\mathrm{Cov}_{p^{(t)}}(F,W) for any function F of the index i . Taking F=V^{2} and F=V and using \mathrm{Var}(V)=\mathbb{E}[V^{2}]-(\mathbb{E}V)^{2} gives \frac{d}{dt}\mathrm{Var}(V)=a\,\mathrm{Cov}(V^{2},W)-2\mathbb{E}V\cdot a\,\mathrm{Cov}(V,W)=a\,\mathrm{Cov}\big((V-\mathbb{E}V)^{2},W\big). Multiplying by a^{2} yields the stated \phi_{v}^{\prime}(t) . ∎ Now we are ready to prove Proposition 16 . Proof of Proposition 16 . Fix x,v,\Delta and consider \phi_{v}(t) as in Lemma 23 . From the covariance form, \displaystyle|\phi_{v}^{\prime}(t)| \displaystyle=a^{3}\left|\mathbb{E}\!\left[(V-\mathbb{E}V)^{2}\,(W-\mathbb{E}W)\right]\right|\;\leq\;a^{3}\,\Big(\sup_{i}|W_{i}-\mathbb{E}W|\Big)\,\mathbb{E}\!\left[(V-\mathbb{E}V)^{2}\right] \displaystyle\leq\;a^{3}\big(\max_{i}\Delta_{i}-\min_{i}\Delta_{i}\big)\,\mathrm{Var}(V)\;\leq\;2a^{3}\|\Delta\|_{\infty}\,\mathrm{Var}(V). By Lemma 22 , \phi_{v}(t)=a^{2}\mathrm{Var}(V) , hence |\phi_{v}^{\prime}(t)|\leq(2a)\,\|\Delta\|_{\infty}\,\phi_{v}(t). Evaluating at t=0 gives ( 9 ) in Definition 14 with M=2a=2\sqrt{2}\eta and \|\cdot\|_{\infty} ∎ E.3 Proof of Proposition 17 : Local self-concordance of log-total potential Proposition 24 (Restatement of Proposition 17 ) . The function {\log\Phi}(\bm{x},t) satisfies local generalized self-concordance with M=1 , \nu=2 and \mathcal{C} being the line-segment in ( 11 ) with respect to a special norm \|\cdot\|_{*} defined as \|(\bar{\bm{x}},\bar{t})\|_{*}=A_{x}(t_{\star},K_{\rm seg})\|\bar{x}\|_{\infty}+A_{t}(t_{\star},K_{\rm seg})|\bar{t}|. where \displaystyle A_{x}(t_{\star},K_{\rm seg})=\frac{8\sqrt{K_{\rm seg}\vee 1}}{\sqrt{t_{\star}}},\quad\text{ and }\quad A_{t}(t_{\star},K_{\rm seg})=\frac{16(K_{\rm seg}\vee 1)}{t_{*}}. Proof of Proposition 17 . Fix (\bm{x},t)\in\mathbb{R}^{n}\times\mathbb{R}_{+} and \mathbf{h}:=(\Delta\bm{x},\Delta t) , and define (\bm{x}^{\prime},t^{\prime})\coloneqq(\bm{x},t)+\mathbf{h} . For any point (\bar{\bm{x}},\bar{t}) on the segment ( 11 ) and any direction \mathbf{u}=(u_{1},\ldots,u_{n},u_{t})\in\mathbb{R}^{n+1} , it suffices to prove \big|\nabla^{3}{\log\Phi}(\bar{x},\bar{t})[\mathbf{u},\mathbf{u},\mathbf{h}]\big|\ \leq\ \Big(A_{x}(t_{\star},K_{\rm seg})\,\|\Delta\bm{x}\|_{\infty}+A_{t}(t_{\star},K_{\rm seg})\,|\Delta t|\Big)\;\nabla^{2}{\log\Phi}(\bar{\bm{x}},\bar{t})[\mathbf{u},\mathbf{u}]. (25) for A_{x} and A_{t} in ( 14 ). Overloading a bit of notation, define the path \big(\bm{x}(s),t(s)\big):=(\bm{x},t)+s\,\mathbf{h},\qquad\forall s\in[0,1]. For any \mathbf{u}\in\mathbb{R}^{n+1} define \Psi_{u}(s):=\nabla^{2}{\log\Phi}\big(\bm{x}(s),t(s)\big)[(\mathbf{u},\mathbf{u})],\qquad\forall s\in[0,1]. (26) By the chain rule along the path s\in[0,1]\mapsto(\bm{x}(s),t(s)) , whose derivative in s is \mathbf{h} we have \Psi_{u}^{\prime}(s)=\nabla^{3}{\log\Phi}\big(\bm{x}(s),t(s)\big)[(\mathbf{u},\mathbf{u},\mathbf{h})]\qquad\forall s\in[0,1]. (27) Our goal now is to show |\Psi_{u}^{\prime}(s)|\ \leq\ \big(A_{x}(t_{\star},K_{\rm seg})\|\Delta\bm{x}\|_{\infty}+A_{t}(t_{\star},K_{\rm seg})|\Delta t|\big)\,\Psi_{u}(s), (28) with A_{x},A_{t} given by ( 14 ). Log-sum-exp cumulant identities along the path. Let us start by stating some identities connecting {\log\Phi} with \log\phi and its derivatives. These identities are standard consequences of cumulant expansions for the log-partition function of a finite exponential family; see, e.g., 30 , 38 , 1 . We include the proof in the appendix for completeness. Lemma 25 (Cumulant identities for {\log\Phi} ) . Define f_{i}(\bm{x},t):=\log\phi(x_{i},t)=-\frac{1}{2}\log t+\frac{x_{i}^{2}}{2t},\qquad\text{so that}~{\log\Phi}(\bm{x},t):=\log\sum_{i=1}^{n}e^{f_{i}(\bm{x},t)}, and let \mathbf{p}(\bm{x},t)\in\Delta^{N-1} be the softmax weights of f_{i}(\bm{x},t) , that it, p_{i}(\bm{x},t)\propto\exp(f_{i}(\bm{x},t)) . Let u=(u_{1},\dots,u_{n},u_{t}) and h=(h_{1},\dots,h_{n},h_{t}) be in \mathbb{R}^{n+1} . Define, for each i\in[n] , A_{i}:=\nabla f_{i}(\bm{x},t)[\mathbf{u}],\qquad B_{i}:=\nabla^{2}f_{i}(\bm{x},t)[\mathbf{u},\mathbf{u}],\qquad C_{i}:=\nabla^{2}f_{i}(\bm{x},t)[\mathbf{u},\mathbf{h}], H_{i}:=\nabla f_{i}(\bm{x},t)[\mathbf{h}],\qquad T_{i}:=\nabla^{3}f_{i}(\bm{x},t)[\mathbf{u},\mathbf{u},\mathbf{h}]. Let I be a random variable taking values in [n] such that \mathbb{P}(I=i)=p_{i}(\bm{x},t) for all i\in[n] . Then \displaystyle\nabla^{2}{\log\Phi}(\bm{x},t)[\mathbf{u},\mathbf{u}] \displaystyle=\mathbb{E}[B_{I}]+\mathrm{Var}(A_{I}), (29) \displaystyle\nabla^{3}{\log\Phi}(\bm{x},t)[\mathbf{u},\mathbf{u},\mathbf{h}] \displaystyle=\mathbb{E}[T_{I}]+\mathrm{Cov}(B_{I},H_{I})+2\,\mathrm{Cov}(A_{I},C_{I})+\mathrm{Cov}\big((A_{I}-\mathbb{E}A_{I})^{2},H_{I}\big). (30) Remark regarding notation. Throughout the rest of the proof we fix s\in[0,1] , we suppress s in the notation, and we omit the dependence on s , writing x_{i} and t instead of x_{i}(s) or t(s) . We also often omit the dependency on (\bm{x}(s),t(s)) whenever it is clear from context, writing \nabla^{2}{\log\Phi}[(\mathbf{u},\mathbf{u})] and \nabla^{3}{\log\Phi}[(\mathbf{u},\mathbf{u},\mathbf{h})] instead of \nabla^{2}{\log\Phi}(\bm{x}(s),t(s))[(\mathbf{u},\mathbf{u})] and \nabla^{3}{\log\Phi}(\bm{x}(s),t(s))[(\mathbf{u},\mathbf{u},\mathbf{h})] . They should be interpreted as functions of s\in[0,1] , defined on a given line-segment. Equipped with the above lemma, to establish an upper bound of \nabla^{3}{\log\Phi}[(\mathbf{u},\mathbf{u},\mathbf{h})] in terms of \nabla^{2}{\log\Phi}[(\mathbf{u},\mathbf{u})] as stated in ( 28 ), it suffices to show that each element in ( 30 ) is proportional to either \mathbb{E}[B_{I}] or \mathrm{Var}(A_{I}) . Let us start by computing the values of A_{i},B_{i},C_{i},H_{i},T_{i} for i\in[n] . We will do so by introducing some new notation to reparameterize the derivatives of f_{i} and simplify some of the calculations Per-coordinate reparameterization and explicit derivatives. Fix i\in[n] and let \mathbf{w}\coloneqq(w_{i},w_{t})\in\mathbb{R}^{2} . Define a_{i}^{\star}(\mathbf{w}):=w_{i}-\frac{x_{i}}{t}\,w_{t},\qquad b(\mathbf{w}):=\frac{w_{t}}{t},\qquad r_{i}(\mathbf{w}):=\frac{(a_{i}^{\star}(\mathbf{w}))^{2}}{t},\qquad y(\mathbf{w}):=b(\mathbf{w})^{2}. Moreover, define notation for the partial derivatives of f_{i} as follows: f_{x}\coloneqq\frac{x_{i}}{t},\quad f_{t}\coloneqq-\frac{1}{2t}-\frac{x_{i}^{2}}{2t^{2}},\quad f_{xx}\coloneqq\frac{1}{t},\quad f_{xt}\coloneqq-\frac{x_{i}}{t^{2}},\quad f_{tt}\coloneqq\frac{1}{2t^{2}}+\frac{x_{i}^{2}}{t^{3}}, With the above notation, we obtain the following expressions First derivative. We have \nabla f_{i}[\mathbf{w}]=f_{x}w_{i}+f_{t}w_{t}=\frac{x_{i}}{t}w_{i}-\frac{1}{2t}w_{t}-\frac{x_{i}^{2}}{2t^{2}}w_{t}=\frac{x_{i}}{t}\,a_{i}^{\star}(\mathbf{w})+\frac{1}{2}\left(\frac{x_{i}^{2}}{t}-1\right)\,b(\mathbf{w}). Thus, A_{i}=\frac{x_{i}}{t}\,a_{i}^{\star}(\mathbf{u})+\frac{1}{2}\left(\frac{x_{i}^{2}}{t}-1\right)\,b(\mathbf{u}). and H_{i}=\frac{x_{i}}{t}\,a_{i}^{\star}(\mathbf{h})+\frac{1}{2}\left(\frac{x_{i}^{2}}{t}-1\right)\,b(\mathbf{h}). (31) Second derivative. We have \displaystyle\nabla^{2}f_{i}[(\mathbf{w},\mathbf{w})] \displaystyle=f_{xx}w_{i}^{2}+2f_{xt}w_{i}w_{t}+f_{tt}w_{t}^{2} \displaystyle=\frac{w_{i}^{2}}{t}-\frac{2w_{i}w_{t}x_{i}}{t^{2}}+\frac{w_{t}^{2}x_{i}^{2}}{t^{3}}+\frac{w_{t}^{2}}{2t^{2}} \displaystyle=\frac{(a_{i}^{\star}(\mathbf{w}))^{2}}{t}+\frac{1}{2}b(\mathbf{w})^{2}=r_{i}(\mathbf{w})+\tfrac{1}{2}y(\mathbf{w}). Thus B_{i}=r_{i}(\mathbf{u})+\tfrac{1}{2}y(\mathbf{u}). (32) Mixed second derivative. We have \displaystyle C_{i}=\nabla^{2}f_{i}[(\mathbf{u},\mathbf{h})] \displaystyle=f_{xx}u_{i}h_{i}+f_{tt}u_{t}h_{t}+f_{xt}u_{i}h_{t}+f_{tx}h_{i}u_{t} \displaystyle=\frac{u_{i}h_{i}}{t}+\frac{u_{t}h_{t}}{2t^{2}}+\frac{u_{t}h_{t}x_{i}^{2}}{t^{3}}-\frac{x_{i}}{t^{2}}(u_{i}h_{t}+h_{i}u_{t}) \displaystyle=\frac{1}{t}a_{i}^{\star}(\mathbf{u})a_{i}^{\star}(\mathbf{h})+\frac{1}{2}b(\mathbf{u})b(\mathbf{h}). (33) Third mixed derivative. Differentiating \nabla^{2}f_{i}[(\mathbf{u},\mathbf{u})]=r_{i}(\mathbf{u})+\frac{1}{2}y(\mathbf{u}) in the direction \mathbf{h} yields \displaystyle\nabla^{3}f_{i}[(\mathbf{u},\mathbf{u},\mathbf{h})] \displaystyle=\nabla r_{i}(\mathbf{u})[\mathbf{h}]+\tfrac{1}{2}\nabla y(\mathbf{u})[\mathbf{h}], \displaystyle\nabla r_{i}(\mathbf{u})[\mathbf{h}] \displaystyle=\nabla_{x}\left(\frac{(a_{i}^{\star}(\mathbf{u}))^{2}}{t}\right)h_{i}+\nabla_{t}\left(\frac{(a_{i}^{\star}(\mathbf{u}))^{2}}{t}\right)h_{t} \displaystyle=\frac{2a_{i}^{\star}(\mathbf{u})}{t}\Big(-\frac{u_{t}}{t}h_{i}+\frac{x_{i}u_{t}}{t^{2}}h_{t}\Big)-\frac{(a_{i}^{\star}(\mathbf{u}))^{2}}{t^{2}}h_{t}, \displaystyle\tfrac{1}{2}\nabla y(\mathbf{u})[\mathbf{h}] \displaystyle=\frac{1}{2}\nabla_{x}b(\mathbf{w})^{2}h_{i}+\frac{1}{2}\nabla_{t}b(\mathbf{u})^{2}h_{t}=\frac{1}{2}\nabla_{t}b(\mathbf{u})^{2}h_{t} \displaystyle=b(\mathbf{u})\nabla_{t}b(\mathbf{u})h_{t}=-\frac{u_{t}}{t}\frac{u_{t}}{t^{2}}h_{t}=-\frac{1}{t}(\frac{w_{t}}{t})^{2}h_{t}=-\frac{y(\mathbf{u})}{t}h_{t}. Hence T_{i}:=\nabla^{3}f_{i}[(\mathbf{u},\mathbf{u},\mathbf{h})]=\frac{2a_{i}^{\star}(\mathbf{u})}{t}\Big(-\frac{u_{t}}{t}h_{i}+\frac{x_{i}u_{t}}{t^{2}}h_{t}\Big)-\frac{(a_{i}^{\star}(\mathbf{u}))^{2}}{t^{2}}h_{t}-\frac{y(\mathbf{u})}{t}h_{t}. (34) Bounding intermediate states using the second derivatives From ( 32 ) we have B_{i}=\nabla^{2}f_{i}[(\mathbf{u},\mathbf{u})]=\frac{a_{i}^{*}(\mathbf{u})^{2}}{t}+\frac{1}{2}b(\mathbf{u})^{2}=r_{i}(\mathbf{u})+\frac{1}{2}y(\mathbf{u}) , which yields |a_{i}^{\star}(\mathbf{u})|\leq\sqrt{tB_{i}},\qquad|b(\mathbf{u})|\leq\sqrt{2B_{i}},\qquad r_{i}(\mathbf{u})\leq B_{i},\qquad y(\mathbf{u})\leq 2B_{i}. (35) In addition, recall that \mathbf{h}=(\Delta\bm{x},\Delta t) . From the bounds in terms of K_{\mathrm{seg}} and t^{\star} from ( 13 ), |a_{i}^{\star}(\mathbf{h})|\leq|\Delta x_{i}-\frac{x_{i}\Delta_{t}}{t}|\leq\|\Delta\bm{x}\|_{\infty}+\sqrt{\frac{K_{\rm seg}}{t_{\star}}}\,|\Delta t|,\qquad|b(\mathbf{h})|=\frac{|\Delta t|}{t}\leq\frac{|\Delta t|}{t_{\star}}. (36) These will simplify all subsequent bounds. Recall that from Lemma 25 , \nabla^{3}{\log\Phi}[(\mathbf{u},\mathbf{u},\mathbf{h})]=\mathbb{E}[T_{I}]+\mathrm{Cov}(B_{I},H_{I})+2\,\mathrm{Cov}(A_{I},C_{I})+\mathrm{Cov}\!\big((A_{I}-\mathbb{E}A_{I})^{2},H_{I}\big). Again, our goal it to bound the above as a multiple of \nabla^{2}{\log\Phi}[\mathbf{u},\mathbf{u}] . The latter, again by Lemma 25 , is equal to \mathbb{E}[B_{I}]+\mathrm{Var}[A_{I}] . Therefore, we will bound each of the four terms above by a multiple of either \mathbb{E}[B_{I}] or \mathrm{Var}[A_{I}] . Term 1: bound \big|\mathbb{E}[T_{I}]\big| . Recall ( 34 ): T_{i}=\frac{2a_{i}^{\star}(\mathbf{u})}{t}\Big(-\frac{u_{t}}{t}h_{i}+\frac{x_{i}u_{t}}{t^{2}}h_{t}\Big)-\frac{(a_{i}^{\star}(\mathbf{u}))^{2}}{t^{2}}h_{t}-\frac{y(\mathbf{u})}{t}h_{t}. Recall that h_{i}=\Delta x_{i} and h_{t}=\Delta t . Using that b(\mathbf{u})=u_{t}/t , the bounds from ( 35 ) and t\geq t_{\star} , we bound each term. First, \displaystyle\Big|\frac{2a_{i}^{\star}(\mathbf{u})}{t}\frac{u_{t}}{t}h_{i}\Big| \displaystyle=\Big|\frac{2a_{i}^{\star}(\mathbf{u})}{t}\,b(\mathbf{u})\,h_{i}\Big|\ \leq\ \frac{2|a_{i}^{\star}(\mathbf{u})|}{t}\,|b(\mathbf{u})|\,|\Delta x_{i}| \displaystyle\ \leq\ \frac{2\sqrt{tB_{i}}}{t}\,\sqrt{2B_{i}}\,\|\Delta\bm{x}\|_{\infty}\ \leq\ \frac{2\sqrt{2}}{\sqrt{t_{\star}}}\,B_{i}\,\|\Delta\bm{x}\|_{\infty}. Next, \displaystyle\Big|\frac{2a_{i}^{\star}(\mathbf{u})}{t}\frac{x_{i}u_{t}}{t^{2}}h_{t}\Big| \displaystyle=\Big|\frac{2a_{i}^{\star}(\mathbf{u})}{t}\,\frac{x_{i}}{t}\,b(\mathbf{u})\,h_{t}\Big|\ \leq\ \frac{2|a_{i}^{\star}(\mathbf{u})|}{t}\cdot\frac{|x_{i}|}{t}\cdot|b(\mathbf{u})|\,|\Delta t| \displaystyle\ \leq\ \frac{2\sqrt{tB_{i}}}{t}\cdot\sqrt{\frac{K_{\rm seg}}{t_{\star}}}\cdot\sqrt{2B_{i}}\,|\Delta t|\ \leq\ \frac{2\sqrt{2}\,\sqrt{K_{\rm seg}}}{t_{\star}}\,B_{i}\,|\Delta t|. Also, \Big|\frac{(a_{i}^{\star}(\mathbf{u}))^{2}}{t^{2}}\,h_{t}\Big|\leq\frac{B_{i}}{t}\,|\Delta t|\leq\frac{B_{i}}{t_{\star}}\,|\Delta t|,\qquad\Big|\frac{y(\mathbf{u})}{t}\,h_{t}\Big|\leq\frac{2B_{i}}{t}\,|\Delta t|\leq\frac{2B_{i}}{t_{\star}}\,|\Delta t|. Summing and taking expectation over I\sim\mathbf{p} , \big|\mathbb{E}[T_{I}]\big|\ \leq\ \left(\frac{2\sqrt{2}}{\sqrt{t_{\star}}}\ \|\Delta\bm{x}\|_{\infty}\ +\ \frac{3+2\sqrt{2}\sqrt{K_{\rm seg}}}{t_{\star}}\ |\Delta t|\right)\,\mathbb{E}[B_{I}]. (37) Term 2: bound |\mathrm{Cov}(B_{I},H_{I})| . We will use the following inequality and a bound on \sup|H| . Lemma 26 . Let X\geq 0 be an integrable random variable and let Y be bounded. Then |\mathrm{Cov}(X,Y)|\leq 2\,\sup|Y|\,\mathbb{E}[X]. (38) The proof of the above lemma is deferred to the end. For the bound on \sup_{i}|H_{i}| , from ( 31 ) and ( 36 ) we have for any i\in[n] , \displaystyle|H_{i}|=|\nabla f_{i}[\mathbf{h}]| \displaystyle\ \leq\ \frac{x_{i}}{t}\,a_{i}^{\star}(\mathbf{h})+\frac{1}{2}\left(\frac{x_{i}^{2}}{t}-1\right)\,b(\mathbf{h}) \displaystyle\leq\sqrt{\frac{K_{\rm seg}}{t_{\star}}}\;\|\Delta\bm{x}\|_{\infty}\ +\ \Big(\frac{K_{\rm seg}}{t_{\star}}+\frac{1}{2t_{\star}}\Big)\,|\Delta t|. (39) Applying Lemma 26 with X=B_{I} , Y=H_{I} , yields |\mathrm{Cov}(B_{I},H_{I})|\ \leq\ \left(\frac{2\sqrt{K_{\rm seg}}}{\sqrt{t_{\star}}}\|\Delta\bm{x}\|_{\infty}+\frac{2K_{\rm seg}+1}{t_{\star}}|\Delta t|\right)\,\mathbb{E}[B_{I}]. (40) Observe that \mathbb{E}[B_{I}]\leq\mathbb{E}[B_{I}]+\mathrm{Var}(A_{I})=\Psi_{u}(s) by ( 29 ). Term 3: bound 2\,|\mathrm{Cov}(A_{I},C_{I})| . From ( 33 ), ( 35 ) and ( 36 ), |C_{i}|\ \leq\ \frac{|a_{i}^{\star}(\mathbf{u})|}{t}\,|a_{i}^{\star}(\mathbf{h})|+\frac{|b(\mathbf{u})|}{2}\,|b(\mathbf{h})|\ \leq\ \sqrt{B_{i}}\left(\frac{\|\Delta\bm{x}\|_{\infty}}{\sqrt{t_{\star}}}+\Big(\frac{\sqrt{K_{\rm seg}}}{t_{\star}}+\frac{1}{\sqrt{2}\,t_{\star}}\Big)|\Delta t|\right). By Cauchy–Schwarz (first line) and AM–GM (third line), \displaystyle|\mathrm{Cov}(A_{I},C_{I})| \displaystyle\leq\sqrt{\mathrm{Var}(A_{I})}\sqrt{\mathrm{Var}(C_{I})}\ \leq\ \sqrt{\mathrm{Var}(A_{I})}\sqrt{\mathbb{E}[C_{I}^{2}]} \displaystyle\leq\left(\frac{\|\Delta\bm{x}\|_{\infty}}{\sqrt{t_{\star}}}+\Big(\frac{\sqrt{K_{\rm seg}}}{t_{\star}}+\frac{1}{\sqrt{2}\,t_{\star}}\Big)|\Delta t|\right)\sqrt{\mathrm{Var}(A_{I})\mathbb{E}[B_{I}]} \displaystyle\leq\frac{1}{2}\left(\frac{\|\Delta\bm{x}\|_{\infty}}{\sqrt{t_{\star}}}+\Big(\frac{\sqrt{K_{\rm seg}}}{t_{\star}}+\frac{1}{\sqrt{2}\,t_{\star}}\Big)|\Delta t|\right)\big(\mathrm{Var}(A_{I})+\mathbb{E}[B_{I}]\big). (41) Observe that \mathrm{Var}(A)+\mathbb{E}[B_{I}]=\nabla^{2}{\log\Phi}[(\mathbf{u},\mathbf{u})]=\Phi_{u}(s) (from Lemma 25 ), Term 3 is bounded as follows: 2\,|\mathrm{Cov}(A_{I},C_{I})|\ \leq\ \left(\frac{\|\Delta\bm{x}\|_{\infty}}{\sqrt{t_{\star}}}+\Big(\frac{\sqrt{K_{\rm seg}}}{t_{\star}}+\frac{1}{\sqrt{2}\,t_{\star}}\Big)|\Delta t|\right)\,\Phi_{u}(s). (42) Term 4: bound \big|\mathrm{Cov}((A_{I}-\mathbb{E}A_{I})^{2},H_{I})\big| . Applying Lemma 26 with X=(A_{I}-\mathbb{E}A_{I})^{2} and Y=H_{I} together on the bound on \sup_{i}|H_{i}| from ( 39 ) yields \big|\mathrm{Cov}\big((A_{I}-\mathbb{E}A_{I})^{2},H_{I}\big)\big|\ \leq\ \mathrm{Var}(A_{I})\left(\frac{2\sqrt{K_{\rm seg}}}{\sqrt{t_{\star}}}\|\Delta\bm{x}\|_{\infty}+\frac{2K_{\rm seg}+1}{t_{\star}}|\Delta t|\right). (43) Note that \mathrm{Var}_{p}(A)\leq\Phi_{u}(s) by ( 29 ). Collecting bounds and integrating. Add ( 37 ), ( 40 ), ( 42 ), ( 43 ). Group the coefficients of \|\Delta\bm{x}\|_{\infty} and |\Delta t| yields |\Phi_{u}^{\prime}(s)|\ \leq\ \Big(\tilde{A}_{x}\,\|\Delta\bm{x}\|_{\infty}+\tilde{A}_{t}\,|\Delta t|\Big)\,\Phi_{u}(s), with \tilde{A}_{x}=\frac{2\sqrt{2}}{\sqrt{t_{\star}}}+\frac{2\sqrt{K_{\rm seg}}}{\sqrt{t_{\star}}}+\frac{1}{\sqrt{t_{\star}}}+\frac{2\sqrt{K_{\rm seg}}}{\sqrt{t_{\star}}}=\frac{2\sqrt{2}+1+4\sqrt{K_{\rm seg}}}{\sqrt{t_{\star}}}, \tilde{A}_{t}=\frac{3+2\sqrt{2}\sqrt{K_{\rm seg}}}{t_{\star}}+\frac{2K_{\rm seg}+1}{t_{\star}}+\left(\frac{\sqrt{K_{\rm seg}}}{t_{\star}}+\frac{1}{\sqrt{2}\,t_{\star}}\right)+\frac{2K_{\rm seg}+1}{t_{\star}}=\frac{5+\tfrac{1}{\sqrt{2}}}{t_{\star}}+\frac{(2\sqrt{2}+1)\sqrt{K_{\rm seg}}}{t_{\star}}+\frac{4K_{\rm seg}}{t_{\star}}. The proof is complete by relaxing the above bounds so that \tilde{A}_{x}\leq\frac{8\sqrt{K_{\rm seg}\vee 1}}{\sqrt{t_{\star}}}=A_{x}(t_{\star},K_{\rm seg})\qquad\text{and}\qquad\tilde{A}_{t}\leq\frac{16(K_{\rm seg}\vee 1)}{t_{*}}=A_{t}(t_{\star},K_{\rm seg}). ∎ E.4 Proof of Auxiliary Lemmas Proof of Lemma 25 . Throughout this proof we omit the dependency on (\bm{x},t) . First, define Z\coloneqq\sum_{i=1}^{n}\exp(f_{i}) . Step 1: a basic derivative rule for p_{i} . Since p_{i}=e^{f_{i}}/Z and {\log\Phi}=\log Z , for any direction \mathbf{w}\in\mathbb{R}^{n+1} , \nabla p_{i}[\mathbf{w}]=p_{i}\cdot\big(\nabla f_{i}[\mathbf{w}]-\nabla G[\mathbf{w}]\big). (44) Indeed, \nabla p_{i}[\mathbf{w}]=p_{i}\,\nabla f_{i}[\mathbf{w}]-p_{i}\,\nabla G[\mathbf{w}] by the quotient rule. Step 2: gradient identity. Differentiating {\log\Phi}=\log Z yields \nabla{\log\Phi}[\mathbf{w}]=\frac{1}{Z}\sum_{i=1}^{n}e^{f_{i}}\,\nabla f_{i}[\mathbf{w}]=\sum_{i=1}^{n}p_{i}\,\nabla f_{i}[\mathbf{w}]. In particular, for \mathbf{w}=\mathbf{u} we have \nabla f_{i}[\mathbf{u}]=A_{i} , so \nabla{\log\Phi}[\mathbf{u}]=\mathbb{E}[A_{I}]. (45) Step 3: Hessian identity. Differentiate ( 45 ) in direction \mathbf{u} : \nabla^{2}{\log\Phi}[\mathbf{u},\mathbf{u}]=\nabla\Big(\sum_{i=1}^{n}p_{i}A_{i}\Big)[\mathbf{u}]=\sum_{i=1}^{n}\nabla p_{i}[\mathbf{u}]\;A_{i}+\sum_{i=1}^{n}p_{i}\,\nabla A_{i}[\mathbf{u}]. Now \nabla A_{i}[\mathbf{u}]=\nabla^{2}f_{i}[\mathbf{u},\mathbf{u}]=B_{i} , and by ( 44 ) with \mathbf{w}=\mathbf{u} , \nabla p_{i}[\mathbf{u}]=p_{i}(A_{i}-\nabla{\log\Phi}[\mathbf{u}])=p_{i}(A_{i}-\mathbb{E}[A_{I}]). Therefore \nabla^{2}{\log\Phi}[\mathbf{u},\mathbf{u}]=\sum_{i=1}^{n}p_{i}(A_{i}-\mathbb{E}[A_{I}])A_{i}+\sum_{i=1}^{n}p_{i}B_{i}=\mathbb{E}[B]+\big(\mathbb{E}[A_{I}^{2}]-(\mathbb{E}[A_{I}])^{2}\big), which is ( 29 ). Step 4: differentiate the Hessian in direction h . From ( 29 ), \nabla^{3}{\log\Phi}[\mathbf{u},\mathbf{u},\mathbf{h}]=\nabla\big(\mathbb{E}[B_{I}]\big)[\mathbf{h}]+\nabla\big(\mathrm{Var}(A_{I})\big)[\mathbf{h}]. Step 5: derivative of the expectation term. Using the product rule, \nabla\big(\mathbb{E}[B_{I}]\big)[\mathbf{h}]=\nabla\Big(\sum_{i=1}^{n}p_{i}B_{i}\Big)[\mathbf{h}]=\sum_{i=1}^{n}\nabla p_{i}[\mathbf{h}]\;B_{i}+\sum_{i=1}^{n}p_{i}\,\nabla B_{i}[\mathbf{h}]. Here \nabla B_{i}[\mathbf{h}]=\nabla^{3}f_{i}[\mathbf{u},\mathbf{u},\mathbf{h}]=T_{i} . Also, by ( 44 ) with \mathbf{w}=\mathbf{h} and since H_{i}=\nabla f_{i}[\mathbf{h}] , \nabla p_{i}[\mathbf{h}]=p_{i}(H_{i}-\nabla{\log\Phi}[\mathbf{h}])=p_{i}(H_{i}-\mathbb{E}[H_{I}]), where in the last equation we used that \nabla{\log\Phi}[\mathbf{h}]=\sum_{i}p_{i}\nabla f_{i}[\mathbf{h}]=\mathbb{E}[H_{I}] . Hence, \nabla\big(\mathbb{E}[B_{I}]\big)[\mathbf{h}]=\mathbb{E}[T_{I}]+\mathbb{E}\big[(H_{I}-\mathbb{E}[H_{I}])B_{I}\big]=\mathbb{E}[T_{I}]+\mathrm{Cov}(B_{I},H_{I}). Step 6: derivative of the variance term. Since \mathrm{Var}(A_{I})=\mathbb{E}[A_{I}^{2}]-(\mathbb{E}[A_{I}`^{\prime}])^{2} , we have \nabla\big(\mathrm{Var}(A_{I})\big)[\mathbf{h}]=\nabla\mathbb{E}[A_{I}^{2}][\mathbf{h}]-2\,\mathbb{E}[A_{I}]\;\nabla\mathbb{E}[A_{I}][\mathbf{h}]. (46) We compute each piece. First, \nabla\mathbb{E}[A_{I}][\mathbf{h}]=\nabla\Big(\sum_{i=1}^{n}p_{i}A_{i}\Big)[\mathbf{h}]=\sum_{i=1}^{n}\nabla p_{i}[\mathbf{h}]\;A_{i}+\sum_{i=1}^{n}p_{i}\,\nabla A_{i}[\mathbf{h}]. Now \nabla A_{i}[\mathbf{h}]=\nabla^{2}f_{i}[\mathbf{u},\mathbf{h}]=C_{i} , and \nabla p_{i}[\mathbf{h}]=p_{i}(H_{i}-\mathbb{E}[H_{I}]) , so \nabla\mathbb{E}[A][h]=\mathbb{E}[C]+\mathrm{Cov}(A,H). (47) Second, \nabla\mathbb{E}[A^{2}][h]=\nabla\Big(\sum_{i=1}^{n}p_{i}A_{i}^{2}\Big)[h]=\sum_{i=1}^{n}\nabla p_{i}[h]\;A_{i}^{2}+\sum_{i=1}^{n}p_{i}\,\nabla(A_{i}^{2})[h]. Since \nabla(A_{i}^{2})[h]=2A_{i}\,\nabla A_{i}[h]=2A_{i}C_{i} , we get \nabla\mathbb{E}[A_{I}^{2}][\mathbf{h}]=\mathbb{E}[2A_{I}C_{I}]+\mathrm{Cov}(A_{I}^{2},H_{I}). (48) Substitute ( 47 )–( 48 ) into ( 46 ): \nabla\big(\mathrm{Var}(A_{I})\big)[\mathbf{h}]=2\mathbb{E}[A_{I}C_{I}]+\mathrm{Cov}(A_{I}^{2},H_{I})-2\mathbb{E}[A_{I}]\mathbb{E}[C_{I}]-2\mathbb{E}[A_{I}]\mathrm{Cov}(A_{I},H_{I}). Note that 2\mathbb{E}[A_{I}C_{I}]-2\mathbb{E}[A_{I}]\mathbb{E}[C_{I}]=2\,\mathrm{Cov}(A_{I},C_{I}), and also the covariance identity \mathrm{Cov}\big((A_{I}-\mathbb{E}[A_{I}])^{2},H_{I}\big)=\mathrm{Cov}(A_{I}^{2},H_{I})-2\mathbb{E}[A_{I}]\mathrm{Cov}(A_{I},H_{I}) follows from expanding (A_{I}-\mathbb{E}[A_{I}])^{2}=A_{I}^{2}-2\mathbb{E}[A_{I}]A_{I}+(\mathbb{E}[A_{I}])^{2} and using \mathrm{Cov}(\mathbb{E}[A_{I}],H_{I})=0 since \mathbb{E}[A_{I}] is a constant. Therefore, \nabla\big(\mathrm{Var}(A_{I})\big)[\mathbf{h}]=2\,\mathrm{Cov}(A_{I},C_{I})+\mathrm{Cov}\big((A_{I}-\mathbb{E}[A_{I}])^{2},H_{I}\big). Step 7: conclude. Combining Step 5 and Step 6 with Step 4 gives ( 30 ). ∎ Proof of Lemma 26 . Recall that \mathrm{Cov}(X,Y)=\mathbb{E}\big[(X-\mathbb{E}X)(Y-\mathbb{E}Y)\big]. Since \mathbb{E}(Y-\mathbb{E}Y)=0 , we may also write \mathrm{Cov}(X,Y)=\mathbb{E}\big[X(Y-\mathbb{E}Y)\big]. Using that X\geq 0 , we obtain |\mathrm{Cov}(X,Y)|\leq\mathbb{E}\big[X\,|Y-\mathbb{E}Y|\big]. If \|Y\|_{\infty}:=\sup|Y|<\infty , then |Y-\mathbb{E}Y|\leq|Y|+|\mathbb{E}Y|\leq 2\|Y\|_{\infty}. Therefore, \mathbb{E}\big[X\,|Y-\mathbb{E}Y|\big]\leq 2\|Y\|_{\infty}\,\mathbb{E}[X]. ∎ Appendix F Detailed proof of Theorem 6 : NormalHedge F.1 Higher order derivatives of normal potential Next, we will bound the higher-order derivatives of \phi . Lemma 27 (Bounding the higher order derivatives of \phi ) . Let \phi(x,t)=\phi_{\mbox{\tiny NH}}(x,t) . Assume x^{2}/t\leq K . For all x and t>0 , \frac{\partial^{2}}{\partial x^{2}}\phi(x,t)=\Big(\frac{x^{2}}{t^{2}}+\frac{1}{t}\Big)\phi(x,t)\leq\frac{(1+K)}{t}\phi(x,t) \frac{\partial^{3}}{\partial x^{3}}\phi(x,t)=\Big(\frac{x^{3}}{t^{3}}+\frac{3x}{t^{2}}\Big)\phi(x,t)\leq\frac{K^{1.5}+3K^{0.5}}{t^{1.5}}\phi(x,t) \frac{\partial^{4}}{\partial x^{4}}\phi(x,t)=4\frac{\partial^{2}}{\partial t^{2}}\phi(x,t)=\Big(\frac{x^{4}+6tx^{2}+3t^{2}}{t^{4}}\Big)\phi(x,t)\leq\frac{K^{2}+6K+3}{t^{2}}\phi(x,t) Proof. The proof follows from standard calculus. We have verified the identities symbolically using both SymPy and Maple. ∎ F.2 Proof of Lemma 13 Lemma 28 (Restating Lemma 13 ) . If \phi=\phi_{\mathrm{NH}} , then \DErr_{\Phi}(\bm{x},t)\leq(\max_{i}\nicefrac{{x_{i}^{2}}}{{t}}+4)/4t . Proof of Lemma 13 . Define \mathbf{r}\in\Delta^{N-1} by r_{i}\coloneqq\phi(x_{i},t)/\Phi(\bm{x}) for each i\in[n] . By the formulas for the derivatives of \phi in Lemma 27 , we get \displaystyle\frac{1}{\Phi(\bm{x},t)}\sum_{i}\frac{\partial^{4}}{\partial x^{4}}\phi(x_{i},t) \displaystyle=\mathbb{E}_{i\sim\mathbf{r}}\left[\frac{x_{i}^{4}+6tx_{i}^{2}+3t^{2}}{t^{4}}\right], \displaystyle\text{and}\quad\frac{1}{\Phi(\bm{x},t)}\sum_{i}\frac{\partial^{2}}{\partial x^{2}}\phi(x_{i},t) \displaystyle=\mathbb{E}_{i\sim\mathbf{r}}\left[\frac{x_{i}^{2}+t}{t^{2}}\right]. Set u_{i}\coloneqq\frac{x_{i}^{2}}{t}+1 . Plugging them into the definiton of \DErr_{\Phi}(\bm{x},t) for \phi=\phi_{\mbox{\tiny NH}} yields \displaystyle\DErr_{\Phi}(\bm{x},t)=\frac{1}{4t}\left(\frac{\mathbb{E}_{i\sim\mathbf{r}}[u_{i}^{2}+4u_{i}-2]}{\mathbb{E}_{i\sim\mathbf{r}}[u_{i}]}-\mathbb{E}_{i\sim\mathbf{r}}[u_{i}]\right) \displaystyle\leq\frac{1}{4t}\left(\frac{\mathrm{Var}_{i\sim\mathbf{r}}[u_{i}]}{\mathbb{E}_{i\sim\mathbf{r}}[u_{i}]}+4\right) \displaystyle\leq\frac{\max_{i}\frac{x_{i}^{2}}{t}+4}{4t} where the last step uses the Bhatia-Davis bound, which says that for a random variable X bounded between [a,b] with mean \mu we have \mathrm{Var}(X)\leq(b-\mu)(\mu-a) . Dividing both sides by \mu , one may verify that the right-hand side is maximized at \mu=\sqrt{ab} , which yields \mathrm{Var}[X]/\mu\leq(b-\mu)(\mu-a)/\mu\leq(\sqrt{b}-\sqrt{a})^{2}\leq b-a. ∎ F.3 Proof of the crude bound on \Delta t Lemma 29 (Restating Lemma 19 ) . If K>0 is such that \max_{i\in[N]}\frac{x_{i}^{2}}{t}\leq K , then t\geq 256e^{2}B^{2}\max\{K,1\}\implies\Delta t\leq 2eB^{2}. Proof of Lemma 19 . For this proof, we want to find the smallest \sigma\geq 0 such that \Phi(\bm{x}+\Delta\bm{x},\,t+\sigma)\leq\Phi(\bm{x},t). Since \Phi is continuous, such a \sigma that makes the inequality an equation must necessarily equal \Delta t by uniqueness (Lemma 9 ). Therefore, if we find any \sigma>0 that make the above inequality hold, we have that \Delta t\leq\sigma . Our claim is that \sigma=2eB^{2} works for t as in the lemma. Therefore, for the rest of this proof we will slightly overload the notation of \Delta t , considering an arbitrary \Delta t>0 and showing that if \Delta t=2eB^{2} , then \Phi(\bm{x}+\Delta\bm{x},\,t+\Delta t)\leq\Phi(\bm{x},t) . Let us first obtain a bound on the local-self-concordance parameter. At (\bm{x},t) , by hypothesis we have \max_{i\in[N]}\frac{x_{i}^{2}}{t}\leq K . Thus, since \|\Delta\bm{x}\|_{\infty}\leq B , for every i\in[N] we have \frac{(x_{i}+\Delta x_{i})^{2}}{t+\Delta t}\leq\frac{2x_{i}^{2}}{t+\Delta t}+\frac{2\Delta x_{i}^{2}}{t+\Delta t}\leq 2K+\frac{2B^{2}}{t}. Define (\bm{x}(s),t(s))=(\bm{x}+s\Delta\bm{x},t+s\Delta t) for s\in[0,1] to be the line segment between (\bm{x},t) and (\bm{x}^{\prime},t^{\prime}) . It is clear that t_{\star}:=\min_{s\in[0,1]}t(s)=t , and by the joint-convexity of x^{2}/t on \mathbb{R}\times\mathbb{R}_{+} , we have K_{\rm seg}:=\sup_{s\in[0,1]}\ \max_{i\in[N]}\frac{x_{i}(s)^{2}}{t(s)}=\max_{s\in\{0,1\}}\max_{i\in[N]}\frac{x_{i}(s)^{2}}{t(s)}\leq 2K+\frac{2B^{2}}{t}. Furthermore, if t\geq 2B^{2} we can simplify the bound to K_{\rm seg}\vee 1\leq 2K+1 . Therefore, we can bound the self-concordance parameters of the NormalHedge potential from Proposition 17 by A_{x}(t_{\star},K_{\rm seg})\leq 8\sqrt{(2K+1)/t}=:\overline{A}_{x},\quad\quad A_{t}(t_{\star},K_{\rm seg})\leq 16(2K+1)/t)=:\overline{A}_{t}. (49) These bounds will be used later to show that e^{\Lambda} is small. By Lemma 10 (Taylor’s theorem of \log\Phi(\bm{x}^{\prime},t^{\prime}) around (\bm{x},t) ), we have \displaystyle\log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t)=-\frac{\sum_{i=1}^{N}\frac{\partial^{2}}{\partial x^{2}}\phi(x_{i},t)\Delta t}{2\Phi(\bm{x},t)}+\frac{1}{2}\nabla^{2}\log\Phi(\bar{x},\bar{t})[\Delta,\Delta] for some (\bar{\bm{x}},\bar{t}) on the line segment between (\bm{x},t) to (\bm{x}^{\prime},t^{\prime}) . Define the shorthand \overline{\Lambda}:=\overline{A}_{x}\|\Delta\bm{x}\|_{\infty}+\overline{A}_{t}|\Delta t| , generalized local self-concordance of the potential (Proposition 17 ), we can upper-bound the Hessian of {\log\Phi} at \bar{\bm{x}} by Corollary 18 , which yields \displaystyle\log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t)+\frac{1}{2}\frac{\sum_{i=1}^{N}\frac{\partial^{2}}{\partial x^{2}}\phi(x_{i},t)}{\Phi(\bm{x},t)}\Delta t=\frac{1}{2}\nabla^{2}\log\Phi(\bar{x},\bar{t})[\Delta,\Delta] \displaystyle\leq \displaystyle\frac{1}{2}e^{\bar{\Lambda}}\nabla^{2}\log\Phi(\bm{x},t)[\Delta,\Delta],. By following similar calculations to the ones in the proof of Lemma 11 , one can show that \frac{\Phi(\bm{x},t)(\log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t))}{\sum_{i=1}^{N}\frac{\partial^{2}}{\partial x^{2}}\phi(x_{i},t)}+\frac{\Delta t}{2}\leq\frac{1}{2}e^{\overline{\Lambda}}\left(\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+\Delta t^{2}\DErr_{\Phi}(\bm{x},t)\right) Lemma 13 bounds the discretization error by \max_{i}x_{i}^{2}/t+3 , and by assumption \max_{i}x_{i}^{2}/4t\leq K . Therefore, putting everything together yields \frac{\Phi(\bm{x},t)(\log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t))}{\sum_{i=1}^{N}\frac{\partial^{2}}{\partial x^{2}}\phi(x_{i},t)}+\frac{\Delta t}{2}\leq\frac{1}{2}e^{\overline{\Lambda}}\left(\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+\frac{\Delta t^{2}}{4t}(K+4)\right) Thus, notice that in order for \log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t)\leq 0 , it suffices for us to choose \Delta t\geq e^{\overline{\Lambda}}\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+e^{\overline{\Lambda}}\left(\frac{K+4}{4t}\Delta t^{2}\right). (50) Since \max_{i}|\Delta x_{i}|\leq B (and assume K\geq 1 ), it suffices that \Delta t\geq e^{\bar{\Lambda}}(B^{2}+\frac{K+4}{4t}\Delta t^{2}). (51) We just need to show now that plugging \Delta t=2eB^{2} into ( 51 ) satisfies the inequality. We claim that if we choose \Delta t=2eB^{2} and t\geq 256e^{2}B^{2}\max\{K,1\} (both hypotheses of the lemma we are proving), then the inequality ( 51 ) is true. Thus, let us show that ( 51 ) holds. First, to bound \overline{\Lambda} we use that \Delta t=2eB^{2} and that t\geq 256e^{2}B^{2}\max\{K,1\} in the formulas of \overline{A}_{x},\overline{A}_{t} in ( 49 ) to get \displaystyle\overline{\Lambda} \displaystyle=\overline{A}_{x}\|\Delta\bm{x}\|_{\infty}+\overline{A}_{t}|\Delta t|\leq\frac{8\sqrt{2K+1}B}{\sqrt{t}}+\frac{16(2K+1)2eB^{2}}{t} \displaystyle\leq\sqrt{\frac{2K+1}{8\max\{K,1\}e^{2}}}+\frac{2(2K+1)}{16\max\{K,1\}e}\leq 1. Moreover, we have B^{2}+\frac{K+4}{4t}\Delta t^{2}\leq B^{2}+\frac{K+4}{4\times 256e^{2}B^{2}\max\{K,1\}}\times 4e^{2}B^{4}\leq 2B^{2}. It follows that \textsc{RHS of \eqref{eq:crude_circular_inequality}}\leq e^{\overline{\Lambda}}(2B^{2})\leq 2eB^{2}\leq\Delta t. This checks that our choice of \Delta t is valid for ( 51 ), hence implies that for this choice \log\Phi(\bm{x}^{\prime},t^{\prime})-\log\Phi(\bm{x},t)\leq 0 , which completes the proof for Lemma 19 . ∎ F.4 Bounding K_{\mathrm{seg}} and self-concordance parameters. Now, we will use the fact that \Delta t is algorithmically chosen (see Line 4 of the CP algorithm) to ensure a non-increasing potential \Phi . First of all, observe that for every iterate (\bm{x}_{j},t_{j}) that the algorithm generates, \Phi(\bm{x}_{j},t_{j})\leq\Phi(0,t_{0})=\frac{N}{\sqrt{t_{0}}} . Moreover, we have the following lemmas. Lemma 30 . If \Phi(\bm{x},t)\leq C and \Phi(\bm{x}^{\prime},t^{\prime})\leq C , then for any (\bar{\bm{x}},\bar{t}) on the line-segment between (\bm{x},t) and (\bm{x}^{\prime},t^{\prime}) satisfies \Phi(\bar{\bm{x}},\bar{t})\leq C. Proof. First, observe that \phi is convex (the quadratic over linear function on \mathbb{R}\times\mathbb{R}_{+} ). The function \Phi is thus jointly convex in x,t (the sum of convex functions is convex). It follows that the univariate function when we restrict \Phi to the line segment between (\bm{x},t),(\bm{x}^{\prime},t^{\prime}) is convex. Lastly, the maximum of a convex function in a closed interval occurs on the boundary. ∎ Lemma 31 . If \Phi(\bm{x},t)\leq C then \max_{i}\frac{|x_{i}|^{2}}{t}\leq\frac{1}{2}\log t+\log C . Proof. By the definition and the non-negativity of \phi(x_{i},t) for t>0 , for any i\in[N] we have \frac{1}{\sqrt{t}}\exp(x_{i}^{2}/2t)=\phi(x_{i},t)\leq\sum_{i=1}^{N}\phi(x_{i},t)=\Phi(\bm{x},t)\leq C. The proof is complete by taking log on both sides. ∎ These two lemmas together allow us to obtain a great bound of the local generalized self-concordance parameter of \log\Phi . Specifically, the algorithm maintains the invariant that for any regret vector \bm{x} with time variable t in the algorithm, \max_{i}\frac{x_{i}^{2}}{2t}\leq\frac{1}{2}\log t-\frac{1}{2}\log t_{0}+\log N=\frac{1}{2}\log(t/t_{0})+\log N\eqqcolon K(t). (52) Notice that this quantity is (mildly) growing in O(\log t) . Then, for K_{\mathrm{seg}} define as in ( 13 ) we have K_{\mathrm{seg}}=\sup_{s\in[0,1]}\ \max_{i\in[N]}\frac{x_{i}(s)^{2}}{t(s)}\stackrel{{\scriptstyle\eqref{eq:cp_Kseg_invariant}}}{{\leq}}\log(\max\{t,t^{\prime}\}/t_{0})+\log N\leq\log((t+\Delta t)/t_{0})+2\log N. (53) The next lemma simply shows that, since K(t) grows slowly in t , if we have t_{0}\geq CK(t_{0}) , then we have t\geq CK(t) for all t\geq t_{0} . Lemma 32 . Define K(t):=\max\left\{1,\log(t/t_{0})+2\log N\right\} . Assume t_{0}\geq 256e^{2}B^{2}K(t_{0}) , then for any t>t_{0} , t\geq 256e^{2}B^{2}K(t). (54) Proof. Observe that K(t) monotonically increases with t . Let \tau be such that K(\tau)=1 . For t_{0}\leq t\leq\tau , the claim is trivial, since K(t)=K(t_{0})=1 , t\geq t_{0}\geq 256e^{2}B^{2}K(t_{0})=256e^{2}B^{2}K(t). For t>\tau , define h(t):=t-256e^{2}B^{2}(\log(t/t_{0})+2\log N). Take the derivative of h , we have h^{\prime}(t)=1-\frac{256e^{2}B^{2}}{t}\geq 1-\frac{256e^{2}B^{2}}{t_{0}}, where the inequality holds since t>t_{0}=256e^{2}B^{2}K(t_{0})\geq 256e^{2}B^{2} . Thus, h^{\prime}(t)>0 for all t>\tau . This ensures that h(t)\geq 0 , and, thus t\geq 256e^{2}B^{2}K(t) , for t>\tau . ∎ The next lemma summarizes the above discussion and provides a tighter bound on the self-concordance parameters of the NormalHedge potential for all t\geq t_{0} , which will be useful in the next section to get a refined bound on \Delta t . Lemma 33 . Let t_{0}=256e^{2}B^{2}\max\left\{1,2\log N\right\} . Moreover, let (\bm{x},t) and (\bm{x}^{\prime},t^{\prime})=(\bm{x}+\Delta x,t+\Delta t) be such that t\geq t_{0} and \Phi(\bm{x}^{\prime},t^{\prime})\leq\Phi(\bm{x},t)\leq\Phi(0,t_{0}) . Finally, let A_{x} , A_{t} be as in ( 49 ) Proposition 17 . Then \Lambda:=A_{x}(t_{\star},K_{\rm seg})\,\|\Delta\bm{x}\|_{\infty}+A_{t}(t_{\star},K_{\rm seg})\,|\Delta t|\leq 0.414. Proof. Since \Phi(\bm{x}^{\prime},t^{\prime})\leq\Phi(0,t_{0})=\frac{N}{\sqrt{t_{0}}} , we have seen (see ( 53 )) that K_{\mathrm{seg}}(t)\stackrel{{\scriptstyle\eqref{eq:cp_Kseg_invariant_2}}}{{\leq}}\log((t+\Delta t)/t_{0})+2\log N\leq\log((t+2eB^{2})/t_{0})+2\log N\leq\log(1+t/t_{0})+2\log N, where the last inequality follows from our choice t_{0}=256e^{2}B^{2}\max\left\{1,2\log N\right\}\geq 2eB^{2} . We want to upper bound the above by K(t) defined as in Lemma 32 . The above expression depends on \log(1+t/t_{0}) , while K(t) depends on \log(t/t0) , but fortunately they are not too far from each other. Indeed, notice that \log\left(1+\frac{t}{t_{0}}\right)=\log\left(\frac{t}{t_{0}}\left(\frac{t_{0}}{t}+1\right)\right)=\log(\frac{t}{t_{0}})+\log\left(\frac{t_{0}}{t}+1\right)\leq\log\left(\frac{t}{t_{0}}\right)+\log 2 Therefore, K_{\mathrm{seg}}\leq\log(1+t/t_{0})+2\log N\leq\log(t/t_{0})+2\log N+\log 2\leq K(t)+\log 2\leq 2K(t). Therefore, we can upper bound A_{x}(t_{\star},K_{\rm seg}) and A_{t}(t_{\star},K_{\rm seg}) in terms of K(t) as follows: A_{x}(t_{\star},K_{\rm seg})\leq\frac{8\sqrt{K_{\rm seg}\vee 1}}{\sqrt{t_{\star}}}\leq 8\sqrt{\frac{2K(t)}{t}}, and A_{t}(t_{\star},K_{\rm seg})\leq\frac{16(K_{\rm seg}\vee 1)}{t_{*}}\leq\frac{32K(t)B^{2}}{tB^{2}}. (55) Since t\geq t_{0} , Lemma 32 relates K(t) and t , we have \eqref{eq:interm_at_bound}=\sqrt{\frac{32K(t)B^{2}}{t}}\sqrt{\frac{32K(t)B^{2}}{t}}\frac{1}{B^{2}}\stackrel{{\scriptstyle\eqref{eq:bound_on_Kt}}}{{\leq}}\frac{1}{e}\sqrt{\frac{8K(t)B^{2}}{t}}\frac{1}{B^{2}}. Therefore, \displaystyle\Lambda \displaystyle=A_{x}(t_{\star},K_{\rm seg})\,\|\Delta\bm{x}\|_{\infty}+A_{t}(t_{\star},K_{\rm seg})\,|\Delta t| \displaystyle\leq 8\sqrt{\frac{2K(t)}{t}}\cdot B+\frac{1}{e}\sqrt{\frac{8K(t)B^{2}}{t}}\frac{1}{B^{2}}\cdot 2eB^{2} \displaystyle\leq 8\sqrt{\frac{2K(t)}{t}}\cdot B+2\sqrt{\frac{8K(t)}{t}}B \displaystyle\leq 17B\sqrt{\frac{K(t)}{t}}\stackrel{{\scriptstyle\eqref{eq:bound_on_Kt}}}{{\leq}}17B\sqrt{\frac{1}{256e^{2}B^{2}}}\leq\frac{17}{16\cdot e}\leq 0.414. ∎ F.5 A Refined Bound of \Delta t and Proof of Theorem 6 Now we are ready to obtain a stronger second-order bound of \Delta t , which ultimately implies the regret bound in Theorem 6 . Proof of Theorem 6 . In Lemma 4 we established that, since the potential does not increase in {\sf CP} , if (\bm{x}^{(T)},t^{(T)}) is the final iterate of the CP algorithm after T rounds, then for any \epsilon\in(0,1) , the regret to the top \epsilon -quantile of experts satisfies x_{(N\epsilon)}\leq\sqrt{t_{T}(\log(t_{T}/t_{0})+2\log(1/\epsilon))}. It suffices that we bound t_{T} . For that, we shall bound all the increments \Delta t_{j}\coloneqq t_{j}-t_{j-1} for j=0,1,\ldots,T-1 . Let (\bm{x},t) and (\bm{x}^{\prime},t^{\prime}) be consecutive iterates generated by the CP algorithm. Recall that \Delta\bm{x}=\bm{x}^{\prime}-\bm{x} and \Delta t=t^{\prime}-t . By the choice of \Delta t is the {\sf CP} algorithm we have \Phi(\bm{x},t)=\Phi(\bm{x}^{\prime},t^{\prime}) . Thus, Lemma 11 and by the local self-concordance of the NormalHedge potential (Proposition 17 ) we have, \Delta t\leq e^{\Lambda}\left(\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+\frac{\Delta t^{2}}{4t}\left(\max_{i}\frac{x_{i}^{2}}{t}+4\right)\right) (56) where \mathbf{q}\in\Delta^{N-1} is such that q_{i}\propto\partial_{xx}\phi(x_{i},t) . Moreover, since \Phi(\bm{x},t)\leq\Phi(0,t_{0})=1/\sqrt{t_{0}} , if K(t) is defined as in Lemma 32 , then \max_{i}\frac{x_{i}^{2}}{t}\leq\log(t/t_{0})+\log N\leq K(t). In the next calculation we want to use Lemmas 19 and 32 , both which require t and t_{0} to be large enough. For Lemma 19 , we ned t\geq 256e^{2}B^{2} , which is true since , for our choice of t_{0} , we have t_{0}\geq 256e^{2}B^{2} . Similarly, Lemma 32 requires t_{0}\geq 256e^{2}B^{2}K(t_{0}) where K(t_{0})=\max\{1,2\log N\} , and our choice of t_{0} satisfies this as an equation by the definition of t_{0} . Therefore, ( 56 ) \displaystyle\leq e^{\Lambda}\left(\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]+\frac{\Delta t^{2}}{4t}\underbrace{\left(K(t)+4\right)}_{\leq 5K(t)}\right) \displaystyle\leq e^{\Lambda}\left(\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]+\frac{2eB^{2}\Delta t}{4t}\cdot 5K(t)\right) (by Lemma 19 ) \displaystyle\leq e^{\Lambda}\left(\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]+\frac{4eB^{2}\Delta t}{256e^{2}B^{2}}\right) (by Lemma 32 ) \displaystyle\leq e^{0.414}\left(\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]+\frac{4eB^{2}\Delta t}{256e^{2}B^{2}}\right) (by Lemma 33 ) \displaystyle\leq e^{0.414}\left(\mathbb{E}_{i\sim q}[\Delta x_{i}^{2}]+\frac{\Delta t}{64e}\right) Grouping \Delta t terms on the left hand side and using that e^{-0.414}-\frac{1}{64e}\geq 0.64>0.5 , we get \Delta t\leq 2\mathbb{E}_{i\sim\mathbf{q}}\left[\Delta x_{i}^{2}\right]. (57) Let us apply the above bound to all the increments \Delta t_{1},\Delta t_{2},\dotsc,\Delta_{T} from CP . Namely, by the description of CP we have t=t_{0}+\sum_{j=1}^{T}\Delta t_{j}\leq t_{0}+2\sum_{j=1}^{T}\mathbb{E}_{i\sim\mathbf{q}_{j}}[(\Delta x_{j,i}^{2}]=V_{T}. Therefore, the final regret bounds is \sqrt{(t_{0}+2V_{T})\left(\log(\frac{t_{0}+2V_{T}}{t_{0}})+2\log(1/\epsilon)\right)}. ∎ Remark 34 (Special case when B\rightarrow 0 ) . For any finite N , choosing t_{0}=1 , and B\rightarrow 0 allows us to simplify the regret bound into \sqrt{(1+V_{T})(\log(1+V_{T})+2\log(1/\epsilon))}. where T is the first index such that t>\tau . The factor of 2 improvement on the constant in front of V_{T} is obtained by using the stronger bound in ( 57 ) by taking B\rightarrow 0 . This is slightly stronger than taking B\rightarrow 0 in ( 58 ) as stated in Theorem 6 (improved from \log(1+2V_{T}) to \log(1+V_{T}) ). Appendix G Improved bound with asymptotically tight constant. Theorem 35 (Improved bound) . Under the same assumptions, CP also satisfies a bound that improves the constant factor by \sqrt{2} as V_{T}\to\infty : \mathrm{Regret}_{\epsilon}(T)\leq\sqrt{(t_{0}+V_{T}+\iota B\sqrt{V_{T}})(\log(t_{0}+2V_{T})+2\log(1/\epsilon))} (58) where \iota:=144\max\left\{1,\log(t_{0}+2V_{T})+2\log N\right\}=\tilde{O}(1) . Proof. We can get a bound of the type \sqrt{\left(t_{0}+V_{T}+\tilde{O}(\sqrt{V_{T}})\right)\left(\log(t_{0}+V_{T})+2\log(1/\epsilon)\right)}. In the limit when V_{T}\rightarrow\infty or B\rightarrow 0 and \log(1/\epsilon)\gg\log(V_{T}) , then bound converges to the exact asymptotic limit (even for the leading constant) of \sqrt{2V_{T}\log(1/\epsilon)} . From ( 17 ) and our crude bound \Delta t\leq 2eB^{2} , we have \Delta t=\frac{e^{\Lambda}(t)}{1-e^{\Lambda}(t)\frac{2eB^{2}K(t)}{t}}\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]. This is of the form: \Delta t\leq\frac{1+\epsilon_{1}}{1-\epsilon_{2}}\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]. since \epsilon_{2}<1 we can move things around and obtain \frac{1-\epsilon_{2}}{1+\epsilon_{1}}\Delta t\leq\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}], which gives the following additive bound \Delta t\leq\mathbb{E}_{i\sim\mathbf{q}}[\Delta x_{i}^{2}]+\frac{\epsilon_{1}+\epsilon_{2}}{1+\epsilon_{1}}\Delta t, where the coefficient \frac{\epsilon_{1}+\epsilon_{2}}{1+\epsilon_{1}}\leq\frac{36B\sqrt{K(t)}}{\sqrt{t}} when we substitute the expression of \epsilon_{1} and \epsilon_{2} from above. It follows that \displaystyle t \displaystyle=t_{0}+\sum_{j=1}^{T}\Delta t_{j}=t_{0}+V_{T}+\sum_{j=1}^{T}\frac{36B\sqrt{K(t_{j})}\Delta t_{j}}{\sqrt{t_{j}}} \displaystyle\leq t_{0}+V_{T}+36B\sqrt{K(t)}\sum_{j=1}^{T}\frac{\Delta t_{j}}{\sqrt{\sum_{\ell=1}^{j-1}\Delta t_{\ell}}} \displaystyle\leq t_{0}+V_{T}+72B\sqrt{K(t)}\sqrt{1+\frac{2eB^{2}}{t_{0}}}\sqrt{2V_{T}} \displaystyle\leq t_{0}+V_{T}+144B\sqrt{K(t)}\sqrt{V_{T}}. (59) The second last line follows from the following lemma that bounds a shifted self-normalizing series in Lemma 36 , with the weak bound in ( 57 ) with a factor of 2 allows us to bound \sum_{j}\Delta t_{j}\leq 2V_{T} . The last line uses our assumption on t_{0}\geq 256e^{2}B^{2}K(t_{0})\geq 2eB^{2} . Recall that K(t)\leq\max\left\{1,\log(t_{0}+2V_{T})+2\log N\right\}=\tilde{O}(1). This proves the additive regret bound of the form \sqrt{(t_{0}+V_{T}+\iota\sqrt{V_{T}})(\log(t_{0}+2V_{T})+2\log(1/\epsilon))} where \iota:=144B\max\left\{1,\log(t_{0}+2V_{T})+2\log N\right\}=O(B(\log(t_{0}+V_{T})+\log N)) . This completes the proof for ( 58 ). ∎ Lemma 36 (Shifted self-normalizing bounds) . Let \Delta t_{1},\dots,\Delta t_{T}\geq 0 , let t_{0}>0 , and define t_{j}:=t_{0}+\sum_{i=1}^{j}\Delta t_{i}\qquad(j=1,\dots,T). Assume there exists M>0 such that \Delta_{j}\leq M for all j . Then \sum_{j=1}^{T}\frac{\Delta t_{j}}{\sqrt{t_{j-1}}}\;\leq\;2\sqrt{1+\frac{M}{t_{0}}}\;\bigl(\sqrt{t_{n}}-\sqrt{t_{0}}\bigr). Proof of Lemma 36 . Fix j\in\{1,\dots,T\} . Using t_{j}=t_{j-1}+\Delta t_{j} , \sqrt{t_{j}}-\sqrt{t_{j-1}}=\frac{t_{j}-t_{j-1}}{\sqrt{t_{j}}+\sqrt{t_{j-1}}}=\frac{\Delta t_{j}}{\sqrt{t_{j}}+\sqrt{t_{j-1}}}. Rearranging gives \Delta t_{j}=\bigl(\sqrt{t_{j}}-\sqrt{t_{j-1}}\bigr)\bigl(\sqrt{t_{j}}+\sqrt{t_{j-1}}\bigr), and therefore \frac{\Delta t_{j}}{\sqrt{t_{j-1}}}=\bigl(\sqrt{t_{j}}-\sqrt{t_{j-1}}\bigr)\,\frac{\sqrt{t_{j}}+\sqrt{t_{j-1}}}{\sqrt{t_{j-1}}}=\bigl(\sqrt{t_{j}}-\sqrt{t_{j-1}}\bigr)\,\left(1+\sqrt{\frac{t_{j}}{t_{j-1}}}\right). Next, \frac{t_{j}}{t_{j-1}}=1+\frac{\Delta t_{j}}{t_{j-1}}\leq 1+\frac{M}{t_{0}}, since t_{j-1}\geq t_{0} and \Delta t_{j}\leq M . Hence 1+\sqrt{\frac{t_{j}}{t_{j-1}}}\leq 1+\sqrt{1+\frac{M}{t_{0}}}\leq 2\sqrt{1+\frac{M}{t_{0}}}, where the last inequality uses 1\leq\sqrt{1+\frac{M}{t_{0}}} . Combining the previous displays, \frac{\Delta t_{j}}{\sqrt{t_{j-1}}}\leq 2\sqrt{1+\frac{M}{t_{0}}}\;\bigl(\sqrt{t_{j}}-\sqrt{t_{j-1}}\bigr). Summing over j=1,\dots,T and telescoping yields \sum_{j=1}^{T}\frac{\Delta t_{j}}{\sqrt{t_{j-1}}}\leq 2\sqrt{1+\frac{M}{t_{0}}}\;\sum_{j=1}^{n}\bigl(\sqrt{t_{j}}-\sqrt{t_{j-1}}\bigr)=2\sqrt{1+\frac{M}{t_{0}}}\;\bigl(\sqrt{t_{n}}-\sqrt{t_{0}}\bigr), as claimed. ∎ Appendix H Proof of Theorem 7 (Lower Bound) Our lower bound shows that Theorem 5 is near optimal for every such sequences of loss scales. After T iterations, expert i has loss \sum_{j=1}^{T}{\bm{\ell}}_{j,i} . Since the (\cdot)_{(\alpha N)} notation refers to the (\alpha N)^{\text{th}} largest value, the loss of the (\epsilon N)^{\text{th}} best expert is \big(\sum_{j=1}^{T}{\bm{\ell}}_{j}\big)_{((1-\epsilon)N)} . This leads to the bound \displaystyle\min_{\mathrm{Alg}}\max_{\bm{\ell}_{1:T}\in\prod_{j=1}^{T}\{\pm\sigma_{j}\}}\mathrm{Regret}_{\epsilon}(T) \displaystyle\geq \displaystyle\min_{\mathrm{Alg}}\mathbb{E}_{\bm{\ell}_{j}\sim\mathrm{Uniform}(\{-\sigma_{j},\sigma_{j}\})^{N}}\left[\mathrm{Regret}_{\epsilon}(T)\right] \displaystyle= \displaystyle\min_{\mathrm{Alg}}\mathbb{E}_{\bm{\ell}_{j}\sim\mathrm{Uniform}(\{-\sigma_{j},\sigma_{j}\})^{N}}\left[\sum_{j=1}^{T}\langle\bm{\ell}_{j},\bm{p}_{j}\rangle-\left[\sum_{j=1}^{T}\bm{\ell}_{j}\right]_{((1-\epsilon)N)}\right] \displaystyle= \displaystyle\min_{\mathrm{Alg}}\mathbb{E}_{\bm{\ell}_{j}\sim\mathrm{Uniform}(\{-\sigma_{j},\sigma_{j}\})^{N}}\left[\sum_{j=1}^{T}\langle\bm{\ell}_{j},\bm{p}_{j}\rangle\right]-\mathbb{E}_{\bm{\ell}_{j}\sim\mathrm{Uniform}(\{-\sigma_{j},\sigma_{j}\})^{N}}\left[\left[\sum_{j=1}^{T}\bm{\ell}_{j}\right]_{((1-\epsilon)N)}\right] Since the sequence \big(\sum_{j=1}^{T}\langle\bm{\ell}_{j},\bm{p}_{j}\rangle\big)_{t\geq 0} is a martingale, the first term disappears and we are left with \displaystyle= \displaystyle\mathbb{E}_{\bm{\ell}_{j}\sim\mathrm{Uniform}(\{-\sigma_{j},\sigma_{j}\})^{N}}\left[\left[\sum_{j=1}^{T}\bm{\ell}_{j}\right]_{(N\epsilon)}\right] since the distribution on \sum_{j=1}^{T}{\bm{\ell}}_{j} is symmetric. Define \epsilon_{0}=e^{-23} . We will show that for any \epsilon\in(0,\epsilon_{0}) , with T=T(\epsilon) as in ( 62 ) and N=N(\epsilon) as in ( 72 ), \mathbb{E}_{\bm{\ell}_{j}\sim\mathrm{Uniform}(\{-\sigma_{j},\sigma_{j}\})^{N}}\left[\left[\sum_{j=1}^{T}\bm{\ell}_{j}\right]_{(N\epsilon)}\right]~\geq~2Q\Big(\sqrt{2\log{\textstyle\frac{1}{\epsilon}}}-6\Big), which proves the theorem. For each coordinate i\in[N] , define X_{i}:=\sum_{j=1}^{T}\ell_{j,i}, where \ell_{j,i}\in\{-\sigma_{j},\sigma_{j}\} . By construction, \{X_{i}\}_{i=1}^{N} are independent and satisfy E[X_{i}]=0 . Our main objective is to prove that \mathbb{E}\!\left[X_{(N\epsilon)}\right]=\Omega(Q\sqrt{\log(1/\epsilon)}) , which we will do in ( 68 ) and ( 73 ). Throughout this section, let \Phi and \phi denote the cumulative distribution function and probability density function of a standard normal random variable, respectively. For convenience, define Q:=\frac{1}{2}\sqrt{\sum_{j=1}^{T}\sigma_{j}^{2}} . We then have the following lemma. Lemma 37 . Fix any i\in[N] . Let X_{i} be defined as above, where \{\ell_{j,i}\}_{j=1}^{T} are independent, mean-zero random variables satisfying \Pr(\ell_{j,i}=\sigma_{j})=\Pr(\ell_{j,i}=-\sigma_{j})=1/2 . Recall that \Phi denotes the cumulative distribution function of a standard normal random variable. Then there exists an absolute constant 00 , \Pr[X_{i}\leq-s]\leq\exp\left(-\frac{s^{2}}{2\sum_{j=1}^{T}\sigma_{j}^{2}}\right)=\exp\left(-s^{2}/(8Q^{2})\right). Combining the above bounds with the definition of L(\alpha) , we obtain \Pr[X_{i}\leq L(\alpha)]\leq 1-\epsilon-\alpha. ∎ Theorem 39 . Let X_{1},\ldots,X_{N} be independent random variables that satisfy ( 64 ). Then, there exists g(\alpha)=\begin{cases}\exp(-2\alpha^{2}N)~&\text{if $\alpha\in[0,1-2(\epsilon+\delta))$},\\ (2(1-\epsilon-\alpha))^{N/8}~&\text{if $\alpha\in[1-2(\epsilon+\delta),1-\epsilon)$}.\end{cases} (65) such that for all 0\leq\alpha<1-\epsilon , letting L(\alpha) be as defined in Lemma 38 , we have \Pr[\,X_{(N\epsilon)}\!\leq\!L(\alpha)\,]~\leq~g(\alpha). Proof. Let Z=\sum_{i=1}^{N}\mathbf{1}_{X_{i}\leq L} . The event of interest may be restated as follows. \displaystyle\left\{\>X_{(N\epsilon)}\!\leq\!L(\alpha)\>\right\}~=~\left\{\>\lvert\left\{\;i\in[N]\,:\,X_{i}\leq L(\alpha)\;\right\}\rvert\geq N-\left\lfloor N\epsilon\right\rfloor\>\right\}~=~\left\{\>Z\geq N-\left\lfloor N\epsilon\right\rfloor\>\right\} Define \mu=N(1-\epsilon-\alpha) . By ( 64 ), \Pr[X_{i}\leq L(\alpha)]\leq 1-\epsilon-\alpha , so \mathbb{E}[Z]~\leq~\mu . By a Hoeffding bound, we have \displaystyle\operatorname{Pr}\left[\,Z\geq N-\left\lfloor N\epsilon\right\rfloor\,\right]~\leq~\operatorname{Pr}\left[\,Z\geq(1-\epsilon)N\,\right]~\leq~\operatorname{Pr}\left[\,Z\geq\mu+\alpha N\,\right]~\leq~\exp(-2\alpha^{2}N). This bound is valid for all \alpha , but loose as \alpha\rightarrow 1-\epsilon . Let us now focus on the case \alpha\geq 1-2(\epsilon+\delta) . We will use a Chernoff bound, stated in the form \Pr[Z\geq(1+\beta)\mu]~\leq~\exp\big(-(1+\beta)\ln(1+\beta)\mu/4\big)\qquad\forall\beta\geq 1. We will apply this with \beta=\frac{\alpha N}{\mu}=\frac{\alpha}{1-\epsilon-\alpha}>\frac{1-(2\epsilon+\delta)}{\epsilon+2\delta}\geq\frac{1}{\epsilon+2\delta}-2\geq 1, (66) since \epsilon+2\delta\leq 1/4 . Observe that \alpha>1-2(\epsilon+\delta)\geq 1/2 , since \epsilon+\delta\leq 1/4 . This yields \displaystyle\operatorname{Pr}\left[\,Z\geq N-\left\lfloor N\epsilon\right\rfloor\,\right] \displaystyle~\leq~\Pr[Z\geq\mu+\alpha N] \displaystyle~=~\operatorname{Pr}\left[\,Z\geq(1+\beta)\mu\,\right] \displaystyle~\leq~\exp\big(-\beta\ln(\beta)\mu/4\big) (Chernoff bound) \displaystyle~=~(1/\beta)^{\beta\mu/4}~=~(1/\beta)^{\alpha N/4} (definition of \beta ) \displaystyle~\leq~(1/\beta)^{N/8} (since \beta\geq 1 and \alpha\geq 1/2 ) \displaystyle~=~\Big(\frac{1-\epsilon-\alpha}{\alpha}\Big)^{N/8} (by ( 66 )) \displaystyle~\leq~\Big(2(1-\epsilon-\alpha)\Big)^{N/8} (since \alpha\geq 1/2 ). ∎ Lemma 40 . Suppose that M is a random variable satisfying \operatorname{Pr}\left[\,M\ln(1/\epsilon_{0})=23 . H.2 Bound on the integrals We now rescale the integrals in ( 68 ) appropriately, then separately prove that \displaystyle\frac{1}{2Q}\int_{0}^{\frac{1}{2}-(\epsilon+\delta)}g(\alpha)(-L^{\prime}(\alpha))d\alpha \displaystyle~\leq~1 \displaystyle\frac{1}{4Q}\int_{\frac{1}{2}-(\epsilon+\delta)}^{1-2(\epsilon+\delta)}g(\alpha)(-L^{\prime}(\alpha))d\alpha \displaystyle~\leq~1 \displaystyle\frac{1}{\sqrt{2}Q}\int_{1-2(\epsilon+\delta)}^{1-\epsilon}g(\alpha)(-L^{\prime}(\alpha))d\alpha\Big\} \displaystyle~\leq~1. Recall that \Phi and \phi denote the cumulative distribution function and probability density function of a standard normal random variable, respectively. We will require the inequality \displaystyle\frac{1}{\phi(\Phi^{-1}(x))}\leq\frac{1}{c_{1}x\sqrt{\log(1/x)}}\qquad\forall x\in(0,\tfrac{1}{2}], (70) where \displaystyle c_{1}:=\sqrt{\tfrac{1}{2}}. This follows from Lemma 41 . First integral. It suffices to upper bound \int_{0}^{\frac{1}{2}-(\epsilon+\delta)}\frac{g(\alpha)}{\phi(\Phi^{-1}(1-(\epsilon+\delta)-\alpha))}\,d\alpha,\qquad g(\alpha)=\exp(-2N\alpha^{2}). Observe that for \alpha\in\bigl[0,\tfrac{1}{2}-(\epsilon+\delta)\bigr) we have (\epsilon+\delta)+\alpha\leq\tfrac{1}{2} . Let \Phi and \phi denote the standard normal distribution function and density, respectively. Using the identity \Phi^{-1}(1-u)=-\Phi^{-1}(u) for u\in(0,1) and the evenness of \phi , we obtain \phi(\Phi^{-1}(1-(\epsilon+\delta)-\alpha))=\phi(\Phi^{-1}((\epsilon+\delta)+\alpha)). (71) Combining ( 71 ), ( 70 ), and the definition g(\alpha)=e^{-2N\alpha^{2}} , we obtain \displaystyle\int_{0}^{\frac{1}{2}-(\epsilon+\delta)}\frac{g(\alpha)}{\phi(\Phi^{-1}(1-(\epsilon+\delta)-\alpha))}\,d\alpha \displaystyle=\int_{0}^{\frac{1}{2}-(\epsilon+\delta)}\frac{g(\alpha)}{\phi(\Phi^{-1}((\epsilon+\delta)+\alpha))}\,d\alpha \displaystyle\leq\int_{0}^{\frac{1}{2}-(\epsilon+\delta)}\frac{\exp(-2N\alpha^{2})}{c_{1}\,((\epsilon+\delta)+\alpha)\sqrt{\log\!\frac{1}{(\epsilon+\delta)+\alpha}}}\,d\alpha. Since (\epsilon+\delta)+\alpha\geq\epsilon+\delta and (\epsilon+\delta)+\alpha\leq\frac{1}{2} on the integration range, we have \log\!\bigl(1/((\epsilon+\delta)+\alpha)\bigr)\geq\log 2 , hence \displaystyle\int_{0}^{\frac{1}{2}-(\epsilon+\delta)}\frac{\exp(-2N\alpha^{2})}{c_{1}\,((\epsilon+\delta)+\alpha)\sqrt{\log\!\frac{1}{(\epsilon+\delta)+\alpha}}}\,d\alpha \displaystyle\leq\frac{1}{c_{1}(\epsilon+\delta)\sqrt{\log 2}}\int_{0}^{\frac{1}{2}-(\epsilon+\delta)}\exp(-2N\alpha^{2})\,d\alpha \displaystyle=\frac{1}{c_{1}(\epsilon+\delta)\sqrt{\log 2}}\cdot\frac{\sqrt{\pi}}{2\sqrt{2N}}\,\mathrm{erf}\!\left(\sqrt{2N}\Bigl(\tfrac{1}{2}-(\epsilon+\delta)\Bigr)\right) \displaystyle\leq\frac{1}{c_{1}(\epsilon+\delta)}\cdot\frac{1}{\sqrt{N}}, where we used \mathrm{erf}(x)\leq 1 . Consequently, it suffices to assume N\geq(c_{1}(\epsilon+\delta))^{-2} to ensure that the above bound is at most 1 . Second integral. It suffices to upper bound \int_{\frac{1}{2}-(\epsilon+\delta)}^{1-2(\epsilon+\delta)}\frac{g(\alpha)}{\phi(\Phi^{-1}(1-(\epsilon+\delta)-\alpha))}\,d\alpha,\qquad g(\alpha)=\exp(-2N\alpha^{2}). Observe that for \alpha\in\bigl[\tfrac{1}{2}-(\epsilon+\delta),\,1-2(\epsilon+\delta)\bigr] we have 1-(\epsilon+\delta)-\alpha\leq\frac{1}{2} . Combining ( 70 ) with g(\alpha)=\exp(-2N\alpha^{2}) yields \int_{\frac{1}{2}-(\epsilon+\delta)}^{1-2(\epsilon+\delta)}\frac{g(\alpha)}{\phi(\Phi^{-1}(1-(\epsilon+\delta)-\alpha))}d\alpha\leq\int_{\frac{1}{2}-(\epsilon+\delta)}^{1-2(\epsilon+\delta)}\frac{\exp(-2N\alpha^{2})}{c_{1}\,(1-(\epsilon+\delta)-\alpha)\sqrt{\log\frac{1}{1-(\epsilon+\delta)-\alpha)}}}d\alpha. With the change of variables x=1-(\epsilon+\delta)-\alpha (so dx=-d\alpha ), this becomes \int_{\frac{1}{2}-(\epsilon+\delta)}^{1-2(\epsilon+\delta)}\frac{\exp(-2N\alpha^{2})}{c_{1}\,(1-(\epsilon+\delta)-\alpha)\sqrt{\log\frac{1}{1-(\epsilon+\delta)-\alpha)}}}d\alpha=\int_{\epsilon+\delta}^{1/2}\frac{\exp\!\bigl(-2N(1-(\epsilon+\delta)-x)^{2}\bigr)}{c_{1}\,x\sqrt{\log(1/x)}}\,dx. Since \epsilon+\delta\leq\tfrac{1}{4} , so that the function f(x):=1\big/\!\bigl(x\sqrt{\log(1/x)}\bigr) is decreasing on x\in[(\epsilon+\delta),1/2] . Hence \displaystyle\int_{\epsilon+\delta}^{1/2}\frac{\exp\!\bigl(-2N(1-(\epsilon+\delta)-x)^{2}\bigr)}{c_{1}\,x\sqrt{\log(1/x)}}\,dx \displaystyle\leq\frac{1}{c_{1}(\epsilon+\delta)\sqrt{\log\!\bigl(1/(\epsilon+\delta)\bigr)}}\int_{\epsilon+\delta}^{1/2}\exp\!\bigl(-2N(1-(\epsilon+\delta)-x)^{2}\bigr)\,dx \displaystyle=\frac{1}{c_{1}(\epsilon+\delta)\sqrt{\log\frac{1}{(\epsilon+\delta)}}}\frac{\sqrt{\pi}}{2\sqrt{2N}} \displaystyle\quad\cdot\left[-\mathrm{erf}\left[(2(\epsilon+\delta)-1)\sqrt{2N}\right]+\mathrm{erf}\left(\frac{(2(\epsilon+\delta)-1)\sqrt{2N}}{2}\right)\right] \displaystyle\leq\frac{\sqrt{\pi}}{c_{1}(\epsilon+\delta)\sqrt{2\log\frac{1}{(\epsilon+\delta)}}}\frac{1}{\sqrt{N}} \displaystyle\leq\frac{\sqrt{\pi}}{c_{1}(\epsilon+\delta)}\frac{1}{\sqrt{N}}, where we used |\mathrm{erf}(t)|\leq 1 and \epsilon+\delta\leq 1/4 . Consequently, it suffices to assume N\geq(c_{1}(\epsilon+\delta))^{-2}/\pi to make the above bound at most 1 . Third integral. It suffices to upper bound \int_{1-2(\epsilon+\delta)}^{1-\epsilon}\frac{g(\alpha)}{\sqrt{\log\frac{1}{1-\epsilon-\alpha}}(1-\epsilon-\alpha)}d\alpha,\qquad g(\alpha)=(2(1-\epsilon-\alpha))^{N/8}. Recall that \epsilon+2\delta\leq\tfrac{1}{2} . Set \gamma:=1-\epsilon-\alpha . Then d\gamma=-d\alpha , and the limits \alpha\in[1-2(\epsilon+\delta),\,1-\epsilon] correspond to \gamma\in[0,\,\epsilon+2\delta] . Hence \displaystyle\int_{1-2(\epsilon+\delta)}^{1-\epsilon}\frac{(2(1-\epsilon-\alpha))^{N/8}}{(1-\epsilon-\alpha)\sqrt{\log\!\bigl(1/(1-\epsilon-\alpha)\bigr)}}\,d\alpha \displaystyle=\int_{0}^{\epsilon+2\delta}\frac{(2\gamma)^{N/8}}{\gamma\sqrt{\log(1/\gamma)}}\,d\gamma. Since \gamma\leq\epsilon+2\delta\leq\tfrac{1}{2} on the integration range, we have \log(1/\gamma)\geq\log 2 , and therefore \displaystyle\int_{0}^{\epsilon+2\delta}\frac{(2\gamma)^{N/8}}{\gamma\sqrt{\log(1/\gamma)}}\,d\gamma \displaystyle\leq\frac{2^{N/8}}{\sqrt{\log 2}}\int_{0}^{\epsilon+2\delta}\gamma^{N/8-1}\,d\gamma \displaystyle=\frac{2^{N/8}}{\sqrt{\log 2}}\cdot\frac{8}{N}\,(\epsilon+2\delta)^{N/8}=\frac{8}{N\sqrt{\log 2}}\,[2(\epsilon+2\delta)]^{N/8}. Using 2(\epsilon+2\delta)\leq 1 and by selecting N\geq 8 , we obtain the simpler bound \int_{1-2(\epsilon+\delta)}^{1-\epsilon}\frac{(2(1-\epsilon-\alpha))^{N/8}}{(1-\epsilon-\alpha)\sqrt{\log\!\bigl(1/(1-\epsilon-\alpha)\bigr)}}\,d\alpha\leq\frac{8}{N\sqrt{\log 2}}\leq\frac{16}{N}. Consequently, it suffices to take N\geq 16 to make this bound at most 1 . H.3 Combination Let N(\epsilon)\in\mathbb{N} satisfy N(\epsilon)\geq\max\{(c_{1}(\epsilon+\delta))^{-2},(c_{1}(\epsilon+\delta))^{-2}/\pi,16\}. (72) Then with T=T(\epsilon) as in ( 62 ) and N=N(\epsilon) as in ( 72 ), the integrals in ( 68 ) contribute \displaystyle-\int_{0}^{\frac{1}{2}-(\epsilon+\delta)}g(\alpha)(-L^{\prime}(\alpha))d\alpha-\int_{\frac{1}{2}-(\epsilon+\delta)}^{1-2(\epsilon+\delta)}g(\alpha)(-L^{\prime}(\alpha))d\alpha-\int_{1-2(\epsilon+\delta)}^{1-\epsilon}g(\alpha)(-L^{\prime}(\alpha))d\alpha \displaystyle~\geq~ \displaystyle-2Q-4Q-\sqrt{2}Q. Combining this with our lower bound on L(0) from ( 69 ), we get \mathbb{E}\!\left[X_{(N\epsilon)}\right]~\geq~2Q\Big(\sqrt{2\ln(1/\epsilon)}-2-1-2-\frac{1}{\sqrt{2}}\Big). (73) This completes the proof of Theorem 7 . H.4 Bounds on Gaussians The following fact appears in the literature. See, e.g., 6 , in the proof of Proposition 4.1. Lemma 41 . Let \Phi and \phi denote the standard normal distribution function and density. Then, for all x\in(0,1/2] , x\sqrt{(1/2)\log(1/x)}\;\leq\;\phi\left(\Phi^{-1}(x)\right). We will prove the following bound on the inverse of the Gaussian cumulative distribution function. The multiplicative constant \sqrt{2} here is tight. Lemma 42 . Let \Phi be the cumulative distribution function of the standard Gaussian distribution. For \zeta\in(0,\epsilon_{0}] , where \epsilon_{0}=e^{-23} , we have \displaystyle\Phi^{-1}(1-\zeta) \displaystyle~\geq~\sqrt{2\ln(1/\zeta)}-\sqrt{2} (additive error) (74) \displaystyle~\geq~\sqrt{\ln(1/\zeta)} \displaystyle\qquad\text{\rm(multiplicative error)}. (75) To prove this, we will use the function h(\zeta)=\sqrt{2\ln(1/\zeta)-2\ln\ln(1/\zeta)}. Proposition 43 . h(\zeta)\geq\sqrt{2\ln(1/\zeta)}-\sqrt{2} . Proof. We apply the identity \sqrt{a}-\sqrt{a-b}=b/\big(\sqrt{a}+\sqrt{a-b}) , which is valid for all 0\leq b0. See [ 14 , Theorem 1.2.6] . For x\geq 2 we have 1-x^{-2}\geq 3/4 , so and thus 1-\Phi(x)~\geq~\underbrace{\frac{1}{\sqrt{2\pi}}\frac{3}{4}}_{=\kappa}x^{-1}\exp(-x^{2}/2)\qquad\forall x\geq 2. Since h(\zeta)\geq 2 by Proposition 44 , we may take x=h(\zeta) . Thus, it suffices to prove that \kappa\cdot\big(h(\zeta)\big)^{-1}\cdot\exp(-h(\zeta)^{2}/2)~\geq~\zeta. Taking the log, this is equivalent to \ln\kappa-\ln\big(h(\zeta)\big)-\frac{h(\zeta)^{2}}{2}~\geq~\ln(\zeta) This holds due to Proposition 45 . To prove ( 75 ), we simply rearrange to obtain the equivalent statements \displaystyle\big(\sqrt{2}-1\big)\sqrt{\ln(1/\zeta)} \displaystyle~\geq~\sqrt{2} \displaystyle\ln(1/\zeta) \displaystyle~\geq~\Big(\frac{\sqrt{2}}{\sqrt{2}-1}\Big)^{2} The last inequality holds because \Big(\frac{\sqrt{2}}{\sqrt{2}-1}\Big)^{2}<12 whereas \ln(1/\zeta)\geq\ln(1/\epsilon_{0})=23 . ∎ Appendix I Further discussion on the 28 In this appendix, we discuss the work of 28 and how it does not contradict with our results. This section is unimportant for general readers, but could be helpful for readers who are interested in how the construction of 28 works and why it may indicate that the \log N factor in t_{0} from our Theorem 6 might be necessary. Section I.1 and I.2 explain how the model-selection problem in contextual bandits can be reduced to full-information learning from experts, and how that implies a hardness result on the adaptivity to \epsilon in quantile regret bounds. Section I.3 inspects whether the construction can be generalized to cover variances and second moments defined by a different distribution q\neq p . The conclusion is negative in general, and we pinpoint the underlying reason — the variance of the importance weighting estimator blows up when q\neq p . Section I.4 shows that the construction of 28 does not rule out regret bounds proportional to \sqrt{(V_{T}+\log N)\log(1/\epsilon)}, i.e., the kind of bound we obtain by NormalHedge.BH — even if V_{T} is defined with q=p . I.1 Model Selection in Contextual Bandits and the Wrapper Reduction This section summarizes the construction and lower bound underlying Theorem 4 of 28 as well as the wrapper argument (Appendix B.4) that converts an experts guarantee into a contextual bandit guarantee. We emphasize the mechanism by which a contradiction arises when variance is measured with respect to the learner’s own distribution. I.1.1 The model selection construction Theorem 4 concerns the difficulty of model selection in contextual bandits. The goal is to design a single proper algorithm that competes simultaneously with two nested policy classes \Pi_{1}\subset\Pi_{2}, where \Pi_{1} is small and \Pi_{2} is much larger. The construction uses K=3 actions and defines \Pi_{2}=\{\pi_{0},\pi_{1},\dots,\pi_{k}\},\qquad\Pi_{1}=\{\pi_{0}\}, for a large integer k . A family of stochastic contextual bandit environments \{E_{i^{*}}\}_{i^{*}=1}^{k} is constructed with the following properties: • In environment E_{i^{*}} , policy \pi_{i^{*}} is uniquely optimal, while all other policies incur a small additional loss \Delta . • Distinguishing which environment E_{i^{*}} is in force requires significant exploration. • Excessive exploration causes regret relative to \Pi_{1} , while insufficient exploration prevents identifying the optimal policy in \Pi_{2} . This creates an unavoidable tradeoff between regret with respect to \Pi_{1} and regret with respect to \Pi_{2} . I.1.2 Theorem 4 28 : a model selection lower bound Theorem 4 formalizes this tradeoff. Theorem 46 (Model selection lower bound 28 ) . There exist constants c_{2}>0 and policy classes \Pi_{1}\subset\Pi_{2} such that the following holds. For any proper contextual bandit algorithm, if for any parameter C \mathrm{Regret}(T,\Pi_{1})\leq C\sqrt{T}\quad\text{for all environments}, then there exists an environment \mathbb{E}_{i^{*}} for which \mathrm{Regret}(T,\Pi_{2})\;\geq\;\Omega\!\left(\min\left\{T,\frac{\log|\Pi_{2}|}{C}\sqrt{T}\right\}\right), provided the policy class size satisfies c_{2}C^{2}\leq\log|\Pi_{2}|\leq T/2 . The theorem shows that no single proper algorithm can achieve near-optimal regret guarantees for both \Pi_{1} and \Pi_{2} when |\Pi_{2}| is sufficiently large. This is due to the following construction: \pi_{0} only choose action 3 with a constant loss of 1/2-\Delta/4 . In environment \mathcal{E}_{0} , \pi_{i} for all i=1,...,k gives 1/2 expected loss, with Bernoulli samples when choosing Action 1 and the loss of Action 2 is 1- the loss of Action 1. In environment \mathcal{E}_{i} for each i=1,...,k , \pi_{i} is slightly better in the sense that it has an expected loss of \frac{1}{2}(1-\Delta) . They show that the environment \mathcal{E}_{1:k} and \mathcal{E}_{0} are indistinguishable unless we call policy \pi_{1:k} O(\log k/\Delta^{2}) times. However, if we call the “reveal” policy too many times, then it misses the best arm in \mathcal{E}_{0} and incur regret proportional to \Delta . I.1.3 The wrapper reduction We describe the wrapper reduction of Appendix B.4, which converts a full-information experts algorithm into a proper contextual bandit algorithm. A key technical step is the duplication of policies in order to apply a quantile experts guarantee. Experts representation and duplication. Each policy \pi\in\Pi_{2} is treated as an expert. To compete with a single policy \pi_{0}\in\Pi_{1} using a quantile regret bound, the experts instance is augmented by duplicating \pi_{0} multiple times. Concretely, let \Pi_{2}=\{\pi_{0},\pi_{1},\dots,\pi_{k}\} . We construct a multiset of experts \widetilde{\Pi}_{2}=\{\underbrace{\pi_{0},\dots,\pi_{0}}_{k\ \text{copies}},\pi_{1},\dots,\pi_{k}\}, where each copy of \pi_{0} behaves identically and incurs the same loss at every round. The experts algorithm is run on \widetilde{\Pi}_{2} . This duplication ensures that \pi_{0} constitutes a constant fraction of the expert pool. In particular, \pi_{0} belongs to the best half of experts, so the quantile regret guarantee with parameter \varepsilon_{1}=1/2 applies. Experts distribution. At round t , the experts algorithm outputs a distribution p_{t} over \widetilde{\Pi}_{2} . All copies of \pi_{0} are interchangeable; we abuse notation and write p_{t}(\pi_{0}) for their total mass. Action selection. Given context x_{t} , define the action distribution q_{t}(a\mid x_{t})=\frac{\gamma}{3}+(1-\gamma)\sum_{\pi\in\widetilde{\Pi}_{2}:\,\pi(x_{t})=a}p_{t}(\pi),\qquad a\in\{1,2,3\} where \gamma\in(0,1) is the exploration parameter. The wrapper samples an action A_{t}\sim q_{t}(\cdot\mid x_{t}) and observes the bandit loss \ell_{t,A_{t}} . Importance-weighted loss estimator. For each expert \pi\in\widetilde{\Pi}_{2} , define the IPS estimator \widehat{\ell}_{t}(\pi)=\frac{\mathbf{1}\{\pi(x_{t})=A_{t}\}}{q_{t}(A_{t}\mid x_{t})}\,\ell_{t,A_{t}}. This estimator is unbiased for the true loss \ell_{t,\pi(x_{t})} . To ensure bounded losses, define the scaled loss \tilde{\ell}_{t}(\pi)=\frac{\gamma}{3}\,\widehat{\ell}_{t}(\pi)\in[0,1], and feed the full vector \tilde{\ell}_{t} to the experts algorithm. Regret decomposition. Let \varepsilon_{1}=1/2 and \varepsilon_{2}=1/(2|\Pi_{2}|) . The wrapper satisfies the following regret bounds: \mathrm{Regret}(T,\Pi_{m})\;\leq\;\gamma T\;+\;\frac{3(1-\gamma)}{\gamma}\,\mathrm{Regret}^{\mathrm{exp}}_{\varepsilon_{m}}(T;\tilde{\ell}),\qquad m\in\{1,2\}. where the \gamma T is due to the probability spent in exploration and the second term uses the regret of the full-information online learner (dividing that \gamma/3 normalization factor). For \Pi_{1} , the duplication of \pi_{0} ensures that \pi_{0} lies in the top \varepsilon_{1} -fraction of experts, so the quantile regret bound implies regret with respect to \pi_{0} . For \Pi_{2} , the duplication only doubles the number of policies so needed and \varepsilon_{2}=1/2k corresponds to competing with the single best policy in \Pi_{2} . The two (contextual bandits) regret upper bounds above allow us to inspect different kinds of regret bounds for full-information online learner and see if it results in a contradiction with Theorem 46 . This is how the Theorem 6 of 28 works. I.2 How the contradiction arises when r_{t}=p_{t} We briefly recall the key argument from Appendix B.4 of 28 (the proof of Theorem 6 of 28 ) showing that a second-order experts bound with variance measured under the learner’s own distribution leads to a contradiction with Theorem 46 . I.2.1 The experts assumption used in the paper The paper assumes the existence of a full-information experts algorithm satisfying the following second-order quantile bound. Assumption 47 (Second-order experts bound with self-variance) . There exists a constant G>0 such that for every loss sequence \ell_{t,i}\in[0,1] and every \varepsilon\in(0,1) , \mathrm{Regret}^{\mathrm{exp}}_{\varepsilon}(T)\;\leq\;G\sqrt{\Bigl(\sum_{t=1}^{T}\mathrm{Var}_{i\sim p_{t}}(\ell_{t,i})\Bigr)\ln(1/\varepsilon)}, where p_{t} is the distribution played by the algorithm at round t . The crucial feature is that the variance is taken with respect to the learner’s own randomization. I.2.2 Key variance identity when r_{t}=p_{t} The critical technical step is that, when the variance is taken under the learner’s own distribution p_{t} , the IPS estimator satisfies \mathbb{E}\!\left[\mathrm{Var}_{\pi\sim p_{t}}(\tilde{\ell}_{t,\pi})\right]\;\leq\;\frac{\gamma^{2}}{3}. As a result, \mathbb{E}\!\left[\sum_{t=1}^{T}\mathrm{Var}_{\pi\sim p_{t}}(\tilde{\ell}_{t,\pi})\right]\;\leq\;\frac{\gamma^{2}T}{3}. This quadratic dependence on \gamma is the decisive difference from the arbitrary- r_{t} case that we will talk about in Section I.3 . I.2.3 Consequences for the wrapper bounds Applying Assumption 47 and (SV): Regret to \Pi_{1} . \mathrm{Regret}(T,\Pi_{1})\;\leq\;\gamma T+O\!\left(\frac{1}{\gamma}\sqrt{\gamma^{2}T}\right)=O(\gamma T+\sqrt{T}). Regret to \Pi_{2} . Let k=|\Pi_{2}|-1 . Then \mathrm{Regret}(T,\Pi_{2})\;\leq\;\gamma T\;+\;O\!\left(\frac{1}{\gamma}\sqrt{\gamma^{2}T\ln k}\right)=O(\gamma T+\sqrt{T\ln k}). Crucially, the \sqrt{\ln k} term is not multiplied by any power of 1/\gamma . I.2.4 Choosing \gamma and deriving the contradiction Set \gamma=T^{-1/3} . Then: \mathrm{Regret}(T,\Pi_{1})=O(T^{2/3}),\qquad\mathrm{Regret}(T,\Pi_{2})=O(T^{2/3}+\sqrt{T\ln k}). Thus the Theorem 46 parameter satisfies C\asymp T^{1/6} . Theorem 46 then implies the existence of an environment such that \mathrm{Regret}(T,\Pi_{2})\;\geq\;\Omega\!\left(\frac{\ln k}{C}\sqrt{T}\wedge T\right)=\Omega\!\left(\ln k\cdot T^{1/3}\right). Choosing \ln k\asymp T^{1/2} yields \Omega(T^{5/6})\;\leq\;\mathrm{Regret}(T,\Pi_{2})\;\leq\;O(T^{3/4}), which is a contradiction for large T . In fact the claim of 28 is even stronger in the sense that the second-order quantile regret bound with self-variance not possible for any variance O(T^{\alpha}) with any \alpha<1 . This can be obtained by choosing \gamma=T^{-1/2+\alpha/2} for any 0<\alpha<1 then the \sum_{t}\mathrm{Var}_{p_{t}}=O(\gamma^{2}T)=O(T^{\alpha}) , which gives \mathrm{Regret}(T,\Pi_{1})=O(T^{1/2+\alpha/2}),\qquad\mathrm{Regret}(T,\Pi_{2})=O(T^{1/2+\alpha/2}+\sqrt{T\ln k}). Then Theorem 46 ’s parameter is C\asymp T^{\alpha/2} and that \mathrm{Regret}(T,\Pi_{2})\;\geq\;\Omega\!\left(\frac{\ln k}{C}\sqrt{T}\wedge T\right)=\Omega\!\left(\ln k\cdot T^{1/2-\alpha/2}\right). Choosing \ln k=\Theta(T^{\alpha+\delta}) for a small \delta>1 implies that \mathrm{Regret}(T,\Pi_{2})=\Omega(T^{(1+\alpha+2\delta)/2} and \mathrm{Regret}(T,\Pi_{2})=O(T^{(1+\alpha+\delta)/2}) at the same time, thus giving rise to a contradiction. I.3 The argument may fail when the variance is w.r.t. a different distribution We consider the following strengthened experts hypothesis. Assumption 48 (Second-order experts bound with general variance) . There exists a constant G>0 such that for every full-information experts game with losses \ell_{t,i}\in[0,1] the algorithm can output both a sequence of decisions (p_{t})_{t=1}^{T} a sequence of distributions (r_{t})_{t=1}^{T} over experts, such that for every \varepsilon\in(0,1) , the algorithm satisfies \mathrm{Regret}^{\mathrm{exp}}_{\varepsilon}(T)\;\leq\;G\sqrt{\Bigl(\sum_{t=1}^{T}\mathrm{Var}_{i\sim r_{t}}(\ell_{t,i})\Bigr)\ln(1/\varepsilon)}. This is a generalization of the hypothesis in ( 47 ) that requires r_{t}=p_{t} . We ask whether Assumption 48 contradicts the contextual bandit lower bound of Theorem 46 via the proper wrapper reduction of Appendix B.4. I.3.1 Step 1: The wrapper and the variance bound We apply the same wrapper that runs the experts algorithm on scaled IPS losses. A key difference from the original proof is that the experts hypothesis controls variance with respect to arbitrary distributions r_{t} , not the learner’s own distribution. In this case the best bound one can show is \mathbb{E}\!\left[\sum_{t=1}^{T}\mathrm{Var}_{\pi\sim r_{t}}(\tilde{\ell}_{t,\pi})\right]\;\leq\;\frac{\gamma T}{3}. Only a single factor of \gamma is recovered. The bound cannot be improved beyond a constant factor because if we take r_{t} to be such that we get a uniform distribution of the three actions, which gives a variance of \gamma^{2} every time the action with non-trivial reward is chosen. I.3.2 Step 2: Upper bounds from the experts hypothesis and the resulting lower bound Using the standard wrapper decomposition, one obtains the following bounds. Regret to \Pi_{1} . Let \varepsilon=1/2 . Assumption 48 and (V) imply \mathbb{E}[\mathrm{Regret}(T,\Pi_{1})]\;\leq\;\gamma T+A\sqrt{\frac{T}{\gamma}},\qquad A=3G\sqrt{\frac{\ln 2}{3}}. Equivalently, \mathrm{Regret}(T,\Pi_{1})\;\leq\;C(\gamma)\sqrt{T},\qquad C(\gamma):=\gamma\sqrt{T}+\frac{A}{\sqrt{\gamma}}. (76) Regret to \Pi_{2} . Let k=|\Pi_{2}|-1 and \varepsilon=1/(2k) . Then \mathbb{E}[\mathrm{Regret}(T,\Pi_{2})]\;\leq\;\gamma T+B\sqrt{\frac{T}{\gamma}}\sqrt{\ln(2k)},\qquad B=\sqrt{3}\,G. (77) From Theorem 46 (Theorem 4 in 28 ) we have that \Delta=\min\!\left\{\frac{c_{1}\ln k}{C(\gamma)\sqrt{T}},\frac{1}{4}\right\},\qquad c_{1}=\frac{1}{160}, there exists an environment such that \mathrm{Regret}(T,\Pi_{2})\;\geq\;\frac{\Delta T}{32}=\min\!\left\{\frac{c_{1}\ln k}{32C(\gamma)}\sqrt{T},\;\frac{T}{128}\right\}. (78) The proof further assumes the regime c_{2}C(\gamma)^{2}\;\leq\;\ln k\;\leq\;\frac{T}{2}. I.3.3 Step 4: Where a contradiction would need to occur To obtain a contradiction with Theorem 46 , we would need to choose \gamma\in(0,1) and k such that the lower bound ( 78 ) exceeds the upper bound ( 77 ). Throughout this section we write L:=\ln k and note that \ln(2k)\asymp L up to additive constants, which we ignore for readability. We consider separately the two regimes \gammaT^{-1/3} . The intuition is that T^{-1/3} is precisely the scale at which the two terms \gamma\sqrt{T} and A/\sqrt{\gamma} in C(\gamma) balance. When \gamma\gamma T , A/\sqrt{\gamma}\leq C(\gamma)\leq 2A/\sqrt{\gamma} and the upper and lower bounds of \mathrm{Regret}(T,\Pi_{2}) gives L\sqrt{T\gamma}\lesssim\mathrm{Regret}(T,\Pi_{2})\lesssim\sqrt{TL/\gamma}. For this to be a contradiction, we need L\gg 1/\gamma^{2}>T^{2/3} , but this makes the lower bound \gg T , thus invalid. When \gamma>T^{-1/3} , \sqrt{T/\gamma}<\gamma T , \gamma\sqrt{T}\leq C(\gamma)\leq 2\gamma\sqrt{T} and the upper and lower bounds of \mathrm{Regret}(T,\Pi_{2}) gives \frac{L}{\gamma}\lesssim\mathrm{Regret}(T,\Pi_{2})\lesssim\gamma T+\sqrt{\frac{T}{\gamma}}\sqrt{L}, For this to be a contradiction, \frac{L}{\gamma}\gg\gamma T and \frac{L}{\gamma}\gg\sqrt{\frac{T}{\gamma}}\sqrt{L} , both these two requires L\gg\max\{\gamma^{2}T,\gamma T\}=\gamma T . But this would require the lower bound L/\gamma\gg T , thus invalid. To say it differently, there is no choices of \gamma and L combination that would lead to a contradiction. I.4 What if the regret bound is \sqrt{(\log N+V_{T})\log(1/\varepsilon)} ? In this section we check whether the Marinov–Zimmert wrapper argument can still yield a contradiction if the full-information experts guarantee has the form \mathrm{Regret}^{\mathrm{exp}}_{\varepsilon}(T)\;\leq\;G\sqrt{\bigl(\log N+V_{T}\bigr)\log(1/\varepsilon)},\qquad V_{T}:=\sum_{t=1}^{T}\mathrm{Var}_{i\sim p_{t}}(\ell_{t,i}), where N is the number of experts and the variance is the self-variance under p_{t} . Throughout, we take N=2k in the wrapper instance and write L:=\log(2k)\asymp\log k. I.4.1 Step 1: Wrapper upper bounds under the new hypothesis We apply the same wrapper reduction (Appendix B.4 of 28 ) that runs the experts algorithm on the scaled IPS losses \tilde{\ell}_{t,\pi}\in[0,1] . In the self-variance case one has \mathbb{E}\!\left[\sum_{t=1}^{T}\mathrm{Var}_{\pi\sim p_{t}}\bigl(\tilde{\ell}_{t,\pi}\bigr)\right]\;\lesssim\;\gamma^{2}T, (up to absolute constants). Plugging into the wrapper decomposition yields, for \Pi_{1} (quantile \varepsilon=1/2 so \log(1/\varepsilon)=\log 2=O(1) ), \mathbb{E}\mathrm{Regret}(T,\Pi_{1})\;\lesssim\;\gamma T\;+\;\frac{1}{\gamma}\sqrt{L+\gamma^{2}T}, (79) and for \Pi_{2} (quantile \varepsilon=1/(2k) so \log(1/\varepsilon)=\log(2k)=L ), \mathbb{E}\mathrm{Regret}(T,\Pi_{2})\;\lesssim\;\gamma T\;+\;\frac{1}{\gamma}\sqrt{(L+\gamma^{2}T)\,L}. (80) The only change relative to the earlier sections is that the experts term now depends on L+\gamma^{2}T rather than only \gamma^{2}T . I.4.2 Step 2: Theorem 4 lower bound in terms of C=\mathbb{E}\mathrm{Regret}(T,\Pi_{1})/\sqrt{T} Define the usual parameter C:=\frac{\mathbb{E}\mathrm{Regret}(T,\Pi_{1})}{\sqrt{T}}. From ( 79 ) we have C\;\lesssim\;\gamma\sqrt{T}\;+\;\frac{1}{\gamma\sqrt{T}}\sqrt{L+\gamma^{2}T}. (81) In particular, since the second term is nonnegative, we always have the simple lower bound C\;\geq\;\gamma\sqrt{T}. (82) Now recall Theorem 4 of 28 (our Theorem 46 ): in the regime c_{2}C^{2}\leq L\leq T/2 , there exists an environment E_{i^{*}} such that \mathrm{Regret}_{E_{i^{*}}}(T,\Pi_{2})\;\gtrsim\;\min\left\{\frac{L}{C}\sqrt{T},\ T\right\}. (83) Using ( 82 ) gives the crude but very useful upper bound on the lower bound: \min\left\{\frac{L}{C}\sqrt{T},\ T\right\}\;\leq\;\min\left\{\frac{L}{\gamma},\ T\right\}. (84) I.4.3 Step 3: Why no contradiction can occur We compare ( 84 ) with the upper bound ( 80 ). First, note that ( 80 ) always implies \mathbb{E}\mathrm{Regret}(T,\Pi_{2})\;\geq\;\frac{1}{\gamma}\sqrt{(L+\gamma^{2}T)\,L}\;\geq\;\frac{1}{\gamma}\sqrt{L\cdot L}\;=\;\frac{L}{\gamma}. (85) Therefore the \frac{L}{\gamma} branch of ( 84 ) can never exceed the upper bound. It remains to check the T branch. For ( 83 ) to yield the T term, it is necessary that \frac{L}{C}\sqrt{T}\gtrsim T , i.e. L\gtrsim C\sqrt{T} . Using ( 82 ) this implies L\;\gtrsim\;\gamma T\qquad\Longrightarrow\qquad\gamma\;\lesssim\;\frac{L}{T}. But then \frac{L}{\gamma}\gtrsim T , and hence ( 85 ) implies \mathbb{E}\mathrm{Regret}(T,\Pi_{2})\gtrsim T as well. Thus even in the T branch, the model-selection lower bound cannot exceed the upper bound. Conclusion. The wrapper argument of 28 does not contradict an experts guarantee of the form \sqrt{(\log N+V_{T})\log(1/\varepsilon)} in the self-variance setting: for every choice of \gamma and k , the resulting Theorem 4 lower bound is always bounded above (up to constants) by the wrapper upper bound ( 80 ). Equivalently, the model-selection construction becomes vacuous for ruling out this type of regret guarantee.