Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Краткое содержание

Стохастическая оптимизация является жизненно важным компонентом машинного обучения, и в ее основе лежит алгоритм стохастического градиентного спуска (SGD), метод, который широко используется с момента его первого предложения более 60 лет назад. За последние восемь лет мы стали свидетелями новой интересной разработки: методов уменьшения дисперсии для методов стохастической оптимизации. Эти методы уменьшения дисперсии (методы VR) хорошо работают в сценариях, которые допускают несколько итераций обучающих данных, демонстрируя более быструю сходимость, чем SGD, как в теории, так и на практике. Такое увеличение скорости подчеркивает растущий интерес к методам виртуальной реальности и быстрое накопление результатов исследований в этой области. В этой статье рассматриваются ключевые принципы и основные достижения в методах VR для оптимизации ограниченных наборов данных с целью информирования читателей, не являющихся экспертами. Мы фокусируемся в первую очередь на средах выпуклой оптимизации и предоставляем справочную информацию для читателей, интересующихся расширениями минимизации невыпуклых функций.

Ключевые слова Оптимизация машинного обучения;

1. Введение

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

$${Икс}^{\ast }\in \mathrm{арг}\underset{Икс\in {\mathbb{р}}^{г}}{\mathrm{мин}}\frac{1}{н}\sum _{я=1}^{н}({а}_{я}^{Т}Икс-{б}_{я}{)}^2$$

В этой модели мы имеем $г$ параметры, которые представлены векторами$Икс\in {\mathbb{р}}^{г}$ данный.А пока у нас есть под рукой$н$ точки данных, включая векторы признаков${а}_{я}\in {\mathbb{р}}^{г}$ и целевое значение${б}_{я}\in \mathbb{р}$ .Процесс адаптации модели заключается в корректировке этих параметров таким образом, чтобы прогнозируемый результат модели${а}_{я}^{Т}Икс$ в среднем как можно ближе к целевому значению${б}_{я}$。

В более широком смысле мы могли бы использовать функцию потерь ${ф}_{я}(Икс)$ Чтобы измерить предсказания модели и$я$ Насколько близки точки данных:

$${Икс}^{\ast }\in \mathrm{арг}\underset{Икс\in {\mathbb{р}}^{г}}{\mathrm{мин}}ф(Икс):=\frac{1}{н}\sum _{я=1}^{н}{ф}_{я}(Икс)$$

функция потерь ${ф}_{я}(Икс)$ Если оно больше, это означает, что прогнозы модели сильно отклоняются от данных;${ф}_{я}(Икс)$ Модель, равная нулю, идеально соответствует точкам данных.функция$ф(Икс)$ Отражает средние потери модели по всему набору данных.

Проблемы, подобные форме (2), приведенной выше, применимы не только к линейным задачам наименьших квадратов, но и ко многим другим моделям, изучаемым в машинном обучении. Например, в модели логистической регрессии мы решаем:

$${Икс}^{\ast }\in \mathrm{арг}\underset{Икс\in {\mathbb{р}}^{г}}{\mathrm{мин}}\frac{1}{н}\sum _{я=1}^{н}\mathrm{вотг}(1+{е}^{-{б}_{я}{а}_{я}^{Т}Икс})+\frac{\lambda }{2}\Vert Икс{\Vert }_2^2$$

Здесь мы имеем дело с bi ∈ { − 1 , + 1 } b_i в {-1, +1}бя​∈{−1,+1} Для задачи бинарной классификации прогноз основан на${а}_{я}^{Т}Икс$ символы.В формулу также введен регуляризационный член$\frac{\lambda }{2}\Vert Икс{\Vert }_2^2$ чтобы избежать переобучения данных, где$\Vert Икс{\Vert }_2^2$ выражать$Икс$ Квадрат евклидовой нормы .

В большинстве моделей обучения с учителем процесс обучения может быть выражен в виде (2), включая регуляризованный метод наименьших квадратов L1, машину опорных векторов (SVM), анализ главных компонентов, условные случайные поля и глубокие нейронные сети и т. д.

Ключевой проблемой в современных примерах проблем является количество точек данных. $н$ Наверное, очень большой. Мы часто имеем дело с наборами данных, размер которых выходит далеко за пределы терабайта и которые могут поступать из самых разных источников, таких как Интернет, спутники, удаленные датчики, финансовые рынки и научные эксперименты. Для работы с такими большими наборами данных обычно используют алгоритм стохастического градиентного спуска (SGD), который использует лишь небольшое количество случайно выбранных точек данных на каждой итерации. Кроме того, в последнее время резко возрос интерес к методам стохастического градиента уменьшения дисперсии (VR), которые имеют более высокую скорость сходимости, чем традиционные методы стохастического градиента.

Рисунок 1. В задаче логистической регрессии, основанной на грибовидном наборе данных [7], градиентном спуске (GD), ускоренном градиентном спуске (AGD, ускоренном GD в [50]), стохастическом градиентном спуске (SGD) и методе ADAM [30] по сравнению с методами уменьшения дисперсии (VR) SAG и SVRG, где n = 8124, d = 112.

1.1. Градиентный и стохастический методы градиентного спуска.

Градиентный спуск (GD) — это классический алгоритм, используемый для решения вышеуказанной проблемы (2), и его формула итеративного обновления выглядит следующим образом:
$${Икс}_{к+1}={Икс}_{к}-\gamma \frac{1}{н}\sum _{я=1}^{н}\nabla {ф}_{я}({Икс}_{к})$$

здесь,$\gamma$ — фиксированное значение шага, большее нуля.Во время каждой итерации алгоритма GD каждая точка данных должна быть$я$ Рассчитать градиент$\nabla {ф}_{я}({Икс}_{к})$, а это значит, что GD требует всех $н$ выполнить полный обход точек данных.Когда размер набора данных$н$ Когда он становится очень большим, стоимость каждой итерации алгоритма GD становится очень высокой, что ограничивает его применение.

В качестве альтернативы можно рассмотреть метод стохастического градиентного спуска (SGD), который впервые был предложен Роббинсом и Монро, и его формула итеративного обновления выглядит следующим образом:
$${Икс}_{к+1}={Икс}_{к}-\gamma \nabla {ф}_{{я}_{к}}({Икс}_{к})$$

Алгоритм SGD работает, используя только градиент одной случайно выбранной точки данных на каждой итерации. $\nabla {ф}_{{я}_{к}}({Икс}_{к})$ снизить стоимость каждой итерации. На рисунке 1 мы видим, что SGD достигает более значительного прогресса, чем GD (включая ускоренные методы GD) на ранних этапах процесса оптимизации.На графике показан ход оптимизации с точки зрения эпох, которые определяются как расчет всех$н$ Количество градиентов для обучающих выборок. Алгоритм GD выполняет одну итерацию в каждом раунде, а алгоритм SGD выполняет одну итерацию в каждом раунде.$н$ итерации.Мы используем раунды в качестве основы для сравнения SGD и GD, поскольку по предположению$н$ В очень больших случаях основная стоимость обоих методов сосредоточена в градиенте.$\nabla {ф}_{я}({Икс}_{к})$ расчет.

1.2. Проблема дисперсии

Рассмотрим случайную индексацию ${я}_{к}$ из коллекции { 1 , … , n } {1, лточки, n}{1,…,н} В случае равномерного случайного отбора это означает, что для всех$я$,выбирать ${я}_{к}=я$ Вероятность$п[{я}_{к}=я]$ равный$\frac{1}{н}$ . в этом случае,$\nabla {ф}_{{я}_{к}}({Икс}_{к})$ как$\nabla ф({Икс}_{к})$ Оценка является несмещенной, поскольку по определению ожидания мы имеем:
$$Э[\nabla {ф}_{{я}_{к}}({Икс}_{к})|{Икс}_{к}]=\frac{1}{н}\sum _{я=1}^{н}\nabla {ф}_{я}({Икс}_{к})=\nabla ф({Икс}_{к})(6)$$

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

Однако наличия несмещенной оценки градиента недостаточно для обеспечения сходимости итераций SGD. Чтобы проиллюстрировать этот момент, на рисунке 2 (слева) показана итеративная траектория SGD при применении функции логистической регрессии с использованием постоянного размера шага к набору данных из четырех категорий, предоставленному LIBSVM [7].Концентрические эллипсы на рисунке представляют контуры функции, то есть значение функции$ф(Икс)=с$ соответствующая точка$Икс$ собирать,$с$ — это определенная константа в наборе действительных чисел.разные постоянные значения$с$ Соответствует различным эллипсам.

Итерационная траектория SGD не сходится к оптимальному решению (обозначен на рисунке зеленой звездочкой), а формирует облако точек вокруг оптимального решения. Напротив, на рисунке 2 мы показываем итерационную траекторию метода уменьшения дисперсии (VR), стохастического среднего градиента (SAG), с использованием того же постоянного размера шага, который мы представим позже. Причина, по которой SGD не сходится в этом примере, заключается в том, что сам стохастический градиент не сходится к нулю, и, следовательно, метод SGD с постоянным шагом (5) никогда не останавливается.Это резко контрастирует с методами градиентного спуска (GD), которые, естественно, прекращаются при${Икс}_{к}$ Подходы${Икс}^{\ast }$,градиент $\nabla ф({Икс}_{к})$ будет стремиться к нулю.

Рисунок 2. Графики набора уровней для двумерной логистической регрессии с использованием итеративных методов SGD (слева) и SAG (справа) с фиксированным шагом. Зеленая звездочка обозначает xразвязать.

1.3. Классический метод уменьшения дисперсии.

обработка из-за $\nabla {ф}_{я}({Икс}_{к})$ Существует несколько классических методов решения проблем несходимости, вызванных дисперсией значений.Например, Роббинс и Монро [64] используют серию убывающих ступеней.${\gamma }_{к}$ решить проблему дисперсии, гарантируя, что произведение${\gamma }_{к}\nabla {ф}_{{я}_{к}}({Икс}_{к})$ может сходиться к нулю. Однако корректировка этой последовательности уменьшающихся шагов во избежание слишком ранней или слишком поздней остановки алгоритма является сложной проблемой.

Другой классический метод уменьшения дисперсии — использование нескольких $\nabla {ф}_{я}({Икс}_{к})$ среднее значение для получения полного градиента$\nabla ф(Икс)$ более точная оценка. Этот подход называется мини-пакетом и особенно полезен, когда несколько градиентов можно оценивать параллельно. Это приводит к повторению формы:
$${Икс}_{к+1}={Икс}_{к}-\gamma \frac{1}{|{Б}_{к}|}\sum _{я\in {Б}_{к}}\nabla {ф}_{я}({Икс}_{к})(7)$$
в${Б}_{к}$ представляет собой случайный набор индексов,$|{Б}_{к}|$ выражать${Б}_{к}$ размер.если${Б}_{к}$ При равномерной выборке с заменой дисперсия этой оценки градиента связана с «размером партии».$|{Б}_{к}|$ обратно пропорциональна, поэтому дисперсию можно уменьшить, увеличив размер партии.

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

Другая распространенная стратегия уменьшения дисперсии и улучшения эмпирических показателей SGD — добавление «импульса», дополнительного термина, основанного на направлении, использованном на прошлых этапах. В частности, форма SGD с импульсом выглядит следующим образом:
$${Икс}_{к+1}={Икс}_{к}-\gamma {м}_{к}(9)$$
где параметр импульса$\beta$ Расположен в диапазоне (0, 1).Если начальный импульс${м}_0=0$, и разложим в (8) ${м}_{к}$ Для обновлений мы получаем${м}_{к}$ представляет собой средневзвешенное значение предыдущих градиентов:
$${м}_{к}=\sum _{т=0}^{к}{\beta }^{к-т}\nabla {ф}_{{я}_{т}}({Икс}_{т})(10)$$
поэтому,${м}_{к}$ представляет собой взвешенную сумму стохастических градиентов.потому что${\sum }_{т=0}^{к}{\beta }^{к-т}=\frac{1-{\beta }^{к+1}}{1-\beta }$, мы можем конвертировать $\frac{1-\beta }{1-{\beta }^{к}}{м}_{к}$ Рассматривается как средневзвешенное значение стохастических градиентов.Если мы сравним это с выражением для полного градиента$\nabla ф({Икс}_{к})=\frac{1}{н}{\sum }_{я=1}^{н}\nabla {ф}_{я}({Икс}_{к})$ Для сравнения мы можем$\frac{1-\beta }{1-{\beta }^{к}}{м}_{к}$(а также ${м}_{к}$ ) интерпретируется как оценка полного градиента. Хотя эта взвешенная сумма уменьшает дисперсию, она также поднимает ключевые проблемы.Поскольку взвешенная сумма (10) придает больший вес недавно выбранным градиентам, она не будет сходиться к полному градиенту.$\nabla ф({Икс}_{к})$ , последнее представляет собой простое среднее. Первый метод уменьшения дисперсии, который мы увидим в разделе II-A, решает эту проблему, используя простое среднее вместо любого взвешенного среднего.

1.4. Современные методы уменьшения дисперсии.

В отличие от классических методов, они напрямую используют один или несколько $\nabla {ф}_{я}({Икс}_{к})$ как$\nabla ф({Икс}_{к})$ В качестве приближения современные методы уменьшения дисперсии (VR) используют другую стратегию.Эти методы используют$\nabla {ф}_{я}({Икс}_{к})$ обновить оценку градиента${г}_{к}$, цель которого – сделать ${г}_{к}$ подход$\nabla ф({Икс}_{к})$ .В частности, мы надеемся${г}_{к}$ способен удовлетворить${г}_{к}\approx \nabla ф({Икс}_{к})$ . На основе таких оценок градиента мы затем выполняем приблизительный шаг градиента в форме:
$${Икс}_{к+1}={Икс}_{к}-\gamma {г}_{к}(11)$$
здесь$\gamma >0$ — параметр размера шага.

Чтобы гарантировать использование постоянного размера шага $\gamma$ Когда итерация (11) может сойтись, нам нужно убедиться, что оценка градиента${г}_{к}$ Дисперсия стремится к нулю. Математически это можно выразить так:
$$Э\left[\Vert {г}_{к}-\nabla ф({Икс}_{к}){\Vert }^2\right]\to 0\text{как}к\to \infty (12)$$
ожидания здесь$Э$ основан на алгоритме с точностью до$к$ Все случайные величины рассчитываются для итераций. Свойство (12) обеспечивает возможность остановки метода VR при достижении оптимального решения. Мы считаем это свойство отличительной чертой подхода виртуальной реальности и поэтому называем его свойством виртуальной реальности. Стоит отметить, что выражение «приведенная» дисперсия может ввести в заблуждение, поскольку на самом деле дисперсия стремится к нулю. Свойство (12) является ключевым фактором, позволяющим методам VR достигать более быстрой сходимости в теории (при соответствующих предположениях) и на практике (как показано на рисунке 1).

1.5. Первый пример метода уменьшения дисперсии: SGD².

Простой метод улучшения может заставить рекурсивную формулу SGD (5) достичь сходимости без уменьшения размера шага, то есть перевода каждого градиента. Конкретный метод заключается в вычитании. $\nabla {ф}_{я}({Икс}^{\ast })$, этот метод определяется следующим образом:
$${Икс}_{к+1}={Икс}_{к}-\gamma (\nabla {ф}_{{я}_{к}}({Икс}_{к})-\nabla {ф}_{{я}_{к}}({Икс}^{\ast }))(13)$$
Этот метод называется SGD² [22].Хотя мы обычно не можем знать наверняка каждый$\nabla {ф}_{я}({Икс}^{\ast })$ , но SGD², как пример, может хорошо проиллюстрировать основные характеристики метода уменьшения дисперсии.Более того, многие методы уменьшения дисперсии можно рассматривать как приблизительную форму метода SGD². Эти методы не полагаются на известные данные;$\nabla {ф}_{я}({Икс}^{\ast })$, но вместо этого используйте метод, который может аппроксимировать $\nabla {ф}_{я}({Икс}^{\ast })$ расчетная стоимость.

Стоит отметить, что SGD² использует несмещенную оценку полного градиента.потому что$\nabla ф({Икс}^{\ast })=0$,Ф:
$$Э[\nabla {ф}_{{я}_{к}}({Икс}_{к})-\nabla {ф}_{{я}_{к}}({Икс}^{\ast })]=\nabla ф({Икс}_{к})-\nabla ф({Икс}^{\ast })=\nabla ф({Икс}_{к})$$
Кроме того, когда SGD² достигнет оптимального решения, он, естественно, остановится, поскольку для любого$я$,иметь:
$$(\nabla {ф}_{я}(Икс)-\nabla {ф}_{я}({Икс}^{\ast })){|}_{Икс={Икс}^{\ast }}=0$$

При дальнейшем наблюдении с ${Икс}_{к}$ около${Икс}^{\ast }$(для последовательных $\nabla {ф}_{я}$), SGD² удовлетворяет свойству уменьшения дисперсии (12), потому что:
$$\begin{gathered} Э\left[\Vert {г}_{к}-\nabla ф({Икс}_{к}){\Vert }^2\right]= \\ Э\left[\Vert \nabla {ф}_{{я}_{к}}({Икс}_{к})-\nabla {ф}_{{я}_{к}}({Икс}^{\ast })-\nabla ф({Икс}_{к}){\Vert }^2\right]\le Э\left[\Vert \nabla {ф}_{{я}_{к}}({Икс}_{к})-\nabla {ф}_{{я}_{к}}({Икс}^{\ast }){\Vert }^2\right] \end{gathered}$$
Здесь воспользуемся леммой 2, пусть$Икс=\nabla {ф}_{{я}_{к}}({Икс}_{к})-\nabla {ф}_{{я}_{к}}({Икс}^{\ast })$, и воспользовался $Э[\nabla {ф}_{{я}_{к}}({Икс}_{к})-\nabla {ф}_{{я}_{к}}({Икс}^{\ast })]=\nabla ф({Икс}_{к})$ природа. Это свойство указывает на то, что SGD² имеет более высокую скорость сходимости, чем традиционные методы SGD, которые мы подробно описали в Приложении B.

1.6. Метод быстрой сходимости дисперсии.

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

Предположение 1 (непрерывность Липшица)

Предположим, что функция $ф$является дифференцируемым и $Л$- гладко, для всех $Икс$ и$у$ и кто-то$0<Л<\infty$,Следующие условия:
$$\Vert \nabla ф(Икс)-\nabla ф(у)\Vert \le Л\Vert Икс-у\Vert (14)$$
Это означает, что каждый$фя:{\mathbb{р}}^{г}\to \mathbb{р}$ является дифференцируемым,${Л}_{я}$- гладкая, определяем ${Л}_{\text{Макс}}$ для макс ⁡ { L 1 , . . . , L n } макс{L_1, . . . , Л_н}Макс{Л1​,...,Лн​}。

Хотя обычно это предположение считается слабым, в последующих главах мы обсудим методы виртуальной реальности, подходящие для решения негладких задач. Для дважды дифференцируемой одномерной функции$Л$- Гладкость можно интуитивно понимать как: это эквивалентно предположению, что вторая производная равна $Л$ верхний предел, то есть$|{ф}^{\prime \prime }(Икс)|\le Л$ для всех$Икс\in {\mathbb{р}}^{г}$ .Для дважды дифференцируемых функций многих переменных это эквивалентно предположению матрицы Гессе${\nabla }^2ф(Икс)$ Единственное значение$Л$ верхний предел.

Предположение 2 (сильная выпуклость)

Вторая гипотеза, которую мы рассматриваем, заключается в том, что функция (f) $\mu$-сильно выпуклый, что означает, что для определенного $\mu >0$, функция $Икс\mapsto ф(Икс)-\frac{\mu }{2}\Vert Икс{\Vert }^2$ Он выпуклый.Более того, для каждого$я=1,...,н$，$фя:{\mathbb{р}}^{г}\to \mathbb{р}$ Он выпуклый.

Это сильное предположение.В задаче наименьших квадратов каждая (fi$ выпукла, но общая функция (f) находится только в матрице плана$А:=[{а}_1,...,{а}_{н}]$ Он сильно выпуклый только в том случае, если имеет совершенный ранг строки. Задача регуляризованной логистической регрессии L2 удовлетворяет этому предположению из-за существования члена регуляризации, где$\mu \ge \lambda$。

Важным классом задач, удовлетворяющих этим предположениям, являются задачи оптимизации вида:
$${Икс}^{\ast }\in \mathrm{арг}\underset{Икс\in {\mathbb{р}}^{г}}{\mathrm{мин}}ф(Икс)=\frac{1}{н}\sum _{я=1}^{н}{\ell }_{я}({а}_{я}^{Т}Икс)+\frac{\lambda }{2}\Vert Икс{\Vert }^2(15)$$
где каждая функция «потери»${\ell }_{я}:\mathbb{р}\to \mathbb{р}$ дважды дифференцируема, а ее вторая производная${\ell }_{я}^{\prime \prime }$ ограничено 0 и некоторой верхней границей$М$ между. Сюда входят различные функции потерь с регуляризацией L2 в машинном обучении, такие как метод наименьших квадратов, логистическая регрессия, пробит-регрессия, робастная регрессия Хубера и т. д.В этом случае для всех$я$,У нас есть ${Л}_{я}\le М\Vert {а}_{я}{\Vert }^2+\lambda$ и$\mu \ge \lambda$。

В этих предположениях скорость сходимости метода градиентного спуска (ГР) определяется числом обусловленности $\kappa :=Л/\mu$ Решать. Число обусловленности всегда больше или равно 1, а когда оно значительно больше 1, контуры функции становятся очень эллиптическими, что приводит к колебаниям итераций метода GD.Напротив, когда$\kappa$ Когда оно близко к 1, метод GD сходится быстрее.

При предположениях 1 и 2 метод VR сходится с линейной скоростью.Мы говорим, что значение функции случайного метода ({f(x_k)}) определяется выражением$0<\rho \le 1$ Скорость линейной сходимости (ожидаемая), если существует константа$С>0$ Делает:
$$Э[ф({Икс}_{к})]-ф({Икс}^{\ast })\le (1-\rho {)}^{к}С=О(\mathrm{эксп}(-к\rho ))\forall к(16)$$
В этом отличие от классических методов SGD, которые полагаются только на несмещенные оценки градиента на каждой итерации, которые получают сублинейные скорости только при этих предположениях:
$$Э[ф({Икс}_{к})]-ф({Икс}^{\ast })\le О(1/к)$$
Минимум, удовлетворяющий этому неравенству$к$ Это называется итеративной сложностью алгоритма. Ниже приведены итерационная сложность и стоимость одной итерации для базовых вариантов методов GD, SGD и VR:

Общее время работы алгоритма определяется произведением сложности итерации и времени ее выполнения.используется здесь${\kappa }_{\text{Макс}}:={\mathrm{Макс}}_{я}{Л}_{я}/\mu$ .Уведомление${\kappa }_{\text{Макс}}\ge \kappa$; Следовательно, сложность итерации GD меньше, чем у метода VR;

Однако, поскольку стоимость одной итерации GD равна стоимости метода VR $н$ раз, метод VR превосходит по общему времени работы.

Преимущество классических методов SGD в том, что время их работы и скорость сходимости не зависят от $н$, но у него есть толерантность $ϵ$ Зависимость гораздо хуже, что объясняет плохую работу SGD при малом допуске.

В Приложении B мы приводим простое доказательство того, что метод SGD² имеет ту же итерационную сложность, что и метод VR.

2. Базовый метод уменьшения дисперсии

Разработка методов уменьшения дисперсии (VR) прошла несколько этапов, и первая партия методов привела к значительному улучшению скорости сходимости. Началом этой серии методов является алгоритм SAG. Впоследствии один за другим появились алгоритм стохастического подъема двойной координаты (SDCA), алгоритм MISO, алгоритм уменьшения стохастического градиента (SVRG/S2GD) и алгоритм SAGA (что означает «улучшенный» SAG).

В этой главе мы подробно опишем эти новаторские методы виртуальной реальности. В главе 4 мы рассмотрим некоторые новые методы, которые демонстрируют превосходные характеристики по сравнению с этими базовыми методами в конкретных сценариях применения.

2.1. Метод стохастического среднего градиента (SAG).

Наше исследование первого метода уменьшения дисперсии (VR) начинается с имитации полной градиентной структуры.Поскольку полный градиент$\nabla ф(Икс)$ это все$\nabla {ф}_{я}(Икс)$ Простое среднее градиентов, затем наша оценка полного градиента${г}_{к}$ Это также должно быть среднее значение этих оценок градиента. Эта идея породила наш первый метод VR: метод стохастического среднего градиента (SAG).

Метод SAG [37], [65] представляет собой рандомизированную версию метода раннего инкрементного агрегированного градиента (IAG) [4]. Основная идея SAG заключается в том, что для каждой точки данных$я$ поддерживать оценку${в}_{ик}\approx \nabla {ф}_{я}({Икс}_{к})$ .Затем используйте эти${в}_{ик}$ В качестве оценки полного градиента используется среднее значение, то есть:
$${\overline{г}}_{к}=\frac{1}{н}\sum _{дж=1}^{н}{в}_{шучу}\approx \frac{1}{н}\sum _{дж=1}^{н}\nabla {ф}_{дж}({Икс}_{к})=\nabla ф({Икс}_{к})(18)$$

В каждой итерации SAG из набора { 1 , … , n } {1, лточки, n}{1,…,н} Извлечь индекс из${я}_{к}$, а затем обновляется в соответствии со следующими правилами ${в}_{шучу}$：
$${в}_{шучу}^{к+1}=\{\begin{array}{ll}\nabla {ф}_{{я}_{к}}({Икс}_{к}),& \text{если}дж={я}_{к}\\ {в}_{шучу}^{к},& \text{если}дж\ne {я}_{к}\end{array}(19)$$
Среди них каждый${в}_{0я}$ Может быть инициализирован нулем или$\nabla {ф}_{я}({Икс}_0)$ приблизительная стоимость.С решением${Икс}^{\ast }$ приближение, каждый${в}_{ик}$ постепенно сойдется к$\nabla {ф}_{я}({Икс}^{\ast })$, тем самым удовлетворяя свойству VR (12).

Чтобы эффективно реализовать SAG, нам необходимо обратить внимание на расчет ${\overline{г}}_{к}$ чтобы не начинать суммирование каждый раз с нуля$н$ вектор, потому что это$н$ Цена высока, когда она большая.К счастью, поскольку каждая итерация имеет только один${в}_{ик}$ Условия изменятся и нам не придется каждый раз пересчитывать всю сумму.В частности, предположим, что при итерации$к$ Индекс извлечен из${я}_{к}$, то есть:
$${\overline{г}}_{к}=\frac{1}{н}\sum _{\begin{array}{c}дж=1\\ дж\ne {я}_{к}\end{array}}^{н}{в}_{шучу}+\frac{1}{н}{в}_{{я}_{к}}^{к}={\overline{г}}_{к-1}-\frac{1}{н}{в}_{{я}_{к}}^{к-1}+\frac{1}{н}{в}_{{я}_{к}}^{к}(20)$$

Поскольку помимо ${в}_{{я}_{к}}$ все, кроме${в}_{шучу}$ Все значения остаются прежними, мы просто сохраняем каждое$дж$ Вектор, соответствующий${в}_{дж}$ . Алгоритм 1 показывает конкретную реализацию метода SAG.

SAG — первый стохастический метод, обеспечивающий линейную сходимость, сложность его итерации равна $О(({\kappa }_{\text{Макс}}+н)\mathrm{вотг}(1/ϵ))$, используя размер шага $\gamma =О(1/{Л}_{\text{Макс}})$ . Эту линейную сходимость можно наблюдать на рисунке 1.Стоит отметить, что из-за${Л}_{\text{Макс}}$-Плавная функция для любого ${Л}^{\prime }\ge {Л}_{\text{Макс}}$ Слишком${Л}^{\prime }$- Гладкие методы SAG достигают линейной скорости сходимости при достаточно малых размерах шагов, в отличие от классических методов SGD, которые достигают сублинейных скоростей только с последовательностями уменьшения размеров шагов, которые трудно регулировать на практике.

В то время линейная сходимость SAG была значительным достижением, поскольку она вычисляла только один стохастический градиент (обработка одной точки данных) на каждой итерации. Однако доказательство сходимости, предоставленное Шмидтом и др. [65], очень сложно и основано на компьютерно проверенных шагах. Основная причина, по которой SAG трудно анализировать, заключается в том, что${г}_{к}$ является смещенной оценкой градиента.

Далее мы представляем метод SAGA, вариант SAG, который использует концепцию ковариат для создания несмещенного варианта метода SAG, который имеет аналогичную производительность, но его легче анализировать.

---

Алгоритм 1: метод SAG

1. Параметры: размер шага $\gamma >0$
2. инициализация:${Икс}_0$，${в}_{я}=0\in {\mathbb{р}}^{г}$ для$я=1,\dots ,н$
3. верно $к=1,\dots ,Т-1$ осуществлять:
   а. Случайный выбор ik ∈ { 1 , … , n } i_k в {1, ldots, n}як​∈{1,…,н}
   б. Рассчитать${\overline{г}}_{к}={\overline{г}}_{к-1}-\frac{1}{н}{в}_{{я}_{к}}^{к-1}$
   в. Обновление${в}_{{я}_{к}}^{к}=\nabla {ф}_{{я}_{к}}({Икс}_{к})$
   d. Обновить оценку градиента.${\overline{г}}_{к}={\overline{г}}_{к}+\frac{1}{н}{в}_{{я}_{к}}^{к}$
   е. Обновление${Икс}_{к+1}={Икс}_{к}-\gamma {\overline{г}}_{к}$
4. Выход:${Икс}_{Т}$

2.2.Метод САГА

Сокращенная базовая несмещенная оценка градиента $\nabla {ф}_{{я}_{к}}({Икс}_{к})$ Дисперсионный подход заключается в использовании так называемых ковариат или контрольных переменных.для$я=1,\dots ,н$,настраивать ${в}_{я}\in {\mathbb{р}}^{г}$ является вектором.Используя эти векторы, мы можем преобразовать полный градиент$\nabla ф(Икс)$ Переписано как:
$$\nabla ф(Икс)=\frac{1}{н}\sum _{я=1}^{н}(\nabla {ф}_{я}(Икс)-{в}_{я}+{в}_{я})=\frac{1}{н}\sum _{я=1}^{н}\nabla {ф}_{я}(Икс)-{в}_{я}+\frac{1}{н}\sum _{дж=1}^{н}{в}_{дж}$$
$$:=\frac{1}{н}\sum _{я=1}^{н}\nabla {ф}_{я}(Икс,в)(21)$$
который определяет$\nabla {ф}_{я}(Икс,в):=\nabla {ф}_{я}(Икс)-{в}_{я}+\frac{1}{н}{\sum }_{дж=1}^{н}{в}_{дж}$ .Теперь мы можем случайным образом выбрать$\nabla {ф}_{я}(Икс,в)$ построить полный градиент$\nabla ф(Икс)$ Непредвзятая оценка i ∈ { 1 , … , n } i в {1, ldots, n}я∈{1,…,н}, вы можете применить метод SGD и использовать оценку градиента:
$${г}_{к}=\nabla {ф}_{{я}_{к}}({Икс}_{к},в)=\nabla {ф}_{{я}_{к}}({Икс}_{к})-{в}_{{я}_{к}}+\frac{1}{н}\sum _{дж=1}^{н}{в}_{дж}(22)$$

для наблюдения ${в}_{я}$ Разница в паре выбора${г}_{к}$ влияние, мы можем${г}_{к}=\nabla {ф}_{{я}_{к}}({Икс}_{к},в)$ Заменить и использовать${Э}_{я}\sim \frac{1}{н}[{в}_{я}]=\frac{1}{н}{\sum }_{дж=1}^{н}{в}_{дж}$ Чтобы вычислить математическое ожидание, получим:
$$Э\left[\Vert \nabla {ф}_{я}({Икс}_{к})-{в}_{я}+{Э}_{я}\sim \frac{1}{н}[{в}_{я}-\nabla {ф}_{я}({Икс}_{к})]{\Vert }^2\right]\le Э\left[\Vert \nabla {ф}_{я}({Икс}_{к})-{в}_{я}{\Vert }^2\right](23)$$
Здесь используется лемма 2, где$Икс=\nabla {ф}_{я}({Икс}_{к})-{в}_{я}$ .Эта оценка (23) показывает, что если${в}_{я}$ вместе с$к$ Увеличение близко к$\nabla {ф}_{я}({Икс}_{к})$ , мы можем получить атрибуты VR (12).Вот почему мы звоним${в}_{я}$ являются ковариатами, и мы можем выбрать их, чтобы уменьшить дисперсию.

Например, этот подход также реализуется методом SGD² (13), где ${в}_{я}=\nabla {ф}_{я}({Икс}^{\ast })$ .Однако на практике это обычно не используется, поскольку мы обычно не знаем,$\nabla {ф}_{я}({Икс}^{\ast })$ .Более практичный вариант${в}_{я}$ как мы знаем${\overline{Икс}}_{я}\in {\mathbb{р}}^{г}$ ближайший градиент$\nabla {ф}_{я}({\overline{Икс}}_{я})$ . SAGA для каждой функции${ф}_{я}$ использовать ориентир${\overline{Икс}}_{я}\in {\mathbb{р}}^{г}$и используйте ковариаты ${в}_{я}=\nabla {ф}_{я}({\overline{Икс}}_{я})$, каждый, из которых ${\overline{Икс}}_{я}$ будет нашей последней оценкой${ф}_{я}$ точка. Используя эти ковариаты, мы можем построить оценку градиента, следуя (22), давая:
$${г}_{к}=\nabla {ф}_{{я}_{к}}({Икс}_{к})-\nabla {ф}_{{я}_{к}}({\overline{Икс}}_{{я}_{к}})+\frac{1}{н}\sum _{дж=1}^{н}\nabla {ф}_{дж}({\overline{Икс}}_{дж})(24)$$

Чтобы реализовать SAGA, мы можем хранить градиенты. $\nabla {ф}_{я}({\overline{Икс}}_{я})$ вместо$н$ ориентир${\overline{Икс}}_{я}$ .То есть предположим${в}_{дж}=\nabla {ф}_{дж}({\overline{Икс}}_{дж})$ для j ∈ { 1 , … , n } j в {1, ldots, n}дж∈{1,…,н}, на каждой итерации мы обновляем стохастический градиент, такой как SAG ${в}_{дж}$。

Алгоритм 2 САГА

1. Параметры: размер шага $\gamma >0$
2. инициализация:${Икс}_0$，${в}_{я}=0\in {\mathbb{р}}^{г}$ для$я=1,\dots ,н$
3. руководить $к=1,\dots ,Т-1$ итерации:
   а. Случайный выбор ik ∈ { 1 , … , n } i_k в {1, ldots, n}як​∈{1,…,н}
   б. Сохранить старое значение.${в}_{\text{старый}}={в}_{{я}_{к}}$
   в. Обновление${в}_{{я}_{к}}=\nabla {ф}_{{я}_{к}}({Икс}_{к})$
   д. Обновление${Икс}_{к+1}={Икс}_{к}-\gamma ({в}_{{я}_{к}}-{в}_{\text{старый}}+{\overline{г}}_{к})$
   e. Обновить оценку градиента.${\overline{г}}_{к}={\overline{г}}_{к-1}+\frac{1}{н}({в}_{{я}_{к}}-{в}_{\text{старый}})$
4. Выход:${Икс}_{Т}$

Метод SAGA имеет ту же сложность итерации, что и SAG. $О(({\kappa }_{\text{Макс}}+н)\mathrm{вотг}(1/ϵ))$, используя размер шага $\gamma =О(1/{Л}_{\text{Макс}})$ , но доказательство гораздо проще.Однако, как и SAG, метод SAGA требует хранения$н$ вспомогательные векторы${в}_{я}\in {\mathbb{р}}^{г}$ для$я=1,\dots ,н$, что означает необходимость $О(нг)$ места для хранения.когда$г$ и$н$ Когда оба велики, это может быть неосуществимо. В следующем разделе мы подробно расскажем, как уменьшить требования к памяти для распространенных моделей, таких как регуляризованные линейные модели.

когда смогу $н$ Когда в памяти хранятся два вспомогательных вектора, SAG и SAGA имеют тенденцию вести себя одинаково. Если требования к памяти слишком высоки, хорошей альтернативой является метод SVRG, который мы рассмотрим в следующем разделе. Метод SVRG достигает той же скорости сходимости и на практике часто почти так же быстр, но требует только$О(г)$ памяти, по общим вопросам.

2.3.Метод СВРГ

До появления метода SAGA в некоторых ранних работах впервые были введены ковариаты для решения проблемы большого объема памяти, необходимой для метода SAG.Эти исследования основаны на фиксированной контрольной точке.$\overline{Икс}\in {\mathbb{р}}^{г}$ ковариаты, мы вычислили полный градиент в этой точке$\nabla ф(\overline{Икс})$ .сохраняя контрольные точки$\overline{Икс}$ и соответствующий полный градиент$\nabla ф(\overline{Икс})$, мы можем сделать это, не сохраняя каждый $\nabla {ф}_{дж}(\overline{Икс})$ В случае, используйте${\overline{Икс}}_{дж}=\overline{Икс}$ все$дж$ для реализации обновления (24).В частности, вместо хранения этих векторов мы используем сохраненные опорные точки на каждой итерации.$\overline{Икс}$ вычислять$\nabla {ф}_{{я}_{к}}(\overline{Икс})$ . Первоначально этот метод был предложен разными авторами под разными названиями, но позже был унифицирован как метод SVRG, следуя номенклатуре [28] и [84].

Формализуем метод SVRG в алгоритме 3.

Используя (23), можно получить оценку градиента ${г}_{к}$ Дисперсия ограничена:
$$Э\left[\Vert {г}_{к}-\nabla ф({Икс}_{к}){\Vert }^2\right]\le Э\left[\Vert \nabla {ф}_{я}({Икс}_{к})-\nabla {ф}_{я}(\overline{Икс}){\Vert }^2\right]\le {Л}_{\text{Макс}}^2\Vert {Икс}_{к}-\overline{Икс}{\Vert }^2$$
где второе неравенство использует каждый${ф}_{я}$ из${Л}_{я}$-Гладкость.

Стоит отметить, что ориентир $\overline{Икс}$ Чем ближе к текущей точке${Икс}_{к}$, тем меньше дисперсия оценки градиента.

Чтобы метод SVRG был эффективным, нам необходимо часто обновлять контрольные точки. $\overline{Икс}$ (тем самым требуя расчета полного градиента) сопоставляется с выгодой от уменьшения дисперсии.По этой причине каждый из нас$т$ Обновляйте контрольную точку один раз на каждой итерации, чтобы она была близка к${Икс}_{к}$ (См. строку 11 алгоритма II-C).То есть метод SVRG содержит два цикла: внешний цикл$с$, где вычисляется опорный градиент $\nabla ф({\overline{Икс}}_{с-1})$(строка 4) и внутренний цикл, в котором опорная точка фиксируется, а внутренняя итерация обновляется на основе шага стохастического градиента (22). ${Икс}_{к}$(Строка 10).

В отличие от SAG и SAGA, SVRG требует только $О(г)$ памяти. К недостаткам SVRG относятся: 1) У нас есть дополнительный параметр.$т$, то есть длину внутреннего цикла, необходимо скорректировать. 2) Для каждой итерации необходимо рассчитывать два градиента, а полный градиент необходимо рассчитывать каждый раз при изменении опорной точки;

Джонсон и Чжан [28] показали, что SVRG имеет итеративную сложность. $О(({\kappa }_{\text{Макс}}+н)\mathrm{вотг}(1/ϵ))$ , аналогично SAG и SAGA.Это количество петель в гипотезе.$т$ из коллекции { 1 , … , м } {1, лточки, м}{1,…,м} Получено при условии равномерной выборки, где${Л}_{\text{Макс}}$，$\mu$, размер шага $\gamma$ и$т$ Между ними должны быть удовлетворены определенные зависимости.На практике, используя$\gamma =О(1/{Л}_{\text{Макс}})$ и длина внутреннего цикла$т=н$, SVRG имеет тенденцию работать хорошо, и это именно та настройка, которую мы использовали на рисунке 1.

Сейчас существует множество вариаций исходного метода SVRG.Например, в некоторых вариантах используется$т$ альтернативное распределение [32], некоторые варианты допускают вид$О(1/{Л}_{\text{Макс}})$ Размер шага [27], [33], [35].Существуют также некоторые варианты использования$\nabla ф(\overline{Икс})$ аппроксимация мини-пакета, чтобы снизить стоимость этих полных оценок градиента, и увеличить размер мини-пакета, чтобы сохранить свойства VR.Существуют также варианты, в которых обновления повторяются во внутреннем цикле согласно [54]${г}_{к}$：
[ g_k = набла f_{i_k}(x_k) - набла f_{i_k}(x_{k-1}) + g_{k-1} quad (25) ]
Это обеспечивает более локальное приближение. Использование этого варианта непрерывного обновления (25) показывает уникальные преимущества в минимизации невыпуклых функций, как мы кратко обсудим в разделе IV.Наконец, обратите внимание, что SVRG может воспользоваться преимуществами$\nabla ф({\overline{Икс}}_{с})$ значение, помогающее решить, когда завершить работу алгоритма.

Алгоритм 3. Метод СВРГ.

1. Параметры: размер шага $\gamma >0$
2. Инициализировать контрольную точку ${\overline{Икс}}_0={Икс}_0\in {\mathbb{р}}^{г}$
3. Осуществить внешнюю циркуляцию $с=1,2,\dots$：
   а. Рассчитайте и сохраните.$\nabla ф({\overline{Икс}}_{с-1})$
   б. Предположим${Икс}_0={\overline{Икс}}_{с-1}$
   c. Выберите количество итераций внутреннего цикла.$т$
   г. Осуществить внутреннюю циркуляцию.$к=0,1,\dots ,т-1$：
   я. случайный выбор ik ∈ { 1 , … , n } i_k в {1, ldots, n}як​∈{1,…,н}
   ii. Расчет${г}_{к}=\nabla {ф}_{{я}_{к}}({Икс}_{к})-\nabla {ф}_{{я}_{к}}({\overline{Икс}}_{с-1})+\nabla ф({\overline{Икс}}_{с-1})$
   3. Обновление${Икс}_{к+1}={Икс}_{к}-\gamma {г}_{к}$
   e. Обновление контрольной точки.${\overline{Икс}}_{с}={Икс}_{т}$

2.4. СДКА и его варианты.

Одним из недостатков методов SAG и SVRG является то, что размер их шага зависит от неизвестных значений, которые могут быть неизвестны в некоторых задачах. ${Л}_{\text{Макс}}$ . До SVRG метод SDCA [70], как один из первых методов VR, расширил исследования методов координатного спуска на задачи конечных сумм. Идея SDCA и его вариантов заключается в том, что координаты градиента обеспечивают естественную оценку градиента, уменьшающую дисперсию.В частности, предположим j ∈ { 1 , … , d } j в {1, ldots, d}дж∈{1,…,г}и определить ${\nabla }_{дж}ф(Икс):=\left(\frac{\partial ф(Икс)}{\partial {Икс}_{дж}}\right){е}_{дж}$ является числом (f(x))$дж$ производные по координатным направлениям, где${е}_{дж}\in {\mathbb{р}}^{г}$ Это первый$дж$ единичный вектор.Ключевым свойством производных по координатам является то, что${\nabla }_{дж}ф({Икс}^{\ast })=0$, потому что мы знаем $\nabla ф({Икс}^{\ast })=0$ .Производная этого с каждой точкой данных$\nabla {ф}_{дж}$ другое, последнее${Икс}^{\ast }$ может быть не нулевым. Поэтому мы имеем:
$$\Vert \nabla ф(Икс)-{\nabla }_{дж}ф(Икс){\Vert }^2\to 0\text{когда}Икс\to {Икс}^{\ast }(26)$$
Это означает, что производная по координате удовлетворяет свойству уменьшения дисперсии (12).Кроме того, мы можем использовать${\nabla }_{дж}ф(Икс)$ строить$\nabla ф(Икс)$ несмещенная оценка.Например, предположим$дж$ это из коллекции { 1 , … , d } {1, ldots, d}{1,…,г} Равномерно случайно выбранный индекс в .Следовательно, для любого i ∈ { 1 , … , d } i в {1, ldots, d}я∈{1,…,г},У нас есть $п[дж=я]=\frac{1}{г}$ . поэтому,$г\times {\nabla }_{дж}ф(Икс)$ да$\nabla ф(Икс)$ Непредвзятая оценка, потому что:
$$Э\left[г{\nabla }_{дж}ф(Икс)\right]=г\sum _{я=1}^{г}п[дж=я]\frac{\partial ф(Икс)}{\partial {Икс}_{я}}{е}_{я}=\sum _{я=1}^{г}\frac{\partial ф(Икс)}{\partial {Икс}_{я}}{е}_{я}=\nabla ф(Икс)$$

поэтому,${\nabla }_{дж}ф(Икс)$ Обладает всеми идеальными свойствами, которые мы ожидаем от VR-оценки полных градиентов, без необходимости использования ковариат. Одним из недостатков использования этого координатного градиента является то, что он требует больших вычислительных затрат для нашей задачи о суммах (2).Это связано с тем, что расчет${\nabla }_{дж}ф(Икс)$ Необходимо пройти весь набор данных, потому что${\nabla }_{дж}ф(Икс)=\frac{1}{н}{\sum }_{я=1}^{н}{\nabla }_{дж}{ф}_{я}(Икс)$ . Поэтому использование производных по координатам кажется несовместимым со структурой нашей задачи о сумме. Однако мы часто можем переписать исходную задачу (2) в так называемую двойственную формулировку, в которой производные по координатам могут использовать внутреннюю структуру.

Например, двойственная формула регуляризованной линейной модели L2 (15):
$${в}^{\ast }\in \mathrm{арг}\underset{в\in {\mathbb{р}}^{н}}{\mathrm{Макс}}\frac{1}{н}\sum _{я=1}^{н}-{\ell }_{я}^{\ast }(-{в}_{я})-\frac{\lambda }{2}{\Vert \frac{1}{\lambda }\sum _{я=1}^{н}{в}_{я}{а}_{я}\Vert }^2(27)$$
в${\ell }_{я}^{\ast }(в)$ да${\ell }_{я}$ выпуклое сопряжение.Мы можем использовать отображение$Икс=\frac{1}{\lambda }{\sum }_{я=1}^{н}{в}_{я}{а}_{я}$ восстановить исходную проблему (15)$Икс$ переменная.решит${в}^{\ast }$ Подставив в правую часть приведенного выше отображения, мы можем получить решение (15)${Икс}^{\ast }$。

Обратите внимание, что эта двойная проблема имеет $н$ действительные переменные${в}_{я}\in \mathbb{р}$ , что соответствует одному для каждой обучающей выборки.Более того, каждая функция двойных потерь${\ell }_{я}^{\ast }$ только${в}_{я}$ Функция. То есть первый член функции потерь отделим по координатам. Такая разделимость по координатам в сочетании с простой формой второго слагаемого позволяет эффективно реализовать метод подъема координат.Действительно, Шалев-Шварц и Чжан показали, что подъем координат в этой задаче имеет аналогичную итерационную сложность, что и SAG, SAGA и SVRG.$О(({\kappa }_{\text{Макс}}+н)\mathrm{вотг}(1/ϵ))$。

Стоимость итерации и структура алгоритма также очень похожи: суммирование путем отслеживания ${\sum }_{я=1}^{н}{в}_{я}{а}_{я}$ Чтобы обработать второй член в (27), каждая итерация подъема по двойной координате должна учитывать только одну обучающую выборку, а стоимость каждой итерации такая же, как и$н$ Нечего делать.Кроме того, мы можем использовать поиск по 1D-линии, чтобы эффективно вычислить размер шага для максимизации как${в}_{я}$ Двойная цель функции.Это означает, что даже без${Л}_{\text{Макс}}$ Или знание соответствующих величин также позволяет добиться быстрого времени работы методов виртуальной реальности в наихудшем случае.

3. Практические вопросы уменьшения дисперсии

Чтобы реализовать базовый метод уменьшения дисперсии (VR) и добиться приемлемой производительности, необходимо решить несколько проблем реализации. В этом разделе мы обсудим несколько вопросов, не затронутых выше.

3.1.Размер шага настройки SAG/SAGA/SVRG

В области алгоритмов оптимизации, особенно в методах уменьшения вариаций, таких как стохастический средний градиент (SAG), алгоритм стохастического среднего градиента (SAGA) и стохастический градиент (SVRG), установка размера шага является ключевым вопросом.Хотя для метода стохастического подъема по двойной координате (SDCA) мы можем использовать двойную цель для определения размера шага, теоретическая основа исходных методов переменных SAG, SAGA и SVRG заключается в том, что размер шага должен быть равен$\gamma =О\left(\frac{1}{{Л}_{\text{Макс}}}\right)$ форма.Однако в практических приложениях мы часто не знаем,${Л}_{\text{Макс}}$ точное значение, а использование других размеров шага может дать лучшую производительность.

Классической стратегией установки размера шага в методе полного градиентного спуска (full-GD) является поиск линий Armijo.данная текущая точка${Икс}_{к}$ и направление поиска${г}_{к}$, поиск линии Armijo в ${\gamma }_{к}$ осуществляется на линии, которая определяется как γ k ∈ { γ : xk + γ gk } gamma_k в {gamma : x_k + gamma g_k}γк​∈{γ:Икск​+γгк​}, причем функция должна быть достаточно редуцированной, т.е.:
$$ф({Икс}_{к}+{\gamma }_{к}{г}_{к})<ф({Икс}_{к})-с{\gamma }_{к}\Vert \nabla ф({Икс}_{к}){\Vert }^2$$
Однако этот подход требует нескольких шагов-кандидатов.${\gamma }_{к}$ Расчет$ф({Икс}_{к}+{\gamma }_{к}{г}_{к})$, который оценивает $ф(Икс)$ Стоимость обхода всего набора данных непомерно высока.

Для решения этой проблемы можно использовать метод случайных вариаций, чтобы найти те, которые удовлетворяют следующим условиям: ${\gamma }_{к}$：
$${ф}_{ик}({Икс}_{к}+{\gamma }_{к}{г}_{к})<{ф}_{ик}({Икс}_{к})-с{\gamma }_{к}\Vert \nabla {ф}_{ик}({Икс}_{к}){\Vert }^2$$
Этот подход обычно хорошо работает на практике, особенно когда$\Vert \nabla {ф}_{ик}({Икс}_{к})\Vert$ не близок к нулю, хотя в настоящее время не существует теории, подтверждающей этот подход.

Кроме того, Майрал предложил «технику Ботту» для практической установки размера шага. Этот метод выполняет двоичный поиск, беря небольшую часть набора данных (например, 5%), чтобы попытаться найти оптимальный размер шага за один проход по этой выборке. Подобно поиску по линии Армихо, этот метод часто хорошо работает на практике, но ему снова не хватает теоретической основы.

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

Однако метод SDCA также имеет некоторые недостатки.Во-первых, для этого требуется вычислить выпуклое сопряжение${\ell }_{я}^{\ast }$ а не простой градиент. У нас нет автоматического дифференциального эквивалента для выпуклых сопряжений, поэтому это может увеличить усилия по реализации. В недавней работе были предложены методы SDCA с «двойной свободой», которые не требуют сопряжения и вместо этого напрямую используют градиенты. Однако в этих методах больше невозможно отслеживать двойную цель, чтобы установить размер шага.Во-вторых, хотя SDCA требует только$О(н+г)$ памяти для решения задачи (15), но для этой категории задач SAG/SAGA требуется только$О(н+г)$ памяти (см. раздел 3).Вариант SDCA, подходящий для более общих проблем с SAG/SAGA.$О(нг)$ память, потому что${в}_{я}$ стать обладателем$г$ вектор элементов. Последний тонкий недостаток SDCA заключается в том, что он неявно предполагает сильную константу выпуклости.$\mu$ равный$\lambda$ .для$\mu$ больше, чем$\lambda$ Проблема заключается в том, что оригинальный метод VR обычно значительно превосходит SDCA.

3.2 Определение условий прекращения действия.

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

В традиционном методе полного градиентного спуска (full-GD) мы обычно используем норму градиента. $\Vert \nabla ф({Икс}_{к})\Vert$ Или какая-то другая величина, связанная с этим, чтобы решить, когда остановить итерацию.Для метода SVRG мы можем принять тот же критерий, но использовать$\Vert \nabla ф({\overline{Икс}}_{с})\Vert$ как основание для приговора.Для метода SAG/SAGA, хотя мы и не рассчитываем явно полный градиент, величина $g_{bar{k}}$ будет постепенно приближаться$\nabla ф({Икс}_{к})$, поэтому используйте $\Vert {г}_{\overline{к}}\Vert$ в качестве условия остановки является разумной эвристикой.

В методе SDCA, с некоторой дополнительной работой по записи, мы можем отслеживать градиент двойной цели без добавления дополнительных асимптотических затрат.Кроме того, более систематическим подходом было бы отслеживание двойного разрыва, хотя это увеличило бы$О(н)$ стоимость, но он способен обеспечить условия завершения с двойным доказательством разрыва. Кроме того, на основе условия оптимальности сильно выпуклых целей метод MISO использует принципиальный метод, основанный на квадратичной нижней границе [41].

Ниже приведены математические формулы и переменные, выраженные в формате Markdown:

• Норма градиента:$\Vert \nabla ф({Икс}_{к})\Vert$
• Норма градиента в методе СВРГ:$\Vert \nabla ф({\overline{Икс}}_{с})\Vert$
• Величина градиента аппроксимации в методе SAG/SAGA: $ g_{bar{k}} $
• Увеличение стоимости за итерацию:$О(н)$
• МИСО-метод
• квадратичная нижняя граница

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

3.3. Уменьшите требования к памяти.

Хотя алгоритм стохастического вариационного уменьшения градиента (SVRG) устраняет требования к памяти, присущие более ранним методам уменьшения вариации, в практических приложениях во многих задачах используются алгоритмы SAG (стохастический средний градиентный спуск) и SAGA (стохастический средний градиентный спуск с накоплением градиента). . обычно требуют меньше итераций, чем алгоритм SVRG.Это вызвало мысль: есть ли какие-то проблемы, которые позволяют SAG/SAGA$О(нг)$ Требования к памяти реализованы ниже. В этом разделе исследуется класс линейных моделей, для которых требования к памяти могут быть значительно снижены.

Рассмотрим линейную модель, в которой каждая функция ${ф}_{я}(Икс)$ Это может быть выражено как${\xi }_{я}({\mathbf{а}}_{я}^{\top }Икс)$ .верно$Икс$ Производная дает форму градиента:
$$\nabla {ф}_{я}(Икс)={\xi }^{\prime }({\mathbf{а}}_{я}^{\top }Икс){\mathbf{а}}_{я}$$
здесь,${\xi }^{\prime }$ выражать$\xi$ производная от.Предполагая, что у нас есть прямой доступ к собственным векторам${\mathbf{а}}_{я}$, то для реализации метода SAG/SAGA нам нужно всего лишь сохранить скаляр $\xi ({\mathbf{а}}_{я}^{\top }Икс)$ .Таким образом, требования к памяти варьируются от$О(нг)$ уменьшено до$О(н)$ . Алгоритм SVRG также может использовать эту структуру градиентов: сохраняя это$н$ скаляр, мы можем уменьшить количество оценок градиента, необходимых для каждой «внутренней» итерации SVRG, до 1 для этого класса задач.

Существуют и другие типы задач, например вероятностные графические модели, которые также предлагают возможность снижения требований к памяти [66]. Благодаря специальной структуре данных и оптимизации алгоритма ресурсы памяти, необходимые алгоритму во время выполнения, могут быть дополнительно сокращены.

Ниже приведены математические формулы и переменные, выраженные в формате Markdown:

• Функция линейной модели:${ф}_{я}(Икс)={\xi }_{я}({\mathbf{а}}_{я}^{\top }Икс)$
• Градиентное выражение:$\nabla {ф}_{я}(Икс)={\xi }^{\prime }({\mathbf{а}}_{я}^{\top }Икс){\mathbf{а}}_{я}$
• Вектор признаков:${\mathbf{а}}_{я}$
• Требования к памяти варьируются от $О(нг)$ Сократить до$О(н)$。

3.4. Обработка разреженных градиентов.

В некоторых задачах градиент $\nabla {ф}_{я}(Икс)$ Может содержать большое количество нулевых значений, например, линейная модель с редкими функциями.В этом случае традиционный алгоритм стохастического градиентного спуска (SGD) может быть эффективно реализован, при этом вычислительная сложность линейно зависит от количества ненулевых элементов в градиенте, которое обычно намного меньше размерности задачи.$г$ . Однако в стандартных методах вариационного сокращения (VR) это преимущество не используется. К счастью, есть два известных способа улучшить это.

Первое улучшение было предложено Шмидтом и др., которое использует преимущества простоты процесса обновления и реализует вариант вычислений «на лету», так что стоимость каждой итерации пропорциональна количеству ненулевых вычислений. элементы.Если взять в качестве примера SAG (но этот подход работает для всех вариантов), это достигается за счет не сохранения полного вектора после каждой итерации.${в}_{ик}$, но вычисляет только те, которые соответствуют ненулевым элементам ${в}_{я{к}_{дж}}$, обновляя каждую переменную с тех пор, как последний раз этот элемент был ненулевым ${в}_{я{к}_{дж}}$。

Второй метод улучшения был предложен Леблоном и др. для SAGA, который обновляет формулу. ${Икс}_{к+1}={Икс}_{к}-\gamma (\nabla {ф}_{ик}({Икс}_{к})-\nabla {ф}_{ик}({\overline{Икс}}_{ик})+{\overline{г}}_{к})$ Вводится дополнительная случайность. здесь,$\nabla {ф}_{ик}({Икс}_{к})$ и$\nabla {ф}_{ик}({\overline{Икс}}_{ик})$ является редким, и${\overline{г}}_{к}$ плотный.В этом методе плотный член$({\overline{г}}_{к}{)}_{дж}$ Каждый компонент заменяется на${ж}_{дж}({\overline{г}}_{к}{)}_{дж}$,в $ж\in {\mathbb{р}}^{г}$ — случайный разреженный вектор, набор опорных элементов которого содержится в$\nabla {ф}_{ик}({Икс}_{к})$ , и ожидается, что это постоянный вектор со всеми элементами, равными 1. Таким образом, процесс обновления остается несмещенным (хотя теперь и разреженным), а увеличенная дисперсия не влияет на скорость сходимости алгоритма. Более подробную информацию предоставили Leblond et al.

Ниже приведены математические формулы и переменные, выраженные в формате Markdown:

• градиент:$\nabla {ф}_{я}(Икс)$
• Обновление SGD:${Икс}_{к+1}={Икс}_{к}-\gamma (\nabla {ф}_{ик}({Икс}_{к})-\nabla {ф}_{ик}({\overline{Икс}}_{ик})+{\overline{г}}_{к})$
• Разреженный градиент:$\nabla {ф}_{ик}({Икс}_{к})$ и$\nabla {ф}_{ик}({\overline{Икс}}_{ик})$
• Плотный градиент:${\overline{г}}_{к}$
• Случайные разреженные векторы:$ж$
• Ожидается постоянный вектор: вектор, все элементы которого равны 1.