We study the power of query access for the task of agnostic learning under
the Gaussian distribution. In the agnostic model, no assumptions are made on
the labels and the goal is to compute a hypothesis that is competitive with the
{\em best-fit} function in a known class, i.e., it achieves error
$\mathrm{opt}+\epsilon$, where $\mathrm{opt}$ is the error of the best function
in the class. We focus on a general family of Multi-Index Models (MIMs), which
are $d$-variate functions that depend only on few relevant directions, i.e.,
have the form $g(\mathbf{W} \mathbf{x})$ for an unknown link function $g$ and a
$k \times d$ matrix $\mathbf{W}$. Multi-index models cover a wide range of
commonly studied function classes, including constant-depth neural networks
with ReLU activations, and intersections of halfspaces.
Our main result shows that query access gives significant runtime
improvements over random examples for agnostically learning MIMs. Under
standard regularity assumptions for the link function (namely, bounded
variation or surface area), we give an agnostic query learner for MIMs with
complexity $O(k)^{\mathrm{poly}(1/\epsilon)} \; \mathrm{poly}(d) $. In
contrast, algorithms that rely only on random examples inherently require
$d^{\mathrm{poly}(1/\epsilon)}$ samples and runtime, even for the basic problem
of agnostically learning a single ReLU or a halfspace.
Our algorithmic result establishes a strong computational separation between
the agnostic PAC and the agnostic PAC+Query models under the Gaussian
distribution. Prior to our work, no such separation was known -- even for the
special case of agnostically learning a single halfspace, for which it was an
open problem first posed by Feldman. Our results are enabled by a general
dimension-reduction technique that leverages query access to estimate gradients
of (a smoothed version of) the underlying label function.

研究了高斯分布下对于无偏学习任务的查询访问权限的能力。聚焦于多指数模型（MIMs），研究表明查询访问权限在无偏学习 MIMs 方面相对于随机样本具有显著的运行时改进作用。

无知地利用查询学习多索引模型

Agnostically Learning Multi-index Models with Queries

Solving for adversarial examples with projected gradient descent has been
demonstrated to be highly effective in fooling the neural network based
classifiers. However, in the black-box setting, the attacker is limited only to
the query access to the network and solving for a successful adversarial
example becomes much more difficult. To this end, recent methods aim at
estimating the true gradient signal based on the input queries but at the cost
of excessive queries. We propose an efficient discrete surrogate to the
optimization problem which does not require estimating the gradient and
consequently becomes free of the first order update hyperparameters to tune.
Our experiments on Cifar-10 and ImageNet show the state of the art black-box
attack performance with significant reduction in the required queries compared
to a number of recently proposed methods. The source code is available at
this https URL

本文提出了一种离散替代方法来解决黑匣子攻击的问题，该方法可以在不需要估计导数的情况下有效地攻击神经网络，降低了之前所提出方法所需的查询次数。

高效组合优化的简约黑盒对抗攻击

Parsimonious Black-Box Adversarial Attacks via Efficient Combinatorial  Optimization

Existing black-box attacks on deep neural networks (DNNs) so far have largely
focused on transferability, where an adversarial instance generated for a
locally trained model can "transfer" to attack other learning models. In this
paper, we propose novel Gradient Estimation black-box attacks for adversaries
with query access to the target model's class probabilities, which do not rely
on transferability. We also propose strategies to decouple the number of
queries required to generate each adversarial sample from the dimensionality of
the input. An iterative variant of our attack achieves close to 100%
adversarial success rates for both targeted and untargeted attacks on DNNs. We
carry out extensive experiments for a thorough comparative evaluation of
black-box attacks and show that the proposed Gradient Estimation attacks
outperform all transferability based black-box attacks we tested on both MNIST
and CIFAR-10 datasets, achieving adversarial success rates similar to well
known, state-of-the-art white-box attacks. We also apply the Gradient
Estimation attacks successfully against a real-world Content Moderation
classifier hosted by Clarifai. Furthermore, we evaluate black-box attacks
against state-of-the-art defenses. We show that the Gradient Estimation attacks
are very effective even against these defenses.

提出了一种新的基于梯度估计的黑盒攻击方法，攻击者可以查询目标模型的类概率，无需使用可转移性。该攻击在 MNIST 和 CIFAR-10 数据集上的攻击成功率均超过 100％，同时成功攻击了 Clarifai 的实时图像分类器和最新防御方法。