Journal article
A FIRST-ORDER SMOOTHING TECHNIQUE FOR A CLASS OF LARGE-SCALE LINEAR PROGRAMS
SIAM journal on optimization, Vol.24(2), pp.598-620
01/01/2014
DOI: 10.1137/110854400
Abstract
We study a class of linear programming (LP) problems motivated by large-scale machine learning applications. After reformulating the LP as a convex nonsmooth problem, we apply Nesterov's primal-dual excessive-gap technique. The iteration complexity of the excessive-gap technique depends on a parameter theta that arises because we must bound the primal feasible set, which is originally unbounded. We also dynamically update theta to speed up the convergence. The application of our algorithm to two machine learning problems demonstrates several advantages of the excessive-gap technique over existing methods.
Details
- Title: Subtitle
- A FIRST-ORDER SMOOTHING TECHNIQUE FOR A CLASS OF LARGE-SCALE LINEAR PROGRAMS
- Creators
- Jieqiu Chen - Argonne National LaboratorySamuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.24(2), pp.598-620
- Publisher
- Siam Publications
- DOI
- 10.1137/110854400
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Number of pages
- 23
- Grant note
- DE-AC02-06CH11357 / U.S. Department of Energy; United States Department of Energy (DOE) DE-AC02-06CH11357 / Office of Advanced Scientific Computing Research, Office of Science, U.S. Department of Energy; United States Department of Energy (DOE) CCF-0545514 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2014
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380377902771
Metrics
2 Record Views