- Неточный онлайн-проксимальный зеркальный спуск для изменяющейся во времени композитной оптимизации (arXiv)
Автор: Woocheol Choi, Myeong-Su Lee, Seok-Bae Yun.
Аннотация: В этой статье мы рассматриваем онлайн-проксимальный зеркальный спуск для решения сложных задач оптимизации во времени. Для различных приложений алгоритм естественным образом содержит ошибки в градиентном и проксимальном операторе. Получены точные оценки динамического сожаления алгоритма, когда регулярная часть стоимости выпуклая и гладкая. Если расстояние Брегмана задается евклидовым расстоянием, наш результат также улучшает предыдущую работу двумя способами: (i) мы устанавливаем более точную границу сожаления по сравнению с предыдущей работой в том смысле, что наша оценка не включает член O(T) появляется в этой работе. (ii) Мы также получаем результат, когда областью является все пространство Rn, тогда как предыдущая работа была получена только для ограниченных областей. Мы также предоставляем численные тесты для задач, связанных с ошибками в градиенте и проксимальном операторе.
2. Границы скорости сходимости для метода зеркального спуска: IQC, критерий Попова и дивергенция Брегмана (arXiv)
Автор: Мэнмоу Ли, Халед Лаиб, Такеши Хатанака, Иоаннис Лестас.
Аннотация: в его статье представлен всесторонний анализ сходимости для метода зеркального спуска (МД), широко используемого алгоритма в выпуклой оптимизации. Ключевой особенностью этого алгоритма является то, что он обеспечивает обобщение классических методов на основе градиента за счет использования обобщенных дистанционно-подобных функций, которые формулируются с использованием дивергенции Брегмана. Установление границ скорости сходимости для этого алгоритма, как правило, является нетривиальной задачей из-за отсутствия свойств монотонности в задействованных составных нелинейностях. В этой статье мы показываем, что отклонение Брегмана от оптимального решения, которое обычно используется в качестве функции Ляпунова для этого алгоритма, является частным случаем функций Ляпунова, которые следуют, когда критерий Попова применяется к соответствующей переформулировке задачи. Затем это используется в качестве основы для построения структуры интегральных квадратичных ограничений (IQC), с помощью которой можно вывести границы скорости сходимости с уменьшенным консерватизмом. Мы также проиллюстрируем на примерах, что полученные границы скорости сходимости могут быть жесткими.
