76442

Автор(ы): 

Автор(ов): 

8

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Zeroth-order Median Clipping for Non-Smooth Convex Optimization Problems with Heavy-tailed Symmetric Noise

ISBN/ISSN: 

2331-8422

Наименование источника: 

  • arXiv: [math.OC]

Обозначение и номер тома: 

arxiv:2402.02461

Город: 

  • Cornell

Издательство: 

  • Cornell University

Год издания: 

2024

Страницы: 

1-24 http://arxiv.org/abs/2402.02461
Аннотация
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 κ∈(1,2], our results allow even heavier noise with any κ>0, e.g., the noise distribution can have unbounded 1-st moment. Moreover, our results match the best-known ones for the case of the bounded variance. To achieve this, we use the mini-batched median estimate of the sampled gradient differences, apply gradient clipping to the result, and plug in the final estimate into the accelerated method. We apply this technique to the stochastic multi-armed bandit problem with heavy-tailed distribution of rewards and achieve O(√dT) regret by incorporating the additional assumption of noise symmetry.

Библиографическая ссылка: 

Корнилов Н.М., Дорн Ю.В., Лобанов А.В., Кутузов Н.В., Шибаев И.А., Горбунов Э.А., Гасников А.В., Назин А.В. Zeroth-order Median Clipping for Non-Smooth Convex Optimization Problems with Heavy-tailed Symmetric Noise / arXiv: [math.OC]. Cornell: Cornell University, 2024. arxiv:2402.02461. С. 1-24 http://arxiv.org/abs/2402.02461.