A One-bit, Comparison-Based Gradient Estimator

Abstract

We study zeroth-order optimization for convex functions where we further assume that function evaluations are unavailable. Instead, one only has access to a $\text{comparison oracle}$, which given two points $x$ and $y$ returns a single bit of information indicating which point has larger function value, $f(x)$ or $f(y)$. By treating the gradient as an unknown signal to be recovered, we show how one can use tools from one-bit compressed sensing to construct a robust and reliable estimator of the normalized gradient. We then propose an algorithm, coined SCOBO, that uses this estimator within a gradient descent scheme. We show that when $f(x)$ has some low dimensional structure that can be exploited, SCOBO outperforms the state-of-the-art in terms of query complexity. Our theoretical claims are verified by extensive numerical experiments.

References in corpus (6)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Query Complexity of Derivative-Free Optimization
• The Power of Normalization: Faster Evasion of Saddle Points
• Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling
• AdaDGS: An adaptive black-box optimization method with a nonlocal directional Gaussian smoothing gradient
• Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit

Cited by in corpus (4)

• A Hamilton-Jacobi-based Proximal Operator
• Stochastic Zeroth Order Gradient and Hessian Estimators: Variance Reduction and Refined Bias Bounds
• Curvature-Aware Derivative-Free Optimization
• Small errors in random zeroth-order optimization are imaginary