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

• DOI: 10.48550/arxiv.1710.07804
• Publication Date: 2017-01-01
• Authors: Sijia Liu; Jie Chen; Pin‐Yu Chen; Alfred O. Hero
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; Statistics - Machine Learning; 0202 electrical engineering, electronic engineering, information engineering; Machine Learning (stat.ML); 02 engineering and technology; Machine Learning (cs.LG)

In this paper, we design and analyze a new zeroth-order online algorithm, namely, the alternating direction method of multipliers (ZOO-ADMM), which enjoys dual advantages being gradient-free operation employing ADMM to accommodate complex structured regularizers. Compared first-order gradient-based show that ZOO-ADMM requires $\sqrt{m}$ times more iterations, leading convergence rate $O(\sqrt{m}/\sqrt{T})$, where $m$ is number optimization variables, $T$ iterations. To accelerate ZOO-ADMM, propose two minibatch strategies: gradient sample averaging observation averaging, resulting in an improved $O(\sqrt{1+q^{-1}m}/\sqrt{T})$, $q$ size. addition analysis, also demonstrate applications signal processing, statistics, machine learning.