pipette
ESEspañol

Beyond Finite-Sum Optimization: A Primal-Dual Method for Decentralized Finite-Max Optimization

Zhouxing Luo, Lei Wang, and Xin Liu

Preprint

In the authors' words

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 iterations. Synthetic tests and decentralized logistic regression on Fashion-MNIST illustrate convergence behavior and potential improvements in worst-agent performance.

Main resultLimitation the authors admit

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.