# A gradient estimator via L1-randomization for online zero-order optimization
with two point feedback

Arya Akhavan
Istituto Italiano di Tecnologia
CREST, ENSAE, IP Paris
<EMAIL_ADDRESS>&Evgenii Chzhen
Université Paris-Saclay, CNRS
Laboratoire de mathématiques d’Orsay
<EMAIL_ADDRESS>Massimiliano Pontil
Istituto Italiano di Tecnologia
University College London
<EMAIL_ADDRESS>&Alexandre B. Tsybakov
CREST, ENSAE, IP Paris
<EMAIL_ADDRESS>
###### Abstract

This work studies online zero-order optimization of convex and Lipschitz
functions. We present a novel gradient estimator based on two function
evaluations and randomization on the $\ell_{1}$-sphere. Considering different
geometries of feasible sets and Lipschitz assumptions we analyse online dual
averaging algorithm with our estimator in place of the usual gradient. We
consider two types of assumptions on the noise of the zero-order oracle:
canceling noise and adversarial noise. We provide an anytime and completely
data-driven algorithm, which is adaptive to all parameters of the problem. In
the case of canceling noise that was previously studied in the literature, our
guarantees are either comparable or better than state-of-the-art bounds
obtained by Duchi et al., [14] and Shamir, [33] for non-adaptive algorithms.
Our analysis is based on deriving a new weighted Poincaré type inequality for
the uniform measure on the $\ell_{1}$-sphere with explicit constants, which
may be of independent interest.

##  1 Introduction

In this work we study the problem of convex online zero-order optimization
with two-point feedback, in which adversary fixes a sequence
$f_{1},f_{2},\ldots:\mathbb{R}^{d}\to\mathbb{R}$ of convex functions and the
goal of the learner is to minimize the cumulative regret with respect to the
best action in a prescribed convex set $\Theta\subseteq\mathbb{R}^{d}$. This
problem has received significant attention in the context of continuous
bandits and online optimization [see e.g., 1, 16, 29, 12, 18, 33, 13, 3, 25,
21, and references therein].

We consider the following protocol: at each round $t=1,2,\ldots$ the algorithm
chooses
$\boldsymbol{x}_{t}^{\prime},\boldsymbol{x}_{t}^{\prime\prime}\in\mathbb{R}^{d}$
(that can be queried outside of $\Theta$) and the adversary reveals

$\displaystyle
f_{t}(\boldsymbol{x}_{t}^{\prime})+\xi_{t}^{\prime}\qquad\text{and}\qquad
f_{t}(\boldsymbol{x}_{t}^{\prime\prime})+\xi_{t}^{\prime\prime}\enspace,$

where $\xi^{\prime}_{t},\xi^{\prime\prime}_{t}\in\mathbb{R}$ are the noise
variables (random or not) to be specified. Based on the above information and
the previous rounds, the learner outputs $\boldsymbol{x}_{t}\in\Theta$ and
suffers loss $f_{t}(\boldsymbol{x}_{t})$. The goal of the learner is to
minimize the cumulative regret

$\displaystyle\sum_{t=1}^{T}f_{t}(\boldsymbol{x}_{t})-\min_{\boldsymbol{x}\in\Theta}\sum_{t=1}^{T}f_{t}(\boldsymbol{x})\enspace.$

At the core of our approach is a novel zero-order gradient estimator based on
two function evaluations outlined in Algorithm 1. A key novelty of our
estimator is that it employs a randomization step over the $\ell_{1}$ sphere.
This is in contrast to most of the prior work [see e.g., 22, 28, 16, 1, 32,
14, 5, 17, 3, 4] that was employing $\ell_{2}$ or $\ell_{\infty}$ type
randomizations to define
$\boldsymbol{x}^{\prime}_{t},\boldsymbol{x}^{\prime\prime}_{t}$. We use the
proposed estimator within an online dual averaging procedure to tackle the
zero-order online convex optimization problem, matching or improving the
state-of-the-art results. Duchi et al., [14] and Shamir, [33] have studied
instances of the above problem under the assumption that
$\xi^{\prime}_{t}=\xi^{\prime\prime}_{t}$, which we will further refer to as
canceling noise assumption. Specifically, [14] considered the stochastic
optimization framework where $f_{t}=f$, for every $t$, and obtained bounds on
the optimization error rather than on cumulative regret, while [33] analyzed
the case $\xi^{\prime}_{t}=\xi^{\prime\prime}_{t}=0$. The results in [14, 33]
are obtained for the objective functions that are Lipschitz with respect to
the $\ell_{q}$-norm for $q=1$ and $q=2$, although, with extra derivations it
is possible to extend the above mentioned results beyond such cases. The
proposed method allows us to improve upon these results in several aspects.

Contributions.  The contributions of the present paper can be summarized as
follows. 1) We present a new randomized zero-order gradient estimator and
study its statistical properties, both under canceling noise and under
adversarial noise (see Lemma 1 and Lemma 4); 2) In the canceling noise case
($\xi^{\prime}_{t}=\xi^{\prime\prime}_{t}$) in Theorem 1 we show that dual
averaging based on our gradient estimator either improves or matches the
state-of-the-art bounds [14, 33]. We derive the results for Lipschitz
functions with respect to all $\ell_{q}$-norms, $q\in[1,\infty]$. In
particular, when $q=1$ and $\Theta$ is the probability simplex, our bound is
better by a $\sqrt{\log(d)}$ factor than that of [14, 33]; 3) We propose a
completely data-driven and anytime version of the algorithm, which is adaptive
to all parameters of the problem. We show that it achieves analogous
performance as the non-adaptive algorithm in the case of canceling noise and
only slightly worse performance under adversarial noise. To the best of our
knowledge, no adaptive algorithms were developed for zero-order online
problems in our setting so far; 4) As a key element of our analysis, we derive
in Lemma 3 a weighted Poincaré type inequality [following the terminology of
10] with explicit constants for the uniform measure on $\ell_{1}$-sphere. This
result may be of independent interest.

Notation.  Throughout the paper we use the following notation. We denote by
$\left\lVert\cdot\right\rVert_{p}$ the $\ell_{p}$-norm in $\mathbb{R}^{d}$.
For any $\boldsymbol{x}\in\mathbb{R}^{d}$ we denote by
$\boldsymbol{x}\mapsto\operatorname*{sign}(\boldsymbol{x})$ the component-wise
sign function (defined at $0$ as $1$). We let $\langle\cdot,\cdot\rangle$ be
the standard inner product in $\mathbb{R}^{d}$. For $p\in[1,\infty]$ we
introduce the open $\ell_{p}$-ball and $\ell_{p}$-sphere respectively as

$\displaystyle
B^{d}_{p}\triangleq\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\,:\,\left\lVert\boldsymbol{x}\right\rVert_{p}<1\right\\}\qquad\text{and}\qquad\partial
B^{d}_{p}\triangleq\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\,:\,\left\lVert\boldsymbol{x}\right\rVert_{p}=1\right\\}\enspace.$

For two $a,b\in\mathbb{R}$, we denote by $a\wedge b$ (_resp._ $a\vee b$) the
minimum (_resp._ the maximum) between $a$ and $b$. We denote by
$\Gamma:(0,\infty)\to\mathbb{R}$, the gamma function. In what follows, $\log$
always stands for the natural logarithm and $e$ is Euler’s number.

##  2 The algorithm

Let $\Theta$ be a closed convex subset of $\mathbb{R}^{d}$ and let
$V:\Theta\to\mathbb{R}$ be a convex function. The procedure that we propose in
this paper is summarized in Algorithm 1.

Input: Convex function $V(\cdot)$, step size $\eta_{1}>0$, and parameters
$h_{t}$, for $t=1,2,\ldots,$

Initialization: Generate independently vectors
$\boldsymbol{\zeta}_{1},\boldsymbol{\zeta}_{2},\ldots$ uniformly distributed
on $\partial B^{d}_{1}$, and set $\boldsymbol{z}_{1}=\boldsymbol{0}$

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

$\boldsymbol{x}_{t}=\operatorname*{arg\,max}_{\boldsymbol{x}\in\Theta}\left\\{\eta_{t}\left\langle\boldsymbol{z}_{t},\,\boldsymbol{x}\right\rangle-V(\boldsymbol{x})\right\\}$

$y_{t}^{\prime}=f_{t}(\boldsymbol{x}_{t}+h_{t}\boldsymbol{\zeta}_{t})+\xi_{t}^{\prime}\quad$
and $\quad
y_{t}^{\prime\prime}=f_{t}(\boldsymbol{x}_{t}-h_{t}\boldsymbol{\zeta}_{t})+\xi_{t}^{\prime\prime}$

// Query

$\boldsymbol{g}_{t}=\frac{d}{2h_{t}}(y_{t}^{\prime}-y_{t}^{\prime\prime})\operatorname*{sign}(\boldsymbol{\zeta}_{t})$

// $\ell_{1}$-gradient estimate

$\boldsymbol{z}_{t+1}=\boldsymbol{z}_{t}-\boldsymbol{g}_{t}$

// Update $\boldsymbol{z}_{t}$

update the step-size $\eta_{t+1}$

end for

Algorithm 1 Zero-Order $\ell_{1}$-Randomized Online Dual Averaging

Intuition behind the gradient estimate.  The form of gradient estimator
$\boldsymbol{g}_{t}$ in Algorithm 1 is explained by Stokes’ theorem (see
Theorem 5 in the appendix and the discussion that follows). Stokes’ theorem
provides a connection between the gradient of a function $f$ (first order
information) and $f$ itself (zero order information). Under some regularity
conditions, it establishes that

$\displaystyle\int_{D}\nabla
f(\boldsymbol{x})\,\mathrm{d}\boldsymbol{x}=\int_{\partial
D}f(\boldsymbol{x})\boldsymbol{n}(\boldsymbol{x})\,\mathrm{d}S(\boldsymbol{x})\enspace,$

where $\partial D$ is the boundary of $D$, $\boldsymbol{n}$ is the outward
normal vector to $\partial D$, and $\,\mathrm{d}S(\boldsymbol{x})$ denotes the
surface measure. Introducing $\boldsymbol{U}^{D}$ and
$\boldsymbol{\zeta}^{\partial D}$ distributed uniformly on $D$ and $\partial
D$ respectively, we can rewrite the above identity as

$\displaystyle\mathbf{E}[\nabla
f(\boldsymbol{U}^{D})]=\frac{\operatorname{Vol}_{d-1}(\partial
D)}{\operatorname{Vol}_{d}(D)}\cdot\mathbf{E}[f(\boldsymbol{\zeta}^{\partial
D})\boldsymbol{n}(\boldsymbol{\zeta}^{\partial D})]\enspace,$

where $\operatorname{Vol}_{d-1}(\partial D)$ is the surface area of $D$ and
$\operatorname{Vol}_{d}(D)$ is its volume. In what follows we consider the
special case $D=B^{d}_{1}$. For this choice of $D$ we have
$\boldsymbol{n}(\boldsymbol{x})=\tfrac{1}{\sqrt{d}}\cdot\operatorname*{sign}(\boldsymbol{x})$
with $\operatorname{Vol}_{d-1}(\partial D)/\operatorname{Vol}_{d}(D)=d^{3/2}$
leading to our gradient estimate for the two-point feedback setup.

Computational aspects. Let us highlight two appealing practical features of
the $\ell_{1}$-randomized gradient estimator $\boldsymbol{g}_{t}$ in Algorithm
1. First, we can easily evaluate any $\ell_{p}$-norm of $\boldsymbol{g}_{t}$.
Indeed, it holds that
$\|\boldsymbol{g}_{t}\|_{p}=(d^{1+1/p}/{2h_{t}})|y_{t}^{\prime}-y_{t}^{\prime\prime}|$,
i.e., computing $\|\boldsymbol{g}_{t}\|_{p}$ only requires $O(1)$ elementary
operations. Second, this gradient estimator is very economic in terms of the
required memory: in order to store $\boldsymbol{g}_{t}$ we only need $d$ bits
and $1$ float. None of these properties is inherent to the popular
alternatives based on the randomization over the $\ell_{2}$-sphere [see e.g.,
22, 16, 5] or on Gaussian randomization [see e.g., 23, 24, 19].
To compute $\boldsymbol{g}_{t}$ one needs to generate $\boldsymbol{\zeta}_{t}$
distributed uniformly on $\partial B_{1}^{d}$. The most straightforward way to
do it consists in first generating a $d$-dimensional vector of i.i.d. centered
scaled Laplace random variables and then normalizing this vector by its
$\ell_{1}$-norm. The result is guaranteed to follow the uniform distribution
on $\partial B_{d}^{1}$ [see e.g., 30, Lemma 1]. Furthermore, to sample from
the centered scaled Laplace distribution one can simply use inverse transform
sampling. Indeed, if $U$ is distributed uniformly on $(0,1)$, then
$\log(2U){\bf 1}{\left(U>1/2\right)}-\log(2-2U){\bf 1}{\left(U\geq
1/2\right)}$ follows centered scaled Laplace distribution.

##  3 Assumptions

We say that the convex function $V(\cdot)$ is $1$-strongly convex with respect
to the $\ell_{p}$-norm on $\Theta$ if

$\displaystyle V(\boldsymbol{x}^{\prime})\geq
V(\boldsymbol{x})+\left\langle\boldsymbol{w},\,\boldsymbol{x}^{\prime}-\boldsymbol{x}\right\rangle+\frac{1}{2}\|\boldsymbol{x}-\boldsymbol{x}^{\prime}\|_{p}^{2}\enspace,$

for all $\boldsymbol{x},\boldsymbol{x}^{\prime}\in\Theta$ and all
$\boldsymbol{w}\in\partial V(\boldsymbol{x})$, where $\partial
V(\boldsymbol{x})$ is the subdifferential of $V$ at point $\boldsymbol{x}$.

Throughout the paper, we assume that $p,q\in[1,\infty]$, $d\geq 3$, and set
$p^{*},q^{*}\in[1,\infty]$ such that $\tfrac{1}{p}+\tfrac{1}{p^{*}}=1$ and
$\tfrac{1}{q}+\tfrac{1}{q^{*}}=1$, with the usual convention $1/\infty=0$. We
will use the following assumptions.

######  Assumption 1.

The following conditions hold:

  1. 1.

The set $\Theta\subset\mathbb{R}^{d}$ is compact and convex.

  2. 2.

There exists $V:\Theta\to\mathbb{R}$, which is lower semi-continuous,
$1$-strongly convex on $\Theta$ w.r.t. the $\ell_{p}$-norm and such that

$\sup_{\boldsymbol{x}\in\Theta}V(\boldsymbol{x})-\inf_{\boldsymbol{x}\in\Theta}V(\boldsymbol{x})\leq
R^{2}$

for some constant $R>0$.

  3. 3.

Each function $f_{t}:\mathbb{R}^{d}\to\mathbb{R}$ is convex on
$\mathbb{R}^{d}$ for all $t\geq 1$.

  4. 4.

For all $\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathbb{R}^{d}$, and all
$t\geq 1$ we have $|f_{t}(\boldsymbol{x})-f_{t}(\boldsymbol{x}^{\prime})|\leq
L\|\boldsymbol{x}-\boldsymbol{x}^{\prime}\|_{q}$ for some constant $L>0$.

Assumption 1 is rather standard in the study of dual averaging-type algorithms
and have been previously considered in the context of zero-order problems in
[14, 33]. We assume that $\Theta$ is compact as we are interested in the
worst-case regret, which ensures that $R<+\infty$. We discuss extensions of
our results to the case of unbounded $\Theta$ in Section 8. Note that the
constant $R>0$ is not necessarily dimension independent. Below we provide two
classical examples of $V$ [see e.g., 31, Section 2].

######  Example 1.

Let $\Theta$ be any convex subset of $\mathbb{R}^{d}$ and $p\in(1,2]$. Then,
$V(\boldsymbol{x})=\tfrac{1}{2(p-1)}\|\boldsymbol{x}\|_{p}^{2}$ is
$1$-strongly convex on $\Theta$ w.r.t. the $\ell_{p}$-norm.

######  Example 2.

Let
$\Theta=\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\,:\,\|\boldsymbol{x}\|_{1}=1\,,\,\,\,\,\boldsymbol{x}\geq
0\right\\}$. Then111We use the convention that $0\log(0)=0$.,
$V(\boldsymbol{x})=\sum_{j=1}^{d}x_{j}\log(x_{j})$ is $1$-strongly convex on
$\Theta$ w.r.t. the $\ell_{1}$-norm and $R^{2}\leq\log(d)$.

Assumptions on the noise.  We consider two different assumptions on the noises
$\xi^{\prime}_{t},\xi_{t}^{\prime\prime}$. The first noise assumption is
common in the stochastic optimization context [see e.g., 14, 33, 19, 23, 24].

######  Assumption 2 (Canceling noise).

For all $t=1,2,\ldots$, it holds that
$\xi_{t}^{\prime}=\xi_{t}^{\prime\prime}$ almost surely.

Formally, Assumption 2 permits noisy evaluations of function values. However,
due to the fact that we are allowed to query $f_{t}$ at two points, taking
difference of $y_{t}^{\prime}$ and $y_{t}^{\prime\prime}$ in the estimator of
the gradient effectively erases the noise. It results in a smaller variance of
our gradient estimator. Importantly, Assumption 2 covers the case of no noise,
that is, the classical online optimization setting as defined, e.g., in [31].

Second, we consider an adversarial noise assumption, which is essentially
equivalent to the assumptions used in [3, 4].

######  Assumption 3 (Adversarial noise).

For all $t=1,2,\ldots$, it holds that: (i)
$\mathbf{E}[(\xi_{t}^{\prime})^{2}]\leq\sigma^{2}$ and
$\mathbf{E}[(\xi_{t}^{\prime\prime})^{2}]\leq\sigma^{2}$; (ii)
$(\xi_{t}^{\prime})_{t\geq 1}$ and $(\xi_{t}^{\prime\prime})_{t\geq 1}$ are
independent of $(\boldsymbol{\zeta}_{t})_{t\geq 1}$

Assumption 3 allows for stochastic $\xi_{t}^{\prime}$ and
$\xi_{t}^{\prime\prime}$ that are not necessarily zero-mean or independent
over the trajectory. Furthermore, it permits bounded non-stochastic
adversarial noises. Part (ii) of Assumption 3 is always satisfied. Indeed,
$\xi_{t}^{\prime}$’s and $\xi_{t}^{\prime\prime}$’s are coming from the
environment and are unknown to the learner while $\boldsymbol{\zeta}_{t}$’s
are artificially generated by the learner. We mention part (ii) only for
formal mathematical rigor.

Note that, since the choice of function $V$ belongs to the learner and
$\Theta$ is given, it is always reasonable to assume that parameter $R$ is
known. At the same time, parameters $L$ and $\sigma$ may be either known or
unknown. We will study both cases in the next sections.

##  4 Upper bounds on the regret

In this section, we present the main convergence results for Algorithm 1 when
$L,\sigma,T$ are known to the learner. The case when they are unknown is
analyzed in Section 5, where we develop fully adaptive versions of Algorithm
1.

To state our results in a unified way, we introduce the following sequence
that depends on the dimension $d$ and on the norm index $q\geq 1$:

$\displaystyle\mathrm{b}_{q}(d)\triangleq\frac{1}{d+1}\cdot\begin{dcases}qd^{\frac{1}{q}}&\text{if
}q\in[1,\log(d)),\\\ e\log(d)&\text{if }q\geq\log(d).\end{dcases}$

The value $\mathrm{b}_{q}(d)$ will explicitly influence the choice of the step
size $\eta>0$ and of the discretization parameter $h>0$.

The first result of this section establishes the convergence guarantees under
the canceling noise assumption. This case was previously considered by Duchi
et al., [14] and Shamir, [33].

######  Theorem 1.

Let Assumptions 1 and 2 be satisfied. Then, Algorithm 1 with the parameters

$\displaystyle\eta=\frac{\texttt{A}R}{L}\sqrt{\frac{d^{-1-\frac{2}{{q\wedge
2}}+\frac{2}{p}}}{T}}\quad\text{and any}\quad
h\leq\frac{7R}{100\mathrm{b}_{q}(d)\sqrt{T}}d^{\frac{1}{2}+\frac{1}{q\wedge
2}-\frac{1}{p}}\enspace,$

where $\texttt{A}=(\sqrt{6}+\sqrt{12})^{-1}$, satisfies, for any
$\boldsymbol{x}\in\Theta$,

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]\leq
11.9\cdot RL\sqrt{Td^{1+\frac{2}{q\wedge 2}-\frac{2}{p}}}\enspace.$

Note that, as in other related works [14, 33, 20, 23, 24], under the canceling
noise (or no noise) assumption the discretization parameter $h>0$ can be
chosen arbitrary small. This is due to the fact that, under the canceling
noise assumption, the variance of the gradient estimate $\boldsymbol{g}_{t}$
is bounded by a constant independent of $h$. It is no longer the case under
the adversarial noise assumption as exhibited in the next theorem.

######  Theorem 2.

Let Assumptions 1 and 3 be satisfied. Then Algorithm 1 with the parameters

$\displaystyle\eta=\frac{R}{\sqrt{TL}}\left(\frac{\sigma\mathrm{b}_{q}(d)}{\sqrt{2}R}\sqrt{Td^{4-\frac{2}{p}}}{+}\texttt{A}Ld^{1+\frac{2}{{q\wedge
2}}-\frac{2}{p}}\right)^{-\frac{1}{2}}\quad\text{and}\quad
h=\left(\frac{\sqrt{2}R\sigma}{L\mathrm{b}_{q}(d)}\right)^{\frac{1}{2}}T^{-\frac{1}{4}}d^{1-\frac{1}{2p}}\enspace,$

where $\texttt{A}=6(1{+}\sqrt{2})^{2}$, satisfies, for any
$\boldsymbol{x}\in\Theta$,

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]\leq
11.9$ $\displaystyle\cdot RL\sqrt{Td^{1+\frac{2}{{q\wedge 2}}-\frac{2}{p}}}$
$\displaystyle+$
$\displaystyle\,\,2.4\cdot\sqrt{RL\sigma}T^{\frac{3}{4}}\cdot\begin{dcases}\sqrt{qd^{1+\frac{1}{q}-\frac{1}{p}}}&\text{if
}q\in[1,\log(d)),\\\ \sqrt{e\log(d)d^{1-\frac{1}{p}}}&\text{if
}q\geq\log(d).\end{dcases}$

Comparison to state-of-the-art bounds.  We provide two examples of
$p,q,\Theta$ and compare results for our new method to those of [14, 33] where
only the canceling noise Assumption 2 and $q\in\\{1,2\\}$ were considered.

######  Corollary 1.

Let $p=q=2$ and $\Theta=B^{d}_{2}$. Then under Assumption 2, Algorithm 1 with
$V:\Theta\to\mathbb{R}$ defined in Example 1, satisfies

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]\leq
11.9\cdot L\sqrt{dT}\enspace.$

In the setup of Corollary 1, Duchi et al., [14] obtain $O(L\sqrt{dT\log(d)})$
rate and Shamir, [33] exhibits $O(L\sqrt{dT})$, which is the optimal rate.
Both results do not specify the leading absolute constants.

######  Corollary 2.

Let $p=q=1$ and
$\Theta=\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\,:\,\boldsymbol{x}\geq
0,\,\,\|\boldsymbol{x}\|_{1}=1\right\\}$. Then under Assumption 2, Algorithm 1
with $V:\Theta\to\mathbb{R}$ defined in Example 2, satisfies

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]\leq
11.9\cdot L\sqrt{dT\log(d)}\enspace.$

In the setup of Corollary 2, Shamir, [33] proves the rate
$O(L\sqrt{dT}\log(d))$ for the method with $\ell_{2}$-randomization. On the
other hand, Duchi et al., [14] derived a lower bound
$\Omega(\sqrt{dT/\log(d)})$. Thus, our algorithm further reduces the gap
between the upper and the lower bounds.

Finally, note that in the case $p=1$, $q=2$ with $V:\Theta\to\mathbb{R}$
defined in Example 2 the bound of Theorem 1 is of the order
$O(\sqrt{T\log(d)})$. This case was handled by an algorithm with
$\ell_{1}$-randomization slightly different from ours in [18] leading to the
suboptimal rate $O(\sqrt{dT\log(d)})$.

##  5 Adaptive algorithms

Theorems 1 and 2 used the step size $\eta$ and the discretization parameter
$h$ that depend on the potentially unknown quantities $L$, $\sigma$, and the
optimization horizon $T$. In this section, we show that, under the canceling
noise Assumption 2, adaptation to unknown $L$ comes with nearly no price. On
the other hand, under the adversarial noise Assumption 3, our adaptive rate
has a slightly worse dependence on $L$ and $\sigma$ in the dominant term. The
proof is based on combining the adaptive scheme for online dual averaging [see
Section 7.13 in 26, for an overview] with our bias and variance evaluations,
cf. Section 6 below.

######  Theorem 3.

Let Assumptions 1 and 2 be satisfied. Then, Algorithm 1 with the
parameters222We adopt the convention that $\eta_{1}=1$ and $1/0=1$ in the
definition of $\eta_{t}$.

$\displaystyle\eta_{t}=\frac{R}{\sqrt{2.75\cdot\sum_{k=1}^{t-1}\left\lVert\boldsymbol{g}_{k}\right\rVert^{2}_{p^{*}}}}\quad\text{and
any}\quad
h_{t}\leq\frac{7R}{200\mathrm{b}_{q}(d)\sqrt{t}}d^{\frac{1}{2}+\frac{1}{q\wedge
2}-\frac{1}{p}}\enspace,$

satisfies for any $\boldsymbol{x}\in\Theta$

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]\leq
110.6\cdot RL\sqrt{Td^{1+\frac{2}{q\wedge 2}-\frac{2}{p}}}\enspace.$

The above result gives, up to an absolute constant, the same convergence rate
as that of the non-adaptive Theorem 1. In other words, the price for adaptive
algorithm does not depend on the parameters of the problem. Finally, we derive
an adaptive algorithm under Assumption 3.

######  Theorem 4.

Let Assumptions 1 and 3 be satisfied. Then, Algorithm 1 with the parameters

$\displaystyle\eta_{t}=\frac{R}{\sqrt{2.75\cdot\sum_{k=1}^{t-1}\left\lVert\boldsymbol{g}_{k}\right\rVert^{2}_{p^{*}}}}\quad\text{and
any}\quad
h_{t}=\left(6.65\sqrt{6}\cdot\frac{R}{\mathrm{b}_{q}(d)}\right)^{\frac{1}{2}}t^{-\frac{1}{4}}d^{1-\frac{1}{2p}}\enspace,$

satisfies for any $\boldsymbol{x}\in\Theta$

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]\leq
110.6$ $\displaystyle\cdot RL\sqrt{Td^{1+\frac{2}{{q\wedge 2}}-\frac{2}{p}}}$
$\displaystyle+5.9\cdot\sqrt{R}\left(\sigma{+}L\right)T^{\frac{3}{4}}\cdot\begin{dcases}\sqrt{qd^{1+\frac{1}{q}-\frac{1}{p}}}&\text{if
}q\in[1,\log(d))\\\ \sqrt{e\log(d)d^{1-\frac{1}{p}}}&\text{if
}q\geq\log(d)\end{dcases}\enspace.$

Note that the bound of Theorem 4 has a less advantageous dependency on
$\sigma$ and $L$ compared to Theorem 2, where we had $\sqrt{\sigma L}$ instead
of $\sigma+L$. We remark that if $\sigma$ is known but $L$ is unknown, one can
recover the $\sqrt{\sigma L}$ dependency by selecting $h_{t}$ depending on
$\sigma$. We do not state this result that can be derived in a similar way and
favor here only the fully adaptive version.

##  6 Elements of proofs

In this section, we outline major ingredients for the proofs of Theorems 1 –
4. The full proofs can be found in Appendix C. Here, we only focus on novel
elements without reproducing the general scheme of online dual averaging
analysis [see e.g., 31, 26]. Namely, we highlight two key facts, which are the
smoothing lemma (Lemma 1) and the weighted Poincaré type inequality for the
uniform measure on $\partial B_{1}^{d}$ (Lemma 3) used to control the
variance.

###  6.1 Bias and smoothing lemma

First, as in the prior work that was using smoothing ideas [see e.g., 22, 16,
33], we show that our gradient estimate $\boldsymbol{g}_{t}$ is an unbiased
estimator of a surrogate version of $f_{t}$ and establish its approximation
properties.

######  Lemma 1 (Smoothing lemma).

Fix $h>0$ and $q\in[1,\infty]$. Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be an
$L$-Lipschitz function w.r.t. the $\ell_{q}$-norm. Let $\boldsymbol{U}$ be
distributed uniformly on $B^{d}_{1}$ and $\boldsymbol{\zeta}$ be distributed
uniformly on $\partial B_{d}^{1}$. Let ${\sf
f}_{h}(\boldsymbol{x})\triangleq\mathbf{E}[f(\boldsymbol{x}+h\boldsymbol{U})]$
for $\boldsymbol{x}\in\mathbb{R}^{d}$. Then ${\sf f}_{h}$ is differentiable
and

$\displaystyle\mathbf{E}\left[\frac{d}{2h}\big{(}f(\boldsymbol{x}+h\boldsymbol{\zeta})-f(\boldsymbol{x}-h\boldsymbol{\zeta})\big{)}\operatorname*{sign}(\boldsymbol{\zeta})\right]=\nabla{\sf
f}_{h}(\boldsymbol{x})\enspace.$

Furthermore, we have for all $d\geq 3$ and all
$\boldsymbol{x}\in\mathbb{R}^{d}$,

$\displaystyle|{\sf
f}_{h}(\boldsymbol{x})-f(\boldsymbol{x})|\leq\mathrm{b}_{q}(d)Lh\enspace.$ (1)

Finally, if $\Theta\subset\mathbb{R}^{d}$ is convex, $f$ is convex in
$\Theta{+}hB_{1}^{d}$, then ${\sf f}_{h}$ is convex in $\Theta$ and ${\sf
f}_{h}(\boldsymbol{x})\geq f(\boldsymbol{x})$ for $\boldsymbol{x}\in\Theta$.

###### Proof.

There are three claims to prove. For the first one, we notice that
$\boldsymbol{\zeta}$ has the same distribution as $-\boldsymbol{\zeta}$,
hence,

$\displaystyle\mathbf{E}\left[\frac{d}{2h}\big{(}f(\boldsymbol{x}+h\boldsymbol{\zeta})-f(\boldsymbol{x}-h\boldsymbol{\zeta})\big{)}\operatorname*{sign}(\boldsymbol{\zeta})\right]=\mathbf{E}\left[\frac{d}{h}f(\boldsymbol{x}+h\boldsymbol{\zeta})\operatorname*{sign}(\boldsymbol{\zeta})\right]\enspace,$

and the first claim follows from Theorem 6 in the Appendix (a version of
Stokes’, or divergence, theorem) applied to
$g(\cdot)=f(\boldsymbol{x}+h\cdot)$ with observation that $\nabla
g(\cdot)=h\nabla f(\boldsymbol{x}+h\cdot)$ where $\nabla f$ is the gradient
defined almost everywhere and whose existence is ensured by the Rademacher
theorem.

We now prove the approximation property (1). Assuming $d\geq 3$ grants that
$\log(d)\geq 1$. Since $f$ is $L$-Lipschitz w.r.t. the $\ell_{q}$-norm we get
that, for any $\boldsymbol{x}\in\mathbb{R}^{d}$,

$\displaystyle|{\sf f}_{h}(\boldsymbol{x})-f(\boldsymbol{x})|\leq
Lh\,\mathbf{E}\|\boldsymbol{U}\|_{q}\enspace.$ (2)

If $q\in[1,\log(d))$ then (1) follows from Lemma 2. If $q\geq\log(d)$ then
using again Lemma 2 we find

$\displaystyle\mathbf{E}\|\boldsymbol{U}\|_{q}\leq\mathbf{E}\|\boldsymbol{U}\|_{\log(d)}\leq\frac{\log(d)d^{\frac{1}{\log(d)}}}{d+1}=\frac{e\log(d)}{d+1}\enspace,$

which together with (2) yields the desired bound.

Finally, if $f$ is convex in $\Theta+hB_{1}^{d}$, then for all
$\boldsymbol{x},\boldsymbol{x}^{\prime}\in\Theta$ and $\alpha\in[0,1]$ we have

$\displaystyle{\sf
f}_{h}(\alpha\boldsymbol{x}+(1-\alpha)\boldsymbol{x}^{\prime})=\mathbf{E}\bigg{[}f\big{(}\alpha(\boldsymbol{x}+h\boldsymbol{U})+(1-\alpha)(\boldsymbol{x}^{\prime}+h\boldsymbol{U})\big{)}\bigg{]}\leq\alpha{\sf
f}_{h}(\boldsymbol{x})+(1-\alpha){\sf
f}_{h}(\boldsymbol{x}^{\prime})\enspace.$

Thus ${\sf f}_{h}$ is indeed convex on $\Theta$. Furthermore, again by
convexity of $f$, we deduce that for any $\boldsymbol{x}\in\Theta$

$\displaystyle{\sf
f}_{h}(\boldsymbol{x})=\mathbf{E}[f(\boldsymbol{x}+h\boldsymbol{U})]\geq\mathbf{E}\left[f(\boldsymbol{x})+\left\langle\boldsymbol{w},\,h\boldsymbol{U}\right\rangle\right]=f(\boldsymbol{x})\quad\text{where
$\boldsymbol{w}\in\partial f(\boldsymbol{x})$}\,\,.$

The proof of Lemma 1 relies on the control of the $\ell_{q}$-norm of random
vector $\boldsymbol{U}$ established in the next result.

######  Lemma 2.

Let $q\in[1,\infty)$ and let $\boldsymbol{U}$ be distributed uniformly on
$B^{d}_{1}$. Then
$\mathbf{E}\|\boldsymbol{U}\|_{q}\leq\tfrac{qd^{\frac{1}{q}}}{d+1}$.

###### Proof.

Let $W_{1},\ldots,W_{d},W_{d+1}$ be i.i.d. random variables having the Laplace
distribution with mean $0$ and scale parameter $1$. Set
$\boldsymbol{W}=(W_{1},\ldots,W_{d})$. Then, following [6, Theorem 1] we have

$\displaystyle\boldsymbol{U}\stackrel{{\scriptstyle
d}}{{=}}\frac{\boldsymbol{W}}{\left\lVert\boldsymbol{W}\right\rVert_{1}+|W_{d+1}|}\enspace,$

where $\stackrel{{\scriptstyle d}}{{=}}$ denotes equality in distribution.
Furthermore, [30, Lemma 1] states that the random variables

$\displaystyle\frac{(\boldsymbol{W},|W_{d+1}|)}{\left\lVert\boldsymbol{W}\right\rVert_{1}+|W_{d+1}|}\qquad\text{and}\qquad\left\lVert\boldsymbol{W}\right\rVert_{1}+|W_{d+1}|\enspace,$

are independent. Hence, for any $q\in[1,\infty)$, it holds that

$\displaystyle\mathbf{E}\|\boldsymbol{U}\|_{q}=\frac{\mathbf{E}\|\boldsymbol{W}\|_{q}}{\mathbf{E}\|(\boldsymbol{W},W_{d+1})\|_{1}}=\frac{1}{d+1}\mathbf{E}\|\boldsymbol{W}\|_{q}\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{d+1}\bigg{(}\mathbf{E}\|\boldsymbol{W}\|_{q}^{q}\bigg{)}^{\frac{1}{q}}=\frac{d^{\frac{1}{q}}\Gamma^{\frac{1}{q}}(q+1)}{d+1}\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{qd^{\frac{1}{q}}}{d+1}\enspace,$

where $(a)$ follows from Jensen’s inequality and $(b)$ uses the fact that
$\Gamma^{1/q}(q{+}1)\leq q$ for $q\geq 1$. ∎

###  6.2 Variance and weighted Poincaré type inequality

We additionally need to control the squared $\ell_{p^{*}}$-norm of each
gradient estimator $\boldsymbol{g}_{t}$. This is where we get the main
improvement of our procedure compared to previously proposed methods. To
derive the result, we first establish the following lemma of independent
interest, which allows us to control the variance of Lipschitz functions on
$\partial B^{d}_{1}$. The proof of this lemma is given in the Appendix.

######  Lemma 3.

Let $d\geq 3$. Assume that $G:\mathbb{R}^{d}\to\mathbb{R}$ is a continuously
differentiable function, and $\boldsymbol{\zeta}$ is distributed uniformly on
$\partial B^{d}_{1}$. Then

$\displaystyle\operatorname{Var}(G(\boldsymbol{\zeta}))\leq\frac{4}{d(d-2)}\mathbf{E}\left[\|\nabla
G(\boldsymbol{\zeta})\|_{2}^{2}\left(1+\sqrt{d}\|\boldsymbol{\zeta}\|_{2}\right)^{2}\right]\enspace.$

Furthermore, if $G:\mathbb{R}^{d}\to\mathbb{R}$ is an $L$-Lipschitz function
w.r.t. the $\ell_{2}$-norm then

$\displaystyle\operatorname{Var}(G(\boldsymbol{\zeta}))\leq\frac{4L^{2}}{d(d-2)}\left(1+\sqrt{\frac{2d}{d+1}}\right)^{2}\enspace.$

######  Remark 1.

Since $d^{2}/(d(d-2))\leq 3$ for all $d\geq 3$, the last inequality of Lemma 3
implies that

$\displaystyle\operatorname{Var}(G(\boldsymbol{\zeta}))\leq
12\big{(}{1+\sqrt{2}}\big{)}^{2}\big{(}{L}/{d}\big{)}^{2}\,\,,\qquad\forall
d\geq 3\enspace.$ (3)

We can now deduce the following bound on the squared $\ell_{p^{*}}$-norm of
$\boldsymbol{g}_{t}$.

######  Lemma 4.

Let $p\in[1,\infty]$ and $p^{*}=\tfrac{p}{p-1}$. Assume that $f_{t}$ is
$L$-Lipschitz w.r.t. the $\ell_{q}$-norm. Then, for all $d\geq 3$,

$\displaystyle\mathbf{E}\|\boldsymbol{g}_{t}\|_{p^{*}}^{2}\leq
12(1+\sqrt{2})^{2}L^{2}d^{1+\frac{2}{q\wedge
2}-\frac{2}{p}}+\begin{dcases}0&\text{under canceling noise
Assumption~{}\ref{ass:no_noise}},\\\
\frac{d^{4-\frac{2}{p}}\sigma^{2}}{h^{2}}&\text{under adversarial noise
Assumption~{}\ref{ass:noise}}.\end{dcases}$

###### Proof.

Using the definition of $\boldsymbol{g}_{t}$ we get

$\displaystyle\mathbf{E}[\|\boldsymbol{g}_{t}\|_{p^{*}}^{2}\mid\boldsymbol{x}_{t}]$
$\displaystyle=\frac{d^{2}}{4h^{2}}\mathbf{E}[(f_{t}(\boldsymbol{x}_{t}+h\boldsymbol{\zeta}_{t})-f_{t}(\boldsymbol{x}_{t}-h\boldsymbol{\zeta}_{t})+\xi_{t}^{\prime}-\xi_{t}^{\prime\prime})^{2}\|\operatorname*{sign}(\boldsymbol{\zeta}_{t})\|_{p^{*}}^{2}\mid\boldsymbol{x}_{t}]$
$\displaystyle=\frac{d^{4-\frac{2}{p}}}{4h^{2}}\mathbf{E}[(f_{t}(\boldsymbol{x}_{t}+h\boldsymbol{\zeta}_{t})-f_{t}(\boldsymbol{x}_{t}-h\boldsymbol{\zeta}_{t})+\xi_{t}^{\prime}-\xi_{t}^{\prime\prime})^{2}\mid\boldsymbol{x}_{t}]\enspace.$

Let $G(\boldsymbol{\zeta})\triangleq
f_{t}(\boldsymbol{x}_{t}+h\boldsymbol{\zeta})-f_{t}(\boldsymbol{x}_{t}-h\boldsymbol{\zeta})$.
First, observe that
$\mathbf{E}[G(\boldsymbol{\zeta}_{t})\mid\boldsymbol{x}_{t}]=0$ and under both
Assumption 2 and Assumption 3(ii) it holds that
$\mathbf{E}[G(\boldsymbol{\zeta}_{t})(\xi_{t}^{\prime}-\xi_{t}^{\prime\prime})\mid\boldsymbol{x}_{t}]=0$.
Using these remarks and the fact that under adversarial noise Assumption 3,
$\mathbf{E}[(\xi_{t}^{\prime}-\xi_{t}^{\prime\prime})^{2}\mid\boldsymbol{x}_{t}]\leq
4\sigma^{2}$, we find:

$\displaystyle\mathbf{E}[\|\boldsymbol{g}_{t}\|_{p^{*}}^{2}\mid\boldsymbol{x}_{t}]\leq\frac{d^{4-\frac{2}{p}}}{4h^{2}}\left(\operatorname{Var}(G(\boldsymbol{\zeta}_{t})\mid\boldsymbol{x}_{t})+\begin{dcases}0&\text{under
cancelling noise Assumption~{}\ref{ass:no_noise}}\\\ 4\sigma^{2}&\text{under
adversarial noise Assumption~{}\ref{ass:noise}}\end{dcases}\right).$

Furthermore, since $f_{t}$ is $L$-Lipschitz, w.r.t. the $\ell_{q}$-norm, the
map $\boldsymbol{\zeta}\mapsto G(\boldsymbol{\zeta})$ is
$\big{(}2Lhd^{\frac{1}{q\wedge 2}-\frac{1}{2}}\big{)}$-Lipschitz w.r.t. the
$\ell_{2}$-norm. Applying (3) to bound
$\operatorname{Var}(G(\boldsymbol{\zeta}_{t})\mid\boldsymbol{x}_{t})$, yields
the desired result. ∎

Note that under adversarial noise Assumption 3, the bound on squared
$\ell_{p^{*}}$-norm of $\boldsymbol{g}_{t}$ gets an additional term
$d^{4-\frac{2}{p}}\sigma^{2}h^{-2}$. In contrast to the case of canceling
noise Assumption 2, this does not allow us to take $h$ arbitrary small hence
inducing the bias-variance trade-off.

##  7 Numerical illustration

In this section, we provide a numerical comparison of our algorithm with the
method based on $\ell_{2}$-randomization from Shamir, [33] (see Appendix D for
the definition). We consider the no noise model and $f_{t}=f$, $\forall t$,
with the function $f:\mathbb{R}^{d}\to\mathbb{R}$ defined as

$\displaystyle
f(\boldsymbol{x})=\left\lVert\boldsymbol{x}-\boldsymbol{c}\right\rVert_{2}+\left\lVert\boldsymbol{x}-0.1\cdot\boldsymbol{c}\right\rVert_{1}\enspace,$

where $\boldsymbol{c}=(c_{1},\ldots,c_{d})^{\top}\in\mathbb{R}^{d}$ such that
$c_{j}={\exp(j)}/{\sum_{i=1}^{d}\exp(i)}$ for $j=1,\ldots,d$. We choose

$\Theta=\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\,:\,\|\boldsymbol{x}\|_{1}=1,\,\boldsymbol{x}\geq
0\right\\}~{}~{}~{}{\rm
and}~{}~{}~{}V(\boldsymbol{x})=\sum_{j=1}^{d}x_{j}\log(x_{j})\enspace.$

As stated in Example 2, $V$ is $1$-strongly convex on $\Theta$ w.r.t. the
$\ell_{1}$-norm and $R\leq\sqrt{\log(d)}$. Moreover, $f$ is a Lipschitz
function w.r.t. the $\ell_{1}$-norm. We deploy the adaptive parameterization
that appears in Theorem 3. In Figure 1 we present the optimization error of
the algorithms, which is defined as

$f\bigg{(}\frac{1}{t}\sum_{i=1}^{t}\boldsymbol{x}_{i}\bigg{)}-\min_{\boldsymbol{x}\in\Theta}f(\boldsymbol{x})\enspace.$

Figure 1: Opt. error vs. number of iterations for $\ell_{2}$-randomization (as
in [33]) and our method.

The results are reported over $30$ trials. We plot all the $30$ runs alongside
the average performance. One can observe that the $\ell_{1}$-randomization
method behaves significantly better than the $\ell_{2}$-randomization
algorithm. The theoretical bound for our method in this setup has a
$\sqrt{\log d}$ gain in the rate.

##  8 Discussion and comparison to prior work

We introduced and analyzed a novel estimator for the gradient based on
randomization over the $\ell_{1}$-sphere. We established guarantees for the
online dual averaging algorithm with the gradient replaced by the proposed
estimator. We provided an anytime and completely data-driven algorithm, which
is adaptive to all parameters of the problem. Our analysis is based on
deriving a weighted Poincaré type inequality for the uniform measure on the
$\ell_{1}$-sphere that may be of independent interest.
Under the canceling noise assumption and $q\in\\{1,2\\}$, our setting is
analogous to [14, 33]. For the case $q=p=2$ and canceling noise, we show that
the performance of our method is the same as in [33, Corollary 2] up to
absolute constants that were not made explicit in [33]. For the case of
$q=p=1$ and canceling noise, we improved the bound [33, Corollary 3] by a
$\sqrt{\log(d)}$ factor. For the case $q=2$, $p\geq 1$, comparing with the
lower bound in [14, Proposition 1], shows that the result of Theorem 1 is
minimax optimal. For the case $q=p=1$, [14, Proposition 2] shows that our
result in Theorem 1 is optimal up to a $\log(d)$ factor.
Under the adversarial noise assumption, Theorem 2 provides the rate
$O(T^{3/4})$, that is, we get an additional $T^{1/4}$ factor compared to the
canceling noise case. It remains unclear whether it is optimal under
adversarial noise – this question deserves further investigation. Note that,
under sub-Gaussian i.i.d. noise assumption and $q=p=2$, one can achieve the
rate $\tilde{O}(d^{a}\sqrt{T})$ with a relatively big $a>0$ [2, 8, 13, 21]. In
particular, with an ellipsoid type method [21] obtains the rate
$\mathcal{O}(d^{4.5}\sqrt{T}\log(T)^{2})$ for the cumulative regret.
Finally, let us discuss the compactness of $\Theta$. It is straightforward to
extend the results of Theorems 1, 2 to any closed convex $\Theta$ considering
the regret against a fixed action $\boldsymbol{x}\in\Theta$. Indeed, using
[26, Corollary 7.9], one only needs to replace $R$ appearing in both Theorems
1, 2 by an upper bound on
$\sqrt{V(\boldsymbol{x})-\inf_{\boldsymbol{x}^{\prime}\in\Theta}V(\boldsymbol{x}^{\prime})}$.
The adaptive case is more complicated. One way to tackle this case is to use
[27, Theorem 1] requiring a control of
$\mathbf{E}\max_{t=1,\ldots,T}\|\boldsymbol{g}_{t}\|_{p^{*}}$. This term can
be controlled under the canceling noise Assumption 2 using the Lipschitzness
of $f_{t}$’s, so that Theorem 3 extends to unbounded $\Theta$. However,
without the canceling noise assumption, following the approach outlined above,
one needs to control
$\mathbf{E}\max_{t=1,\ldots,T}\tfrac{|\xi_{t}^{\prime}-\xi^{\prime\prime}_{t}|}{h_{t}}$.
The adversarial noise Assumption 3 is not sufficient to reasonably control
this term, so that extending Theorem 4 to unbounded $\Theta$ is not possible
without further assumptions.

## Acknowledgments and Disclosure of Funding

The work of E. Chzhen was supported by ANR PIA funding: ANR-20-IDEES-0002. The
work of M.Pontil is partially supported by European Union’s Horizon 2020
research and innovation programme under ELISE grant agreement No 951847. The
research of A.Akhavan and A.B. Tsybakov is supported by a grant of the French
National Research Agency (ANR), “Investissements d’Avenir” (LabEx
Ecodec/ANR-11-LABX-0047).

## References

  * Agarwal et al., [2010] Agarwal, A., Dekel, O., and Xiao, L. (2010).  Optimal algorithms for online convex optimization with multi-point bandit feedback.  In Proc. 23rd International Conference on Learning Theory, pages 28–40.
  * Agarwal et al., [2011] Agarwal, A., Foster, D. P., Hsu, D. J., Kakade, S. M., and Rakhlin, A. (2011).  Stochastic convex optimization with bandit feedback.  In Advances in Neural Information Processing Systems, volume 25, pages 1035–1043.
  * Akhavan et al., [2020] Akhavan, A., Pontil, M., and Tsybakov, A. (2020).  Exploiting higher order smoothness in derivative-free optimization and continuous bandits.  In Advances in Neural Information Processing Systems, volume 33.
  * Akhavan et al., [2021] Akhavan, A., Pontil, M., and Tsybakov, A. B. (2021).  Distributed zero-order optimization under adversarial noise.  In Advances in Neural Information Processing Systems, volume 34.
  * Bach and Perchet, [2016] Bach, F. and Perchet, V. (2016).  Highly-smooth zero-th order online optimization.  In Proc. 29th Annual Conference on Learning Theory, pages 1–27.
  * Barthe et al., [2005] Barthe, F., Guédon, O., Mendelson, S., and Naor, A. (2005).  A probabilistic approach to the geometry of the Lpn-ball.  The Annals of Probability, 33(2):480 – 513.
  * Barthe and Wolff, [2009] Barthe, F. and Wolff, P. (2009).  Remarks on non-interacting conservative spin systems: the case of gamma distributions.  Stochastic processes and their applications, 119(8):2711–2723.
  * Belloni et al., [2015] Belloni, A., Liang, T., Narayanan, H., and Rakhlin, A. (2015).  Escaping the local minima via simulated annealing: Optimization of approximately convex functions.  In Proc. 28th Annual Conference on Learning Theory, pages 240–265.
  * Bobkov and Ledoux, [1997] Bobkov, S. and Ledoux, M. (1997).  Poincaré’s inequalities and Talagrand’s concentration phenomenon for the exponential distribution.  Probability Theory and Related Fields, 107(3):383–400.
  * Bobkov and Ledoux, [2009] Bobkov, S. G. and Ledoux, M. (2009).  Weighted Poincaré-type inequalities for Cauchy and other convex measures.  The Annals of Probability, 37(2):403 – 427.
  * Boucheron et al., [2013] Boucheron, S., Lugosi, G., and Massart, P. (2013).  Concentration inequalities: A nonasymptotic theory of independence.  Oxford university press.
  * Bubeck and Cesa-Bianchi, [2012] Bubeck, S. and Cesa-Bianchi, N. (2012).  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  Foundations and Trends in Machine Learning, 5(1):1–122.
  * Bubeck et al., [2017] Bubeck, S., Lee, Y. T., and Eldan, R. (2017).  Kernel-based methods for bandit convex optimization.  In Proc. 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 72–85.
  * Duchi et al., [2015] Duchi, J. C., Jordan, M. I., Wainwright, M. J., and Wibisono, A. (2015).  Optimal rates for zero-order convex optimization: The power of two function evaluations.  IEEE Transactions on Information Theory, 61(5):2788–2806.
  * Evans and Gariepy, [2018] Evans, L. C. and Gariepy, R. F. (2018).  Measure theory and fine properties of functions.  Routledge.
  * Flaxman et al., [2005] Flaxman, A. D., Kalai, A. T., and McMahan, H. B. (2005).  Online convex optimization in the bandit setting: gradient descent without a gradient.  In Proc. 16th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pages 385––394.
  * Gasnikov et al., [2017] Gasnikov, A., Krymova, E., Lagunovskaya, A., Usmanova, I., and Fedorenko, F. (2017).  Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case.  Automation and Remote Control, 78(2):224–234.
  * Gasnikov et al., [2016] Gasnikov, A., Lagunovskaya, A., Usmanova, I., and Fedorenko, F. (2016).  Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex.  Automation and Remote Control, 77(11):2018–2034.
  * Ghadimi and Lan, [2013] Ghadimi, S. and Lan, G. (2013).  Stochastic first- and zeroth-order methods for nonconvex stochastic programming.  SIAM Journal on Optimization, 23(4):2341–2368.
  * Hu et al., [2016] Hu, X., Prashanth, L. A., György, A., and Szepesvári, C. (2016).  Escaping the local minima via simulated annealing: Optimization of approximately convex functions.  In Proc. 10th International Conference on Artificial Intelligence and Statistics, pages 819–828.
  * Lattimore and Gyorgy, [2021] Lattimore, T. and Gyorgy, A. (2021).  Improved regret for zeroth-order stochastic convex bandits.  In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 2938–2964. PMLR.
  * Nemirovsky and Yudin, [1983] Nemirovsky, A. S. and Yudin, D. B. (1983).  Problem Complexity and Method Efficiency in Optimization. Wiley & Sons.
  * Nesterov, [2011] Nesterov, Y. (2011).  Random gradient-free minimization of convex functions.  Technical Report 2011001, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain.
  * Nesterov and Spokoiny, [2017] Nesterov, Y. and Spokoiny, V. (2017).  Random gradient-free minimization of convex functions.  Found. Comput. Math., 17:527––566.
  * Novitskii and Gasnikov, [2021] Novitskii, V. and Gasnikov, A. (2021).  Improved exploiting higher order smoothness in derivative-free optimization and continuous bandit.  arXiv preprint arXiv:2101.03821.
  * Orabona, [2019] Orabona, F. (2019).  A modern introduction to online learning.  ArXiv, abs/1912.13213.
  * Orabona and Pál, [2016] Orabona, F. and Pál, D. (2016).  Scale-free online learning.  Theoretical Computer Science, 716.
  * Polyak and Tsybakov, [1990] Polyak, T. B. and Tsybakov, A. B. (1990).  Optimal order of accuracy of search algorithms in stochastic optimization.  Problems of Information Transmission, 26(2):45–53.
  * Saha and Tewari, [2011] Saha, A. and Tewari, A. (2011).  Improved regret guarantees for online smooth convex optimization with bandit feedback.  In Proc. 14th International Conference on Artificial Intelligence and Statistics, pages 636–642.
  * Schechtman and Zinn, [1990] Schechtman, G. and Zinn, J. (1990).  On the volume of the intersection of two $L^{n}_{p}$ balls.  Proc. Amer. Math. Soc., 110(1):217–224.
  * Shalev-Shwartz, [2012] Shalev-Shwartz, S. (2012).  Online learning and online convex optimization, volume 4.  Now Publishers, Inc.
  * Shamir, [2013] Shamir, O. (2013).  On the complexity of bandit and derivative-free stochastic convex optimization.  In Proc. 30th Annual Conference on Learning Theory, pages 1–22.
  * Shamir, [2017] Shamir, O. (2017).  An optimal algorithm for bandit and zero-order convex optimization with two-point feedback.  Journal of Machine Learning Research, 18(1):1703–1713.
  * Zorich, [2016] Zorich, V. A. (2016).  Mathematical analysis II.  Springer.

Supplementary Material

This supplementary material contains the proofs and results omitted from the
main body. In Appendix A we recall the appropriate version of the Stokes’
theorem and discuss its applicability for Lipschitz functions on $B_{1}^{d}$.
In Appendix B we provide the proof of Lemma 3. Finally, in Appendix C we
provide the proofs of Theorems 1, 2, 3, 4.

#### Additional notation

For two functions $g,\eta:\mathbb{R}^{d}\to\mathbb{R}$, we denote by
$\eta\star g$ their convolution defined point-wise for
$\boldsymbol{x}\in\mathbb{R}^{d}$ as

$\displaystyle\big{(}\eta\star
g\big{)}(\boldsymbol{x})=\int_{\mathbb{R}^{d}}\eta(\boldsymbol{x}-\boldsymbol{x}^{\prime})g(\boldsymbol{x}^{\prime})\,\mathrm{d}\boldsymbol{x}^{\prime}\enspace.$

The standard mollifier $\eta_{\epsilon}:\mathbb{R}^{d}\to\mathbb{R}$ is
defined as
$\eta_{\epsilon}(\boldsymbol{x})=\epsilon^{-d}\eta_{1}(\boldsymbol{x}/\epsilon)$
for $\epsilon>0$ and $\boldsymbol{x}\in\mathbb{R}$, where
$\eta_{1}:\mathbb{R}^{d}\to\mathbb{R}$ is defined as

$\displaystyle\eta_{1}(\boldsymbol{x})=\begin{cases}C\exp\left(\frac{1}{\|\boldsymbol{x}\|_{2}^{2}-1}\right)&\text{if
}\|\boldsymbol{x}\|_{2}\leq 1\\\ 0&\text{otherwise}\end{cases}\enspace,$

with $C$ chosen so that
$\int_{\mathbb{R}^{d}}\eta_{1}(\boldsymbol{x})\,\mathrm{d}\boldsymbol{x}=1$.

##  Appendix A Integration by parts

We first recall the following result that can be found in [34, Section 13.3.5,
Exercise 14a].

######  Theorem 5 (Integration by parts in a multiple integral).

Let $D$ be an open connected subset of $\mathbb{R}^{d}$ with a piecewise
smooth boundary $\partial D$ oriented by the outward unit normal
$\boldsymbol{n}=(n_{1},\ldots,n_{d})^{\top}$. Let $g$ be a continuously
differentiable function in $D\cup\partial D$. Then

$\displaystyle\int_{D}\nabla
g(\boldsymbol{u})\,\mathrm{d}\boldsymbol{u}=\int_{\partial
D}g(\boldsymbol{\zeta})\boldsymbol{n}(\boldsymbol{\zeta})\,\mathrm{d}S(\boldsymbol{\zeta})\enspace.$

######  Remark 2.

We refer to [34, Section 12.3.2, Definitions 4 and 5] for the definition of
piecewise smooth surfaces and their orientations respectively.

The idea of using the instance of Theorem 5 (also called Stokes’ theorem) with
$D=B^{d}_{2}$ to obtain $\ell_{2}$-randomized estimators of the gradient
belongs to Nemirovsky and Yudin, [22]. It was further used in several papers
[16, 5, 31, 33] to mention just a few. Those papers were referring to [22] but
[22] did not provide an exact statement of the result (nor a reference) and
only tossed the idea in a discussion. However, the classical analysis
formulation as presented in Theorem 5 does not apply to Lipschitz continuous
functions that were considered in [16, 5, 31, 33]. We are not aware of whether
its extension to Lipschitz continuous functions, though rather standard, is
proved in the literature.

In this paper, we apply Theorem 5 with the $\ell_{1}$-ball $D=B^{d}_{1}$. Our
aim in this section is to provide a variant of Theorem 5 applicable to a
Lipschitz continuous function $g:\mathbb{R}^{d}\to\mathbb{R}$, which is not
necessarily continuously differentiable on $D\cup\partial
D=B^{d}_{1}\cup\partial B^{d}_{1}$. To this end, we will go through the
argument of approximating $g$ by $C^{\infty}(\Omega)$ functions, where
$\Omega\subset\mathbb{R}^{d}$ is an open bounded connected subset of
$\mathbb{R}^{d}$ such that $D\cup\partial D\subset\Omega$. Let
$g_{n}=\eta_{{1}/n}\star g$, where $\eta_{1/n}$ is the standard mollifier. Let
$g:\mathbb{R}^{d}\to\mathbb{R}$ be a function satisfying the Lipschitz
condition w.r.t. the $\ell_{1}$-norm:
$|g(\boldsymbol{u})-g(\boldsymbol{u}^{\prime})|\leq
L\|\boldsymbol{u}-\boldsymbol{u}^{\prime}\|_{1}$. Since $g$ is continuous in
$\Omega$ and, by construction $D\cup\partial D\subset\Omega$, then using basic
properties of mollification [see e.g., 15, Theorem 4.1 (ii)] we have

$\displaystyle g_{n}\longrightarrow g$

uniformly on $D\cup\partial D$ (in particular, uniformly on $\partial D$).
Furthermore, let $\nabla g$ be the gradient of $g$, which by Rademacher
theorem [see e.g., 15, Theorem 3.2] is well defined almost everywhere w.r.t.
the Lebesgue measure and

$\displaystyle\|\nabla g(\boldsymbol{u})\|_{\infty}\leq L\qquad\text{a.e.}$

It follows that $\frac{\partial g}{\partial u_{j}}$ is absolutely integrable
on $\Omega$ for any $j\in[d]$. Furthermore, since

$\displaystyle\frac{\partial g_{n}}{\partial
u_{j}}=\eta_{1/n}\star\left(\frac{\partial g}{\partial u_{j}}\right)\enspace,$

we can apply [15, Theorem 4.1 (iii)] that yields

$\displaystyle\int_{D}\|\nabla g_{n}(\boldsymbol{u})-\nabla
g(\boldsymbol{u})\|_{2}\,\mathrm{d}\boldsymbol{u}\longrightarrow 0\enspace.$

Combining the above remarks we obtain that the result of Theorem 5 is valid
for functions $g$ that are Lipschitz continuous w.r.t. the $\ell_{1}$-norm.
Thus, it is also valid when the Lipschitz condition is imposed w.r.t. any
$\ell_{q}$-norm with $q\in[1,\infty]$. Specifying this conclusion for the
particular case $D=B_{1}^{d}$, we obtain the following theorem.

######  Theorem 6.

Let the function $g:\mathbb{R}^{d}\to\mathbb{R}$ be Lipschitz continuous
w.r.t. the $\ell_{q}$-norm with $q\in[1,\infty]$. Then

$\displaystyle\int_{B^{d}_{1}}\nabla
g(\boldsymbol{u})\,\mathrm{d}\boldsymbol{u}=\frac{1}{\sqrt{d}}\int_{\partial
B^{d}_{1}}g(\boldsymbol{\zeta})\operatorname*{sign}(\boldsymbol{\zeta})\,\mathrm{d}S(\boldsymbol{\zeta})\enspace,$

where $\nabla g(\cdot)$ is defined up to a set of zero Lebesgue measure by the
Rademacher theorem.

##  Appendix B Proof of Lemma 3

To prove Lemma 3, we first recall the weighted Poincaré inequality for the
univariate exponential measure (mean $0$ and scale parameter $1$ Laplace
distribution).

######  Lemma 5 (Lemma 2.1 in [9]).

Let $W$ be mean $0$ and scale parameter $1$ Laplace random variable. Let
$g:\mathbb{R}\to\mathbb{R}$ be continuous almost everywhere differentiable
function such that

$\displaystyle\mathbf{E}[|g(W)|]<\infty\quad\text{and}\quad\mathbf{E}[|g^{\prime}(W)|]<\infty\quad\text{and}\quad\lim_{|w|\rightarrow\infty}g(w)\exp(-|w|)=0\enspace,$

then,

$\displaystyle\mathbf{E}[(g(W)-\mathbf{E}[g(W)])^{2}]\leq
4\mathbf{E}[(g^{\prime}(W))^{2}].$

We are now in a position to prove Lemma 3. The proof is inspired by [7, Lemma
2].

###### Proof of Lemma 3.

Throughout the proof, we assume without loss of generality that
$\mathbf{E}[G(\boldsymbol{\zeta})]=0$. Indeed, if it is not the case, we use
the result for the centered function
$\tilde{G}(\boldsymbol{\zeta})=G(\boldsymbol{\zeta})-\mathbf{E}[G(\boldsymbol{\zeta})]$,
which has the same gradient.

First, consider the case of continuously differentiable $G$. Let
$\boldsymbol{W}=\left(W_{1},\dots,W_{d}\right)$ be a vector of i.i.d. mean $0$
and scale parameter $1$ Laplace random variables and define
$\boldsymbol{T}(\boldsymbol{w})=\boldsymbol{w}/\left\lVert\boldsymbol{w}\right\rVert_{1}$.
Introduce the notation

$\displaystyle
F(\boldsymbol{w})\triangleq\|\boldsymbol{w}\|_{1}^{\nicefrac{{1}}{{2}}}G(\boldsymbol{T}(\boldsymbol{w}))\enspace.$

Lemma 1 in [30] asserts that, for $\boldsymbol{\zeta}$ uniformly distributed
on $\partial B_{1}^{d}$,

$\displaystyle\boldsymbol{T}(\boldsymbol{W})\stackrel{{\scriptstyle
d}}{{=}}\boldsymbol{\zeta}\quad\text{and}\quad\boldsymbol{T}(\boldsymbol{W})\text{
is independent of }\|\boldsymbol{W}\|_{1}\enspace.$ (4)

In particular,

$\displaystyle\operatorname{Var}(F(\boldsymbol{W}))=d\operatorname{Var}(G(\boldsymbol{\zeta}))\enspace.$

Using the Efron-Stein inequality [see e.g., 11, Theorem 3.1] we obtain

$\displaystyle\operatorname{Var}(F(\boldsymbol{W}))\leq\sum_{i=1}^{d}\mathbf{E}\left[\operatorname{Var}_{i}(F)\right]\enspace,$

where

$\displaystyle\operatorname{Var}_{i}(F)=\mathbf{E}\bigg{[}\big{(}F(\boldsymbol{W})-\mathbf{E}[F(\boldsymbol{W})\mid\boldsymbol{W}^{-i}]\big{)}^{2}\mid\boldsymbol{W}^{-i}\bigg{]}$

with
$\boldsymbol{W}^{-i}\triangleq(W_{1},\ldots,W_{i-1},W_{i+1},\ldots,W_{d})$.
Note that on the event $\\{\boldsymbol{W}^{-i}\neq\boldsymbol{0}\\}$ (whose
complement has zero measure), the function

$\displaystyle w\mapsto
F(W_{1},\ldots,W_{i-1},w,W_{i+1},\ldots,W_{d})\enspace,$

satisfies the assumptions of Lemma 5. Thus,

$\displaystyle
d\operatorname{Var}(G(\boldsymbol{\zeta}))=\operatorname{Var}(F(\boldsymbol{W}))\leq
4\sum_{j=1}^{d}\mathbf{E}\left[\left(\frac{\partial
F}{\partial{w_{j}}}(\boldsymbol{W})\right)^{2}\right]=4\mathbf{E}\|\nabla
F(\boldsymbol{W})\|_{2}^{2}\enspace.$ (5)

In order to compute $\nabla F(\boldsymbol{W})$, we observe that for every
$i\neq j\in[d]$ we have for all $\boldsymbol{w}\neq\boldsymbol{0}$ such that
$w_{i},w_{j}\neq 0$

$\displaystyle\frac{\partial T_{i}}{\partial
w_{j}}(\boldsymbol{w})=-\frac{w_{i}\operatorname*{sign}(w_{j})}{\|\boldsymbol{w}\|_{1}^{2}}\quad\text{and}\quad\frac{\partial
T_{i}}{\partial
w_{i}}(\boldsymbol{w})=\frac{1}{\|\boldsymbol{w}\|_{1}}-\frac{w_{i}\operatorname*{sign}(w_{i})}{\|\boldsymbol{w}\|_{1}^{2}}\enspace.$

Thus, the Jacobi matrix of $\boldsymbol{T}(\boldsymbol{w})$ has the form

$\displaystyle\mathbf{J}_{\boldsymbol{T}}(\boldsymbol{w})=\frac{\mathbf{I}}{\|\boldsymbol{w}\|_{1}}-\frac{{\boldsymbol{w}(\operatorname*{sign}(\boldsymbol{w}))^{\top}}}{\|\boldsymbol{w}\|_{1}^{2}}=\frac{1}{\|\boldsymbol{w}\|_{1}}\left(\mathbf{I}-\boldsymbol{T}(\boldsymbol{w})\big{(}\operatorname*{sign}(\boldsymbol{w})\big{)}^{\top}\right)\enspace.$

It follows that almost surely

$\displaystyle\nabla
F(\boldsymbol{W})=\frac{1}{2\|\boldsymbol{W}\|_{1}^{\nicefrac{{1}}{{2}}}}G(\boldsymbol{T}(\boldsymbol{W}))\operatorname*{sign}(\boldsymbol{W})+\frac{1}{\|\boldsymbol{W}\|_{1}^{\nicefrac{{1}}{{2}}}}\bigg{(}\mathbf{I}-\boldsymbol{T}(\boldsymbol{W})\big{(}\operatorname*{sign}(\boldsymbol{W})\big{)}^{\top}\bigg{)}\nabla
G(\boldsymbol{T}(\boldsymbol{W}))\enspace\enspace.$

Observe that since
$\left\langle\operatorname*{sign}(\boldsymbol{W}),\,\boldsymbol{T}(\boldsymbol{W})\right\rangle=1$
almost surely, we have

$\displaystyle\big{(}\operatorname*{sign}(\boldsymbol{W})\big{)}^{\top}\bigg{(}\mathbf{I}-\boldsymbol{T}(\boldsymbol{W})\big{(}\operatorname*{sign}(\boldsymbol{W})\big{)}^{\top}\bigg{)}\nabla
G(\boldsymbol{T}(\boldsymbol{W}))=0\quad\text{almost surely}\enspace.$

The above two equations imply that almost surely

$\displaystyle 4\|\nabla F(\boldsymbol{W})\|_{2}^{2}$
$\displaystyle=\frac{d}{\|\boldsymbol{W}\|_{1}}G^{2}(\boldsymbol{T}(\boldsymbol{W}))+\frac{4}{\|\boldsymbol{W}\|_{1}}\left\lVert\bigg{(}\mathbf{I}-\boldsymbol{T}(\boldsymbol{W})\big{(}\operatorname*{sign}(\boldsymbol{W})\big{)}^{\top}\bigg{)}\nabla
G(\boldsymbol{T}(\boldsymbol{W}))\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{d}{\|\boldsymbol{W}\|_{1}}G^{2}(\boldsymbol{T}(\boldsymbol{W}))+\frac{4}{\|\boldsymbol{W}\|_{1}}\left\lVert\nabla
G(\boldsymbol{T}(\boldsymbol{W}))\right\rVert_{2}^{2}(1+\sqrt{d}\|\boldsymbol{T}(\boldsymbol{W})\|_{2})^{2}\enspace,$

where we used the fact that the operator norm of
$\mathbf{I}-\boldsymbol{a}\boldsymbol{b}^{\top}$ is not greater than
$1+\|\boldsymbol{a}\|_{2}\|\boldsymbol{b}\|_{2}$. Combining the above bound
with (5), and using the facts that
$\mathbf{E}[\|\boldsymbol{W}\|_{1}^{-1}]=\frac{1}{d-1}$,
$\mathbf{E}[G(\boldsymbol{T}(\boldsymbol{W}))]=\mathbf{E}[G(\boldsymbol{\zeta})]=0$
and the independence of $\|\boldsymbol{W}\|_{1}$ and
$\boldsymbol{T}(\boldsymbol{W})$ (cf. (4)) yields

$\displaystyle
d\left(1-\frac{1}{d-1}\right)\operatorname{Var}(G(\boldsymbol{\zeta}))\leq\frac{4}{d-1}\mathbf{E}\left[\|\nabla
G(\boldsymbol{T}(\boldsymbol{W}))\|_{2}^{2}{(1+\sqrt{d}\|\boldsymbol{T}(\boldsymbol{W})\|_{2})^{2}}\right]\enspace.$

Rearranging, we deduce the first claim of the lemma since
$\boldsymbol{T}(\boldsymbol{W})\stackrel{{\scriptstyle
d}}{{=}}\boldsymbol{\zeta}$.

To prove the second statement of the lemma regarding Lipschitz functions, it
is sufficient to apply the first one to $G_{n}$—the sequence of smoothed
versions of $G$ such that $G_{n}\in C^{\infty}(\mathbb{R})$ and

$\displaystyle G_{n}\longrightarrow G\enspace,$

uniformly on every compact subset, and $\sup_{n\geq 1}\|\nabla
G_{n}(\boldsymbol{x})\|_{2}\leq L$ for almost all
$\boldsymbol{x}\in\mathbb{R}^{d}$. A sequence $G_{n}$ satisfying these
properties can be constructed by standard mollification due to the fact that
$G$ is Lipschitz continuous [see e.g., 15, Theorem 4.2]. Finally, to obtain
the value
$\mathbf{E}\|\boldsymbol{T}(\boldsymbol{W})\|_{2}^{2}=\mathbf{E}\|\boldsymbol{\zeta}\|_{2}^{2}$
we use Lemma 6 below. ∎

######  Lemma 6.

Let $\boldsymbol{\zeta}$ be distributed uniformly on $\partial B^{d}_{1}$.
Then,
$\mathbf{E}\left\lVert\boldsymbol{\zeta}\right\rVert^{2}_{2}=\frac{2}{d+1}$.

###### Proof.

We use the same tools as in the proof of Lemma 2. Let
$\boldsymbol{W}=(W_{1},\ldots,W_{d})$ be a vector of i.i.d. random variables
following the Laplace distribution with mean $0$ and scale parameter $1$. By
(4) we have that $\boldsymbol{\zeta}\stackrel{{\scriptstyle
d}}{{=}}\frac{\boldsymbol{W}}{\left\lVert\boldsymbol{W}\right\rVert_{1}}$ and
$\boldsymbol{\zeta}$ is independent of
$\left\lVert\boldsymbol{W}\right\rVert_{1}$. Therefore,

$\displaystyle\mathbf{E}\|\boldsymbol{\zeta}\|_{2}^{2}=\frac{\mathbf{E}\left\lVert\boldsymbol{W}\right\rVert^{2}_{2}}{\mathbf{E}\left\lVert\boldsymbol{W}\right\rVert_{1}^{2}}\enspace.$
(6)

Here,

$\displaystyle\mathbf{E}\left\lVert\boldsymbol{W}\right\rVert^{2}_{2}=\sum_{j=1}^{d}\mathbf{E}[W_{j}^{2}]=d\mathbf{E}[W_{1}^{2}]=2d\enspace.$
(7)

Furthermore, $\left\lVert\boldsymbol{W}\right\rVert_{1}$ follows the Erlang
distribution with parameters $(d,1)$, which implies

$\displaystyle\mathbf{E}\left\lVert\boldsymbol{W}\right\rVert_{1}^{2}=\frac{1}{\Gamma(d)}\int_{0}^{\infty}x^{d+1}\exp(-x)\,\mathrm{d}x=\frac{\Gamma(d+2)}{\Gamma(d)}\enspace.$
(8)

The lemma follows by combining (6) – (8). ∎

##  Appendix C Upper bounds

The proofs of Theorems 1, 2, 3, 4 resemble each other. They only differ in the
ways of handling the variance terms depending on
$\|\boldsymbol{g}_{t}\|_{p^{*}}^{2}$ and in the choice of parameters. For this
reason, we suggest the interested reader to follow the proofs in a linear
manner starting from the next paragraph.

#### Common part of the proofs of Theorems 1, 2.

We start with the part of the proofs that is common for Theorems 1, 2. Fix
some $\boldsymbol{x}\in\Theta$. Due to Assumption 1, we can use Lemma 1, which
implies

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\left\langle\mathbf{E}\left[\boldsymbol{g}_{t}\mid\boldsymbol{x}_{t}\right],\,\boldsymbol{x}_{t}-\boldsymbol{x}\right\rangle\right]=\mathbf{E}\left[\sum_{t=1}^{T}\left\langle\nabla{\sf
f}_{t,h}(\boldsymbol{x}_{t}),\,\boldsymbol{x}_{t}-\boldsymbol{x}\right\rangle\right]\geq\mathbf{E}\left[\sum_{t=1}^{T}\big{(}{\sf
f}_{t,h}(\boldsymbol{x}_{t})-{\sf f}_{t,h}(\boldsymbol{x})\big{)}\right],$

where ${\sf
f}_{t,h}(\boldsymbol{x})=\mathbf{E}[f_{t}(\boldsymbol{x}+h\boldsymbol{U})]$
with $\boldsymbol{U}$ uniformly distributed on $B_{1}^{d}$. Furthermore, by
the approximation property derived in Lemma 1 and the standard bound on the
cumulative regret of dual averaging algorithm [see e.g., 26, Corollary 7.9.]
we deduce that

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq\mathbf{E}\left[\sum_{t=1}^{T}\langle\mathbf{E}\left[\boldsymbol{g}_{t}|\boldsymbol{x}_{t}\right],\boldsymbol{x}_{t}-\boldsymbol{x}\rangle\right]+L\mathrm{b}_{q}(d)\sum_{t=1}^{T}h_{t}$
(9)
$\displaystyle\leq\frac{R^{2}}{\eta}+\frac{\eta}{2}\sum_{t=1}^{T}\mathbf{E}\left\lVert\boldsymbol{g}_{t}\right\rVert_{p^{*}}^{2}+L\mathrm{b}_{q}(d)\sum_{t=1}^{T}h_{t}\enspace,$

where in the last inequality we used the identity
$\eta_{1}=\ldots=\eta_{T}=\eta$. The results of Theorems 1, 2 follow from the
bound (9) as detailed below.

###### Proof of Theorem 1.

Here $h_{1}=\ldots=h_{T}=h$, and we work under Assumption 2. In this case,
bounding $\mathbf{E}\|\boldsymbol{g}_{t}\|_{p^{*}}$ in (9) via Lemma 4 yields

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq{\frac{R^{2}}{\eta}+6(1+\sqrt{2})^{2}L^{2}\cdot\eta
Td^{1+\frac{2}{q\wedge 2}-\frac{2}{p}}}+LhT\mathrm{b}_{q}(d)\enspace.$

Minimizing the the right hand side of the above inequality over $\eta>0$ and
substituting
$\eta=\frac{R}{L\left(\sqrt{6}+\sqrt{12}\right)}\sqrt{\frac{d^{-1-\frac{2}{{q\wedge
2}}+\frac{2}{p}}}{T}}$ we deduce that

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq
2\left(\sqrt{6}+\sqrt{12}\right)RLd^{\frac{1}{2}+\frac{1}{{q\wedge
2}}-\frac{1}{p}}\sqrt{T}+LhT\mathrm{b}_{q}(d)\enspace.$

Taking
$h\leq\frac{7R}{100\mathrm{b}_{q}(d)\sqrt{T}}d^{\frac{1}{2}+\frac{1}{q\wedge
2}-\frac{1}{p}}$ makes negligible the second summand in the above bound. This
concludes the proof. ∎

###### Proof of Theorem 2.

Here again $h_{1}=\ldots=h_{T}=h$, but we work under Assumption 3. Then,
bounding $\mathbf{E}\|\boldsymbol{g}_{t}\|_{p^{*}}$ in (9) via Lemma 4 yields

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]\leq{\frac{R^{2}}{\eta}+\eta
T\left(\frac{d^{4-\frac{2}{p}}\sigma^{2}}{h^{2}}+6\left(1+\sqrt{2}\right)^{2}L^{2}d^{1+\frac{2}{{q\wedge
2}}-\frac{2}{p}}\right)}+LhT\mathrm{b}_{q}(d)\enspace.$

Minimizing the right hand side of the above inequality over $\eta>0$ and
substituting the optimal value

$\eta=\frac{R}{\sqrt{T}}\left(\frac{d^{4-\frac{2}{p}}\sigma^{2}}{2h^{2}}+6\left(1+\sqrt{2}\right)^{2}L^{2}d^{1+\frac{2}{{q\wedge
2}}-\frac{2}{p}}\right)^{-\frac{1}{2}}\enspace,$

results in the following upper bound on the regret

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq
2R\sqrt{T}\left(\frac{d^{4-\frac{2}{p}}\sigma^{2}}{2h^{2}}+6\left(1+\sqrt{2}\right)^{2}L^{2}d^{1+\frac{2}{{q\wedge
2}}-\frac{2}{p}}\right)^{\frac{1}{2}}+LhT\mathrm{b}_{q}(d)$ $\displaystyle\leq
2\left(\sqrt{6}+\sqrt{12}\right)RL\sqrt{Td^{1+\frac{2}{{q\wedge
2}}-\frac{2}{p}}}+{\sqrt{2}R\sqrt{T}\frac{d^{2-\frac{1}{p}}\sigma}{h}+LhT\mathrm{b}_{q}(d)}\enspace,$

where for the last inequality we used the fact that
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for $a,b\geq 0$. Minimizing over $h>0$ the
last expression and substituting the optimal value
$h=\left(\frac{\sqrt{2}R\sigma}{L\mathrm{b}_{q}(d)}\right)^{\frac{1}{2}}T^{-\frac{1}{4}}d^{1-\frac{1}{2p}}$
we get

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]\leq
11.9RL\sqrt{Td^{1+\frac{2}{{q\wedge
2}}-\frac{2}{p}}}+2.4\sqrt{RL\sigma}T^{\frac{3}{4}}\sqrt{\mathrm{b}_{q}(d)}d^{\frac{1}{2}-\frac{1}{2p}}.\qed$

#### Common part of the proofs of Theorems 3, 4.

Here, we state the common parts of the proofs for Theorems 3, 4. Similar to
the first inequality in (9), we have

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq\mathbf{E}\left[\sum_{t=1}^{T}\langle\boldsymbol{g}_{t},\boldsymbol{x}_{t}-\boldsymbol{x}\rangle\right]+L\mathrm{b}_{q}(d)\sum_{t=1}^{T}h_{t}\enspace.$

Note that without loss of generality, we can assume that
$\sum_{k=1}^{t}\left\lVert\boldsymbol{g}_{k}\right\rVert_{p^{*}}^{2}\neq 0$,
for all $t\geq 1$. This is a consequence of the fact that if
$\sum_{k=1}^{t}\left\lVert\boldsymbol{g}_{k}\right\rVert_{p^{*}}^{2}=0$, then
the first term on the r.h.s. of the above inequality will be zero up to round
$t$. Thus, we can erase these iterates from the cumulative regret, only paying
the bias term for those rounds. In what follows we essentially use [27,
Corollary 1], which we re-derive for the sake of clarity. Assume that
$\eta_{t}=\tfrac{\lambda}{\sqrt{\sum_{k=1}^{t-1}\left\lVert\boldsymbol{g}_{k}\right\rVert^{2}_{p^{*}}}}$
for $t\in\\{2,\dots,T\\}$ and $\lambda>0$. Then, applying [27, Theorem 1] we
deduce that

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq\left(\frac{R^{2}}{\lambda}+2.75\cdot\lambda\right)\mathbf{E}\left[\sqrt{\sum_{t=1}^{T}\left\lVert\boldsymbol{g}_{t}\right\rVert^{2}_{p^{*}}}\right]$
$\displaystyle\phantom{\leq}+3.5D\cdot\mathbf{E}[\max_{t\in[T]}\left\lVert\boldsymbol{g}_{t}\right\rVert_{p^{*}}]+L\mathrm{b}_{q}(d)\sum_{t=1}^{T}h_{t}\enspace,$

where we introduced
$D=\sup_{\boldsymbol{u},\boldsymbol{w}\in\Theta}\left\lVert\boldsymbol{u}-\boldsymbol{w}\right\rVert_{p}$.
By [27, Proposition 1], we have $D\leq\sqrt{8}R$. Moreover, by Jensen’s
inequality, using the rough bound
$\mathbf{E}[\max_{t\in[T]}\left\lVert\boldsymbol{g}_{t}\right\rVert_{p^{*}}]\leq\sqrt{\sum_{t=1}^{T}\mathbf{E}\left[\left\lVert\boldsymbol{g}_{t}\right\rVert^{2}_{p^{*}}\right]}$,
and substituting $\lambda=\frac{R}{\sqrt{2.75}}$, we deduce that

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq\left(2\sqrt{2.75}+3.5\sqrt{8}\right)R\sqrt{\sum_{t=1}^{T}\mathbf{E}\left[\left\lVert\boldsymbol{g}_{t}\right\rVert^{2}_{p^{*}}\right]}+L\mathrm{b}_{q}(d)\sum_{t=1}^{T}h_{t}\enspace.$
(10)

Proofs of Theorems 3, 4 provided below follow from the above inequality by
properly selecting $h_{t}>0$.

###### Proof of Theorem 3.

The bound of Lemma 4 under Assumption 2 applied to (10) yields

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq
2\left(2\sqrt{2.75}+3.5\sqrt{8}\right)\left(\sqrt{3}+\sqrt{6}\right)RL\sqrt{Td^{1+\frac{2}{q\wedge
2}-\frac{2}{p}}}+L\mathrm{b}_{q}(d)\sum_{t=1}^{T}h_{t}$ $\displaystyle\leq
110.53\cdot RL\sqrt{Td^{1+\frac{2}{q\wedge
2}-\frac{2}{p}}}+L\mathrm{b}_{q}(d)\sum_{t=1}^{T}h_{t}\enspace.$

Taking
$h_{t}\leq\frac{7R}{200\mathrm{b}_{q}(d)\sqrt{t}}d^{\frac{1}{2}+\frac{1}{q\wedge
2}-\frac{1}{p}}$ makes negligible the last summand in the above bound. This
concludes the proof. ∎

###### Proof of Theorem 4.

Using (10), the bound of Lemma 4 under Assumption 3 and the fact that
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for $a,b\geq 0$, we deduce that

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq\left(2\sqrt{2.75}+3.5\sqrt{8}\right)R\left(\sum_{t=1}^{T}\frac{d^{4-\frac{2}{p}}\sigma^{2}}{h_{t}^{2}}+12(1+\sqrt{2})^{2}L^{2}T\cdot
d^{1+\frac{2}{q\wedge 2}-\frac{2}{p}}\right)^{\frac{1}{2}}$
$\displaystyle\phantom{\leq}+L\mathrm{b}_{q}(d)\sum_{t=1}^{T}h_{t}$
$\displaystyle\leq 110.6\cdot RL\sqrt{Td^{1+\frac{2}{q\wedge
2}-\frac{2}{p}}}+13.3R\cdot
d^{2-\frac{1}{p}}\sigma\left(\sum_{t=1}^{T}\frac{1}{h_{t}^{2}}\right)^{\frac{1}{2}}$
$\displaystyle\phantom{\leq}+L\mathrm{b}_{q}(d)\sum_{t=1}^{T}h_{t}\enspace.$

Since
$h_{t}=\left(6.65\sqrt{6}\cdot\frac{R}{\mathrm{b}_{q}(d)}\right)^{\frac{1}{2}}t^{-\frac{1}{4}}d^{1-\frac{1}{2p}}$
and $\sum_{t=1}^{T}t^{\frac{1}{2}}\leq\tfrac{2}{3}T^{\frac{3}{2}}$ and
$\sum_{t=1}^{T}t^{-\frac{1}{4}}\leq\tfrac{4}{3}T^{\frac{3}{4}}$, we get

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\big{(}f_{t}(\boldsymbol{x}_{t})-f_{t}(\boldsymbol{x})\big{)}\right]$
$\displaystyle\leq 110.6\cdot RL\sqrt{Td^{1+\frac{2}{q\wedge
2}-\frac{2}{p}}}+5.9\cdot\sqrt{R}\left(\sigma+L\right)T^{\frac{3}{4}}\sqrt{\mathrm{b}_{q}(d)}d^{\frac{1}{2}-\frac{1}{2p}}\enspace.\qed$

##  Appendix D Definition of $\ell_{2}$-randomized estimator

In this section we recall the algorithm of Shamir, [33]. Let
$\boldsymbol{\zeta}^{\circ}\in\mathbb{R}^{d}$ be distributed uniformly on
$\partial B^{d}_{2}$. Instead of the gradient estimator that we introduce in
Algorithm 1, at a each step $t\geq 1$, Shamir, [33] uses

$\displaystyle\boldsymbol{g}_{t}^{\circ}\triangleq\frac{d}{2h}(y_{t}^{\prime}-y_{t}^{\prime\prime})\boldsymbol{\zeta}_{t}^{\circ}\enspace,$

where
$y_{t}^{\prime}=f_{t}(\boldsymbol{x}_{t}+h_{t}\boldsymbol{\zeta}^{\circ})$,
$y_{t}^{\prime\prime}=f_{t}(\boldsymbol{x}_{t}-h_{t}\boldsymbol{\zeta}_{t}^{\circ})$,
and $\boldsymbol{\zeta}^{\circ}_{t}$’s are independent random variables with
the same distribution as $\boldsymbol{\zeta}^{\circ}$.


Uniform Asymptotic Expansion for the Incomplete Beta Function

Uniform Asymptotic Expansion
for the Incomplete Beta Function

Gergő NEMES and Adri B. OLDE DAALHUIS

G. Nemes and A.B. Olde Daalhuis Maxwell Institute and School of Mathematics,
The University of Edinburgh,
Peter Guthrie Tait Road, Edinburgh EH9 3FD, UK<EMAIL_ADDRESS><EMAIL_ADDRESS>http://www.maths.ed.ac.uk/~gnemes/,
http://www.maths.ed.ac.uk/~adri/

Received September 12, 2016, in final form October 21, 2016; Published online
October 25, 2016

In [Temme N.M., Special functions. An introduction to the classical functions
of mathematical physics, A Wiley-Interscience Publication, John Wiley & Sons,
Inc., New York, 1996, Section 11.3.3.1] a uniform asymptotic expansion for the
incomplete beta function was derived. It was not obvious from those results
that the expansion is actually an asymptotic expansion. We derive a remainder
estimate that clearly shows that the result indeed has an asymptotic property,
and we also give a recurrence relation for the coefficients.

incomplete beta function; uniform asymptotic expansion

41A60; 33B20

##  1 Introduction

For positive real numbers $a$, $b$ and $x\in[0,1]$, the (normalised)
incomplete beta function $I_{x}(a,b)$ is defined by

$\displaystyle
I_{x}(a,b)=\frac{1}{B(a,b)}\int_{0}^{x}t^{a-1}(1-t)^{b-1}\,\mathrm{d}t,$

where $B(a,b)$ denotes the ordinary beta function:

$\displaystyle
B(a,b)=\int_{0}^{1}t^{a-1}(1-t)^{b-1}\,\mathrm{d}t=\frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)}$

(see, e.g., [2, Section 8.17(i)]). In this paper, we will use the notation of
[2, Section 8.18(ii)].

The incomplete beta function plays an important role in statistics in
connection with the beta distribution (see, for instance, [1, pp. 210–275]).
Large parameter asymptotic approximations are useful in these applications.
For fixed $x$ and $b$, one could use the asymptotic expansion

$\displaystyle
I_{x}(a,b)=\frac{x^{a}(1-x)^{b-1}}{aB(a,b)}\,{}_{2}F_{1}\left(\begin{matrix}{1,1-b}\\\
{a+1}\end{matrix};\frac{x}{x-1}\right)\sim\frac{x^{a}(1-x)^{b-1}}{aB(a,b)}\sum_{n=0}^{\infty}\frac{\left(1-b\right)_{n}}{\left(a+1\right)_{n}}\left(\frac{x}{x-1}\right)^{n},$
(1)

as $a\to+\infty$. The right-hand side of (1) converges only for
$x\in[0,\frac{1}{2})$, but for any fixed $x\in[0,1)$ it is still useful when
used as an asymptotic expansion as $a\to+\infty$. For more details, see [3,
Section 11.3.3]. However, it is readily seen that (1) breaks down as $x\to 1$.
Since this limit has significant importance in applications, Temme derived in
[3, Section 11.3.3.1] an asymptotic expansion as $a\to+\infty$ that holds
uniformly for $x\in(0,1]$. His result can be stated as follows.

######  Theorem 1.1.

Let $\xi=-\ln x$. Then for any fixed positive integer $N$ and fixed positive
real $b$,

$\displaystyle
I_{x}(a,b)=\frac{\Gamma(a+b)}{\Gamma(a)}\left(\sum_{n=0}^{N-1}d_{n}F_{n}+\mathcal{O}\big{(}a^{-N}\big{)}F_{0}\right),$
(2)

as $a\to+\infty$, uniformly for $x\in(0,1]$. The functions
$F_{n}=F_{n}(\xi,a,b)$ are defined by the recurrence relation

$\displaystyle aF_{n+1}=(n+b-a\xi)F_{n}+n\xi F_{n-1},$ (3)

with

$\displaystyle F_{0}=a^{-b}Q(b,a\xi),\qquad
F_{1}=\frac{b-a\xi}{a}F_{0}+\frac{\xi^{b}\mathrm{e}^{-a\xi}}{a\Gamma(b)},$

and $Q(a,z)=\Gamma(a,z)/\Gamma(a)$ is the normalised incomplete gamma function
$($see [2, Section 8.2(i)]). The coefficients $d_{n}=d_{n}(\xi,b)$ are defined
by the generating function

$\displaystyle\left(\frac{1-\mathrm{e}^{-t}}{t}\right)^{b-1}=\sum_{n=0}^{\infty}d_{n}(t-\xi)^{n}.$
(4)

In particular,

$\displaystyle d_{0}=\left(\frac{1-x}{\xi}\right)^{b-1},\qquad
d_{1}=\frac{x\xi+x-1}{(1-x)\xi}(b-1)d_{0}.$

They satisfy the recurrence relation

$\displaystyle\xi(n+1)(n+2)d_{0}d_{n+2}=\xi\sum_{m=0}^{n}(m+1)\left(n-2m+1+\frac{m-n-1}{b-1}\right)d_{m+1}d_{n-m+1}$
$\displaystyle\hphantom{\xi(n+1)(n+2)d_{0}d_{n+2}=}{}+\sum_{m=0}^{n}(m+1)\left(n-2m-2-\xi+\frac{m-n}{b-1}\right)d_{m+1}d_{n-m}$
$\displaystyle\hphantom{\xi(n+1)(n+2)d_{0}d_{n+2}=}{}+\sum_{m=0}^{n}(1-m-b)d_{m}d_{n-m}.$
(5)

In the case that $b=1$, we have $d_{0}=1$ and $d_{n}=0$ for $n\geq 1$.

Our contribution is the remainder estimate in (2) and the recurrence relation
(5). In fact, it is not at all obvious from (3) that the sequence
$\\{F_{n}\\}_{n=0}^{\infty}$ has an asymptotic property as $a\to+\infty$. We
will show that for any non-negative integer $n$,

$\displaystyle 0<F_{n+1}\leq\frac{n+\beta}{a}F_{n},$ (6)

where $\beta=\max(1,b)$.

In [4, Section 38.2.8] the function $F_{n}$ is identified as a Kummer
$U$-function:

$\displaystyle
F_{n}=\frac{\xi^{n+b}\mathrm{e}^{-a\xi}n!}{\Gamma(b)}U(n+1,n+b+1,a\xi).$

##  2 Proof of the main results

We proceed similarly as in [3, Section 11.3.3.1] and start with the integral
representation

$\displaystyle
I_{x}(a,b)=\frac{1}{B(a,b)}\int_{\xi}^{+\infty}t^{b-1}\mathrm{e}^{-at}\left(\frac{1-\mathrm{e}^{-t}}{t}\right)^{b-1}\,\mathrm{d}t.$
(7)

We substitute the truncated Taylor series expansion

$\displaystyle\left(\frac{1-\mathrm{e}^{-t}}{t}\right)^{b-1}=\sum_{n=0}^{N-1}d_{n}(t-\xi)^{n}+r_{N}(t)$

into (7) and obtain

$\displaystyle
I_{x}(a,b)=\frac{\Gamma(a+b)}{\Gamma(a)}\left(\sum_{n=0}^{N-1}d_{n}F_{n}+R_{N}(a,b,x)\right),$

where $F_{n}$ is given by the integral representation

$\displaystyle
F_{n}=\frac{1}{\Gamma(b)}\int_{\xi}^{+\infty}t^{b-1}\mathrm{e}^{-at}(t-\xi)^{n}\,\mathrm{d}t=\frac{\mathrm{e}^{-a\xi}}{\Gamma(b)}\int_{0}^{+\infty}(\tau+\xi)^{b-1}\tau^{n}\mathrm{e}^{-a\tau}\,\mathrm{d}\tau,$
(8)

and the remainder term $R_{N}(a,b,x)$ is defined by

$\displaystyle
R_{N}(a,b,x)=\frac{1}{\Gamma(b)}\int_{\xi}^{+\infty}t^{b-1}\mathrm{e}^{-at}r_{N}(t)\,\mathrm{d}t.$
(9)

The recurrence relation (3) can be obtained from (8) via a simple integration
by parts.

Let, for a moment,

$\displaystyle
c_{n}(a,b)=\int_{0}^{+\infty}(\tau+\xi)^{b-1}\tau^{n}\mathrm{e}^{-a\tau}\,\mathrm{d}\tau.$

Then via integration by parts we find

$\displaystyle ac_{n+1}(a,b)=(n+b)c_{n}(a,b)+\xi(1-b)c_{n}(a,b-1).$ (10)

We make the observation that

$\displaystyle 0\leq\xi
c_{n}(a,b-1)=\xi\int_{0}^{+\infty}(\tau+\xi)^{b-2}\tau^{n}\mathrm{e}^{-a\tau}\,\mathrm{d}\tau\leq
c_{n}(a,b).$ (11)

It follows from (10) and (11) that

$\displaystyle ac_{n+1}(a,b)\leq\begin{cases}(n+1)c_{n}(a,b)&\text{if}\
0<b\leq 1,\\\ (n+b)c_{n}(a,b)&\text{if}\ b\geq 1.\end{cases}$

Since $F_{n}=\mathrm{e}^{-a\xi}c_{n}(a,b)/\Gamma(b)$, this inequality implies
(6).

To obtain the remainder estimate in (2), we use the Cauchy integral
representation

$\displaystyle
r_{N}(t)=\frac{(t-\xi)^{N}}{2\pi\mathrm{i}}\oint_{\\{\xi,t\\}}\frac{\left(\frac{1-\mathrm{e}^{-\tau}}{\tau}\right)^{b-1}}{(\tau-t)(\tau-\xi)^{N}}\,\mathrm{d}\tau,$
(12)

where the contour encircles the points $\xi$ and $t$ once in the positive
sense. From the integral representation (9), we have that $0\leq\xi\leq t$.
Thus, in the case that $N\geq 1$, we can deform the contour in (12) to the
path

$\displaystyle[1+\infty\mathrm{i},1+\pi\mathrm{i}]\cup[1+\pi\mathrm{i},-1+\pi\mathrm{i}]\cup[-1+\pi\mathrm{i},-1-\pi\mathrm{i}]$
$\displaystyle\hphantom{[1+\infty\mathrm{i},1+\pi\mathrm{i}]}{}\cup[-1-\pi\mathrm{i},1-\pi\mathrm{i}]\cup[1-\pi\mathrm{i},1-\infty\mathrm{i}].$

For the integrals along the final three portions of the path, we have the
estimates

$\displaystyle\left|\frac{1}{2\pi\mathrm{i}}\int_{-1+\pi\mathrm{i}}^{-1-\pi\mathrm{i}}\frac{\left(\frac{1-\mathrm{e}^{-\tau}}{\tau}\right)^{b-1}}{(\tau-t)(\tau-\xi)^{N}}\,\mathrm{d}\tau\right|\leq\frac{\max\left((\mathrm{e}-1)^{b-1},\left(\frac{\mathrm{e}+1}{\sqrt{\pi^{2}+1}}\right)^{b-1}\right)}{(1+\xi)^{N+1}},$
$\displaystyle\left|\frac{1}{2\pi\mathrm{i}}\int_{-1-\pi\mathrm{i}}^{1-\pi\mathrm{i}}\frac{\left(\frac{1-\mathrm{e}^{-\tau}}{\tau}\right)^{b-1}}{(\tau-t)(\tau-\xi)^{N}}\,\mathrm{d}\tau\right|\leq\frac{\max\left(\left(\frac{\mathrm{e}^{\pm
1}+1}{\sqrt{\pi^{2}+1}}\right)^{b-1}\right)}{\pi^{N+2}},$ (13)

and

$\displaystyle\left|\frac{1}{2\pi\mathrm{i}}\int_{1-\pi\mathrm{i}}^{1-\infty\mathrm{i}}\frac{\left(\frac{1-\mathrm{e}^{-\tau}}{\tau}\right)^{b-1}}{(\tau-t)(\tau-\xi)^{N}}\,\mathrm{d}\tau\right|\leq\frac{1}{2\pi}\int_{\pi}^{+\infty}\frac{\max\big{(}\big{(}1\pm\mathrm{e}^{-1}\big{)}^{b-1}\big{)}\big{(}s^{2}+1\big{)}^{(1-b)/2}}{\sqrt{s^{2}+(1-t)^{2}}\big{(}s^{2}+(1-\xi)^{2}\big{)}^{N/2}}\,\mathrm{d}s$
$\displaystyle\hphantom{\left|\frac{1}{2\pi\mathrm{i}}\int_{1-\pi\mathrm{i}}^{1-\infty\mathrm{i}}\frac{\left(\frac{1-\mathrm{e}^{-\tau}}{\tau}\right)^{b-1}}{(\tau-t)(\tau-\xi)^{N}}\,\mathrm{d}\tau\right|}{}\leq\frac{\max\big{(}\big{(}1\pm\mathrm{e}^{-1}\big{)}^{b-1}\big{)}}{2\pi}\int_{\pi}^{+\infty}\frac{\big{(}s^{2}+1\big{)}^{(1-b)/2}}{s^{N+1}}\,\mathrm{d}s,$
(14)

respectively. The integrals along the first two portions can be estimated
similarly to (13) and (14). Hence, for $0\leq\xi\leq t$ and $N\geq 1$, we have

$\displaystyle|r_{N}(t)|\leq C_{N}(b)(t-\xi)^{N},$

where the constant $C_{N}(b)$ does not depend on $\xi$. Using this result in
the integral representation (9), we can infer that

$\displaystyle|R_{N}(a,b,x)|\leq C_{N}(b)F_{N}.$

Finally, combining this result with the inequalities (6), we obtain the
required remainder estimate in (2).

The reader can check that the function
$f(t)=\left(\frac{1-\mathrm{e}^{-t}}{t}\right)^{b-1}$ is a solution of the
nonlinear differential equation

$\displaystyle tf(t)f^{\prime\prime}(t)-\frac{b-2}{b-1}tf^{\prime
2}(t)+(t+2)f(t)f^{\prime}(t)+(b-1)f^{2}(t)=0.$

If we substitute the Taylor series (4) into this differential equation and
rearrange the result, we obtain the recurrence relation (5).

### Acknowledgements

This research was supported by a research grant (GRANT11863412/70NANB15H221)
from the National Institute of Standards and Technology. The authors thank the
anonymous referees for their helpful comments and suggestions on the
manuscript.

## References

  * [1] Johnson N.L., Kotz S., Balakrishnan N., Continuous univariate distributions, Vol. 2, 2nd ed., Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Inc., New York, 1995.
  * [2] Olver F.W.J., Lozier D.W., Boisvert R.F., Clark C.W. (Editors), NIST handbook of mathematical functions, U.S. Department of Commerce, National Institute of Standards and Technology, Washington, DC, Cambridge University Press, Cambridge, 2010, Release 1.0.13 of 2016-09-16, available at http://dlmf.nist.gov/.
  * [3] Temme N.M., Special functions. An introduction to the classical functions of mathematical physics, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1996.
  * [4] Temme N.M., Asymptotic methods for integrals, Series in Analysis, Vol. 6, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015.