Методы нулевого порядка для негладких стохастических задач при шуме с тяжёлыми хвостами

В последнее время безградиентные методы оптимизации стали важным инструментом в обучении с подкреплением и энергоэффективной донастройке LLM. В стандартной постановке с равномерно ограниченной дисперсией шума был получен оптимальный ускоренный алгоритм. Однако предположение об ограниченной дисперсии является строгим и обычно не выполняется на практике. Поэтому мы ослабляем его, допуская распределение шума с тяжёлыми хвостами и тем самым расширяя класс решаемых задач. Мы предлагаем безградиентные алгоритмы с оракулом нулевого порядка при состязательном шуме с неограниченной дисперсией для негладких выпуклых и выпукло-вогнутых задач оптимизации. Мы применяем оператор клиппирования для борьбы с тяжёлыми хвостами и батчирование для эффективных вычислений за счёт параллелизации. Наш анализ даёт асимптотические оценки для таких ключевых параметров, как сложность по числу итераций, сложность по числу обращений к оракулу и максимальный уровень состязательного шума.