- Децентрализованный метод условного градиента на изменяющихся во времени графах (arXiv)
Автор : Роман Ведерников, Александр Рогозин, Александр Гасников.
Аннотация: В этой статье мы изучаем обобщение метода распределенного условного градиента на изменяющиеся во времени сетевые архитектуры. Мы теоретически анализируем свойства сходимости алгоритма и проводим численные эксперименты. Изменяющаяся во времени сеть моделируется как детерминированная стохастическая последовательность графов.
2. Неточный метод условного градиента для двухуровневой оптимизации с ограничениями (arXiv).
Автор: Назанин Абольфазли, Руйчен Цзян, Ариан Мохтари, Эрфан Яздандуст Хамедани.
Аннотация: Двухуровневая оптимизация — это важный класс задач оптимизации, в которых одна задача оптимизации вложена в другую. Эта структура широко используется в задачах машинного обучения, включая метаобучение, гиперочистку данных и завершение матрицы с шумоподавлением. В этой статье мы фокусируемся на двухуровневой задаче оптимизации с сильно выпуклой задачей нижнего уровня и гладкой целевой функцией верхнего уровня над компактным и выпуклым множеством ограничений. Было разработано несколько методов для решения задач безусловной двухуровневой оптимизации, но работы по методам для условий с ограничениями ограничены. Фактически, для тех методов, которые могут решать задачи с ограничениями, либо скорость сходимости низкая, либо вычислительные затраты на итерацию высоки. Чтобы решить эту проблему, в этой статье мы представляем новый однопетлевой метод без проекций, использующий технику вложенной аппроксимации. Предлагаемый нами метод имеет улучшенную сложность на итерацию, превосходящую существующие методы, и обеспечивает оптимальную скорость сходимости, гарантирующую соответствие самой известной сложности безпроекционных алгоритмов для решения задач одноуровневой оптимизации с выпуклыми ограничениями. В частности, когда целевая функция верхнего уровня выпукла, наш метод требует O ~ (ε−1) итераций для поиска ε-оптимального решения. Более того, когда целевая функция верхнего уровня невыпуклая, сложность нашего метода составляет O(ε−2) для нахождения ε-стационарной точки. Мы также представляем численные эксперименты, чтобы продемонстрировать превосходную эффективность нашего метода по сравнению с современными методами.
