mlsanityData to 14 Oct 2026

Gradient Testing and Estimation by Comparisons

arXiv 2405.11454 ↗First posted 19 May 2024cs.LG cs.DS math.OCcited by 0

Not on the map. Why?

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.

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

28 of 53 references.

References · 28

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2016Practical Black-Box Attacks against Machine Learningcited by 903
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  4. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  5. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 574
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  7. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  8. 2019Sign-OPT: A Query-Efficient Hard-label Adversarial Attackcited by 120
  9. 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
  10. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  11. 2017Online to Offline Conversions, Universality and Adaptive Minibatch Sizescited by 39
  12. 2023Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oraclescited by 35
16 more
  1. 2017Quantum SDP-Solvers: Better upper and lower boundscited by 27
  2. 2019Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 24
  3. 2018Convex optimization using quantum oraclescited by 19
  4. 2020A One-bit, Comparison-Based Gradient Estimatorcited by 16
  5. 2018Quantum algorithms and lower bounds for convex optimizationcited by 15
  6. 2018On the Local Minima of the Empirical Riskcited by 12
  7. 2023Quantum speedups for stochastic optimizationcited by 12
  8. 2019Efficiently avoiding saddle points with zero order methods: No gradients requiredcited by 10
  9. 2020Quantum algorithms for escaping from saddle pointscited by 10
  10. 2022On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walkscited by 9
  11. 2023Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Samplingcited by 7
  12. 2023Quantum Langevin Dynamics for Optimizationcited by 7
  13. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  14. 2023Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Gamescited by 6
  15. 2019Quantum algorithms for Second-Order Cone Programming and Support Vector Machinescited by 4
  16. 2021Smooth Convex Optimization using Sub-Zeroth-Order Oraclescited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Smoothed Score Queries and the Complexity of Sampling
  2. 2026Finding Stationary Points by Comparisons
  3. 2024Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexity
  4. 2025Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
  5. 2024Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates
  6. 2026Optimal score function estimation via derivatives constraints
  7. 2025Implicit score matching meets denoising score matching: improved rates of convergence and log-density Hessian estimation
  8. 2024Revisiting Score Function Estimators for k-Subset Sampling