Abstract
In this paper, we design and analyze a new zeroth-order online algorithm, namely, the zeroth-order online alternating direction method of multipliers (ZOO-ADMM), which enjoys dual advantages of being gradient-free operation and employing the ADMM to accommodate complex structured regularizers. Compared to the first-order gradient-based online algorithm, we show that ZOO-ADMM requires √m times more iterations, leading to a convergence rate of O(√m/√T), where m is the number of optimization variables, and T is the number of iterations. To accelerate ZOO-ADMM, we propose two minibatch strategies: gradient sample averaging and observation averaging, resulting in an improved convergence rate of O(√1 + q−1m/√T), where q is the minibatch size. In addition to convergence analysis, we also demonstrate ZOO-ADMM to applications in signal processing, statistics, and machine learning.
| Original language | English |
|---|---|
| Pages | 288-297 |
| Number of pages | 10 |
| State | Published - 2018 |
| Event | 21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018 - Playa Blanca, Lanzarote, Canary Islands, Spain Duration: 9 Apr 2018 → 11 Apr 2018 |
Conference
| Conference | 21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018 |
|---|---|
| Country/Territory | Spain |
| City | Playa Blanca, Lanzarote, Canary Islands |
| Period | 9/04/18 → 11/04/18 |