Conference proceeding
Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/epsilon)
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 29 (NIPS 2016), Vol.29
Advances in Neural Information Processing Systems
01/01/2016
Abstract
In this paper, we develop a novel homotopy smoothing (HOPS) algorithm for solving a family of non-smooth problems that is composed of a non-smooth term with an explicit max-structure and a smooth term or a simple non-smooth term whose proximal mapping is easy to compute. The best known iteration complexity for solving such non-smooth optimization problems is O(1/epsilon) without any assumption on the strong convexity. In this work, we will show that the proposed HOPS achieved a lower iteration complexity of (O) over tilde (1/epsilon(1-theta)) with theta is an element of (0, 1] capturing the local sharpness of the objective function around the optimal solutions. To the best of our knowledge, this is the lowest iteration complexity achieved so far for the considered non-smooth optimization problems without strong convexity assumption. The HOPS algorithm employs Nesterov's smoothing technique and Nesterov's accelerated gradient method and runs in stages, which gradually decreases the smoothing parameter in a stage-wise manner until it yields a sufficiently good approximation of the original function. We show that HOPS enjoys a linear convergence for many well-known non-smooth problems (e.g., empirical risk minimization with a piece-wise linear loss function and l(1) norm regularizer, finding a point in a polyhedron, cone programming, etc). Experimental results verify the effectiveness of HOPS in comparison with Nesterov's smoothing algorithm and the primal-dual style of first-order methods.
Details
- Title: Subtitle
- Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/epsilon)
- Creators
- Yi Xu - University of IowaYan Yan - University of Technology SydneyQihang Lin - Univ Iowa, Dept Management Sci, Iowa City, IA 52242 USATianbao Yang - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA
- Contributors
- D D Lee (Editor)M Sugiyama (Editor)U V Luxburg (Editor)I Guyon (Editor)R Garnett (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 29 (NIPS 2016), Vol.29
- Publisher
- Neural Information Processing Systems (Nips)
- Series
- Advances in Neural Information Processing Systems
- ISSN
- 1049-5258
- Number of pages
- 9
- Grant note
- IIS-1463988; IIS-1545995 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2016
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984380613102771
Metrics
5 Record Views