Edinburgh Research Explorer

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

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

Related Edinburgh Organisations

Open Access permissions



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


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.

    Research areas

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

Download statistics

No data available

ID: 21823635