Метод стохастического градиентного спуска

Идея метода

Вспомним, что функция потерь в машинном обучении представляет собой эмпирический риск, то есть средние потери по объектам обучающей выборки:

$$L(\mathbf{w}) = \frac{1}{N}\sum_{n=1}^{N}\mathcal{L}(f_{\mathbf{w}}(\mathbf{x}_{n}),\,y_{n})$$

Рассмотрим детальнее метод градиентного спуска с учётом вида функции потерь:

инициализируем $t=0$, а $\mathbf{w}_0$ случайно

пока не выполнено условие остановки:

             $\mathbf{w}:=\mathbf{w}-\varepsilon\nabla_{\mathbf{w}}L(\mathbf{w}) = \mathbf{w}-\varepsilon\frac{1}{N}\sum_{n=1}^N \nabla_{\mathbf{w}}\mathcal{L}(\hat{y}(\mathbf{x}_n),y_n)$

Получается, что на каждом шаге алгоритма необходимо вычислять производные функции потерь на каждом объекте. Это приводит к медленной работе метода, если объектов в обучающей выборке много. При этом, поскольку алгоритм состоит из многих итераций с малым шагом $\varepsilon$, нам совсем не обязательно вычислять точное значение градиента $L(\mathbf{w})$, а достаточно сдвигаться лишь примерно в сторону уменьшения функции.

Идея метода стохастического градиентного спуска (stochastic gradient descent, SGD) заключается в использовании быстро вычислимой аппроксимации эмпирического риска для расчета градиента. Для этого используется приближение средними потерями на $K$ случайных объектах:

$$L(\mathbf{w})=\frac{1}{N}\sum_{n=1}^{N}\mathcal{L}(\mathbf{x}_{n},y_{n}|\mathbf{w})\approx\frac{1}{K}\sum_{n\in I}\mathcal{L}(\mathbf{x}_{n},y_{n}|\mathbf{w})=\tilde{L}(\mathbf{w})$$

где $I=\{n_1,...n_K\}$ - индексы $K$ случайных объектов обучающей выборки, называемых минибатчом (minibatch). Используя эту аппроксимацию, получим метод стохастического градиентного спуска:

инициализируем настраиваемые веса $\mathbf{w}$ случайно

пока не выполнено условие остановки:

             случайно выбрать $K$ объектов $I=\{n_1,...n_K\}$ из $\{1,2,...N\}$

             $\mathbf{w}:=\mathbf{w}-\varepsilon\nabla_{\mathbf{w}}\tilde{L}(\mathbf{w}) = \mathbf{w}-\varepsilon_t\frac{1}{K}\sum_{n\in I} \nabla_{\mathbf{w}}\mathcal{L}(\hat{y}(\mathbf{x}_n),y_n)$

Как видим, одна итерация стохастического градиентного спуска выполняется за $O(K)$ операций, а не за $O(N)$, как в обычном методе градиентного спуска.

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

На практике объекты обучающей выборки переставляются в случайном порядке, а затем извлекаются последовательно по $K$ штук за раз. Однократный проход по всем объектам обучающей выборки называют эпохой (epoch).

Онлайн-обучение

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

Выбор K

Если $K$ велико, а объекты содержат повторяющуюся информацию, то точность аппроксимации будет высокой при более быстрой сходимости по сравнению с методом градиентного спуска.

Интересно, что метод будет сходиться даже при $K=1$. Конечно, оценка эмпирического риска всего по одному объекту будет очень грубой. Однако, поскольку эта оценка является несмещённой (за счёт случайного выбора объекта), метод всё равно будет сходиться, надо лишь использовать более малый шаг обучения $\varepsilon$. Тогда, за увеличенное количество итераций, мы сможем обойти существенную часть объектов выборки и в итоге сместить веса в правильную сторону.

На практике $K$ выбирают таким, чтобы минибатч помещался в память и векторные операции, связанные с его обработкой, производились за один такт параллельных вычислений устройства.

Сходимость

Для сходимости функция потерь должна быть непрерывно-дифференцируемой, выпуклой в окрестности оптимума и удовлетворять условию Липшица (иметь ограниченную производную). Детальнее об условиях сходимости можно прочитать здесь. Важным отличием условий сходимости стохастического градиентного спуска является то, что шаг сходимости должен быть не константой $\varepsilon$, а последовательностью $\varepsilon_t$, стремящейся к нулю в окрестности оптимума.

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

Скорость уменьшения шага для сходимости

Формально метод сходится, если шаг удовлетворяет следующим двум условиям:

$$\begin{aligned} \sum_{t=1}^{+\infty}\varepsilon_{t}=+\infty & \qquad\text{достигаем произвольной то�чки}\\ \sum_{t=1}^{+\infty}\varepsilon_{t}^{2}<+\infty & \qquad\varepsilon_{t}\text{ сходится к нулю достаточно быстро} \end{aligned}$$

Например, этому условию удовлетворяет последовательность

$$\varepsilon_t=\frac{a}{1+bt}, \text{ где $a,b>0$ - гиперпараметры.}$$

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