# Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2015.

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

- [Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems](https://mlsanity.com/paper/2209.04604/) (2022)

## Abstract (arXiv)

We consider a generic convex-concave saddle point problem with separable structure, a form that covers a wide-ranged machine learning applications. Under this problem structure, we follow the framework of primal-dual updates for saddle point problems, and incorporate stochastic block coordinate descent with adaptive stepsize into this framework. We theoretically show that our proposal of adaptive stepsize potentially achieves a sharper linear convergence rate compared with the existing methods. Additionally, since we can select "mini-batch" of block coordinates to update, our method is also amenable to parallel processing for large-scale data. We apply the proposed method to regularized empirical risk minimization and show that it performs comparably or, more often, better than state-of-the-art methods on both synthetic and real-world data sets.