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

Стохастический градиентный спуск (англ. Stochastic Gradient Descent, SGD) — это итеративный метод оптимизации целевой функции, основанный на вычислении градиента не по всей выборке данных, а по одному случайно выбранному элементу (или небольшой подвыборке — мини-батчу). Является одним из базовых алгоритмов машинного обучения, особенно в задачах обучения нейронных сетей и линейных моделей на больших объёмах данных. В отличие от классического градиентного спуска, который требует полного перебора всех обучающих примеров на каждой итерации, SGD использует стохастическую (случайную) оценку градиента, что значительно ускоряет сходимость на начальных этапах и позволяет обрабатывать наборы данных, не помещающиеся в оперативную память.

История

Метод стохастической аппроксимации, лежащий в основе SGD, был предложен в 1951 году американскими математиками Гербертом Роббинсом и Сэттоном Монро. Первоначально алгоритм разрабатывался для решения задач регрессионного анализа и адаптивной фильтрации. В 1960-х годах метод был адаптирован для обучения перцептронов (Фрэнк Розенблатт) и адаптивных линейных нейронов (ADALINE, Бернард Уидроу). Однако широкое распространение SGD получил с развитием глубокого обучения в 2000-2010-х годах, когда стало очевидно, что классический градиентный спуск неприменим к многомиллионным наборам данных (ImageNet, YouTube-8M) и моделям с миллиардами параметров (например, GPT, BERT).

Основные принципы

Целевая функция и градиент

В задачах машинного обучения требуется минимизировать эмпирический риск — среднее значение функции потерь \( L \) по всем \( n \) обучающим примерам:

\[ Q(w) = \frac{1}{n} \sum_{i=1}^{n} L_i(w) \]

где \( w \) — вектор параметров модели. Градиент \( \nabla Q(w) \) указывает направление наибольшего возрастания функции. Для минимизации параметры обновляются в противоположном направлении:

\[ w_{t+1} = w_t - \eta \nabla Q(w_t) \]

Здесь \( \eta \) — скорость обучения (шаг). В классическом (пакетном) градиентном спуске градиент вычисляется по всем \( n \) примерам, что требует \( O(n) \) операций на итерацию.

Стохастическая оценка

В SGD градиент вычисляется по одному случайно выбранному примеру \( i_t \):

\[ w_{t+1} = w_t - \eta \nabla L_{i_t}(w_t) \]

Такая оценка является несмещённой: \( \mathbb{E}[\nabla L_{i_t}(w_t)] = \nabla Q(w_t) \), но имеет высокую дисперсию. Это приводит к тому, что траектория оптимизации становится «шумной» — параметры могут колебаться вокруг минимума, а не сходиться к нему монотонно. Однако для выпуклых функций при правильном выборе скорости обучения (убывающей по закону \( \eta_t \sim 1/t \)) SGD гарантированно сходится к глобальному минимуму.

Мини-батч SGD

На практике чаще используется компромиссный вариант — мини-батч SGD (Mini-batch SGD), при котором градиент вычисляется по небольшой случайной подвыборке размером \( m \) (обычно 16–512 примеров):

\[ w_{t+1} = w_t - \frac{\eta}{m} \sum_{i \in B_t} \nabla L_i(w_t) \]

Этот подход:

• снижает дисперсию оценки градиента по сравнению с чистым SGD;
• позволяет эффективно использовать векторные операции на GPU/TPU;
• обеспечивает более стабильную сходимость, чем SGD, и более быструю, чем пакетный спуск.

Модификации и улучшения

Импульс (Momentum)

Добавление инерции (импульса) позволяет сгладить колебания и ускорить движение в направлении, где градиент сохраняет знак. Обновление выполняется через накопление экспоненциально скользящего среднего градиентов:

\[ v_{t+1} = \beta v_t + \eta \nabla L_{i_t}(w_t), \quad w_{t+1} = w_t - v_{t+1} \]

где \( \beta \) — коэффициент импульса (обычно 0.9). Метод предложен Борисом Поляком в 1964 году.

Нестеровский импульс (NAG)

Модификация, предложенная Юрием Нестеровым в 1983 году, сначала делает шаг в направлении накопленного импульса, затем вычисляет градиент в новой точке:

\[ w_{t+1} = w_t - \beta v_t - \eta \nabla L_{i_t}(w_t - \beta v_t) \]

Это позволяет «заглядывать вперёд» и корректировать траекторию, что часто даёт более быструю сходимость.

Адаптивные методы

Современные оптимизаторы автоматически подбирают скорость обучения для каждого параметра:

• AdaGrad (Джон Души, 2011): накапливает квадраты градиентов, уменьшая шаг для часто обновляемых параметров. Недостаток — чрезмерное уменьшение шага со временем.
• RMSProp (Джеффри Хинтон, 2012): использует экспоненциально скользящее среднее квадратов градиентов, что решает проблему AdaGrad.
• Adam (Дидерик Кингма, Джимми Ба, 2014): комбинирует импульс и RMSProp, добавляя коррекцию смещения. Стал стандартом для глубокого обучения.
• AdamW (Илья Лощилов, 2017): отделяет регуляризацию L2 от обновления весов, что улучшает обобщающую способность.

Применение

Обучение нейронных сетей

SGD и его модификации (Adam, AdamW, SGD+Momentum) являются основными методами оптимизации в библиотеках TensorFlow, PyTorch, JAX. Они используются для обучения:

• свёрточных нейронных сетей (CNN) для классификации изображений;
• рекуррентных нейронных сетей (RNN, LSTM) для обработки последовательностей;
• трансформеров (BERT, GPT, LLaMA) для задач NLP.

Линейные модели

В задачах логистической регрессии, линейной регрессии и SVM на больших данных SGD позволяет обрабатывать выборки, не помещающиеся в память (out-of-core learning). В библиотеке scikit-learn реализован класс SGDClassifier для бинарной и многоклассовой классификации.

Рекомендательные системы

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

Обработка естественного языка

Модели word2vec (Word2Vec) и GloVe обучаются с использованием SGD на больших корпусах текстов. В частности, метод negative sampling (Милколов и др., 2013) основан на стохастической оценке градиента.

Критика и ограничения

• Чувствительность к скорости обучения. Неправильный выбор \( \eta \) приводит к расходимости или крайне медленной сходимости. Требуется подбор (learning rate scheduling) или использование адаптивных методов.
• Застревание в седловых точках. В невыпуклых задачах (глубокие сети) SGD может долго находиться вблизи седловых точек, где градиент близок к нулю. Импульс и адаптивные методы частично решают эту проблему.
• Необходимость перемешивания данных. Для обеспечения несмещённости оценки градиента данные должны быть случайно перемешаны перед каждой эпохой. В противном случае возможно смещение в сторону последних примеров.
• Отсутствие гарантий для невыпуклых задач. Для глубоких нейронных сетей теоретическая сходимость SGD к глобальному минимуму не доказана, хотя на практике алгоритм часто находит решения с хорошей обобщающей способностью.

Сравнение с другими методами

Интересные факты

• В 2018 году исследователи из MIT показали, что SGD с большим размером мини-батча и фиксированной скоростью обучения может находить более плоские минимумы, которые лучше обобщаются на тестовых данных.
• Алгоритм SGD лежит в основе обучения модели GPT-3 (175 млрд параметров) — обучение заняло несколько месяцев на тысячах GPU.
• В 2020 году группа DeepMind предложила метод «Lookahead» — комбинацию SGD с более медленным обновлением «медленных» весов, что улучшает стабильность.

Источники

• Robbins, H., Monro, S. (1951). «A Stochastic Approximation Method». The Annals of Mathematical Statistics.
• Bottou, L. (2010). «Large-Scale Machine Learning with Stochastic Gradient Descent». Proceedings of COMPSTAT.
• Kingma, D. P., Ba, J. (2014). «Adam: A Method for Stochastic Optimization». arXiv:1412.6980.
• Goodfellow, I., Bengio, Y., Courville, A. (2016). Deep Learning. MIT Press.
• Sutskever, I., Martens, J., Dahl, G., Hinton, G. (2013). «On the importance of initialization and momentum in deep learning». ICML.