Summary
This paper provides high probability bounds for the convergence of gradient-free methods on convex and strongly-convex functions when the noise in the gradient oracle has infinite variance. An oracle provides $f(x,\xi)$, a noisy evaluation of the function $f$ at point $x\in \mathbb{R}^d$ by the oracle, where $\xi$ is the noise variable. For the same noise $\xi$, the function is $M_2(\xi)$-Lipschitz, where $M_2(\xi)$ quantifies the noise level.
If the noise variance is finite, ($\mathbb{E}[M_2(\xi)^2] < \infty$), [1] provides optimal iteration and oracle complexity for convergence of in expectation. The primary technique used in [1] is a batched accelerated gradient method which uses smoothing. For a fixed constant $\tau>0$ which defines the smoothing level, smoothing computes an approximate gradient of $f$ at point $x\in \mathbb{R}^d$ as,
$$
g^B(x) = \frac{d}{2B \tau }\sum_{i=1}^B (f(x + \tau e_i, \xi_i) - f(x - \tau e_i, \xi_i))e_i
$$
Here, $e_i$ are sampled uniformly from the unit sphere, $\xi_i$ are the noise variables of the oracle and $B$ is the batch size. On expectation, the smoothed gradient is the gradient of $ \mathbb{E}_{e,\xi}[f(x + \tau e, \xi)] $. For small value of $\tau$, this approximation is close to $f$. Further, even if the function $f$ is non-smooth but Lipschitz, smoothing makes $\frac{\sqrt{d}M_2}{\tau}$ smooth.
This paper extends this technique to the infinite noise variance setting, $\mathbb{E}[M_2(\xi)^\alpha] < M_2^\alpha$ for some $\alpha \in (1,2]$ by applying clipping. Specifically, the technique of clipped Stochastic Similar Triangles used for handling heavy tailed noise in smooth optimization is extended to the non-smooth case by the above smoothing procedure.
For convex Lipschitz functions, the iteration complexity and oracle complexity is $\frac{\sqrt{d}^{1/4}}{\epsilon}$ and $\left(\frac{\sqrt{d}}{\epsilon}\right)^\frac{\alpha}{\alpha-1}$. For $\mu$-strongly convex and lipshcitz functions, the corresponding bounds are $\frac{d^{1/4}}{(\mu\epsilon)^{-1/2}}$ and $\left(\frac{d}{\mu\epsilon}\right)^{\frac{\alpha}{\alpha-1}}$. These rates are shown to be optimal in $\epsilon$.
Further, when if the oracle provides a corrupted value of $f$ with an additive corruption of $\lvert\delta(x)\rvert \leq \Delta$, the authors derive the maximum possible values of $\Delta$ such that the convergence rates for both smooth and non-smooth settings are unaffected by the corruption.
**References**
1. Gasnikov et al. The power of first-order smooth optimization for black-box non-smooth problems. ICML 2022.
2. Sadiev et al. High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance. ICML 2023.
Strengths
- **Interesting Problem Setting**: Heavy-tailed noise is a significant problem which violates the commonly used bounded variance assumption in stochastic optimization. The authors extend the solution of clipping to handle it for derivative-free methods.
- **Convergence Rates** : These are the first convergence rates for derivate-free optimization under heavy-tailed noise. Further, the rates are high probability bounds instead of in expectation. Additionally, for both cases, convex and strongly convex, the obtained rates are optimal in terms of error $\epsilon$.
- **Thorough literature review** : The authors thoroughly review existing results in derivative-free methods and clipping.
Weaknesses
- **Presentation** : The paper seems to be missing an introduction and experiment section. Although the paper is theoretical, the proposed algorithm, clipped-SSTM with two-point feedback, is new and should have been tested on at least synthetic problems.
- **Lack of a motivating example** : The authors do not provide a motivating example which justifies the heavy-tailed noise in gradient-free settings.
Questions
- Are there any lower bounds for oracle and iteration complexity in the adversarial corruption case in terms of $\Delta$?
- Are there methods other than clipping to handle unbounded variance in stochastic optimization?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.