Beyond Finite-Sum Optimization: A Primal-Dual Method for Decentralized Finite-Max Optimization
Abstract
Many decentralized systems are judged by their worst-performing agents rather than their average performance. We study finite-max optimization over a connected undirected network, where each agent knows only its own smooth, possibly nonconvex objective. Quadratic regularization yields a smooth finite-sum representation with a scalar dual variable and locally computable clipped weights. We develop an alternating primal-dual gradient tracking (APDGT) method, using neighbor communication without any global or centralized projections. Under smoothness and level-boundedness assumptions, a localized Lyapunov analysis with vanishing regularization establishes bounded primal iterates and Clarke stationarity of every accumulation point of their network average. The averaged sequence contains an ε-stationary point, measured by near-active gradients, within O (ε−3) iterations. Synthetic tests and decentralized logistic regression on Fashion-MNIST illustrate convergence behavior and potential improvements in worst-agent performance.
Related
- DOFFO_TR: a Decentralized Objective Function-Free Optimization method with Trust-Region
- Sampled-Max Subgradient Method for Convex Finite-Max Optimization
- Primal/Dual Method for the Grothendieck Constant
- A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
- On the Regularization of Primal-Dual Dynamics in Time-Dependent Nonconvex Optimization
BibTeX
@misc{luo2026beyond,
title = {{Beyond Finite-Sum Optimization: A Primal-Dual Method for Decentralized Finite-Max Optimization}},
author = {Zhouxing Luo and Lei Wang and Xin Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26555},
eprint = {2610.26555},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26555},
}
RIS
TY - UNPB
TI - Beyond Finite-Sum Optimization: A Primal-Dual Method for Decentralized Finite-Max Optimization
AU - Zhouxing Luo
AU - Lei Wang
AU - Xin Liu
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26555
UR - https://arxiv.org/abs/2610.26555
AB - Many decentralized systems are judged by their worst-performing agents rather than their average performance. We study finite-max optimization over a connected undirected network, where each agent knows only its own smooth, possibly nonconvex objective. Quadratic regularization yields a smooth finite-sum representation with a scalar dual variable and locally computable clipped weights. We develop an alternating primal-dual gradient tracking (APDGT) method, using neighbor communication without any global or centralized projections. Under smoothness and level-boundedness assumptions, a localized Lyapunov analysis with vanishing regularization establishes bounded primal iterates and Clarke stationarity of every accumulation point of their network average. The averaged sequence contains an ε-stationary point, measured by near-active gradients, within O (ε^−3) iterations. Synthetic tests and decentralized logistic regression on Fashion-MNIST illustrate convergence behavior and potential improvements in worst-agent performance.
ER -