Выпуклая оптимизация
Проксимальные методы
LASSO регрессия - одна строка кода в sklearn - автоматически обнуляет ненужные признаки среди тысяч. Под капотом работает проксимальный градиент: математика мягкого порога, которую Beck и Teboulle описали в статье 2009 года, собравшей 10 000+ цитат.
- Биоинформатика: LASSO отбирает значимые гены из 20 000 возможных предикторов
- МРТ: compressed sensing - восстановление изображений из неполных измерений
- Обработка сигналов: TV-регуляризация для denoising через FISTA
- Federated Learning: ADMM используется в TensorFlow Federated и PySyft
- Рекомендательные системы: sparse matrix factorization через ADMM
- Финансы: sparse portfolio optimization с L1-ограничениями
Проксимальный оператор: обобщение проекции
LASSO регрессия в sklearn: одна строка кода, 10 тысяч признаков, автоматически sparse решение. `sklearn.linear_model.Lasso(alpha=0.1).fit(X, y)`. Под капотом - proximal gradient метод. Понять как именно - значит понять, как получаются sparse модели в ML.
Проксимальный оператор функции f в точке v - это решение задачи минимизации с квадратичным штрафом за удаление от v. Интуиция: сдвинуться от v в сторону минимума f, не уходя далеко. При f = индикатор множества C: prox = проекция на C. При f = L1-норма: prox = мягкий порог.
Почему мягкий порог prox_{lambda*||.||_1}(v) обнуляет малые компоненты? Как это связано с тем, что LASSO даёт sparse решения?
ISTA и FISTA: O(1/k) против O(1/k^2)
Проксимальный градиентный метод решает задачи min f(x) + g(x), где f - гладкая (например, квадратичная потеря), g - негладкая (например, L1). Итерация: шаг градиентного спуска по f, затем проксимальный шаг по g. ISTA: O(1/k). FISTA с моментом Нестерова: O(1/k^2) - оптимально.
Beck & Teboulle (2009) - статья о FISTA собрала 10 000+ цитат. Ускорение Нестерова с O(1/k) до O(1/k^2) бесплатно: добавляется одна строка кода (momentum update), стоимость итерации та же. FISTA - стандарт для задач вида 'гладкое + негладкое'.
Чем FISTA отличается от ISTA по структуре итерации? Почему ускорение бесплатно по вычислительной стоимости?
ADMM: распределённая оптимизация
ADMM (Alternating Direction Method of Multipliers) - движок распределённого ML. Boyd et al. (2011) - одна из самых цитируемых статей в оптимизации (15 000+ цитат). Google, Facebook, TensorFlow Federated - везде ADMM под капотом. Решает min f(x) + g(z) при Ax + Bz = c, расщепляя задачу на поочерёдные шаги.
TensorFlow Federated и PySyft используют ADMM-подобные схемы для обучения моделей на телефонах без передачи данных на сервер. Каждое устройство = агент. Только усредненные обновления весов уходят на сервер. ADMM обеспечивает сходимость без полной централизации.
ADMM разбивает задачу LASSO на x-шаг и z-шаг. Почему x-шаг - это решение гладкой квадратичной системы, а z-шаг - мягкий порог? Какую часть задачи каждый шаг решает?
Ключевые идеи
- prox_{lambda*f}(v) = argmin{f(x) + 1/(2*lambda)*||x-v||^2}: обобщение проекции на невыпуклые функции
- Мягкий порог = prox_{lambda*||.||_1}: обнуляет малые компоненты -> sparse ML
- ISTA: grad шаг по f + prox шаг по g, O(1/k) сходимость
- FISTA: ISTA + momentum Нестерова, O(1/k^2) - бесплатное ускорение
- ADMM: расщепление min f(x)+g(z) при x=z на чередующиеся шаги; масштабируется на кластер
Связанные темы
Проксимальные методы обобщают градиентный спуск на негладкий случай.
- Субдифференциальное исчисление — Условие оптимальности prox выражается через субдифференциал
- Стохастическая оптимизация — Стохастический ADMM и SGD с проксимальным шагом