[论文] Agnostic Learning by Imitating

论文概要

研究领域: ML
作者: Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold, Konstantinos Stavropoulos, Pranay Tankala
发布时间: 2026-11-03
arXiv: 2611.05346

中文摘要

给定一个机器学习模型类和对一个带二元标签数据分布的采样访问，哪个计算任务更难：训练一个判别模型把正负样本区分开、并达到该类中最优成员的水平；还是训练一个生成模型，使其输出对类中所有成员都不可分辨？我们证明这两个计算学习理论中的基本任务不仅紧密相关，而且在复杂度上实际等价。等价的一个方向此前已知：复杂性理论中强大的正则性引理以 boosting 风格给出从「不可分辨任务」（multiaccuracy）到「区分任务」（agnostic learning）的高效 oracle 归约。我们的主要贡献是另一方向的高效 oracle 归约。进一步地，我们证明 multiaccuracy oracle 是一个异常强大的原语：通过类似的高效直接构造，它不仅可实现 agnostic learning，还能实现一大类看似要求更高的学习目标。我们的结果关键在于能对 oracle 做自适应查询，这与此前「仅对单个 multiaccurate 预测器做后处理连弱学习都做不到」的工作形成鲜明对比。技术上，我们把该离线问题与在线场景下的一种无悔学习联系起来，从而用 follow-the-leader 类算法修改标签分布并聚合 multiaccuracy oracle 的预测。

原文摘要

Given a class of machine learning models and sample access to a data distribution with binary labels, which computational task is harder: training a discriminative model that distinguishes positive and negative labels as well as the best member of the class, or training a generative model whose outputs are indistinguishable from real data by all members of the class? We prove that these two fundamental tasks in computational learning theory are not just closely related, but actually equivalent to each other in complexity. One direction of this equivalence was previously known. Indeed, the powerful regularity lemma in complexity theory gives an efficient oracle reduction from the indistinguishability task (a.k.a. multiaccuracy) to the distinguishing task (a.k.a. agnostic learning) in the style of boosting algorithms. Our main contribution is an efficient oracle reduction in the other direction. Taking this idea further, we show that a multiaccuracy oracle is a remarkably powerful primitive, achieving not just agnostic learning but also a wide range of seemingly more demanding learning objectives via similarly efficient and direct constructions. Our results crucially use the power of making adaptive queries to the oracle, and stand in stark contrast to prior work, which showed that post-processing a single multiaccurate predictor is insufficient for even weak forms of learning. On a technical level, we draw a connection between our (offline) problem and a version of no-regret learning in the online setting, which allows us to use follow-the-leader type algorithms to modify the label distribution and aggregate the predictions of the multiaccuracy oracle.

自动采集于 2026-11-05

#论文 #arXiv #AI #小凯