Fast and Efficient Asynchronous Gossip Algorithm for Robust and Non-Smooth Convex Decentralized Learning

Decentralized learning on resource-constrained edge devices demands algorithms that are communication-efficient, robust to data corruption, and lightweight in memory. The gist: AsylADMM is a novel asynchronous gossip algorithm for decentralized non-smooth optimization requiring only two variables per node, which converges faster than existing baselines on median and quantile estimation problems.

Problem Context and Motivation

Decentralized learning on resource-constrained edge devices demands algorithms that are communication-efficient, robust to data corruption, and lightweight in memory. State-of-the-art gossip-based methods address communication efficiency, but achieving robustness remains challenging because standard gossip methods are primarily designed for smooth losses while robust estimation typically relies on non-smooth objectives like pinball loss. Asynchronous decentralized ADMM methods handle non-smooth objectives but often require memory that scales with node degree, making them impractical when memory is limited. The paper addresses this gap by proposing AsylADMM, a novel asynchronous gossip algorithm requiring only two variables per node to achieve robustness and efficiency in non-smooth convex decentralized optimization.

Algorithm Design and Novelty

AsylADMM is proposed as a novel asynchronous gossip algorithm for non-smooth convex decentralized optimization. The key modifications compared to prior methods are: (i) using a single aggregate for the dual variables, and (ii) 'eliminating storage of neighbor values'. This simplifies primal and dual updates while reducing auxiliary variables per node. The algorithm is derived from the augmented Lagrangian:

(Lρ(x, z, y) = f(x) + y⊤(z − Mx) + ρ2∥z − Mx∥2)

The algorithm proceeds via an edge-based sampling protocol where an edge is selected with probability pe. The updates involve a consensus step, a dual update, and a primal update. A notable advantage is the simplicity of the update rules, which require only one communication step and reduce storage. For example, in Algorithm 2 (AsylADMM), agents in an edge perform:

(µˆk ← µˆk + ρ(ze − xk)/dk; xk ← prox fk/ρdk(ze + ˆµk/ρ))

Theoretical Analysis and Convergence

The paper provides two novel theoretical results. First, it presents a new convergence analysis for the synchronous variant using a modified Lyapunov function, which leads to Theorem 3.3 proving that the residual norm converges to zero and the objective value approaches the optimal value. Second, it offers a simplified convergence analysis for AsylADMM based on the squared loss (mean estimation) for step size ρ ≤ 1. In this simplified setting, it proves that in the special case ρ = 1, our algorithm recovers classical pairwise averaging, establishing a clear link to a well-studied gossip algorithm.

Empirical Validation and Performance

AsylADMM's performance is validated through extensive experiments across diverse network topologies and data distributions. The paper demonstrates that AsylADMM converges faster than competing methods on median and quantile estimation problems. Specifically:

1. On median estimation (Figure 1a), AsylADMM outperforms SubGD, DAPD, and AsyncADMM, showing better stability.

2. On quantile estimation (Figure 1b), AsylADMM remains consistently stable and competitive compared to the higher variability of DAPD and AsyncADMM.

3. The algorithm extends naturally to other challenging non-smooth problems such as geometric median, lasso regression and robust regression (via least trimmed squares).

4. Empirical results confirm that choosing ρ > 1 can substantially accelerate convergence in geometric graphs for mean estimation.

Generalization to Robust Problems

The framework is shown to be versatile across various non-smooth problems. For instance, the application to Lasso regression (Figure 2b) demonstrates that AsylADMM outperforms DAPD while remaining memory efficient. Furthermore, in robust regression using Least Trimmed Squares (LTS), the algorithm maintains a running estimate of the (1−α)-quantile of the residuals across the network using AsylADMM to discard nodes with large residuals, showing it is significantly more robust to outliers than standard decentralized OLS. The paper concludes that reporting Mean Absolute Error (MAE) is a faithful proxy for the full optimality gap in these experiments.

Conclusion and Future Directions

AsylADMM offers significant advantages over existing methods by achieving memory efficiency, fast convergence, and robustness across non-smooth convex optimization tasks. The work establishes a practical pathway toward robust decentralized learning by providing theoretical insights into the asynchronous case and demonstrating its efficacy on complex estimation problems like geometric median and trimmed means. Future work is suggested to include a comprehensive convergence analysis for the general setting and extensions to non-convex objectives. It also investigates advanced trimming rules, including quantile-based trimming which significantly outperforms rank-based trimming in many scenarios.

As a fastidious researcher, I have analyzed this paper, Fast and Efficient Gossip Algorithms for Robust and Non-smooth Decentralized Learning. The core contribution is AsylADMM, a memory-efficient asynchronous gossip algorithm designed to handle non-smooth convex decentralized optimization problems (like median and quantile estimation) robustly.

Based on the findings in the paper, here are specific improvements we can implement in AI systems:

) Improved AI System Capabilities: Robust, Communication-Efficient Decentralized Learning Agents.

The improved system will be an ensemble of distributed agents capable of performing complex statistical inference and optimization tasks directly on resource-constrained edge devices without requiring centralized coordination or massive memory overhead. Specifically, the system can achieve the following:

1. [Robust Estimation for Quantile/Median Inference]: The system can accurately estimate robust statistics (like geometric median or quantiles) from noisy, contaminated sensor data (e.g., from wireless sensor networks).

2. [Outlier-Resistant Regression]: The system can perform decentralized regression tasks like Lasso or Trimmed Least Squares (LTS) to identify and mitigate the influence of adversarial outliers in real-time data streams, leading to more reliable parameter estimation than standard Ordinary Least Squares (OLS).

3. [Memory-Efficient Edge Deployment]: The agents will operate on devices with severe memory limitations by utilizing AsylADMM, which requires only two variables per node instead of the degree-dependent storage required by prior decentralized ADMM methods. This allows for deployment in IoT and edge AI scenarios where memory is a critical constraint.

4. [Adaptive Robust Trimming]: The system can implement adaptive trimming rules (using quantile estimation) to exclude data points that fall into the tails of the distribution, outperforming simple rank-based trimming, especially when dealing with high contamination levels or complex graph structures (e.g., geometric graphs).

5. [Convergence Acceleration via Step-Size Tuning]: The system can dynamically adjust its step size (e.g., using AsylADMM's empirical findings that a step size of 2 can accelerate convergence on mean estimation) to reach the optimal solution faster, balancing speed and accuracy for different tasks like mean estimation versus quantile estimation.

6. [Topology-Aware Performance]: The system's performance can be optimized based on the underlying network topology (e.g., geometric graphs vs. cycle graphs), allowing it to leverage specific communication patterns to maximize convergence speed in heterogeneous edge environments.

Asynchronous primal-dual methods for decentralized non-smooth convex optimization often require each node to maintain O(d) auxiliary variables, where d is its degree. This dependence on degree increases memory requirements and can amplify the effects of stale information, especially in dense networks. Motivated by the challenge of frugal memory management in decentralized learning, we introduce Goal-PD, an asynchronous gossip-based primal-dual algorithm that maintains only two variables per node, regardless of the node's degree. We establish almost-sure convergence of Goal-PD to a minimizer of the underlying optimization problem, and prove linear convergence when the objective functions are piecewise linear-quadratic. For decentralized mean estimation, we show that pairwise averaging is a special case of Goal-PD, which establishes a direct link between the proposed primal-dual framework and classical gossip. Experiments on synthetic and real datasets over various network topologies, with non-smooth objectives including median estimation, show that Goal-PD converges faster than existing asynchronous baselines while requiring significantly less memory by design.