Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911302665895936 |
|---|---|
| author | Kornilov, Nikita Dorn, Yuriy Lobanov, Aleksandr Kutuzov, Nikolay Shibaev, Innokentiy Gorbunov, Eduard Nazin, Alexander Gasnikov, Alexander |
| author_facet | Kornilov, Nikita Dorn, Yuriy Lobanov, Aleksandr Kutuzov, Nikolay Shibaev, Innokentiy Gorbunov, Eduard Nazin, Alexander Gasnikov, Alexander |
| contents | 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 $κ$-th moment with $κ\in (1,2]$, our results allow even heavier noise with any $κ> 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, namely, to achieve function accuracy $\varepsilon$ our methods with Lipschitz oracle require $\tilde{O}(d^2\varepsilon^{-2})$ iterations for any $κ> 0$. 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 $\tilde{O}(\sqrt{dT})$ regret. We demonstrate the performance of our zeroth-order and MAB algorithms for various $κ\in (0,2]$ on synthetic and real-world data. Our methods do not lose to SOTA approaches and dramatically outperform them for $κ\leq 1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02461 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise Kornilov, Nikita Dorn, Yuriy Lobanov, Aleksandr Kutuzov, Nikolay Shibaev, Innokentiy Gorbunov, Eduard Nazin, Alexander Gasnikov, Alexander Optimization and Control 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 $κ$-th moment with $κ\in (1,2]$, our results allow even heavier noise with any $κ> 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, namely, to achieve function accuracy $\varepsilon$ our methods with Lipschitz oracle require $\tilde{O}(d^2\varepsilon^{-2})$ iterations for any $κ> 0$. 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 $\tilde{O}(\sqrt{dT})$ regret. We demonstrate the performance of our zeroth-order and MAB algorithms for various $κ\in (0,2]$ on synthetic and real-world data. Our methods do not lose to SOTA approaches and dramatically outperform them for $κ\leq 1$. |
| title | Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2402.02461 |