Conference proceeding
A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 70, Vol.70
Proceedings of Machine Learning Research
01/01/2017
Abstract
This paper focuses on convex constrained optimization problems, where the solution is subject to a convex inequality constraint. In particular, we aim at challenging problems for which both projection into the constrained domain and a linear optimization under the inequality constraint are time-consuming, which render both projected gradient methods and conditional gradient methods (a.k.a. the Frank-Wolfe algorithm) expensive. In this paper, we develop projection reduced optimization algorithms for both smooth and non-smooth optimization with improved convergence rates under a certain regularity condition of the constraint function. We first present a general theory of optimization with only one projection. Its application to smooth optimization with only one projection yields O(1/epsilon) iteration complexity, which improves over the O(1/epsilon(2)) iteration complexity established before for nonsmooth optimization and can be further reduced under strong convexity. Then we introduce a local error bound condition and develop faster algorithms for non-strongly convex optimization at the price of a logarithmic number of projections. In particular, we achieve an iteration complexity of ((O) over tilde (1/epsilon(2(1-theta)())) for non-smooth optimization and ((O) over tilde (1/epsilon(1-theta)) for smooth optimization, where theta epsilon (0, 1] appearing the local error bound condition characterizes the functional local growth rate around the optimal solutions. Novel applications in solving the constrained l(1) minimization problem and a positive semi-definite constrained distance metric learning problem demonstrate that the proposed algorithms achieve significant speed-up compared with previous algorithms.
Details
- Title: Subtitle
- A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
- Creators
- Tianbao Yang - Univ Iowa, Iowa City, IA 52242 USAQihang Lin - University of IowaLijun Zhang - Nanjing University
- Contributors
- D Precup (Editor)Y W Teh (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 70, Vol.70
- Publisher
- JMLR-JOURNAL MACHINE LEARNING RESEARCH
- Series
- Proceedings of Machine Learning Research
- ISSN
- 2640-3498
- Number of pages
- 10
- Grant note
- IIS-1463988; IIS-1545995 / National Science Foundation; National Science Foundation (NSF) 61603177 / NSFC; National Natural Science Foundation of China (NSFC) BK20160658 / JiangsuSF
- Language
- English
- Date published
- 01/01/2017
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984380472402771
Metrics
7 Record Views