A one-bit, comparison-based gradient estimator.

Joint with HanQin Cai, Wotao Yin and Zhenliang Zhang.

We link the problem of approximating the gradient of a function using only comparison based evaluations to one-bit compressed sensing. We provide a gradient estimator and an optimization algorithm that exceeds the prior state-of-the-art when gradients are approximately sparse.

Arxiv version