arXiv来源发表:
不可知学习与多准确度被证明等价：一个多准确度预言机，经自适应查询就能达到最优判别
核心概要
在固定特征分布、任意模型类的设定下，不可知学习（训练判别模型去逼近类内最优）与多准确度（训练生成模型使类内所有观察者都分不清真假标签）被证明在统计与计算复杂度上等价。此前只有从不可知学习到多准确度这一方向已知，反方向因单个多准确度预测器即使校准也无法超过随机猜测而悬置；新的归约反复调用多准确度预言机、按预测值分层并加权平均，最终得到既多准确又校准的预测器，从而完成不可知学习。
深度剖析
不可知学习与多准确度这两个学习任务在复杂度上被证明等价，而不只是相近。 此前只有从不可知学习到多准确度这一方向已知，借助复杂度理论中的正则性引理，以提升算法的风格把不可知学习归约为多准确度。 等价性表述为：对任意特征分布与任意模型类，任一问题的有效算法都能通过开销为多项式级别的预言机归约转成另一问题的有效算法。
反方向的归约靠反复向多准确度预言机提问，再把各轮回答组合起来。 单个多准确度预测器即使经过任意后处理也不足以做弱不可知学习，因为存在多准确但反校准的预测器，其真实标签在给定预测后仍近似均匀随机。 归约在每一轮改变标签分布而保持特征边缘分布不变，按预测值分层求条件多准确度，最后对迭代结果做加权平均；该归约也能在统计查询框架内实现。
启示与展望
结论针对固定且已知的特征边缘分布、二值标签以及任意给定模型类，以预言机归约的形式给出，开销为多项式级别；归约同样可在统计查询框架内实现，因此不可知学习的统计查询下界也适用于多准确度预测。
下界针对的是对条件多准确度预言机的调用次数，而非对底层多准确度预言机的调用次数，后者被列为后续方向；部分下界实例只适用于特定归约算法，另一些则不限于此。