AI RESEARCH
Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization
arXiv CS.LG
•
ArXi:2506.15387v2 Announce Type: replace-cross We propose two variants of the Primal Dual Hybrid Gradient (PDHG) algorithm for saddle point problems with block decomposable duals, hereafter called Multi-Timescale PDHG (MT-PDHG) and its accelerated variant (AMT-PDHG). Through novel mixtures of Bregman divergence and multi-timescale extrapolations, our MT-PDHG and AMT-PDHG converge under arbitrary updating rates for different dual blocks while remaining fully deterministic and robust to extreme delays in dual updates.