Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems
Abstract
We consider a generic convex-concave saddle point problem with a 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 stepsizes into this framework. We theoretically show that our proposal of adaptive stepsizes 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.
Cite
Text
Zhu and Storkey. "Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2015. doi:10.1007/978-3-319-23528-8_40Markdown
[Zhu and Storkey. "Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2015.](https://mlanthology.org/ecmlpkdd/2015/zhu2015ecmlpkdd-adaptive/) doi:10.1007/978-3-319-23528-8_40BibTeX
@inproceedings{zhu2015ecmlpkdd-adaptive,
title = {{Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems}},
author = {Zhu, Zhanxing and Storkey, Amos J.},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2015},
pages = {645-658},
doi = {10.1007/978-3-319-23528-8_40},
url = {https://mlanthology.org/ecmlpkdd/2015/zhu2015ecmlpkdd-adaptive/}
}