Доклады Российской академии наук. Математика, информатика, процессы управления, 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

Полный текст (PDF)

Аннотация

Предложен новый способ обоснования ускоренного градиентного слайдинга Дж. Лана, позволяющий распространить технику слайдинга на сочетание ускоренных градиентных методов с ускоренными методами редукции дисперсии. Получены новые оптимальные оценки для решения задач минимизации суммы гладких сильно выпуклых функций с гладким регуляризатором.

Ключевые слова: ускоренный градиентный слайдинг Дж. Лана, ускоренные методы редукции дисперсии, гладкие сильно выпуклые функции

Многие задачи анализа данных (машинного обучения) приводят к необходимости решения задач минимизации функции вида суммы (эмпирический риск) с большим числом слагаемых, отвечающих объему выборки [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 ,$
где f и gk имеют ${{L}_{f}}$ и ${{L}_{g}}$ – липшицевы градиенты в 2-норме, а функция F$\mu $-сильно выпуклая в 2‑норме, причем $\mu \ll {{L}_{f}}$. В задаче (1) введем дополнительное условие $m \leqslant {{L}_{g}}{\text{/}}\mu $. Результат Дж. Лана [9, section 8.2] заключается в том, что для решения рассмотренной задачи с заданной точностью достаточно $\tilde {O}(\sqrt {{{L}_{f}}{\text{/}}\mu } )$ вычислений $\nabla f$ и $\tilde {O}(\sqrt {{{L}_{g}}{\text{/}}\mu } )$ вычислений $\nabla g$, т.е. $\tilde {O}(m\sqrt {{{L}_{g}}{\text{/}}\mu } )$ вычислений $\nabla {{g}_{k}}$. При этом не важно с какой именно точностью $\varepsilon $. Эта точность будет входить под логарифмами в приведенные далее оценки, а для наглядности логарифмические сомножители было решено опустить. Далее оговорки о точности решения возникающих подзадач также опускаются, поскольку все это влияет только на логарифмические сомножители в итоговых оценках, которые опущены. Здесь и далее $\tilde {O}\left( \, \right) = O\left( \, \right)$ с точностью до логарифмического множителя.

Наложим еще одно дополнительное условие $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 ,$
где $L$ по построению должно удовлетворять неравенству $\mu \leqslant L \leqslant {{L}_{f}}$. Задачу (2) можно решать неускоренным композитным градиентным методом [1, 12], считая $g\left( x \right) + \tfrac{L}{2}{\text{||}}x - {{x}^{k}}{\text{||}}_{2}^{2}$ композитом. Число итераций такого метода будет совпадать с числом вычислений $\nabla f$ и равно $\tilde {O}({{L}_{f}}{\text{/}}(L + \mu ))$. Но в условиях задачи не предполагалась проксимальная дружественность функции g, поэтому возникающую на каждой итерации неускоренного композитного градиентного метода задачу вида (детали см. в препринте [7])
(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} $
в свою очередь, необходимо будет решать. Для решения задачи (3) можно использовать ускоренный композитный метод редукции дисперсии [1, 9, 10], считая $\tfrac{{{{L}_{f}}}}{2}{\text{||}}x - {{\tilde {x}}^{l}}{\text{||}}_{2}^{2} + \tfrac{L}{2}{\text{||}}x - {{x}^{k}}{\text{||}}_{2}^{2}$ композитом. Число вычислений $\nabla {{g}_{k}}$ для такого метода будет $\tilde {O}(\sqrt {m{{L}_{g}}\left( {{{L}_{f}} + L} \right)} )$. Точнее говоря, оценка имеет вид: $\tilde {O}(m + \sqrt {m{{L}_{g}}{\text{/}}\left( {{{L}_{f}} + L} \right)} )$. Однако в виду предположений $m{{L}_{f}} \leqslant {{L}_{g}}$, $L \leqslant {{L}_{f}}$:

$\tilde {O}\left( {m + \sqrt {m{{L}_{g}}{\text{/}}({{L}_{f}} + L)} } \right) = \tilde {O}\left( {\sqrt {m{{L}_{g}}{\text{/}}({{L}_{f}} + L)} } \right).$

Таким образом, общее число вычислений $\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). Продемонстрируем возможные преимущества предложенного подхода в выпуклом (но не сильно выпуклом случае).

Рассматривается постановка задачи

$F(x) = \frac{1}{2}\left\langle {x,Cx} \right\rangle + \frac{1}{m}\sum\limits_{k = 1}^m \,{{g}_{k}}\left( {\left\langle {{{a}_{k}},x} \right\rangle } \right) \to \mathop {min}\limits_{x \in {{\mathbb{R}}^{n}}} .$

Предполагаем, что ${\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] будет требовать

$O\left( {\sqrt {\frac{{\left( {s{\text{/}}\varepsilon + {{\lambda }_{{max}}}(C)} \right){{R}^{2}}}}{\varepsilon }} } \right)$
итераций для достижения точности ε по функции со сложностью одной итерации
$O(ms + {{n}^{2}})$
арифметических операций (а.о.). В настоящей работе предложен подход, который требует
$\tilde {O}\left( {\sqrt {\frac{{{{\lambda }_{{max}}}(C){{R}^{2}}}}{\varepsilon }} } \right)$
итераций ускоренного градиентного метода для квадратичной формы (первого слагаемого). При этом сложность одной такой итерации

$O({{n}^{2}})\quad {\text{а}}.{\text{о}}.$

Также предложенный подход требует

$\tilde {O}\left( {\sqrt {\frac{{\left( {ms{\text{/}}\varepsilon } \right){{R}^{2}}}}{\varepsilon }} } \right)$
итераций ускоренного метода редукции дисперсии [1, 9, 10]. При этом сложность одной такой итерации

$O(s)\quad {\text{а}}.{\text{о}}.$

Для наглядности эти результаты собраны в табл. 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).

Список литературы

  1. Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. М.: МФТИ, 2018.

  2. Allen-Zhu Z., Hazan E. Optimal Black-Box Reductions between Optimization Objectives // Advances in Neural Information Processing Systems. 2016. P. 1614–1622.

  3. 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.

  4. Bottou L., Curtis F.E., Nocedal J. Optimization Methods for Large-Scale Machine Learning // Siam Review. 2018. V. 60. № 2. P. 223–311.

  5. 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

  6. Hazan E. Lecture Notes: Optimization for Machine Learning // arXiv:1909.03550

  7. Ivanova A., Gasnikov A., Dvurechensky P., Dvinskikh D., Tyurin A., Vorontsova E., Pasechnyuk D. Oracle Complexity Separation in Convex Optimization // arXiv:2002.02706

  8. Ivanova A., Grishchenko D., Gasnikov A., Shulgin E. Adaptive Catalyst for Smooth Convex Optimization // arXiv:1911.11271

  9. Lan G. Lectures on Optimization. Methods for Machine Learning // https://pwp.gatech.edu/guanghui-lan/publications/

  10. 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.

  11. 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.

  12. Nesterov Yu. Gradient Methods for Minimizing Composite Functions // Math. Prog. 2013. V. 140. № 1. P. 125–161.

  13. Nesterov Yu. Smooth Minimization of Non-Smooth Function // Math. Program. 2005. V. 103. № 1. P. 127–152.

  14. Shalev-Shwartz S., Ben-David S. Understanding Machine Learning: From Theory to Algorithms. Cambridge: Cambridge University Press, 2014.

  15. Shalev-Shwartz S., Shamir O., Srebro N., Sridharan K. Stochastic Convex Optimization // COLT. 2009.

Дополнительные материалы отсутствуют.

Инструменты

Доклады Российской академии наук. Математика, информатика, процессы управления