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 方面相对于随机样本具有显著的运行时改进作用。