Gradient Testing and Estimation by Comparisons
read the original abstract
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 $f\colon\mathbb R^n\to\mathbb R$, $\mathbf{x}\in\mathbb R^n$, and $\varepsilon>0$, we design a gradient testing algorithm that determines whether the normalized gradient $\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\|$ is $\varepsilon$-close or $2\varepsilon$-far from a given unit vector $\mathbf{v}$ using $O(1)$ queries, as well as a gradient estimation algorithm that outputs an $\varepsilon$-estimate of $\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\|$ using $O(n\log(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.
This paper has not been read by Pith yet.
Forward citations
Cited by 4 Pith papers
-
Function-free Optimization via Comparison Oracles
Introduces a comparison-oracle framework using preference level-set geometry to achieve near-optimal query complexity for normal direction estimation and descent-based optimization under regularity and convexity.
-
Function-free Optimization via Comparison Oracles
Introduces a geometry-based framework for comparison-oracle optimization, with O(d log(d/ε)) comparisons for normal direction estimation and Õ(d D²/ε²) comparisons to reach ε level-set optimality gap under regularity,...
-
Finding Stationary Points by Comparisons
Presents classical Õ(n²/ε^{1.5}) and quantum Õ(n/ε^{1.5}) query algorithms for ε-stationary points of twice-differentiable non-convex functions with Lipschitz gradient and Hessian via comparison oracles.
-
Sequential Resource Trading Using Comparison-Based Gradient Estimation
A comparison-based gradient estimation algorithm for sequential multi-issue resource trading between two greedily rational agents guarantees strict utility improvements per accepted trade and asymptotic convergence to...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.