Группа российских ученых из МФТИ, Сколтеха и Научно-исследовательского центра искусственного интеллекта Университета Иннополис разработала революционный алгоритм для решения сложной задачи децентрализованной оптимизации. Результаты исследования опубликованы в материалах конференции NeurIPS 2024.
В современном мире многие вычислительные задачи требуют обработки больших объемов данных, распределенных по множеству компьютеров или устройств, образующих сеть. Классический подход - обработка данных на центральном сервере - становится неэффективным при большом количестве узлов и больших объемах данных. Децентрализованная оптимизация предлагает альтернативное решение, которое заключается в том, что каждый узел сети выполняет вычисления, используя только свои локальные данные, и обменивается информацией только со своими соседями. Это существенно повышает надежность, масштабируемость и защищенность системы.
Эта задача существенно усложняется, если учитывать, что связи между узлами сети могут меняться со временем. Динамичность сети характерна для многих реальных систем, таких как беспроводные сенсорные сети, распределенные системы машинного обучения и будущие поколения федеративного обучения. В таких условиях разработка эффективных алгоритмов оптимизации представляет собой значительную вычислительную проблему. До сих пор в научной литературе отсутствовали оптимальные алгоритмы, а также теоретические оценки минимального количества коммуникаций и вычислений, необходимых для решения задачи децентрализованной оптимизации для негладких функций в динамических сетях.
Исследовательская группа российских ученых успешно преодолела этот барьер.
"Мы впервые установили нижние границы сложности коммуникации и вычислений для решения задач негладкой выпуклой децентрализованной оптимизации в динамически изменяющихся сетях, - рассказалАлександр Гасников, заведующий лабораторией математических методов оптимизации МФТИ. - Более того, мы разработали первый оптимальный алгоритм, который достигает этих нижних границ и демонстрирует значительно улучшенную теоретическую производительность по сравнению с существующими методами".
Разработанный алгоритм основан на особом методе решения задачи оптимизации - сведение к решению специально седловой задачи. Эта методика позволяет переформулировать исходную задачу в виде более удобного для решения уравнения. В отличие от предыдущих подходов, новый алгоритм учитывает негладкость функций, хранящихся на узлах сети. Ключевым моментом является применение ускоренного метода "вперед-назад", модифицированного для работы в динамической среде. Алгоритм использует механизм обратной связи по ошибкам для эффективного обмена информацией в сети с переменной топологией.
Ученые доказали оптимальность своего алгоритма, установив строгие нижние границы сложности вычислений и коммуникаций. Эти границы показывают, что разработанный алгоритм работает не только эффективно, но и достигает теоретически наилучшего возможного результата для данного класса задач. Полученные теоретические результаты подтверждены предварительными численными экспериментами, демонстрирующими превосходство нового алгоритма по скорости сходимости и масштабируемости по сравнению с существующими методами.
Для проверки алгоритма исследователи использовали модель задачи регрессии с квадратичной регуляризацией на синтетических данных. Эксперименты проводились на различных типах сетей с различной степенью связности узлов, моделирующих различные сценарии реальных систем. Результаты показали существенное превосходство нового алгоритма над известными аналогами, особенно при увеличении числа узлов сети и сложности оптимизируемой функции.
Для сравнения авторы использовали обычный децентрализованный алгоритм субградиентного спуска, который разошелся и не смог решить задачу, более усовершенствованный алгоритм субградиентного спуска с Push-суммами и алгоритм ZO-SADOM, использующий рандомизированное сглаживание.
Усовершенствованный алгоритм субградиентного спуска использует протокол Push-Sum для агрегации информации, что позволяет ему справляться с потенциально несимметричной матрицей весов сети и обеспечивает корректную сходимость. Однако скорость сходимости Subgradient-Push оказалась невысока.
Алгоритм ZO-SADOM, хотя и способен эффективно работать в условиях изменяющейся сети и негладких функций, имеет худшую оценку сложности по сравнению с разработанным авторами новым алгоритмом. Это обусловлено дополнительными вычислительными затратами, связанными с рандомизированным сглаживанием, и не оптимальным использованием метода ADMM в контексте задачи. Авторы статьи успешно показали, что их новый метод обходит эти недостатки.
Интересно, что даже в сценарии, когда каждый узел обменивается информацией только с ближайшими соседями (локальный поиск минимума), новый алгоритм значительно превосходит по производительности существующие аналоги, которые требуют обмена данными по всей сети.
Полученные результаты открывают новые перспективы для дальнейших исследований в области децентрализованной оптимизации. В частности, авторы планируют изучить возможность применения разработанного алгоритма для решения задач с невыпуклыми функциями и адаптации алгоритма к более сложным и реалистичным моделям динамических сетей.
Разработка оптимального алгоритма для децентрализованной оптимизации в динамических сетях представляет собой значительный прорыв в области вычислительной математики и машинного обучения. Новый алгоритм обладает высокой эффективностью, масштабируемостью и устойчивостью к изменениям сетевой топологии, что открывает новые возможности для решения широкого круга практических задач.
