统计查询模型

形式陈述

模型

统计查询学习器不访问单个样本，而向 oracle 提交有界函数 $\phi:\mathcal Z\to[-1,1]$ 和容差 $\tau>0$ 。Oracle 返回某个 $v$ ，逼近期望并保证

|v-\mathbb E_{Z\sim D}\phi(Z)|\le\tau.

返回值不是精确期望，也不必随机或无偏；它可在允许区间内采取对学习器最不利的值。算法可根据此前回答自适应地选择后续查询。

复杂度的三个坐标

高效 SQ 学习必须同时控制查询次数、最小容差和处理每个查询的计算时间。一个只发一次查询但要求 $\tau=2^{-d}$ 的算法并不高效：模拟该精度通常需要指数样本，答案也需大量位表示。因而 SQ 下界常证明，任何学习器要么发非常多查询，要么请求极小容差。

用样本模拟 oracle

对固定 $\phi\in[-1,1]$ ，用 $m$ 个 IID 样本返回经验平均 $\widehat v=m^{-1}\sum_j\phi(Z_j)$ 。Hoeffding 界给出

\Pr(|\widehat v-\mathbb E\phi|>\tau) \le2e^{-m\tau^2/2}.

因此模拟一个固定查询到失败概率 $\delta$ 需要 $m=O(\tau^{-2}\log(1/\delta))$ 。若有 $q$ 个自适应查询，直接复用同一数据会引入 adaptive data analysis 问题；简单做法是为每个查询使用独立样本并分配 $\delta/q$ ，但样本代价相应增加。

直觉

SQ oracle 不展示任何单个数据点，而允许学习器测量分布的模糊投影。查询函数选择“看哪个统计方向”，容差决定分辨率；一个弱相关信号若小于 $\tau$ ，oracle 完全可以用允许误差把它隐藏。

这也解释了复杂度为何有三个坐标。查询数控制测量方向的数量，最小容差控制每次测量所需样本精度，计算时间控制这些方向能否实际构造；只把调用次数写成多项式，会漏掉指数精度这一条隐蔽通道。

例子与边界

边界与关系

查询函数有界是有限样本模拟的关键；无界统计量需尾部假设或稳健估计。经典 SQ 模型与随机分类噪声有紧密联系，但不是所有样本算法都能高效表达为 SQ，奇偶函数学习就是重要分界。高效 PAC 学习直接获取样本；SQ 限制了访问分布的接口，因此其困难性是更具体的计算/信息限制。

SQ oracle 也不同于普通查询复杂度中的坐标 oracle：后者返回隐藏输入某一位置的精确值，前者返回分布期望的容差近似，单次答案依赖整个分布。性质测试则描述成员与 $\varepsilon$ -far 的判定目标，测试器具体可以使用坐标、样本或更强的分布访问接口。一个 SQ 算法可以实现某些测试器，但“查询数 $q$ ”只有连同容差 $\tau$ 、样本模拟方式与距离参数一起转换，才可与 property-testing 查询复杂度比较。

推论与应用

固定的有界 SQ 查询可由 $O(\tau^{-2}\log(1/\delta))$ 个独立样本模拟，因此具有逆多项式容差和多项式查询数的 SQ 算法通常能转成样本算法。自适应复用数据时，独立样本分配只是安全但昂贵的基线，更精细复用需要专门的泛化或隐私工具。

SQ 下界则证明某类问题无法仅靠低精度分布平均解决：学习器必须使用超多查询或极小容差。它刻画的是受限访问接口的困难，不会自动排除能利用单样本结构、成员查询或其他更强 oracle 的算法。

参考资料

Michael Kearns, Efficient Noise-Tolerant Learning from Statistical Queries, JACM, 1998.
Vitaly Feldman, A General Characterization of the Statistical Query Complexity, COLT, 2017.

形式陈述

模型

复杂度的三个坐标

用样本模拟 oracle

相关性例子

边界与关系

反向链接

形式陈述 ​

模型 ​

复杂度的三个坐标 ​

用样本模拟 oracle ​

相关性例子 ​

边界与关系 ​

反向链接

形式陈述

模型

复杂度的三个坐标

用样本模拟 oracle

相关性例子

边界与关系