Ускоренный градиент Нестерова

Материал из MachineLearning.

Версия от 10:28, 25 июня 2026; Arina Pakalova (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Ускоренный градиент Нестерова (англ. Nesterov accelerated gradient, NAG) — семейство оптимальных по порядку итеративных методов первого порядка для решения задач выпуклой оптимизации. Метод обеспечивает достижение нижней оценки сложности для класса гладких выпуклых задач, равной $O(1/k^2)$ , где $k$ — номер итерации^[1].

Содержание

1 Определение и актуальность в теории оптимизации
2 Постановка задачи
3 Описание метода
4 Теоретические свойства и скорость сходимости
5 Литература
6 См. также

Определение и актуальность в теории оптимизации

В середине 1980-х годов Ю. Е. Нестеровым была доказана нижняя оценка скорости сходимости для класса гладких выпуклых задач минимизации, показывающая, что ни один метод первого порядка не может гарантировать скорость сходимости быстрее, чем $O(1/k^2)$ . До этой работы стандартный градиентный спуск обеспечивал лишь скорость $O(1/k)$ .

Ускоренный градиент Нестерова является первым алгоритмом, достигающим этой теоретической нижней границы, что делает его оптимальным в смысле теории вычислительной сложности черного ящика (first-order black-box optimization)^[1]. В дальнейшем концепция «ускорения» была обобщена на широкий класс невыпуклых, вариационных и стохастических задач, став фундаментальным строительным блоком современных алгоритмов машинного обучения (например, алгоритма FISTA)^[1].

Постановка задачи

Рассмотрим задачу безусловной минимизации: $\min_{x \in \mathbb{R}^n} f(x),$ где целевая функция $f: \mathbb{R}^n \to \mathbb{R}$ удовлетворяет следующим условиям:

Выпуклость: для любых $x, y \in \mathbb{R}^n$ выполняется $f(y) \ge f(x) + \langle \nabla f(x), y - x \rangle$ .
Гладкость: градиент функции является липшицевым с константой $L > 0$ , то есть для любых $x, y \in \mathbb{R}^n$ :

$\|\nabla f(x) - \nabla f(y)\| \le L \|x - y\|.$ Эквивалентное условие гладкости: $f(y) \le f(x) + \langle \nabla f(x), y - x \rangle + \frac{L}{2} \|x - y\|^2.$

Пусть $x^*$ — точка минимума функции $f(x)$ , а $f^* = f(x^*)$ — глобальное минимальное значение.

Описание метода

Классический вариант метода (1983 г.) генерирует две последовательности: основную точку $x_k$ и вспомогательную (экстраполированную) точку $y_k$ .

Алгоритм:

Инициализация: $y_0 = x_0 \in \mathbb{R}^n$ .
Итерация $k = 0, 1, 2, \dots$ :

$\begin{cases} x_{k+1} = y_k - \frac{1}{L} \nabla f(y_k), \\ y_{k+1} = x_{k+1} + \frac{k}{k+3} (x_{k+1} - x_k). \end{cases}$ В данном выражении коэффициент $\frac{k}{k+3}$ является частным случаем последовательности $\alpha_k = \frac{2}{k+3}$ . Существуют эквивалентные формы записи через трехточечный рекуррентный процесс, однако приведенная форма наиболее наглядно демонстрирует механизм «заглядывания вперед» (look-ahead), когда градиент вычисляется не в текущей аппроксимации $x_k$ , а в экстраполированной точке $y_k$ .

Теоретические свойства и скорость сходимости

Основной теоретический результат для метода формулируется с помощью техники оценивающих последовательностей (estimate sequences)^[1].

Определение. Последовательность функций $\phi_k: \mathbb{R}^n \to \mathbb{R}$ называется оценивающей последовательностью для функции $f$ , если выполняются два условия:

$\phi_k(x) \le f(x)$ для всех $x \in \mathbb{R}^n$ и всех $k \ge 0$ .
Существует такая последовательность $\{y_k\}$ , что $f(y_k) \le \phi_k(x^*)$ для всех $k \ge 0$ .

Теорема (О скорости сходимости для гладких выпуклых функций)

Пусть функция $f$ выпукла и имеет липшицев градиент с константой $L$ . Тогда для последовательности $\{y_k\}$ , генерируемой ускоренным градиентом Нестерова, выполняется: $f(y_k) - f^* \le \frac{2L \|x_0 - x^*\|^2}{(k+1)^2}.$

Доказательство. Рассмотрим оценивающую последовательность вида: $\phi_{k+1}(x) = (1 - \alpha_{k+1})\phi_k(x) + \alpha_{k+1} \left[ f(x_{k+1}) + \langle \nabla f(x_{k+1}), x - x_{k+1} \rangle + \frac{L}{2}\|x - x_{k+1}\|^2 \right],$ где $\alpha_0 = 1$ и $\alpha_{k+1} = \frac{2}{k+3}$ . В качестве начальной функции выберем $\phi_0(x) = f(x_0) + \langle \nabla f(x_0), x - x_0 \rangle + \frac{L}{2}\|x - x_0\|^2$ .

Утверждение 1: $\phi_k(x) \le f(x)$ для всех $x$ . Докажем по индукции.

База: $\phi_0(x)$ является глобальной верхней оценкой для $f(x)$ в силу условия гладкости.
Шаг индукции: Пусть $\phi_k(x) \le f(x)$ . По условию гладкости, выражение в квадратных скобках также является верхней оценкой $f(x)$ . Так как $(1-\alpha_{k+1}) \ge 0$ и $\alpha_{k+1} \ge 0$ , их выпуклая комбинация $\phi_{k+1}(x)$ также не превышает $f(x)$ .

Утверждение 2: Выполнение условия $f(y_k) \le \phi_k(x^*)$ . Найдем минимум правой части выражения для $\phi_{k+1}(x)$ . Точка минимума квадратичной функции в скобках есть $x_{k+1}$ . Значение в этой точке равно $f(x_{k+1})$ . Следовательно, минимальное значение $\phi_{k+1}(x)$ достигается в точке: $y_{k+1} = \arg\min_{x} \phi_{k+1}(x) = (1-\alpha_{k+1})y_k + \alpha_{k+1} x_{k+1}.$ Подставляя $x_{k+1} = y_k - \frac{1}{L}\nabla f(y_k)$ и выражение для $\alpha_{k+1}$ , после алгебраических преобразований получаем рекуррентное соотношение $y_{k+1} = x_{k+1} + \frac{k}{k+3}(x_{k+1} - x_k)$ , что в точности совпадает с алгоритмом. Оценим значение: $\phi_{k+1}(y_{k+1}) = (1-\alpha_{k+1})\phi_k(y_{k+1}) + \alpha_{k+1} f(x_{k+1}) \le (1-\alpha_{k+1})\phi_k(x^*) + \alpha_{k+1} \left[ f(y_k) - \frac{1}{2L}\|\nabla f(y_k)\|^2 \right].$ Используя предположение индукции $f(y_k) \le \phi_k(x^*)$ и неравенство Коши-Буняковского-Шварца для градиента, можно показать, что $\phi_{k+1}(y_{k+1}) \le \phi_k(x^*) - \frac{\alpha_{k+1}}{2L}\|\nabla f(y_k)\|^2 \le \phi_k(x^*)$ . Отсюда $f(y_{k+1}) \le \phi_{k+1}(x^*)$ .

Утверждение 3: Оценка скорости. Введем вспомогательную последовательность $A_k = \alpha_k \prod_{i=1}^{k-1} (1-\alpha_i)$ . Можно показать, что $A_k = \frac{2}{(k+1)(k+2)}$ . Из разложения оценивающей последовательности в точке $x^*$ следует: $A_{k+1} (f(y_{k+1}) - f^*) \le \phi_0(x^*) - f^* \le \frac{L}{2}\|x_0 - x^*\|^2.$ Подставляя явный вид $A_{k+1}$ , получаем искомую оценку $f(y_k) - f^* \le \frac{2L \|x_0 - x^*\|^2}{(k+1)^2}$ . $\blacksquare$

Теорема (О скорости сходимости для сильно выпуклых функций)

Если функция $f$ является сильно выпуклой с параметром $\mu > 0$ , то метод модифицируется путем замены коэффициента экстраполяции на константу: $\beta = \frac{\sqrt{L} - \sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}}.$ Тогда скорость сходимости становится линейной: $f(y_k) - f^* \le \left( \frac{\sqrt{L} - \sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}} \right)^{2k} (f(y_0) - f^*).$

Свойства метода

Оптимальность: Метод достигает теоретической нижней границы $O(1/k^2)$ для класса гладких выпуклых задач. Изменение константы шага или коэффициента экстраполяции не может улучшить асимптотику по порядку.
Немонотонность: В отличие от классического градиентного спуска, последовательность значений целевой функции $\{f(y_k)\}$ не является монотонно убывающей. Допускаются локальные возрастания функции на отдельных итерациях.
Чувствительность к шуму: Метод критически зависит от точности вычисления градиента. При добавлении стохастического шума (в SGD) ускорение может быть утрачено без применения специальных техник стабилизации (например, variance reduction).
Зависимость от константы Липшица: Практическое применение метода требует знания или оценки константы $L$ . Слишком завышенная оценка приводит к замедлению сходимости, заниженная — к расходимости алгоритма.

Литература

См. также

Статья написана с использованием LLM и проверена участником Arina Pakalova 14:28, 25 июня 2026 (MSD)

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%81%D0%BA%D0%BE%D1%80%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82_%D0%9D%D0%B5%D1%81%D1%82%D0%B5%D1%80%D0%BE%D0%B2%D0%B0»