Optimal rates for zero-order optimization: the power of two function evaluations

9 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Trust Region Policy Optimization (2015, background): “However, the complexity scales as d(2) if we are given single noisy function evaluations [8] and d if we are given pairs of evaluations with the same noise sample [9].”
An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback (2015, methodology): “However, to tackle the general case, where f(·; ξ) may be non-smooth, [4] resorted to a non-trivial smoothing s cheme and a significantly more involved analysis.”
Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates (2013, methodology): “By letting P+j denote the joint distribution over the random index V and Z conditional on the jth coordinate Vj = 1 (and similarly for P−j), we obtain the following sharper version of Assouad’s lemma [4] (see also the papers [3, 19]; we provide a proof in Appendix F.”