Online Learning Without Prior Information

Problem Definition and Prior Work

The case in which we have no bound on either $B$ or $L_{\max}$ is common in practice. A standard pragmatic approach to this lack of information is to simply make a guess for these parameters and then apply an algorithm that uses the guess as input, but this approach is theoretically unsound in online learning, and rather laborious and inelegant in general. We explore lower bounds and algorithms that adapt to the unknown quantities in a principled way in this paper.

Where no information is given, we prove that there is a frontier of matching lower and upper bounds on $R_{T}(u)$ that trades-off a $\|u\|L_{\max}\sqrt{T}\log(\|u\|T)$ term with a $\exp(\max_{t}L_{t}/L_{t-1})$ term along two dimensions, which we parametrize by $k$ and $\gamma$.The square root is missing from the exponential term because we improved the lower bound given in Cutkosky and Boahen (2016) (see Section 3). Along the first dimension, the exponential penalty is reduced to $\exp((L_{t}/L_{t-1})/k^{2})$ for any $k>0$ at the expense of rescaling the regret’s $\sqrt{T}$ term to $k\|u\|L_{\max}\sqrt{T}\log(\|u\|T)$. Along the second dimension, the logarithm’s power in the $\sqrt{T}$ term is reduced to $\|u\|L_{\max}\sqrt{T}\log^{\gamma}(\|u\|T)$ for any $\gamma\in(1/2,1]$ at the expense of increasing the exponential penalty to $\exp((L_{t}/L_{t-1})^{1/(2\gamma-1)})$. We prove the lower bounds by constructing a specific adversarial loss sequence, and we prove the upper bounds by providing a family of algorithms whose regret matches the lower bound frontier for any $k$ and $\gamma$.

Notation and Setup

We will focus all of our lower bounds in Section 3 and algorithms in Section 5 on the case in which the domain $W$ is an entire Hilbert space, so that $W$ has infinite diameter and no boundary. This case is very common in practical optimization optimization problems encountered in machine learning, in which any constraints are often only implicitly enforced via regularization. Our objective is to design lower bounds and algorithms such that $R_{T}(u)$ depends on $\|u\|$, $T$, and $L_{\max}$ without prior knowledge of these parameters.

A Frontier of Lower Bounds

In this section we give our frontier of lower bounds for online optimization without prior information. First we describe our adversarial loss sequence and lower bound frontier along the $k$ dimension, and then we extend the argument to obtain the full two dimensional frontier parametrized by both $k$ and $\gamma$.

The cost that an algorithm pays when faced with the adversarial sequence is stated formally in the following Theorem.

where $L_{t}=\max_{t^{\prime}\leq t}\|g_{t^{\prime}}\|$, and $L_{\max}=L_{T}=\max_{t\leq T}\|g_{t}\|$.

The first inequality in this bound demonstrates that it is impossible to guarantee sublinear regret without prior information while maintaining $O(L_{\max}\|u\|\log(\|u\|))$ dependence on $L_{\max}$ and $\|u\|$,it is possible to guarantee sublinear regret in exchange for $O(L_{\max}\|u\|^{2})$ dependence, see Orabona and Pál (2016b) but the second inequality provides hope that if the loss sequence is limited to small jumps in $L_{t}$, then we might be able to obtain sublinear regret. Specifically, from the first inequality, observe that in order to bring the exponential term to lower than $O(T)$, the value of $k$ needs to be at least $\Omega(\sqrt{T}/\log(T))$, which causes the non-exponential term to become $O(T)$. However, the second inequality emphasizes that our high regret is the result of a large jump in the value of $L_{t}$, so that we might expect to do better if there are no such large jumps. Our upper bounds are given in the form of algorithms that guarantee regret matching the second inequality of this lower bound for any $k$, showing that we can indeed do well without prior information so long as $L_{t}$ does not increase too quickly.

2 Trade-offs in the Logarithmic exponent γ𝛾\gamma

To extend the frontier to the $\gamma$ dimension, we modify our adversarial sequence by setting $g_{T}=O(\gamma k^{1/\gamma}T^{1-1/2\gamma})$ instead of $O(k\sqrt{T})$. This results in a penalty that is exponential in $(\sqrt{T}/k)^{1/\gamma}$, which we express as a multiple of $(L_{t}/\gamma k^{2}L_{t-1})^{1/(2\gamma-1)}$. Since $\gamma\in(1/2,1]$, we are getting a larger exponential penalty even though the adversarial subgradients have decreased in size, illustrating that decreasing the logarithmic factor is very expensive.

The full frontier is stated formally in the following Theorem.

where $L_{t}=\max_{t^{\prime}\leq t}\|g_{t^{\prime}}\|$ and $L_{\max}=L_{T}=\max_{t\leq T}\|g_{t}\|$.

Again, the first inequality tells us that adversarial sequences can always deny the algorithm sublinear regret and the second inequality says that so long as $L_{t}$ grows slowly, we can still hope for sublinear regret. This time, however, the second inequality appears to blow up when $\gamma\to 1/2$. In this case, $L_{\max}=O(k^{2})$ regardless of $T$ and so the value of $L_{t}/L_{t-1}$ is never very large, keeping the exponent in the second inequality less than 1 so that the singularity in the exponent does not send the bound to infinity. This singularity at $\gamma=1/2$ tells us that the adversary does not need to be “very adversarial” in order to force us to experience exponential regret.

To gain some more intuition for what happens at $\gamma=1/2$, consider a model in which the adversary must commit ahead of time to some $L_{\max}$ (which corresponds to picking $k$), unknown to the optimization algorithm, such that $\|g_{t}\|\leq L_{\max}$ for all $t$. When a bound $L_{\text{bound}}\geq L_{\max}$ is known to the algorithm ahead of time, then it is possible to achieve $O(\|u\|L_{\text{bound}}\sqrt{T\log(\|u\|T)})$ regret (e.g. see Orabona and Pál (2016a)). However, note that when $\gamma=1/2$, committing to an appropriate $L_{\max}$ would not prevent an adversary from using the sequence of Theorem 2. Therefore, Theorem 2 tells us that algorithms which achieve $O(\|u\|L_{\text{bound}}\sqrt{T\log(\|u\|T)})$ regret are inherently very fragile because if the bound is incorrect (which happens for large enough $k$), then the adversary can force the algorithm to suffer $L_{\max}\exp(O(T/L_{\max}))$ regret for arbitrarily large $T$.

Continuing with the model in which the adversary must commit to some unknown $L_{\max}$ ahead of time, suppose we are satisfied with $O(\|u\|L_{\max}\sqrt{T}\log^{\gamma}(\|u\|T))$ regret for some $\gamma>1/2$. In this case, after some (admittedly possibly very large) number of iterations, the exponential term in the second inequality no longer grows with $T$, and the adversarial strategy of Theorem 2 is not available because this strategy requires a choice of $L_{\max}$ that depends on $T$. Therefore an algorithm that guarantees regret matching the second inequality for some $k$ and $\gamma$ will obtain an asymptotic dependence on $T$ that is only $\log^{\gamma}(T)\sqrt{T}$.

These lower bounds show that there is a fundamental frontier of tradeoffs the between parameters $\gamma$ and $k$ and the exponential penalty. Now we proceed to derive algorithms that match any point on the frontier without prior information.

Regret Analysis without Information

In this section we provide the tools used to derive algorithms whose regret matches the lower bounds in the previous section. Our algorithms make use of the Follow-the-Regularized-Leader (FTRL) framework, which is an elegant and intuitive way to design online learning algorithms (see Shalev-Shwartz (2011); McMahan (2014) for detailed discussions). After seeing the $t^{th}$ loss of the online learning game, an FTRL algorithm chooses a function $\psi_{t}$ (called a regularizer), and picks $w_{t+1}$ according to:

Careful choice of regularizers is obviously crucial to the success of such an algorithm, and in the following we provide simple conditions on $\psi$ sufficient for FTRL to achieve optimal regret without prior information. Our analysis generalizes many previous works for online learning with unconstrained $W$ (e.g. Orabona (2013, 2014); Cutkosky and Boahen (2016)) in which regret bounds were proved via arduous ad-hoc constructions. Further, our techniques improve the regret bound in the algorithm that does not require prior information of Cutkosky and Boahen (2016). We note that an alternative set of conditions on regularizers was given in Orabona and Pál (2016a) via an elegant reduction to coin-betting algorithms, but this prior analysis requires a known bound on $L_{\max}$.

Our regularizers $\psi_{t}$ take the form $\psi_{t}(w)=\frac{k}{a_{t}\eta_{t}}\psi(a_{t}w)$ for some fixed function $\psi$ and numbers $a_{t}$ and $\eta_{t}$. The value $k$ specifies the corresponding tradeoff parameter in the lower-bound frontier, while the function $\psi$ specifies the value of $\gamma$. The values for $a_{t}$ and $\eta_{t}$ do not depend on $k$ or $\psi$, but are carefully chosen functions of the observed gradients $g_{1},\dots,g_{t}$ that guarantee the desired asymptotics in the regret bound.

Prior analyses of FTRL often make use of strongly-convex regularizers to simplify regret analysis, but it turns out that strongly-convex regularizers cannot match our lower bounds. Fortunately, there is a simple generalization of strong-convexity that will suffice for our purposes. This generalized notion is very similar to a dual version of the “local smoothness” condition used in Orabona (2013). We define this generalization of strong-convexity below.

We’ll usually just write $\sigma$-strongly convex instead of $\sigma(\cdot,\cdot)$-strongly convex since our definition is purely a generalization of the standard one. We will also primarily make use of the special case $\sigma(w,z)=\min(\sigma(w),\sigma(z))$.

2 Adaptive regularizers

Now we present a few definitions that will allow us to easily construct sequences of regularizers that achieve regret bounds without information. Intuitively, we require that our regularizers $\psi_{t}$ grow super-linearly in order to ensure that $\psi_{t}(w)+g_{1:t}w$ always has a minimal value. However, we do not want $\psi_{t}$ to grow quadratically because this will result in $O(\|u\|^{2})$ regret. The formal requirements on the shape of $\psi_{t}$ are presented in the following definition:

For any $C$, there exists a $B$ such that $\psi(x)\sigma(x)\geq C$ for all $\|x\|\geq B$.

is called a $(\sigma,\|\cdot\|)$-adaptive regularizer. We also define the useful auxiliary function $h(w)=\psi(w)\sigma(w)$ and by mild abuse of notation, we define $h^{-1}(x)=\max_{h(w)\leq x}\|w\|$.

We will use adaptive regularizers as building blocks for our FTRL regularizers $\psi_{t}$, so it is important to have examples of such functions. We will provide some tools for finding adaptive regularizers in Section 5, but to keep an example in mind for now, we remark that $\psi(w)=(\|w\|+1)\log(\|w\|+1)-\|w\|$ is a $\left(\frac{1}{\|\cdot\|+1},\|\cdot\|\right)$-adaptive regularizer where $\|\cdot\|$ is the $L_{2}$ norm.

The following definition specifies the sequences $\eta_{t}$ and $a_{t}$ which we use to turn an adaptive regularizer into the regularizers used for our FTRL algorithms:

Let $\|\cdot\|$ be a norm and $\|\cdot\|_{\star}$ be the dual norm ($\|x\|_{\star}=\sup_{\|y\|=1}x\cdot y$). Let $g_{1},\dots,g_{T}$ be a sequence of subgradients and set $L_{t}=\max_{t^{\prime}\leq t}\|g_{t}\|_{\star}$. Define the sequences $\frac{1}{\eta_{t}}$ and $a_{t}$ recursively by:

Suppose $\psi$ is a $(\sigma,\|\cdot\|)$-adaptive regularizer and $k>0$. Define

Now without further ado, we give our regret bound for FTRL using these regularizers.

Suppose $\psi$ is a $(\sigma,\|\cdot\|)$-adaptive regularizer and $g_{1},\dots,g_{T}$ is some arbitrary sequence of subgradients. Let $k\geq 1$, and let $\psi_{t}$ be defined as in Definition 5.

Then FTRL with regularizers $\psi_{t}$ achieves regret

This bound consists of three terms, the first of which will correspond to the $\sqrt{T}$ term in our lower bounds and the last of which will correspond to the exponential penalty. The middle term is a constant independent of $u$ and $T$. To unpack a specific instantiation of this bound, consider the example adaptive regularizer $\psi(w)=(\|w\|+1)\log(\|w\|+1)-\|w\|$. For this choice of $\psi$, we have $\psi(2uT)/\sqrt{2T}=O(\|u\|\sqrt{T}\log(T\|u\|+1))$ so that the first term in the regret bound matches the $\sqrt{T}$ term in our lower bound with $\gamma=1$. Roughly speaking, $h(w)\approx\log(w)$, so that $h^{-1}(x)\approx\exp(x)$ and the quantity $D=\max_{t}\frac{L_{t-1}^{2}}{(\|g\|_{\star}^{2})_{1:t-1}}h^{-1}\left(\frac{5L_{t}}{k^{2}L_{t-1}}\right)$ matches the exponential penalty in our lower bound. In the following section we formalize this argument and exhibit a family of adaptive regularizers that enable us to design algorithms whose regret matches any desired point on the lower bound frontier.

Optimal Algorithms

In this section we construct specific adaptive regularizers in order to obtain optimal algorithms using our regret upper bound of Theorem 6. The results in the previous section hold for arbitrary norms, but from this point on we will focus on the $L_{2}$ norm. Our regret upper bound expresses regret in terms of the function $h^{-1}$. Inspection of the bound shows that if $h^{-1}(x)$ is exponential in $x^{1/(2\gamma-1)}$, and $\psi(w)=O(\|w\|\log^{\gamma}(\|w\|+1))$, then our upper bound will match (the second inequality in) our lower bound frontier. The following Collary formalizes this observation.

If $\psi$ is an $(\sigma,\|\cdot\|)$-adaptive regularizer such that

then for any $k\geq 1$, FTRL with regularizers $\psi_{t}(w)=\frac{k}{a_{t}\eta_{t}}\psi(a_{t}w)$ yields regret

We call regularizers that satisfy these conditions $\gamma$-optimal.

With this Corollary in hand, to match our lower bound frontier we need only construct a $\gamma$-optimal adaptive regularizer for all $\gamma\in(1/2,1]$. Constructing adaptive regularizers is made much simpler with Proposition 8 below. This proposition allows us to design adaptive regularizers in high dimensional spaces by finding simple one-dimensional functions. It can be viewed as taking the place of arguments in prior work (McMahan and Orabona, 2014; Orabona and Pál, 2016a; Cutkosky and Boahen, 2016) that reduce high dimensional problems to one-dimensional problems by identifying a “worst-case” direction for each subgradient $g_{t}$.

Let $\|\cdot\|$ be the $L_{2}$ norm $(\|w\|=\|w\|_{2}=\sqrt{w\cdot w})$. Let $\phi$ be a three-times differentiable function from the non-negative reals to the reals that satisfies

$\lim_{x\to\infty}\phi(x)\phi^{\prime\prime}(x)=\infty$.

Then $\psi(w)=\phi(\|w\|)$ is a $(\phi^{\prime\prime}(\|\cdot\|),\|\cdot\|)$-adaptive regularizer.

Now we are finally ready to derive our first optimal regularizer:

Let $\|\cdot\|$ be the $L_{2}$ norm. Let $\phi(x)=(x+1)\log(x+1)-x$. Then $\psi(w)=\phi(\|w\|)$ is a $1$-optimal, $(\phi^{\prime\prime}(\|\cdot\|),\|\cdot\|)$-adaptive regularizer.

We can use Proposition 8 to prove this with a few simple calculations:

Now the conclusion of the Proposition is immediate from Proposition 8 and inspection of the above equations.

A simple application of Corollary 7 shows that FTRL with regularizers $\psi_{t}(w)=\frac{k}{\eta_{t}}((\|w\|+1)\log(\|w\|+1)-\|w\|)$ matches our lower bound with $\gamma=1$ for any desired $k$.

In fact, the result of Proposition 9 is a more general phenomenon:

Let $\|\cdot\|$ be the $L_{2}$ norm. Given $\gamma\in(1/2,1]$, set $\phi(x)=\int_{0}^{x}\log^{\gamma}(z+1)\ dz$. Then $\psi(w)=\phi(\|w\|)$ is a $\gamma$-optimal, $(\phi^{\prime\prime}(\|\cdot\|),\|\cdot\|)$-adaptive regularizer.

Since $\gamma\leq 1$, $\phi^{\prime\prime\prime}(x)\leq 0$ and so $\phi$ satisfies the first four conditions of Proposition 8. It remains to characterize $\phi(x)$ and $\phi(x)\phi^{\prime\prime}(x)$, which we do by finding lower and upper bounds on $\phi(x)$:

where the inequality follows since $\frac{x}{x+1}\leq\log(x+1)$, which can be verified by differentiating both sides. Therefore $\phi(x)\geq\frac{1}{2}x\log^{\gamma}(x+1)$. This lower-bound implies

which gives us the last condition in Proposition 8, as well as the first condition for $\gamma$-optimality.

This implies $\phi(x)\leq x\log(x+1)$ which gives us the second condition for $\gamma$-optimality.

Thus, by applying Theorem 6 to the regularizers of Proposition 10, we have a family of algorithms that matches our family of lower-bounds up to constants. The updates for these regularizers are extremely simple:

The guarantees of Theorem 6 do not make any assumptions on how $k$ is chosen, so that we could choose $k$ using prior knowledge if it is available. For example, if a bound on $L_{t}/L_{t-1}$ is known, we can set $k\geq\sqrt{\max_{t}L_{t}/L_{t-1}}$. This reduces the exponentiated quantity $\max_{t}L_{t}/k^{2}L_{t-1}$ to a constant, leaving a regret of $O(\|u\|\log(T\|u\|+1)L_{\max}\sqrt{T\max_{t}L_{t}/L_{t-1}})$. This bound holds without requiring a bound on $L_{\max}$. Thus our algorithms open up an intermediary realm in which we have no bounds on $\|u\|$ or $L_{\max}$, and yet we can leverage some other information to avoid the exponential penalty.

FreeRex

Now we explicitly describe an algorithm, along with a fully worked-out regret bound. The norm $\|\cdot\|$ used in the following is the $L_{2}$ norm ($\|w\|=\sqrt{w\cdot w}$), and our algorithm uses the adaptive regularizer $\psi(w)=(\|w\|+1)\log(\|w\|+1)-\|w\|$. Similar calculations could be performed for arbitrary $\gamma$ using the regularizers of Proposition 10, but we focus on the $\gamma=1$ because it allows for simpler and tighter analysis through our closed-form expression for $\psi$. Since we do not require any information about the losses, we call our algorithm FreeRex for Information-free Regret via exponential updates.

The regret of FreeRex (Algorithm 1) is bounded by

Define $\phi(x)=(x+1)\log(x+1)-x$. Then $\psi(w)=(\|w\|+1)\log(\|w\|+1)-\|w\|$ is a $(\phi^{\prime\prime}(\|\cdot\|),\|\cdot\|)$-adaptive regularizer by Proposition 9. Therefore we can immediately apply Theorem 6 to obtain

where we’ve defined $\phi^{\prime\prime}_{\text{min}}=\inf_{\|w\|\leq h^{-1}(10/k^{2})}k\phi^{\prime\prime}(\|w\|)$.

From Proposition 19 (part 2) we have $\frac{1}{\eta_{T}}\leq\sqrt{2\|g\|^{2}_{1:T}+L_{\max}\max_{t\leq T}\|g_{1:t}\|}$. We also have $(\|w\|+1)\log(\|w|+1)-\|w\|=\|w\|\log(\|w\|+1)+\log(\|w\|+1)-\|w\|\leq\|w\|\log(\|w\|+1)$, so we are left with

Now it remains to bound $h^{-1}(10/k^{2})$ and $D$. From our expression for $h$, we have

Substituting the value $Q_{T}=2\frac{\|g\|_{1:T}}{L_{\max}}$, we conclude

From which the result follows by substituting in our expression for $D$.

As a specific example, for $k=\sqrt{5}$ we numerically evaluate the bound to get

Conclusions

We have presented a frontier of lower bounds on the worst-case regret of any online convex optimization algorithm without prior information. This frontier demonstrates a fundamental trade-off at work between $kuL_{\max}\log^{\gamma}(Tu+1)$ and $\exp\left[\left(\max_{t}\frac{L_{t}}{\gamma k^{2}L_{t-1}}\right)^{\frac{1}{2\gamma-1}}\right]$ terms. We also present some easy-to-use theorems that allow us to construct algorithms that match our lower bound for any chosen $k$ and $\gamma$. Note that by virtue of not requiring prior information, our algorithms are nearly hyperparameter-free. They only require the essentially unavoidable trade-off parameters $k$ and $\gamma$. Since our analysis does not make assumptions about the loss functions or comparison point $u$, the parameters $k$ and $\gamma$ can be freely chosen by the user. Unlike other algorithms that require $\|u\|$ or $L_{\max}$, there are no unknown constraints on these parameters.

Although we answer some important questions, there is still much to do in online learning without prior information. For example, it is possible to obtain $O(\|u\|^{2}L_{\max}\sqrt{T})$ regret without prior information (Orabona and Pál, 2016b), so it should be possible to extend our lower-bound frontier beyond $\|u\|\log(\|u\|)$. Further, it would be valuable to further characterize the conditions for which the adversary can guarantee regret that is exponential in $T$. We showed that one such condition is that there must be a large jump in the value of $L_{t}$, but there may very well be others. Fully characterizing these conditions should allow us design algorithms that smoothly interpolate between “nice” environments that do not satisfy the conditions and fully adversarial ones that do.

Finally, while our analysis allows for the use of arbitrary norms, we focus our examples on the $L_{2}$ norm. It may be interesting to design adaptive regularizers with respect to a more diverse set of norms, or to extend our theory to encompass time-changing norms.

References

Appendix A Lower Bound Proof

Before getting started, we need one technical observation:

and set $r_{t}=Z_{t}-Z_{t-1}$. Then for all sufficiently large $T$,

For sufficiently large $T$, this quantity is positive and increasing in $T$. Therefore for sufficiently large $T$,

where the third inequality holds only for sufficiently large $T$.

Now we prove Theorem 2, restated below. Theorem 1 is an immediate consequence of Theorem 2, so we do not prove it seperately. See 2

Let $S_{n}=\sum_{t=1}^{n}\hat{w}_{t}$. Let $Z_{t}=\frac{t^{1-1/2\gamma}}{2t}\left[\exp\left(\frac{t^{1/2\gamma}}{(4k)^{1/\gamma}}\right)-1\right]$, and set $r_{t}=Z_{t}-Z_{t-1}$ Suppose $T_{1}>T_{0}$ is such that

For all $t_{1}>t_{2}>T_{1}$, $Z_{t_{1}}>Z_{t_{2}}$.

For all $t>T_{1}$, $r_{t}\geq\frac{Z_{t-1}}{3\gamma(4k)^{1/\gamma}(t-1)^{1-1/2\gamma}}$ (by Proposition 12).

We consider the quantity $\liminf_{n\to\infty}\frac{S_{n}}{Z_{n}}$. There are two cases, either the $\liminf$ is less than 1, or it is not.

Case 1: $\liminf_{n\to\infty}\frac{S_{n}}{Z_{n}}<1$

Set $u=\frac{1}{T}\left[\exp\left(\frac{T^{1/2\gamma}}{(4k)^{1/\gamma}}\right)-1\right]$. Then clearly

Now observe that we have chosen $u$ carefully so that

where we have used $L_{\max}=1$ to insert factors of $L_{\max}$ where appropriate.

Observing that $L_{t}/L_{t-1}=1$ for all $t$, we can also easily conclude (using properties 3 and 5 of $T_{1}$):

Case 2: $\liminf_{n\to\infty}\frac{S_{n}}{Z_{n}}\geq 1$

By definition of $\liminf$, there exists some $T_{2}>T_{1}$ and $Q\geq 1$ such that $S_{T_{2}}\leq\frac{3}{2}QZ_{T_{2}}$ and for all $t>T_{2}$, $S_{t}>\frac{3Q}{4}Z_{t}$.

Suppose for contradiction that $\hat{w}_{t}\leq\frac{Q}{2}r_{t}$ for all $t>T_{2}$. Then for all $T>T_{2}$,

Since the second term does not depend on $T$, this implies that for sufficiently large $T$, $\frac{S_{T}}{Z_{T}}\leq\frac{3}{4}QZ_{T}$, which contradicts our choice of $T_{2}$. Therefore $\hat{w}_{t}>\frac{Q}{2}r_{t}$ for some $t>T_{2}$.

Let $T$ be the the smallest index $T>T_{2}$ such that $\hat{w}_{T}>\frac{Q}{2}r_{T}$. Since $\hat{w}_{t}\leq\frac{Q}{2}r_{t}$ for $t<T$, we have

where we have used property 1 of $T_{1}$ to conclude $Z_{T_{2}}\leq Z_{T-1}$.

where we have used $Q\geq 1$ in the last line. Now we use the fact that $L_{\max}=18\gamma(4k)^{1/\gamma}(T-1)^{1-1/2\gamma}$ (by property 6 of $T_{1}$) to write

where we have used the fourth assumption on $T_{1}$ in the last line.

Since we are considering $u=0$, we can always insert arbitrary multiples of $u$:

Now we relate the quantity in the exponent to $L_{t}/L_{t-1}$. We have $L_{T}=g_{T}$ and $L_{T-1}=1$ so that

Now observe that $\frac{1}{T-1}=\frac{L_{T-1}^{2}}{\sum_{t=1}^{T-1}\|g_{t}\|^{2}}$ so that we have

Further, since $\frac{1}{t-1}=\frac{L_{t-1}^{2}}{\sum_{t^{\prime}=1}^{t-1}\|g_{t^{\prime}}\|^{2}}$ for all $t\leq T$, condition 5 on $T_{1}$ tells us that

Therefore we can put everything together to get

Appendix B FTRL regret

We prove a general bound on the regret of FTRL. Our bound is not fundamentally tighter than the many previous analyses of FTRL, but we decompose the regret in a new way that makes our analysis much easier. We make use of “shadow regularizers”, $\psi^{+}_{t}$ that can be used to characterize regret more easily. Our bound bears some similarity in form to the adaptive online mirror descent bound of (Orabona et al., 2014) and the analysis of FTRL with varying regularizers of (Cutkosky and Boahen, 2016).

We define $X_{t}=w^{+}_{t+2}$ for $t<T$ and $X_{T}=u$. We’ll use the symbols $X_{t}$ as intermediate variables in our proof in an attempt to keep the algebra cleaner. By definition of $w^{+}_{t+1}$, for all $t\leq T$ we have

Summing this inequality across all $t$ we have

Now we substitute our values of $X_{t}=w^{+}_{t+2}$ for $t<T$ and $X_{T}=u$ to obtain

Appendix C Facts About Strong Convexity

In this section we prove some basic facts about our generalized strong convexity.

$\psi+f$ is $\sigma$-strongly convex for any convex function $f$.

$c\psi$ is $c\sigma$-strongly convex for any $c\geq 0$.

Suppose $c\geq 0$ and $\phi(w)=\psi(cw)$. Let $\sigma^{\prime}(x,y)=\sigma(cx,cy)$. Then $\phi$ is $c^{2}\sigma^{\prime}$-strongly convex.

Let $x,y\in W$ and let $g\in\partial\psi(x)$ and $b\in\partial f(x)$. Then $g+b\in\partial(\psi+f)(x)$. By convexity and strongly convexity respectively we have:

so that adding these equations shows that $\psi+f$ is $\sigma$-strongly convex.

This follows immediately by multiplying the defining equation for strong convexity of $\psi$ by $c$.

Let $x,y\in W$ and let $g\in\partial\psi(cx)$. Then $cg\in\partial\phi(x)$.

Note that for any linear function $f(w)=g\cdot w$, if $\psi$ is $\sigma$-strongly convex, then $\psi+f$ is also $\sigma$-strongly convex.

We show that the following lemma from (McMahan, 2014) about strongly-convex functions continues to hold under our more general definition. The proof of this lemma (and the next) are identical to the standard ones, but we include them here for completeness.

Suppose $A$ and $B$ are arbitrary convex functions such that $A+B$ is $\sigma$-strongly convex. Let $w_{1}=\mathop{\text{argmin}}A$ and $w_{2}=\mathop{\text{argmin}}A+B$ and let $g\in\partial B(w_{1})$. Then

Since $w_{2}\in\mathop{\text{argmin}}A+B$, we have $0\in\partial(A+B)(w_{2})$ and so by definition of strong convexity we have

Now let $g\in\partial B(w_{1})$. Consider the function $\hat{A}(w)=A(w)+B(w)-\langle g,w\rangle$. Then we must have $0\in\partial\hat{A}(w_{1})$ and so by strong-convexity again we have

Finally, we have an analog of a standard way to check for strong-convexity:

Appendix D Proof of Theorem 8

First we prove a proposition that allows us to generate a strongly convex function easily:

Where the last line follows since $\frac{\phi^{\prime}(x)}{x}\geq\phi^{\prime\prime}(x)$ for all $x\geq 0$. Since $\phi^{\prime\prime\prime}(x)\leq 0$, $\phi^{\prime\prime}(x)$ is always decreasing for positive $x$ and so we have

for all $t\in$. Therefore we can apply Proposition 16 to conclude that $\psi$ is $\phi^{\prime\prime}(\|w\|)$-strongly convex.

Now we prove Proposition 8, restated below: See 8

It’s clear that $\psi(0)=0$ so the first condition for being an adaptive regularizer is satisfied.

Next we will show that $\frac{\phi^{\prime}(x)}{x}\geq\phi^{\prime\prime}(x)$ so that we can apply Proposition 17. It suffices to show

Clearly this identity holds for $x=0$. Differentiating the right-hand-side of the equation, we have

since $\phi^{\prime\prime\prime}(x)\leq 0$ and $x\geq 0$. Thus $\phi^{\prime}(x)-x\phi^{\prime\prime}(x)$ is non-decreasing and so must always be non-negative.

Therefore, by Proposition 17, $\psi$ is $(\phi^{\prime\prime}(\|\cdot\|),\|\cdot\|)$-strongly convex. Also, since $\phi^{\prime\prime\prime}(x)\leq 0$, $\phi^{\prime\prime}(\|x\|)\leq\phi^{\prime\prime}(\|y\|)$ when $\|x\|\geq\|y\|$ so that $\psi$ satisfies the second condition for being an adaptive regularizer.

Finally, observe that $\lim_{x\to\infty}\phi(x)\phi^{\prime\prime}(x)$ implies by definition that for any $C$ there exists a $B$ such that $\phi(x)\phi^{\prime\prime}(x)\geq C$ whenever $x\geq B$. Therefore we immediately see that $\psi(x)\phi^{\prime\prime}(\|x\|)\geq C$ for all $\|x\|\geq B$ so that the third condition is satified.

Appendix E Proof of Theorem 6

First we define new regularizers $\psi_{t}^{+}$ analagously to $\psi_{t}$ that we will use in conjunction with Theorem 13:

Given a norm $\|\cdot\|$ and a sequence of subgradients $g_{1},\dots,g_{T}$, define $L_{t}$ and $\frac{1}{\eta_{t}}$ as in Definition 5, and define $L_{0}=L_{1}$. We define $\frac{1}{\eta_{t}^{+}}$ recursively by:

Further, given a $k\geq 1$ and a non-decreasing sequence of positive numbers $a_{t}$, define $\psi_{t}^{+}$ by:

Throughout the following arguments we will assume $\eta_{t}$ and $\eta_{t}^{+}$ are the sequences defined in Definitions 5 and 18.

The next proposition establishes several identities that we will need in proving our bounds.

Suppose $\psi$ is a $(\sigma,\|\cdot\|)$-adaptive regularizer, and $g_{1},\cdots,g_{T}$ be some sequence of subgradients. Then the following identities hold:

Let $\hat{\psi}$ be such that $\hat{\psi}(a_{t-1}w)=\psi(a_{t-1}w)$ for $w\in W$ and $\hat{\psi}(a_{t-1}w)=\infty$ for $w\notin W$. There exists some subgradient of $\hat{\psi}$ at $a_{t-1}w_{t}$, which with mild abuse of notation we call $\nabla\psi(a_{t-1}w_{t})$, such that:

Let $\hat{\psi}$ be such that $\hat{\psi}(a_{t-1}w)=\psi(a_{t-1}w)$ for $w\in W$ and $\hat{\psi}(a_{t-1}w)=\infty$ for $w\notin W$. Then we can write $w_{t}=\mathop{\text{argmin}}_{w\in W}\frac{k}{a_{t-1}\eta_{t-1}}\psi(a_{t-1}w)+g_{1:t-1}\cdot w=\mathop{\text{argmin}}\frac{k}{a_{t-1}\eta_{t-1}}\hat{\psi}(a_{t-1}w)+g_{1:t-1}$. From this it follws that there is some subgradient of $\hat{\psi}$ at $a_{t-1}w_{t}$, which we refer to (by mild abuse of notation) as $\nabla\hat{\psi}(a_{t-1}w_{t})$ such that

Note that we must appeal to a subgradient rather than the actual gradient in order to encompass the case that $a_{t-1}w_{t}$ is on the boundary of $W$.

Now we are ready to prove the various parts of the Proposition.

By definition of $\eta_{t-1}$ and $\eta^{+}_{t}$ we have

where in the last line we used the fact that $\eta^{+}_{t}\leq\eta_{t-1}$ to conclude that $1+\frac{\eta^{+}_{t}}{\eta_{t-1}}\leq 2$.

For the other direction, we have two cases:

$\frac{1}{(\eta^{+}_{t})^{2}}=\frac{1}{(\eta_{t-1})^{2}}+2\|g_{t}\|_{\star}\min(\|g_{t}\|_{\star},L_{t-1})$.

$\frac{1}{(\eta^{+}_{t})^{2}}=L_{t-1}\|g_{1:t}\|_{\star}$.

Case 1 $\frac{1}{(\eta^{+}_{t})^{2}}=\frac{1}{(\eta_{t-1})^{2}}+2\|g_{t}\|_{\star}\min(\|g_{t}\|_{\star},L_{t-1})$:

where in the last line we used the fact that $1+\frac{\eta^{+}_{t}}{\eta_{t-1}}\geq 1$.

Case 2 $\frac{1}{(\eta^{+}_{t})^{2}}=L_{t-1}\|g_{1:t}\|_{\star}$:

Now we follow the exact same argument as in Case 1 to show $\frac{1}{\eta^{+}_{t}}-\frac{1}{\eta_{t-1}}\leq L_{t-1}\|g_{t}\|_{\star}\eta^{+}_{t}$, which proves the desired result.

We proceed by induction for both claims. The statements are clear for $\frac{1}{\eta_{1}}=\sqrt{2}\|g_{1}\|_{\star}$. Suppose

Then observe that $\frac{1}{\eta_{t}^{2}}+2\|g_{t+1}\|_{\star}^{2}\leq 2L_{t+1}(\|g\|_{\star})_{1:t+1}$ by the induction hypothesis, and $L_{t+1}\|g_{1:t+1}\|_{\star}\leq 2L_{t+1}(\|g\|_{\star})_{1:t+1}$. Therefore $\frac{1}{\eta_{t+1}}\leq\sqrt{2L_{t+1}(\|g\|_{\star})_{1:t+1}}$, proving the first claim.

The induction step for the second claim follows from the observations:

so that $\frac{1}{\eta_{t+1}}\leq\sqrt{2(\|g\|_{\star}^{2})_{1:t+1}+L_{\max}\max_{t^{\prime}\leq t+1}\|g_{1:t^{\prime}}\|_{\star}}$ as desired.

Let $I_{a_{t-1}W}(w)$ be the indicator of the set $a_{t-1}W$ - $I_{a_{t-1}W}(a_{t-1}w)=0$ if $w\in W$ and $\infty$ otherwise. Observe that $\hat{\psi}(w)=\psi(w)+I_{a_{t-1}W}(w)$. Observe that $\hat{\psi}(w)=I_{a_{t-1}W}(w)+\psi(w)$.

Now the third equation follows from Lemma 15, setting $A(w)=I_{a_{t-1}W}(w)+\frac{k}{a_{t-1}\eta_{t-1}}\psi(w)+\frac{g_{1:t-1}}{a_{t-1}}\cdot w$ and $B(w)=I_{a_{t-1}W}(w)+\frac{g_{t}}{a_{t-1}}\cdot w+\left(\frac{1}{a_{t-1}\eta^{+}_{t}}-\frac{k}{a_{t-1}\eta_{t-1}}\right)\psi(w)$. Then by inspection of the definitions of $w_{t}$ and $w^{+}_{t+1}$, we have $a_{t-1}w_{t}=\mathop{\text{argmin}}A$ and $a_{t-1}w^{+}_{t+1}=\mathop{\text{argmin}}A+B$. Further, by Corollary 14, $A+B$ is $\frac{k\sigma}{a_{t-1}\eta^{+}_{t}}$-strongly convex. We can re-write $A$ and $B$ in terms of $\hat{\psi}$ by simply replacing the $\psi$s with $\hat{\psi}$s and removing the $I_{a_{t-1}W}$s. Now we use the facts noted at the beginning of the proof:

Applying these identities with Lemma 15 we have:

And we divide by $a_{t-1}$ to conclude the desired identity.

Using the already-proved parts 1 and 3 of this Proposition and definition of dual norm, we have

The fifth part of the Proposition follows directly from part 3 by the definition of dual norm.

Case 1 $\frac{1}{(\eta^{+}_{t})^{2}}=\frac{1}{(\eta_{t-1})^{2}}+2\|g_{t}\|_{\star}\min(\|g_{t}\|_{\star},L_{t-1})$: In this case we have

Case 2 $\frac{1}{(\eta^{+}_{t})^{2}}=L_{t-1}\|g_{1:t}\|_{\star}$:

Suppose $\psi$ a $(\sigma,\|\cdot\|)$-adaptive regularizer and $g_{1},\cdots,g_{T}$ is some sequence of subgradients. We use the terminology of Definition 5. Recall that we define $h(w)=\psi(w)\sigma(w)$ and $h^{-1}(x)=\max_{h(w)\leq x}\|w\|$. Suppose either of the follow holds:

$\|w^{+}_{t+1}\|\geq\frac{h^{-1}\left(2\frac{L_{t}}{k^{2}L_{t-1}}\right)}{a_{t-1}}$ and $\|w^{+}_{t+1}\|\geq\|w_{t}\|$.

$\|w_{t}\|\geq\frac{h^{-1}\left(5\frac{L_{t}}{k^{2}L_{t-1}}\right)}{a_{t-1}}$ and $\|w_{t}\|\geq\|w^{+}_{t+1}\|$.

As in Proposition 19, we use $\nabla\psi(x)$ to simply mean some particular subgradient of $\psi$ at $x$.

Case 1: $\|w^{+}_{t+1}\|\geq\frac{h^{-1}\left(2\frac{L_{t}}{k^{2}L_{t-1}}\right)}{a_{t-1}}$ and $\|w^{+}_{t+1}\|\geq\|w_{t}\|$:

By definition of adaptive regularizer (part 2), we must have $\sigma(a_{t-1}w^{+}_{t+1})\leq\sigma(a_{t-1}w_{t})$ since $\|w^{+}_{t+1}\|\geq\|w_{t}\|$. Therefore $\sigma(a_{t-1}w^{+}_{t+1},a_{t-1}w_{t})=\sigma(a_{t-1}w^{+}_{t+1})$.

By definition of $h$, when $\|w^{+}_{t+1}\|\geq\frac{h^{-1}\left(2\frac{L_{t}}{k^{2}L_{t-1}}\right)}{a_{t-1}}$ we can apply Proposition 19 (parts 1 and 5) to obtain

We remark that in the calculations above, we showed

Case 2 $\|w_{t}\|\geq\frac{h^{-1}\left(5\frac{\|g_{t}\|_{\star}}{k^{2}L_{t-1}}\right)}{a_{t-1}}$, and $\|w_{t}\|\geq\|w^{+}_{t+1}\|$:

Again, by definition of adaptive regularizer (part 2), we must have $\sigma(a_{t-1}w^{+}_{t+1})\geq\sigma(a_{t-1}w_{t})$ since $\|w^{+}_{t+1}\|\leq\|w_{t}\|$. Therefore $\sigma(a_{t-1}w^{+}_{t+1},a_{t-1}w_{t})=\sigma(a_{t-1}w_{t})$. Let $\hat{\psi}$ be as in Proposition 19 part 4. Oberve that $w_{t+1}^{+}$ and $w_{t}$ are both in $W$, so that we have $\psi(a_{t-1}w^{+}_{t+1})=\hat{\psi}(a_{t-1}w^{+}_{t+1})$ and $\psi(a_{t-1}w_{t})=\hat{\psi}(a_{t-1}w_{t})$. Then we have:

Now by definition of $h$, when $\|w_{t}\|\geq\frac{h^{-1}(5\frac{L_{t}}{k^{2}L_{t-1}})}{a_{t-1}}$ we have

The next theorem is a general fact about adaptive regularizers that is useful for controlling $\psi^{+}_{t}-\psi_{t}$:

Let’s differentiate: $\frac{d}{da}\frac{\psi(aw)}{a}=\frac{\nabla\psi(aw)\cdot w}{a}-\frac{\psi(aw)}{a^{2}}$. Thus it suffices to show

But this follows immediately from the definition of subgradient, since $\psi(0)=0$.

Suppose $\psi$ is a $(\sigma,\|\cdot\|)$-adaptive regularizer and $g_{1},\dots,g_{T}$ is an arbitrary sequence of subgradients (possibly chosen adaptively). Using the terminology of Definition 5,

This follows from the fact that $a_{t-1}\leq a_{t}$, and property 4 of an adaptive regularizer ($\psi(ax)/a$ is a non-decreasing function of $a$). By Proposition 19 (part 1), we have $\frac{1}{\eta^{+}_{t}}\leq\frac{1}{\eta_{t}}$. Therefore:

Suppose $\psi$ is a $(\sigma,\|\cdot\|)$-adaptive regularizer and $g_{1},\dots,g_{T}$ is an arbitrary sequence of subgradients (possibly chosen adaptively). We use the regularizers of Definition 5. Recall that we define $h(w)=\psi(w)\sigma(w)$ and $h^{-1}(x)=\mathop{\text{argmax}}_{h(w)\leq x}\|w\|$. Define