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

Open

Documents

http://link.springer.com/chapter/10.1007%2F978-3-319-23528-8_40
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
Pages645-658
Number of pages14
ISBN (Electronic)978-3-319-23528-8
ISBN (Print)978-3-319-23527-1
DOIs
Publication statusPublished - 2015

Publication series

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

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.

    Research areas

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

Download statistics

No data available

ID: 21823635