# Contextual Continuum Bandits: Static Versus Dynamic Regret

Arya Akhavan
Istituto Italiano di Tecnologia
CMAP, Ecole Polytechnique, IP Paris
<EMAIL_ADDRESS>&Karim Lounici
CMAP, Ecole Polytechnique, IP Paris
<EMAIL_ADDRESS>Massimiliano Pontil
Istituto Italiano di Tecnologia
University College London
<EMAIL_ADDRESS>&Alexandre B. Tsybakov
CREST, ENSAE, IP Paris
<EMAIL_ADDRESS>
###### Abstract

We study the contextual continuum bandits problem, where the learner
sequentially receives a side information vector and has to choose an action in
a convex set, minimizing a function associated to the context. The goal is to
minimize all the underlying functions for the received contexts, leading to a
dynamic (contextual) notion of regret, which is stronger than the standard
static regret. Assuming that the objective functions are Hölder with respect
to the contexts, we demonstrate that any algorithm achieving a sub-linear
static regret can be extended to achieve a sub-linear dynamic regret. We
further study the case of strongly convex and smooth functions when the
observations are noisy. Inspired by the interior point method and employing
self-concordant barriers, we propose an algorithm achieving a sub-linear
dynamic regret. Lastly, we present a minimax lower bound, implying two key
facts. First, no algorithm can achieve sub-linear dynamic regret over
functions that are not continuous with respect to the context. Second, for
strongly convex and smooth functions, the algorithm that we propose achieves,
up to a logarithmic factor, the minimax optimal rate of dynamic regret as a
function of the number of queries.

##  1 Introduction

The continuum bandit problem presents a sequential decision-making challenge
where, at each round, an action is taken as a continuous variable followed by
suffering a corresponding loss. Various variants of this problem have been
explored in the literature. The most extensively studied framework involves
the learner receiving a function $f_{t}:\Theta\rightarrow\mathbb{R}$ (random
or non-random), at each round $t$, where $\Theta\subseteq\mathbb{R}^{d}$ is a
convex body (compact and convex set with a non-empty interior). Based on
$\\{(y_{k},\boldsymbol{z}_{k})\\}_{k=1}^{t-1}$, the learner selects
$\boldsymbol{z}_{t}\in\Theta$, suffers loss $f_{t}(\boldsymbol{z}_{t})$, and
receives the noisy feedback

$y_{t}=f_{t}(\boldsymbol{z}_{t})+\xi_{t},$

where $\xi_{t}$ denotes the noise variable. The standard goal of the learner
is to minimize the static regret

$\displaystyle\mathbf{E}\Big{[}\sum_{t=1}^{T}f_{t}(\boldsymbol{z}_{t})-\min_{\boldsymbol{z}\in\Theta}\sum_{t=1}^{T}f_{t}(\boldsymbol{z})\Big{]}.$
(1)

However, in this paper we consider a more ambitious task, which is to minimize
the dynamic regret

$\displaystyle\mathbf{E}\Big{[}\sum_{t=1}^{T}f_{t}(\boldsymbol{z}_{t})-\sum_{t=1}^{T}\min_{\boldsymbol{z}\in\Theta}f_{t}(\boldsymbol{z})\Big{]}.$
(2)

Note that (2) presents a stronger notion of regret; achieving sub-linear
dynamic regret implies sub-linear static regret. The difference between static
and dynamic regret is where the minimum is placed. If static regret is small,
it means the algorithm is at least as good as a single constant action that
does well on the average of the functions seen during learning. In contrast,
proving that dynamic regret is small implies that the algorithm is good for
any function individually.

There is a sharp difference between static and dynamic regret. In general,
obtaining a sub-linear static regret does not imply convergence properties for
the sequence $\\{f_{t}(\boldsymbol{z}_{t})\\}_{t=1}^{T}$. The static regret is
not necessarily positive. Conversely, if an algorithm achieves sub-linear
dynamic regret, it asymptotically approaches the minimum values of the
received functions. Therefore a key question arises: When it is possible to
achieve a sub-linear dynamic regret?

In the setting of non-bandit online zero- and first-order optimization,
several authors have extensively explored the minimization of dynamic regret
(2), see e.g., [34, 54, 9, 19, 24, 52]. To achieve sub-linear dynamic regret,
these works introduce complexity assumptions on the received functions. Such
assumptions characterize similarity between two consecutive functions helping
the learner to leverage previously received information for subsequent
inference. In the present paper, we consider the problem of contextual
continuum bandits under the similarity notion described by Assumption 1 below.

Contextual continuum bandits. Let $\Theta\subseteq\mathbb{R}^{d}$ be a convex
body. Let $f:\mathbb{R}^{d}\times[0,1]^{p}\to\mathbb{R}$ be an unknown
function. At each round $t$:

  * •

A context $\boldsymbol{c}_{t}\in[0,1]^{p}$ is revealed by the adversary.

  * •

The learner chooses a query point $\boldsymbol{z}_{t}\in\Theta$ and gets a
noisy evaluation of $f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})$:

$\displaystyle y_{t}=f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})+\xi_{t},$ (3)

where $\xi_{t}$ is a scalar noise variable.

The learner’s objective in this framework is to minimize the contextual
regret, defined as:

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\text{min}_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\right].$
(4)

By letting $f_{t}(\cdot)=f(\cdot,\boldsymbol{c}_{t})$ we see that (4) is
equivalent to the dynamic regret (2). Here and in the sequel, unless other
assumption is explicitly stated, we assume that $\boldsymbol{c}_{t}$ is drawn
by an adversary who may be aware of all previous actions of the learner and
past information received by the learner. This formalization is an extension
of the contextual multi-armed bandit problem [5] to the continuous action
setup. One can consider the continuous dosage drug design problem as an
example. At each round $t$, the learner encounters a patient with a specific
medical profile encoded as $\boldsymbol{c}_{t}$. The learner’s goal is to
craft a drug containing $d$ substances that closely matches the optimal drug
design for a patient with the profile $\boldsymbol{c}_{t}$. Informally,
achieving a sub-linear dynamic regret implies that, as $t$ increases, the
designed drug approaches the best possible drug for the medical profile
$\boldsymbol{c}_{t}$. However, in Section 5 we demonstrate that, regardless of
the behavior of the function $f(\cdot,\boldsymbol{c})$, if the function
$f(\boldsymbol{x},\cdot)$ lacks continuity, obtaining a sub-linear dynamic
regret may be impossible. Hence, we are lead to assume that
$f(\boldsymbol{x},\cdot)$ is a continuous function for any
$\boldsymbol{x}\in\mathbb{R}^{d}$. This is aligned with the example of
continuous dosage drug design. Indeed, it is natural to consider that the
effect of a fixed drug is similar for two patients with similar medical
profiles. This intuition leads us to the following somewhat stronger
assumption that we adopt in the sequel.

######  Assumption 1.

For $(L,\gamma)\in[0,\infty)\times(0,1]$ we assume that
$f\in\mathcal{F_{\gamma}}(L)$, where $\mathcal{F_{\gamma}}(L)$ denotes the
class of all functions $f:\mathbb{R}^{d}\times[0,1]^{p}\to\mathbb{R}$ such
that

$\displaystyle|f(\boldsymbol{x},\boldsymbol{c})-f(\boldsymbol{x},\boldsymbol{c}^{\prime})|\leq
L\left\lVert\boldsymbol{c}-\boldsymbol{c}^{\prime}\right\rVert^{\gamma},\quad\text{for
all}\quad\boldsymbol{x}\in\Theta,\,\,\boldsymbol{c},\boldsymbol{c}^{\prime}\in[0,1]^{p},$
(5)

where $\left\lVert\cdot\right\rVert$ is the Euclidean norm.

In Section 3, we provide a static-to-dynamic regret conversion theorem that
can be summarized as follows. Consider functions $f_{t}$ that can be
represented as $f_{t}(\boldsymbol{x})=f(\boldsymbol{x},\boldsymbol{c}_{t})$,
where $f:\mathbb{R}^{d}\times[0,1]^{p}\to\mathbb{R}$. We show that if there
exists an algorithm attaining a sub-linear static regret (1) when all
$f_{t}$’s belong to a class of functions $\mathcal{F}$, then the same
algorithm can be extended to achieve sub-linear dynamic regret for functions
within $\mathcal{F}\cap\mathcal{F}_{\gamma}(L)$.

In Section 4, we focus on a specific class $\mathcal{F}$ that consists of
strongly convex and smooth functions. In order to apply the approach developed
in Section 3, we first construct an algorithm that achieves sub-linear static
regret, see Algorithm 2. It is inspired by the Bandit Convex Optimization
(BCO) algorithm proposed in [20], which is valid for non-noisy observations,
that is, when $\xi_{t}\equiv 0$ in (3). In contrast, Algorithm 2 works for
noisy observations. Next, for functions $f$ that additionally belong to the
class $\mathcal{F}_{\gamma}(L)$, we extend the algorithm to attain a sub-
linear dynamic regret using the conversion theorem of Section 3. Finally, in
Section 5 we demonstrate that, if $f(\boldsymbol{x},\cdot)$ lacks continuity,
obtaining a sub-linear dynamic regret may be impossible. Moreover, the minimax
lower bound established in Section 5 implies near optimality (up to a
logarithmic factor) of the algorithm proposed in Section 4.

##  2 Related work

The material presented below can be approached from three interconnected
points of view: (i) the setting of contextual bandits, which is the main focus
of this paper; (ii) the study of dynamic regret and the conditions under which
sub-linear dynamic regret is achievable; and (iii) the convex bandits setting
with strongly convex objective functions (see Sections 4 and 5).

Contextual bandits. Contextual bandit problem is a variant of bandit problem,
where at each round the learner is equipped with an additional side
information on the subsequent objective function. The problem has been
introduced by [46] in the context of multi-armed bandits. Improvements and
different setups, but all within the framework of multi-armed bandits, have
been studied by many authors, see, e.g., [18, 45, 7, 39, 40, 38, 28, 6, 25,
48]. In the framework of continuum bandits, [42] studied the problem when
Assumption 1 holds with $\gamma=1$, along with an additional assumption that
the objective functions are Lipschitz with respect to the action variable, and
proposed a method achieving an exponentially growing with $p$ dynamic regret.
In [14], the authors studied the problem when Assumption 1 is satisfied, the
objective functions are Lipschitz and convex with respect to the action
variable, and the objective functions attain their global minimum in the
constraint set $\Theta$. They proposed an algorithm that achieves a sub-linear
dynamic regret and proved its optimality by deriving a matching minimax lower
bound.

In a framework close to the one that we consider in Sections 4 and 5, [33]
addressed the problem of contextual bandits when the functions are strongly
convex and smooth. To establish an upper bound for the regret, [33] assumed
that, for each $\boldsymbol{c}\in[0,1]^{p}$, the global minimizer
$\operatorname*{arg\,min}_{\boldsymbol{x}\in\mathbb{R}^{d}}f(\boldsymbol{x},\boldsymbol{c})$
is an interior point of the constraint set $\Theta$. While this assumption
might be hard to grant in practice, it does simplify the analysis
considerably. In the present paper, we drop this assumption and obtain in
Section 4 an upper bound that improves upon the result of [33]. Furthermore,
in Section 5 we present a matching lower bound demonstrating that the
algorithm that we propose is optimal to within a logarithmic factor.

Dynamic regret. In the context of online convex optimization, numerous authors
have obtained bounds on the dynamic regret. In the first-order optimization
setup, where the learner can access a noisy gradient of the function at any
given point, dynamic regret was explored by [9, 24, 34, 47, 49, 52, 53, 44].
For zero-order optimization, the dynamic regret has been studied by [54, 51,
50, 47, 15]. Among these papers, only [47, 15, 51] have addressed the
classical bandit framework, in which the learner is not allowed to query
function evaluations outside of the constraint set $\Theta$. We may also note
that all the papers on contextual bandits cited above are dealing with the
contextual regret, which is equivalent to the dynamic regret if the contexts
are adversarial as discussed after (4). However, it is quite common in the
literature to assume that the contexts are i.i.d. rather than adversarial.

Convex bandits. Convex bandits represent a family of constrained convex online
optimization problems where, at each round, the learner can only observe a
single function evaluation, and the query point must belong to the constraint
set $\Theta$. Static regret in convex bandits problems has been extensively
studied in the literature, see e.g., [32, 37, 30] and the references therein.
A particular instance dealing with strongly convex and smooth functions has
been investigated in [20] and [23] in a non-stochastic setting. In [20], the
authors proposed an algorithm leveraging an interior point method and a self-
concordant function. The achieved regret is nearly optimal, ranging from
$d\sqrt{T}$ to $d^{3/2}\sqrt{T}$ depending on the geometry of the constraint
set. Assuming that all the minimizers of the objective functions are in the
interior of the constraint set, [23] introduced an algorithm with a regret of
the order $d\sqrt{T}$. Both [20] and [23] studied the problem with no noise
($\xi_{t}\equiv 0$). In Section 4, we extend the results of [20] to noisy
function evaluation as in (3).

Regarding simply convex functions, the first studies date back to [16, 26],
where the authors addressed the setting with convex and Lipschitz objectives
and proposed algorithms that achieve a regret of the order $T^{3/4}$ up to a
factor depending on $d$. These works assume that the observed function values
are noise-free. Successive improvements [12, 21, 8, 29] showed that a regret
of the order $\sqrt{T}$ (up to a factor depending on $d$) can be attained in
the noise-free setting, the sharpest known rate being $d^{2.5}\sqrt{T}$ [29].
Noisy variant of the problem was studied only when the objective function does
not vary over time and the noise is sub-Gaussian. This led to algorithms with
a regret of the order $d^{16}\sqrt{T}$ [2] and $d^{4.5}\sqrt{T}$ [31]. For a
detailed survey on convex bandits, we refer the reader to [30, Sec. 2].

##  3 Static-to-dynamic regret conversion

We consider strategies for choosing the query points such that
$\boldsymbol{z}_{0}\in\mathbb{R}^{d}$ is a random variable, and
$\boldsymbol{z}_{t}=\pi_{t}(\\{\boldsymbol{c}_{k},\boldsymbol{z}_{k},y_{k}\\}_{k=1}^{t-1},\boldsymbol{c}_{t},\boldsymbol{\zeta}_{t})$
for $t\geq 1$, where $\pi_{t}$ is a measurable function with values in
$\mathbb{R}^{d}$, and $(\boldsymbol{\zeta}_{t})_{t\geq 1}$ is a sequence of
random variables with values in a measurable space $(\mathcal{Z},\mathcal{U})$
such that $\boldsymbol{\zeta}_{t}$ is independent of
$\\{\boldsymbol{c}_{k},\boldsymbol{z}_{k},y_{k}\\}_{k=1}^{t-1},\boldsymbol{c}_{t}$.
We call the process $\pi=(\pi_{t})_{t\geq 1}$ a randomized procedure and we
denote the set of all randomized procedures by $\Pi$.

Let $\mathcal{F}^{\prime}$ be a class of real-valued functions on
$\mathbb{R}^{d}$. We define
$\mathcal{F}=\\{f:f(\cdot,\boldsymbol{c})\in\mathcal{F}^{\prime}\text{ for all
}\boldsymbol{c}\in[0,1]^{p}\\}$. Assume that there exists a randomized
procedure $\pi$ that achieves a sub-linear static regret over $T$ runs for the
sequence of functions $\\{f(\cdot,\boldsymbol{c}_{t})\\}_{t=1}^{T}$ where
$f\in\mathcal{F}$. Namely, if $\\{\boldsymbol{z}_{t}\\}_{t=1}^{T}$ are outputs
of $\pi$, then there exists
$F:\mathbb{R}^{+}\cup\\{0\\}\to\mathbb{R}^{+}\cup\\{0\\}$, such that $F$ is a
concave function and

$\displaystyle{\sup_{f\in\mathcal{F}}\,}\mathbf{E}\left[\sum_{t=1}^{T}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}\sum_{t=1}^{T}f(\boldsymbol{z},\boldsymbol{c}_{t})\right]\leq
F(T).$ (6)

Moreover, we assume there exists
$(\tau_{1},\tau_{2},\tau_{3},\mathrm{T}_{0})\in[0,\infty)\times[0,1)\times[0,\infty)\times[1,\infty)$
such that, for $T\geq\mathrm{T}_{0}$,

$\displaystyle F(T)\leq Cd^{\tau_{1}}T^{\tau_{2}}\log^{\tau_{3}}(T+1),$ (7)

where $C>0$ is a constant that does not depend on $T$ and $d$.

######  Definition 1.

We call a randomized procedure that satisfies (6) and (7) a
$(\mathcal{F},\tau_{1},\tau_{2},\tau_{3},\mathrm{T}_{0})$-consistent
randomized procedure and we denote the set of all such procedures by
$\Pi(\mathcal{F},\tau_{1},\tau_{2},\tau_{3},\mathrm{T}_{0})$.

Input: Randomized procedure $\pi=(\pi_{t})_{t=1}^{\infty}$, parameter
$K\in\mathbb{N}$ and a partition $\\{B_{i}\\}_{i=1}^{K^{d}}$ of $[0,1]^{p}$

Initialization: $N_{1}(0),\dots,N_{K^{p}}(0)=0$,
$H(1),\dots,H(K^{p})=\\{0\\},\text{ and }\boldsymbol{z}_{0}=\boldsymbol{0}$

for  _ $t=1,\ldots,T$_ do

if  _$\boldsymbol{c}_{t}\in B_{i}$_ then

Let $N_{i}(t)=N_{i}(t-1)+1$

// Increment

Based on $\boldsymbol{c}_{t}$ and
$\\{y_{k},\boldsymbol{z}_{k},\boldsymbol{c}_{k}\\}_{k\in H(i)}$, use
$\pi_{N_{i}(t)}$ to choose $\boldsymbol{z}_{t}\in\Theta$

// Choosing the query point

$y_{t}=f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})+\xi_{t}$

// Query

$H(i)=H(i)\cup\\{t\\}$

// Update the set of indices

end if

end for

Algorithm 1

Algorithm 1 is a meta-algorithm for static-to-dynamic regret conversion. It
uses a partition $\\{B_{i}\\}_{i=1}^{K^{p}}$ of the hypercube $[0,1]^{p}$,
where all the cells $B_{i}$ are hypercubes of equal volume with edges of
length $1/K$. Fix a consistent randomized procedure $\pi$ for the class of
functions $\mathcal{F}$. At each round $t$, if the context
$\boldsymbol{c}_{t}$ falls into the cell $B_{i}$, Algorithm 1 chooses the
query point $\boldsymbol{z}_{t}$ by the procedure $\pi$ based only on the past
contexts from the same cell $B_{i}$ and the corresponding past query points.

Let $\\{\boldsymbol{c}_{i_{j}}\\}_{j=1}^{N_{i}(T)}$ be all the contexts
belonging to $B_{i}$ revealed up to round $T$, where $N_{i}(T)$ is the total
number of such contexts, and let
$\\{\boldsymbol{z}_{i_{j}}\\}_{j=1}^{N_{i}(T)}$ be the outputs of $\pi$
restricted to the contexts that belong to $B_{i}$ (the inner loop of Algorithm
1). This segment of the algorithm involves saving the index of the rounds
associated with the received contexts in cell $B_{i}$. The set $H(i)$ is the
collection of such indices. Denote by $\boldsymbol{b}_{i}$ the barycenter of
$B_{i}$, and let
$\boldsymbol{x}_{i}^{*}\in\operatorname*{arg\,min}_{\boldsymbol{x}\in\Theta}f(\boldsymbol{x},\boldsymbol{b}_{i})$.
Then,

$\displaystyle\mathbf{E}\bigg{[}\sum_{t=1}^{T}\bigg{(}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},$
$\displaystyle\boldsymbol{c}_{t})\bigg{)}\bigg{]}=\mathbf{E}\bigg{[}\sum_{i=1}^{K^{p}}\sum_{j=1}^{N_{i}(T)}\left(f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}_{i}^{*},\boldsymbol{c}_{i_{j}})+\Delta_{i_{j}}\right)\bigg{]}$
$\displaystyle\leq\mathbf{E}\bigg{[}\sum_{i=1}^{K^{p}}\big{(}\sum_{j=1}^{N_{i}(T)}f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-\min_{\boldsymbol{z}\in\Theta}\sum_{j=1}^{N_{i}(T)}f(\boldsymbol{z},\boldsymbol{c}_{i_{j}})+\sum_{j=1}^{N_{i}(T)}\Delta_{i_{j}}\big{)}\bigg{]},$

where
$\Delta_{i_{j}}=f(\boldsymbol{x}_{i}^{*},\boldsymbol{c}_{i_{j}})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{i_{j}})$.
Notice that $\Delta_{i_{j}}\leq
2\max_{\boldsymbol{z}\in\Theta}|f(\boldsymbol{z},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{z},\boldsymbol{b}_{i})|$,
so that under Assumption 1 we have $\Delta_{i_{j}}\leq
2L(\sqrt{p}/K)^{\gamma}$. Thus, we can control the dynamic regret by the sum
of the static regret, which grows with $K$, and the bias term comprised of
$\Delta_{i_{j}}$’s, which decreases with $K$. There exists an optimal $K$
exhibiting a trade-off between the static regret and the bias. In Theorem 1,
we show that if $K$ is tuned optimally,

$\displaystyle
K=K(\tau_{1},\tau_{2},\tau_{3},\gamma)\triangleq\max\left(1,\left\lfloor\left(Lp^{\frac{\gamma}{2}}d^{-\tau_{1}}{T^{(1-\tau_{2})}\log^{-\tau_{3}}(T+1)}\right)^{\frac{1}{p(1-\tau_{2})+\gamma}}\right\rfloor\right),$
(8)

then Algorithm 1 achieves a sub-linear dynamic regret.

######  Theorem 1.

Let $(L,\gamma)\in[0,\infty)\times(0,1]$. Let $\pi$ be a randomized procedure
such that (6) holds with a concave function $F$ and let $\boldsymbol{z}_{t}$’s
be the updates of Algorithm 1 with a positive integer $K$.

Then, we have

$\displaystyle\sup_{f\in\mathcal{F}\cap\mathcal{F}_{\gamma}(L)}\mathbf{E}\big{[}\sum_{t=1}^{T}\big{(}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\big{)}\big{]}\leq
K^{p}F\left(\frac{T}{K^{p}}\right)+2LT\left(\frac{\sqrt{p}}{K}\right)^{\gamma}.$
(9)

If, in addition,
$\pi\in\Pi(\mathcal{F},\tau_{1},\tau_{2},\tau_{3},\mathrm{T}_{0})$ for a
triplet
$(\tau_{1},\tau_{2},\mathrm{T}_{0})\in[0,\infty)\times[0,1)\times[1,\infty)$,
and $K=K(\tau_{1},\tau_{2},\tau_{3},\gamma)$ (see (8)), then for any $T\geq
K^{p}\mathrm{T}_{0}$, we have

$\displaystyle\sup_{f\in\mathcal{F}\cap\mathcal{F}_{\gamma}(L)}\mathbf{E}\big{[}\sum_{t=1}^{T}\big{(}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\big{)}\big{]}$
$\displaystyle\hskip 28.45274pt\leq
C^{\prime}\max\bigg{(}d^{\tau_{1}}T^{\tau_{2}}L_{1},\left(Lp^{\frac{\gamma}{2}}\right)^{\frac{p(1-\tau_{2})}{p(1-\tau_{2})+\gamma}}\left(d^{\tau_{1}}L_{1}\right)^{\frac{\gamma}{p(1-\tau_{2})+\gamma}}T^{\frac{(p-\gamma)(1-\tau_{2})+\gamma}{p(1-\tau_{2})+\gamma}}\bigg{)}.$
(10)

where $L_{1}=\log^{\tau_{3}}(T+1)$ and $C^{\prime}>0$ is a constant
independent of $T$, $d$, and $p$.

Note that the Lipschitz constant $L$ measures how sensitive the function $f$
is with respect to variations of the contexts. If $L=0$ the static and dynamic
regrets are equivalent, and it is not surprising that (7) and (1) have the
same rates. We also note that a bound that depends in the same way as (1) on
the parameters $p$, $d$, and $T$ can be achieved with a choice of $K$
independent of $L$. In Theorem 1 we assume that the learner knows the value of
$L$ but this is only done to highlight the gap between the notions of static
and dynamic regret.

The approach to contextual bandits based on partitioning the space of contexts
and running some algorithms $\pi$ separately within each cell is not new, see
[27, 13, 42]. These papers, as well as the follow-up works developing the same
approach, focused on a specific algorithm $\pi$, a specific class
$\mathcal{F}$ and provided a proof using their particular properties. They did
not invoke conversion from static to dynamic regret. In contrast, Theorem 1
highlights a general static-to-dynamic conversion phenomenon and provides a
ready-to-use tool for exploring particular examples. In the next section, we
demonstrate its application to the important case that $\mathcal{F}^{\prime}$
is the class of strongly convex and smooth functions.

##  4 Strongly convex and smooth functions

In this section, we apply the static-to-dynamic regret conversion developed in
Section 3 to the contextual bandits problem with the objective functions $f$
such that $f(\cdot,\boldsymbol{c})$ is $\beta$-smooth and $\alpha$-strongly
convex for any $\boldsymbol{c}\in[0,1]^{p}$.

######  Definition 2.

Let $\beta>0$. Function $F:\mathbb{R}^{d}\to\mathbb{R}$ is called
$\beta$-smooth, if it is continuously differentiable and for any
$\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{d}$ it satisfies

$\displaystyle\left\lVert\nabla F(\boldsymbol{x})-\nabla
F(\boldsymbol{y})\right\rVert\leq\beta\left\lVert\boldsymbol{x}-\boldsymbol{y}\right\rVert.$

######  Definition 3.

Let $\alpha>0$. A differentiable function $F:\mathbb{R}^{d}\to\mathbb{R}$ is
called $\alpha$-strongly convex, if for any
$\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{d}$ it satisfies

$\displaystyle F(\boldsymbol{x})\geq F(\boldsymbol{y})+\langle\nabla
F(\boldsymbol{y}),\boldsymbol{x}-\boldsymbol{y}\rangle+\frac{\alpha}{2}\left\lVert\boldsymbol{x}-\boldsymbol{y}\right\rVert^{2}.$

We impose the following assumption on the function $f$.

######  Assumption 2.

For $(\alpha,\beta,M)\in(0,\infty)\times[\alpha,\infty)\times(0,\infty)$, we
assume that $f\in\mathcal{F}_{\alpha,\beta}(M)$, where
$\mathcal{F}_{\alpha,\beta}(M)$ denotes the class of all functions
$f:\mathbb{R}^{d}\times[0,1]^{p}\to\mathbb{R}$ such that for all
$\boldsymbol{c}\in[0,1]^{p}$ the following holds.

  * i)

$f(\cdot,\boldsymbol{c})$ is $\alpha$-strongly convex.

  * ii)

$f(\cdot,\boldsymbol{c})$ is $\beta$-smooth.

  * iii)

$\max_{\boldsymbol{x}\in\Theta}|f(\boldsymbol{x},\boldsymbol{c})|\leq M$.

Following the approach of Section 3, we first construct a consistent
randomized procedure, that is, a procedure with sub-linear static regret, cf.
(6). To this end, our starting point is the BCO algorithm introduced in [20]
to solve strongly convex bandit problems. The BCO algorithm makes use of the
interior point method, which is a vital tool in convex optimization, see, e.g,
[36]. A pioneering role of introducing this method to the field of online
learning is credited to [1]. We cannot directly apply the BCO algorithm as
defined in [20] since [20] deals with the setting, where the observations
$y_{t}$ are noise-free. Therefore, we propose a modification of the BCO
algorithm adapted to noisy observations (3) with sub-Gaussian noise $\xi_{t}$.
It is defined in Algorithm 2. In what follows, $[T]$ denotes the set of all
positive integers less than or equal to $T$. We denote the unit Euclidean ball
in $\mathbb{R}^{d}$ by $B^{d}$ and the unit Euclidean sphere by $\partial
B^{d}$.

######  Assumption 3.

There is $\sigma>0$ such that for all $t\in[T]$ the following holds: (i)
$\xi_{t}$ is $\sigma$-sub-Gaussian, i.e., for any $\lambda>0$ we have
$\mathbf{E}\left[\exp\left(\lambda\xi_{t}\right)\right]\leq\exp\left(\sigma^{2}\lambda^{2}/2\right)$;
(ii) $\xi_{t}$ is independent of $\boldsymbol{\zeta}_{t}$.

We emphasize that the mutual independence of the noise variables $\xi_{t}$ is
not assumed.

The main ingredient of the interior point method is a self-concordant barrier
defined as follows.

######  Definition 4.

Let $\text{int}(\Theta)$ be the interior of the set $\Theta$. For $\mu>0$, a
function $\mathcal{R}:\text{int}(\Theta)\to\mathbb{R}$ is a self-concordant
function if the following holds.

  * •

$\mathcal{R}$ is three times differentiable and converges to infinity for any
trajectory that converges to the boundary of $\Theta$, i.e.,
$\mathcal{R}(\boldsymbol{y})\to\infty$ as $\boldsymbol{y}\to\partial\Theta$.

  * •

For any $\boldsymbol{x}\in\mathbb{R}^{d}$ and
$\boldsymbol{y}\in\text{int}(\Theta)$ we have

$\displaystyle|\nabla^{3}\mathcal{R}(\boldsymbol{y})[\boldsymbol{x},\boldsymbol{x},\boldsymbol{x}]|\leq
2\left(\nabla^{2}\mathcal{R}(\boldsymbol{y})[\boldsymbol{x},\boldsymbol{x}]\right)^{\frac{3}{2}},$

where for $m\in[3]$, and
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{m}\in\mathbb{R}^{d}$

$\displaystyle\nabla^{m}\mathcal{R}(\boldsymbol{y})[\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{m}]=\frac{\partial^{m}}{\partial
t_{1}\dots\partial
t_{m}}\mathcal{R}\left(\boldsymbol{y}+t_{1}\boldsymbol{x}_{1}+\dots+t_{m}\boldsymbol{x}_{m}\right)|_{t_{1}=0,\dots,t_{m}=0}.$

If, in addition, for some $\mu>0$, and any $\boldsymbol{x}\in\mathbb{R}^{d}$
and $\boldsymbol{y}\in\text{int}(\Theta)$ we have

$\displaystyle|\nabla\mathcal{R}(\boldsymbol{y})[\boldsymbol{x}]|\leq\mu^{\frac{1}{2}}\left(\nabla^{2}\mathcal{R}(\boldsymbol{y})[\boldsymbol{x},\boldsymbol{x}]\right)^{\frac{1}{2}},$

then the function $\mathcal{R}$ is called a $\mu$-self-concordant barrier.

Since $\Theta$ is bounded, $\nabla^{2}\mathcal{R}(\boldsymbol{x})$ is positive
definite and the minimizer of $\mathcal{R}$ in $\text{int}(\Theta)$ is unique,
see [35, Chapter 3, Section V]. Moreover, without loss of generality, we
assume that
$\min_{\boldsymbol{x}\in\text{int}(\Theta)}\mathcal{R}(\boldsymbol{x})=0$.
Self-concordant barriers can be chosen depending on the geometry of $\Theta$.
For the examples of $\mathcal{R}$ and the corresponding values of $\mu$, we
refer the reader to Appendix D.

Input: $\mu$-self-concordant barrier function $\mathcal{R}$ on $\Theta$, and
$q_{T}=M+2\sigma\sqrt{\log(T+1)}$

Initialization:
$\boldsymbol{x}_{0}=\operatorname*{arg\,min}_{\boldsymbol{x}\in\text{int}(\Theta)}\mathcal{R}(\boldsymbol{x})$

for  _ $t=1,\ldots,T$_ do

$\eta_{t}=(4dq_{T})^{-1}\min\left(1,\sqrt{\frac{16(\mu+\beta/\alpha)\log(t+1)}{t}}\right)$

// Update the step size

$P_{t}=\left(\nabla^{2}\mathcal{R}(\boldsymbol{x}_{t-1})+\eta_{t}\alpha
t\mathbf{I}_{d}\right)^{-\frac{1}{2}}$

// Update the perturbation parameter

Generate $\boldsymbol{\zeta}_{t}$ from $\partial B^{d}$

// Randomization

$\boldsymbol{z}_{t}=\boldsymbol{x}_{t-1}+P_{t}\boldsymbol{\zeta}_{t}$

// Output

$y_{t}=f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})+\xi_{t}\quad$

// Query

$\boldsymbol{g}_{t}=dy_{t}P_{t}^{-1}\boldsymbol{\zeta}_{t}$

// Estimate the gradient

$\boldsymbol{x}_{t}=\operatorname*{arg\,min}_{\boldsymbol{x}\in\Theta}\sum_{k=1}^{t}\eta_{k}\left(\langle\boldsymbol{g}_{k},\boldsymbol{x}\rangle+\frac{\alpha}{2}\left\lVert\boldsymbol{x}-\boldsymbol{x}_{k-1}\right\rVert^{2}\right)+\mathcal{R}(\boldsymbol{x})$

// Iterate

end for

Algorithm 2

The discrepancy between Algorithm 2 and the BCO algorithm of [20] is in the
assigned step size. In [20] the step size is constant while it varies with $t$
in Algorithm 2. Next, in Algorithm 2, the step size is downscaled by
$q_{T}=M+2\sigma\sqrt{\log(T+1)}$ whereas in [20] it is downscaled by $M$
without any additional logarithmic term. This difference is due to the fact
that the observations in (3) are noisy whereas in [20] they are assumed to be
noise-free. In our analysis, we rely on the fact that $\eta_{t}\left\lVert
P_{t}\boldsymbol{g}_{t}\right\rVert$ is uniformly bounded with high
probability. To ensure this, it is enough to scale down the step size by
adding the above logarithmic term to $M$. Indeed, due to Assumption 3, we have
that $\max_{t\in[T]}|y_{t}|\leq q_{T}$ with a suitably high probability.

Algorithm 2 algorithm selects
$\boldsymbol{z}_{t}\in\\{\boldsymbol{x}_{t-1}+P_{t}\boldsymbol{\zeta}|\boldsymbol{\zeta}\in\partial
B^{d}\\}\subseteq
D\triangleq\\{\boldsymbol{z}|(\boldsymbol{z}-\boldsymbol{x}_{t-1})^{\top}\nabla^{2}\mathcal{R}(\boldsymbol{x}_{t-1})(\boldsymbol{z}-\boldsymbol{x}_{t-1})\leq
1\\}$, in which $D$ is the Dikin ellipsoid. Consequently, $D\subseteq\Theta$;
see [35, Proposition 14.2.2] for a proof. Therefore,
$\boldsymbol{z}_{t}\in\Theta$ for all $t\in[T]$.

######  Theorem 2.

Let Assumptions 2 and 3 hold. Then, the static regret of Algorithm 2 satisfies

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}\sum_{t=1}^{T}f(\boldsymbol{z},\boldsymbol{c}_{t})\right]\leq
F(T),$ (11)

where $F(\cdot)$ is a concave function defined for $x\geq 0$ by

$\displaystyle F(x)$
$\displaystyle=\frac{d}{4}\big{(}M+2\sigma\sqrt{\log(x+1)}\big{)}\Bigg{(}11\sqrt{\nu
x\log(x+1)}+\nu\left(\log(x+1)+2\log(\nu+1)\right)\Bigg{)}+6M$

with $\nu=16(\mu+\beta/\alpha)$. Moreover, for $T\geq\nu^{2}/16$, we have

$\displaystyle F(T)\leq
18d\left(M+2\sigma\sqrt{\log(T+1)}\right)\sqrt{\big{(}\mu+\frac{\beta}{\alpha}\big{)}\,T\log(T+1)}.$
(12)

For the case of noise-free observations in (3) we have $\sigma=0$, and (12)
has the same order as the bound on the regret provided in [20]. Note that for
$\sigma=0$, unlike [20], our Algorithm 2 is anytime and does not require any
knowledge of $T$. We also note that, for the case of bounded noise
($|\xi_{t}|\leq\sigma$), $q_{T}$ can be set as $q_{T}=M+\sigma$ and a refined
regret in (12) can be derived, where the multiplicative term
$M+2\sigma\sqrt{\log(T+1)}$ is replaced by $M+\sigma$.

It is a known fact (see Appendix D) that, for any convex body $\Theta$, one
can construct a $\mu$-self-concordant barrier such that for $\rho\in[0,1]$,
$\mu\leq\texttt{A}d^{\rho}$, where $\texttt{A}>0$ is a constant depending only
on $\Theta$ and independent of $d$. This fact and Theorem 2 imply that
$\Pi\left(\mathcal{F}_{\alpha,\beta}(M),1+\rho/2,1/2,1,16(\mu+\beta/\alpha)^{2}\right)$
is non-empty. In [41, 4, 3], the authors established a lower bound of the
order of $d/\sqrt{T}$ for the optimization error when the noise is Gaussian
[41] or satisfies more general assumptions [4, 3]. By convexity, this lower
bound, when multiplied by $T$, provides a lower bound for the static regret in
the case $L=0$, that is,
$f(\boldsymbol{x},\boldsymbol{c}_{1})=f(\boldsymbol{x},\boldsymbol{c}_{t})$
for all $\boldsymbol{x}\in\mathbb{R}^{d}$ and $t\in[T]$. Thus, the lower bound
in [41, 4, 3] results in a valid lower bound of the order of $d\sqrt{T}$ for
the static regret in the noisy setting. Therefore, if $\rho=0$, which is the
case when $\Theta$ is a Euclidean ball, (12) is optimal up to a logarithmic
factor. In the worst case scenario ($\rho=1$), for instance, when $\Theta$ is
the $\ell_{\infty}$-ball or the simplex (see Appendix D), akin to [20], our
algorithm exhibits an optimality gap of up to $d^{1/2}$ and logarithmic
factors.

In order to enable the static-to-dynamic regret conversion via Theorem 1, we
need Assumption 1, that is, the premise that $f$ belongs to
$\mathcal{F}_{\gamma}(L)$. Since it always holds that
$\mu\leq\texttt{A}d^{\rho}$, where $\rho\in[0,1]$ and $\texttt{A}>0$ is a
numerical constant, we obtain the following corollary of Theorems 1 and 2.

Input: Parameter $K\in\mathbb{N}$ and a partition of $[0,1]^{p}$ namely
$(B_{i})_{i=1}^{K^{p}}$, $\mu$-self-concordant barrier $\mathcal{R}$

Initialization: $N_{1}(0),\dots,N_{K^{p}}(0)=0$,
$H(1),\dots,H(K^{p})=\\{0\\}$,
$\boldsymbol{x}_{0}=\operatorname*{arg\,min}_{\boldsymbol{x}\in\text{int}(\Theta)}\mathcal{R}(\boldsymbol{x})$

for  _ $t=1,\ldots,T$_ do

if  _$\boldsymbol{c}_{t}\in B_{i}$_ then

$N_{i}(t)=N_{i}(t-1)+1$

// Increment

Let $q=\max H(i)$

// The index of the last event in $B_{i}$

$\eta_{t}=(4dq_{T})^{-1}\min\left(1,\sqrt{\frac{16(\mu+\beta/\alpha)\log(N_{i}(t)+1)}{N_{i}(t)}}\right)$

// Update the step size

$P_{t}=\left(\nabla^{2}\mathcal{R}(\boldsymbol{x}_{q})+\eta_{t}\alpha
N_{i}(t)\mathbf{I}_{d}\right)^{-\frac{1}{2}}$

// Update the perturbation parameter

Generate $\boldsymbol{\zeta}_{t}$ from $\partial B^{d}$

// Randomization

$\boldsymbol{z}_{t}=\boldsymbol{x}_{q}+P_{t}\boldsymbol{\zeta}_{t}$

// Output

$y_{t}=f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})+\xi_{t}\quad$

// Query

$\boldsymbol{g}_{t}=dy_{t}P_{t}^{-1}\boldsymbol{\zeta}_{t}$

// Estimate the gradient

$\boldsymbol{x}_{t}=\operatorname*{arg\,min}_{\boldsymbol{x}\in\Theta}\sum_{k\in
H(i)}\eta_{k}\left(\langle\boldsymbol{g}_{k},\boldsymbol{x}\rangle+\frac{\alpha}{2}\left\lVert\boldsymbol{x}-\boldsymbol{x}_{k-1}\right\rVert^{2}\right)+\mathcal{R}(\boldsymbol{x})$

// Iterate

$H(i)=H(i)\cup{t}$

// Save the index of last event in $B_{i}$

end if

end for

Algorithm 3

######  Corollary 1.

Let Assumptions 1, 2, and 3 hold. Let $\rho\in[0,1]$ be such that
$\mu\leq\texttt{A}d^{\rho}$, where $\texttt{A}>0$ is a numerical constant.
Then, the dynamic regret of Algorithm 3 with $K=K(1+\rho/2,1/2,1,\gamma)$ (see
(8)), satisfies

$\displaystyle\mathbf{E}\big{[}\sum_{t=1}^{T}\big{(}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\big{)}\big{]}\leq
C\max\bigg{\\{}L_{1}d^{1+\rho}+L_{2}\sqrt{d^{2+\rho}T},\,$
$\displaystyle\qquad\qquad\qquad\qquad\qquad
L_{1}\Big{(}Lp^{\frac{\gamma}{2}}L_{2}^{-1}\Big{)}^{\frac{2p}{p+2\gamma}}d^{\frac{2\gamma(1+\rho)-p}{p+2\gamma}}T^{\frac{p}{p+2\gamma}},\,L_{2}^{\frac{2\gamma}{p+2\gamma}}\Big{(}Lp^{\frac{\gamma}{2}}\Big{)}^{\frac{p}{p+2\gamma}}d^{\frac{(2+\rho)\gamma}{p+2\gamma}}T^{\frac{p+\gamma}{p+2\gamma}}\bigg{\\}},$

where $L_{1}=\sqrt{\log(T+1)}\log(Td+1)$, $L_{2}=\log(T+1)$, and $C>0$ is a
constant depending only on $M,\sigma,\beta/\alpha$.

The main term in the bound of Corollary 1 scales as
$T^{\frac{p+\gamma}{p+2\gamma}}$. In [33], this rate was obtained for a
different algorithm, under the additional assumption that for each
$\boldsymbol{c}\in[0,1]^{p}$ the global minimizer
$\operatorname*{arg\,min}_{\boldsymbol{x}\in\mathbb{R}^{d}}f(\boldsymbol{x},\boldsymbol{c})$
is an interior point of the constraint set $\Theta$. Note also that the
multiplicative factors in Corollary 1 exhibit a very mild dependence on both
dimensions $p$ and $d$, never exceeding $p^{1/2}d$ in the main term.

##  5 Lower bound

In this section, along with the classes $\mathcal{F}_{\gamma}(L)$,
$\gamma\in(0,1]$, we will consider the class $\mathcal{F}_{0}(L)$, which
includes discontinuous functions.

######  Definition 5.

For $L>0$, let $\mathcal{F}_{0}(L)$ be the class of functions such that
$f\in\mathcal{F}_{0}(L)$ if

$\displaystyle|f(\boldsymbol{x},\boldsymbol{c})-f(\boldsymbol{x},\boldsymbol{c}^{\prime})|\leq
L,\quad\text{for
all}\quad\boldsymbol{x}\in\Theta,\,\,\boldsymbol{c},\boldsymbol{c}^{\prime}\in[0,1]^{p}.$
(13)

We will assume that the noises $\\{\xi_{t}\\}_{t=1}^{T}$ are independent with
cumulative distribution function $F$ satisfying the condition

$\displaystyle\int\log\left(\,\mathrm{d}F\left(u\right)/dF\left(u+v\right)\right)\,\mathrm{d}F(u)\leq
I_{0}v^{2},\quad\quad|v|<v_{0},$ (14)

for some $0<I_{0}<\infty,0<v_{0}\leq\infty.$ It can be shown that condition
(14) is satisfied for $F$ with a sufficiently smooth density and finite Fisher
information. If $F$ follows a Gaussian distribution, (14) holds with
$v_{0}=\infty$. Note that Gaussian noise satisfies Assumption 3 used to prove
the upper bound.

Next, we introduce the distribution of the contexts used in deriving the lower
bound. Similar to previous sections, for any $K\in\mathbb{N}$, consider the
partition of $[0,1]^{p}$, denoted by $\\{B_{i}\\}_{i=1}^{K^{p}}$, for which we
assume that $B_{i}$’s have equal volumes. Moreover, for $i\in[K^{p}]$, let
$\mathbf{P}_{i}$ denote the uniform distribution on
$G_{i}=(1/2)(B_{i}+\boldsymbol{b}_{i})$, where $\boldsymbol{b}_{i}$ is the
barycenter of $B_{i}$. Then, we assume that
$\\{\boldsymbol{c}_{t}\\}_{t=1}^{T}$ are independently distributed according
to $\mathbb{P}_{K}$, where

$\displaystyle\mathbb{P}_{K}(\Upsilon)=K^{-p}\sum_{i=1}^{K^{p}}\mathbf{P}_{i}(\Upsilon\cap
G_{i}),$ (15)

for $\Upsilon\subseteq[0,1]^{p}$. Distribution $\mathbb{P}_{K}$ represents a
challenging scenario for the learning process. Indeed, the contexts are
uniformly spread, preventing concentration in any specific region of
$[0,1]^{p}$. Moreover, they are not clustered near the boundaries of each
cell, thus preventing the learner from exploiting proximity between the cells.
See Appendix C for further details.

######  Theorem 3.

For
$(\alpha,\beta,M,\gamma,L)\in(0,\infty)\times[3\alpha,\infty)\times[\alpha+1,\infty)\times[0,1]\times[0,\infty)$
consider the class of functions
$\bar{\mathcal{F}}=\mathcal{F}_{\alpha,\beta}(M)\cap\mathcal{F}_{\gamma}(L)$.
Let $\Theta=B^{d}$, and let $\\{\boldsymbol{c}_{t}\\}_{t=1}^{T}$ be
independently distributed according to $\mathbb{P}_{K}$, where
$K=\max\left(1,\left\lfloor\left(\min\left(1,L^{2}\right)T\right)^{\frac{1}{p+2\gamma}}\right\rfloor\right)$.
Let $\pi\in\Pi$ be any randomized procedure and assume that
$\\{\boldsymbol{z}_{t}\\}_{t=1}^{T}$ are outputs of $\pi$. Then,

$\displaystyle\sup_{f\in\bar{\mathcal{F}}}\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\right]\geq\texttt{A}\left(\min\left(1,L^{\frac{2(p+\gamma)}{p+2\gamma}}\right)T^{\frac{p+\gamma}{p+2\gamma}}+\min\left(T,d\sqrt{T}\right)\right),$
(16)

where $\texttt{A}>0$ is a constant that does not depend on $d$, $p$, and $T$.

Applying (16) with $L>0$ and $\gamma=0$ shows that no randomized procedure can
achieve sub-linear dynamic regret on the corresponding class
$\bar{\mathcal{F}}$. Thus, controlling the increments of $f$ with any $L>0$,
in the absence of continuity with respect to $\boldsymbol{c}$, is not
sufficient to get a sub-linear dynamic regret.

For $\gamma\in(0,1]$, the bound (16) combined with Corollary 1 implies that
Algorithm 3 with $K$ chosen as in Corollary 1 achieves the optimal rate of
regret in $T$ up to logarithmic factors. An additional (mild) gap between the
upper and lower bounds is due to the discrepancy in the factors depending on
$d,p,$ and $L$.

If $L=0$ the bound in (16) scales as $\min(T,d\sqrt{T})$. In this case, the
objective functions are constant with respect to the context variable,
$f(\boldsymbol{x},\boldsymbol{c}_{1})=f(\boldsymbol{x},\boldsymbol{c}_{t})$,
for $\boldsymbol{x}\in\mathbb{R}^{d}$ and $t\in[T]$, so that the dynamic
regret in (16) is equal to the static regret. Moreover, by convexity, both
regrets are bounded from below by the optimization error corresponding to
$f(\cdot,\boldsymbol{c}_{1})$ multiplied by $T$. Using this remark we notice
that, for $L=0$, the bound (16) agrees with the lower bound on the
optimization error for strongly convex and smooth functions, known to be of
the order $d/\sqrt{T}$ [41, 4, 3].

Theorem 3 can be stated in a more general manner. In the definition of $\Pi$,
the randomized procedures are restricted to query only within the constraint
set $\Theta$. However, in the proof of the lower bound, we did not impose such
a restriction, allowing $\pi$ to query anywhere within $\mathbb{R}^{d}$. Thus,
Theorem 3 remains valid for this broader set of algorithms. Furthermore, the
proof of Theorem 3 can be extended to hold for any convex body $\Theta$ and
not only for $\Theta=B^{d}$. Indeed, by shifting and scaling the unit
Euclidean ball, we can embed it in $\Theta$. Subsequently, we can apply the
same shifting and scaling to the action argument of the set of functions
$f_{\boldsymbol{\omega},\boldsymbol{\tau}}$ in the proof of Theorem 3.

## References

  * [1] Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin.  Competing in the dark: An efficient algorithm for bandit linear optimization.  In COLT, pages 263–274. Citeseer, 2008.
  * [2] Alekh Agarwal, Dean P Foster, Daniel Hsu, Sham M Kakade, and Alexander Rakhlin.  Stochastic convex optimization with bandit feedback.  SIAM Journal on Optimization, 23(1):213–240, 2013.
  * [3] Arya Akhavan, Evgenii Chzhen, Massimiliano Pontil, and Alexandre B Tsybakov.  Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm.  arXiv preprint arXiv:2306.02159, 2023.
  * [4] Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov.  Exploiting higher order smoothness in derivative-free optimization and continuous bandits.  Advances in Neural Information Processing Systems, 33:9017–9027, 2020.
  * [5] Peter Auer.  Using confidence bounds for exploitation-exploration trade-offs.  Journal of Machine Learning Research, 3(Nov):397–422, 2002.
  * [6] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47:235–256, 2002.
  * [7] Hamsa Bastani and Mohsen Bayati.  Online decision making with high-dimensional covariates.  Operations Research, 68(1):276–294, 2020.
  * [8] Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin.  Escaping the local minima via simulated annealing: Optimization of approximately convex functions.  In Conference on Learning Theory, pages 240–265. PMLR, 2015.
  * [9] Omar Besbes, Yonatan Gur, and Assaf Zeevi.  Non-stationary stochastic optimization.  Operations Research, 63(5):1227–1244, 2015.
  * [10] Sébastien Bubeck, Michael B Cohen, Yin Tat Lee, and Yuanzhi Li.  An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1130–1137, 2018.
  * [11] Sébastien Bubeck and Ronen Eldan.  The entropic barrier: a simple and optimal universal self-concordant barrier.  arXiv preprint arXiv:1412.1587, 2014.
  * [12] Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan.  Kernel-based methods for bandit convex optimization.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 72–85, 2017.
  * [13] Sébastien Bubeck, Gilles Stoltz, Csaba Szepesvári, and Rémi Munos.  Online optimization in x-armed bandits.  Advances in Neural Information Processing Systems, 21, 2008.
  * [14] Ningyuan Chen and Guillermo Gallego.  Nonparametric learning and optimization with covariates.  arXiv preprint arXiv:1805.01136, 2018.
  * [15] Tianyi Chen and Georgios B Giannakis.  Bandit convex optimization for scalable and dynamic IoT management.  IEEE Internet of Things Journal, 6(1):1276–1286, 2018.
  * [16] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan.  Online convex optimization in the bandit setting: gradient descent without a gradient.  arXiv preprint cs/0408007, 2004.
  * [17] Daniel JF Fox.  A Schwarz lemma for Kähler affine metrics and the canonical potential of a proper convex cone.  Annali di Matematica Pura ed Applicata, 194(1):1–42, 2015.
  * [18] Alexander Goldenshluger and Assaf Zeevi.  Woodroofe’s one-armed bandit problem revisited.  The Annals of Applied Probability, 19(4):1603–1633, 2009.
  * [19] Eric C Hall and Rebecca M Willett.  Online convex optimization in dynamic environments.  IEEE Journal of Selected Topics in Signal Processing, 9(4):647–662, 2015.
  * [20] Elad Hazan and Kfir Levy.  Bandit convex optimization: Towards tight bounds.  Advances in Neural Information Processing Systems, 27, 2014.
  * [21] Elad Hazan and Yuanzhi Li.  An optimal algorithm for bandit convex optimization.  arXiv preprint arXiv:1603.04350, 2016.
  * [22] Roland Hildebrand.  Canonical barriers on convex cones.  Mathematics of operations research, 39(3):841–850, 2014.
  * [23] Shinji Ito.  An optimal algorithm for bandit convex optimization with strongly-convex and smooth loss.  In International Conference on Artificial Intelligence and Statistics, pages 2229–2239. PMLR, 2020.
  * [24] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan.  Online optimization: Competing with dynamic comparators.  In Artificial Intelligence and Statistics, pages 398–406. PMLR, 2015.
  * [25] Sham M Kakade, Shai Shalev-Shwartz, and Ambuj Tewari.  Efficient bandit algorithms for online multiclass prediction.  In Proceedings of the 25th international conference on Machine learning, pages 440–447, 2008.
  * [26] Robert Kleinberg.  Nearly tight bounds for the continuum-armed bandit problem.  Advances in Neural Information Processing Systems, 17, 2004.
  * [27] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal.  Multi-armed bandits in metric spaces.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681–690, 2008.
  * [28] John Langford and Tong Zhang.  The epoch-greedy algorithm for multi-armed bandits with side information.  Advances in neural information processing systems, 20, 2007.
  * [29] Tor Lattimore.  Improved regret for zeroth-order adversarial bandit convex optimisation.  Mathematical Statistics and Learning, 2(3):311–334, 2020.
  * [30] Tor Lattimore.  Bandit convex optimisation.  arXiv preprint arXiv:2402.06535, 2024.
  * [31] Tor Lattimore and Andràs György.  Improved regret for zeroth-order stochastic convex bandits.  In Conference on Learning Theory, pages 2938–2964. PMLR, 2021.
  * [32] Tor Lattimore and Csaba Szepesvári.  Bandit algorithms.  Cambridge University Press, 2020.
  * [33] Wenhao Li, Ningyuan Chen, and L Jeff Hong.  A dimension-free algorithm for contextual continuum-armed bandits.  arXiv preprint arXiv:1907.06550, 2019.
  * [34] Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro.  Online optimization in dynamic environments: Improved regret rates for strongly convex problems.  In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7195–7201. IEEE, 2016.
  * [35] Arkadi Nemirovski.  Interior point polynomial time methods in convex programming.  Lecture notes, 42(16):3215–3224, 2004.
  * [36] Yurii Nesterov and Arkadii Nemirovskii.  Interior-point polynomial algorithms in convex programming.  SIAM, 1994.
  * [37] Francesco Orabona.  A modern introduction to online learning.  arXiv preprint arXiv:1912.13213, 2019.
  * [38] Sandeep Pandey, Deepak Agarwal, Deepayan Chakrabarti, and Vanja Josifovski.  Bandits for taxonomies: A model-based approach.  In Proceedings of the 2007 SIAM international conference on data mining, pages 216–227. SIAM, 2007.
  * [39] Vianney Perchet and Philippe Rigollet.  The multi-armed bandit problem with covariates.  The Annals of Statistics, 41(2):693–721, 2013.
  * [40] Philippe Rigollet and Assaf Zeevi.  Nonparametric bandits with covariates.  arXiv preprint arXiv:1003.1630, 2010.
  * [41] Ohad Shamir.  On the complexity of bandit and derivative-free stochastic convex optimization.  In Conference on Learning Theory, pages 3–24. PMLR, 2013.
  * [42] Aleksandrs Slivkins.  Contextual bandits with similarity information.  In Proceedings of the 24th annual Conference On Learning Theory, pages 679–702. JMLR Workshop and Conference Proceedings, 2011.
  * [43] Alexandre B. Tsybakov.  Introduction to nonparametric estimation.  Springer Series in Statistics. Springer, New York, 2009.
  * [44] Yuanyu Wan, Lijun Zhang, and Mingli Song.  Improved dynamic regret for online Frank-Wolfe.  In The Thirty Sixth Annual Conference on Learning Theory, pages 3304–3327. PMLR, 2023.
  * [45] Chih-Chun Wang, Sanjeev R Kulkarni, and H Vincent Poor.  Bandit problems with side observations.  IEEE Transactions on Automatic Control, 50(3):338–355, 2005.
  * [46] Michael Woodroofe.  A one-armed bandit problem with a concomitant variable.  Journal of the American Statistical Association, 74(368):799–806, 1979.
  * [47] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi.  Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient.  In International Conference on Machine Learning, pages 449–457. PMLR, 2016.
  * [48] Yuhong Yang and Dan Zhu.  Randomized allocation with nonparametric estimation for a multi-armed bandit problem with covariates.  The Annals of Statistics, 30(1):100–121, 2002.
  * [49] Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou.  Improved dynamic regret for non-degenerate functions.  Advances in Neural Information Processing Systems, 30, 2017.
  * [50] Lijun Zhang, Tianbao Yang, Zhi-Hua Zhou, et al.  Dynamic regret of strongly adaptive methods.  In International conference on machine learning, pages 5882–5891. PMLR, 2018.
  * [51] Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou.  Bandit convex optimization in non-stationary environments.  Journal of Machine Learning Research, 22(125):1–45, 2021.
  * [52] Peng Zhao and Lijun Zhang.  Improved analysis for dynamic regret of strongly convex and smooth functions.  In Learning for Dynamics and Control, pages 48–59. PMLR, 2021.
  * [53] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou.  Dynamic regret of convex and smooth functions.  Advances in Neural Information Processing Systems, 33:12510–12520, 2020.
  * [54] Martin Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In Proceedings of the 20th International Conference on Machine Learning, pages 928–936, 2003.

## Supplementary material

In Appendix A, we present the proof of Theorem 1. Appendices B and C begin
with a set of auxiliary and preliminary lemmas, followed by the proofs of the
main results: Theorem 2, Corollary 1, and Theorem 3. In Appendix D, we collect
some properties of self-concordant barrier functions.

##  Appendix A Proof of Theorem 1

###### Proof of Theorem 1.

For $i\in[K^{p}]$, let $N_{i}(T)$ the number of $\boldsymbol{c}_{t}$’s
belonging to $B_{i}$. Denote $i_{1},\dots,i_{N_{i}(T)}$ as the set of all
indices such that $\boldsymbol{c}_{i_{j}}\in B_{i}$ for all $j\in[N_{i}(T)]$.
We have

$\displaystyle\sum_{t=1}^{T}\left(f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\right)=\sum_{i=1}^{K^{p}}\sum_{j=1}^{N_{i}(T)}\left(f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{i_{j}})\right).$

For $i\in[K^{p}]$, let $\boldsymbol{b}_{i}\in B_{i}$ the barycenter of the
cube $B_{i}$ and
$\boldsymbol{x}^{*}_{i}\in\operatorname*{arg\,min}_{\boldsymbol{x}\in\Theta}f(\boldsymbol{x},\boldsymbol{b}_{i})$.
Since (6) holds it follows that

$\displaystyle\mathbf{E}\left[\sum_{j=1}^{N_{i}(T)}\left(f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}_{i}^{*},\boldsymbol{c}_{i_{j}})\right)|N_{i}(T)\right]\leq
F(N_{i}(T)),$

where $F$ is a concave function. Note that
$\mathbf{E}\left[N_{i}(T)\right]=p_{i}T$, for some $p_{i}\in[0,1]$, such that
$\sum_{i=1}^{K^{p}}p_{i}=1$. By taking expectations from both sides and
applying Jensen’s inequality we get

$\displaystyle\mathbf{E}\left[\sum_{j=1}^{N_{i}(T)}\left(f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})\right)\right]$
$\displaystyle\leq F(p_{i}T).$

Summing both sides over $i\in[K^{p}]$ and using Jensen’s inequality again we
obtain

$\displaystyle\mathbf{E}\left[\sum_{i=1}^{K^{p}}\sum_{j=1}^{N_{i}(T)}\left(f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})\right)\right]\leq\sum_{i=1}^{K^{p}}F(p_{i}T)\leq
K^{p}F\left(\sum_{i=1}^{K^{p}}\frac{p_{i}T}{K^{p}}\right)=K^{p}F\left(\frac{T}{K^{p}}\right).$
(17)

If, in addition,
$\pi\in\Pi(\mathcal{F},\tau_{1},\tau_{2},\tau_{3},\mathrm{T}_{0})$, then for
$T\geq K^{p}\,\mathrm{T}_{0}$ we get that

$\displaystyle\mathbf{E}\left[\sum_{i=1}^{K^{p}}\sum_{j=1}^{N_{i}(T)}\left(f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})\right)\right]\leq
Cd^{\tau_{1}}T^{\tau_{2}}\log^{\tau_{3}}(T+1)K^{p(1-\tau_{2})}.$ (18)

Let
$\boldsymbol{z}^{*}_{i_{j}}\in\operatorname*{arg\,min}_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{i_{j}})$.
We can write

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\left(f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\right)\right]$
$\displaystyle=\mathbf{E}\left[\sum_{i=1}^{K^{p}}\sum_{j=1}^{N_{i}(T)}\left(f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})+f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{z}^{*}_{i_{j}},\boldsymbol{c}_{i_{j}})\right)\right]$
$\displaystyle=\mathbf{E}\bigg{[}\sum_{i=1}^{K^{p}}\sum_{j=1}^{N_{i}(T)}\bigg{(}f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})+f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}_{i}^{*},\boldsymbol{b}_{i})$
$\displaystyle\quad+f(\boldsymbol{x}_{i}^{*},\boldsymbol{b}_{i})-f(\boldsymbol{z}^{*}_{i_{j}},\boldsymbol{c}_{i_{j}})\bigg{)}\bigg{]}.$

Since $f(\boldsymbol{x}_{i}^{*},\boldsymbol{b}_{i})\leq
f(\boldsymbol{z}_{i_{j}}^{*},\boldsymbol{b}_{i})$, we have

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\left(f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\right)\right]$
$\displaystyle\leq\mathbf{E}\bigg{[}\sum_{i=1}^{K^{p}}\sum_{j=1}^{N_{i}(T)}\bigg{(}f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})+f(\boldsymbol{x}_{i}^{*},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}_{i}^{*},\boldsymbol{b}_{i})$
$\displaystyle\quad+f(\boldsymbol{z}^{*}_{i_{j}},\boldsymbol{b}_{i})-f(\boldsymbol{z}^{*}_{i_{j}},\boldsymbol{c}_{i_{j}})\bigg{)}\bigg{]}$
$\displaystyle\leq\mathbf{E}\left[\sum_{i=1}^{K^{p}}\sum_{j=1}^{N_{i}(T)}\left(f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})+2L\left\lVert\boldsymbol{c}_{i_{j}}-\boldsymbol{b}_{i}\right\rVert^{\gamma}\right)\right],$

where the last inequality is due to Assumption 1. Let
$\delta=\max_{i\in[K^{p}]}\max_{\boldsymbol{x},\boldsymbol{y}\in
B_{i}}\left\lVert\boldsymbol{x}-\boldsymbol{y}\right\rVert$. Since all
$B_{i}$’s are hypercubes with edges of length $1/K$ we have
$\delta=\sqrt{p}/K$, so that

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\left(f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\right)\right]$
$\displaystyle\leq\mathbf{E}\left[\sum_{i=1}^{K^{p}}\sum_{j=1}^{N_{i}(T)}\left(f(\boldsymbol{z}_{i_{j}},\boldsymbol{c}_{i_{j}})-f(\boldsymbol{x}^{*}_{i},\boldsymbol{c}_{i_{j}})\right)\right]+2TL\left(\frac{\sqrt{p}}{K}\right)^{\gamma}.$
(19)

Combining (17) and (19), gives

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\left(f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\right)\right]$
$\displaystyle\leq
K^{p}F\left(\frac{T}{K^{p}}\right)+2TL\left(\frac{\sqrt{p}}{K}\right)^{\gamma},$

which concludes the proof of (9). In order to prove the bound (1), we note
that, by (18) and (19),

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\left(f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\right)\right]$
$\displaystyle\leq
Cd^{\tau_{1}}T^{\tau_{2}}\log^{\tau_{3}}(T+1)K^{p(1-\tau_{2})}+2TL\left(\frac{\sqrt{p}}{K}\right)^{\gamma}.$

The two terms on the right hand side are of the same order of magnitude if
$K=K(\tau_{1},\tau_{2},\tau_{3},\gamma)$. Under this choice of $K$ we get

$\displaystyle\mathbf{E}\bigg{[}\sum_{t=1}^{T}\bigg{(}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}$
$\displaystyle f(\boldsymbol{z},\boldsymbol{c}_{t})\bigg{)}\bigg{]}\leq
C^{\prime}\max\bigg{(}d^{\tau_{1}}T^{\tau_{2}}\log^{\tau_{3}}(T+1),$
$\displaystyle\left(Lp^{\frac{\gamma}{2}}\right)^{\frac{p(1-\tau_{2})}{p(1-\tau_{2})+\gamma}}\left(d^{\tau_{1}}\log^{\tau_{3}}(T+1)\right)^{\frac{\gamma}{p(1-\tau_{2})+\gamma}}T^{\frac{(p-\gamma)(1-\tau_{2})+\gamma}{p(1-\tau_{2})+\gamma}}\bigg{)},$

where $C^{\prime}>0$ is a constant that does not depend on $T,p$ and $d$. ∎

##  Appendix B Proof of Theorem 2 and Corollary 1

######  Lemma 1.

Let $\\{\eta_{t}\\}_{t=1}^{T}$ be as in Algorithm 2. Then, for all $t\geq 2$
we have

$\displaystyle 1-\frac{\eta_{t}}{\eta_{t-1}}\leq\mathbf{1}\left(t\geq
16\mu\right)\sqrt{\frac{1}{t}}.$ (20)

###### Proof.

Note that $t/\log(t+1)$ is an increasing function for all $t\geq 1$. Let
$t_{0}$ be the smallest positive integer such that $t_{0}/\log(t_{0}+1)\geq
16(\mu+\beta/\alpha)$, and note that

$\displaystyle\eta_{t}=(4dq_{T})^{-1},\quad\text{for }t<t_{0},$

and

$\displaystyle\eta_{t}=(4dq_{T})^{-1}\left(\frac{16(\mu+\beta/\alpha)\log(t+1)}{t}\right)^{\frac{1}{2}},\quad\text{for
}t\geq t_{0},$

where $q_{T}=M+2\sigma\sqrt{\log(T+1)}$. If $t<t_{0}$ then
$1-\eta_{t}/\eta_{t-1}=0$. For the case $t=t_{0}$, we can write

$\displaystyle
1-\frac{\eta_{t}}{\eta_{t-1}}=\frac{\sqrt{t_{0}}-\sqrt{16(\mu+\beta/\alpha)\log(t_{0}+1)}}{\sqrt{t_{0}}}.$

Note that $t_{0}\leq 16\left(\mu+\beta/\alpha\right)\log(t_{0}+1)+1$. Thus,

$\displaystyle
1-\frac{\eta_{t}}{\eta_{t-1}}\leq\frac{\sqrt{t_{0}}-\sqrt{t_{0}-1}}{\sqrt{t_{0}}}\leq\sqrt{\frac{1}{t_{0}}}=\sqrt{\frac{1}{t}}.$

For $t>t_{0}$ we have

$\displaystyle
1-\frac{\eta_{t}}{\eta_{t-1}}=1-\sqrt{\frac{t-1}{t}}\sqrt{\frac{\log(t+1)}{\log(t)}}\leq\frac{\sqrt{t}-\sqrt{t-1}}{\sqrt{t}}\leq\sqrt{\frac{1}{t}}.$

By combing the above inequalities we get

$\displaystyle 1-\frac{\eta_{t}}{\eta_{t-1}}\leq\mathbf{1}\left(t\geq
t_{0}\right)\sqrt{\frac{1}{t}}.$

Since $16(\mu+\beta/\alpha)\geq 16$, we have $t_{0}\geq 2$, and consequently
$\log(t_{0}+1)\geq 1$. Thus,

$\displaystyle t_{0}\geq 16(\mu+\frac{\beta}{\alpha})\log(t_{0}+1)\geq 16\mu.$

Therefore, for all $t\in[T]$ we have

$\displaystyle\mathbf{1}\left(t\geq t_{0}\right)\leq\mathbf{1}\left(t\geq
16\mu\right),$

which concludes the proof. ∎

Before proceeding with the proofs, let us recall the concept of the Newton
decrement of a self-concordant function. Let
$\Psi:\text{int}(\Theta)\to\mathbb{R}$ be a self-concordant function. The
Newton decrement of $\Psi$ at $\boldsymbol{x}\in\text{int}(\Theta)$ is defined
as

$\displaystyle\lambda(\Psi,\boldsymbol{x})=\max_{\boldsymbol{h}\in\mathbb{R}^{d}}\\{\nabla\Psi(\boldsymbol{x})[\boldsymbol{h}]|\nabla^{2}\Psi(\boldsymbol{x})[\boldsymbol{h},\boldsymbol{h}]\leq
1\\}.$ (21)

In the case that $\nabla^{2}\Psi(\boldsymbol{x})$ is positive definite, for
all $\boldsymbol{x}\in\text{int}(\Theta)$ (21) can be written as

$\displaystyle\lambda(\Psi,\boldsymbol{x})=\sqrt{(\nabla\Psi(\boldsymbol{x}))^{\top}(\nabla^{2}\Psi(\boldsymbol{x}))^{-1}\nabla\Psi(\boldsymbol{x})}.$
(22)

The proof of the equivalency of (21) and (22) can be found in [35, Chapter 2,
Section IVa]. Moreover, if $\Psi$ is a $\mu$-self-concordant barrier then
$\lambda(\Psi,\boldsymbol{x})\leq\mu^{1/2}$ for all
$\boldsymbol{x}\in\text{int}(\Theta)$.

The next lemma plays a key role in our analysis.

######  Lemma 2.

Let $\Psi:\text{int}(\Theta)\to\mathbb{R}$ be a self-concordant function. Then
$\Psi$ attains its minimum on $\text{int}(\Theta)$ if and only if there exists
$\boldsymbol{x}\in\text{int}(\Theta)$ with $\lambda(\Psi,\boldsymbol{x})<1$.
Moreover, if $\lambda(\Psi,\boldsymbol{x})<1$, then

$\displaystyle((\boldsymbol{x}-\boldsymbol{x}^{*})^{\top}\nabla^{2}\Psi(\boldsymbol{x})(\boldsymbol{x}-\boldsymbol{x}^{*}))^{\frac{1}{2}}\leq\frac{\lambda(\Psi,\boldsymbol{x})}{1-\lambda(\Psi,\boldsymbol{x})},$

where
$\boldsymbol{x}^{*}=\operatorname*{arg\,min}_{\boldsymbol{x}\in\text{int}(\Theta)}\Psi(\boldsymbol{x})$.

For a proof of Lemma 2, we refer the reader to [35, Chapter 2, Section VIII].

######  Lemma 3.

Define the event

$\Lambda_{T}=\\{|\xi_{t}|\leq 2\sigma\sqrt{\log(T+1)}\,\text{ for all
}t\in[T]\\}.$

Let $\\{\boldsymbol{x}_{t}\\}_{t=0}^{T}$ be the iterates defined in Algorithm
2. If $\Lambda_{T}$ holds, for all $t\in[T]$ we have

$\displaystyle\left\lVert\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\right\rVert_{t}\leq
2\left(\eta_{t}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}+\sqrt{\frac{\mu}{t}}\right),$
(23)

where we use the notation
$\left\lVert\boldsymbol{u}\right\rVert_{t}:=\sqrt{\boldsymbol{u}^{\top}P_{t}^{-2}\boldsymbol{u}}$
and
$\left\lVert\boldsymbol{u}\right\rVert_{t}^{*}:=\sqrt{\boldsymbol{u}^{\top}P_{t}^{2}\boldsymbol{u}}$
for all $\boldsymbol{u}\in\mathbb{R}^{d}$.

###### Proof.

Let $\tilde{\Phi}_{t}:\text{int}(\Theta)\to\mathbb{R}$ be such that

$\displaystyle\tilde{\Phi}_{t}(\boldsymbol{u})=\eta_{t}\left(\sum_{k=1}^{t}\langle\boldsymbol{g}_{k},\boldsymbol{u}\rangle+\frac{\alpha}{2}\sum_{k=1}^{t}\left\lVert\boldsymbol{u}-\boldsymbol{x}_{k-1}\right\rVert^{2}\right)+\mathcal{R}(\boldsymbol{u}).$

Note that $\tilde{\Phi}_{t}$ is a self-concordant function with
$\boldsymbol{x}_{t}\in\operatorname*{arg\,min}_{\boldsymbol{x}\in\text{int}(\Theta)}\tilde{\Phi}_{t}(\boldsymbol{x})$,
and $\nabla^{2}\tilde{\Phi}_{t}(\boldsymbol{x}_{t-1})=P_{t}^{-2}$. Consider
the Newton decrement $\lambda(\tilde{\Phi}_{t},\boldsymbol{x}_{t-1})$, cf.
(22). The first part of the proof is dedicated to providing an upper bound for
$\lambda(\tilde{\Phi}_{t},\boldsymbol{x}_{t-1})$. Then we use Lemma 2 to prove
(23). For $t\in[T]$ we have

$\displaystyle\lambda(\tilde{\Phi}_{t},\boldsymbol{x}_{t-1})=\sqrt{(\nabla\tilde{\Phi}_{t}(\boldsymbol{x}_{t-1}))^{\top}(\nabla^{2}\tilde{\Phi}_{t}(\boldsymbol{x}_{t-1}))^{-1}\nabla\tilde{\Phi}_{t}(\boldsymbol{x}_{t-1})}=\left\lVert\nabla\tilde{\Phi}_{t}(\boldsymbol{x}_{t-1})\right\rVert_{t}^{*}.$
(24)

For $t=1$, we can write

$\displaystyle\left\lVert\nabla\tilde{\Phi}_{1}(\boldsymbol{x}_{0})\right\rVert_{1}^{*}=\left\lVert\eta_{1}\langle\boldsymbol{g}_{1},\boldsymbol{x}_{0}\rangle+\nabla\mathcal{R}(\boldsymbol{x}_{0})\right\rVert\leq\eta_{1}\left\lVert\boldsymbol{g}\right\rVert_{1}^{*},$
(25)

where the last inequality follows from the facts that
$\boldsymbol{x}_{0}=\operatorname*{arg\,min}_{\boldsymbol{x}\in\text{int}(\Theta)}\mathcal{R}(\boldsymbol{x})$
and $\mathcal{R}(\boldsymbol{x}_{0})=0$.

Moreover, for $t\geq 2$ we have

$\displaystyle\nabla\tilde{\Phi}_{t}(\boldsymbol{x}_{t-1})$
$\displaystyle=\frac{\eta_{t}}{\eta_{t-1}}\left(\eta_{t-1}\sum_{k=1}^{t-1}\boldsymbol{g}_{k}+\eta_{t-1}\alpha\sum_{k=1}^{t-1}(\boldsymbol{x}-\boldsymbol{x}_{k-1})+\nabla\mathcal{R}(\boldsymbol{x}_{t-1})\right)+\eta_{t}\boldsymbol{g}_{t}$
$\displaystyle\phantom{00000}+\left(1-\frac{\eta_{t}}{\eta_{t-1}}\right)\nabla\mathcal{R}(\boldsymbol{x}_{t-1})$
$\displaystyle=\frac{\eta_{t}}{\eta_{t-1}}\nabla\tilde{\Phi}_{t-1}(\boldsymbol{x}_{t-1})+\eta_{t}\boldsymbol{g}_{t}+\left(1-\frac{\eta_{t}}{\eta_{t-1}}\right)\nabla\mathcal{R}(\boldsymbol{x}_{t-1})$
$\displaystyle=\eta_{t}\boldsymbol{g}_{t}+\left(1-\frac{\eta_{t}}{\eta_{t-1}}\right)\nabla\mathcal{R}(\boldsymbol{x}_{t-1}).$
(26)

Using (24) – (25) we find that, for all $t\in[T]$,

$\displaystyle\lambda(\tilde{\Phi}_{t},\boldsymbol{x}_{t-1})=\left\lVert\nabla\tilde{\Phi}_{t}(\boldsymbol{x}_{t-1})\right\rVert_{t}^{*}\leq\eta_{t}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}+\left(1-\frac{\eta_{t}}{\eta_{t-1}}\right)\left\lVert\nabla\mathcal{R}(\boldsymbol{x}_{t-1})\right\rVert_{t}^{*}.$

Thanks to Lemma 1 we can bound the term $1-\eta_{t}/\eta_{t-1}$ to obtain

$\displaystyle\lambda(\tilde{\Phi}_{t},\boldsymbol{x}_{t-1})\leq\eta_{t}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}+\left\lVert\nabla\mathcal{R}(\boldsymbol{x}_{t-1})\right\rVert_{t}^{*}\mathbf{1}\left(t\geq
16\mu\right)\sqrt{\frac{1}{t}}.$

On the other hand, since $\mathcal{R}$ is a $\mu$-self-concordant function we
have

$\displaystyle(\left\lVert\nabla\mathcal{R}(\boldsymbol{x}_{t-1})\right\rVert_{t}^{*})^{2}\leq\nabla\mathcal{R}(\boldsymbol{x}_{t-1})^{\top}(\nabla^{2}\mathcal{R}(\boldsymbol{x}_{t-1}))^{-1}\nabla\mathcal{R}(\boldsymbol{x}_{t-1})=\lambda^{2}(\mathcal{R},\boldsymbol{x}_{t-1})\leq\mu,$

so that

$\displaystyle\lambda(\tilde{\Phi}_{t},\boldsymbol{x}_{t-1})\leq\eta_{t}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}+\mathbf{1}\left(t\geq
16\mu\right)\sqrt{\frac{\mu}{t}}\leq\eta_{t}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}+\frac{1}{4}.$
(27)

Since we assumed that $\Lambda_{T}$ holds, we can write

$\displaystyle\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}=\left\lVert
d(f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})+\xi_{t})P_{t}^{-1}\boldsymbol{\zeta}_{t}\right\rVert_{t}^{*}\leq
d(|f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})|+|\xi_{t}|)\leq
d(M+2\sigma\sqrt{\log(T+1)}).$ (28)

By the definition of $\eta_{t}$, for all $t\in[T]$ we have that
$\eta_{t}\leq(4d(M+2\sigma\sqrt{\log(T+1)}))^{-1}$ which implies that
$\eta_{t}\left\lVert\boldsymbol{g}\right\rVert_{t}^{*}\leq 1/4$. Using this
inequality in (27) gives $\lambda(\tilde{\Phi}_{t},\boldsymbol{x}_{t-1})\leq
1/2$. Therefore, by Lemma 2 we can write

$\displaystyle\left\lVert\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\right\rVert_{t}=\left\lVert\boldsymbol{x}_{t-1}-\operatorname*{arg\,min}_{\boldsymbol{x}\in\text{int}(\Theta)}\tilde{\Phi}_{t}(\boldsymbol{x})\right\rVert_{t}\leq
2\lambda(\tilde{\Phi}_{t},\boldsymbol{x}_{t-1}).$

The last display together with (27) yields

$\displaystyle\left\lVert\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\right\rVert$
$\displaystyle\leq
2\left(\eta_{t}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}+\mathbf{1}\left(t\geq
16\mu\right)\sqrt{\frac{\mu}{t}}\right)\leq
2\left(\eta_{t}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}+\sqrt{\frac{\mu}{t}}\right).$

∎

######  Lemma 4.

Consider a function $h:\mathbb{R}^{d}\times[0,1]^{p}\to\mathbb{R}$, and set
$h_{t}(\boldsymbol{x})=h(\boldsymbol{x},\boldsymbol{c}_{t})$ for $t\geq 1$.
Assume that $\\{h_{t}\\}_{t=1}^{T}$ is a sequence of $\alpha$-strongly convex
functions for some $\alpha>0$. Let $\\{\boldsymbol{x}_{t}\\}_{t=0}^{T}$ be the
iterates defined in Algorithm 2. Let $\boldsymbol{g}_{t}$’s be random vectors
in $\mathbb{R}^{d}$ such that
$\mathbf{E}\left[\boldsymbol{g}_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t},\Lambda_{T}\right]=\nabla
h_{t}(\boldsymbol{x}_{t-1})$ for $t\geq 1$. Then, for any
$\boldsymbol{x}\in\text{int}(\Theta)$ we have

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[h_{t}(\boldsymbol{x}_{t-1})-h_{t}(\boldsymbol{x})|\Lambda_{T}\right]\leq
2dq_{T}\left(dq_{T}\sum_{t=1}^{T}\eta_{t}+2\sqrt{\mu
T}\right)+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{x}),$

where $q_{T}=M+2\sigma\sqrt{\log(T+1)}$.

###### Proof.

Fix $\boldsymbol{x}\in\text{int}(\Theta)$. Since $h_{t}$ is a strongly convex
function, for any $\boldsymbol{x}\in\Theta$ we can write

$\displaystyle\sum_{t=1}^{T}\left(h_{t}(\boldsymbol{x}_{t-1})-h_{t}(\boldsymbol{x})\right)\leq\sum_{t=1}^{T}\langle\mathbf{E}\left[\boldsymbol{g}_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t},\Lambda_{T}\right],\boldsymbol{x}_{t-1}-\boldsymbol{x}\rangle-\frac{\alpha}{2}\sum_{t=1}^{T}\left\lVert\boldsymbol{x}-\boldsymbol{x}_{t-1}\right\rVert^{2}.$
(29)

To simplify the notation, we rewrite $\boldsymbol{x}_{t}$ as follows

$\displaystyle\boldsymbol{x}_{t}$
$\displaystyle=\operatorname*{arg\,min}_{\boldsymbol{u}\in\Theta}\sum_{k=1}^{t}\langle\boldsymbol{g}_{k},\boldsymbol{u}\rangle+\underbrace{\frac{\alpha}{2}\sum_{k=1}^{t}\left\lVert\boldsymbol{u}-\boldsymbol{x}_{k-1}\right\rVert^{2}+\eta_{t}^{-1}\mathcal{R}(\boldsymbol{u})}_{=\vcentcolon
R_{t}(\boldsymbol{u})}$
$\displaystyle=\operatorname*{arg\,min}_{\boldsymbol{u}\in\Theta}\underbrace{\sum_{k=1}^{t}\langle\boldsymbol{g}_{k},\boldsymbol{u}\rangle+R_{t}(\boldsymbol{u})}_{=\vcentcolon\Phi_{t}(\boldsymbol{u})}=\operatorname*{arg\,min}_{\boldsymbol{u}\in\Theta}{\Phi_{t}(\boldsymbol{u})}.$

Moreover, set $\Phi_{0}(\boldsymbol{u})=\mathcal{R}(\boldsymbol{u})$ for all
$\boldsymbol{u}\in\text{int}(\Theta)$. Since
$\boldsymbol{x}_{0}=\operatorname*{arg\,min}_{\boldsymbol{u}\in\text{int}(\Theta)}\Phi_{0}(\boldsymbol{u})$
and we assume that $\mathcal{R}(\boldsymbol{x}_{0})=0$, we have

$\displaystyle-\sum_{t=1}^{T}\langle\boldsymbol{g}_{t},\boldsymbol{x}\rangle$
$\displaystyle=-\Phi_{T}(\boldsymbol{x})+\Phi_{T}(\boldsymbol{x}_{T})-\Phi_{T}(\boldsymbol{x}_{T})+R_{T}(\boldsymbol{x})$
$\displaystyle\leq\sum_{t=1}^{T}\left(\Phi_{t-1}(\boldsymbol{x}_{t-1})-\Phi_{t}(\boldsymbol{x}_{t})\right)+R_{T}(\boldsymbol{x}),$

where the last display is due to the fact that
$\Phi_{T}(\boldsymbol{x}_{T})\leq\Phi_{T}(\boldsymbol{x})$. Subsequently,

$\displaystyle\sum_{t=1}^{T}\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t-1}-\boldsymbol{x}\rangle\leq\sum_{t=1}^{T}\left(\underbrace{\Phi_{t-1}(\boldsymbol{x}_{t-1})-\Phi_{t}(\boldsymbol{x}_{t})+\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t-1}\rangle}_{\text{term
I}}\right)+R_{T}(\boldsymbol{x}).$ (30)

In order to control term I, we first derive an alternative expression for
$\Phi_{t}$. By the definition of $\Phi_{t}$,

$\displaystyle\Phi_{t}(\boldsymbol{x}_{t})=\sum_{k=1}^{t}\langle\boldsymbol{g}_{k},\boldsymbol{x}_{t}\rangle+R_{t}(\boldsymbol{x}_{t})$
$\displaystyle=\sum_{k=1}^{t-1}\langle\boldsymbol{g}_{k},\boldsymbol{x}_{t}\rangle+\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t}\rangle+R_{t-1}(\boldsymbol{x}_{t})+\left(R_{t}(\boldsymbol{x}_{t})-R_{t-1}(\boldsymbol{x}_{t})\right)$
$\displaystyle=\Phi_{t-1}(\boldsymbol{x}_{t})+\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t}\rangle+\left(R_{t}(\boldsymbol{x}_{t})-R_{t-1}(\boldsymbol{x}_{t})\right),$

so that

term I
$\displaystyle=\left(\Phi_{t-1}(\boldsymbol{x}_{t-1})+\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t-1}\rangle\right)-\left(\Phi_{t-1}(\boldsymbol{x}_{t})+\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t}\rangle\right)+R_{t-1}(\boldsymbol{x}_{t})-R_{t}(\boldsymbol{x}_{t})$
$\displaystyle\leq\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\rangle,$
(31)

where the last inequality is due to the fact that
$R_{t-1}(\boldsymbol{x}_{t})\leq R_{t}(\boldsymbol{x}_{t})$, and
$\Phi_{t-1}(\boldsymbol{x}_{t-1})=\min_{\boldsymbol{z}\in\Theta}\Phi_{t-1}(\boldsymbol{z})\leq\Phi_{t-1}(\boldsymbol{x}_{t})$.
From (30) and (31) we obtain

$\displaystyle\sum_{t=1}^{T}\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t-1}-\boldsymbol{x}\rangle\leq\sum_{t=1}^{T}\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\rangle+\frac{\alpha}{2}\sum_{t=1}^{T}\left\lVert\boldsymbol{x}-\boldsymbol{x}_{t-1}\right\rVert^{2}+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{x}).$

Taking expectations conditioned on the event $\Lambda_{T}$ gives

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t-1}-\boldsymbol{x}\rangle|\Lambda_{T}\right]$
$\displaystyle\leq\mathbf{E}\left[\sum_{t=1}^{T}\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\rangle+\frac{\alpha}{2}\sum_{t=1}^{T}\left\lVert\boldsymbol{x}-\boldsymbol{x}_{t-1}\right\rVert^{2}|\Lambda_{T}\right]+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{x})$
$\displaystyle\leq\mathbf{E}\left[\sum_{t=1}^{T}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}\left\lVert\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\right\rVert_{t}+\frac{\alpha}{2}\sum_{t=1}^{T}\left\lVert\boldsymbol{x}-\boldsymbol{x}_{t-1}\right\rVert^{2}|\Lambda_{T}\right]+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{x}).$

Furthermore, by the tower rule,

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\langle\mathbf{E}\left[\boldsymbol{g}_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t},\Lambda_{T}\right],\boldsymbol{x}_{t-1}-\boldsymbol{x}\rangle\big{|}\Lambda_{T}\right]$
$\displaystyle\leq\mathbf{E}\left[\sum_{t=1}^{T}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}\left\lVert\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\right\rVert_{t}+\frac{\alpha}{2}\sum_{t=1}^{T}\left\lVert\boldsymbol{x}-\boldsymbol{x}_{t-1}\right\rVert^{2}|\Lambda_{T}\right]$
$\displaystyle\phantom{0000000}+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{x}).$

Using the assumption that
$\mathbf{E}\left[\boldsymbol{g}_{t}|\,\boldsymbol{x}_{t-1},\boldsymbol{c}_{t},\Lambda_{T}\right]=\nabla
h_{t}(\boldsymbol{x}_{t-1})$, the fact that $\\{h_{t}\\}_{t=1}^{T}$ are
$\alpha$-strongly convex functions, and (29), yields

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}(h_{t}(\boldsymbol{x}_{t-1})-h_{t}(\boldsymbol{x}))|\Lambda_{T}\right]\leq\mathbf{E}\left[\sum_{t=1}^{T}\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}\left\lVert\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\right\rVert_{t}|\Lambda_{T}\right]+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{x}).$
(32)

We now apply Lemma 3 to bound the value
$\left\lVert\boldsymbol{x}_{t-1}-\boldsymbol{x}_{t}\right\rVert_{t}$ on the
event $\Lambda_{T}$. It follows that

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}(h_{t}(\boldsymbol{x}_{t-1})-h_{t}(\boldsymbol{x}))|\Lambda_{T}\right]\leq
2\left(\sum_{t=1}^{T}\eta_{t}\mathbf{E}\left[(\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*})^{2}|\Lambda_{T}\right]+\sqrt{\frac{\mu}{t}}\mathbf{E}\left[\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}|\Lambda_{T}\right]\right)+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{x}).$
(33)

Recall that $q_{T}=M+2\sigma\sqrt{\log(T+1})$, and under $\Lambda_{T}$, the
uniform bound (28) gives
$\left\lVert\boldsymbol{g}_{t}\right\rVert_{t}^{*}\leq dq_{T}$. Hence,

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[h_{t}(\boldsymbol{x}_{t-1})-h_{t}(\boldsymbol{x})|\Lambda_{T}\right]$
$\displaystyle\leq
2\left(d^{2}q_{T}^{2}\sum_{t=1}^{T}\eta_{t}+dq_{T}\sum_{t=1}^{T}\sqrt{\frac{\mu}{t}}\right)+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{x})$
$\displaystyle\leq 2dq_{T}\left(dq_{T}\sum_{t=1}^{T}\eta_{t}+2\sqrt{\mu
T}\right)+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{x}).$

∎

######  Lemma 5.

[20, Corollary 6] Let $A\in\mathbb{R}^{d\times d}$ be an invertible matrix.
Let $\boldsymbol{U}$ be distributed uniformly on $B^{d}$. Let ${\sf
f}_{A}(\boldsymbol{x},\boldsymbol{c})\triangleq\mathbf{E}\left[f(\boldsymbol{x}+A\boldsymbol{U},\boldsymbol{c})\right]$
for $\boldsymbol{x}\in\mathbb{R}^{d}$ and $\boldsymbol{c}\in[0,1]^{p}$. Then,

$\displaystyle\nabla_{\boldsymbol{x}}{\sf
f}_{A}(\boldsymbol{x},\boldsymbol{c})=\mathbf{E}\left[df(\boldsymbol{x}+A\boldsymbol{\zeta},\boldsymbol{c})A^{-1}\boldsymbol{\zeta}\right],$

where $\boldsymbol{\zeta}$ is uniformly distributed on $\partial B^{d}$. If
Assumption 2(i) holds, then ${\sf f}_{A}(\cdot,\boldsymbol{c})$ is
$\alpha$-strongly convex on $\mathbb{R}^{d}$ for all
$\boldsymbol{c}\in[0,1]^{p}$.

######  Lemma 6.

Let Assumption 3(ii) hold. Let $\boldsymbol{U}$ be distributed uniformly on
$B^{d}$. For $t\geq 1$, let ${\sf
f}_{t,P}:\mathbb{R}^{d}\times[0,1]^{p}\to\mathbb{R}$ be a surrogate function
defined by the relation

$\displaystyle{\sf
f}_{t,P}(\boldsymbol{x},\boldsymbol{c})=\mathbf{E}\left[f(\boldsymbol{x}+P_{t}\boldsymbol{U},\boldsymbol{c})|\boldsymbol{x}_{t-1}\right].$
(34)

Let $\\{\boldsymbol{g}_{t}\\}_{t=1}^{T}$ and
$\\{\boldsymbol{x}_{t}\\}_{t=0}^{T-1}$ be defined as in Algorithm 2, and
$\Lambda$ be any event that only depends on $\\{\xi_{t}\\}_{t=1}^{T}$. Then
for all $t\in[T]$ we have

$\displaystyle\mathbf{E}\left[\boldsymbol{g}_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t},\Lambda\right]=\nabla_{\boldsymbol{x}}{\sf
f}_{t,P}(\boldsymbol{x}_{t-1},\boldsymbol{c}_{t}).$

###### Proof.

By the definition of $\boldsymbol{g}_{t}$ we have

$\displaystyle\mathbf{E}\left[\boldsymbol{g}_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t},\Lambda\right]$
$\displaystyle=d\mathbf{E}\left[\left(f(\boldsymbol{x}_{t-1}+P_{t}\boldsymbol{\zeta}_{t},\boldsymbol{c}_{t})+\xi_{t}\right)P_{t}^{-1}\boldsymbol{\zeta}_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t},\Lambda\right]$
$\displaystyle=$ $\displaystyle
d\mathbf{E}\left[f(\boldsymbol{x}_{t-1}+P_{t}\boldsymbol{\zeta}_{t},\boldsymbol{c}_{t})P_{t}^{-1}\boldsymbol{\zeta}_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t}\right]+\underbrace{d\mathbf{E}[\xi_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t},\Lambda]P_{t}^{-1}\mathbf{E}\left[\boldsymbol{\zeta}_{t}\right]}_{=0},$

where the last equality is due to Assumption 3(ii). Now, by Lemma 5 we have

$\displaystyle
d\mathbf{E}\left[f(\boldsymbol{x}_{t-1}+P_{t}\boldsymbol{\zeta}_{t},\boldsymbol{c}_{t})P_{t}^{-1}\boldsymbol{\zeta}_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t}\right]=\nabla_{\boldsymbol{x}}{\sf
f}_{t,P}(\boldsymbol{x}_{t-1},\boldsymbol{c}_{t}),$

which concludes the proof. ∎

######  Lemma 7.

[20, Lemma 4] For $\mu>0$ let $\mathcal{R}:\text{int}(\Theta)\to\mathcal{R}$
be a $\mu$-self-concordant barrier with
$\min_{\boldsymbol{x}\in\text{int}(\Theta)}\mathcal{R}(\boldsymbol{x})=0$.
Then, for all $\boldsymbol{x},\boldsymbol{y}\in\text{int}(\Theta)$ we have

$\displaystyle\mathcal{R}(\boldsymbol{x})-\mathcal{R}(\boldsymbol{y})\leq\mu\log\left(\frac{1}{1-\pi_{\boldsymbol{x}}(\boldsymbol{y})}\right),$

where $\pi_{\boldsymbol{x}}(\boldsymbol{y})=\inf\\{t\geq
0:\boldsymbol{x}+t^{-1}(\boldsymbol{y}-\boldsymbol{x})\\}$ is the Minkowsky
function. Particularly, for $\boldsymbol{x}\in\text{int}(\Theta)$ if
$\boldsymbol{x}_{0}\in\operatorname*{arg\,min}_{\boldsymbol{u}\in\text{int}(\Theta)}\mathcal{R}(\boldsymbol{u})$,
and $\boldsymbol{x}^{\prime}=(1-1/T)\boldsymbol{x}+\boldsymbol{x}_{0}$ then

$\displaystyle\mathcal{R}(\boldsymbol{x}^{\prime})\leq\mu\log\left(T\right).$
(35)

###### Proof of Theorem 2.

Let $\boldsymbol{z}^{\prime}=(1-1/T)\boldsymbol{z}+(1/T)\boldsymbol{x}_{0}$.
Note that

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z},\boldsymbol{c}_{t})\right]$
$\displaystyle=\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})\right]+\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})-f(\boldsymbol{z},\boldsymbol{c}_{t})\right]$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})\right]+\frac{1}{T}\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{x}_{0},\boldsymbol{c}_{t})-f(\boldsymbol{z},\boldsymbol{c}_{t})\right]$
(36)
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})\right]+2M,$
(37)

where (36) is due to convexity of $f(\cdot,\boldsymbol{c})$. Invoking the
event $\Lambda_{T}$ we can write

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})\right]$
$\displaystyle=\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}^{c}\right]\mathbf{P}[\Lambda_{T}^{c}]+\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right]\mathbf{P}[\Lambda_{T}].$

Since $\\{\xi_{t}\\}_{t=1}^{T}$ are $\sigma$-sub-Gaussian we have

$\displaystyle\mathbf{P}\left[\Lambda_{T}^{c}\right]\leq\sum_{t=1}^{T}\mathbf{P}\left[|\xi_{t}|>2\sigma\sqrt{\log(T+1})\right]\leq
2\sum_{t=2}^{T+1}T^{-2}=2T^{-1}.$

Thus,

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})\right]\leq
4M+\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right].$
(38)

Next, introducing the surrogate function ${\sf
f}_{t,P}(\boldsymbol{x},\boldsymbol{c})=\mathbf{E}\left[f(\boldsymbol{x}+P_{t}\boldsymbol{U},\boldsymbol{c})|\boldsymbol{x}_{t-1}\right]$
we consider the decomposition

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right]$
$\displaystyle\hskip
28.45274pt=\underbrace{\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{x}_{t-1},\boldsymbol{c}_{t})|\Lambda_{T}\right]}_{\text{term
I}}+\underbrace{\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{x}_{t-1},\boldsymbol{c}_{t})-{\sf
f}_{t,P}(\boldsymbol{x}_{t-1},\boldsymbol{c}_{t})|\Lambda_{T}\right]}_{\text{term
II}}$ $\displaystyle\hskip
56.9055pt+\underbrace{\sum_{t=1}^{T}\mathbf{E}\left[{\sf
f}_{t,P}(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right]}_{\text{term
III}}+\underbrace{\sum_{t=1}^{T}\mathbf{E}\left[{\sf
f}_{t,P}(\boldsymbol{x}_{t-1},\boldsymbol{c}_{t})-{\sf
f}_{t,P}(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right]}_{\text{term
IV}}.$

In what follows, we bound each term in this decomosition separately. For term
I, by Assumption 2(ii) we have

$\displaystyle\text{term
I}=\mathbf{E}\left[\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{x}_{t-1},\boldsymbol{c}_{t})|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t}\right]|\Lambda_{T}\right]$
$\displaystyle\leq\frac{\beta}{2}\sum_{t=1}^{T}\mathbf{E}\left[\left\lVert
P_{t}\boldsymbol{\zeta}_{t}\right\rVert^{2}\right]$
$\displaystyle\leq\frac{\beta}{2}\sum_{t=1}^{T}\mathbf{E}\left[\left\lVert
P_{t}\right\rVert^{2}_{\text{op}}\right]\leq\frac{\beta}{2\alpha}\sum_{t=1}^{T}\frac{1}{\eta_{t}t},$

where $\left\lVert\cdot\right\rVert_{\text{op}}$ denotes the operator norm. By
the fact that $f(\cdot,\boldsymbol{c}_{t})$ is a convex function and by
Jensen’s inequality, we deduce that term II is negative. For term III, by
Assumption 2(ii) we have

term III
$\displaystyle\leq\frac{\beta}{2}\sum_{i=1}^{T}\mathbf{E}\left[\left\lVert
P_{t}\boldsymbol{U}\right\rVert^{2}\right]\leq\frac{\beta}{2}\sum_{t=1}^{T}\mathbf{E}\left[\left\lVert
P_{t}\right\rVert^{2}_{\text{op}}\right]\leq\frac{\beta}{2\alpha}\sum_{t=1}^{T}\frac{1}{\eta_{t}t}.$

To control term IV, first note that by Lemma 5 $\\{{\sf
f}_{t,P}(\cdot,\boldsymbol{c}_{t})\\}_{t=1}^{T}$ are $\alpha$-strongly convex
functions. Furthermore, by Lemma 6 we have that
$\mathbf{E}\left[\boldsymbol{g}_{t}|\boldsymbol{x}_{t-1},\boldsymbol{c}_{t},\Lambda_{T}\right]=\nabla{\sf
f}_{t,P}(\boldsymbol{x}_{t-1},\boldsymbol{c}_{t})$. Therefore, by Lemma 4 we
obtain

term IV $\displaystyle\leq
2d^{2}q_{T}^{2}\sum_{t=1}^{T}\eta_{t}+4dq_{T}\sqrt{\mu
T}+\eta_{T}^{-1}\mathcal{R}(\boldsymbol{z}^{\prime}),$

where $q_{T}=M+2\sigma\sqrt{\log(T+1)}$ and
$\boldsymbol{z}^{\prime}=(1-1/T)\boldsymbol{z}+(1/T)\boldsymbol{x}_{0}$. By
Lemma 7 we have $\mathcal{R}(\boldsymbol{z}^{\prime})\leq\mu\log(T)$, so that

term IV $\displaystyle\leq
2d^{2}q_{T}^{2}\sum_{t=1}^{T}\eta_{t}+4dq_{T}\sqrt{\mu
T}+\eta_{T}^{-1}\mu\log(T).$

Thus,

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right]\leq
2d^{2}q_{T}^{2}\sum_{t=1}^{T}\eta_{t}+4dq_{T}\sqrt{\mu
T}+\eta_{T}^{-1}\mu\log(T)+\frac{\beta}{\alpha}\sum_{t=1}^{T}\frac{1}{\eta_{t}t}.$

Since
$\eta_{t}=(4dq_{T})^{-1}\min\big{(}1,\frac{\nu\log(t+1)}{t}\big{)}^{\frac{1}{2}}$
with $\nu=16(\mu+\beta/\alpha)$ we get

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right]$
$\displaystyle\leq dq_{T}\sqrt{\nu\log(T+1)T}+4dq_{T}\sqrt{\mu T}+$
$\displaystyle+4dq_{T}\mu\max\left(\log^{2}(T+1),\frac{T\log(T+1)}{\nu}\right)^{\frac{1}{2}}+\frac{\beta}{\alpha}\sum_{t=1}^{T}\frac{1}{\eta_{t}t}.$

Using the fact that $16\mu\leq\nu$, and $\max\\{a,b\\}\leq a+b$ for $a,b>0$,
we further simplify the above bound to obtain

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right]$
$\displaystyle\leq\frac{9}{4}dq_{T}\sqrt{\nu\log(T+1)T}+4dq_{T}\mu\log(T+1)+\frac{\beta}{\alpha}\sum_{t=1}^{T}\frac{1}{\eta_{t}t}.$

Since $t/\log(t+1)\geq\sqrt{t}$ for all $t\in[T]$, then if $t\geq\nu^{2}$ we
have $t\geq\nu\log(t+1)$. Thus,

$\displaystyle\frac{\beta}{\alpha}\sum_{t=1}^{T}\frac{1}{\eta_{t}t}$
$\displaystyle\leq\frac{4\beta}{\alpha}dq_{T}\left(\sum_{t=1}^{\nu^{2}}\frac{1}{t}+\sum_{t=2}^{T}\sqrt{\frac{1}{\nu
t\log(t+1)}}\right)$ $\displaystyle\leq
4dq_{T}\left(\frac{\beta}{\alpha}\log(\nu^{2}+1)+\frac{2\beta}{\alpha}\sqrt{\frac{T}{\nu}}\right)\leq
4dq_{T}\left(\frac{\beta}{\alpha}\log(\nu^{2}+1)+\frac{1}{8}\sqrt{\nu
T}\right),$

where the last inequality is due to the fact that $16\beta/\alpha\leq\nu$.
Thus,

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right]$
$\displaystyle\leq
dq_{T}\left(\frac{11}{4}\sqrt{\nu\log(T+1)T}+4\left(\mu\log(T+1)+\frac{\beta}{\alpha}\log(\nu^{2}+1)\right)\right)$
$\displaystyle\leq\frac{dq_{T}}{4}\left(11\sqrt{\nu\log(T+1)T}+\nu\left(\log(T+1)+\log(\nu^{2}+1)\right)\right).$

Since $q_{T}=M+2\sigma\sqrt{\log(T+1)}$ we have

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z}^{\prime},\boldsymbol{c}_{t})|\Lambda_{T}\right]$
$\displaystyle\leq\frac{d}{4}\big{(}M+2\sigma\sqrt{\log(T+1)}\big{)}\bigg{(}11\sqrt{\nu
T\log(T+1)}$ (39)
$\displaystyle\quad+\nu\left(\log(T+1)+2\log(\nu+1)\right)\bigg{)}.$

Combining (37), (38), and (39) implies

$\displaystyle\sum_{t=1}^{T}\mathbf{E}\left[f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-f(\boldsymbol{z},\boldsymbol{c}_{t})\right]$
$\displaystyle\leq F(T),$

where

$\displaystyle F(T)$
$\displaystyle=\frac{d}{4}\big{(}M+2\sigma\sqrt{\log(T+1)}\big{)}\bigg{(}11\sqrt{\nu
T\log(T+1)}+\nu\left(\log(T+1)+2\log(\nu+1)\right)\bigg{)}+6M.$

Noticing that $F$ is a concave function we complete the first part of the
proof. For the second part of the proof, assume that $T\geq
16(\mu+\beta/\alpha)^{2}$. In this case we have $T\geq\nu$ since
$\beta/\alpha\geq 1$. Therefore,

$\displaystyle
F(T)\leq\frac{d}{4}\big{(}M+2\sigma\sqrt{\log(T+1)}\big{)}\bigg{(}11\sqrt{\nu
T\log(T+1)}+3\nu\log(T+1)\bigg{)}+6M.$

On the other hand, the condition $T\geq 16(\mu+\beta/\alpha)^{2}$ implies that

$\displaystyle\sqrt{\nu
T\log(T+1)}\geq\frac{\nu}{2}T^{\frac{1}{4}}\sqrt{\log(T+1)}\geq\frac{\nu}{2}\log(T+1),$

and therefore,

$\displaystyle F(T)$
$\displaystyle\leq\frac{17d}{4}\big{(}M+2\sigma\sqrt{\log(T+1)}\big{)}\sqrt{\nu
T\log(T+1)}+6M$
$\displaystyle=17d(M+2\sigma\sqrt{\log(T+1)})\sqrt{\left(\mu+\frac{\beta}{\alpha}\right)T\log(T+1)}+6M$
$\displaystyle\leq
d\left(18M+34\sigma\sqrt{\log(T+1)}\right)\sqrt{\left(\mu+\frac{\beta}{\alpha}\right)T\log(T+1)},$

where the the last inequality is due to the fact that $T\geq 16$ and
$\sqrt{T\log(T+1)}\geq 6.73$. ∎

###### Proof of Corollary 1.

Since $F$ in (11) is a concave function we can apply (9) to obtain

$\displaystyle\mathbf{E}\big{[}\sum_{t=1}^{T}\big{(}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\big{)}\big{]}$
$\displaystyle\leq
K^{p}F\left(\frac{T}{K^{p}}\right)+2LT\left(\frac{\sqrt{p}}{K}\right)^{\gamma}.$

Using the definition of $F$ and the inequality $\mu\leq\texttt{A}d^{\rho}$, we
get

$\displaystyle\mathbf{E}\big{[}\sum_{t=1}^{T}\big{(}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\big{)}\big{]}$
$\displaystyle\leq
C_{*}\Big{(}L_{1}d^{1+\rho}K^{p}+L_{2}\sqrt{K^{p}d^{2+\rho}T}+LT\left(\frac{\sqrt{p}}{K}\right)^{\gamma}\Big{)},$
(40)

where $L_{1}=\sqrt{\log(T+1)}\log(Td+1)$, $L_{2}=\log(T+1)$, and $C_{*}>0$ is
a constant depending only on $M,\sigma,\beta/\alpha$.

Consider now two cases. First, let
$Lp^{\frac{\gamma}{2}}d^{-(1+\rho/2)}T^{1/2}\log^{-1}(T+1)>1$. In this case,
since $x/2\leq\lfloor x\rfloor\leq x$ for $x>1$, we obtain that

$K=K(1+\rho/2,1/2,1,\gamma)\asymp\Big{(}Lp^{\frac{\gamma}{2}}d^{-(1+\rho/2)}T^{1/2}\log^{-1}(T+1)\Big{)}^{\frac{2}{p+2\gamma}},$

so that, to within a constant depending only on $M,\sigma,\beta/\alpha$, the
right hand side of (40) is of the order

$\displaystyle
L_{1}d^{1+\rho}\Big{(}Lp^{\frac{\gamma}{2}}d^{-(1+\rho/2)}L_{2}^{-1}\Big{)}^{\frac{2p}{p+2\gamma}}T^{\frac{p}{p+2\gamma}}+L_{2}^{\frac{2\gamma}{p+2\gamma}}\Big{(}Lp^{\frac{\gamma}{2}}\Big{)}^{\frac{p}{p+2\gamma}}d^{\frac{(2+\rho)\gamma}{p+2\gamma}}T^{\frac{p+\gamma}{p+2\gamma}}.$

In the second case,
$Lp^{\frac{\gamma}{2}}d^{-(1+\rho/2)}T^{1/2}\log^{-1}(T+1)\leq 1$. Then
$K(1+\rho/2,1/2,1,\gamma)=1$, so that the right hand side of (40) does not
exceed

$\displaystyle
C_{*}(L_{1}d^{1+\rho}+L_{2}\sqrt{d^{2+\rho}T}+(Lp^{\frac{\gamma}{2}}T^{1/2})\sqrt{T})\leq
C_{*}(L_{1}d^{1+\rho}+(L_{2}+1)\sqrt{d^{2+\rho}T}).$

Putting these remarks together we get

$\displaystyle\mathbf{E}\big{[}\sum_{t=1}^{T}\big{(}f(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{z}\in\Theta}f(\boldsymbol{z},\boldsymbol{c}_{t})\big{)}\big{]}\leq
C\max\bigg{\\{}L_{1}d^{1+\rho}+L_{2}\sqrt{d^{2+\rho}T},\,$
$\displaystyle\qquad\qquad\qquad\qquad\qquad
L_{1}\Big{(}Lp^{\frac{\gamma}{2}}L_{2}^{-1}\Big{)}^{\frac{2p}{p+2\gamma}}d^{\frac{2\gamma(1+\rho)-p}{p+2\gamma}}T^{\frac{p}{p+2\gamma}},\,L_{2}^{\frac{2\gamma}{p+2\gamma}}\Big{(}Lp^{\frac{\gamma}{2}}\Big{)}^{\frac{p}{p+2\gamma}}d^{\frac{(2+\rho)\gamma}{p+2\gamma}}T^{\frac{p+\gamma}{p+2\gamma}}\bigg{\\}},$

where $C>0$ is a constant depending only on $M,\sigma,\beta/\alpha$. ∎

##  Appendix C Proof of Theorem 3

######  Lemma 8.

Suppose that $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ are two probability
measures that are defined on a probability space $(X,\mathcal{M})$, such that
$\mathbf{P}_{1}$ is absolutely continuous with respect to $\mathbf{P}_{2}$.
Let $\Upsilon\in\mathcal{M}$ be such that
$\mathbf{P}_{1}(\Upsilon)=\mathbf{P}_{2}(\Upsilon)\neq 0$. Let
$\tilde{\mathbf{P}}_{1}$ and $\tilde{\mathbf{P}}_{2}$ be the conditional
probability measures of $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ given the event
$\Upsilon$, respectively, i.e., for $i=1,2$ and $\Gamma\in\mathcal{M}$

$\displaystyle\tilde{\mathbf{P}}_{i}(\Gamma)=\mathbf{P}_{i}(\Gamma\cap\Upsilon)\mathbf{P}_{i}^{-1}(\Upsilon).$

Then,

  1. 1.

For $i=1,2$

$\frac{\,\mathrm{d}\tilde{\mathbf{P}}_{i}(\boldsymbol{x})}{\,\mathrm{d}\mathbf{P}_{i}(\boldsymbol{x})}=\mathbb{1}(\boldsymbol{x}\in\Upsilon)\mathbf{P}_{i}^{-1}(\Upsilon).$

  2. 2.

$KL(\tilde{\mathbf{P}}_{1},\tilde{\mathbf{P}}_{2})=\int\log\left(\frac{\,\mathrm{d}\mathbf{P}_{1}(\boldsymbol{x})}{\,\mathrm{d}\mathbf{P}_{2}(\boldsymbol{x})}\right)\mathbb{1}(\boldsymbol{x}\in\Upsilon)\mathbf{P}_{1}^{-1}(\Upsilon)\,\mathrm{d}\mathbf{P}_{1}(\boldsymbol{x}).$

###### Proof of Theorem 3.

We choose a finite set of functions in a way that its members cannot be
distinguished from each other with positive probability but are separated
enough from each other to guarantee that the maximal regret for this family is
not smaller than the desired lower bound.

Set
$K=\max\left(1,\left\lfloor\left(\min\left(1,L^{2}\right)T\right)^{\frac{1}{p+2\gamma}}\right\rfloor\right)$.
Let $(B_{i})_{i=1}^{K^{p}}$ be a partition of $[0,1]^{p}$, where $B_{i}$’s are
disjoint cubes with edges of length $1/K$. Then, for any
$\boldsymbol{c}\in[0,1]^{p}$ there exists $i\in\\{1,\dots,K^{p}\\}$ that
satisfies $d(\boldsymbol{c},\partial B_{i})\leq\delta$, where $\partial B_{i}$
is the boundary of $B_{i}$, $d(\boldsymbol{c},\partial
B_{i})=\min_{\boldsymbol{u}\in\partial
B_{i}}\left\lVert\boldsymbol{c}-\boldsymbol{u}\right\rVert$ and
$\delta=\frac{1}{2K}$, cf. (45).

Let $\eta_{0}:\mathbb{R}\to\mathbb{R}$ be an infinitely many times
differentiable function such that

$\displaystyle\eta_{0}(x)=\begin{cases}=1\quad\quad&\text{if }|x|\leq 1/4,\\\
\in(0,1)\quad\quad&\text{if }1/4<|x|<1,\\\ =0\quad\quad&\text{if }|x|\geq
1.\end{cases}$

Set $\eta(x)=\int_{-\infty}^{x}\eta_{0}(u)\,\mathrm{d}u$. Let
$\Omega=\\{-1,1\\}^{K^{p}}$ and $\\{-1,1\\}^{d-1}$ be the sets of binary
sequences of length $K^{p}$ and $d-1$, respectively. Consider the finite set
of functions
$f_{\boldsymbol{\omega},\boldsymbol{\tau}}:\mathbb{R}^{d}\times[0,1]^{p}\to\mathbb{R}$,
$\boldsymbol{\omega}\in\Omega$, $\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}$ such
that:

$\displaystyle
f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})=\alpha\left\lVert\boldsymbol{x}\right\rVert^{2}+r_{1}L\eta\Big{(}x_{1}\delta^{-\frac{\gamma}{2}}\Big{)}$
$\displaystyle\left(\sum_{j=1}^{K^{p}}\omega_{j}d^{\gamma}(\boldsymbol{c},\partial
B_{j})\mathbb{1}\left(\boldsymbol{c}\in B_{j}\right)\right)$ (41)
$\displaystyle+r_{2}h^{2}\left(\sum_{i=2}^{d}\tau_{i}\eta\left(\frac{x_{i}}{h}\right)\right),\quad\quad\boldsymbol{x}=(x_{1},\dots,x_{d}),$

where $\omega_{j},\tau_{i}\in\\{-1,1\\}$,
$h=\min\left(d^{-\frac{1}{2}},T^{-\frac{1}{4}}\right)$ and $r_{1},r_{2}$ are
fixed positive numbers that will be chosen small enough. By Lemma 10 we have
that
$f_{\boldsymbol{\omega},\boldsymbol{\tau}}\in\mathcal{F}_{\alpha,\beta}(M)\cap\mathcal{F}_{\gamma}(L)$
provided
$r_{1}\leq\min\left(1,1/L^{2}\right)\min\left(1/2\eta(1),\alpha/L^{\prime}\right),r_{2}\leq\min\left(1/2\eta(1),\alpha/L^{\prime}\right)$,
where $L^{\prime}=\max_{x\in\mathbb{R}}|\eta^{\prime\prime}\left(x\right)|$.
Furthermore, by choosing $r_{1}\leq\alpha/\left(2\max\left(1,L\right)\right)$
and $r_{2}\leq\alpha/2$ we have

$\alpha^{-1}\delta^{-\gamma}r_{1}L\sum_{j=1}^{K^{p}}\omega_{j}d^{\gamma}(\boldsymbol{c}_{t},\partial
B_{j})\mathbb{1}\left(\boldsymbol{c}\in
B_{j}\right)\leq\frac{1}{2},\quad\quad\text{}\quad\quad\alpha^{-1}r_{2}\leq\frac{1}{2},$

and that under this condition the equation
$\nabla_{\boldsymbol{x}}f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})=0$
has the solution

$\displaystyle\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c})=\left(x^{*}_{1}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c}),\dots,x^{*}_{d}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c})\right),$

where
$x^{*}_{1}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c})=-(1/2)\alpha^{-1}\delta^{-\frac{\gamma}{2}}r_{1}L\sum_{j=1}^{K^{p}}\omega_{j}d^{\gamma}(\boldsymbol{c}_{t},\partial
B_{j})\mathbb{1}\left(\boldsymbol{c}\in B_{j}\right)$ and
$x^{*}_{i}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c})=-(1/2)\tau_{i}r_{2}\alpha^{-1}h$,
for $2\leq i\leq d$. Furthermore,

$\displaystyle\left\lVert\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c})\right\rVert^{2}\leq\frac{1}{4\alpha^{2}}\left(r_{1}^{2}L^{2}\delta^{\gamma}+dr_{2}^{2}h^{2}\right)\leq\frac{1}{8},$

which implies
$\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c})\in\Theta$.

For any fixed
$\boldsymbol{\omega}\in\Omega,\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}$, and
$1\leq t\leq T$, we denote by
$\mathbf{P}_{\boldsymbol{\omega},\boldsymbol{\tau},t}$ the probability measure
corresponding to the joint distribution of
$(\boldsymbol{z}_{1},y_{1}^{t},\boldsymbol{c}_{1}^{t})$ where
$y_{k}=f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{z}_{k},\boldsymbol{c}_{k})+\xi_{k}$
with independent identically distributed $\xi_{k}$’s such that
$\eqref{con:lw}$ holds and $\boldsymbol{z}_{k}$’s chosen by the randomized
procedure $\pi$. We have

$\displaystyle\,\mathrm{d}\mathbf{P}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left(\boldsymbol{z}_{1},y_{1}^{t},\boldsymbol{c}_{1}^{t}\right)=\,\mathrm{d}F\left(y_{1}-f_{\boldsymbol{\omega},\boldsymbol{\tau}}\left(\boldsymbol{z}_{1},\boldsymbol{c}_{1}\right)\right)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{1})\prod_{i=2}^{t}\,\mathrm{d}F\left(y_{i}-f_{\boldsymbol{\omega},\boldsymbol{\tau}}\left(\Phi_{i}\left(\boldsymbol{z}_{1},y_{1}^{i-1},\boldsymbol{c}_{1}^{i}\right),\boldsymbol{c}_{i}\right)\right)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{i}).$
(42)

Without loss of generality, we omit here the dependence of $\Phi_{i}$ on
$\boldsymbol{z}_{2},\dots,\boldsymbol{z}_{i-1}$ since
$\boldsymbol{z}_{i},i\geq 2$, is a Borel function of
$\boldsymbol{z}_{1},y_{1},\dots,y_{i-1},\boldsymbol{c}_{1},\dots,\boldsymbol{c}_{i}$.
Let $\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}$ denote the
expectation w.r.t. $\mathbf{P}_{\boldsymbol{\omega},\boldsymbol{\tau},t}$.

Note that

$\sum_{t=1}^{T}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{z}_{t},\boldsymbol{c}_{t})-\min_{\boldsymbol{x}\in\Theta}f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c}_{t})\right]\geq\frac{\alpha}{2}\sum_{t=1}^{T}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\left\lVert\boldsymbol{z}_{t}-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c}_{t})\right\rVert^{2}\right]$
(43)

due to the uniform strong convexity of functions $\boldsymbol{x}\mapsto
f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})$.

Consider the statistics

$\displaystyle(\hat{\boldsymbol{\omega}}_{t},\hat{\boldsymbol{\tau}}_{t})\in\operatorname*{arg\,min}_{\boldsymbol{\omega}\in\Omega,\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}}\left\lVert\boldsymbol{z}_{t}-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c}_{t})\right\rVert.$

Since
$\left\lVert\boldsymbol{x}^{*}(\hat{\boldsymbol{\omega}}_{t},\hat{\boldsymbol{\tau}}_{t},\boldsymbol{c}_{t})-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c}_{t})\right\rVert\leq\left\lVert\boldsymbol{z}_{t}-\boldsymbol{x}^{*}(\hat{\boldsymbol{\omega}}_{t},\hat{\boldsymbol{\tau}}_{t},\boldsymbol{c}_{t})\right\rVert+\left\lVert\boldsymbol{z}_{t}-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c}_{t})\right\rVert\leq
2\left\lVert\boldsymbol{z}_{t}-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c}_{t})\right\rVert$
for all $\boldsymbol{\omega}\in\Omega,\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}$ we
obtain

$\displaystyle\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\left\lVert\boldsymbol{z}_{t}-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c}_{t})\right\rVert^{2}\right]$
$\displaystyle\geq\frac{1}{4}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\left\lVert\boldsymbol{x}^{*}(\hat{\boldsymbol{\omega}}_{t},\hat{\boldsymbol{\tau}}_{t},\boldsymbol{c}_{t})-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c}_{t})\right\rVert^{2}\right]$
$\displaystyle=\frac{1}{4}\alpha^{-2}L^{2}\delta^{-\gamma}r_{1}^{2}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\sum_{j=1}^{K^{p}}d^{2\gamma}(\boldsymbol{c}_{t},\partial
B_{j})\mathbb{1}\left(\hat{\omega}_{t,j}\neq\omega_{j}\right)\mathbb{1}\left(\boldsymbol{c}_{t}\in
B_{j}\right)\right]$
$\displaystyle\phantom{00000}+\frac{1}{4}\alpha^{-2}h^{2}r_{2}^{2}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\rho(\boldsymbol{\tau},\hat{\boldsymbol{\tau}_{t}})\right],$

where
$\rho(\boldsymbol{\tau},\hat{\boldsymbol{\tau}}_{t})=\sum_{i=2}^{d}\mathbb{1}\left(\boldsymbol{\tau}_{i}\neq\hat{\boldsymbol{\tau}}_{t,i}\right)$
is the Hamming distance between $\boldsymbol{\tau}$ and
$\hat{\boldsymbol{\tau}}_{t}$, with
$\hat{\boldsymbol{\omega}}_{t}=\left(\hat{\omega}_{t,1},\dots,\hat{\omega}_{t,K^{p}}\right)$
and
$\hat{\boldsymbol{\tau}}_{t}=\left(\hat{\tau}_{t,2},\dots,\hat{\tau}_{t,d}\right)$.
Note that, due to (46), for $\varepsilon=1/2$ we have

$\mathbb{P}_{K}\left[d(\boldsymbol{c}_{t},\partial
B_{j})\geq\frac{1}{4K}\Big{|}\boldsymbol{c}_{t}\in
B_{j}\right]\geq\mathbb{P}_{K}\left[\left\lVert\boldsymbol{c}_{t}-\boldsymbol{b}_{j}\right\rVert_{\infty}\leq\frac{1}{4K}\Big{|}\boldsymbol{c}_{t}\in
B_{j}\right]=1,$

which yields

$\mathbb{P}_{K}\left[d^{2\gamma}(\boldsymbol{c}_{t},\partial
B_{j})\geq\left(\frac{\delta^{2}}{4p^{2}}\right)^{\gamma}\Big{|}\boldsymbol{c}_{t}\in
B_{j}\right]=1.$

Thus,

$\displaystyle\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}$
$\displaystyle\left[\left\lVert\boldsymbol{z}_{t}-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{c}_{t})\right\rVert^{2}\right]\geq\frac{1}{4}\alpha^{-2}\delta^{-\gamma}r_{1}^{2}L^{2}\sum_{j=1}^{K^{p}}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[d^{2\gamma}(\boldsymbol{c}_{t},\partial
B_{j})\mathbb{1}\left(\hat{\omega}_{t,j}\neq\omega_{j}\right)|\boldsymbol{c}_{t}\in
B_{j}\right]\mathbb{P}_{K}\left(\boldsymbol{c}_{t}\in B_{j}\right)$
$\displaystyle\phantom{1000000000000}+\frac{1}{4}\alpha^{-2}r_{2}^{2}h^{2}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\rho(\boldsymbol{\tau},\hat{\boldsymbol{\tau}_{t}})\right]$
$\displaystyle=\frac{1}{4}\alpha^{-2}r_{1}^{2}L^{2}\delta^{-\gamma}\sum_{j=1}^{K^{p}}\bigg{(}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[d^{2\gamma}(\boldsymbol{c}_{t},\partial
B_{j})\mathbb{1}\left(\hat{\omega}_{t,j}\neq\omega_{j}\right)\Big{|}\boldsymbol{c}_{t}\in
B_{j},d^{2\gamma}(\boldsymbol{c}_{t},\partial
B_{j})\geq\left(\frac{\delta^{2}}{4p^{2}}\right)^{\gamma}\right]$
$\displaystyle\phantom{10000}\mathbb{P}_{K}\left(d^{2\gamma}(\boldsymbol{c}_{t},\partial
B_{j})\geq\left(\frac{\delta^{2}}{4p^{2}}\right)^{\gamma}\Big{|}\boldsymbol{c}_{t}\in
B_{j}\right)\mathbb{P}_{K}\left(\boldsymbol{c}_{t}\in
B_{j}\right)\bigg{)}+\alpha^{-2}r_{2}^{2}h^{2}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\rho(\boldsymbol{\tau},\hat{\boldsymbol{\tau}_{t}})\right]$
$\displaystyle\geq\frac{\alpha^{-2}}{4^{\gamma+1}}r_{1}^{2}L^{2}\delta^{\gamma}\sum_{j=1}^{K^{p}}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\mathbb{1}\left(\hat{\omega}_{t,j}\neq\omega_{j}\right)\Big{|}\boldsymbol{c}_{t}\in
B_{j},d^{2\gamma}(\boldsymbol{c}_{t},\partial
B_{j})\geq\left(\frac{\delta^{2}}{4p^{2}}\right)^{\gamma}\right]\mathbb{P}_{K}\left(\boldsymbol{c}_{t}\in
B_{j}\right)$
$\displaystyle\phantom{1000000000000}+\frac{1}{4}\alpha^{-2}r_{2}^{2}h^{2}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\rho(\boldsymbol{\tau},\hat{\boldsymbol{\tau}_{t}})\right].$

Introduce the random event $\Upsilon_{t,j}=\\{\boldsymbol{c}_{t}\in B_{j},\
d(\boldsymbol{c}_{t},\partial B_{j})\geq\frac{\delta}{2p}\\}$. Summing both
sides from $1$ to $T$, taking the maximum over $\Omega$ and $\\{-1,1\\}^{d-1}$
and then taking the minimum over all statistics
$\hat{\boldsymbol{\omega}}_{t}$ with values in $\Omega$ and
$\hat{\boldsymbol{\tau}}_{t}$ with values in $\\{-1,1\\}^{d-1}$ we obtain

$\displaystyle\min_{\hat{\boldsymbol{\omega}}_{1},\dots,\hat{\boldsymbol{\omega}}_{T}}$
$\displaystyle\max_{\boldsymbol{\omega}\in\Omega}\sum_{t=1}^{T}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\left\lVert\boldsymbol{z}_{t}-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{c}_{t})\right\rVert^{2}\right]\geq\frac{\alpha^{-2}}{4^{\gamma+1}}r_{1}^{2}L^{2}\delta^{\gamma}K^{-p}\underbrace{\min_{\hat{\boldsymbol{\omega}}_{1},\dots,\hat{\boldsymbol{\omega}}_{T}}\max_{\boldsymbol{\omega}\in\Omega}\sum_{t=1}^{T}\sum_{j=1}^{K^{p}}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\mathbb{1}\left(\hat{\omega}_{t,j}\neq\omega_{j}\right)|\Upsilon_{t,j}\right]}_{\text{term
I}}$
$\displaystyle\phantom{000000}+\frac{1}{4}\alpha^{-2}r_{2}^{2}h^{2}\underbrace{\min_{\hat{\boldsymbol{\tau}}_{1},\dots,\hat{\boldsymbol{\tau}}_{T}}\max_{\boldsymbol{\omega}\in\Omega,\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}}\sum_{t=1}^{T}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\rho(\boldsymbol{\tau},\hat{\boldsymbol{\tau}_{t}})\right]}_{\text{term
II}}.$

We will treat terms I and II separately. For term I we can write

term I $\displaystyle\geq
2^{-K^{p}-d+1}\min_{\hat{\boldsymbol{\omega}}_{1},\dots,\hat{\boldsymbol{\omega}}_{T}}\sum_{t=1}^{T}\sum_{j=1}^{K^{p}}\sum_{\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}}\sum_{\boldsymbol{\omega}\in\Omega}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\mathbb{1}\left(\hat{\omega}_{t,j}\neq\omega_{j}\right)|\Upsilon_{t,j}\right]$
$\displaystyle\geq
2^{-K^{p}-d+1}\sum_{t=1}^{T}\sum_{j=1}^{K^{p}}\sum_{\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}}\sum_{\boldsymbol{\omega}\in\Omega}\min_{\hat{\boldsymbol{\omega}}_{t,j}}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\mathbb{1}\left(\hat{\omega}_{t,j}\neq\omega_{j}\right)|\Upsilon_{t,j}\right]$

Let $\Omega_{j}=\\{\boldsymbol{\omega}\in\Omega:\omega_{j}=1\\}$, and for any
$\boldsymbol{\omega}\in\Omega_{j}$, denote $\bar{\boldsymbol{\omega}}$ such
that $\omega_{i}=\bar{\omega}_{i}$, for any $i\neq j$, and
$\bar{\omega}_{j}=-1$. Thus,

term I $\displaystyle\geq
2^{-K^{p}-d+1}\sum_{t=1}^{T}\sum_{j=1}^{K^{p}}\sum_{\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}}\sum_{\boldsymbol{\omega}\in\Omega_{j}}\min_{\hat{\omega}_{t,j}}\left(\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\mathbb{1}\left(\hat{\omega}_{t,j}\neq
1\right)|\Upsilon_{t,j}\right]+\mathbf{E}_{\bar{\boldsymbol{\omega}},\boldsymbol{\tau},t}\left[\mathbb{1}\left(\hat{\omega}_{t,j}\neq-1\right)|\Upsilon_{t,j}\right]\right)$
$\displaystyle\geq\frac{1}{2}\sum_{t=1}^{T}\sum_{j=1}^{K^{p}}\min_{\boldsymbol{\tau}\in\\{-1,1\\}^{d-1},\boldsymbol{\omega}\in\Omega_{j}}\min_{\hat{\omega}_{t,j}}\left(\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}\left[\mathbb{1}\left(\hat{\omega}_{t,j}\neq
1\right)|\Upsilon_{t,j}\right]+\mathbf{E}_{\bar{\boldsymbol{\omega}},\boldsymbol{\tau},t}\left[\mathbb{1}\left(\hat{\omega}_{t,j}\neq-1\right)|\Upsilon_{t,j}\right]\right).$

For any $\boldsymbol{\omega}\in\Omega_{j}$ and
$\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}$, let
$\tilde{\mathbf{P}}_{\boldsymbol{\omega},\boldsymbol{\tau},t}$ and
$\tilde{\mathbf{P}}_{\bar{\boldsymbol{\omega}},\boldsymbol{\tau},t}$ be the
conditional probability distributions of
$\mathbf{P}_{\boldsymbol{\omega},\boldsymbol{\tau},t}$ and
$\mathbf{P}_{\bar{\boldsymbol{\omega}},\boldsymbol{\tau},t}$ on the event
$\Upsilon_{t,j}$, respectively. Then, by Lemma 9 we have

$\displaystyle
KL\bigg{(}\tilde{\mathbf{P}}_{\boldsymbol{\omega},\boldsymbol{\tau},t},\tilde{\mathbf{P}}_{\bar{\boldsymbol{\omega}},\boldsymbol{\tau},t}\bigg{)}$
$\displaystyle\leq
I_{0}\sum_{i=1}^{t-1}\int\max_{\boldsymbol{x}\in\Theta}|f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c}_{i})-f_{\bar{\boldsymbol{\omega}},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c}_{i})|^{2}\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{i})$
$\displaystyle\phantom{0000}+I_{0}\int\max_{\boldsymbol{x}\in\Theta}|f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c}_{t})-f_{\bar{\boldsymbol{\omega}},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c}_{t})|^{2}\mathbb{1}(\boldsymbol{c}_{t}\in\Upsilon_{t,j})\mathbb{P}_{K}^{-1}(\Upsilon_{t,j})\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{t})$
$\displaystyle\leq
I_{0}\sum_{i=1}^{t-1}\int|2r_{1}L\eta(1)d^{\gamma}(\boldsymbol{c}_{i},\partial
B_{j})|^{2}\mathbb{1}\left(\boldsymbol{c}_{i}\in
B_{j}\right)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{i})$
$\displaystyle\phantom{0000}+I_{0}\int|2r_{1}\eta(1)d^{\gamma}(\boldsymbol{c}_{t},\partial
B_{j})|^{2}\mathbb{1}(\boldsymbol{c}_{t}\in\Upsilon_{t,j})\mathbb{P}_{K}^{-1}(\Upsilon_{t,j})\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{t})$
$\displaystyle\leq
4I_{0}r_{1}^{2}L^{2}\eta^{2}(1)\delta^{2\gamma}\left(\sum_{i=1}^{t-1}\int\mathbb{1}\left(\boldsymbol{c}_{i}\in
B_{j}\right)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{i})+1\right)\leq
4I_{0}r_{1}^{2}L^{2}\eta^{2}(1)\delta^{2\gamma}\left(tK^{-p}+1\right).$

Since $\delta=1/(2K)$,
$K=\max\left(1,\left\lfloor\left(\min\left(1,L^{2}\right)T\right)^{\frac{1}{p+2\gamma}}\right\rfloor\right)$
we obtain that

$\displaystyle
KL\left(\tilde{\mathbf{P}}_{\boldsymbol{\omega},\boldsymbol{\tau},t},\tilde{\mathbf{P}}_{\bar{\boldsymbol{\omega}},\boldsymbol{\tau},t}\right)\leq\log(2)$

if we choose
$r_{1}\leq\left(\log(2)/(8I_{0}\eta^{2}(1)\max(1,L^{2}))\right)^{1/2}$.
Therefore, using Theorem 2.12 from [43] we get

$\displaystyle\text{term
I}\geq\frac{TK^{p}}{4}\exp(-\log(2))=\frac{TK^{p}}{8}.$

Moreover, for any $\boldsymbol{\omega}\in\Omega$ and
$\boldsymbol{\tau},\boldsymbol{\tau}^{\prime}\in\\{-1,1\\}^{d-1}$ such that
$\rho(\boldsymbol{\tau},\boldsymbol{\tau}^{\prime})=1$ we have

$\displaystyle
KL\left(\mathbf{P}_{\boldsymbol{\omega},\boldsymbol{\tau},t},\mathbf{P}_{\boldsymbol{\omega},\boldsymbol{\tau}^{\prime},t}\right)$
$\displaystyle=\int\log\left(\frac{\,\mathrm{d}\mathbf{P}_{\boldsymbol{\omega},\boldsymbol{\tau},t}}{\,\mathrm{d}\mathbf{P}_{\boldsymbol{\omega},\boldsymbol{\tau}^{\prime},t}}\right)\,\mathrm{d}\mathbf{P}_{\boldsymbol{\omega},\boldsymbol{\tau},t}$
$\displaystyle=\int\bigg{[}\log\left(\frac{\,\mathrm{d}F(y_{1}-f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{z}_{1},\boldsymbol{c}_{1}))}{\,\mathrm{d}F(y_{1}-f_{\boldsymbol{\omega},\boldsymbol{\tau}^{\prime}}(\boldsymbol{z}_{1},\boldsymbol{c}_{1}))}\right)+$
$\displaystyle\phantom{0000000}+\sum_{i=2}^{t}\log\left(\frac{\,\mathrm{d}F(y_{i}-f_{\boldsymbol{\omega},\boldsymbol{\tau}}\left(\Phi_{i}\left(\boldsymbol{z}_{1}^{i-1},y_{1}^{i-1},\boldsymbol{c}_{1}^{i}\right),\boldsymbol{c}_{i})\right)}{\,\mathrm{d}F(y_{i}-f_{\boldsymbol{\omega},\boldsymbol{\tau}^{\prime}}\left(\Phi_{i}\left(\boldsymbol{z}_{1}^{i-1},y_{1}^{i-1},\boldsymbol{c}_{1}^{i}\right),\boldsymbol{c}_{i})\right)}\right)\bigg{]}$
$\displaystyle\phantom{000000000}\,\mathrm{d}F\left(y_{i}-f_{\boldsymbol{\omega},\boldsymbol{\tau}}\left(\boldsymbol{z}_{1}^{i-1},\boldsymbol{c}_{1}\right)\right)\prod_{i=2}^{t}\,\mathrm{d}F\left(y_{i}-f_{\boldsymbol{\omega},\boldsymbol{\tau}}\left(\Phi_{i}\left(\boldsymbol{z}_{1}^{i-1},y_{1}^{i-1},\boldsymbol{c}_{1}^{i}\right),\boldsymbol{c}_{i}\right)\right)$
$\displaystyle\leq
I_{0}\sum_{i=1}^{t}\max_{\boldsymbol{x}\in\Theta}|f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c}_{i})-f_{\boldsymbol{\omega},\boldsymbol{\tau}^{\prime}}(\boldsymbol{x},\boldsymbol{c}_{i})|^{2}=4tI_{0}r_{2}^{2}h^{4}\eta^{2}(1).$

Using the fact that $h\leq T^{-\frac{1}{4}}$, choosing
$r_{2}\leq\left(\log(2)/(4I_{0}\eta^{2}(1))\right)^{1/2}$ and applying again
Theorem 2.12 from [43] implies

$\displaystyle\text{term
II}\geq\frac{T(d-1)}{4}\exp(-\log(2))\geq\frac{Td}{16}.$

Putting together the bounds for terms I and II we get

$\displaystyle\min_{\hat{\boldsymbol{\omega}}_{1},\hat{\boldsymbol{\tau}}_{1}\dots,\hat{\boldsymbol{\omega}}_{T},\hat{\boldsymbol{\tau}}_{T}}\max_{\boldsymbol{\omega}\in\Omega,\tau\in\\{-1,1\\}^{d-1}}\sum_{t=1}^{T}\mathbf{E}_{\boldsymbol{\omega},\boldsymbol{\tau},t}$
$\displaystyle\left[\left\lVert\boldsymbol{z}_{t}-\boldsymbol{x}^{*}(\boldsymbol{\omega},\boldsymbol{\tau},\boldsymbol{c}_{t})\right\rVert^{2}\right]\geq\frac{\alpha^{-2}}{256}r_{1}^{2}T\delta^{\gamma}+\frac{\alpha^{-2}}{64}r_{2}^{2}dTh^{2}$
$\displaystyle\geq\frac{\alpha^{-2}}{2048}r_{3}^{2}\min\left(1,L^{\frac{2(d+\gamma)}{d+2\gamma}}\right)T^{\frac{d+\gamma}{d+2\gamma}}+\frac{\alpha^{-2}}{64}r_{2}^{2}\min\left(T,dT^{\frac{1}{2}}\right),$
(44)

where $r_{3}=r_{2}/\min(1,L)$. Considering the fact that $r_{2}$ and $r_{3}$
are independent of $d,p,L$, and $T$, (44) combined with (43) implies the
theorem. ∎

Recall the definition of $\mathbb{P}_{K}$ in (15). The following figure
illustrates the support of $\mathbb{P}_{K}$ for $K=3$ and $p=2$. By
definition, $\mathbb{P}_{K}$ yields a uniform distribution for each black
square in the figure.

Figure 1: Support of $\mathbb{P}_{K}$ for $K=3$ and $p=2$

The next lemma provides an upper bound on the Kullback-Leibler divergence of
two probability measures, which plays a key role in our analysis of the lower
bound.

######  Lemma 9.

With the same notation as in the proof of Theorem 3, for
$\boldsymbol{\omega},\boldsymbol{\omega}^{\prime}\in\Omega$ and $t\geq 1$
denote $\mathbf{P}_{\boldsymbol{\omega},t}$ and
$\mathbf{P}_{\boldsymbol{\omega}^{\prime},t}$ as they are defined in (42). Let
$\Upsilon\subseteq[0,1]^{p}$ such that $\mathbb{P}_{K}(\Upsilon)\neq 0$. Let
$\tilde{\mathbf{P}}_{\boldsymbol{\omega},t}$
$\tilde{\mathbf{P}}_{\boldsymbol{\omega}^{\prime},t}$ be the conditional
probability measures of ${\mathbf{P}}_{\boldsymbol{\omega},t}$
${\mathbf{P}}_{\boldsymbol{\omega}^{\prime},t}$ given the event
$\boldsymbol{c}_{t}\in\Upsilon$, respectively. Then, if (14) holds, we have

$\displaystyle
KL(\tilde{\mathbf{P}}_{\boldsymbol{\omega},t},\tilde{\mathbf{P}}_{\boldsymbol{\omega}^{\prime},t})$
$\displaystyle\leq
I_{0}\sum_{i=1}^{t-1}\max_{\boldsymbol{x}\in\Theta}|f_{\boldsymbol{\omega},t}(\boldsymbol{x},\boldsymbol{c}_{i})-f_{\boldsymbol{\omega}^{\prime},t}(\boldsymbol{x},\boldsymbol{c}_{i})|\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{i})$
$\displaystyle\phantom{0000}+I_{o}\int\max_{\boldsymbol{x}\in\Theta}|f_{\boldsymbol{\omega},t}(\boldsymbol{x},\boldsymbol{c}_{i})-f_{\boldsymbol{\omega}^{\prime},t}(\boldsymbol{x},\boldsymbol{c}_{i})|\mathbb{1}(\boldsymbol{c}_{t}\in\Upsilon)\mathbb{P}_{K}^{-1}(\Upsilon)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{t}).$

###### Proof.

By Lemma 8(i), for any $\boldsymbol{\omega}\in\Omega$ we have

$\displaystyle\,\mathrm{d}\tilde{\mathbf{P}}_{\boldsymbol{\omega},t}(\boldsymbol{z}_{1},y_{1}^{t},\boldsymbol{c}_{1}^{t})$
$\displaystyle=\,\mathrm{d}F(y_{1}-f_{\boldsymbol{\omega}}(\boldsymbol{z}_{1},\boldsymbol{c}_{1}))\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{1})\left(\prod_{i=2}^{t-1}\,\mathrm{d}F(y_{i}-f_{\boldsymbol{\omega}}(\pi_{i}(\boldsymbol{z}_{1},y_{1}^{i-1},\boldsymbol{c}_{1}^{i-1})))\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{i})\right)$
$\displaystyle\phantom{00000}\,\mathrm{d}F(y_{t}-f_{\boldsymbol{\omega}}(\pi_{i}(\boldsymbol{z}_{1},y_{1}^{t-1},\boldsymbol{c}_{1}^{t})))\mathbb{1}(\boldsymbol{c}_{t}\in\Upsilon)\mathbb{P}_{K}^{-1}(\Upsilon)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{t}).$

Therefore, for any
$\boldsymbol{\omega},\boldsymbol{\omega}^{\prime}\in\Omega$, by Lemma 8(ii) we
can write

$\displaystyle
KL\bigg{(}\tilde{\mathbf{P}}_{\boldsymbol{\omega},t},\tilde{\mathbf{P}}_{\boldsymbol{\omega}^{\prime},t}\bigg{)}=\int\log\left(\frac{\,\mathrm{d}\mathbf{P}_{\boldsymbol{\omega},t}}{\,\mathrm{d}\mathbf{P}_{\boldsymbol{\omega}^{\prime},t}}\right)\,\mathrm{d}\tilde{\mathbf{P}}_{\boldsymbol{\omega},t}$
$\displaystyle\phantom{00000000000}=\int\bigg{[}\log\left(\frac{\,\mathrm{d}F(y_{1}-f_{\boldsymbol{\omega}}(\boldsymbol{z}_{1},\boldsymbol{c}_{1}))}{\,\mathrm{d}F(y_{1}-f_{\boldsymbol{\omega}^{\prime}}(\boldsymbol{z}_{1},\boldsymbol{c}_{1}))}\right)+$
$\displaystyle\phantom{0000000}+\sum_{i=2}^{t}\log\left(\frac{\,\mathrm{d}F(y_{i}-f_{\boldsymbol{\omega}}\left(\pi_{i}\left(\boldsymbol{z}_{1},y_{1}^{i-1},\boldsymbol{c}_{1}^{i}\right),\boldsymbol{c}_{i})\right)}{\,\mathrm{d}F(y_{i}-f_{\boldsymbol{\omega}^{\prime}}\left(\pi_{i}\left(\boldsymbol{z}_{1},y_{1}^{i-1},\boldsymbol{c}_{1}^{i}\right),\boldsymbol{c}_{i})\right)}\right)\bigg{]}$
$\displaystyle\,\mathrm{d}F\left(y_{1}-f_{\boldsymbol{\omega}}\left(\boldsymbol{z}_{1},\boldsymbol{c}_{1}\right)\right)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{1})\left(\prod_{i=2}^{t-1}\,\mathrm{d}F\left(y_{i}-f_{\boldsymbol{\omega}}\left(\pi_{i}\left(\boldsymbol{z}_{1},y_{1}^{i-1},\boldsymbol{c}_{1}^{i}\right),\boldsymbol{c}_{i}\right)\right)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{i})\right)$
$\displaystyle\phantom{00000000000000000}\,\mathrm{d}F\left(y_{t}-f_{\boldsymbol{\omega}}\left(\pi_{t}\left(\boldsymbol{z}_{1},y_{1}^{t-1},\boldsymbol{c}_{1}^{t}\right),\boldsymbol{c}_{t}\right)\right)\mathbb{1}(\boldsymbol{c}_{t}\in\Upsilon)\mathbb{P}_{K}^{-1}(\Upsilon)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{t})$
$\displaystyle\leq
I_{0}\sum_{i=1}^{t-1}\int\max_{\boldsymbol{x}\in\Theta}|f_{\boldsymbol{\omega}}(\boldsymbol{x},\boldsymbol{c}_{i})-f_{\boldsymbol{\omega}^{\prime}}(\boldsymbol{x},\boldsymbol{c}_{i})|^{2}\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{i})$
$\displaystyle\phantom{00000}+I_{0}\int\max_{\boldsymbol{x}\in\Theta}|f_{\boldsymbol{\omega}}(\boldsymbol{x},\boldsymbol{c}_{t})-f_{\boldsymbol{\omega}^{\prime}}(\boldsymbol{x},\boldsymbol{c}_{t})|^{2}\mathbb{1}(\boldsymbol{c}_{t}\in\Upsilon)\mathbb{P}_{K}^{-1}(\Upsilon)\,\mathrm{d}\mathbb{P}_{K}(\boldsymbol{c}_{t}).$

∎

######  Lemma 10.

With the same notation as in the proof Theorem 3, let
$f_{\boldsymbol{\omega},\boldsymbol{\tau}}:\mathbb{R}^{d}\times[0,1]^{p}\to\mathbb{R}$
denoted the function that it is defined in (41). Then, for all
$\boldsymbol{\omega}\in\Omega$ and $\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}$,
$f_{\boldsymbol{\omega},\boldsymbol{\tau}}\in\mathcal{F}_{\alpha,\beta}(M)\cap\mathcal{F}_{\gamma}(L).$

###### Proof.

Fix $\boldsymbol{\omega}\in\Omega,\boldsymbol{\tau}\in\\{-1,1\\}^{d-1}$.
First, let us prove that for all $\boldsymbol{x}\in\mathbb{R}^{d}$,
$f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\cdot)$ is a
$1$-Lipschitz function. For any
$\boldsymbol{c},\boldsymbol{c}^{\prime}\in[0,1]^{p}$, we can write

$\displaystyle|f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})-f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c}^{\prime})|$
$\displaystyle=r_{1}L\eta\left(x_{1}\delta^{-\frac{\gamma}{2}}\right)\bigg{|}\sum_{j=1}^{K^{p}}\omega_{j}\left(d^{\gamma}(\boldsymbol{c},\partial
B_{j})\mathbb{1}\left(\boldsymbol{c}\in
B_{j}\right)-d^{\gamma}(\boldsymbol{c}^{\prime},\partial
B_{j})\mathbb{1}\left(\boldsymbol{c}^{\prime}\in B_{j}\right)\right)\bigg{|}$
$\displaystyle\leq
r_{1}L\eta\left(1\right)\bigg{|}\sum_{j=1}^{K^{p}}\omega_{j}\left(d(\boldsymbol{c},\partial
B_{j})\mathbb{1}\left(\boldsymbol{c}\in
B_{j}\right)-d^{\gamma}(\boldsymbol{c}^{\prime},\partial
B_{j})\mathbb{1}\left(\boldsymbol{c}^{\prime}\in B_{j}\right)\right)\bigg{|}.$

For $i,j\in K^{p}$, let us assume that $\boldsymbol{c}\in B_{i}$ and
$\boldsymbol{c}^{\prime}\in B_{j}$, and let $\boldsymbol{y}_{i}\in\partial
B_{i},\boldsymbol{y}^{\prime}_{j}\in\partial B_{j}$, such that
$d(\boldsymbol{c},\partial
B_{i})=\left\lVert\boldsymbol{c}-\boldsymbol{y}_{i}\right\rVert$ and
$d(\boldsymbol{c}^{\prime},\partial
B_{j})=\left\lVert\boldsymbol{c}^{\prime}-\boldsymbol{y}^{\prime}_{j}\right\rVert$.
If $i=j$, then

$\displaystyle|f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})-f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c}^{\prime})|$
$\displaystyle\leq
r_{1}L\eta\left(1\right)\bigg{|}d^{\gamma}(\boldsymbol{c},\partial
B_{i})-d^{\gamma}(\boldsymbol{c}^{\prime},\partial B_{i})\bigg{|}$
$\displaystyle=r_{1}L\eta\left(1\right)\bigg{(}\mathbb{1}\left(d(\boldsymbol{c},\partial
B_{i})\geq d\left(\boldsymbol{c}^{\prime},\partial
B_{i}\right)\right)\left(\left\lVert\boldsymbol{c}-\boldsymbol{y}_{i}\right\rVert-\left\lVert\boldsymbol{c}^{\prime}-\boldsymbol{y}^{\prime}_{i}\right\rVert\right)$
$\displaystyle\phantom{00000}+\mathbb{1}\left(d(\boldsymbol{c},\partial
B_{i})<d\left(\boldsymbol{c}^{\prime},\partial
B_{i}\right)\right)\left(\left\lVert\boldsymbol{c}^{\prime}-\boldsymbol{y}^{\prime}_{i}\right\rVert^{\gamma}-\left\lVert\boldsymbol{c}-\boldsymbol{y}_{i}\right\rVert^{\gamma}\right)\bigg{)}$
$\displaystyle\leq
r_{1}L\eta\left(1\right)\bigg{(}\mathbb{1}\left(d(\boldsymbol{c},\partial
B_{i})\geq d\left(\boldsymbol{c}^{\prime},\partial
B_{i}\right)\right)\left(\left\lVert\boldsymbol{c}-\boldsymbol{y}^{\prime}_{i}\right\rVert^{\gamma}-\left\lVert\boldsymbol{c}^{\prime}-\boldsymbol{y}^{\prime}_{i}\right\rVert^{\gamma}\right)$
$\displaystyle\phantom{00000}+\mathbb{1}\left(d(\boldsymbol{c},\partial
B_{i})<d\left(\boldsymbol{c}^{\prime},\partial
B_{i}\right)\right)\left(\left\lVert\boldsymbol{c}^{\prime}-\boldsymbol{y}_{i}\right\rVert^{\gamma}-\left\lVert\boldsymbol{c}-\boldsymbol{y}_{i}\right\rVert^{\gamma}\right)\bigg{)}\leq
L\left\lVert\boldsymbol{c}-\boldsymbol{c}^{\prime}\right\rVert^{\gamma},$

where the last inequality is obtained by the fact that $r_{1}\leq
1/(2\eta(1)\max(1,L))$. If $i\neq j$, it means that $\boldsymbol{c}$ and
$\boldsymbol{c}^{\prime}$ does not belong to the same grid and we have

$\displaystyle d(\boldsymbol{c},\partial
B_{i})\leq\left\lVert\boldsymbol{c}-\boldsymbol{c}^{\prime}\right\rVert,\quad\quad\text{and}\quad\quad
d(\boldsymbol{c}^{\prime},\partial
B_{j})\leq\left\lVert\boldsymbol{c}-\boldsymbol{c}^{\prime}\right\rVert.$

Consequently, we can write

$\displaystyle|f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})-f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c}^{\prime})|$
$\displaystyle\leq
r_{1}L\eta\left(1\right)\left(d^{\gamma}\left(\boldsymbol{c},\partial
B_{i}\right)+d^{\gamma}\left(\boldsymbol{c}^{\prime},\partial
B_{i}\right)\right)\leq
L\left\lVert\boldsymbol{c}-\boldsymbol{c}^{\prime}\right\rVert^{\gamma},$

where the last inequality is due to $r_{1}\leq 1/(2\eta(1)\max(1,L)).$

Fixing $\boldsymbol{c}\in[0,1]^{p}$, we calculate
$\nabla_{\boldsymbol{x}}^{2}f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\cdot,\boldsymbol{c})$.
Let
$\left(\nabla^{2}_{\boldsymbol{x}}f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})\right)_{i,j}$
indicate the $(i,j)$ entry of the Hessian matrix. For $1\leq i\neq j\leq
K^{p}$ it is straightforward to check that

$\left(\nabla^{2}_{\boldsymbol{x}}f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})\right)_{i,j}=0.$

Now, for $i=j=1$, we have

$\displaystyle|\left(\nabla^{2}_{\boldsymbol{x}}f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})\right)_{1,1}-2\alpha|\leq
r_{1}L\delta^{-\gamma}\max_{x\in\mathbb{R}}|\nabla^{2}_{x}\eta\left(x\right)|\sum_{j=1}^{K^{p}}d^{\gamma}(\boldsymbol{c},\partial
B_{j})\mathbb{1}\left(\boldsymbol{c}\in B_{j}\right)\leq\alpha,$

for $r_{1}\leq\alpha/\left(L^{\prime}\max\left(1,L\right)\right),$ where we
introduced
$L^{\prime}=\max_{x\in\mathbb{R}}|\eta^{\prime\prime}\left(x\right)|$.
Furthermore, for $i=j>1$, we can write

$\displaystyle|\left(\nabla^{2}_{\boldsymbol{x}}f_{\boldsymbol{\omega},\boldsymbol{\tau}}(\boldsymbol{x},\boldsymbol{c})\right)_{i,i}-2\alpha|\leq
r_{2}\max_{x\in\mathbb{R}}|\nabla^{2}_{x}\eta\left(x\right)|\leq\alpha,$

for $r_{2}\leq\alpha/L^{\prime}$. Finally, to show that
$|f(\boldsymbol{x},\boldsymbol{c})|\leq M$ for all $\boldsymbol{x}\in\Theta$
and $\boldsymbol{c}\in[0,1]^{p}$, we have

$\displaystyle|f(\boldsymbol{x},\boldsymbol{c})|\leq\alpha+r_{1}L\eta(1)+r_{2}\eta(1)\leq
M.$

∎

######  Lemma 11.

For any $\boldsymbol{c}\in B_{j}$ we have

$d(\boldsymbol{c},\partial B_{j})\leq\frac{1}{2K},$ (45)

and, for any $\varepsilon\in(0,1)$,

$\left\lVert\boldsymbol{c}-\boldsymbol{b}_{j}\right\rVert_{\infty}\leq\frac{\varepsilon}{2K}\quad\Longrightarrow\quad
d(\boldsymbol{c},\partial B_{j})\geq\frac{1-\varepsilon}{2K},$ (46)

where $\left\lVert\cdot\right\rVert_{\infty}$ is the $\ell_{\infty}$ norm.

###### Proof.

Without loss of generality, we assume throughout the proof that $K=1$ and
$\boldsymbol{b}_{j}=0$, so that the closure of $B_{j}$ is $[-1/2,1/2]^{d}$ and
$\partial
B_{j}=\\{\boldsymbol{u}:\left\lVert\boldsymbol{u}\right\rVert_{\infty}=1/2\\}$.
Inequality (45) follows from the fact that $d(\boldsymbol{c},\partial
B_{j})\leq d(\boldsymbol{c},\boldsymbol{c}^{\prime})\leq{1}/{2}$, where
$\boldsymbol{c}^{\prime}\in\partial B_{j}$ is a vector such that all its
coordinates except the first one coincide with those of $\boldsymbol{c}$, and
the first coordinate $c^{\prime}_{1}$ of $\boldsymbol{c}^{\prime}$ is equal to
the projection of the first coordinate $c_{1}\in[-1/2,1/2]$ of
$\boldsymbol{c}$ onto the set $\\{-1/2,1/2\\}$.

In order to prove (46), we denote by $\boldsymbol{u}^{*}$ a solution of the
problem

$\min_{\boldsymbol{u}:\left\lVert\boldsymbol{u}\right\rVert_{\infty}=1/2}\left\lVert\boldsymbol{c}-\boldsymbol{u}\right\rVert.$

There exists $i^{*}$ such that $|u_{i^{*}}^{*}|=1/2$, where $u_{i^{*}}^{*}$ is
the $i^{*}$th coordinate of $\boldsymbol{u}^{*}$. Under the assumption that
$\left\lVert\boldsymbol{c}\right\rVert_{\infty}\leq\varepsilon/2$ we have

$d^{2}(\boldsymbol{c},\partial
B_{j})=\left\lVert\boldsymbol{c}-\boldsymbol{u}^{*}\right\rVert^{2}\geq|c_{i^{*}}-u_{i^{*}}^{*}|^{2}\geq\min(|c_{i^{*}}-1/2|^{2},|c_{i^{*}}+1/2|^{2})\geq\Big{(}\frac{1-\varepsilon}{2}\Big{)}^{2}.$

This proves (46).

∎

##  Appendix D General comments on self-concordant barriers

In [36, Proposition 2.3.6], the authors demonstrated the existence of a convex
body $\Theta$ such that any $\mu$-self-concordant barrier over $\Theta$ should
have $\mu\geq d$. The proposition is stated as follows:

Statement of [36, Proposition 2.3.6]: Let $\Theta\in\mathbb{R}^{d}$ be a
convex polytope, such that certain boundary points of $\Theta$ belong to $m$
of $(d-1)$-dimensional facets of $\Theta$, where $m\in[d]$. Moreover, assume
that the normal vectors to these facets are linearly independent. Then the
value of $\mu$ for any $\mu$-self-concordant barrier on $\Theta$ cannot be
less than $m$. In particular, the $d$-dimensional non-negative orthant,
simplex, and hyper-cube do not admit barriers with the parameter less than
$\mu$.

For the case when $\Theta$ is a polytope, one can construct the following
self-concordant barrier [35, Corollary 3.1.1]

  * •

$\mathcal{R}(\boldsymbol{u})=-\sum_{j=1}^{m}\log(\langle\boldsymbol{a}_{j},\boldsymbol{u}\rangle-
b_{j})$ is an $m$-self-concordant barrier for the polytope

$\Theta=\\{\boldsymbol{u}\in\mathbb{R}^{d}:\langle\boldsymbol{a}_{j},\boldsymbol{u}\rangle\geq
b_{j},\quad\text{for
}j\in[m]\quad\text{and}\quad\boldsymbol{a}_{j}\in\mathbb{R}^{d},b_{j}\in\mathbb{R}\\}.$

Note that in the above, if $\Theta$ is the $d$-dimensional hyper-cube then
$m=2d$, and in this case [36, Proposition 2.3.6] indicates that the above
$\mathcal{R}$ has an optimal $\mu$ as a function of $d$. Moreover, if $\Theta$
is the $d$-dimensional simplex then $m=d+1$, which again by [36, Proposition
2.3.6] we can see that the above example of $\mathcal{R}$ has an optimal $\mu$
as a function of $d$.

For the case when $\Theta$ is scaled version of the unit Euclidean ball with
ratio $r>0$, one can consider the following self-concordant barrier [35,
Example 9.3.2]

  * •

$\mathcal{R}(\boldsymbol{u})=-\log(r^{2}-\left\lVert\boldsymbol{u}\right\rVert^{2})$
is a $2$-self-concordant barrier for $\Theta$.

Considering the result in [36, Corollary 2.3.3], we have always that $\mu\geq
1$ which shows the optimality of the above $\mathcal{R}$ for the unit
Euclidean ball.

We refer the reader to [35, Chapter 9] for further examples of self-concordant
barrier functions.

In the general case of a convex body $\Theta$, [11, 22, 17], proposed
$\mu$-self-concordant barriers with $\mu\leq\texttt{A}d$, where $\texttt{A}>0$
is a non-increasing function of $d$. Particularly, [11, Theorem 1] shows that
$\texttt{A}\leq 1+100\sqrt{\log(d)/d}$, for all $d\geq 80$. All of these
constructions by [11, 22, 17] are computationally expensive (see [11, Section