Arxiv/Distributed Saddle-Point Problems Under Similarity 2021 2107.10706 — различия между версиями
StasFomin (обсуждение | вклад) |
|||
| Строка 10: | Строка 10: | ||
}} | }} | ||
{{enddiv}} | {{enddiv}} | ||
| − | |||
[[Категория:ArxivArticles]] | [[Категория:ArxivArticles]] | ||
Текущая версия на 06:37, 17 марта 2022
Мы изучаем методы решения (сильно) выпуклых- (сильно) вогнутых задач перевала (SPP) в сетях двух типов - с основной / рабочей (централизованной) архитектурой и ячеистой (таким образом децентрализованной) сетями.
Предполагается, что локальные функции в каждом узле аналогичны из-за схожести статистических данных или по иным причинам. Мы устанавливаем нижние оценки сложности для довольно общего класса алгоритмов, решающих SPP. Мы показываем, что заданная субоптимальность ϵ> 0 достигается по сетям главный / рабочий в Ω (Δ⋅δ / μ⋅log (1 / ε)) раундах связи, где δ> 0 измеряет степень подобия локальных функций, μ — их константа сильной выпуклости, а Δ - диаметр сети.
Нижняя граница сложности связи для ячеистых сетей составляет Ω (1 / ρ −− √⋅δ / μ⋅log (1 / ε)), где ρ - (нормализованная) собственная щель матрицы сплетен, используемой для связи между соседними узлами. Затем мы предлагаем алгоритмы сопоставления нижних границ для любого типа сетей (с точностью до лог-факторов).
Мы оцениваем эффективность предложенных алгоритмов на проблеме робастной логистической регрессии.
…»