← 研踪 PaperTrailarXiv:2611.12694 · v1
Agnostic Marginal-Nonuniform Learning
首次提交 2026-11-10 00:55
版本更新 2026-11-10 00:55
雷达观测 2026-11-10 15:22
摘要
We study the problem of binary classification in the marginal-nonuniform learning framework in the agnostic setting. In this model, the constants in the learning rate may depend on the marginal distribution of the unlabeled data, but the guarantee must hold uniformly over all conditional distributions of the labels. We also study fine-grained rates. We consider two criteria. (1) The standard agnostic setting, where the learner competes with the best concept in the class. In this setting, an immediate consequence of standard agnostic PAC learning results gives us the optimal rate of $\tfrac{1}{\sqrt{n}}$ for every class $\mathcal{H}$ with finite $\mathrm{VC}(\mathcal{H})$ and shows that arbitrarily slow rates are necessary otherwise. This also gives us the optimal fine-grained rate of $\sqrt{\tfrac{\mathrm{VC}(\mathcal{H})}{n}}$. Therefore, the dependence on the marginal distribution does not help, which is in contrast to the realizable setting. (2) In the relaxed agnostic setting, where the learner competes with $(1+λ)$ times the error of the best concept for a fixed $λ\in (0,1]$, the picture from the realizable setting reappears. We obtain a trichotomy of the achievable optimal rates: exponential rates of the form $e^{-n}$ arise precisely when the class is finite; linear rates of the form $\tfrac{1}{n}$ arise when the class is infinite but $\mathrm{VC}(\mathcal{H})$ is finite; and arbitrarily slow rates occur when $\mathrm{VC}(\mathcal{H})=\infty$. We also obtain the optimal fine-grained rate of $\tfrac{\mathrm{uVCE}(\mathcal{H})}{λn}$, where $\mathrm{uVCE}(\mathcal{H})$ is a recently introduced combinatorial complexity dimension called the uncentered $\mathrm{VC}$-eluder dimension.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-10 00:55 · 最新观测版本
Agnostic Marginal-Nonuniform Learning
We study the problem of binary classification in the marginal-nonuniform learning framework in the agnostic setting. In this model, the constants in the learning rate may depend on the marginal distribution of the unlabeled data, but the guarantee must hold uniformly over all conditional distributions of the labels. We also study fine-grained rates. We consider two criteria. (1) The standard agnostic setting, where the learner competes with the best concept in the class. In this setting, an immediate consequence of standard agnostic PAC learning results gives us the optimal rate of $\tfrac{1}{\sqrt{n}}$ for every class $\mathcal{H}$ with finite $\mathrm{VC}(\mathcal{H})$ and shows that arbitrarily slow rates are necessary otherwise. This also gives us the optimal fine-grained rate of $\sqrt{\tfrac{\mathrm{VC}(\mathcal{H})}{n}}$. Therefore, the dependence on the marginal distribution does not help, which is in contrast to the realizable setting. (2) In the relaxed agnostic setting, where the learner competes with $(1+λ)$ times the error of the best concept for a fixed $λ\in (0,1]$, the picture from the realizable setting reappears. We obtain a trichotomy of the achievable optimal rates: exponential rates of the form $e^{-n}$ arise precisely when the class is finite; linear rates of the form $\tfrac{1}{n}$ arise when the class is infinite but $\mathrm{VC}(\mathcal{H})$ is finite; and arbitrarily slow rates occur when $\mathrm{VC}(\mathcal{H})=\infty$. We also obtain the optimal fine-grained rate of $\tfrac{\mathrm{uVCE}(\mathcal{H})}{λn}$, where $\mathrm{uVCE}(\mathcal{H})$ is a recently introduced combinatorial complexity dimension called the uncentered $\mathrm{VC}$-eluder dimension.
查看此版本解读 →查看此版本原文 ↗