SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2107.10706 · NeurIPS · 2021

Distributed Saddle-Point Problems Under Similarity

Alexander Gasnikov, Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

We study solution methods for (strongly-)convex-(strongly)-concave Saddle-Point Problems (SPPs) over networks of two type-master/workers (thus centralized) architectures and mesh (thus decentralized) networks. The local functions at each node are assumed to be similar, due to statistical data similarity or otherwise. We establish lower complexity bounds for a fairly general class of algorithms solving the SPP. We show that a given suboptimality > 0 is achieved over master/workers networks in Ω ∆•δ/µ•log(1/ε) rounds of communications, where δ > 0 measures the degree of similarity of the local functions, µ is their strong convexity constant, and ∆ is the diameter of the network. The lower communication complexity bound over mesh networks reads Ω 1/ √ ρ • δ/µ • log(1/ε) , where ρ is the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes. We then propose algorithms matching the lower bounds over either types of networks (up to log-factors). We assess the effectiveness of the proposed algorithms on a robust regression problem.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2107.10706")
get_code_for_paper("2107.10706")
have("2107.10706")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2107.10706.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2107.10706.svg)](https://syntology.ai/paper/2107.10706)

Connect an agent — have() is free.