# Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm

Changlong Wu
CSoI
Purdue University
<EMAIL_ADDRESS>Mohsen Heidari
CSoI
Purdue University
<EMAIL_ADDRESS>Ananth Grama
CSoI
Purdue University
<EMAIL_ADDRESS>Wojciech Szpankowski
CSoI
Purdue University
<EMAIL_ADDRESS>
###### Abstract

We study the sequential general online regression, known also as the
sequential probability assignments, under logarithmic loss when compared
against a broad class of experts. We focus on obtaining tight, often matching,
lower and upper bounds for the sequential minimax regret that are defined as
the excess loss it incurs over a class of experts. After proving a general
upper bound we consider some specific classes of experts from Lipschitz class
to bounded Hessian class and derive matching lower and upper bounds with
provably optimal constants. Our bounds work for a wide range of values of the
data dimension and the number of rounds. To derive lower bounds, we use tools
from information theory (e.g., Shtarkov sum) and for upper bounds, we resort
to new “smooth truncated covering” of the class of experts. This allows us to
find constructive proofs by applying a simple and novel truncated Bayesian
algorithm. Our proofs are substantially simpler than the existing ones and yet
provide tighter (and often optimal) bounds.

##  1 Introduction

In the online learning and/or sequential probability assignments arising in
information theory, portfolio optimization, and machine learning the training
algorithm consumes $d$ dimensional data in rounds $t\in\\{1,2,\ldots,T\\}$ and
predicts the label $\hat{y}_{t}$ based on data received and labels observed so
far. Then the true label $y_{t}$ is revealed and the loss
$\ell(y_{t},\hat{y}_{t})$ is incurred. The (pointwise) _regret_ is defined as
the (excess) loss incurred by the algorithm over a class of experts, also
called the hypothesis class.

More precisely, at each round $t\geq 1$ the learner obtains a $d$ dimensional
input/ feature vector ${\bf x}_{t}\in{\mathbb{R}}^{d}$. In addition to ${\bf
x}_{t}$, the learner may use the past observations $({\bf x}_{r},y_{r})$,
$r<t$ to make a prediction $\hat{y}_{t}$ of the true label. Therefore, the
prediction can be written as $\hat{y}_{t}=\phi_{t}(y^{t-1},{\bf x}^{t})$,
where $\phi_{t}$ represents the strategy of the learner to obtain its
prediction based on the past and current observations. Once a prediction is
made, the nature reveals the true label $y_{t}$ and the learner incurs loss
$\ell:\hat{\mathcal{Y}}\times\mathcal{Y}\rightarrow{\mathbb{R}}$, where
$\hat{{\cal Y}}$ and ${\cal Y}$ are the prediction and label domains
respectively. Hereafter, we assume throughout $\hat{{\cal Y}}=[0,1]$,
$\mathcal{Y}=\\{0,1\\}$ with logarithmic loss

${\ell}(\hat{y}_{t},y_{t})=-y_{t}\log(\hat{y}_{t})-(1-y_{t})\log(1-\hat{y}_{t}).$
(1)

In regret analysis, we are interested in comparing the accumulated loss of the
learner with that of the best strategy within a predefined class of predictors
(experts) denoted as $\mathcal{H}$. More precisely, ${\cal H}$ is a collection
of predicting functions $h:{\mathbb{R}}^{d}\mapsto\hat{{\cal Y}}$ with input
being ${\bf x}_{t}$ at time $t$. Therefore, given a learner $\phi_{t},t>0$ and
$(y_{t},{\bf x}_{t})_{t=1}^{T}$ after $T$ rounds the pointwise regret is
defined as

$\displaystyle R(\hat{y}^{T},y^{T},\mathcal{H}|{\bf x}^{T})=$
$\displaystyle\sum_{t=1}^{T}\ell(\hat{y}_{t},y_{t})-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(h(x_{t}),y_{t}),$

where $\hat{y}_{t}=\phi_{t}(y^{t-1},{\bf x}^{t})$. Observe that the first term
above represents the accumulated loss incurred by the learning algorithm,
while the second summation deals with the best prediction within
$\mathcal{H}$. There are two useful perspectives on analyzing the regret,
highlighted next.

Fixed Design: This point of view studies the minimal regret for the worst
realization of the label with the feature vector ${\bf x}^{T}$ known in
advance. Suppose that the learner has a fixed strategy $\phi_{t},t>0$. Then,
the fixed design minimax regret for a given ${\bf x}^{T}$ is defined as

$r_{T}^{*}({\cal H}|{\bf
x}^{T})=\inf_{\phi^{T}}\sup_{y^{T}}R(\phi^{T},y^{T},\mathcal{H}|{\bf x}^{T}).$
(2)

Further, the fixed design maximal minimax regret is

$r^{*}_{T}({\cal H})=\sup_{{\bf
x}^{T}}\inf_{\phi^{T}}\sup_{y^{T}}R(\phi^{T},y^{T},\mathcal{H}|{\bf x}^{T}).$
(3)

Sequential Design: In this paper we mostly focus on the sequential or agnostic
regret in which the optimization on regret is performed at every time $t$
without knowing in advance ${\bf x}^{T}$ or $y^{T}$. Then the sequential
(maximal) minimax regret is [22]

$r^{a}_{T}(\mathcal{H})=\sup_{{\bf
x}_{1}}\inf_{\hat{y}_{1}}\sup_{y_{1}}\cdots\sup_{{\bf
x}_{T}}\inf_{\hat{y}_{T}}\sup_{y_{T}}R(\hat{y}^{T},{y}^{T},{\cal H}|{\bf
x}^{T}).$ (4)

In [36] it is shown that $r^{a}_{T}(\mathcal{H})\geq r^{*}_{T}(\mathcal{H})$
for all ${\cal H}$. We will use $r^{*}_{T}({\cal H})$ as our tool to derive
lower bounds for $r^{a}_{T}(\mathcal{H})$.

Our main goal is to gain insights into the growth of the sequential regret
$r^{a}_{T}(\mathcal{H})$ for various classes ${\cal H}$ and to show how the
structure of ${\cal H}$, as well as the relationship between $d$ and $T$
impact the precise growth of the regret. To see this more clearly, we briefly
review the regret in universal source coding.

### Regrets in Information Theory.

In universal compression the dependence between the regret and the reference
class was intensively studied [9, 19, 25, 26, 30, 37, 38]. Here there is no
feature vector ${\bf x}^{t}$ and the dimension $d=1$. A sequence $y^{T}$ is
generated by a source $P$ that belongs to a class of sources $\mathcal{S}$,
which can be viewed as the reference class ${\cal H}$ in online learning. The
minimax regret for the logarithmic loss is then [8, 29, 9]
$r_{T}^{*}(\mathcal{S})=\min_{Q}\max_{y^{T}}[-\log
Q(y^{T})+\log\sup_{P\in\mathcal{S}}P(y^{T})],$ where $Q$ is the universal
probability assignment approximating the unknown $P$. The main question is how
the structure of $\mathcal{S}$ impacts the growth of the minimax regret. Let
$m$ denote the alphabet size (in online learning, we only consider $m=2$). It
is known [9, 19, 25, 26, 30, 37, 38] that for Markov sources of order $r$ the
regret grows like $m^{r}(m-1)/2\log T$ for fixed $m$ [25, 19, 26, 32] while in
[32] the minimax regret was analyzed for all ranges of $m$ and $T$. For non-
Markovian sources the growth is super logarithmic. For example, for renewal
sources of order $r$ the regret is $\Theta(T^{r/(r+1)})$ [6] and the precise
constant in front of the leading term is know for $r=1$ [10]. However, it
should be pointed out that [5, 1] studied the general classes of densities
smoothly parameterized by a $d$-dimensional data to obtain general results for
the minimax regret that can be phrased as an online regret.

### Main Contributions.

Our main results are summarized in Table 1. One of the main contributions of
this paper is the concept of a global sequential covering used to prove
_constructively_ general upper bounds on the regret (Theorem 1). We establish
Theorem 1 via a novel smooth truncation approach enabling us to find tight
upper bounds that subsume the state-of-the-art results (e.g., [21, 3])
obtained non-algorithmically. In fact, Algorithm 2 developed in this paper
achieves these bounds. Moreover, Theorem 1 provides optimal constants that are
crucial to derive the best bounds in special cases discussed next. For general
Lipschitz parametric class ${\cal H}$, in Theorem 2, we derive the upper bound
$d\log(T/d)+O(d)$ for $T>d$. In Theorem 3, we show that the leading constant
$1$ (in front of $d\log(T/d)$) is optimal for $T\gg d\log(T)$. Furthermore, we
obtain the best constant for the leading term $\frac{d}{2}\log(T/d)$ when the
Hessian of $\log f$ is bounded for any function $f\in{\cal H}$ (see Theorem
4). Then, we show in Theorem 5 that the constant $\frac{1}{2}$ in our bound is
optimal for functions of the form $f(\langle{\bf w},{\bf x}\rangle)$, where
${\bf w}\in{\mathbb{R}}^{d}$ is the parameter of the function, $\langle{\bf
w},{\bf x}\rangle$ is the inner product in ${\mathbb{R}}^{d}$, ${\bf w}$ and
${\bf x}$ are in a general $\ell_{s}$-norm unite ball, and $T\gg d^{(s+2)/s}$.
This result recovers all the lower bounds in [28] obtained for the logistic
regression (however, the technique of [28] works for other functions with
bounded second derivatives, like the probit function). Lastly, when $d\geq T$
, for a linear function of the form $|\langle{\bf w},{\bf x}\rangle|$ we show
that the growth is at least $\Omega(T^{s/(s+1)})$ under $\ell_{s}$ ball and at
most $\tilde{O}(T^{2/3})$ for $\ell_{2}$ ball (see Theorem 6 and Example 2).

The main technique used in our paper (smooth truncation) is novel with
potential other applications (e.g., average minimax regret). Instead of the
conventional approach for truncating only the values close to $\\{0,1\\}$, we
truncate all values in $[0,1]$ in a smooth way (see Lemma 4). This allows us
to obtain an upper bound via a simple truncated Bayesian algorithm. Our proofs
are substantially simpler (cf. [3]) yet provide tighter and often optimal
bounds.

In summary, our main contributions are: (i) constructive proofs through a new
smooth truncated Bayesian algorithm, (ii) the novel concept of global
sequential covering, (iii) lower and upper bounds with optimal leading
constants, and at last (iv) novel information-theoretic technique for the
lower bounds.

Table 1: Summary of results Constrains | $d\text{ v.s }T$ | Bounds | Comment
---|---|---|---
General $\alpha$ cover $\mathcal{G}_{\alpha}$ | N.A. | $\displaystyle r^{a}_{T}(\mathcal{H})\leq\inf_{0<\alpha<1}\left\\{2\alpha T+\log|\mathcal{G}_{\alpha}|\right\\}$ |  Theorem 1
General Lipschitz $f$ | Any | $r^{a}_{T}(\mathcal{H}_{f})\leq d\log\left(\frac{T}{d}+1\right)+O(d)$ |  Theorem 2
under $\ell_{s}$ ball | $T\gg d\log T$ | $r^{a}_{T}(\mathcal{H}_{f})\geq d\log\left(\frac{T}{d}\right)-O(d\log\log T)$ |  Theorem 3
Bounded Hessian | Any | $\displaystyle r^{a}_{T}(\mathcal{H}_{f})\leq\frac{d}{2}\log\left(\frac{T}{d}+1\right)+O(d)$ | Theorem 4
of $\log f$ under $\ell_{2}$ ball
$f(\langle{\bf w},{\bf x}\rangle)$ with $f^{\prime}(0)\not=0$ | $T\gg d^{(s+2)/s}$ | $r^{a}_{T}(\mathcal{H}_{f})\geq\frac{d}{2}\log\left(\frac{T}{d^{(s+2)/s}}\right)-O(d)$ | Theorem 5
under $\ell_{s}$ ball
$|\langle{\bf w},{\bf x}\rangle|$ under $\ell_{s}$ ball | $d\geq T$ | $r^{a}_{T}(\mathcal{H}_{f})\geq\frac{s+1}{s\cdot e}T^{s/(s+1)}$ |  Theorem 6
$|\langle{\bf w},{\bf x}\rangle|$ under $\ell_{2}$ ball | $d\geq T$ | $\Omega(T^{2/3})\leq r^{a}_{T}(\mathcal{H}_{f})\leq\tilde{O}(T^{2/3})$ |  Example 2

### Related Work

In this paper we study the sequential minimax regret for a general online
regression with logarithmic loss using tools of information theory, in
particular the universal source coding (lower bounds) [1, 9, 17, 19, 24, 25,
26, 37] and sequential covering (upper bounds).

Most of the existing works in online regression deal with the logistic
regression. We first mention the work of [12] who studied the pointwise regret
of the logistic regression for the proper setting. Unlike the improper
learning, studied in this paper, where feature ${\bf x}_{t}$ at time $t$ is
also available to the learner, [12] showed that the pointwise regret is
$\Theta(T^{1/3})$ for $d=1$ and $O(\sqrt{T})$ for $d>1$. Furthermore, [16]
demonstrates results that regret for logistic regression grows like $O(d\log
T/d)$. This was further generalized in [11]. These results were strengthened
in [28], which also provides the matching lower bounds. Precise asymptotics
for the fixed design minimax regret were recently presented in [13, 14] for
$d=o(T^{1/3})$.

Regret bounds under logarithmic loss for general expert class $\mathcal{H}$
was first investigated by Vovk under the framework of mixable losses [15, 33].
In particular, Vovk showed that for finite class $\mathcal{H}$, the regret
growth is $\log|\mathcal{H}|$ via the _aggregating algorithm_ (i.e., the
Bayesian algorithm that we will discuss below). We refer the reader to [4,
Chapter 3.5, 3.6] and the references therein for more results on this topic.
Cesa-Bianchi and Lugosi [4] were the first to investigate log-loss under
general (infinite) expert class $\mathcal{H}$ [4, Chapter 9.10, 9.11], where
they derived a general upper bound using the concept of covering number and a
two-stage prediction scheme. In particular, Cesa-Bianchi and Lugosi showed
that for Lipschitz parametric classes with values bounded away from
$\\{0,1\\}$, one can achieve a regret bound of the form $d/2\log(T/d)$. When
the values are close to $\\{0,1\\}$, they used a _hard_ truncation approach,
which gives a sub-optimal bound of the form $2d\log(T/d)$. Moreover, the
approach of [4] only works for the fixed design regret (or _simulatable_ in
their context). In [21], the authors extended the result of [4, Chapter 9.10]
to the sequential case via the machinery of sequential covering that was
established in [20]. However, [21] also used the same _hard_ truncation as in
[4] resulting in suboptimal upper bounds. In [3], the authors obtained an
upper bound similar to the upper bound presented in Theorem 1 via the
observation that the $\log$ function is self-concordance. In particular, this
allows them to resolve the tight bounds for non-parametric Lipschitz functions
map $[0,1]^{s}\rightarrow[0,1]$.

##  2 Problem Formulation and Preliminaries

We denote $\mathcal{X}$ as the input feature space and $\mathcal{H}$ as the
concept class which is a set of functions mapping
$\mathcal{X}\rightarrow[0,1]$. We often use an auxiliary set $\mathcal{W}$ to
index $\mathcal{H}$. We say a function $g$ is _sequential_ if it maps
$\mathcal{X}^{*}\rightarrow[0,1]$, where $\mathcal{X}^{*}$ is set of all
finite sequences with elements in $\mathcal{X}$. We denote $\mathcal{G}$ as a
class of _sequential_ functions. If $T$ is a time horizon, then for any
$t\in[T]$, we write ${\bf x}^{t}=\\{{\bf x}_{1},\cdots,{\bf x}_{t}\\}$ and
$y^{t}=\\{y_{1},\cdots,y_{t}\\}$. We use standard asymptotic notation
$f(t)=O(g(t))$ or $f(t)\ll g(t)$ if there exist constant $C$ such that
$f(t)\leq Cg(t)$ for all $t\geq 0$.

The main objective of this paper is to study the growth of the sequential
minimax regret $r^{a}_{T}({\cal H})$ for a large class of experts ${\cal H}$.
We accomplish it with two different techniques. For the lower bound, we
precisely estimate the fixed design minimax regret $r_{T}^{*}({\cal H}|{\bf
x}^{T})$ using the Shtarkov sum [29], discussed next. For the upper bound, we
construct a novel global cover set ${\mathcal{G}}$ of ${\cal H}$ and design a
new (truncated) Bayesian algorithm to find precise bounds with constants that
are provably optimal.

### Lower Bounds.

We investigate the lower bound of the adversarial regret $r^{a}_{T}({\cal H})$
by considering its corresponding fixed design minimax regret $r^{*}_{T}({\cal
H}|{\bf x}^{T})$ and $r^{*}_{T}({\cal H})=\max_{{\bf x}^{T}}r^{*}_{T}({\cal
H}|{\bf x}^{T})$. We are able to do it due to the recent result [36] which we
quote next.

######  Lemma 1 (Wu et al., 2022).

Let ${\cal H}$ be any general hypothesis class and ${\ell}$ be any loss
function. Then $r^{a}_{T}(\mathcal{H}|{\bf x}^{T})=r^{*}_{T}(\mathcal{H}|{\bf
x}^{T})$ for any ${\bf x}^{T}\in\mathcal{X}^{T}$. Furthermore,

$r^{a}_{T}(\mathcal{H})\geq r^{*}_{T}(\mathcal{H}),$

and the inequality is strict for certain $\mathcal{H}$, and loss function
$\ell$.

We establish precise growth of $r^{*}_{T}({\cal H})$ by estimating the
Shtarkov sum that was intensively analyzed in information theory [29, 9] and
recently applied in online learning [27, 13]. For the logarithmic loss, the
Shtarkov sum (conditioned on ${\bf x}^{T}$) is defined as follows 111Note that
the Starkov sum can be defined for any class of measures, however, here we
only use the form for product measures.

$S_{T}(\mathcal{H}|{\bf
x}^{T})\overset{\text{def}}{=}\sum_{y^{T}\in\\{0,1\\}^{T}}\sup_{h\in\mathcal{H}}P_{h}(y^{T}\mid{\bf
x}^{T}),$

where $P_{h}(y^{T}\mid{\bf x}^{T})=\prod_{t=1}^{T}h({\bf
x}_{t})^{y_{t}}(1-h({\bf x}_{t}))^{1-y_{t}}$ and we _interpret_ $h({\bf
x}_{t})=P(y_{t}=1|{\bf x}_{t})$. The regret can be expressed in terms of the
Shtarkov sum (see [13, Equation (6)] or [4, Theorem 9.1]) as

$\displaystyle r^{*}_{T}(\mathcal{H})=\sup_{{\bf x}^{T}}\log
S_{T}(\mathcal{H}|{\bf x}^{T}).$ (5)

It is known that the leading term in the Shtarkov sum for a large class of
${\cal H}$ is often independent of ${\bf x}^{T}$ [28, 11, 13, 14]. Therefore,
the Shtarkov sum often gives the leading growth of $r_{T}^{*}({\cal H}|{\bf
x}^{T})$ independent of ${\bf x}^{T}$, which also suggests the leading growth
of the agnostic regret $r^{a}_{T}({\cal H})$.

### Upper Bounds.

We now discuss our constructive approach to upper bounds. In the next section,
we present our Smooth truncated Bayesian Algorithm (Algorithm 2) that provides
a constructive and often achievable upper bound. Here we focus on some, mostly
known, preliminaries.

Let $\mathcal{G}$ be any reference class map
$\mathcal{X}^{*}\rightarrow[0,1]$. Let $\mathcal{W}$ be an index set of
$\mathcal{G}$ and $\mu$ be an arbitrary finite measure over $\mathcal{W}$. The
standard Bayesian predictor with prior $\mu$ is presented in Algorithm 1.
Based on this algorithm, we have the following two lemmas [4, Chapter 3.3]
that are used to establish most of the upper bounds in this paper. For
completeness, we provide simple proofs in Appendix A.

Algorithm 1 Bayesian predictor

Input: Reference class $\mathcal{G}:=\\{g_{w}:w\in\mathcal{W}\\}$ with index
set $\mathcal{W}$ and prior $\mu$ over $\mathcal{W}$

1:Set $p_{w}(y^{0}\mid{\bf x}^{0})=1$ for all $w\in\mathcal{W}$.

2:for $t=1,\cdots,T$ do

3: Receive feature vector ${\bf x}_{t}$

4: Make prediction with the following equation:
$\hat{y}_{t}=\frac{\int_{\mathcal{W}}g_{w}({\bf x}^{t})p_{w}(y^{t-1}\mid{\bf
x}^{t-1})\text{d}\mu}{\int_{\mathcal{W}}p_{w}(y^{t-1}\mid{\bf
x}^{t-1})\text{d}\mu}.$

5: Receive label $y_{t}$

6: For all $w\in\mathcal{W}$, update: $~{}p_{w}(y^{t}\mid{\bf
x}^{t})=e^{-\ell(g_{w}({\bf x}^{t}),y_{t})}p_{w}(y^{t-1}\mid{\bf x}^{t-1})$.

7:end for

######  Lemma 2.

Let $\mathcal{G}$ be a collection of functions
$g_{w}:\mathcal{X}^{*}\rightarrow[0,1],w\in\mathcal{W}$. Let $\hat{y}_{t}$ be
the Bayesian prediction rule as in Step 4 of Algorithm 1 with prior $\mu$.
Then, for any ${\bf x}^{T}$ and $y^{T}$ we have

$\sum_{t=1}^{T}\ell(\hat{y}_{t},y_{t})\leq-\log\frac{\int_{\mathcal{W}}p_{w}(y^{T}\mid{\bf
x}^{T})\mathrm{d}\mu}{\int_{\mathcal{W}}1\mathrm{d}\mu},$

where $p_{w}(y^{T}\mid{\bf x}^{T})=e^{-\sum_{t=1}^{T}\ell(g_{w}({\bf
x}^{t}),y_{t})}$ and $\ell$ is the log-loss as in equation (1).

The following lemma bounds the regret under log-loss of finite classes, which
is well known.

######  Lemma 3.

For any finite class of experts $\mathcal{G}$, we have
$r^{a}_{T}(\mathcal{G})\leq\log|\mathcal{G}|.$

##  3 Main Results

We start with a novel covering set called the global sequential cover that is
different than the one used in [3]:

######  Definition 1 (Global sequential covering).

For any $\mathcal{H}\subset[0,1]^{\mathcal{X}}$, we say class $\mathcal{G}$ of
functions map $\mathcal{X}^{*}\rightarrow[0,1]$ is a global _sequential_
$\alpha$-covering of $\mathcal{H}$ at scale $T$ if for any ${\bf
x}^{T}\in\mathcal{X}^{T}$ and $h\in\mathcal{H}$, there exists
$g\in\mathcal{G}$ such that $\forall t\in[T]$,

$|h({\bf x}_{t})-g({\bf x}^{t})|\leq\alpha.$

Throughout we assume that $0<\alpha<1$.

Note that the main difference between our _global_ sequential covering and the
sequential covering used in [3] is that our covering function _does not_
depend on the underlying trees introduced in [22] 222Note that the covering
functions in Definition 1 can be viewed as the experts constructed in [22,
Section 6.1]. This is crucial to apply our covering set directly in an
algorithmic way (see Algorithm 2). Particularly, it enables us to establish
our lower and upper bounds for Lipschitz classes of functions with the optimal
constants on the leading term. We further improve these results for Lipschitz
class with bounded Hessian. Finally, we study the cases when the data
dimension $d$ is growing faster than $T$ by bounding the covering size through
the sequential fat-shattering number. In particular, we prove matching (up to
$\text{poly}\log T$ factor) upper and lower bounds for the generalized linear
functions.

### General Results.

We are now in the position to state our first main general finding.

######  Theorem 1.

If for any $\alpha>0$ there exists a global sequential $\alpha$-covering set
$\mathcal{G}_{\alpha}$ of $\mathcal{H}$, then

$r^{a}_{T}(\mathcal{H})\leq\inf_{0<\alpha<1}\left\\{2\alpha
T+\log|\mathcal{G}_{\alpha}|\right\\},$ (6)

and this bound is achievable algorithmically.

We should point out that Theorem 1 also improves the results of [3] by
obtaining better constants in front of both $\alpha T$ and
$\log|\mathcal{G_{\alpha}}|$. The proof is based on the following key lemma
that is established in Appendix B.

Algorithm 2 Smooth truncated Bayesian predictor

Input: Reference class $\mathcal{G}$ with index set $\mathcal{W}$ and prior
$\mu$ over $\mathcal{W}$, and truncation parameter $\alpha$

1:Let $p_{w}(y^{0}\mid{\bf x}^{0})=1$ for all $w\in\mathcal{W}$

2:for $t=1,\cdots,T$ do

3: Receive feature ${\bf x}_{t}$

4: For all $w\in\mathcal{W}$, set  $\tilde{g}_{w}({\bf
x}^{t})=\frac{g_{w}({\bf x}^{t})+\alpha}{1+2\alpha}$

5: Make prediction  $\hat{y}_{t}=\frac{\int_{\mathcal{W}}\tilde{g}_{w}({\bf
x}^{t})p_{w}(y^{t-1}\mid{\bf
x}^{t-1})\text{d}\mu}{\int_{\mathcal{W}}p_{w}(y^{t-1}\mid{\bf
x}^{t-1})\text{d}\mu}$

6: Receive label $y_{t}$

7: For all $w\in\mathcal{W}$, update: $~{}p_{w}(y^{t}\mid{\bf
x}^{t})=e^{-\ell(\tilde{g}_{w}({\bf x}^{t}),y_{t})}p_{w}(y^{t-1}\mid{\bf
x}^{t-1})$.

8:end for

######  Lemma 4.

Suppose $\mathcal{H}$ has a global sequential $\alpha$-covering set
$\mathcal{G}$ for some $\alpha\in[0,1]$. Then, there exists a truncated set
$\tilde{\mathcal{G}}$ of $\mathcal{G}$ with
$|\tilde{\mathcal{G}}|=|\mathcal{G}|$ such that for all ${\bf x}^{T},y^{T}$
and $h\in\mathcal{H}$ there exists a $\tilde{g}\in\tilde{\mathcal{G}}$
satisfying

$\frac{p_{h}(y^{T}\mid{\bf x}^{T})}{p_{\tilde{g}}(y^{T}\mid{\bf
x}^{T})}\leq\left(1+2\alpha\right)^{T},$ (7)

where

$p_{h}(y^{T}\mid{\bf x}^{T})=\prod_{t=1}^{T}h({\bf x}_{t})^{y_{t}}(1-h({\bf
x}_{t}))^{1-y_{t}}\ \ \ {\rm and}\ \ \ p_{\tilde{g}}(y^{T}\mid{\bf
x}^{T})=\prod_{t=1}^{T}\tilde{g}({\bf x}^{t})^{y_{t}}(1-\tilde{g}({\bf
x}^{t}))^{1-y_{t}}.$

###### Proof of Theorem 1.

We show that for any $0<\alpha<1$ if an $\alpha$-covering set
$\mathcal{G}_{\alpha}$ exists, then one can achieve the claimed bound for such
an $\alpha$. To do so, we run the Smooth truncated Bayesian Algorithm
(Algorithm 2) on $\mathcal{G}_{\alpha}$ with uniform prior and truncation
parameter $\alpha$. We denote by $\tilde{\mathcal{G}}_{\alpha}$ to be the
truncated class of $\mathcal{G}_{\alpha}$ as in Lemma 4 (same as the step $4$
of Algorithm 2). We now fix ${\bf x}^{T},y^{T}$. By Lemma 3 (with
$\mathcal{G}$ being $\tilde{\mathcal{G}}_{\alpha}$), we have

$\sum_{t=1}^{T}\ell(\hat{y}_{t},y_{t})\leq\inf_{\tilde{g}\in\tilde{\mathcal{G}}_{\alpha}}\sum_{t=1}^{T}\ell(\tilde{g}({\bf
x}^{t}),y_{t})+\log|\tilde{\mathcal{G}}_{\alpha}|=\inf_{\tilde{g}\in\tilde{\mathcal{G}}_{\alpha}}\sum_{t=1}^{T}\ell(\tilde{g}({\bf
x}^{t}),y_{t})+\log|\mathcal{G}_{\alpha}|,$

the last equality follows from
$|\mathcal{G}_{\alpha}|=|\tilde{\mathcal{G}}_{\alpha}|$. Since
$\sum_{t=1}^{T}\ell(f({\bf x}^{t}),y_{t})=-\log p_{f}(y^{T}\mid{\bf x}^{T})$
for any function $f$, then by Lemma 4 we conclude that

$\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\ell(h({\bf
x}_{t}),y_{t})\geq\inf_{\tilde{g}\in\tilde{\mathcal{G}}_{\alpha}}\sum_{t=1}^{T}\ell(\tilde{g}({\bf
x}^{t}),y_{t})-T\log\left(1+2\alpha\right).$

The result follows by combining the inequalities and noticing that
$\log(1+x)\leq x$ for all $x\geq-1$. ∎

We further note that for any constant $c_{1},c_{2}$ for which the bound
$r^{a}_{T}(\mathcal{H})\leq c_{1}\alpha T+c_{2}\log|\mathcal{G}_{\alpha}|$
holds universally we must have $c_{1}\geq 2$ and $c_{2}\geq 1$. Therefore, our
bounds are optimal on the constants333Note that Theorem 1 can be easily
generalized to alphabet of size $K$ by using truncation
$\tilde{g}(y_{t}\mid{\bf x}^{t})=\frac{g(y_{t}\mid{\bf
x}^{t})+\alpha}{1+K\alpha}$. The derived bound will be of form $K\alpha
T+\log|\mathcal{G}_{\alpha}|$ . This is tight on the constant $K$ as well.. To
see this, we let $\mathcal{X}=[T]$ and define $g$ to be the function that maps
every $t\in[T]$ to $\frac{1}{2}$. Let $\mathcal{H}$ be the class of functions
that maps to $[1/2-\alpha,1/2+\alpha]$. Clearly, $\mathcal{H}$ is
$\alpha$-covered by $g$. By noting that the maximum probability is
$(1/2+\alpha)^{T}=(1+2\alpha)^{T}(1/2)^{T}$, we compute the Shtarkov sum (5)
to get:

$r^{a}_{T}(\mathcal{H})\geq r^{*}_{T}(\mathcal{H})\geq\log(1+2\alpha)^{T}\sim
2\alpha T,$

where $\sim$ holds when $\alpha$ is sufficiently small. This implies that we
must have $c_{1}\geq 2$. The fact that $c_{2}\geq 1$ is due to that the
mixability constant of log-loss is $1$, which also follows from Theorem 3
below.

### Lipschitz Parametric Class.

We now consider a Lipschitz parametric function class. Given a function
$f:\mathcal{W}\times\mathcal{X}\rightarrow[0,1]$, define the following class

$\mathcal{H}_{f}=\\{f({\bf w},\cdot)\in[0,1]^{\mathcal{X}}~{}:~{}{\bf
w}\in\mathcal{W}\\},$

where ${\bf w}\in\mathcal{W}$ is often a $d$-dimensional vector in
${\mathbb{R}}^{d}$.

We will assume that $f({\bf w},{\bf x})$ is $L$-Lipschitz on ${\bf w}$ for
every ${\bf x}$, where $L\in\mathbb{R}^{+}$. More formally, $\forall{\bf
w}_{1},{\bf w}_{2}\in\mathcal{W}$ and ${\bf x}\in\mathcal{X}$ we have

$|f({\bf w}_{1},{\bf x})-f({\bf w}_{2},{\bf x})|\leq L||{\bf w}_{1}-{\bf
w}_{2}||,$

where $||\cdot||$ is some norm on $\mathcal{W}$. For example, if we take
$\mathcal{W}\subset\mathbb{R}^{d}$ then the norm can be $\ell_{1}$, $\ell_{2}$
or $\ell_{\infty}$ norm. For any specific norm $||\cdot||$, we write
$\mathcal{B}(R)$ for the ball under such norm with radius $R$ in
$\mathcal{W}$. In particular, we denote by $\mathcal{B}_{s}^{d}(R)$ the ball
in $\mathbb{R}^{d}$ of radius $R$ under $\ell_{s}$ norm centered at the
origin.

######  Theorem 2.

Let $f:\mathcal{B}_{s}^{d}(R)\times\mathbb{R}^{d}\rightarrow[0,1]$ be a
$L$-Lipschitz function under $\ell_{s}$ norm. Then

$r^{a}_{T}(\mathcal{H}_{f})\leq\min\left\\{d\log\left(\frac{2RLT}{d}+1\right)+2d,T\right\\}.$
(8)

###### Proof.

By $L$-Lipschitz condition, to find an $\alpha$-covering in the sense of
Definition 1, we only need to find a covering of $\mathcal{B}_{s}^{d}(R)$ with
radius $\alpha/L$. By standard result (see e.g. Lemma 5.7 and Example 5.8 of
[34]) we know that the covering size is upper bounded by

$\left(\frac{2RL}{\alpha}+1\right)^{d}.$

By Theorem 1, we find

$r^{a}_{T}(\mathcal{H}_{f})\leq\inf_{0<\alpha<1}\left\\{2\alpha
T+d\log\left(\frac{2RL}{\alpha}+1\right)\right\\}.$

Taking $\alpha=d/T$, we conclude

$r^{a}_{T}(\mathcal{H}_{f})\leq d\log\left(\frac{2RLT}{d}+1\right)+2d.$

This completes the proof for $T\geq d$. The upper bound $T$ is achieved by
predicting $\frac{1}{2}$ every time. ∎

######  Example 1.

For logistic function $f({\bf w},{\bf x})=(1+e^{-\langle{\bf w},{\bf
x}\rangle})^{-1},$ and ${\bf w}\in\mathcal{B}_{2}^{d}(R)$ with ${\bf
x}\in\mathcal{B}_{2}^{d}(1)$ our result recovers those of [11], but with a
better leading constant (the bound in [11] has a constant $5$). Note that, the
result in [3] also provides a sub-optimal constant $c\sim 4$. Moreover, our
bounds have a logarithmic dependency on Lipschitz constant $L$.

The question arises whether the factor in front of $\log T$ can be improved to
$d/2$ instead of $d$ as discussed in some recent papers [28, 13, 14]. In
Theorem 3 below, we show that, in general, it cannot unless we further
strengthen our assumption (see Theorem 4). For the ease of presentation, we
only consider the parameters restricted to $\ell_{2}$ norm. The proof can be
found in Appendix C.

######  Theorem 3.

For any $d,T,R,L$ such that $T\gg d\log(RLT)$, there exists $L$-Lipschitz
function $f:\mathcal{B}_{2}^{d}(R)\times\mathbb{R}^{d}\rightarrow[0,1]$ such
that

$r^{a}_{T}(\mathcal{H}_{f})\geq d\log\left(\frac{RLT}{d}\right)-d\log
64-d\log\log(RLT).$ (9)

### Lipschitz Class with Bounded Hessian.

As we have demonstrated in Theorem 3 the leading constant $1$ of the regret
for Lipschitz parametric classes can not be improved in general. We now show
that for some special function $f$ one can improve the constant to
$\frac{1}{2}$, as already noticed in [28, 13, 14]. For any function
$f:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow[0,1]$, we say the Hessian of
$\log f$ is uniformly bounded on $\mathcal{X}\subset\mathbb{R}^{d}$, if there
exists constant $C$ such that for any ${\bf w}\in\mathbb{R}^{d}$ and ${\bf
x}\in\mathcal{X}$ and $y\in\\{0,1\\}$ we have

$\sup_{||\textbf{u}||_{2}\leq 1}|\textbf{u}^{T}\nabla^{2}_{{\bf w}}\log f({\bf
w},{\bf x})^{y}(1-f({\bf w},{\bf x}))^{1-y}\textbf{u}|\leq C,$

where $\nabla^{2}_{{\bf w}}$ is the Hessian at ${\bf w}$. The proof of the
next theorem can be found in Appendix D.

######  Theorem 4.

Let $f:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow[0,1]$ be a function such
that the Hessian of $\log f$ is uniformly bounded by $C$ on $\mathcal{X}$. Let

$\mathcal{H}_{f}=\\{f({\bf w},{\bf x}):{\bf w}\in\mathcal{W},{\bf
x}\in\mathcal{X}\\}$

be such a class of $f$ restricted to some compact set
$\mathcal{W}\subset\mathbb{R}^{d}$. Then

$r^{a}_{T}(\mathcal{H}_{f})\leq\log\frac{\text{Vol}(\mathcal{W}^{*})}{\text{Vol}(\mathcal{B}_{2}^{d}(\sqrt{d/CT}))}+d/2+\log
2.$ (10)

where $\mathcal{W}^{*}=\\{{\bf w}+\textbf{u}\mid{\bf
w}\in\mathcal{W},~{}\textbf{u}\in\mathcal{B}_{2}^{d}(\sqrt{d/CT})\\}$,
$\text{Vol}(\cdot)$ is volume under Lebesgue measure. In particular, for
$\mathcal{W}=\mathcal{B}_{2}^{d}(R)$, we have

$r^{a}_{T}(\mathcal{H}_{f})\leq\frac{d}{2}\log\left(\frac{2CR^{2}T}{d}+2\right)+d/2+\log
2.$

Note that, Theorem 4 subsumes the results of [16, 28]444To get the upper
bounds in [28] one only needs to estimate the volume of $\ell_{s}$ balls,
which is well known [35]., where the authors considered the function of form
$f(\langle{\bf w},{\bf x}\rangle)$ and requires that the second derivative of
$\log f$ is bounded, see also [4, Chapter 11.10]. However, the KL-divergence-
based argument of [16] can not be used directly in the setup of Theorem 4
since we _do not_ assume the function $f$ has a linear structure. Our main
proof technique of Theorem 4 is a direct application of Lemma 2 and an
estimation of the integrals via Taylor expansion; see Appendix D for more
details on the proof.

Finally, we complete this part with the following lower bound for generalized
linear functions under unit $\ell_{s}$ balls. See Appendix E for proof.

######  Theorem 5.

Let $f:\mathbb{R}\rightarrow[0,1]$ be an arbitrary function such that there
exists $c_{1},c_{2}\in(0,1)$ and for all $r>0$ we have
$[c_{1}-c_{2}d^{-r},c_{1}+c_{2}d^{-r}]\subset f([-d^{-r},d^{-r}])$ for all
sufficient large $d$. Let

$\mathcal{H}_{f}=\\{f(\langle{\bf w},{\bf x}\rangle):{\bf
w}\in\mathcal{B}_{s}^{d}(1),{\bf x}\in\mathcal{B}_{s}^{d}(1)\\}$

where $s>0$. Then

$r^{a}_{T}(\mathcal{H}_{f})\geq\frac{d}{2}\log\left(\frac{T}{d^{(s+2)/s}}\right)-O(d)$
(11)

where $O$ hides some absolute constant that is independent of $d,T$.

Note that for the logistic function $f(x)=(1+e^{-x})^{-1}$ Theorem 5 holds
with $c_{1}=\frac{1}{2}$ and $c_{2}=\frac{1}{5}$. Therefore,
1. If $s=1$, then

$r^{a}_{T}(\mathcal{H}_{f})\geq\frac{d}{2}\log\left(\frac{T}{d^{3}}\right)-O(d).$

2. If $s=2$, then

$r^{a}_{T}(\mathcal{H}_{f})\geq\frac{d}{2}\log\left(\frac{T}{d^{2}}\right)-O(d).$

3. If $s=\infty$, then

$r^{a}_{T}(\mathcal{H}_{f})\geq\frac{d}{2}\log\left(\frac{T}{d}\right)-O(d).$

This recovers all the lower bounds from [28]. We note that a simple sufficient
condition for Theorem 5 to hold is to require $f^{\prime}(0)\not=0$ if $f(x)$
is differentiable.

### Large Growth.

We now present some results for large $d$ growing even faster than $T$. We
will show that the size of _global_ sequential covering (Definition 1) of a
class $\mathcal{H}$ can be bounded by the sequential fat-shattering number of
$\mathcal{H}$ in a similar fashion as in [22]. We first introduce the notion
of sequential fat-shattering number as in [22].

We denote $\\{0,1\\}^{d}_{*}$ to be the set of all binary sequences of length
less than or equal to $d$. A binary tree of depth $d$ with labels in
$\mathcal{X}$ is defined to be a map
$\tau:\\{0,1\\}^{d}_{*}\rightarrow\mathcal{X}$. For any function class
$\mathcal{H}\subset[0,1]^{\mathcal{X}}$, we say $\mathcal{H}$ $\alpha$-fat
shatters tree $\tau$ if there exists $[0,1]$-value tree
$\textbf{s}:\\{0,1\\}^{d}_{*}\rightarrow[0,1]$ such that for any binary
sequence $\epsilon_{1}^{d}\in\\{0,1\\}^{d}_{*}$ there exist $h\in\mathcal{H}$
such that for all $t\in[d]$:
1\. If $\epsilon_{t}=0$, then
$h(\tau(\epsilon_{1}^{t-1}))\leq\textbf{s}(\epsilon_{1}^{t-1})-\alpha;$
2\. If $\epsilon_{t}=1$, then
$h(\tau(\epsilon_{1}^{t-1}))\geq\textbf{s}(\epsilon_{1}^{t-1})+\alpha.$

######  Definition 2.

The sequential $\alpha$-fat shattering number of $\mathcal{H}$ is defined to
be the maximum number $d(\alpha)$ such that $\mathcal{H}$ $\alpha$-fat
shatters a tree $\tau$ of depth $d:=d(\alpha)$.

In the below lemma, we present an upper bound for the cardinally of the global
covering set with algorithmically constructed cover set $\mathcal{G}_{\alpha}$
(see also [22, Section 6.1]). Appendix F presents the proof.

######  Lemma 5.

Let $\mathcal{H}$ be any class map $\mathcal{X}\rightarrow[0,1]$ and
$d(\alpha)$ be the sequential $\alpha$-fat shattering number of $\mathcal{H}$.
Then there exists a global sequential $\alpha$-covering set
$\mathcal{G}_{\alpha}$ of $\mathcal{H}$ as in Definition 1 such that

$|\mathcal{G}_{\alpha}|\leq\sum_{t=0}^{d(\alpha/3)}\binom{T}{t}\left\lceil\frac{3}{2\alpha}\right\rceil^{t}\leq\left\lceil\frac{3T}{2\alpha}\right\rceil^{d(\alpha/3)+1}.$
(12)

######  Example 2.

By [22] we know that the sequential $\alpha$-fat shattering number of linear
functions $f({\bf w},{\bf x})=|\langle{\bf w},{\bf x}\rangle|$ with ${\bf
w},{\bf x}\in\mathcal{B}_{2}^{d}(1)$ is of order $\tilde{O}(\alpha^{-2})$
where in $\tilde{O}$ we hide a polylog factor. Lemma 5 implies that the global
sequential $\alpha$-covering number is upper bounded by

$\left\lceil\frac{(3T)}{(2\alpha)}\right\rceil^{d(\alpha/3)+1}.$

By Theorem 1, we have

$r^{a}_{T}(\mathcal{H}_{f})\leq\inf_{0<\alpha<1}\left\\{2\alpha
T+\tilde{O}\left(\frac{1}{\alpha^{2}}\right)\right\\}\leq\tilde{O}(T^{2/3}),$

by taking $\alpha=T^{-1/3}$. This bound is _independent_ of the data dimension
$d$.

######  Remark 1.

Observe that for any class $\mathcal{H}$ with sequential fat-shattering number
of order $\alpha^{-s}$ one can achieve a regret upper bound of order
$\tilde{O}(T^{s/s+1})$ by Theorem 1. We refer to [22, 23] for the estimations
of sequential fat-shattering number of a variety of classes.

Finally, we present the following general lower bound. See Appendix G for
proof.

######  Theorem 6.

For any $s\geq 1$, we define

$\mathcal{D}_{s}=\left\\{\textbf{p}\in[0,1]^{T}:\sum_{t=1}^{T}p_{t}^{s}\leq
1\right\\}.$

We can view the vectors in $\mathcal{D}_{s}$ as functions mapping
$[T]\rightarrow[0,1]$. Then

$r^{a}_{T}(\mathcal{D}_{s})\geq
r^{*}_{T}(\mathcal{D}_{s})\geq\Omega(T^{s/s+1}).$ (13)

To see why Theorem 6 implies a lower bound for $f({\bf w},{\bf
x})=|\langle{\bf w},{\bf x}\rangle|$ with $d\geq T$, as in Example 2, we take
${\bf w},{\bf x}\in\mathcal{B}_{2}^{T}(1)$ (i.e., with $d=T$) and define ${\bf
x}_{t}={\bf e}_{t}$ with ${\bf e}_{t}$ being the standard base of
$\mathbb{R}^{T}$ that takes value $1$ at position $t$ and zeros otherwise.
Note that the functions of $\mathcal{H}_{f}$ with $f({\bf w},{\bf
x})=|\langle{\bf w},{\bf x}\rangle|$ restricted on ${\bf x}^{T}$ is exactly
$\mathcal{D}_{2}$. Then

$r^{a}_{T}(\mathcal{H}_{f})\geq r^{*}_{T}(\mathcal{H}_{f})\geq
r^{*}_{T}(\mathcal{D}_{2})\geq\Omega(T^{2/3})$

and this is a matching lower bound of Example 2. Note that, it is proved in
[21] that for function $f({\bf w},{\bf x})=\frac{\langle{\bf w},{\bf
x}\rangle+1}{2}$, one can achieve the regret of form $\tilde{O}(\sqrt{T})$555A
$\tilde{\Omega}(\sqrt{T})$ lower bound for $d\geq\sqrt{T}$ can be derived from
Theorem 5, recovering [21, Lemma 8].. Example 2 implies that the generalized
linear functions of form $f(\langle{\bf w},{\bf x}\rangle)$ can have different
regrets with polynomial gap even with a simple shift on the value (though they
have the same covering number). It is therefore an interesting open problem to
investigate a tighter complexity measure (instead of a covering number as in
Definition 1) that captures this phenomenon.

##  4 Conclusion

In this paper, we presented best known lower and upper bounds on sequential
online regret for a large class of experts. We accomplish it by designing a
new smooth truncated Bayesian algorithm, together with a new concept of global
sequential covering, that achieves these upper bounds. For the lower bounds,
we use an novel information-theoretic approach based on the Shtarkov sum. We
anticipate that these techniques could be generalized to a broader set of
problems, e.g., when the covariant ${\bf x}^{T}$ present stochastically. We
leave it to the future works.

## References

  * [1] A. Barron, J. Rissanen, and B. Yu.  The minimum description length principle in coding and modeling.  IEEE Trans. Inf. Theory, 44(6):2743–2760, Oct. 1998.
  * [2] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz.  Agnostic online learning.  In COLT, volume 3, page 1, 2009.
  * [3] Blair Bilodeau, Dylan Foster, and Daniel Roy.  Tight bounds on minimax regret under logarithmic loss via self-concordance.  In International Conference on Machine Learning, pages 919–929. PMLR, 2020.
  * [4] N. Cesa-Bianchi and G. Lugosi.  Prediction, Learning and Games.  Cambridge University Press, 2006.
  * [5] B. Clarke and A. Barron.  Jeffreys’ prior is asymptotically least favorable under entropy of risk.  J. Statistical PLanning and Inference, pages 453 – 471, 1994.
  * [6] I. Csiszar and P. Shields.  Redundancy rates for renewal and other processes.  IEEE Trans. Inf. Theory, 42:2065–2072, 1995.
  * [7] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz.  Multiclass learnability and the erm principle.  In Proceedings of the 24th Annual Conference on Learning Theory, pages 207–232. JMLR Workshop and Conference Proceedings, 2011.
  * [8] L. D. Davisson.  Universal noiseless coding.  IEEE Trans. Inf. Theory, IT-19(6):783–795, Nov. 1973.
  * [9] M. Drmota and W. Szpankowski.  Precise minimax redundancy and regrets.  IEEE Trans. Inf. Theory, IT-50:2686–2707, 2004.
  * [10] P. Flajolet and W. Szpankowski.  Analytic variations on redundancy rates of renewal processes.  IEEE Trans. Information Theory, 48:2911–2921, 2002.
  * [11] Dylan J Foster, Satyen Kale, Haipeng Luo andMehryar Mohri, and Karthik Sridharan.  Logistic regression: The importance of being improper.  In COLT - Conference on Learning Theory, 2018.
  * [12] E. Hazan, T. Koren, and K. Y. Levy.  Logistic regression: Tight bounds for stochastic and online optimization.  In The 27th Conference on Learning Theory, COLT 2014, pages 197–209. MIT press, 2014.
  * [13] P. Jacquet, G. I. Shamir, and W. Szpankowski.  Precise minimax regret for logistic regression with categorical feature values.  In PRML: ALT’21, volume 132, pages 755–771, 2021.
  * [14] Philippe Jacquet, Gil Shamir, and Wojciech Szpankowski.  Precise minimax regret for logistic regression with categorical feature values.  In Algorithmic Learning Theory, pages 755–771. PMLR, 2021.
  * [15] Rémi Jézéquel, Pierre Gaillard, and Alessandro Rudi.  Mixability made efficient: Fast online multiclass logistic regression.  Advances in Neural Information Processing Systems, 34, 2021.
  * [16] Sham M Kakade and Andrew Y. Ng.  Online bounds for bayesian algorithms.  In L. K. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems 17, pages 641–648. MIT Press, 2005.
  * [17] R. E. Krichevsky and V. K. Trofimov.  The performance of universal encoding.  IEEE Trans. Inform. Theory, IT-27(2):199–207, Mar. 1981.
  * [18] Edward James McShane.  Extension of range of functions.  Bulletin of the American Mathematical Society, 40(12):837–842, 1934\.
  * [19] A. Orlitsky and N. P. Santhanam.  Speaking of infinity.  IEEE Trans. Inf. Theory, 50(10):2215–2230, Oct. 2004.
  * [20] A. Rakhlin and K. Sridharan.  Online nonparametric regression with general los function.  In COLT, 2014.
  * [21] Alexander Rakhlin and Karthik Sridharan.  Sequential probability assignment with binary alphabets and large classes of experts.  arXiv preprint arXiv:1501.07340, 2015.
  * [22] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning: Random averages, combinatorial parameters, and learnability.  Advances in Neural Information Processing Systems, 23, 2010.
  * [23] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Sequential complexities and uniform martingale laws of large numbers.  Probability Theory and Related Fields, 161(1):111–153, 2015.
  * [24] J. Rissanen.  Universal coding, information, prediction, and estimation.  IEEE Trans. Inform. Theory, IT-30(4):629–636, Jul. 1984.
  * [25] J. Rissanen.  Fisher information and stochastic complexity.  IEEE Trans. Information Theory, 42:40–47, 1996.
  * [26] G. I. Shamir.  On the MDL principle for i.i.d. sources with large alphabets.  IEEE Trans. Inform. Theory, 52(5):1939–1955, May 2006.
  * [27] G. I. Shamir and W. Szpankowski.  Low complexity approximate bayesian logistic regression for sparse online learning.  In ArXiv: http://arxiv.org/abs/2101.12113, 2021.
  * [28] Gil I Shamir.  Logistic regression regret: What’s the catch?  In Conference on Learning Theory, pages 3296–3319. PMLR, 2020.
  * [29] Y. M. Shtarkov.  Universal sequential coding of single messages.  Problems of Information Transmission, 23(3):3–17, Jul.-Sep. 1987\.
  * [30] W. Szpankowski.  On asymptotics of certain recurrences arising in universal coding.  Problems of Information Transmission, 34:55–61, 1998.
  * [31] W. Szpankowski.  Average Case Analysis of Algorithms on Sequences.  Wiley, New York, 2001.
  * [32] W. Szpankowski and M. Weinberger.  Minimax pointwise redundancy for memoryless models over large alphabets.  IEEE Trans. Information Theory, 58:4094–4104, 2012.
  * [33] Volodya Vovk.  Competitive on-line statistics.  International Statistical Review, 69(2):213–248, 2001.
  * [34] Martin J Wainwright.  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press, 2019.
  * [35] Xianfu Wang.  Volumes of generalized unit balls.  Mathematics Magazine, 78(5):390–395, 2005.
  * [36] C. Wus, M. Heidari, A. Grama, and W. Szpankowski.  Sequential vs fixed design minimax regrets for learning.  preprint, 2022.
  * [37] Q. Xie and A. Barron.  Minimax redundancy for the class of memoryless sources.  IEEE Trans. Information Theory, pages 647–657, 1997.
  * [38] Q. Xie and A. Barron.  Asymptotic minimax regret for data compression, gambling, and prediction.  IEEE Trans. Information Theory, 46:431–445, 2000.
  * [39] Kenji Yamanishi.  Minimax relative loss analysis for sequential prediction algorithms using parametric hypotheses.  In Proceedings of the eleventh annual conference on Computational learning theory, pages 32–43, 1998.

##  Appendix A Proofs of Lemma 2 and Lemma 3

We prove here Lemma 2 and Lemma 3. For the reader’s convenience we repeat both
lemmas.

Lemma 2 Let $\mathcal{G}$ be a collection of functions
$g_{w}:\mathcal{X}^{*}\rightarrow[0,1],w\in\mathcal{W}$. Let $\hat{y}_{t}$ be
the Bayesian prediction rule as in Step 4 of Algorithm 1 with prior $\mu$.
Then, for any ${\bf x}^{T}$ and $y^{T}$ we have

$\sum_{t=1}^{T}\ell(\hat{y}_{t},y_{t})\leq-\log\frac{\int_{\mathcal{W}}p_{w}(y^{T}\mid{\bf
x}^{T})\text{d}\mu}{\int_{\mathcal{W}}1\text{d}\mu},$

where $p_{w}(y^{T}\mid{\bf x}^{T})=e^{-\sum_{t=1}^{T}\ell(g_{w}({\bf
x}^{t}),y_{t})}$ and $\ell$ is the log-loss.

###### Proof.

We first observe that for any $y\in\\{0,1\\}$ we have $e^{-\ell(\cdot,y)}$ is
concave over $[0,1]$. Let

$\lambda_{t-1}(w)=\frac{p_{w}(y^{t-1}\mid{\bf
x}^{t-1})}{\int_{\mathcal{W}}p_{w}(y^{t-1}\mid{\bf x}^{t-1})\text{d}\mu}.$

Note that $\lambda_{t-1}(w)$ forms a probability density over $\mathcal{W}$
w.r.t. $\mu$. By definition of $\hat{y}_{t}$, we have
$\hat{y}_{t}=\mathbb{E}_{\lambda_{t-1}}[g_{w}({\bf x}^{t})],$ where the
expectation is over the density of $\lambda_{t-1}(w)$. Therefore, by Jensen’s
inequality and the update procedure as in item 6 of Algorithm 1, we have

$e^{-\ell(\hat{y}_{t},y_{t})}=e^{-\ell(\mathbb{E}[g_{w}({\bf
x}^{t})],y_{t})}\geq\mathbb{E}[e^{-\ell(g_{w}({\bf
x}^{t}),y_{t})}]=\frac{\int_{\mathcal{W}}p_{w}(y^{t}\mid{\bf
x}^{t})\text{d}\mu}{\int_{\mathcal{W}}p_{w}(y^{t-1}\mid{\bf
x}^{t-1})\text{d}\mu}.$

By telescoping the sum, we find

$e^{-\sum_{t=1}^{T}\ell(\hat{y}_{t},y_{t})}\geq\frac{\int_{\mathcal{W}}p_{w}(y^{T}\mid{\bf
x}^{t})\text{d}\mu}{\int_{\mathcal{W}}1\text{d}\mu}.$

This implies

$\sum_{t=1}^{T}\ell(\hat{y}_{t},y_{t})\leq-\log\frac{\int_{\mathcal{W}}p_{w}(y^{T}\mid{\bf
x}^{T})\text{d}\mu}{\int_{\mathcal{W}}1\text{d}\mu}$

and completes the proof. ∎

Lemma 3 For any finite class of experts $\mathcal{G}$

$r^{a}_{T}(\mathcal{G})\leq\log|\mathcal{G}|.$

###### Proof.

Let $\mu(w)=\frac{1}{|\mathcal{W}|}$ as in Lemma 2 and $\hat{y}_{t}$ be the
Bayesian predictor with input $\mathcal{G}$ and $\mu$. Then

$\displaystyle\sum_{t=1}^{T}\ell(\hat{y}_{t},y_{t})$
$\displaystyle\leq-\log\frac{\int_{\mathcal{W}}p_{w}(y^{T}\mid{\bf
x}^{T})\text{d}\mu}{\int_{\mathcal{W}}1\text{d}\mu}$ (14)
$\displaystyle=-\log\int_{\mathcal{W}}p_{w}(y^{T}\mid{\bf
x}^{T})\text{d}\mu+\log 1$ (15)
$\displaystyle=-\log\int_{\mathcal{W}}p_{w}(y^{T}\mid{\bf x}^{T})\text{d}\mu$
(16) $\displaystyle\leq-\log p_{w^{*}}(y^{T}\mid{\bf
x}^{T})+\log|\mathcal{W}|,~{}\text{where }w^{*}\text{ maximizes
}p_{w}(y^{T}\mid{\bf x}^{T})$ (17)
$\displaystyle=\sum_{t=1}^{T}\ell(g_{w^{*}}({\bf
x}^{t}),y_{t})+\log|\mathcal{G}|,~{}\text{ since
}|\mathcal{W}|=|\mathcal{G}|.$ (18)

This concludes the proof. ∎

##  Appendix B Proof of Lemma 4

We construct the set $\tilde{\mathcal{G}}$ as in Algorithm 2. For any
$g\in\mathcal{G}$ we define a smooth truncated function $\tilde{g}$ such that
for any ${\bf x}^{t}\in\mathcal{X}^{*}$

$\tilde{g}({\bf x}^{t})=\frac{g({\bf x}^{t})+\alpha}{1+2\alpha}.$

We introduce the following short-hand notation, for any function $f$ we define

$f(y_{t})=f({\bf x}^{t})^{y_{t}}(1-f({\bf x}^{t}))^{1-y_{t}}.$

For any ${\bf x}^{T},y^{T}$ and $h\in\mathcal{H}$, let $g\in\mathcal{G}$ be a
$\alpha$-covering of $h$ and $\tilde{g}$ be the truncated function as defined
above. For any $t$, we consider two cases.

Case 1: If $y_{t}=1$, we have:

$\displaystyle\frac{h(y_{t})}{\tilde{g}(y_{t})}$ $\displaystyle=\frac{h({\bf
x}^{t})}{\tilde{g}({\bf x}^{t})},~{}\text{since }y_{t}=1$ (19)
$\displaystyle\leq\frac{g({\bf x}^{t})+\alpha}{\tilde{g}({\bf
x}^{t})},~{}g\text{ is }\alpha\text{ cover of }h$ (20)
$\displaystyle=\frac{g({\bf x}^{t})+\alpha}{(g({\bf
x}^{t})+\alpha)/(1+2\alpha)},~{}\text{ definition of }\tilde{g}$ (21)
$\displaystyle=1+2\alpha$ (22)

Case 2: If $y_{t}=0$, we have

$\displaystyle\frac{h(y_{t})}{\tilde{g}(y_{t})}$ $\displaystyle=\frac{1-h({\bf
x}^{t})}{1-\tilde{g}({\bf x}^{t})}$ (23) $\displaystyle\leq\frac{1-g({\bf
x}^{t})+\alpha}{1-\tilde{g}({\bf x}^{t})},~{}g\text{ is }\alpha\text{ cover of
}h$ (24) $\displaystyle=\frac{1-g({\bf x}^{t})+\alpha}{1-(g({\bf
x}^{t})+\alpha)/(1+2\alpha)}~{}\text{, definition of }\tilde{g}$ (25)
$\displaystyle=\frac{1-g({\bf x}^{t})+\alpha}{(1-g({\bf
x}^{t})+\alpha)/(1+2\alpha)}$ (26) $\displaystyle=1+2\alpha,$ (27)

Now, combining the two cases, we have

$\displaystyle\frac{p_{h}(y^{T}\mid{\bf x}^{T})}{p_{\tilde{g}}(y^{T}\mid{\bf
x}^{T})}$ $\displaystyle=\prod_{t=1}^{T}\frac{h(y_{t})}{\tilde{g}(y_{t})}$
(28) $\displaystyle\leq\left(1+2\alpha\right)^{T}.$ (29)

This completes the proof of Lemma 4.

##  Appendix C Proof of Theorem 3

We need the following two lemmas.

######  Lemma 6.

Let $\mathcal{P}$ be a finite class of distributions over the same domain
$\mathcal{X}$. Denote

$S=\sum_{x\in\mathcal{X}}\max_{p\in\mathcal{P}}p(x)$

be the Shtarkov sum. Then for any estimation rule
$\Phi:\mathcal{X}\rightarrow\mathcal{P}$ we have

$\max_{p\in\mathcal{P}}p(\Phi(x)\not=p)\geq 1-\frac{S}{|\mathcal{P}|}.$

###### Proof.

Note that $\Phi$ partitions $\mathcal{X}$ into $|\mathcal{P}|$ disjoint parts.
For any $p\in\mathcal{P}$, we denote
$\mathcal{X}_{p}=\\{x\in\mathcal{X}:\Phi(x)=p\\}$ be the partition
corresponding to $p$. We have

$\sum_{p\in\mathcal{P}}p(\mathcal{X}_{p})=\sum_{x\in\mathcal{X}}p_{x}(x)\leq\sum_{x\in\mathcal{X}}\max_{p\in\mathcal{P}}p(x)=S,$

where $p_{x}\in\mathcal{P}$ is the distribution such that
$x\in\mathcal{X}_{p_{x}}$. This implies

$\min_{p\in\mathcal{P}}p(\mathcal{X}_{p})\leq\frac{S}{|\mathcal{P}|}.$

The result follows by taking the complements of $\mathcal{X}_{p}$. ∎

######  Lemma 7.

For any $M$ and $T\gg\log M$, there exist $M$ vectors
$v_{1},v_{2},\cdots,v_{M}\in\\{0,1\\}^{T}$ such that for any $i\not=j\in[M]$
we have

$\sum_{t=1}^{T}1\\{v_{i}[t]\not=v_{j}[t]\\}\geq T/4.$

###### Proof.

We use a probabilistic argument to construct the vectors $v_{i}$. To do so, we
choose each $v_{i}$ independently from uniform distribution over
$\\{0,1\\}^{T}$. Now, it easy to see that the expected distinct coordinates of
any two vectors is $T/2$. The result follows by a simple application of
Chernoff bound (e.g., see [31]) by showing that the event of the lemma has a
positive probability. ∎

Now we are in the position to prove Theorem 3. Let ${\bf x}_{1},\cdots,{\bf
x}_{T}\in\mathbb{R}^{d}$ be any distinct points. We will construct a
$L$-Lipschitz function $f({\bf w},{\bf x})$ such that the regret restricted
only on ${\bf x}^{T}$ is large. To do so, we consider a maximum packing $M$ of
the parameter space $\mathcal{B}_{2}^{d}(R)$ of radius $\alpha/L>0$ (where
$\alpha$ is to be determined latter). Standard volume argument (see Chapter 5
of [34]) yields that

$|M|\geq\left(\frac{LR}{2\alpha}\right)^{d}.$

Now, we will define a $L$-Lipschitz functions $f({\bf w},{\bf x})$ only on
${\bf w}\in M$ and ${\bf x}\in\\{{\bf x}_{1},\cdots,{\bf x}_{T}\\}$. By Lemma
7 (assume for now the conditions are satisfied), we can find $|M|$ binary
vectors $V\subset\\{0,1\\}^{T}$ such that any pair of the vectors has Hamming
distance lower bounded by $T/4$. For each of the vector $v\in V$, we define a
vector $u\in[0,1]^{T}$ in the following way, for all $t\in[T]$

  * 1.

If $v[t]=0$ then set $u[t]=0$;

  * 2.

If $v[t]=1$ then set $u[t]=\alpha$.

Denote by $U$ be the set of all such vectors $u$. Note that $|U|=M$. For any
${\bf w}\in M$, we can associate a unique $u\in U$ such that for all $t\in[T]$

$f({\bf w},{\bf x}_{t})=u[t].$

We now show that $f$ is indeed $L$-Lipschitz restricted on $M$ for all ${\bf
x}_{t}\in\\{{\bf x}_{1},\cdots,{\bf x}_{T}\\}$. This is because for any ${\bf
w}_{1}\not={\bf w}_{2}\in M$ we have $|f({\bf w}_{1},{\bf x}_{t})-f({\bf
w}_{2},{\bf x}_{t})|\leq\alpha$ by definition of $U$ and $||{\bf w}_{1}-{\bf
w}_{2}||_{2}\geq\alpha/L$ since $M$ is a packing.

We now view the vectors in $u\in U$ as a product of Bernoulli distributions
with each coordinate $t$ independently sampled from $\mathrm{Bern}(u[t])$. We
show that the sources in $U$ are identifiable. To see this, we note that for
any distinct pairs $u_{1},u_{2}\in U$, there exist a set $I\in[T]$ such that
$u_{1}$ and $u_{2}$ differ on $I$ and $|I|\geq T/4$. This further implies that
there exist a set $J\subset I$ with $|J|\geq T/8$ such that $u_{1}$ takes all
$0$ on $J$ and $u_{2}$ takes all $\alpha$ on $J$ (or vice versa). We can then
distinguish $u_{1},u_{2}$ by checking if the samples on $J$ are all $0$s or
not. The probability of making error is upper bounded by

$(1-\alpha)^{T/8}\leq e^{-\alpha T/8}.$

Since there are only $|M|^{2}$ such pairs, we have the probability of wrongly
identifying the source upper bounded by

$|M|^{2}e^{-\alpha T/8}.$

Taking $\alpha=\frac{16d\log(RLT)}{T}$, the error probability is upper bounded
by

$\left(\frac{RLT}{32d\log(RLT)}\right)^{2d}e^{-2d\log(RLT)}\leq\left(\frac{1}{32d\log(RLT)}\right)^{2d}\leq\frac{1}{2},$

for sufficient large $d,T$, where we have use the fact that
$|M|\leq(\frac{RLT}{32d\log(RLT)})^{d}$. Note that we only showed a lower
bound on $|M|$ before, but this is not a problem since we can always remove
some points from $M$ to make the upper bound holds as well.

By Lemma 6, we know that the Shtarkov sum of sources in $U$ is lower bounded
by $|M|/2$. Therefore, we have

$r^{a}_{T}(\mathcal{H}_{f})\geq r^{*}_{T}(\mathcal{H}_{f})\geq\log(|M|/2)\geq
d\log\left(RLT/d\right)-d\log 64-d\log\log(RLT).$

Now, we have to extend the function to the whole set $\mathcal{B}_{2}^{d}(R)$
and keep the $L$-Lipschitz property. This follows from a classical result in
real analysis (see [18, Theorem 1]) by defining for all ${\bf
w}\in\mathcal{B}_{2}^{d}(R)$ and ${\bf x}_{t}\in\\{{\bf x}_{1},\cdots,{\bf
x}_{T}\\}$

$f({\bf w},{\bf x}_{t})=\sup_{{\bf w}^{\prime}\in M}\\{f({\bf w}^{\prime},{\bf
x}_{t})-L||{\bf w}-{\bf w}^{\prime}||_{2}\\}.$

For the ${\bf x}\not\in\\{{\bf x}_{1},\cdots,{\bf x}_{T}\\}$, we can simply
let $f({\bf w},{\bf x})=0$ for all ${\bf w}$.

Finally, we need to check that the condition of Lemma 7 holds for our choice
of $\alpha$, this is satisfied by our assumption $T\gg d\log(RLT)$.

##  Appendix D Proof of Theorem 4

To make the proof more transparent, we only prove the case for
$\mathcal{W}=\mathcal{B}_{2}^{d}(R)$ since the proof for other compact
$\mathcal{W}$ follows similar path. Note that, for
$\mathcal{W}=\mathcal{B}_{2}^{d}(R)$, we have
$\mathcal{W}^{*}=\mathcal{B}_{2}^{d}(R+\sqrt{d/CT})$.

The proof resembles that of [11] but running the Bayesian predictor (Algorithm
1) over $\mathcal{W}^{*}$ instead of $\mathcal{W}$ with $\mathcal{G}$ being
$\mathcal{H}_{f}$ and $\mu$ being Lebesgue measure. Let ${\bf x}^{T}$, $y^{T}$
and $\hat{y}^{T}$ be the feature, label and predictions of the Bayesian
predictor respectively. By Lemma 2

$\displaystyle\sum_{t=1}^{T}\ell(\hat{y}_{t},y_{t})\leq-\log\frac{\int_{\mathcal{B}_{2}^{d}(R+\sqrt{d/CT})}p_{{\bf
w}}(y^{T}\mid{\bf
x}^{T})\text{d}\mu}{\int_{\mathcal{B}_{2}^{d}(R+\sqrt{d/CT})}1\text{d}\mu},$
(30)

where $\mu$ is the Lebesgue measure and

$p_{{\bf w}}(y^{T}\mid{\bf x}^{T})=\prod_{t=1}^{T}f({\bf w},{\bf
x}_{t})^{y_{t}}(1-f({\bf w},{\bf x}_{t}))^{1-y_{t}}.$

We now write $h_{t}({\bf w})\overset{\text{def}}{=}\log f({\bf w},{\bf
x}_{t})^{y_{t}}(1-f({\bf w},{\bf x}_{t}))^{1-y_{t}}$ to simplify notation. It
is easy to see that $\ell(f({\bf w},{\bf x}_{t}),y_{t})=-h_{t}({\bf w})$.

Let ${\bf w}^{*}$ be the point in $\mathcal{B}_{2}^{d}(R)$ that maximizes

$h({\bf w})\overset{\text{def}}{=}\sum_{t=1}^{T}h_{t}({\bf w}).$

Let $\textbf{u}=\nabla h({\bf w}^{*})$ be the gradient of $h$ at ${\bf
w}^{*}$. By Taylor theorem, we have for any ${\bf
w}\in\mathcal{B}_{2}^{d}(R+\sqrt{d/CT})$

$h({\bf w})=h({\bf w}^{*})+\textbf{u}^{T}({\bf w}-{\bf
w}^{*})+\frac{1}{2}({\bf w}-{\bf w}^{*})^{\tau}\nabla^{2}_{{\bf
w}^{\prime}}h({\bf w}^{\prime})({\bf w}-{\bf w}^{*}),$

where ${\bf w}^{\prime}$ is a convex combination of ${\bf w}$ and ${\bf
w}^{*}$ and $\textbf{u}^{\tau}$ is the transpose of u.

Now, the key observation is that for any point ${\bf w}$ such that
$\textbf{u}^{\tau}({\bf w}-{\bf w}^{*})\geq 0$ we have

$h({\bf w})\geq h({\bf w}^{*})+\frac{1}{2}({\bf w}-{\bf
w}^{*})^{\tau}\nabla^{2}_{{\bf w}^{\prime}}h({\bf w}^{\prime})({\bf w}-{\bf
w}^{*})\geq h({\bf w}^{*})-\frac{1}{2}CT||{\bf w}-{\bf w}^{*}||_{2}^{2},$ (31)

where the last inequality follows from our assumption about the bounded
Hessian of $\log f$. Let $B$ be the half ball of radius $\sqrt{d/CT}$ centered
at ${\bf w}^{*}$ such that for all ${\bf w}\in B$ we have $\textbf{u}^{T}({\bf
w}-{\bf w}^{*})\geq 0$. By (31), for all ${\bf w}\in B$

$h({\bf w})\geq h({\bf w}^{*})-\frac{1}{2}CT(\sqrt{d/CT})^{2}=h({\bf
w}^{*})-d/2.$ (32)

Note that $B\subset\mathcal{B}_{2}^{d}(R+\sqrt{d/CT})$. Then using above
observations we arrive at

$\displaystyle\sum_{t=1}^{T}\ell(\hat{y}_{t},y_{t})$
$\displaystyle\leq-\log\frac{\int_{\mathcal{B}_{2}^{d}(R+\sqrt{d/CT})}p_{{\bf
w}}(y^{T}\mid{\bf
x}^{T})\text{d}\mu}{\int_{\mathcal{B}_{2}^{d}(R+\sqrt{d/CT})}1\text{d}\mu}$
(33) $\displaystyle\leq-\log\frac{\int_{B}p_{{\bf w}}(y^{T}\mid{\bf
x}^{T})\text{d}\mu}{\int_{\mathcal{B}_{2}^{d}(R+\sqrt{d/CT})}1\text{d}\mu}$
(34) $\displaystyle\leq-\log\frac{e^{-d/2}\int_{B}p_{{\bf
w}^{*}}(y^{T}\mid{\bf
x}^{T})\text{d}\mu}{\int_{\mathcal{B}_{2}^{d}(R+\sqrt{d/CT})}1\text{d}\mu}$
(35) $\displaystyle=-\log p_{{\bf w}^{*}}(y^{T}\mid{\bf
x}^{T})+d/2-\log\frac{\text{Vol}(B)}{\text{Vol}(\mathcal{B}_{2}^{d}(R+\sqrt{d/CT}))}$
(36) $\displaystyle=-\log p_{{\bf w}^{*}}(y^{T}\mid{\bf
x}^{T})+d/2-\log\frac{\frac{1}{2}\sqrt{\frac{d}{CT}}^{d}}{(R+\sqrt{d/CT})^{d}}$
(37) $\displaystyle\leq-\log p_{{\bf w}^{*}}(y^{T}\mid{\bf
x}^{T})+d/2+\frac{d}{2}\log\left(\frac{2CR^{2}T}{d}+2\right)+\log 2$ (38)
$\displaystyle=\sum_{t=1}^{T}\ell(f({\bf w}^{*},{\bf
x}_{t}),y_{t})+\frac{d}{2}\log\left(\frac{2CR^{2}T}{d}+2\right)+d/2+\log 2.$
(39)

This completes the proof of Theorem 4.

######  Remark 2.

When compared to the technique in [39], Theorem 4 does not assume that the
gradient critical point of the loss is zero (e.g., the minimum may occur on
the boundary). This is why we need to restrict to the half ball $B$ in order
to discard the linear term of Taylor expansion in Equation (32). Moreover, in
the proof we work directly on the continuous space instead of a discretized
cover, giving an efficient algorithm provided the posterior is efficiently
samplable (by e.g., assuming some log-concavity of $f$ as in [11]).

##  Appendix E Proof of Theorem 5

We start with the following technical lemma.

######  Lemma 8.

The following inequality holds, for $r>0$:

$\sum_{\textbf{y}\in\\{0,1\\}^{T/d}}\sup_{w\in[c_{1}-c_{2}d^{-r},c_{1}+c_{2}d^{-r}]}P(\textbf{y}\mid
w)\geq\Omega(\sqrt{T/d^{2r+1}}),$ (40)

where $P(\textbf{y}\mid w)=w^{k}(1-w)^{T/d-k}$ with $k$ being the number of
$1$s in y.

###### Proof.

By Stirling approximation, for all $k\in[T/d]$, there exists a constant
$C\in\mathbb{R}^{+}$ such that

$\displaystyle B(k,T/d)$
$\displaystyle\overset{\text{def}}{=}\binom{T/d}{k}\left(\frac{k}{T/d}\right)^{k}\left(1-\frac{k}{T/d}\right)^{T/d-k}$
$\displaystyle\geq C\sqrt{\frac{T/d}{k(T/d-k)}}.$

Since $P(\textbf{y}\mid w)$ achieves maximum at $w=k*d/T$, we have

$\sum_{\textbf{y}\in\\{0,1\\}^{T/d}}\sup_{w\in[c_{1}-c_{2}d^{-r},c_{1}+c_{2}d^{-r}]}p(\textbf{y}\mid
w)\geq\sum_{k=c_{1}T/d-c_{2}T/d^{r+1}}^{c_{1}T/d+c_{2}T/d^{r+1}}B(k,T/d).$

Therefore, for each $k$ in the above summation, we have that

$\frac{1}{\sqrt{k(T/d-k)}}\geq\sqrt{(c_{1}+c_{2}d^{-r})(1-c_{1}-c_{2}d^{-r})}d/T.$

Therefore, the LHS of (40) is lower bounded by

$C\sqrt{(c_{1}+c_{2}d^{-r})(1-c_{1}-c_{2}d^{-r})}\sqrt{\frac{T}{d}}\frac{2c_{2}}{d^{r}}=\Omega(\sqrt{T/d^{2r+1}})$

for sufficient large $d$. ∎

Now we are ready to prove Theorem 5. We choose a particular ${\bf x}^{T}$: We
split the ${\bf x}^{T}$ into $d$ blocks each with length of $T/d$. With that,
the $i$th part of the inputs and the outputs are denoted by ${\bf
x}^{(i)}=({\bf x}_{(T/d)*(i-1)+1},\cdots,{\bf x}_{(T/d)*i})$ and
$\textbf{y}^{(i)}=(y_{(T/d)*(i-1)+1},\cdots,y_{(T/d)*i})$, respectively. We
define for any ${\bf x}_{t}$ in the $i$th block ${\bf x}^{(i)}$ equals ${\bf
e}_{i}$ the standard $d$ base of $\mathbb{R}^{d}$ with $1$ in position $i$ and
$0$s otherwise. Note that, with these choice of ${\bf x}_{t}$s, we have
$\langle{\bf w},{\bf x}_{t}\rangle=w_{i}$, where $w_{i}$ is the $i$th
coordinate of ${\bf w}$ and ${\bf x}_{t}\in{\bf x}^{(i)}$.

We will lower bound $r^{*}_{T}(\mathcal{H}_{f}\mid{\bf x}^{T})$, which will
automatically give a lower bound on $r^{a}_{T}(\mathcal{H}_{f})$. We only need
to compute the following Shtarkov sum

$S_{T}(\mathcal{H}_{f}|{\bf x}^{T})=\sum_{y^{T}\in\\{0,1\\}^{T}}\sup_{{\bf
w}\in\mathcal{B}_{s}^{d}(1)}\prod_{i=1}^{d}P_{f}(\textbf{y}^{(i)}|w_{i}),$
(41)

where $P_{f}(\textbf{y}^{(i)}|w_{i})=f(w_{i})^{k_{i}}(1-f(w_{i}))^{T/d-k_{i}}$
with $k_{i}$ being the number of $1$s in $\textbf{y}^{(i)}$. We observe

$\displaystyle S_{T}(\mathcal{H}_{f}|{\bf x}^{T})$
$\displaystyle\geq\sum_{y^{T}\in\\{0,1\\}^{T}}\prod_{i=1}^{d}\sup_{w_{i}\in[-d^{-1/s},d^{-1/s}]}P_{f}(\textbf{y}^{(i)}|w_{i})$
$\displaystyle=\prod_{i=1}^{d}\sum_{\textbf{y}^{(i)}\in\\{0,1\\}^{T/d}}\sup_{w_{i}\in[-d^{-1/s},d^{-1/s}]}P_{f}(\textbf{y}^{(i)}|w_{i})$
$\displaystyle=\Big{(}\sum_{\textbf{y}\in\\{0,1\\}^{T/d}}\sup_{w\in[-d^{-1/s},d^{-1/s}]}P_{f}(\textbf{y}|w)\Big{)}^{d}$
$\displaystyle\geq\left(\sum_{\textbf{y}\in\\{T/d\\}}\sup_{w\in[c_{1}-c_{2}d^{-1/s},c_{1}+c_{2}d^{-1/s}]}P(\textbf{y}\mid
w)\right)^{d}$

where $P(\textbf{y}\mid w)$ is as in Lemma 8 and the last inequality holds
since $[c_{1}-c_{2}d^{-1/s},c_{1}+c_{2}d^{-1/s}]\subset
f([d^{-1/s},d^{-1/s}])$ by the assumption. Now, Lemma 8 implies that

$S_{T}(\mathcal{H}_{f}\mid{\bf x}^{T})\geq
c^{d}\left(\frac{T}{d^{(s+2)/s}}\right)^{d/2},$

where $c$ is some absolute constant that is independent of $d,T$. We conclude

$r^{a}_{T}(\mathcal{H}_{f})\geq r^{*}_{T}(\mathcal{H}_{f})\geq\log
S_{T}(\mathcal{H}_{f}|{\bf
x}^{T})\geq\frac{d}{2}\log\left(\frac{T}{d^{(s+2)/s}}\right)-O(d)$

which completes the proof.

##  Appendix F Proof of Lemma 5

We first introduce a discretized notion of fat-shattering number, which can be
viewed as a misspecified Littlestone dimension [2, 7], see also [23]. For any
$\alpha>0$, we can choose $K\leq\lceil 1/2\alpha\rceil$ points
$z_{1}<z_{2}\cdots<z_{K}$ in the interval $[0,1]$ such that any point in
$[0,1]$ is $\alpha$ close to some $z_{k}$ and $z_{k+1}-z_{k}=2\alpha$ for all
$k\in[K]$. Now, we define a discretized class $\mathcal{H}^{\prime}$ for the
$[0,1]$-valued class $\mathcal{H}$ in the following way. For any
$h\in\mathcal{H}$, we define function $h^{\prime}\in\mathcal{H}^{\prime}$ such
that for any ${\bf x}\in\mathcal{X}$ we have

$h^{\prime}({\bf x})=\arg\min_{z_{k}\in\\{z_{1},\cdots,z_{K}\\}}|z_{k}-h({\bf
x})|,$

where we break ties arbitrarily.

We now view the functions in $\mathcal{H}^{\prime}$ as functions map
$\mathcal{X}\rightarrow[K]$ (i.e., we view each $z_{k}$ as its index $k$). For
any discretized class $\mathcal{H}^{\prime}$, we define the discretized
$1$-shattering as follows. For any $\mathcal{X}$-valued tree $\tau$ of depth
$d$, we say $\mathcal{H}^{\prime}$ $1$-shatters $\tau$, if there exists
$[K]$-valued tree $\text{s}:\\{0,1\\}^{d}_{*}\rightarrow[K]$ such that for any
$\epsilon_{1}^{d}\in\\{0,1\\}^{d}_{*}$ there exist
$h^{\prime}\in\mathcal{H}^{\prime}$ such that for all $t\in[d]$:

  * 1.

If $\epsilon_{t}=0$, then
$h^{\prime}(\tau(\epsilon_{1}^{t-1}))\leq\textbf{s}(\epsilon_{1}^{t-1})-1.$

  * 2.

if $\epsilon_{t}=1$, then
$h^{\prime}(\tau(\epsilon_{1}^{t-1}))\geq\textbf{s}(\epsilon_{1}^{t-1})+1.$

######  Definition 3.

The discretized $1$-shattering number of a discretized class
$\mathcal{H}^{\prime}$ is defined to be the maximum number $d$ such that
$\mathcal{H}^{\prime}$ $1$-shatters some tree $\tau$ of depth $d$. This number
is denoted as $\textbf{FAT}_{1}(\mathcal{H}^{\prime})$. If no such tree
exists, we define the $1$-shattering number to be $0$ if
$\mathcal{H}^{\prime}$ is non-empty and $-1$ if $\mathcal{H}^{\prime}$ is
empty.

The proof of Lemma 5 follows from the following three lemmas.

######  Lemma 9.

The discretized $1$-shattering number of $\mathcal{H}^{\prime}$ is upper
bounded by the $\alpha$-fat shattering number of $\mathcal{H}$ where
$\mathcal{H}^{\prime}$ is the discretized class of $\mathcal{H}$ at scale
$\alpha$.

###### Proof.

Let $\tau$ be the tree of depth $d$ that is shattered by $\mathcal{H}$ with a
$[K]$-valued tee s. We define a $[0,1]$-valued tree $\textbf{s}^{\prime}$ as
follows for any $\epsilon_{1}^{t}\in\\{0,1\\}^{d}_{*}$,

$\textbf{s}^{\prime}(\epsilon_{1}^{t-1})=z_{\textbf{s}(\epsilon_{1}^{t-1})}.$

We now show that the $\tau$ and $\textbf{s}^{\prime}$ are the desired pair
that is $\alpha$-shattered by $\mathcal{H}$. This follows from the fact that
for any $z_{k}$ and $z_{l}$ with $k\not=l$ if some $y\in[0,1]$ is closer to
$z_{l}$ , then

$|y-z_{k}|\geq\alpha$

as easy to see. ∎

For any discretized class $\mathcal{H}^{\prime}$, we say a class $\mathcal{G}$
of functions map $\mathcal{X}^{*}\rightarrow[K]$ $1$-covers
$\mathcal{H}^{\prime}$ if for any ${\bf x}_{1},\cdots,{\bf
x}_{T}\in\mathcal{X}$ and $h^{\prime}\in\mathcal{H}^{\prime}$ there exists
$g\in\mathcal{G}$ such that for all $t\in[T]$

$|h^{\prime}({\bf x}_{t})-g({\bf x}^{t})|\leq 1.$

The following result is crucial for our following analysis, which is an
analogy of Lemma 12 of [2] (see also [7, 22]).

Algorithm 3 M-SOA algorithm

Input: Hypothesis class $\mathcal{H}$ with functions map
$\mathcal{X}\rightarrow[K]$

1:Let $\mathcal{H}^{*}=\mathcal{H}$

2:for $t=1,\cdots,T$ do

3: Receive feature ${\bf x}_{t}$

4: For $k\in[K]$, let  $\mathcal{H}^{*}_{({\bf
x}_{t},k)}\overset{\text{def}}{=}\\{h\in\mathcal{H}^{*}\mid h({\bf
x}_{t})=k\\}$

5: Make prediction
$\hat{y}_{t}=\arg\max_{k\in[K]}\textbf{FAT}_{1}(\mathcal{H}^{*}_{({\bf
x}_{t},k)})$ (where we break ties arbitrarily and deal with empty classes as
in Definition 3)

6: Receive label $y_{t}$

7: If $|\hat{y}_{t}-y_{t}|\geq 2$, set
$\mathcal{H}^{*}=\mathcal{H}^{*}_{({\bf x}_{t},y_{t})}$

8: If $|\hat{y}_{t}-y_{t}|<2$, set  $\mathcal{H}^{*}=\mathcal{H}^{*}$

9:end for

######  Lemma 10.

Suppose the discretized $1$-shattering number of $\mathcal{H}^{\prime}$ is
upper bounded by $d$, then there exists a $1$-covering set $\mathcal{G}$ of
$\mathcal{H}^{\prime}$ such that

$|\mathcal{G}|\leq\sum_{t=0}^{d}\binom{T}{t}K^{t}\leq(TK)^{d+1}.$

###### Proof.

We now describe an algorithm that is similar to the SOA algorithm of [2],
which we will call it M-SOA (Algorithm 3)666The major difference with the
standard SOA is steps 7-8 and where ”M” stands for misspecified.. The
algorithm goes as follows: it maintains a running hypothesis class
$\mathcal{H}^{*}$, initially equals $\mathcal{H}^{\prime}$. Let $({\bf
x}_{t},y_{t})$ be the sample label pair received at round $t$. We will denote
by $\mathcal{H}^{*}_{({\bf x}_{t},y_{t})}$ the functions in $\mathcal{H}^{*}$
that is consistent with $({\bf x}_{t},y_{t})$, i.e., for all
$h\in\mathcal{H}^{*}_{({\bf x}_{t},y_{t})}$ we have

$h({\bf x}_{t})=y_{t}.$

At time step $t$, the algorithm M-SOA will predict $k\in[K]$ such that
$\textbf{FAT}_{1}(\mathcal{H}^{*}_{({\bf x}_{t},k)})$ is maximum, where we
denote by $\textbf{FAT}_{1}(\mathcal{H}^{*}_{({\bf x}_{t},k)})$ the
discretised 1-shattering number of $\mathcal{H}^{*}_{({\bf x}_{t},k)}$ and
break ties arbitrarily. After receiving the true label $y_{t}$, the M-SOA
algorithm will do the following. If $|\hat{y}_{t}-y_{t}|\geq 2$, then it sets
$\mathcal{H}^{*}=\mathcal{H}^{*}_{({\bf x}_{t},y_{t})}$. Else, it remains on
the same $\mathcal{H}^{*}$. We then continue the prediction procedure for the
next time step with the new $\mathcal{H}^{*}$.

We say the algorithm M-SOA makes an error at time step $t$ if
$|\hat{y}_{t}-y_{t}|\geq 2$ where $\hat{y}_{t}$ is the prediction given by
M-SOA at time step $t$. We claim that the M-SOA will make at most $d$ errors
if the samples $({\bf x}^{T},y^{T})$ is consistent with some
$h\in\mathcal{H}^{\prime}$.

To see this, we prove by induction on $d$ and $T$ (the base case for $d=0$ or
$T=0$ is easy to check). Suppose we have observed ${\bf x}_{1}$ at the first
step. We show that there can not be two element $k_{1},k_{2}\in[K]$ such that
$|k_{1}-k_{2}|\geq 2$ and both $\mathcal{H}^{\prime}_{({\bf x}_{1},k_{1})}$
and $\mathcal{H}^{\prime}_{({\bf x}_{1},k_{2})}$ has discretized
$1$-shattering number $\geq d$. Otherwise, we can concatenate the shattering
tree of $\mathcal{H}^{\prime}_{({\bf x}_{1},k_{1})}$ and
$\mathcal{H}^{\prime}_{({\bf x}_{1},k_{2})}$ with the root labeled by ${\bf
x}_{1}$ to form a depth $d+1$ shattering tree of $\mathcal{H}^{\prime}$ (with
$\textbf{s}(\phi)$ being any number $\in(k_{1},k_{2})$). This is a
contradiction, since the discretized $1$-shattering number of
$\mathcal{H}^{\prime}$ is upper bounded by $d$. This shows that either we will
make no error at the first step or the discretized $1$-shattering number
decreased by at least $1$ on the remaining consistent class of functions
(after $y_{1}$ has been revealed). For the first case, by induction hypothesis
for $T-1$ we have the number of errors is at most $d$. For the second case, we
also have the number of errors upper bounded by $d-1+1=d$.

We now follow the idea from the proof of Lemma 12 of [2] to construct a
covering set $\mathcal{G}$. For any subset $I\subset[T]$ of size $|I|\leq d$
and $\\{k_{t}\\}_{t\in I}\in[K]^{|I|}$, we define a function $g$ by running
our M-SOA algorithm by changing steps $7-8$ as follows. At each time step
$t\in[I]$, we update $\mathcal{H}^{*}=\mathcal{H}^{*}_{({\bf x}_{t},k_{t})}$.
Otherwise, for any $t\not\in I$, we remain on the same $\mathcal{H}^{*}$. The
values of $g$ for each ${\bf x}^{t}$ is given by the output of M-SOA at time
step $t$.

Since the M-SOA will make at most $d$ errors if the sample-label pairs $({\bf
x}^{T},y^{T})$ are consistent with some function in $\mathcal{H}^{\prime}$, we
know that any $h\in\mathcal{H}^{\prime}$ is $1$-covered by the function
generated by running M-SOA with some $I$ and $\\{k_{t}\\}_{t\in I}$ in the
above fashion. To complete we observe that by a simple counting argument the
number of such pairs $I$ and $\\{k_{t}\\}_{t\in I}$ is at most

$\sum_{t=0}^{d}\binom{T}{t}K^{t}$

which completes the proof. ∎

Finally, we need the following lemma that relates $1$-covering of
$\mathcal{H}^{\prime}$ with global sequential $\alpha$-covering of
$\mathcal{H}$.

######  Lemma 11.

Suppose there exist a $1$-covering set $\mathcal{G}$ of
$\mathcal{H}^{\prime}$, then there exists a global $3\alpha$-covering
$\mathcal{G}^{\prime}$ of $\mathcal{H}$ such that
$|\mathcal{G}|=|\mathcal{G}^{\prime}|$, where $\mathcal{H}^{\prime}$ is the
discretised class of $\mathcal{H}$ at scale $\alpha$.

###### Proof.

For any $g\in\mathcal{G}$, we define a function $g^{\prime}$ such that for all
${\bf x}^{t}$ we have

$g^{\prime}({\bf x}^{t})=z_{g({\bf x}^{t})}.$

The claim follows from the fact that any $y$ that is closest to $z_{k}$
satisfies $|y-z_{k}|\leq\alpha$ and if some $z$ $1$-covers $z_{k}$ then we
have $|z-z_{k}|\leq 2\alpha$, by triangle inequality

$|y-z|\leq 3\alpha$

as needed. ∎

The proof of Lemma 5 follows from Lemma 9, Lemma 10, and Lemma 11.

##  Appendix G Proof of Theorem 6

It is sufficient to compute the Shtarkov sum as in (5). For any
$y^{T}\in\\{0,1\\}^{T}$ with $k$ $1$s, we claim that

$\sup_{\textbf{p}\in\mathcal{D}_{s}}p(y^{T})=\frac{1}{k^{k/s}},$

where

$p(y^{T})=\prod_{t=1}^{T}p_{t}^{y_{t}}(1-p_{t})^{1-y_{t}}.$

To see this, we use a _perturbation_ argument. Denote $I$ be the positions in
$y^{T}$ that takes value $1$ such that $|I|=k$. For any p such that $p(y^{T})$
is maximum, we must have $p_{j}=0$ for all $j\not\in I$. Suppose otherwise, we
then can move some probability mass on $p_{j}$ to some $p_{i}<1$ with $i\in
I$, which will increase the value of $p(y^{T})$, thus a contradiction. Now, we
need to show that

$\prod_{i\in I}p_{i}\leq\frac{1}{k^{k/s}},$

this follows easily by AM-GM (i.e., arithmetic mean vs geometric mean)
inequality since $\sum_{i\in I}p_{i}^{s}\leq 1$ and it takes equality when
$p_{i}=\frac{1}{k^{1/s}}$ for all $i\in I$. Now, the Shtarkov sum can be
written as

$\sum_{k=0}^{T}\binom{T}{k}\frac{1}{k^{k/s}}.$ (42)

To find a lower bound, we only need to estimate the maximum term in the
summation. We have

$\max_{k}\binom{T}{k}\frac{1}{k^{k/s}}\geq\max_{k}\frac{T^{k}}{k^{(1+1/s)k}}\geq
e^{\frac{s+1}{s\cdot e}T^{s/s+1}},$

where the last inequality follows by taking $k=\frac{1}{e}T^{s/s+1}$, and we
also use the fact that

$\binom{T}{k}\geq\frac{T^{k}}{k^{k}}.$

Therefore, we have

$r^{*}_{T}(\mathcal{D}_{s})\geq\frac{s+1}{s\cdot
e}T^{s/s+1}=\Omega(T^{s/s+1})$

which completes the proof.