Проксимальный градиентный спуск

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

Перейти к: навигация, поиск
Статья написана с использованием LLM Gemini 3.1 Pro и проверена участником Renal Gazizullin 16:30, 23 июня 2026 (MSD)


Проксимальный градиентный спуск — метод оптимизации первого порядка, предназначенный для решения задач композитной оптимизации, в которых целевая функция представима в виде суммы гладкой и негладкой выпуклых компонент.

Содержание

Введение и формальная постановка задачи

Рассматривается задача безусловной минимизации:

\min_{x \in \mathbb{R}^d} F(x) = f(x) + g(x),

где:

  • f: \mathbb{R}^d \to \mathbb{R} — выпуклая дифференцируемая функция, градиент которой \nabla f является липшиц-непрерывным с константой L > 0:
\|\nabla f(x) - \nabla f(y)\|_2 \le L \|x - y\|_2 \quad \forall x, y \in \mathbb{R}^d;

Классический Градиентный спуск неприменим к данной задаче ввиду отсутствия \nabla g(x) во всех точках области определения. Прямой переход к субградиентному спуску приводит к деградации скорости сходимости до \mathcal{O}(1/\sqrt{k}). Проксимальный градиентный спуск позволяет обойти это ограничение, обрабатывая гладкую часть явным шагом по градиенту, а негладкую — неявным шагом через проксимальный оператор, что позволяет сохранить асимптотику сходимости \mathcal{O}(1/k).

Проксимальный оператор

Для выпуклой функции g и параметра масштаба \lambda > 0 проксимальным оператором \operatorname{prox}_{\lambda g}: \mathbb{R}^d \to \mathbb{R}^d называется отображение[1]:

\operatorname{prox}_{\lambda g}(v) = \arg\min_{x \in \mathbb{R}^d} \left( g(x) + \frac{1}{2\lambda} \|x - v\|_2^2 \right).

Геометрический смысл

Оператор ищет компромисс между минимизацией значения g(x) и близостью к аргументу v в смысле евклидовой метрики. При \lambda \to 0 оператор вырождается в тождественное преобразование \operatorname{prox}_{0 g}(v) = v, а при \lambda \to \infty возвращает точку безусловного минимума функции g. В частном случае, когда g(x) = \mathbb{I}_C(x) (индикаторная функция выпуклого множества C), проксимальный оператор тождественно равен оператору евклидовой проекции на множество C.

Связь с теоремой Моро

Фундаментальное свойство проксимального оператора задается через огибающую Моро (регуляризацию Иосиды функции g):

M_{\lambda g}(v) = \inf_{x \in \mathbb{R}^d} \left( g(x) + \frac{1}{2\lambda} \|x - v\|_2^2 \right).

Согласно теореме Моро, функция M_{\lambda g} является непрерывно дифференцируемой (даже если g разрывна), а её градиент вычисляется аналитически:

\nabla M_{\lambda g}(v) = \frac{1}{\lambda} \left( v - \operatorname{prox}_{\lambda g}(v) \right).

Следствием данного тождества является тот факт, что шаг проксимального градиентного спуска эквивалентен шагу стандартного градиентного спуска, применённому к гладкой аппроксимации Моро.

Вычисление проксимальных операторов

Практическая ценность метода определяется наличием замкнутой аналитической формы для \operatorname{prox}_{\lambda g}. Классическим примером является L_1-регуляризатор задачи LASSO: g(x) = \|x\|_1 = \sum_{i=1}^d |x_i|.

Аналитический вывод для L1-нормы

Поскольку целевая функция сепарабельна по координатам вектора x, многомерная задача оптимизации распадается на d независимых скалярных задач:

[\operatorname{prox}_{\lambda \|\cdot\|_1}(v)]_i = \arg\min_{x_i \in \mathbb{R}} \left( |x_i| + \frac{1}{2\lambda} (x_i - v_i)^2 \right).

Обозначим минимизируемую функцию одной переменной через \psi(x_i). Необходимым и достаточным условием глобального минимума выпуклой недифференцируемой функции является принадлежность нуля её субдифференциалу:

0 \in \partial \psi(x_i) ↔ 0 \in \partial |x_i| + \frac{1}{\lambda}(x_i - v_i) ↔ v_i - x_i \in \lambda \partial |x_i|.

Субдифференциал функции модуля \partial |x_i| имеет вид:

\partial |x_i| = \begin{cases} \{1\}, & x_i > 0 \\ [-1, 1], & x_i = 0 \\ \{-1\}, & x_i < 0 \end{cases}

Рассмотрим три возможных локализации оптимальной точки x_i^*:

  1. Случай x_i^* > 0: Субдифференциал равен 1. Условие оптимума: v_i - x_i^* = \lambda → x_i^* = v_i - \lambda. Данное допущение непротиворечиво тогда и только тогда, когда v_i > \lambda.
  2. Случай x_i^* < 0: Субдифференциал равен -1. Условие оптимума: v_i - x_i^* = -\lambda → x_i^* = v_i + \lambda. Непротиворечиво при v_i < -\lambda.
  3. Случай x_i^* = 0: Субдифференциал представляет собой отрезок [-1, 1]. Условие оптимума: v_i \in \lambda [-1, 1] ↔ |v_i| \le \lambda.

Синтез трех случаев дает оператор мягкого порогового отсечения[1]:

\mathcal{S}_\lambda(v_i) = \operatorname{sign}(v_i) \max(0, |v_i| - \lambda).

Оператор осуществляет непрерывное стягивание компонент вектора к нулю; координаты, по модулю не превосходящие порог \lambda, строго обнуляются, генерируя разреженное решение.

Базовый алгоритм ISTA

Алгоритм ISTA представляет собой каноническую реализацию метода. Итерационный процесс строится на принципе мажоризации-минимизации (MM).

В точке x_k гладкая компонента f(x) аппроксимируется сверху строго выпуклой квадратичной суррогатной функцией (согласно лемме о липшицевом градиенте):

f(x) \le f(x_k) + \langle \nabla f(x_k), x - x_k \rangle + \frac{L}{2} \|x - x_k\|_2^2.

Минимизация результирующей верхней оценки всей функции F(x) на шаге k записывается как:

x_{k+1} = \arg\min_x \left( f(x_k) + \langle \nabla f(x_k), x - x_k \rangle + \frac{L}{2} \|x - x_k\|_2^2 + g(x) \right).

Выделение полного квадрата по переменной x сводит задачу к форме проксимального оператора:

x_{k+1} = \arg\min_x \left( g(x) + \frac{L}{2} \left\| x - \left( x_k - \frac{1}{L}\nabla f(x_k) \right) \right\|_2^2 \right) \equiv \operatorname{prox}_{\frac{1}{L}g} \left( x_k - \frac{1}{L}\nabla f(x_k) \right).

Шаги алгоритма

Для начального вектора x_0 \in \mathbb{R}^d и величины шага \gamma \in (0, 1/L] алгоритм повторяет:

  1. Явный шаг градиентного спуска:
y_k = x_k - \gamma \nabla f(x_k).
  1. Неявный проксимальный шаг:
x_{k+1} = \operatorname{prox}_{\gamma g}(y_k).

Условия сходимости

Для выпуклых функций f, g при шаге \gamma \le 1/L метод ISTA гарантирует сублинейную скорость сходимости по целевому функционалу:

F(x_k) - F(x^*) \le \frac{L \|x_0 - x^*\|_2^2}{2k}.

Если f является сильно выпуклой с константой \mu > 0, метод сходится с линейной скоростью: F(x_k) - F(x^*) \le \left(1 - \frac{\mu}{L}\right)^k (F(x_0) - F(x^*)).

Ускоренные и стохастические методы

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

Алгоритм FISTA[1] модифицирует ISTA путем внедрения импульса Нестерова. Проксимальный шаг осуществляется не из текущей точки x_k, а из экстраполированной точки y_{k+1}:

  • Инициализация: x_0 = y_1 \in \mathbb{R}^d, \; t_1 = 1.
  • На каждой итерации k \ge 1:
  1. x_k = \operatorname{prox}_{\gamma g}\left( y_k - \gamma \nabla f(y_k) \right);
  2. t_{k+1} = \frac{1 + \sqrt{1 + 4t_k^2}}{2};
  3. y_{k+1} = x_k + \frac{t_k - 1}{t_{k+1}} (x_k - x_{k-1}).

FISTA достигает асимптотики сходимости \mathcal{O}(1/k^2), что является нижней теоретической границей сложности для методов первого порядка на классе гладких выпуклых задач.

Проксимальные стохастические методы с редукцией дисперсии

В задачах обучения на больших данных функция f(x) имеет структуру эмпирического риска: f(x) = \frac{1}{n}\sum_{i=1}^n f_i(x). Применение наивного проксимального стохастического градиентного спуска (Prox-SGD) приводит к потере линейной сходимости на сильно выпуклых задачах из-за ненулевой асимптотической дисперсии стохастического градиента. Преодоление проблемы требует техник Variance Reduction.

Prox-SVRG

Метод Prox-SVRG [1] оперирует вложенными циклами (эпохами). На внешнем цикле в точке \tilde{x} вычисляется и фиксируется точный вектор градиента \nabla f(\tilde{x}). На внутреннем цикле для случайного индекса i_k строится модифицированная оценка градиента:

v_k = \nabla f_{i_k}(x_k) - \nabla f_{i_k}(\tilde{x}) + \nabla f(\tilde{x}).

Шаг обновления: x_{k+1} = \operatorname{prox}_{\gamma g}(x_k - \gamma v_k). По мере приближения точек x_k, \tilde{x} к оптимуму x^*, дисперсия вектора v_k автоматически асимптотически стремится к нулю.

Prox-SAGA

Метод Prox-SAGA[1] заменяет расчет полных градиентов хранением в памяти таблицы последних вычисленных градиентов для каждого из n объектов: \{g_i\}_{i=1}^n. На шаге k случайно выбирается индекс j, вычисляется \nabla f_j(x_k), and вектор направления формируется как:

v_k = \nabla f_j(x_k) - g_j + \frac{1}{n}\sum_{i=1}^n g_i.

После шага пересчета x_{k+1} = \operatorname{prox}_{\gamma g}(x_k - \gamma v_k) запись в таблице обновляется: g_j \leftarrow \nabla f_j(x_k).

Prox-SARAH

Метод Prox-SARAH [1] использует смещенную рекурсивную оценку. Вектор направления пересчитывается по формуле:

v_k = \nabla f_{i_k}(x_k) - \nabla f_{i_k}(x_{k-1}) + v_{k-1.

Отказ от требования несмещенности (\mathbb{E}[v_k] \ne \nabla f(x_k)) позволяет получить более стабильную траекторию убывания нормы градиента. Это делает Prox-SARAH предпочтительным выбором для невыпуклых задач композитной оптимизации (например, обучение глубоких нейронных сетей с L_0- или L_1-регуляризацией).

На сильно выпуклых задачах (таких как LASSO) алгоритмы Prox-SVRG и Prox-SAGA достигают линейной скорости сходимости с общей оракульной сложностью \mathcal{O}\left( (n + L/\mu) \log(1/\epsilon) \right), что позволяет свести итоговую вычислительную стоимость к одному проходу по датасету.

Литература

Источник — «http://recognition.su/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA»
Личные инструменты