Выпуклая оптимизация
Негладкая оптимизация и проксимальные методы
L1-норма и total variation появляются в сотнях задач обработки сигналов и изображений - но они не дифференцируемы в нуле. Как оптимизировать функции без градиента в ключевых точках?
- MRI-реконструкция: FISTA (Бек и Тебулль, 2009) решает TV-минимизацию для MRI Siemens за секунды - снижение времени сканирования на 50% при том же качестве
- LASSO в геномике: L1-регрессия выбирает 50-100 значимых генов из 500 000 кандидатов; проксимальный метод сходится за 200-500 итераций
- Сжатие нейросетей: L1-регуляризация весов с проксимальным soft-thresholding шагом обнуляет малые веса - структурный прунинг без дополнительных алгоритмов
- Обработка аудио: total variation регуляризация для подавления импульсного шума; ISTA в 10x быстрее субградиентного метода
Предварительные знания
- Выпуклые функции
- Градиентный спуск
- Двойственная теория
Субградиентные методы
Многие задачи оптимизации содержат недифференцируемые функции: L1-регуляризация в Lasso, hinge loss в SVM, total variation в обработке изображений. Классический градиентный спуск к ним напрямую неприменим - градиент в точках излома не существует. Субградиентные методы расширяют GD: используют любой элемент субдифференциала, обобщённого понятия градиента для выпуклых функций.
Субградиентный метод сходится со скоростью O(1/sqrt(k)) даже для гладких выпуклых функций (где GD даёт O(1/k) или быстрее). Это плата за общность: без предположения о дифференцируемости лучшую скорость получить нельзя. Для гладких задач предпочтительнее GD; для негладких - проксимальные методы или акселерация.
Субградиенты не несут информации о значении функции в окрестности: малая норма субградиента не означает близости к оптимуму (как у градиента). Это делает критерий остановки нетривиальным; обычно используется доля от начальной невязки или максимальное число итераций.
Почему субградиентный метод не гарантирует монотонного убывания f?
Проксимальные алгоритмы
Проксимальные алгоритмы (Moreau 1965, Rockafellar 1976) предлагают элегантное решение: вместо борьбы с недифференцируемостью, явно вычисляют проксимальный оператор - аналог шага градиентного спуска для негладкой части. Для большинства практических регуляризаторов (L1, L2, indicator выпуклого множества, nuclear norm) prox-оператор имеет закрытую форму. Это позволяет соединить эффективность GD на гладкой части с точной обработкой негладкой.
Прокс-операторы стандартных функций: для L2-нормы - линейное сжатие; для индикатора выпуклого множества - проекция; для nuclear norm матрицы - soft thresholding сингулярных значений; для total variation - решение задачи Rudin-Osher-Fatemi через GraphCut или dual approach.
Что делает прокс-операторы L1-нормы особенно полезными для разрежённой регрессии?
Bundle-методы: накопление субградиентов
Классический субградиентный метод теряет информацию: используется один субградиент на итерации, остальные забываются. Bundle-методы (Lemarechal 1975, Kiwiel 1985) хранят множество предыдущих субградиентов и строят кусочно-линейную модель функции. Это улучшает сходимость на практике, особенно для задач с сильно негладкой структурой - дифференцируемые с разрывами производной части. Используются в lagrangian relaxation для целочисленного программирования.
Bundle-методы сходятся со скоростью O(1/k) для выпуклых задач при умеренных параметрах. На практике существенно быстрее субградиентного метода на задачах с большим числом изломов. Современные имплементации (BNDLE Mosek, BMOR) применяют ограниченный размер bundle (k_max ~ 30-50) для контроля памяти.
Bundle Trust-Region (Hiriart-Urruty 1993) - вариант с trust-region вместо квадратичной регуляризации. Адаптивно меняет t_k на основе качества модели: при хорошем прогрессе t_k растёт (доверие к модели больше), при плохом - уменьшается. Эмпирически лучше для негладких задач с большой кривизной.
Bundle compression: при достижении максимального размера bundle применяют aggregation - заменяют несколько субградиентов одним выпуклым комбинацией с потерей информации, но компактным представлением. Эффективные правила компрессии - открытая исследовательская тема.
Зачем bundle-методы хранят несколько субградиентов вместо одного?
Ключевые идеи
- Субдифференциал df(x) - выпуклое множество субградиентов; условие 0 in df(x*) обобщает grad f(x*) = 0
- Проксимальный оператор prox_{lambda g}(v) обобщает проекцию; для L1 - soft-thresholding S_lambda(v)
- ISTA: шаг = nabla f + prox g, скорость O(1/k); FISTA с инерцией Нестерова даёт O(1/k^2)
- Primal-dual splitting (Chambolle-Pock) решает min f(x)+g(Kx) за O(1/k^2) двумя проксимальными шагами
- Многие prox имеют замкнутые формулы: nuclear norm, group LASSO, simplex projection, group norm
Связи с другими областями
Негладкая оптимизация пронизывает обработку сигналов, машинное обучение и теорию управления.
- Проксимальные методы — Прокс-операторы - стандартный инструмент негладкой оптимизации
- Proximal методы: операторы для non-smooth optimization — Базовая глава о proximal mapping и FISTA/ADMM
- Стохастическая оптимизация и адаптивные методы — Прокс-SGD комбинирует адаптивные шаги с негладкими регуляризаторами
Вопросы для размышления
- Почему FISTA с инерцией Нестерова даёт O(1/k^2), хотя каждая итерация стоит столько же, сколько в ISTA?
- Как prox_{lambda g}(v) вырождается в проекцию на выпуклое множество C при g = indicator_C?
- Почему soft-thresholding является именно проксимальным оператором выпуклой L1-нормы, а не жёсткого порога (hard-thresholding)?