• Добавить в закладки
  • Facebook
  • Twitter
  • Telegram
  • VK
  • Печать
  • Email
  • Скопировать ссылку
2 часа назад
ФизТех
69

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

4.4

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

Зависимость достигаемой точности от количества итераций для разных алгоритмов в задаче гребневой регрессии на разных графах: (1a) Линейный граф; (1b) Граф Эрдеша—Реньи с вероятностью активации ребра p = 0,1; (1c) Граф Эрдеша—Реньи с вероятностью активации ребра p = 0,5 / © NeurIPS 2024

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

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

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

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

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

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

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

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

Численные эксперименты подтвердили теоретические выводы о том, что новые алгоритмы значительно превосходит по скорости существующие децентрализованные алгоритмы. Эта разница особенно заметна при решении сложных задач с большим количеством данных и при работе в слабо связанных сетях. Алгоритм был успешно протестирован на задаче гребневой регрессии (ridge regression) — распространенной задаче машинного обучения.

«Наш подход использует метод разбиения операторов с новой переменной метрикой, что позволяет использовать локальный поиск по линиям с обратным шагом (backtracking line-search) для адаптивного выбора размера шага без глобальной информации или обширной коммуникации, — рассказал Александр Гасников, заведующий лабораторией математических методов оптимизации МФТИ. — Это приводит к благоприятным гарантиям сходимости и зависимости от параметров оптимизации и сети по сравнению с существующими неадаптивными методами. Примечательно, что новый метод является первым адаптивным децентрализованным алгоритмом, который достигает линейной сходимости для сильно выпуклых и гладких функций».

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

Нашли опечатку? Выделите фрагмент и нажмите Ctrl + Enter.
Московский физико-технический институт (национальный исследовательский университет), известен также как Физтех — ведущий российский вуз по подготовке специалистов в области теоретической, экспериментальной и прикладной физики, математики, информатики, химии, биологии и смежных дисциплин. Расположен в городе Долгопрудном Московской области, отдельные корпуса и факультеты находятся в Жуковском и в Москве.
Подписывайтесь на нас в Telegram, Яндекс.Новостях и VK
Вчера, 19:00
Андрей

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

Позавчера, 15:35
Андрей

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

Вчера, 15:25
Елизавета Александрова

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

Позавчера, 15:35
Андрей

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

20 декабря
Игорь Байдов

Один из самых знаменитых археологических памятников мира — Стоунхендж — начали возводить на территории современного графства Уилтшир в Англии еще в каменном веке. На протяжении полутора тысяч лет Стоунхендж достраивали и перестраивали, изменяя при этом его планировку. Авторы нового исследования еще раз проанализировали маршрут камней, из которых сложено мегалитическое сооружение, и рассказали, зачем его могли перестроить между 2620-2480 годами до нашей эры, когда в центре сооружения появился Алтарный камень.

20 декабря
Любовь

Чтобы выяснить, связано ли количество ежедневных шагов с депрессией во взрослом возрасте, международная исследовательская группа проанализировала данные 33 исследований, в которых участвовали почти 100 тысяч человек. Результаты показали, что ходьба значительно влияет на психическое здоровье, в том числе снижая риск развития депрессии

28 ноября
Елизавета Александрова

Обсерватории постоянно улавливают «мигающие» радиосигналы из глубин Вселенной. Чаще всего их источниками оказываются нейтронные звезды, которые за это и назвали пульсарами. Но к недавно обнаруженному источнику GLEAM-X J0704-37 они, по мнению астрономов, отношения не имеют.

25 ноября
Полина Меньшова

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

3 декабря
Елизавета Александрова

Американская лунная программа «Артемида» предусматривает экспедиции длительностью от нескольких дней до долгих недель и даже месяцев, но луномобиля для передвижения экипажа по поверхности спутника Земли на сегодня нет. Поэтому космическое агентство США продумывает план действий на случай, если астронавты окажутся далеко от базы и кто-то из них внезапно не сможет идти самостоятельно.

[miniorange_social_login]

Комментарии

Написать комментарий
Подтвердить?
Подтвердить?
Причина отклонения
Подтвердить?
Не получилось опубликовать!

Вы попытались написать запрещенную фразу или вас забанили за частые нарушения.

Понятно
Жалоба отправлена

Мы обязательно проверим комментарий и
при необходимости примем меры.

Спасибо
Аккаунт заблокирован!

Из-за нарушений правил сайта на ваш аккаунт были наложены ограничения. Если это ошибка, напишите нам.

Понятно
Что-то пошло не так!

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

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

Мы скоро изучим заявку и свяжемся с Вами по указанной почте в случае положительного исхода. Спасибо за интерес к проекту.

Понятно
Ваше сообщение получено

Мы скоро прочитаем его и свяжемся с Вами по указанной почте. Спасибо за интерес к проекту.

Понятно