# Randomized Primal-Dual Methods with Adaptive Step Sizes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2018.

## Built on by (most cited first, 2 of 2)

- [A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2312.02277/) (2023)
- [Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization](https://mlsanity.com/paper/2505.21944/) (2025)

## Abstract (arXiv)

In this paper we propose a class of randomized primal-dual methods to contend with large-scale saddle point problems defined by a convex-concave function L(x,y)triangleqsumi=1m fi(xi)+Phi(x,y)-h(y). We analyze the convergence rate of the proposed method under mere convexity and strong convexity assumptions of L in x-variable. In particular, assuming nablayPhi(·,·) is Lipschitz and nablaxPhi(·,y) is coordinate-wise Lipschitz for any fixed y, the ergodic sequence generated by the algorithm achieves the convergence rate of O(M/k) in the expected primal-dual gap. Furthermore, assuming that L(·,y) is strongly convex for any y, and that Phi(x,·) is affine for any x, the scheme enjoys a faster rate of O(M/k2) in terms of primal solution suboptimality. We implemented the proposed algorithmic framework to solve kernel matrix learning problem, and tested it against other state-of-the-art first-order methods