Текущий выпуск Номер 7, 2024 Том 16

Все выпуски

[ Switch to English ]

Решение распределенных вариационных неравенств с использованием смещенной компрессии, похожести данных и локальных обновлений

Воронов Р.Е., Масленников Е.М., Безносиков А.Н.
 pdf (741K) / Дополнительные материалы

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

Ключевые слова: вариационные неравенства, смещенное сжатие, похожесть данных, локальные обновления
Цитата: Воронов Р.Е., Масленников Е.М., Безносиков А.Н. Решение распределенных вариационных неравенств с использованием смещенной компрессии, похожести данных и локальных обновлений // Компьютерные исследования и моделирование, 2024, т. 16, № 7, с. 1813-1827
Citation in English: Voronov R.E., Maslennikov E.M., Beznosikov A.N. Communication-efficient solution of distributed variational inequalities using biased compression, data similarity and local updates // Computer Research and Modeling, 2024, vol. 16, no. 7, pp. 1813-1827
DOI: 10.20537/2076-7633-2024-16-7-1813-1827
URL: http://crm.ics.org.ru/journal/article/3570/

 

Дополнительные материалы:

 

Доказательство Теоремы 1

SI_voronov.pdf

 

Creative Commons License Статья доступна по лицензии Creative Commons Attribution-NoDerivs 3.0 Unported License.

Журнал индексируется в Scopus

Полнотекстовая версия журнала доступна также на сайте научной электронной библиотеки eLIBRARY.RU

Журнал входит в систему  Российского индекса научного цитирования.

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Международная Междисциплинарная Конференция "Математика. Компьютер. Образование"

Международная Междисциплинарная Конференция МАТЕМАТИКА. КОМПЬЮТЕР. ОБРАЗОВАНИЕ.

Copyright © 2009–2024 Институт компьютерных исследований