Градиентный спуск и ускорение Нестерова

Зачем нужны алгоритмы первого порядка?

Методы второго порядка (метод Ньютона) очень быстрые, но требуют вычисления и обращения матрицы Гессе — O(n³) операций за шаг. При n = 10⁶ параметров (нейросеть среднего размера) это просто невозможно. Методы первого порядка используют только градиент — O(n) операций. Они медленнее на итерацию, но каждая итерация дёшевая, что делает их незаменимыми для задач большой размерности.

Градиентный спуск: базовый алгоритм

Идея проста: двигаемся в направлении наибольшего убывания функции.

x^{k+1} = x^k − α ∇f(x^k)

Здесь α > 0 — размер шага (learning rate). При слишком большом α — алгоритм расходится. При слишком малом — очень медленная сходимость.

Класс L-гладких функций: f называется L-гладкой, если ‖∇f(x) − ∇f(y)‖ ≤ L‖x − y‖ для всех x, y. Константа L — «степень гладкости» (наибольшее собственное значение матрицы Гессе).

Теорема о сходимости: для выпуклой L-гладкой f с шагом α = 1/L:

f(x^k) − f* ≤ L‖x⁰ − x*‖² / (2k)

Это скорость O(1/k): чтобы уменьшить ошибку вдвое, нужно удвоить число итераций.

Для μ-сильно выпуклых функций (все собственные значения ∇²f ≥ μ > 0):

f(x^k) − f* ≤ (1 − μ/L)^k · (f(x⁰) − f*)

Это линейная (экспоненциальная) сходимость! Число κ = L/μ — «число обусловленности» задачи. При κ = 1 сходимость мгновенная; при κ = 1000 нужно ~4000 итераций для 4 знаков точности.

Ускорение Нестерова (1983)

Юрий Нестеров обнаружил удивительный факт: добавив «инерцию» к градиентному спуску, можно вдвое увеличить скорость сходимости без увеличения стоимости одной итерации.

Алгоритм Нестерова (NAG):

y^{k+1} = x^k − α ∇f(x^k) (шаг градиента) x^{k+1} = y^{k+1} + βₖ(y^{k+1} − y^k) (момент инерции)

где βₖ = (k−1)/(k+2) — «моментный» коэффициент, который растёт к 1.

Скорость сходимости: O(1/k²) — вдвое быстрее градиентного спуска! Это теоретически оптимально для методов первого порядка (нижняя оценка Нестерова).

Физический смысл: «инерция» не даёт застрять в «ущельях» — местах с большим κ. Шарик, катящийся с инерцией, «перелетает» узкое дно ущелья и останавливается ближе к минимуму.

Полный разбор примера

Задача: минимизировать f(x) = (1/2)(x₁² + 100x₂²) — вытянутая парабола с κ = 100.

Градиентный спуск с α = 1/L = 1/100:

x^{k+1} = x^k − (1/100)(x₁^k, 100x₂^k) = (x₁^k(1 − 1/100), x₂^k(1 − 1))

По x₂ мгновенное обнуление, по x₁ медленное: x₁^k = (99/100)^k x₁⁰. После 1000 итераций: (0.99)^{1000} ≈ 0.000045 → примерно 4-5 значимых цифр.

Нестеров: сходится за ~20√κ ≈ 200 итераций вместо 1000. Это 5-кратное ускорение при κ = 100.

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

Для задач машинного обучения: f(x) = (1/N) Σᵢ fᵢ(x). При N = 10⁶ вычисление полного градиента стоит O(N). SGD использует случайный подвыборку:

x^{k+1} = x^k − αₖ ∇fᵢ(x^k), где i выбирается случайно

Стоимость итерации: O(1) вместо O(N). Цена: «шум» в оценке градиента → нельзя использовать фиксированный шаг.

Скорость: O(1/√k) для выпуклых, O(1/k) для сильно выпуклых (при правильном затухании шага).

Адаптивные методы: Adam, RMSProp, AdaGrad — масштабируют шаг покоординатно. В глубоком обучении Adam почти всегда лучше SGD с фиксированным шагом.

Применения в машинном обучении

Вся современная нейросетевая оптимизация — это варианты SGD с моментом. GPT-4 обучался с Adam на 100+ миллиардах параметров. Ускорение Нестерова используется при обучении физических моделей, задачах сжатия, рекомендательных систем. Понимание теоретической скорости сходимости позволяет выбрать правильный алгоритм и настроить гиперпараметры.

Связь с современными библиотеками

В практике машинного обучения алгоритмы первого порядка реализованы в специализированных библиотеках: PyTorch (torch.optim.SGD, Adam, AdamW), TensorFlow (tf.keras.optimizers), JAX (optax). Все они построены вокруг градиентных методов, расширенных адаптивными шагами, моментом и нормализацией. Adam (Kingma & Ba, 2014) поддерживает экспоненциально сглаженные оценки первого и второго моментов градиента — этим он автоматически адаптирует шаг для каждой координаты, что критично при работе с разреженными или плохо обусловленными задачами. Для очень больших моделей (LLM с миллиардами параметров) применяются распределённые версии: ZeRO, FSDP, которые шардируют состояние оптимизатора между GPU.

Сравнение скорости сходимости

В выпуклой задаче:

Градиентный спуск: O(1/k) для гладких функций, O(1/√k) для негладких
Ускоренный (Нестеров): O(1/k²) — теоретический оптимум для гладких выпуклых задач
Прокс-методы: O(1/k) или O(1/k²) с ускорением (FISTA)
Стохастический градиентный спуск (SGD): O(1/√k) для выпуклых, O(1/k) с усреднением

Этот порядок сходимости определяет, сколько итераций нужно для достижения заданной точности ε: для O(1/k) нужно ~1/ε итераций, для O(1/k²) — лишь ~1/√ε. Разница колоссальная при ε = 10⁻⁶: 10⁶ против 10³ итераций.