Fugu-MT 論文翻訳(概要): On Agnostic PAC Learning in the Small Error Regime

論文の概要: On Agnostic PAC Learning in the Small Error Regime

arxiv url: http://arxiv.org/abs/2502.09496v1
Date: Thu, 13 Feb 2025 17:03:03 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-14 13:50:17.257087
Title: On Agnostic PAC Learning in the Small Error Regime
Title（参考訳）: 小誤差レジームにおけるAgnostic PAC学習について
Authors: Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas,
Abstract要約: 経験的リスク最小化学習者は、実現可能なケースでは最適だが、不可知なケースでは最適である。 Hanneke、Larsen、Zhivotovskiyの作業は、エラー項のパラメータとして$tau$を含めることで、この欠点に対処する。我々の学習者は、一定の$c leq 2.1$に対して、誤りの少ない$tau + Omega left(sqrtfractau))m + fracd + log (1 / delta)m right)の厳密性を達成することを示す。
参考スコア（独自算出の注目度）: 4.422219522591412
License:
Abstract: Binary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the agnostic case. Roughly speaking, this owes itself to the fact that non-realizable distributions $\mathcal{D}$ are simply more difficult to learn than realizable distributions -- even when one discounts a learner's error by $\mathrm{err}(h^*_{\mathcal{D}})$, the error of the best hypothesis in $\mathcal{H}$ for $\mathcal{D}$. Thus, optimal agnostic learners are permitted to incur excess error on (easier-to-learn) distributions $\mathcal{D}$ for which $\tau = \mathrm{err}(h^*_{\mathcal{D}})$ is small. Recent work of Hanneke, Larsen, and Zhivotovskiy (FOCS `24) addresses this shortcoming by including $\tau$ itself as a parameter in the agnostic error term. In this more fine-grained model, they demonstrate tightness of the error lower bound $\tau + \Omega \left(\sqrt{\frac{\tau (d + \log(1 / \delta))}{m}} + \frac{d + \log(1 / \delta)}{m} \right)$ in a regime where $\tau > d/m$, and leave open the question of whether there may be a higher lower bound when $\tau \approx d/m$, with $d$ denoting $\mathrm{VC}(\mathcal{H})$. In this work, we resolve this question by exhibiting a learner which achieves error $c \cdot \tau + O \left(\sqrt{\frac{\tau (d + \log(1 / \delta))}{m}} + \frac{d + \log(1 / \delta)}{m} \right)$ for a constant $c \leq 2.1$, thus matching the lower bound when $\tau \approx d/m$. Further, our learner is computationally efficient and is based upon careful aggregations of ERM classifiers, making progress on two other questions of Hanneke, Larsen, and Zhivotovskiy (FOCS `24). We leave open the interesting question of whether our approach can be refined to lower the constant from 2.1 to 1, which would completely settle the complexity of agnostic learning.
Abstract（参考訳）: 経験的リスク最小化(ERM: Empirical Risk Minimization)学習者は、実現可能なケースでは最適だが、不可知なケースでは最適である。大まかに言えば、これは非実現可能分布 $\mathcal{D}$ が実現不可能な分布よりも学習が難しいという事実に起因している。たとえ学習者の誤りを $\mathrm{err}(h^*_{\mathcal{D}})$ で割引しても、$\mathcal{H}$ for $\mathcal{D}$ の最良の仮説の誤差は$\mathcal{D}$ である。したがって、最適非依存学習者は、$\tau = \mathrm{err}(h^*_{\mathcal{D}})$が小さいような(より簡単な)分布に対して過剰な誤差を発生させることが許される。 Hanneke, Larsen, Zhivotovskiy (FOCS `24) の最近の研究は、この欠点に対処し、agnostic error term に $\tau$ をパラメータとして含めている。このよりきめ細かいモデルでは、エラーの下位境界である$\tau + \Omega \left(\sqrt{\frac{\tau (d + \log(1 / \delta))}{m}} + \frac{d + \log(1 / \delta)}{m} \right)$を$\tau > d/m$とすると、$\tau \approx d/m$, $d$で$\mathrm{VC}(\mathcal{H})が与えられるとき、より低い境界が存在するかどうかという疑問を開き放つ。本論では, 誤差$c \cdot \tau + O \left(\sqrt {\frac{\tau (d + \log(1 / \delta))}{m}} + \frac{d + \log(1 / \delta)}{m} \right)$ for a constant $c \leq 2.1$, so with the lower bound when $\tau \approx d/m$。さらに,本学習者は計算効率が高く,ERM分類器の注意深い集約に基づいて,Henneke,Larsen,Zhivotovskiy (FOCS `24。我々は、我々のアプローチが2.1から1への定数を下げるために洗練できるかどうかという興味深い疑問を解き放つ。

論文の概要: On Agnostic PAC Learning in the Small Error Regime

関連論文リスト