We study zeroth-order optimization for convex functions where we further
assume that function evaluations are unavailable. Instead, one only has access
to a $\textit{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.

本文利用一位 $	extit {comparison oracle}$ 来实现零阶优化问题的求解，结合一位未知信号的压缩感知，提出了使用梯度下降算法的新型算法 SCOBO，在具有低维结构可供利用的情况下，优于现有技术。

一位使用比较法的一比特梯度估计器

A One-bit, Comparison-Based Gradient Estimator

Binary measurements arise naturally in a variety of statistical and
engineering applications. They may be inherent to the problem---e.g., in
determining the relationship between genetics and the presence or absence of a
disease---or they may be a result of extreme quantization. In one-bit
compressed sensing it has recently been shown that the number of one-bit
measurements required for signal estimation mirrors that of unquantized
compressed sensing. Indeed, $s$-sparse signals in $\mathbb{R}^n$ can be
estimated (up to normalization) from $\Omega(s \log (n/s))$ one-bit
measurements. Nevertheless, controlling the precise accuracy of the error
estimate remains an open challenge. In this paper, we focus on optimizing the
decay of the error as a function of the oversampling factor $\lambda := m/(s
\log(n/s))$, where $m$ is the number of measurements. It is known that the
error in reconstructing sparse signals from standard one-bit measurements is
bounded below by $\Omega(\lambda^{-1})$. Without adjusting the measurement
procedure, reducing this polynomial error decay rate is impossible. However, we
show that an adaptive choice of the thresholds used for quantization may lower
the error rate to $e^{-\Omega(\lambda)}$. This improves upon guarantees for
other methods of adaptive thresholding as proposed in Sigma-Delta quantization.
We develop a general recursive strategy to achieve this exponential decay and
two specific polynomial-time algorithms which fall into this framework, one
based on convex programming and one on hard thresholding. This work is inspired
by the one-bit compressed sensing model, in which the engineer controls the
measurement procedure. Nevertheless, the principle is extendable to signal
reconstruction problems in a variety of binary statistical models as well as
statistical estimation problems like logistic regression.

本文介绍了一种基于自适应阈值策略的一比特压缩感知方法，针对二进制测量问题进行了研究，在某些情况下可以实现对稀疏信号的重建。

使用二进制测量稀疏信号的重建误差的指数衰减

Exponential decay of reconstruction error from binary measurements of  sparse signals

In one-bit compressed sensing, previous results state that sparse signals may
be robustly recovered when the measurements are taken using Gaussian random
vectors. In contrast to standard compressed sensing, these results are not
extendable to natural non-Gaussian distributions without further assumptions,
as can be demonstrated by simple counter-examples. We show that approximately
sparse signals that are not extremely sparse can be accurately reconstructed
from single-bit measurements sampled according to a sub-gaussian distribution,
and the reconstruction comes as the solution to a convex program.

本研究通过使用次高斯分布的单比特测量，结合凸程序解决方案，可以精确地重建几乎稀疏的信号。

非高斯测量的一位压缩感知

One-bit compressed sensing with non-Gaussian measurements

We give the first computationally tractable and almost optimal solution to
the problem of one-bit compressed sensing, showing how to accurately recover an
s-sparse vector x in R^n from the signs of O(s log^2(n/s)) random linear
measurements of x. The recovery is achieved by a simple linear program. This
result extends to approximately sparse vectors x. Our result is universal in
the sense that with high probability, one measurement scheme will successfully
recover all sparse vectors simultaneously. The argument is based on solving an
equivalent geometric problem on random hyperplane tessellations.

本文通过随机线性测量得到的 O (s log^2 (n/s)) 个标志位，利用线性规划，从稀疏向量中精确恢复出 s-sparse 向量 x，进而将结果推广到了近似稀疏的向量 x。文章以解决随机超平面填充的等效几何问题为基础，并且该方法几乎是最优解。