Adapting zeroth order algorithms for comparison-based optimization.
Published in (Submitted to SIURO), 2021
Joint with Isha Slavin*.
Comparison-Based Optimization (CBO) methods are used when the only feedback attainable is via an oracle which takes as input a pair of points (x,y) and as output tells you which has the lower objective function value. Somewhat surprisingly, many zeroth-order methods are actually CBO methods in disguise. We provide a criterion for telling when this is the case, and tools for doing the conversion.