Исследователи из России и США разработали новый децентрализованный алгоритм оптимизации, который позволяет эффективно решать различные задачи без необходимости в центральном сервере и предварительной настройке параметров. Результаты их работы были опубликованы на конференции NeurIPS 2024.
В современных распределенных системах, где множество компьютеров (агентов) работают вместе, часто используется центральный сервер для координации вычислений. Это может создавать узкие места и проблемы с масштабируемостью. Существующие децентрализованные алгоритмы требуют точной информации о параметрах задачи и структуре сети, что не всегда возможно. Это похоже на строительство дома без плана и материалов.
Новый алгоритм решает эту проблему, позволяя каждому агенту самостоятельно определять оптимальный размер шага в процессе обучения, используя только локальную информацию. Это делает алгоритм более адаптивным и быстрым. Он постоянно подстраивается под особенности функции потерь без необходимости обмена данными со всеми агентами.
Теоретические исследования показали, что новый алгоритм обеспечивает линейную сходимость, что означает, что он быстро приближается к решению даже на поздних этапах. Сходимость зависит от сложности задачи и от того, насколько хорошо агенты могут обмениваться информацией. В хорошо связанных сетях алгоритм работает почти так же быстро, как централизованный.
Авторы предложили две версии алгоритма. Первая использует глобальную информацию о размере шага, что обеспечивает более быструю сходимость, но требует больше обмена данными. Вторая версия работает только с информацией от ближайших соседей, что снижает потребность в коммуникации, но может быть немного медленнее. Выбор между этими алгоритмами зависит от конкретной сети и ее возможностей.
Эксперименты подтвердили, что новые алгоритмы значительно быстрее существующих децентрализованных решений, особенно при работе с большими данными и в слабо связанных сетях. Алгоритм успешно протестировали на задаче гребневой регрессии, популярной в машинном обучении.
Александр Гасников, заведующий лабораторией математических методов оптимизации МФТИ, отметил, что их метод позволяет адаптивно выбирать размер шага без необходимости в глобальной информации, что приводит к лучшим результатам по сравнению с существующими методами.
В будущем исследователи планируют адаптировать свои методы для стохастических задач и более сложных сетевых топологий, что поможет создать более эффективные системы машинного обучения в распределенных средах.
