Открыта подача заявок на проектную смену SOTA от Яндекс

С 9 по 20 октября 2023 года в Сириусе пройдет проектная смена SOTA от Яндекса. Смена посвящена воспроизведению результатов научных статей, в ней активно будут участвовать сотрудники лаборатории. Подать заявку можно до 30 августа. Подробнее о смене на сайте Сириуса.

В рамках смены будут реализовываться следующие проекты с участием сотрудников лаборатории:

1. Марковские операторы сжатия

Преподаватели:

Гасников Александр (зав. каф. МОУ, зав лаб. ММО школы ПМИ МФТИ);

Безносиков Александр (заведующий лабораторией МФТИ-Яндекс, научный сотрудник лаборатории математических методов оптимизации, преподаватель кафедры МОУ);

Бородич Екатерина (н.с. лаборатории ММО МФТИ, преподаватель МФТИ, м.н.с. ИППИ РАН).

Описание проекта:

Машинное обучение становится популярнее с каждым днём. Между тем, львиная доля задач обучения — это задачи оптимизации. В связи с тем, что в современных реалиях размеры моделей и объемы обучающих выборок растут с геометрической скоростью, все чаще приходится прибегать к распределенным подходам обучения. Смысл в том, чтобы разделить обучающую выборку между вычислителями, при это каждый вычислитель считает градиент по своим локальным данным, пересылает этот градиент на сервер, а сервер, агрегируя все градиенты, делает итоговый шаг спуска. В такой постановке коммуникации являются бесполезной (с точки зрения оптимизации) тратой времени, поэтому хотелось бы уменьшить их влияние на общее время работы алгоритма обучения.

Чтобы снизить коммуникационную сложность, можно прибегать к использованию сжатий пересылаемой информации. В самом простом случае, мы можем пересылать не полный градиент, а, например, случайный набор его координат. Обычно в таких подходах случайность выбора координат на каждой пересылке генерируется независимо для каждого раунда коммуникации. Возникает вопрос: если мы пересылали какую-то координату на прошлой итерации, то может быть сейчас стоит уменьшить вероятность ее выбора или вообще не пересылать ее? Кажется, такой подход является более практичным, но с точки зрения теории операторы сжатия перестают быть независимыми и становятся марковскими. Можно пойти дальше и учитывать не только последнюю генерацию случайности, но и последние 2, 5, 10. Также такой оператор можно использовать в комбинации с другими операторами сжатия.

Цель этого проекта исследовать озвученные выше вопросы с точки зрения как теории, так и практики.

Статьи для изучения:

On Biased Compression for Distributed Learning

First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities

2. Исследование характеристик меняющихся графов

Преподаватели:

Гасников Александр (зав. каф. МОУ, зав лаб. ММО школы ПМИ МФТИ);

Рогозин Александр (научный сотрудник лаборатории ММО, руководитель проекта Huawei).

Описание проекта:

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

С точки зрения оптимизации, сложность решения децентрализованной задачи зависит от параметров как оптимизируемых функций, которые хранятся на узлах, так и от параметров меняющейся сети. Обычно основной характеристикой сети считается mixing time, которое соответствует спектральным свойствам коммуникационной матрицы графа. Однако возможно использование других характеристик.

В проекте мы рассмотрим метрику эффективного числа соседей и постараемся понять, насколько хорошо она описывает сеть с точки зрения оптимизации.

Статья для изучения:

Beyond spectral gap: The role of the topology in decentralized learning

3. Обучение перепараметризованных моделей

Преподаватели:

Двинских Даша (доцент ВШЭ, лектор по Математической статистике на базовом потоке ФКН);

Лобанов Александр (младший научный сотрудник лаборатории продвинутой комбинаторики и сетевых приложений МФТИ).

Описание проекта:

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

Как использовать перепараметризацию при обучении (оптимизации) таких моделей? Наука здесь довольно сильно продвинулась в последние годы. В частности, совсем недавно были получены тонкие результаты о том, как можно использовать моментное ускорение и батчирование в таких моделях: An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning. Поскольку все это достаточно новые вещи, то многие из теоретических достижений еще не достаточно проверены на практике. Более того, некоторые направления исследований, которые хорошо разработаны в классическом (неперепараметризованном) случае, пока и в теоретическом плане не в должной степени перенесены на перепараметризованные модели (например, изучение тяжелых хвостов, что характерно для обучения моделей типа BERT; безградиентные модели обучения и т.д.).

В проекте будет предложено проверить, на сколько на практике перепараметризация может ускорять процесс обучения, при должной его корректировки.

4. Ускоренный методы решения стохастических распределенных задач на децентрализованных меняющихся сетях связи

Преподаватели:

Ковалев Дмитрий (CORE UCL, Belgium);

Екатерина Бородич Екатерина (н.с. лаборатории ММО МФТИ, преподаватель МФТИ, м.н.с. ИППИ РАН).

Описание проекта:

Задачи оптимизации имеют массу практических применений в различных областях от экономики и оптимального управления до машинного обучения и анализа данных. Реалии сегодняшнего дня очень часто подталкивают решать задачи распределенно, т.е. используя сразу несколько вычислительных устройств. В таком случае очень важно организовать процесс коммуникаций между вычислителями. Хорошим и популярным вариантом является централизованный подход, который предполагает, что общение осуществляется через некоторого координатора (сервер). Обычно такой сервер соединен со всеми остальными вычислителями, может принимать информацию от них, агрегировать и рассылать ответы. В первых двух направлениях проекта мы остановимся именно на таком варианте общения устройств.

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

Это и есть цель данного проекта — разработать алгоритм, который сможет решать децентрализованно на меняющихся графах связи различного рода стохастические задачи оптимизации. Более того, хочется получить не просто эффективный алгоритм, а оптимальный с точки зрения теории, поэтому здесь не обойтись без популярной и широко используемой в алгоритмах обучения техники ускорения с помощью момента инерции.

Статьи для изучения:

Recent theoretical advances in decentralized distributed convex optimization

Decentralized Convex Optimization over Time-Varying Graphs: a Survey

29.07.2023