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