Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem

Adams Wei Yu; Qihang Lin; Tianbao Yang

doi:10.48550/arxiv.1508.03390

Back

Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem

Preprint

Open access

Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem

Adams Wei Yu, Qihang Lin and Tianbao Yang

ArXiv.org

08/13/2015

DOI: 10.48550/arxiv.1508.03390

Files and links (1)

url

https://doi.org/10.48550/arxiv.1508.03390View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

We propose a doubly stochastic primal-dual coordinate optimization algorithm for empirical risk minimization, which can be formulated as a bilinear saddle-point problem. In each iteration, our method randomly samples a block of coordinates of the primal and dual solutions to update. The linear convergence of our method could be established in terms of 1) the distance from the current iterate to the optimal solution and 2) the primal-dual objective gap. We show that the proposed method has a lower overall complexity than existing coordinate methods when either the data matrix has a factorized structure or the proximal mapping on each block is computationally expensive, e.g., involving an eigenvalue decomposition. The efficiency of the proposed method is confirmed by empirical studies on several real applications, such as the multi-task large margin nearest neighbor problem.

Details

Title: Subtitle: Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem
Creators: Adams Wei Yu
Qihang Lin
Tianbao Yang
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.1508.03390
ISSN: 2331-8422
Language: English
Date posted: 08/13/2015
Academic Unit: Business Analytics; Computer Science
Record Identifier: 9984380579102771

Metrics

8 Record Views