Направления исследований
Основные направления текущих исследований научного коллектива:
Распределенная оптимизация
Recent theoretical advances in decentralized distributed convex optimization
Decentralized optimization over time-varying graphs
В частности, в условиях симиларити и с редукцией дисперсии: Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity
Optimal Algorithms for Decentralized Stochastic Variational Inequalities
Ниже описаны проекты, которыми можно заниматься по данному направлению (проектов намного больше, здесь приведено лишь несколько примеров):
Оптимальные оценки для Вариационных Неравенств (ВН) в архитектуре Federated Learning (FL)
В качестве задачи, прежде всего, рекомендуется разобраться вот с этой статьей: The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication. Особенно, в части получения формул (12) и (13). По сути то, о чем тут идет речь, есть ускоренный метод с батчами, просто с разным размером батча (1 и максимально возможным, при котором от батчирования есть эффект).
Собственно, задачей является перенесение результатов статьи The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication в части оптимальных методов на седловые задачи и ВН на базе метода из работы Solving variational inequalities with stochastic mirror-prox algorithm и его пробатченного варианта.
Более тонкой задачей является получение нижней оценки в архитектуре FL для ВН наподобие того, как это было сделано в статье The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication. В других архитектурах это сделано, например, в работе Distributed saddle-point problems: lower bounds, near-optimal and robust algorithms.
В случае седловых билинейных задач (с квадратичными композитами) и даже более общего класса ВН с линейным векторным полем, кажется, что в случае стох. постановок может иметь место результаты типа Is Local SGD Better than Minibatch SGD? (Section 3). Было бы здорово это проверить.
Оптимальные оценки для задач выпуклой оптимизации в условиях интерполяции в архитектуре FL
В 2021 году вышла статья, в которой впервые показывается, как ускоренные методы уживаются с условиями интерполяции в плане батчирования: An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
Однако, этого пока не было сделано в FL архитектуре. Зато было сделано (оптимальные методы для задач гладкой выпуклой оптимизации в архитектуре FL) без условий интерполяции: The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication. То есть задача — поженить эти две работы.
Релевантная статья по теме: Faster Convergence of Local SGD for Over-Parameterized Models
Редукция дисперсии, проксимальные оболочки, симиларити в неевклидовом прокс сетапе с приложением к задаче поиска барицентра Васерштейна.
В работе Дмитрия Ковалева Optimal Algorithms for Decentralized Stochastic Variational Inequalities от 2022 года был предложен оптимальный децентрализованный алгоритм решения безусловных седловых задач (сильно выпукло-вогнутых) с редукцией дисперсии. Как известно, задача поиска барицентра Васерштейна (см. Decentralized Distributed Optimization for Saddle Point Problems, а также Numerical Methods for Large-Scale Optimal Transport) может быть сведена как раз к седловой задаче, причем решать такую задачу удобно распределено (в том числе и децентрализованно), в виду больших вычислительных затрат. Причем, на одном узле, естественно, хранить несколько картинок (слагаемых исходной большой суммы).
Таким образом приходим к седловой выпукло-вогнутой задаче децентрализованной оптимизации вида суммы, в которой в каждом узле хранится функция, в свою очередь, имеющая вид суммы функций. Децентрализованные алгоритмы решения таких задач, учитывающие, структуру вида суммы функции, хранящейся в каждом узле, при условии, что есть возможность обращаться к каждому из слагаемых этой суммы отдельно (например, есть возможность вычислять градиент каждого слагаемого), называются децентрализованными методами с редукцией дисперсии. Результаты статьи Ковалева и других не подходят для задачи вычисления барицентра Васерштейна (ВБВ) сразу по нескольким причинам:
1) у задачи ВБВ в седловом представлении нет сильной выпукло-вогнутости (есть просто выпукло-вогнутость, но не сильная);
2) у задачи ВБВ в седловом представлении есть ограничения;
3) схема статьи Ковалева и др. предполагает, что по max и по min переменным выбирается евклидова норма в оптимальном методе. В задаче ВБВ (как следует из работы Рогозина и других) по группе min переменных выгодно выбирать 1-норму (поскольку есть симплексные ограничения на min переменные).
Планируется развить результаты статьи Ковалева и других на более общий класс задач выпукло-вогнутой оптимизации с ограничениями и не обязательно евклидовыми прокс-структурами, чтобы можно было применить эти результаты к задаче ВБВ в седловом представлении.
Отметим, что редукция дисперсии в неевклидовом прокс-сетапе (но нераспределенном) ранее прорабатывалась в работе Stochastic Variance Reduction for Variational Inequality Methods для седловых задач и ВН, а в материале A unified variance-reduced accelerated gradient method for convex optimization для обычной оптимизации.
В работе Александра Безносикова Distributed Saddle-Point Problems Under Data Similarity (см. также Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity — вариант без лишнего лоагрифма, правда, в централизованном случае) был предложен эффективный распределенный (в том числе и децентрализованный) способ решения безусловных сильно выпукло-вогнутых седловых задач вида суммы, в которых слагаемые являются близкими функциями. Как уже отмечалось выше, в задаче ВБВ в седловом представлении слагаемые имеют вид суммы функций. Если задача ВБВ пришла из анализа данных и каждая картинка/мера (барицентр которых ищется) независимо сэмплирована из одного и того же распределения, то в каждом узле хранится сумма статистически независимых функций, сэмплированных из одного и того же распределения. Это означает, что функции, хранящиеся в узлах, статистически близки (степень близости обратно пропорционально корню из числа слагаемых, хранящихся в узле).
Таким образом, можно по-другому обыграть структуру задачи и вместо редукции дисперсии (которая максимально экономит оракульные вызовы в узлах, то есть число вычислений градиентов слагаемых в каждом узле, но не экономит число коммуникаций между узлами) использовать схожесть функций, хранящихся в узлах, и существенно сэкономить в числе коммуникаций. К сожалению, прямое приложение результатов статьи Безносикова и др. к задаче вычисления ВБВ в седловом представлении не работает ровно по тем же трем причинам, что и были указаны выше. Планируется развить результаты статьи Безносикова и др. на более общий класс задач выпукло-вогнутой оптимизации с ограничениями и не обязательно евклидовыми прокс-структурами, чтобы можно было применить эти результаты к задаче ВБВ в седловом представлении.
В обоих сюжетах наиболее сложным местом представляется обобщение на неевклидовы прокс-структуры и наличие ограничений. Это все потребуется существенно новых идей и отличной техники. Дело в том, что в статьях Ковалева и др. и Безносикова и др. существенным образом использовалась евклидовость нормы. Рассуждения этих статей уже не пройдут для случая общей нормы.
Тензорные методы их приложения
Exploiting higher-order derivatives in convex optimization methods
В данном направлении планируется развивать идею, что задачи квадратичной стохастической оптимизации в архитектуре федеративного обучения очень эффективно могут быть решены в смысле необходимого числа коммуникаций. А для тензорных методов вспомогательная задача, которую нужно решать на каждой итерации, похожа на задачу, которую нужно решать на итерации метода Ньютона, стало быть, является квадратичной. Таким образом, есть надежда сократить число коммуникаций при решении задач стохастической распределенной оптимизации тензорными методами.
Отметим, что в 2022 году в этой области сотрудниками лаборатории были получены оптимальные тензорные методы (без лишних логарифмов в оценках сложности): The first optimal acceleration of high-order methods in smooth convex optimization. Однако открытым остается много вопросов, связанных с таким подходом. Прямо-двойственный ли такой метод? Можно ли на его основе построить пробатченный стохастический вариант и т.п.
Безградиентные методы оптимизации
An accelerated method for derivative-free smooth stochastic convex optimization
One-Point Gradient-Free Methods for Smooth and Non-Smooth Saddle-Point Problems
The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problems
Gradient-Free Optimization for Non-Smooth Saddle Point Problems under Adversarial Noise
Randomized gradient-free methods in convex optimization
Последние исследования в этой области сосредотачиваются не только на получении методов с оптимальными оценками оракульных вызовов, но и методов с оптимальными оценками числа последовательных итераций и методов, наиболее робастных к уровню неслучайного шума (враждебного) в значении функции. Часто это одни и те же методы, оптимальные сразу по всем критериям.
Несмотря на то, что прогресс последнего времени тут довольно большой, по-прежнему остаются вопросы, на которые ответы не известны. Например, для гладких задач неизвестны нижние оценки на максимально допустимый уровень (враждебного) шума, при котором можно решить задачу с заданной точностью. Также неизвестны в общем случае оценки вероятностей больших уклонений для задач стохастической оптимизации с субгауссовским шумом, но не евклидовым прокс-сетапом. А с учетом того, что способы формирования стохастической модели градиента на базе вычисленных значений функции могут быть разными (Безградиентные прокc-методы с неточным оракулом для негладких задач выпуклой стохастической оптимизации на симплексе, A gradient estimator via L1-randomization for online zero-order optimization with two point feedback, Randomized gradient-free methods in convex optimization), дополнительно возникает задача изучения разных рандомизаций с целью выявления наилучшего по перечисленным выше критериям.
Структурная минимизация
Ускоренные методы для седловых задач
On Accelerated Methods for Saddle-Point Problems with Composite Structure
The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization
В обычной минимизации принято описывать целевую функцию (как представителя некоторого большого класса функций) константами, которые характеризуют поведение функции как функции всех своих аргументов. На самом деле, во многих приложениях (особенно при решении седловых задач) естественным образом выделяются разные блоки переменных, по которым свойства целевой функции существенно разные. Например, это проявляется в многостадийных моделях транспортных потоков при поиске равновесий.
Конечно, можно ориентироваться на худшие константы и использовать известные методы, но насколько можно выиграть от использования такой асимметричной (блочной) структуры? Частично ответ на этот вопрос дают покомпонентные методы. Однако в общем случае вопрос по-прежнему открыт. В последнее время довольно много продвижений было в данном направлении по части седловых задач с разными константами сильно выпуклости и сильно вогнутости, а также разных констант Липшица градиента. Однако, для задач со структурой min min результатов уже заметно меньше.
Более того, и для min max и для min min задач по-прежнему открытыми являются вопросы о нижних оценках. В частности, для задач малоразмерной выпуклой оптимизации нижние оценки получаются с помощью сопротивляющегося оракула https://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf (3 Methods with linear convergence, II, но начать лучше прямо с самого первого раздела Lecture 1 — на одномерном случае все понятнее).
В то время как для задач большой размерности — c помощью «худшей в мире функции» — см., например, указания к упражнениям 1.3 и 2.1 пособия МЦНМО, можно найти на ресурсе Методы Оптимизации. МФТИ. В работе «Решение сильно выпукло-вогнутых композитных седловых задач с небольшой размерностью одной из групп переменных» исследуются задачи min max, в которых одна из групп min переменных имеет небольшую размерность, а другая группа, напротив, большую. Получены верхние оценки.
Интересно было бы попробовать получить нижние оценки путем комбинации двух конструкций. Кажется, что в математическом плане пример построения нижней оценки будет содержать новые интересные идеи. В развитие этого проекта интересно было бы подумать и о нижних оценках для min min задач, в которых по одной из групп переменных (негладких) имеется малая размерность. Верхние оценки имеются в работах «О решении выпуклых min-min задач с гладкостью и сильной выпуклостью по одной из групп переменных и малой размерностью другой» и Solving smooth min-min and min-max problems by mixed oracle algorithms .
Отметим также, что как нижние так и верхние оценки получаются на число вызовов градиентного оракула. Но в задачах с разными блоками переменных можно говорить о разных оракулах. Например в седловой задаче можно говорить о градиенте по min-переменным и градиенте по max-переменным. А если в задаче еще есть и недружественные композиты (градиенты которых в виду «недружественности» также придет считать), то возникает много различных оракулов и, как следствие, много критериев. И говорить об оптимальных методах и нижних оценках в случае нескольких критериев нужно аккуратно. Представляется интересным построение соответствующей теории оптимальных методов для задач со структурой.