Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 492, № 1, стр. 85-88
Ускоренный градиентный слайдинг-метод в задачах минимизации суммы функций
Д. М. Двинских 1, С. С. Омельченко 2, *, А. В. Гасников 1, **, А. И. Тюрин 3
1 Институт проблем передачи информации
им. А.А. Харкевича Российской академии наук
Москва, Россия
2 Московский физико-технический институт (национальный исследовательский университет)
Московская обл., Долгопрудный, Россия
3 Национальный исследовательский университет “Высшая школа экономики”
Москва, Россия
* E-mail: sergery.omelchenko@phystech.edu
** E-mail: gasnikov@yandex.ru
Поступила в редакцию 20.03.2020
После доработки 26.03.2020
Принята к публикации 03.04.2020
Аннотация
Предложен новый способ обоснования ускоренного градиентного слайдинга Дж. Лана, позволяющий распространить технику слайдинга на сочетание ускоренных градиентных методов с ускоренными методами редукции дисперсии. Получены новые оптимальные оценки для решения задач минимизации суммы гладких сильно выпуклых функций с гладким регуляризатором.
Многие задачи анализа данных (машинного обучения) приводят к необходимости решения задач минимизации функции вида суммы (эмпирический риск) с большим числом слагаемых, отвечающих объему выборки [1, 4, 14, 15]. В последнее десятилетие активно развиваются численные методы оптимизации функции вида суммы [1, 4, 6, 9]. В частности, были получены оптимальные методы (ускоренные методы редукции дисперсии) для такого класса задач, когда слагаемые в сумме – гладкие (сильно) выпуклые функции, см., например, [9]. Были исследованы задачи, в которых дополнительно в минимизируемую функцию вносится аддитивно, возможно, негладкий, но выпуклый/сильно выпуклый композитный член (по терминологии анализа данных вносится слагаемое, отвечающее “регуляризации”), являющийся проксимально дружественным [1, 10], т.е. задача минимизации такого члена с квадратичной добавкой – простая задача. В настоящей работе предлагается способ получения оптимальных оценок для случая, когда композитный член будет выпуклым (сильно выпуклым) гладким, но уже не будет проксимально дружественным. Не предполагается проксимальная дружественность и у слагаемых в сумме.
В разделе 1 техника ускоренного градиентного слайдинга Дж. Лана [9, section 8.2] будет объяснена с помощью популярной в последнее время конструкции каталист [1, 11]. Обнаруженный способ позволил распространить область приложений техники слайдинга на интересующий нас класс задач. В разделе 2 результаты обобщаются на различные негладкие постановки задач, в частности на обобщенные линейные модели [15] и другие модели, допускающие эффективное сглаживание [2, 13].
1. ОСНОВНЫЕ РЕЗУЛЬТАТЫ
Рассмотрим следующую задачу:
(1)
$F(x) = f(x) + g(x) = f(x) + \frac{1}{m}\sum\limits_{k = 1}^m \,{{g}_{k}}(x) \to \mathop {\min }\limits_x ,$Наложим еще одно дополнительное условие $m{{L}_{f}} \leqslant {{L}_{g}}$. Применим к рассмотренной задаче технику каталист [1, 11]. Отметим также, что если использовать технику каталист в варианте [1, 8], то применение данной техники не привносит дополнительного логарифмического множителя. Тогда вместо исходной задачи (1) потребуется $\tilde {O}(\sqrt {L{\text{/}}\mu } )$ раз решать задачу вида
(2)
$f\left( x \right) + g\left( x \right) + \frac{L}{2}{\text{||}}x - {{x}^{k}}{\text{||}}_{2}^{2} \to \mathop {\min }\limits_x ,$(3)
$\begin{gathered} \langle \nabla f({{{\tilde {x}}}^{l}}),x - {{{\tilde {x}}}^{l}}\rangle + \frac{{{{L}_{f}}}}{2}{\text{||}}x - {{{\tilde {x}}}^{l}}{\text{||}}_{2}^{2} + \\ \, + g\left( x \right) + \frac{L}{2}{\text{||}}x - {{x}^{k}}{\text{||}}_{2}^{2} \to \mathop {\min }\limits_x , \\ \end{gathered} $Таким образом, общее число вычислений $\nabla {{g}_{k}}$ будет
(4)
$\begin{gathered} \tilde {O}(m\sqrt {L{\text{/}}\mu } ) + \tilde {O}(\sqrt {L{\text{/}}\mu } ) \cdot \tilde {O}\left( {{{L}_{f}}{\text{/}}(L + \mu )} \right) \times \\ \, \times \tilde {O}(\sqrt {m{{L}_{g}}{\text{/}}\left( {{{L}_{f}} + L} \right)} ). \\ \end{gathered} $Первое слагаемое появилось из-за того, что в каталисте требуется считать $\nabla F$ на каждой итерации.
Выбирая параметр $L$ ($\mu \leqslant L \leqslant {{L}_{f}}$) так, чтобы выражение (4) было минимальным, получим (с учетом сделанных предположений $m{{L}_{f}} \leqslant {{L}_{g}}$ и $\mu \ll {{L}_{f}})$, что $L \simeq {{L}_{f}}$. Следовательно, имеет место
Теорема 1. При $m{{L}_{f}} \leqslant {{L}_{g}}$ задачу (1) можно решить с помощью описанной выше техники за $\tilde {O}(\sqrt {{{L}_{f}}{\text{/}}\mu } )$ вычислений $\nabla f$ и $\tilde {O}(\sqrt {m{{L}_{g}}{\text{/}}\mu } )$ вычисле-ний $\nabla {{g}_{k}}.$
Последняя оценка в $\tilde {O}(\sqrt m )$ раз лучше оценки, которую можно получить, используя исходный ускоренный градиентный слайдинг Дж. Лана [9]. Несложно заметить [9], что приведенные в теореме 1 оценки оптимальны с точностью до логарифмических множителей.
Заметим, что в описанном выше подходе с g(x) общего вида ускоренный метод редукции дисперсии можно заменить на покоординантный спуск или безградиентный метод [5]. Таким образом, можно получить расщепление задачи не только по гладкости или структуре слагаемых, но и по структуре оракула, доступного для каждого из слагаемых. Другой пример такого расщепления см. в [3].
Заметим также, что если в описанном выше подходе ограничиться вариантом каталиста из [1, 11], то все рассуждения можно провести в модельной (для f) общности [1].
2. ПРИЛОЖЕНИЕ
Заметим, что аналогично случаям задач из [1, 14, 15] описанная выше техника может использоваться и тогда, когда gk – не гладкие функции, но допускающие сглаживание [2, 13]. Скажем, двойственное сглаживание по Ю.Е. Нестерову [1, 2, 13]. А именно, предположим, что функции gk имеют проксимально-дружественные сопряженные функции $g_{k}^{*}$. В частности, это имеет место для обобщенной линейной модели [15], в которой ${{g}_{k}}(x): = {{g}_{k}}(\langle {{a}_{k}},x\rangle )$. Тогда, регуляризируя сопряженные функции $g_{k}^{*}$ с коэффициентом регуляризации ~ε, где ε – желаемая точность (по функции) решения исходной задачи, получим, что ε/2-решение сглаженной задачи будет ε-решением исходной. При том, что для сглаженной задачи Lg ~ ${{\varepsilon }^{{ - 1}}}$.
Заметим, что с помощью регуляризации исходной задачи [1] описанные выше результаты распространяются с сильно выпуклого случая на просто выпуклый случай. Для этого в постановку выпуклой задачи (1) вносится регуляризация $ + \mu {\text{/}}2\left\| x \right\|_{2}^{2}$, где $\mu = \varepsilon {\text{/}}{{R}^{2}}$. Здесь ε – желаемая точность решения задачи по функции, а $R = {{\left\| {{{x}_{*}}} \right\|}_{2}}$ – 2-норма решения (на практике можно брать оценку сверху [1]). Из [1] следует, что ε/2-решение так регуляризованной задачи будет ε-решением исходной задачи (1). Продемонстрируем возможные преимущества предложенного подхода в выпуклом (но не сильно выпуклом случае).
Рассматривается постановка задачи
Предполагаем, что ${\text{|}}g_{k}^{{''}}(y){\text{|}} = O(1{\text{/}}\varepsilon )$, матрица A = = [a1, ..., am]T имеет $ms$ ненулевых элементов, $\mathop {max}\limits_{k = 1,...,m} \left\| {{{a}_{k}}} \right\|_{2}^{2}$ = O(s), где $1 \ll s \leqslant n$ и C – неотрицательно определенная матрица с ${{\lambda }_{{max}}}(C) \leqslant 1{\text{/}}(\varepsilon m)$. Ускоренный градиентный метод (FGM) [1] будет требовать
Также предложенный подход требует
Для наглядности эти результаты собраны в табл. 1. Из табл. 1 можно сделать вывод, что при $s \gg 1$, ${{\lambda }_{{max}}}(C) \leqslant 1{\text{/}}(\varepsilon m) \ll s{\text{/}}\varepsilon $, предложенный в данной работе подход имеет лучшую теоретическую сложность, чем ускоренный градиентный метод, который принято было считать наилучшим для данного класса задач.
ИСТОЧНИКИ ФИНАНСИРОВАНИЯ
Таблица 1.
Алгоритм | Сложность | Ссылка |
---|---|---|
FGM | $O\left( {\frac{R}{\varepsilon }\sqrt s (ms + {{n}^{2}})} \right)$ | [1] |
Слайдинг | $\tilde {O}\left( {\frac{R}{\varepsilon }\sqrt {ms} \cdot s} \right) + \tilde {O}\left( {\sqrt {\frac{{{{\lambda }_{{max}}}(C){{R}^{2}}}}{\varepsilon }} \cdot {{n}^{2}}} \right)$ | данная статья |
Работа поддержана грантами РФФИ 18–31–20005 мол_а_вед (раздел 1) и РФФИ 19–31–90062 Аспиранты (раздел 2).
Работа первого автора (Д.М. Двинских) была выполнена при поддержке Министерства науки и высшего образования Российской Федерации (госзадание № 075-00337-20-03).
Список литературы
Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. М.: МФТИ, 2018.
Allen-Zhu Z., Hazan E. Optimal Black-Box Reductions between Optimization Objectives // Advances in Neural Information Processing Systems. 2016. P. 1614–1622.
Beznosikov A., Gorbunov E., Gasnikov A. Derivative-Free Method for Decentralized Distributed Non-Smooth Optimization // IFAC 2020. The 21st World Congress of the International Federation of Automatic Control.
Bottou L., Curtis F.E., Nocedal J. Optimization Methods for Large-Scale Machine Learning // Siam Review. 2018. V. 60. № 2. P. 223–311.
Dvurechensky P., Gasnikov A., Tiurin A. Randomized Similar Triangles Method: A Unifying Framework for Accelerated Randomized Optimization Methods (Coordinate Descent, Directional Search, Derivative-Free Method) // arXiv:1707.08486
Hazan E. Lecture Notes: Optimization for Machine Learning // arXiv:1909.03550
Ivanova A., Gasnikov A., Dvurechensky P., Dvinskikh D., Tyurin A., Vorontsova E., Pasechnyuk D. Oracle Complexity Separation in Convex Optimization // arXiv:2002.02706
Ivanova A., Grishchenko D., Gasnikov A., Shulgin E. Adaptive Catalyst for Smooth Convex Optimization // arXiv:1911.11271
Lan G. Lectures on Optimization. Methods for Machine Learning // https://pwp.gatech.edu/guanghui-lan/publications/
Lan G., Li Z., Zhou Y. A Unified Variance-Reduced Accelerated Gradient Method for Convex Optimization // Advances in Neural Information Processing Systems. 2019. P. 10462–10472.
Lin H., Mairal J., Harchaoui Z. Catalyst Acceleration for First-Order Convex Optimization: from Theory to Practice // J. Machine Learning Research. 2017. V. 18. № 1. P. 7854–7907.
Nesterov Yu. Gradient Methods for Minimizing Composite Functions // Math. Prog. 2013. V. 140. № 1. P. 125–161.
Nesterov Yu. Smooth Minimization of Non-Smooth Function // Math. Program. 2005. V. 103. № 1. P. 127–152.
Shalev-Shwartz S., Ben-David S. Understanding Machine Learning: From Theory to Algorithms. Cambridge: Cambridge University Press, 2014.
Shalev-Shwartz S., Shamir O., Srebro N., Sridharan K. Stochastic Convex Optimization // COLT. 2009.
Дополнительные материалы отсутствуют.
Инструменты
Доклады Российской академии наук. Математика, информатика, процессы управления