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

Dear Reviewer Jooe, thank you for your comments. Here are the answers to your questions and comments.

It would be great if the authors can highlight the additional technical challenges and novelties. Otherwise, this paper looks incremental given the prior works.

We addressed this question in the general response.

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.

Symmetric noise assumption may look restrictive, but we must highlight that a huge part of previous research on MAB and ZO methods with explicit noise structure is focused on symmetric distributions such as normal distribution, uniform distribution and Bernoulli distribution with p=1/2, Symmetric $\alpha$-stable distributiosn.

In practice, we can not know the noise distribution for sure. Nevertheless, one can run our method and if noise is close to symmetric, our methods are to show much better convergence. Moreover, in experiments with non-symmetric noise D.2.1, our methods do not lose to the standard SOTA approaches for any noises. Hence, running our methods in practice ends up with either typical convergence rates or faster rates in symmetric cases.

In the Limitation section, we describe the common strategy to solve a general optimization problem: run several algorithms in a competitive manner to see which performs better in practice. In this concept, we believe that including our methods in a list can only benefit the final result.

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.

We will add extra comparison dedicated to bandits methods in the revised version of the paper. The main difference is that our method can work with extremely heavy-tailed noise with unbounded math expectation ($\kappa < 1$) in both theory and practice without degeneration depending on $\kappa$. Other works do not consider that kind of noises.

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

Thank you! We will follow your suggestion.

Q1:

In our proof, an extra factor $\log d$ arises since we work with the $\ell_\infty$ norm instead of $\ell_2$ norm in the proof for bandits. Lemma 1 states that we need this extra factor $a_\infty \approx \log d$ for the bound of median estimator’s variance.

We would like to highlight that “optimality” here refers to the setting with any heavy-tailed noise with bounded variance. And we notice the fact that our bounds for any $\kappa$ and these optimal bounds exactly match. For the symmetric noises only, as far as we are aware, there is no proved lower bound.

We also discussed the "suboptimality" term in the general response.

Q2:

For the most common cases $\kappa$ is at least 1 (i.e. expectation exists), hence we could take a median size $m = 3$. In case when $\kappa$ could be arbitrarily small, we can construct an adaptive scheme, but we didn’t cover this part in our work. In practice, we additionally grid searched the median parameter $m$ among the range [3,5,7]. We noticed that unlike the choice of the clipping level, the choice of the median size slightly affects the convergence and does not require careful fine-tuning for the considered $\kappa$. Usually, the range [3,5,7] is enough to find optimal median size for optimal convergence.

Dear Reviewer ZxE4, thank you for your comments. Here are the answers to your questions and comments.

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

We addressed this weakness in the general response.

Currently, the effectiveness of the method is verified on synthetic datasets. Could it also be validated on real-world datasets?

For the bandits' setup, we verified our method on both synthetic and real-world's cryptocurrency portfolio selection problems in Sections $5.1, 5.2$, respectively.

For ZO methods, as far as we are aware, there are no publicly available real-world datasets to test performance in the community.

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.

Thank you for your comment. We will cite all mentioned works and discuss them in the revised version. Here we give brief comments on them. We didn’t know about [1], we will enlist it. Works [2] and [3] related to contextual multi-armed bandits (linear and Lipschitz, respectively), which are out of scope of this paper. Works [4,5,6] focus on non-convex case, while we work with convex functions for which gradient smoothing framework has theoretical base.

We believe that it is possible to expand our ZO and MAB median clipping approach to above-mentioned settings in future research.

Dear Reviewer SJFH, thank you for your comments. Here are the answers to your questions and comments.

The regret bound in the bandit case is suboptimal.

We addressed this question in the general response.

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?

As an example of the real world problem for the Lipschitz oracle, we can refer to the rounding error. As two points get close to each other, the corresponding rounding error decreases. In our paper, we also consider an oracle providing two points with independent noises and call it “Independent” oracle. This oracle is more conventional as it just returns functions values corrupted by independent noise sample.

Dear Reviewer uwXZ, thank you for your comments. Here are the answers to your questions and comments.

Technical Innovations:

We addressed this weakness in the general response.

Adversarial Case:

We do not think that batching restricts the use of our algorithm for adversarial MAB. In simple terms, instead of sampling one shot with a given probability distribution over arms, the algorithm will make a few shots with the same distribution to be able to construct a batch. This is a trade when we use more samples to construct better gradient estimates.

Known $\kappa$:

Note that we need to $\kappa$ only to set the optimal median size $m = \frac{2}{\kappa} + 1$. For the most common cases $\kappa$ is at least 1 (i.e. expectation exists), hence we could take median size m = 3. In case when $\kappa$ could be arbitrarily small, we can construct an adaptive scheme (we believe that it is possible to build analogue of scheme from [4] applied to median size), but we didn’t cover this part in our work.

In experiments with bandits and ZO methods, we additionally grid searched the median parameter $m$ among the range [3,5,7]. We noticed that unlike the choice of the clipping level, the choice of the median size slightly affects the convergence and does not require careful fine-tuning for the considered $kappa$. Usually, the range [3,5,7] is enough to find optimal median size for optimal convergence.

Presentation:

1. For Table 1, we will add discussion in the revised version of the paper. Our algorithms for ZO and bandits settings successfully incorporate the symmetry of the noise, allowing it to work with bounded $\kappa$-th moment. For $\kappa \leq1$, we are the first to prove convergence rates and verify it in practice. For convex ZO problems with $\kappa > 1$, we derive the bound $\sim \varepsilon^{-2}$ instead of baselines $\sim \varepsilon^{-\frac{\kappa}{\kappa - 1}}$.

However, such breaking results can be guaranteed only for symmetric noises. In practice, we can not know the noise distribution for sure, but one can run our method and if noise is close to symmetric, our methods are to show much better convergence. Moreover, in experiments with non-symmetric noise D.2.1, our methods do not lose to the baselines. Hence, running our methods in practice ends up with either typical convergence rates or faster rates in symmetric cases.

2. We discussed our Assumption in Appendix A in more detail. We show that it includes typical practical examples of heavy-tailed ZO oracles (Remark 5) and is consistent with previous Assumptions from [1] (Remark 3). We will expand the discussion right after Assumption 3 in the revised version.

Q1:

It stands for Zero Order clipped median Stochastic Similar Triangles Method. Clipped-Stochastic Similar Triangles Method was initially presented in [2].

Q2:

We think there is a misunderstanding here. Line 73- Line 74 refer to previous works on MAB with heavy tails. We will state it more clearly.

Q3:

We think there is a slight misunderstanding. For the symmetric noises, as far as we are aware, there are no proved lower bounds. On line 81, we refer to the optimal lower bounds for unconstrained zero-order optimization under any noise from lines 43-46 (when $\kappa = 2$). We make this moment more clear in the revised version.

Q4:

We addressed this question in the general response.

Q5:

The symmetry assumption makes the estimator unbiased (Lemma 1) with the finite variance. Here is the intuition behind it. The median of $2m+1$ elements is an $m+1$-th order statistic whose distribution is the product of original heavy-tailed distributions. Hence, if $m$ is large enough, this product properly lightens the original tails.

Q6:

Intuitively, our method does not have $\kappa$ dependency due to symmetry assumption. The symmetry allows us to prove that median estimate with a few samples is unbiased estimation with the finite variance for any $\kappa > 0$. In [4], the authors use clipping to cope with heavy tails and, thus, have to leverage between low variance and bias and big number of required samples. This trade-off worsens the regret bound as $\kappa \to 1$.

References:

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

[2] Gorbunov, Eduard, Marina Danilova, and Alexander Gasnikov. "Stochastic optimization with heavy-tailed noise via accelerated gradient clipping." Advances in Neural Information Processing Systems 33 (2020): 15042-15053.

[3] Bubeck, S., Cesa-Bianchi, N., & Lugosi, G. (2013). Bandits with heavy tail. IEEE Transactions on Information Theory, 59(11), 7711-7717.

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