Проксимальные методы ✂️

Если ты когда-нибудь обучал Lasso-регрессию, ты наверняка видел этот эффект своими глазами: часть коэффициентов модели после обучения оказывается ровно нулём — не «почти нулём», не $0{,}0001$, а буквально числом $0$, которое sklearn печатает как 0.0. При этом Ridge-регрессия на тех же данных с той же силой регуляризации даёт коэффициенты маленькие, но упрямо ненулевые — все до единого. Это выглядит как какая-то магия: два очень похожих штрафа, $\lambda\|x\|_1$ и $\lambda\|x\|_2^2$, отличаются на первый взгляд лишь степенью, а на выходе дают принципиально разное поведение — одно зануляет веса и тем самым отбирает признаки, другое лишь ужимает их к нулю, никогда не достигая его точно.

В прошлом уроке про субградиентные методы ты уже видел, что модуль $|x|$ не дифференцируем в нуле, и научился обходить эту проблему, заменяя точную производную множеством субградиентов $\partial|0| = [-1,1]$. Субградиентный спуск честно решает задачу минимизации $f(x)+\lambda\|x\|_1$, но делает это вслепую: на каждом шаге он берёт произвольный элемент субдифференциала, шум которого не даёт коэффициентам аккуратно «доехать» до точного нуля и там остаться — сходимость медленная ($O(1/\sqrt{k})$), а разреженность, если и появляется, то случайно и приближённо. Субградиентный метод объясняет, что оптимизировать в присутствии негладкости, но не объясняет, откуда конкретно берётся разреженность.

Проксимальные методы отвечают на этот вопрос напрямую и конструктивно. Вместо того чтобы усреднять всю задачу в одну общую негладкую функцию и брать от неё произвольный субградиент, проксимальный подход явно разделяет цель на гладкую часть (например, среднеквадратичную ошибку) и негладкую часть (например, $L_1$-штраф) и обрабатывает их по-разному: по гладкой части делается обычный шаг градиентного спуска, а по негладкой — точный, аналитически вычислимый шаг специальной операции, которая называется проксимальным оператором. Когда эта операция применяется к $L_1$-норме, она оказывается не абстрактной формулой, а очень конкретным и по-инженерному прозрачным правилом: «увеличенные шумом маленькие координаты обнуляются полностью, большие координаты просто сдвигаются к нулю на фиксированную величину». Это правило называется мягким пороговым отображением (soft thresholding), и именно оно — прямая, доказуемая причина того, почему Lasso-регрессия отбирает признаки, а Ridge-регрессия — нет.

В этом уроке ты пройдёшь весь путь от постановки задачи «гладкая часть плюс негладкая часть» до полного доказательства формулы мягкого порогового отображения, увидишь, как из проксимального оператора и обычного градиентного шага складывается проксимальный градиентный метод, и познакомишься с двумя его конкретными реализациями — ISTA и её ускоренной версией FISTA. К концу урока разреженность Lasso перестанет быть загадочным побочным эффектом формулы и станет прямым следствием одной конкретной, доказанной теоремы.

История

Понятие проксимального оператора родилось не в машинном обучении и даже не в прикладной оптимизации, а в абстрактном функциональном анализе. В 1962 году французский математик Жан-Жак Моро (Jean-Jacques Moreau), работавший в университете Монпелье, опубликовал статью «Proximité et dualité dans un espace hilbertien» («Близость и двойственность в гильбертовом пространстве»), в которой ввёл операцию, обобщающую проекцию точки на выпуклое множество до проекции точки на выпуклую функцию. Моро интересовала чисто теоретическая задача — как аккуратно работать с невыпуклыми и негладкими объектами в гильбертовых пространствах с помощью двойственности, — и у него не было в голове ни градиентного спуска, ни регрессии: вычислительная оптимизация как отдельная дисциплина тогда только зарождалась.

Теория получила дальнейшее развитие в 1970-х годах в руках американского математика Р. Тиррелла Рокафеллара (R. Tyrrell Rockafellar), который в своей фундаментальной книге «Convex Analysis» («Выпуклый анализ») и последующих статьях о монотонных операторах показал, что проксимальный оператор — это в точности резольвента субдифференциала функции, и на этой основе построил проксимальный точечный алгоритм (proximal point algorithm) для минимизации выпуклых функций. Параллельно и совершенно независимо схожая идея всплыла в цифровой обработке сигналов: в 2004 году Ингрид Добеши (Ingrid Daubechies), Мишель Дефриз (Michel Defrise) и Кристин Де Мол (Christine De Mol) предложили итеративный алгоритм мягкого порогового отображения для восстановления разреженных сигналов по вейвлет-коэффициентам — по сути, заново открыв формулу проксимального оператора $L_1$-нормы, но с точки зрения обработки сигналов, а не абстрактной выпуклой геометрии.

Ключевой прорыв, объединивший теорию с практикой оптимизации и сделавший проксимальные методы по-настоящему быстрыми, случился в 2009 году: Амир Бек (Amir Beck) и Марк Тебулль (Marc Teboulle) опубликовали статью «A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems» («Быстрый итеративный алгоритм сжатия-порогового отображения для линейных обратных задач»), в которой к обычному проксимальному градиентному шагу (уже известному как ISTA) добавили ускоряющий трюк Юрия Нестерова из его метода 1983 года для гладкой выпуклой оптимизации — экстраполяцию между итерациями. Так родилась FISTA, которая при той же простоте вычислений на каждом шаге сходится квадратично быстрее по числу итераций. Сегодня проксимальные градиентные методы и их ускоренные версии — это стандартный вычислительный движок за задачами компрессированного восстановления сигналов, разреженного кодирования и регуляризованных линейных моделей, а идея мягкого порогового отображения, доказанная в этом уроке, напрямую объясняет поведение решателей Lasso в glmnet, scikit-learn и десятках других библиотек.

Задача: минимизация суммы гладкой и негладкой части

Интуиция

Очень многие целевые функции в машинном обучении устроены по одному и тому же шаблону: есть «часть про данные» — насколько хорошо модель объясняет обучающую выборку, и есть «часть про предпочтения» — какие решения мы вообще готовы принимать (штраф за сложность модели, требование неотрицательности параметров, ограничение на форму решения). Первая часть почти всегда гладкая: среднеквадратичная ошибка, логарифмическое правдоподобие логистической регрессии — это дифференцируемые, часто дважды дифференцируемые функции. Вторая часть — про регуляризацию или ограничения — очень часто как раз негладкая: $L_1$-норма имеет излом в нуле, индикатор допустимого множества вообще разрывен на границе.

Субградиентный спуск из прошлого урока умеет решать такую задачу «в лоб», считая всю сумму единой негладкой функцией и беря от неё произвольный субградиент на каждом шаге. Но это выбрасывает ценную информацию: мы знаем, что гладкая часть дифференцируема почти везде и у неё есть точный градиент, и мы знаем явную аналитическую форму негладкой части — не какую-то абстрактную негладкую функцию, а конкретно $L_1$-норму, индикатор конкретного множества или другую хорошо изученную конструкцию. Проксимальные методы используют именно эту структуру: они не усредняют всё в один общий (шумный) субградиент, а обрабатывают каждую часть тем инструментом, который ей подходит лучше всего.

Формальное определение

Задача проксимальной оптимизации. Требуется найти

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

где $f$ — гладкая (непрерывно дифференцируемая) выпуклая функция с $L$-липшицевым градиентом:

$$\|\nabla f(x) - \nabla f(y)\| \le L\|x - y\| \quad \text{для всех } x, y,$$

а $g$ — выпуклая функция (возможно, негладкая или даже принимающая значение $+\infty$ вне некоторого множества), для которой известен явно вычислимый проксимальный оператор.

Условие на $f$ — то же самое требование $L$-липшицевости градиента, которое уже встречалось в уроках про градиентный спуск и метод Ньютона: оно гарантирует, что квадратичная аппроксимация функции $f$ не может «обмануть» алгоритм слишком сильно. Условие на $g$ мягче: она вообще не обязана быть гладкой, но должна быть достаточно «понятной», чтобы для неё можно было эффективно решить вспомогательную задачу — именно эту вспомогательную задачу называют проксимальным оператором, и ей посвящён следующий раздел.

Примеры

Пример 1: Lasso-регрессия. Пусть $A \in \mathbb{R}^{m \times n}$ — матрица признаков, $b \in \mathbb{R}^m$ — вектор целевой переменной. Тогда

Градиент гладкой части вычисляется явно: $\nabla f(x) = A^\top(Ax-b)$, а его липшицева константа равна наибольшему собственному значению матрицы $A^\top A$. Это ровно та задача, которую решает Lasso, и ровно та форма, для которой созданы проксимальные методы.

Пример 2: ограниченная оптимизация через индикатор. Пусть нужно минимизировать гладкую функцию $f(x)$ при ограничении $x \ge 0$ (например, веса модели физически не могут быть отрицательными — концентрации, вероятности, интенсивности). Определим индикаторную функцию множества $C = \{x : x \ge 0\}$:

Тогда задача $\min f(x) + g(x)$ эквивалентна ограниченной задаче $\min_{x \ge 0} f(x)$: любая точка вне $C$ получает бесконечный штраф и никогда не может быть минимумом суммы. Так ограничения превращаются в негладкую часть общей формулировки «гладкое плюс негладкое», не требуя отдельного алгоритма для ограниченной оптимизации.

Пример 3: эластичная сеть (elastic net). Пусть $f(x) = \frac{1}{2}\|Ax-b\|^2 + \frac{\alpha_2}{2}\|x\|_2^2$ (среднеквадратичная ошибка плюс гладкий $L_2$-штраф — оба слагаемых дифференцируемы, поэтому оба идут в гладкую часть), а $g(x) = \lambda\|x\|_1$ (только по-настоящему негладкий $L_1$-штраф). Это разбиение показывает важную деталь: разбиение на $f$ и $g$ не задано автоматически самой задачей — это решение, которое принимает тот, кто применяет метод, и разумное правило простое: всё, что дифференцируемо, отправляется в $f$, а в $g$ остаётся только то, что действительно негладкое и для чего есть эффективный проксимальный оператор.

Почему это важно

Явное разделение задачи на гладкую и негладкую части — это не просто эстетическое удобство записи, а прямой источник вычислительной эффективности. Субградиентный метод, не различающий части задачи, гарантированно сходится лишь со скоростью $O(1/\sqrt{k})$ независимо от того, насколько «хорошая» гладкая часть у задачи. Проксимальные методы, эксплуатируя структуру, добиваются скорости $O(1/k)$ (ISTA) или даже $O(1/k^2)$ (FISTA) — так же, как обычный градиентный спуск на гладких задачах устойчиво обгоняет методы, которые не используют гладкость вовсе. Именно эта разница в скорости и в точности (включая точный, а не приближённый, ноль в решении) объясняет, почему промышленные решатели Lasso, elastic net, group lasso и задач компрессированного восстановления сигналов почти никогда не используют «наивный» субградиентный спуск, если структура задачи позволяет применить проксимальный метод.

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

Интуиция

Представь, что тебе нужно сдвинуться от точки $v$ в сторону, где негладкая функция $g$ принимает маленькие значения, но при этом ты не хочешь уходить от $v$ слишком далеко — например, потому что $v$ уже была получена как разумный промежуточный результат градиентного шага по гладкой части задачи. Проксимальный оператор — это математически точная формализация этого компромисса: найди точку $x$, которая одновременно и уменьшает $g(x)$, и остаётся близко к $v$, штрафуя удаление от $v$ квадратично. Чем меньше параметр $\alpha$, тем сильнее «якорь», удерживающий $x$ рядом с $v$; чем больше $\alpha$, тем сильнее решение притягивается к минимуму самой функции $g$.

Формальное определение

Проксимальный оператор. Для выпуклой функции $g$ и параметра $\alpha > 0$ проксимальный оператор определяется как

$$\mathrm{prox}_{\alpha g}(v) = \arg\min_{x \in \mathbb{R}^n} \left\{ g(x) + \frac{1}{2\alpha}\|x - v\|^2 \right\}$$

Минимизируемое выражение — сумма выпуклой функции $g$ и строго (сильно) выпуклой квадратичной функции $\frac{1}{2\alpha}\|x-v\|^2$. Сумма выпуклой и сильно выпуклой функций сильно выпукла, а у сильно выпуклой функции глобальный минимум всегда существует и единственен — значит, $\mathrm{prox}_{\alpha g}(v)$ корректно определён как одна конкретная точка, а не множество, для любого выпуклого $g$ и любого $v$.

Примеры

Пример 1: $g = 0$ — тождественный оператор. Если негладкой части нет вовсе ($g(x) = 0$ для всех $x$), задача минимизации сводится к $\arg\min_x \frac{1}{2\alpha}\|x-v\|^2$, а минимум квадрата расстояния до $v$ достигается ровно в $x = v$. Значит, $\mathrm{prox}_{\alpha \cdot 0}(v) = v$ — проксимальный оператор становится тождественным отображением, и, как ты увидишь в следующем разделе, проксимальный градиентный шаг при $g=0$ превращается в обычный шаг градиентного спуска.

Пример 2: $g$ — индикатор множества, прокс — проекция. Пусть $g(x) = \iota_C(x)$ — индикатор выпуклого множества $C$ из примера 2 предыдущего раздела. Тогда

где $\Pi_C(v)$ — обычная евклидова проекция точки $v$ на множество $C$: вне $C$ штраф бесконечен, значит минимум ищется только внутри $C$, а внутри $C$ индикатор равен нулю и остаётся лишь минимизировать расстояние до $v$. Это в точности та проекция, которая используется в методе проецируемого градиентного спуска для задач с ограничениями — и результат не зависит от $\alpha$, поскольку индикатор не имеет собственного «масштаба» штрафа. Так формально подтверждается, что проксимальный оператор — это прямое обобщение проекции на произвольные выпуклые функции, а не только на множества.

Пример 3: предварительный взгляд на $g = \lambda|\cdot|$. Для скалярной функции $g(x) = \lambda|x|$ результат оказывается похож на проекцию, но не совпадает с ней: вместо жёсткого «отрезать всё, что выходит за границу множества» здесь получается мягкое, непрерывное сжатие к нулю с возможностью точного обнуления. Полный вывод этой формулы — центральная часть данного урока, и ей посвящён отдельный раздел ниже.

Почему это важно

Проксимальный оператор — это модульный строительный блок: если для твоей функции $g$ есть эффективная формула или быстрый алгоритм вычисления $\mathrm{prox}_{\alpha g}$, ты автоматически получаешь доступ ко всему семейству проксимальных методов, независимо от того, насколько сложна сама $g$. Индикатор множества даёт проецируемый градиентный спуск, $L_1$-норма даёт ISTA/FISTA для Lasso, ядерная норма (сумма сингулярных чисел матрицы) даёт эффективные алгоритмы восстановления матриц низкого ранга, групповые нормы дают group lasso с отбором целых групп признаков сразу. Единая математическая конструкция покрывает целый спектр практических задач — именно поэтому проксимальные методы образуют не один алгоритм, а целое семейство методов, объединённых общим принципом.

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

Интуиция

Идея проксимального градиентного шага — соединить дешёвый явный шаг по гладкой части с точным проксимальным шагом по негладкой части, вместо того чтобы пытаться минимизировать всю сумму $f+g$ за один раз. Формально это делается через приём, уже знакомый по методу Ньютона и квазиньютоновским методам: вместо точной функции $f$ строится её квадратичная верхняя оценка (мажоранта) в текущей точке, и минимизируется сумма этой оценки с точной негладкой частью $g$ — задача, которая, в отличие от исходной, решается в замкнутой форме через проксимальный оператор.

Формальное определение

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

$$x_{k+1} = \mathrm{prox}_{\alpha_k g}\bigl(x_k - \alpha_k \nabla f(x_k)\bigr), \qquad \alpha_k \le \frac{1}{L}$$

где $L$ — константа Липшица градиента $f$, а шаг $x_k - \alpha_k\nabla f(x_k)$ — обычный градиентный шаг по гладкой части $f$.

Вывод этой формулы прямой. Возьмём квадратичную мажоранту $f$ в точке $x_k$ с коэффициентом кривизны $\frac{1}{\alpha}$:

и вместо исходной задачи $\min_x f(x)+g(x)$ решим приближённую задачу, где $f$ заменена на эту мажоранту:

Слагаемое $f(x_k)$ константа и не влияет на argmin. Остальные квадратичные и линейные по $x$ члены сворачиваются дополнением до полного квадрата:

Последнее слагаемое не зависит от $x$ и на argmin не влияет, поэтому

что в точности совпадает с определением проксимального оператора, применённого к результату обычного градиентного шага. Этот приём называют расщеплением вперёд-назад (forward-backward splitting): «вперёд» — явный градиентный шаг по $f$, «назад» — неявный (implicit) проксимальный шаг по $g$.

Примеры

Пример 1: полный численный шаг для игрушечной задачи Lasso. Пусть $f(x,y) = (x-3)^2 + (y-0{,}3)^2$ (гладкая часть с явным минимумом в $(3, 0{,}3)$, гессиан $\mathrm{diag}(2,2)$, значит $L=2$), $g(x,y) = |x| + |y|$ ($L_1$-штраф с $\lambda=1$). Стартуем из $x_0=(0,0)$ с шагом $\alpha = 1/L = 0{,}5$.

Градиент в старте: $\nabla f(0,0) = (2(0-3),\ 2(0-0{,}3)) = (-6,\ -0{,}6)$.

Градиентный шаг (пока без прокса): $x_0 - \alpha\nabla f(x_0) = (0,0) - 0{,}5\cdot(-6,-0{,}6) = (3,\ 0{,}3)$.

Порог мягкого отображения: $\alpha\lambda = 0{,}5\cdot 1 = 0{,}5$. Применяем к каждой координате: первая координата $3 > 0{,}5$, значит остаётся $3-0{,}5=2{,}5$; вторая координата $|0{,}3|\le 0{,}5$, значит становится ровно $0$.

Обрати внимание: чистый градиентный минимум гладкой части был бы $(3, 0{,}3)$ — обе координаты ненулевые. Проксимальный шаг сохранил и слегка сдвинул большую координату (с $3$ до $2{,}5$), но малую координату обнулил полностью — не приближённо, а точно. Это и есть тот самый эффект, который отличает Lasso от обычной регрессии.

Пример 2: почему без проксимального шага ноль не появится. Если бы вместо проксимального шага использовался обычный шаг градиентного спуска по всей сумме $f(x,y)+\lambda(|x|+|y|)$, взятый с произвольным субградиентом $\lambda\cdot\mathrm{sign}(y)$ или случайным значением из $[-\lambda,\lambda]$ в точке излома, результат почти наверняка не оказался бы точным нулём: субградиентный шаг лишь немного подталкивает координату в сторону нуля на каждой итерации, а точный ноль в общем случае достигается только в пределе, если вообще достигается. Именно неявность (implicit) проксимального шага — то, что он решает вспомогательную задачу оптимизации точно, а не делает маленький шаг в направлении убывания — даёт возможность попасть ровно в ноль за конечное число шагов.

Пример 3: требование на шаг $\alpha$. Если взять $\alpha$ больше, чем $1/L$, например $\alpha = 1$ вместо $\alpha=0{,}5$ для той же функции $f(x,y)=(x-3)^2+(y-0{,}3)^2$ с $L=2$, градиентная часть шага станет нестабильной: $x_0 - 1\cdot(-6,-0{,}6) = (6,\ 0{,}6)$ — шаг перепрыгивает истинный минимум $(3,0{,}3)$ по каждой координате, и последующий прокс лишь частично компенсирует этот перелёт. Условие $\alpha \le 1/L$ для проксимального градиентного метода — это то же самое требование на длину шага, что и для обычного градиентного спуска на гладких функциях, распространённое на проксимальную версию без изменений.

Почему это важно

Формула проксимального градиентного шага — это конкретный, вычислимый рецепт: один обычный шаг по градиенту плюс одно применение (часто аналитической) формулы прокса. Когда негладкая часть — это $L_1$-норма, этот рецепт превращается в конкретный алгоритм ISTA, разобранный ниже, а когда негладкая часть — индикатор множества, тот же самый рецепт превращается в хорошо знакомый проецируемый градиентный спуск. Универсальность формулы и означает, что одна и та же вычислительная схема покрывает регуляризацию, ограничения и их комбинации без необходимости придумывать отдельный алгоритм под каждый случай.

Проксимальный оператор L1-нормы: мягкое пороговое отображение и разреженность Lasso

Интуиция

Для $g(x) = \lambda|x|$ (скалярный случай) прокс ищет компромисс между двумя тянущими силами: квадратичный «якорь» тянет решение к исходной точке $v$, а штраф $\lambda|x|$ тянет решение к нулю (поскольку $|x|$ минимальна именно при $x=0$). Если $v$ уже достаточно близко к нулю — тяга к нулю побеждает полностью, и решение обнуляется ровно, а не приближённо. Если $v$ далеко от нуля — тяга к нулю лишь немного сдвигает решение в сторону нуля на фиксированную величину, а знак и «дальность» точки сохраняются. Ключевое отличие от штрафа $\lambda x^2$ (квадратичного, как в Ridge) в том, что $|x|$ имеет излом в нуле — постоянный по модулю «наклон» штрафа $\lambda$ в обе стороны от нуля, который не ослабевает по мере приближения к нулю, в отличие от штрафа $2\lambda x$, сила которого линейно падает до нуля вместе с $x$. Именно этот излом и создаёт возможность точного, а не асимптотического, попадания в ноль.

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

Теорема (мягкое пороговое отображение). Для $g(x) = \lambda|x|$ при $\lambda > 0$, $x \in \mathbb{R}$:

$$\mathrm{prox}_{\lambda|\cdot|}(v) = S_\lambda(v) = \mathrm{sign}(v)\max(|v|-\lambda,\ 0) = \begin{cases} v - \lambda, & v > \lambda \\ 0, & |v| \le \lambda \\ v + \lambda, & v < -\lambda \end{cases}$$

Доказательство. По определению нужно найти $x^\star = \arg\min_x h(x)$, где $h(x) = \frac{1}{2}(x-v)^2 + \lambda|x|$. Функция $h$ выпукла (сумма выпуклых функций), поэтому необходимое и достаточное условие минимума — включение нуля в субдифференциал: $0 \in \partial h(x^\star)$.

Случай $x^\star > 0$. Здесь $|x|$ гладкая с производной $1$, поэтому $h'(x) = (x-v) + \lambda$. Условие $h'(x^\star)=0$ даёт $x^\star = v - \lambda$. Такое решение допустимо (согласовано с предположением $x^\star>0$) только если $v - \lambda > 0$, то есть $v > \lambda$.

Случай $x^\star < 0$. Симметрично, $h'(x) = (x-v) - \lambda$, откуда $x^\star = v+\lambda$, допустимо при $v < -\lambda$.

Случай $x^\star = 0$. Субдифференциал модуля в нуле — весь отрезок $\partial|0| = [-1,1]$ (это уже встречалось в уроке про субградиентные методы), поэтому субдифференциал $h$ в нуле — это $\partial h(0) = (0-v) + \lambda[-1,1] = [-v-\lambda,\ -v+\lambda]$. Условие $0 \in \partial h(0)$ равносильно $-v-\lambda \le 0 \le -v+\lambda$, то есть $-\lambda \le v \le \lambda$, иначе говоря $|v|\le\lambda$.

Три случая исчерпывают все возможные значения $v$ и не пересекаются, поэтому единственное решение $x^\star$ в каждом случае и есть искомый прокс — что в точности совпадает с формулой $S_\lambda(v)$. $\blacksquare$

Для векторной $L_1$-нормы $g(x)=\lambda\|x\|_1 = \lambda\sum_i |x_i|$ формула применяется покоординатно: $\mathrm{prox}_{\lambda\|\cdot\|_1}(v)_i = S_\lambda(v_i)$ для каждой координаты $i$ отдельно, поскольку и квадрат нормы $\|x-v\|^2 = \sum_i (x_i-v_i)^2$, и $L_1$-норма — суммы независимых слагаемых по координатам, а минимизация суммы независимых одномерных функций сводится к независимой минимизации каждого слагаемого.

Примеры

Пример 1: покоординатное мягкое пороговое отображение вектора. Пусть $v = (3,\ 0{,}5,\ -4,\ 0{,}1)$, $\lambda = 1$. Применяем $S_1$ к каждой координате:

Две маленькие координаты, $0{,}5$ и $0{,}1$, обнулились полностью, а две большие, $3$ и $-4$, просто сдвинулись к нулю на единицу, сохранив знак. Ровно это происходит на каждой итерации ISTA при обучении Lasso: слабо информативные признаки (маленькое значение после градиентного шага) вылетают из модели, сильно информативные — остаются с небольшим смещением.

Пример 2: возврат к флагманскому примеру. В разобранном выше проксимальном градиентном шаге для $f(x,y)=(x-3)^2+(y-0{,}3)^2$, $\lambda=1$, $\alpha=0{,}5$, после градиентного шага получилась точка $(3, 0{,}3)$, а эффективный порог составил $\alpha\lambda=0{,}5$. По только что доказанной теореме: для первой координаты $v=3 > 0{,}5$, значит $S_{0{,}5}(3) = 3-0{,}5=2{,}5$; для второй координаты $|v|=0{,}3 \le 0{,}5$, значит $S_{0{,}5}(0{,}3)=0$. Результат $x_1=(2{,}5,\ 0)$ в точности совпадает с тем, что было получено раньше — теперь это не просто наблюдение, а прямое следствие доказанной формулы.

Пример 3: почему $L_2$-штраф (Ridge) так себя не ведёт. Для сравнения вычислим прокс для гладкого квадратичного штрафа $g(x) = \lambda x^2$ (формально прокс определён и для гладких функций, хотя обычно им пользуются только когда нужен для негладкой части; здесь он нужен исключительно для контраста). Минимизируем $h(x) = \frac{1}{2}(x-v)^2 + \lambda x^2$: производная $h'(x) = (x-v)+2\lambda x = 0$ даёт $x(1+2\lambda) = v$, то есть

Возьмём те же числа, что и для второй координаты флагманского примера: $v=0{,}3$, $\lambda=0{,}5$. Тогда $\mathrm{prox}_{0{,}5(\cdot)^2}(0{,}3) = \dfrac{0{,}3}{1+1} = 0{,}15$ — заметно уменьшилось, но осталось строго положительным. Формула $v/(1+2\lambda)$ даёт ровно ноль только тогда, когда сам $v$ уже был нулём — при любом ненулевом $v$ результат остаётся ненулевым вне зависимости от того, насколько велико $\lambda$. Сравни это с $S_\lambda(v)$: мягкое пороговое отображение содержит целую область $|v|\le\lambda$, при попадании в которую результат становится точно нулём — этой области у квадратичного штрафа попросту нет, потому что $x^2$ не имеет излома в нуле, и его «сила притяжения к нулю» линейно ослабевает по мере приближения $x$ к нулю, а не остаётся постоянной, как у $|x|$.

Почему это важно

Это ровно тот механизм, который объясняет главный практический факт про Lasso: при обучении на каждой итерации ISTA координата, отвечающая слабому или шумному признаку, после градиентного шага получает маленькое значение — и мягкое пороговое отображение обнуляет её полностью и точно. Координата, отвечающая по-настоящему информативному признаку, получает большое значение после градиентного шага, и мягкое пороговое отображение лишь немного сдвигает её, сохраняя знак и относительную величину. Повторяясь итерацию за итерацией, этот процесс и есть автоматический отбор признаков — не эвристика поверх регрессии, а прямое следствие геометрии $L_1$-нормы, формализованное доказанной выше теоремой.

ISTA и FISTA

Интуиция

ISTA (Iterative Shrinkage-Thresholding Algorithm, итеративный алгоритм сжатия-порогового отображения) — это не новый алгоритм, а просто название проксимального градиентного шага из предыдущего раздела в частном случае $g(x)=\lambda\|x\|_1$: на каждой итерации делается обычный градиентный шаг по гладкой части, а затем результат «сжимается» мягким пороговым отображением. FISTA (Fast ISTA) добавляет к этой схеме ускоряющий трюк, знакомый по методу Нестерова для гладкой выпуклой оптимизации: вместо того чтобы вычислять градиент в последней найденной точке $x_k$, его вычисляют в специально экстраполированной точке $y_k$, которая забегает немного вперёд по направлению недавнего движения — как будто алгоритм не просто идёт к минимуму, а ещё и учитывает набранную «инерцию».

Формальное определение

ISTA.

$$x_{k+1} = S_{\alpha\lambda}\bigl(x_k - \alpha\nabla f(x_k)\bigr), \qquad \alpha \le \frac{1}{L}$$

Сходимость: $F(x_k) - F(x^\star) = O(1/k)$.

FISTA. Инициализация: $y_1 = x_0$, $t_1 = 1$. На каждой итерации $k = 1, 2, \dots$:

$$x_k = S_{\alpha\lambda}\bigl(y_k - \alpha\nabla f(y_k)\bigr)$$$$t_{k+1} = \frac{1 + \sqrt{1 + 4t_k^2}}{2}$$$$y_{k+1} = x_k + \frac{t_k - 1}{t_{k+1}}(x_k - x_{k-1})$$

Сходимость: $F(x_k) - F(x^\star) = O(1/k^2)$.

import numpy as np

def soft_threshold(v, threshold):
    return np.sign(v) * np.maximum(np.abs(v) - threshold, 0.0)

def ista_step(x, grad_f, alpha, lam):
    return soft_threshold(x - alpha * grad_f(x), alpha * lam)

def fista(x0, grad_f, alpha, lam, n_iters):
    x_prev, y, t = x0.copy(), x0.copy(), 1.0
    for _ in range(n_iters):
        x = soft_threshold(y - alpha * grad_f(y), alpha * lam)
        t_next = (1 + np.sqrt(1 + 4 * t**2)) / 2
        y = x + ((t - 1) / t_next) * (x - x_prev)
        x_prev, t = x, t_next
    return x_prev

Примеры

Пример 1: сколько итераций нужно на практике. Пусть требуется достичь точности $\varepsilon = 0{,}001$ по зазору $F(x_k)-F(x^\star)$, а константа в оценке сходимости примерно равна единице. Для ISTA из $O(1/k)$ получаем $k \approx 1/\varepsilon = 1000$ итераций. Для FISTA из $O(1/k^2)$ получаем $k^2 \approx 1/\varepsilon$, то есть $k \approx \sqrt{1000} \approx 32$ итерации. Ускорение почти в 30 раз при том, что стоимость одной итерации FISTA отличается от ISTA лишь одним дополнительным векторным сложением — экстраполяцией.

Пример 2: числовая трасса коэффициентов момента. Начнём с $t_1=1$. Тогда $t_2 = \dfrac{1+\sqrt{1+4\cdot 1^2}}{2} = \dfrac{1+\sqrt5}{2} \approx 1{,}618$ — это в точности золотое сечение $\varphi$. Коэффициент экстраполяции на первом шаге: $\dfrac{t_1-1}{t_2} = \dfrac{0}{1{,}618} = 0$ — значит, самый первый шаг FISTA полностью совпадает с обычным шагом ISTA, что согласуется с инициализацией $y_1=x_0$. Дальше: $t_3 = \dfrac{1+\sqrt{1+4\cdot 1{,}618^2}}{2} \approx \dfrac{1+\sqrt{11{,}47}}{2} \approx 2{,}193$, и коэффициент экстраполяции на втором шаге $\dfrac{t_2-1}{t_3} = \dfrac{0{,}618}{2{,}193} \approx 0{,}282$. Ещё через шаг $t_4 \approx 2{,}749$, коэффициент $\approx \dfrac{1{,}193}{2{,}749} \approx 0{,}434$. Коэффициент экстраполяции монотонно растёт к единице по мере накопления итераций — алгоритм постепенно «доверяет» инерции всё сильнее.

Пример 3: где это реально работает. В компрессированном восстановлении сигналов (compressed sensing) — например, в ускоренной реконструкции изображений МРТ по неполным измерениям — гладкая часть представляет собой ошибку рассогласования с измерениями, а негладкая часть — $L_1$-штраф на коэффициенты сигнала в вейвлет-базисе, что заставляет восстановленный сигнал быть разреженным в этом базисе; именно алгоритмы семейства ISTA/FISTA лежат в основе таких реконструкций. В регуляризованных линейных моделях библиотеки вроде glmnet и решатели для group lasso используют проксимальные градиентные методы напрямую, а в самом scikit-learn для классического Lasso по умолчанию применяется покоординатный спуск (тема следующего урока), но библиотеки для сильно разреженных и крупномасштабных задач (например, восстановление матриц низкого ранга, обучение с $L_1$-регуляризацией на миллионах признаков в потоковой обработке) регулярно опираются именно на ISTA/FISTA.

Почему это важно

Разница между $O(1/k)$ и $O(1/k^2)$ не абстрактная: на задачах с сотнями тысяч признаков (геномика, обработка текста с огромными разреженными признаковыми пространствами) она превращает часы вычислений в минуты. При этом FISTA не требует ничего сверх того, что уже есть у ISTA — тот же градиент гладкой части, тот же проксимальный оператор, только одна дополнительная экстраполяция между шагами — поэтому на практике FISTA почти всегда предпочтительнее ISTA при прочих равных условиях.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Вычисли $\mathrm{prox}_{1\cdot|\cdot|}(2{,}7)$.

Задание 2: Вычисли $\mathrm{prox}_{1\cdot|\cdot|}(0{,}4)$.

Задание 3: Вычисли $\mathrm{prox}_{2\cdot|\cdot|}(-5)$.

Задание 4: Дан вектор $v = (4,\ -0{,}3,\ 1{,}5,\ -2)$, $\lambda = 1$. Вычисли покоординатное мягкое пороговое отображение $S_1(v)$.

Задание 5: Для $f(x) = (x-5)^2$ найди липшицеву константу $L$ градиента и максимально допустимый шаг $\alpha=1/L$.

Задание 6: Для той же $f(x)=(x-5)^2$ и $x_0=0$ сделай один шаг обычного градиентного спуска (без регуляризации, $g=0$) с $\alpha=0{,}5$.

Задание 7: Пусть $g$ — индикатор множества $[0,\infty)$. Вычисли $\mathrm{prox}_{\alpha g}(-3)$.

Задание 8: Объясни, чему равен $\mathrm{prox}_{\alpha\cdot 0}(7)$ и почему.

Задание 9: Вычисли $\mathrm{prox}_{\lambda(\cdot)^2}(v)$ при $v=6$, $\lambda=0{,}5$, и сравни с $S_{0{,}5}(6)$ (мягким пороговым отображением с теми же числами).

Задание 10: Почему проксимальный оператор выпуклой функции $g$ всегда определён однозначно — как единственная точка, а не множество?

Продвинутые задания (11–20)

Задание 11: Для $f(x,y)=(x-4)^2+(y-0{,}1)^2$, $g(x,y)=|x|+|y|$ ($\lambda=1$), $x_0=(0,0)$, $\alpha=0{,}5$ вычисли один проксимальный градиентный шаг $x_1$.

Задание 12: Для $f(x,y)=(x-0{,}15)^2+(y-5)^2$, тех же $g$, $\lambda=1$, $\alpha=0{,}5$, $x_0=(0,0)$ вычисли $x_1$.

Задание 13: Проверь, что $x^\star=1$ — точка минимума $h(x)=\frac{1}{2}(x-3)^2+2|x|$, вычислив производную $h$ в этой точке.

Задание 14: Заверши вывод формулы проксимального градиентного шага: покажи, как выражение $\nabla f(x_k)^\top(x-x_k) + \frac{1}{2\alpha}\|x-x_k\|^2$ сворачивается в $\frac{1}{2\alpha}\|x-(x_k-\alpha\nabla f(x_k))\|^2$ плюс константа.

Задание 15: Для $f(x)=\frac{1}{2}\|Ax-b\|^2$, $A=\mathrm{diag}(3,\ 0{,}5)$, $b=(6,1)$, вычисли $L$, $\alpha=1/L$ и градиентный шаг из $x=(0,0)$.

Задание 16: Продолжи задание 15: примени мягкое пороговое отображение с $\lambda=1$ и порогом $\alpha\lambda$. Какая координата обнулится и почему?

Задание 17: Вычисли коэффициенты $t_1, t_2, t_3$ последовательности FISTA и коэффициенты экстраполяции $(t_1-1)/t_2$ и $(t_2-1)/t_3$.

Задание 18: Если ISTA требует около 1000 итераций для точности $\varepsilon=0{,}001$ (сходимость $O(1/k)$), сколько итераций примерно требует FISTA (сходимость $O(1/k^2)$) для той же точности?

Задание 19: Почему FISTA вычисляет градиент в экстраполированной точке $y_k$, а не в последней найденной точке $x_k$?

Задание 20: Запиши формулу проецируемого градиентного спуска как частный случай проксимального градиентного шага при $g=\iota_C$.

Задания-челленджи (21–30)

Задание 21: Обоснуй, почему для любого выпуклого $g$ и любого $\alpha>0$ проксимальный оператор существует и однозначен, без явного решения конкретной формулы.

Задание 22: Покажи, что при $\lambda\to0$ мягкое пороговое отображение $S_\lambda(v)$ стремится к $v$.

Задание 23: Покажи, что при $\lambda\to\infty$ мягкое пороговое отображение $S_\lambda(v)$ стремится к $0$ для любого конечного $v$.

Задание 24: Используя числа из заданий 15–16, объясни в терминах машинного обучения, почему такое поведение называют автоматическим отбором признаков.

Задание 25: Почему на практике часто используют адаптивный линейный поиск (backtracking) для выбора $\alpha$ в ISTA/FISTA вместо фиксированного $\alpha=1/L$?

Задание 26: Для эластичной сети $f(x)=\frac{1}{2}\|Ax-b\|^2+\frac{\alpha_2}{2}\|x\|_2^2$, $g(x)=\lambda\|x\|_1$ объясни, почему $L_2$-слагаемое должно входить в $f$, а не в $g$, и как это влияет на формулу прокс-шага.

Задание 27: Докажи в общем виде, почему прокс векторной $L_1$-нормы сводится к покоординатному применению скалярного мягкого порогового отображения.

Задание 28: Почему для сильно выпуклой гладкой части $f$ (например, за счёт добавленного $L_2$-слагаемого в эластичной сети) сходимость ISTA/FISTA улучшается до линейной, а не остаётся сублинейной?

Задание 29: Следующий урок посвящён покоординатному спуску, который решает Lasso, точно минимизируя по одной координате за раз при фиксированных остальных. Объясни, почему точная одномерная минимизация по координате Lasso тоже сводится к формуле мягкого порогового отображения.

Задание 30: Обобщи в двух-трёх предложениях: чем проксимальные методы (урок 291) концептуально отличаются от субградиентных методов (урок 290) в подходе к задаче $f(x)+\lambda\|x\|_1$, и какую цену и какую выгоду даёт это отличие?

Частые ошибки

Ошибка 1. Считают проксимальный оператор просто другим названием проекции на множество.

Как выглядит: «$\mathrm{prox}_{\alpha g}(v)$ — это всегда какая-то проекция $v$ куда-то».

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

Как правильно: прокс совпадает с проекцией только тогда, когда $g$ — индикатор множества. Для других функций, например для $g=\lambda|\cdot|$, результат — не «ближайшая точка в каком-то множестве», а решение отдельной задачи компромисса между близостью к $v$ и минимизацией $g$, и оно, как показывает soft thresholding, может как сдвигать точку (для больших $|v|$), так и обнулять её (для маленьких $|v|$) — двух разных режимов поведения у чистой проекции не бывает.

Ошибка 2. Считают, что мягкое пороговое отображение — это эвристика «округли маленькие значения до нуля», а не точное решение конкретной задачи оптимизации.

Как выглядит: «soft thresholding — это просто способ занулить шум, как в вейвлет-сжатии картинок».

Почему возникает: внешне формула действительно напоминает пороговую обработку сигнала, и в исторических источниках (Добеши и соавторы) она и появилась именно в контексте обработки сигналов.

Как правильно: формула $S_\lambda(v)=\mathrm{sign}(v)\max(|v|-\lambda,0)$ — это доказанное, единственное решение задачи $\arg\min_x \frac12(x-v)^2+\lambda|x|$, а не эвристика; при этом она не только зануляет маленькие значения, но и сдвигает большие на постоянную величину $\lambda$ — округлением к ближайшему это назвать нельзя.

Ошибка 3. Путают поведение $L_1$- и $L_2$-регуляризации, полагая, что обе дают разреженность, просто «в разной степени».

Как выглядит: «если увеличить силу Ridge-регуляризации, коэффициенты тоже в конце концов обнулятся».

Почему возникает: обе регуляризации визуально «сжимают» веса к нулю на графике коэффициентов в зависимости от силы штрафа, и график действительно показывает похожее направление тренда.

Как правильно: формула прокса Ridge-подобного штрафа $v/(1+2\lambda)$ даёт ровно ноль только при уже нулевом $v$ и ни при каком конечном $\lambda$ не обнулит ненулевой $v$ точно; только штраф с изломом в нуле (как $L_1$) создаёт целую зону $|v|\le\lambda$, при попадании в которую результат становится точно нулём.

Ошибка 4. Забывают про ограничение на шаг $\alpha\le1/L$ для проксимального градиентного метода, считая, что раз есть «умный» прокс-шаг, требования к длине шага смягчаются.

Как выглядит: берут произвольно большой шаг $\alpha$, полагая, что прокс сам «исправит» любые проблемы с расходимостью.

Почему возникает: прокс действительно точно решает свою вспомогательную задачу, и кажется, что эта точность компенсирует слишком грубый градиентный шаг.

Как правильно: условие $\alpha\le1/L$ гарантирует сходимость именно градиентной («вперёд») части шага — прокс лишь корректно обрабатывает негладкую часть на основе уже вычисленной (потенциально «перелетевшей» минимум) точки, и слишком большой $\alpha$ приводит к тем же проблемам с расходимостью, что и в обычном градиентном спуске.

Ошибка 5. Реализуя FISTA, вычисляют градиент в точке $x_k$ вместо экстраполированной точки $y_k$.

Как выглядит: копируют формулу ISTA и добавляют экстраполяцию $y_{k+1}$ только для следующего шага, но градиент по-прежнему берут в $x_k$.

Почему возникает: формула FISTA внешне похожа на ISTA с добавленным «довеском» в конце, и легко не заметить, что именно точка вычисления градиента, а не только формула обновления $x$, должна измениться.

Как правильно: всё ускорение FISTA держится именно на том, что градиент вычисляется в экстраполированной точке $y_k$, а не в $x_k$ — пропуск этого шага превращает FISTA обратно в обычный ISTA (или, что хуже, в неверно реализованный алгоритм с непредсказуемым поведением), не давая обещанного ускорения до $O(1/k^2)$.

Ошибка 6. Считают, что проксимальные методы применимы только к простым штрафам вроде $L_1$-нормы.

Как выглядит: «прокс-методы — это специальный трюк только для Lasso».

Почему возникает: $L_1$-норма — самый известный и самый часто разбираемый пример, и его легко принять за границу применимости всего семейства методов.

Как правильно: проксимальные методы работают с любой выпуклой $g$, для которой есть эффективно вычислимый прокс — индикаторы множеств (ограниченная оптимизация), ядерная норма (восстановление матриц низкого ранга), групповые нормы (group lasso, отбор целых групп признаков), полная вариация (шумоподавление изображений) — всё это имеет собственные закрытые или быстро вычислимые формулы прокса и укладывается в ту же самую общую схему.

Главное запомнить

• Задача проксимальной оптимизации имеет вид $F(x)=f(x)+g(x)$, где $f$ гладкая с липшицевым градиентом, а $g$ выпуклая (возможно негладкая), но с эффективно вычислимым прокс-оператором.

• Проксимальный оператор $\mathrm{prox}_{\alpha g}(v)=\arg\min_x\{g(x)+\frac{1}{2\alpha}\|x-v\|^2\}$ обобщает проекцию на множество: для $g=\iota_C$ он в точности совпадает с проекцией $\Pi_C$.

• Проксимальный градиентный шаг $x_{k+1}=\mathrm{prox}_{\alpha g}(x_k-\alpha\nabla f(x_k))$ выводится минимизацией квадратичной мажоранты гладкой части плюс точной негладкой части — «шаг вперёд» по градиенту, «шаг назад» через прокс.

• Для $g(x)=\lambda|x|$ прокс доказуемо равен мягкому пороговому отображению $S_\lambda(v)=\mathrm{sign}(v)\max(|v|-\lambda,0)$, доказательство строится на условии оптимальности $0\in\partial h(x^\star)$ по трём случаям знака.

• Soft thresholding точно обнуляет координаты с $|v|\le\lambda$ и сдвигает остальные на $\lambda$, сохраняя знак — это и есть прямой механизм отбора признаков в Lasso.

• Прокс квадратичного (Ridge-подобного) штрафа даёт $v/(1+2\lambda)$ — мультипликативное сжатие без излома в нуле, поэтому Ridge никогда не даёт точного нуля при ненулевом $v$ и никакого автоматического отбора признаков.

• ISTA — это в точности проксимальный градиентный шаг при $g=\lambda\|\cdot\|_1$, сходится со скоростью $O(1/k)$; шаг $\alpha$ должен удовлетворять $\alpha\le1/L$, как и в обычном градиентном спуске.

• FISTA добавляет экстраполяцию (вычисление градиента в точке $y_k$, а не $x_k$) по образцу ускорения Нестерова и достигает скорости $O(1/k^2)$ практически без роста стоимости итерации.

• Прокс векторной $L_1$-нормы разделяется покоординатно благодаря тому, что и квадрат нормы, и сама $L_1$-норма — суммы независимых по координатам слагаемых.

• Проксимальные методы образуют единый шаблон, покрывающий регуляризацию ($L_1$, ядерная норма, групповые нормы), ограничения (через индикаторы) и их комбинации — именно универсальность прокс-оператора делает семейство методов широко применимым за пределами одного только Lasso.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок напрямую опирается на предыдущий урок 290 о субградиентных методах: без понимания того, что такое субдифференциал $\partial|x|$ и почему модуль не дифференцируем в нуле, доказательство формулы мягкого порогового отображения через условие $0\in\partial h(x^\star)$ было бы непонятным техническим трюком, а не логичным продолжением уже освоенного инструмента. Также понадобилось понятие липшицевой константы градиента и требования $\alpha\le1/L$ из уроков про градиентный спуск (285) и метод Ньютона (287), а понятие сильной выпуклости и коэрцитивности — из урока про выпуклые функции (278), на котором держится доказательство единственности прокс-оператора.

Что изучить дальше

Следующий урок 292 разбирает покоординатный спуск — алгоритм, который решает ту же задачу Lasso совершенно другим путём: вместо общего градиентного шага по всем координатам сразу он точно минимизирует по одной координате за раз, зафиксировав остальные. Задание 29 этого урока уже показало главную связь: точное покоординатное решение задачи Lasso по одной переменной снова сводится к той же формуле мягкого порогового отображения — soft thresholding оказывается не специфичным для проксимального градиентного метода трюком, а фундаментальным строительным блоком, который переиспользуется в алгоритмах с совсем другой структурой.

Lasso против Ridge: откуда на самом деле берётся разреженность

Стоит проговорить это прямо и явно, поскольку весь урок был построен вокруг именно этого вопроса. И Lasso, и Ridge решают похожую задачу — минимизацию среднеквадратичной ошибки с добавленным штрафом на величину коэффициентов, — но принципиально по-разному ведут себя на маленьких коэффициентах, и разница объясняется не «силой» регуляризации, а геометрией штрафной функции в окрестности нуля.

Штраф Ridge, $\lambda\|x\|_2^2$, всюду гладкий и дифференцируемый, включая ноль: его производная в точке $x$ равна $2\lambda x$ и линейно стремится к нулю по мере приближения $x$ к нулю. Как было явно вычислено в разделе про soft thresholding, проксимальный оператор такого штрафа — это $v/(1+2\lambda)$: результат приближается к нулю пропорционально, но никогда не достигает его точно ни при каком конечном $\lambda$, если исходное $v$ было ненулевым. Геометрически штраф Ridge — гладкая парабола, и её «сила притяжения» к нулю ослабевает ровно там, где нужна была бы наибольшая сила, чтобы преодолеть последний шаг до нуля.

Штраф Lasso, $\lambda\|x\|_1$, имеет излом в нуле: его «наклон» константен и равен $\lambda$ по обе стороны от нуля, вплоть до самого нуля, и субдифференциал в самой точке нуля — целый отрезок $[-\lambda,\lambda]$. Доказанная в этом уроке формула мягкого порогового отображения показывает прямое следствие этого излома: существует целая зона входных значений $|v|\le\lambda$, для которых решение вспомогательной задачи прокса — это точно ноль, а не предел, к которому стремится ответ. Именно постоянство (а не убывание) силы штрафа вблизи нуля и создаёт возможность точного попадания в ноль за конечное число итераций.

Практическое следствие для машинного обучения прямое: Lasso используют, когда среди множества признаков ожидается, что часть из них не несёт полезной информации, и хочется получить не просто регуляризованную, но и интерпретируемую, разреженную модель — например, в геномике, где из десятков тысяч генов реально значимы единицы, или в задачах с сильно избыточными признаковыми пространствами (текстовые n-граммы, автоматически сгенерированные признаки). Ridge используют, когда все признаки предположительно несут хоть какую-то информацию и цель регуляризации — бороться с мультиколлинеарностью и переобучением, не удаляя признаки из модели вовсе. Elastic net, разобранный в примерах этого урока, — практический компромисс, использующий оба штрафа одновременно, где $L_2$-часть идёт в гладкую часть задачи (стабилизирует решение при сильно коррелированных признаках), а $L_1$-часть по-прежнему обрабатывается прокс-оператором и отвечает за разреженность.

Где это нужно в жизни

📊 Регуляризованные линейные модели. Lasso, elastic net и group lasso в задачах с большим числом признаков (биоинформатика, эконометрика с сотнями потенциальных предикторов, задачи с автоматически сгенерированными признаками) полагаются на проксимальные методы или на алгебраически эквивалентный покоординатный спуск как на вычислительный движок, обеспечивающий одновременно регуляризацию и отбор признаков за один проход обучения.

🖼️ Обработка сигналов и изображений. Компрессированное восстановление сигналов (compressed sensing), в том числе ускоренная реконструкция изображений МРТ по неполным измерениям, и шумоподавление изображений через штраф полной вариации (total variation) напрямую используют проксимальные градиентные методы, эксплуатируя разреженность сигнала в подходящем базисе (вейвлеты, градиенты изображения).

🧬 Восстановление структуры данных. Восстановление матриц низкого ранга (matrix completion, например в рекомендательных системах) использует ту же самую схему проксимального градиентного метода, только вместо мягкого порогового отображения к сингулярным числам применяется его матричный аналог — сингулярное пороговое отображение (singular value thresholding), доказываемое тем же приёмом.

⚙️ Инфраструктура обучения моделей. Понимание того, что soft thresholding — не изолированный трюк, а фундаментальная операция, которая переиспользуется и в проксимальном градиентном методе, и в покоординатном спуске следующего урока, и в различных вариациях стохастических методов с $L_1$-регуляризацией (proximal SGD, FTRL-подобные онлайн-алгоритмы), помогает быстро узнавать одну и ту же математику под разными именами в разных библиотеках и статьях.

Интересные факты

• Жан-Жак Моро ввёл проксимальный оператор в 1962 году как чисто теоретическую конструкцию функционального анализа в гильбертовых пространствах, не имея в виду ни оптимизацию как вычислительную дисциплину, ни тем более машинное обучение — практическая ценность его конструкции для алгоритмов регуляризованной регрессии раскрылась лишь спустя несколько десятилетий.

• Формулу мягкого порогового отображения независимо переоткрыли исследователи цифровой обработки сигналов Ингрид Добеши, Мишель Дефриз и Кристин Де Мол в 2004 году в контексте восстановления разреженных сигналов по вейвлет-коэффициентам — они пришли к той же самой формуле совершенно другим путём и по другим мотивам, чем абстрактная теория Моро сорока годами ранее.

• В последовательности коэффициентов момента FISTA второе значение $t_2=\frac{1+\sqrt5}{2}\approx1{,}618$ оказывается в точности золотым сечением — редкий случай, когда число, знакомое ещё античным математикам, естественным образом всплывает в формуле ускоряющего трюка современного алгоритма машинного обучения.

• Алгоритм ISTA/FISTA лежит в основе ускоренной реконструкции изображений в магнитно-резонансной томографии: за счёт эксплуатации разреженности сигнала в подходящем базисе такие методы позволяют восстанавливать диагностически качественное изображение по значительно меньшему числу измерений, чем требует классическая теорема Найквиста — Шеннона, сокращая время сканирования пациента.

Лайфхаки

• Перед тем как реализовывать субградиентный спуск вручную для своего кастомного регуляризатора, проверь, есть ли у него известный закрытый прокс-оператор (индикаторы множеств, $L_1$, квадрат $L_2$, ядерная норма, групповые нормы, полная вариация — у всех есть) — если есть, проксимальный метод почти всегда быстрее и точнее.

• По умолчанию выбирай FISTA, а не «обычную» ISTA: дополнительная экстраполяция стоит одного векторного сложения на итерацию, а выигрыш в скорости сходимости от $O(1/k)$ до $O(1/k^2)$ часто оказывается решающим на больших задачах.

• Если точную липшицеву константу $L$ дорого вычислять (например, наибольшее сингулярное значение огромной матрицы признаков), используй адаптивный подбор шага (backtracking line search) вместо того, чтобы гадать с фиксированным $\alpha$ — слишком большой шаг ломает сходимость, слишком маленький бесполезно её замедляет.

• Если библиотечный решатель Lasso выдаёт коэффициенты, которые «почти ноль, но не совсем», прежде чем удивляться отсутствию честной разреженности, проверь число итераций и критерий сходимости — недостаточно сошедшийся проксимальный или покоординатный метод даёт именно такую картину, а не потому, что алгоритм «на самом деле» ведёт себя как Ridge.

• Держи в голове флагманский численный пример этого урока (маленькая координата обнуляется, большая только сдвигается) как быстрый ментальный тест: если предложенная кем-то регуляризация не имеет излома в нуле — задай себе вопрос, сможет ли она вообще дать точный ноль, прежде чем доверять заявлениям о её «разреженности».

• При отладке собственной реализации FISTA в первую очередь проверяй, что градиент вычисляется именно в экстраполированной точке $y_k$, а не в последнем найденном $x_k$ — это самая частая причина, по которой «ускоренный» алгоритм на практике не показывает обещанного ускорения.

Урок про субградиентные методы научил тебя честно работать с негладкостью, когда о структуре задачи ничего особенного не известно. Этот урок показал, что происходит, когда структура известна и её можно использовать: задача аккуратно распадается на дешёвый градиентный шаг и точную, доказанную формулу для негладкой части, а в случае $L_1$-регуляризации эта формула оказывается не абстракцией, а прямым, проверяемым объяснением того, почему Lasso делает то, что делает. В следующем уроке ты увидишь ту же самую формулу мягкого порогового отображения ещё раз, но выведенную совершенно другим путём — через точную покоординатную минимизацию, — и это станет лишним подтверждением того, что за разными на вид алгоритмами машинного обучения часто стоит одна и та же небольшая группа фундаментальных математических идей.