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

Zhanxing Zhu, Amos Storkey

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationEuropean Conference, ECML PKDD 2015, Porto, Portugal, September 7-11, 2015, Proceedings, Part I
EditorsAnnalisa Appice, Pedro Pereira Rodrigues, Vítor Santos Costa, Carlos Soares, João Gama, Alípio Jorge
PublisherSpringer International Publishing
Number of pages14
ISBN (Electronic)978-3-319-23528-8
ISBN (Print)978-3-319-23527-1
Publication statusPublished - 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
ISSN (Print)0302-9743

Keywords / Materials (for Non-textual outputs)

  • Large-scale optimization
  • Parallel optimization
  • Stochastic coordinate descent
  • Convex-concave saddle point problems


Dive into the research topics of 'Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems'. Together they form a unique fingerprint.

Cite this