• РЕГИСТРАЦИЯ

Российские ученые создали оптимальный алгоритм децентрализованной оптимизации для динамических сетей

1 243

Группа российских ученых из МФТИ, Сколтеха и Научно-исследовательского центра искусственного интеллекта Университета Иннополис разработала революционный алгоритм для решения сложной задачи децентрализованной оптимизации. Результаты исследования опубликованы в материалах конференции NeurIPS 2024.

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

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

Исследовательская группа российских ученых успешно преодолела этот барьер.

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

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

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

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

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

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

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

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

***************************************************************

Рисунок 1. Рой дронов в Санкт-Петербурге. Источник: Дарья Драй ИА REGNUM.Разработанный алгоритм позволяет обучать большие модели на распределенных вычислительных ресурсах с учетом ненадежности связи между узлами, оптимизировать распределение ресурсов в беспроводных сетях и энергосистемах, обеспечивать коллективное управлением группами роботов и роями дронов в условиях динамически изменяющейся среды, а также создавать эффективные и устойчивые системы федеративного обучения, учитывающие динамику мобильных сетей.

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

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

https://zanauku.mipt.ru/2024/12/19/rossijskie-uchenye-sozdali-optimalnyj-algoritm-detsentralizovannoj-optimizatsii-dlya-dinamicheskih-setej/

    Что ж ты, джентльмен, сдал назад?

    Так вот почему британцы вдруг резко расхотели  отправлять наземные войска на Украину? The Times приводит сегодня слова коммодора авиации Блайта Кроуфорда, который до прошлой недели...

    Попову дали пять лет. На СВО? "Нет вакансий!" А он журналистам: "Спасибо, ребята"
    • Beria
    • Вчера 10:49
    • В топе

    Тамбовский гарнизонный суд дал генералу Ивану Попову 5 лет. С отбыванием в колонии общего режима. А ещё, по решению суда, экс-командарм должен выплатить штраф в 800 тысяч рублей. В этом деле, к...

    Ваш комментарий сохранен и будет опубликован сразу после вашей авторизации.

    0 новых комментариев

      В России собран первый дизель-генератор для нового грузопассажирского тепловоза ТЭ26

      В апреле 2025 года собран и отправлен для установки на новом российском тепловозе ТЭ26 первый дизель-генератор 18-9ДГМ-02. Силовой агрегат выпущен на Коломенском заводе в Московской области и является модификацией серийного 18-9ДГМ c новым тяговым агрегатом, первый тепловоз новой модели строят на Брянском машиностроительном заводе. Что это за техника?Но...
      1032

      День в истории.

         24 апреля 1877 года началась Русско-турецкая война, которая принесла свободу Болгарии.Это была война за свободу славянских народов. Турки жестоко подавили Апрельское восстание 1876 года в Болгарии. Боролись против турецкого владычества и другие славянские народы. После попыток дипломатического давления на Стамбул Россия объявила Османской им...
      100

      «АвтоВАЗ» представит в ОАЭ свою экспортную стратегию

        Компания проведет международную конференцию партнеров по экспорту, на которой представит ключевые направления развития бренда LADA на зарубежных рынках.Мероприятие объединит действующих и потенциальных партнеров, а также лидеров автомобильной отрасли из более чем 37 стран мира, включая государства СНГ, Ближнего Востока, Африки, Латинской Америки и...
      246

      РАЗРАБОТАНА УПАКОВКА ДЛЯ НАДЕЖНОЙ ПЕРЕВОЗКИ И ДЛИТЕЛЬНОГО ХРАНЕНИЯ КРОВИ

        Группа молодых ученых Московского авиационного института разработала упаковку для надежной транспортировки и длительного хранения крови. Она изнутри покрыта тонким слоем ионов серебра, которое убивает проникающие извне микробы, вследствие чего срок хранения без риска для здоровья пациента при последующем переливании значительно увеличивается.Учены...
      137

      СПУЩЕНО НА ВОДУ СУДНО НА ПОДВОДНЫХ КРЫЛЬЯХ «ПЕТР СТОЛЫПИН»

        В Нижегородской области спустили на воду второе судно на подводных крыльях (СПК) «Валдай 45Р». Новое судно носит имя Петра Аркадьевича Столыпина, занимавшего с 1903 по 1906 годы пост главы Саратовской губернии.15 мая на территории производственного комплекса ЦКБ планируется передать новый «Валдай 45Р» заказчику, а далее СПК своим ходом отправится ...
      369

      НАЧАЛИСЬ ИСПЫТАНИЯ СИСТЕМЫ СПУТНИКОВОЙ СВЯЗИ ДЛЯ БЕСПИЛОТНИКОВ

        Российское конструкторское бюро «Интеллектуальные приборы» («Интеп») разработало первую в России систему спутниковой связи реального времени для беспилотных летательных аппаратов среднего класса. Изделие способно обеспечить новые возможности для БПЛА, существенно расширив радиус их действия. Генеральный директор конструкторского бюро Александр Кон...
      456

      СТАРТОВАЛО СЕРИЙНОЕ ПРОИЗВОДСТВО ИЗДЕЛИЙ И ИНСТРУМЕНТА ДЛЯ СТАНКОВ С ЧПУ

        На станкоинструментальном заводе «Вириал» в Санкт-Петербурге запустили серийное производство полного цикла твердосплавных сменных пластин и заготовок осевого инструмента для станков с числовым программным управлением. Первые партии продукции уже успешно прошли промышленные испытания. Среди ключевых заказчиков продукции Объединенная авиастроительна...
      113

      Военкор телеканала «Звезда» Никита Гольдин, который был ранен при обстреле ВСУ ракетами HIMARS в ЛНР, скончался в больнице. Он умер рано утром 22 апреля....
      125

      ПВО ночью сбила 87 украинских беспилотников

      Вооруженные силы за ночь сбили 87 дронов ВСУ над восемью регионами России, сообщило Минобороны. "В течение прошедшей ночи дежурными средствами ПВО уничтожено и перехвачено 87 украинских беспилотных летательных аппаратов самолетного типа", — рассказали в ведомстве.Военные ликвидировали:45 БПЛА — над территорией Крыма;по десять — над Белгородской и К...
      157

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

         Пример абсолютной самоотверженности – Александр Вячеславович Печелатов. Фельдшер скорой помощи Казачинско-Ленской районной больницы погиб при исполнении служебных обязанностей. Мы с горечью вспоминаем трагический случай, произошедший в 2024 году. Тогда бригада скорой медицинской помощи Казачинско-Ленской районной больницы выехала на вызов в ...
      355

      С использованием «Леонардо» авиакомпании России за два года перевезли 210 млн пассажиров

      На сегодняшний день российской системой обслуживания пассажиров пользуются 64 авиаперевозчикаФото: Пресс-служба Госкорпорации РостехС использованием системы бронирования авиабилетов «Леонардо» (Passenger Service System, PSS), развитием которой занимаются «РТ-Проектные технологии» Госкорпорации Ростех и «Сирена-Трэвел», авиакомпании России с 2023 года по...
      327

      Ростех внедрит на заводах собственную беспроводную связь с высоким уровнем безопасности

      Универсальная система позволит заменить зарубежные и устаревшие аналогиФото: Пресс-служба Госкорпорации РостехКомпания «РТ-Проектные технологии» Госкорпорации Ростех совместно с промышленным интегратором «УльтимаТек» импортозаместит защищенную беспроводную связь для промышленных объектов. Внедрением новейшей системы будет заниматься совместное предприят...
      342

      «Калашников» открыл новую производственную площадку в Москве

      Холдинг разместит здесь экспериментальное электронное производство по выпуску комплектующих и элементов электронной компонентной базыФото: концерн «Калашников»В Москве состоялось открытие новой производственной площадки концерна «Калашников». В церемонии принял участия мэр столицы Сергей Собянин. Завод площадью 34 тысячи кв. м возвели в рекордно коротки...
      459

      Человек с золотым лаптем

      Василий Александрович Кокорев (1817–1889) был меценатом просвещения, оборотистым промышленником, почётным членом Академии художеств, мыслителем-экономистом. На его письменном столе в конторе стоял золотой лапоть, напоминая партнёрам-купцам, что все мы, мол, корнями из крестьян-лапотников. И не стыдиться, а гордиться тем нужно — вон как высоко поднялись!...
      377

      Друзья, и в пасхальные дни продолжаются случаи, когда на изображениях или макетах храмов стираются православные кресты

        К нам продолжают поступать обращения граждан из разных регионов. Традиционные религии России - это неотъемлемая часть духовного и исторического наследия нашей страны. Задачи по защите наших традиционных духовно-нравственных ценностей поставлены перед всеми структурами и органами власти.  Во исполнение решений (https://t.me/Anna_Jurjevna/11107...
      310

      Суд арестовал имущество семьи экс-замгубернатора Ростовской области на 276 млн

      В Москве суд арестовал имущество семьи бывшего замгубернатора – министра транспорта Ростовской области Виталия Кушнарева на сумму более 276,6 миллиона рублей, сообщили в РИА Новости со ссылкой на правоохранительные органы."Общая стоимость арестованного имущества – более 276,6 миллиона рублей", – отметил собеседник агентства.Среди имущества, на которое н...
      850

      Ростех начал испытания системы «свой-чужой» для БПЛА

      Аппаратура в автоматическом режиме маркирует дружественные дроны на высоте до 5 км и расстоянии до 100 км от радиозапросчикаФото: Пресс-служба Госкорпорации РостехХолдинг «Росэл» Госкорпорации Ростех приступил к испытаниям системы идентификации беспилотников. Аппаратура работает по принципу «свой-чужой» и в автоматическом режиме маркирует дружественные ...
      330

      «РТ-Техприемка» создает ИИ-агенты на основе LLM моделей

      Новые разработки были представлены на конференции по анализу данных и технологиям искусственного интеллекта Data FusionФото: «РТ-Техприемка» Компания «РТ-Техприемка» Госкорпорации Ростех создает решения на основе искусственного интеллекта, которые позволят улучшить бизнес-процессы. Новые разработки, в частности корпоративный ИИ-помощник для работы с нор...
      190

      Сегодня день рождения....Остальное-когда подрастет

      Ленин как идеолог терроризмаИз обращения в Боевой комитет при Санкт-Петербургском комитете, 16 ноября 1905 г.: «Основывайте тотчас боевые дружины везде и повсюду – и у студентов, и у рабочих особенно. Пусть тотчас же организуются отряды от 3 до 10, до 30 и т.д. человек. Пусть тотчас же вооружаются они сами, кто как может, кто револьвером, кто ножом, кто...
      178

      Российские военные освободили населенный пункт Сухая Балка в ДНР

      Подразделения "Южной" группировки войск взяли под контроль населенный пункт Сухая Балка в ДНР, сообщили в Минобороны РФ."В результате активных действий подразделений "Южной" группировки войск освобожден населенный пункт Сухая Балка Донецкой Народной Республики", - говорится в сводке министерства. https://ria.ru/20250422/mo-2012704839.html...
      167
      Служба поддержи

      Яндекс.Метрика