Arxiv/Distributed Saddle-Point Problems Under Similarity 2021 2107.10706 — различия между версиями

«Distributed Saddle-Point Problems Under Similarity 2021 2107.10706»^{скачать}

Мы изучаем методы решения (сильно) выпуклых- (сильно) вогнутых задач перевала (SPP) в сетях двух типов - с основной / рабочей (централизованной) архитектурой и ячеистой (таким образом децентрализованной) сетями.

Предполагается, что локальные функции в каждом узле аналогичны из-за схожести статистических данных или по иным причинам. Мы устанавливаем нижние оценки сложности для довольно общего класса алгоритмов, решающих SPP. Мы показываем, что заданная субоптимальность ϵ> 0 достигается по сетям главный / рабочий в Ω (Δ⋅δ / μ⋅log (1 / ε)) раундах связи, где δ> 0 измеряет степень подобия локальных функций, μ — их константа сильной выпуклости, а Δ - диаметр сети.

Нижняя граница сложности связи для ячеистых сетей составляет Ω (1 / ρ −− √⋅δ / μ⋅log (1 / ε)), где ρ - (нормализованная) собственная щель матрицы сплетен, используемой для связи между соседними узлами. Затем мы предлагаем алгоритмы сопоставления нижних границ для любого типа сетей (с точностью до лог-факторов).

Мы оцениваем эффективность предложенных алгоритмов на проблеме робастной логистической регрессии.