# Dueling Convex Optimization with General Preferences

Aadirupa Saha Toyota Technological Institute at Chicago (TTIC);
<EMAIL_ADDRESS>Tomer Koren Blavatnik School of Computer Science, Tel Aviv
University and Google Tel Aviv<EMAIL_ADDRESS>Yishay Mansour
Blavatnik School of Computer Science, Tel Aviv University and Google Tel Aviv;
<EMAIL_ADDRESS>
###### Abstract

We address the problem of _convex optimization with dueling feedback_ , where
the goal is to minimize a convex function given a weaker form of _dueling_
feedback. Each query consists of two points and the dueling feedback returns a
(noisy) single-bit binary comparison of the function values of the two queried
points. The translation of the function values to the single comparison bit is
through a _transfer function_. This problem has been addressed previously for
some restricted classes of transfer functions, but here we consider a very
general transfer function class which includes all functions that can be
approximated by a finite polynomial with a minimal degree $p$. Our main
contribution is an efficient algorithm with convergence rate of
$\smash{\widetilde{O}}(\epsilon^{-4p})$ for a smooth convex objective
function, and an optimal rate of $\smash{\widetilde{O}}(\epsilon^{-2p})$ when
the objective is smooth and strongly convex.

##  1 Introduction

Convex optimization algorithms are fundamental across many fields, including
machine learning. Most commonly, convex optimization is studied in a first-
order gradient oracle model, where the optimization algorithm may query
gradients of the objective function. A more limited model is that of zero-
order oracle access, where the optimization algorithm may only query function
values of the objective rather than gradients. Both of these models are
extremely well-studied, and the optimal convergence rates in each of them are
well known (see, e.g., Nesterov, 2003).

However, there are optimization scenarios where even zero-order access is
unavailable or unreliable. Indeed, studies have shown that it is often easier,
faster and involves lesser bias to collect feedback on a relative scale rather
than asking for reward/loss feedback on an absolute scale. For example to
understand the liking for a given pair of items, say (A,B), it is easier for
the users to answer preference-based queries like: “Do you prefer item A over
B?”, rather than their absolute counterparts: “How much do you score items A
and B in a scale of [0-10]?”. Consequently, relative preference queries are
extremely common in domains such as recommendation systems, online
merchandises, search engine optimization, crowd-sourcing, drug testing,
tournament ranking, social surveys, etc (Hajek et al., 2014; Khetan and Oh,
2016). This motivated the introduction of dueling bandits Yue and Joachims
(2009) in the online learning setting.

Drawing motivation from the above, in this paper we study a challenging convex
optimization model where the access to the objective function is through a
_noisy pairwise comparison oracle_. Namely, given an underlying convex
objective function $f:{\mathcal{D}}\mapsto{\mathbb{R}}$
(${\mathcal{D}}\subseteq{\mathbb{R}}^{d}$ being a convex decision space), at
each step the optimization algorithm is allowed to query two points
${\mathbf{w}},{\mathbf{w}}^{\prime}$ in the feasible domain, upon which only a
noisy $1$-bit feedback $o_{t}\in\\{\pm 1\\}$ is revealed, whose expected value
indicates their relative function values. More specifically, the feedback
signal $o_{t}$ is such that

$\displaystyle{\mathbf{E}}[o_{t}\mid{\mathbf{w}},{\mathbf{w}}^{\prime}]=\rho(f({\mathbf{w}})-f({\mathbf{w}}^{\prime})),$

where $\rho:{\mathbb{R}}\mapsto[-1,1]$ is a (possibly nonlinear) _transfer
function_ mapping difference in function values to a signed preference signal,
and $\rho(f({\mathbf{w}})-f({\mathbf{w}}^{\prime}))$ is interpreted as the
degree to which ${\mathbf{w}}$ should be preferred over
${\mathbf{w}}^{\prime}$, or vice versa. Provided such access, our goal is to
find a feasible point that approximately minimizes the objective $f$.
Borrowing terminology from the literature on dueling bandits, we call our
framework _General Dueling Convex Optimization_ (G-DCO) for general transfer
functions.

Noisy pairwise comparison access could potentially be significantly weaker
than the already weak zero-order access. Indeed, a special case of this
framework has been studied by Jamieson et al. (2012) who focused on polynomial
transfer functions of the form
$\rho(x)=c\operatorname{\operatorname{sign}}(x)|x|^{p}$ and gave tight upper
and lower bounds in the pairwise comparison model for _strongly convex and
smooth_ objectives. Their results indicate that as $p$ grows larger, the best
achievable convergence rate degrades quickly, and already when $p>1$ this rate
becomes strictly inferior to that of zero-order optimization. Much more
recently, Saha et al. (2021b) considered a similar pairwise comparison model
with a different type of a transfer function, namely the sign function
$\rho(x)=\operatorname{\operatorname{sign}}(x)$ $(p=0)$, and established fast
convergence rates for this case exclusively.

Both of these works point us at a some fundamental questions: Can we design
algorithms for dueling convex optimization that are able to leverage more
general transfer functions? Can we converge to a minimizer even when the
transfer is unknown to the algorithm? And what properties of the transfer
function dictate the achievable optimization rates? In this paper, we make
progress towards answering these questions.

###  1.1 Our contributions

We make the following main contributions:

  1. (i)

We formalize a generalized dueling convex optimization setting for convex
optimization with pairwise-preference feedback given by a general transfer
function $\rho$, which is only assumed to be well-behaved around the origin
(see Section 2.1 for a precise definition of the query model and optimization
objective). Our framework generalizes and significantly extends two existing
settings of optimization with comparison feedback Jamieson et al. (2012); Saha
et al. (2021b) (Section 2).

  2. (ii)

We give a novel algorithm for dueling convex optimization with a general
transfer function $\rho$, called Relative-Gradient-Descent (Algorithm 1),
which relies on performing a ‘generalized gradient descent’ like update on the
$p^{th}$-degree-scaled _Gradient_ of the objective function $f$ (see 2, 11). 1
explains how $p^{th}$-degree-scaled _Gradient_ is a generalization of gradient
estimate and smoothly interpolates between different types of descent
directions. We prove that when the optimization objective function is smooth,
our algorithm needs an order of $O(\epsilon^{-4p})$ queries to the pairwise-
preference oracle for finding an $\epsilon$-optimal point (see 3). Here, $p$
is the minimal non-zero degree in a series expansion of $\rho(x)$ around zero
(Section 3).

  3. (iii)

We further show that our algorithm can achieve faster convergence rates when
the function is additionally also strongly convex (Algorithm 2, 6).
Concretely, we show that in this case only $O(\epsilon^{-2p})$ pairwise
queries are sufficient for $\epsilon$-convergence. The latter rate is shown to
be tight as it matches existing lower bounds (for certain transfer functions)
for strongly convex optimization with comparison feedback due to Jamieson et
al. (2015) (Section 4).

Our algorithmic results complement those of Saha et al. (2021b), who only
considered the sign transfer function. Compared to the results of Jamieson et
al. (2012), we are able to handle both the convex and strongly convex cases
(while they only deal with the strongly convex case), and we only require the
transfer to be well-behaved around the origin (while they rely on its global
structure111Indeed, their algorithm relies on a line-search procedure at each
step, employing the comparison oracle for implementing a one-dimensional noisy
binary search.). Thus, we are able to encompass a much wider variety of
transfer functions whose local behavior around zero is approximated by a
polynomial—this includes virtually all functions that admit a series expansion
around the origin.

###  1.2 Related work

#### Dueling Bandits.

Due to the widespread applicability and ease of data collection with relative
feedback, learning from preferences has gained much popularity in the machine
learning community and widely studied as the problem of _Dueling-Bandits_ over
last decade (Ailon et al., 2014; Yue et al., 2012; Zoghi et al., 2014a, b,
2015; Saha et al., 2021a; Gajane et al., 2015; Bengs et al., 2021), which is
an online learning framework that generalizes the standard multi-armed bandit
(MAB) (Auer et al., 2002) setting for identifying a set of ‘good’ arms from a
fixed decision-space (set of items) by querying preference feedback of
actively chosen item-pairs.

#### Limitations of Existing Dueling Bandit techniques.

Although the relative feedback variants of stochastic MAB problem have been
widely studied in the literature, the majority of the existing techniques are
restricted to finite decision spaces and stochastic setting which primarily
rely on estimating the entries of the underlying preference-matrix . These
settings, though important as basic steps, are mostly impractical for all real
world scenarios which often involves large (or potentially infinite) decision
spaces, where lies one of the primary motivation of this work. On the other
hand, from an optimization point of view, our work is a key step towards
analyzing the fundamental performance limits of function minimization using
the weaker form of $0/1$ bit relative preferences. The few existing attempts
along this line is discussed in Related Works.

#### Dueling Bandits in continuous spaces.

Surprisingly, following the same spirit of extending standard multi-armed
bandits (MAB) to continuous decision spaces (as in _linear_ or _GP-bandits_),
there has not been much work on the continuous extension of the Dueling Bandit
problem for large (and structured) decision spaces. The works in Sui et al.
(2017); González et al. (2017) did attempt a similar objective, however,
without any satisfactory theoretical performance guarantees. In another recent
work, Brost et al. (2016) address the problem of regret minimization in
continuous _Dueling Bandits_ , however without any finite time regret
guarantee of their proposed algorithms. Recently, Oh and Iyengar (2019); Saha
(2021) consider the problem of regret minimization from $k$-subsetwise
preference feedback ($k=2$ boils down to the dueling setup) on structured
decision spaces, although their underlying utility function is assumed to be
only linear, unlike any general convex function considered in our work;
moreover, their preference model is restricted only to the class of
Multinomial Logit (MNL) based random utility model, unlike the general link
function based preference feedback class that we considered. Dudík et al.
(2015); Saha and Krishnamurthy (2021) represents another line of dueling
bandit work, which incorporates context specific dueling preference model.
Specifically, their algorithms are designed to compete against an abstract
policy set of context to action mappings w.r.t. ‘minimax-regret’. Their
algorithms are also designed to handle potentially large decision spaces,
although, the regret objectives are focused to identifying the von-Neumann
distribution of the underlying preference models, which is very different from
the _function minimization with dueling feedback_ point of view that we
considered.

#### Optimization for dueling feedback.

Along the line of optimization for dueling feedback, Yue and Joachims (2009)
is the first to address the regret minimization problem for fixed functions
$f$ (arm rewards) with preference feedback, although their techniques are
majorly restricted to the class of smooth and differentiable preference
functions that allows gradient estimation. This is the main reason they could
directly apply the classical one-point gradient estimation based _Bandit
Gradient Descent (BGD)_ algorithm of Flaxman et al. (2005) for the setting,
unlike us. Moreover, another limitation of their framework is their
optimization objective is defined in terms of the ‘preferences’ which are
directly observable and hence easier to optimize, as opposed to defining it
w.r.t. $f$ as considered in this work. Following up Yue and Joachims (2009),
Kumagai (2017) considers the similar problem of dueling bandits on continuous
arm set but under rather restrictive sets of assumptions: Twice continuously
differentiable, Lipschitz, strongly convex and smooth score/reward function,
which are often impractical for modeling any real-world preference feedback.

Closest to our work in spirit are Jamieson et al. (2012) and Saha et al.
(2021b), both of which precisely focus on function optimization with relative
pairwise preference feedback. The latter however is designed to work only
under sign based relative feedback which reveals the exact information of
which of the two queried points have smaller function value. We instead
consider a very general class of polynomial based preference functions (see
Section 2) which generalizes the _sign-feedback_ model of Saha et al. (2021b)
as a special case. While the first, although gives provably optimal
convergence rates, their guarantees are restricted to the ‘well behaved’ class
of strongly-convex and smooth functions (with bounded Lipschitz gradient). The
assumptions and consequently their techniques are hence quite restrictive: A
major hindrance towards generalizing their algorithmic ideas to a general
function class is owning to their line-search based coordinate descent
algorithm which is known to fail without strong-convexity. On the other hand,
our algorithm is shown to yield optimal convergence guarantees for more
general class of smooth-convex functions. Additionally we match the
convergence rate of Jamieson et al. (2012) with the additional strong
convexity assumption which shows the generality of our analysis for a large
class of dueling feedback based optimization (G-DCO) problems. As motivated in
our list of contributions, the novelty lies of our analysis lies in the
Relative-Gradient-Descent based optimization approach, which smoothly
interpolates between different complexity classes of different _Dueling Convex
Optimization_ problems based on the degree of the underlying polynomial link
function $p$ (see 1). Besides our method is arguably simpler both in terms of
implementation and analysis.

##  2 Preliminaries and Problem Setup

Notation. Let $[n]=\\{1,2,\ldots n\\}$, for any $n\in{\mathbb{N}}$. Given a
set $S$, for any two items $x,y\in S$, we denote by $x\succ y$ the event $i$
is preferred over $j$. For any $r>0$, let ${\mathcal{B}}_{d}(r)$ and
${\mathcal{S}}_{d}(r)$ denote the ball and the surface of the sphere of radius
$r$ in $d$ dimensions respectively. ${\mathbf{I}}_{d}$ denotes the $d\times d$
identity matrix. For any vector ${\mathbf{x}}\in{\mathbb{R}}^{d}$,
$\|{\mathbf{x}}\|_{2}$ denotes the $\ell_{2}$ norm of vector ${\mathbf{x}}$.

###  2.1 Problem setup

We consider the problem of minimizing a convex and $\beta$-smooth function
$f:{\mathcal{D}}\mapsto{\mathbb{R}}$ defined on a bounded convex domain
${\mathcal{D}}\subseteq{\mathbb{R}}^{d}$ of Euclidean diameter $D$. We denote
by ${\mathbf{w}}^{*}\in\arg\min_{{\mathbf{w}}\in{\mathcal{D}}}f({\mathbf{w}})$
a point where $f$ is minimized over ${\mathcal{D}}$.

#### Query model:

Our access to the objective $f$ is through a noisy comparison oracle that upon
a pair of inputs $({\mathbf{w}},{\mathbf{w}}^{\prime})\in{\mathcal{D}}^{2}$
emits a random binary response $o\in\set{\pm 1}$ such that
${\mathbf{E}}[o\mid{\mathbf{w}},{\mathbf{w}}^{\prime}]=\rho(f({\mathbf{w}})-f({\mathbf{w}}^{\prime}))$,
where $\rho:\mathbb{R}\to[-1,1]$ is a fixed _transfer function_ mapping
difference in function values to (signed) preferences, unknown to the
algorithm. For example, given $\rho$ the query model could output a random
variable $o$ such that
$o\sim\mathrm{Ber}^{\pm}\brk!{\rho(f({\mathbf{w}})-f({\mathbf{w}}^{\prime}))}$
where $\mathrm{Ber}^{\pm}$ denotes a signed version of the Bernoulli
distribution (such that for a random variable $X\sim\mathrm{Ber}^{\pm}(p)$, we
have $\Pr(X=+1)=1-\Pr(X=-1)=\frac{p+1}{2}$).

#### Transfer function:

We will assume throughout that the transfer function
$\rho:{\mathbb{R}}\mapsto[-1,1]$ is fixed and unknown to the algorithm. We
make the following assumptions on $\rho$:

######  Assumption 1.

(i). $\rho$ is differentiable and anti-symmetric (namely, $\rho(-x)=-\rho(x)$
for all $x$) and satisfies $\rho(0)=0$ and
$\operatorname{\operatorname{sign}}(\rho(x))=\operatorname{\operatorname{sign}}(x)$
for $x\neq 0$; (ii) there are constants $p\geq 1$ and $r,c_{\rho}>0$ such that
for all $x\in(-r,r)$ it holds that $\rho^{\prime}(x)\geq c_{\rho}p|x|^{p-1}$.

Following gives the intuition behind the practicability of the above set of
assumptions: Let us define the function
${\tilde{\rho}_{p}}:{\mathbb{R}}\mapsto[-1,1]$ such that
${\tilde{\rho}_{p}}(x)=c_{\rho}\operatorname{\operatorname{sign}}(x)\abs{x}^{p}$.
Then note $\rho$ satisfies
${\rho^{\prime}(x)}\geq{\tilde{\rho}_{p}}^{\prime}(x)=c_{\rho}p|x|^{p-1}$ for
all $x\in(0,r]$. This essentially implies that our class of admissible
transfer functions ($\rho$) admit a series expansion of the form
$\rho(x)=\sum_{n=p}^{\infty}a_{n}x^{n}$ around close neighborhood of $x=0$
with minimal degree $p\geq 1$ (see 1 for a formal justification). We will
henceforth refer _${\tilde{\rho}_{p}}$ as the ‘$p$-th order proxy ’ of
$\rho$_. Note that, one can recover the ‘$\operatorname{\operatorname{sign}}$
feedback’ of Saha et al. (2021b) for $\rho={\tilde{\rho}_{p}}$ with
$p=0,c_{\rho}=1$. 222It is important to note here
$\operatorname{\operatorname{sign}}$ transfer function is not differentiable,
so 1-(ii) become vacuous in this case.

It is also important to note that our assumptions imply that $\rho$ is
monotonically increasing in a small neighborhood of the origin. While we
assume that _$\rho$ is unknown_ to the algorithm, we will implicitly assume
that the parameters $p,r,c_{\rho}$ above are known. (This knowledge will be
used only for optimally tuning the hyper-parameters of our algorithms.)

#### Optimization goal:

The goal of the optimization process is then, given $\epsilon>0$, to find a
point ${\mathbf{w}}$ such that
$f({\mathbf{w}})-f({\mathbf{w}}^{*})\leq\epsilon$ while minimizing the number
of queries to to the comparison oracle.

###  2.2 Admissible Transfer Functions

Our latter assumption on the transfer function $\rho$ is perhaps the most
stringent one; however, it is satisfied by a wide variety of natural transfer
functions: those that admit a series expansion about the origin with uniformly
bounded coefficients.

######  Lemma 1.

Let $\rho$ admit a series expansion $\rho(x)=\sum_{n=p}^{\infty}a_{n}x^{n}$
about $x=0$ with minimal degree $p\geq 1$ and radius of convergence
$\delta>0$. Then, if $a_{p}>0$ and $\abs{na_{n}}\leq M$ for all $n>p$, we have
that

$\displaystyle\abs{\rho^{\prime}(x)}\geq\tfrac{1}{2}pa_{p}\abs{x}^{p-1}\quad\text{for}\quad\abs{x}<\min\set
2{\delta,\frac{pa_{p}}{4M}}.$

Note that since we require $\rho(0)=0$, it must be that $a_{0}=0$ and the
assumption $p\geq 1$ holds naturally. Further, since we would like $\rho(x)>0$
to hold for $x>0$, the first nonzero coefficient must be positive, namely
$a_{p}>0$. Thus, the only non-trivial assumption is that the series
coefficients are uniformly bounded; however, this condition holds for many
natural transfer functions: e.g., for the sigmoidal $\arctan(x)$, hyperbolic
tangent $\tanh(x)$ and for the error function $\mathrm{erf}(x)$, it holds
simply with $M=1$.

###### Proof of 1.

On the interval of convergence $(-\delta,\delta)$ we have
$\rho^{\prime}(x)=\sum_{n=p}^{\infty}na_{n}x^{n-1}$ as one can exchange the
order of summation and differentiation. Let us write
$\rho^{\prime}(x)=pa_{p}x^{p-1}+R(x)$, where $R(x)=\sum_{n>p}na_{n}x^{n-1}$.
Then, for $\abs{x}<\delta\leq\tfrac{1}{2}$,

$\displaystyle\abs{R(x)}\leq\sum_{n>p}\abs{na_{n}}\,\abs{x}^{n-1}\leq
M\abs{x}^{p}\sum_{n=0}^{\infty}\abs{x}^{n}=M\abs{x}^{p}\frac{1}{1-\abs{x}}\leq
2M\abs{x}^{p}.$

Thus, when $\abs{x}\leq pa_{p}/4M$ we have
$\abs{R(x)}\leq\tfrac{1}{2}pa_{p}\abs{x}^{p-1}$. It follows that
$\abs{\rho^{\prime}(x)}\geq
pa_{p}\abs{x}^{p-1}-\abs{R(x)}\geq\tfrac{1}{2}pa_{p}\abs{x}^{p-1}$ as claimed.
∎

##  3 Dueling Convex Optimization with General Transfer Functions

In this section we propose an optimization algorithm for our problem (see
Objective in Section 2) for any convex and $\beta$-smooth $f$ ($\beta>0$).
Note the primary difficulty towards designing an efficient algorithm for the
purpose lies in the fact that we can not hope to estimate the gradient of $f$
for any general dueling/pairwise preference model (i.e. any general $\rho$).
Thus we can not apply the standard _gradient descent_ based techniques to
address this problem (Boyd et al., 2004; Bubeck, 2014; Hazan, 2019).

We get around with the difficulty by noting that, though one may not be able
to estimate the exact gradient of $f$, $\nabla f({\mathbf{w}})$, at a given
point of interest ${\mathbf{w}}\in{\mathcal{D}}$, we can hope to estimate a
‘$p$-th order proxy of $\nabla f({\mathbf{w}})$’, called $p^{th}$-degree-
scaled _Gradient_ of $f$ at ${\mathbf{w}}$, from the $1$-bit preference
feedback generated according to the transfer function (or pairwise preference
model) $\rho$. The following definition and the lemma describes a more formal
argument on this.

######  Definition 2 ($p^{th}$-degree-scaled _Gradient_).

Given any function $f:{\mathbb{R}}^{d}\mapsto{\mathbb{R}}$, we define the
$p^{th}$-degree-scaled _Gradient_ of $f$ at any point
${\mathbf{w}}\in{\mathbb{R}}^{d}$ to be $\nabla f({\mathbf{w}})\norm{\nabla
f({\mathbf{w}})}^{p-1}$ for any $p\geq 1$.

11, in Appendix B, gives a formal justification of the key characteristics of
$p^{th}$-degree-scaled _Gradient_ estimate. 1 gives a more intuitive
explanation of the same and how we exploited it in our optimization algorithm
(Algorithm 1).

######  Remark 1 (Key idea behind Algorithm 1: How it estimates a descent
direction in terms of $p^{th}$-degree-scaled _Gradient_?).

As shown in 11 (Appendix B), the expected value of our ${\mathbf{g}}_{t}$
estimate in Algorithm 1
$({\mathbf{E}}_{{\mathbf{u}}_{t},o_{t}}[{\mathbf{g}}_{t}])$, captures the
estimated $p^{th}$-degree-scaled _Gradient_ (upto constant factors): It
reflects the direction of the gradient $\nabla f({\mathbf{w}})$ (in
expectation) but magnitudewise represents the $p$-order magnitude of that of
the true gradient $\norm{\nabla f({\mathbf{w}})}$. Thus $-{\mathbf{g}}_{t}$
represents a valid descent direction in expectation, since it points to the
negative direction of the gradient (modulo its magnitude is now skewed by the
degree $p$).

It is important to note that $p^{th}$-degree-scaled _Gradient_ at any point
${\mathbf{w}}$ is a power generalization of ‘gradient feedback’ at
${\mathbf{w}}$, $\nabla f({\mathbf{w}})$, which can automatically smoothly
interpolate between different scaling orders of descent directions depending
on the ‘expressiveness’ of the transfer function $\rho$ (captured through
$p$). Clearly, the best case is attained for $p=1$, when our feedback model is
equivalent to the zeroth-order or bandit convex optimization feedback model
(Flaxman et al., 2005), when $p^{th}$-degree-scaled _Gradient_ exactly boils
down to the gradient estimate $\nabla f({\mathbf{w}})$. Moreover, note if
$p=0$, our feedback model recovers the
$\operatorname{\operatorname{sign}}$-feedback model of Saha et al. (2021b) and
in this case our gradient estimate also ${\mathbf{E}}[{\mathbf{g}}_{t}]$
roughly captures the normalized gradient $\frac{\nabla
f({\mathbf{w}})}{\norm{\nabla f({\mathbf{w}})}}$ (direction of the gradient at
${\mathbf{w}}$) on expectation, as used in Saha et al. (2021b) as well.

###  3.1 Algorithm Design: Relative-Gradient-Descent

The crux of the idea lies in designing $p^{th}$-degree-scaled _Gradient_ based
algorithm (Algorithm 1), which is a generalized notion of gradient descent
based optimization technique: The algorithm proceeds sequentially, where at
each step $t$, it maintains a current point of interest
${\mathbf{w}}_{t}\in{\mathcal{D}}$, estimate the $p^{th}$-degree-scaled
_Gradient_ of $f$ at point ${\mathbf{w}}_{t}$ using dueling feedback (as
indicated in 11), and take a ‘carefully chosen small’ step in the negative
direction of the estimated $p^{th}$-degree-scaled _Gradient_ to reach the
updated point of interest ${\mathbf{w}}_{t+1}$.

More formally, the algorithm starts from an initial point
${\mathbf{w}}_{1}\in{\mathcal{D}}$. Now at any round $t=1,2,\ldots$, the
algorithm queries the dueling feedback on a pair of points
$({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t},{\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})$,
such that ${\mathbf{u}}_{t}\sim\text{Unif}({\mathcal{S}}_{d}(1))$ is any
random unit norm $d$-dimensional vector, $\gamma$ being a carefully tuned
perturbation parameter. Upon receiving the $1$-bit preference feedback
$o_{t}\in\\{\pm 1\\}$, it finds a $p^{th}$-degree-scaled _Gradient_ estimate
of $f$ at ${\mathbf{w}}_{t}$ as ${\mathbf{g}}_{t}:=o_{t}{\mathbf{u}}_{t}$
which gives a valid descent direction on expectation as shown in 11 (see 1 for
more insights). It then takes an $\eta$-sized step along the negative
direction of ${\mathbf{g}}_{t}$ to obtain the next iterate
${\mathbf{w}}_{t+1}:={\mathbf{w}}_{t}-\eta{\mathbf{g}}_{t}$ (with suitable
projection if necessary). The details of the algorithm is presented in
Algorithm 1.

3 analyses its convergence guarantees which shows that upon iterating through
the above steps for at most $O(\epsilon^{-4p})$ rounds, the algorithm should
be able to find a desired $\epsilon$-optimal point.

Algorithm 1 Relative-Gradient-Descent

1: Input: Initial point: ${\mathbf{w}}_{1}\in{\mathcal{D}}$, Learning rate
$\eta$, Perturbation parameter $\gamma$, Query budget $T$

2: for $t=1,2,3,\ldots,T$ do

3: Sample ${\mathbf{u}}_{t}\sim\text{Unif}({\mathcal{S}}_{d}(1))$

4: Set ${\mathbf{x}}_{t}^{\prime}:={\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t}$,
${\mathbf{y}}_{t}^{\prime}:={\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t}$

5: Play the duel $({\mathbf{x}}_{t}^{\prime},{\mathbf{y}}_{t}^{\prime})$, and
observe $o_{t}\in{\pm 1}$ such that
$o_{t}\sim\mathrm{Ber}^{\pm}\big{(}\rho\big{(}f({\mathbf{x}}_{t}^{\prime})-f({\mathbf{y}}_{t}^{\prime})\big{)}\big{)}$.

6: Update
$\tilde{\mathbf{w}}_{t+1}\leftarrow{\mathbf{w}}_{t}-\eta{\mathbf{g}}_{t}$,
where ${\mathbf{g}}_{t}=o_{t}{\mathbf{u}}_{t}$

7: Project
${\mathbf{w}}_{t+1}=\arg\min_{{\mathbf{w}}\in{\mathcal{D}}}\norm{{\mathbf{w}}-\tilde{\mathbf{w}}_{t+1}}$

8: end for

Since our proposed Algorithm 1 is based on an iterative ‘$p^{th}$-degree-
scaled _Gradient_ -descent’ based approach (1), the interesting part in it’s
convergence analysis was indeed to understand how this can be exploited to
gradually descent towards the true minimizer ${\mathbf{w}}^{*}$ and reach an
$\epsilon$-optimal point with small enough query complexity. The details are
explained more mathematically in the proof of 3.

###  3.2 Convergence Analysis for Smoothly Convex Functions

######  Theorem 3.

Consider a dueling feedback optimization problem parameterized by any general
admissible transfer function $\rho$ with $p$-th order proxy
${\tilde{\rho}_{p}}$ and a $\beta$ smooth convex function
$f:{\mathcal{D}}\mapsto{\mathbb{R}}$. Then given any $\epsilon>0$, for the
choice of $\gamma=\frac{\tilde{c}\epsilon}{\beta\sqrt{d}D}$ and
$\eta=\frac{pc_{\rho}\tilde{c}^{2p-1}\epsilon^{2p}}{d^{(2p+1)/2}\beta^{p}D^{2p-1}}$,
there exists at least one $t$ such that
${\mathbf{E}}[f({\mathbf{w}}_{t})]-f({\mathbf{w}}^{*})\leq\epsilon$, after at
most
$T=\frac{d^{2p+1}\beta^{2p}D^{4p}}{p^{2}(\tilde{c}^{2p-1}c_{\rho})^{2}\epsilon^{4p}}+1$
iterations; i.e.
$\min_{t\in[T]}{\mathbf{E}}[f({\mathbf{w}}_{t})]-f({\mathbf{w}}^{*})\leq\epsilon$,
where $\tilde{c}=\tfrac{1}{20}$ is a universal constant.

3 shows that for any general transfer function $\rho$ with a $p$-th degree
$p$-th order proxy ${\tilde{\rho}_{p}}$, Algorithm 1 gives a convergence rate
of $O(\epsilon^{-4p})$ to find an $\epsilon$-optimal point. However, 5 shows a
improved convergence rate of $O(\epsilon^{-3})$ for linear $(p=1)$ transfer
functions which recovers the convergence rate obtained in Saha and Tewari
(2011) for smooth convex functions in the _Bandit Convex Optimization_ ($1$
point feedback setting). Moreover, 3 also shows how Algorithm 1 can yield a
faster convergence rate of $O(\epsilon^{-1})$ for
$\operatorname{\operatorname{sign}}$ transfer functions $(p=0)$ which matches
the convergence rate obtained in Saha et al. (2021b) — in fact, not just the
final convergence rate, our algorithm (Relative-Gradient-Descent, Algorithm 1)
generalizes the $\beta$-NGD algorithm of Saha et al. (2021b) since our descent
direction estimate $({\mathbf{g}}_{t})$, exactly behaves like the normalized
gradient (gradient direction) at point ${\mathbf{w}}_{t}$ which was the crux
of their optimization analysis. Please see the proof of 5 for more details.

###### Proof of 3 (sketch).

The complete details of the proofs can be found in Appendix C. We denote by
${\mathcal{H}}_{t}$ the history
$\\{{\mathbf{w}}_{\tau},{\mathbf{u}}_{\tau},o_{\tau}\\}_{\tau=1}^{t-1}\cup{\mathbf{w}}_{t}$
till time $t$. We start by noting that by definition:

${\mathbf{E}}_{o_{t}}[{\mathbf{g}}_{t}\mid{\mathcal{H}}_{t},{\mathbf{u}}_{t}]=\rho(f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})){\mathbf{u}}_{t}$

Base Case: Let us start with the assumption that
$f({\mathbf{w}}_{1})-f({\mathbf{w}}^{*})>\epsilon$ (as otherwise we already
have
$\min_{t\in[T]}{\mathbf{E}}[f({\mathbf{w}}_{t})]-f({\mathbf{w}}^{*})\leq\epsilon$
and there is nothing to prove).

We proceed with the proof inductively, i.e. given ${\mathcal{H}}_{t}$ and
assuming (conditioning on) $f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$,
we can show that ${\mathbf{w}}_{t+1}$ always come closer to the minimum
${\mathbf{w}}^{*}$ on expectation in terms of the $\ell_{2}$-norm. More
formally, given ${\mathcal{H}}_{t}$ and assuming
$f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$ we will show:
${\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}]\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2},$
where
${\mathbf{E}}_{t}[\cdot]:={\mathbf{E}}_{o_{t},{\mathbf{u}}_{t}}[\cdot\mid{\mathcal{H}}_{t}]$
denote the expectation with respect to ${\mathbf{u}}_{t},o_{t}$ given
${\mathcal{H}}_{t}$. The precise statement can be summarized in the following
lemma:

######  Lemma 4 (Roundwise Progress of Relative-Gradient-Descent).

Consider the problem setup of 3 and also the choice of $\eta$, $\gamma$. Then
at any time $t$, during the run of Relative-Gradient-Descent (Algorithm 1),
given ${\mathcal{H}}_{t}$, if
$f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$, we can show that:

$\displaystyle{\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}]\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-\frac{p^{2}(\tilde{c}^{2p-1}c_{\rho})^{2}\epsilon^{4p}}{d^{2p+1}\beta^{2p}D^{4p-2}}$
(1)

###### Proof.

We first note that by our update rule,

$\displaystyle{\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle\leq{\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}]-2\eta{\mathbf{E}}_{t}[\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}]+\eta^{2}$
$\displaystyle=\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-2\eta{\mathbf{E}}_{t}[\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}]+\eta^{2}.$
(2)

On the other hand, since both $f$ and $\rho$ is convex (by assumption), using
9 we get:

$\displaystyle{\mathbf{E}}_{t}[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})]={\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho\brk{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}{\mathbf{u}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})\mid{\mathcal{H}}_{t}}$
$\displaystyle={\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{{\rho\brk{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}}\cdot{{\mathbf{u}}_{t}}\mid{\mathcal{H}}_{t}}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle=\frac{\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}\big{(}\nabla
f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})+\nabla
f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})\big{)}\mid{\mathcal{H}}_{t}}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle=\frac{\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}\big{(}\nabla
f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})+\nabla
f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})\big{)}\mid{\mathcal{H}}_{t}}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*}),$
(3)

where the last equality follows since $\rho(-x)=-\rho(x)$ (see 1-i). Now,
using convexity of $f$ and $\beta$-smoothness, we can further show that:

$\displaystyle{\mathbf{E}}_{t}[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})]\geq\frac{2\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}\brk!{f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})-\beta\gamma^{2}}},$
(4) $\displaystyle\text{and also
}{\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}]\geq{\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs{2\gamma{\mathbf{u}}_{t}\boldsymbol{\cdot}\nabla
f({\mathbf{w}}_{t})}]-\beta\gamma^{2}=2\frac{\tilde{c}\gamma\norm{\nabla
f({\mathbf{w}}_{t})}}{\sqrt{d}}-\beta\gamma^{2}$

where the last equality is due to 8. Additionally, since by assumption
$f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$, i.e. the suboptimality gap
to be at least $\epsilon$, by 10 we can further derive a lower bound:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}]\geq\frac{2\tilde{c}\gamma\epsilon}{\sqrt{d}\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}}-\beta\gamma^{2}={\frac{2\tilde{c}\gamma\epsilon}{\sqrt{d}D}}-\beta\gamma^{2}.$

Now for the choice of $\gamma=\frac{\tilde{c}\epsilon}{\beta\sqrt{d}D}$ since
the lower bound in right hand side is always positive, by monotonicity of
${\tilde{\rho}_{p}}^{\prime}$ in the positive orthant we get:

$\displaystyle\rho({\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}])$
$\displaystyle\geq{\tilde{\rho}_{p}}^{\prime}({\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}])$
$\displaystyle\geq{\tilde{\rho}_{p}}^{\prime}\bigg{(}{\frac{\tilde{c}^{2}\epsilon^{2}}{\beta{d}D^{2}}}\bigg{)}=c_{\rho}p\bigg{(}{\frac{\tilde{c}^{2}\epsilon^{2}}{\beta{d}D^{2}}}\bigg{)}^{p-1},$
(5)

where the first inequality follows by the definition of ${\tilde{\rho}_{p}}$
which is $p$-th order proxy of $\rho$ (see 1), and the last equality follows
since by definition $\rho^{\prime}(x)=c_{\rho}px^{p-1}\text{ for any
}x\in{\mathbb{R}}_{+}$. Finally combining Equations 4 and 3.2, and the choice
of $\gamma$, we can finally derive the lower bound:

$\displaystyle{\mathbf{E}}_{t}[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})]\geq\frac{pc_{\rho}\tilde{c}^{2p-1}\epsilon^{2p}}{d^{(2p+1)/2}\beta^{p}D^{2p-1}},$
(6)

Combining Section 3.2 with Equation 6:

$\displaystyle{\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-2\eta{\mathbf{E}}_{t}[\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}]+\eta^{2}$
$\displaystyle\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-2\eta\Bigg{(}\frac{pc_{\rho}\tilde{c}^{2p-1}\epsilon^{2p}}{d^{(2p+1)/2}\beta^{p}D^{2p-1}}\Bigg{)}+\eta^{2}$
$\displaystyle\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-\Bigg{(}\frac{pc_{\rho}\tilde{c}^{2p-1}\epsilon^{2p}}{d^{(2p+1)/2}\beta^{p}D^{2p-1}}\Bigg{)}^{2},~{}~{}\text{
setting
}\eta=\Bigg{(}\frac{pc_{\rho}\tilde{c}^{2p-1}\epsilon^{2p}}{d^{(2p+1)/2}\beta^{p}D^{2p-1}}\Bigg{)},$

which concludes the claim of 4. ∎

Now coming back to the main proof of 3, note by iteratively taking expectation
over ${\mathcal{H}}_{T}$ on both sides of Equation 1 and summing over
$t=1,\ldots,T$, we get,

$\displaystyle{\mathbf{E}}_{{\mathcal{H}}_{T}}[\norm{{\mathbf{w}}_{T+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle\leq\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}-\frac{p^{2}(\tilde{c}^{2p-1}c_{\rho})^{2}\epsilon^{4p}}{d^{2p+1}\beta^{2p}D^{4p-2}}T.$

However, note if we set
$T=\frac{d^{2p+1}\beta^{2p}D^{4p}}{p^{2}(\tilde{c}^{2p-1}c_{\rho})^{2}\epsilon^{4p}}$,
this implies
${\mathbf{E}}_{{\mathcal{H}}_{T}}[\norm{{\mathbf{w}}_{T+1}-{\mathbf{w}}^{*}}^{2}]\leq
0$, or equivalently ${\mathbf{w}}_{T+1}={\mathbf{w}}^{*}$, which concludes the
claim.

To clarify further, note we show that for any run of Alg. Algorithm 1 if
indeed $f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$ continues to hold
for all $t=1,2,\ldots T$, then ${\mathbf{w}}_{T+1}={\mathbf{w}}^{*}$ at
$T=\frac{d^{2p+1}\beta^{2p}D^{4p}}{p^{2}(\tilde{c}^{2p-1}c_{\rho})^{2}\epsilon^{4p}}$.
If not, there must have been a time $t\in[T]$ such that
$f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})<\epsilon$. ∎

While 3 gives the convergence rate of Algorithm 1 for any general ‘admissible
transfer function’ $\rho$ (see Section 2 for the setup), the following theorem
shows that Algorithm 1 can achieve improved convergence rates for certain
class of special transfer functions, as remarked in 5. The proof is given in
Section C.3.

######  Theorem 5 (Improved Convergence Rate for Special Transfer Functions.).

Algorithm 1 yields improved $\epsilon$-convergence rate ($T_{\epsilon}$) for
some special class of well-defined transfer functions, e.g.:

  1. 1.

Linear transfer functions $\rho(x)=c_{\rho}x,~{}\forall x\in{\mathbb{R}}_{+}$,
then we have $T=\frac{2d^{2}\beta D^{2}}{c_{\rho}^{2}\epsilon^{3}}$;

  2. 2.

Sigmoid transfer functions $\rho(x)=\frac{1-e^{-\omega x}}{1+e^{-\omega
x}},~{}\forall x\in{\mathbb{R}}_{+}$, $\omega>0$, then we have
$T=O\Big{(}\frac{d^{2}\beta D^{2}}{c_{\rho}^{2}\epsilon^{3}}\Big{)}$.

It is worth noting that, for _Linear transfer functions_ , i.e. when
$\rho(x)=c_{\rho}x$ $(p=1)$, our setting is equivalent to the bandit feedback
(or zeroth-order) optimization setting (Flaxman et al., 2005) and our proposed
algorithm obtains the same $O(d^{2/3}T^{-1/3})$ convergence rate of Saha and
Tewari (2011) which is the best known rate till date for zeroth-order smooth
convex optimization with gradient descent based algorithms. Moreover, for
_Sign transfer functions_ , i.e. for
$\rho(x)=\operatorname{\operatorname{sign}}(x)$ ($p=0$), our algorithm can
essentially recovers the $\beta$-NGD algorithm (Algorithm 1) of Saha et al.
(2021b) and hence we can obtain the optimal convergence guarantee of
$T=O\Big{(}\frac{dD\beta}{\epsilon}\Big{)}$ (see analysis of Case-3 in Section
C.3 for details). These results thus show the generalizability of our problem
framework as well as our algorithmic approach (Algorithm 1).

##  4 Strongly Convex Dueling Optimization

In this section, we analyze an epoch-wise version of Relative-Gradient-Descent
(Algorithm 1) which is shown to yield better convergence guarantees for
$\alpha$-strongly convex and $\beta$-smooth functions. The key idea lies in
noting that in order to design an optimal algorithm for $\alpha$-strongly
convex $\beta$-smooth functions, one can simply iteratively reuse any
$\beta$-smoothly convex optimization routine (e.g. we can use our Alg.
Algorithm 1) by running it as a black-box over a successive number of epoch-
wise warm-starts. Our resulting convergence analysis (6) shows that, in this
case the algorithm can find an $\epsilon$-optimal point upon querying just
$O(\epsilon^{-2p})$ pairwise comparisons (as opposed to the
$O(\epsilon^{-4p})$ sample complexity rate for the $\beta$-smooth case, see
3). This is possible due to the nice properties of strong convexity, where
nearness in the suboptimality gap in terms of the function values,
$f({\mathbf{w}})-f({\mathbf{w}}^{*})$ implies nearness in terms of the
$\ell_{2}$-distance from $\norm{{\mathbf{w}}-{\mathbf{w}}^{*}}$ (see the third
property in Lem. 18). In fact the $O(\epsilon^{-2p})$ convergence rate can
shown to be information theoretically optimal (see 2).

###  4.1 Algorithm Design: Epoch-RGD

As motivated above, our proposed method Epoch-RGD (Algorithm 2) uses an
‘epoch-wise black-boxing of a smooth-convex optimization routine’ with ‘warm-
starting’ approach. For our purpose, we use the earlier proposed Relative-
Gradient-Descent (Algorithm 1) as the black-box. More formally, the algorithm,
starts with some initial point ${\mathbf{w}}_{1}$ and runs over a sequence of
$k_{\epsilon}=O\Big{(}\log\frac{\beta D^{2}}{\epsilon}\Big{)}$ epochs: Inside
each epoch $k\in[k_{\epsilon}]$, we call the Relative-Gradient-
Descent$({\mathbf{w}}_{k},\eta_{k},\gamma_{k},t_{k})$ subroutine with the the
initial (warm-start) iterate ${\mathbf{w}}_{k}$, suitably tuned parameters
$\eta_{k},\gamma_{k}$ and a query budget of $t_{k}$. The decision point
returned by Relative-Gradient-Descent after $t_{k}$ steps is considered to the
next iterate, setting ${\mathbf{w}}_{k+1}\leftarrow$ Relative-Gradient-
Descent$({\mathbf{w}}_{k},\eta_{k},\gamma_{k},t_{k})$ and we proceed to the
$(k+1)$-th epoch, warm-starting it with ${\mathbf{w}}_{k+1}$.

The key idea behind the epoch-wise warm-start approach exploits the fact that
between any two consecutive epochs, say $k$ and $k+1$, the $\ell_{2}$ distance
of ${\mathbf{w}}_{k}$ from ${\mathbf{w}}^{*}$ gets reduced by a constant
fraction on an expectation (7). Thus, it can be shown that running the
algorithms for roughly
$k_{\epsilon}=O\Big{(}\log\frac{\beta\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}}{\epsilon}\Big{)}$
epoch, would lead to
$\norm{{\mathbf{w}}_{k_{\epsilon}}-{\mathbf{w}}^{*}}^{2}\leq\epsilon$, which
in turn imply the $\epsilon$-convergence (see the proof of 6 for details). The
formal description of the algorithm is given in Algorithm 2.

Algorithm 2 Epoch-RGD($\epsilon$)

1: Input: Error tolerance $\epsilon>0$

2: Initialize Initial point: ${\mathbf{w}}_{1}\in{\mathbb{R}}^{d}$ such that
$\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}\leq D$, Phase count
$k_{\epsilon}:=\lceil\log_{4/3}\frac{\beta D^{2}}{2\epsilon}\rceil$ $D_{1}=D$,
$B:=\frac{2c_{\rho}p}{(\alpha+\beta)}\Big{(}\big{(}\nicefrac{{\alpha^{2}}}{{4\beta}}\big{)}^{p}\frac{\tilde{c}^{2p-1}}{d^{\frac{2p+1}{2}}}\Big{)}$,
$\tilde{c}\leftarrow$ the universal constant from 8.

3: for $k=1,2,3,\ldots,k_{\epsilon}$ do

4: $\eta_{k}\leftarrow BD_{k}^{2p+1}$,
$\gamma_{k}\leftarrow\frac{\tilde{c}\alpha D_{k}}{2\beta\sqrt{d}}$,
$t_{k}=\frac{1}{2B^{2}{(D_{k}^{2})}^{2p}}$,
$D_{k+1}\leftarrow\sqrt{\frac{3}{4}}D_{k}$.

5: Update ${\mathbf{w}}_{k+1}\leftarrow$ Relative-Gradient-
Descent$\big{(}{\mathbf{w}}_{k},\eta_{k},\gamma_{k},t_{k}\big{)}$

6: end for

7: Return ${\mathbf{w}}_{k_{\epsilon}+1}$

###  4.2 Convergence Analysis for Smooth and Strongly Convex Functions

######  Theorem 6 (Convergence Analysis of Epoch-RGD for Smooth and Strongly
convex Functions).

Consider a dueling feedback optimization problem parameterized by any general
admissible transfer function $\rho$ with $p$-th order proxy
${\tilde{\rho}_{p}}$ and a $\beta$ smooth $\alpha$-strongly convex function
$f:{\mathcal{D}}\mapsto{\mathbb{R}}$. Then given any $\epsilon>0$, the the
final point ${\mathbf{w}}_{k_{\epsilon}+1}$ returned by Algorithm 2 satisfies
${\mathbf{E}}[f({\mathbf{w}}_{t+1})]-f({\mathbf{w}}^{*})\leq\epsilon$, with a
sample complexity of at most $O(\frac{1}{B^{2}{\epsilon}^{2p}})$ pairwise
comparisons. (Here the constant $B$ is as defined in Algorithm 2,
$\tilde{c}=\tfrac{1}{20}$ is a universal constant.

######  Remark 2 (Optimal Convergence of Epoch-RGD for Strongly Convex and
Smooth Functions).

Note if $\rho({\mathbf{x}})$ is exactly of the form
$\rho({\mathbf{x}})=\operatorname{\operatorname{sign}}({\mathbf{x}})\abs{x}^{p}$,
then our dueling (pairwise preference) feedback model is equivalent to the
same used in Jamieson et al. (2012). It is interesting to note that, their
derived lower bound sample complexity for the $\epsilon$-convergence for
smooth and strongly convex functions was indeed shown to be
$\Omega(\epsilon^{-2p})$ which implies the optimality of Epoch-RGD (Algorithm
2) for $\alpha$-strongly convex and $\beta$-smooth functions for any values of
$p$. The line search algorithm proposed by Jamieson et al. (2012) also
achieves the same convergence rate for strongly convex functions, modulo some
additional multiplicative polylogarithmic terms in $d,\epsilon$ etc, which we
do not incur. Also Epoch-RGD is much more modular and simpler to implement as
well as relatively easier to analyze. Besides, the application scope of Epoch-
RGD is much more general that applies to the class of any general transfer
function (as discussed in Section 2) and also works for non-strongly convex
functions (see 3).

Moreover, 6 shows that Algorithm 2 actually gives optimal rates for the
special transfer functions studied earlier, e.g., $O(\epsilon^{-2})$
convergence rate for _linear transfer function_ $(p=1)$ a.k.a. zeroth-order
feedback model (as proved in Hazan and Levy (2014)), or sigmoid based
preference feedback (see 5). Besides it also yields the optimal
$O(\log\frac{1}{\epsilon})$ convergence rate for
$\operatorname{\operatorname{sign}}$ feedback $(p=0)$ (see Theorem $7$ in Saha
et al. (2021b)), since note our algorithm is essentially a generalization of
Algrithm 2 of Saha et al. (2021b) which we can easily recover with the proper
tuning of the algorithm parameters $\eta_{k},\gamma_{k},t_{k}$
($k\in[k_{\epsilon}]$).

###### Proof of 6 (sketch).

The complete details of the proofs can be found in Appendix D. The proof of
the main theorem is based on a key lemma that shows after every epoch of
length $t_{k}$, the distance of the resulting point ${\mathbf{w}}_{k+1}$ from
the optimal ${\mathbf{w}}^{*}$ must decrease by at least a constant fraction.
The formal statement is given below:

######  Lemma 7 (Epochwise Convergence Guarantee of Epoch-RGD).

Consider the problem setup of 6. Then the point ${\mathbf{w}}_{k+1}$ returned
by $k$-th epoch run of Epoch-RGD (Algorithm 2) starting form the initial point
${\mathbf{w}}_{k}$, satisfies:

${\mathbf{E}}[\norm{{\mathbf{w}}_{k+1}-{\mathbf{w}}^{*}}^{2}\mid{\mathbf{w}}_{k}]\leq\frac{3}{4}\norm{{\mathbf{w}}_{k}-{\mathbf{w}}^{*}}^{2},$

$\forall k\in[k_{\epsilon}]$. Where the expectation is taken over the
randomness of the algorithm and the dueling feedback received inside the run
of Relative-Gradient-
Descent$\big{(}{\mathbf{w}}_{k},\eta_{k},\gamma_{k},t_{k}\big{)}$.

The main part of the proof of 7 follows along the similar line of argument as
of 4, however we need to carefully apply the properties of $\alpha$ strong-
convexity of $f$ in order to achieve the improved convergence rates. The
complete details can be found Section D.1. Given 7, claim of 6 now follows
from the following epoch-wise recursion argument:

Let
${\mathcal{H}}_{[k]}:=\\{({\mathbf{w}}_{k^{\prime}})_{k^{\prime}\in[k_{\epsilon}]},({\mathbf{u}}_{t^{\prime}},o_{t^{\prime}})_{t^{\prime}\in[\sum_{k^{\prime}=1}^{k}t_{k^{\prime}}]}\\}\cup\\{{\mathbf{w}}_{k+1}\\}$
denotes the complete history till the end of epoch $k$ starting from the first
epoch $\forall k\in[k_{\epsilon}]$.

Further, let us denote by
${\mathcal{H}}_{k}:=\\{{\mathbf{w}}_{k},({\mathbf{u}}_{t^{\prime}},o_{t^{\prime}})_{t^{\prime}\in[\sum_{k^{\prime}=1}^{k-1}t_{k^{\prime}}+1,\sum_{k^{\prime}=1}^{k}t_{k^{\prime}}]}\\}\cup\\{{\mathbf{w}}_{k+1}\\}$
be the history only within epoch $k$.

Proof of Correctness.  From 7, note we have already established

${\mathbf{E}}_{{\mathcal{H}}_{k}}[\norm{{\mathbf{w}}_{k+1}-{\mathbf{w}}^{*}}^{2}\mid{\mathbf{w}}_{k}]\leq{\frac{3}{4}}\norm{{\mathbf{w}}_{k}-{\mathbf{w}}^{*}}^{2}.$

Applying the argument iteratively over $E$ epochs, and the law of iterated
expectations, we have:

$\displaystyle{\mathbf{E}}_{{\mathcal{H}}_{[E]}}[\norm{{\mathbf{w}}_{E+1}-{\mathbf{w}}^{*}}^{2}]\leq(\nicefrac{{3}}{{4}})^{E}\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}.$
(7)

Thus choosing $E=\lceil\log_{4/3}(\frac{\beta D^{2}}{2\epsilon})\rceil$, where
$\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}\leq D$, we have
$E\geq\log_{4/3}(\frac{\beta\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}}{2\epsilon})~{}\implies~{}(\nicefrac{{3}}{{4}})^{E}\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}\leq\frac{2\epsilon}{\beta}.$

Thus from (7), we get:
${\mathbf{E}}_{{\mathcal{H}}_{[E]}}[\norm{{\mathbf{w}}_{E+1}-{\mathbf{w}}^{*}}^{2}]\leq\frac{2\epsilon}{\beta},$
and further applying $\beta$-smoothness of $f$, we get:

$\displaystyle{\mathbf{E}}_{{\mathcal{H}}_{[E]}}[f({\mathbf{w}}_{E+1})-f({\mathbf{w}}^{*})]\leq{\mathbf{E}}_{{\mathcal{H}}_{[E]}}[\frac{\beta}{2}\norm{{\mathbf{w}}_{E+1}-{\mathbf{w}}^{*}}^{2}]\leq\epsilon,$

which proves the correctness of Algorithm 2 for the choice of total number of
epochs $k_{\epsilon}=E$.

Proof of Sample Complexity.  In order to verify that Algorithm 2 indeed
converges to an $\epsilon$-optimal point in $O(\epsilon^{-2p})$ sample
complexity, note we simply need to count the total sample complexity incurred
in the $k_{\epsilon}$ epochwise runs of Relative-Gradient-Descent (see Line #5
of Algorithm 2). However, by design of Epoch-RGD (Algorithm 2), since
Relative-Gradient-
Descent$\big{(}{\mathbf{w}}_{k},\eta_{k},\gamma_{k},t_{k}\big{)}$ is run for
only $t_{k}=\frac{1}{2B^{2}{(D_{k}^{2})}^{2p}}$ iterations, the total sample
complexity of Epoch-RGD becomes:

$\displaystyle\sum_{k=1}^{k_{\epsilon}}t_{k}$
$\displaystyle=\frac{1}{2B^{2}}\sum_{k=1}^{k_{\epsilon}}\frac{1}{{(D_{k}^{2})}^{2p}}=\frac{1}{2B^{2}(D^{2})^{2p}}\bigg{(}1+\frac{1}{(\nicefrac{{3}}{{4}})^{2p}}+\frac{1}{((\nicefrac{{3}}{{4}})^{2p})^{2}}+\cdots+\frac{1}{((\nicefrac{{3}}{{4}})^{2p})^{k_{\epsilon}-1}}\bigg{)}$
$\displaystyle=\frac{1}{2B^{2}(D^{2})^{2p}}\frac{(\nicefrac{{4}}{{3}}^{2p})^{k_{\epsilon}}-1}{\nicefrac{{4}}{{3}}^{2p}-1}\leq\frac{1}{4B^{2}(D^{2})^{2p}}\Big{(}(\nicefrac{{\beta
D^{2}}}{{2\epsilon}})^{2p}-1\Big{)}=O\Big{(}\frac{1}{B^{2}\epsilon^{2p}}\Big{)}$

where the last inequality is since $k_{\epsilon}=\lceil\log_{4/3}(\frac{\beta
D^{2}}{2\epsilon})\rceil$ by definition. Thus follows the claimed sample
complexity of Epoch-RGD in 6 and this concludes the proof. ∎

##  5 Conclusion and Perspective

We consider the problem of convex optimization under a general class of
pairwise preferences (dueling) feedback. Note the primary difficulty towards
designing an efficient algorithm for the purpose lies in the fact that we can
not hope to estimate the gradient of $f$ for any general dueling/pairwise
preference model. Thus we can not apply the standard _gradient descent_ based
techniques to address this problem. We get around with the difficulty by
estimating a $p$-th order proxy of the gradient, called $p^{th}$-degree-scaled
_Gradient_. The crux of the idea lies in designing Relative-Gradient-Descent
based algorithm (Algorithm 1), which is a generalized notion of gradient
descent based optimization technique. Using this we design an efficient
algorithm with convergence rate of $\smash{\widetilde{O}}(\epsilon^{-4p})$ for
a smooth convex objective function, and an optimal rate of
$\smash{\widetilde{O}}(\epsilon^{-2p})$ when the objective is smooth and
strongly convex.

#### Future work.

Although the derived convergence rate for the strongly convex setting is
information theoretically tight, the exact convergence lower bound is unclear
for the class of smooth functions, which might be an interesting problem to
pursue independently. Another open problem is to analyze this problem beyond
the smoothness assumption. Considering a regret minimization objective instead
of the optimization perspective, as well as understanding the information
theoretic regret performance limit would be interesting direction as well. One
can also consider generalizing the optimization framework to subsetwise
preferences, instead of just pairwise (dueling) feedback. It might also be
useful to extend our setup for contextual scenarios, adversarial preferences
or non-stationary function sequences and understand the scopes of feasible
solutions as well as the impossibility results.

## Acknowledgments

This project has received funding from the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation program (grant
agreement No. 882396), the Israel Science Foundation (grant numbers 993/17;
2549/19), Tel Aviv University Center for AI and Data Science (TAD), the Len
Blavatnik and the Blavatnik Family foundation, and the Yandex Initiative for
Machine Learning at Tel Aviv University.

## References

  * Ailon et al. (2014) Nir Ailon, Zohar Shay Karnin, and Thorsten Joachims.  Reducing dueling bandits to cardinal bandits.  In _ICML_ , volume 32, pages 856–864, 2014.
  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2-3):235–256, 2002.
  * Bengs et al. (2021) Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke Hüllermeier.  Preference-based online learning with dueling bandits: A survey.  _Journal of Machine Learning Research_ , 2021.
  * Boyd et al. (2004) Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Brost et al. (2016) Brian Brost, Yevgeny Seldin, Ingemar J. Cox, and Christina Lioma.  Multi-dueling bandits and their application to online ranker evaluation.  _CoRR_ , abs/1608.06253, 2016.
  * Bubeck (2014) Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _arXiv preprint arXiv:1405.4980_ , 2014.
  * Dudík et al. (2015) Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi.  Contextual dueling bandits.  In _Conference on Learning Theory_ , 2015.
  * Flaxman et al. (2005) Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan.  Online convex optimization in the bandit setting: gradient descent without a gradient.  In _Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms_ , pages 385–394. Society for Industrial and Applied Mathematics, 2005.
  * Fletcher (2013) Roger Fletcher.  _Practical methods of optimization_.  John Wiley & Sons, 2013.
  * Gajane et al. (2015) Pratik Gajane, Tanguy Urvoy, and Fabrice Clérot.  A relative exponential weighing algorithm for adversarial utility-based dueling bandits.  In _Proceedings of the 32nd International Conference on Machine Learning_ , pages 218–227, 2015.
  * González et al. (2017) Javier González, Zhenwen Dai, Andreas Damianou, and Neil D Lawrence.  Preferential bayesian optimization.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 1282–1291. JMLR. org, 2017.
  * Hajek et al. (2014) Bruce Hajek, Sewoong Oh, and Jiaming Xu.  Minimax-optimal inference from partial rankings.  In _Advances in Neural Information Processing Systems_ , pages 1475–1483, 2014.
  * Hazan (2019) Elad Hazan.  Introduction to online convex optimization.  _arXiv preprint arXiv:1909.05207_ , 2019.
  * Hazan and Levy (2014) Elad Hazan and Kfir Levy.  Bandit convex optimization: Towards tight bounds.  In _Advances in Neural Information Processing Systems_ , pages 784–792, 2014.
  * Jamieson et al. (2012) Kevin G Jamieson, Robert Nowak, and Ben Recht.  Query complexity of derivative-free optimization.  In _Advances in Neural Information Processing Systems_ , pages 2672–2680, 2012.
  * Jamieson et al. (2015) Kevin G Jamieson, Sumeet Katariya, Atul Deshpande, and Robert D Nowak.  Sparse dueling bandits.  In _AISTATS_ , 2015.
  * Khetan and Oh (2016) Ashish Khetan and Sewoong Oh.  Data-driven rank breaking for efficient rank aggregation.  _Journal of Machine Learning Research_ , 17(193):1–54, 2016.
  * Kumagai (2017) Wataru Kumagai.  Regret analysis for continuous dueling bandit.  In _Advances in Neural Information Processing Systems 30_ , 2017.
  * Luenberger et al. (1984) David G Luenberger, Yinyu Ye, et al.  _Linear and nonlinear programming_ , volume 2.  Springer, 1984.
  * Nesterov (2003) Yurii Nesterov.  _Introductory lectures on convex optimization: A basic course_ , volume 87.  Springer Science & Business Media, 2003.
  * Nocedal and Wright (1999) Jorge Nocedal and Stephen J Wright.  _Numerical optimization_.  Springer, 1999.
  * Oh and Iyengar (2019) Min-hwan Oh and Garud Iyengar.  Thompson sampling for multinomial logit contextual bandits.  In _Advances in Neural Information Processing Systems_ , pages 3145–3155, 2019.
  * Saha (2021) Aadirupa Saha.  Optimal algorithms for stochastic contextual preference bandits.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Saha and Krishnamurthy (2021) Aadirupa Saha and Akshay Krishnamurthy.  Efficient and optimal algorithms for contextual dueling bandits under realizability.  _arXiv preprint arXiv:2111.12306_ , 2021.
  * Saha et al. (2021a) Aadirupa Saha, Tomer Koren, and Yishay Mansour.  Adversarial dueling bandits.  In _International Conference on Machine Learning_ , 2021a.
  * Saha et al. (2021b) Aadirupa Saha, Tomer Koren, and Yishay Mansour.  Dueling convex optimization.  In _International Conference on Machine Learning_ , pages 9245–9254. PMLR, 2021b.
  * Saha and Tewari (2011) Ankan Saha and Ambuj Tewari.  Improved regret guarantees for online smooth convex optimization with bandit feedback.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 636–642, 2011.
  * Sui et al. (2017) Yanan Sui, Vincent Zhuang, Joel Burdick, and Yisong Yue.  Multi-dueling bandits with dependent arms.  In _Conference on Uncertainty in Artificial Intelligence_ , UAI’17, 2017.
  * Yue and Joachims (2009) Yisong Yue and Thorsten Joachims.  Interactively optimizing information retrieval systems as a dueling bandits problem.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , pages 1201–1208, 2009.
  * Yue et al. (2012) Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims.  The $k$-armed dueling bandits problem.  _Journal of Computer and System Sciences_ , 78(5):1538–1556, 2012.
  * Zoghi et al. (2014a) Masrour Zoghi, Shimon Whiteson, Remi Munos, Maarten de Rijke, et al.  Relative upper confidence bound for the $k$-armed dueling bandit problem.  In _JMLR Workshop and Conference Proceedings_ , pages 10–18. JMLR, 2014a.
  * Zoghi et al. (2014b) Masrour Zoghi, Shimon A Whiteson, Maarten De Rijke, and Remi Munos.  Relative confidence sampling for efficient on-line ranker evaluation.  In _Proceedings of the 7th ACM international conference on Web search and data mining_ , pages 73–82. ACM, 2014b.
  * Zoghi et al. (2015) Masrour Zoghi, Zohar S Karnin, Shimon Whiteson, and Maarten De Rijke.  Copeland dueling bandits.  In _Advances in Neural Information Processing Systems_ , pages 307–315, 2015.

## Supplementary: Dueling Convex Optimization with General Preferences

##  Appendix A Useful Results (used in Sections 3, 3.2 and 4.2)

######  Lemma 8.

For a given vector ${\mathbf{g}}\in{\mathbb{R}}^{d}$ and a random unit vector
${\mathbf{u}}$ drawn uniformly from ${\mathcal{S}}_{d}(1)$, we have

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}}[\abs{{\mathbf{g}}\boldsymbol{\cdot}{\mathbf{u}}}]=\frac{\tilde{c}{\norm{{\mathbf{g}}}}}{\sqrt{d}},$

for some universal constant $\tilde{c}\in[\tfrac{1}{20},1]$.

###### Proof.

Without loss of generality we can assume $\norm{{\mathbf{g}}}=1$, since one
can divide by $\norm{{\mathbf{g}}}$ in both side of Lem. 8 without affecting
the claim. Now to bound
${\mathbf{E}}[\abs{{\mathbf{g}}\boldsymbol{\cdot}{\mathbf{u}}}]$, note that
since ${\mathbf{u}}$ is drawn uniformly from ${\mathcal{S}}_{d}(1)$, by
rotation invariance this equals ${\mathbf{E}}[\abs{u_{1}}]$. For an upper
bound, observe that by symmetry
${\mathbf{E}}[u_{1}^{2}]=\tfrac{1}{d}{\mathbf{E}}[\sum_{i=1}^{d}u_{i}^{2}]=\tfrac{1}{d}$
and thus

$\displaystyle{\mathbf{E}}[\abs{u_{1}}]\leq\sqrt{{\mathbf{E}}[u_{1}^{2}]}=\frac{1}{\sqrt{d}}.$

We turn to prove a lower bound on
${\mathbf{E}}[\abs{{\mathbf{g}}\boldsymbol{\cdot}{\mathbf{u}}}]$. If
${\mathbf{u}}$ were a Gaussian random vector with i.i.d. entries
$u_{i}\sim{\mathcal{N}}(0,1/d)$, then from standard properties of the
(truncated) Gaussian distribution we would have gotten that
${\mathbf{E}}[\abs{u_{1}}]=\sqrt{2/\pi d}$. For ${\mathbf{u}}$ uniformly
distributed on the unit sphere, $u_{i}$ is distributed as
$v_{1}/\norm{{\mathbf{v}}}$ where ${\mathbf{v}}$ is Gaussian with i.i.d.
entries ${\mathcal{N}}(0,1/d)$. We then can write

$\displaystyle\Pr\brk*{\abs{u_{1}}\geq\frac{\epsilon}{\sqrt{d}}}$
$\displaystyle=\Pr\brk*{\frac{\abs{v_{1}}}{\norm{{\mathbf{v}}}}\geq\frac{\epsilon}{\sqrt{d}}}\geq\Pr\brk*{\abs{v_{1}}\geq\frac{1}{\sqrt{d}}\mbox{
and }\norm{{\mathbf{v}}}\leq\frac{1}{\epsilon}}$ $\displaystyle\geq
1-\Pr\brk*{\abs{v_{1}}<\frac{1}{\sqrt{d}}}-\Pr\brk*{\norm{{\mathbf{v}}}>\frac{1}{\epsilon}}.$

Since $\sqrt{d}v_{1}$ is a standard Normal, we have

$\displaystyle\Pr\brk*{\abs{v_{1}}<\frac{1}{\sqrt{d}}}=\Pr\brk*{-1<\sqrt{d}v_{1}<1}=2\Phi(1)-1\leq
0.7,$

and since ${\mathbf{E}}[\norm{{\mathbf{v}}}^{2}]=1$ an application of Markov’s
inequality gives

$\displaystyle\Pr\brk!{\norm{{\mathbf{v}}}>\frac{1}{\epsilon}}=\Pr\brk!{\norm{{\mathbf{v}}}^{2}>\frac{1}{\epsilon^{2}}}\leq\epsilon^{2}{\mathbf{E}}[\norm{{\mathbf{v}}}^{2}]=\epsilon^{2}.$

For $\epsilon=\tfrac{1}{4}$ this implies that $\Pr\brk!{\abs{u_{1}}\geq
1/4\sqrt{d}}\geq\tfrac{1}{5}$, whence
${\mathbf{E}}[\abs{{\mathbf{g}}\boldsymbol{\cdot}{\mathbf{u}}}]={\mathbf{E}}[\abs{u_{1}}]\geq
1/20\sqrt{d}.$ ∎

######  Lemma 9.

Let $g:{\mathbb{R}}^{d}\to{\mathbb{R}}$ be differentiable and let
${\mathbf{u}}$ be a random unit vector in ${\mathbb{R}}^{d}$. Then

$\displaystyle{\mathbf{E}}[g({\mathbf{u}}){\mathbf{u}}]=\frac{1}{d}{\mathbf{E}}[\nabla
g(u)].$

###### Proof.

The above claim follows from Lemma 1 of Flaxman et al. (2005) which shows that
for any differentiable function $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ and any
${\mathbf{x}}\in{\mathbb{R}}^{d}$,

$\displaystyle{\mathbf{E}}[f({\mathbf{x}}+\gamma{\mathbf{u}}){\mathbf{u}}]=\frac{\delta}{d}\nabla{\mathbf{E}}[f({\mathbf{x}}+\gamma{\mathbf{u}})]=\frac{\delta}{d}{\mathbf{E}}[\nabla
f({\mathbf{x}}+\gamma{\mathbf{u}})].$

Fix ${\mathbf{x}}=0$ and substitute
$f({\mathbf{z}})=g(\tfrac{1}{\gamma}{\mathbf{z}})$. Then $\nabla
f({\mathbf{z}})=\frac{1}{\gamma}\nabla g(\frac{1}{\gamma}{\mathbf{z}})$, and
we obtain:

$\displaystyle{\mathbf{E}}[g({\mathbf{u}}){\mathbf{u}}]=\frac{1}{d}{\mathbf{E}}[\nabla
g({\mathbf{u}})].$

∎

######  Lemma 10.

Suppose $f:{\mathcal{D}}\mapsto{\mathbb{R}}$ is a convex function for some
convex set ${\mathcal{D}}\subseteq{\mathbb{R}}^{d}$ such that for any
${\mathbf{x}},{\mathbf{y}}\in{\mathbb{R}}^{d}$,
$f({\mathbf{x}})-f({\mathbf{y}})>\epsilon$. Then this implies $\|\nabla
f({\mathbf{x}})\|>\frac{\epsilon}{\|{\mathbf{x}}-{\mathbf{y}}\|}$. Further,
assuming
$D:=\max_{{\mathbf{x}},{\mathbf{y}}\in{\mathbb{R}}^{d}}\|{\mathbf{x}}-{\mathbf{y}}\|_{2}$,
we get $\|\nabla f({\mathbf{x}})\|>\frac{\epsilon}{D}$ for any
${\mathbf{x}}\in{\mathcal{D}}$.

###### Proof.

The proof simply follows using convexity of $f$ as:

$\displaystyle f({\mathbf{x}})-f({\mathbf{y}})>\epsilon$
$\displaystyle\implies\epsilon<f({\mathbf{x}})-f({\mathbf{y}})\leq\nabla
f({\mathbf{x}})({\mathbf{x}}-{\mathbf{y}})\leq\|\nabla
f({\mathbf{x}})\|_{2}\|{\mathbf{x}}-{\mathbf{y}}\|_{2}$
$\displaystyle\implies\|\nabla
f({\mathbf{x}})\|\geq\frac{\epsilon}{\|{\mathbf{x}}-{\mathbf{y}}\|}.$

∎

##  Appendix B Appendix for Section 3

######  Lemma 11 (Estimation of $p^{th}$-degree-scaled _Gradient_ from Dueling
Feedback from general transfer function $\rho$).

Consider any general admissible transfer function
$\rho:{\mathbb{R}}\mapsto[-1,1]$ (that satisfies 1). Then if
$f:{\mathcal{D}}\mapsto{\mathbb{R}}$ is $L$-Lipschitz and $\beta$-smooth,
given any ${\mathbf{w}}\in{\mathcal{D}}$ such that $r\geq\frac{2L\norm{\nabla
f({\mathbf{w}})}}{\beta\sqrt{d}}$,
$o\sim\mathrm{Ber}^{\pm}\big{(}\rho\big{(}f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}\big{)}$
where ${\mathbf{u}}\sim\text{Unif}({\mathcal{S}}_{d}(1))$, and suitably tuned
step-size $\gamma>0$:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}},o}$
$\displaystyle[o{\mathbf{u}}]\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})\geq\begin{cases}C(d,\beta,c_{\rho},p,r,L)\norm{\nabla
f({\mathbf{w}})}^{2p-1}\nabla{\tilde{f}}({\mathbf{w}})\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*}),&\text{
for any }p\geq 1,\\\ \frac{4\gamma
c_{\rho}}{d}\nabla{\tilde{f}}({\mathbf{w}})\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*}),&\text{
for }p=1.\end{cases}$

Here $\nabla{\tilde{f}}({\mathbf{w}})$ denotes the gradient of the smoothed
function ${\tilde{f}}$ at ${\mathbf{w}}$, where
${\tilde{f}}({\mathbf{w}}):={\mathbf{E}}_{{\mathbf{u}}\sim\text{Unif}({\mathcal{S}}_{d}(1))}[f({\mathbf{w}}+\gamma{\mathbf{u}})]$,
and $C(d,\beta,c_{\rho},p,r,L)$ is a constant dependent on the problem
parameters $d,\beta,c_{\rho},p,r,L$.

###  B.1 Proof of 11

See 11

###### Proof.

We start by noting that given ${\mathbf{w}}$ and denoting
${\mathbf{g}}=o{\mathbf{u}}$:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}},o}[{\mathbf{g}}]$
$\displaystyle={\mathbf{E}}_{{\mathbf{u}}}[{\mathbf{E}}_{o}[o{\mathbf{u}}\mid{\mathbf{u}}]]$
$\displaystyle={\mathbf{E}}_{{\mathbf{u}}}[\rho\big{(}f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}{\mathbf{u}}]$

Let us start with the case for $p\geq 1$. Note since $\rho$ is differentiable
by assumption (see 1-i) as well as $f$, using 9 in the first equality, we get:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}}$
$\displaystyle\brk[s]!{\rho\brk{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})}{\mathbf{u}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})}$
$\displaystyle=\frac{\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}}\brk[s]!{\rho^{\prime}\big{(}f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}\big{(}\nabla
f({\mathbf{w}}+\gamma{\mathbf{u}})+\nabla
f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})$
$\displaystyle\geq\frac{2\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}}\brk[s]!{{\tilde{\rho}_{p}}^{\prime}\big{(}\abs{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})}\big{)}\big{(}\nabla
f({\mathbf{w}}+\gamma{\mathbf{u}})+\nabla
f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*}),$
(8)

where the second equality follows since $\rho^{\prime}(-x)=\rho^{\prime}(x)$
by the anti-symmetry of $\rho$ (see 1-(i)). Note in Section B.1, we further
lower bounded $\rho^{\prime}$ by ${\tilde{\rho}_{p}}^{\prime}$ using 1-(ii)
along with the observation that $\nabla
f({\mathbf{w}}+\gamma{\mathbf{u}})\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})$
is positive for any ${\mathbf{u}}\in{\mathcal{S}}_{d}(1)$ by first order
optimality conditions.

It is important to note that, to ensure $r$-proximity to the origin, as needed
in 1-(ii), it needed to satisfy
$\abs{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})}\leq
r$, which we ensured by choosing $\gamma\leq\frac{r}{2L}$ (as recall by
assumption $f$ is $L$-lipschitz).

Case: $p=1$.  Note in this case from Section B.1 we get:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}}$
$\displaystyle\brk[s]!{\rho\brk{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})}{\mathbf{u}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})}$
$\displaystyle\geq\frac{2\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}}\brk[s]!{c_{\rho}\big{(}\nabla
f({\mathbf{w}}+\gamma{\mathbf{u}})+\nabla
f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})$
$\displaystyle=\frac{2\gamma
c_{\rho}}{d}{\mathbf{E}}_{{\mathbf{u}}}\brk[s]!{\big{(}\nabla
f({\mathbf{w}}+\gamma{\mathbf{u}})+\nabla
f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})$
$\displaystyle=\frac{2\gamma
c_{\rho}}{d}\big{(}\nabla{\mathbf{E}}_{{\mathbf{u}}}\brk[s]!{f({\mathbf{w}}+\gamma{\mathbf{u}})}+\nabla{\mathbf{E}}_{{\mathbf{u}}}\brk[s]!{f({\mathbf{w}}-\gamma{\mathbf{u}})}\big{)}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})=\frac{4\gamma
c_{\rho}}{d}{\nabla{\tilde{f}}({\mathbf{w}})}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*}),$

where the inequality follows since when $p=1$,
${\tilde{\rho}_{p}}^{\prime}(x)=c_{\rho}$ (independent of $x,\,\forall
x\in{\mathbb{R}}$). The last equality follows by exchanging expectation and
derivative (since $f$ is differentiable and finite valued by assumptions).

Case: $p\geq 1$.  Now lets consider the case for any general $p\geq 1$: Now
for the first term in Section B.1, again applying the $\beta$-smoothness of
$f$ we get:

$\displaystyle\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})-\tfrac{1}{2}\beta\gamma^{2}$ $\displaystyle\leq
f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}})\leq\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})+\tfrac{1}{2}\beta\gamma^{2}$
$\displaystyle-\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})-\tfrac{1}{2}\beta\gamma^{2}$ $\displaystyle\leq
f({\mathbf{w}}-\gamma{\mathbf{u}})-f({\mathbf{w}})\leq-\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})+\tfrac{1}{2}\beta\gamma^{2}.$

Subtracting the inequalities, we get

$\displaystyle\abs*{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})-2\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})}\leq\beta\gamma^{2}$ $\displaystyle\implies$ $\displaystyle
2\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})-\beta\gamma^{2}\leq
f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})\leq
2\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla f({\mathbf{w}})+\beta\gamma^{2}.$

Note above implies:
$\abs*{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})}\geq\abs{2\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})}-\beta\gamma^{2}.$ Now using Lem. 4 of Saha et al. (2021b), we
know that:

${\mathbf{P}}_{\mathbf{u}}\big{(}\abs{{\mathbf{u}}^{\top}\nabla
f({\mathbf{w}})}\geq\beta\gamma\big{)}\geq 1-\lambda,\text{ where
}\lambda=\inf_{\gamma^{\prime}>0}\bigg{\\{}\gamma^{\prime}+\frac{2\beta\gamma\sqrt{d\log(1/\gamma^{\prime})}}{\norm{\nabla
f({\mathbf{w}})}}\bigg{\\}}$

for any ${\mathbf{w}}\in{\mathbb{R}}^{d}$. Note choosing
$\gamma^{\prime}=\frac{\beta\gamma\sqrt{d}}{\norm{\nabla f({\mathbf{w}})}}$,
we get $\lambda\leq\frac{\beta\gamma\sqrt{d}}{\norm{\nabla
f({\mathbf{x}})}}\bigg{(}1+2\sqrt{\log\frac{\norm{\nabla
f({\mathbf{x}})}}{\sqrt{d}\beta\gamma}}\bigg{)}$. Note if we further choose
$\gamma\leq\frac{\norm{\nabla f({\mathbf{w}})}}{10\beta\sqrt{d}}$, we have
$\lambda\leq 1/2$.

Thus we have:
${\mathbf{P}}_{\mathbf{u}}\big{(}\abs*{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})}\geq\beta\gamma^{2}\big{)}\geq
1-\lambda,$ and using Section B.1, we further get:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}}$
$\displaystyle\brk[s]!{\rho\brk{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})}{\mathbf{u}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})}$
$\displaystyle\geq\frac{2\gamma(1-\lambda)}{d}{\mathbf{E}}_{{\mathbf{u}}}\brk[s]!{{\tilde{\rho}_{p}}^{\prime}\big{(}\beta\gamma^{2}\big{)}\big{(}\nabla
f({\mathbf{w}}+\gamma{\mathbf{u}})+\nabla
f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*}),$
(9)

Here it is important to note that above lower bound holds since (a) from first
order optimality conditions for any ${\mathbf{u}}\in{\mathcal{S}}_{d}(1)$,
$f({\mathbf{w}}+\gamma{\mathbf{u}})\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})>0$,
and also (b) ${\tilde{\rho}_{p}}^{\prime}\big{(}x\big{)}>0$ for any $x>0$ by
definition of ${\tilde{\rho}_{p}}^{\prime}$.

Thus from Section B.1 we further get:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}}$
$\displaystyle\brk[s]!{\rho\brk{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})}{\mathbf{u}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})}$
$\displaystyle\geq\frac{2\gamma(1-\lambda){\tilde{\rho}_{p}}^{\prime}\big{(}\beta\gamma^{2}\big{)}}{d}{\mathbf{E}}_{{\mathbf{u}}}\brk[s]!{\big{(}\nabla
f({\mathbf{w}}+\gamma{\mathbf{u}})+\nabla
f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})$
$\displaystyle=\frac{2c_{\rho}p(1-\lambda)\gamma^{2p-1}\beta^{p-1}}{d}\big{(}\nabla\tilde{f}({\mathbf{w}}+\gamma{\mathbf{u}})+\nabla\tilde{f}({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*}),$
(10)

The result now follows by noting
${\tilde{\rho}_{p}}^{\prime}(x)=c_{\rho}px^{p-1}\text{ for any
}x\in{\mathbb{R}}_{+}$,
$\nabla{\tilde{f}}({\mathbf{w}})={\mathbf{E}}_{{\mathbf{u}}\sim\text{Unif}({\mathcal{S}}_{d}(1))}[\nabla
f({\mathbf{w}}+\gamma{\mathbf{u}})]$ and choosing
$\gamma=\min\Big{(}\frac{r}{2L},\frac{\norm{\nabla
f({\mathbf{w}})}}{10\beta\sqrt{d}}\Big{)}$. That concludes the proof for any
$p\geq 1$. ∎

######  Remark 3.

It is also worth noting that, for $p=0$, $c_{\rho}=1$, our transfer function
recovers the $\operatorname{\operatorname{sign}}$ feedback of Saha et al.
(2021b). In this case it can be shown that:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}},o}$
$\displaystyle[o{\mathbf{u}}]\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})\geq\frac{1}{40\sqrt{d}}\frac{\nabla
f({\mathbf{w}})\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})}{\norm{\nabla
f({\mathbf{w}})}},$

which ssentially recovers the normalized gradient estimate (or the direction
of the gradient).

The claim for $p=0$ simply follows by consecutively applying Lemma $4$ and $3$
of Saha et al. (2021b) as follows: From Lemma $4$ of Saha et al. (2021b) we
have:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}}$
$\displaystyle[\operatorname{\operatorname{sign}}\big{(}f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}{\mathbf{u}}]\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})\geq(1-\lambda){\mathbf{E}}_{{\mathbf{u}}}[\operatorname{\operatorname{sign}}\big{(}\nabla
f({\mathbf{w}})\boldsymbol{\cdot}{\mathbf{u}}\big{)}{\mathbf{u}}]\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*}),$

where $\lambda$ is as defined in the Case for $p\geq 1$ above. But using Lemma
$3$ of Saha et al. (2021b) we further get:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}}$
$\displaystyle[\operatorname{\operatorname{sign}}\big{(}f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})\big{)}{\mathbf{u}}]\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})\geq\frac{1}{40\sqrt{d}}\frac{\nabla
f({\mathbf{w}})\boldsymbol{\cdot}({\mathbf{w}}-{\mathbf{w}}^{*})}{\norm{\nabla
f({\mathbf{w}})}},$

which concludes the claim choosing
$\gamma=\min\Big{(}\frac{r}{2L},\frac{\norm{\nabla
f({\mathbf{w}})}}{10\beta\sqrt{d}}\Big{)}$ (noting that $\lambda\leq 1/2$ for
this choice of $\gamma$ as explained in the case for $p\geq 1$ above).

##  Appendix C Appendix for Section 3.2

Notations.  We denote by ${\mathcal{H}}_{t}$ the history
$\\{{\mathbf{w}}_{\tau},{\mathbf{u}}_{\tau},o_{\tau}\\}_{\tau=1}^{t-1}\cup{\mathbf{w}}_{t}$
till time $t$, for all $t\in[T]$.
${\mathbf{E}}_{t}[\cdot]:={\mathbf{E}}_{o_{t},{\mathbf{u}}_{t}}[\cdot\mid{\mathcal{H}}_{t}]$
denote the expectation with respect to ${\mathbf{u}}_{t},o_{t}$ given
${\mathcal{H}}_{t}$

###  C.1 Proof of 4

See 4

###### Complete Proof of 4.

First note by our update rule,

$\displaystyle{\mathbf{E}}_{t}[\norm{\tilde{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle={\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}]-2{\eta}{\mathbf{E}}_{t}\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}+\eta^{2}{\mathbf{E}}_{t}\norm{{\mathbf{u}}_{t}}^{2}$
$\displaystyle={\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}]-2\eta{\mathbf{E}}_{t}[\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}]+\eta^{2}.$
(11)

But since projection to ${\mathcal{D}}$ reduces distance from
${\mathbf{w}}^{*}$ we have:

$\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}\leq\norm{\tilde{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}$

This further implies:

$\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}\leq\norm{{\mathbf{w}}_{t+1}^{\prime}-{\mathbf{w}}_{t+1}}^{2}+\norm{{\mathbf{w}}_{t+1}^{\prime}-{\mathbf{w}}^{*}}^{2}\leq\gamma^{2}+\norm{\tilde{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}.$

Applying above in Section C.1 we get:

$\displaystyle{\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle\leq{\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}]-2\eta{\mathbf{E}}_{t}[\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}]+\eta^{2}$
$\displaystyle=\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-2\eta{\mathbf{E}}_{t}[\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}]+\eta^{2}.$
(12)

On the other hand, since both $f$ and $\rho$ is convex (by assumption), using
9 we get:

$\displaystyle{\mathbf{E}}_{t}[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})]={\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho\brk{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}{\mathbf{u}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})\mid{\mathcal{H}}_{t}}$
$\displaystyle={\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{{\rho\brk{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}}\cdot{{\mathbf{u}}_{t}}\mid{\mathcal{H}}_{t}}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle=\frac{\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}\big{(}\nabla
f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})+\nabla
f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})\big{)}\mid{\mathcal{H}}_{t}}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle=\frac{\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}\big{(}\nabla
f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})+\nabla
f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})\big{)}\mid{\mathcal{H}}_{t}}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*}),$
(13)

where the last equality follows since $\rho(-x)=-\rho(x)$ (see 1-i). Now,
since $f$ is convex and $\beta$-smooth, we have that:

$\displaystyle\nabla
f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle\geq
f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}^{*}+\gamma{\mathbf{u}}_{t})$
$\displaystyle\geq f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})+\nabla
f({\mathbf{w}}_{t})\boldsymbol{\cdot}(\gamma{\mathbf{u}}_{t})-\nabla
f({\mathbf{w}}^{*})\boldsymbol{\cdot}(\gamma{\mathbf{u}}_{t})-\beta\norm{\gamma{\mathbf{u}}_{t}}^{2}$
$\displaystyle=f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})+\gamma(\nabla
f({\mathbf{w}}_{t})-\nabla
f({\mathbf{w}}^{*}))\boldsymbol{\cdot}{\mathbf{u}}_{t}-\beta\gamma^{2}.$

Likewise, for the term $\nabla
f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})$
we get,

$\displaystyle\nabla
f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle\geq
f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}^{*}-\gamma{\mathbf{u}}_{t})$
$\displaystyle\geq f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})-\nabla
f({\mathbf{w}}_{t})\boldsymbol{\cdot}(\gamma{\mathbf{u}}_{t})+\nabla
f({\mathbf{w}}^{*})\boldsymbol{\cdot}(\gamma{\mathbf{u}}_{t})-\beta\norm{\gamma{\mathbf{u}}_{t}}^{2}$
$\displaystyle=f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})-\gamma(\nabla
f({\mathbf{w}}_{t})-\nabla
f({\mathbf{w}}^{*}))\boldsymbol{\cdot}{\mathbf{u}}_{t}-\beta\gamma^{2}.$

Summing, we thus get:

$\displaystyle\big{(}\nabla f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})+\nabla
f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})\big{)}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})\geq
2(f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*}))-2\beta\gamma^{2}.$ (14)

Now since by 1-(2) we have $\rho^{\prime}(x)>0$ for any $x\in(0,r]$, we can
claim that

$\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}>0;$

see 4 for a formal justification (on choices of $\gamma$ to satisfy
$\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\leq
r$).

######  Remark 4.

Recall from 1, there exists some constants$p,r,c_{\rho}>0$ such that
$\abs{\rho(x)}\geq\abs{{\tilde{\rho}_{p}}(x)}$ forall $x\in[-r,r]$. Clearly we
apply inequality $(a)$ for
$x=f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})$.
Now to justify indeed
$\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\leq
r$, we note that since $f$ is $\beta$-smooth, it is also locally-lipschitz
inside the bounded domain ${\mathcal{D}}$ and suppose $L$ is the resulting
lipschitz constant. Then we have
$\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\leq
2L\gamma$, and to ensure the above condition, we can assume $2L\gamma\leq r$
by choosing small enough $\gamma$. But since we set
$\gamma=\frac{\tilde{c}\epsilon}{\beta D\sqrt{d}}$, note the constraints are
satisfied for any $\epsilon\leq\frac{r\beta D\sqrt{d}}{2L\tilde{c}}$.

For simplicity, let us denote
${\mathbf{E}}_{{\mathbf{u}}_{t}}[\cdot]:={\mathbf{E}}_{{\mathbf{u}}_{t}}[\cdot\mid{\mathcal{H}}_{t}]$.
Recall, since
$\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}>0$
by 1, now using Equations 14 and C.1, we can write:

$\displaystyle{\mathbf{E}}_{t}$
$\displaystyle[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})]=\frac{\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}\big{(}\nabla
f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})+\nabla
f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})\big{)}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}$
$\displaystyle\geq\frac{2\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}\brk!{f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})-\beta\gamma^{2}}}$
$\displaystyle\geq\frac{2\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}}\brk!{f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})-\beta\gamma^{2}}$
$\displaystyle>\frac{2\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}}\big{)}\brk!{\epsilon-\beta\gamma^{2}}~{}\big{(}\text{since
we conditioned on }f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon\big{)},$
$\displaystyle>\frac{2\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}\abs{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}}{\epsilon/2},$
(15)

where the second last inequality follows since we choose
$\gamma=\frac{\tilde{c}\epsilon}{\beta\sqrt{d}D}$ (recall from 3). However
since $\tilde{c}<1$, note we have $\gamma\leq\frac{\epsilon}{\beta\sqrt{d}D}$
and further since $D>\sqrt{\frac{2\epsilon}{\beta}}$, 333Note otherwise, i.e.
if $D\leq\sqrt{\frac{2\epsilon}{\beta}}$, for any point
${\mathbf{w}}\in{\mathcal{D}}$,
$f({\mathbf{w}})-f({\mathbf{w}}^{*})\leq\epsilon$ by 16 and the optimization
problem of 3 becomes trivial to solve above in turn implies
$\gamma<\sqrt{\frac{\epsilon}{2\beta}}$ and hence
$\brk!{\epsilon-\beta\gamma^{2}}>\frac{\epsilon}{2}$. Last equality is from
1-(ii) where recall that
${\tilde{\rho}_{p}}(x)=c_{\rho}\operatorname{\operatorname{sign}}(x)\abs{x}^{p}$
forall denotes the $p$-th order proxy of $\rho$ and hence
$\rho^{\prime}(x)\geq c_{\rho}px^{p-1}={\tilde{\rho}_{p}}^{\prime}(x)$ for
$x\in[0,r]$. Now applying the $\beta$-smoothness of $f$:

$\displaystyle\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})-\tfrac{1}{2}\beta\gamma^{2}$ $\displaystyle\leq
f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}})\leq\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})+\tfrac{1}{2}\beta\gamma^{2}$
$\displaystyle-\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})-\tfrac{1}{2}\beta\gamma^{2}$ $\displaystyle\leq
f({\mathbf{w}}-\gamma{\mathbf{u}})-f({\mathbf{w}})\leq-\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})+\tfrac{1}{2}\beta\gamma^{2}.$

Subtracting the inequalities, we get

$\displaystyle\abs*{f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})-2\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})}\leq\beta\gamma^{2}$ $\displaystyle\implies$ $\displaystyle
2\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla
f({\mathbf{w}})-\beta\gamma^{2}\leq
f({\mathbf{w}}+\gamma{\mathbf{u}})-f({\mathbf{w}}-\gamma{\mathbf{u}})\leq
2\gamma{\mathbf{u}}\boldsymbol{\cdot}\nabla f({\mathbf{w}})+\beta\gamma^{2}.$

Note above implies:
$\abs*{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}\geq\abs{2\gamma{\mathbf{u}}_{t}\boldsymbol{\cdot}\nabla
f({\mathbf{w}}_{t})}-\beta\gamma^{2}.$

Now taking expectation over ${\mathbf{u}}_{t}$ in both side:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}]\geq{\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs{2\gamma{\mathbf{u}}_{t}\boldsymbol{\cdot}\nabla
f({\mathbf{w}}_{t})}]-\beta\gamma^{2}=2\frac{\tilde{c}\gamma\norm{\nabla
f({\mathbf{w}}_{t})}}{\sqrt{d}}-\beta\gamma^{2}$

where the last equality is due to 8. Additionally, since we assumed
$f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$, i.e. the suboptimality gap
to be at least $\epsilon$, by 10 we can further derive a lower bound:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}]\geq\frac{2\tilde{c}\gamma\epsilon}{\sqrt{d}\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}}-\beta\gamma^{2}={\frac{2\tilde{c}\gamma\epsilon}{\sqrt{d}D}}-\beta\gamma^{2}.$

And now note that setting $\gamma=\frac{\tilde{c}\epsilon}{\beta\sqrt{d}D}$,
the right hand side is positive. Now, lower bounding $\rho^{\prime}$ by
${\tilde{\rho}_{p}}^{\prime}$ as per 1-(ii) and further applying monotonicity
of ${\tilde{\rho}_{p}}^{\prime}(\cdot)$ in the positive orthant, we get:

$\displaystyle\rho^{\prime}({\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}])\geq\rho^{\prime}({\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}])\geq{\tilde{\rho}_{p}}^{\prime}\bigg{(}{\frac{2\tilde{c}\gamma\epsilon}{\sqrt{d}D}}-\beta\gamma^{2}\bigg{)}.$
(16)

Then from Section C.1:

$\displaystyle{\mathbf{E}}_{t}$
$\displaystyle[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})]\geq\frac{2\gamma}{d}{\tilde{\rho}_{p}}^{\prime}\bigg{(}{\frac{2\tilde{c}\gamma\epsilon}{\sqrt{d}D}}-\beta\gamma^{2}\bigg{)}\nicefrac{{\epsilon}}{{2}}~{}~{}(\text{applying
the bound from from }\eqref{eq:may15a})$
$\displaystyle\geq\frac{2\gamma}{d}\Big{(}c_{\rho}p\gamma^{p-1}\abs{\frac{2\tilde{c}\epsilon}{\sqrt{d}D}-\beta\gamma}^{p-1}\Big{)}\nicefrac{{\epsilon}}{{2}}~{}~{}(\text{as,
}{\tilde{\rho}_{p}}^{\prime}(x)=c_{\rho}px^{p-1}\text{ for any
}x\in{\mathbb{R}}_{+}),$ (17)

Then for the above choice of
$\gamma=\frac{\tilde{c}\epsilon}{\beta\sqrt{d}D}$, we finally get:

$\displaystyle{\mathbf{E}}_{t}[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})]$
$\displaystyle\geq\frac{2\gamma\epsilon}{2d}\big{(}c_{\rho}p\gamma^{p-1}\abs{\frac{\tilde{c}^{2}\epsilon^{2}}{{d}D^{2}}}^{p-1}\big{)}$
$\displaystyle=\frac{pc_{\rho}\tilde{c}^{2p-1}\epsilon^{2p}}{d^{(2p+1)/2}\beta^{p}D^{2p-1}},$
(18)

Combining Section C.1 with Section C.1:

$\displaystyle{\mathbf{E}}_{t}$
$\displaystyle[\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}]\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-2\eta{\mathbf{E}}_{t}[\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}]+\eta^{2}$
$\displaystyle\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-2\eta\Bigg{(}\frac{pc_{\rho}\tilde{c}^{2p-1}\epsilon^{2p}}{d^{(2p+1)/2}\beta^{p}D^{2p-1}}\Bigg{)}+\eta^{2}$
$\displaystyle\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-\Bigg{(}\frac{pc_{\rho}\tilde{c}^{2p-1}\epsilon^{2p}}{d^{(2p+1)/2}\beta^{p}D^{2p-1}}\Bigg{)}^{2},~{}~{}\text{
setting
}\eta=\Bigg{(}\frac{pc_{\rho}\tilde{c}^{2p-1}\epsilon^{2p}}{d^{(2p+1)/2}\beta^{p}D^{2p-1}}\Bigg{)},$

which concludes the claim of 4. ∎

###  C.2 Proof of 3

See 3

###### Complete Proof of 3.

We denote by ${\mathcal{H}}_{t}$ the history
$\\{{\mathbf{w}}_{\tau},{\mathbf{u}}_{\tau},o_{\tau}\\}_{\tau=1}^{t-1}\cup{\mathbf{w}}_{t}$
till time $t$.

We start by noting that by definition:

${\mathbf{E}}_{o_{t}}[{\mathbf{g}}_{t}\mid{\mathcal{H}}_{t},{\mathbf{u}}_{t}]=\rho(f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})){\mathbf{u}}_{t}$

We proceed with the proof inductively, i.e. given ${\mathcal{H}}_{t}$ and
assuming (conditioning on) $f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$,
we can show that ${\mathbf{w}}_{t+1}$ always come closer to the minimum
${\mathbf{w}}^{*}$ on expectation in terms of the $\ell_{2}$-norm. More
formally, given ${\mathcal{H}}_{t}$ and assuming
$f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$ we will show:

${\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}]\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}$

where
${\mathbf{E}}_{t}[\cdot]:={\mathbf{E}}_{o_{t},{\mathbf{u}}_{t}}[\cdot\mid{\mathcal{H}}_{t}]$
denote the expectation with respect to ${\mathbf{u}}_{t},o_{t}$ given
${\mathcal{H}}_{t}$. The precise statement is given by 4.

Given the statement of 4, now note that by iteratively taking expectation over
${\mathcal{H}}_{T}$ on both sides of Equation 1 and summing over
$t=1,\ldots,T$, we get,

$\displaystyle{\mathbf{E}}_{{\mathcal{H}}_{T}}[\norm{{\mathbf{w}}_{T+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle\leq\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}-\frac{p^{2}(\tilde{c}^{2p-1}c_{\rho})^{2}\epsilon^{4p}}{d^{2p+1}\beta^{2p}D^{4p-2}}T.$

However, note if we set
$T=\frac{d^{2p+1}\beta^{2p}D^{4p}}{p^{2}(\tilde{c}^{2p-1}c_{\rho})^{2}\epsilon^{4p}}$,
this implies
${\mathbf{E}}_{{\mathcal{H}}_{T}}[\norm{{\mathbf{w}}_{T+1}-{\mathbf{w}}^{*}}^{2}]\leq
0$, or equivalently ${\mathbf{w}}_{T+1}={\mathbf{w}}^{*}$, which concludes the
claim.

To clarify further, note we show that for any run of Alg. Algorithm 1 if
indeed $f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$ continues to hold
for all $t=1,2,\ldots T$, then ${\mathbf{w}}_{T+1}={\mathbf{w}}^{*}$ at
$T=\frac{d^{2p+1}\beta^{2p}D^{4p}}{p^{2}(\tilde{c}^{2p-1}c_{\rho})^{2}\epsilon^{4p}}$.
If not, there must have been a time $t\in[T]$ such that
$f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})<\epsilon$. This concludes the proof
with $T_{\epsilon}=T$. ∎

###  C.3 Proof of 5

See 5

###### Proof.

Case 1. Linear transfer functions: $\rho(x)=c_{\rho}x,~{}\forall
x\in{\mathbb{R}}_{+}$. So in this case $\rho$ is the $p$-th order proxy of
itself, i.e. ${\tilde{\rho}_{p}}=\rho$ with $p=1$ and any $r\in{\mathbb{R}}$.

Here $\rho^{\prime}(x)=c_{\rho}$ for any $x\in{\mathbb{R}}$. Then following
the same steps as derived in the proof of 3, note we have,

$\displaystyle{\mathbf{E}}_{t}[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})]$
$\displaystyle\geq\frac{2\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}{f({\mathbf{w}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{w}}_{t}-\gamma{\mathbf{u}}_{t})}}\big{)}\brk!{f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})-\beta\gamma^{2}}$
$\displaystyle=\frac{2\gamma}{d}c_{\rho}\brk!{f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})-\beta\gamma^{2}}$

Moreover, since we conditioned on
$f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})>\epsilon$, plugging this in above and
combining with

$\displaystyle{\mathbf{E}}_{t}[\norm{{\mathbf{w}}_{t+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-\frac{4\eta\gamma
c_{\rho}}{d}\Bigg{(}\brk!{f({\mathbf{w}}_{t})-f({\mathbf{w}}^{*})}-\beta\gamma^{2}\Bigg{)}+\eta^{2}$
$\displaystyle\leq\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-\frac{4\eta\gamma
c_{\rho}}{d}\Bigg{(}\epsilon-\beta\gamma^{2}\Bigg{)}+\eta^{2}$
$\displaystyle\overset{(a)}{=}\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-\frac{4\eta
c_{\rho}}{d}\big{(}\frac{\epsilon^{3/2}}{2\sqrt{2\beta}}\big{)}+\eta^{2}$
$\displaystyle\overset{(b)}{=}\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}}^{2}-\frac{c_{\rho}^{2}\epsilon^{3}}{2\beta
d^{2}},$

where $(a)$ follows by setting $\gamma=\sqrt{\frac{\epsilon}{2\beta}}$, and
$(b)$ follows by setting $\eta=\frac{c_{\rho}\epsilon^{3/2}}{d\sqrt{2\beta}}$.

Then same as the proof of 3, now iteratively taking expectations over
${\mathcal{H}}_{T}$ on both sides of Equation 1 and summing over
$t=1,\ldots,T$, we get,

$\displaystyle{\mathbf{E}}_{{\mathcal{H}}_{T}}[\norm{{\mathbf{w}}_{T+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle\leq\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}-\frac{c_{\rho}^{2}\epsilon^{3}}{2\beta
d^{2}}T.$

However, note if we set $T=\frac{2d^{2}\beta
D^{2}}{c_{\rho}^{2}\epsilon^{3}}$, this implies
${\mathbf{E}}_{{\mathcal{H}}_{T}}[\norm{{\mathbf{w}}_{T+1}-{\mathbf{w}}^{*}}^{2}]\leq
0$, or equivalently ${\mathbf{w}}_{T+1}={\mathbf{w}}^{*}$, which concludes the
claim (similarly as line of argument we concluded the proof of 3).

Case 2. Sigmoid transfer functions: $\rho(x)=\frac{1-e^{-\omega
x}}{1+e^{-\omega x}},~{}\forall x\in{\mathbb{R}}_{+}$, $\omega>0$. In this
case the it can be shown that $\rho$ can be approximated by a linear function
near the origin, or more specifically, depending on the constant $\omega$,
there exists $c_{\rho}^{\omega}$ and $r^{\omega}$ such that

$\abs{\rho(x)}\geq c_{\rho}^{\omega}\abs{x}~{}\forall
x\in[-r^{\omega},r^{\omega}].$

The claimed convergence bound now follows similar to the analysis shown for
Case $1$ above.

Case 3. Sign transfer function:
$\rho(x)=\operatorname{\operatorname{sign}}(x),~{}\forall
x\in{\mathbb{R}}_{+}$.

In this case also, $\rho$ is the $p$-th order proxy of itself, with $p=0$,
$c_{\rho}=1$ and any $r\in{\mathbb{R}}$. This particular transfer function was
considered in the similar optimization setup in Saha et al. (2021b). We show
below how our proposed Algorithm 1 (Relative-Gradient-Descent) generalizes
their $\beta$-NGD algorithm and recovers their convergence rate of
$O(\epsilon^{-1})$.

We start by noting that, our algorithm generalizes the $\beta$-NGD algorithm
of Saha et al. (2021b). The convergence rate claim now follows by noting that
in this case our descent direction ${\mathbf{g}}_{t}$ at any point
${\mathbf{w}}_{t}$, becomes the normalized gradient estimate, of
${\mathbf{w}}_{t}$ with high probability (over the random draws of
${\mathbf{u}}_{t}$). Roughly speaking it can be show that

${\mathbf{E}}_{{\mathbf{u}}_{t}}[{\mathbf{g}}_{t}\mid{\mathbf{w}}_{t}]\approx\frac{\tilde{c}}{\sqrt{d}}\big{(}\nicefrac{{\nabla
f({\mathbf{w}}_{t})}}{{\norm{\nabla f({\mathbf{w}}_{t})}}}\big{)},$

using Lemma $2$ and $4$ of Saha et al. (2021b), or more precisely,

${\mathbf{E}}_{{\mathbf{u}}_{t}}[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})\mid{\mathbf{w}}_{t}]\geq\frac{\tilde{c}}{\sqrt{d}}\bigg{(}\frac{\nabla
f({\mathbf{w}}_{t})\boldsymbol{\cdot}({\mathbf{w}}_{t}-{\mathbf{w}}^{*})}{\norm{\nabla
f({\mathbf{w}}_{t})}}\bigg{)}-2\lambda\norm{{\mathbf{w}}_{t}-{\mathbf{w}}^{*}},$

where $\lambda=\frac{3\beta\delta}{\|\nabla
f({\mathbf{w}}_{t})\|}\sqrt{d\log\frac{\|\nabla
f({\mathbf{w}}_{t})\|}{\sqrt{d}\beta\delta}}$. Combining the above bound in
the proof of 3 (to lower bound the term
${\mathbf{E}}_{t}[{\mathbf{g}}_{t}\cdot({\mathbf{w}}_{t}-{\mathbf{w}}^{*})]$),
the result follows. In fact in this case the proof of 3 exactly follows the
same line of argument as that of the proof of Theorem $5$ of Saha et al.
(2021b). This shows the generalization ability of our proof analysis for
different special class of transfer functions. ∎

##  Appendix D Appendix for Section 4.2

###  D.1 Proof of 7

See 7

###### Complete Proof of 7.

The proof relies on analyzing the epochwise performance guarantee of any
representative run Relative-Gradient-
Descent$\big{(}{\mathbf{w}}_{k},\eta_{k},\gamma_{k},t_{k}\big{)}$ (see Line #5
of Algorithm 2).

For simplicity of notations, for any epoch $k$, inside the call of Relative-
Gradient-Descent$\big{(}{\mathbf{w}}_{k},\eta_{k},\gamma_{k},t_{k}\big{)}$,
let us assume ${\mathbf{x}}_{1}(={\mathbf{w}}_{k})$ denotes the initial point
in the run of Relative-Gradient-Descent (Algorithm 1) and let is denote by
$D_{0}=\norm{{\mathbf{x}}_{1}-{\mathbf{w}}^{*}}$. The goal is to analyze the
guarantees on the output point ${\mathbf{x}}_{T+1}$ of the run of
$p^{th}$-degree-scaled _Gradient_ after $T=t_{k}$ time steps; thus
${\mathbf{x}}_{T+1}={\mathbf{w}}_{k+1}$. We use the same notations as used in
the proof of 3.

Recall from Section C.1, at any time step $t$ inside the run of
$p^{th}$-degree-scaled _Gradient_ we have:

$\displaystyle{\mathbf{E}}_{t}[\norm{{\mathbf{x}}_{t+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle\leq\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}^{2}-2\eta{\mathbf{E}}_{t}\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{x}}_{t}-{\mathbf{w}}^{*})}+\eta^{2},$
(19)

and on the other hand, from Section C.1 we have:

$\displaystyle{\mathbf{E}}_{t}[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{x}}_{t+1}-{\mathbf{w}}^{*})]={\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho\brk{f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})}{\mathbf{u}}_{t}\mid{\mathcal{H}}_{t}}\boldsymbol{\cdot}({\mathbf{x}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle=\frac{\gamma}{d}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\rho^{\prime}\big{(}\abs{f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})}\big{)}\big{(}\nabla
f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})+\nabla
f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})\big{)}\mid{\mathcal{H}}_{t}}\boldsymbol{\cdot}({\mathbf{x}}_{t}-{\mathbf{w}}^{*}).$
(20)

Now since $f$ is convex and $\beta$-smooth, applying 19, we know that for any
${\mathbf{w}}\in{\mathcal{D}}$,

$\displaystyle\big{(}\nabla f({\mathbf{w}})-\nabla
f({\mathbf{w}}^{*})\big{)}^{\top}({\mathbf{w}}-{\mathbf{w}}^{*})\geq\frac{\alpha\beta}{\alpha+\beta}\norm{{\mathbf{w}}-{\mathbf{w}}^{*}}^{2}+\frac{1}{\alpha+\beta}\norm{\nabla
f({\mathbf{w}})-\nabla f({\mathbf{w}}^{*})}^{2}.$

Moreover since ${\mathbf{w}}^{*}$ is the minimizer of $f$ in ${\mathcal{D}}$,
we have $\nabla
f({\mathbf{w}}^{*})\boldsymbol{\cdot}({\mathbf{x}}_{t}-{\mathbf{w}}^{*})\geq
0$ (from first order optimality conditions, see 14). Hence from above we
further get:

$\displaystyle\nabla f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})$
$\displaystyle\boldsymbol{\cdot}({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*})\geq\big{(}\nabla
f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-\nabla
f({\mathbf{w}}^{*})\big{)}\boldsymbol{\cdot}({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle\geq\frac{\alpha\beta}{\alpha+\beta}\norm{{\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*}}^{2}+\frac{1}{\alpha+\beta}\norm{\nabla
f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-\nabla f({\mathbf{w}}^{*})}^{2}.$

Likewise,

$\displaystyle\nabla f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})$
$\displaystyle\boldsymbol{\cdot}({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*})\geq\frac{\alpha\beta}{\alpha+\beta}\norm{{\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*}}^{2}+\frac{1}{\alpha+\beta}\norm{\nabla
f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})-\nabla f({\mathbf{w}}^{*})}^{2}.$

Combining the two, we get:

$\displaystyle\nabla
f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})\boldsymbol{\cdot}({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*})+\nabla
f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})\boldsymbol{\cdot}({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle\geq\frac{\alpha\beta}{\alpha+\beta}(\norm{{\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*}}^{2}+\norm{{\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*}}^{2})$
$\displaystyle\quad\quad\quad\quad\quad\quad+\frac{1}{\alpha+\beta}(\norm{\nabla
f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-\nabla
f({\mathbf{w}}^{*})}^{2}+\norm{\nabla
f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})-\nabla f({\mathbf{w}}^{*})}^{2})$
$\displaystyle\overset{(a)}{\geq}\frac{\alpha\beta}{\alpha+\beta}(\norm{{\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*}}^{2}+\norm{{\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*}}^{2})+\frac{\alpha}{\alpha+\beta}(\norm{{\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*}}^{2}+\norm{{\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t}-{\mathbf{w}}^{*}}^{2})$
$\displaystyle=\frac{2(\alpha\beta+\alpha)}{\alpha+\beta}(\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}^{2}+\gamma^{2}\norm{{\mathbf{u}}_{t}}^{2})=\frac{2(\alpha\beta+\alpha)}{\alpha+\beta}(\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}^{2}+\gamma^{2}),$

where the inequality $(a)$ follows due to 18. Thus we can write:

$\displaystyle\nabla f({\mathbf{x}}_{t}+$
$\displaystyle\gamma{\mathbf{u}}_{t})\boldsymbol{\cdot}({\mathbf{x}}_{t}-{\mathbf{w}}^{*})+\nabla
f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})\boldsymbol{\cdot}({\mathbf{x}}_{t}-{\mathbf{w}}^{*})$
$\displaystyle\geq\frac{2(\alpha\beta+\alpha)}{\alpha+\beta}(\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}^{2}+\gamma^{2})-\gamma(\nabla
f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-\nabla
f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t}))\boldsymbol{\cdot}{\mathbf{u}}_{t}$
$\displaystyle\overset{(b)}{\geq}\frac{2(\alpha\beta+\alpha)}{\alpha+\beta}(\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}^{2}+\gamma^{2})-\gamma\norm{\nabla
f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-\nabla
f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})}$
$\displaystyle\geq\frac{2(\alpha\beta+\alpha)}{\alpha+\beta}(\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}^{2}+\gamma^{2})-2\beta\gamma^{2}$
$\displaystyle=\frac{2\alpha(\beta+1)}{\beta(\tilde{\kappa}+1)}\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}^{2}-\frac{2(\beta-\tilde{\kappa})}{\tilde{\kappa}+1}\gamma^{2},$
(21)

where $(b)$ follows from Cauchy-Schwarz, the last inequality holds due to 16,
and $\tilde{\kappa}:=\frac{\alpha}{\beta}$.

Recall we assumed $\norm{{\mathbf{x}}_{1}-{\mathbf{w}}^{*}}=D_{0}$. Let
$T(=t_{k})$ be the sample complexity of the run Relative-Gradient-
Descent$\big{(}{\mathbf{w}}_{k},\eta_{k},\gamma_{k},t_{k}\big{)}$, i.e. the
Relative-Gradient-Descent runs for $T$ time-steps starting from the initial
point ${\mathbf{x}}_{1}={\mathbf{w}}_{k}$.

Case analysis 1: (Assume $\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}\geq
D_{0}/2$ for all $t=[T]$).  In this case, by assumption,
$\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}\geq D_{0}/2$. So from above we
further get:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})}]\geq\frac{2\tilde{c}\alpha\gamma
D_{0}}{2\sqrt{d}}-\beta\gamma^{2}.$

And now note that setting $\gamma=\frac{\tilde{c}\alpha
D_{0}}{2\beta\sqrt{d}}$, the right hand side is positive. Further using 1-(3)
and by the definition of ${\tilde{\rho}_{p}}$, we get:

$\displaystyle{\mathbf{E}}_{{\mathbf{u}}_{t}}[\rho^{\prime}(\abs*{f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})})]$
$\displaystyle\geq{\mathbf{E}}_{{\mathbf{u}}_{t}}[{\tilde{\rho}_{p}}^{\prime}(\abs*{f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})})]$
$\displaystyle\geq{\tilde{\rho}_{p}}^{\prime}({\mathbf{E}}_{{\mathbf{u}}_{t}}[\abs*{f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})}])$
$\displaystyle\geq{\tilde{\rho}_{p}}^{\prime}\bigg{(}\frac{2\tilde{c}\alpha\gamma
D_{0}}{2\sqrt{d}}-\beta\gamma^{2}\bigg{)}={\tilde{\rho}_{p}}^{\prime}\bigg{(}\frac{\tilde{c}^{2}\alpha^{2}D_{0}^{2}}{4\beta
d}\bigg{)}.$ (22)

where the second and the third inequalities are respectively due to Jensen’s
inequality, as by definition ${\tilde{\rho}_{p}}^{\prime}$ is convex (for any
$p\geq 1$) in the positive orthant and also monotonically increasing. Further
by denoting $A=\frac{\alpha(\beta+1)}{\beta(\tilde{\kappa}+1)}$ and
$A^{\prime}=\frac{(\beta-\tilde{\kappa})}{\tilde{\kappa}+1}$, note that for
this choice of $\gamma$ we have

$\displaystyle
A\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}^{2}-A^{\prime}\gamma^{2}$
$\displaystyle>\frac{\alpha(\beta+1)}{\beta(\tilde{\kappa}+1)}\frac{D_{0}^{2}}{4}-\frac{(\beta-\tilde{\kappa})}{\tilde{\kappa}+1}\bigg{(}\frac{\tilde{c}\alpha
D_{0}}{2\beta\sqrt{d}}\bigg{)}^{2}$
$\displaystyle\overset{(c)}{\geq}\frac{\alpha(\beta+1)}{\beta(\tilde{\kappa}+1)}\frac{D_{0}^{2}}{4}-\frac{(\beta-\tilde{\kappa})}{\tilde{\kappa}+1}\bigg{(}\frac{\alpha^{2}D_{0}^{2}}{4\beta^{2}{d}}\bigg{)}$
$\displaystyle\overset{}{\geq}\frac{\alpha(\beta+1)}{\beta(\tilde{\kappa}+1)}\frac{D_{0}^{2}}{4}-\frac{\alpha^{2}}{\beta{d}(\tilde{\kappa}+1)}\frac{D_{0}^{2}}{4}$
$\displaystyle\geq\frac{\alpha(\beta+1)}{\beta(\tilde{\kappa}+1)}\frac{D_{0}^{2}}{4}-\frac{\alpha^{2}}{\beta{d}(\tilde{\kappa}+1)}\frac{D_{0}^{2}}{4}$
$\displaystyle=\frac{\alpha(\beta+1-\alpha/d)}{\beta(\tilde{\kappa}+1)}\frac{D_{0}^{2}}{4}>\frac{\alpha}{\alpha+\beta}\frac{D_{0}^{2}}{4},$

where $(c)$ follows since $\tilde{c}\leq 1$ (as follows form 8), and the last
inequality is due to the fact that by definition $\beta\geq\alpha$ and $d\geq
1$. Then combining above with Sections D.1 and LABEL:{eq:may15} we have:

$\displaystyle{\mathbf{E}}_{t}$
$\displaystyle[{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{x}}_{t}-{\mathbf{w}}^{*})]\geq\frac{2\gamma}{d}{\tilde{\rho}_{p}}^{\prime}\big{(}{\mathbf{E}}_{{\mathbf{u}}_{t}}\brk[s]!{\abs{f({\mathbf{x}}_{t}+\gamma{\mathbf{u}}_{t})-f({\mathbf{x}}_{t}-\gamma{\mathbf{u}}_{t})}}\big{)}\bigg{(}\frac{\alpha}{\alpha+\beta}\frac{D_{0}^{2}}{4}\bigg{)}$
$\displaystyle\geq\frac{2\alpha
D_{0}^{2}}{d(\alpha+\beta)4}\bigg{(}\frac{\tilde{c}\alpha
D_{0}}{2\beta\sqrt{d}}\bigg{)}\rho^{\prime}\bigg{(}\frac{\tilde{c}^{2}\alpha^{2}D_{0}^{2}}{4\beta
d}\bigg{)}~{}~{}(\text{from }\eqref{eq:may15},\text{ where recall we needed to
set }\gamma=\frac{\tilde{c}\alpha D_{0}}{2\beta\sqrt{d}})$
$\displaystyle=\frac{2\alpha
D_{0}^{2}}{d(\alpha+\beta)4}\bigg{(}\frac{\tilde{c}\alpha
D_{0}}{2\beta\sqrt{d}}\bigg{)}c_{\rho}p\bigg{(}\frac{\tilde{c}^{2}\alpha^{2}D_{0}^{2}}{4\beta
d}\bigg{)}^{p-1}~{}~{}(\text{as, }\rho^{\prime}(x)=c_{\rho}px^{p-1}\text{ for
any }x\in{\mathbb{R}}_{+})$
$\displaystyle=BD_{0}^{2p+1},~{}~{}\bigg{(}\text{where we denote by,
}B:=\frac{2c_{\rho}p}{(\alpha+\beta)}\Big{(}\big{(}\nicefrac{{\alpha^{2}}}{{4\beta}}\big{)}^{p}\frac{\tilde{c}^{2p-1}}{d^{\frac{2p+1}{2}}}\Big{)}\bigg{)}.$
(23)

Plugging the above expression in Equation 19:

$\displaystyle{\mathbf{E}}_{t}$
$\displaystyle[\norm{{\mathbf{x}}_{t+1}-{\mathbf{w}}^{*}}^{2}]\leq\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}^{2}-2\eta{\mathbf{E}}_{t}[\brk[s]{{\mathbf{g}}_{t}\boldsymbol{\cdot}({\mathbf{x}}_{t}-{\mathbf{w}}^{*})}]+\eta^{2}$
$\displaystyle\leq D_{0}^{2}-\eta B(D_{0}^{2p+1})+\eta^{2}~{}~{}\bigg{(}\text{
where recall
}B:=\frac{2c_{\rho}p}{(\alpha+\beta)}\Big{(}\big{(}\nicefrac{{\alpha^{2}}}{{4\beta}}\big{)}^{p}\frac{\tilde{c}^{2p-1}}{d^{\frac{2p+1}{2}}}\Big{)}\bigg{)}$
$\displaystyle=D_{0}^{2}-B^{2}{D_{0}^{2}}^{(2p+1)},~{}~{}\bigg{(}\text{ by
setting
}\eta=BD_{0}^{2p+1}=\frac{2c_{\rho}p}{(\alpha+\beta)}\Big{(}\big{(}\nicefrac{{\alpha^{2}}}{{4\beta}}\big{)}^{p}\frac{\tilde{c}^{2p-1}}{d^{\frac{2p+1}{2}}}\Big{)}D_{0}^{2p+1}\bigg{)}.$
(24)

Now let us fix some time-stamp $T$ and let us assume
$\norm{{\mathbf{x}}_{t}-{\mathbf{w}}^{*}}\geq D_{0}/2$ for all $t=[T]$. Then
taking expectation over ${\mathcal{H}}_{T+1}$ on both sides iteratively and
summing over $t=1,\ldots,T$, note that we get:

$\displaystyle{\mathbf{E}}_{{\mathcal{H}}_{T+1}}[\norm{{\mathbf{x}}_{T+1}-{\mathbf{w}}^{*}}^{2}]$
$\displaystyle\leq D_{0}^{2}-B^{2}{D_{0}^{2}}^{(2p+1)}T.$

Then if we set $T=\frac{1}{2B^{2}{D_{0}^{2}}^{2p}}$, at time $T+1$ we have:

${\mathbf{E}}_{{\mathcal{H}}_{T+1}}[\norm{{\mathbf{x}}_{T+1}-{\mathbf{w}}^{*}}^{2}]\leq
D_{0}^{2}/2<3D_{0}^{2}/4.$

Case analysis 2: ($\exists$ at least an $\tau\in[T]$ such that
$\norm{{\mathbf{x}}_{\tau}-{\mathbf{w}}^{*}}\leq D_{0}/2$). In this case, from
Equation 19, after $(T-\tau)$ steps we can have the expected value of
$\norm{{\mathbf{x}}_{T+1}-{\mathbf{w}}^{*}}^{2}$ can be at most:

${\mathbf{E}}_{{\mathcal{H}}_{T+1}}[\norm{{\mathbf{x}}_{T+1}-{\mathbf{w}}^{*}}^{2}]\leq\norm{{\mathbf{x}}_{\tau}-{\mathbf{w}}^{*}}^{2}+(T-\tau)\eta^{2}\leq
D_{0}^{2}/4+T\eta^{2}=3D_{0}^{2}/4,$

since recall that we set
$\eta=BD_{0}^{2p+1}=\frac{2c_{\rho}p}{(\alpha+\beta)}\Big{(}\big{(}\nicefrac{{\alpha^{2}}}{{4\beta}}\big{)}^{p}\frac{\tilde{c}^{2p-1}}{d^{\frac{2p+1}{2}}}\Big{)}D_{0}^{2p+1}$.

This implies that for the above choice of $\gamma$ and $\eta$ we can get
constant fraction reduction in the “sub-optimality gap”
$(\norm{{\mathbf{w}}_{k}-{\mathbf{w}}^{*}})$ after at most
$O(\frac{1}{2B^{2}{D_{0}^{2}}^{2p}})$ time steps. ∎

###  D.2 Proof of 6

See 6

###### Complete Proof of 6.

The proof of 6 is based on the key claim of 7 which shows that after every
epoch of length $t_{k}$, the distance of the resulting point
${\mathbf{w}}_{k+1}$ from the optimal ${\mathbf{w}}^{*}$ must decrease by at
least a constant fraction. Recall from the statement of 7, we have:

See 7

The claim of 6 now follows form the following epoch-wise recursion argument:

Let
${\mathcal{H}}_{[k]}:=\\{({\mathbf{w}}_{k^{\prime}})_{k^{\prime}\in[k_{\epsilon}]},({\mathbf{u}}_{t^{\prime}},o_{t^{\prime}})_{t^{\prime}\in[\sum_{k^{\prime}=1}^{k}t_{k^{\prime}}]}\\}\cup\\{{\mathbf{w}}_{k+1}\\}$
denotes the complete history till the end of epoch $k$ starting from the first
epoch $\forall k\in[k_{\epsilon}]$.

Further, let us denote by
${\mathcal{H}}_{k}:=\\{{\mathbf{w}}_{k},({\mathbf{u}}_{t^{\prime}},o_{t^{\prime}})_{t^{\prime}\in[\sum_{k^{\prime}=1}^{k-1}t_{k^{\prime}}+1,\sum_{k^{\prime}=1}^{k}t_{k^{\prime}}]}\\}\cup\\{{\mathbf{w}}_{k+1}\\}$
be the history only within epoch $k$.

Proof of Correctness.  From 7, note we have already established that
$E_{{\mathcal{H}}_{k}}[\norm{{\mathbf{w}}_{k+1}-{\mathbf{w}}^{*}}^{2}\mid{\mathbf{w}}_{k}]\leq{\frac{3}{4}}\norm{{\mathbf{w}}_{k}-{\mathbf{w}}^{*}}^{2}$.

Applying the argument iteratively over $E$ epochs, and the law of iterated
expectations, we have:

$\displaystyle{\mathbf{E}}_{{\mathcal{H}}_{[E]}}[\norm{{\mathbf{w}}_{E+1}-{\mathbf{w}}^{*}}^{2}]\leq(\nicefrac{{3}}{{4}})^{E}\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}.$
(25)

Thus choosing $E=\lceil\log_{4/3}(\frac{\beta D^{2}}{2\epsilon})\rceil$, where
$\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}\leq D$, we have

$\displaystyle
E\geq\log_{4/3}(\frac{\beta\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}}{2\epsilon})~{}\implies~{}(\nicefrac{{3}}{{4}})^{E}\norm{{\mathbf{w}}_{1}-{\mathbf{w}}^{*}}^{2}\leq\frac{2\epsilon}{\beta}.$

Thus from (25), we get:

${\mathbf{E}}_{{\mathcal{H}}_{[E]}}[\norm{{\mathbf{w}}_{E+1}-{\mathbf{w}}^{*}}^{2}]\leq\frac{2\epsilon}{\beta},$

and further applying $\beta$-smoothness of $f$, we get:

$\displaystyle{\mathbf{E}}_{{\mathcal{H}}_{[E]}}[f({\mathbf{w}}_{E+1})-f({\mathbf{w}}^{*})]\leq{\mathbf{E}}_{{\mathcal{H}}_{[E]}}[\frac{\beta}{2}\norm{{\mathbf{w}}_{E+1}-{\mathbf{w}}^{*}}^{2}]\leq\epsilon,$

which proves the correctness of Algorithm 2 for the choice of total number of
epochs $k_{\epsilon}=E$.

Proof of Sample Complexity.  In order to verify that Algorithm 2 indeed
converges to an $\epsilon$-optimal point in $O(\epsilon^{-2p})$ sample
complexity, note we simply need to count the total sample complexity incurred
in the $k_{\epsilon}$ epochwise runs of Relative-Gradient-Descent (see Line #5
of Algorithm 2). However, by design of Epoch-RGD (Algorithm 2), since
Relative-Gradient-
Descent$\big{(}{\mathbf{w}}_{k},\eta_{k},\gamma_{k},t_{k}\big{)}$ is run for
only $t_{k}=\frac{1}{2B^{2}{(D_{k}^{2})}^{2p}}$ iterations, the total sample
complexity of Epoch-RGD becomes:

$\displaystyle\sum_{k=1}^{k_{\epsilon}}t_{k}$
$\displaystyle=\frac{1}{2B^{2}}\sum_{k=1}^{k_{\epsilon}}\frac{1}{{(D_{k}^{2})}^{2p}}=\frac{1}{2B^{2}}\bigg{(}\frac{1}{{(D_{1}^{2})}^{2p}}+\frac{1}{{(D_{2}^{2})}^{2p}}+\cdots+\frac{1}{{(D_{k_{\epsilon}}^{2})}^{2p}}\bigg{)}$
$\displaystyle=\frac{1}{2B^{2}}\bigg{(}\frac{1}{{(D^{2})}^{2p}}+\frac{1}{{(\nicefrac{{3}}{{4}}D^{2})}^{2p}}+\frac{1}{{((\nicefrac{{3}}{{4}})^{2}D^{2})}^{2p}}+\cdots+\frac{1}{{((\nicefrac{{3}}{{4}})^{k_{\epsilon}-1}D_{k_{\epsilon}}^{2})}^{2p}}\bigg{)}$
$\displaystyle=\frac{1}{2B^{2}(D^{2})^{2p}}\bigg{(}1+\frac{1}{(\nicefrac{{3}}{{4}})^{2p}}+\frac{1}{{((\nicefrac{{3}}{{4}})^{2}}^{2p}}+\cdots+\frac{1}{{((\nicefrac{{3}}{{4}})^{k_{\epsilon}-1})}^{2p}}\bigg{)}$
$\displaystyle=\frac{1}{2B^{2}(D^{2})^{2p}}\bigg{(}1+\frac{1}{(\nicefrac{{3}}{{4}})^{2p}}+\frac{1}{((\nicefrac{{3}}{{4}})^{2p})^{2}}+\cdots+\frac{1}{((\nicefrac{{3}}{{4}})^{2p})^{k_{\epsilon}-1}}\bigg{)}$
$\displaystyle=\frac{1}{2B^{2}(D^{2})^{2p}}\frac{(\nicefrac{{4}}{{3}}^{2p})^{k_{\epsilon}}-1}{\nicefrac{{4}}{{3}}^{2p}-1}\leq\frac{1}{4B^{2}(D^{2})^{2p}}\Big{(}(\nicefrac{{\beta
D^{2}}}{{2\epsilon}})^{2p}-1\Big{)}=O\Big{(}\frac{1}{B^{2}\epsilon^{2p}}\Big{)}$

where the last inequality is since $k_{\epsilon}=\lceil\log_{4/3}(\frac{\beta
D^{2}}{2\epsilon})\rceil$ by definition. Thus follows the claimed sample
complexity of Epoch-RGD in 6 and this concludes the proof. ∎

##  Appendix E Standard Results from Convex Optimization

The results covered in this section can be found in Hazan (2019); Luenberger
et al. (1984); Boyd et al. (2004); Fletcher (2013); Nesterov (2003); Nocedal
and Wright (1999).

######  Definition 12 (Lipschitz Function).

Assume ${\mathcal{D}}\subseteq{\mathbb{R}}^{d}$ be bounded decision space.
Then any function $f:{\mathcal{D}}\mapsto{\mathbb{R}}$ f is called
$L$-Lipschitz over ${\mathcal{D}}$ with respect to a norm $\norm{\cdot}$ if
for all ${\mathbf{x}},{\mathbf{y}}\in{\mathcal{D}}$, we have:

$\abs{f({\mathbf{x}})-f({\mathbf{y}})}\leq L\norm{{\mathbf{x}}-{\mathbf{y}}}.$

###  E.1 Useful properties for Convex Functions

######  Definition 13 (Convex Function).

Assume ${\mathcal{D}}\subseteq{\mathbb{R}}^{d}$ be any convex and bounded
decision space. Then any differential function
$f:{\mathcal{D}}\mapsto{\mathbb{R}}$ is called convex if for all
${\mathbf{x}},{\mathbf{y}}\in{\mathcal{D}}$,

$f({\mathbf{x}})-f({\mathbf{y}})\geq\nabla
f({\mathbf{y}})^{\top}({\mathbf{x}}-{\mathbf{y}}).$

######  Lemma 14 (First Order Optimality Condition (Luenberger et al., 1984;
Boyd et al., 2004)).

Assume $f:{\mathcal{D}}\mapsto{\mathbb{R}}$ is a convex function and
${\mathbf{x}}^{*}$ be the minimizer of $f$. Then for any
${\mathbf{x}}\in{\mathcal{D}}$,

$\nabla f({\mathbf{x}}^{*})^{\top}({\mathbf{y}}-{\mathbf{x}}^{*})\geq 0$

###  E.2 Useful properties for $\beta$-Smooth Convex Functions

######  Definition 15 ($\beta$-Smooth Convex Function).

Assume ${\mathcal{D}}\subseteq{\mathbb{R}}^{d}$ be any convex and bounded
decision space. Then any differential and convex function
$f:{\mathcal{D}}\mapsto{\mathbb{R}}$ is also called $\beta$-smooth (any
$\beta>0$) if for all ${\mathbf{x}},{\mathbf{y}}\in{\mathcal{D}}$,

$f({\mathbf{x}})-f({\mathbf{y}})\leq\nabla
f({\mathbf{y}})^{\top}({\mathbf{x}}-{\mathbf{y}})+\frac{\beta}{2}\norm{{\mathbf{x}}-{\mathbf{y}}}^{2}.$

######  Lemma 16 (Properties of $\beta$-smooth functions (Hazan, 2019; Bubeck,
2014)).

Suppose $f:{\mathcal{D}}\mapsto{\mathbb{R}}$ is a $\beta$-smooth convex
function. Then for all ${\mathbf{x}},{\mathbf{y}}\in{\mathbb{R}}^{d}$,

$\displaystyle f({\mathbf{x}})-f({\mathbf{y}})\leq\nabla
f({\mathbf{x}})^{\top}({\mathbf{x}}-{\mathbf{y}})$
$\displaystyle-\frac{1}{2\beta}\norm{\nabla f({\mathbf{x}})-\nabla
f({\mathbf{y}})}^{2}$ $\displaystyle\norm{\nabla f({\mathbf{x}})-\nabla
f({\mathbf{y}})}$ $\displaystyle\leq\beta\norm{{\mathbf{x}}-{\mathbf{y}}}.$

Further if ${\mathbf{x}}^{*}$ is the minimizer of $f$ and
${\mathbf{x}}^{*}\in\text{Int}({\mathcal{D}})$ (i.e. ${\mathbf{x}}^{*}$ belong
to the interior of $f$’s domain ${\mathcal{D}}$), then

$\displaystyle\norm{\nabla f({\mathbf{x}})}^{2}\leq
2\beta(f({\mathbf{x}})-f({\mathbf{x}}^{*})$ $\displaystyle
f({\mathbf{x}})-f({\mathbf{x}}^{*})\leq\frac{\beta}{2}\norm{{\mathbf{x}}-{\mathbf{x}}^{*}}^{2}.$

###  E.3 Useful properties for $\alpha$-Strongly Convex Functions

######  Definition 17 ($\alpha$-Strongly Convex Function).

Assume ${\mathcal{D}}\subseteq{\mathbb{R}}^{d}$ be any convex and bounded
decision space. Then any differential and convex function
$f:{\mathcal{D}}\mapsto{\mathbb{R}}$ is also called $\alpha$-strongly convex
(any $\alpha>0$) if for all ${\mathbf{x}},{\mathbf{y}}\in{\mathcal{D}}$,

$f({\mathbf{x}})-f({\mathbf{y}})\geq\nabla
f({\mathbf{y}})^{\top}({\mathbf{x}}-{\mathbf{y}})+\frac{\alpha}{2}\norm{{\mathbf{x}}-{\mathbf{y}}}^{2}.$

######  Lemma 18.

If $f:{\mathcal{D}}\mapsto{\mathbb{R}}$ is an $\alpha$-strongly convex
function, with ${\mathbf{x}}^{*}$ being the minimizer of $f$. Then for any
${\mathbf{x}},{\mathbf{y}},{\mathbf{z}}\in{\mathcal{D}}$,

$\displaystyle\norm{\nabla f({\mathbf{x}})-\nabla
f({\mathbf{y}})}\geq\alpha\|{\mathbf{x}}-{\mathbf{y}}\|$
$\displaystyle\norm{\nabla
f({\mathbf{z}})}\geq\alpha\|{\mathbf{z}}-{\mathbf{x}}^{*}\|$
$\displaystyle\frac{\alpha}{2}\|{\mathbf{x}}^{*}-{\mathbf{x}}\|^{2}\leq
f({\mathbf{x}})-f({\mathbf{x}}^{*}).$

###### Proof.

This simply follows by the properties of $\alpha$-strongly convex function.
Note by definition of $\alpha$-strong convexity, for any
${\mathbf{x}},{\mathbf{y}}\in{\mathbb{R}}$,

$f({\mathbf{x}})-f({\mathbf{y}})\geq\nabla
f({\mathbf{y}})^{\top}({\mathbf{x}}-{\mathbf{y}})+\frac{\alpha}{2}\|{\mathbf{x}}-{\mathbf{y}}\|^{2}.$

Similarly,

$f({\mathbf{y}})-f({\mathbf{x}})\geq\nabla
f({\mathbf{x}})^{\top}({\mathbf{y}}-{\mathbf{x}})+\frac{\alpha}{2}\|{\mathbf{x}}-{\mathbf{y}}\|^{2}.$

Adding we get:

$\displaystyle(\nabla f({\mathbf{y}})-\nabla
f({\mathbf{x}}))^{\top}({\mathbf{y}}-{\mathbf{x}})\geq{\alpha}\|{\mathbf{x}}-{\mathbf{y}}\|^{2}$

Now applying Cauchy-Schwarz inequality to the left hand side of the above
inequality yields the first result.

To get the second result, let us use ${\mathbf{y}}={\mathbf{z}}$ and
${\mathbf{x}}={\mathbf{x}}^{*}$ in the above inequality, which along with the
first order optimality yields (14):

$\nabla
f({\mathbf{z}})^{\top}({\mathbf{z}}-{\mathbf{x}}^{*})\geq{\alpha}\|{\mathbf{z}}-{\mathbf{x}}^{*}\|^{2}$

The result now follows by again applying Cauchy-Schwarz inequality to the left
hand side of the above inequality. Finally the last part of the proof simply
follows setting ${\mathbf{y}}={\mathbf{x}}^{*}$ and from the first order
optimality condition (see 14). ∎

###  E.4 Useful properties for $\alpha$-Strongly Convex and $\beta$-Smooth
Convex Functions $(\beta\geq\alpha)$

######  Lemma 19 (Properties of $\beta$-smooth and $\alpha$-strongly convex
functions (Bubeck, 2014)).

Suppose $f:{\mathcal{D}}\mapsto{\mathbb{R}}$ is a $\beta$-smooth and
$\alpha$-strongly convex function. Then for all
${\mathbf{x}},{\mathbf{y}}\in{\mathcal{D}}$

$\displaystyle\big{(}\nabla f({\mathbf{x}})-\nabla
f({\mathbf{y}})\big{)}^{\top}({\mathbf{x}}-{\mathbf{y}})\geq\frac{\alpha\beta}{\alpha+\beta}\norm{{\mathbf{x}}-{\mathbf{y}}}^{2}+\frac{1}{\alpha+\beta}\norm{\nabla
f({\mathbf{x}})-\nabla f({\mathbf{y}})}^{2}$