Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applications

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 gradientfree operation and employing the ADMM to accommodate complex structured regularizers. Compared to the first-order gradientbased online algorithm, we show that ZOOADMM requires A/m times more iterations, leading to a convergence rate of 0(\m/ \j), 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-lmNT), 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.