半空间学习也能差分隐私：三种不可知设定下隐私代价被统计项吸收，样本量不再多付

半空间的高斯边际不可知学习现在有了计算高效的差分隐私版本，覆盖输出不必是半空间的非正当学习、输出必须是半空间的正当学习，以及允许常数倍最优误差的半正当学习三种设定。 此前在无限定义域上，无分布假设的差分隐私半空间学习在信息论上不可行，而已有的隐私不可知学习归约虽在统计上有效，却没有被证明计算高效。 非正当与正当设定给出误差不超过最优半空间误差加精度参数的高概率保证，半正当设定给出误差不超过最优误差的常数倍加精度参数的高概率保证，且三种算法对固定精度而言运行时间是样本量的多项式。

做法是把非隐私的多项式回归路线私有化：用截断的 Hermite 特征做私有的多项式 L1 回归，再对阈值化后的候选分类器做私有选择。 非隐私路线先用低次多项式拟合标签再取阈值，但直接加噪需要系数有界和特征范数有界两个额外性质。 把系数限制在单位欧氏球内、把特征向量截断到范数上限后，截断只以截断概率的量级抬高总体损失，于是可以用私有凸经验风险最小化拟合系数。

正当学习先私有地估计一个多项式，再由它构造一个包含近最优半空间的低维子空间，在该子空间上半空间只需 O(d) 个参数。 非正当学习的输出是 d 的 1/α² 次方量级的系数，而半空间表示更紧凑、更易解释，也更快点算。 子空间维数为 α 的负四次方量级，对其上的单位法向量离散化得到有限半空间类，再用指数机制在独立验证块上选出最终半空间。

半正当学习改用私有化的非凸梯度下降子程序，并在一个几何网格上搜索最优误差的上界，从而把样本复杂度对 1/α 的依赖从指数降为多项式。 前两种设定的样本复杂度对 1/α 呈指数依赖，半正当设定允许误差为最优误差的常数倍，从而绕开这一障碍。 给定一个已知的最优误差上界，子程序返回误差为该上界常数倍的半空间；对候选上界逐一运行后，用指数机制在独立验证集上挑出假设。

结论针对输入边际为高斯分布（另有一节扩展到已知的对数凹边际）且标签可任意的分布，误差保证以至少 1 减去失败概率的概率成立；非正当与正当设定还要求维度不低于精度参数的负五次方量级的常数倍。

“隐私免费”成立的条件是隐私参数不小于精度参数，此时隐私项才被统计项吸收；非正当设定需要对每一族已知边际显式构造正交多项式基，而更通用的基或从数据中私有地学习基仍是未解方向。