Journal article
An efficient primal dual prox method for non-smooth optimization
Machine learning, Vol.98(3), pp.369-406
03/01/2015
DOI: 10.1007/s10994-014-5436-1
Abstract
We study the non-smooth optimization problems in machine learning, where both the loss function and the regularizer are non-smooth functions. Previous studies on efficient empirical loss minimization assume either a smooth loss function or a strongly convex regularizer, making them unsuitable for non-smooth optimization. We develop a simple yet efficient method for a family of non-smooth optimization problems where the dual form of the loss function is bilinear in primal and dual variables. We cast a non-smooth optimization problem into a minimax optimization problem, and develop a primal dual prox method that solves the minimax optimization problem at a rate of assuming that the proximal step can be efficiently solved, significantly faster than a standard subgradient descent method that has an convergence rate. Our empirical studies verify the efficiency of the proposed method for various non-smooth optimization problems that arise ubiquitously in machine learning by comparing it to the state-of-the-art first order methods.
Details
- Title: Subtitle
- An efficient primal dual prox method for non-smooth optimization
- Creators
- Tianbao Yang - NECMehrdad Mahdavi - Michigan State UniversityRong Jin - Michigan State UniversityShenghuo Zhu - NEC
- Resource Type
- Journal article
- Publication Details
- Machine learning, Vol.98(3), pp.369-406
- Publisher
- Springer Nature
- DOI
- 10.1007/s10994-014-5436-1
- ISSN
- 0885-6125
- eISSN
- 1573-0565
- Number of pages
- 38
- Language
- English
- Date published
- 03/01/2015
- Academic Unit
- Computer Science
- Record Identifier
- 9984259433202771
Metrics
2 Record Views