提出可异步更新的分布式优化算法，提升通信效率与鲁棒性。
Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization
- 采用多时标外推与Bregman散度混合策略，支持不同模块任意更新速率。
- 在异构目标与通信成本下，实现线性收敛，依赖梯度相似性最优。
- 适合大规模分布式系统，尤其通信延迟严重或节点能力不均的场景。
针对具有块可分对偶的鞍点问题，我们提出两种变体：多时标原始对偶杂交梯度（MT-PDHG）及其加速版本（AMT-PDHG）。通过新颖的Bregman散度与多时标外推结合，算法在任意不同对偶块更新速率下仍保持收敛，且完全确定、对极端延迟鲁棒。进一步将（A）MT-PDHG与Lan等（2020）、Lan（2016）提出的梯度滑动技术结合，应用于分布式优化。不同块可独立设定更新速率，实现对代理间通信轮次的精细控制，显著提升异构局部目标与通信成本下的效率。此外，通过合理设置惩罚水平，算法对函数相似性呈现线性依赖，即最优依赖，回答了非光滑目标是否可达此性质的开放问题（Arjevani and Shamir, 2015）。
原文摘要 · Abstract (English)
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).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。