Стохастическое уменьшение дисперсии

(Стохастическое) уменьшение дисперсии — это алгоритмический подход к минимизации функций, которые можно разложить на конечные суммы. Используя структуру конечной суммы, методы уменьшения дисперсии способны достичь скорости сходимости, которую невозможно достичь с помощью методов, которые рассматривают цель как бесконечную сумму, как в классической настройке стохастической аппроксимации .

Подходы к уменьшению дисперсии широко используются для обучения моделей машинного обучения, таких как логистическая регрессия и машины опорных векторов. ^[1] поскольку эти задачи имеют структуру конечной суммы и единообразную обусловленность , что делает их идеальными кандидатами для уменьшения дисперсии.

Цели конечной суммы

Функция $f$ Считается, что структура конечной суммы может быть разложена на суммирование или среднее значение:

f(x)={\frac {1}{n}}\sum _{i=1}^{n}f_{i}(x),

где значение функции и производная каждой $f_{i}$ можно запросить самостоятельно. Хотя методы уменьшения дисперсии могут применяться для любых положительных $n$ и любой $f_{i}$ структуры, их благоприятные теоретические и практические свойства возникают тогда, когда $n$ велико по сравнению с числом обусловленности каждого $f_{i}$ , и когда $f_{i}$ имеют схожие (но не обязательно идентичные) липшицеву гладкость и выпуклости сильные константы .

Структуру конечной суммы следует противопоставить стохастической аппроксимации, которая имеет дело с функциями вида ${\textstyle f(\theta )=\operatorname {E} _{\xi }[F(\theta ,\xi )]}$ что является ожидаемым значением функции, зависящей от случайной величины ${\textstyle \xi }$ . Любую задачу конечной суммы можно оптимизировать с помощью алгоритма стохастической аппроксимации, используя $F(\cdot ,\xi )=f_{\xi }$ .

Быстрая конвергенция

Методы уменьшения стохастической дисперсии без ускорения позволяют найти минимумы $f$ в пределах точности $\epsilon >$ , то есть $f(x)-f(x_{*})\leq \epsilon$ в несколько этапов заказа:

O\left(\left({\frac {L}{\mu }}+n\right)\log \left({\frac {1}{\epsilon }}\right)\right).

Количество шагов зависит только логарифмически от требуемого уровня точности, в отличие от структуры стохастической аппроксимации, где количество шагов $O{\bigl (}L/(\mu \epsilon ){\bigr )}$ требуемая точность растет пропорционально требуемой точности.Методы стохастического уменьшения дисперсии сходятся почти так же быстро, как метод градиентного спуска. $O{\bigl (}(L/\mu )\log(1/\epsilon ){\bigr )}$ скорость, несмотря на использование только стохастического градиента, при $1/n$ более низкая стоимость, чем градиентный спуск.

Ускоренные методы в рамках системы уменьшения стохастической дисперсии достигают еще более высоких скоростей сходимости, требуя всего лишь

O\left(\left({\sqrt {\frac {nL}{\mu }}}+n\right)\log \left({\frac {1}{\epsilon }}\right)\right)

шаги, чтобы достичь $\epsilon$ точность, потенциально ${\sqrt {n}}$ быстрее, чем неускоренные методы. Нижние границы сложности. ^[2] для класса конечных сумм установите, что эта скорость является максимально возможной для гладких сильно выпуклых задач.

Подходы

Подходы к уменьшению дисперсии делятся на 3 основные категории: методы табличного усреднения, методы полного градиентного снимка и двойные методы. Каждая категория содержит методы, предназначенные для решения выпуклых, негладких и невыпуклых задач, каждый из которых отличается настройками гиперпараметров и другими алгоритмическими деталями.

САГА

В методе САГА ^[3] прототипный подход к усреднению таблицы, таблица размеров $n$ поддерживается и содержит последний градиент, зафиксированный для каждого $f_{i}$ термин, который мы обозначаем $g_{i}$ . На каждом этапе индекс $i$ производится выборка, и новый градиент $\nabla f_{i}(x_{k})$ вычисляется. Итерация $x_{k}$ обновляется с помощью:

x_{k+1}=x_{k}-\gamma \left[\nabla f_{i}(x_{k})-g_{i}+{\frac {1}{n}}\sum _{i=1}^{n}g_{i}\right],

и после этого запись в таблицу $i$ обновляется с помощью $g_{i}=\nabla f_{i}(x_{k})$ .

SAGA является одним из самых популярных методов уменьшения дисперсии благодаря своей простоте, легко адаптируемой теории и отличной производительности. Это преемник метода SAG. ^[4] улучшение его гибкости и производительности.

С.В.Р.Г.

Метод градиента с уменьшенной стохастической дисперсией (SVRG), ^[5] прототипный метод моментального снимка использует аналогичное обновление, за исключением того, что вместо использования среднего значения таблицы он использует полный градиент, который переоценивается в точке моментального снимка ${\tilde {x}}$ через регулярные промежутки времени $m\geq n$ итерации. Обновление становится:

x_{k+1}=x_{k}-\gamma [\nabla f_{i}(x_{k})-\nabla f_{i}({\tilde {x}})+\nabla f({\tilde {x}})],

Этот подход требует двух оценок стохастического градиента за шаг, одна для вычисления $\nabla f_{i}(x_{k})$ и один для вычисления $\nabla f_{i}({\tilde {x}})],$ тогда как в таблице усреднения подходов нужен только один.

Несмотря на высокие вычислительные затраты, SVRG популярен, поскольку его простая теория сходимости легко адаптируется к новым настройкам оптимизации. Он также имеет меньшие требования к объему памяти, чем подходы к табличному усреднению, что делает его применимым во многих ситуациях, где табличные методы не могут быть использованы.

SDCA

Использование двойного представления цели приводит к другому подходу уменьшения дисперсии, который особенно подходит для конечных сумм, где каждый член имеет структуру, которая делает вычисление выпуклого сопряжения $f_{i}^{*},$ или его проксимальный оператор послушен. Стандартный метод SDCA ^[6] рассматривает конечные суммы, которые имеют дополнительную структуру по сравнению с общей настройкой конечной суммы:

f(x)={\frac {1}{n}}\sum _{i=1}^{n}f_{i}(x^{T}v_{i})+{\frac {\lambda }{2}}\|x\|^{2},

где каждый $f_{i}$ является одномерным, и каждый $v_{i}$ это точка данных, связанная с $f_{i}$ .SDCA решает двойную проблему:

\max _{\alpha \in \mathbb {R} ^{n}}-{\frac {1}{n}}\sum _{i=1}^{n}f_{i}^{*}(-\alpha _{i})-{\frac {\lambda }{2}}\left\|{\frac {1}{\lambda n}}\sum _{i=1}^{n}\alpha _{i}v_{i}\right\|^{2},

с помощью процедуры стохастического подъема координат , где на каждом шаге цель оптимизируется по случайно выбранной координате $\alpha _{i}$ , оставив все остальные координаты прежними. Примерное простое решение $x$ можно восстановить из $\alpha$ ценности:

x={\frac {1}{\lambda n}}\sum _{i=1}^{n}\alpha _{i}v_{i}

.

Этот метод обеспечивает аналогичные теоретические скорости сходимости с другими методами уменьшения стохастической дисперсии, избегая при этом необходимости указывать параметр размера шага. На практике это происходит быстро, когда $\lambda$ является большим, но значительно медленнее, чем другие подходы, когда $\lambda$ мал.

Ускоренные подходы

Ускоренные методы уменьшения дисперсии основаны на описанных выше стандартных методах. Самые ранние подходы используют проксимальные операторы для ускорения сходимости, приблизительно или точно. Также были разработаны подходы прямого ускорения. ^[7]

Катализатор ускорения

Структура катализатора ^[8] использует любой из стандартных методов, описанных выше, в качестве внутреннего оптимизатора для приблизительного решения проксимального оператора :

x_{k}\approx {\text{argmin}}_{x}\left\{f(x)+{\frac {\kappa }{2}}\|x-y_{k-1}\|^{2}\right\}

после чего он использует шаг экстраполяции для определения следующего $y$ :

y_{k}=x_{k}+\beta _{k}(x_{k}-x_{k-1})

Гибкость и простота каталитического метода делают его популярным базовым подходом. Он не обеспечивает оптимальную скорость сходимости среди ускоренных методов, но потенциально медленнее до логарифмического коэффициента гиперпараметров.

Точка-САГА

Проксимальные операции также могут применяться непосредственно к $f_{i}$ условия для получения ускоренного метода. Метод Point-SAGA ^[9] заменяет операции градиента в SAGA проксимальными операторными вычислениями, что приводит к простому методу прямого ускорения:

x_{k+1}={\text{prox}}_{j}^{\gamma }\left(z_{k}\triangleq x_{k}+\gamma \left[g_{j}-{\frac {1}{n}}\sum _{i=1}^{n}g_{i}\right]\right),

с обновлением таблицы $g_{j}={\frac {1}{\gamma }}(z_{k}-x_{k+1})$ выполняется после каждого шага. Здесь ${\text{prox}}_{j}^{\gamma }$ определяется как проксимальный оператор для $j$ й срок:

{\text{prox}}_{j}^{\gamma }(y)={\text{argmin}}_{x}\left\{f_{j}(x)+{\frac {1}{2\gamma }}\|x-y\|^{2}\right\}.

В отличие от других известных ускоренных методов, Point-SAGA требует только одной итерационной последовательности. $x$ поддерживаться между этапами и имеет то преимущество, что имеет только один настраиваемый параметр $\gamma$ . Он обеспечивает оптимальную ускоренную скорость сходимости для сильно выпуклой минимизации конечной суммы без дополнительных логарифмических коэффициентов.

См. также

Ссылки

^ "sklearn.linear_model.LogisticRegrade" . Scikit Узнайте . Проверено 26 февраля 2022 г.
^ Лан, Гуанхуэй; Чжоу, И (2018). «Оптимальный метод рандомизированного постепенного градиента». Математическое программирование: серии A и B. 171 (1–2): 167–215. arXiv : 1507.02000 . дои : 10.1007/s10107-017-1173-0 . S2CID 9143586 .
^ Дефацио, Аарон; Бах, Фрэнсис; Лакост-Жюльен, Симон (2014). «SAGA: метод быстрого постепенного градиента с поддержкой несильно выпуклых составных целей». Нейронные системы обработки информации . arXiv : 1407.0202 .
^ Шмидт, Марк; Ле Ру, Николя; Бах, Франциск (2017). «Минимизация конечных сумм со стохастическим средним градиентом». Математическое программирование . 162 . arXiv : 1309.2388 .
^ Джонсон, Ри; Чжан, Тонг (2013). «Ускорение стохастического градиентного спуска с использованием прогнозируемого уменьшения дисперсии» (PDF) . Нейронные системы обработки информации .
^ Шалев-Шварц, Шай; Чжан, Тонг (2013). «Стохастические методы восхождения с двумя координатами для минимизации регуляризованных потерь» (PDF) . Журнал исследований машинного обучения . 14 .
^ Лан, Гуанхуэй; Чжоу, И (2018). «Оптимальный метод рандомизированного постепенного градиента». Математическое программирование: серии A и B. 171 (1–2): 167–215. arXiv : 1507.02000 . дои : 10.1007/s10107-017-1173-0 . S2CID 9143586 .
^ Линь, Хунчжоу; Майрал, Жюльен; Харшауи, Заид (2016). «Катализаторное ускорение для выпуклой оптимизации первого порядка: от теории к практике». Журнал исследований машинного обучения . 18 . arXiv : 1712.05654 .
^ Дефацио, Аарон (2016). «Простой практический ускоренный метод определения конечных сумм». Нейронные системы обработки информации . arXiv : 1602.02442 .

[1] "sklearn.linear_model.LogisticRegrade" . Scikit Узнайте . Проверено 26 февраля 2022 г.

[2] Лан, Гуанхуэй; Чжоу, И (2018). «Оптимальный метод рандомизированного постепенного градиента». Математическое программирование: серии A и B. 171 (1–2): 167–215. arXiv : 1507.02000 . дои : 10.1007/s10107-017-1173-0 . S2CID 9143586 .

[3] Дефацио, Аарон; Бах, Фрэнсис; Лакост-Жюльен, Симон (2014). «SAGA: метод быстрого постепенного градиента с поддержкой несильно выпуклых составных целей». Нейронные системы обработки информации . arXiv : 1407.0202 .

[4] Шмидт, Марк; Ле Ру, Николя; Бах, Франциск (2017). «Минимизация конечных сумм со стохастическим средним градиентом». Математическое программирование . 162 . arXiv : 1309.2388 .

[5] Джонсон, Ри; Чжан, Тонг (2013). «Ускорение стохастического градиентного спуска с использованием прогнозируемого уменьшения дисперсии» (PDF) . Нейронные системы обработки информации .

[6] Шалев-Шварц, Шай; Чжан, Тонг (2013). «Стохастические методы восхождения с двумя координатами для минимизации регуляризованных потерь» (PDF) . Журнал исследований машинного обучения . 14 .

[7] Лан, Гуанхуэй; Чжоу, И (2018). «Оптимальный метод рандомизированного постепенного градиента». Математическое программирование: серии A и B. 171 (1–2): 167–215. arXiv : 1507.02000 . дои : 10.1007/s10107-017-1173-0 . S2CID 9143586 .

[8] Линь, Хунчжоу; Майрал, Жюльен; Харшауи, Заид (2016). «Катализаторное ускорение для выпуклой оптимизации первого порядка: от теории к практике». Журнал исследований машинного обучения . 18 . arXiv : 1712.05654 .

[9] Дефацио, Аарон (2016). «Простой практический ускоренный метод определения конечных сумм». Нейронные системы обработки информации . arXiv : 1602.02442 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]