ZerothOrder Online Alternating Direction Method of Multipliers: Convergence Analysis and Applications
[edit]
Proceedings of the TwentyFirst International Conference on Artificial Intelligence and Statistics, PMLR 84:288297, 2018.
Abstract
In this paper, we design and analyze a new zerothorder online algorithm, namely, the zerothorder online alternating direction method of multipliers (ZOOADMM), which enjoys dual advantages of being gradientfree operation and employing the ADMM to accommodate complex structured regularizers. Compared to the firstorder gradientbased online algorithm, we show that ZOOADMM requires $\sqrt{m}$ times more iterations, leading to a convergence rate of $O(\sqrt{m}/\sqrt{T})$, where $m$ is the number of optimization variables, and $T$ is the number of iterations. To accelerate ZOOADMM, we propose two minibatch strategies: gradient sample averaging and observation averaging, resulting in an improved convergence rate of $O(\sqrt{1+q^{1}m}/\sqrt{T})$, where $q$ is the minibatch size. In addition to convergence analysis, we also demonstrate ZOOADMM to applications in signal processing, statistics, and machine learning.
Related Material


