Proximal методы: операторы для non-smooth optimization

Adam, SGD - отлично работают для smooth objectives. Но что если loss содержит $\|x\|_1$ для разрежённости? Constraint $\|x\| \leq R$ для устойчивости? Indicator simplex для probability simplex? Proximal operator превращает каждый non-smooth блок в простую subproblem - часто с closed-form решением. ISTA, FISTA, ADMM - три способа использовать его в production: от scikit-learn LASSO до Spark MLlib на TB-датасетах. Знание этих методов - граница между 'умею регуляризовать гладкие модели' и 'умею писать solver для произвольной convex задачи с регуляризатором или ограничением'.

• **scikit-learn `Lasso`** - под капотом coordinate descent с soft-thresholding на каждой координате - proximal $\ell_1$ в чистом виде
• **Apache Spark MLlib** - distributed LASSO на TB-данных через ADMM с row-partition-параллелизмом, классический пример scalable convex optimization
• **Sparse training в нейросетях** - `torch.nn.utils.prune.l1_unstructured` применяет soft-threshold к весам слоя; FISTA-style updates в кастомных оптимизаторах для structured sparsity

Proximal operator: универсальный кирпич non-smooth optimization

LASSO на 100k признаках: loss = $\frac{1}{2}\|Ax - b\|^2 + \lambda \|x\|_1$. Первая часть гладкая, у неё есть градиент. Вторая - $\ell_1$-норма - в нуле производной не имеет, и весь смысл задачи именно там: subgradient может быть любым числом из $[-\lambda, \lambda]$. Обычный GD на таком objective не работает: шаг будет дёргать координаты вокруг нуля без сходимости. Нужен другой инструмент - тот, что умеет 'выключать' координату ровно в ноль за один шаг.

Этот инструмент - proximal operator. Идея: вместо того чтобы спускаться по градиенту негладкой $f$, решить локальную задачу 'найти точку, близкую к $v$, но с маленьким значением $f$'. Получается универсальный кирпич: для $\ell_1$ он соберётся в soft-thresholding, для индикатора множества - в проекцию, для гладкой $f$ - в обычный gradient step. Один формализм покрывает регуляризацию, ограничения и проекции одновременно.

**Определение proximal operator:** $$\text{prox}_{\lambda f}(v) = \arg\min_x \left[ f(x) + \frac{1}{2\lambda} \|x - v\|^2 \right]$$ **Геометрическая интерпретация:** ближайшая к $v$ точка, балансирующая 'близость к $v$' и 'малость $f$'. Параметр $\lambda > 0$ контролирует баланс: при $\lambda \to 0$ оператор стремится к identity ($x = v$), при $\lambda \to \infty$ - к минимизатору $f$. **Каноничные примеры:** - $f \equiv 0$: $\text{prox}_{\lambda f}(v) = v$ - identity. - $f(x) = \|x\|_1$: **soft-thresholding** $\text{prox}_{\lambda \|\cdot\|_1}(v)_i = \text{sign}(v_i) \cdot \max(|v_i| - \lambda, 0)$. - $f = I_C$ (индикатор выпуклого $C$): $\text{prox}_{\lambda I_C}(v) = \Pi_C(v)$ - проекция на $C$. - $f(x) = \frac{1}{2}\|x\|^2$: $\text{prox}_{\lambda f}(v) = v / (1 + \lambda)$ - shrinkage.

Главное свойство: proximal operator всегда определён однозначно для convex $f$ (квадратичный член делает задачу strongly convex), и его можно вычислить за время порядка размерности задачи для большинства практических $f$. Это превращает негладкую оптимизацию в последовательность простых subproblems - там, где GD спотыкался, proximal делает шаг точно в ноль.

**Где proximal operator работает в production:** - **scikit-learn `Lasso`** - под капотом coordinate descent, но базовая операция на каждой координате - soft-thresholding. - **PyTorch `torch.nn.utils.prune.l1_unstructured`** - применяет soft-threshold к весам слоя для разрежения. - **CVXPY** при разборе задач с $\ell_1$, indicator-ами и пр. строит proximal-граф автоматически. - **Adversarial training** ($\ell_\infty$-PGD) - проекция на $\ell_\infty$-шар через clipping - proximal оператор индикатора box-а.

ISTA: proximal gradient для composite objectives

Реальные ML-задачи почти всегда composite: гладкая часть (data fit) плюс негладкая (регуляризация). LASSO - $\frac{1}{2}\|Ax - b\|^2 + \lambda\|x\|_1$. Group LASSO, elastic net, sparse logistic regression - все одной структуры. Proximal gradient method (ISTA - Iterative Soft-Thresholding Algorithm) - прямое обобщение GD на этот класс: один шаг = gradient step по гладкой части, потом proximal по негладкой.

**Composite optimization:** $$\min_x F(x) = f(x) + g(x)$$ где $f$ - гладкая (например, L-smooth, дифференцируемая), $g$ - негладкая, но 'proximal-friendly' (легко вычислить $\text{prox}_{\eta g}$). **ISTA-итерация:** $$x^{k+1} = \text{prox}_{\eta g}\left(x^k - \eta \nabla f(x^k)\right)$$ Два шага в одном: 1. Gradient step по гладкой $f$: $y^k = x^k - \eta \nabla f(x^k)$. 2. Proximal step по негладкой $g$: $x^{k+1} = \text{prox}_{\eta g}(y^k)$. **Для LASSO** ($f = \frac{1}{2}\|Ax - b\|^2$, $g = \lambda\|x\|_1$): $$x^{k+1} = \text{soft\_threshold}\left(x^k - \eta A^T(Ax^k - b),\ \eta \lambda\right)$$ стандартный LASSO-solver.

Сходимость ISTA при $\eta = 1/L$ (где $L$ - константа Липшица $\nabla f$) даёт $F(x^k) - F^* \leq O(1/k)$ - ровно как GD на чисто гладкой задаче. Никакой потери от негладкости $g$: proximal 'поглощает' её бесплатно. Если $f$ к тому же strongly convex, ISTA становится линейно сходящимся $(1 - \mu/L)^k$, но per-iter cost - один gradient + один proximal - не увеличивается.

**ISTA в practice:** - **Compressed sensing** (восстановление sparse signal по under-determined measurements) - ISTA - первый из работающих методов. - **Image deblurring / denoising** через total variation - $g = \text{TV}$, gradient step по data fidelity, proximal по TV. - **scikit-learn `Lasso`** использует coordinate descent (faster для sparse data), но ISTA - это базовый алгоритм, который объясняет, **почему** LASSO находит разрежённое решение: каждый шаг физически зануляет координаты с малой 'силой'. - **Neural network sparsity:** training с $\ell_1$-регуляризацией через ISTA-style updates даёт модель с реально нулевыми весами (а не просто маленькими).

FISTA: ускорение Nesterov для proximal

ISTA сходится как $O(1/k)$. Но GD на гладкой задаче можно ускорить до $O(1/k^2)$ через Nesterov momentum. Beck и Teboulle в 2009 показали: тот же приём работает и в proximal-настройке. FISTA (Fast ISTA) - простое расширение ISTA с двумя последовательностями итерат и momentum-шагом перед proximal. Per-iteration cost - тот же, что у ISTA. Скорость сходимости - на порядок быстрее.

**FISTA-итерация:** Поддерживаются две последовательности: $x^k$ (текущая итерата) и $y^k$ (extrapolated point). Шаг $k$: 1. Gradient + proximal на $y^k$: $x^{k+1} = \text{prox}_{\eta g}(y^k - \eta \nabla f(y^k))$. 2. Обновление momentum-коэффициента: $t_{k+1} = \frac{1 + \sqrt{1 + 4 t_k^2}}{2}$ (с $t_0 = 1$). 3. Extrapolation: $y^{k+1} = x^{k+1} + \frac{t_k - 1}{t_{k+1}} (x^{k+1} - x^k)$. **Сходимость (Beck, Teboulle 2009):** $$F(x^k) - F^* \leq \frac{2 L \|x^0 - x^*\|^2}{(k + 1)^2} = O(1/k^2)$$ Для strongly convex $f$ - $(1 - 1/\sqrt{\kappa})^k$ вместо ISTA-шного $(1 - 1/\kappa)^k$ - выигрыш в $\sqrt{\kappa}$ раз.

Связь с deep learning: Nesterov momentum в `torch.optim.SGD(momentum=0.9, nesterov=True)` - ровно та же идея extrapolation, только без proximal-этапа. Обновление коэффициента $t_k$ воспроизводит классический Nesterov rate, но в практике DL используют фиксированный momentum 0.9 - проще и устойчивее на шумных стохастических градиентах.

**FISTA в production:** - **TFOCS** (Stanford) - вся библиотека построена вокруг FISTA-варианта. - **CVXPY** при разборе LASSO/group LASSO в SCS-режиме использует FISTA-style backend. - **Image processing pipelines** (MRI reconstruction, CT denoising) - FISTA с TV-регуляризацией стандарт. - **PyTorch L1 regularization** в кастомных оптимизаторах - SOAP, AdamW с decoupled L1 - leverage FISTA-style updates для координатных правил.

ADMM: декомпозиция через proximal

ISTA и FISTA работают, когда задача имеет вид 'гладкое + негладкое'. Но что если негладких слагаемых несколько? Sparse + low-rank decomposition: $\|x\|_1 + \|X\|_*$. Consensus optimization: $\sum_i f_i(x_i)$ с $x_i = z$. Distributed LASSO на 1000 машинах с partition-данных. Здесь FISTA сломается - нужна декомпозиция, при которой каждый кусок objective обрабатывается своим proximal-ом независимо. Это ADMM.

**Alternating Direction Method of Multipliers** для задачи $$\min_{x, z}\ f(x) + g(z)\quad \text{s.t.}\quad Ax + Bz = c$$ Augmented Lagrangian: $$L_\rho(x, z, u) = f(x) + g(z) + u^T(Ax + Bz - c) + \frac{\rho}{2}\|Ax + Bz - c\|^2$$ **Три шага каждой итерации:** 1. **x-update** (proximal-like для $f$): $x^{k+1} = \arg\min_x L_\rho(x, z^k, u^k)$. 2. **z-update** (proximal-like для $g$): $z^{k+1} = \arg\min_z L_\rho(x^{k+1}, z, u^k)$. 3. **dual update**: $u^{k+1} = u^k + \rho(Ax^{k+1} + Bz^{k+1} - c)$. **Killer feature:** $f$ и $g$ обрабатываются **раздельно**, в своих subproblem-ах. Если $f = \sum_i f_i(x_i)$ - x-update распадается на параллельные задачи.

Для LASSO в consensus-форме разбиваем данные $A$ по строкам на $N$ частей: $A_i, b_i$ - на машине $i$. Каждая машина решает локальную ridge regression $\frac{1}{2}\|A_i x_i - b_i\|^2 + \frac{\rho}{2}\|x_i - z + u_i\|^2$ независимо (x-update). Затем все машины присылают $x_i$ на координатор, который применяет soft-threshold (z-update) и рассылает $z$ обратно. Один round = одна итерация. Сходимость - линейная для строго convex, $O(1/k)$ в общем случае.

**ADMM в production:** - **Apache Spark MLlib** - LASSO-solver для TB-датасетов построен на ADMM с partition-параллелизмом. - **Federated learning** - FedAvg алгоритмически близок к ADMM-relaxation: локальные обновления + усреднение через 'координатор'. - **Boyd et al. (2010)** - review paper 'Distributed Optimization and Statistical Learning via ADMM' - 1000+ цитирований, де-факто стандарт для distributed convex optimization. - **Robust PCA** ($\min \|L\|_* + \lambda\|S\|_1$ s.t. $L + S = M$) решается через ADMM: nuclear norm и $\ell_1$ - в разных переменных, естественная декомпозиция.

Сходимость ADMM не такая быстрая на single-machine задаче, как FISTA: per-iteration linear solve дороже proximal step. Параметр $\rho$ требует тюнинга (большой - быстрая dual-сходимость, медленная primal). Но именно эти 'недостатки' - цена за свойство, которое FISTA не даёт: subproblems можно решать параллельно. На huge data ADMM выигрывает по wallclock-у, даже если итераций больше.

Ключевые идеи

• **Proximal operator** $\text{prox}_{\lambda f}(v) = \arg\min_x [f(x) + \frac{1}{2\lambda}\|x - v\|^2]$ - универсальный кирпич: $\ell_1$-soft-threshold, проекция на множество, shrinkage L2 - всё одной формулой
• **ISTA:** $x^{k+1} = \text{prox}_{\eta g}(x^k - \eta\nabla f(x^k))$ - gradient по гладкой $f$ + proximal по негладкой $g$, сходимость $O(1/k)$ как у GD
• **FISTA:** ISTA + Nesterov-extrapolation между итератами, $O(1/k^2)$ при том же per-iter cost - стандартный solver в TFOCS, CVXPY
• **ADMM:** декомпозиция через augmented Lagrangian. x-update, z-update, dual-update раздельно, subproblems параллелизуются - база distributed ML (Spark, federated learning)

Что дальше

Proximal-методы соединяют гладкую теорию GD с реальностью негладких регуляризаторов и ограничений. Дальше - стохастические варианты и приложения:

• Сходимость градиентного спуска — Скорости $O(1/k)$ и $O(1/k^2)$ из cvx-06 переносятся на ISTA и FISTA дословно - proximal не портит rate
• KKT-условия — ADMM - это итеративное решение KKT-системы через augmented Lagrangian; dual-update - градиентный шаг по двойственным переменным
• Двойственность Лагранжа — Augmented Lagrangian внутри ADMM - регуляризованная версия классического Lagrangian; $\rho$ - параметр регуляризации

Вопросы для размышления

• LASSO с $\lambda = 0.01$ на $n = 10^4$, $d = 10^5$. Когда выгоднее ISTA vs FISTA vs ADMM с точки зрения wallclock и memory? Что меняется при $d = 10^7$ и распределённых данных?
• Soft-thresholding обнуляет координаты с $|v_i| < \lambda$. Какое условие на subgradient $\partial \|x\|_1$ в нуле объясняет, что это правильное proximal для $\ell_1$? Как это связано с KKT-условиями LASSO?
• ADMM-параметр $\rho$ влияет на скорость primal vs dual сходимости. Какое адаптивное правило для $\rho$ балансирует две стороны, и почему фиксированный $\rho$ - частая причина медленной сходимости в практике?

Связанные уроки

• cvx-04 — Двойственность Лагранжа - база ADMM (он построен на augmented Lagrangian)
• cvx-05 — Субградиенты определяют, где proximal operator вообще имеет смысл
• cvx-06 — Скорости $O(1/k)$ и $O(1/k^2)$ переносятся на ISTA и FISTA
• cvx-08 — Stochastic и distributed методы - прямое расширение proximal-подхода
• ml-09-gradient-descent — Sparse training в нейросетях через soft-thresholding - proximal в чистом виде
• fa-07