An Efficient Primal-Dual Prox Method for Non-Smooth Optimization
Preprint
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 $O(1/T)$ {assuming that the proximal step can be efficiently solved}, significantly faster than a standard subgradient descent method that has an $O(1/\sqrt{T})$ convergence rate. Our empirical study verifies 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.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- A smoothing stochastic gradient method for composite optimizationOptimization Methods and Software, 2014
- Primal-Dual Splitting Algorithm for Solving Inclusions with Mixtures of Composite, Lipschitzian, and Parallel-Sum Type Monotone OperatorsSet-Valued and Variational Analysis, 2011
- A First-Order Primal-Dual Algorithm for Convex Problems with Applications to ImagingJournal of Mathematical Imaging and Vision, 2010
- NESVM: A Fast Gradient Method for Support Vector Machines2010
- Pegasos: primal estimated sub-gradient solver for SVMMathematical Programming, 2010
- Accelerated Gradient Method for Multi-task Sparse Learning Problem2009
- A forward–backward splitting algorithm for the minimization of non-smooth convex functionals in Banach spaceInverse Problems, 2008
- Smooth minimization of non-smooth functionsMathematical Programming, 2004
- A Feature Selection Newton Method for Support Vector Machine ClassificationComputational Optimization and Applications, 2004
- A modification of the Arrow-Hurwicz method for search of saddle pointsMathematical Notes, 1980