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

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

1 238

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

    Когда мы стали чужими

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

    "Донни всех подебил". Дайджест за 6 апреля 2025

    Главным событием уходящей недели стало, без сомнения, введение президентом США Дональдом Трампом тарифов против всей планеты (за исключением России и Белоруссии, Козырев своих не трогает). Даже пи...

    Германия потребовала российский газ
    • pretty
    • Вчера 08:16
    • В топе

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

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

    0 новых комментариев
    :bowtie: :smile: :laughing: :blush: :smiley: :relaxed: :smirk: :heart_eyes: :kissing_heart: :kissing_closed_eyes: :flushed: :relieved: :satisfied: :grin: :wink: :stuck_out_tongue_winking_eye: :stuck_out_tongue_closed_eyes: :grinning: :kissing: :kissing_smiling_eyes: :stuck_out_tongue: :sleeping: :worried: :frowning: :anguished: :open_mouth: :grimacing: :confused: :hushed: :expressionless: :unamused: :sweat_smile: :sweat: :disappointed_relieved: :weary: :pensive: :disappointed: :confounded: :fearful: :cold_sweat: :persevere: :cry: :sob: :joy: :astonished: :scream: :neckbeard: :tired_face: :angry: :rage: :triumph: :sleepy: :yum: :mask: :sunglasses: :dizzy_face: :imp: :smiling_imp: :neutral_face: :no_mouth: :innocent: :alien: :yellow_heart: :blue_heart: :purple_heart: :heart: :green_heart: :broken_heart: :heartbeat: :heartpulse: :two_hearts: :revolving_hearts: :cupid: :sparkling_heart: :sparkles: :star: :star2: :dizzy: :boom: :collision: :anger: :exclamation: :question: :grey_exclamation: :grey_question: :zzz: :dash: :sweat_drops: :notes: :musical_note: :fire: :shit: :thumbsup: :thumbsup: :-1: :thumbsdown: :ok_hand: :punch: :facepunch: :fist: :v: :wave: :hand: :raised_hand: :open_hands: :point_up: :point_down: :point_left: :point_right: :raised_hands: :pray: :point_up_2: :clap: :muscle: :metal: :fu: :runner: :running: :couple: :family: :dancer: :dancers: :ok_woman: :no_good: :information_desk_person: :raising_hand: :bride_with_veil: :person_with_pouting_face: :person_frowning: :bow: :couplekiss: :couple_with_heart: :massage: :haircut: :nail_care: :boy: :girl: :woman: :man: :baby: :older_woman: :older_man: :person_with_blond_hair: :man_with_gua_pi_mao: :man_with_turban: :construction_worker: :cop: :angel: :princess: :smiley_cat: :smile_cat: :heart_eyes_cat: :kissing_cat: :smirk_cat: :scream_cat: :crying_cat_face: :joy_cat: :pouting_cat: :japanese_ogre: :japanese_goblin: :see_no_evil: :hear_no_evil: :speak_no_evil: :guardsman: :skull: :feet: :lips: :kiss: :droplet: :ear: :eyes: :nose: :tongue: :love_letter: :bust_in_silhouette: :busts_in_silhouette: :speech_balloon: :thought_balloon: :feelsgood: :finnadie: :goberserk: :godmode: :hurtrealbad: :rage1: :rage2: :rage3: :rage4: :suspect: :trollface:
    Пишите здесь

    80летпобеды

    6 апреля 1943 года секретарь Витебского подпольного обкома ВКП(б) Яким Жилянин подготовил Справку о преступлениях немецких оккупантов в Витебской области. В документе говорилось: «В каждом населенном пункте Россонского и других районов Витебской области, где проходила карательная экспедиция противника, остался кровавый след их преступлений над мирными с...
    185

    В Пермском крае стая собак загнала двух школьниц по пояс в водоем

    Детская прогулка в Пермском крае едва не закончилась трагедией: стая из девяти бездомных собак внезапно начала преследовать двух девочек школьного возраста.https://rg.ru/2025/04/06/reg-pfo/prokuratura-prikamia-nachala-proverku-po-faktu-napadeniia-stai-sobak-na-detej.htmlhttps://t.me/WhatDontYouLoveUsAnymore...
    181

    В Нью-Дели прошел российско-индийский мотопробег к 80-летию Победы

    Российско-индийский мотопробег, приуроченный к 80-летию Победы в Великой Отечественной войне, прошел в Нью-Дели. Кадры мероприятия появились в распоряжении РЕН ТВ. Мотопробег был организован совместными усилиями российского и индийского посольств, Русского дома в Нью-Дели и столичного мотоклуба Delhi Bikers Breakfast Run. Отмечается, что н...
    147

    Четвертый ледокол проекта 22220 покинул территорию завода, ушел в эксплуатацию на 40 лет

    Универсальный атомный ледокол проекта 22220 "Якутия" покинул достроечную набережную Балтийского завода в Петербурге и отправился в порт приписки Мурманск, сообщило предприятие. https://t.me/rian_ru...
    107

    В РФПИ заявили о большом желании компаний США вернуться в РФ

    Зафиксировано большое количество запросов от американских компаний, которые хотят вернуться в Россию. Об этом заявил глава Российского фонда прямых инвестиций (РФПИ), спецпредставитель президента РФ по экономическому сотрудничеству с зарубежными странами Кирилл Дмитриев в интервью Первому каналу.«Мы видим большое количество запросов от американских комп...
    91

    Сегодня еще одна знаменательная дата в истории нашего государства – день официального вхождения малороссийских земель в состав России.

       6 апреля 1654 царь Алексей Михайлович Романов подписал жалованную грамоту гетману Богдану Хмельницкому и Войску Запорожскому. Документ официально закрепил решение о воссоединении Великой и Малой Руси. На тот момент малороссийские земли представляли собой несколько областей: Киевскую, Черкасскую Полтавскую и Черниговскую. Воссоединение Украин...
    93

    Сводка Министерства обороны Российской Федерации о ходе проведения специальной военной операции по состоянию на 6 апреля 2025 г.

      - Сегодня ночью Вооруженными Силами Российской Федерации нанесен групповой удар высокоточным оружием большой дальности воздушного и морского базирования, а также беспилотными летательными аппаратами по центральной артиллерийской базе вооружения ВСУ, а также предприятиям оборонно-промышленного комплекса, задействованным в производстве БПЛА. Цель уд...
    162

    ВС России освободили населенный пункт Басовка в Сумской области

    Российская группировка войск "Север" освободила населённый пункт Басовка в Сумской области Украины, сообщили в Минобороны РФ."Подразделениями группировки войск "Север" в ходе наступательных действий освобожден населенный пункт Басовка Сумской области", - говорится в сводке ведомства о ходе отражения попытки вторжения ВСУ на территорию России в Курской о...
    149

    В 1926-1928 годах большевики провели массовое переименование названий блюд.

       Убирались старые буржуазные названия, заменялись на новые нейтральные или идеологически выдержанные.Но на более всего интересует то, как проводились переименования в национальных республиках. И тут замечательное свидетельство фото 3, с инструкцией о переименовании в Белорусской ССР.Обратите внимание на то, что борщ малороссийский остается с ...
    694

    Суд арестовал активы Чубайса в деле по иску "Роснано"

    Арбитражный суд Москвы в деле по иску "Роснано" о взыскании убытков с Анатолия Чубайса и семи другим бывших руководителей этой корпорации арестовал имущество ответчиков, в том числе денежные средства, в пределах суммы исковых требований – более 5,6 миллиарда рублей, следует из опубликованного определения суда.Иск "Роснано" поступил в суд 31 марта, он пр...
    262

    Глава Следственного комитета Бастрыкин выступил с идеей снизить возрастной порог наступления уголовной ответственности за сбыт наркотиков с 16 до 14 лет

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

    125 лет назад 6 апреля 1899 года в Москве пущен первый трамвай

      Современный общественный транспорт впервые появился в Москве только в 1872 году. До этого замечательного дня москвичи могли ходить пешком, ездить верхом и пользоваться услугами частных предпринимателей, которые в 1847 году организовали движение открытых многоместных конных экипажей – омнибусов. Они даже создали в 1850 году Общество московских мног...
    222

    6 АПРЕЛЯ 1772 ГОДА ЕКАТЕРИНА II ОТМЕНИЛА ПОШЛИНУ НА НОШЕНИЕ БОРОДЫ, КОТОРУЮ ВВЁЛ ПЁТР I.

      Данная пошлина просуществовала в России более семи десятилетий. Однако результат уже был достигнут – поголовного ношение бороды среди мужского населения в России к тому времени уже не существовало.Но и после отмены пошлины во времена Екатерины II ходить с бородой не разрешалось государственным чиновникам, военным и придворным.https://t.me/historic...
    203

    Уникальная российская ледовая платформа работает в 500 км от Северного полюса

    На единственной в мире ледостойкой самодвижущейся платформе (ЛСП) «Северный полюс», построенной в 2022 году в Санкт-Петербурге, дрейфующей в районе 180 градуса восточной долготы, на расстоянии около 500 км от самой северной точки нашей планеты, продолжается работа научной экспедиции. В конце марта 2025 года на борт этого гибрида судна и полноценной науч...
    444

    Новые российские троллейбусы поступили в город Балаково

    В дополнение к 12 новым троллейбусам 6281.01 «Адмирал» с увеличенным автономным ходом, поставленным в прошлом году, в марте 2025 года в город Балаково (Саратовская область) прибыли еще 4 аналогичные машины.Как сообщает производитель российского электротранспорта компания «ПК Транспортные системы», поставка новых троллейбусов в город позволяет улучшить к...
    317

    В Нижнем Новгороде спустили на воду земснаряд Florian-501

    Компания "ГидроСтрой" спустила на воду первую из четырех барж (земснарядов) для проведения швартовых испытаний, сообщило Федеральное агентство морского и речного транспорта.Баржа оснащена сваями, якорными системами удержания и экскаватором для эффективной работы по дноуглублению. Судно задействуют при реконструкции судоходных шлюзов 15-16 Городецкого ги...
    186

    НА КУБЕ ЗАПУСТИЛИ СБОРОЧНУЮ ПЛОЩАДКУ УАЗ

      В Гаване состоялся запуск сборочной площадки УАЗ. Автомобили выпускают крупноузловым методом из российских машинокомплектов. На новом заводе одновременно может собираться до шести автомобилей в день, то есть до полутора тысяч машин в год.Продажи внедорожников ожидаются в апреле. Выход на проектную мощность запланирован на сентябрь 2025 года. Помим...
    263

    "Тотальный диктант" по русскому языку охватил 50 стран мира

    Единственный диктант, где двойку точно получить невозможно, его еще называют тотальный, стартовал по всему миру 21-ый раз. От Москвы до Владивостока, от Сербии до Китая."У тотального диктанта большая серьезная миссия, – как минимум, популяризировать родной наш русский язык", – сказала актриса, теле- и радиоведущая Марина Кравец. Артисты, в...
    159

    Стоимость более половины квартир в России завышена на рекордные 31,1%

    Стоимость более половины квартир в России завышена в среднем на 31,1%. Такими данными располагают в федеральной компании "Этажи".В марте 2024 года средняя стоимость квадратного метра в России составляла 96,5 тысячи рублей. Но этот же показатель на вторичном рынке среди выставляемой на продажу недвижимости равнялся уже 122,5 тысячи рублей."На фоне высоки...
    278

    Засекреченное средство РЭБ "Волна-2" защищает Россию от беспилотников

    Регионы России защищает от украинских беспилотников засекреченное средство радиоэлектронной борьбы (РЭБ) "Волна-2". Все началось с разработки в небольшом помещении, а теперь эти системы защищают всю территорию РФ. Корреспонденту "Известий" Анастасии Харченко удалось узнать подробности о секретной "Волне".Со стороны работа этой РЭБ совсем незаметна. Враж...
    393
    Служба поддержи

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