信息论极限下的高效鲁棒学习

新研究解决了固定分布下布尔概念类鲁棒学习的计算效率难题，在拥有 ERM 预言机时实现了能达到最优误差 $\eta + \varepsilon$ 的多项式时间算法。针对超收缩分布下支持低阶多项式逼近的函数类，研究还提出了无需 ERM 预言机的高效鲁棒学习算法。该技术结合了在线凸优化，并证明不可知设定下的高效 SQ 可学习性蕴含了带污染分布下的高效学习。