跳到正文
返回论文列表
stat.ML提交于 已译

稀有尾部统计用于学习带标签噪声的有偏高斯半空间

Rare-Tail Statistics For Learning Biased Gaussian Halfspaces with Label Noise

Arya Mazumdar · Prateeti Mukherjee · Harsh Vardhan

中文摘要

重新审视存在标签噪声时学习一般高斯半空间(Gaussian halfspaces)的经典问题,重点关注大偏置(large-bias)情形——在若干标准标签噪声模型中,该情形被推测存在信息-计算差距(information-computation gaps)。提出并分析稀有尾部均值估计器(rare-tail mean estimator):一种极简单的一次性统计量,仅对观测到的少数类取平均。在大偏置情形下,经典 Averaging(Servedio, 1999)及相关全局一阶矩统计量可证明次优;而稀有尾部均值估计器在广泛标签噪声模型下,以信息论样本率(忽略对数因子)恢复目标半空间方向,这些模型包括 probit 噪声与远离边界衰减极慢的边界相关噪声。该保证允许决策边界附近的标签近乎随机,同时仍能从小样本中实现强方向恢复。该估计器在无噪声与有噪声情形间平滑过渡:无噪声时达到与基于可分性的经典方法相同的样本率;低噪声或远离边界衰减的噪声下,即使线性可分性已被破坏仍保持该率。应用上考虑两阶段课程:源样本(边界附近噪声可任意接近 1/2 且远离边界衰减极慢)先于目标样本(以相同速率翻转每个标签,即随机分类噪声 RCN)。两阶段共享同一 Bayes 最优半空间,估计器为现有精炼流程提供所需的方向热启动,二者结合在大偏置情形下以信息论样本率(忽略对数因子)学习 RCN 目标。

关键要点

  1. 01大偏置高斯半空间在标签噪声下存在信息-计算差距,经典 Averaging 方法可证明次优。
  2. 02稀有尾部均值估计器仅平均少数类观测,在 probit 等噪声模型下达到信息论样本率。
  3. 03允许边界附近标签近乎随机,仍能从小样本强恢复半空间方向。
  4. 04无噪声时匹配经典可分性方法样本率,低噪声下线性可分性破坏后仍保持该率。
  5. 05两阶段课程中为 RCN 目标精炼提供方向热启动,联合达到信息论样本率。

解读

尚无解读。

原始英文摘要

arXiv:2611.24181v1 Announce Type: new Abstract: We revisit the classical problem of learning general Gaussian halfspaces in the presence of label noise, with particular focus on the large-bias regime, where information-computation gaps are conjectured in several standard label-noise models. Concretely, we present and analyze the rare-tail mean estimator, an extremely simple one-shot statistic that averages only the observed minority class. In the large-bias regime, classical Averaging (Servedio, 1999) and related global first-moment statistics are provably suboptimal, while the rare-tail mean estimator recovers the target halfspace direction at the information-theoretic sample rate (modulo log factors) under a broad class of label noise models, including probit noise and margin-dependent noise with very slow decay away from the boundary. Notably, our guarantees allow labels arbitrarily close to the decision boundary to be nearly random, while still giving strong directional recovery from a small number of samples. The estimator also cleanly interpolates between the noiseless and noisy regimes: without noise, it attains the same sample rate as classical separability-based methods for realizable halfspaces, and under low noise, or noise that decays away from the boundary, it keeps this rate even after linear separability has been destroyed. As an application, we consider a two-stage curriculum in which source samples, whose noise may be arbitrarily close to $1/2$ near the boundary and decay very slowly away from it, precede target samples, whose noise flips every label at the same rate, i.e., random classification noise (RCN). Since both stages share the same Bayes optimal halfspace, our estimator supplies the directional warm start needed by existing refinement routines, and together they learn the RCN target at the information-theoretic sample rate in the large-bias regime, up to log factors.

同方向论文 · stat.ML

查看全部 →