# Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 30 references that are in the map.
- First posted on arXiv 3 Oct 2024.

## Builds on (most cited first, 20 of 20)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization](https://mlsanity.com/paper/1910.06513/) (2019)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization](https://mlsanity.com/paper/1910.12166/) (2019)
- [A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order](https://mlsanity.com/paper/1606.00498/) (2016)
- [Optimal Black-Box Reductions Between Optimization Objectives](https://mlsanity.com/paper/1603.05642/) (2016)
- [Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions](https://mlsanity.com/paper/1808.06296/) (2018)
- [An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/1802.09022/) (2018)
- [Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization](https://mlsanity.com/paper/1902.06158/) (2019)
- [Inexact Proximal Gradient Methods for Non-convex and Non-smooth Optimization](https://mlsanity.com/paper/1612.06003/) (2016)
- [An Accelerated DFO Algorithm for Finite-sum Convex Functions](https://mlsanity.com/paper/2007.03311/) (2020)

## Abstract (arXiv)

Zeroth-order (ZO) optimization is one key technique for machine learning problems where gradient calculation is expensive or impossible. Several variance reduced ZO proximal algorithms have been proposed to speed up ZO optimization for non-smooth problems, and all of them opted for the coordinated ZO estimator against the random ZO estimator when approximating the true gradient, since the former is more accurate. While the random ZO estimator introduces bigger error and makes convergence analysis more challenging compared to coordinated ZO estimator, it requires only O(1) computation, which is significantly less than O(d) computation of the coordinated ZO estimator, with d being dimension of the problem space. To take advantage of the computationally efficient nature of the random ZO estimator, we first propose a ZO objective decrease (ZOOD) property which can incorporate two different types of errors in the upper bound of convergence rate. Next, we propose two generic reduction frameworks for ZO optimization which can automatically derive the convergence results for convex and non-convex problems respectively, as long as the convergence rate for the inner solver satisfies the ZOOD property. With the application of two reduction frameworks on our proposed ZOR-ProxSVRG and ZOR-ProxSAGA, two variance reduced ZO proximal algorithms with fully random ZO estimators, we improve the state-of-the-art function query complexities from Oleft(minfracdn1/2ε2, fracdε3right) to tildeOleft(fracn+dε2right) under d > n^frac12 for non-convex problems, and from Oleft(fracdε2right) to tildeOleft(nlogfrac1ε+fracdεright) for convex problems.