# Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization

arXiv: https://arxiv.org/abs/2506.15387 · HTML: https://mlsanity.com/paper/2506.15387/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 57 references that are in the map.
- First posted on arXiv 18 Jun 2025.

## Builds on (most cited first, 30 of 30)

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [Advances in Asynchronous Parallel and Distributed Optimization](https://mlsanity.com/paper/2006.13838/) (2020)
- [Energy-Efficient Resource Management for Federated Edge Learning with CPU-GPU Heterogeneous Computing](https://mlsanity.com/paper/2007.07122/) (2020)
- [Importance Sampling for Minibatches](https://mlsanity.com/paper/1602.02283/) (2016)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017)
- [Balancing Communication and Computation in Distributed Optimization](https://mlsanity.com/paper/1709.02999/) (2017)
- [Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties](https://mlsanity.com/paper/1403.3862/) (2014)
- [ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates](https://mlsanity.com/paper/1506.02396/) (2015)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Gradient Sliding for Composite Optimization](https://mlsanity.com/paper/1406.0919/) (2014)
- [Asynchronous Coordinate Descent under More Realistic Assumptions](https://mlsanity.com/paper/1705.08494/) (2017)
- [Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization](https://mlsanity.com/paper/1512.08122/) (2015)
- [Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness](https://mlsanity.com/paper/2105.12715/) (2021)
- [On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1307.8254/) (2013)
- [The Communication Complexity of Optimization](https://mlsanity.com/paper/1906.05832/) (2019)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)
- [On the convergence of stochastic primal-dual hybrid gradient](https://mlsanity.com/paper/1911.00799/) (2019)
- [On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization](https://mlsanity.com/paper/2405.16218/) (2024)
- [Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters](https://mlsanity.com/paper/1602.02151/) (2016)

## Abstract (arXiv)

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. We further apply our (A)MT-PDHG, augmented with the gradient sliding techniques introduced in Lan et al. (2020), Lan (2016), to distributed optimization. The flexibility in choosing different updating rates for different blocks allows a more refined control over the communication rounds between different pairs of agents, thereby improving the efficiencies in settings with heterogeneity in local objectives and communication costs. Moreover, with careful choices of penalty levels, our algorithms show linear and thus optimal dependency on function similarities, a measure of how similar the gradients of local objectives are. This provides a positive answer to the open question whether such dependency is achievable for non-smooth objectives (Arjevani and Shamir 2015).