Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity

Abstract

Zeroth-order (a.k.a, derivative-free) methods are a class of effective optimization methods for solving complex machine learning problems, where gradients of the objective functions are not available or computationally prohibitive. Recently, although many zeroth-order methods have been developed, these approaches still have two main drawbacks: 1) high function query complexity; 2) not being well suitable for solving the problems with complex penalties and constraints. To address these challenging drawbacks, in this paper, we propose a class of faster zeroth-order stochastic alternating direction method of multipliers (ADMM) methods (ZO-SPIDER-ADMM) to solve the nonconvex finite-sum problems with multiple nonsmooth penalties. Moreover, we prove that the ZO-SPIDER-ADMM methods can achieve a lower function query complexity of $O(nd+d{n}^{\frac{1}{2}}{\epsilon }^{-1})$ for finding an $\epsilon$-stationary point, which improves the existing best nonconvex zeroth-order ADMM methods by a factor of $O(d^{\frac{1}{3}}{n}^{\frac{1}{6}})$, where $n$ and $d$ denote the sample size and data dimension, respectively. At the same time, we propose a class of faster zeroth-order online ADMM methods (ZOO-ADMM+) to solve the nonconvex online problems with multiple nonsmooth penalties. We also prove that the proposed ZOO-ADMM+ methods achieve a lower function query complexity of $O(d{\epsilon }^{-\frac{3}{2}})$, which improves the existing best result by a factor of $O({\epsilon }^{-\frac{1}{2}})$. Extensive experimental results on the structure adversarial attack on black-box deep neural networks demonstrate the efficiency of our new algorithms.

arXiv commentThis paper was accepted to IEEE Transactions on Pattern Analysis and Machine Intelligence

References in corpus (14)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Training Neural Networks Without Gradients: A Scalable ADMM Approach
• Structured Adversarial Attack: Towards General Implementation and Better Interpretability
• Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
• A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• Structured Evolution with Compact Architectures for Scalable Policy Optimization
• Zeroth Order Nonconvex Multi-Agent Optimization over Networks
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Accelerated Variance Reduced Stochastic ADMM
• Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization
• Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization

Cited by in corpus (3)

• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Desirable Companion for Vertical Federated Learning: New Zeroth-Order Gradient Based Algorithm