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

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

Існуючі децентралізовані алгоритми оптимізації страждають від серйозного недоліку: для їх ефективної роботи необхідно точно знати параметри як самої задачі оптимізації (наприклад, «константу Ліпшица» градієнта, що характеризує крутизну функції втрат), так і топології мережі, по якій спілкуються агенти (ступінь їх взаємозв'язку). У реальних розподілених системах агенти зазвичай не мають доступу до цієї глобальної інформації, що змушує використовувати дуже консервативні налаштування параметрів і, як наслідок, призводить до повільної збіжності або навіть розбіжності алгоритму. Це схоже на те, як якщо б будівельники намагалися побудувати будинок, не знаючи ні плану будівлі, ні того, де знаходиться будівельний матеріал.

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

Він заснований на методі «розбиття операторів» і використанні нової змінної метрики. Це дозволяє кожному агенту самостійно визначати оптимальний розмір кроку в процесі навчання, використовуючи локальну інформацію. Це подібно до того, як досвідчений будівельник, оцінюючи ситуацію на місці, вирішує, який інструмент і як використовувати.

Замість того, щоб покладатися на заздалегідь задані параметри, алгоритм постійно адаптується до місцевих особливостей функції втрат. Кожен агент виконує локальний пошук оптимального кроку, не вимагаючи обміну інформацією з усіма іншими агентами в мережі. Цей «локальний» підхід значно прискорює обчислення і робить алгоритм більш масштабованим.

Теоретичний аналіз показав, що новий алгоритм забезпечує лінійну збіжність – це означає, що швидкість наближення до рішення залишається високою навіть на пізніх етапах обчислень. Швидкість збіжності залежить від двох факторів: складності самої задачі оптимізації та «зв'язності» мережі, тобто того, наскільки добре агенти обмінюються інформацією між собою. У добре зв'язаних мережах швидкість збіжності наближається до швидкості централізованого алгоритму. Це як якщо б усі будівельники працювали на одному об'єкті, а не по всьому місту.

Автори запропонували дві модифікації свого алгоритму. Обидва алгоритми є децентралізованими і використовують локальний лінійний пошук для адаптивного вибору розміру кроку кожним агентом індивідуально. Однак механізм узгодження цих локальних розмірів кроку різний. Перший алгоритм використовує механізм пошуку глобального мінімуму. Кожен агент обчислює свій локальний оптимальний розмір кроку, а потім усі агенти обмінюються цією інформацією, і в якості глобального розміру кроку вибирається мінімальне значення серед усіх агентів, що вимагає комунікації між усіма агентами в мережі. Другий алгоритм заснований на використанні тільки локального мінімуму. Кожен агент обчислює свій локальний оптимальний розмір кроку, а потім вибирає в якості свого розміру кроку мінімум серед своїх безпосередніх сусідів, включаючи самого себе. Це вимагає комунікації тільки з сусідами в мережі.

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

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

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

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