МФТИ | Оптимизация

Проектная смена
"Современные методы теории информации,
оптимизации и управления"

Проходила в Адлер Арене Сируиса с 2 по 23 августа 2020 г.
Проф. А.В. Гасниковым были прочитаны три лекции. Первые две лекции базировались на статье "Ускоренный метаалгоритм для задач выпуклой оптимизации" (ЖВМ и МФ. Т. 61. № 2), заключительная лекция базировалась на обзоре "Recent Theoretical Advances in Non-Convex Optimization":

Лекция 1: Ускоренный метаалгоритм – 1
Видео    Презентация 1
Лекция 2: Ускоренный метаалгоритм – 2 / Введение в численные методы невыпуклой оптимизации – 1
Видео    Презентация 1    Презентация 2
Лекция 3: Введение в численные методы невыпуклой оптимизации – 2
Видео    Презентация 2

Также А.В. Гасниковым совместно с учениками
и при поддержке со стороны Сириуса (в лице А.С. Ненашева)
были предложены следующие проекты.

Ниже приводится краткое описание только части проектов, по которым в результате появились публикации. Также указывается участник(-и) смены, которые выполнил(-и) проект. Изначальные постановки части проектов можно посмотреть по ссылке. Собственно, именно в таком виде участникам проектной смены предлагались проекты. Далее участники выбирали один (иногда несколько) проектов и связывались с кураторами (руководителями) проектов. В течение смены проходила работа по погружению в проект. После окончания смены эта работа в подавляющем большинстве случаев была продолжена, что привело в итоге к подготовке статей. Именно по таким проектам и приводится информация:

Проект по написанию обзора по Децентрализованной распределенной оптимизации

arXiv препринт

Алгоритм с наилучшими оценками сложности для поиска барицентра Вассерштейна

Проект предложен Д.М. Двинских. Выполнил проект студент ФКН ВШЭ Даниил Тяпкин.
Рассказ о проекте на сайте Сируиса.
Статья на AISTATS 2021, подготовленная по итогам проекта.
Видео доклада с выступлением по теме проекта.
Проект получил развитие в виде статьи, в которой алгоритм Двинских-Тяпкина был распространён на распределённые децентрализованные постановки задачи.

Распараллеливание поиска оптимальной стратегии в Reinforcement Learning путем сведение к задаче линейного программирования и использования прямо-двойственного рандомизированного зеркального спуска с переключением

Выполнил проект студент ФКН ВШЭ Даниил Тяпкин.
arXiv препринт

Численные методы поиска равновесий в двухстадийной модели транспортных потоков

Проект выполнила аспирантка школы ПМИ МФТИ Екатерина Котлярова.
arXiv препринт

Метод трех квадратов (адаптивный вариант метода Гаусса-Ньютона-Нестерова). Стохастический вариант метода трех квадратов

Проект был предложен Ю.Е. Нестеровым и Д.И. Камзоловым. Проект выполнил аспирант ФИЦ ИУ ВЦ РАН (на момент проектной смены студент магистратуры ВМК МГУ имени М. В. Ломоносова) Никита Юдин.
Английская версия (заметно отличается от русской)
Русская версия

Ускоренные методы децентрализованной распределенной оптимизации на меняющихся со временем графах (отвечает Wireless коммуникации)

Проект был предложен А.В. Рогозиным и был выполнен при участии студента магистратуры СколТеха Владислава Лукошкина.
arXiv препринт
Проект имел продолжение в виде статьи 1 и статьи 2.

Ускоренные методы для седловых задач композитной структуры

Проект был выполнен студентами бакалавриата школы ПМИ МФТИ Владиславом и Ярославом Томиниными под руководством д.ф.-м.н. П.Е. Двуреченского.
arXiv препринт

Методы решения седловых задач в случае малой размерности одной из групп переменных

Проект был выполнен студентом совместной магистратуры школы ПМИ МФТИ и СколТеха Егором Гладиным.
arXiv препринт
Проект имел продолжение в виде цикла из статьи 1 и статьи 2.

Стохастический вариант метода эллипсоидов

Проект был выполнен студентом совместной магистратуры школы ПМИ МФТИ и СколТеха Егором Гладиным и студенткой магистратуры школы РКТ МФТИ Кариной Зайнуллиной.
arXiv препринт.

Ускоренный метод альтернативных направлений и его приложения к тензорным разложениям

Проект был предложен совместно с акад. Е.Е. Тыртышниковым и проф. И.В. Оселедцем. Проект выполнили к.ф.-м.н. (на момент проектной смены аспирант МФТИ) Назарий Тупица и Даниил Меркулов.
Статья в журнале Труды МФТИ.

Ускоренные методы для седловых задач со структурой суммы и композитными членами

Проект был предложен совместно с д.ф.-м.н. П.Е. Двуреченским и выполнен бакалаврами школы ПМИ МФТИ Владиславом и Ярославом Томиниными.
arXiv препринт.

Тензорные методы для седловых задач

Проект был выполнен аспирантом школы ПМИ МФТИ Петром Остроуховым.
arXiv препринт.

Non-convex optimization in digital pre-distortion of the signal

Проект был выполнен совместно с Д. Пасечнюком, А. Масловским и А. Рогозиным.
arXiv препринт.

Ускоренный покомпонентный метод минимизации функций типа soft-max, учитывающий разреженность задачи

Проект выполнили Д.А. Пасечнюк и аспирант МФТИ Владислав Матюхин.
arXiv препринт (русская версия)
arXiv препринт (английская версия).

Проекты, предложенные к.ф.-м.н. (на момент проектной смены – аспирант школы ПМИ МФТИ) Д.И. Камзоловым:

Гипербыстрый тензорный метод для распределенного централизованного решения задач обучения логистической регрессии (при участии коллег из Yahoo!)

Проект был выполнен при участии студента магистратуры СколТеха Александра Лукашевича.
arXiv препринт
Проект имел продолжение в виде статьи.

Стохастические тензорные методы

Проект был выполнен студентом магистратуры школы ПМИ Артемом Агафоновым.
arXiv препринт
Проект имел продолжение в виде статьи.

Проекты, предложенные А.Н. Безносиковым:

Локальный стохастический градиентный спуск для решения седловых задач. Приложения к GANам

arXiv препринт
Впоследствие, проект получил развитие на случай более общих архитектур взаимодействия (децентрализованных) в статье.

Безградиентные методы для решения задач невыпуклой оптимизации, близких к выпуклым задачам

arXiv препринт

Безградиентные методы для решения гладких седловых задач с неточным стохастическим оракулом

Проект был сделан при активном участии студента магистратуры школы ПМИ МФТИ Абдурахмона Садиева.
arXiv препринт
Проект имел продолжении в виде цикла из статьи 1, статьи 2 и статьи 3.

Э.А. Горбунов вёл работу над следующими статьями:

Стохастический градиентный спуск с локальными шагами: общая теория и новые эффективные методы / Local SGD: Unified Theory and New Efficient Methods

arXiv препринт
Статья принята на AISTATS 2021.

Следующие работы Э.А. Горбунова были поддержаны грантом РФФИ “Научное наставничество” (№ 19-31-51001):

Линейно сходящийся распределённый вариант стохастического градиентного спуска с компенсацией ошибки / Linearly Converging Error Compensated SGD

Абстракт
Опубликована на конференции NeurIPS 2020
Видео.

Эффективное децентрализованное обучение на гетерогенных ненадёжных устройствах / Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices

arXiv препринт

МАРИНА: быстрый алгоритм решения невыпуклых задач распределённой оптимизации с компрессией / MARINA: Faster Non-Convex Distributed Learning with Compression

arXiv препринт
Видео.

Распределённые и параллельные алгоритмы решения задач анализа данных

Проектная смена
"Современные методы теории информации,
оптимизации и управления"

Проект по написанию обзора по Децентрализованной распределенной оптимизации

Алгоритм с наилучшими оценками сложности для поиска барицентра Вассерштейна

Численные методы поиска равновесий в двухстадийной модели транспортных потоков

Метод трех квадратов (адаптивный вариант метода Гаусса-Ньютона-Нестерова). Стохастический вариант метода трех квадратов

Ускоренные методы децентрализованной распределенной оптимизации на меняющихся со временем графах (отвечает Wireless коммуникации)

Ускоренные методы для седловых задач композитной структуры

Методы решения седловых задач в случае малой размерности одной из групп переменных

Стохастический вариант метода эллипсоидов

Ускоренный метод альтернативных направлений и его приложения к тензорным разложениям

Ускоренные методы для седловых задач со структурой суммы и композитными членами

Тензорные методы для седловых задач

Non-convex optimization in digital pre-distortion of the signal

Ускоренный покомпонентный метод минимизации функций типа soft-max, учитывающий разреженность задачи

Гипербыстрый тензорный метод для распределенного централизованного решения задач обучения логистической регрессии (при участии коллег из Yahoo!)

Стохастические тензорные методы

Локальный стохастический градиентный спуск для решения седловых задач. Приложения к GANам

Безградиентные методы для решения задач невыпуклой оптимизации, близких к выпуклым задачам

Безградиентные методы для решения гладких седловых задач с неточным стохастическим оракулом

Стохастический градиентный спуск с локальными шагами: общая теория и новые эффективные методы / Local SGD: Unified Theory and New Efficient Methods

Линейно сходящийся распределённый вариант стохастического градиентного спуска с компенсацией ошибки / Linearly Converging Error Compensated SGD

Эффективное децентрализованное обучение на гетерогенных ненадёжных устройствах / Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices

МАРИНА: быстрый алгоритм решения невыпуклых задач распределённой оптимизации с компрессией / MARINA: Faster Non-Convex Distributed Learning with Compression

Фотоальбом

Распределённые и параллельные алгоритмы решения задач анализа данных

Проектная смена"Современные методы теории информации,оптимизации и управления"

Проект по написанию обзора по Децентрализованной распределенной оптимизации

Алгоритм с наилучшими оценками сложности для поиска барицентра Вассерштейна

Численные методы поиска равновесий в двухстадийной модели транспортных потоков

Метод трех квадратов (адаптивный вариант метода Гаусса-Ньютона-Нестерова). Стохастический вариант метода трех квадратов

Ускоренные методы децентрализованной распределенной оптимизации на меняющихся со временем графах (отвечает Wireless коммуникации)

Ускоренные методы для седловых задач композитной структуры

Методы решения седловых задач в случае малой размерности одной из групп переменных

Стохастический вариант метода эллипсоидов

Ускоренный метод альтернативных направлений и его приложения к тензорным разложениям

Ускоренные методы для седловых задач со структурой суммы и композитными членами

Тензорные методы для седловых задач

Non-convex optimization in digital pre-distortion of the signal

Ускоренный покомпонентный метод минимизации функций типа soft-max, учитывающий разреженность задачи

Гипербыстрый тензорный метод для распределенного централизованного решения задач обучения логистической регрессии (при участии коллег из Yahoo!)

Стохастические тензорные методы

Локальный стохастический градиентный спуск для решения седловых задач. Приложения к GANам

Безградиентные методы для решения задач невыпуклой оптимизации, близких к выпуклым задачам

Безградиентные методы для решения гладких седловых задач с неточным стохастическим оракулом

Стохастический градиентный спуск с локальными шагами: общая теория и новые эффективные методы / Local SGD: Unified Theory and New Efficient Methods

Линейно сходящийся распределённый вариант стохастического градиентного спуска с компенсацией ошибки / Linearly Converging Error Compensated SGD

Эффективное децентрализованное обучение на гетерогенных ненадёжных устройствах / Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices

МАРИНА: быстрый алгоритм решения невыпуклых задач распределённой оптимизации с компрессией / MARINA: Faster Non-Convex Distributed Learning with Compression

Фотоальбом

Проектная смена
"Современные методы теории информации,
оптимизации и управления"