Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization

Tianbao Yang; Qihang Lin

doi:10.48550/arxiv.1510.01444

Back

Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization

Preprint

Open access

Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization

Tianbao Yang and Qihang Lin

ArXiv.org

10/06/2015

DOI: 10.48550/arxiv.1510.01444

Files and links (1)

url

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

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

In this paper, we show that simple {Stochastic} subGradient Decent methods with multiple Restarting, named {\bf RSGD}, can achieve a \textit{linear convergence rate} for a class of non-smooth and non-strongly convex optimization problems where the epigraph of the objective function is a polyhedron, to which we refer as {\bf polyhedral convex optimization}. Its applications in machine learning include $\ell_1$ constrained or regularized piecewise linear loss minimization and submodular function minimization. To the best of our knowledge, this is the first result on the linear convergence rate of stochastic subgradient methods for non-smooth and non-strongly convex optimization problems.

Details

Title: Subtitle: Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization
Creators: Tianbao Yang
Qihang Lin
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.1510.01444
ISSN: 2331-8422
Language: English
Date posted: 10/06/2015
Academic Unit: Business Analytics; Computer Science
Record Identifier: 9984380603902771

Metrics

5 Record Views