Kevin: Query Complexity of Derivative-Free Optimization || Pari: Covariance Sketching
Kevin: This work 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 …