Abstract
Two characteristics that make convex decomposition algorithms attractive are simplicity of operations and generation of parallelizable structures. In principle, these schemes require that all coordinates update at the same time, i.e., they are synchronous by construction. Introducing asynchronicity in the updates can resolve several issues that appear in the synchronous case, like load imbalances in the computations or failing communication links. However, and to the best of our knowledge, there are no instances of asynchronous versions of commonly-known algorithms combined with inertial acceleration techniques. In this work we propose an inertial asynchronous and parallel fixed-point iteration from which several new versions of existing convex optimization algorithms emanate. Departing from the norm that the frequency of the coordinates' updates should comply to some prior distribution, we propose a scheme where the only requirement is that the coordinates update within a bounded interval. We prove convergence of the sequence of iterates generated by the scheme at a linear rate. One instance of the proposed scheme is implemented to solve a distributed optimization load sharing problem in a smart grid setting and its superiority with respect to the non-accelerated version is illustrated.
Introduction
In the realm of large-scale machine learning and distributed control, convex optimization problems are frequently tackled using operator splitting or decomposition methods, such as forward-backward splitting. These algorithms are naturally suited for distributing computational workloads across multiple agents or processing cores. However, traditional implementations are synchronous: the system waits for the slowest agent to complete its local computation before updating the global state. This "straggler" problem leads to significant inefficiencies in heterogeneous environments.
While asynchronous variants have been developed to mitigate these bottlenecks, they have historically lacked inertial acceleration (momentum). Momentum is a critical technique for accelerating the convergence of splitting algorithms, which otherwise often exhibit slow sublinear rates. This paper introduces a framework that successfully combines asynchronous updates with inertial acceleration, providing both theoretical guarantees and empirical evidence of its effectiveness.
Methodology: Asynchronous Inertial Iteration
The core contribution is an asynchronous, inertial Krasnosel'skiĭ-Mann (KM) fixed-point iteration. The architecture moves away from the rigid synchronization of traditional methods toward a more flexible producer-consumer model.
System Architecture
The system consists of a central coordinator and $N$ independent agents. The coordinator manages the global state of the optimization variables, while agents perform local computations.
- Asynchronous Communication: Agents pull the current global state, compute updates locally, and push results back. The coordinator updates the global state continuously as results arrive, eliminating the need to wait for a complete set of updates from all agents.
- Deterministic Bounded Delay: Unlike many asynchronous methods that rely on probabilistic update assumptions, this framework requires only that every agent contributes at least one update within a maximum time window ($\tau$). This "bounded delay" model is more robust to real-world network unpredictability.
- Inertial Acceleration: A Heavy Ball-style momentum term is integrated into the local agent updates. To maintain stability, the authors model the delayed information and momentum as an "additive error" in the fixed-point iteration.
Convergence Analysis
The authors prove that for strongly monotone operators (corresponding to strongly convex objectives), the sequence of iterates converges to the optimal solution at a linear rate. This proof holds even in the presence of outdated information, provided that step sizes and relaxation parameters are appropriately bounded.
Experimental Evaluation
The proposed algorithm was evaluated on a simulated micro-grid real-time dispatch problem. The setup involved a 500kWh Lithium Titanate battery and a variable number of commercial buildings ($N = 5$ to $50$) modeled using OpenBuild software. The system was tasked with following a realized Area Control Signal (ACS) from Swissgrid.
Key Results
The "Async Aggregated Inertial" method was compared against standard synchronous baselines over a 40-second wall-clock simulation:
- Superior Accuracy: For a 5-agent configuration, the proposed method achieved an error distance of 0.003, significantly lower than the 0.116 achieved by the synchronous baseline. Even at $N=50$, the advantage remained clear (0.448 vs. 0.824).
- Increased Throughput: By removing synchronization barriers, the asynchronous method completed significantly more updates. In the 5-agent case, it performed 1,639 updates compared to just 172 for the synchronous method, demonstrating a massive improvement in computational efficiency.
Conclusion
This work demonstrates that momentum can be successfully integrated into asynchronous distributed systems without sacrificing convergence guarantees. By replacing probabilistic assumptions with a deterministic bounded delay model, the authors provide a framework that is both theoretically sound and practically robust. Future research will explore the use of dynamic Nesterov-like momentum sequences and tighter theoretical bounds that more explicitly reflect the acceleration benefits of the inertial term.
Summary updated