Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi Arm Bandit Problem with Heavy-tailed Symmetric Noise

## Abstract

Abstract In this paper, we consider non-smooth convex optimization with a zeroth-order oracle corrupted by symmetric stochastic noise. Unlike the existing high-probability results requiring the noise to have bounded κ 𝜅 \kappa italic_κ -th moment with κ ∈ ( 1 , 2 ] 𝜅 1 2 \kappa\in(1,2] italic_κ ∈ ( 1 , 2 ] , our results allow even heavier noise with any κ > 0 𝜅 0 \kappa>0 italic_κ > 0 , e.g., the noise distribution can have unbounded expectation. Our convergence rates match the best-known ones for the case of the bounded variance. To achieve this, we build the median gradient estimate with bounded second moment as the mini-batched median of the sampled gradient differences. We apply this technique to the stochastic multi-armed bandit problem with heavy-tailed distribution of rewards and achieve O ~ ⁢ ( d ⁢ T ) ~ 𝑂 𝑑 𝑇 \tilde{O}(\sqrt{dT}) over~ start_ARG italic_O end_ARG ( square-root start_ARG italic_d italic_T end_ARG ) regret. We demonstrate the performance of our zeroth-order and MAB algorithms for different κ 𝜅 \kappa italic_κ on synthetic and real-world data. Our methods do not lose to SOTA approaches, moreover, they dramatically outperform SOTA for κ ≤ 1 𝜅 1 \kappa\leq 1 italic_κ ≤ 1 .

## 1 Introduction

During the recent few years, stochastic optimization problems with heavy-tailed noise received a lot of attention from many researchers. In particular, heavy-tailed noise is observed in various problems, such as the training of large language models (Brown et al., ; Zhang et al., ), generative adversarial networks (Goodfellow et al., ; Gorbunov et al., ), finance (Rachev, ), and blockchain (Wang et al., ). One of the most popular techniques for handling heavy-tailed noise in theory and practice is the gradient clipping (Gorbunov et al., ; Cutkosky and Mehta, ; Nguyen et al., ; Puchkin et al., ) which allows deriving high-probability bounds and considerably improves convergence even in case of light tails Sadiev et al. ().

However, most of the mentioned works focus on the gradient-based (first-order) methods. For some problems, e.g., the multi-armed bandit (Flaxman et al., ; Bartlett et al., ; Bubeck and Cesa-Bianchi, ), only losses or function values are available, and thus, zeroth-order algorithms are required. Stochastic zeroth-order optimization is being actively studied. For a detailed overview, see the recent survey Gasnikov et al. () and the references
therein. The only existing works that handle heavy-tailed noise in zeroth-order optimization are (Kornilov et al., ; ). Under noise with bounded $\kappa$-th moment for $\kappa\in(1,2]$, the authors obtain optimal high-probability convergence for $d$-dimensional non-smooth convex problems, i.e., function accuracy $\varepsilon$ is achieved in $\sim(\sqrt{d}\varepsilon^{-1})^{\frac{\kappa}{\kappa-1}}\text{oracle calls}.$ These rates match the optimal rates for first-order optimization Gorbunov et al. (), however, they degenerate as $\kappa\to 1$, and the convergence is not guaranteed for $\kappa=1$.

For symmetric (and close to symmetric) heavy-tailed noise distributions, the degeneration issue can be handled via median estimators Zhong et al. (); Puchkin et al. (), which are frequently used in robust mean estimation and robust machine learning Lugosi and Mendelson (). In the case of first-order methods, the authors of Puchkin et al. () achieve better complexity guarantees and show that the narrowing of the distributions’ class is essential for it. However, the possibility of application of the median estimators to the case of the zeroth-order optimization and multi-armed bandit remains open. In this paper, we address this question.

### 1.1 Motivation

The previous results on zeroth-order stochastic optimization were based on the assumption of the existence of the finite expectation of the noise $\phi$ ($\kappa\in(1,2]$). The assumption of the symmetric noise allows us to consider a wider range of problems (e.g., without finite expectation) and achieve a convergence rate as if the noise had a bounded second moment.

As the main application example, we consider the stochastic multi-armed bandit problem with symmetric heavy-tailed distribution of losses introduced in Bubeck et al. (). The standard assumption is the same as in zeroth-order stochastic optimization: bounded $\kappa$-moment of losses ($\kappa\in(1,2]$). The assumption of the symmetric noise allows us to consider a wider range of problems and get better regret rates compared to current SOTA algorithms.

### 1.2 Contributions

Theory I. We propose our novel ZO-clipped-med-SSTM ($\S$3.2) for unconstrained optimization and ZO-clipped-med-SMD ($\S$3.3) for optimization on convex compact. For any symmetric heavy-tailed noise, our methods achieve with high-probability optimal convergence rates of the case of bounded variance. In the Table 1, we provide convergence guarantees for the unconstrained optimization.

**Table 1: Number of successive iterations to achieve a function’s accuracy $\varepsilon$ with high probability; unconstrained optimization via Lipschitz oracle with bounded $\kappa$-th moment. Constants $b,d,M^{\prime}_{2}$ denote the batch size, dimensionality and the Lipschitz constant of the oracle, respectively.**
|  | ZO-clipped-SSTM Kornilov et al. () | ZO-clipped-med-SSTM (this work) |
| --- | --- | --- |
| $\kappa>1$, $b$ oracle calls per iter. | $\kappa>0$, symmetric noise, $\frac{b}{\kappa}$ calls |  |
| Convex | $\widetilde{\cal O}\left(\max\left\{\frac{d^{\frac{1}{4}}M^{\prime}_{2}}{<br>\varepsilon},\frac{1}{b}\left(\frac{\sqrt{d}M^{\prime}_{2}}{\varepsilon}\right<br>)^{\frac{\kappa}{\kappa-1}}\right\}\right)$ | $\widetilde{{\cal O}}\left(\max\left\{\frac{d^{\frac{1}{4}}M^{\prime}_{2}}{<br>\varepsilon},\frac{1}{b}\left(\frac{\sqrt{d}M^{\prime}_{2}}{\varepsilon}\right<br>)^{2}\right\}\right)$ |
| $\mu$-str. conv. | $\widetilde{\cal O}\left(\max\left\{\frac{d^{\frac{1}{4}}M^{\prime}_{2}}{<br>\varepsilon},\frac{1}{b}\left(\frac{d(M^{\prime}_{2})^{2}}{\mu\varepsilon}<br>\right)^{\frac{\kappa}{2(\kappa-1)}}\right\}\right)$ | $\widetilde{\cal O}\left(\max\left\{\frac{d^{\frac{1}{4}}M^{\prime}_{2}}{<br>\varepsilon},\frac{1}{b}\frac{d(M^{\prime}_{2})^{2}}{\mu\varepsilon}\right\}\right)$ |

Theory II. We propose Clipped-INF-med-SMD ($\S$4) for the stochastic multi-armed bandit (MAB) with symmetric heavy-tailed reward distribution. In Theorem 3, we obtain $\tilde{O}(\sqrt{Td})$ bound on regret which is suboptimal compared to the lower bound for stochastic MAB with bounded variance. Moreover, this bound holds not only in expectation, but with controlled large deviations.

Practice. We demonstrate in the series of experiments on extremely noised real and synthetic data superior performance of our methods in comparison with previously known SOTA approaches.

## 2 Preliminaries

In this section, we introduce general notations and assumptions on optimized functions. We also recall popular gradient smoothing and clipping techniques.

Notations. For vector $x\in\mathbb{R}^{d}$ and $p\in[1,2]$, we define $p$-norm as $\|x\|_{p}\stackrel{{\scriptstyle\text{def}}}{{=}}\left(\sum\limits_{i=1}^{d}|x
_{i}|^{p}\right)^{\frac{1}{p}}$ and its dual norm as $\|x\|_{q}$, where $\frac{1}{p}+\frac{1}{q}=1$. In the case $q=\infty$, we define $\|x\|_{\infty}=\max\limits_{i=1,\dots,d}|x_{i}|$. We denote the Euclidean unit ball $B^{d}_{2}\stackrel{{\scriptstyle\text{def}}}{{=}}\{x\in\mathbb{R}^{d}:\|x\|_{2
}\leq 1\}$, the Euclidean unit sphere $S^{d}_{2}\stackrel{{\scriptstyle\text{def}}}{{=}}\{x\in\mathbb{R}^{d}:\|x\|_{2
}=1\}$ and the probability simplex $\Delta_{+}^{d}\stackrel{{\scriptstyle\text{def}}}{{=}}\{x\in\mathbb{R}^{d}_{+}
:\sum_{i=1}^{d}x_{i}=1\}$.

Median operator $\text{Median}(\{a_{i}\}_{i=1}^{2m+1})$ applied to the elements sequence of the odd size $2m+1,m\in\mathbb{N}$ returns $m$-th order statistics. We also use short notation for $\max$ operator, i.e. $a\lor b\stackrel{{\scriptstyle\text{def}}}{{=}}\max(a,b)$.

###### Assumption 1 (Strong convexity) .

The function $f:\mathbb{R}^{d}\to\mathbb{R}$ is $\mu$-strongly convex, if there exists $\mu\geq 0$ such that for all $x_{1},x_{2}\in\mathbb{R}^{d}$ and $\lambda\in[0,1]:$

$$ $\displaystyle f(\lambda x_{1}+(1-\lambda)x_{2})$ $\displaystyle\leq$ $\displaystyle\lambda f(x_{1})+(1-\lambda)f(x_{2})-\frac{1}{2}\mu\lambda(1- \lambda)\|x_{1}-x_{2}\|_{2}^{2},$ $$

If $\mu=0$ we say that the function is just “convex”.

###### Assumption 2 (Lipschitz continuity) .

The function $f:\mathbb{R}^{d}\to\mathbb{R}$ is $M_{2}$-Lipschitz continuous w.r.t. the Euclidean norm, if there exists $M_{2}>0$, such that for all $x_{1},x_{2}\in\mathbb{R}^{d}$:

$$ $|f(x_{1})-f(x_{2})|\leq M_{2}\|x_{1}-x_{2}\|_{2}.$ $$

If a differentiable function has $L$-Lipschitz gradient, we call it $L$-smooth.

Randomized smoothing.
The main scheme that allows us to develop gradient-free
methods for non-smooth convex problems
is randomized smoothing Ermoliev (); Gasnikov et al. (); Nemirovskij and Yudin (); Nesterov and Spokoiny (); Spall ().
For the fixed smoothing parameter $\tau>0$, we build a smooth approximation $\hat{f}_{\tau}$ for a non-smooth $f:\mathbb{R}^{d}\to\mathbb{R}$ as:

$$ $\hat{f}_{\tau}(x)\overset{\text{def}}{=}\mathbb{E}_{\mathbf{u}}[f(x+\tau \mathbf{u})],$ (1) $$

where $\mathbf{u}\sim U(B^{d}_{2})$ is a random vector uniformly distributed on the Euclidean unit ball $B^{d}_{2}$.

If the function $f$ is $\mu$-strongly convex (As 1) and $M_{2}$-Lipschitz (As 2), then the smoothed function $\hat{f}_{\tau}$ is $\mu$-strongly convex and $\nicefrac{{\sqrt{d}M_{2}}}{{\tau}}$-smooth. Moreover, it does not differ from the original $f$ too much, namely, (See Lemma 2 from Appendix B.1)

$$ $\sup\limits_{x\in\mathbb{R}^{d}}|\hat{f}_{\tau}(x)-f(x)|\leq\tau M_{2}.$ (2) $$

Clipping. To handle heavy-tailed noise, we use a clipping technique which clips tails of gradient’s distribution. For the clipping level $\lambda>0$ and $q-$norm, where $q\in[2,+\infty]$, we define the clipping operator clip as follows:

$$ $\texttt{clip}_{q}\left(g,\lambda\right)=\frac{g}{\|g\|_{q}}\min\left(\|g\|_{q} ,\lambda\right),$ $$

where $g\in\mathbb{R}^{d}$ is an arbitrary non-zero gradient vector.

###### Assumption 1 (Strong convexity) .

###### Assumption 2 (Lipschitz continuity) .

## 3 Zeroth-order optimization with symmetric heavy-tailed noise

In this section, we present our novel algorithms for zeroth-order optimization with independent and Lipschitz oracles. In subsection 3.1, we introduce the problem, symmetric heavy-tailed noise assumptions and median estimation with its properties. In subsection 3.2, we propose our accelerated batched ZO-clipped-med-SSTM for unconstrained problems. In subsection 3.3, we describe our ZO-clipped-med-SMD for problems on convex compacts. All proofs are located in Appendix B.

### 3.1 Theory

We consider a non-smooth convex optimization problem on a convex set $Q\subseteq\mathbb{R}^{d}$:

$$ $\min\limits_{x\in Q}f(x),$ (3) $$

where $f:\mathbb{R}^{d}\to\mathbb{R}$ is $d$-dimensional, $\mu$-strongly convex (As 1) and $M_{2}$-Lipschitz (As 2) function. A point $x^{*}$ denotes one of the problem’s solutions. In zeroth-order setup, the optimization is performed only by accessing the pairs of function evaluations rather than sub-gradients.

Two-point oracle. For any two points $x,y\in\mathbb{R}^{d}$, an oracle returns the pair of the scalar values $f(x,\xi)$ and $f(y,\xi)$, which are noised evaluation of real values $f(x)$ and $f(y).$ Moreover, noised values have the same realization of the stochastic variable $\xi$ and can be written as

$$ $f(x,\xi)-f(y,\xi)=f(x)-f(y)+\phi(\xi|x,y),$ $$

where $\phi(\xi|x,y)$ is the stochastic noise, whose distribution depends on points $x,y$.

#### 3.1.1 Noise distribution.

We propose our novel assumption on distribution of $\phi(\xi|x,y)$, induced by a random variable $\xi$. It allows us to introduce symmetry and heavy-tailed noise with bounded up to $\kappa$-th moments, $\kappa>0$.

###### Assumption 3 (Symmetric noise distribution) .

Symmetry. For any two points $x,y\in\mathbb{R}^{d}$, noise $\phi(\xi|x,y)$ has symmetric probability density $p(u|x,y)$, i.e. $p(u|x,y)=p(-u|x,y),\forall u\in\mathbb{R}$.

Heavy tails. We assume that there exist $\kappa>0$, $\gamma>0$ and scale function $B(x,y):\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$, such that $\forall u\in\mathbb{R}$ holds

$$ $p(u|x,y)\leq\frac{\gamma^{\kappa}\cdot|B(x,y)|^{\kappa}}{|B(x,y)|^{1+\kappa}+| u|^{1+\kappa}}.$ (4) $$

We consider two possible oracles:

Independent oracle: $\phi(\xi|x,y)$ distribution doesn’t depend on points $x,y$, i.e.,

$$ $\gamma\cdot B(x,y)\equiv\Delta.$ (5) $$

Lipschitz oracle: $\phi(\xi|x,y)$ distribution becomes more concentrated around 0 0 as $x,y$ become closer:

$$ $|\gamma\cdot B(x,y)|\leq\Delta\cdot\|x-y\|_{2},$ (6) $$

where $\Delta>0$ is the noise Lipschitz constant.

This assumption covers a majority of symmetric absolutely continuous distributions with bounded up to $\kappa$-th moments. For example, if a random variable $\xi$ has Cauchy distribution, then one can use

- •
Independent oracle: $f(x,\xi)=f(x)+\xi_{x},f(y,\xi)=f(y)+\xi_{y}$ with independent $\xi_{x},\xi_{y}$.
- •
Lipschitz oracle: $f(x,\boldsymbol{\xi})=f(x)+\langle\boldsymbol{\xi},x\rangle,f(y,\boldsymbol{
\xi})=f(y)+\langle\boldsymbol{\xi},y\rangle$, where $\boldsymbol{\xi}$ is $d$-dimensional random vector. Oracle gives the same realization of $\boldsymbol{\xi}$ for both $x$ and $y$.

For the case $\kappa\in(1,2]$, our Assumption 3 can be reduced to the standard assumptions from Dvinskikh et al. (); Kornilov et al. (), see Remark 3. However, there is slight difference: we make our Assumption 3 on variable $\phi(\xi|x,y)$ with fixed $x,y$, while in Kornilov et al. () the authors make assumption on $\xi$ itself and condition $x,y$ by it. For the very same reason, we can not generalize common proof techniques from previous works, and we obtain in our upper bounds with $M_{2}+d\Delta$ instead of $M_{2}+\Delta$.
We refer to Appendix A for more details and intuition behind Assumption 3.

###### Assumption 3 (Symmetric noise distribution) .

#### 3.1.2 Median Estimation.

In our pipeline, instead of minimizing the non-smooth function $f$ directly, we propose to minimize the smooth approximation $\hat{f}_{\tau}$ with the fixed smoothing parameter $\tau$ via first-order methods. Following (2), the solution for $\hat{f}_{\tau}$ is also a good approximate minimizer of $f$ when $\tau$ is sufficiently small.

Following Shamir (), the gradient of $\hat{f}_{\tau}$ at point $x\in\mathbb{R}^{d}$ can be estimated by the vector:

$$ $\displaystyle g(x,\mathbf{e},\xi)$ $\displaystyle=$ $\displaystyle\frac{d}{2\tau}(f(x+\tau\mathbf{e},\xi)-f(x-\tau\mathbf{e},\xi)) \mathbf{e}$ $\displaystyle=$ $\displaystyle\frac{d}{2\tau}(f(x+\tau\mathbf{e})-f(x-\tau\mathbf{e})+\phi(\xi| x+\tau\mathbf{e},x-\tau\mathbf{e}))\mathbf{e},$ $$

where $\mathbf{e}\sim U(S^{d}_{2})$ is
a random vector uniformly distributed on the Euclidean unit sphere $S^{d}_{2}$. Moreover, $\mathbf{e},\xi$ are independent of each other conditionally on $x$. However, the noise $\phi$ might have unbounded first and second moments. To fix this, we lighten tails of $\phi$ to obtain an unbiased estimate of $\nabla\hat{f}_{\tau}$. For a point $x\in\mathbb{R}^{d}$, we apply the component-wise median operator to $2m+1$ samples $\{g(x,\mathbf{e},\xi^{i})\}_{i=1}^{2m+1}$ with independent $\xi^{i}$ and the same $x$ and $\mathbf{e}$:

$$ $\texttt{Med}^{m}(x,\mathbf{e},\{\xi\})\stackrel{{\scriptstyle\text{def}}}{{=}} \texttt{Median}(\{g(x,\mathbf{e},\xi^{i})\}_{i=1}^{2m+1}).$ (8) $$

The median operator can be applied to the batch of $\{\mathbf{e}^{j}\}_{j=1}^{b}$ with batch size $b$ and further averaging:

$$ $\texttt{BatchMed}^{m}_{b}(x,\{\mathbf{e}\},\{\xi\})\stackrel{{\scriptstyle \text{def}}}{{=}}\frac{1}{b}\sum_{j=1}^{b}\texttt{Med}^{m}(x,\mathbf{e}^{j},\{ \xi\}^{j}).$ (9) $$

For a large enough number of samples, median estimations have bounded second moment.

###### Lemma 1 (Median estimation’s properties) .

Consider $\mu$-strongly convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ with oracle corrupted by noise under As. 3 with $\Delta$ and $\kappa>0$. If median size $m>\frac{2}{\kappa}$ with norm $q\in[2,+\infty]$, then $\forall x\in\mathbb{R}^{d}$ the median estimates (8) and (9) are unbiased, i.e.,

$$ $\mathbb{E}_{\mathbf{e},\xi}[\texttt{Med}^{m}(x,\mathbf{e},\{\xi\})]=\mathbb{E} _{\mathbf{e},\xi}[\texttt{BatchMed}^{m}_{b}(x,\{\mathbf{e}\},\{\xi\})]=\nabla \hat{f}_{\tau}(x),$ $$

and have bounded second moment, i.e.,

$$ $\displaystyle\mathbb{E}_{\mathbf{e},\xi}[\|\texttt{BatchMed}^{m}_{b}(x,\{ \mathbf{e}\},\{\xi\})-\nabla\hat{f}_{\tau}(x)\|_{2}^{2}]$ $\displaystyle\leq$ $\displaystyle\frac{\sigma^{2}}{b},$ (10) $$

$$ $\displaystyle\mathbb{E}_{\mathbf{e},\xi}[\|\texttt{Med}^{m}(x,\mathbf{e},\{\xi \})-\nabla\hat{f}_{\tau}(x)\|_{q}^{2}]\leq\sigma^{2}a_{q}^{2},\quad a_{q}=d^{ \frac{1}{q}-\frac{1}{2}}\min\{\sqrt{32\ln d-8},\sqrt{2q-1}\}.$ (11) $$

For independent oracle, we have $\sigma^{2}=8dM_{2}^{2}+2\left(\frac{d\Delta}{\tau}\right)^{2}(2m+1)\left(\frac
{4}{\kappa}\right)^{\frac{2}{\kappa}},$
and, for Lipschitz oracle, we have $\sigma^{2}=8dM_{2}^{2}+(16m+8)d^{2}\Delta^{2}\left(\frac{4}{\kappa}\right)^{
\frac{2}{\kappa}}.$

###### Lemma 1 (Median estimation’s properties) .

### 3.2 ZO-clipped-med-SSTM for unconstrained problems

We present our novel ZO-clipped-med-SSTM which works on the whole space $Q=\mathbb{R}^{d}$ with the Euclidean norm. We base it on the first-order accelerated clipped Stochastic Similar Triangles Method (clipped-SSTM) with the optimal high-probability complexity
bounds from Gorbunov et al. (). Namely, we use its zeroth-order version ZO-clipped-SSTM from Kornilov et al. () with the batched median estimation (9).

Figure: Algorithm 1 ZO-clipped-med-SSTM

###### Theorem 1 (Convergence of ZO-clipped-med-SSTM ) .

Consider convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ on $\mathbb{R}^{d}$ with two-point oracle corrupted by noise under As. 3 with $\Delta$ and $\kappa>0$. We set batch size $b$, median size $m=\frac{2}{\kappa}+1$ and initial distance $R=\|x_{0}-x^{*}\|$. To achieve function accuracy $\varepsilon$, i.e., $f(y^{K})-f(x^{*})\leq\varepsilon$ with probability at least $1-\beta$ via ZO-clipped-med-SSTM with parameters $A=\ln\nicefrac{{4K}}{{\beta}}\geq 1$,
$a=\Theta(\min\{A^{2},\nicefrac{{\sigma K^{2}\sqrt{A}\tau}}{{\sqrt{bd}M_{2}R}}
\}),\lambda_{k}=\Theta(\nicefrac{{R}}{{(\alpha_{k+1}A)}})$ and smoothing parameter $\tau=\frac{\varepsilon}{4M_{2}}$, the number of iterations $K$ must be

$$ $\widetilde{{\cal O}}\left(\frac{d^{\frac{1}{4}}M_{2}R}{\varepsilon}\lor\frac{( \sqrt{d}M_{2}R)^{2}}{b\cdot\varepsilon^{2}}\left(1\lor\left(\frac{4}{\kappa} \right)^{\frac{2}{\kappa}}\!\!\frac{d\Delta^{2}}{\varepsilon^{2}}\right)\right ),\widetilde{{\cal O}}\left(\max\!\left\{\frac{d^{\frac{1}{4}}M_{2}R}{ \varepsilon},\frac{d(M_{2}^{2}\!\!+\!\!d\Delta^{2}/\kappa^{\frac{2}{\kappa}})R ^{2}}{b\cdot\varepsilon^{2}}\right\}\right),$ $$

for independent and Lipschitz oracle, respectively.
Each iteration requires $(2m+1)\cdot b$ oracle calls. Moreover, with probability at least $1-\beta$ the iterates of ZO-clipped-med-SSTM remain in the ball with center $x^{*}$ and radius $2R$, i.e., $\{x^{k}\}_{k=0}^{K+1},\{y^{k}\}_{k=0}^{K},\{z^{k}\}_{k=0}^{K}\subseteq\{x\in
\mathbb{R}^{d}:\|x-x^{*}\|_{2}\leq 2R\}$.

For Lipschitz oracle, the first term in bound is optimal in $\varepsilon$ for the deterministic non-smooth problems Bubeck et al. (), and the second term is optimal in $\varepsilon$ for zeroth-order problems with the finite variance Nemirovskij and Yudin (). In case of one-point oracle, while noise $\phi$ is “small”, i.e.,

$$ $\Delta\leq\left(\frac{\kappa}{4}\right)^{\frac{1}{\kappa}}\frac{\varepsilon}{ \sqrt{d}}$ (12) $$

optimal convergence rate is preserved. This bound is optimal in terms of accuracy $\varepsilon$, see Lobanov (); Pasechnyuk et al. (); Risteski and Li (). For $\mu-$strongly-convex functions with Lipschitz oracle or independent oracle with small noise, we apply the restarted version of ZO-Clipped-med-SSTM. Algorithm’s description, more details and results are located in Appendix C.1.

###### Theorem 1 (Convergence of ZO-clipped-med-SSTM ) .

#### 3.2.1 Extended classes of the optimized functions

###### Remark 1 (Smooth objective) .

The estimates presented in Theorem 1 can be improved by introducing a new assumption, namely the assumption that the objective function $f$ is $L$-smooth with $L>0$: ${\|\nabla f(y)-\nabla f(x)\|_{2}\leq L\|y-x\|_{2}}$, $\forall x,y\in\mathbb{R}^{d}$. Using this assumption, we obtain the following value of the smoothing parameter $\tau=\sqrt{\varepsilon/L}$ (see Gasnikov et al., , the end of Section 4.1). Thus, assuming smoothness and convexity (As. 1) of the objective function and assuming symmetric noise (As. 3), we obtain the following estimates for the iteration complexity: $\widetilde{{\cal O}}\left(\max\left\{\sqrt{\frac{LR^{2}}{\varepsilon}},\frac{(
\sqrt{d}R)^{2}}{b\cdot\varepsilon^{2}}\left(M_{2}^{2}\lor\left(\frac{4}{\kappa
}\right)^{\frac{2}{\kappa}}\frac{dL\Delta^{2}}{\varepsilon}\right)\right\}\right)$ and ${\widetilde{{\cal O}}\left(\max\left\{\sqrt{\frac{LR^{2}}{\varepsilon}},\frac{
d(M_{2}^{2}+d\Delta^{2}/\kappa^{\frac{2}{\kappa}})R^{2}}{b\cdot\varepsilon^{2}
}\right\}\right)}$ for independent and Lipschitz oracle, respectively. These rates match the iteration’s complexity for the full gradient coordinate-wise estimation.

###### Remark 2 (Polyak–Lojasiewicz objective) .

The results of Theorem 1 can be extended to the case when the objective function satisfies the Polyak–Lojasiewicz condition: let a function $f(x)$ is differentiable and there exists constant $\mu>0$ s.t. $\forall x\in\mathbb{R}^{d}$ the following inequality holds ${\|\nabla f(x)}\|_{2}^{2}\geq 2\mu(f(x)-f(x^{*}))$. Then, assuming smoothness (see Remark 1) and Polyak–Lojasiewicz condition for the objective function and assuming symmetric noise (As. 3), we obtain the following estimates for the iteration complexity: $\widetilde{{\cal O}}\left(\max\left\{\frac{L}{\mu},\frac{dL}{b\mu^{2}
\varepsilon}\left(M_{2}^{2}\lor\left(\frac{4}{\kappa}\right)^{\frac{2}{\kappa}
}\frac{dL\Delta^{2}}{\varepsilon}\right)\right\}\right)$ and ${\widetilde{{\cal O}}\left(\max\left\{\frac{L}{\mu},\frac{dL(M_{2}^{2}+d\Delta
^{2}/\kappa^{\frac{2}{\kappa}})}{b\mu^{2}\varepsilon}\right\}\right)}$ for independent and Lipschitz oracle, respectively.

###### Remark 1 (Smooth objective) .

###### Remark 2 (Polyak–Lojasiewicz objective) .

### 3.3 ZO-clipped-med-SMD for constrained problems

We propose our novel ZO-clipped-med-SMD to minimize functions on a convex compact $Q\subset\mathbb{R}^{d}$. We use unbatched median estimation (8) in the zeroth-order algorithm ZO-clipped-SMD from Kornilov et al. (), which is based on Mirror Gradient Descent.

We define $1$-strongly convex w.r.t. $p$—norm and differentiable prox-function $\Psi_{p}$. We denote its convex (Fenchel) conjugate and its Bregman divergence, respectively, as

$$ $\Psi_{p}^{*}(y)=\sup\limits_{x\in\mathbb{R}^{d}}\{\langle x,y\rangle-\Psi_{p}( x)\},\quad V_{\Psi_{p}}(y,x)=\Psi_{p}(y)-\Psi_{p}(x)-\langle\nabla\Psi_{p}(x), y-x\rangle.$ $$

Figure: Algorithm 2 ZO-clipped-med-SMD

###### Theorem 2 .

Consider convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ with two-point oracle corrupted by noise under As. 3 with $\kappa>0$. To achieve function accuracy $\varepsilon$, i.e., $f(\overline{x}_{K})-f(x^{*})\leq\varepsilon$ with probability at least $1-\beta$ via ZO-clipped-med-SMD with median size $m=\frac{2}{\kappa}+1$, clipping level $\lambda=\sigma a_{q}\sqrt{K}$, stepsize $\nu=\frac{D_{\Psi_{p}}}{\lambda}$, diameter $D_{\Psi_{p}}^{2}\stackrel{{\scriptstyle\text{def}}}{{=}}2\sup\limits_{x,y\in Q
}V_{\Psi_{p}}(x,y)$, prox-function $\Psi_{p}$ and $\tau=\frac{\varepsilon}{4M_{2}}$, the number of iterations $K$ must be

$$ $\widetilde{{\cal O}}\left(\frac{(\sqrt{d}M_{2}a_{q}D_{\Psi_{p}})^{2}}{ \varepsilon^{2}}\left(1\lor\left(\frac{4}{\kappa}\right)^{\frac{2}{\kappa}} \frac{d\Delta^{2}}{\varepsilon^{2}}\right)\right),\quad\widetilde{{\cal O}} \left(\frac{d(M^{2}_{2}+d\Delta^{2}/\kappa^{\frac{2}{\kappa}})a^{2}_{q}D^{2}_{ \Psi_{p}}}{\varepsilon^{2}}\right)$ (13) $$

for independent and Lipschitz oracle, respectively. Each iteration requires $(2m+1)$ oracle calls.

Bounds (13) are optimal in terms of $\varepsilon$ for stochastic non-smooth optimization on convex compact with the finite variance Vural et al. (). The upper bound for $\Delta$ under which optimal convergence rate is preserved is the same as for unconstrained optimization (12).

For $\mu$-strongly-convex functions with Lipschitz oracle or independent oracle with small noise, we apply the restarted version of ZO-Clipped-SMD. Algorithm and results are located in Appendix C.2.

###### Theorem 2 .

## 4 Application to the multi-armed bandit problem with heavy tails

In this section, we present our novel Clipped-INF-med-SMD algorithm for multi-armed bandit problem with heavy-tailed rewards. In online optimization with horizon $T$, on $t$-th step, we propose point $x_{t}\in\mathbb{R}^{d}$ and then suffer the stochastic loss $l_{t}(x_{t})$. Our goal is to minimize regret of our strategy compared to a fixed competitor strategy $u$ defined as

$$ $\mathbb{E}[\mathcal{R}_{T}(u)]=\mathbb{E}\left[\sum_{t=1}^{T}l_{t}(x_{t})-\sum _{t=1}^{T}l_{t}(u)\right].$ $$

##### Stochastic multi-armed bandit problem (MAB)

Consider stochastic linear loss functions $l_{t}(x_{t})=\langle\mu+\xi_{t},x_{t}\rangle$, with noise $\xi_{t}$ and unknown fixed vector of expected losses $\mu\in\mathbb{R}^{d}$. The heavy noise assumption usually requires existence of $\kappa\in(1,2]$, such that $\mathbb{E}[\|\mu+\xi_{t}\|^{\kappa}]\leq\sigma^{\kappa}$. The decision variable $x_{t}\in\triangle^{d}_{+}$ can be viewed as the player’s mixed strategy (probability distribution over arms), that they use to sample arms with the aim to minimize expected regret. The player observes only sampled losses for the chosen arm, i.e., the (sub)gradient $g(x)\in\partial l(x)$ is not observed in the MAB setting, and one must use inexact oracle instead.

Bandits with heavy tails were first introduced in Bubeck et al. () along with lower bounds on regret $\Omega\left(MT^{\frac{1}{\kappa}}d^{\frac{\kappa-1}{\kappa}}\right)$ and nearly optimal algorithmic scheme Robust UCB. Recently few optimal algorithms were proposed Lee et al. (); Zimmert and Seldin (); Huang et al. (); Dorn et al. () with online mirror descent (OMD) as the main ingredient. Currently, these types of algorithms are referred to as best-of-two-worlds algorithms.

In this section, we assume that the probability density of the noise $\xi$ satisfies Assumption 3 for some $\kappa>0$. We construct our Clipped-INF-med-SMD (Algorithm 3) based on Online Mirror Descent, but in case of symmetric noise we can improve regret upper bounds and make it $\tilde{O}(\sqrt{Td})$ which is suboptimal compared to the lower bound for stochastic MAB with the bounded variance of losses.

In our algorithm, we use an importance-weighted estimator:

$$ $\hat{g}_{t,i}=\begin{cases}\frac{g_{t,i}}{x_{t,i}}&\text{if }i=A_{t}\\ 0&\text{otherwise}\end{cases},$ $$

where $A_{t}$ is the index of the chosen (at round $t$) arm. This estimator is unbiased, i.e. $\mathbb{E}_{x_{t}}[\hat{g}_{t}]=g_{t}$. The main drawback of this estimator is that, in the case of small $x_{t,i}$, the value of $\hat{g}_{t,i}$ can be arbitrarily large. When the noise $g_{t}-\mu$ has heavy tails (i.e., $\|g_{t}-\mu\|_{\infty}$ can be large with high probability), this drawback can be amplified. That is why we use robust median estimation with further clipping.

Figure: Algorithm 3 Clipped-INF-med-SMD

###### Theorem 3 .

Consider MAB problem where the conditional probability density function for each loss satisfies Assumption 3 with $\Delta,\kappa>0,$ and $\|\mu\|_{\infty}\leq R$. Then, for the period $T$, the sequence $\{x_{t}\}_{t=1}^{T}$ generated by Clipped-INF-med-SMD with parameters $m=\frac{2}{\kappa}+1$, $\tau=\sqrt{d}$, $\nu=\frac{\sqrt{(2m+1)}}{\sqrt{T(36c^{2}+2R^{2})}}$, $\lambda=\sqrt{T}$ and prox-function $\Psi_{1}(x)=\psi(x)\stackrel{{\scriptstyle\text{def}}}{{=}}2\left(1-\sum_{i=1}
^{d}x_{i}^{1/2}\right)$ satisfies

$$ $\mathbb{E}\left[\mathcal{R}_{T}(u)\right]\leq\sqrt{Td}\cdot(8c^{2}/\sqrt{d}+4 \sqrt{(2m+1)(18c^{2}+R^{2})}),\quad u\in\Delta_{+}^{d},$ (14) $$

where $c^{2}=\left(32\ln d-8\right)\cdot\left(8M_{2}^{2}+2\Delta^{2}(2m+1)\left(\frac
{4}{\kappa}\right)^{\frac{2}{\kappa}}\right)$. Moreover, high probability bounds from Theorem 2 also hold. Proof of Theorem 3 is located in Appendix B.3.

###### Theorem 3 .

## 5 Numerical Experiments

In this section, we demonstrate the superior performance of ours ZO-clipped-med-SSTM and Clipped-INF-med-SMD under heavy-tailed noise on experiments on syntactical and real-world data. Additional experiments and technical details are located in Appendix D.

### 5.1 Multi-Armed Bandit

We compare our Clipped-INF-med-SMD with popular SOTA algorithms tailored to handle MAB problem with heavy tails, namely, HTINF Huang et al. () and APE Lee et al. (). HTINF is INF-type (Online Mirror Descent with gradient estimator for bandit feedback) algorithm with specific pruning procedure. APE is a perturbation-based exploration strategy that use p-robust mean estimator. We focus on an experiment involving only two available arms ($d=2$). Each arm $i$ generates random losses $g_{t,i}\sim\xi_{t}+\beta_{i}$. Parameters $\beta_{0}=3,\beta_{1}=3.5$ are fixed, and independent random variables $\xi_{t}$ have the same probability density $\text{p}_{\xi_{t}}\left(x\right)=\frac{1}{3\cdot\left(1+\left(\frac{x}{3}
\right)^{2}\right)\cdot\pi}$.

For all methods, we evaluate the distribution of expected regret and probability of picking the best arm over $100$ runs. The results are presented in Figure 1.

Figure: Figure 1: Average expected regret and probability of optimal arm picking mean for $100$ experiments and $30000$ samples with $0.95$ and $0.05$ percentiles for regret and ± std bounds for probabilities
Refer to caption: x1.png

As one can see from the graphs, HTINF and APE do not have convergence in probability, while our Clipped-INF-med-SMD does, which confirms the efficiency of the proposed method. In Appendix D.1, we provide technical details and additional experiments for different $\kappa$.

### 5.2 Cryptocurrency portfolio optimization

We choose cryptocurrency portfolio optimization problem for Clipped-INF-med-SMD real world application, since cryptocurrency pricing data is known by having heavy-tailed distribution. In our scenario, we have $n=9$ assets for investing. At step $t$, we choose assets’ distribution $x_{t,i}\in\Delta^{n}$ and then observe the whole income vector $r_{t,i}$ for each asset $i$. The main goal is to maximize total income $\max\mathbb{E}\sum_{t=1}^{T}\sum_{i=1}^{n}r_{t,i}x_{t,i}$ over a fixed time interval with length $T$.

Portfolio selection has the full feedback for all assets, while, in standard bandits, we observe only one asset per step. We adjust our Clipped-INF-med-SMD for the full feedback via calculating line 4 in Algorithm 3 for each asset $i$. As baselines, we use two strategies: hold ETH and the Efficient Frontier method (Markovitz", ) with maximal sharp ratio portfolio selected. For a dataset, we use open prices from Binance Spot for 2023.

The results are presented in Figure 2. As one can see, the Efficient Frontier strategy can’t efficiently perform on cryptocurrency assets, and Clipped-INF-med-SMD achieved higher performance than just holding the ETH strategy, so it can be applied for detecting potentially promising assets.

Figure: Figure 2: Strategies profit coefficient and Clipped-INF-med-SMD assets distribution over 2023 year
Refer to caption: x2.png

### 5.3 Zeroth-order optimization

To demonstrate the performance of ZO-clipped-med-SSTM, we follow Kornilov et al. () and conduct experiments on the following problem:

$$ $\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{2}+\langle\xi,x\rangle,$ $$

where $\xi$ is a random vector with independent components sampled from the symmetric Levy $\alpha$-stable distribution with different $\alpha=0.75,1.0,1.25,1.5$, $A\in\mathbb{R}^{l\times d}$, $b\in\mathbb{R}^{l}$. Note, that $\alpha$ has the same meaning as $\kappa$, because this distribution asymptotic behavior is $f(x)\sim\frac{1}{|x|^{1+\alpha}}$ for $\alpha<2$.

For ZO-clipped-med-SSTM, the best median size is $m=2$. We compare it with the median size $m=0$ which is basically ZO-clipped-SSTM. We additionally compare our algorithm with ZO-clipped-SGD from Kornilov et al. () and ZO-clipped-med-SGD  — version of ZO-clipped-SGD with gradient estimation step replaced with median clipping version from our work.

The results over 3 launches are presented in Figure 3. The green lines on the graphs represent algorithms with median clipping. We can see that for extremely noised data $\kappa\leq 1$, our median clipping-based methods significantly outperform non-median versions. While, for standard heavy-tailed noise $\kappa>1$, our methods do not lose to other competitors.

In Appendix D.2, we provide technical details about hyperparameters, additional experiments with enlarged number of launches and study asymmetric noise and its effect on our median methods.

Figure: Figure 3: Convergence of ZO-clipped-SSTM, ZO-clipped-med-SSTM, ZO-clipped-SGD and ZO-clipped-med-SGD in terms of a gap function w.r.t. the number of consumed samples from the dataset for different $\alpha=\kappa$ parameters (left-to-right and top-to-bottom: 0.75, 1.0, 1.25, 1.5)
Refer to caption: extracted/5911462/additional_graphs/COMPRESSED/train_loss_zo_methods_average_1_paths_3_noise_sstm_sgd_alpha_0.75.jpg

## 6 Discussion

Limitations. The assumption of the symmetric noise can be seen as a limitation from a practical point of view. It is indeed the case, but we argue that it is not as severe as it looks.
A common strategy to solve a general optimization problem is to run several algorithms in a competitive manner to see which performs better in practice. This approach is implemented in industrial solvers such as Gurobi. Thus, if we have different algorithms, each suited to its own conditions, we can simply test to see which one is faster for our particular case. In this scenario, we want a set of algorithms, each designed for its specific case. Our algorithm can serve as one of the options in such mix, since it provides considerable acceleration in a significant number of noise cases.

Potential impact. We believe that ideas and obtained results from our work can inspire the community to further develop both zeroth-order methods and clipping technique. Especially considering how effectively our algorithms can work in a wide range of noise cases.

Broader impact. This paper presents work whose goal is to advance the field of Optimization. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

## 7 Acknowledgements

This research has been financially supported by The Analytical Center for the Government of the Russian Federation (Agreement 70-2021-00143 dd. 01.11.2021, IGK 000000D730324P540002)

## Appendix A Remarks about the assumption on the noise

In this section, we discuss our novel noise Assumption 3. We provide comparison with previous works (Remark 3), standard examples (Remark 5) and explain the roles of parameters (Remark 4).

###### Remark 3 (Comparison with previous assumptions) .

In works Dvinskikh et al. [], Kornilov et al. [], different assumption on Lipschitz noise is considered. For any realization of $\xi$, the function $f(x,\xi)$ is $M^{\prime}_{2}(\xi)$-Lipschitz, i.e.,

$$ $|f(x,\xi)-f(y,\xi)|\leq M^{\prime}_{2}(\xi)\|x-y\|_{2},\quad\forall x,y\in Q$ (15) $$

and $M^{\prime}_{2}(\xi)^{\kappa}$ has bounded $\kappa$-th moment ($\kappa$ > 1), i.e., $[M^{\prime}_{2}]^{\kappa}\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbb{E}_{
\xi}[M^{\prime}_{2}(\xi)^{\kappa}]<\infty$.

We emphasize that if Assumption 3 holds with $\kappa$ then one can find $M^{\prime}_{2}(\xi,x,y)$ such that (15) holds for any $1<\kappa^{\prime}<\kappa$ with $M^{\prime}_{2}=O(M_{2}+\Delta)$, where constant in $O(\cdot)$ depends only on $\kappa^{\prime}$.

###### Proof.

Let noise $\phi(\xi|x,y)$ satisfies Assumption 3 with Lipschitz oracle and $\kappa>1$, then it holds

$$ $\displaystyle|f(x,\xi)-f(y,\xi)|$ $\displaystyle=$ $\displaystyle|f(x)-f(y)+\phi(\xi|x,y)|$ $\displaystyle\leq$ $\displaystyle|f(x)-f(y)|+|\phi(\xi|x,y)|$ $\displaystyle\overset{\text{As~{}\ref{as:Lipshcitz}}}{\leq}$ $\displaystyle M_{2}\|x-y\|_{2}$ $\displaystyle+$ $\displaystyle\frac{|\phi(\xi|x,y)|}{\|x-y\|_{2}}\|x-y\|_{2}.$ $$

Let us denote $M^{\prime}_{2}(\xi,x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}M_{2}+\frac{|
\phi(\xi|x,y)|}{\|x-y\|_{2}}$ and show that for any $1<\kappa^{\prime}<\kappa$ random variable $M^{\prime}_{2}(\xi,x,y)$ has bounded $\kappa^{\prime}$-th moment which doesn’t depend on $x,y$. We notice that

$$ $\displaystyle\mathbb{E}_{\xi}[|\phi(\xi|x,y)|^{\kappa^{\prime}}]$ $\displaystyle=$ $\displaystyle\int\limits_{-\infty}^{+\infty}|u|^{\kappa^{\prime}}p(u|x,y)du$ $\displaystyle\leq$ $\displaystyle\int\limits_{-\infty}^{+\infty}\frac{|u|^{\kappa^{\prime}}\gamma^ {\kappa}|B(x,y)|^{\kappa}}{|B(x,y)|^{1+\kappa}+|u|^{1+\kappa}}du.$ $$

After substitution $t=\nicefrac{{u}}{{|B(x,y)|}}$, we get

$$ $\displaystyle\mathbb{E}_{\xi}[|\phi(\xi|x,y)|^{\kappa^{\prime}}]$ $\displaystyle\leq$ $\displaystyle\frac{\gamma^{\kappa}|B(x,y)|^{\kappa}}{|B(x,y)|^{\kappa-\kappa^{ \prime}}}\int\limits_{0}^{+\infty}\frac{|t|^{\kappa^{\prime}}}{1+|t|^{1+\kappa }}dt$ $\displaystyle\overset{\eqref{eq:noise_lip}}{\leq}$ $\displaystyle\gamma^{\kappa-\kappa^{\prime}}\Delta^{\kappa^{\prime}}\|x-y\|_{2 }^{\kappa^{\prime}}\int\limits_{0}^{+\infty}\frac{|t|^{\kappa^{\prime}}}{1+|t| ^{1+\kappa}}dt.$ $$

Integral $I(\kappa^{\prime})=\int\limits_{0}^{+\infty}\frac{\gamma^{\kappa-\kappa^{
\prime}}|t|^{\kappa^{\prime}}dt}{1+|t|^{1+\kappa}}$ converges since $\kappa^{\prime}<\kappa$ but its value tends to $\infty$ as $\kappa^{\prime}\to\kappa-0$.
Finally, we have

$$ $\displaystyle\mathbb{E}_{\xi}[M^{\prime}_{2}(\xi,x,y)^{\kappa^{\prime}}]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{\xi}\left[\left|M_{2}+\frac{|\phi(\xi|x,y)|}{\|x-y\|_ {2}}\right|^{\kappa^{\prime}}\right]$ $\displaystyle\overset{\text{Jensen inq, $\kappa^{\prime}>1$}}{\leq}$ $\displaystyle 2^{\kappa^{\prime}-1}\left[M_{2}^{\kappa^{\prime}}+\frac{\mathbb {E}_{\xi}\left[|\phi(\xi|x,y)|^{\kappa^{\prime}}\right]}{\|x-y\|_{2}^{\kappa^{ \prime}}}\right]$ $\displaystyle\leq$ $\displaystyle 2^{\kappa^{\prime}-1}\left[M_{2}^{\kappa^{\prime}}+I(\kappa^{ \prime})\Delta^{\kappa^{\prime}}\right].$ $$

Therefore, $M^{\prime}_{2}=(\mathbb{E}_{\xi}[M^{\prime}_{2}(\xi,x,y)^{\kappa^{\prime}}])^{
\frac{1}{\kappa^{\prime}}}=O(M_{2}+\Delta)$, where constant in $O(\cdot)$ depends only on $\kappa^{\prime}$.
∎

###### Remark 4 (Role of the scale function $B(x,y)$ ) .

In inequality (4) due to normalization property of probability density we must ensure that

$$ $\int\limits_{-\infty}^{+\infty}\frac{\gamma^{\kappa}|B(x,y)|^{\kappa}}{|B(x,y) |^{1+\kappa}+|u|^{1+\kappa}}du\geq\int\limits_{-\infty}^{+\infty}p(u|x,y)du=1.$ $$

One can make substitution $t=u/|B(x,y)|$ and ensure that for $\kappa\leq 2$

$$ $\int\limits_{-\infty}^{+\infty}\frac{\gamma^{\kappa}|B(x,y)|^{\kappa}du}{|B(x, y)|^{1+\kappa}+|u|^{1+\kappa}}=\gamma^{\kappa}\int\limits_{-\infty}^{+\infty} \frac{dt}{1+|t|^{1+\kappa}}\overset{\kappa=1}{\geq}\gamma^{\kappa}\pi.$ $$

Hence, $\gamma$ is sufficient to satisfy

$$ $\displaystyle\gamma\geq\left(\frac{1}{\pi}\right)^{\frac{1}{\kappa}}.$ $$

As scale value $|B(x,y)|$ decreases, quantiles of $p(u|x,y)$ gets closer to zero. Therefore, $|B(x,y)|$ can be considered as analog of variance of distribution $p(u|x,y)$.

###### Remark 5 (Standard oracles examples) .

To build noise $\phi(\xi|x,y)$ satisfying Assumption 3 with $\kappa>0$ we will use independent random variables $\{\xi_{k}\}$ with symmetric probability density functions $p_{\xi_{k}}(u)$

$$ $\displaystyle p_{\xi_{k}}(u)\leq\frac{|\gamma_{k}\Delta_{k}|^{\kappa}}{|\Delta _{k}|^{1+\kappa}+|u|^{1+\kappa}},\quad\Delta_{k},\gamma_{k}>0,$ $$

such that for any real numbers $\{a_{k}\}_{k=1}^{n}$ and sum $\sum\limits_{k=1}^{n}a_{k}\xi_{k}$ it holds

$$ $\displaystyle p_{\sum\limits_{k=1}^{n}a_{k}\xi_{k}}(u)\leq\frac{\left(\sum \limits_{k=1}^{n}|\gamma_{k}a_{k}\Delta_{k}|\right)^{\kappa}}{\left(\sum \limits_{k=1}^{n}|a_{k}\Delta_{k}|\right)^{1+\kappa}+|u|^{1+\kappa}}.$ (16) $$

Moreover, using Cauchy-Schwarz inequality we bound

$$ $\sum\limits_{k=1}^{n}|\gamma_{k}a_{k}\Delta_{k}|\leq\|(\gamma_{1}\Delta_{1}, \dots,\gamma_{n}\Delta_{n})^{\top}\|_{2}\cdot\|(a_{1},\dots,a_{k})^{\top}\|_{2}.$ (17) $$

For example, variables $\xi_{k}$ can have Cauchy distribution with $\kappa=1$ and $p(u)=\frac{1}{\pi}\frac{\Delta_{k}}{\Delta_{k}^{2}+u^{2}}$ parametrized by scale $\Delta_{k}$. For the independent Cauchy variables with scales $\{\Delta_{k}\}_{k=1}^{n}$ and any real numbers $\{a_{k}\}_{k=1}^{n}$, the sum $\sum\limits_{k=1}^{n}a_{k}\xi_{k}$ is the Cauchy variable with scale $\sum\limits_{k=1}^{n}|a_{k}|\Delta_{k}$. Therefore, inequality (16) for Cauchy variables holds true. For oracles, we have the following constants.

- •
Independent oracle:
$f(x,\xi)=f(x)+\xi_{x},f(y,\xi)=f(y)+\xi_{y},\phi(\xi|x,y)=\xi_{x}-\xi_{y}$, where $\xi_{x},\xi_{y}$ are independent samples for each point $x$ and $y$. Thus, we have the final scale $\Delta=\Delta_{x}+\Delta_{y}.$
- •
Lipschitz oracle:
$f(x,\boldsymbol{\xi})=f(x)+\langle\boldsymbol{\xi},x\rangle,f(y,\boldsymbol{
\xi})=f(y)+\langle\boldsymbol{\xi},y\rangle,\phi(\boldsymbol{\xi}|x,y)=\langle
\boldsymbol{\xi},x-y\rangle$, where $\boldsymbol{\xi}$ is $d$-dimensional random vector with components $\xi_{k}$. Oracle gives the same realization of $\boldsymbol{\xi}$ for both $x$ and $y$. In that case, the vector $\boldsymbol{\xi}$ can be restated to $\boldsymbol{\xi}=A\boldsymbol{\xi}_{ind}$ with $\phi(\boldsymbol{\xi}|x,y)=\langle\boldsymbol{\xi}_{ind},A^{\top}(x-y)\rangle$, where $A$ is the correlation matrix and $\boldsymbol{\xi}_{ind}$ are independent Cauchy variables. Now, if the vector $\boldsymbol{\xi}_{ind}$ has scales $\{\Delta_{k}\}_{k=1}^{n}$, then we have $\gamma$ and $B(x,y)$ from Assumption 3 equal to
$\displaystyle\gamma$
$\displaystyle=$
$\displaystyle\frac{1}{\pi},$
$\displaystyle B(x,y)$
$\displaystyle=$
$\displaystyle\sum\limits_{k=1}^{d}|\Delta_{k}[A^{\top}(x-y)]_{k}|\overset{
\eqref{eq:Cauchy_sch}}{\leq}\|(\Delta_{1},\dots,\Delta_{d})^{\top}\|_{2}||A^{
\top}||_{2}||x-y||_{2}.$

###### Remark 3 (Comparison with previous assumptions) .

###### Proof.

###### Remark 4 (Role of the scale function B ⁢ ( x , y ) 𝐵 𝑥 𝑦 B(x,y) italic_B ( italic_x , italic_y ) ) .

###### Remark 5 (Standard oracles examples) .

## Appendix B Proofs

### B.1 Proof of Lemma 1 .

To begin with, we need some properties of the smoothed approximation $\hat{f}_{\tau}$.

###### Lemma 2 ( Gasnikov et al. [ 2022b ] , Theorem 2.1) .

Consider $\mu$-strongly convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$. For the smoothed function $\hat{f}_{\tau}$ defined in (1), the following properties hold true:

- 1.
Function $\hat{f}_{\tau}$ is $M_{2}$-Lipschitz and satisfies
$\sup\limits_{x\in\mathbb{R}^{d}}|\hat{f}_{\tau}(x)-f(x)|\leq\tau M_{2}.$
- 2.
Function $\hat{f}_{\tau}$ is differentiable on $\mathbb{R}^{d}$ with the following gradient at point $x\in\mathbb{R}^{d}$:
$\nabla\hat{f}_{\tau}(x)=\mathbb{E}_{\mathbf{e}}\left[\frac{d}{\tau}f(x+\tau
\mathbf{e})\mathbf{e}\right],$
where $\mathbf{e}\sim U(S^{d}_{2})$ is a random vector uniformly distributed on the unit Euclidean sphere.
- 3.
Function $\hat{f}_{\tau}$ is $L$-smooth with $L=\nicefrac{{\sqrt{d}M_{2}}}{{\tau}}$ on $\mathbb{R}^{d}$.

###### Proposition 1 (Strong convexity of $\hat{f}_{\tau}$ ) .

Consider $\mu$-strongly convex (As. 1) function $f$. Then the smoothed function $\hat{f}_{\tau}$ defined in (1) is also $\mu$-strongly convex.

###### Proof.

Function $f$ is $\mu$-strongly convex if for any points $x,y\in\mathbb{R}^{d}$ and $t\in[0,1]$ we have

$$ $f(xt+y(1-t))\leq t\cdot f(x)+(1-t)\cdot f(y)-\frac{1}{2}\mu t(1-t)\|x-y\|_{2}^ {2}.$ $$

Following definition of $\hat{f}_{\tau}$, we write down for $\mathbf{u}\in U(B^{d}_{2})$ inequality

$$ $\displaystyle f(xt+y(1-t)+\tau\mathbf{u})$ $\displaystyle=$ $\displaystyle f((x+\tau\mathbf{u})\cdot t+(y+\tau\mathbf{u})\cdot(1-t))$ $\displaystyle\leq$ $\displaystyle t\cdot f(x+\tau\mathbf{u})+(1-t)\cdot f(y+\tau\mathbf{u})-\frac{ 1}{2}\mu t(1-t)\|x-y\|_{2}^{2}.$ $$

Taking math expectation $\mathbb{E}_{\mathbf{u}}$ from both sides, we have

$$ $\mathbb{E}_{\mathbf{u}}[f(xt+y(1-t)+\tau\mathbf{u})]\leq t\cdot\mathbb{E}_{ \mathbf{u}}[f(x+\tau\mathbf{u})]+(1-t)\cdot\mathbb{E}_{\mathbf{u}}[f(y+\tau \mathbf{u})]-\frac{1}{2}\mu t(1-t)\|x-y\|_{2}^{2}.$ $$

∎

###### Proof of Lemma 1 ..

Firstly, we notice from our construction of the oracle

$$ $f(x,\xi)-f(y,\xi)=f(x)-f(y)+\phi(\xi|x,y),\quad\forall x,y\in\mathbb{R}^{d},$ $$

we have

$$ $\displaystyle g(x,\mathbf{e},\xi)$ $\displaystyle=$ $\displaystyle\frac{d}{2\tau}(f(x+\tau\mathbf{e},\xi)-f(x-\tau\mathbf{e},\xi))$ $\displaystyle=$ $\displaystyle\frac{d}{2\tau}[f(x+\tau\mathbf{e})-f(x-\tau\mathbf{e})]\mathbf{e }+\frac{d}{2\tau}\phi(\xi|x+\tau\mathbf{e},x-\tau\mathbf{e})\mathbf{e}$ $$

and for $\texttt{Med}^{m}(x,\mathbf{e},\{\xi\})$ we have

$$ $\displaystyle\texttt{Med}^{m}(x,\mathbf{e},\{\xi\})=\texttt{Median}\left(\left \{g(x,\mathbf{e},\xi^{i})\right\}_{i=1}^{2m+1}\right)$ (18) $\displaystyle=$ $\displaystyle\texttt{Median}\left(\left\{\frac{d}{2\tau}[f(x+\tau\mathbf{e})-f (x-\tau\mathbf{e})]\mathbf{e}+\frac{d}{2\tau}\phi(\xi^{i}|x+\tau\mathbf{e},x- \tau\mathbf{e})\mathbf{e}\right\}_{i=1}^{2m+1}\right)$ $\displaystyle=$ $\displaystyle\frac{d}{2\tau}[f(x+\tau\mathbf{e})-f(x-\tau\mathbf{e})]\mathbf{e}$ $\displaystyle+$ $\displaystyle\frac{d}{2\tau}\texttt{Median}\big{(}\big{\{}\phi(\xi^{i}|x+\tau \mathbf{e},x-\tau\mathbf{e})\big{\}}_{i=1}^{2m+1}\big{)}\mathbf{e}.$ (19) $$

Finite second moment:

Further, we analyze two terms: gradient estimation term (18) and the noise term (19).

Following work Kornilov et al. [] [Lemma $2.3.$] we have an upper bound for the second moment of (18)

$$ $\displaystyle\mathbb{E}_{\mathbf{e}}\left[\left|\left|\frac{d}{2\tau}[f(x+\tau \mathbf{e})-f(x-\tau\mathbf{e})]\mathbf{e}\right|\right|_{q}^{2}\right]\leq da _{q}^{2}M_{2}^{2},$ (20) $$

where $a_{q}=d^{\frac{1}{q}-\frac{1}{2}}\min\{\sqrt{32\ln d-8},\sqrt{2q-1}\}$ is a special coefficient, such that,

$$ $\mathbb{E}_{\mathbf{e}}[\|\mathbf{e}\|_{q}^{2}]\leq a_{q}^{2}.$ (21) $$

See Lemma 2.1 from [Gorbunov et al., ] and Lemma $8.4$ from Kornilov et al. [] for more details.

Next, we deal with noise term (19). For symmetric variable $\phi(\xi|x,y)$ for all $x,y\in\mathbb{R}^{d}$ under Assumption 3 it holds

$$ $\displaystyle p(u)\leq\frac{\gamma^{\kappa}|B(x,y)|^{\kappa}}{|B(x,y)|^{1+ \kappa}+|u|^{1+\kappa}}.$ $$

Further, we prove that, for large enough $m$, noise term has finite variance. For this purpose, we denote $Y\stackrel{{\scriptstyle\text{def}}}{{=}}\texttt{Median}\big{(}\big{\{}\phi(
\xi^{i}|x,y)\big{\}}_{i=1}^{2m+1}\big{)}$ and cumulative distribution function of $Y$

$$ $P(t)\stackrel{{\scriptstyle\text{def}}}{{=}}\int\limits_{-\infty}^{t}p(u)du.$ $$

Median of $2m+1$ i.i.d. variables distributed according to $p(u)$ is $(m+1)$-th order statistic, which has probability density function

$$ $(2m+1)\begin{pmatrix}2m\\ m\end{pmatrix}P(t)^{m}(1-P(t))^{m}p(t).$ $$

The second moment $\mathbb{E}[Y^{2}]$ can be calculated via

$$ $\displaystyle\mathbb{E}[Y^{2}]$ $\displaystyle=$ $\displaystyle\int\limits_{-\infty}^{+\infty}(2m+1)\begin{pmatrix}2m\\ m\end{pmatrix}t^{2}P(t)^{m}(1-P(t))^{m}p(t)dt$ $\displaystyle\leq$ $\displaystyle(2m+1)\begin{pmatrix}2m\\ m\end{pmatrix}\sup_{t}\{t^{2}P(t)^{m}(1-P(t))^{m}\}\int\limits_{-\infty}^{+ \infty}p(t)dt$ $\displaystyle\leq$ $\displaystyle(2m+1)\begin{pmatrix}2m\\ m\end{pmatrix}\sup_{t}\{t^{2}P(t)^{m}(1-P(t))^{m}\}.$ $$

For any $t<0$, we have

$$ $\displaystyle P(t)$ $\displaystyle=$ $\displaystyle\int\limits_{-\infty}^{t}p(u)du\leq\int\limits_{-\infty}^{t}\frac {|\gamma B(x,y)|^{\kappa}}{|B(x,y)|^{1+\kappa}+|u|^{1+\kappa}}$ $\displaystyle\leq$ $\displaystyle\int\limits_{-\infty}^{t}\frac{|\gamma B(x,y)|^{\kappa}}{|u|^{1+ \kappa}}\leq\frac{|\gamma B(x,y)|^{\kappa}}{\kappa}\cdot\frac{1}{|t|^{\kappa}}.$ $$

Similarly, one can prove that for any $t>0$

$$ $1-P(t)=\int\limits^{\infty}_{t}p(u)du\leq\frac{|\gamma B(x,y)|^{\kappa}}{ \kappa}\cdot\frac{1}{t^{\kappa}}.$ $$

Since for any number $a\in[0,1]$ holds $a(1-a)\leq\frac{1}{4}$ we have for any $t\in\mathbb{R}$

$$ $P(t)(1-P(t))\leq\min\left\{\frac{1}{4},\frac{|\gamma B(x,y)|^{\kappa}}{\kappa} \cdot\frac{1}{|t|^{\kappa}}\right\}$ $$

along with

$$ $\displaystyle t^{2}P(t)^{m}(1-P(t))^{m}\leq\min\left\{\frac{t^{2}}{4^{m}}, \left(\frac{|\gamma B(x,y)|^{\kappa}}{\kappa}\right)^{m}\cdot\frac{1}{|t|^{m \kappa-2}}\right\}.$ (22) $$

If $m\kappa>2$ the first term of (22) increasing and the second one decreasing with the growth of $|t|$, then the maximum of the minimum (22) is achieved when

$$ $\displaystyle\frac{t^{2}}{4^{m}}$ $\displaystyle=$ $\displaystyle\left(\frac{|\gamma B(x,y)|^{\kappa}}{\kappa}\right)^{m}\cdot \frac{1}{|t|^{m\kappa-2}},$ $\displaystyle|t|$ $\displaystyle=$ $\displaystyle|\gamma B(x,y)|\left(\frac{4}{\kappa}\right)^{\frac{1}{\kappa}}.$ $$

Therefore, we get for any $t\in\mathbb{R}$

$$ $t^{2}P(t)^{m}(1-P(t))^{m}\leq\frac{|\gamma B(x,y)|^{2}}{4^{m}}\left(\frac{4}{ \kappa}\right)^{\frac{2}{\kappa}},$ $$

and, as a consequence

$$ $\displaystyle\mathbb{E}[Y^{2}]\leq(2m+1)\begin{pmatrix}2m\\ m\end{pmatrix}\frac{|\gamma B(x,y)|^{2}}{4^{m}}\left(\frac{4}{\kappa}\right)^{ \frac{2}{\kappa}}.$ $$

It only remains to note

$$ $\displaystyle\begin{pmatrix}2m\\ m\end{pmatrix}=\frac{(2m)!}{m!\cdot m!}=\prod\limits_{j=1}^{m}\frac{2j}{j} \cdot\prod\limits_{j=1}^{m}\frac{2j-1}{j}\leq 4^{m}.$ $$

Since $Y$ has the finite second moment, it has finite math expectation

$$ $\mathbb{E}[Y]=\int\limits_{-\infty}^{+\infty}(2m+1)\begin{pmatrix}2m\\ m\end{pmatrix}tP(t)^{m}(1-P(t))^{m}p(t)dt.$ $$

For any $t\in\mathbb{R}$, due to symmetry of $p(t)$, we have $P(t)=(1-P(-t))$ and $p(t)=p(-t)$ and, as a consequence,

$$ $\mathbb{E}[Y]=\int\limits_{-\infty}^{+\infty}(2m+1)\begin{pmatrix}2m\\ m\end{pmatrix}tP(t)^{m}(1-P(t))^{m}p(t)dt=0.$ $$

Finally, we have an upper bound for (19)

$$ $\displaystyle\mathbb{E}_{\mathbf{e},\xi}\left|\left|\frac{d}{2\tau}\texttt{ Median}\big{(}\big{\{}\phi(\xi^{i}|x+\tau\mathbf{e},x-\tau\mathbf{e})\big{\}} \big{)}\mathbf{e}\right|\right|_{q}^{2}$ (23) $\displaystyle=$ $\displaystyle\left(\frac{d}{2\tau}\right)^{2}\mathbb{E}_{\mathbf{e}}[\mathbb{E }_{\xi}[Y^{2}|\mathbf{e}]\cdot\|\mathbf{e}\|_{q}^{2}]$ $\displaystyle\leq$ $\displaystyle\left(\frac{d}{2\tau}\right)^{2}(2m+1)\left(\frac{4}{\kappa} \right)^{\frac{2}{\kappa}}\cdot\mathbb{E}_{\mathbf{e}}[|\gamma B(x+\tau\mathbf {e},x-\tau\mathbf{e})|^{2}\|\mathbf{e}\|_{q}^{2}].$ $$

In case of the independent oracle, from Assumption 3 and (5) we simplify

$$ $\displaystyle\mathbb{E}_{\mathbf{e}}[|\gamma B(x+\tau\mathbf{e},x-\tau\mathbf{ e})|\|\mathbf{e}\|_{q}^{2}]\leq\Delta^{2}\mathbb{E}_{\mathbf{e}}[\|\mathbf{e} \|_{q}^{2}]\overset{\eqref{eq:med_prop_a_q}}{\leq}\Delta^{2}a_{q}^{2}.$ (24) $$

In case of the Lipschitz oracle, we use (6) and get

$$ $\displaystyle\mathbb{E}_{\mathbf{e}}[|\gamma B(x+\tau\mathbf{e},x-\tau\mathbf{ e})|\|\mathbf{e}\|_{q}^{2}]$ $\displaystyle\leq$ $\displaystyle 4\Delta^{2}\tau^{2}\mathbb{E}_{\mathbf{e}}[\|\mathbf{e}\|_{2}^{2 }\|\mathbf{e}\|_{q}^{2}]\overset{\eqref{eq:med_prop_a_q}}{\leq}4\Delta^{2}\tau ^{2}a_{q}^{2}.$ $$

Combining upper bounds (20)
and (24) or (B.1), we obtain total bound

$$ $\displaystyle\mathbb{E}_{\mathbf{e},\xi}[\|\texttt{Med}^{m}(x,\mathbf{e},\{\xi \})\|_{q}^{2}]$ $\displaystyle\leq$ $\displaystyle 2\cdot\eqref{eq:med_prop_1_upper}+2\cdot\eqref{eq:med_prop_one_bound}$ $\displaystyle\eqref{eq:med_prop_lip_bound}.$ $$

For the batched gradient estimation $\texttt{BatchMed}^{m}_{b}(x,\{\mathbf{e}\},\{\xi\})$ and $q=2$, we use Lemma $4$ from Kornilov et al. [] that states

$$ $\displaystyle\mathbb{E}_{\mathbf{e},\xi}[\|\texttt{BatchMed}^{m}_{b}(x,\{ \mathbf{e}\},\{\xi\})\|_{2}^{2}]\leq\frac{1}{b}\cdot\mathbb{E}_{\mathbf{e},\xi }[\|\texttt{Med}^{m}(x,\mathbf{e},\{\xi\})\|_{2}^{2}].$ $$

For the bound of the centered second moment, we use Jensen’s inequality for any random vector $X$

$$ $\mathbb{E}[||X-\mathbb{E}[X]||_{q}^{2}]\leq 2\mathbb{E}[||X||_{q}^{2}]+2|| \mathbb{E}[X]||_{q}^{2}\leq 4\mathbb{E}[||X||_{q}^{2}].$ $$

Unbiasedness:

According to Lemma 2, the term (18) is an unbiased estimation of the gradient $\nabla\hat{f}_{\tau}(x)$. Indeed, the distribution of $\mathbf{e}$ is symmetrical and we can derive

$$ $\mathbb{E}_{\mathbf{e}}\left[\frac{d}{2\tau}[f(x+\tau\mathbf{e})-f(x-\tau \mathbf{e})]\mathbf{e}\right]=\mathbb{E}_{\mathbf{e}}\left[\frac{d}{\tau}[f(x+ \tau\mathbf{e})]\right]=\nabla\hat{f}^{\tau}(x).$ $$

Since $Y$ has the finite second moment, it has finite math expectation

$$ $\mathbb{E}[Y]=\int\limits_{-\infty}^{+\infty}(2m+1)\begin{pmatrix}2m\\ m\end{pmatrix}tP(t)^{m}(1-P(t))^{m}p(t)dt.$ $$

For any $t\in\mathbb{R}$, due to symmetry of $p(t)$, we have $P(t)=(1-P(-t))$ and $p(t)=p(-t)$ and, as a consequence,

$$ $\mathbb{E}[Y]=\int\limits_{-\infty}^{+\infty}(2m+1)\begin{pmatrix}2m\\ m\end{pmatrix}tP(t)^{m}(1-P(t))^{m}p(t)dt=0.$ $$

Hence, we obtained that $\mathbb{E}_{\mathbf{e},\xi}[\texttt{Med}^{m}(x,\mathbf{e},\{\xi\})]=\nabla\hat
{f}_{\tau}(x)$ along with $\mathbb{E}_{\mathbf{e},\xi}[\texttt{BatchMed}^{m}_{b}(x,\{\mathbf{e}\},\{\xi\}
)]=\nabla\hat{f}_{\tau}(x)$ as the batching is the mean of random vectors with the same math expectation.
∎

###### Lemma 2 ( Gasnikov et al. [ 2022b ] , Theorem 2.1) .

###### Proposition 1 (Strong convexity of f ^ τ subscript ^ 𝑓 𝜏 \hat{f}_{\tau} over^ start_ARG italic_f end_ARG start_POSTSUBSCRIPT italic_τ end_POSTSUBSCRIPT ) .

###### Proof.

###### Proof of Lemma 1 ..

### B.2 Proof of Convergence Theorems 1 and 2

For any point $x\in\mathbb{R}^{d}$, we might consider median estimations $\texttt{Med}^{m}(x,\mathbf{e},\{\xi\})$ and $\texttt{BatchMed}^{m}_{b}(x,\{\mathbf{e}\},\{\xi\})$ to be the oracle for the gradient of $\hat{f}_{\tau}(x)$ that satisfies Assumption 4.

###### Assumption 4 .

Let $G(x,\mathbf{e},\xi)$ be the oracle for the gradient of function $\hat{f}_{\tau}(x)$, such that for any point $x\in Q$ it is unbiased, i.e.,

$$ $\displaystyle\mathbb{E}_{\mathbf{e},\xi}[G(x,\mathbf{e},\xi)]=\nabla\hat{f}_{ \tau}(x),$ $$

and has bounded second moment, i.e.,

$$ $\displaystyle\mathbb{E}_{\mathbf{e},\xi}[\|G(x,\mathbf{e},\xi)-\nabla\hat{f}_{ \tau}(x)\|^{2}_{q}]\leq\Sigma^{2}_{q},$ (25) $$

where $\Sigma_{q}$ might depend on $\tau$.

Thus, in order to prove convergence of ZO-clipped-med-SSTM and ZO-clipped-med-SMD we use general convergence theorems with oracle satisfying Assumption 4 for ZO-clipped-SSTM (Theorem $1$ from Kornilov et al. [] with $\alpha=2$) and ZO-clipped-SMD (Theorem $4.3$ from Kornilov et al. [] with $\kappa=1$). Next, we take $\texttt{BatchMed}^{m}_{b}(x,\{\mathbf{e}\},\{\xi\})$ and $\texttt{Med}^{m}(x,\mathbf{e},\{\xi\})$ as the necessary oracles and substitute $\Sigma_{q}$ from (25) with $\sigma$ and $\sigma a_{q}$ from Lemma 1, respectively.

###### Assumption 4 .

#### B.2.1 Unconstrained problems.

###### Theorem 4 (Convergence of ZO-clipped-SSTM ) .

Consider convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ on $\mathbb{R}^{d}$ with gradient oracle under As. 4 with $\Sigma_{2}$.

We denote $\|x^{0}-x^{*}\|_{2}^{2}\leq R^{2}$, where $x^{0}$
is a starting point and $x^{*}$ is an optimal solution to (3).

We run ZO-clipped-SSTM for $K$ iterations with smoothing parameter $\tau$, batch size $b$, probability $1-\beta$ and further parameters $A=\ln\nicefrac{{4K}}{{\beta}}\geq 1$,
$a=\Theta(\min\{A^{2},\nicefrac{{\Sigma_{2}K^{2}\sqrt{A}\tau}}{{\sqrt{db}M_{2}R
}}\}),\lambda_{k}=\Theta(\nicefrac{{R}}{{(\alpha_{k+1}A)}})$.
We guarantee that with probability at least $1-\beta$:

$$ $f(y^{k})-f(x^{*})=2M_{2}\tau+\widetilde{{\cal O}}\left(\max\left\{\frac{\sqrt{ d}M_{2}R^{2}}{\tau K^{2}},\frac{\Sigma_{2}R}{\sqrt{bK}}\right\}\right).$ $$

Moreover, with probability at least $1-\beta$ the iterates of ZO-clipped-SSTM remain in the ball with center $x^{*}$ and radius $2R$, i.e., $\{x^{k}\}_{k=0}^{K+1},\{y^{k}\}_{k=0}^{K},\{z^{k}\}_{k=0}^{K}\subseteq\{x\in
\mathbb{R}^{d}:\|x-x^{*}\|_{2}\leq 2R\}$.

For ZO-clipped-med-SSTM, optimal convergence rate and parameters are presented in Theorem 5.

###### Theorem 5 (Convergence of ZO-clipped-med-SSTM ) .

Consider convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ on $\mathbb{R}^{d}$ with two-point oracle corrupted by noise under As. 3 with $\kappa>0$.

We denote $\|x^{0}-x^{*}\|_{2}^{2}\leq R^{2}$, where $x^{0}$
is a starting point and $x^{*}$ is an optimal solution to (3).

We run ZO-clipped-med-SSTM for $K$ iterations with smoothing parameter $\tau$, batchsize $b$, probability $1-\beta$ and further parameters $m=\frac{2}{\kappa}+1,A=\ln\nicefrac{{4K}}{{\beta}}\geq 1$,
$a=\Theta(\min\{A^{2},\nicefrac{{\sigma K^{2}\sqrt{A}\tau}}{{\sqrt{bd}M_{2}R}}
\}),\lambda_{k}=\Theta(\nicefrac{{R}}{{(\alpha_{k+1}A)}})$.
We guarantee that with probability at least $1-\beta$:

$$ $f(y^{k})-f(x^{*})=2M_{2}\tau+\widetilde{{\cal O}}\left(\max\left\{\frac{\sqrt{ d}M_{2}R^{2}}{\tau K^{2}},\frac{\sigma R}{\sqrt{bK}}\right\}\right),$ (26) $$

where $\sigma$ comes from Lemma 1.

Moreover, with probability at least $1-\beta$ the iterates of ZO-clipped-med-SSTM remain in the ball with center $x^{*}$ and radius $2R$, i.e., $\{x^{k}\}_{k=0}^{K+1},\{y^{k}\}_{k=0}^{K},\{z^{k}\}_{k=0}^{K}\subseteq\{x\in
\mathbb{R}^{d}:\|x-x^{*}\|_{2}\leq 2R\}$.

Statement of Theorem 1 follows if we equate both terms of (26) to $\frac{\varepsilon}{2}$, taking $\tau=\frac{\varepsilon}{4M_{2}}$ and explicit formula for $\sigma$ from Lemma 1.

###### Theorem 4 (Convergence of ZO-clipped-SSTM ) .

###### Theorem 5 (Convergence of ZO-clipped-med-SSTM ) .

#### B.2.2 Constrained problems.

###### Theorem 6 (Convergence of ZO-clipped-SMD ) .

Consider convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ on a convex compact $Q$ with gradient oracle under As. 4 with $\Sigma_{q}$.

We run ZO-clipped-SMD for $K$ iterations with smoothing parameter $\tau$, norm $q\in[2,+\infty]$, prox-function $\Psi_{p}$, probability $1-\beta$ and further parameters $\lambda=\Sigma_{q}\sqrt{K}$, $\nu=\frac{D_{\Psi_{p}}}{\lambda}$, where squared diameter $D_{\Psi_{p}}^{2}\stackrel{{\scriptstyle\text{def}}}{{=}}2\sup\limits_{x,y\in Q
}V_{\Psi_{p}}(x,y).$
We guarantee that with probability at least $1-\beta$:

$$ $f(y^{k})-f(x^{*})=2M_{2}\tau+\widetilde{{\cal O}}\left(\frac{\Sigma_{q}D_{\Psi _{p}}}{\sqrt{K}}\right).$ $$

For ZO-clipped-med-SMD, optimal convergence rate and parameters are presented in Theorem 7.

###### Theorem 7 (Convergence of ZO-clipped-med-SMD ) .

Consider convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ on a convex compact $Q$ with two-point oracle corrupted by noise As. 3 with $\kappa>0$.

We run ZO-clipped-med-SMD for $K$ iterations with smoothing parameter $\tau$, $q\in[2,+\infty]$, prox-function $\Psi_{p}$, probability $1-\beta$ and further parameters $m=\frac{2}{\kappa}+1$, $\lambda=\sigma a_{q}\sqrt{K}$, $\nu=\frac{D_{\Psi_{p}}}{\lambda}$, where diameter squared $D_{\Psi_{p}}^{2}\stackrel{{\scriptstyle\text{def}}}{{=}}2\sup\limits_{x,y\in Q
}V_{\Psi_{p}}(x,y).$
We guarantee that with probability at least $1-\beta$:

$$ $f(y^{k})-f(x^{*})=2M_{2}\tau+\widetilde{{\cal O}}\left(\frac{\sigma a_{q}D_{ \Psi_{p}}}{\sqrt{K}}\right),$ $$

where $\sigma,a_{q}$ come from Lemma 1.

Statement of Theorem 2 follows if we equate both terms of (7) to $\frac{\varepsilon}{2}$, taking $\tau=\frac{\varepsilon}{4M_{2}}$ and explicit formulas for $\sigma$ and $a_{q}$ from Lemma 1.

###### Theorem 6 (Convergence of ZO-clipped-SMD ) .

###### Theorem 7 (Convergence of ZO-clipped-med-SMD ) .

##### Recommendations for standard constrained problems.

In this paragraph, we discuss some standard sets $Q$ and prox-functions $\Psi_{p}$ taken from Ben-Tal and Nemirovski []. We can choose prox-functions to reduce $a_{q}D_{\Psi_{p}}$ and get better convergence constants. The two main setups are

- 1.
Ball setup, $p=2,q=2$:
$\qquad\Psi_{p}(x)=\frac{1}{2}\|x\|_{2}^{2},$
- 2.
Entropy setup, $p=1,q=\infty$:
$\qquad\Psi_{p}(x)=(1+\gamma)\sum_{i=1}^{d}(x_{i}+\gamma/d)\log(x_{i}+\gamma/d).$

We consider unit balls $B^{d}_{p^{\prime}}$ and standard simplex $\triangle^{d}_{+}$ as $Q$. For $Q=\triangle^{d}_{+}$ or $B^{d}_{1}$, the Entropy setup is preferable. Meanwhile, for $Q=B^{d}_{2}$ or $B^{d}_{\infty}$, the Ball setup is better.

### B.3 Proof of Theorem 3

###### Lemma 3 .

Let $f(x)$ be a linear function, then
$\nabla f(x)=\nabla\hat{f}_{\tau}(x)$.

###### Proof.

$$ $\displaystyle\nabla\hat{f}_{\tau}(x)=\nabla\mathbb{E}_{\mathbf{u}\sim B_{2}^{d }}[f(x+\tau\mathbf{u})]=\nabla\mathbb{E}_{\mathbf{u}\sim B_{2}^{d}}[\langle\mu ,x+\tau\mathbf{u}\rangle]$ $\displaystyle=\nabla\langle\mu,x+\tau\mathbb{E}_{\mathbf{u}\sim B_{2}^{d}}[u] \rangle=\nabla\langle\mu,x\rangle=\nabla f(x).$ $$

∎

###### Lemma 4 .

Let $f(x)$ be a linear function, $q=\infty$, $\tau=\alpha\sqrt{d}$, then

$$ $\mathbb{E}_{\mathbf{e},\xi}[\|g_{med}^{k+1}-\mu\|_{\infty}^{2}]\leq\left(32\ln d -8\right)\cdot\left(8M_{2}^{2}+2\alpha^{2}\Delta^{2}(2m+1)\left(\frac{4}{ \kappa}\right)^{\frac{2}{\kappa}}\right).$ $$

###### Proof.

From 1 with $q=\infty$ and $\tau=\alpha\sqrt{d}$ we get

$$ $\mathbb{E}_{\mathbf{e},\xi}[\|\texttt{Med}^{m}(x,\mathbf{e},\{\xi\})-\nabla \hat{f}_{\tau}(x)\|_{\infty}^{2}]\leq\sigma^{2}a_{\infty}^{2},\quad a_{\infty} =d^{-\frac{1}{2}}\sqrt{32\ln d-8},$ $$

where $\sigma^{2}=d\left(8M_{2}^{2}+2\alpha^{2}\Delta^{2}(2m+1)\left(\frac{4}{\kappa}
\right)^{\frac{2}{\kappa}}\right)$.

Hence, w.r.t (3) we get

$$ $\mathbb{E}_{\mathbf{e},\xi}[\|g_{med}^{k+1}-\mu\|_{\infty}^{2}]\leq\left(32\ln d -8\right)\cdot\left(8M_{2}^{2}+2\alpha^{2}\Delta^{2}(2m+1)\left(\frac{4}{ \kappa}\right)^{\frac{2}{\kappa}}\right).$ $$

∎

###### Lemma 5 .

[Lemma 5.1 from Sadiev et al. []] Let $X$ be a random vector in $\mathbb{R}^{d}$ and $\bar{X}=\texttt{clip}(X,\lambda)$, then

$$ $\|\bar{X}-\mathbb{E}[\bar{X}]\|\leq 2\lambda.$ (27) $$

Moreover, if for some $c\geq 0$

$$ $\mathbb{E}[X]=x\in\mathbb{R}^{n},\quad\mathbb{E}[\|X-x\|^{2}]\leq c^{2}$ $$

and $\|x\|\leq\frac{\lambda}{2}$, then

$$ $\displaystyle\left\|\mathbb{E}[\bar{X}]-x\right\|$ $\displaystyle\leq\frac{4c^{2}}{\lambda},$ (28) $\displaystyle\mathbb{E}\left[\left\|\bar{X}-x\right\|^{2}\right]$ $\displaystyle\leq 18c^{2},$ (29) $\displaystyle\mathbb{E}\left[\left\|\bar{X}-\mathbb{E}[\bar{X}]\right\|^{2}\right]$ $\displaystyle\leq 18c^{2}.$ (30) $$

###### Remark 6 .

Combination of Lemma 4 and Lemma 5 with $X=g_{med}^{k(t)}$ and $x=\mu$ in case when $\lambda\geq 2\|\mu\|_{\infty}$ immidiatly get the following bounds:

$$ $\left\|\mathbb{E}[g_{med}^{k(t)}]-\mathbb{E}[\tilde{g}_{med}^{k(t)}]\right\|_{ \infty}=\left\|\mu-\mathbb{E}[\tilde{g}_{med}^{k(t)}]\right\|_{\infty}\leq \frac{4c^{2}}{\lambda},$ $$

$$ $\mathbb{E}\left[\|\tilde{g}_{med}^{k(t)}\|_{\infty}^{2}\right]\leq 2\mathbb{E} \left[\|\tilde{g}_{med}^{k(t)}-\mu\|_{\infty}^{2}+\|\mu\|_{\infty}^{2}\right] \leq 2\|\mu\|_{\infty}^{2}+36c^{2},$ $$

for $c^{2}=\left(32\ln d-8\right)\cdot\left(8M_{2}^{2}+2\alpha^{2}\Delta^{2}(2m+1)
\left(\frac{4}{\kappa}\right)^{\frac{2}{\kappa}}\right).$

###### Lemma 6 .

Suppose that Clipped-INF-med-SMD with $1/2$-Tsallis entropy

$$ $\psi(x)=2\left(1-\sum_{i=1}^{d}x_{i}^{1/2}\right),\quad x\in\Delta_{+}^{d}$ $$

as prox-function generates the sequences $\{x_{k}\}_{k=0}^{K}$ and $\{\tilde{g}_{med}^{k}\}_{k=0}^{K}$, then for any $u\in\Delta_{+}^{d}$ holds:

$$ $\displaystyle\sum_{k=0}^{K}\sum_{s=1}^{2m+1}\langle\tilde{g}_{med}^{k},x_{k}-u\rangle$ $\displaystyle\leq(2m+1)\left[2\frac{d^{1/2}-\sum_{i=1}^{d}u_{i}^{1/2}}{\nu}+ \nu\sum_{k=0}^{K}\sum_{i=1}^{d}(\langle\tilde{g}_{med}^{k})_{i}^{2}\cdot x_{k, i}^{3/2}\right].$ $$

###### Proof.

By definition, the Bregman divergence $V_{\psi}(x,y)$ is:

$$ $V_{\psi}(x,y)=\psi(x)-\psi(y)-\langle\nabla\psi(y),x-y\rangle$ $$

$$ $=2\left(1-\sum_{i=1}^{d}x_{i}^{1/2}\right)-2\left(1-\sum_{i=1}^{d}y_{i}^{1/2} \right)+\sum_{i=1}^{d}y_{i}^{-1/2}(x_{i}-y_{i})$ $$

$$ $=-2\sum_{i=1}^{d}x_{i}^{1/2}+2\sum_{i=1}^{d}y_{i}^{1/2}+\sum_{i=1}^{d}y_{i}^{- 1/2}(x_{i}-y_{i}).$ $$

Note that the algorithm can be considered as an online mirror descent (OMD) with batching and the Tsallis entropy used as prox-function:

$$ $\displaystyle x_{k+1}=\arg\min_{x\in\Delta_{+}^{d}}\left[\nu x^{\mathtt{T}} \tilde{g}_{med}^{k}+V_{\psi}(x,x_{k})\right].$ $$

Thus, the standard inequality for OMD holds:

$$ $\displaystyle\langle\tilde{g}_{med}^{k},x_{k}-u\rangle\leq\frac{1}{\nu}\left[V _{\psi}(u,x_{k})-V_{\psi}(u,x_{k+1})-V_{\psi}(x_{k+1},x_{k})\right]+\langle \tilde{g}_{med}^{k},x_{k}-x_{k+1}\rangle.$ (31) $$

From Tailor theorem, we have

$$ $\displaystyle V_{\psi}(z,x_{k})=\frac{1}{2}(z-x_{k})^{T}\nabla^{2}\psi(y_{k})( z-x_{k})=\frac{1}{2}\|z-x_{k}\|^{2}_{\nabla^{2}\psi(y_{k})}$ $$

for some point $y_{k}\in[z,x_{k}]$.

Hence, we have

$$ $\displaystyle\langle\tilde{g}_{med}^{k},x_{k}-x_{k+1}\rangle-\frac{1}{\nu}V_{ \psi}(x_{k+1},x_{k})$ $\displaystyle\leq\max_{z\in R^{d}_{+}}\left[\langle\tilde{g}_{med}^{k},x_{k}-z \rangle-\frac{1}{\nu}V_{\psi}(z,x_{k})\right]$ $\displaystyle=\left[\langle\tilde{g}_{med}^{k},x_{k}-z^{*}_{k}\rangle-\frac{1} {\nu}V_{\psi}(z^{*}_{k},x_{k})\right]$ $\displaystyle\leq\frac{\nu}{2}\|\tilde{g}_{med}^{k}\|^{2}_{(\nabla^{2}\psi(y_{ k}))^{-1}}+\frac{1}{2}\|z^{*}-x_{k}\|^{2}_{\nabla^{2}\psi(y_{k})}-\frac{1}{\nu }V_{\psi}(z^{*},x_{k})$ $\displaystyle=\frac{\nu}{2}\|\tilde{g}_{med}^{k}\|^{2}_{(\nabla^{2}\psi(y_{k}) )^{-1}},$ $$

where $z^{*}=\arg\max_{z\in\mathbb{R}^{d}_{+}}\left[\langle\tilde{g}_{med}^{k},x_{k}-
z\rangle-\frac{1}{\nu}V_{\psi}(z,x_{k})\right]$.

Proceeding with (31), we get:

$$ $\displaystyle\langle\tilde{g}_{med}^{k},x_{k}-u\rangle\leq\frac{1}{\nu}\left[V _{\psi}(u,x_{k})-V_{\psi}(u,x_{k+1})\right]+\frac{\nu}{2}\|\tilde{g}_{med}^{k} \|^{2}_{(\nabla^{2}\psi(y_{k}))^{-1}}.$ $$

Sum over $k$ gives

$$ $\displaystyle\sum_{k=0}^{K}\langle\tilde{g}_{med}^{k},x_{k}-u\rangle$ $\displaystyle\leq\frac{V_{\psi}(x_{0},u)}{\nu}+\frac{\nu}{2}\sum_{k=0}^{K}( \tilde{g}_{med}^{k})^{T}\left(\nabla^{2}\psi(y_{k})\right)^{-1}\tilde{g}_{med} ^{k}$ $$

$$ $=2\frac{d^{1/2}-\sum_{i=1}^{d}u_{i}^{1/2}}{\nu}+\nu\sum_{k=0}^{K}\sum_{i=1}^{d }(\tilde{g}_{med}^{k})_{i}^{2}y_{k,i}^{3/2},$ (32) $$

where $y_{k}\in[x_{k},z_{k}^{*}]$ and $z_{k}^{*}=\arg\max_{z\in R^{d}_{+}}\left[\langle\tilde{g}_{med}^{k},x_{k}-z
\rangle-\frac{1}{\nu}V_{\psi}(z,x_{k})\right]$.

From the first-order optimality condition for $z^{*}_{k}$ we obtain

$$ $-\nu(\tilde{g}_{med}^{k})_{i}+(x_{k,i})^{1/2}=(z_{k,i}^{*})^{1/2}$ $$

and thus we get $z_{k,i}^{*}\leq x_{k,i}$.

Thus, (32) becomes

$$ $\sum_{k=0}^{K}\langle\tilde{g}_{med}^{k},x_{k}-u\rangle\leq 2\frac{d^{1/2}- \sum_{i=1}^{d}u_{i}^{1/2}}{\nu}+\nu\sum_{k=0}^{K}\sum_{i=1}^{d}(\tilde{g}_{med }^{k})_{i}^{2}\cdot x_{k,i}^{3/2}$ $$

and concludes the proof.
∎

###### Lemma 7 .

Suppose that Clipped-INF-med-SMD with $1/2$-Tsallis entropy as prox-function generates the sequences $\{x_{k}\}_{k=0}^{K}$ and $\{\tilde{g}_{med}^{k}\}_{k=0}^{K}$, and for each arm $i$ random reward $g_{t,i}$ at any step $t$ has bounded expectation $\mathbb{E}[g_{t,i}]\leq\frac{\lambda}{2}$ and the noise $g_{t,i}-\mu_{i}$ has symmetric distribution, then for any $u\in\Delta_{+}^{d}$ holds:

$$ $\mathbb{E}_{x_{k},\mathbf{e}_{[k]},\xi_{[k]}}\left[\sum_{i=1}^{d}(\tilde{g}_{ med}^{k})_{i}^{2}\cdot x_{k,i}^{3/2}\right]\leq\sqrt{d}\cdot(2\|\mu\|_{\infty} ^{2}+36c^{2}).$ (33) $$

Proof:

$$ $\displaystyle\mathbb{E}_{x_{k},\mathbf{e}_{[k]},\xi_{[k]}}\left[\sum_{i=1}^{d} (\tilde{g}_{med}^{k})_{i}^{2}\cdot x_{k,i}^{3/2}\right]\leq\mathbb{E}_{x_{k}, \mathbf{e}_{[k]},\xi_{[k]}}\left[\sum_{i=1}^{d}(\tilde{g}_{med}^{k})_{i}^{2} \cdot x_{k,i}^{1/2}\right]$ $\displaystyle\leq\mathbb{E}_{x_{k},\mathbf{e}_{[k]},\xi_{[k]}}\left[\sqrt{\sum _{i=1}^{d}(\tilde{g}_{med}^{k})_{i}^{2}}\cdot\sqrt{\tilde{g}_{med}^{k})_{i}^{2 }\cdot x_{k,i}^{1/2}}\right]$ $\displaystyle\leq\sqrt{\mathbb{E}_{x_{k},\mathbf{e}_{[k]},\xi_{[k]}}\left[\sum _{i=1}^{d}(\tilde{g}_{med}^{k})_{i}^{2}\right]}\cdot\sqrt{\mathbb{E}_{x_{k}, \mathbf{e}_{[k]},\xi_{[k]}}\left[(\tilde{g}_{med}^{k})_{i}^{2}\cdot x_{k,i}^{1 /2}\right]}$ $\displaystyle\leq\sqrt{d}\cdot(2\|\mu\|_{\infty}^{2}+36c^{2}).$ $$

Theorem 3
Consider MAB problem where the conditional probability density function for each loss satisfies Assumption 3 with $\Delta,\kappa>0,$ and $\|\mu\|_{\infty}\leq R$. Then, for the period $T$, the sequence $\{x_{t}\}_{t=1}^{T}$ generated by Clipped-INF-med-SMD with parameters $m=\frac{2}{\kappa}+1$, $\tau=\alpha\sqrt{d}$, $\nu=\frac{\sqrt{(2m+1)}}{\sqrt{T(36c^{2}+2R^{2})}}$, $\lambda=\sqrt{T}$ and prox-function $\psi(x)=2\left(1-\sum_{i=1}^{d}x_{i}^{1/2}\right)$ satisfies

$$ $\mathbb{E}\left[\mathcal{R}_{T}(u)\right]\leq\sqrt{Td}\cdot(8c^{2}/\sqrt{d}+4 \sqrt{(2m+1)(18c^{2}+R^{2})}),\quad u\in\Delta_{+}^{d},$ (34) $$

where $c^{2}=\left(32\ln d-8\right)\cdot\left(8M_{2}^{2}+2\alpha^{2}\Delta^{2}(2m+1)
\left(\frac{4}{\kappa}\right)^{\frac{2}{\kappa}}\right)$. Moreover, high probability bounds from Theorem 2 also hold.

###### Proof of Theorem 3 :.

Firstly, for any $x,y\in\triangle^{d}_{+}$ we have

$$ $\|x-y\|_{2}\leq\sqrt{2}.$ (35) $$

Next we obtain

$$ $\displaystyle\mathbb{E}\left[\mathcal{R}_{T}(u)\right]=\mathbb{E}\left[\sum_{t =1}^{T}l(x_{t})-\sum_{t=1}^{T}l(u)\right]\leq\mathbb{E}\left[\sum_{t=1}^{T} \langle\nabla l(x_{t}),x_{t}-u\rangle\right]$ $\displaystyle\leq\mathbb{E}\left[\sum_{t=1}^{T}\langle\mu-g_{med}^{k(t)},x_{k( t)}-u\rangle\right]+\mathbb{E}\left[\sum_{t=1}^{T}\langle g_{med}^{k(t)}- \tilde{g}_{med}^{k(t)},x_{k(t)}-u\rangle\right]+\mathbb{E}\left[\sum_{t=1}^{T} \langle\tilde{g}_{med}^{k(t)},x_{k(t)}-u\rangle\right]$ $\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}\langle g_{med}^{k(t)}-\tilde{g}_{ med}^{k(t)},x_{k(t)}-u\rangle\right]+\mathbb{E}\left[\sum_{t=1}^{T}\langle \tilde{g}_{med}^{k(t)},x_{k(t)}-u\rangle\right]$ $\displaystyle\leq\left[\sum_{t=1}^{T}\|\mathbb{E}[g_{med}^{k(t)}]-\mathbb{E}[ \tilde{g}_{med}^{k(t)}]\|_{\infty}\cdot\|x_{k(t)}-u\|_{1}\right]+\mathbb{E} \left[\sum_{t=1}^{T}\langle\tilde{g}_{med}^{k(t)},x_{k(t)}-u\rangle\right]$ $\displaystyle\overbrace{\leq}^{\text{Remark \ref{useful bounds}, \eqref{eq: simlex_bound}}}\frac{8c^{2}T}{\lambda}+(2m+1)\mathbb{E}\left[\sum_{k=0}^{K} \langle\tilde{g}_{med}^{k},x_{k}-u\rangle\right]$ $\displaystyle\overbrace{\leq}^{\text{Lemma \ref{regretest1}}}\frac{8c^{2}T}{ \lambda}+(2m+1)\left[2\frac{d^{1/2}-\sum_{i=1}^{d}u_{i}^{1/2}}{\nu}+\nu\sum_{k =0}^{K}\sum_{i=1}^{d}(\langle\tilde{g}_{med}^{k})_{i}^{2}\cdot x_{k,i}^{3/2}\right]$ $\displaystyle\overbrace{\leq}^{\text{Lemma \ref{regretest2}}}\frac{8c^{2}T}{ \lambda}+2(2m+1)\frac{\sqrt{d}}{\nu}+\nu T\sqrt{d}(36c^{2}+2\|\mu\|_{\infty}^{ 2})$ $\displaystyle=\sqrt{Td}\cdot(8c^{2}/\sqrt{d}+4\sqrt{(2m+1)(18c^{2}+R^{2})}),$ $$

where $c^{2}=\left(32\ln d-8\right)\cdot\left(8M_{2}^{2}+2\alpha^{2}\Delta^{2}(2m+1)
\left(\frac{4}{\kappa}\right)^{\frac{2}{\kappa}}\right)$.

∎

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Remark 6 .

###### Lemma 6 .

###### Proof.

###### Lemma 7 .

###### Proof of Theorem 3 :.

## Appendix C Restarted algorithms ZO-clipped-SSTM and ZO-clipped-SMD .

The restart technique is to run in cycle algorithm $\mathcal{A}$, taking the output point from the previous run as the initial point for the current one.

Figure: Algorithm 4 Restarted ZO-clipped-$\mathcal{A}$

Strong convexity of function $f$ with minimum $x^{*}$ implies an upper bound for the distance between point $x$ and solution $x^{*}$ as

$$ $\frac{\mu}{2}\|x-x^{*}\|_{2}^{2}\leq f(x)-f(x^{*}).$ $$

Considering upper bounds from Corollary 1, 2 for $f(x)-f(x^{*})$, one can construct a relation between $\|x_{0}-x^{*}\|_{2}$ and $\|x-x^{*}\|_{2}$ after $K$ iterations. Based on this relation, one can calculate iteration, after which it is more efficient to start a new run rather than continue current with slow convergence rate.

We apply the general Convergence Theorem $2$ from Kornilov et al. [] for R-ZO-clipped-SSTM and Theorem $5.2$ from Kornilov et al. [] for R-ZO-clipped-SMD with oracle satisfying Assumption 4. However, oracle can not depend on, $\tau$ which means that we should use either Lipschitz oracle or one-point oracle with small noise, i.e.,

$$ $\Delta\leq\left(\frac{\kappa}{4}\right)^{\frac{1}{\kappa}}\frac{\varepsilon}{ \sqrt{d}}.$ (36) $$

In the Convergence Theorems, minimal necessary value of $\tau=\frac{\varepsilon}{4M_{2}}$, hence

$$ $\displaystyle\sigma^{2}$ $\displaystyle=$ $\displaystyle 8dM_{2}^{2}+2\left(\frac{d\Delta}{\tau}\right)^{2}(2m+1)\left( \frac{4}{\kappa}\right)^{\frac{2}{\kappa}}\leq 32(2m+1)\cdot dM_{2}^{2}.$ $$

### C.1 Unconstrained problems

###### Theorem 8 (Convergence of R-ZO-clipped-SSTM ) .

Consider $\mu$-strongly convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ on $\mathbb{R}^{d}$ with gradient oracle under As. 4 with $\Sigma_{2}$.

We denote $\|x^{0}-x^{*}\|^{2}\leq R^{2}$, where $x^{0}$ is a starting point.

Let $\varepsilon$ be desired accuracy, value $1-\beta$ be desired probability and $N_{r}=\lceil\log_{2}(\nicefrac{{\mu R^{2}}}{{2\varepsilon}})\rceil$
be the number of restarts. For each stage $t=1,...,N_{r}$, we run ZO-clipped-SSTM with batch size $b_{t}$, $\tau_{t}=\nicefrac{{\varepsilon_{t}}}{{4M_{2}}},L_{t}=\nicefrac{{M_{2}\sqrt{d}
}}{{\tau_{t}}},K_{t}=\widetilde{\Theta}(\max\{\sqrt{\nicefrac{{L_{t}R_{t-1}^{2
}}}{{\varepsilon_{t}}}},(\nicefrac{{\Sigma_{2}R_{t-1}}}{{\varepsilon_{t}}})^{2
}/b_{t}\})$, $a_{t}=\widetilde{\Theta}(\max\{1,\nicefrac{{\Sigma_{2}K_{t}^{\frac{3}{2}}}}{{
\sqrt{b_{t}}L_{t}R_{t}}}\})$ and $\lambda_{k}^{t}=\widetilde{\Theta}(\nicefrac{{R}}{{\alpha_{k+1}^{t}}})$, where $R_{t-1}=2^{-\frac{(t-1)}{2}}R$, $\varepsilon_{t}=\nicefrac{{\mu R_{t-1}^{2}}}{{4}}$, $\ln\nicefrac{{4N_{r}K_{t}}}{{\beta}}\geq 1$, $\beta\in(0,1]$.
Then, to guarantee $f(\hat{x}^{N_{r}})-f(x^{*})\leq\varepsilon$ with probability at least $1-\beta$, R-ZO-clipped-SSTM requires

$$ $\widetilde{\cal O}\left(\max\left\{\sqrt{\frac{M_{2}^{2}\sqrt{d}}{\mu \varepsilon}},\frac{\Sigma_{2}^{2}}{\mu\varepsilon}\right\}\right)\quad$ (37) $$

total number of oracle calls.

###### Theorem 9 (Convergence of Restarted ZO-clipped-med-SSTM ) .

Consider $\mu$-strongly convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ on $\mathbb{R}^{d}$ with oracle corrupted by noise under As. 3 with $\Delta,\kappa>0$.

To achieve function accuracy $\varepsilon$, i.e., $f(\hat{x}^{N_{r}})-f(x^{*})\leq\varepsilon$ with probability at least $1-\beta$ via Restarted ZO-clipped-med-SSTM median size must be $m=\frac{2}{\kappa}+1$, other parameters must be set according to Theorem 8 ($\Sigma_{2}=\sigma$ from Lemma 1). Then, Restarted ZO-clipped-med-SSTM requires for

- •
independent oracle under (36):
$\displaystyle\widetilde{\cal O}\left((2m+1)\cdot\max\left\{\sqrt{\frac{M_{2}^{
2}\sqrt{d}}{\mu\varepsilon}},\frac{dM_{2}^{2}}{\kappa\mu\varepsilon}\right\}
\right),$
(38)
- •
Lipschitz oracle:
$\displaystyle\widetilde{\cal O}\left((2m+1)\cdot\max\left\{\sqrt{\frac{M_{2}^{
2}\sqrt{d}}{\mu\varepsilon}},\frac{d(M_{2}^{2}+d\Delta^{2}/\kappa^{\frac{2}{
\kappa}})}{\mu\varepsilon}\right\}\right)$
(39)

total number of oracle calls.

Similar to the convex case, the first term in bounds (39), (38) is optimal in $\varepsilon$ for the deterministic case for non-smooth strongly convex problems (see Bubeck et al. []). The second term is optimal in terms of $\varepsilon$ for zeroth-order problems with finite variance (see Nemirovskij and Yudin []).

###### Theorem 8 (Convergence of R-ZO-clipped-SSTM ) .

###### Theorem 9 (Convergence of Restarted ZO-clipped-med-SSTM ) .

### C.2 Constrained problems

###### Theorem 10 (Convergence of R-ZO-clipped-SMD ) .

Consider $\mu$-strongly convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ on a convex compact $Q$ with gradient oracle under As. 4 with $\Sigma_{q}$.

We set the prox-function $\Psi_{p}$ and norm $p\in[1,2]$. Denote $R_{0}^{2}\stackrel{{\scriptstyle\text{def}}}{{=}}\sup_{x,y\in Q}2V_{\Psi_{p}}(
x,y)$ for the diameter of the set $Q$ and $R_{t}=R_{0}/2^{t}$.

Let $\varepsilon$ be desired accuracy and $N=\widetilde{O}\left(\frac{1}{2}\log_{2}\left(\frac{\mu R_{0}^{2}}{2
\varepsilon}\right)\right)$ be the number of restarts. For each $t=\overline{1,N_{r}}$, we run ZO-clipped-SMD with $K_{t}=\widetilde{O}\left(\left[\frac{\Sigma_{q}}{\mu R_{t}}\right]^{2}\right)$, $\tau_{t}=\frac{\Sigma_{q}R_{t}}{M_{2}\sqrt{K_{t}}}$, $\lambda_{t}=\sqrt{K_{t}}\Sigma_{q}$ and $\nu_{t}=\frac{R_{t}}{\lambda_{t}}$. To guarantee $f(\hat{x}^{N_{r}})-f(x^{*})\leq\varepsilon$ with prob. at least $1-\beta$, R-ZO-clipped-SMD requires

$$ $\widetilde{O}\left(\frac{\Sigma_{q}^{2}}{\mu\varepsilon}\right)$ $$

total number of oracle calls.

###### Theorem 11 (Convergence of Restarted ZO-clipped-med-SMD ) .

Consider $\mu$-strongly convex (As. 1) and $M_{2}$-Lipschitz (As. 2) function $f$ on $\mathbb{R}^{d}$ with two-point oracle corrupted by noise under As. 3 with $\kappa>0$ and $\Delta>0$.

To achieve accuracy $\varepsilon$, i.e., $f(\hat{x}^{N_{r}})-f(x^{*})\leq\varepsilon$ via Restarted ZO-clipped-med-SMD with probability at least $1-\beta$ median size must be $m=\frac{2}{\kappa}+1$, other parameters must be set according to Theorem 10 ($\Sigma_{q}=\sigma a_{q}$ from Lemma 1). In this case, Restarted ZO-clipped-med-SMD requires for

- •
independent oracle under (36):
$\displaystyle\widetilde{\cal O}\left((2m+1)\cdot\frac{dM_{2}^{2}a^{2}_{q}}{
\kappa\mu\varepsilon}\right),$
(40)
- •
Lipschitz oracle:
$\displaystyle\widetilde{\cal O}\left((2m+1)\cdot\frac{d(M_{2}^{2}+d\Delta^{2}/
\kappa^{\frac{2}{\kappa}})a^{2}_{q}}{\mu\varepsilon}\right)$
(41)

total number of oracle calls, where $a_{q}=d^{\frac{1}{q}-\frac{1}{2}}\min\{\sqrt{32\ln d-8},\sqrt{2q-1}\}$.

###### Theorem 10 (Convergence of R-ZO-clipped-SMD ) .

###### Theorem 11 (Convergence of Restarted ZO-clipped-med-SMD ) .

## Appendix D Experiments details

Each experiment is computed on a CPU in several hours. The code is written in Python and will be made public after acceptance. For HTINF Huang et al. [], APE Lee et al. [], ZO-clipped-SSTM and ZO-clipped-SGD Kornilov et al. [], we provide our own implementation based on pseudocodes from the original articles.

### D.1 Multi-armed bandits

In our experimental setup, individual experiments are subject to significant random deviations. To enhance the informativeness of the results, we conduct $100$ individual experiments and analyze aggregated statistics.

By design, we possess knowledge of the conditional probability of selecting the optimal arm for all algorithms, which remains stochastic due to the nature of the experiment’s history.

To mitigate the high dispersion in probabilities, we apply an average filter with a window size of $30$ to reduce noise in the plot. APE and HTINF can’t handle cases when noise expectation is unbounded, so we modeled this case with a low value of $\alpha=0.01$, where $1+\alpha$ is the moment that exists in the problem statement for APE and HTINF.

#### D.1.1 Dependence on κ 𝜅 \kappa italic_κ

We conduct experiments to check dependence on $\kappa$ under the symmetric Levy $\alpha$-stable noise, where $\alpha=\kappa$. We compare standard INFC method from [Dorn et al., ] which allows $\kappa\leq 1$ with Clipped-INF-med-SMD, and comparison results can be found in Figure 4.

Figure: Figure 4: Convergence of Clipped-INF-med-SMD and INFC under $\kappa=1.5,1,0.5$, respectively
Refer to caption: extracted/5911462/image_2024-10-02_13-35-29.png

Figure: Figure 5: Convergence of ZO-clipped-SSTM, ZO-clipped-med-SSTM, ZO-clipped-SGD and ZO-clipped-med-SGD over $15$ launches
Refer to caption: extracted/5911462/train_loss_zo_methods_big_task_n_100_noise_1_average_5_paths_3_noise_sstm_sgd_small_pages-to-jpg-0001.jpg

### D.2 Zeroth-order optimization

To generate $A\in\mathbb{R}^{l\times d}$ and $b\in\mathbb{R}^{l}$ we draw them from standard normal distribution with $d=16$ and $l=200$. For algorithms, we gridsearch stepsize $a$ over $\{0.1,0.01,0.001,0.0001\}$ and smoothing parameter $\tau$ over $\{0.1,0.01,0.001\}$. For ZO-clipped-med-SSTM, the parameters $a=0.001$, $L=1$ (note that $a$ and $L$ are actually used together in the algorithm, therefore, we gridsearch only one of them) and $\tau=0.01$ are the best. For ZO-clipped-med-SGD, we use $a=0.01$, default momentum of $0.9$ and $\tau=0.1$. For non-median versions, after the same gridsearch, parameters happened to be the same.

To obtain better estimates for methods’ performance, we conduct experiment with $\kappa=1$ over $15$ launches and present the results in Figure 5.

#### D.2.1 Symmetric and asymmetric noise

To check the dependence on the addition of an asymmetric part to the noise, we replace the noise $\xi$ with $\xi=w*\xi_{1}+(1-w)*|\xi_{2}|$ with $\xi_{1}$ drawn from a symmetric Levy $\alpha$-stable distribution with $\alpha=1.0$ and $\xi_{2}$ being a random vector with independent components sampled from

- •
the same distribution
- •
standard normal distribution.

For $w$, we consider $0.9$ (meaning the weight of symmetric noise is bigger) and $0.5$ (equal impact). We take a component-wise absolute values of $\xi_{2}$, which makes $w$ a mix of symmetric and asymmetric noise. The results are presented in Figures 6 (Levy noise) and 7 (normal noise).

Figure: Figure 6: Convergence of ZO-clipped-SSTM, ZO-clipped-med-SSTM, ZO-clipped-SGD and ZO-clipped-med-SGD with asymmetric Levy noise addition with weight of symmetric part of $0.9$ and $0.5$ on left and right, respectively
Refer to caption: extracted/5911462/additional_graphs/COMPRESSED/train_loss_zo_methods_average_1_paths_3_noise_sstm_sgd_alpha_1.0_levy_0.9.jpg

Figure: Figure 7: Convergence of ZO-clipped-SSTM, ZO-clipped-med-SSTM, ZO-clipped-SGD and ZO-clipped-med-SGD with asymmetric normal noise addition with weight of symmetric part of $0.9$ and $0.5$ on left and right, respectively
Refer to caption: extracted/5911462/additional_graphs/COMPRESSED/train_loss_zo_methods_average_1_paths_3_noise_sstm_sgd_alpha_1.0_normal_0.9.jpg

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: The need for a two-point oracle seems like a limiting factor. Being able to obtain 2 samples with the same noise parameter does not seem trivial. In what real world settings do we have access to such oracles?
soundness: 4
strengths: In the convex optimization setting, convergence rate of the proposed algorithms are either the first result or matches the best known bounds in the literature (in the case of bounded variance).

Algorithms are demonstrated to perform well in comparison to previous SOTA, even in the bandit case.
summary: This paper consider non-smooth convex optimization with a zeroth-order oracle with heavy-tail symmetric stochastic noise. Algorithms are proposed for settings with heavier noise than what is often considered in the literature. The technique is further applied to stochastic multi-armed bandit problem.
weaknesses: The regret bound in the bandit case is suboptimal.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. What does “ZO-clipped-med-SSTM” denote for?
2. On Line 14-Line 15, the authors state that “Unlike the existing high-probability results requiring the noise to have bounded $\kappa$-th moment with $\kappa\in(1, 2]$..”. However, on Line 73-Line 74, it seems that this work actually needs the assumption of bounded $\kappa$-moment of losses ($\kappa\in(1, 2]$) in the case of heavy-tailed MABs. 
3. On Line 81, the authors state that the proposed method achieves high-probability optimal convergence rates. However, I do not seem to find any discussions about the lower bound of the convergence rate for the case of unconstrained optimization. How can we regard the upper bound as “optimal” if there are no lower bounds provided?
4. On Line 84-Line 85, the authors say that they achieve the $\widetilde{O}(\sqrt{dT})$ regret while also saying that their result is “suboptimal”. Why is this result “suboptimal”? To me, this is (nearly) optimal as it is known that the minimax-optimal regret lower bound for MABs is exactly of $\Omega(\sqrt{dT})$.
5. The algorithm in [3] can only obtain a regret of order $ O\left(\sigma K^{1-1 / \kappa} T^{1 / \kappa}+\sqrt{K T}\right) $. Intuitively, why the algorithm in this work can obtain the $\widetilde{O}(\sqrt{dT})$ regret without the dependence on $\kappa$ of the exponent of $T$? Is this because the algorithm explicitly leverages the knowledge of $\kappa$ to tune $m$?
6. The algorithm in [3] can only construct a biased estimator, which also results in their need to handle additional “skipping errors”. Intuitively, why the algorithm in this work can construct the unbiased estimator?
soundness: 3
strengths: 1.	This work seems to be the first work to solve the zeroth-order non-smooth convex optimization with heavy-tailed noises.
summary: This work makes the first step to study zeroth-order non-smooth convex optimization with heavy-tailed noises. To this end, the authors propose the ZO-clipped-med-SSTM estimator and apply it to solve zeroth-order non-smooth convex optimization with heavy-tailed noises in both the constrained and unconstrained cases. Also, the authors showcase the capability of their method in the case of multi-armed bandits (MABs) with heavy-tailed reward noises. Numerical experiments are provided.
weaknesses: 1. **Technical Innovations**: Both the clipping operation, the construction of the batch gradient estimator, and the algorithmic designs of ZO-clipped-med-SSTM seem particularly similar to those in [1]. Also, Lemma 1, the key lemma in this work, is proven based on the 
Lemma 2.3 of [2], which guarantees the bounded second moment. I would suggest the authors give more detailed comparisons with previous works, especially on the key technical innovations that do not appear in previous works.
2. **Adversarial Case**: The proposed algorithm requires the construction of a gradient estimator in a batched manner, which makes it unable to deal with the adversarial MABs with heavy-tailed noises. This is a drawback compared with [3], which is unable to handle adversarial MABs with heavy-tailed noises.
3. **Known $\kappa$**: All the algorithms in this work seem to require the knowledge of $\kappa$ to tune the median size parameter $m$. However, the algorithm in [3] can work in the case with unknown $\kappa$.
4. **Presentation**: 
   * For Table 1, I think it would be better if there are some discussions about both the advantages and the disadvantages of the results of the proposed methods against the baseline methods. Currently, the authors just present the results without providing any discussions on them.
   * Assumption 3 seems to be quite different from the heavy-tailed assumption in [3]. I think it would be better if the authors could give detailed discussions on this.

[1] Kornilov et al. Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance. NeurIPS, 23.

[2] Kornilov et al. Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact. Computational Management Science, 23.

[3] Huang et al. Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed
Bandits. ICML, 22.

____
**Post-rebuttal**: Sorry for the late replies. I thank the authors for the explanations. Some of my previous concerns regarding the presentation are addressed. However, my concern regarding whether the proposed algorithm is applicable in adversarial cases remains unsolved. In particular, the authors said that “algorithm will make a few shots with the same distribution to be able to construct a batch”. However, in adversarial cases, I think the key problem is exactly that the loss distribution may vary in each round and I believe it is impossible to construct a batch for the loss distribution in one round. For the technical novelty and my previous concerns regarding the advantages of the results against those in [1], it turns out that these are mainly due to the symmetric noise distribution assumption in Assumption 3 of this work. Such an assumption seems not very natural in practice and is also not required by [1]. As such, I am afraid that this work might not be ready for publication in ICLR and I have to maintain my current rating for this work.

[1] Huang et al. Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits. ICML, 22.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See in Weakness.
soundness: 3
strengths: - This paper is clearly written and well-organized.
- The authors have established a series of theoretical results, and perform the corresponding numerical experiments.
summary: This paper considers the problem of non-smooth convex optimization with bandit and heavy tailed feedbacks, and introduces the technique of building unbiased median gradient estimate with bounded second moment. This technique are further applied into the MAB problems with heavy-tailed rewards. Several empirical investigations are conducted to verify their theoretical findings.
weaknesses: - It seems that the proposed methods are simple combinations of existing algorithms with a median gradient estimate. For example, the proposed ZO-clipped-med-SSTM is similar to ZO-clipped-SSTM, with only a different gradient estimate. While I understand that even this combination presents certain analytical challenges, I encourage the authors to clearly describe these challenges
- Currently, the effectiveness of the method is verified on synthetic datasets. Could it also be validated on real-world datasets?
- Several crucial related works on bandits with heavy-tailed feedbacks [1, 2, 3] and  non-smooth optimization [4, 5, 6] are missing from the discussion of this paper. 


[1] Multi-armed bandit problems with heavy-tailed reward distributions. 2011.

[2] Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs. 2018.

[3] Optimal Algorithms for Lipschitz Bandits with Heavy-tailed Rewards. 2019.

[4] Complexity of finding stationary points of nonconvex nonsmooth functions. 2020.

[5] No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians. 2024.

[6] High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails. 2024.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: - For the stochastic MAB problem, as suggested by the authors that the regret upper bound of the proposed algorithm is $\tilde{O}(\sqrt{Td})$, which is suboptimal compared to the lower bound for MAB with bounded variance of losses. Is this because the proposed algorithm can deal with unbounded variance case (with the symmetric noise assumption)? If it is, how is the proposed upper bound in Theorem 3? Is there any lower bound?
- According to Theorem 1, 2, 3, the parameter $m$, which decides the batch size used to estimate the median, depends on the noise parameter $\kappa$. When the knowledge of $\kappa$ is not provided, how can the algorithm be implemented?

Please also kindly refer to the Weakness section.
soundness: 3
strengths: - With the additional symmetric noise assumption, this paper has improved the prior methods under the heavy-tailed noise case.
- The paper is relatively clear and easy to follow. Most concepts are well explained and the comparison of the final results with prior works is clear.
summary: This paper considers zeroth-order convex optimization problems with symmetric stochastic heavy-tailed noise. The gradient is estimated by the median in a batch, instead of using the empirical mean used in prior works. This technique is also applied to the linear bandits with heavy-tailed symmetric noise.
weaknesses: **Majors**:
- Under the additional symmetric noise assumption, this paper deals with the case when $\kappa\in(0,1)$, and improves the bound for $\kappa\in[1,2)$. From the algorithm design, Algorithm 1 and ZO-clipped-SSTM (Kornilov et al. (2023b)) largely follow the same procedure, expect that the estimate of the gradient changes from the randomly smoothed mean to the randomly smoothed median. Similarly, Algorithm 2 and ZO-Clip-SMD (Kornilov et al. (2023a)) are similar expect for the gradient estimate part. From this perspective, the main procedure required to deal with $\kappa\in(0,1)$ is the change of estimation statistics. It would be great if the authors can highlight the additional technical challenges and novelties. Otherwise, this paper looks incremental given the prior works.
- The motivation for the symmetric assumption is not well explained. As the symmetry in the noise is critical for the median estimate, a motivation is needed to support this assumption. 
- As this paper adopts bandits as an application and there is already some work in the bandits literature which considers heavy-tailed noise or robust bandits problems (e.g., [1]) without the symmetric noise assumption, it would be great if the authors can compare their results to them, in terms of the assumptions, methods, theoretical guarantees and efficiency of the algorithms.

**Minors**:
- Can the authors kindly modify Line 73? It can be misleading as Bubeck et al. (2013) does not make the symmetric noise assumption.

[1] Mathieu, T., Basu, D., & Maillard, O. A. (2024). Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithms. _Transactions on Machine Learning Research Journal_.

Meta-review: This paper studies zeroth-order non-smooth convex optimization with heavy-tailed symmetric noise. Compared to previous algorithms, the algorithm proposed in this paper could handle heavier noise, i.e., noise with bounded $\kappa$-th moment for any $\kappa>0$. The authors further apply this technique to stochastic multi-armed bandit with heavy-tailed rewards to showcase the capability of their method.

The main weakness raised by the reviewers is the main assumption made in this paper, i.e., the noise symmetry assumption. Compared to prior work, the main technical innovations come from this assumption, and it is unclear if such strong assumption would hold in practice. Although the authors argued that their algorithm can be applied in practice even without this assumption, it is not justified with theoretical analysis. Moreover, some prior work in the robust bandits literature does not require such a strong assumption. 

Given the high standards of ICLR and the weakness mentioned above, I would recommend rejecting this paper.

Decision: Reject