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

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

(Различия между версиями)

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

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

Ускоренный градиент Нестерова (англ. 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$ . Слишком завышенная оценка приводит к замедлению сходимости, заниженная — к расходимости алгоритма.

Литература

См. также

Источник — «http://83.149.227.45/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»

@@ Строка 1: / Строка 1: @@
-{{well|Статья написана с использованием LLM '''GPT-4o''' и проверена участником [[Участник:Arina Pakalova|Arina Pakalova]] 14:23, 25 июня 2026 (MSD)}}
+{{well|Статья написана с использованием LLM и проверена участником [[Участник: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>.
-'''Генерация признаков''' (англ. ''feature generation'', ''feature construction'') — это процесс создания новых переменных на основе исходного [[Признаковое описание|признакового описания]] объектов с целью повышения информативности данных для последующего применения алгоритмов [[Машинное обучение|машинного обучения]].
+== Определение и актуальность в теории оптимизации ==
+В середине 1980-х годов Ю. Е. Нестеровым была доказана нижняя оценка скорости сходимости для класса гладких выпуклых задач минимизации, показывающая, что ни один метод первого порядка не может гарантировать скорость сходимости быстрее, чем <tex>O(1/k^2)</tex>. До этой работы стандартный [[Градиентный спуск|градиентный спуск]] обеспечивал лишь скорость <tex>O(1/k)</tex>.
-Генерация признаков является ключевым этапом [[Конструирование признаков|конструирования признаков]] (feature engineering) и принципиально отличается от [[Отбор признаков|отбора признаков]] (feature selection). Если отбор подразумевает выбор оптимального подмножества из уже существующих переменных, то генерация заключается в расширении пространства признаков за счет явного или неявного вычисления новых характеристик<ref name="kuhn">Kuhn, M., & Johnson, K. (2019). ''Feature Engineering and Selection: A Practical Approach for Predictive Models''. CRC Press.</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. — 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>.
-== Формальное определение ==
+== Постановка задачи ==
+Рассмотрим задачу безусловной минимизации:
+<tex>
+\min_{x \in \mathbb{R}^n} f(x),
+</tex>
+где целевая функция <tex>f: \mathbb{R}^n \to \mathbb{R}</tex> удовлетворяет следующим условиям:
-Пусть задано исходное признаковое описание объекта <tex>x \in \mathbb{R}^d</tex>. Генерация признаков представляет собой отображение:
+# '''[[Выпуклая функция|Выпуклость]]''': для любых <tex>x, y \in \mathbb{R}^n</tex> выполняется <tex>f(y) \ge f(x) + \langle \nabla f(x), y - x \rangle</tex>.
-<tex>\phi: \mathbb{R}^d \rightarrow \mathbb{R}^D</tex>,
+# '''[[Условие Липшица|Гладкость]]''': градиент функции является [[Липшицева непрерывность|липшицевым]] с константой <tex>L > 0</tex>, то есть для любых <tex>x, y \in \mathbb{R}^n</tex>:
-где <tex>D > d</tex>. Новое описание объекта формируется как <tex>\tilde{x} = \phi(x)</tex>. Целью данного преобразования является переход в такое пространство <tex>\mathbb{R}^D</tex>, в котором [[Обучающая выборка|обучающая выборка]] становится линейно разделимой или обладает более выраженной структурой, позволяющей построить модель с меньшей [[Ошибка обобщения|ошибкой обобщения]]<ref name="bishop">Bishop, C. M. (2006). ''Pattern Recognition and Machine Learning''. Springer.</ref>.
+<tex>
+\|\nabla f(x) - \nabla f(y)\| \le L \|x - y\|.
+</tex>
+Эквивалентное условие гладкости:
+<tex>
+f(y) \le f(x) + \langle \nabla f(x), y - x \rangle + \frac{L}{2} \|x - y\|^2.
+</tex>
-== Основные методы генерации признаков ==
+Пусть <tex>x^*</tex> — точка минимума функции <tex>f(x)</tex>, а <tex>f^* = f(x^*)</tex> — глобальное минимальное значение.
-Методы генерации классифицируются в зависимости от типа исходных данных и применяемых математических преобразований.
+== Описание метода ==
+Классический вариант метода (1983 г.) генерирует две последовательности: основную точку <tex>x_k</tex> и вспомогательную (экстраполированную) точку <tex>y_k</tex>.
-=== Базовые математические преобразования ===
+'''Алгоритм:'''
-К данной группе относятся арифметические операции над скалярными признаками:
+* '''Инициализация:''' <tex>y_0 = x_0 \in \mathbb{R}^n</tex>.
-* '''Логарифмирование и степенные преобразования:''' применяются для изменения распределения признака (например, для приближения к нормальному распределению) и снижения влияния выбросов.
+* '''Итерация''' <tex>k = 0, 1, 2, \dots</tex>:
-* '''Дискретизация (биннинг):''' преобразование непрерывной переменной в категориальную путем разбиения области значений на интервалы.
+<tex>
-* '''Нормализация и стандартизация:''' хотя технически это преобразования масштаба, они создают новые представления признаков, необходимые для корректной работы метрических алгоритмов (например, [[Метод k-ближайших соседей|метода k-ближайших соседей]]).
+\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}
+</tex>
+В данном выражении коэффициент <tex>\frac{k}{k+3}</tex> является частным случаем последовательности <tex>\alpha_k = \frac{2}{k+3}</tex>. Существуют эквивалентные формы записи через трехточечный рекуррентный процесс, однако приведенная форма наиболее наглядно демонстрирует механизм «заглядывания вперед» (look-ahead), когда градиент вычисляется не в текущей аппроксимации <tex>x_k</tex>, а в экстраполированной точке <tex>y_k</tex>.
-=== Признаки взаимодействия (Interaction features) ===
+== Теоретические свойства и скорость сходимости ==
-Создаются путем комбинирования двух или более исходных переменных для фиксации совместного влияния факторов на [[Целевая переменная|целевую переменную]]:
-* '''Мультипликативное взаимодействие:''' произведение признаков <tex>x_i \cdot x_j</tex>. Классическим примером являются [[Полиномиальные признаки|полиномиальные признаки]], где формируются все возможные произведения исходных переменных до заданной степени. Это позволяет линейным моделям (таким как [[Линейная регрессия|линейная регрессия]] или [[Логистическая регрессия|логистическая регрессия]]) аппроксимировать нелинейные зависимости<ref name="hastie">Hastie, T., Tibshirani, R., & Friedman, J. (2009). ''The Elements of Statistical Learning'' (2nd ed.). Springer.</ref>.
-* '''Аддитивное взаимодействие и отношения:''' суммы или частные от деления признаков (например, отношение площади комнаты к ее объему).
-=== Специфические генераторы для структурированных данных ===
+Основной теоретический результат для метода формулируется с помощью техники '''оценивающих последовательностей''' (estimate sequences)<ref name="Nesterov2004">Nesterov Y. Introductory Lectures on Convex Optimization: A Basic Course. — Springer Science & Business Media, 2004. — (См. Главу 2).</ref>.
-* '''Временные ряды:''' генерация лаг-признаков (значений за предыдущие периоды), скользящих статистик (среднее значение, дисперсия, минимум/максимум в окне), признаков сезонности (день недели, месяц) и автокорреляционных функций.
-* '''Текстовые данные:''' применение подходов [[Мешок слов|мешка слов]] (Bag-of-Words), вычисление [[TF-IDF|TF-IDF]] характеристик, генерация n-грамм. Данные методы преобразуют неструктурированный текст в числовую матрицу «объект-признак».
-* '''Графовые данные:''' вычисление характеристик вершин и рёбер, таких как степень вершины, [[Коэффициент кластеризации|коэффициент кластеризации]], меры центральности (например, PageRank), расстояния в графе.
-=== Автоматическая генерация признаков ===
+'''Определение.''' Последовательность функций <tex>\phi_k: \mathbb{R}^n \to \mathbb{R}</tex> называется оценивающей последовательностью для функции <tex>f</tex>, если выполняются два условия:
-Вместо ручного конструирования применяются алгоритмические подходы:
+# <tex>\phi_k(x) \le f(x)</tex> для всех <tex>x \in \mathbb{R}^n</tex> и всех <tex>k \ge 0</tex>.
-* '''Глубокое обучение (Deep Learning):''' скрытые слои [[Искусственная нейронная сеть|искусственных нейронных сетей]] (например, [[Сверточная нейронная сеть|сверточных сетей]] для изображений) выполняют иерархическую автоматическую генерацию признаков. Выходы предпоследнего слоя выступают в роли сгенерированных признаков для финального классификатора<ref name="bishop"/>.
+# Существует такая последовательность <tex>\{y_k\}</tex>, что <tex>f(y_k) \le \phi_k(x^*)</tex> для всех <tex>k \ge 0</tex>.
-* '''Генетическое программирование (Genetic Programming):''' эволюционный поиск оптимальных математических формул для комбинации исходных признаков.
-* '''Синтез глубоких признаков (Deep Feature Synthesis):''' алгоритм, реализованный в библиотеке Featuretools, который автоматически применяет наборы примитивных трансформаций (aggregation, transform) к реляционным базам данных для генерации новых признаков.
-== Проблемы и ограничения ==
+=== Теорема (О скорости сходимости для гладких выпуклых функций) ===
+Пусть функция <tex>f</tex> выпукла и имеет липшицев градиент с константой <tex>L</tex>. Тогда для последовательности <tex>\{y_k\}</tex>, генерируемой ускоренным градиентом Нестерова, выполняется:
+<tex>
+f(y_k) - f^* \le \frac{2L \|x_0 - x^*\|^2}{(k+1)^2}.
+</tex>
-Применение генерации признаков сопряжено с рядом проблем:
+'''Доказательство.'''
-* '''[[Проклятие размерности|Проклятие размерности]]:''' избыточная генерация признаков приводит к экспоненциальному росту размерности пространства. Это требует пропорционального роста объема обучающей выборки для сохранения плотности данных, иначе модель подвержена [[Переобучение|переобучению]].
+Рассмотрим оценивающую последовательность вида:
-* '''Мультиколлинеарность:''' создание производных признаков (например, суммы двух сильно скоррелированных признаков) часто приводит к высокой корреляции между предикторами. Это может вызвать числовую нестабильность при обучении линейных моделей без регуляризации.
+<tex>
-* '''Вычислительная сложность:''' хранение и обработка разреженных матриц огромной размерности (характерных для n-грамм или полиномиальных признаков высокой степени) требует значительных ресурсов оперативной памяти и процессорного времени.
+\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],
+</tex>
+где <tex>\alpha_0 = 1</tex> и <tex>\alpha_{k+1} = \frac{2}{k+3}</tex>.
+В качестве начальной функции выберем <tex>\phi_0(x) = f(x_0) + \langle \nabla f(x_0), x - x_0 \rangle + \frac{L}{2}\|x - x_0\|^2</tex>.
+Утверждение 1: <tex>\phi_k(x) \le f(x)</tex> для всех <tex>x</tex>. Докажем по индукции.
+* База: <tex>\phi_0(x)</tex> является глобальной верхней оценкой для <tex>f(x)</tex> в силу условия гладкости.
+* Шаг индукции: Пусть <tex>\phi_k(x) \le f(x)</tex>. По условию гладкости, выражение в квадратных скобках также является верхней оценкой <tex>f(x)</tex>. Так как <tex>(1-\alpha_{k+1}) \ge 0</tex> и <tex>\alpha_{k+1} \ge 0</tex>, их выпуклая комбинация <tex>\phi_{k+1}(x)</tex> также не превышает <tex>f(x)</tex>.
+Утверждение 2: Выполнение условия <tex>f(y_k) \le \phi_k(x^*)</tex>.
+Найдем минимум правой части выражения для <tex>\phi_{k+1}(x)</tex>. Точка минимума квадратичной функции в скобках есть <tex>x_{k+1}</tex>. Значение в этой точке равно <tex>f(x_{k+1})</tex>. Следовательно, минимальное значение <tex>\phi_{k+1}(x)</tex> достигается в точке:
+<tex>
+y_{k+1} = \arg\min_{x} \phi_{k+1}(x) = (1-\alpha_{k+1})y_k + \alpha_{k+1} x_{k+1}.
+</tex>
+Подставляя <tex>x_{k+1} = y_k - \frac{1}{L}\nabla f(y_k)</tex> и выражение для <tex>\alpha_{k+1}</tex>, после алгебраических преобразований получаем рекуррентное соотношение <tex>y_{k+1} = x_{k+1} + \frac{k}{k+3}(x_{k+1} - x_k)</tex>, что в точности совпадает с алгоритмом.
+Оценим значение:
+<tex>
+\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].
+</tex>
+Используя предположение индукции <tex>f(y_k) \le \phi_k(x^*)</tex> и неравенство Коши-Буняковского-Шварца для градиента, можно показать, что <tex>\phi_{k+1}(y_{k+1}) \le \phi_k(x^*) - \frac{\alpha_{k+1}}{2L}\|\nabla f(y_k)\|^2 \le \phi_k(x^*)</tex>. Отсюда <tex>f(y_{k+1}) \le \phi_{k+1}(x^*)</tex>.
+Утверждение 3: Оценка скорости.
+Введем вспомогательную последовательность <tex>A_k = \alpha_k \prod_{i=1}^{k-1} (1-\alpha_i)</tex>. Можно показать, что <tex>A_k = \frac{2}{(k+1)(k+2)}</tex>.
+Из разложения оценивающей последовательности в точке <tex>x^*</tex> следует:
+<tex>
+A_{k+1} (f(y_{k+1}) - f^*) \le \phi_0(x^*) - f^* \le \frac{L}{2}\|x_0 - x^*\|^2.
+</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>f</tex> является [[Сильно выпуклая функция|сильно выпуклой]] с параметром <tex>\mu > 0</tex>, то метод модифицируется путем замены коэффициента экстраполяции на константу:
+<tex>
+\beta = \frac{\sqrt{L} - \sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}}.
+</tex>
+Тогда скорость сходимости становится линейной:
+<tex>
+f(y_k) - f^* \le \left( \frac{\sqrt{L} - \sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}} \right)^{2k} (f(y_0) - f^*).
+</tex>
+=== Свойства метода ===
+# '''Оптимальность''': Метод достигает теоретической нижней границы <tex>O(1/k^2)</tex> для класса гладких выпуклых задач. Изменение константы шага или коэффициента экстраполяции не может улучшить асимптотику по порядку.
+# '''Немонотонность''': В отличие от классического градиентного спуска, последовательность значений целевой функции <tex>\{f(y_k)\}</tex> не является монотонно убывающей. Допускаются локальные возрастания функции на отдельных итерациях.
+# '''Чувствительность к шуму''': Метод критически зависит от точности вычисления градиента. При добавлении стохастического шума (в SGD) ускорение может быть утрачено без применения специальных техник стабилизации (например, variance reduction).
+# '''Зависимость от константы Липшица''': Практическое применение метода требует знания или оценки константы <tex>L</tex>. Слишком завышенная оценка приводит к замедлению сходимости, заниженная — к расходимости алгоритма.
 == Литература ==
 <references />
+== См. также ==
+* [[Метод инерции Поляка]]
+* [[Диагональный метод Левенберга-Марквардта]]
+* [[Метод наискорейшего спуска]]	-
+* [http://www.machinelearning.ru/wiki/images/3/34/Rodomanov-fast-gradient-methods.pdf Быстрый градиентный метод]
+* [http://www.machinelearning.ru/wiki/images/0/03/Rodomanov_FGM.pdf Анализ быстрого градиентного метода нестерова для задач машинного обучения с L1-регуляризацией]
+* [[Метод сопряжённых градиентов]]