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