2024/09/28 by Kushal Chakrabarti, Mayank Baranwal, Baranwal, Mayank +1 · 1 citation
Computer Science · #Neural Networks and Applications #cs.AI #cs.LG #cs.SY #eess.SY #math.DS #math.OC
paper · pdf · doi:10.48550/arxiv.2409.19279
openalex publication_date 2024/09/28 · openalex created_date 2024/10/28 · openalex updated_date 2026/07/28
Continuous-time models can reveal accelerated structures in distributed optimization, but their rates need not survive direct discretization. We introduce a second-order primal--dual flow for smooth convex distributed optimization and construct an exactly conserved energy that yields an \mathcal O(t-2) rate for both the aggregate objective gap and the squared consensus error. We then prove a horizon-wise Ω(k-1) lower bound for a broad class of single-loop finite-memory primal--dual discretizations, ruling out a \mathcal O(k-2) aggregate-objective guarantee within this class. Motivated by this barrier, we develop a double-loop method that combines finite-step polynomial consensus with an accelerated outer update. It uses one gradient evaluation and at most m-1 communication rounds per outer iteration, m being the number of agents, maintains exact consensus and achieves an \mathcal O(k-2) aggregate-objective rate. Numerical comparisons with representative distributed methods support the theory and quantify the communication cost of acceleration.