- Алгоритм стохастического проксимального разделения для композитной минимизации (arXiv)
Автор : Андрей Патраску, Пол Ирофти
Аннотация: Поддержанные недавними вкладами в несколько ветвей, алгоритмы расщепления первого порядка стали центральными для структурированной негладкой оптимизации. В крупномасштабных или зашумленных контекстах, когда доступна только стохастическая информация о гладкой части целевой функции, распространение проксимальных градиентных схем на стохастические оракулы основано на проксимальной управляемости негладкой компоненты, и это было глубоко проанализировано в литература. Однако остались пробелы, показанные составными моделями, где негладкий член больше не поддается проксимальному рассмотрению. В этой заметке мы рассматриваем сложные задачи оптимизации, где предполагается доступ только к стохастической информации как о гладких, так и о негладких компонентах, используя стохастическую проксимальную схему первого порядка со стохастическими проксимальными обновлениями. Мы предоставляем O (1k) сложность итерации (в расчете на квадрат расстояния до оптимального набора) при сильном предположении о выпуклости целевой функции. Эмпирическое поведение иллюстрируется численными тестами моделей параметрического разреженного представления.
2. Переменный метрический алгоритм прямого-обратного направления для составных задач минимизации (arXiv)
Автор : Одри Репетти, Ив Вио.
Аннотация: Мы представляем основанный на прямом и обратном алгоритме минимизацию суммы дифференцируемой функции и негладкой функции, которые могут быть невыпуклыми. Основной вклад этой работы заключается в рассмотрении сложного случая, когда негладкая функция соответствует сумме невыпуклых функций, полученной в результате композиции строго возрастающей, вогнутой, дифференцируемой функции и выпуклой негладкой функции. Предлагаемый алгоритм составной функции с переменной метрикой вперед-назад (C2FB) обходит явное и часто сложное вычисление оператора близости составных функций с помощью подхода «мажорация-минимизация». Именно, каждая составная функция мажорируется с помощью линейной аппроксимации дифференцируемой функции, что позволяет применять шаг близости только к сумме негладких функций. Мы доказываем сходимость итераций алгоритма к критической точке целевой функции, используя неравенство Курдыки-Лоясевича. Сходимость гарантируется даже при неточном вычислении операторов близости с учетом относительных погрешностей. Мы показываем, что предлагаемый подход является обобщением методов повторного взвешивания с гарантиями сходимости. В частности, применительно к функции логарифмической суммы наш алгоритм сводится к обобщенной версии знаменитого перевзвешенного метода ℓ1. Наконец, с помощью моделирования задачи обработки изображений мы показываем, что предложенный алгоритм C2FB требует меньшего количества итераций для сходимости и приводит к лучшим критическим точкам по сравнению с традиционными методами повторного взвешивания и классическими алгоритмами прямого и обратного анализа.
