Сила обобщённой гладкости в стохастической выпуклой оптимизации: алгоритмы первого и нулевого порядка

Эта работа посвящена изучению задач стохастической оптимизации в предположении обобщённой гладкости. Рассматривая несмещённый градиентный оракул в стохастическом градиентном спуске, мы предлагаем стратегии, позволяющие достичь оценок слагаемых, описывающих линейную скорость. В частности, в случае $L_0 = 0$ мы получаем в выпуклой постановке сложность по числу итераций: $N = \mathcal{O}\left(L_1R \log\frac{1}{\varepsilon} + \frac{L_1 c R^2}{\varepsilon}\right)$ для Clipped Stochastic Gradient Descent и $N = \mathcal{O}\left(L_1R \log\frac{1}{\varepsilon}\right)$ для Normalized Stochastic Gradient Descent. Кроме того, мы обобщаем результаты о сходимости на случай смещённого градиентного оракула и показываем, что сила $(L_0,L_1)$-гладкости распространяется на алгоритмы нулевого порядка. Наконец, мы демонстрируем возможность линейной сходимости в выпуклой постановке с помощью численных экспериментов, что вызвало некоторый интерес в сообществе машинного обучения.