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

Результаты исследования представлены в материалах конференции NeurIPS 2024. В современном мире множество вычислительных задач требует обработки больших объемов данных, распределенных по сети из множества компьютеров или устройств.

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

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

Исследовательская группа российских ученых успешно преодолела этот барьер. «Мы впервые установили нижние границы сложности коммуникации и вычислений для решения задач негладкой выпуклой децентрализованной оптимизации в динамически изменяющихся сетях, — сообщил Александр Гасников, заведующий лабораторией математических методов оптимизации МФТИ. — Более того, мы разработали первый оптимальный алгоритм, который достигает этих нижних границ и демонстрирует значительно улучшенную теоретическую производительность по сравнению с существующими методами».

Разработанный алгоритм основан на уникальном методе решения задачи оптимизации — сведении к специально седловой задаче. Эта методика позволяет переформулировать исходную задачу в более удобное для решения уравнение. В отличие от предыдущих подходов, новый алгоритм учитывает негладкость функций, хранящихся на узлах сети. Ключевым моментом является применение ускоренного метода «вперед-назад», адаптированного для работы в динамической среде. Алгоритм использует механизм обратной связи по ошибкам для эффективного обмена информацией в сети с переменной топологией.

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

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

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

Усовершенствованный алгоритм субградиентного спуска применяет протокол Push-Sum для агрегации информации, что позволяет ему справляться с потенциально несимметричной матрицей весов сети и обеспечивает корректную сходимость. Однако скорость сходимости Subgradient-Push оказалась невысокой.

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

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

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

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

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