Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

{{well|Статья написана с использованием LLM '''Gemini 3.1 Pro''' и проверена участником [[Участник:Renal Gazizullin|Renal Gazizullin]] 16:30, 23 июня 2026 (MSD)}} '''Проксимальный градиентный спуск''' — метод оптимизации первого порядка, предназначенный для решения задач композитной оптимизации, в которых целевая функция представима в виде суммы гладкой и негладкой выпуклых компонент. == Введение и формальная постановка задачи == Рассматривается задача безусловной минимизации: :: <tex>\min_{x \in \mathbb{R}^d} F(x) = f(x) + g(x),</tex> где: * <tex>f: \mathbb{R}^d \to \mathbb{R}</tex> — выпуклая дифференцируемая функция, градиент которой <tex>\nabla f</tex> является [[Липшицева непрерывность|липшиц-непрерывным]] с константой <tex>L > 0</tex>: :: <tex>\|\nabla f(x) - \nabla f(y)\|_2 \le L \|x - y\|_2 \quad \forall x, y \in \mathbb{R}^d;</tex> * <tex>g: \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}</tex> — [[Собственная функция (выпуклый анализ)|собственная]] [[Замкнутая функция|замкнутая]] выпуклая функция, которая может быть недифференцируемой. Классический [[Градиентный спуск]] неприменим к данной задаче ввиду отсутствия <tex>\nabla g(x)</tex> во всех точках области определения. Прямой переход к [[Субградиентный метод|субградиентному спуску]] приводит к деградации скорости сходимости до <tex>\mathcal{O}(1/\sqrt{k})</tex>. Проксимальный градиентный спуск позволяет обойти это ограничение, обрабатывая гладкую часть явным шагом по градиенту, а негладкую — неявным шагом через проксимальный оператор, что позволяет сохранить асимптотику сходимости <tex>\mathcal{O}(1/k)</tex>. == Проксимальный оператор == Для выпуклой функции <tex>g</tex> и параметра масштаба <tex>\lambda > 0</tex> '''проксимальным оператором''' <tex>\operatorname{prox}_{\lambda g}: \mathbb{R}^d \to \mathbb{R}^d</tex> называется отображение<ref>Moreau, J. J. Proximité et dualité dans un espace hilbertien // Bulletin de la Société Mathématique de France. — 1965. — Т. 93. — С. 273–299.</ref>: :: <tex>\operatorname{prox}_{\lambda g}(v) = \arg\min_{x \in \mathbb{R}^d} \left( g(x) + \frac{1}{2\lambda} \|x - v\|_2^2 \right).</tex> === Геометрический смысл === Оператор ищет компромисс между минимизацией значения <tex>g(x)</tex> и близостью к аргументу <tex>v</tex> в смысле евклидовой метрики. При <tex>\lambda \to 0</tex> оператор вырождается в тождественное преобразование <tex>\operatorname{prox}_{0 g}(v) = v</tex>, а при <tex>\lambda \to \infty</tex> возвращает точку безусловного минимума функции <tex>g</tex>. В частном случае, когда <tex>g(x) = \mathbb{I}_C(x)</tex> (индикаторная функция выпуклого множества <tex>C</tex>), проксимальный оператор тождественно равен [[Оператор проектирования|оператору евклидовой проекции]] на множество <tex>C</tex>. === Связь с теоремой Моро === Фундаментальное свойство проксимального оператора задается через [[Огибающая Моро|огибающую Моро]] (регуляризацию Иосиды функции <tex>g</tex>): :: <tex>M_{\lambda g}(v) = \inf_{x \in \mathbb{R}^d} \left( g(x) + \frac{1}{2\lambda} \|x - v\|_2^2 \right).</tex> Согласно '''теореме Моро''', функция <tex>M_{\lambda g}</tex> является непрерывно дифференцируемой (даже если <tex>g</tex> разрывна), а её градиент вычисляется аналитически: :: <tex>\nabla M_{\lambda g}(v) = \frac{1}{\lambda} \left( v - \operatorname{prox}_{\lambda g}(v) \right).</tex> Следствием данного тождества является тот факт, что шаг проксимального градиентного спуска эквивалентен шагу стандартного градиентного спуска, применённому к гладкой аппроксимации Моро. == Вычисление проксимальных операторов == Практическая ценность метода определяется наличием замкнутой аналитической формы для <tex>\operatorname{prox}_{\lambda g}</tex>. Классическим примером является <tex>L_1</tex>-регуляризатор задачи [[Lasso-регрессия|LASSO]]: <tex>g(x) = \|x\|_1 = \sum_{i=1}^d |x_i|</tex>. === Аналитический вывод для L1-нормы === Поскольку целевая функция сепарабельна по координатам вектора <tex>x</tex>, многомерная задача оптимизации распадается на <tex>d</tex> независимых скалярных задач: :: <tex>[\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).</tex> Обозначим минимизируемую функцию одной переменной через <tex>\psi(x_i)</tex>. Необходимым и достаточным условием глобального минимума выпуклой недифференцируемой функции является принадлежность нуля её [[Субдифференциал|субдифференциалу]]: :: <tex>0 \in \partial \psi(x_i)</tex> ↔ <tex> 0 \in \partial |x_i| + \frac{1}{\lambda}(x_i - v_i) </tex> ↔ <tex>v_i - x_i \in \lambda \partial |x_i|.</tex> Субдифференциал функции модуля <tex>\partial |x_i|</tex> имеет вид: :: <tex>\partial |x_i| = \begin{cases} \{1\}, & x_i > 0 \\ [-1, 1], & x_i = 0 \\ \{-1\}, & x_i < 0 \end{cases}</tex> Рассмотрим три возможных локализации оптимальной точки <tex>x_i^*</tex>: # '''Случай <tex>x_i^* > 0</tex>:''' Субдифференциал равен <tex>1</tex>. Условие оптимума: <tex>v_i - x_i^* = \lambda </tex> → <tex> x_i^* = v_i - \lambda</tex>. Данное допущение непротиворечиво тогда и только тогда, когда <tex>v_i > \lambda</tex>. # '''Случай <tex>x_i^* < 0</tex>:''' Субдифференциал равен <tex>-1</tex>. Условие оптимума: <tex>v_i - x_i^* = -\lambda </tex> → <tex> x_i^* = v_i + \lambda</tex>. Непротиворечиво при <tex>v_i < -\lambda</tex>. # '''Случай <tex>x_i^* = 0</tex>:''' Субдифференциал представляет собой отрезок <tex>[-1, 1]</tex>. Условие оптимума: <tex>v_i \in \lambda [-1, 1] </tex> ↔ <tex> |v_i| \le \lambda</tex>. Синтез трех случаев дает '''оператор мягкого порогового отсечения'''<ref>Parikh, N., Boyd, S. Proximal Algorithms // Foundations and Trends in Optimization. — 2014. — Т. 1, № 3. — С. 127–239.</ref>: :: <tex>\mathcal{S}_\lambda(v_i) = \operatorname{sign}(v_i) \max(0, |v_i| - \lambda).</tex> Оператор осуществляет непрерывное стягивание компонент вектора к нулю; координаты, по модулю не превосходящие порог <tex>\lambda</tex>, строго обнуляются, генерируя разреженное решение. == Базовый алгоритм ISTA == Алгоритм '''ISTA''' представляет собой каноническую реализацию метода. Итерационный процесс строится на принципе [[Мажоризация-минимизация|мажоризации-минимизации]] (MM). В точке <tex>x_k</tex> гладкая компонента <tex>f(x)</tex> аппроксимируется сверху строго выпуклой квадратичной суррогатной функцией (согласно лемме о липшицевом градиенте): :: <tex>f(x) \le f(x_k) + \langle \nabla f(x_k), x - x_k \rangle + \frac{L}{2} \|x - x_k\|_2^2.</tex> Минимизация результирующей верхней оценки всей функции <tex>F(x)</tex> на шаге <tex>k</tex> записывается как: :: <tex>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).</tex> Выделение полного квадрата по переменной <tex>x</tex> сводит задачу к форме проксимального оператора: :: <tex>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).</tex> === Шаги алгоритма === Для начального вектора <tex>x_0 \in \mathbb{R}^d</tex> и величины шага <tex>\gamma \in (0, 1/L]</tex> алгоритм повторяет: # Явный шаг градиентного спуска: :: <tex>y_k = x_k - \gamma \nabla f(x_k).</tex> # Неявный проксимальный шаг: :: <tex>x_{k+1} = \operatorname{prox}_{\gamma g}(y_k).</tex> === Условия сходимости === Для выпуклых функций <tex>f, g</tex> при шаге <tex>\gamma \le 1/L</tex> метод ISTA гарантирует сублинейную [[Скорость сходимости|скорость сходимости]] по целевому функционалу: :: <tex>F(x_k) - F(x^*) \le \frac{L \|x_0 - x^*\|_2^2}{2k}.</tex> Если <tex>f</tex> является [[Сильно выпуклая функция|сильно выпуклой]] с константой <tex>\mu > 0</tex>, метод сходится с линейной скоростью: <tex>F(x_k) - F(x^*) \le \left(1 - \frac{\mu}{L}\right)^k (F(x_0) - F(x^*))</tex>. == Ускоренные и стохастические методы == === Ускорение Нестерова (FISTA) === Алгоритм '''FISTA'''<ref>Beck, A., Teboulle, M. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems // SIAM Journal on Imaging Sciences. — 2009. — Т. 2, № 1. — С. 183–202.</ref> модифицирует ISTA путем внедрения импульса Нестерова. Проксимальный шаг осуществляется не из текущей точки <tex>x_k</tex>, а из экстраполированной точки <tex>y_{k+1}</tex>: * Инициализация: <tex>x_0 = y_1 \in \mathbb{R}^d, \; t_1 = 1</tex>. * На каждой итерации <tex>k \ge 1</tex>: # <tex>x_k = \operatorname{prox}_{\gamma g}\left( y_k - \gamma \nabla f(y_k) \right);</tex> # <tex>t_{k+1} = \frac{1 + \sqrt{1 + 4t_k^2}}{2};</tex> # <tex>y_{k+1} = x_k + \frac{t_k - 1}{t_{k+1}} (x_k - x_{k-1}).</tex> FISTA достигает асимптотики сходимости <tex>\mathcal{O}(1/k^2)</tex>, что является [[Оптимальный метод оптимизации|нижней теоретической границей]] сложности для методов первого порядка на классе гладких выпуклых задач. === Проксимальные стохастические методы с редукцией дисперсии === В задачах обучения на больших данных функция <tex>f(x)</tex> имеет структуру эмпирического риска: <tex>f(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)</tex>. Применение наивного проксимального [[Стохастический градиентный спуск|стохастического градиентного спуска]] (Prox-SGD) приводит к потере линейной сходимости на сильно выпуклых задачах из-за ненулевой асимптотической дисперсии стохастического градиента. Преодоление проблемы требует техник Variance Reduction. ==== Prox-SVRG ==== Метод '''Prox-SVRG''' <ref>Xiao, L., Zhang, T. A Proximal Stochastic Gradient Method with Progressive Variance Reduction // SIAM Journal on Optimization. — 2014. — Т. 24, № 4. — С. 2057–2075.</ref> оперирует вложенными циклами (эпохами). На внешнем цикле в точке <tex>\tilde{x}</tex> вычисляется и фиксируется точный вектор градиента <tex>\nabla f(\tilde{x})</tex>. На внутреннем цикле для случайного индекса <tex>i_k</tex> строится модифицированная оценка градиента: :: <tex>v_k = \nabla f_{i_k}(x_k) - \nabla f_{i_k}(\tilde{x}) + \nabla f(\tilde{x}).</tex> Шаг обновления: <tex>x_{k+1} = \operatorname{prox}_{\gamma g}(x_k - \gamma v_k)</tex>. По мере приближения точек <tex>x_k, \tilde{x}</tex> к оптимуму <tex>x^*</tex>, дисперсия вектора <tex>v_k</tex> автоматически асимптотически стремится к нулю. ==== Prox-SAGA ==== Метод '''Prox-SAGA'''<ref>Defazio, A., Bach, F., Lacoste-Julien, S. SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives // Advances in Neural Information Processing Systems (NIPS). — 2014. — Т. 27.</ref> заменяет расчет полных градиентов хранением в памяти таблицы последних вычисленных градиентов для каждого из <tex>n</tex> объектов: <tex>\{g_i\}_{i=1}^n</tex>. На шаге <tex>k</tex> случайно выбирается индекс <tex>j</tex>, вычисляется <tex>\nabla f_j(x_k)</tex>, and вектор направления формируется как: :: <tex>v_k = \nabla f_j(x_k) - g_j + \frac{1}{n}\sum_{i=1}^n g_i.</tex> После шага пересчета <tex>x_{k+1} = \operatorname{prox}_{\gamma g}(x_k - \gamma v_k)</tex> запись в таблице обновляется: <tex>g_j \leftarrow \nabla f_j(x_k)</tex>. ==== Prox-SARAH ==== Метод '''Prox-SARAH''' <ref>Pham, N. T., Nguyen, L. M., van Dijk, M., et al. ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization // Journal of Machine Learning Research. — 2020. — Т. 21, № 110. — С. 1–48.</ref> использует смещенную рекурсивную оценку. Вектор направления пересчитывается по формуле: :: <tex>v_k = \nabla f_{i_k}(x_k) - \nabla f_{i_k}(x_{k-1}) + v_{k-1.</tex> Отказ от требования несмещенности (<tex>\mathbb{E}[v_k] \ne \nabla f(x_k)</tex>) позволяет получить более стабильную траекторию убывания нормы градиента. Это делает Prox-SARAH предпочтительным выбором для ''невыпуклых'' задач композитной оптимизации (например, обучение глубоких нейронных сетей с <tex>L_0</tex>- или <tex>L_1</tex>-регуляризацией). На сильно выпуклых задачах (таких как LASSO) алгоритмы Prox-SVRG и Prox-SAGA достигают линейной скорости сходимости с общей оракульной сложностью <tex>\mathcal{O}\left( (n + L/\mu) \log(1/\epsilon) \right)</tex>, что позволяет свести итоговую вычислительную стоимость к одному проходу по датасету. == Литература == <references/> [[Категория:Методы оптимизации]] [[Категория:Энциклопедия анализа данных]] [[Категория:Выпуклый анализ]] [[Категория:Численные методы]]

• Шаблон:Mbox
• Шаблон:Well

Возврат к странице Проксимальный градиентный спуск.