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

Логистическая регрессия на ImageNet-1k: 1.28M примеров, 1000 классов. Full GD - одна итерация = 4 секунды на A100. SGD с batch 256 - 0.0008 секунды. Та же математика, скорость отличается в 5000 раз. Почему оба сходятся - и какой ценой? Ответ - в трёх скоростях: $O(1/T)$ для convex L-smooth, $(1-1/\kappa)^T$ для strongly convex, $O(1/T^2)$ для Nesterov-momentum. Каждая степень - результат конкретного предположения о геометрии $f$. Снять предположение - сходимость замедлится. Усилить - ускорится. Знание этих скоростей - язык, на котором инженеры выбирают между SGD, Adam, AdamW и решают, нужен ли warmup.

• **SGD vs Full GD на ImageNet:** SGD-итерация в 5000 раз дешевле, и в overparametrized режиме сходится так же линейно - объяснимо через NTK-теорию (Jacot 2018)
• **Adam в трансформерах** ($O(B \cdot d)$ memory, per-coordinate adaptive): побеждает SGD когда градиенты разных слоёв на 2-3 порядка по масштабу - effective per-coord $\kappa = O(1)$
• **Edge of stability** (Cohen et al, ICLR 2021): практический lr нарушает $\eta < 2/L$, но loss падает за счёт self-stabilization landscape'а - empirical факт за пределами классической теории
• **Warmup в BERT/GPT:** lr линейно растёт первые 10000 шагов не для осторожности, а потому что $\lambda_{\max}(\nabla^2 f)$ растёт до $2/\eta$ - ранний удар вызвал бы NaN

Предварительные знания

• KKT-условия
• Двойственность Лагранжа

L-smoothness и базовая O(1/T) сходимость

Логистическая регрессия на ImageNet-1k: 1.28 миллиона примеров, 1000 классов. Full GD - одна итерация считает градиент по всему датасету: 4 секунды на A100. SGD с batch 256 - 0.0008 секунды. Та же математика, разница в скорости в 5000 раз. Вопрос не в том, какой метод 'правильный'. Вопрос в том, почему оба сходятся - и какой ценой.

Сходимость GD - это не про 'когда-нибудь дойдёт'. Это про **скорость** в конкретных степенях $T$: $1/T$, $1/T^2$, $(1-1/\kappa)^T$. Каждая степень - результат конкретного предположения о геометрии $f$. Снять предположение - сходимость замедлится. Усилить - ускорится. И есть нижние границы: ниже которых не пробить даже теоретически.

**L-smoothness** (Lipschitz-непрерывность градиента): $$\|\nabla f(x) - \nabla f(y)\| \leq L \cdot \|x - y\|$$ Эквивалентная форма (для дважды дифференцируемых $f$): $\nabla^2 f(x) \preceq L \cdot I$ - все собственные значения гессиана не превосходят $L$. **Descent lemma** - прямое следствие: $$f(y) \leq f(x) + \nabla f(x)^T (y - x) + \frac{L}{2} \|y - x\|^2$$ Квадратичная **верхняя** граница, которая всегда лежит над $f$. GD минимизирует именно эту параболу: при $\eta = 1/L$ шаг $x_{k+1} = x_k - \frac{1}{L} \nabla f(x_k)$ - вершина квадратичной аппроксимации.

Подстановка $y = x_k - \eta \nabla f(x_k)$ в descent lemma при $\eta = 1/L$ даёт ключевое неравенство: $$f(x_{k+1}) \leq f(x_k) - \frac{1}{2L} \|\nabla f(x_k)\|^2$$ Каждый шаг гарантированно уменьшает $f$ на величину, пропорциональную квадрату нормы градиента. Дальше - стандартный telescoping: суммируя по $k = 0, \ldots, T-1$ и используя выпуклость, получаем итоговую оценку.

**Теорема (convex + L-smooth):** при $\eta = 1/L$ градиентный спуск даёт $$f(x_T) - f(x^*) \leq \frac{L \|x_0 - x^*\|^2}{2T} = O(1/T)$$ Это **сублинейная** сходимость. Чтобы уменьшить ошибку в 10 раз - нужно в 10 раз больше итераций. Интерпретация: в отсутствие выпуклости 'снизу' (только сверху $L$-липшицевость) GD идёт по квадратичной 'ловушке' и не может ускориться. Каждая итерация даёт фиксированный прогресс, но прогресс **не накапливается экспоненциально**.

**Связь с PyTorch:** `torch.nn.Linear + MSELoss` без регуляризации - это convex L-smooth задача с $L = \lambda_{\max}(X^T X)$. По умолчанию `torch.optim.SGD(lr=1e-3)` берёт $\eta$ намного меньше $1/L$ - это запас прочности на случай 'плохого' batch'а в стохастическом режиме. Точная константа $L$ для глубоких сетей не вычислима за разумное время; на практике lr подбирается line search'ем или grid-овой проверкой.

Strongly convex и линейная сходимость

L-smoothness ограничивает функцию **сверху** квадратичной параболой. Strong convexity ограничивает её **снизу** - той же параболой, но с другой константой. Зажатая с двух сторон $f$ ведёт себя почти как сама квадратичная функция, и GD на ней разгоняется до экспоненциальной скорости.

**$\mu$-strong convexity:** для всех $x, y$ $$f(y) \geq f(x) + \nabla f(x)^T (y - x) + \frac{\mu}{2} \|y - x\|^2$$ Эквивалентно (для дважды дифференцируемых): $\nabla^2 f(x) \succeq \mu I$ - наименьшее собственное значение гессиана не меньше $\mu > 0$. **Совмещая с L-smoothness** ($\mu I \preceq \nabla^2 f \preceq L I$): $$\|x_{k+1} - x^*\|^2 \leq \left(1 - \frac{\mu}{L}\right)^k \|x_0 - x^*\|^2$$ и в терминах функционала: $$f(x_k) - f(x^*) \leq \left(1 - \frac{\mu}{L}\right)^k \cdot [f(x_0) - f(x^*)]$$ Это **линейная сходимость** (в учебниках оптимизации - перевод 'linear' = 'геометрическая прогрессия в логе').

Ключевая величина - **число обусловленности** $\kappa = L / \mu \geq 1$. Чем больше $\kappa$, тем 'вытянутее' эллипсы уровня и тем хуже работает GD. Для одной декады точности (уменьшить ошибку в 10 раз) нужно $\kappa \ln 10 \approx 2.3 \kappa$ итераций.

**Condition number $\kappa = L / \mu$ - стоимость точности:** - $\kappa = 1$ - идеальная сферическая геометрия, GD сходится за $O(\log(1/\varepsilon))$ - $\kappa = 100$ - типичная регуляризованная логистическая регрессия, $\sim 230$ итераций на декаду - $\kappa = 10^6$ - плохо обусловленная задача, $\sim 2.3 \cdot 10^6$ итераций - $\kappa = \infty$ - не strongly convex (flat directions), линейной сходимости нет L2-регуляризация $f(x) + \frac{\lambda}{2} \|x\|^2$ принудительно делает задачу $\lambda$-strongly convex - именно поэтому weight decay в нейросетях не только борется с переобучением, но и стабилизирует оптимизацию: $\mu \geq \lambda$, $\kappa \leq L/\lambda$.

**Где встречается на практике:** - **Ridge regression** ($\lambda \geq 0.01$) - $\kappa$ контролируется явно через $\lambda$, GD сходится быстро. - **Logistic regression без регуляризации** на разделимых данных - не strongly convex, $\kappa = \infty$, GD расходится по нормам коэффициентов (но loss всё равно стремится к нулю). - **Глубокие нейросети** - локально не strongly convex почти нигде; $\mu$ может быть отрицательным (saddle points). Поэтому SGD, не GD.

Nesterov acceleration и нижняя граница O(1/T^2)

1983 год. Юрий Нестеров публикует в советском журнале 'Доклады АН СССР' схему с двумя последовательностями точек, которая ускоряет GD с $O(1/T)$ до $O(1/T^2)$. Текст на русском, в обычном GD-сообществе никто его не читает. Через 20 лет paper переоткрывают на Западе - и Nesterov momentum входит в каждый ML-фреймворк под именами `nesterov=True` и `Heavy Ball`.

**Nesterov accelerated gradient (NAG)** - две связанные последовательности: $$y_k = x_k + \beta_k (x_k - x_{k-1})$$ $$x_{k+1} = y_k - \eta \nabla f(y_k)$$ Градиент берётся **в точке-предсказании** $y_k$, не в текущей $x_k$. Параметр $\beta_k = (k-1)/(k+2)$ - momentum, накапливающий 'инерцию' предыдущих шагов. **Скорость сходимости (convex L-smooth):** $$f(x_T) - f(x^*) \leq \frac{2 L \|x_0 - x^*\|^2}{(T+1)^2} = O(1/T^2)$$ **Для $\mu$-strongly convex** с $\beta = (\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1)$: $$f(x_T) - f(x^*) \leq \left(1 - \frac{1}{\sqrt{\kappa}}\right)^T [f(x_0) - f(x^*)]$$ Корень из $\kappa$, не $\kappa$. Для $\kappa = 10^4$ обычный GD требует $\sim 23000$ итераций на декаду, NAG - $\sim 230$. Разница в 100 раз.

**Heavy Ball Поляка (1964)** - идейный предок: $x_{k+1} = x_k - \eta \nabla f(x_k) + \beta (x_k - x_{k-1})$. Аналогия с механикой: шар с массой катится по склону - инерция переносит его через мелкие минимумы и выравнивает зигзаги в долинах. Однако Heavy Ball **не достигает $O(1/T^2)$** для произвольных convex L-smooth функций (только для квадратичных). NAG - другая, более тонкая схема: градиент считается **в смещённой точке**, что меняет асимптотику.

**Нижняя граница Нестерова (1983):** для любого алгоритма, использующего только информацию первого порядка ($\nabla f$), на классе convex L-smooth функций существует $f$, для которой $$f(x_T) - f(x^*) \geq \frac{3 L \|x_0 - x^*\|^2}{32 (T+1)^2}$$ То есть $O(1/T^2)$ - **физический предел** для first-order методов без дополнительной структуры. Никакой комбинации momentum, learning rate, restart-ов не пробить $1/T^2$. Чтобы пробить - нужна вторая производная (Newton, $O(\log \log 1/\varepsilon)$ локально) либо специальная структура (separable, sparse, graph).

**Связь с ODE и физикой:** в пределе $\eta \to 0$ Heavy Ball сходится к ОДУ $$\ddot{x} + \gamma \dot{x} + \nabla f(x) = 0$$ - демпфированное движение в потенциале $f$. NAG соответствует ОДУ с **переменным затуханием** $\gamma(t) = 3/t$ (Su-Boyd-Candès 2014). Это объясняет, почему NAG ведёт себя 'умнее': коэффициент трения подстраивается во времени, и инерция не разгоняется до катастрофы.

Reality check: SGD, Adam и edge of stability

Вся теория выше предполагает: функция выпуклая, гладкая, существует $L$, $\mu$, шаг подобран ровно $1/L$. Глубокие нейросети нарушают каждое из этих предположений. И всё равно учатся. Это не магия и не противоречие - это очень аккуратная инженерия поверх теории, которая 'почти' применима.

**Что 'почти' остаётся в нейросетях:** - **Overparametrization** (параметров больше, чем примеров): loss landscape вокруг любой точки локально близок к выпуклому. Эмпирически - линейная сходимость SGD к нулевому training loss. - **NTK-режим (Neural Tangent Kernel, Jacot 2018):** при бесконечной ширине сети динамика SGD эквивалентна kernel regression - чисто convex задаче с известным $\kappa$. - **Adam = per-coordinate adaptive learning rate:** на координатах с большим $|\nabla|$ берётся маленький шаг, на маленьких - большой. Эффект - выравнивание $\kappa$ по координатам, **per-coordinate condition number** становится $O(1)$. - **L2 / weight decay** (`AdamW`, Loshchilov & Hutter 2017) - принудительная strong convexity вокруг нуля.

**Cohen et al, ICLR 2021 - 'Edge of Stability'.** Эмпирически: при стандартном lr (без warmup) GD на нейросетях ведёт себя так. Сначала максимальное собственное значение гессиана $\lambda_{\max}$ растёт. Доходит до $2/\eta$. И **застывает там** - GD начинает прыгать через минимум, но не расходится. Loss продолжает падать в среднем.

**Что нарушает классическую теорию в edge of stability:** - Условие сходимости GD на квадратичной задаче: $\eta < 2/L$. На EoS $\eta L_{\text{eff}} = 2$ - на самой границе. - Descent lemma не работает: $f(x_{k+1})$ может быть **больше** $f(x_k)$ на отдельных шагах. - Loss всё равно убывает в среднем за счёт неклассического механизма ('progressive sharpening + self-stabilization'). **Практическое следствие:** lr warmup (Loshchilov 2017, BERT, GPT) - не для 'осторожности', а для того, чтобы $\lambda_{\max}$ дойдя до $2/\eta$ не вызывал NaN на ранних шагах.

Ключевые идеи

• **L-smoothness** ($\|\nabla f(x) - \nabla f(y)\| \leq L\|x-y\|$) + descent lemma - основа любой оценки скорости GD
• **Convex + L-smooth:** $\eta = 1/L$ даёт $O(1/T)$ - сублинейная сходимость без strong convexity
• **Strongly convex** ($\mu I \preceq \nabla^2 f \preceq L I$): линейная сходимость $(1-1/\kappa)^T$ с condition number $\kappa = L/\mu$
• **Nesterov accelerated gradient:** $O(1/T^2)$ для convex L-smooth, $(1-1/\sqrt{\kappa})^T$ для strongly convex - физический предел first-order методов
• **Reality в нейросетях:** SGD вместо GD, Adam/AdamW per-coordinate adaptive, edge of stability нарушает $\eta < 2/L$, но landscape self-stabilizes

Что дальше

Сходимость GD - база для всего семейства методов первого порядка. Дальше - расширения и адаптации:

• Проксимальные методы — ISTA/FISTA расширяют GD на негладкие задачи (LASSO) с теми же скоростями $O(1/T)$ и $O(1/T^2)$
• Gradient Descent в ML — SGD, mini-batch, momentum, Adam - инженерные адаптации convex теории под нейросети
• Градиент — Объект, без которого вся теория не существует - и условия первого порядка $\nabla f = 0$

Вопросы для размышления

• Логистическая регрессия с L2-регуляризацией $\lambda = 0.01$ на $n = 10^6$ примерах. Как оценить количество SGD-итераций до сходимости через $\kappa$ и Nesterov-rate? Где теория ломается на практике?
• В overparametrized нейросети SGD сходится линейно к нулевому training loss - но landscape невыпуклый. Какое предположение convex теории здесь 'почти' выполнено и почему?
• Heavy Ball Поляка работает быстрее GD на квадратичной задаче, но не достигает $O(1/T^2)$ для общих convex L-smooth. Что именно делает Nesterov по-другому, и почему этого хватает для оптимальности?

Связанные уроки

• cvx-04 — Двойственность Лагранжа - база для понимания методов
• cvx-05 — KKT-условия определяют, куда сходится GD при ограничениях
• cvx-07 — Проксимальные методы расширяют GD на негладкие задачи
• ml-09-gradient-descent — SGD на нейросетях - инженерное продолжение convex GD
• calc-19-gradient — Сам объект - градиент - и условия первого порядка