半空间学习也能差分隐私：三种不可知设定下隐私代价被统计项吸收，样本量不再多付
在标签可任意错误的高斯边际半空间学习中，差分隐私此前缺少计算高效的算法。这项工作报告了三种设定下的高效差分隐私学习器：非正当学习、正当学习和半正当学习；当隐私参数不小于精度参数时，隐私带来的额外样本代价被各自的非隐私统计项吸收，因而在样本复杂度意义上“隐私免费”。
不可知学习与多准确度被证明等价：一个多准确度预言机，经自适应查询就能达到最优判别
在固定特征分布、任意模型类的设定下，不可知学习（训练判别模型去逼近类内最优）与多准确度（训练生成模型使类内所有观察者都分不清真假标签）被证明在统计与计算复杂度上等价。此前只有从不可知学习到多准确度这一方向已知，反方向因单个多准确度预测器即使校准也无法超过随机猜测而悬置；新的归约反复调用多准确度预言机、按预测值分层并加权平均，最终得到既多准确又校准的预测器，从而完成不可知学习。
已读完全部报道