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

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

(Различия между версиями)
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
{{well|Статья написана с использованием LLM '''GLM-5-Turbo''' и проверена участником [[Участник:Arina Pakalova|Arina Pakalova]] 14:54, 25 июня 2026 (MSD)}}
{{well|Статья написана с использованием LLM '''GLM-5-Turbo''' и проверена участником [[Участник:Arina Pakalova|Arina Pakalova]] 14:54, 25 июня 2026 (MSD)}}
-
'''Ускоренный градиент Нестерова''' (англ. ''Nesterov accelerated gradient'', NAG) — семейство оптимальных по порядку итеративных методов первого порядка для решения задач [[Выпуклая оптимизация|выпуклой оптимизации]]. Метод обеспечивает достижение нижней оценки сложности для класса гладких выпуклых задач, равной <tex>O(1/k^2)</tex>, где <tex>k</tex> — номер итерации<ref name="Nesterov1983">Нестеров Ю. Е. Метод решения задачи выпуклого программирования со скоростью сходимости <tex>O(1/k^2)</tex> // Доклады Академии Наук. — 1983. — Т. 269, № 3. — С. 543–547.</ref>.
+
'''Ускоренный градиент Нестерова''' (англ. ''Nesterov accelerated gradient'', NAG) — семейство оптимальных по порядку итеративных методов первого порядка для решения задач [[Выпуклая оптимизация|выпуклой оптимизации]]. Метод обеспечивает достижение нижней оценки сложности для класса гладких выпуклых задач, равной <tex>O(1/k^2)</tex>, где <tex>k</tex> — номер итерации<ref name="Nesterov1983">Нестеров Ю. Е. Метод решения задачи выпуклого программирования со скоростью сходимости <tex>O(1/k^2)</tex> // Доклады Академии Наук. — 1983. — Т. 269, № 3.</ref>.
== Определение и актуальность в теории оптимизации ==
== Определение и актуальность в теории оптимизации ==
В середине 1980-х годов Ю. Е. Нестеровым была доказана нижняя оценка скорости сходимости для класса гладких выпуклых задач минимизации, показывающая, что ни один метод первого порядка не может гарантировать скорость сходимости быстрее, чем <tex>O(1/k^2)</tex>. До этой работы стандартный [[Градиентный спуск|градиентный спуск]] обеспечивал лишь скорость <tex>O(1/k)</tex>.
В середине 1980-х годов Ю. Е. Нестеровым была доказана нижняя оценка скорости сходимости для класса гладких выпуклых задач минимизации, показывающая, что ни один метод первого порядка не может гарантировать скорость сходимости быстрее, чем <tex>O(1/k^2)</tex>. До этой работы стандартный [[Градиентный спуск|градиентный спуск]] обеспечивал лишь скорость <tex>O(1/k)</tex>.
-
Ускоренный градиент Нестерова является первым алгоритмом, достигающим этой теоретической нижней границы, что делает его '''оптимальным''' в смысле теории вычислительной сложности черного ящика (first-order black-box optimization)<ref name="Bubeck2015">Bubeck S. Convex Optimization: Algorithms and Complexity. // Foundations and Trends in Machine Learning. — 2015. — Vol. 8, No. 3-4. — P. 231–357.</ref>. В дальнейшем концепция «ускорения» была обобщена на широкий класс невыпуклых, вариационных и стохастических задач, став фундаментальным строительным блоком современных алгоритмов машинного обучения (например, алгоритма FISTA)<ref name="FISTA">Beck A., Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems // SIAM Journal on Imaging Sciences. — 2009. — Vol. 2, no. 1. — P. 183–202.</ref>.
+
Ускоренный градиент Нестерова является первым алгоритмом, достигающим этой теоретической нижней границы, что делает его '''оптимальным''' в смысле теории вычислительной сложности черного ящика (first-order black-box optimization)<ref name="Bubeck2015">Bubeck S. Convex Optimization: Algorithms and Complexity. // Foundations and Trends in Machine Learning. — 2015. — Vol. 8, No. 3-4.</ref>. В дальнейшем концепция «ускорения» была обобщена на широкий класс невыпуклых, вариационных и стохастических задач, став фундаментальным строительным блоком современных алгоритмов машинного обучения (например, алгоритма FISTA)<ref name="FISTA">Beck A., Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems // SIAM Journal on Imaging Sciences. — 2009. — Vol. 2, no. 1.</ref>.
== Постановка задачи ==
== Постановка задачи ==
Строка 42: Строка 42:
== Теоретические свойства и скорость сходимости ==
== Теоретические свойства и скорость сходимости ==
-
Основной теоретический результат для метода формулируется с помощью техники '''оценивающих последовательностей''' (estimate sequences)<ref name="Nesterov2004">Nesterov Y. Introductory Lectures on Convex Optimization: A Basic Course. — Springer Science & Business Media, 2004. — (См. Главу 2).</ref>.
+
Основной теоретический результат для метода формулируется с помощью техники '''оценивающих последовательностей''' (estimate sequences)<ref name="Nesterov2004">Nesterov Y. Introductory lectures on convex optimization: A basic course. – Springer Science & Business Media, 2013. – Т. 87.</ref>.
'''Определение.''' Последовательность функций <tex>\phi_k: \mathbb{R}^n \to \mathbb{R}</tex> называется оценивающей последовательностью для функции <tex>f</tex>, если выполняются два условия:
'''Определение.''' Последовательность функций <tex>\phi_k: \mathbb{R}^n \to \mathbb{R}</tex> называется оценивающей последовательностью для функции <tex>f</tex>, если выполняются два условия:
Строка 84: Строка 84:
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+1}) - f^*) \le \phi_0(x^*) - f^* \le \frac{L}{2}\|x_0 - x^*\|^2.
</tex>
</tex>
-
Подставляя явный вид <tex>A_{k+1}</tex>, получаем искомую оценку <tex>f(y_k) - f^* \le \frac{2L \|x_0 - x^*\|^2}{(k+1)^2}</tex>. <tex>\blacksquare</tex>
+
Подставляя явный вид <tex>A_{k+1}</tex>, получаем искомую оценку <tex>f(y_k) - f^* \le \frac{2L \|x_0 - x^*\|^2}{(k+1)^2}</tex>. Ч. т. д.
-
 
+
=== Теорема (О скорости сходимости для сильно выпуклых функций) ===
=== Теорема (О скорости сходимости для сильно выпуклых функций) ===
Если функция <tex>f</tex> является [[Сильно выпуклая функция|сильно выпуклой]] с параметром <tex>\mu > 0</tex>, то метод модифицируется путем замены коэффициента экстраполяции на константу:
Если функция <tex>f</tex> является [[Сильно выпуклая функция|сильно выпуклой]] с параметром <tex>\mu > 0</tex>, то метод модифицируется путем замены коэффициента экстраполяции на константу:
Строка 101: Строка 100:
# '''Чувствительность к шуму''': Метод критически зависит от точности вычисления градиента. При добавлении стохастического шума (в SGD) ускорение может быть утрачено без применения специальных техник стабилизации (например, variance reduction).
# '''Чувствительность к шуму''': Метод критически зависит от точности вычисления градиента. При добавлении стохастического шума (в SGD) ускорение может быть утрачено без применения специальных техник стабилизации (например, variance reduction).
# '''Зависимость от константы Липшица''': Практическое применение метода требует знания или оценки константы <tex>L</tex>. Слишком завышенная оценка приводит к замедлению сходимости, заниженная — к расходимости алгоритма.
# '''Зависимость от константы Липшица''': Практическое применение метода требует знания или оценки константы <tex>L</tex>. Слишком завышенная оценка приводит к замедлению сходимости, заниженная — к расходимости алгоритма.
-
 
-
== Литература ==
 
-
<references />
 
== См. также ==
== См. также ==
Строка 112: Строка 108:
* [http://www.machinelearning.ru/wiki/images/0/03/Rodomanov_FGM.pdf Анализ быстрого градиентного метода нестерова для задач машинного обучения с L1-регуляризацией]
* [http://www.machinelearning.ru/wiki/images/0/03/Rodomanov_FGM.pdf Анализ быстрого градиентного метода нестерова для задач машинного обучения с L1-регуляризацией]
* [[Метод сопряжённых градиентов]]
* [[Метод сопряжённых градиентов]]
 +
 +
== Примечания ==
 +
{{примечания}}
 +
 +
== Литература ==
 +
* {{статья | автор = Нестеров Ю. Е. | заглавие = Метод решения задачи выпуклого программирования со скоростью сходимости <tex>O(1/k^2)</tex> | издание = Доклады Академии Наук | год = 1983 | том = 269 | номер = 3 }}
 +
* {{статья | автор = Bubeck S. | заглавие = Convex Optimization: Algorithms and Complexity | издание = Foundations and Trends in Machine Learning | год = 2015 | том = 8 | номер = 3-4 }}
 +
* {{статья | автор = Beck A., Teboulle M. | заглавие = A fast iterative shrinkage-thresholding algorithm for linear inverse problems | издание = SIAM Journal on Imaging Sciences | год = 2009 | том = 2 | номер = 1 }}
 +
* {{статья | автор = Nesterov Y. | заглавие = Introductory lectures on convex optimization: A basic course | издательство = Springer Science & Business Media | год = 2013 | том = 87 }}

Текущая версия

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


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

Содержание

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

В середине 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} удовлетворяет следующим условиям:

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

  1. \phi_k(x) \le f(x) для всех x \in \mathbb{R}^n и всех k \ge 0.
  2. Существует такая последовательность \{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}. Ч. т. д.

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

Если функция 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^*).

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

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

См. также

Примечания

Литература

  • Нестеров Ю. Е. Метод решения задачи выпуклого программирования со скоростью сходимости O(1/k^2) // Доклады Академии Наук. — 1983. — Т. 269. — № 3.
  • Bubeck S. Convex Optimization: Algorithms and Complexity // Foundations and Trends in Machine Learning. — 2015. — Т. 8. — № 3-4.
  • Beck A., Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems // SIAM Journal on Imaging Sciences. — 2009. — Т. 2. — № 1.
  • Nesterov Y. Introductory lectures on convex optimization: A basic course. — Springer Science & Business Media, 2013. — Т. 87.
Источник — «http://recognition.su/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»
Личные инструменты