Black-Box Reductions for Parameter-free Online Learning in Banach Spaces

Parameter Free Online Learning

Our primary contribution is a series of three reductions that simplify the design of parameter-free algorithms,The name “parameter-free” was first used by Chaudhuri et al. for an expert algorithm that does not need to know the entropy of the competitor to achieve the optimal regret bound for any competitor. that is algorithms whose regret bound is optimal without the need to tune parameters (e.g. learning rates). First, we show that algorithms for online exp-concave optimization imply parameter-free algorithms for OLO (Section 2). Second, we show a general reduction from online learning in arbitrary dimensions with any norm to one-dimensional online learning (Section 3). Finally, given any two convex sets $W\subset V$, we construct an online learning algorithm over $W$ from an online learning algorithm over $V$ (Section 4).

First, we use our reductions to design a new parameter-free algorithm that improves upon the prior regret bounds, achieving

Notation. The dual of a Banach space $B$ over a field $F$, denoted $B^{\star}$, is the set of all continuous linear maps $B\to F$. We will use the notation $\langle v,w\rangle$ to indicate the application of a dual vector $v\in B^{\star}$ to a vector $w\in B$. $B^{\star}$ is also a Banach space with the dual norm: $\|v\|_{\star}=\sup_{w\in B,\ \|v\|=1}\langle w,v\rangle$. For completeness, in Appendix A we recall some more background on Banach spaces.

Online Newton Step to Online Linear Optimization via Betting Algorithms

In this section we show how to use the Online Newton Step (ONS) algorithm to construct a 1D parameter-free algorithm. Our approach relies on the coin-betting abstraction for the design of parameter-free algorithms. Coin betting strategies record the wealth of the algorithm, which is defined by some initial (i.e. user-specified) $\epsilon$ plus the total “reward” $\sum_{t=1}^{T}-g_{t}w_{t}$ it has gained:

Given this wealth measurement, coin betting algorithms “bet” a signed fraction $v_{t}\in(-1,1)$ of their current wealth on the outcome of the “coin” $g_{t}\in$ by playing $w_{t}=v_{t}\text{Wealth}_{T-1}$, so that $\text{Wealth}_{T}=\text{Wealth}_{T-1}-g_{t}v_{t}\text{Wealth}_{T-1}$. The advantage of betting algorithms lies in the fact that high wealth is equivalent to a low regret , but lower-bounding the wealth of an algorithm is conceptually simpler than upper-bounding its regret because the competitor $\mathring{w}$ does not appear in (1). Thus the question is how to pick betting fractions $v_{t}$ that guarantee high wealth. This is usually accomplished through careful design of bespoke potential functions and meticulous algebraic manipulation, but we take a different and simpler path.

At a high level, our approach is to re-cast the problem of choosing betting fractions $v_{t}$ as itself an online learning problem. We show that this online learning problem has exp-concave losses rather than linear losses. Exp-concave losses are known to be much easier to optimize than linear losses and it is possible to obtain $\ln(T)$ regret rather than the $\sqrt{T}$ limit for linear optimization . So by using an exp-concave optimization algorithm such as the Online Newton Step (ONS), we find the optimal betting fraction $\mathring{v}$ very quickly, and obtain high wealth. The pseudocode for the resulting strategy is in Algorithm 1.

Later (in Section 7), we will see that this same 1D argument holds seamlessly in Banach spaces, where now the betting fraction $v_{t}$ is a vector in the Banach space and the outcome of the coin $g_{t}$ is a vector in the dual space with norm bounded by 1. We therefore postpone computing exact constants for the Big-O notation in Theorem 1 to the more general Theorem 8.

It is important to note that ONS in 1D is extremely simple to implement. Even the projection onto a bounded set becomes just a truncation between two real numbers, so that Algorithm 1 can run quickly. We can show the following regret guarantee:

For $|g_{t}|\leq 1$, Algorithm 1, guarantees the regret bound:

Define $\text{Wealth}_{T}(\mathring{v})$ to be wealth of the betting algorithm that bets the constant (signed) fraction $\mathring{v}$ on every round, starting from initial wealth $\epsilon>0$.

We begin with the regret-reward duality that is the start of all coin-betting analyses . Suppose that we obtain a bound $\text{Wealth}_{T}\geq f_{T}\left(-\sum_{t=1}^{T}g_{t}\right)$ for some $f_{T}$. Then,

where $f_{T}^{\star}$ indicates the Fenchel conjugate, defined by $f_{T}^{\star}(x)=\sup_{\theta}\ \theta x-f_{T}(\theta)$.

So, now it suffices to prove a wealth lower bound. First, observing that $\text{Wealth}_{T}=\text{Wealth}_{T-1}-\text{Wealth}_{T-1}g_{t}v_{t}$, we derive a simple expression for $\ln\text{Wealth}_{T}$ by recursion:

Similarly, we have $\ln\text{Wealth}_{T}(\mathring{v})=\ln(\epsilon)+\sum_{t=1}^{T}\ln(1-\mathring{v}g_{t})$. We subtract the identities to obtain

where $R_{T}^{v}(\mathring{v})$ is the regret of our method for choosing $v_{t}$.

For the next step, observe that $-\ln(1-g_{t}v)$ is exp-concave (a function $f$ is exp-concave if $\exp(-f)$ is concave), so that choosing $v_{t}$ is an online exp-concave optimization problem. Prior work on exp-concave optimization allows us to obtain $R^{v}_{T}(\mathring{v})=O\left(\ln\left(\sum_{t=1}^{T}g_{t}^{2}\right)\right)$ for any $|\mathring{v}|\leq\tfrac{1}{2}$ using the ONS algorithm. Therefore (dropping all constants for simplicity), we use (3) to obtain $\text{Wealth}_{T}\geq\text{Wealth}_{T}(\mathring{v})/\sum_{t=1}^{T}g_{t}^{2}$ for all $|\mathring{v}|\leq\tfrac{1}{2}$.

Finally, we need to show that there exists $\mathring{v}$ such that $\text{Wealth}_{T}(\mathring{v})/\sum_{t=1}^{T}g_{t}^{2}$ is high enough to guarantee low regret on our original problem. Consider $\mathring{v}=\tfrac{-\sum_{t=1}^{T}g_{t}}{2\sum_{t=1}^{T}g_{t}^{2}+2\left|\sum_{t=1}^{T}g_{t}\right|}\in[-1/2,1/2]$. Then, we invoke the tangent bound $\ln(1+x)\geq x-x^{2}$ for $x\in[-1/2,1/2]$ (e.g. see ) to see:

where $f_{T}(x)=\epsilon\exp[x^{2}/(4\sum_{t=1}^{T}g_{t}^{2}+4|x|)]/\sum_{t=1}^{T}g_{t}^{2}$. To obtain the desired result, we recall that $\text{Wealth}_{T}\geq f_{T}\left(\sum_{t=1}^{T}g_{t}\right)$ implies $R_{T}(\mathring{w})\leq\epsilon+f_{T}^{\star}(\mathring{w})$, and calculate $f_{T}^{\star}$ (see Lemma 19).

In order to implement the algorithm, observe that our reference betting fraction $\mathring{v}$ lies in $[-1/2,1/2]$, so we can run ONS restricted to the domain $[-1/2,1/2]$. Exact constants can be computed by substituting the constants coming from the ONS regret guarantee, as we do in Theorem 8. ∎

From 1D Algorithms to Dimension-Free Algorithms

A common strategy for designing parameter-free algorithms is to first create an algorithm for 1D problems (as we did in the previous section), and then invoke some particular algorithm-specific analysis to extend the algorithm to high dimensional spaces [23; 6; 20]. This strategy is unappealing for a couple of reasons. First, these arguments are often somewhat tailored to the algorithm at hand, and so a new argument must be made for a new 1D algorithm (indeed, it is not clear that any prior dimensionality extension arguments apply to our Algorithm 1). Secondly, all such arguments we know of apply only to Hilbert spaces and so do not allow us to design algorithms that consider norms other than the standard Euclidean $2$-norm. In this section we address both concerns by providing a black-box reduction from optimization in any Banach space to 1D optimization. In further contrast to previous work, our reduction can be proven in just a few lines.

Given these inputs, the reduction uses the 1D algorithm $\mathcal{A_{\text{1D}}}$ to learn a “magnitude” $z$ and the unit-ball algorithm $\mathcal{A}_{S}$ to learn a “direction” $y$. This direction and magnitude are multiplied together to form the final output $w=zy$. Given a gradient $g$, the “magnitude error” is given by $\langle g,y\rangle$, which is intuitively the component of the gradient parallel to $w$. The “direction error” is just $g$. Our reduction is described formally in Algorithm 2.

Where by slight abuse of notation we set $\mathring{w}/\|\mathring{w}\|=0$ when $\mathring{w}=0$. Further, the subgradients $s_{t}$ sent to $\mathcal{A_{\text{1D}}}$ satisfy $|s_{t}|\leq\|g_{t}\|_{\star}$.

First, observe that $|s_{t}|\leq\|g_{t}\|_{\star}\|y_{t}\|\leq\|g_{t}\|_{\star}$ since $\|y_{t}\|\leq 1$ for all $t$. Now, compute:

With this reduction in hand, designing dimension-free and parameter-free algorithms is now exactly as easy as designing 1D algorithms, so long as we have access to a unit-ball algorithm $\mathcal{A}_{S}$. As mentioned, for any Hilbert space we indeed have such an algorithm. In general, algorithms $\mathcal{A}_{S}$ exist for most other Banach spaces of interest , and in particular one can achieve $R^{\mathcal{A}_{S}}_{T}(\mathring{w})\leq O\left(\sqrt{\tfrac{1}{\lambda}\sum_{t=1}^{T}\|g_{t}\|_{\star}^{2}}\right)$ whenever $B$ is $(2,\lambda)$-uniformly convex using the Follow-the-Regularized-Leader algorithm with regularizers scaled by $\tfrac{\sqrt{\lambda}}{\sqrt{\sum_{i=1}^{t}\|g_{i}\|_{\star}^{2}}}$ .

Applying Algorithm 2 to our 1D Algorithm 1, for any $(2,\lambda)$-uniformly convex $B$, we obtain:

Not only does this provide the fastest known parameter-free algorithm for an arbitrary norm, it is also the first parameter-free algorithm to obtain a dependence on the gradients of $\|g_{t}\|_{\star}^{2}$ rather than $\|g_{t}\|_{\star}$Independently, achieved the same runtime in the supervised prediction setting, but with no adaptivity to $g_{t}$.. This improved bound immediately implies much lower regret in easier settings, such as smooth losses with small loss values at $\mathring{w}$ .

Reduction to Constrained Domains

The previous algorithms have dealt with optimization over an entire vector space. Although common and important case in practice, sometimes we must perform optimization with constraints, in which each $w_{t}$ and the comparison point $\mathring{w}$ must lie in some convex domain $W$ that is not an entire vector space. This constrained problem is often solved with the classical Mirror Descent or Follow-the-Regularized-Leader analysis. However, these approaches have drawbacks: for unbounded sets, they typically maintain regret bounds that have suboptimal dependence on $\mathring{w}$, or, for bounded sets, they depend explicitly on the diameter of $W$. We will address these issues with a simple reduction. Given any convex domain $V\supset W$ and an algorithm $\mathcal{A}$ that maintains regret $R^{\mathcal{A}}_{T}(\mathring{w})$ for any $\mathring{w}\in V$, we obtain an algorithm that maintains $2R^{\mathcal{A}}_{T}(\mathring{w})$ for any $\mathring{w}$ in $W$.

Before giving the reduction, we define the distance to a convex set $W$ as $S_{W}(x)=\inf_{d\in W}\|x-d\|$ as well as the projection to $W$ as $\Pi_{W}(x)=\{d\in W:\|d-x\|\leq\|c-x\|,\forall c\in W\}$. Note that if $B$ is reflexive,All Hilbert spaces and finite-dimensional Banach spaces are reflexive. $\Pi_{W}(x)\neq\emptyset$ and that it is a singleton if $B$ is a Hilbert space [16, Exercise 4.1.4].

The intuition for our reduction is as follows: given a vector $z_{t}\in V$ from $\mathcal{A}$, we predict with any $w_{t}\in\Pi_{W}(z_{t})$. Then give $\mathcal{A}$ a subgradient at $z_{t}$ of the surrogate loss function $\langle g_{t},\cdot\rangle+\|g_{t}\|_{\star}S_{W}$, which is just the original linearized loss plus a multiple of $S_{W}$. The additional term $S_{W}$ serves as a kind of Lipschitz barrier that penalizes $\mathcal{A}$ for predicting with any $z_{t}\notin W$. Pseudocode for the reduction is given in Algorithm 3.

Assume that the algorithm $\mathcal{A}$ obtains regret $R^{\mathcal{A}}_{T}(\mathring{w})$ for any $\mathring{w}\in V$. Then Algorithm 3 guarantees regret:

Before proving this Theorem, we need a small technical Proposition, proved in Appendix D.

$S_{W}$ is convex and $1$-Lipschitz for any closed convex set $W$ in a reflexive Banach space $B$.

We conclude this section by observing that in many cases it is very easy to compute an element of $\Pi_{W}$ and a subgradient of $S_{W}$. For example, when $W$ is a unit ball, it is easy to see that $\Pi_{W}(x)=\tfrac{x}{\|x\|}$ and $\partial S_{W}(x)=\partial\|x\|$ for any $x$ not in the ball. In general, we provide the following result that often simplifies computing the subgradient of $S_{W}$ (proved in Appendix D):

Let $B$ be a reflexive Banach space such that for every $0\neq b\in B$, there is a unique dual vector $b^{\star}$ such that $\|b^{\star}\|_{\star}=1$ and $\langle b^{\star},b\rangle=\|b\|$. Let $W\subset B$ a closed convex set. Given $x\in B$ and $x\notin W$, let $p\in\Pi_{W}(x)$. Then $\{(x-p)^{\star}\}=\partial S_{W}(x)$.

Reduction for Multi-Scale Experts

In this section, we apply our reductions to the multi-scale experts problem considered in [9; 1]. Our algorithm improves upon both prior algorithms: the approach of has a mildly sub-optimal dependence on the prior distribution, while the approach of takes time $O(T)$ per update, resulting in a quadratic total runtime. Our algorithm matches the regret bound of while running in the same time complexity as online gradient descent.

We accomplish this through two reductions. First, given any distribution $(\pi_{1},\dots,\pi_{N})$ and any family of 1-dimensional OLO algorithms $\mathcal{A}(\epsilon)$ that guarantees $R(u)\leq O\left(\epsilon+|u|\sqrt{\log(|u|T/\epsilon)T}\right)$ on 1-Lipschitz losses for any given $\epsilon$ (such as our Algorithm 1 or many other parameter-free algorithms), we apply the classic “coordinate-wise updates” trick to generate an $N$-dimensional OLO algorithm with regret $R_{T}(u)=O\left(\epsilon+\sum_{i=1}^{N}|u_{i}|\sqrt{\log\left(|u_{i}|T/(\epsilon\pi_{i})\right)T}\right)$ on losses that are $1$-Lipschitz with respect to the $1$-norm.

Suppose for any $\epsilon>0$, $\mathcal{A}(\epsilon)$ guarantees regret

for 1-dimensional losses bounded by $1$. Then Algorithm 4 guarantees regret

With this in hand, notice that applying our reduction Algorithm 3 with the $1$-norm easily yields an algorithm over the probability simplex $W$ with the same regret (up to a factor of 2), as long as $\|g_{t}\|_{\infty}\leq 1$. Then, we apply an affine change of coordinates to make our multi-scale experts losses have $\|g_{t}\|_{\infty}\leq 1$, so that applying this algorithm yields the desired result (see Algorithm 5).

If $g_{t}$ satisfies $|g_{t,i}|\leq c_{i}$ for all $t$ and $i$ and $\mathcal{A}(\epsilon)$ satisfies the conditions of Theorem 5, then, for any $\mathring{w}$ in the probability simplex, Algorithm 5 satisfies the regret bound

In Appendix E we show how to compute the projection $\Pi_{S}$ and a subgradient of $S_{W}$ in $O(N)$ time via a simple greedy algorithm. As a result, our entire reduction runs in $O(N)$ time per update.

Reduction to Adapt to Curvature

In this section, we present a black-box reduction to make a generic online learning algorithm over a Banach space adaptive to the curvature of the losses. Given a set $W$ of diameter $D=\sup_{x,y\in W}\|x-y\|$, our reduction obtains $O(\log(TD)^{2}/\mu)$ regret on online $\mu$-strongly convex optimization problems, but still guarantees $O(\log(TD)^{2}D\sqrt{T})$ regret for online linear optimization problems, both of which are only log factors away from the optimal guarantees. We follow the intuition of , who suggest adding a weighted average of previous $w_{t}$s to the outputs of a base algorithm as a kind of “momentum” term. We improve upon their regret guarantee by a log factor and by the $\|g_{t}\|_{\star}^{2}$ terms instead of $\|g_{t}\|_{\star}$. More importantly, their algorithm involves an optimization step which may be very slow for most domains (e.g. the unit ball). In contrast, thanks to our fast reduction in Section 4, we keep the same running time as the base algorithm. Finally, previous results for algorithms with similar regret (e.g. [7; 30]) show logarithmic regret only for stochastic strongly convex problems. We give a two-line argument extending this to the adversarial case as well.

Let $\mathcal{A}$ be an online linear optimization algorithm that outputs $w_{t}$ in response to $g_{t}$. Suppose $W$ is a convex closed set of diameter $D$. Suppose $\mathcal{A}$ guarantees for all $t$ and $\mathring{v}$:

for constants $A$, $B$ and $C$ and $\epsilon$ independent of $t$. Then for all $\mathring{w}\in W$, Algorithm 6 guarantees

Where we have used $\|g_{t}\|_{\star}\leq 1$.

Banach-space betting through ONS

Let $B$ be a $d$-dimensional real Banach space and $u\in B$ be an arbitrary unit vector. Then, there exists a linear operator $L$ such that using the Algorithm 7, we have for any $\mathring{w}\in B$,

The main particularity of this bound is the presence of the terms $\sqrt{d\sum_{t=1}^{T}\langle g_{t},\mathring{w}\rangle^{2}}$ rather than the usual $\|\mathring{w}\|\sqrt{\sum_{t=1}^{T}\|g_{t}\|_{\star}^{2}}$. We can interpret this bound as being adaptive to any sequence of norms $\|\cdot\|_{1},\dots,\|\cdot\|_{t}$ because $\sqrt{d\sum_{t=1}^{T}\langle g_{t},\mathring{w}\rangle^{2}}\leq\sqrt{d\sum_{t=1}^{T}\|\mathring{w}\|_{t}^{2}(\|g_{t}\|_{t})_{\star}^{2}}$. A similar kind of “many norm adaptivity” was recently achieved in , which competes with the best fixed $L_{p}$ norm (or the best fixed norm in any finite set). Our bound in Theorem 8 is a factor of $\sqrt{d}$ worse,The dependence on $d$ is unfortunately unimprovable, as shown by . but we can compete with any possible sequence of norms rather than with any fixed one.

Conclusions

We have introduced a sequence of three reductions showing that parameter-free online learning algorithms can be obtained from online exp-concave optimization algorithms, that optimization in a vector space with any norm can be obtained from 1D optimization, and that online optimization with constraints is no harder than optimization without constraints. Our reductions result in simpler arguments in many cases, and also often provide better algorithms in terms of regret bounds or runtime. We therefore hope that these tools will be useful for designing new online learning algorithms.

Acknowledgments

This material is based upon work partly supported by the National Science Foundation under grant no. 1740762 “Collaborative Research: TRIPODS Institute for Optimization and Learning” and by a Google Research Award for FO.

References

Appendix

In Section A we collect some background information about Banach spaces, their duals, and other properties.

In Section B we provide an analysis of the ONS algorithm in Banach spaces that is useful for proving Theorem 8.

In Section C we apply this analysis of ONS in Banach spaces to prove Theorem 8, and provide the missing Fenchel conjugate calculation required to prove Theorem 1, which are our reductions from parameter-free online learning to Exp-concave optimization.

In Section D we prove Proposition 1, used in our reduction from constrained optimization to unconstrained optimization in Section 4. In this section we also prove Theorem 4, which simplifies computing subgradients of $S_{W}$ in many cases.

In Section E we show how to compute $\Pi_{W}$ and a subgradient of $S_{W}$ on $O(N)$ time for use in our multi-scale experts algorithm.

Finally, in Section F we prove Theorem 7, our regret bound for an algorithm that adapts to stochastic curvature.

Appendix A Banach Spaces

Given any vector space $V$, there is a natural injection $V\to V^{\star\star}$ given by $x\mapsto\langle\cdot,x\rangle$. When this injection is an isomorphism of Banach spaces, then the space $V$ is called reflexive. All finite-dimensional Banach spaces are reflexive.

Given any linear map of Banach spaces $T:X\to Y$, we define the adjoint map $T^{\star}:Y^{\star}\to X^{\star}$ by $T^{\star}(y^{\star})(x)=\langle y^{\star},T(x)\rangle$. $T^{\star}$ has the property (by definition) that $\langle y^{\star},T(x)\rangle=\langle T^{\star}(y^{\star}),x\rangle$. As a special case, if $B$ is a reflexive Banach space and $T:B\to B^{\star}$, then we can use the natural identification between $B^{\star\star}$ and $B$ to view $T^{\star}$ as $T^{\star}:B\to B^{\star}$. Thus, in this case it is possible to have $T=T^{\star}$, in which case we call $T$ self-adjoint.

We define a Banach space $B$ as $(p,D)$ uniformly convex if :

From this definition, we can see that if $B$ is $(2,D)$ uniformly convex, then $\|\cdot\|^{2}$ is a $D$-strongly convex function with respect to $\|\cdot\|$:

Let $f(x)$ a convex function that satisfies

Then, $f$ satisfies $f(x+\delta)\geq f(x)+g(\delta)+D\frac{\|\delta\|^{p}}{p}$ for any subgradient $g\in\partial f(x)$. In particular for $p=2$, $f$ is $D$ strongly convex with respect to $\|\cdot\|$.

that implies $\frac{D}{p}\|2\delta\|^{p}\leq R_{x}(2\delta)$. So that $f(x+\tau)=f(x)+g(\tau)+R_{x}(\tau)\geq f(x)+g(\tau)+\frac{D}{p}\|\tau\|^{p}$ as desired. ∎

Let $B$ be a $(2,D)$ uniformly convex Banach space, then $f(x)=\frac{1}{2}\|x\|^{2}$ is $D$-strongly convex.

Let $x=u+v$ and $y=u-v$. Then, from the definition of $(2,D)$ uniformly convex Banach space, we have

Using Lemma 9, we have the stated bound. ∎

Appendix B Proof of the regret bound of ONS in Banach spaces

First, we need some additional facts about self-adjoint operators. These are straight-forward properties in Hilbert spaces, but may be less familiar in Banach spaces so we present them below for completeness.

Suppose $X$ and $Y$ are Banach spaces and $T:X\to Y$ is invertible. Then, $T^{\star}$ is invertible and $(T^{-1})^{\star}=(T^{\star})^{-1}$.

Let $y^{\star}\in Y^{\star}$. Let $x\in X$. Recall that by definition $\langle T^{\star}(y^{\star}),x\rangle=\langle y^{\star},T(x)\rangle$. Then we have

where we used the definition of adjoint twice. Therefore, $(T^{-1})^{\star}(T^{\star}(y^{\star}))=y^{\star}$ and so $(T^{-1})^{\star}=(T^{\star})^{-1}$. ∎

Suppose $B$ is a reflexive Banach space and $T:B\to B^{\star}$ is such that

for some vectors $b^{i}\in B^{\star}$. Then $T^{\star}=T$.

Let $g,f\in B$. Since $B$ is reflexive, $g$ corresponds to the function $\langle\cdot,g\rangle\in B^{\star\star}$. Now, we compute:

Suppose $\tau>0$, $B$ is a $d$-dimensional real Banach space, $b^{1},\dots,b^{d}$ are a basis for $B^{\star}$ and $g_{1},\dots,g_{T}$ are elements of $B^{\star}$. Then, $A:B\to B^{\star}$ defined by $A(x)=\tau\sum_{i=1}^{d}\langle b^{i},x\rangle b^{i}+\sum_{t=1}^{T}\langle g_{t},x\rangle g_{t}$ is invertible and self-adjoint, and $\langle Ax,x\rangle>0$ for all $x\neq 0$.

First, $A$ is self-adjoint by Proposition 5.

Next, we show $A$ is invertible. Suppose otherwise. Then, since $B$ and $B^{\star}$ are both $d$-dimensional, $A$ must have a non-trivial kernel element $x$. Therefore,

so that $\langle b^{i},x\rangle=0$ for all $i$. Since the $b^{i}$ form a basis for $B^{\star}$, this implies $\langle y,x\rangle=0$ for all $y\in B^{\star}$, which implies $x=0$. Therefore, $A$ has no kernel and so must be invertible.

Finally, observe that since (5) holds for any $x$, we must have $\langle Ax,x\rangle>0$ if $x\neq 0$. ∎

Now we state the ONS algorithm in Banach spaces and prove its regret guarantee:

Using the notation of Algorithm 8, suppose $L(x)=\sum_{i=1}^{d}\langle b^{i},x\rangle$ for some basis $b^{i}\in B^{\star}$ and that $B$ is $d$-dimensional. Then for any $\mathring{v}\in S$,

First, observe by Proposition 6 that $A_{t}$ is invertible and self-adjoint for all $t$.

Now, define $x_{t+1}=v_{t}-\frac{1}{\beta}A^{-1}_{t}(z_{t})$ so that $v_{t+1}=\Pi^{A_{t}}_{S}(x_{t+1})$. Then, we have

where in the last line we used $\langle A_{t}(v_{t}-\mathring{v}),A^{-1}_{t}(z_{t})\rangle=\langle(v_{t}-\mathring{v}),A_{t}^{\star}A^{-1}_{t}(z_{t})\rangle$ and $A_{t}^{\star}=A_{t}$. We now use the Lemma 8 from , extended to Banach spaces thanks to the last statement of Proposition 6, to have

It remains to choose $L$ properly and analyze the sum $\sum_{t=1}^{T}\langle z_{t},A^{-1}_{t}(z_{t})\rangle$ In order to do this, we introduce the concept of an Auerbach basis (e.g. see Theorem 1.16):

Let $B$ be a $d$-dimensional Banach space. Then there exists a basis of $b_{1},\dots,b_{d}$ of $B$ and a basis $b^{1},\dots,b^{d}$ of $B^{\star}$ such that $\|b_{i}\|=\|b^{i}\|_{\star}=1$ for all $i$ and $\langle b_{i},b^{j}\rangle=\delta_{ij}$. Any bases $(b_{i})$ and $(b^{i})$ satisfying these conditions is called an Auerbach basis.

We will use an Auerbach basis to define $L$, and also to provide a coordinate system that makes it easier to analyze the sum $\sum_{t=1}^{T}\langle z_{t},A^{-1}_{t}(z_{t})\rangle$.

Suppose $B$ is $d$-dimensional. Let $(b_{i})$ and $(b^{i})$ be an Auerbach basis for $B$. Set $L(x)=\sum_{i=1}^{d}\langle b^{i},x\rangle b^{i}$. Define $A_{t}$ as in Algorithm 7. Then, for any $\mathring{v}\in S$, the following holds

First, we show that $\frac{\beta}{2}\langle L(\mathring{v}),\mathring{v}\rangle\leq\frac{\beta d}{2}\|\mathring{v}\|^{2}$. To see this, observe that for any $x\in B$,

Since $\langle b^{i},b_{j}\rangle=\delta_{ij}$, these maps respect the action of dual vectors in $B^{\star}$. That is,

Further, since each $\|b_{i}\|=\|b_{i}\|_{\star}=1$, we have

Further, when written as a matrix, the $ij$th element of $\overline{M}$ is

These maps all commute properly: $\overline{Mx}=\overline{M}\overline{x}$ for any $M\in\mathcal{L}(B,B^{\star})$ and $x\in B$, and similarly $\overline{Mx}=\overline{M}\overline{x}$ for any $M\in\mathcal{L}(B^{\star},B)$ and $x\in B^{\star}$. It follows that $\overline{M}^{-1}=\overline{M^{-1}}$ for any $M$ as well.

Now, let’s calculate $\overline{L}_{ij}$:

so that the matrix $\overline{L}$ is the identity.

Finally, if $M_{g}:B\to B^{\star}$ is the map $M_{g}(x)=\langle g,x\rangle g$, then a simple calculation shows

With these details described, recall that we are trying to bound the sum

We have $\|\overline{z_{n}}\|\leq\sqrt{d}\|z_{n}\|_{\star}$ and

where in the second inequality we used the fact that the determinant is maximized when all the eigenvalues are equal to $\frac{\sum_{t=1}^{T}\|\overline{z_{t}}\|^{2}}{d}$. ∎

For completeness, we also state the regret bound and the setting of the parameters $\beta$ and $\tau$ to obtain a regret bound for exp-concave functions. Note that we use a different settings in Algorithms 1 and 7, tailored to our specific setting.

Suppose we run Algorithm 7 on $\alpha$ exp-concave losses. Let $D$ be the diameter of the domain $S$ and $\|\nabla f(x)\|_{\star}\leq Z$ for all the $x$ in $S$. Then set $\beta=\frac{1}{2}\min\left(\frac{1}{4ZD},\alpha\right)$ and $\tau=\frac{1}{\beta^{2}D^{2}}$. Then

First, observe that classic analysis of $\alpha$ exp-concave functions [12, Lemma 3] shows that for any $x,y\in S$,

Therefore, by Theorems 11 and 13, we have

Substitute our values for $\beta$ and $\tau$ to conclude

where in the last line we used $\frac{1}{\beta}\leq 8(ZD+1/\alpha)$. ∎

Appendix C Proofs of Theorems 1 and 8

Now, observe that since $1-\langle g_{t},\mathring{v}\rangle\geq 0$ and $1-\langle g_{t},v\rangle\geq 0$, $1+\frac{\langle g_{t},v-\mathring{v}\rangle}{1-\langle g_{t},v\rangle}\geq 0$ as well so that $\frac{\langle g_{t},v-\mathring{v}\rangle}{1-\langle g_{t},v\rangle}\geq-1$. Further, since $\|\mathring{v}-v\|\leq 1$ and $1-\langle g_{t},v\rangle\geq 1/2$, $\frac{\langle g_{t},v-\mathring{v}\rangle}{1-\langle g_{t},v\rangle}\leq 2$. Therefore, by Lemma 15 we have

where we have used $\|\mathring{v}\|\leq 1/2$. Then observe that $\|z_{t}\|_{\star}^{2}=\frac{\|g_{t}\|_{\star}^{2}}{(1+\langle g_{t},\beta_{t}\rangle)^{2}}\leq 4\|g_{t}\|_{\star}^{2}$ so that $\ln(1+\sum_{t=1}^{T}\|z_{t}\|_{\star}^{2})\leq\ln(1+4\sum_{t=1}^{T}\|g_{t}\|_{\star}^{2})$. Finally, substitute the specified value of $\beta$ and numerically evaluate to conclude the bound. ∎

Now, we collect some Fenchel conjugate calculations that allow us to convert our wealth lower-bounds into regret upper-bounds:

Let $f(x)=a\exp(b|x|)$, where $a,b>0$. Then

Let $f(x)=a\exp(b\frac{x^{2}}{|x|+c})$, where $a,b>0$ and $c\geq 0$. Then

Case $|x^{\star}|\leq c$. In this case, we have that $f(x^{\star})\geq a\exp(b\frac{x^{2}}{2c})$, so

where the last inequality is from Lemma 18 in .

Case $|x^{\star}|>c$. In this case, we have that $f(x^{\star})\geq a\exp\left(b\tfrac{(x^{\star})^{2}}{2|x^{\star}|}\right)=a\exp\left(\tfrac{b}{2}|x^{\star}|\right)$, so

where the last inequality is from Lemma 18.

Considering the max over the two cases gives the stated bound. ∎

Let $u$ be an arbitrary unit vector and $\|g_{t}\|_{\star}\leq 1$ for $t=1,\cdots,T$. Then

Recall that $\ln(1+x)\geq x-x^{2}$ for $|x|\leq 1/2$. Then, we compute

Choose $v=\frac{u}{2}\frac{\left\langle\sum_{t=1}^{T}g_{t},u\right\rangle}{\sum_{t=1}^{T}\langle g_{t},u\rangle^{2}+\left|\left\langle\sum_{t=1}^{T}g_{t},u\right\rangle\right|}$. Then, clearly $\|v\|\leq\frac{1}{2}$. Thus, we have

Let $u$ be an arbitrary unit vector in $B$ and $t>0$. Then, using the Algorithm 7, we have

Let’s compute a bound on our wealth, $\text{Wealth}_{T}$. We have that

where we have used the calculation of Fenchel conjugate of $f$ from Lemma 19. Then observe that $\exp(d/17)\leq\exp((9d+1)/153)\leq 2^{9d+1}$ to conclude:

Given some $\mathring{w}$, set $u=\frac{\mathring{w}}{\|\mathring{w}\|}$ and $t=\|\mathring{w}\|$. Then observe that $t^{2}\sum_{t=1}^{T}\langle g_{t},u\rangle^{2}=\sum_{t=1}^{T}\langle g_{t},\mathring{w}\rangle^{2}$ and apply the previous Lemma 21 to conclude the desired result. ∎

Appendix D Proof of Proposition 1 and Theorem 4

Let $x,y\in B$, $t\in$, $x^{\prime}\in\Pi_{W}(x)$, and $y^{\prime}\in\Pi_{W}(y)$. Then

For the Lipschitzness, let $x\in B$ and $x^{\prime}\in\Pi_{W}(x)$, and observe that

Similarly, let $x\in B$, $\delta$ such that $x+\delta\in B$ and $x^{\prime}\in\Pi_{W}(x+\delta)$, then

So that $|S_{W}(x)-S_{W}(x+\delta)|\leq\|\delta\|$. ∎

Now we restate and prove Theorem 4: See 4

Let $x^{\prime}=\frac{x+p}{2}$. Then clearly $S_{W}(x^{\prime})\leq\|x^{\prime}-p\|=\frac{\|x-p\|}{2}=S_{W}(x)-\|x-x^{\prime}\|$. Since $S_{W}$ is 1-Lipschitz, $S_{W}(x^{\prime})\geq S_{W}(x)-\|x-x^{\prime}\|$ and so $S_{W}(x^{\prime})=S_{W}(x)-\|x-x^{\prime}\|$.

Suppose $g\in\partial S_{W}(x)$. Then $\langle g,x^{\prime}-x\rangle+S_{W}(x)\leq S_{W}(x^{\prime})=S_{W}(x)-\|x-x^{\prime}\|$. Therefore, $\langle g,x^{\prime}-x\rangle\leq-\|x-x^{\prime}\|$. Since $\|g\|_{\star}\leq 1$, we must have $\|g\|_{\star}=1$ and $\langle g,x-p\rangle=\|x-p\|$. By assumption, this uniquely specifies the vector $(x-p)^{\star}$. Since $\partial S_{W}$ is not the empty set, $\{(x-p)^{\star}\}=\partial S_{W}(x)$. ∎

In this section we show how to compute $\Pi_{W}(x)$ and a subgradient of $S_{W}(x)$ in Algorithm 5. First we tackle $\Pi_{W}(x)$. Without loss of generality, assume the $c_{i}$ are ordered so that $c_{1}\geq c_{2}\geq\cdots\geq c_{N}$. We also consider $W_{k}=\{x:x_{i}\geq 0\text{ for all }i\text{ and }\sum_{i=1}^{N}x_{i}/c_{i}=k\}$ instead of $W=W_{1}$. Obviously we are particularly interested in the case $k=1$, but working in this mild generality allows us to more easily state an algorithm for computing $\Pi_{W}(x)$ in a recursive manner.

Let $N>1$ and $W_{k}=\{x:x_{i}\geq 0\text{ for all }i\text{ and }\sum_{i=1}^{N}x_{i}/c_{i}=k\}$, and let $S_{W_{k}}(x)=\inf_{y\in W_{k}}\|x-y\|_{1}$. Suppose the $c_{i}$ are ordered so that $c_{1}\geq c_{2}\geq\cdots\geq c_{N}$. Then for any $x=(x_{1},\dots,x_{n})$, there exists a $y=(y_{1},\dots,y_{n})\in\Pi_{W_{k}}(x)$ such that

First, suppose $N=1$. Then clearly there is only one element of $W_{k}$ and so the choice of $\Pi_{W_{k}}(x)$ is forced. So now assume $N>1$.

Let $(y_{1},\dots,y_{N})\in\Pi_{W_{k}}(x_{1},\dots,x_{N})$ be such that $|y_{1}-x_{1}|$ is as small as possible (such a point exists because $W_{k}$ is compact).

We consider three cases: either $x_{1}>kc_{1},$ $x_{1}<0$ or $x_{1}\in[0,kc_{1}]$.

Case 1: $x>kc_{1}$. Suppose $y_{1}<kc_{1}$. Let $i$ be the largest index such that $y_{i}\neq 0$. $i\neq 1$ since $y_{1}/c_{1}<k$. Choose $0<\epsilon<\min(y_{i}\frac{c_{1}}{c_{i}},kc_{1}-y_{1})$. Then let $y^{\prime}$ be such that $y^{\prime}_{1}=y_{1}+\epsilon$, $y^{\prime}_{i}=y_{i}-\epsilon\frac{c_{i}}{c_{1}}$ and $y^{\prime}_{j}=y_{j}$ otherwise. Then by definition of $\epsilon$, $y^{\prime}_{i}\geq 0$ and $y^{\prime}_{1}\leq kc_{1}$. Further, $\sum_{j=1}^{N}y^{\prime}_{j}/c_{j}=\epsilon/c_{1}-\frac{c_{i}}{c_{1}}\epsilon/c_{i}+\sum_{j=1}^{N}y_{j}/c_{j}=k$ so that $y^{\prime}\in W_{k}$. However, since $x_{1}>kc_{1},$ $\|y^{\prime}-x\|_{1}\leq\|y-x\|_{1}-\epsilon+\epsilon\frac{c_{i}}{c_{1}}\leq\|y-x\|_{1}$. Therefore, $y^{\prime}\in\Pi_{W_{k}}(x)$, but $|y^{\prime}_{1}-x_{1}|<|y_{1}-x_{1}|$, contradicting our choice of $y_{1}$. Therefore, $y_{1}=kc_{1}$.

Case 2: $x<0$. This case is very similar to the previous case. Suppose $y_{1}>0$. Let $i$ be the largest index such that $y_{i}\neq kc_{i}$. $i\neq 1$ since otherwise $\sum_{j=1}^{N}y_{j}/c_{j}>\sum_{j=2}^{N}k=k(N-1)\geq k$, which is not possible. Choose $0<\epsilon<\min(y_{1},c_{1}(kc_{i}-y_{i})/c_{i})$. Set $y^{\prime}$ such that $y^{\prime}_{1}=y_{1}-\epsilon$, $y^{\prime}_{i}=y_{i}+\epsilon\frac{c_{i}}{c_{1}}$. Then, again we have $y^{\prime}\in W_{k}$ and $\|y^{\prime}-x\|_{1}\leq\|y-x_{1}\|_{1}-\epsilon+\epsilon\frac{c_{i}}{c_{1}}\leq\|y-x\|_{1}$ so that $y^{\prime}\in\Pi_{W_{k}}(x)$, but $|y^{\prime}_{1}-x_{1}|<|y_{1}-x_{1}|$. Therefore, we cannot have $y_{1}>0$ and so $y_{1}=0$.

Case 3: $x\in[0,kc_{1}]$. Suppose $y_{1}<x_{1}\leq kc_{1}$. Then by the same the argument as for Case 1, there is some $i>1$ such that for any $0<\epsilon<\min(y_{i}\frac{c_{1}}{c_{i}},x_{1}-y_{1})$, we can construct $y^{\prime}$ with $y^{\prime}\in\Pi_{W_{k}}(x)$ and $|y^{\prime}_{1}-x_{1}|<|y_{1}-x_{1}|$. Therefore, $y_{1}\geq x_{1}$.

Similarly, if $y_{1}>x_{1}$, then by the same argument as for Case 2, there is some $i>1$ such that for any $0<\epsilon<\min(y_{1}-x_{1},c_{1}(kc_{i}-y_{i})/c_{i})$, we again construct $y^{\prime}$ with $y^{\prime}\in\Pi_{W_{k}}(x)$ and $|y^{\prime}_{1}-x_{1}|<|y_{1}-x_{1}|$. Therefore, $y_{1}=x_{1}$. ∎

This result suggests an explicit algorithm for choosing $y\in\Pi_{W}(x)=\Pi_{W_{1}}(x)$. Using the Proposition we can pick $y_{1}$ such that there is a $y\in\Pi_{W_{1}}(x)$ with first coordinate $y_{1}$. If $y\in\Pi_{W_{k}}(x)$ has first coordinate $y_{1}$, then if $W^{2}_{k}=\{(y_{2},\dots,y_{n}):y_{i}\geq 0\text{ for all }i\text{ and }\sum_{i=2}^{N}y_{i}/c_{i}=k\}$, then $(y_{2},\dots,y_{N})\in\Pi_{W^{2}_{k-y_{1}/c_{1}}}(x_{2},\dots,x_{N})$. Therefore, we can use a greedy algorithm to choose each $y_{i}$ in increasing order of $i$ and obtain a point $y\in\Pi_{W_{k}}(x)$ in $O(N)$ time. This procedure is formalized in Algorithm 9.

Unfortunately, $\|\cdot\|_{1}$ does not satisfy the hypotheses of Theorem 4 and so we need to do a little more work to compute a subgradient.

Let $(y_{1},\dots,y_{n})$ be the output of Algorithm 9 on input $x=(x_{1},\dots,x_{N})$. Then if $i=N$, $\frac{\partial S_{W}(x)}{\partial x_{i}}={\rm sign}(x_{N}-y_{N})$. Let $M$ be the smallest index such that $y_{M}=k_{M}c_{M}$, where $k_{i}$ is defined in Algorithm 9. There exists a subgradient $g\in\partial S_{W}(x)$ such that

We start with a few reductions. First, we show that by a small perturbation argument we can assume $x_{M}\neq k_{M}c_{M}$. Next, we show that it suffices to prove that $S_{W}$ is linear on a small $L_{\infty}$ ball near $x$. Then we go about proving the Proposition for that $L_{\infty}$ ball, which is the meat of the argument.

Before we start the perturbation argument, we need a couple observations about $M$. First, observe that $k_{i}=y_{i}=0$ for all $i>M$.