# 2. GD, SGD, momentum, RMSProp и Adam

> Оптимизаторы различаются тем, какие данные используют на шаге и как преобразуют историю градиентов.

## Мотивация

Полный градиент точен, но дорог на миллионах объектов. Стохастический градиент дешёв, но шумен. Momentum сглаживает направление, RMSProp адаптирует масштаб координат, Adam сочетает обе идеи. Выбор шага и корректная реализация зачастую важнее названия оптимизатора.

## Интуиция

GD измеряет наклон по всей выборке. SGD использует один случайный объект, mini-batch — компромисс, хорошо использующий векторные вычисления. Шум mini-batch мешает точной сходимости, но ускоряет ранний прогресс. Momentum накапливает «скорость». RMSProp делит шаг на корень из недавних квадратов градиента. Adam ведёт экспоненциальные средние градиента и его квадрата и исправляет их начальное смещение к нулю.

## Определения и обозначения

Пусть \(L(\boldsymbol\theta)=n^{-1}\sum_i\ell_i(\boldsymbol\theta)\), итерация \(t\), learning rate \(\eta_t>0\), mini-batch \(\mathcal B_t\) размера \(m\):

\[
\mathbf g_t=\frac1m\sum_{i\in\mathcal B_t}\nabla\ell_i(\boldsymbol\theta_t).
\]

При равномерной выборке \(\mathbb E[\mathbf g_t\mid\boldsymbol\theta_t]=\nabla L(\boldsymbol\theta_t)\). Эпоха — обработка примерно \(n\) примеров.

## Вывод алгоритмов

**GD/SGD/mini-batch:**

\[
\boldsymbol\theta_{t+1}=\boldsymbol\theta_t-\eta_t\mathbf g_t.
\]

GD берёт \(m=n\), классический SGD — \(m=1\). Для квадратичной \(L(\theta)=a\theta^2/2\):

\[
\theta_{t+1}=(1-\eta a)\theta_t.
\]

Сходимость требует \(|1-\eta a|<1\), то есть \(0<\eta<2/a\). В многомерной квадратичной задаче безопасный постоянный шаг связан с \(2/\lambda_{\max}(\mathbf H)\).

**Momentum** в одной распространённой записи:

\[
\mathbf v_t=\beta\mathbf v_{t-1}+(1-\beta)\mathbf g_t,\qquad
\boldsymbol\theta_{t+1}=\boldsymbol\theta_t-\eta\mathbf v_t.
\]

Некоторые библиотеки не используют множитель \(1-\beta\); тогда эффективный масштаб \(\eta\) другой.

**RMSProp:**

\[
\mathbf s_t=\rho\mathbf s_{t-1}+(1-\rho)\mathbf g_t\odot\mathbf g_t,
\qquad
\boldsymbol\theta_{t+1}=\boldsymbol\theta_t-
\eta\frac{\mathbf g_t}{\sqrt{\mathbf s_t}+\varepsilon}.
\]

**Adam:**

\[
\begin{aligned}
\mathbf m_t&=\beta_1\mathbf m_{t-1}+(1-\beta_1)\mathbf g_t,\\
\mathbf v_t&=\beta_2\mathbf v_{t-1}+(1-\beta_2)\mathbf g_t^2,\\
\hat{\mathbf m}_t&=\mathbf m_t/(1-\beta_1^t),\\
\hat{\mathbf v}_t&=\mathbf v_t/(1-\beta_2^t),\\
\boldsymbol\theta_{t+1}
&=\boldsymbol\theta_t-\eta\hat{\mathbf m}_t/
(\sqrt{\hat{\mathbf v}_t}+\varepsilon).
\end{aligned}
\]

Операции во второй момент и делении поэлементные. Bias correction нужен, потому что нулевая инициализация занижает ранние моменты.

## Разобранный пример

**Дано.** \(L(\theta)=\frac12(\theta-3)^2\), \(\theta_0=0\), \(\eta=0{,}5\).

**Решение.** \(g_t=\theta_t-3\). GD:
\(\theta_1=0-0{,}5(-3)=1{,}5\);
\(\theta_2=1{,}5-0{,}5(-1{,}5)=2{,}25\);
\(\theta_3=2{,}625\).
Ошибка каждый шаг умножается на \(1-\eta=0{,}5\), поэтому стремится к нулю геометрически.

**Проверка.** При \(\eta=2\) параметры чередуются между 0 и 6 и не сходятся; при \(\eta>2\) расходятся.

## Связь с Python и NumPy

```python
import numpy as np

rng = np.random.default_rng(42)
X = rng.normal(size=(200, 2))
true_w = np.array([2.0, -1.0])
y = X @ true_w + rng.normal(scale=0.2, size=200)
w = np.zeros(2)
m = np.zeros(2)
v = np.zeros(2)
beta1, beta2, lr, eps = 0.9, 0.999, 0.05, 1e-8

for t in range(1, 501):
    idx = rng.choice(len(y), size=32, replace=False)
    residual = X[idx] @ w - y[idx]
    g = X[idx].T @ residual / len(idx)
    m = beta1 * m + (1 - beta1) * g
    v = beta2 * v + (1 - beta2) * (g * g)
    m_hat = m / (1 - beta1 ** t)
    v_hat = v / (1 - beta2 ** t)
    w -= lr * m_hat / (np.sqrt(v_hat) + eps)

print("weights:", w, "full loss:", np.mean((X @ w - y) ** 2) / 2)
```

Перемешивание и seed делают стохастический эксперимент контролируемым. Loss для мониторинга лучше считать отдельно на train и validation.

## Практический выбор

Начните с масштабирования признаков и baseline. Для гладких небольших выпуклых задач полный GD или L-BFGS может быть эффективнее. Mini-batch выбирают по памяти и пропускной способности устройства. SGD с momentum часто даёт хорошую обобщающую способность; Adam быстро получает рабочий результат при разном масштабе градиентов. Learning-rate schedule (warmup, step decay, cosine) обычно важен. Gradient clipping ограничивает норму при взрывающихся градиентах, но не лечит первопричину.

## Типичные ошибки и ограничения

- Сравнивать оптимизаторы при разных бюджетах вычислений и без настройки \(\eta\).
- Считать Adam гарантированно лучшим или сходящимся во всех задачах.
- Забывать bias correction, \(\varepsilon\) или поэлементный квадрат.
- Использовать один случайный порядок данных и делать сильный вывод.
- Путать batch size с числом эпох.
- Оценивать качество только train loss: оптимизация и обобщение — разные задачи.
- Смешивать L2 в loss и decoupled weight decay: AdamW обновляет decay отдельно.

## Краткое резюме

- Mini-batch даёт несмещённый, но шумный градиент.
- Learning rate управляет устойчивостью и скоростью.
- Momentum усредняет направление, RMSProp — квадрат масштаба, Adam — оба момента.
- Оптимизатор нужно сравнивать по validation-метрике и вычислительному бюджету.

## Связанные материалы

- Практика: [`../assignments/01_gradient_descent.md`](../assignments/01_gradient_descent.md).
- Практика: [`../assignments/02_logistic_from_scratch.md`](../assignments/02_logistic_from_scratch.md).

- Поверхности: [`01_derivatives_and_loss_surfaces.md`](01_derivatives_and_loss_surfaces.md).
- Следующая глава: [`03_regularization_bias_variance.md`](03_regularization_bias_variance.md).
- Численная устойчивость: [`../../../common/foundations/numerical_stability.md`](../../../common/foundations/numerical_stability.md).
- Термины: [`glossary.md`](glossary.md).