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

Введение

Алгоритм оптимизации

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

История

В 1951 году Герберт Роббинс и Саттон Монро представили самые ранние методы стохастического приближения, предшествующие стохастическому градиентному спуску. Основываясь на этой работе, год спустя Джек Кифер и Джейкоб Вольфовиц опубликовали алгоритм оптимизации, очень близкий к стохастическому градиентному спуску, используя центральные разности в качестве приближения градиента. Позже, в 1950-х годах, Фрэнк Розенблатт использовал SGD для оптимизации своей модели перцептрона, продемонстрировав первое применение стохастического градиентного спуска к нейронным сетям. Обратное распространение ошибки было впервые описано в 1986 году, при этом стохастический градиентный спуск использовался для эффективной оптимизации параметров в нейронных сетях с несколькими скрытыми слоями. Вскоре после этого было разработано другое улучшение: мини-пакетный градиентный спуск, при котором небольшие пакеты данных заменяют отдельные примеры. В 1997 году впервые были изучены практические преимущества векторизации, достижимые с такими небольшими пакетами, что проложило путь к эффективной оптимизации в машинном обучении. По состоянию на 2023 год этот подход с мини-пакетами остается стандартом для обучения нейронных сетей, сочетая преимущества стохастического градиентного спуска и обычного градиентного спуска. К 1980-м годам уже был введен метод импульса (momentum), который был добавлен к методам оптимизации SGD в 1986 году. Однако эти методы оптимизации предполагали постоянные гиперпараметры, то есть фиксированную скорость обучения и параметр импульса. В 2010-х годах были предложены адаптивные подходы к применению SGD с индивидуальной скоростью обучения для каждого параметра, такие как AdaGrad (от "Adaptive Gradient") в 2011 году и RMSprop (от "Root Mean Square Propagation") в 2012 году. В 2014 году был опубликован Adam (от "Adaptive Moment Estimation"), применяющий адаптивные подходы RMSprop к импульсу; впоследствии было разработано множество улучшений и вариантов Adam, таких как Adadelta, Adagrad, AdamW и Adamax. В области машинного обучения в 2023 году в подходах к оптимизации доминируют оптимизаторы, основанные на Adam. TensorFlow и PyTorch, самые популярные библиотеки машинного обучения, по состоянию на 2023 год в основном включают только оптимизаторы, основанные на Adam, а также предшественники Adam, такие как RMSprop и классический SGD. PyTorch также частично поддерживает Limited memory BFGS, метод поиска вдоль линии, но только для одноустройственных конфигураций без групп параметров.

In 1951, Herbert Robbins and Sutton Monro introduced the earliest stochastic approximation methods, preceding stochastic gradient descent. Building on this work one year later, Jack Kiefer and Jacob Wolfowitz published an optimization algorithm very close to stochastic gradient descent, using central differences as an approximation of the gradient. Later in the 1950s, Frank Rosenblatt used SGD to optimize his perceptron model, demonstrating the first applicability of stochastic gradient descent to neural networks. Backpropagation was first described in 1986, with stochastic gradient descent being used to efficiently optimize parameters across neural networks with multiple hidden layers. Soon after, another improvement was developed: mini batch gradient descent, where small batches of data are substituted for single samples. In 1997, the practical performance benefits from vectorization achievable with such small batches were first explored, paving the way for efficient optimization in machine learning. As of 2023, this mini batch approach remains the norm for training neural networks, balancing the benefits of stochastic gradient descent with gradient descent. By the 1980s, momentum had already been introduced, and was added to SGD optimization techniques in 1986. However, these optimization techniques assumed constant hyperparameters, i. e. a fixed learning rate and momentum parameter. In the 2010s, adaptive approaches to applying SGD with a per parameter learning rate were introduced with AdaGrad (for "Adaptive Gradient") in 2011 and RMSprop (for "Root Mean Square Propagation") in 2012. In 2014, Adam (for "Adaptive Moment Estimation") was published, applying the adaptive approaches of RMSprop to momentum; many improvements and branches of Adam were then developed such as Adadelta, Adagrad, AdamW, and Adamax. Within machine learning, approaches to optimization in 2023 are dominated by Adam derived optimizers. TensorFlow and PyTorch, by far the most popular machine learning libraries, as of 2023 largely only include Adam derived optimizers, as well as predecessors to Adam such as RMSprop and classic SGD. PyTorch also partially supports Limited memory BFGS, a line search method, but only for single device setups without parameter groups.

Примечательные применения

Стохастический градиентный спуск — популярный алгоритм для обучения широкого спектра моделей в машинном обучении, включая (линейные) машины опорных векторов, логистическую регрессию (см., например, Vowpal Wabbit) и графические модели. В сочетании с алгоритмом обратного распространения ошибки он является де-факто стандартным алгоритмом для обучения искусственных нейронных сетей. Его применение также отмечалось в геофизическом сообществе, в частности, в задачах полной инверсии волновой формы (FWI). Стохастический градиентный спуск конкурирует с алгоритмом L-BFGS, который также широко используется. Стохастический градиентный спуск используется как минимум с 1960 года для обучения моделей линейной регрессии, изначально под названием ADALINE. Другим алгоритмом стохастического градиентного спуска является адаптивный фильтр наименьших среднеквадратичных ошибок (LMS).

Расширения и варианты

Было предложено и использовано множество улучшений базового алгоритма стохастического градиентного спуска. В частности, в машинном обучении необходимость задания скорости обучения (размера шага) была признана проблемной. Слишком высокое значение этого параметра может привести к расхождению алгоритма, а слишком низкое – к замедлению сходимости. Концептуально простое расширение стохастического градиентного спуска заключается в том, чтобы сделать скорость обучения убывающей функцией ηt от номера итерации t, формируя таким образом расписание скорости обучения, при котором первые итерации приводят к значительным изменениям параметров, а последующие – лишь к тонкой настройке. Такие расписания известны со времен работы МакКуина по k-средним. Практические рекомендации по выбору размера шага для различных вариантов SGD приведены в работе Сполла.

Среднее значение

Усредненный стохастический градиентный спуск, разработанный независимо Руппертом и Поляком в конце 1980-х годов, представляет собой обычный стохастический градиентный спуск, который сохраняет усредненное значение вектора параметров во времени. То есть, обновление происходит так же, как и при обычном стохастическом градиентном спуске, но алгоритм также ведет учет и, после завершения оптимизации, этот усредненный вектор параметров заменяет w.

AdaGrad

AdaGrad (для адаптивного алгоритма градиента) — модифицированный алгоритм стохастического градиентного спуска с индивидуальной скоростью обучения для каждого параметра, впервые опубликованный в 2011 году. Неформально, он увеличивает скорость обучения для редко встречающихся параметров и уменьшает её для часто встречающихся. Эта стратегия часто улучшает сходимость по сравнению со стандартным стохастическим градиентным спуском в задачах, где данные разрежены, а редко встречающиеся параметры несут больше информации. Примерами таких приложений являются обработка естественного языка и распознавание изображений.

Спуск стохастического градиента на основе знака

Несмотря на то, что оптимизация на основе знаков берет начало в вышеупомянутом Rprop, в 2018 году исследователи попытались упростить Adam, исключив учет величины стохастического градиента и рассматривая только его знак.

Поиск обратной линии

Поиск с возвратом (backtracking line search) – еще один вариант градиентного спуска. Вся информация ниже взята из указанной ссылки. Он основан на условии, известном как условие Армихо–Гольдштейна. Оба метода позволяют изменять скорость обучения на каждой итерации, однако способ изменения отличается. Поиск с возвратом использует вычисление значений функции для проверки условия Армихо, и в принципе цикл в алгоритме определения скорости обучения может быть длительным и заранее неизвестным. Адаптивный SGD не требует цикла для определения скорости обучения. С другой стороны, адаптивный SGD не гарантирует "свойство убывания" – которым обладает поиск с возвратом, а именно, что для всех n. Если градиент функции потерь глобально липшиц-непрерывен, с константой Липшица L, и скорость обучения выбрана порядка 1/L, то стандартная версия SGD является частным случаем поиска с возвратом.

Методы второго порядка

Стохастический аналог стандартного (детерминированного) алгоритма Ньютона — Рафсона (метод "второго порядка") обеспечивает асимптотически оптимальную или почти оптимальную форму итеративной оптимизации в условиях стохастического приближения. Метод, использующий прямые измерения гессианских матриц слагаемых в эмпирической функции риска, был разработан Бердом, Хансеном, Носедалом и Сингером. Однако непосредственное определение необходимых гессианских матриц для оптимизации может быть невозможным на практике. Практические и теоретически обоснованные методы для версий второго порядка SGD, не требующие прямой информации о гессиане, предложены Споллом и другими. (Рупперт приводит менее эффективный метод, основанный на конечных разностях вместо одновременных возмущений.) Другой подход к аппроксимации гессианской матрицы — замена её информационной матрицей Фишера, которая преобразует обычный градиент в естественный. Эти методы, не требующие прямой информации о гессиане, основаны либо на значениях слагаемых в указанной эмпирической функции риска, либо на значениях градиентов слагаемых (то есть на входных данных SGD). В частности, асимптотически достижима оптимальность второго порядка без прямого вычисления гессианских матриц слагаемых в эмпирической функции риска.