Просмотр исходного текста страницы Arxiv/Distributed Saddle-Point Problems Under Similarity 2021 2107.10706

{{checked|}}
{{arxivlink|arxiv/Distributed Saddle-Point Problems Under Similarity 2021 2107.10706|
Мы изучаем методы решения (сильно) выпуклых- (сильно) вогнутых задач перевала (SPP) в сетях двух типов - с основной / рабочей (централизованной) архитектурой и ячеистой (таким образом децентрализованной) сетями.  

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

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

Мы оцениваем эффективность предложенных алгоритмов на проблеме робастной логистической регрессии.
}}
{{enddiv}}
{{reserve-task|[[Участник:ABeznosikov|ABeznosikov]] 10:31, 9 декабря 2021 (UTC)}}

[[Категория:ArxivArticles]]