Методы проксимального градиента и алгоритм FISTA в разреженной оптимизации
В современную эру машинного обучения, сжатия данных и обработки сигналов (Compressed Sensing) регулярно возникают задачи оптимизации огромной размерности, в которых целевая функция является суммой гладкой и негладкой составляющих. Классическим примером является задача регуляризованной регрессии LASSO, где гладкая квадратичная ошибка штрафуется негладкой L1-нормой для обеспечения разреженности решения. Для эффективного решения таких задач традиционные градиентные методы неприменимы, а субградиентные методы сходятся недопустимо медленно. Решением стал математический аппарат проксимальных операторов и методы проксимального градиента.
Математический фундамент метода закладывает понятие проксимального оператора (Proximal Mapping). Для выпуклой функции $h(x)$ и параметра шага $\lambda > 0$, проксимальный оператор определяется как точка $y$, которая минимизирует сумму функции $h(y)$ и квадратичного штрафа за отклонение от начальной точки $x$: $\text{prox}_{\lambda h}(x) = \arg\min_y \left( h(y) + \frac{1}{2\lambda}||y - x||_2^2 \right)$. Гениальность подхода заключается в том, что для многих практически важных негладких функций (например, L1-нормы) этот оператор имеет простое замкнутое аналитическое решение. Для L1-регуляризации это оператор мягкого порогового отсечения (Soft-Thresholding), который буквально "обнуляет" малые значения весов, создавая ту самую математическую разреженность (sparsity), которую ищут дата-саентисты.
Алгоритм итеративного сжатия-порога (Iterative Shrinkage-Thresholding Algorithm, ISTA) является базовым проксимальным градиентным методом. На каждой итерации алгоритм делает шаг классического градиентного спуска только по гладкой части функции, а затем к полученной промежуточной точке применяется проксимальный оператор негладкой части. Математически доказано, что ISTA сходится к глобальному оптимуму со скоростью $O(1/k)$, где $k$ — номер итерации, что делает его эквивалентом обычного градиентного спуска для гладких функций, но с возможностью "бесплатно" обрабатывать изломы и недифференцируемости.
Подлинный прорыв произошел в 2009 году с разработкой алгоритма FISTA (Fast Iterative Shrinkage-Thresholding Algorithm) математиками Беком и Тебуллем. Опираясь на идеи ускорения Нестерова, FISTA вводит импульс (Momentum) в вычисления. Проксимальный шаг применяется не к точке, полученной на предыдущей итерации, а к хитро вычисленной экстраполяции двух последних точек. Использование импульса Нестерова улучшило теоретическую оценку скорости сходимости с $O(1/k)$ до $O(1/k^2)$ при пренебрежимо малом усложнении вычислительной логики. Это означает, что для достижения заданной точности FISTA требует на порядки меньше итераций, чем базовый ISTA.
Сегодня FISTA и его варианты (такие как ADMM, который концептуально близок) являются основой для алгоритмов обработки магнитно-резонансных томограмм, реконструкции изображений в астрофизике и обучения разреженных глубоких нейронных сетей. Понимание свойств проксимальных операторов и принципов экстраполяции Нестерова дает разработчикам алгоритмов ключ к созданию сверхбыстрых математических моделей, способных отфильтровывать истинные знания от колоссальных массивов цифрового шума.
Список литературы:
1. Beck A., Teboulle M. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. — SIAM Journal on Imaging Sciences, 2009.
2. Parikh N., Boyd S. Proximal Algorithms. — Foundations and Trends in Optimization, 2014.
3. Нестеров Ю.Е. Введение в выпуклую оптимизацию. — М.: МЦНМО, 2010.
Related items
- Ричард Эрнест Беллман
- Теория двойственности Фенхеля и основы выпуклого анализа
- Теория массового обслуживания как задача оптимизации процессов
- Квадратичное программирование: методы решения и применение в машинном обучении
- Алгоритмы динамического программирования на графах с ограниченной древесной шириной