Keyi Chen<EMAIL_ADDRESS>
Department of Computer Science, Boston University, Boston, MA, USA
Ashok Cutkosky<EMAIL_ADDRESS>
Francesco Orabona<EMAIL_ADDRESS>
Department of Electrical & Computer Engineering, Boston University, Boston,
MA, USA

# Implicit Parameter-free Online Learning with Truncated Linear Models

###### Abstract

Parameter-free algorithms are online learning algorithms that do not require
setting learning rates. They achieve optimal regret with respect to the
distance between the initial point and _any_ competitor. Yet, parameter-free
algorithms do not take into account the geometry of the losses. Recently, in
the stochastic optimization literature, it has been proposed to instead use
_truncated_ linear lower bounds, which produce better performance by more
closely modeling the losses. In particular, truncated linear models greatly
reduce the problem of overshooting the minimum of the loss function.
Unfortunately, truncated linear models cannot be used with parameter-free
algorithms because the updates become very expensive to compute. In this
paper, we propose new parameter-free algorithms that can take advantage of
truncated linear models through a new update that has an “implicit” flavor.
Based on a _novel decomposition of the regret_ , the new update is efficient,
requires only one gradient at each step, never overshoots the minimum of the
truncated model, and retains the favorable parameter-free properties. We also
conduct an empirical study demonstrating the practical utility of our
algorithms.

###### keywords:

Online convex optimization, Regret, Truncated linear models, Parameter-free

##  1 Introduction

In this paper, we study Online Convex Optimization (OCO) (Gordon, 1999;
Zinkevich, 2003). In this setting, for each of $T$ steps, a learner produces a
prediction $\boldsymbol{w}_{t}\in V$ in each step $t$, where
$V\subseteq\mathbb{R}^{d}$ is the feasible convex set. After each prediction,
an adversary reveals a convex loss function $\ell_{t}:V\to\mathbb{R}$ and the
learner pays $\ell_{t}(\boldsymbol{w}_{t})$. The aim of the learner is to
minimize its _regret_ with respect to any fixed prediction $\boldsymbol{u}\in
V$, defined as

$\operatorname{Regret}_{T}(\boldsymbol{u})\triangleq\sum_{t=1}^{T}\ell_{t}(\boldsymbol{w}_{t})-\sum_{t=1}^{T}\ell_{t}(\boldsymbol{u})~{}.$

Depending on the assumptions on the feasible set and the losses, there are
many OCO algorithms that achieve optimal regret. The two main families of OCO
algorithms are based on Online Mirror Descent (OMD) (Nemirovsky and Yudin,
1983; Warmuth and Jagota, 1997) and Follow-The-Regularized-Leader (FTRL)
(Shalev-Shwartz, 2007; Abernethy et al., 2008b; Hazan and Kale, 2008). For the
particular case where $V\equiv\mathbb{R}^{d}$, _parameter-free_ algorithms are
minimax optimal (Orabona and Pál, 2016; Cutkosky and Orabona, 2018). The key
feature of parameter-free algorithms is that the
$\operatorname{Regret}_{T}(\boldsymbol{u})$ scales nearly linearly in
$\|\boldsymbol{u}\|$, and is _constant_ for $\boldsymbol{u}=0$. This guarantee
is only obtainable by popular strategies like Online Subgradient Descent
(Zinkevich, 2003) if the learning rate is carefully tuned to the (unknown!)
value of $\|\boldsymbol{u}\|$. This lack of tuning learning rates motivates
the name “parameter-free”. Yet, even this favorable minimax optimality might
not be satisfactory.

In particular, most OCO algorithms simply approximate the losses using linear
functions, ignoring their geometry. This approach is justified by the fact
that the worst-case losses are indeed just linear ones. However, in the
extremely common case that the losses are not actually linear, that is they
are not worst-case, the algorithm is wasting potentially useful information.
More generally, too much focus on worst-case analyses and asymptotic rates can
prevent the design of better algorithms.

In an effort to address this issue and go beyond focusing only on asymptotic
rates, Asi and Duchi (2019) have proposed the use of _truncated linear models_
instead of linear models to obtain better stochastic Mirror Descent algorithms
with negligible additional computational complexity. Truncated linear models
are tighter lower bounds to the original function that do not require
additional curvature while still yielding a closed form update for Mirror
Descent algorithms. For example, a common issue with standard gradient descent
methods is that they can _overshoot_ the minimum of the loss during any given
iteration. The use of truncated linear models significantly mitigates this
concern by providing a “signal” that gradient descent might overshoot,
allowing the learning algorithm to take a more conservative step. The same
idea can be applied to the online (rather than stochastic) setting, but only
for OMD. It is unknown how to use truncated linear models in parameter-free
algorithms without having an explosion in the computational time.

$x$$f(x)$ Figure 1: Coin-Betting with truncated linear models (Red), Coin-
Betting with linear models (Green), OGD with large constant stepsizes (Grey),
and OGD with small constant stepsizes (Black).

In this work, we propose new parameter-free algorithms that are able to take
advantage of truncated linear models. Note that any optimization algorithm
based on linear models can overshoot the optimum, but parameter-free
algorithms may be even more prone to overshooting because their iterates can
move _exponentially far_ between iterations. Instead, our new algorithms
effectively alleviate this problem, see Figure 1. Our algorithms are based on
a _new decomposition of the regret that takes advantage of the geometry of
truncated linear losses_ that might be of independent interest.

In summary, our primary contribution is a new algorithm that maintains optimal
parameter-free regret bounds _but also_ incorporates additional geometric
information about the loss functions. While such an improvement is not visible
in _worst-case_ rates, we demonstrate through an “implicit-style” regret bound
that the algorithm could perform _significantly better_ in practice, and
verify this behavior in an empirical study.

The rest of the paper is organized as follows: in Section 2 we discuss related
work and in Section 3 we review some definitions and background knowledge. In
Section 4, we show the difficulties in using truncated linear models in
parameter-free algorithms. In Section 5, we present our solution and prove a
bound on its regret. Since this algorithm does not have a closed form update
rule, in Section 6 we propose a more efficiently computable variant while
still retaining the same theoretical guarantee. In Section 7, we present a
coordinate-wise extension that obtains a tighter bound as well as better
empirical performance. Finally, in Section 8, we empirically validate our
algorithm.

##  2 Related work

Parameter-free OCO Algorithms Parameter-free OCO algorithms are motivated by a
desire to avoid choosing a step size and can achieve optimal theoretical
regret bounds (e.g., McMahan and Orabona, 2014; Orabona, 2014; Orabona and
Pál, 2016; Cutkosky and Boahen, 2017; Foster et al., 2018; Cutkosky and
Orabona, 2018; Kotłowski, 2020; Kempka et al., 2019; Cutkosky and Sarlos,
2019; Jun and Orabona, 2019; van der Hoeven, 2019; Mhammedi and Koolen, 2020;
Orabona and Pál, 2021; Chen et al., 2021). Some of them are based on the FTRL
framework (Shalev-Shwartz, 2007; Abernethy et al., 2008b; Hazan and Kale,
2008) (sometimes indirectly through methods such as coin-betting). The closest
work to our algorithms is the CODE algorithm (Chen et al., 2022) which is the
first attempt to combine parameter-free methods with truncated losses.
Inspired by the Importance Weight Awareness updates in Karampatziakis and
Langford (2011), CODE models the optimization algorithm with an ODE, and
solves the ODE in a closed form to make infinitely many infinitesimal
parameter-free updates on truncated losses. While CODE solves the ODE in
closed form, it does not have any theoretical guarantee. In our work, in each
step $t$, we consider the loss in two points only: on the current prediction
and the updated one. This gives rise to an implicit equation that we can solve
for truncated losses and to an optimal regret guarantee.

Truncated Linear Models and Implicit Updates Truncated linear models were
proposed in Asi and Duchi (2019) to create a tighter surrogate model for
optimization. While the use of convex linear lower bounds is also the core
method in OCO algorithms (see, e.g., Orabona, 2019), we are not aware of any
other online learning algorithm with a regret guarantee based on truncated
linear models. Asi and Duchi (2019) incorporate truncated linear models into
the Mirror Descent update (Nemirovsky and Yudin, 1983), forming a
_proximal/implicit_ update (Moreau, 1965; Martinet, 1970; Rockafellar, 1976;
Kivinen and Warmuth, 1997; Parikh and Boyd, 2014). In online learning, Kulis
and Bartlett (2010) provides the first regret bounds for implicit updates that
match those of OMD, while McMahan (2010) makes the first attempt to quantify
the advantage of the implicit updates in the regret bound. Song et al. (2018)
generalize the results in McMahan (2010) to Bregman divergences and strongly
convex functions, and quantify the gain differently in the regret bound.
Finally, Campolongo and Orabona (2020) show that implicit updates give rise to
regret guarantees that depend on the temporal variability of the losses as
well. We will match the dependency on the subgradients in our final results to
the one of FTRL with implicit updates (McMahan, 2010), which underlines the
“implicit” nature of our algorithm.

##  3 Preliminary

In this section, we introduce some of the needed background and definition.

Convex Analysis Definitions For a function
$f:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$, we define a subgradient of
$f$ in $\boldsymbol{x}\in\mathbb{R}^{d}$ as a vector
$\boldsymbol{g}\in\mathbb{R}^{d}$ that satisfies $f(\boldsymbol{y})\geq
f(\boldsymbol{x})+\langle\boldsymbol{g},\boldsymbol{y}-\boldsymbol{x}\rangle,\
\forall\boldsymbol{y}\in\mathbb{R}^{d}$. We denote the set of subgradients of
$f$ at $\boldsymbol{x}$ by $\partial f(\boldsymbol{x})$. A function
$f:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$ is $\mu$-strongly convex over
a convex set $V\subseteq\mathop{\mathrm{int}}\mathop{\mathrm{dom}}f$ w.r.t.
$\|\cdot\|$ if $\forall\boldsymbol{x},\boldsymbol{y}\in V$, we have
$\boldsymbol{g}\in\partial f(\boldsymbol{x})$, $f(\boldsymbol{y})\geq
f(\boldsymbol{x})+\langle\boldsymbol{g},\boldsymbol{y}-\boldsymbol{x}\rangle+\frac{\mu}{2}\|\boldsymbol{x}-\boldsymbol{y}\|^{2}$.
The Fenchel conjugate $f^{\star}$ of a function
$f:\mathbb{R}^{d}\to\mathbb{R}$ is defined as
$f^{\star}(\boldsymbol{\theta})=\sup_{\boldsymbol{x}}\langle\boldsymbol{\theta},\boldsymbol{x}\rangle-f(\boldsymbol{x})$.
We denote the projection of a vector $\boldsymbol{x}$ onto a convex set $B$ as
$\Pi_{B}(\boldsymbol{x})\triangleq\mathop{\mathrm{argmin}}_{\boldsymbol{u}\in
B}\ \|\boldsymbol{x}-\boldsymbol{u}\|^{2}$.

Coin-Betting and Online Learning We now explain the coin-betting framework for
parameter-free algorithm design (Orabona and Pál, 2016), which operates
through convex duality. We consider a vector-valued “coin”
$\boldsymbol{c}_{t}\in\mathbb{R}^{d}$ with $\|\boldsymbol{c}_{t}\|\leq 1$
provided to a gambler in response to a “bet”
$\boldsymbol{x}_{t}\in\mathbb{R}^{d}$. The gambler earns
$\langle\boldsymbol{c}_{t},\boldsymbol{x}_{t}\rangle$ dollars, for a total
wealth of
$\operatorname{Wealth}_{t}=\epsilon+\sum_{i=1}^{t}\langle\boldsymbol{c}_{i},\boldsymbol{x}_{i}\rangle$
at time $t$, assuming an initial endowment of $\epsilon$. We enforce that
$\boldsymbol{x}_{t}=\boldsymbol{\beta}_{t}\operatorname{Wealth}_{t-1}$ for
some _betting fraction_ $\|\boldsymbol{\beta}_{t}\|\leq 1$, which intuitively
corresponds to preventing the gambler from betting more money than the gambler
has: $\operatorname{Wealth}_{t}\geq 0$ for all $t$. The goal of the gambler is
of course to make the wealth as high as possible. To use this gambling game in
online learning, set
$\boldsymbol{c}_{t}\in-\partial\ell_{t}(\boldsymbol{x}_{t})$, and let the
learner’s $\boldsymbol{w}_{t}\in\mathbb{R}^{d}$ be simply equal to the
gambler’s $\boldsymbol{x}_{t}$. To analyze the regret, suppose that
$\operatorname{Wealth}_{T}\geq H\left(\sum_{t=1}^{T}\boldsymbol{c}_{t}\right)$
for some arbitrary function $H$. Then we have:

$\displaystyle\sum_{t=1}^{T}\ell_{t}(\boldsymbol{w}_{t})-\ell_{t}(\boldsymbol{u})$
$\displaystyle\leq\sum_{t=1}^{T}\langle\boldsymbol{c}_{t},\boldsymbol{u}-\boldsymbol{w}_{t}\rangle=\epsilon+\sum_{t=1}^{T}\langle\boldsymbol{c}_{t},\boldsymbol{u}\rangle-\operatorname{Wealth}_{T}$
$\displaystyle\leq\epsilon+\sum_{t=1}^{T}\langle\boldsymbol{c}_{t},\boldsymbol{u}\rangle-H\left(\sum_{t=1}^{T}\boldsymbol{c}_{t}\right)\leq\epsilon+\sup_{G\in\mathbb{R}^{d}}\langle
G,\boldsymbol{u}\rangle-H(G)=\epsilon+H^{\star}(\boldsymbol{u})$

where in the first inequality we use the definition of the subgradient, in the
second the assumption on $H$, and the last equality the definition of Fenchel
conjugate $H^{\star}$.

Critically, notice that the wealth lower-bound $\operatorname{Wealth}_{T}\geq
H\left(\sum_{t=1}^{T}\boldsymbol{c}_{t}\right)$ does not involve
$\boldsymbol{u}$. Instead, $\boldsymbol{u}$ appears only in analysis through
Fenchel duality, which provides the parameter-free property. Hence, _we can
use any betting algorithm that guarantees a high wealth to design a parameter-
free optimization algorithm._

$f(x)$TruncatedLinear($x_{0}$)($x_{1}$)($x^{*}$) Figure 2: Models of the
function $f(x)=\log(1+e^{-x})$: a truncated linear model (Red) built around
the point $x_{0}$, and a linear model (Green) built around the point $x_{1}$.
$x^{*}$ is the hinge corner.

Truncated Linear model For any $\hat{\ell}_{t}$ such that
$\hat{\ell}_{t}(\boldsymbol{w}_{t})=\ell_{t}(\boldsymbol{w}_{t})$ and
$\hat{\ell}_{t}(\boldsymbol{w})\leq\ell_{t}(\boldsymbol{w}),~{}\forall\boldsymbol{w}$,
we have
$\sum_{t=1}^{T}(\ell_{t}(\boldsymbol{w}_{t})-\ell_{t}(\boldsymbol{u}))\leq\sum_{t=1}^{T}(\hat{\ell}_{t}(\boldsymbol{w}_{t})-\hat{\ell}_{t}(\boldsymbol{u}))$.
Linear models
$\hat{\ell}_{t}(\boldsymbol{w})=\ell_{t}(\boldsymbol{w}_{t})+\langle\boldsymbol{g}_{t},\boldsymbol{w}-\boldsymbol{w}_{t}\rangle$
satisfy this property with
$\boldsymbol{g}_{t}\in\partial\ell_{t}(\boldsymbol{w}_{t})$, which motivates
the popularity of online _linear_ optimization. However, we might think to
design tighter approximations. In particular, Asi and Duchi (2019) proposed
truncated linear models:

$\hat{\ell}_{t}(\boldsymbol{w})\triangleq\max\\{\ell_{t}(\boldsymbol{w}_{t})+\langle\boldsymbol{g}_{t},\boldsymbol{w}-\boldsymbol{w}_{t}\rangle,\inf_{\boldsymbol{w}}\ell_{t}(\boldsymbol{w})\\}~{}.$

Besides the property above, truncated linear models satisfy: i)
$\hat{\ell}_{t}(\boldsymbol{w})$ is convex and subdifferentiable on the
domain; ii) For any $\boldsymbol{w}$, we have
$\boldsymbol{g}^{+}=h\boldsymbol{g}_{t}$ where
$\boldsymbol{g}^{+}\in\partial\hat{\ell}_{t}(\boldsymbol{w})$ and $h\in[0,1]$;
iii)
$\hat{\ell}_{t}(\boldsymbol{w})\geq\inf_{\boldsymbol{w}}\ell_{t}(\boldsymbol{w})$.
In the following, we will assume that
$\inf_{\boldsymbol{w}}\ell_{t}(\boldsymbol{w})=0$, w.l.o.g. for loss functions
bounded from below.

##  4 Difficulties in Using Truncated Models in Parameter-free Algorithms

Many parameter-free algorithms are based on FTRL. Hence, it is natural to ask
whether it is possible to directly use truncated linear models instead of
linear models in FTRL to utilize truncated linear models in parameter-free
algorithms. This approach immediately runs into significant problems.
Specifically, FTRL algorithms usually maintain the sum of the losses observed
so far.

One can easily store this sum when the losses are linear, but truncated losses
would require $\mathcal{O}(T)$ space and $\mathcal{O}(poly(T))$ time for every
update. Thus, using truncated linear models with FTRL has the same
computational cost as using the original cost functions - the simplification
to using truncated linear models does not appear to help. In contrast, our
solution has the same computational and space complexity of online gradient
descent.

Another possibility is to adapt the coin-betting design of parameter-free
algorithms (Orabona and Pál, 2016) to truncated linear models. A moment of
thinking should convince the reader this is far from simple: The reduction
from optimization to coin-betting described in Section 3 works by transforming
subgradients into coin outcomes, but the subgradient of a truncated loss is
exactly the same as the subgradient of the original function! Thus, simply
using the reduction as-is on the truncated linear model would provide _no
benefit_ over using the simpler linear model.

Another method that seems possible is using truncated linear models in online
gradient descent, and then make online gradient descent parameter-free via
some application of the doubling trick (Shalev-Shwartz, 2012, 2.3.1). Perhaps
surprisingly, employing the doubling trick in this way is quite difficult. The
only known application of the doubling trick is in Streeter and McMahan
(2012), but it does not achieve the optimal regret bound, and more
importantly, employs a delicate identity relating the regret and sums of
gradients that may fail for the truncated linear model. Furthermore, the
doubling trick usually has terrible empirical performance, which completely
defeats the purpose of using truncated linear models.

##  5 Parameter-free OCO with Truncated Linear Models

In this section, we introduce our novel parameter-free algorithms for
truncated linear models.

We overcome the difficulties described above through a multi-step process,
during which we will introduce three separate algorithms. First, we introduce
a new regret decomposition to take advantage of truncated losses while still
only requiring storage of a few vectors. As an illustration of the key
principles, we will use this new regret decomposition to design Algorithm 1.
While the theoretical guarantee of Algorithm 1 matches our desiderata, the
update does not have a closed form. Hence, we then show how to slightly change
our algorithm to obtain a closed form update in Algorithm 2. Finally, in
Section 7, we consider each coordinate as a separate 1-d problem to obtain a
coordinate-wise variant that achieves better performance both theoretically
and empirically.

As mentioned previously, using truncated linear models in an FTRL-based
parameter-free algorithm would result in an inefficient update.

Therefore, in the following, we show a different approach inspired by the idea
of implicit updates (Kivinen et al., 2006; Kulis and Bartlett, 2010; McMahan,
2010). Our method introduces a new variation on the standard approach to
bounding online convex optimization with online linear optimization, and an
accompanying update to the regret/reward duality.

A New Regret Decomposition We are interested in upper bounding the terms
$\ell_{t}(\boldsymbol{w}_{t})-\ell_{t}(\boldsymbol{u})$ for any
$\boldsymbol{u}\in\mathbb{R}^{d}$. The usual method (Zinkevich, 2003) is to
upper bound the regret by linear terms, and then proceed to bound the regret
on the linear losses as follows:

$\operatorname{Regret}_{T}(\boldsymbol{u})=\sum_{t=1}^{T}\ell_{t}(\boldsymbol{w}_{t})-\ell_{t}(\boldsymbol{u})\leq\sum_{t=1}^{T}\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t}-\boldsymbol{u}\rangle,$

where $\boldsymbol{g}_{t}\in\partial\ell_{t}(\boldsymbol{w}_{t})$. While this
approach gives worst-case optimal upper bounds, it completely ignores the
geometry of the loss functions $\ell_{t}$. In contrast, we consider upper
bounding the term $\ell_{t}(\boldsymbol{w}_{t})-\ell_{t}(\boldsymbol{u})$ with
the truncated linear loss $\hat{\ell}_{t}$, and decompose the regret on the
truncated linear losses from an “implicit” point of view for a tighter bound.
Specifically, for any $\boldsymbol{u}\in\mathbb{R}^{d}$ we have

$\displaystyle\ell_{t}(\boldsymbol{w}_{t})-\ell_{t}(\boldsymbol{u})$
$\displaystyle\leq\hat{\ell}_{t}(\boldsymbol{w}_{t})-\hat{\ell}_{t}(\boldsymbol{u})=\hat{\ell}_{t}(\boldsymbol{w}_{t})-\hat{\ell}_{t}(\boldsymbol{w}_{t+1})+\hat{\ell}_{t}(\boldsymbol{w}_{t+1})-\hat{\ell}_{t}(\boldsymbol{u})$
(1)
$\displaystyle\leq\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\rangle+\langle\boldsymbol{g}_{t}^{+},\boldsymbol{w}_{t+1}-\boldsymbol{u}\rangle~{},$

where $\boldsymbol{g}_{t}\in\partial\ell_{t}(\boldsymbol{w}_{t})$,
$\boldsymbol{g}_{t}\in\partial\hat{\ell}_{t}(\boldsymbol{w}_{t})$,
$\boldsymbol{g}_{t}^{+}\in\partial\hat{\ell}_{t}(\boldsymbol{w}_{t+1})$, the
first inequality is true by the property of the truncated linear model, and
the second inequality is from the convexity. This decomposition can _take into
account part of the geometry of the function through
$\boldsymbol{g}_{t}^{+}$_, which quantifies how far we are from the infimum of
$\ell_{t}$. Note that the decomposition itself is very general and does _not_
require $\hat{\ell}$ to be a truncated linear loss: this structure is
primarily used to form more efficient algorithms.

Implicit Coin-Betting To leverage this decomposition, we now define a modified
notion of the _wealth_ quantity described in Section 3. Our key idea is to
realize that _the regret/reward duality is more general than previously
thought_. In particular, we define $\operatorname{Wealth}_{0}=\epsilon$ and
$\operatorname{Wealth}_{T}\triangleq\operatorname{Wealth}_{T-1}-\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\rangle-\langle\boldsymbol{g}_{t}^{+},\boldsymbol{w}_{t+1}\rangle$,
to have

$\operatorname{Wealth}_{T}=\epsilon-\sum_{t=1}^{T}(\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\rangle+\langle\boldsymbol{g}_{t}^{+},\boldsymbol{w}_{t+1}\rangle)~{}.$
(2)

This implies
$\operatorname{Regret}_{T}(\boldsymbol{u})\leq\epsilon+\left\langle-\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+},\boldsymbol{u}\right\rangle-\operatorname{Wealth}_{T}$.
Suppose that we obtain a bound
$\operatorname{Wealth}_{T}\geq\psi_{T}\left(-\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right)$
for some $\psi_{T}$. Then, we can still use the Fenchel conjugate:

$\displaystyle\operatorname{Regret}_{T}(\boldsymbol{u})-\epsilon\leq-\left\langle\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+},\boldsymbol{u}\right\rangle-\psi_{T}\left(-\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right)\leq\sup_{\boldsymbol{y}}\
\langle\boldsymbol{y},\boldsymbol{u}\rangle-\psi_{T}(\boldsymbol{y})=\psi_{T}^{\star}(\boldsymbol{u})~{}.$

Hence, it suffices to design an algorithm that guarantees a lower bound on
$\operatorname{Wealth}_{T}$ to achieve a regret upper bound, _even for our
modified notion of wealth_. Moreover, given that our regret decomposition
takes into account the geometry of the truncated linear losses, we can expect
a regret guarantee that becomes tighter when we are close to the infimum of
the functions $\ell_{t}$.

Algorithm 1 Parameter-free OCO with Truncated Linear Models

1: Initialize
$\boldsymbol{\beta}_{1}\leftarrow\boldsymbol{0},\operatorname{Wealth}_{0}\leftarrow
1,\eta_{1}\leftarrow 1/3$

2: for $t=1$ to $T$ do

3: Predict
$\boldsymbol{w}_{t}\leftarrow\boldsymbol{\beta}_{t}\operatorname{Wealth}_{t-1}$

4: Receive $\ell_{t}(\boldsymbol{w}_{t})$ and
$\boldsymbol{g}_{t}\in\partial\ell_{t}(\boldsymbol{w}_{t})$

5: Calculate $\boldsymbol{g}_{t}^{+}$ (see Section 5.1).
$\boldsymbol{g}_{t}^{+}=h_{t}\boldsymbol{g}_{t}$ by property (ii) of truncated
linear models

6:
$\hat{\boldsymbol{\beta}}_{t+1}\leftarrow\boldsymbol{\beta}_{t}-\frac{\boldsymbol{g}_{t}^{+}+2\boldsymbol{\beta}_{t}(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})}{1/\eta_{1}+2\sum_{i=1}^{t-1}(\|\boldsymbol{g}_{i}\|^{2}-\|\boldsymbol{g}_{i}^{+}-\boldsymbol{g}_{i}\|^{2})}$

7:
$\boldsymbol{\beta}_{t+1}\leftarrow\hat{\boldsymbol{\beta}}_{t+1}/\max\left(1,2\|\hat{\boldsymbol{\beta}}_{t+1}\|\right)$

8:
$\operatorname{Wealth}_{t}\leftarrow\operatorname{Wealth}_{t-1}\frac{1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle}{1+(h_{t}-1)\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle}$

9: end for

We designed Algorithm 1 to maximize the wealth in (2), yielding a regret bound
in Theorem 5.1.

######  Theorem 5.1.

Assume $\ell_{t}(\boldsymbol{x}),t=1,\dots,T$, to be convex functions. Set
$\operatorname{Wealth}_{0}=\epsilon=1$ and assume that
$\|\boldsymbol{g}_{t}\|\leq 1$ and
$\boldsymbol{g}_{t}^{+}=h_{t}\boldsymbol{g}_{t}$ where $h_{t}\in[0,1]$.

Then, Algorithm 1 satisfies

$\displaystyle\operatorname{Regret}_{T}(\boldsymbol{u})=$
$\displaystyle\mathcal{O}\left(\max\left\\{\|\boldsymbol{u}\|\ln\left(\|\boldsymbol{u}\|\left(1+\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)\right)\right.\right.,$
$\displaystyle\left.\left.\|\boldsymbol{u}\|\sqrt{\sum_{t=1}^{T}(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})\cdot\ln\left(1+\|\boldsymbol{u}\|\sum_{t=1}^{T}(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})\right)}\right\\}\right).$

To convey the main ideas, here we present a proof sketch, the full proof is
included in the Appendix.

######  Proof 5.2 (Proof sketch).

We first lower bound the wealth of the algorithm. From the definition of the
wealth (2) and the fact that the algorithm predicts with
$\boldsymbol{w}_{t}=\boldsymbol{\beta}_{t}\operatorname{Wealth}_{t-1}$, we
have

$\operatorname{Wealth}_{t}=\operatorname{Wealth}_{t-1}-\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\rangle-\langle\boldsymbol{g}_{t}^{+},\boldsymbol{w}_{t+1}\rangle\Rightarrow\operatorname{Wealth}_{t}=\frac{\operatorname{Wealth}_{t-1}(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)}{1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle}~{}.$
(3)

This implies that
$\ln\operatorname{Wealth}_{T}=\ln\epsilon+\sum_{t=1}^{T}(\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle))$.
It is possible to show that $\ln\operatorname{Wealth}_{T}-\ln\epsilon$ can be
lower bounded as

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\left(\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle)\right)$
(4)
$\displaystyle\geq\sum_{t=1}^{T}\left[-\langle\boldsymbol{g}^{+}_{t},\boldsymbol{\beta}_{t}\rangle-(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|\boldsymbol{\beta}_{t}\|^{2}-2\|\boldsymbol{g}_{t}\|\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\right]~{}.$

So, $\boldsymbol{\beta}_{t}$ is designed to be the output of running OGD
(Online Gradient Descent) on $\mu_{t}$ strongly-convex losses
$f_{t}(\boldsymbol{\beta})\triangleq\langle\boldsymbol{g}_{t}^{+},\boldsymbol{\beta}\rangle+\frac{\mu_{t}}{2}\|\boldsymbol{\beta}_{t}\|^{2}$,
where
$\mu_{t}=2(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}-\boldsymbol{g}_{t}^{+}\|^{2})$
with $\boldsymbol{\beta}\in B$, $B=\\{\boldsymbol{x}|\|\boldsymbol{x}\|\leq
1/2\\}$, and stepsizes
$\eta_{t}=\frac{1}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}$. Standard OGD analysis
provides the lower bound for
$\sum_{t=1}^{T}\langle\boldsymbol{g}^{+}_{t},\boldsymbol{\beta}_{t}\rangle+(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|\boldsymbol{\beta}_{t}\|^{2}$.
Besides, $\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|$ is upper
bounded by
$\frac{3\|\boldsymbol{g}_{t}^{+}\|}{1+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}$.
Combining all pieces together leads to the lower bound

$\ln\operatorname{Wealth}_{T}\geq-3/2-7.25\ln\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)+\min\left\\{\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{4},\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}\right\\}~{}.$

A lower bound on $\operatorname{Wealth}_{T}$ indicates an upper bound on
regret. Now, we derive the upper bound on the regret from the Fenchel
conjugate of the function above.

Note that the bounded subgradient assumption is a known requirement shared by
all parameter-free algorithms, see lower bound in Cutkosky and Boahen (2017).
However, the limitation is milder than it seems at first blush: this Lipschitz
bound can actually be over-estimated by a factor of $\sqrt{T}$ before
significant damage is done to the regret bound. This can be seen by observing
that other than an $O(\log{T})$ term, our regret bounds scale with the
observed norms of the gradients. Thus, the limitation is actually rather
benign - we simply assume a bound of 1 to simplify equations.

Comparison with Parameter-Free Bounds Previous work of Cutkosky and Orabona
(2018) achieved a regret bound of
$\mathcal{O}\left(\|\boldsymbol{u}\|\sqrt{\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|^{2}}\right)$
which has the optimal worst-case dependence on $\|\boldsymbol{g}_{t}\|$
(Abernethy et al., 2008a; Cutkosky, 2018). In Theorem 5.1, we obtain a regret
bound depending on
$\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2}=\|\boldsymbol{g}_{t}\|^{2}(2h_{t}-h_{t}^{2})$.
So, as long as the algorithm goes close to the hinge corner of the truncated
linear model, it will yield an $h_{t}<1$ and a smaller regret. Intuitively,
this should be expected to occur whenever it is possible to obtain small loss
as obtaining small loss requires reaching the hinge of the truncated linear
model.

Relation to Implicit Updates Truncated linear models were introduced as an
approximation of the implicit updates (Asi and Duchi, 2019). In this view, it
is instructive to compare the dependency on the subgradients in Theorem 5.1
and the regret bounds for implicit updates. For example, McMahan (2010,
Theorem 2) gives a regret guarantee for FTRL with implicit updates and non-
adaptive regularizer that depends on
$\langle\boldsymbol{g}_{t}-\frac{1}{2}\boldsymbol{g}^{+}_{t},\boldsymbol{g}_{t}^{+}\rangle$.
This quantity is exactly
$\frac{1}{2}(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})$
that appears in Theorem 5.1. This supports the idea that the decomposition in
(1) “emulates” the idea of implicit updates in parameter-free algorithms.
However, there is a subtle difference: in standard implicit updates
$\boldsymbol{g}_{t}^{+}\in\partial\ell_{t}(\boldsymbol{w}_{t+1})$ is a
subgradient of the original loss function. Instead, here
$\boldsymbol{g}_{t}^{+}\in\partial\hat{\ell}_{t}(\boldsymbol{w}_{t+1})$, so it
is a subgradient of the truncated linear model. We can see this as a price we
pay to obtain a smaller computational complexity compared to standard implicit
updates.

Comparison with OMD with truncated linear model To the best of our knowledge,
there are actually no regret guarantees with OMD with truncated linear models
in the literature (Asi and Duchi (2019) do not consider the adversarial
setting). However, it is quite likely that OMD with truncated models can
achieve an implicit regret similar to that reported by McMahan (2010) _subject
to oracle tuning of the learning rates_. Our results match this benchmark in
the dependency on $\boldsymbol{g}_{t}$ and $\boldsymbol{g}_{t}^{+}$ and
improve in the dependency on $\|\boldsymbol{u}\|$ since we do not require
oracle tuning of the learning rate.

No Overshooting Property We now prove that the proposed algorithm never
overshoots the minimum of the truncated linear loss. Moreover, in the case
that the minimum of $\hat{\ell}_{t}$ coincides with the minimum of $\ell_{t}$,
we end up exactly in the minimum, as illustrated by Figure 1.

######  Theorem 5.3.

Under the assumptions of Theorem 5.1 and the notation of Algorithm 1, assume
that $\boldsymbol{g}_{t}\neq\boldsymbol{0}$. Then, the update
$\boldsymbol{w}_{t+1}$ can never land on the flat part of the loss
$\hat{\ell}_{t}$, but only on its linear part or in the corner.

######  Proof 5.4.

The statement is equivalent to showing that
$\ell_{t}(\boldsymbol{w}_{t})+\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t+1}-\boldsymbol{w}_{t}\rangle\geq
0$ from the definition of $\hat{\ell}_{t}$. We prove it by contradiction.
Let’s assume that
$\ell_{t}(\boldsymbol{w}_{t})+\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t+1}-\boldsymbol{w}_{t}\rangle<0$.
Then, we would have $\hat{\ell}_{t}(\boldsymbol{w}_{t+1})=0$ and
$\boldsymbol{g}_{t}^{+}=\boldsymbol{0}$ (equivalently $h_{t}=0$). In turn,
this would imply $\boldsymbol{\beta}_{t+1}=\boldsymbol{\beta}_{t}$ and
$\operatorname{Wealth}_{t}=\operatorname{Wealth}_{t-1}$. So, we would have
$\boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}$ which is impossible because
$\boldsymbol{g}_{t}\neq\boldsymbol{0}$.

Note that we assume $\boldsymbol{g}_{t}\neq\boldsymbol{0}$ in Theorem 5.3
since when $\boldsymbol{g}_{t}=\boldsymbol{0}$ the algorithm is already in the
corner.

###  5.1 Computation of $h_{t}$

The next challenge is how to find $h_{t}$. This is the only part of the
Algorithm that uses the truncated linear model structure: the analysis Theorem
5.1 actually applies to _any_ losses for which
$\boldsymbol{g}_{t}^{+}=h_{t}\boldsymbol{g}_{t}$. Truncated linear models
combine this favorable property with the additional property that it is
possible to efficiently compute $h_{t}$. The argument of Theorem 5.3 shows
that we cannot be in the flat region. By inspection of the updates, there are
two achievable cases: in the first case $h_{t}=1$ and we are not in the corner
of the truncated model, while in the second case, we are in the corner. Hence,
as a first step, we posit that $h_{t}=1$, calculate $\boldsymbol{w}_{t+1}$ and
see if indeed $\boldsymbol{g}_{t}^{+}=\boldsymbol{g}_{t}$. If this is not the
case, then the solution must be in the corner and $h_{t}\in[0,1)$. By
definition
$\boldsymbol{w}_{t+1}=\boldsymbol{\beta}_{t+1}\operatorname{Wealth}_{t}$,
where

$\boldsymbol{\beta}_{t+1}=\prod_{B}(\boldsymbol{\beta}_{t}-\eta_{t}(h_{t}\boldsymbol{g}_{t}+2\boldsymbol{\beta}_{t}\|\boldsymbol{g}_{t}\|^{2}(2h_{t}-h^{2}_{t}))\text{
and
}\operatorname{Wealth}_{t}=\operatorname{Wealth}_{t-1}\frac{1-\boldsymbol{g}_{t}\boldsymbol{\beta}_{t}}{1+(\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t})\boldsymbol{\beta}_{t+1}}~{}.$

Thus, $\boldsymbol{w}_{t+1}$ is a function of $h_{t}$. Assuming
$\inf_{\boldsymbol{w}}\ell_{t}(\boldsymbol{w})=0$ w.l.o.g. for loss functions
bounded from below, we are looking for $h_{t}$ that makes

$\ell_{t}(\boldsymbol{w}_{t})+\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t+1}-\boldsymbol{w}_{t}\rangle=0~{}.$
(5)

Although we could solve for $h_{t}$ via bisection, there is no closed form
solution due to the projection of $\boldsymbol{\beta}_{t+1}$. Thus, we next
propose a more complex algorithm with a closed form equation for $h_{t}$.

##  6 Variant with Closed-form Update

In this section, we introduce the Algorithm 2: a variant of Algorithm 1 that
has a closed form update. The key steps are still the same, but here we want
to remove the projection step on $\boldsymbol{\beta}_{t}$. In this way, the
expression of $\boldsymbol{w}_{t+1}$ depends on a simple polynomial in
$h_{t}$. In turn, to remove the projection step, we change the update of
$\boldsymbol{\beta}_{t}$ so that its norm is always assured to be bounded.

Algorithm 2 Parameter-free OCO with Truncated Linear Models – closed form
update

1: Initialize
$\boldsymbol{\beta}_{1}\leftarrow\boldsymbol{0},\eta_{1}\leftarrow\frac{1}{2C},C\leftarrow
9,\operatorname{Wealth}_{0}\leftarrow 1$

2: for $t=1$ to $T$ do

3: Predict
$\boldsymbol{w}_{t}\leftarrow\boldsymbol{\beta}_{t}\operatorname{Wealth}_{t-1}$

4: Receive $\ell_{t}(\boldsymbol{w}_{t})$ and
$\boldsymbol{g}_{t}\in\partial\ell_{t}(\boldsymbol{w}_{t})$

5: Calculate $h_{t}$ (see Section 6.1)

6: if $\|\boldsymbol{\beta}_{t}\|<\frac{3}{8}$ then

7:
$\boldsymbol{\beta}_{t+1}\leftarrow\boldsymbol{\beta}_{t}-\eta_{t}(\boldsymbol{g}_{t}^{+}+2\boldsymbol{\beta}_{t}(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2}))$

8:
$\frac{1}{\eta_{t+1}}\leftarrow\frac{1}{\eta_{t}}+2(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})$

9: else

10:
$\boldsymbol{\beta}_{t+1}\leftarrow\boldsymbol{\beta}_{t}-\eta_{t}2C\|\boldsymbol{g}_{t}^{+}\|\boldsymbol{\beta}_{t}$

11:
$\frac{1}{\eta_{t+1}}\leftarrow\frac{1}{\eta_{t}}+2C\|\boldsymbol{g}_{t}^{+}\|$

12: end if

13:
$\operatorname{Wealth}_{t}\leftarrow\operatorname{Wealth}_{t-1}\frac{1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle}{1+(h_{t}-1)\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle}$

14: end for

For Algorithm 2, we can prove the following guarantee. We present a proof
sketch, while the full proof is in the Appendix.

######  Theorem 6.1.

Assume $\ell_{t}(x),t=1,\dots,T$, to be convex functions. Set
$\operatorname{Wealth}_{0}=\epsilon=1$, $C=9$ and $1/\eta_{1}=2C$, and assume
that $\|\boldsymbol{g}_{t}\|\leq 1$ and
$\boldsymbol{g}_{t}^{+}=h_{t}\boldsymbol{g}_{t}$ where $h_{t}\in[0,1]$.

Then, for all $\boldsymbol{u}\in\mathbb{R}^{d}$, Algorithm 2 satisfies the
same bound as in Theorem 5.1, up to constants hidden in the big O notation.

######  Proof 6.2 (Proof sketch).

As we stated above, due to the projection step in line 6 of Algorithm 1,
$h_{t}$ can not be solved in a closed form. To overcome this, we design a new
update rule that guarantees that $\boldsymbol{\beta}_{t}$ will always end up
in the ball $B=\\{\boldsymbol{x}:\|\boldsymbol{x}\|\leq\frac{1}{2}\\}$ to
avoid the projection step.

In Algorithm 1, $\beta_{t}$ is the output of running OGD on strongly-convex
losses $f_{t}(\beta)$. However, when $\beta_{t}$ is close to 1/2, the next
iteration, $\beta_{t+1}$, could go too far so that a projection step can be
necessary. To avoid this, we intricately design an update rule that when
$\|\beta_{t}\|\geq 3/8$ indicating that $\beta_{t}$ is close to the boundary
of the ball, the next iteration will shrink it a little bit, to make sure that
it stays in the ball $B$. The new update rule is the output of running OGD on
strongly-convex losses $\phi_{t}(\beta)$. In the following, we introduce the
sketch of the proof.

$\boldsymbol{\beta}_{t}$ is the output of OGD with
$\eta_{t}=\frac{1}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}$ on the strongly-convex
losses $\phi_{t}(\boldsymbol{\beta})$:

$\phi_{t}(\boldsymbol{\beta})=\begin{cases}f_{t}(\boldsymbol{\beta}),&\text{
if }\|\boldsymbol{\beta}_{t}\|<\frac{3}{8},\\\
C\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{\beta}\|^{2},&\text{ if
}\frac{3}{8}\leq\|\boldsymbol{\beta}_{t}\|\leq\frac{1}{2},\end{cases}$

where $\boldsymbol{\beta}_{t}\in B$ and
$B=\\{\boldsymbol{x}:\|\boldsymbol{x}\|\leq\frac{1}{2}\\}$.
$\phi_{t}(\boldsymbol{\beta})$ is $\mu_{t}$ strongly convex.
$\boldsymbol{\beta}_{1}^{\star}\triangleq\arg\min_{\boldsymbol{\beta}\in
B_{1}}\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta})$, where
$B_{1}=\\{\boldsymbol{x}:\|\boldsymbol{x}\|\leq\frac{1}{4}\\}$. The intricate
design of $\phi_{t}(\boldsymbol{\beta})$ allows to say that if
$\boldsymbol{\beta}_{t}\geq 3/8$,
$\|\boldsymbol{\beta}_{t+1}\|=(1-\eta_{t}2C\|\boldsymbol{g}_{t}^{+}\|)\|\boldsymbol{\beta}_{t}\|$
will shrink if $\eta_{t}\leq 1/{2C}$; if $\boldsymbol{\beta}_{t}\leq 3/8$,
$\|\boldsymbol{\beta}_{t+1}\|$ will stay in $B$ if $\eta_{t}$ is small enough.
Therefore, Algorithm 2 guarantees $\|\boldsymbol{\beta}_{t}\|\leq\frac{1}{2}$
for all $t=1,\dots,T$, which removes the projection step on
$\boldsymbol{\beta}_{t}$, and gives rise to the closed form updates.

Furthermore, for $C\geq 9$, the regret of $\phi_{t}(\boldsymbol{\beta}_{t})$
upper bounds the regret of $f_{t}(\boldsymbol{\beta}_{t})$:
$f_{t}(\boldsymbol{\beta}_{t})-f_{t}(\boldsymbol{\beta}_{1}^{\star})\leq\phi_{t}(\boldsymbol{\beta}_{t})-\phi_{t}(\boldsymbol{\beta}_{1}^{\star})$.
We upper bound
$\sum_{t=1}^{T}\phi_{t}(\boldsymbol{\beta}_{t})-\phi_{t}(\boldsymbol{\beta}_{1}^{\star})$
by standard OGD analysis, which implies a bound on
$\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{t})$. Combining the upper bound of
$\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|$ and
$\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{t})$ lower bounds wealth by (4). The
rest of the proof is similar to the proof of Theorem 5.1.

We also note that the non-overshooting property holds for this algorithm too.
The proof is exactly the same as before and it is omitted.

######  Theorem 6.3.

Under the assumptions of Theorem 6.1 and the notation of Algorithm 2, assume
that $\boldsymbol{g}_{t}\neq\boldsymbol{0}$. Then, the update
$\boldsymbol{w}_{t+1}$ can never land on the flat part of the loss
$\hat{\ell}_{t}$, but only on its linear part or on the corner.

###  6.1 Computation of $h_{t}$ with Closed Form Solution

Now, we show how to obtain a closed form expression for the update in
Algorithm 2. As before, first we tentatively set $h_{t}=1$ and check if
$\boldsymbol{g}^{+}_{t}=\boldsymbol{g}_{t}$. If yes, then $h_{t}=1$ and we can
compute $\boldsymbol{w}_{t+1}$. If not, thanks to Theorem 6.3, we know that
$\boldsymbol{w}_{t+1}$ lands in the corner of $\hat{\ell}_{t}$ and we need to
compute $h_{t}\in[0,1)$. In this case we are looking for the $h_{t}$ such that
$\boldsymbol{w}_{t+1}$ satisfies (5).

Let
$A=\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t}\rangle-\ell_{t}(\boldsymbol{w}_{t})$,
$B=\operatorname{Wealth}_{t}(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)$.
We consider two cases based on $\boldsymbol{\beta}_{t}$.

If $\|\boldsymbol{\beta}_{t}\|\leq\frac{3}{8}$, we have that
$\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle=\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}-\eta_{t}(\boldsymbol{g}_{t}^{+}+2\boldsymbol{\beta}_{t}(2h_{t}\|\boldsymbol{g}_{t}\|^{2}-h_{t}^{2}\|\boldsymbol{g}_{t}\|^{2}))\rangle$.
Let
$D=2\eta_{t}\|\boldsymbol{g}_{t}\|^{2}\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle$,
so (5) becomes a cubic equation of $h_{t}$ that has closed form solution:

$\displaystyle-
ADh_{t}^{3}+(2AD+A\eta_{t}\|\boldsymbol{g}_{t}\|^{2}+(A+B)D)h_{t}^{2}+(-(A+B)\eta_{t}\|\boldsymbol{g}_{t}\|^{2}-2(A+B)D$
$\displaystyle\quad-A\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)h_{t}+(A+B)\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle-A=0~{}.$

If $\frac{3}{8}\leq\|\boldsymbol{\beta}_{t}\|\leq\frac{1}{2}$, we have
$\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle=\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle(1-2C\eta_{t}\|\boldsymbol{g}_{t}\|h_{t})$.
Let
$D=2C\eta_{t}\|\boldsymbol{g}_{t}\|\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle$.
So, (5) can be rewritten as the following quadratic equation of $h_{t}$ and
again it has closed form solution:
$ADh_{t}^{2}+(-A\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle-(A+B)D)h_{t}+(A+B)\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle-A=0$.

##  7 Tighter Regret Guarantee through Coordinate-wise Updates

In this section, we introduce a coordinate-wise variant of Parameter-free OCO
with truncated linear models. This is a simple extension of Algorithm 2 by
considering each coordinate as a different 1-d OCO algorithm. The advantage is
that this regret bound is even _tighter_ than the bound of Theorem 5.1. Here
we present the Theorem 7.1. (The proof can be found in the Appendix.) We use
$\beta_{t,i},~{}u_{i},~{}g_{t,i}\in\mathbb{R}$ to represent the i-th element
of the vector correspondingly.

Algorithm 3 Parameter-free OCO with Truncated Linear Models – coordinate-wise
update

1: Initialize
$\boldsymbol{\beta}_{1}\leftarrow\boldsymbol{0},\eta_{1}\leftarrow\frac{1}{2C}\cdot\boldsymbol{1},C\leftarrow
9,\operatorname{Wealth}_{0}\leftarrow\boldsymbol{1}\in\mathbb{R}^{d}$

2: for $t=1$ to $T$ do

3: Predict
$\boldsymbol{w}_{t}\leftarrow\boldsymbol{\beta}_{t}\odot\operatorname{Wealth}_{t-1}$

4: Receive $\ell_{t}(\boldsymbol{w}_{t})$ and
$\boldsymbol{g}_{t}\in\partial\ell_{t}(\boldsymbol{w}_{t})$

5: Calculate $h_{t}$ s.t.
$\ell_{t}(\boldsymbol{w}_{t})+\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t+1}-\boldsymbol{w}_{t}\rangle=0$
(see Section 5.1)

6: for $i=1$ to $d$ do

7: if $|\beta_{t,i}|<\frac{3}{8}$ then

8:
$\beta_{t+1,i}\leftarrow\beta_{t,i}-\eta_{t,i}(g_{t,i}^{+}+2\beta_{t,i}(2g_{t,i}g_{t,i}^{+}-(g_{t,i}^{+})^{2}))$

9:
$\frac{1}{\eta_{t+1,i}}\leftarrow\frac{1}{\eta_{t,i}}+2(g_{t,i}^{2}-(g_{t,i}^{+}-g_{t,i})^{2})$

10: else

11: $\beta_{t+1,i}\leftarrow\beta_{t,i}-\eta_{t,i}2C|g_{t,i}^{+}|\beta_{t,i},$

12: $\frac{1}{\eta_{t+1,i}}\leftarrow\frac{1}{\eta_{t,i}}+2C|g_{t,i}^{+}|$

13: end if

14:
$\operatorname{Wealth}_{t,i}\leftarrow\operatorname{Wealth}_{t-1,i}\frac{1-g_{t,i}\beta_{t,i}}{1+(h_{t}-1)g_{t,i}\beta_{t+1,i}}$

15: end for

16: end for

######  Theorem 7.1.

Assume $\ell_{t}(x),t=1,\dots,T$, to be convex functions. Set
$\operatorname{Wealth}_{0}=\epsilon=\boldsymbol{1}$, $C=9$. For $i=1,\dots,d$,
$1/\eta_{1,i}=2C$ and assume that $|g_{t,i}|\leq 1$,
$\boldsymbol{g}_{t}^{+}=h_{t}\boldsymbol{g}_{t}$ where $h_{t}\in[0,1]$. Then,
for all $\boldsymbol{u}\in\mathbb{R}^{d}$, Algorithm 3 guarantees

$\displaystyle\operatorname{Regret}_{T}(\boldsymbol{u})$
$\displaystyle=\sum_{i=1}^{d}\epsilon+\mathcal{O}\left(\max\left\\{|u_{i}|\ln\left(|u_{i}|\left(1+\sum_{t=1}^{T}|g_{t,i}||g_{t,i}^{+}|\right)\right)\right.\right.,$
$\displaystyle\quad\left.\left.|u_{i}|\sqrt{\sum_{t=1}^{T}(2|g_{t,i}||g_{t,i}^{+}|-|g_{t,i}^{+}|^{2})\cdot\ln\left(1+|u_{i}|\sum_{t=1}^{T}(2|g_{t,i}||g_{t,i}^{+}|-|g_{t,i}^{+}|^{2})\right)}\right\\}\right)~{}.$

To see how this bound is more desirable than Theorem 5.1, first notice that
the bound obtains some adaptivity to $L_{1}$ geometry: if
$G_{\infty}=\max\|g_{t}\|_{\infty}$, then the bound is at most
$\tilde{\mathcal{O}}(\|u\|_{1}G_{\infty}{\sqrt{T}})$. Furthermore, by
application of Cauchy-Schwarz (twice!) we can see that the bound is at most an
additive $\epsilon d$ larger than Theorem 5.1 \- and could be much smaller if
either application of Cauchy-Schwarz is loose. Thus, this bound is never much
worse than that of Theorem 5.1, but has the further desirable property that
one can add a large number of “irrelevant” dimensions for which $u_{i}=0$
without harming the bound.

Unfortunately, we no longer have a closed form expression for $h_{t}$ due to
the coupling of the coordinates. However, at each iteration, we can find a
$\delta$-approximation to $h_{t}$ using $\mathcal{O}(\log(1/\delta))$ steps of
bisection and a single gradient oracle call. By “bisection” we mean a binary-
search style algorithm: given a guess for $h_{t}$, we can compute if the true
value is lower or higher than the guess by computing what the update would be
if the guess were correct and checking if we have overshot the corner of the
truncated bound. Though this inflates the cost of an update by
$\mathcal{O}(\log(1/\delta))$, this is still _significantly_ more efficient
than the $\text{poly}(T)$ oracle calls required to run FTRL with truncated
linear models directly at each step. This small extra computation cost is a
price we pay for better theoretical as well as empirical results.

##  8 Empirical Evaluation

While our main contribution is theoretical, here we evaluate the empirical
performance of Algorithm 2 and Algorithm 3 to show their practical potential.
We will denote the algorithms as Implicit Coin, and Coordinate-wise Implicit
Coin. We would also like to stress that we used Algorithm 2 and Algorithm 3 as
they are, with the choice of the hyperparameters directly given by theory,
i.e., $\eta_{0}$, $C$, $\operatorname{Wealth}_{0}$. It is quite possible that
these choices were not optimal. We do this on purpose: we want to demonstrate
how robust parameter-free algorithms are, even with theory-derived constants.

We compare SGD, SGD with truncated models (aProx) (Asi and Duchi, 2019), SGD
with Importance Weight Aware updates (IWA) (Karampatziakis and Langford,
2011), Coin-betting algorithm (Coin) (Orabona and Pál, 2016), Coin-betting
with ODE updates (CODE) (Chen et al., 2022), COntinuous COin Betting (COCOB)
(Orabona and Tommasi, 2017).

We tested the algorithms on real-world datasets from the LIBSVM website (Chang
and Lin, 2001) and OpenML (Vanschoren et al., 2013). 2dPlane, CPU-act, and
Houses are classification tasks, Rainfall, Bank32nh, and House-8L are
regression tasks. (More information about datasets is in Appendix). We
standardize and pre-process the samples, normalizing them to unit norm
vectors. We shuffle the data and separate into a training set ($70\%$),
validation set ($15\%$), and test set ($15\%$).

Figure 3: Regression tasks: Mean test loss versus epochs.

Figure 4: Classification tasks: Mean test loss versus epochs.

For SGD, aProx and IWA, we tune the initial step size $\eta_{0}$ and consider
stepsize sequence of the form: $\eta_{k}=\eta_{0}/\sqrt{k}$. All the
parameter-free algorithms do not have parameters to tune. Implicit Coin has a
closed form solution for $h_{t}$, so the implementation is as efficient as
SGD. For CODE and Coordinate-wise Implicit Coin, we used a bisection algorithm
to find $h_{t}$.

We considered linear predictors trained with the hinge loss for
classification, and with the absolute loss for regression. We trained all
algorithms for 10 epochs over the training data. Each epoch requires running
through the total shuffled training set. All the experiments are repeated 3
times, we report the average of the 3 repetitions. For all the algorithms that
require a learning rate, on every dataset and for each repetition, we use the
validation loss to choose the best learning rate, train using that learning
rate, test on the test set, and report the test loss averaged over 3
repetitions.

Figure 3 and Figure 4 show the average of test losses versus number of epochs.
In all experiments, Coordinate-wise Implicit Coin has a performance that is
superior or comparable to all the competitors. It is worth remembering that
the algorithms with a learning rate were tuned on the validation set, while
the parameter-free algorithms were not tuned in any way. Moreover, in all
cases, Implicit Coin has a better performance than Coin. Given that their key
difference is the truncated models in Implicit coin, this directly supports
the advantage of these updates over linearized ones.

More in detail, on regression tasks (Figures 3), the performance of
Coordinate-wise Implicit Coin is superior to the other competitors at the end
of the training on Rainfall and House-8L. COCOB, CODE, and Coordinate-wise
Implicit Coin outperform the other competitors significantly on Houses-8L, and
their performances are close to each other on Bank32nh. On the classification
tasks (Figure 4), Coordinate-wise Implicit Coin and Implicit Coin achieve
essentially the optimal performance on CPU-act and Houses correspondingly. On
2dPlane, Coordinate-wise Implicit Coin, Implicit Coin, and CODE perform almost
equally satisfying, and they outperform the other competitors.

##  9 Conclusion

In this paper, we present new parameter-free algorithms utilizing a better
convex lower bound: the truncated linear model. _We overcome the theoretical
difficulties of using truncated linear models in parameter-free algorithms
with a new regret decomposition_. Our regret bounds are analogous to bounds
achieved by implicit methods. Besides, we propose a variant of our algorithm
that has a very efficient closed form update rule, matching the runtime of
gradient descent. Finally, we provide a coordinate-wise variant with tighter
regret bounds.

In the future, we would like to explore the additional possibilities offered
by the new decomposition of regret. For example, we would like to overcome the
limitation of the current per-coordinate formulation and explore the
possibility to design a per-coordinate variant that uses truncated linear
models, retaining the closed form update. Besides, considering the good
empirical performance of CODE and the similarity in the spirit of CODE and
Implicit Coin, we are interested in the possibility of studying the
theoretical properties of CODE.

This material is based upon work supported by the National Science Foundation
under the grants no. 1908111 “AF: Small: Collaborative Research: New
Representations for Learning Algorithms and Secure Computation” and no.
2046096 “CAREER: Parameter-free Optimization Algorithms for Machine Learning”.

## References

  * Abernethy et al. (2008a) J. Abernethy, P. L. Bartlett, A. Rakhlin, and A. Tewari.  Optimal strategies and lower bounds for online convex games.  In _Proceedings of the 21st Annual Conference on Learning Theory_ , pages 414–424. Omnipress, 2008a.
  * Abernethy et al. (2008b) J. D. Abernethy, E. Hazan, and A. Rakhlin.  Competing in the dark: An efficient algorithm for bandit linear optimization.  In Rocco A. Servedio and Tong Zhang, editors, _Proc. of Conference on Learning Theory (COLT)_ , pages 263–274. Omnipress, 2008b.
  * Asi and Duchi (2019) H. Asi and J. C. Duchi.  Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity.  _SIAM Journal on Optimization_ , 29(3):2257–2290, 2019.
  * Campolongo and Orabona (2020) N. Campolongo and F. Orabona.  Temporal variability in implicit online learning.  In _Advances in Neural Information Processing Systems_ , volume 33. Curran Associates, Inc., 2020.
  * Chang and Lin (2001) C.-C. Chang and C.-J. Lin.  _LIBSVM: a library for support vector machines_ , 2001.  Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
  * Chen et al. (2022) K. Chen, J. Langford, and F. Orabona.  Better parameter-free stochastic optimization with ODE updates for coin-betting.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2022.
  * Chen et al. (2021) L. Chen, H. Luo, and C.-Y. Wei.  Impossible tuning made possible: A new expert algorithm and its applications.  In _Proc. of the Conference on Learning Theory_ , 2021.
  * Cutkosky (2018) A. Cutkosky.  _Algorithms and Lower Bounds for Parameter-free Online Learning_.  PhD thesis, Stanford University, 2018.
  * Cutkosky and Boahen (2017) A. Cutkosky and K. Boahen.  Online learning without prior information.  In _Proc. of the 2017 Conference on Learning Theory_ , volume 65 of _Proc. of Machine Learning Research_ , pages 643–677, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR.
  * Cutkosky and Orabona (2018) A. Cutkosky and F. Orabona.  Black-box reductions for parameter-free online learning in Banach spaces.  In _Proc. of the Conference on Learning Theory (COLT)_ , 2018.
  * Cutkosky and Sarlos (2019) A. Cutkosky and T. Sarlos.  Matrix-free preconditioning in online learning.  In _International Conference on Machine Learning_ , pages 1455–1464. PMLR, 2019.
  * Foster et al. (2018) D. J. Foster, A. Rakhlin, and K. Sridharan.  Online learning: Sufficient statistics and the Burkholder method.  In _Proc. of the Conference on Learning Theory_ , 2018.
  * Gordon (1999) G. J. Gordon.  Regret bounds for prediction problems.  In _Proc. of the twelfth annual conference on Computational learning theory (COLT)_ , pages 29–40, 1999.
  * Hazan and Kale (2008) E. Hazan and S. Kale.  Extracting certainty from uncertainty: Regret bounded by variation in costs.  In _Proc. of the 21st Conference on Learning Theory_ , 2008.
  * Jun and Orabona (2019) K.-S. Jun and F. Orabona.  Parameter-free online convex optimization with sub-exponential noise.  In _Proc. of the Conference on Learning Theory (COLT)_ , 2019.
  * Karampatziakis and Langford (2011) N. Karampatziakis and J. Langford.  Online importance weight aware updates.  In _Proc. of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence_ , UAI’11, pages 392––399, Arlington, Virginia, USA, 2011. AUAI Press.
  * Kempka et al. (2019) M. Kempka, W. Kotłowski, and M. K. Warmuth.  Adaptive scale-invariant online algorithms for learning linear models.  In K. Chaudhuri and R. Salakhutdinov, editors, _Proc. of the 36th International Conference on Machine Learning_ , volume 97 of _Proc. of Machine Learning Research_ , pages 3321–3330, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
  * Kivinen and Warmuth (1997) J. Kivinen and M. Warmuth.  Exponentiated gradient versus gradient descent for linear predictors.  _Information and Computation_ , 132(1):1–63, January 1997.
  * Kivinen et al. (2006) J. Kivinen, M. K. Warmuth, and B. Hassibi.  The $p$-norm generalization of the LMS algorithm for adaptive filtering.  _IEEE Transactions on Signal Processing_ , 54(5):1782–1793, 2006.
  * Kotłowski (2020) W. Kotłowski.  Scale-invariant unconstrained online learning.  _Theoretical Computer Science_ , 808:139–158, 2020.
  * Kulis and Bartlett (2010) B. Kulis and P. L. Bartlett.  Implicit online learning.  In _International Conference on Machine Learning_ , pages 575–582, 2010.
  * Martinet (1970) B. Martinet.  Régularisation d’inéquations variationnelles par approximations successives. rev. française informat.  _Recherche Opérationnelle_ , 4:154–158, 1970.
  * McMahan (2010) H. B. McMahan.  A unified view of regularized dual averaging and mirror descent with implicit updates.  _arXiv preprint arXiv:1009.3240_ , 2010.
  * McMahan and Orabona (2014) H. B. McMahan and F. Orabona.  Unconstrained online linear learning in Hilbert spaces: Minimax algorithms and normal approximations.  In _Proc of the Annual Conference on Learning Theory, COLT_ , 2014\.
  * Mhammedi and Koolen (2020) Z. Mhammedi and W. M Koolen.  Lipschitz and comparator-norm adaptivity in online learning.  In _Conference on Learning Theory_ , pages 2858–2887. PMLR, 2020\.
  * Moreau (1965) J.-J. Moreau.  Proximité et dualité dans un espace hilbertien.  _Bulletin de la Société mathématique de France_ , 93:273–299, 1965.
  * Nemirovsky and Yudin (1983) A. S. Nemirovsky and D. Yudin.  _Problem complexity and method efficiency in optimization_.  Wiley, New York, NY, USA, 1983.
  * Orabona (2014) F. Orabona.  Simultaneous model selection and optimization through parameter-free stochastic learning.  In _Advances in Neural Information Processing Systems 27_ , 2014.
  * Orabona (2019) F. Orabona.  A modern introduction to online learning.  _arXiv preprint arXiv:1912.13213_ , 2019.
  * Orabona and Pál (2016) F. Orabona and D. Pál.  Coin betting and parameter-free online learning.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, _Advances in Neural Information Processing Systems 29_ , pages 577–585. Curran Associates, Inc., 2016.
  * Orabona and Pál (2021) F. Orabona and D. Pál.  Parameter-free stochastic optimization of variationally coherent functions.  _arXiv preprint arXiv:2102.00236_ , 2021.
  * Orabona and Tommasi (2017) F. Orabona and T. Tommasi.  Training deep networks without learning rates through coin betting.  In _Advances in Neural Information Processing Systems_ , pages 2160–2170, 2017.
  * Parikh and Boyd (2014) N. Parikh and S. Boyd.  Proximal algorithms.  _Foundations and Trends in optimization_ , 1(3):127–239, 2014.
  * Rockafellar (1976) R. T. Rockafellar.  Monotone operators and the proximal point algorithm.  _SIAM journal on control and optimization_ , 14(5):877–898, 1976.
  * Shalev-Shwartz (2007) S. Shalev-Shwartz.  _Online Learning: Theory, Algorithms, and Applications_.  PhD thesis, The Hebrew University, 2007.
  * Shalev-Shwartz (2012) S. Shalev-Shwartz.  Online learning and online convex optimization.  _Foundations and Trends in Machine Learning_ , 4(2), 2012\.
  * Song et al. (2018) C. Song, J. Liu, H. Liu, Y. Jiang, and T. Zhang.  Fully implicit online learning.  _arXiv preprint arXiv:1809.09350_ , 2018.
  * Streeter and McMahan (2012) M. Streeter and B. McMahan.  No-regret algorithms for unconstrained online convex optimization.  In _Advances in Neural Information Processing Systems 25_ , pages 2402–2410. Curran Associates, Inc., 2012.
  * van der Hoeven (2019) D. van der Hoeven.  User-specified local differential privacy in unconstrained adaptive online learning.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Vanschoren et al. (2013) J. Vanschoren, J. N. van Rijn, B. Bischl, and L. Torgo.  OpenML: Networked science in machine learning.  _SIGKDD Explorations_ , 15(2):49–60, 2013.
  * Warmuth and Jagota (1997) M. K. Warmuth and A. K. Jagota.  Continuous and discrete-time nonlinear gradient descent: Relative loss bounds and convergence.  In _Electronic proceedings of the 5th International Symposium on Artificial Intelligence and Mathematics_ , volume 326, 1997.
  * Zinkevich (2003) M. Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In _Proc. of the International Conference on Machine Learning_ , pages 928–936, 2003.

##  Appendix A Proof of Theorem 5.1

Before we prove Theorem 5.1, we first introduce some technical Lemmas that
will be used in the proof.

######  Lemma A.1.

Under the assumptions of Theorem 5.1 and the notation of Algorithm 1, we have
$\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\leq\frac{3\|\boldsymbol{g}_{t}^{+}\|}{1+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}$
for all $t=1,\dots,T$.

######  Proof A.2.

By the definition of
$\boldsymbol{\beta}_{t+1},~{}\hat{\boldsymbol{\beta}}_{t+1},~{}\boldsymbol{\beta}_{t}$,
we have:

$\displaystyle\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|$
$\displaystyle\leq\|\hat{\boldsymbol{\beta}}_{t+1}-\boldsymbol{\beta}_{t}\|=\frac{\|\boldsymbol{g}_{t}^{+}+2\boldsymbol{\beta}_{t}(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|}{3+2\sum_{i=1}^{t-1}(\|\boldsymbol{g}_{i}\|^{2}-\|\boldsymbol{g}_{i}^{+}-\boldsymbol{g}_{i}\|^{2})}$
$\displaystyle\leq\frac{\|\boldsymbol{g}_{t}^{+}\|+2\|\boldsymbol{\beta}_{t}\|(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})}{3+2\sum_{i=1}^{t-1}(2\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|-\|\boldsymbol{g}_{i}^{+}\|^{2})}\leq\frac{\|\boldsymbol{g}_{t}^{+}\|+2\|\boldsymbol{\beta}_{t}\|(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})}{3+2\sum_{i=1}^{t-1}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}$
$\displaystyle\leq\frac{\|\boldsymbol{g}_{t}^{+}\|+2\|\boldsymbol{\beta}_{t}\|\|\boldsymbol{g}_{t}^{+}\|(2\|\boldsymbol{g}_{t}\|-h_{t}\|\boldsymbol{g}_{t}\|)}{1+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}\leq\frac{3\|\boldsymbol{g}_{t}^{+}\|}{1+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}~{},$

where we used the fact that
$\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|\leq 1$ in second to last
inequality.

######  Lemma A.3.

Let $a_{0}\geq 0$ and $f:[0,+\infty)\to[0,+\infty)$ a nonincreasing function.
Then,

$\sum_{t=1}^{T}a_{t}f\left(a_{0}+\sum_{i=1}^{t}a_{i}\right)\leq\int_{a_{0}}^{\sum_{t=0}^{T}a_{t}}f(x)dx~{}.$

######  Proof A.4.

Denote by $s_{t}=a_{0}+\sum_{i=1}^{t}a_{i}$.

$a_{t}f\left(a_{0}+\sum_{i=1}^{t}a_{i}\right)=a_{t}f(s_{t})=\int_{s_{t-1}}^{s_{t}}f(s_{t})dx\leq\int_{s_{t-1}}^{s_{t}}f(x)dx~{}.$

Summing over $t=1,\dots,T$, we have the stated bound.

######  Lemma A.5.

Let $V$ a non-empty closed convex set in $\mathbb{R}^{d}$. Assume that the
functions $f_{t}:\mathbb{R}\to(-\infty,\infty]$ are $\mu_{t}$-strongly convex
w.r.t $\|\cdot\|_{2}$ over
$V\subset\cap_{t=1}^{T}\mathop{\mathrm{int}}\mathop{\mathrm{dom}}f_{t}$, where
$\mu_{t}>0$. Assume we receive subgradients $\boldsymbol{v}_{t}\in\partial
f_{t}(\boldsymbol{w}_{t})$ and set $\boldsymbol{w}_{t}$ using Online Gradient
Descent with stepsizes:
$\eta_{t}=\frac{1}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}$. Then, for any
$\boldsymbol{u}\in V$, we have the following regret guarantee:

$\displaystyle\sum_{t=1}^{T}(f_{t}(\boldsymbol{w}_{t})-f_{t}(\boldsymbol{u}))\leq\frac{\|\boldsymbol{w}_{1}-\boldsymbol{u}\|^{2}}{2\eta_{1}}+\sum_{t=1}^{T}\frac{\eta_{t}\left\|\boldsymbol{v}_{t}\right\|^{2}}{2}+\sum_{t=1}^{T}\frac{\mu_{t}}{2}\|\boldsymbol{w}_{t+1}+\boldsymbol{w}_{t}-2\boldsymbol{u}\|\|\boldsymbol{w}_{t+1}-\boldsymbol{w}_{t}\|~{}.$

######  Proof A.6.

From the strongly convexity of the function $f_{t}$, we have that

$f_{t}(\boldsymbol{w}_{t})-f_{t}(\boldsymbol{u})\leq\langle\boldsymbol{v}_{t},\boldsymbol{w}_{t}-\boldsymbol{u}\rangle-\frac{\mu_{t}}{2}\|\boldsymbol{w}_{t}-\boldsymbol{u}\|~{},$

where $\boldsymbol{v}_{t}\in\partial f_{t}(\boldsymbol{w}_{t})$. From the fact
that $\eta_{t}=\frac{1}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}$, we have

$\frac{1}{2\eta_{t}}+\frac{\mu_{t}}{2}=\frac{1}{2\eta_{t+1}},\qquad
t=1,\dots,T~{}.$

Also, observe that

$\displaystyle\|\boldsymbol{w}_{t}-\boldsymbol{u}\|^{2}$
$\displaystyle=\|\boldsymbol{w}_{t+1}-\boldsymbol{u}+\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\|^{2}$
$\displaystyle=\|\boldsymbol{w}_{t+1}-\boldsymbol{u}\|^{2}+2\langle\boldsymbol{w}_{t+1}-\boldsymbol{u},\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\rangle+\|\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\|^{2}$
$\displaystyle=\|\boldsymbol{w}_{t+1}-\boldsymbol{u}\|^{2}+\langle
2\boldsymbol{w}_{t+1}-2\boldsymbol{u}+\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1},\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\rangle$
$\displaystyle\geq\|\boldsymbol{w}_{t+1}-\boldsymbol{u}\|^{2}-\|\boldsymbol{w}_{t+1}+\boldsymbol{w}_{t}-2\boldsymbol{u}\|\|\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\|~{}.$

Thus, we have

$\displaystyle\sum_{t=1}^{T}(f_{t}(\boldsymbol{w}_{t})-f_{t}(\boldsymbol{u}))$
$\displaystyle\leq\sum_{t=1}^{T}\left(\frac{1}{2\eta_{t}}\|\boldsymbol{w}_{t}-\boldsymbol{u}\|^{2}-\frac{1}{2\eta_{t}}\|\boldsymbol{w}_{t+1}-\
\boldsymbol{u}\|^{2}-\frac{\mu_{t}}{2}\|\boldsymbol{w}_{t}-\boldsymbol{u}\|^{2}+\frac{\eta_{t}}{2}\left\|\boldsymbol{v}_{t}\right\|^{2}\right)$
$\displaystyle\leq\sum_{t=1}^{T}\left(\frac{1}{2\eta_{t}}\|\boldsymbol{w}_{t}-\boldsymbol{u}\|^{2}-\frac{1}{2\eta_{t}}\|\boldsymbol{w}_{t+1}-\boldsymbol{u}\|^{2}-\frac{\mu_{t}}{2}\|\boldsymbol{w}_{t+1}-\boldsymbol{u}\|^{2}\right.$
$\displaystyle\qquad\left.+\frac{\mu_{t}}{2}\|\boldsymbol{w}_{t+1}-\boldsymbol{w}_{t}\|\|\boldsymbol{w}_{t+1}+\boldsymbol{w}_{t}-2\boldsymbol{u}\|+\frac{\eta_{t}}{2}\left\|\boldsymbol{v}_{t}\right\|^{2}\right)$
$\displaystyle=\sum_{t=1}^{T}\left(\frac{1}{2\eta_{t}}\|\boldsymbol{w}_{t}-\boldsymbol{u}\|^{2}-\frac{1}{2\eta_{t+1}}\|\boldsymbol{w}_{t+1}-\boldsymbol{u}\|^{2}\right)$
$\displaystyle\qquad+\sum_{t=1}^{T}\frac{\mu_{t}}{2}\|\boldsymbol{w}_{t+1}-\boldsymbol{w}_{t}\|\|\boldsymbol{w}_{t+1}+\boldsymbol{w}_{t}-2\boldsymbol{u}\|+\sum_{t=1}^{T}\frac{\eta_{t}}{2}\left\|\boldsymbol{v}_{t}\right\|^{2}~{}.$

Summing and telescoping, we obtain

$\sum_{t=1}^{T}\left(f_{t}(\boldsymbol{w}_{t})-f_{t}(\boldsymbol{u})\right)\leq\frac{\|\boldsymbol{w}_{1}-\boldsymbol{u}\|^{2}}{2\eta_{1}}+\sum_{t=1}^{T}\frac{\mu_{t}}{2}\|\boldsymbol{w}_{t+1}-\boldsymbol{w}_{t}\|\|\boldsymbol{w}_{t+1}+\boldsymbol{w}_{t}-2\boldsymbol{u}\|+\sum_{t=1}^{T}\frac{\eta_{t}}{2}\left\|\boldsymbol{v}_{t}\right\|^{2}~{}.$

######  Corollary A.7.

Consider an OCO problem with losses
$f_{t}(\boldsymbol{\beta})=\langle\boldsymbol{g}_{t}^{+},\boldsymbol{\beta}\rangle+\left(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}-\boldsymbol{g}_{t}^{+}\|^{2}\right)\|\boldsymbol{\beta}\|^{2}$,
with $\boldsymbol{\beta}\in B$, $B=\\{\boldsymbol{x}|\|\boldsymbol{x}\|\leq
1/2\\}$.

Then, from Lemma A.5, we have

$\sum_{t=1}^{T}(f_{t}(\boldsymbol{\beta}_{t})-f_{t}(\boldsymbol{\beta}^{\star}))\leq
3/2+17/4\sum_{t=1}^{T}\frac{2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}~{}.$

######  Proof A.8.

From Lemma A.5,

$\displaystyle\sum_{t=1}^{T}(f_{t}(\boldsymbol{\beta}_{t})-f_{t}(\boldsymbol{\beta}^{\star}))\leq\frac{\|\boldsymbol{\beta}_{1}-\boldsymbol{\beta}^{\star}\|^{2}}{2\eta_{1}}+\sum_{t=1}^{T}\frac{\mu_{t}}{2}\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\|\boldsymbol{\beta}_{t+1}+\boldsymbol{\beta}_{t}-2\boldsymbol{\beta}^{\star}\|+\sum_{t=1}^{T}\frac{\eta_{t}}{2}\left\|\boldsymbol{v}_{t}\right\|^{2}~{}.$

Observe that
$\boldsymbol{\beta}_{t},\boldsymbol{\beta}_{t+1},\boldsymbol{\beta}^{\star}\in
B$, so
$\|\boldsymbol{\beta}_{t+1}+\boldsymbol{\beta}_{t}-2\boldsymbol{\beta}^{\star}\|\leq
2$. Moreover, we have $\mu_{t}\leq 2\|\boldsymbol{g}_{t}\|$. So, summing the
second term and using Lemma A.1, we obtain

$\sum_{t=1}^{T}\frac{\mu_{t}}{2}\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\|\boldsymbol{\beta}_{t+1}+\boldsymbol{\beta}_{t}-2\boldsymbol{\beta}^{\star}\|\leq\sum_{t=1}^{T}\mu_{t}\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\leq
3\sum_{t=1}^{T}\frac{2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}~{}.$

Noting that $\boldsymbol{v}_{t}\in\partial
f_{t}(\boldsymbol{\beta}_{t})=\boldsymbol{g}_{t}^{+}+2\boldsymbol{\beta}_{t}(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})$,
we have

$\left\|\boldsymbol{v}_{t}\right\|^{2}\leq\|\boldsymbol{g}_{t}^{+}\|^{2}+4\|\boldsymbol{\beta}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{g}_{t}\|+4\|\boldsymbol{\beta}_{t}\|^{2}\|\boldsymbol{g}_{t}\|(2\|\boldsymbol{g}_{t}^{+}\|)\leq
5\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{g}_{t}\|~{}.$

Hence, summing the third term, we have

$\sum_{t=1}^{T}\frac{\eta_{t}}{2}\left\|\boldsymbol{v}_{t}\right\|^{2}\leq\frac{5}{4}\sum_{t=1}^{T}\frac{2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}~{}.$

Now using the fact that $\frac{1}{\eta_{1}}=3$, we obtain

$\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{t})-f_{t}(\boldsymbol{\beta}^{\star})\leq
3/2+\frac{17}{4}\sum_{t=1}^{T}\frac{2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}~{}.$

######  Lemma A.9.

Consider an OCO problem with losses
$f_{t}(\boldsymbol{\beta})=\langle\boldsymbol{g}_{t}^{+},\boldsymbol{\beta}\rangle+\frac{\mu_{t}}{2}\|\boldsymbol{\beta}\|^{2}$
and
$\mu_{t}=2\left(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}-\boldsymbol{g}_{t}^{+}\|^{2}\right)$,
with $\boldsymbol{\beta}\in B=\\{\boldsymbol{x}|\|\boldsymbol{x}\|\leq r\\}$.
Define $\boldsymbol{\beta}_{T}^{*}:=\arg\min_{\boldsymbol{\beta}\in
B}\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta})$. Then we have

$\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{T}^{\star})\leq\max\left\\{\frac{-r\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{2},\frac{-\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}\right\\}~{}.$

######  Proof A.10.

We consider 2 cases: By definition
$\boldsymbol{\beta}^{\star}=\boldsymbol{\beta}_{T+1}=\prod_{B}(\hat{\boldsymbol{\beta}}_{T+1})$,
$f_{t}$ is $\mu_{t}$ strongly convex, where
$\mu_{t}=2(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})$.

  * •

If $\hat{\boldsymbol{\beta}}_{T+1}\in B$, that is
$\boldsymbol{\beta}_{T+1}=\hat{\boldsymbol{\beta}}_{T+1}=\frac{-\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}}{\sum_{t=1}^{T}\mu_{t}}$.
In this case,

$\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}^{*})=\left(\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right)\frac{-\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}}{\sum_{t=1}^{T}\mu_{t}}+\frac{\left\|-\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{\left(\sum_{t=1}^{T}\mu_{t}\right)^{2}}\frac{\sum_{t=1}^{T}\mu_{t}}{2}=-\frac{1}{2}\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{\sum_{t=1}^{T}\mu_{t}}~{}.$

  * •

If $\hat{\boldsymbol{\beta}}_{T+1}\not\in B$,
$\boldsymbol{\beta}_{T+1}=\prod_{B}(\hat{\boldsymbol{\beta}}_{T+1})=r\frac{-\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}}{\|-\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\|}$.
In this case,

$\|\hat{\boldsymbol{\beta}}_{T+1}\|=\left\|\frac{-\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}}{\sum_{t=1}^{T}\mu_{t}}\right\|\geq
r~{}.$

That is,

$\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|\geq
r\sum_{t=1}^{T}\mu_{t}~{}.$

Therefore, we have

$\displaystyle\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}^{*})$
$\displaystyle=-r\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|+r^{2}\sum_{t=1}^{T}\frac{\mu_{t}}{2}\left(\frac{\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\|}{\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\|}\right)^{2}\leq-r\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|+\frac{r^{2}}{2}\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{r}$
$\displaystyle=-\frac{r}{2}\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|~{}.$

In conclusion,

$\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}^{\star})\leq\max\left\\{\frac{-r\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{2},\frac{-\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}\right\\}~{}.$

######  Lemma A.11.

Let $\|\boldsymbol{g}_{t}\|\leq 1$,
$\boldsymbol{g}_{t}^{+}=h_{t}\boldsymbol{g}_{t}$ where $h_{t}\in[0,1]$, for
$t=1,\dots,T$. Then, we have

$\displaystyle\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle)$
$\displaystyle\geq-\langle\boldsymbol{g}_{t}^{+},\boldsymbol{\beta}_{t}\rangle-(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|\boldsymbol{\beta}_{t}\|^{2}$
$\displaystyle\quad-2\|\boldsymbol{g}_{t}\|\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|~{}.$

######  Proof A.12.

$\displaystyle\ln($ $\displaystyle
1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle)$
$\displaystyle\geq\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle+\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|)$
$\displaystyle=\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln\left(1+\frac{\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|}{1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle}\right)$
$\displaystyle\geq\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\frac{\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|}{1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle}$
$\displaystyle\geq\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\frac{\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|}{1-1/2}$
$\displaystyle\geq\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-2\|\boldsymbol{g}_{t}\|\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|,$

where in the last inequality we used the fact that
$\boldsymbol{g}_{t}^{+}=h_{t}\boldsymbol{g}_{t}$, $0\leq h_{t}\leq 1$,
$\|\boldsymbol{\beta}_{t}\|\leq 1/2$. The sum of these last terms is upper
bounded by a logarithmic term.

Now, considering the first two terms, we have

$\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)=f(\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle),$

where $f(x)=\ln(1-x)-\ln(1+(h_{t}-1)x)$ for $|x|\leq 1/2$.

To have the tightest inequality, we consider two cases separately.

Case $0\leq x\leq 1/2$. We consider $g(x)=f(x)-h_{t}x$. We have that the first
derivative of $g$ is negative for $0\leq x\leq 1/2$. Moreover, the function
$\phi(x)=x^{2}(2h_{t}-h_{t}^{2})$ is increasing for $0\leq x\leq 1/2$. Hence,
for $0\leq x\leq 1/2$, we have

$\frac{\ln(1-x)-\ln(1+(h_{t}-1)x)-h_{t}x}{x^{2}(2h_{t}-h_{t}^{2})}=\frac{g(x)}{\phi(x)}\geq\frac{g(1/2)}{\phi(1/2)}=\frac{-4\ln(1+h_{t})-2h_{t}}{2h_{t}-h_{t}^{2}}\geq-1,$

where in the last inequality we used the fact that $0\leq h_{t}\leq 1$.

Case $-1/2\leq x<0$. Here, we lower bound $f$ using a Taylor expansion:

$f(x)=f(0)+xf^{\prime}(0)+\frac{x^{2}}{2}f^{\prime\prime}(y),$

where $y$ is between $0$ and $x$. Denoting $a=h_{t}-1$, we have

$\displaystyle
f(x)=-xh_{t}-\frac{x^{2}}{2}\frac{(a+1)(2ay-a+1)}{(y-1)^{2}(ay+1)^{2}}~{}.$

Now, consider the quadratic term in the above expression. Dividing and
multiplying by $1-a\geq 0$, we have

$\frac{(1-a^{2})(2ay-a+1)}{(1-a)(y-1)^{2}(ay+1)^{2}}~{}.$

We are interested in keeping the term $1-a^{2}$ and upper bounding the rest.
Given that we are considering the case $-1/2\leq x<0$, we have $-1/2\leq y<0$.
So, we have

$2ay-a+1\leq 1-a-y+ay=(1-a)(1-y)~{}.$

and

$\displaystyle\frac{2ay-a+1}{(1-a)(y-1)^{2}(ay+1)^{2}}$
$\displaystyle\leq\frac{(1-a)(1-y)}{(1-a)(y-1)^{2}(ay+1)^{2}}=\frac{1}{(1-y)(ay+1)^{2}}\leq
1~{}.$

Hence, putting all together, we have

$\displaystyle\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)$
$\displaystyle-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)\geq-
h_{t}\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle-(1-a^{2})(\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)^{2}$
$\displaystyle\geq-
h_{t}\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle-(1-a^{2})\|\boldsymbol{g}_{t}\|^{2}\|\boldsymbol{\beta}_{t}\|^{2}$
$\displaystyle=-\langle\boldsymbol{g}^{+}_{t},\boldsymbol{\beta}_{t}\rangle-(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}\|^{2}(h_{t}-1)^{2})\|\boldsymbol{\beta}_{t}\|^{2}$
$\displaystyle=-\langle\boldsymbol{g}^{+}_{t},\boldsymbol{\beta}_{t}\rangle-(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|\boldsymbol{\beta}_{t}\|^{2}~{}.$

Now, we present the full proof of Theorem 5.1. Note that a part of the proof
of Theorem 6.1 is similar to the proof of Theorem 5.1.

######  Proof A.13 (Proof of Theorem 5.1).

From the (2), we get

$\operatorname{Wealth}_{t}=\operatorname{Wealth}_{t-1}-\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\rangle-\langle\boldsymbol{g}_{t}^{+},\boldsymbol{w}_{t+1}\rangle~{}.$

Using the fact that the algorithm predicts with
$\boldsymbol{w}_{t}=\boldsymbol{\beta}_{t}\operatorname{Wealth}_{t-1}$, we
obtain

$\operatorname{Wealth}_{t}=\operatorname{Wealth}_{t-1}\frac{1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle}{1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle}~{}.$

This implies that
$\ln\operatorname{Wealth}_{T}=\ln\epsilon+\sum_{t=1}^{T}\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle)$.

Using Lemma A.11 and Lemma A.1, we have

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\left(\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle)\right)$
$\displaystyle\geq\sum_{t=1}^{T}\left[-\langle\boldsymbol{g}^{+}_{t},\boldsymbol{\beta}_{t}\rangle-(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|\boldsymbol{\beta}_{t}\|^{2}-2\|\boldsymbol{g}_{t}\|\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\right]$
$\displaystyle\geq\sum_{t=1}^{T}\Bigg{[}-\langle\boldsymbol{g}^{+}_{t},\boldsymbol{\beta}_{t}\rangle-(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|\boldsymbol{\beta}_{t}\|^{2}-\frac{6\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}\Bigg{]}$
$\displaystyle\geq-3\ln\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)-\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{t})~{}.$

Where $f_{t}$ is as defined in Corollary A.7. Applying Corollary, and defining
$\mu_{t}$ as in Lemma A.9, we have

$\displaystyle\geq-3/2-7.25\ln\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)-\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}^{\star})$
$\displaystyle\geq-3/2-7.25\ln\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)-\max\left\\{\frac{-\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{4},\frac{-\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}\right\\}$
$\displaystyle=-3/2-7.25\ln\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)+\min\left\\{\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{4},\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}\right\\}~{}.$

The last inequality is from Lemma A.9. Next, we perform a case analysis to
derive the upper bound for $\operatorname{Regret}_{T}$.

If
$\min\left\\{\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{4},\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}\right\\}=\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{4}$,
then

$\operatorname{Wealth}_{T}\geq\frac{e^{-3/2}}{\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)^{7.25}}\exp\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{4}~{}.$

By Cutkosky and Orabona (2018, Lemma 18), we have

$\displaystyle\operatorname{Regret}_{T}(\boldsymbol{u})\leq
4\|\boldsymbol{u}\|\left(\ln\frac{4\|\boldsymbol{u}\|\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)^{7.25}}{e^{-3/2}}-1\right)~{}.$

If
$\min\left\\{\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{4},\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}\right\\}=\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}$
, then

$\operatorname{Wealth}_{T}\geq\frac{e^{-3/2}}{\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)^{7.25}}\exp\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}~{}.$

By Orabona and Tommasi (2017, Lemma 1), we have

$\displaystyle\operatorname{Regret}_{T}(\boldsymbol{u})\leq-\frac{e^{-3/2}}{\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)^{7.25}}$
$\displaystyle+\|\boldsymbol{u}\|\sqrt{2\sum_{t=1}^{T}(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})\ln\left(1+\frac{\left(\sum_{t=1}^{T}\mu_{t}\right)\|\boldsymbol{u}\|^{2}\left(1+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)^{14.5}}{e^{-3}}\right)}~{}.$

Finally, combining the two cases result gives the regret bound

$\displaystyle\operatorname{Regret}_{T}(\boldsymbol{u})$
$\displaystyle=\mathcal{O}\left(\max\left\\{\|\boldsymbol{u}\|\ln\left(\|\boldsymbol{u}\|\left(1+\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)\right)\right.\right.,$
$\displaystyle\left.\left.\|\boldsymbol{u}\|\sqrt{\sum_{t=1}^{T}(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})\cdot\ln\left(1+\|\boldsymbol{u}\|\sum_{t=1}^{T}(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})\right)}\right\\}\right).$

##  Appendix B Proof of Theorem 6.1

In this section, we present the proofs of Theorem 6.1 and the Lemmas required
for its proof.

Lemma B.3 shows that the regret of $\phi_{t}(\boldsymbol{\beta}_{t})$ upper
bounds the regret of $f_{t}(\boldsymbol{\beta}_{t})$, and Lemma B.1 gives the
upper bound of the regret of running $\phi_{t}(\boldsymbol{\beta}_{t})$. Thus
we are able to obtain similar results as in Corollary A.7. Lemma B.5 proves
that Algorithm 2 guarantees $\|\boldsymbol{\beta}_{t}\|\leq 1/2$ which removes
the projection step, and leads to the closed form updates.

######  Lemma B.1.

For $t=1,\dots,T$, $\boldsymbol{\beta}_{t}$ are outputs of running OGD with
stepsizes: $\eta_{t}=\frac{1}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}$ on the
strongly convex losses $\phi_{t}(\boldsymbol{\beta})$ defined as following:

  * •

If $\|\boldsymbol{\beta}_{t}\|<\frac{3}{8}$,
$\phi_{t}(\boldsymbol{\beta})=f_{t}(\boldsymbol{\beta})$,

  * •

If $\frac{3}{8}\leq\|\boldsymbol{\beta}_{t}\|\leq\frac{1}{2}$,
$\phi_{t}(\boldsymbol{\beta})=C\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{\beta}\|^{2}$,

where $\boldsymbol{\beta}_{t}\in B$ and
$B=\\{\boldsymbol{x}:\|\boldsymbol{x}\|\leq\frac{1}{2}\\}$.
$\phi_{t}(\boldsymbol{\beta})$ is $\mu_{t}$ strongly convex.
$\boldsymbol{\beta}_{1}^{\star}\triangleq\arg\min_{\boldsymbol{\beta}\in
B_{1}}\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta})$, where
$B_{1}=\\{\boldsymbol{x}:\|\boldsymbol{x}\|\leq\frac{1}{4}\\}$. Then, for
$C\geq 3$ we have

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle(\phi_{t}(\boldsymbol{\beta}_{t})-\phi_{t}(\boldsymbol{\beta}_{1}^{\star}))\leq-\frac{5C^{2}}{4}\ln(1/\eta_{1}-2)+\frac{1}{2\eta_{1}}+\frac{5C^{2}}{4}\ln\left(1/\eta_{1}-2+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)~{}.$

######  Proof B.2.

Applying Lemma A.5, we have

$\displaystyle\sum_{t=1}^{T}(\phi_{t}(\boldsymbol{\beta}_{t})-\phi_{t}(\boldsymbol{\beta}_{1}^{\star}))\leq\frac{\|\boldsymbol{\beta}_{1}-\boldsymbol{\beta}_{1}^{\star}\|^{2}}{2\eta_{1}}+\sum_{t=1}^{T}\left(\mu_{t}\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|+\frac{\eta_{t}\left\|\nabla\phi_{t}(\boldsymbol{\beta}_{t})\right\|^{2}}{2}\right)~{}.$

We now consider the two possible cases for $h_{t}$.

If $\phi_{t}(\boldsymbol{\beta})=f_{t}(\boldsymbol{\beta})$, then

$\left\|\nabla\phi_{t}(\boldsymbol{\beta}_{t})\right\|=\|\boldsymbol{g}_{t}^{+}+2\boldsymbol{\beta}_{t}(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|\leq
3\|\boldsymbol{g}_{t}^{+}\|~{}.$

Hence, $\left\|\nabla\phi_{t}(\boldsymbol{\beta}_{t})\right\|^{2}\leq
9\|\boldsymbol{g}_{t}^{+}\|^{2}\leq
9\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|$. Moreover,
$\mu_{t}=2(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\geq
2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|$.

If
$\phi_{t}(\boldsymbol{\beta})=C\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{\beta}_{t}\|^{2}$,
then

$\left\|\nabla\phi_{t}(\boldsymbol{\beta}_{t})\right\|=\left\|2C\boldsymbol{\beta}_{t}\|\boldsymbol{g}_{t}^{+}\|\right\|\leq
C\|\boldsymbol{g}_{t}^{+}\|~{}.$

Hence,
$\left\|\nabla\phi_{t}(\boldsymbol{\beta}_{t})\right\|^{2}=C^{2}\|\boldsymbol{g}_{t}^{+}\|^{2}\leq
C^{2}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|$. Moreover, assuming
$C\geq 1$, we have $\mu_{t}=2C\|\boldsymbol{g}_{t}^{+}\|\geq
2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|$.

Consequently, with $C\geq 3$, we have

$\sum_{t=1}^{T}\frac{\eta_{t}\left\|\nabla\phi_{t}(\boldsymbol{\beta}_{t})\right\|^{2}}{2}\leq\frac{1}{2}\sum_{t=1}^{T}\frac{C^{2}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}\leq\frac{C^{2}}{4}\sum_{t=1}^{T}\frac{2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}+2\sum_{i=1}^{t-1}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}~{}.$

Applying Lemma B.7 and $C\geq 3$, we thus obtain

$\displaystyle\sum_{t=1}^{T}\phi_{t}(\boldsymbol{\beta}_{t})$
$\displaystyle-\phi_{t}(\boldsymbol{\beta}_{1}^{\star})\leq\frac{1}{2\eta_{1}}+\left(\max\left(C^{2},3\right)+\frac{C^{2}}{4}\right)\sum_{t=1}^{T}\frac{2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}+2\sum_{i=1}^{t-1}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}$
$\displaystyle\leq\frac{1}{2\eta_{1}}+\left(\max\left(C^{2},3\right)+\frac{C^{2}}{4}\right)\sum_{t=1}^{T}\frac{2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}-2+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}$
$\displaystyle\leq\frac{1}{2\eta_{1}}+\left(\max\left(C^{2},3\right)+\frac{C^{2}}{4}\right)\left(\ln\left(1/\eta_{1}-2+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)-\ln(1/\eta_{1}-2)\right)$
$\displaystyle=\frac{5C^{2}}{4}\ln\left(1/\eta_{1}-2+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)+\frac{1}{2\eta_{1}}-\frac{5C^{2}}{4}\ln(1/\eta_{1}-2)~{}.$

######  Lemma B.3.

Under conditions and notations of Lemma B.1 and for any $C\geq 9$, we have

$f_{t}(\boldsymbol{\beta}_{t})-f_{t}(\boldsymbol{\beta}_{1}^{\star})\leq\phi_{t}(\boldsymbol{\beta}_{t})-\phi_{t}(\boldsymbol{\beta}_{1}^{\star})~{}.$

######  Proof B.4.

We consider the two cases for the losses $h_{t}$.

When $\frac{3}{8}\leq\|\boldsymbol{\beta}_{t}\|\leq\frac{1}{2}$, we have
$\phi_{t}(\boldsymbol{\beta}_{t})=C\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{\beta}_{t}\|^{2}$.
Hence, we have

$\phi_{t}(\boldsymbol{\beta}_{t})-\phi_{t}(\boldsymbol{\beta}_{1}^{\star})=C\|\boldsymbol{g}_{t}^{+}\|\left(\|\boldsymbol{\beta}_{t}\|^{2}-\|\boldsymbol{\beta}^{\star}_{1}\|^{2}\right)~{}.$

Moreover,

$\displaystyle
f_{t}(\boldsymbol{\beta}_{t})-f_{t}(\boldsymbol{\beta}_{1}^{\star})$
$\displaystyle=\langle\boldsymbol{g}_{t}^{+},\boldsymbol{\beta}_{t}-\boldsymbol{\beta}^{\star}_{1}\rangle+(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})\|\boldsymbol{\beta}_{t}\|^{2}-(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})\|\boldsymbol{\beta}^{\star}_{1}\|^{2}$
$\displaystyle\leq\|\boldsymbol{g}_{t}^{+}\|(\|\boldsymbol{\beta}_{t}\|+\|\boldsymbol{\beta}^{\star}_{1}\|)+\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{g}_{t}\|(2-h_{t})(\|\boldsymbol{\beta}_{t}\|^{2}-\|\boldsymbol{\beta}^{\star}_{1}\|^{2})$
$\displaystyle\leq\|\boldsymbol{g}_{t}^{+}\|(\|\boldsymbol{\beta}_{t}\|+\|\boldsymbol{\beta}^{\star}_{1}\|)+\|\boldsymbol{g}_{t}^{+}\|(\|\boldsymbol{\beta}_{t}\|^{2}-\|\boldsymbol{\beta}^{\star}_{1}\|^{2})~{}.$

Hence, we have
$f_{t}(\boldsymbol{\beta}_{t})-f_{t}(\boldsymbol{\beta}^{\star}_{1})\leq\phi_{t}(\boldsymbol{\beta}_{t})-\phi_{t}(\boldsymbol{\beta}^{\star}_{1})$
iff

$\|\boldsymbol{\beta}_{t}\|+\|\boldsymbol{\beta}^{\star}_{1}\|+\|\boldsymbol{\beta}_{t}\|^{2}-\|\boldsymbol{\beta}^{\star}_{1}\|^{2}\leq
C\left(\|\boldsymbol{\beta}_{t}\|^{2}-\|\boldsymbol{\beta}^{\star}_{1}\|^{2}\right),$

that is

$C\geq\frac{\|\boldsymbol{\beta}_{t}\|+\|\boldsymbol{\beta}^{\star}_{1}\|+\|\boldsymbol{\beta}_{t}\|^{2}-\|\boldsymbol{\beta}^{\star}_{1}\|^{2}}{\|\boldsymbol{\beta}_{t}\|^{2}-\|\boldsymbol{\beta}^{\star}_{1}\|^{2}}=\frac{1}{\|\boldsymbol{\beta}_{t}\|-\|\boldsymbol{\beta}^{\star}_{1}\|}+1~{}.$

Using the fact that
$\frac{1}{\|\boldsymbol{\beta}_{t}\|-\|\boldsymbol{\beta}^{\star}_{1}\|}+1\leq
9$, gives the stated value for C. When
$\|\boldsymbol{\beta}_{t}\|\leq\frac{3}{8}$, we have
$\phi_{t}(\boldsymbol{\beta})=f_{t}(\boldsymbol{\beta})$ and
$f_{t}(\boldsymbol{\beta}_{t})-f_{t}(\boldsymbol{\beta}^{\star}_{1})\leq\phi_{t}(\boldsymbol{\beta}_{t})-\phi_{t}(\boldsymbol{\beta}^{\star}_{1})$
is trivially true.

######  Lemma B.5.

Under the assumptions of Theorem 6.1 and the notation of Algorithm 2, let
$1/\eta_{1}\geq\max(2C,16)$. Then, $\|\boldsymbol{\beta}_{t}\|\leq\frac{1}{2}$
for all $t=1,\dots,T$.

######  Proof B.6.

We prove this by induction: Base case:
$\boldsymbol{\beta}_{0}=\boldsymbol{0}$,
$\|\boldsymbol{\beta}_{0}\|\leq\frac{1}{2}$ is trivially true.
Induction step: Suppose $\|\boldsymbol{\beta}_{t}\|\leq\frac{1}{2}$, we prove
$\|\boldsymbol{\beta}_{t+1}\|\leq\frac{1}{2}$. We perform the following case
analysis:

If $\frac{3}{8}\leq\|\boldsymbol{\beta}_{t}\|\leq\frac{1}{2}$,

$\|\boldsymbol{\beta}_{t+1}\|=\left\|\boldsymbol{\beta}_{t}-\frac{2C\boldsymbol{\beta}_{t}\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}\right\|\leq\|\boldsymbol{\beta}_{t}\|\left(1-\frac{2C\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}\right)\leq\|\boldsymbol{\beta}_{t}\|\leq\frac{1}{2}~{}.$

If $\|\boldsymbol{\beta}_{t}\|<\frac{3}{8}$

$\displaystyle\|\boldsymbol{\beta}_{t+1}\|$
$\displaystyle=\left\|\boldsymbol{\beta}_{t}-\frac{\boldsymbol{g}_{t}^{+}+2\boldsymbol{\beta}_{t}(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}\right\|\leq\|\boldsymbol{\beta}_{t}\|+\left\|\frac{\boldsymbol{g}_{t}^{+}+2\boldsymbol{\beta}_{t}(2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|-\|\boldsymbol{g}_{t}^{+}\|^{2})}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}\right\|$
$\displaystyle\leq\frac{3}{8}+2\eta_{1}\leq\frac{1}{2}~{}.$

######  Lemma B.7.

Under the assumptions of Theorem 6.1 and the notation of Algorithm 2, we have,
for any $C\geq 1$, we have

$\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\leq\max\left(C,3\right)\frac{\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}+2\sum_{i=1}^{t-1}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}~{}.$

and

$\mu_{t}\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\leq\max\left(C^{2},3\right)\frac{2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}+2\sum_{i=1}^{t-1}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}~{}.$

######  Proof B.8.

We consider the two cases for $h_{t}$.

  * •

If
$\phi_{t}(\boldsymbol{\beta})=C\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{\beta}\|^{2}$,
we have $\mu_{t}=2C\|\boldsymbol{g}_{t}^{+}\|$. Assuming $C\geq 1$ we have
$2C\|\boldsymbol{g}_{t}^{+}\|\geq
2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|$. Moreover,
$\left\|\nabla\phi_{t}(\boldsymbol{\beta}_{t})\right\|=2C\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{\beta}_{t}\|\leq
C\|\boldsymbol{g}_{t}^{+}\|$. So, we have

$\mu_{t}\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\leq
2C\|\boldsymbol{g}_{t}^{+}\|\frac{C\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}+\sum_{i=1}^{t-1}\mu_{i}}\leq
C^{2}\frac{2\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{g}_{t}\|}{1/\eta_{1}+2\sum_{i=1}^{t-1}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}~{}.$

  * •

If $\phi_{t}(\boldsymbol{\beta})=f_{t}(\boldsymbol{\beta})$, we have

$2\|\boldsymbol{g}_{t}\|\geq
2\|\boldsymbol{g}_{t}\|^{2}\geq\mu_{t}=2(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})=2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|(2-h_{t})\geq
2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|~{}.$

Moreover, $\left\|\nabla\phi_{t}(\boldsymbol{\beta}_{t})\right\|\leq
3\|\boldsymbol{g}_{t}^{+}\|$. So, we obtain
$\mu_{t}\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\leq
3\frac{2\|\boldsymbol{g}_{t}^{+}\|\|\boldsymbol{g}_{t}\|}{1/\eta_{1}+2\sum_{i=1}^{t-1}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}$
.

Taking the maximum of the two cases, we obtain the stated upper bounds.

We can now present the proof of Theorem 6.1.

######  Proof B.9 (Proof of Theorem 6.1).

Using Lemma A.11 in the first inequality, and Lemma B.7 in the second
inequality, we have

$\displaystyle\sum_{t=1}^{T}\left(\ln(1-\langle\boldsymbol{g}_{t},\boldsymbol{\beta}_{t}\rangle)-\ln(1+\langle\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t},\boldsymbol{\beta}_{t+1}\rangle)\right)$
$\displaystyle\geq\sum_{t=1}^{T}\left(-\langle\boldsymbol{g}^{+}_{t},\boldsymbol{\beta}_{t}\rangle-(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|\boldsymbol{\beta}_{t}\|^{2}-2\|\boldsymbol{g}_{t}\|\|\boldsymbol{\beta}_{t+1}-\boldsymbol{\beta}_{t}\|\right)$
$\displaystyle\geq\sum_{t=1}^{T}\left(-\langle\boldsymbol{g}^{+}_{t},\boldsymbol{\beta}_{t}\rangle-(\|\boldsymbol{g}_{t}\|^{2}-\|\boldsymbol{g}_{t}^{+}-\boldsymbol{g}_{t}\|^{2})\|\boldsymbol{\beta}_{t}\|^{2}-C\frac{2\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|}{1/\eta_{1}-2+2\sum_{i=1}^{t}\|\boldsymbol{g}_{i}\|\|\boldsymbol{g}_{i}^{+}\|}\right)$
$\displaystyle\geq-C\ln\left(1/\eta_{1}-2+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)-\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{t})$
$\displaystyle\geq-\frac{1}{2\eta_{1}}+\frac{5C^{2}}{4}\ln(1/\eta_{1}-2)-\left(\frac{5C^{2}}{4}+C\right)\ln\left(1/\eta_{1}-2+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)-\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{1}^{\star})$
$\displaystyle\geq-\left(\frac{5C^{2}}{4}+C\right)\ln\left(1/\eta_{1}-2+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)-\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{1}^{\star})$
$\displaystyle=-110.25\ln\left(16+2\sum_{t=1}^{T}\|\boldsymbol{g}_{t}\|\|\boldsymbol{g}_{t}^{+}\|\right)-\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{1}^{\star})~{},$

The second to the last inequality is from Lemma B.3 and Lemma B.1. $C=9$ gives
rise to the last inequality and the last equation. We now use Lemma A.9 to
obtain

$-\sum_{t=1}^{T}f_{t}(\boldsymbol{\beta}_{1}^{\star})\geq-\max\left\\{\frac{-\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{8},\frac{-\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}\right\\}\\\
=\min\left\\{\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|}{8},\frac{\left\|\sum_{t=1}^{T}\boldsymbol{g}_{t}^{+}\right\|^{2}}{2\sum_{t=1}^{T}\mu_{t}}\right\\}~{}.$

The rest proof is similar to the proof of Theorem 5.1. Finally, we obtain the
same bound as in Theorem 5.1, up to constants hidden in big O notation.

##  Appendix C Proof of Theorem 7.1

######  Proof C.1.

In each coordinate, we perform the regret decomposition as following:

$\displaystyle\operatorname{Regret}$
${}_{T}(\boldsymbol{u})=\sum_{t=1}^{T}\ell_{t}(\boldsymbol{w}_{t})-\ell_{t}(\boldsymbol{u})=\sum_{t=1}^{T}\hat{\ell}_{t}(\boldsymbol{w}_{t})-\hat{\ell}_{t}(\boldsymbol{w}_{t+1})+\hat{\ell}_{t}(\boldsymbol{w}_{t+1})-\hat{\ell}_{t}(\boldsymbol{u})$
$\displaystyle\leq\sum_{t=1}^{T}\langle\boldsymbol{g}_{t},\boldsymbol{w}_{t}-\boldsymbol{w}_{t+1}\rangle+\langle\boldsymbol{g}_{t}^{+},\boldsymbol{w}_{t+1}-\boldsymbol{u}\rangle=\sum_{t=1}^{T}\sum_{i=1}^{d}g_{t,i}(w_{t,i}-w_{t+1,i})+g_{t,i}^{+}(w_{t+1,i}-u_{i})$
$\displaystyle=\sum_{i=1}^{d}\sum_{t=1}^{T}g_{t,i}(w_{t,i}-w_{t+1,i})+g_{t,i}^{+}(w_{t+1,i}-u_{i})$
$\displaystyle=\sum_{i=1}^{d}u_{i}\left(-\sum_{t=1}^{T}g_{t,i}^{+}\right)-\left(-\sum_{t=1}^{T}(g_{t,i}(w_{t,i}-w_{t+1,i})+g_{t,i}^{+}w_{t+1,i})\right)~{},$

where $\boldsymbol{g}_{t}\in\partial\ell_{t}(\boldsymbol{w}_{t})$,
$\boldsymbol{g}_{t}\in\partial\hat{\ell}_{t}(\boldsymbol{w}_{t})$,
$\boldsymbol{g}_{t}^{+}\in\partial\hat{\ell}_{t}(\boldsymbol{w}_{t+1})$.

Define
$\operatorname{Wealth}_{T,i}=\epsilon-\sum_{t=1}^{T}(g_{t,i}(w_{t,i}-w_{t+1,i})+g_{t,i}^{+}w_{t+1,i})$.
Suppose we obtain a bound
$\operatorname{Wealth}_{T,i}\geq\psi_{T}\left(\sum_{i=1}^{T}g_{t,i}^{+}\right)$
for some $\psi_{T}$. Using the definition of Fenchel conjugate, and the lower
bound on the wealth in each coordinate, we have

$\displaystyle\operatorname{Regret}_{T}(\boldsymbol{u})$
$\displaystyle\leq\sum_{i=1}^{d}u_{i}\left(-\sum_{t=1}^{T}g_{t,i}^{+}\right)-(\operatorname{Wealth}_{T,i}-\epsilon)\leq\sum_{i=1}^{d}\epsilon+u_{i}\left(-\sum_{t=1}^{T}g_{t,i}^{+}\right)-\psi_{T}\left(\sum_{i=1}^{T}g_{t,i}^{+}\right)$
$\displaystyle\leq\sum_{i=1}^{d}\epsilon+\sup_{y}y\cdot
u_{i}-\psi_{T}(y)=\sum_{i=1}^{d}\epsilon+\psi^{*}_{T}(u_{i})~{}.$

In each coordinate, Algorithm 3 is a specific case of running Algorithm 2 with
$d=1$. Applying the result in Theorem 6.1, we obtain the final bound.

##  Appendix D List of Datasets

In our empirical evaluation, we used 3 regression datasets and 3
classification datasets from the LIBSVM website (Chang and Lin, 2001) and
OpenML (Vanschoren et al., 2013), randomly selected among the ones with a
large number of samples. For the OpenML datasets, categorical features are
one-hot-encoded. A short summary of the datasets is in Table 1.

Table 1: Datasets in experiments. Dataset | Type | Number of samples | Number of features
---|---|---|---
CPU-act | classification | 8192 | 21
2dPlane | classification | 40768 | 10
Houses | classification | 20640 | 8
Rainfall | regression | 16755 | 3
Bank32nh | regression | 8192 | 32
Houses-8L | regression | 22784 | 8