# Gradient Testing and Estimation by Comparisons

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 53 references that are in the map.
- First posted on arXiv 19 May 2024.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [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)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Sign-OPT: A Query-Efficient Hard-label Adversarial Attack](https://mlsanity.com/paper/1909.10773/) (2019)
- [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)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [A One-bit, Comparison-Based Gradient Estimator](https://mlsanity.com/paper/2010.02479/) (2020)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)
- [On the Local Minima of the Empirical Risk](https://mlsanity.com/paper/1803.09357/) (2018)
- [Quantum speedups for stochastic optimization](https://mlsanity.com/paper/2308.01582/) (2023)
- [Efficiently avoiding saddle points with zero order methods: No gradients required](https://mlsanity.com/paper/1910.13021/) (2019)
- [Quantum algorithms for escaping from saddle points](https://mlsanity.com/paper/2007.10253/) (2020)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling](https://mlsanity.com/paper/2301.03763/) (2023)
- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [Quantum algorithms for Second-Order Cone Programming and Support Vector Machines](https://mlsanity.com/paper/1908.06720/) (2019)
- [Smooth Convex Optimization using Sub-Zeroth-Order Oracles](https://mlsanity.com/paper/2103.00667/) (2021)

## Abstract (arXiv)

We study gradient testing and gradient estimation of smooth functions using only a comparison oracle that, given two points, indicates which one has the larger function value. For any smooth fcolonmathbb Rn→mathbb R, x∈mathbb Rn, and varepsilon>0, we design a gradient testing algorithm that determines whether the normalized gradient nabla f(x)/|nabla f(x)| is varepsilon-close or 2varepsilon-far from a given unit vector v using O(1) queries, as well as a gradient estimation algorithm that outputs an varepsilon-estimate of nabla f(x)/|nabla f(x)| using O(nlog(1/varepsilon)) queries which we prove to be optimal. Furthermore, we study gradient estimation in the quantum comparison oracle model where queries can be made in superpositions, and develop a quantum algorithm using O(log (n/varepsilon)) queries.