A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates
This work addresses optimization efficiency for problems in machine learning and operations research, representing an incremental improvement with specific convergence guarantees.
The paper tackles nonsmooth constrained convex optimization by developing a randomized block-coordinate primal-dual algorithm, achieving optimal O(n/k) and O(n^2/k^2) convergence rates for general and strong convexity cases, respectively, with rates proven on the last iterate sequence.
We develop a novel unified randomized block-coordinate primal-dual algorithm to solve a class of nonsmooth constrained convex optimization problems, which covers different existing variants and model settings from the literature. We prove that our algorithm achieves optimal $\mathcal{O}(n/k)$ and $\mathcal{O}(n^2/k^2)$ convergence rates (up to a constant factor) in two cases: general convexity and strong convexity, respectively, where $k$ is the iteration counter and n is the number of block-coordinates. Our convergence rates are obtained through three criteria: primal objective residual and primal feasibility violation, dual objective residual, and primal-dual expected gap. Moreover, our rates for the primal problem are on the last iterate sequence. Our dual convergence guarantee requires additionally a Lipschitz continuity assumption. We specify our algorithm to handle two important special cases, where our rates are still applied. Finally, we verify our algorithm on two well-studied numerical examples and compare it with two existing methods. Our results show that the proposed method has encouraging performance on different experiments.