Розроблено оптимальний алгоритм децентралізованої оптимізації для динамічних мереж.

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

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

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

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

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

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

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

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

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

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

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

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

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

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