- Push-LSVRG-UP: распределенная стохастическая оптимизация в несбалансированных направленных сетях с несогласованными инициируемыми вероятностями (arXiv)
Автор: Цзинхуэй Ху, Го Чэнь, Хуацин Ли, Цысян Шэнь, Вэйдун Чжан.
Аннотация: Распределенная стохастическая оптимизация, возникающая в результате пересечения и интеграции традиционной стохастической оптимизации, распределенных вычислений и хранения данных, а также науки о сетях, имеет преимущества высокой эффективности и низкой вычислительной сложности на итерацию при решении крупномасштабных задач оптимизации. Эта статья посвящена решению крупномасштабной выпуклой задачи оптимизации с конечной суммой в многоагентной системе в несбалансированных направленных сетях. Чтобы эффективно решить эту проблему, был разработан и назван Push-LSVRG-UP алгоритм оптимизации распределенного консенсуса, использующий метод push-sum и метод распределенного беспетлевого стохастического градиента с уменьшенной дисперсией (LSVRG) с несогласованными срабатывающими вероятностями. Каждый агент в этой алгоритмической структуре выполняет только локальные вычисления и общается только со своими соседями, не допуская утечки их личной информации. Анализ сходимости Push-LSVRG-UP основан на анализе взаимосвязей между четырьмя ошибками, связанными с многоагентной системой. Теоретические результаты обеспечивают явный допустимый диапазон постоянного размера шага, линейной скорости сходимости и сложности итерации Push-LSVRG-UP при достижении глобально оптимального решения. Показано, что Push-LSVRG-UP достигает превосходных характеристик ускоренной линейной сходимости, меньших затрат на хранение и меньшей вычислительной сложности на итерацию, чем большинство существующих работ. Между тем, введение нескоординированного вероятностного триггерного механизма позволяет Push-LSVRG-UP повысить независимость и гибкость агентов при вычислении локальных пакетных градиентов. При моделировании практичность и улучшенная производительность Push-LSVRG-UP проявляются в решении двух задач распределенного обучения на основе наборов данных из реального мира.
2. Нижние границы и ускоренные алгоритмы в распределенной стохастической оптимизации со сжатием связи (arXiv)
Автор: Ютун Хэ, Синьмэн Хуан, Имин Чен, Вотао Инь, Кун Юань.
Аннотация: Сжатие связи является важной стратегией для уменьшения накладных расходов на связь за счет уменьшения объема информации, которой обмениваются вычислительные узлы в крупномасштабной распределенной стохастической оптимизации. Хотя было получено множество алгоритмов с гарантией сходимости, оптимальный предел производительности при сжатии связи остается неясным. В этой статье мы исследуем предел производительности алгоритмов распределенной стохастической оптимизации, использующих сжатие связи. Мы фокусируемся на двух основных типах компрессоров, несмещенных и сжатых, и обращаемся к максимально возможной степени сходимости, которую можно получить с помощью этих компрессоров. Мы устанавливаем нижние границы скорости сходимости распределенной стохастической оптимизации в шести различных условиях, комбинируя сильно выпуклые, обычно выпуклые или невыпуклые функции с несмещенными или сжимающими типами сжатия. Чтобы преодолеть разрыв между нижними границами и скоростями существующих алгоритмов, мы предлагаем NEOLITHIC, почти оптимальный алгоритм со сжатием, который достигает установленных нижних границ с точностью до логарифмических коэффициентов в мягких условиях. Обширные экспериментальные результаты подтверждают наши теоретические выводы. Эта работа дает представление о теоретических ограничениях существующих компрессоров и мотивирует дальнейшие исследования принципиально новых свойств компрессоров.
