Conference proceeding
ADMM without a Fixed Penalty Parameter: Faster Convergence with New Adaptive Penalization
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 30 (NIPS 2017), Vol.30
Advances in Neural Information Processing Systems
01/01/2017
Abstract
Alternating direction method of multipliers (ADMM) has received tremendous interest for solving numerous problems in machine learning, statistics and signal processing. However, it is known that the performance of ADMM and many of its variants is very sensitive to the penalty parameter of a quadratic penalty applied to the equality constraints. Although several approaches have been proposed for dynamically changing this parameter during the course of optimization, they do not yield theoretical improvement in the convergence rate and are not directly applicable to stochastic ADMM. In this paper, we develop a new ADMM and its linearized variant with a new adaptive scheme to update the penalty parameter. Our methods can be applied under both deterministic and stochastic optimization settings for structured non-smooth objective function. The novelty of the proposed scheme lies at that it is adaptive to a local sharpness property of the objective function, which marks the key difference from previous adaptive scheme that adjusts the penalty parameter per-iteration based on certain conditions on iterates. On theoretical side, given the local sharpness characterized by an exponent theta is an element of (0; 1], we show that the proposed ADMM enjoys an improved iteration complexity of (O) over tilde (1/epsilon(1-theta))(1) in the deterministic setting and an iteration complexity of (O) over tilde (1/epsilon(2(1-theta))) in the stochastic setting without smoothness and strong convexity assumptions. The complexity in either setting improves that of the standard ADMM which only uses a fixed penalty parameter. On the practical side, we demonstrate that the proposed algorithms converge comparably to, if not much faster than, ADMM with a fine-tuned fixed penalty parameter.
Details
- Title: Subtitle
- ADMM without a Fixed Penalty Parameter: Faster Convergence with New Adaptive Penalization
- Creators
- Yi Xu - University of IowaMingrui Liu - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USAQihang Lin - Univ Iowa, Dept Management Sci, Iowa City, IA 52242 USATianbao Yang - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA
- Contributors
- I Guyon (Editor)U V Luxburg (Editor)S Bengio (Editor)H Wallach (Editor)R Fergus (Editor)S Vishwanathan (Editor)R Garnett (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 30 (NIPS 2017), Vol.30
- Publisher
- Neural Information Processing Systems (Nips)
- Series
- Advances in Neural Information Processing Systems
- ISSN
- 1049-5258
- Number of pages
- 11
- Grant note
- IIS-1463988; IIS-1545995 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2017
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984380435902771
Metrics
5 Record Views