Статьи сотрудников лаборатории прошли на конференцию NeurIPS 2024
У сотрудников лаборатории прошло несколько статей на конференцию NeurIPS 2024:
1) Artem Agafonov, Petr Ostroukhov, Roman Mozhaev, Konstantin Yakovlev, Eduard Gorbunov, Martin Takác, Alexander Gasnikov, Dmitry Kamzolov. Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations.
«Вариационные неравенства представляют собой широкий класс задач, включая задачи минимизации и минимаксные задачи, которые часто встречаются в машинном обучении. Существующие методы второго и более высоких порядков для вариационных неравенств требуют точного вычисления производных, что зачастую приводит к чрезмерно высоким затратам на итерации. В этой работе мы изучаем влияние неточности Якобиана на методы второго порядка. Для случая гладкого и монотонного случая мы устанавливаем нижнюю границу с явной зависимостью от уровня неточности Якобиана и предлагаем оптимальный алгоритм для данного ключевого случая. Если производные вычисляются точно, наш метод сходится с той же скоростью, что и оптимальные точные методы второго порядка. Чтобы снизить затраты на решение вспомогательной задачи, которая возникает во всех методах высокого порядка с глобальной сходимостью, мы вводим несколько аппроксимаций Квази-Ньютона. Наш метод с обновлениями Квази-Ньютона достигает глобальной сублинейной скорости сходимости. Мы также обобщаем наш подход на случай неточных производных высокого порядка и подтверждаем теоретические результаты экспериментами», — рассказал Артем Агафонов.
Исследователь добавил, что теоретический результат о сходимости метода удалось окончательно доказать в самолете в Вену, на конференцию ICLR 24.
«Приятно, когда в статье получилось предложить новую нижнюю оценку, потому что их не так много (всего одна для каждого класса задач). Они дают понимание, что решить конкретную задачу быстрее никак нельзя. Вдвойне приятно, что нам также удалось предложить оптимальный метод. Таким образом, статья представляет собой по сути законченную историю о том как работать с вариационными неравенствами в случае неточности во второй производной. Работать над статьей было очень комфортно. Основной костяк команды, который работал над теоретической, частью, состоял из моих друзей — Димы Камзолова и Пети Остроухова. Мы были очень заряжены и мотивировали друг друга», — отметил Агафонов.
2) Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov, Igor Sokolov, Ahmed Khaled, Konstantin Burlachenko, Peter Richtárik. Federated Optimization Algorithms with Random Reshuffling and Gradient Compression.
3) Aleksandr Lobanov, Alexander Gasnikov, Andrey Krasnov. Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values.
«Проект возник в связи челленджем, с которым столкнулась команда студента МФТИ Андрея Краснова при разработке стартапа “Умная кофемашина”. При создании кофемашины, способной находить пропорции ингредиентов для достижения идеального вкуса, возникли сложности, связанные с ограниченным доступом к информации о значениях целевой функции. После обращения с просьбой решения этого челленджа к Александру Гасникову и к Александру Лобанову, началась работа над проектом — разработка новых алгоритмов, основанных на концепции оракула, которые могут эффективно решать задачи оптимизации, используя только сравнительные оценки (Order Oracle). В процессе работы над проектом было открыто исследовательское направление, касающееся существования ускорения в данной концепции, которое ранее оставалось открытым», — пояснил Александр Лобанов.
Он отметил, что проект представляет собой важный шаг в области оптимизации, с высоким потенциалом для практического применения и коммерческого успеха, что делает его привлекательным для инвестиций и дальнейшего развития.
4) Nikita Maksimovich Kornilov, Petr Mokrov, Alexander Gasnikov, Alexander Korotin. Optimal Flow Matching: Learning Straight Trajectories in Just One Step.
«В этой работе мы изучали, как связаны два популярных фреймворка в мире генеративного моделирования:Flow Matching и Optimal Transport. Flow Matching позволяет переводить одно распределение в другое путём обучения векторного поля, задающего нужное дифференциальное уравнение. С его помощью можно, например, генерировать картинки из шума. В Optimal Transport также учатся переводить распределения друг в друга через инференс нейронной сети, но дополнительно пытаются сохранить близость входа и выхода. OT используется, например, чтобы делать upscaling разрешения картинок. Хотя эти фреймворки и выполняют похожие задачи, но под капотом у них заложены сильно различающиеся подходы к решению. В нашей статье, мы доказали в теории и показали на практике, что можно модифицировать FM, не изменив его сути, так, чтобы он стал решать OT. Это позволяет нам объединить самые лучшие стороны обоих методов», — поделился Никита Корнилов.
Он добавил, что в экспериментах демонстрируются SOTA результаты на OT бенчмарках и исправляются недостатки FM (в частности, кривизну траекторий, зависимость от начальных параметров и медленный сэмплинг). По его словам, в этой работе самым неожиданным образом удалось применить выпуклый анализ, чтобы получить нетривиальные теоремы.
5) Ilya Kuruzov, Gesualdo Scutari, Alexander Gasnikov. Achieving Linear Convergence with Parameter-Free Algorithms in Decentralized Optimization.
«Данная работа предлагает первый, насколько нам известно, алгоритм распределенной децентрализованной оптимизации, не требующий настройки каких-либо параметров и при этом имеющий теоретическими гарантии сходимости в (сильно-)выпуклом случае. Предложенный метод основан на идеях прямо-двойственных методов и локальном линейном поиске в узлах. Кроме этого данный метод превосходит в производительности многие известные методы неадаптивные методы децентрализованной оптимизации», — пояснил Илья Курузов.
Он добавил, что построение адаптивных методов оптимизации является крайне важной задачей, поскольку такие алгоритмы не требуют предварительной настройки, что делает их более легко применимыми на практике.
6) Dmitry Kovalev, Ekaterina Borodich, Alexander Gasnikov, Dmitrii Feoktistov. Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks.
Конференция NeurIPS проводится с целью содействия обмену достижениями в области искусственного интеллекта и машинного обучения. На ней зачитываются доклады, проводятся устные и стендовые презентации. Наряду с конференцией проводятся тематические семинары.