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

arXiv: https://arxiv.org/abs/1907.13463 · HTML: https://mlsanity.com/paper/1907.13463/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2019.

## Built on by (most cited first, 2 of 2)

- [Federated Learning from Molecules to Processes: A Perspective](https://mlsanity.com/paper/2506.18525/) (2025)
- [SPADE-DFL: Communication-Efficient Decentralized Federated Learning via Derivative-Free Linearized ADMM](https://mlsanity.com/paper/2609.29446/) (2026)

## Abstract (arXiv)

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+dn^frac12ε-1) for finding an ε-stationary point, which improves the existing best nonconvex zeroth-order ADMM methods by a factor of O(d^frac13n^frac16), 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ε^-frac32), which improves the existing best result by a factor of O(ε^-frac12). Extensive experimental results on the structure adversarial attack on black-box deep neural networks demonstrate the efficiency of our new algorithms.