提出高效构造单索引模型的通用预测器，显著降低样本需求与计算成本。
Omnipredicting Single-Index Models with Multi-Index Models
- 基于改进的Isotron算法，构造多索引形式的通用预测器。
- 仅需约ε⁻⁴样本即可达到ε-竞争力，比之前方法减少10倍以上。
- 适合关注理论效率与通用学习框架的研究者，尤其关注可推广性设计。
近期研究定义了通用预测器（omnipredictors）的概念，即能在一组损失函数下同时逼近最优预测性能的函数。然而，现有对单索引模型（SIMs）的通用预测器构造需要极高的样本复杂度和运行时间，且输出为复杂、不合理的假设。本文提出一种新构造方法：在比较类为有界线性预测器、损失函数由单调且Lipschitz连续链接函数诱导的前提下，所提学习器输出的预测器在任意匹配损失下均达到ε-竞争力。该算法仅需约ε⁻⁴个样本，近线性时间内完成；若链接函数为双李普希茨，则样本复杂度可降至约ε⁻²。相比此前唯一已知构造（[HJKRR18, GHK+23]）所需的ε⁻¹⁰量级样本，本方法实现显著改进。我们通过新分析手段精确刻画经典Isotron算法在挑战性的无假设学习设置下的行为，其成果可能具有独立研究价值。由于基于Isotron，所得通用预测器为含约ε⁻²个预测头的多索引模型，更接近一般损失族与比较类下的合理通用预测目标。
原文摘要 · Abstract (English)
Recent work on supervised learning [GKR+22] defined the notion of omnipredictors, i.e., predictor functions $p$ over features that are simultaneously competitive for minimizing a family of loss functions $\mathcal{L}$ against a comparator class $\mathcal{C}$. Omniprediction requires approximating the Bayes-optimal predictor beyond the loss minimization paradigm, and has generated significant interest in the learning theory community. However, even for basic settings such as agnostically learning single-index models (SIMs), existing omnipredictor constructions require impractically-large sample complexities and runtimes, and output complex, highly-improper hypotheses. Our main contribution is a new, simple construction of omnipredictors for SIMs. We give a learner outputting an omnipredictor that is $\varepsilon$-competitive on any matching loss induced by a monotone, Lipschitz link function, when the comparator class is bounded linear predictors. Our algorithm requires $\approx \varepsilon^{-4}$ samples and runs in nearly-linear time, and its sample complexity improves to $\approx \varepsilon^{-2}$ if link functions are bi-Lipschitz. This significantly improves upon the only prior known construction, due to [HJKRR18, GHK+23], which used $\gtrsim \varepsilon^{-10}$ samples. We achieve our construction via a new, sharp analysis of the classical Isotron algorithm [KS09, KKKS11] in the challenging agnostic learning setting, of potential independent interest. Previously, Isotron was known to properly learn SIMs in the realizable setting, as well as constant-factor competitive hypotheses under the squared loss [ZWDD24]. As they are based on Isotron, our omnipredictors are multi-index models with $\approx \varepsilon^{-2}$ prediction heads, bringing us closer to the tantalizing goal of proper omniprediction for general loss families and comparators.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。