REVIEW 3 cited by
Query Complexity of Derivative-Free Optimization
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
This paper provides lower bounds on the convergence rate of Derivative Free Optimization (DFO) with noisy function evaluations, exposing a fundamental and unavoidable gap between the performance of algorithms with access to gradients and those with access to only function evaluations. However, there are situations in which DFO is unavoidable, and for such situations we propose a new DFO algorithm that is proved to be near optimal for the class of strongly convex objective functions. A distinctive feature of the algorithm is that it uses only Boolean-valued function comparisons, rather than function evaluations. This makes the algorithm useful in an even wider range of applications, such as optimization based on paired comparisons from human subjects, for example. We also show that regardless of whether DFO is based on noisy function evaluations or Boolean-valued function comparisons, the convergence rate is the same.
Forward citations
Cited by 3 Pith papers
-
When cheap gradients fail: the measurement cost of attacking quantum classifiers
Unbiased gradient extraction for attacking quantum classifiers costs at least Θ(d^{5/2}) shots under norm-concentration scaling, and ~d³ for tested deep circuits, so the attacker's relative cost diverges versus classi...
-
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.
-
Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees
An iterative hard-thresholding variant with a two-step projection offers global objective-value guarantees for sparse optimization with support-preserving convex constraints, including the first zeroth-order hard-thre...
Discussion (0). Continue with ORCID to comment.