Technical Summary: Fast and Efficient Gossip Algorithms for Robust and Non-smooth Decentralized Learning

1. Problem Formulation

The paper addresses the challenge of decentralized learning on resource-constrained edge devices. In this setting, $n$ agents connected via a network $G=(V, E)$ collaboratively solve a minimization problem of the form:
$$\arg\min_{x \in \mathbb{R}^d} \sum_{i=1}^n f_i(x)$$
where each local objective $f_i$ is closed, proper, convex, and potentially non-smooth.

The specific motivation arises from the need for robustness against data corruption (e.g., outliers or faulty sensors). Robust statistics such as the median, quantiles, and geometric median are effective against corruption but require minimizing non-smooth loss functions (e.g., the pinball loss for quantiles). While standard gossip algorithms are communication-efficient, they are primarily designed for smooth losses. Existing methods for non-smooth objectives, such as asynchronous ADMM-based approaches (e.g., AsyncADMM, DAPD), typically require storing auxiliary variables that scale with the node degree ($d_k$). Specifically, prior methods require $2d_k + 1$ variables per node, which becomes impractical for dense graphs or devices with limited memory.

2. Methodology: AsylADMM

The authors propose AsylADMM (Asynchronous and Lite ADMM), a novel gossip algorithm designed to handle non-smooth convex decentralized optimization with minimal memory overhead.

Core Design Principles

1. Memory Efficiency: Unlike prior asynchronous ADMM methods that store edge-specific dual variables and neighbor states, AsylADMM requires each node to store only two variables:

   • The primal variable $x_k$.
   • A single aggregated dual variable $\hat{\mu}_k$.
     This reduces the memory footprint from $O(d_k)$ to $O(1)$, independent of the node degree.

2. Algorithmic Structure:

   • Reparameterization: The algorithm reformulates the standard ADMM updates by aggregating dual variables. Instead of maintaining individual dual variables for every incident edge, nodes maintain a single aggregate $\hat{\mu}_k = \sum_{e \in N_k} y_{e,k} / d_k$.
   • Heuristic Updates: In the asynchronous setting, when an edge $e=(i, j)$ is activated:
     • The nodes compute a fresh pairwise average $z_e = (x_i + x_j)/2$.
     • They update their local dual aggregates using the current edge constraint: $\hat{\mu}_k \leftarrow \hat{\mu}_k + \rho(z_e - x_k)/d_k$.
     • They perform a proximal update: $x_k \leftarrow \text{prox}_{f_k/(\rho d_k)}(z_e + \hat{\mu}_k/\rho)$.
   • Key Distinction: The algorithm uses the current information from both endpoints of the activated edge for the primal update, rather than relying on outdated neighbor averages stored in auxiliary states.

3. Synchronous Variant: The authors also define a synchronous version of the algorithm where all nodes update simultaneously, serving as a theoretical baseline.

3. Theoretical Contributions

The paper provides two primary theoretical results:

1. Convergence of the Synchronous Variant:

   • The authors establish a new convergence analysis for the synchronous version of their reordered ADMM variant (updating $z \to y \to x$).
   • Using a modified Lyapunov function $V^t = \|\tilde{y}^t - \rho M \tilde{x}^t\|^2$, they prove that the primal residual converges to zero ($\|r^t\| \to 0$) and the objective value converges to the optimal value ($f(x^t) \to f(x^*)$).

2. Simplified Analysis for AsylADMM:

   • A full convergence proof for the asynchronous non-smooth case is noted as non-trivial due to the non-linearity of proximal operators and the use of heuristics.
   • Instead, the authors provide a convergence analysis for a simplified setting using the squared loss (mean estimation) with step size $\rho \le 1$.
   • They prove that for $\rho \le 1$, the algorithm converges almost surely.
   • Special Case ($\rho = 1$): They demonstrate that when $\rho = 1$, AsylADMM exactly recovers the classical pairwise averaging gossip algorithm, establishing a formal link to well-studied consensus protocols.

4. Empirical Results

Extensive experiments were conducted on various non-smooth problems, including median estimation, quantile estimation, geometric median, Lasso regression, and robust regression (Least Trimmed Squares).

• Performance: AsylADMM consistently converges faster than existing baselines (AsyncADMM, DAPD, and Subgradient Descent) across diverse network topologies (Geometric, Watts-Strogatz, Cycle) and data distributions (including contaminated Gaussian data).
• Stability: The proposed method exhibits lower variance across trials compared to baselines, which often struggle with the trade-off between using outdated information and memory constraints.
• Memory Efficiency: The algorithm maintains high performance while storing only two variables per node, validating its suitability for resource-constrained environments.
• Step Size Sensitivity: Empirical results suggest that for mean estimation on geometric graphs, choosing $\rho > 1$ (specifically $\rho = 2$) can significantly accelerate convergence, although the theoretical guarantee provided is for $\rho \le 1$.
• Robustness: In robust regression tasks (Least Trimmed Squares), AsylADMM effectively identifies and trims outliers, outperforming standard OLS and Huber regression in terms of final parameter error.

5. Significance and Claims

The paper claims that AsylADMM opens a practical pathway toward robust and non-smooth decentralized learning. Its primary significance lies in:

• Bridging the Gap: It successfully combines the robustness of non-smooth optimization (via proximal methods) with the communication efficiency of gossip algorithms, without the prohibitive memory costs of previous asynchronous ADMM approaches.
• Scalability: By reducing memory requirements to a constant per node, it enables the deployment of robust learning algorithms on large-scale, dense networks of edge devices where prior methods were impractical.
• Theoretical Foundation: It provides the first convergence analysis for a synchronous variant of this specific reordered ADMM structure and offers theoretical insights into the asynchronous case via the squared loss reduction.

The authors note that while the empirical results are strong, a complete theoretical convergence analysis for the general non-smooth asynchronous case remains an open problem for future work.