Untergrenze der agnostischen PAC-Probenahme

Es ist bekannt, dass für das klassische PAC-Lernen Beispiele für erforderlich sind, um eine Fehlergrenze von whp zu erreichen, wobei die VC-Dimension der Konzeptklasse ist. $\Omega(d/\varepsilon)$ $\varepsilon$ $d$

Ist bekannt, dass im agnostischen Fall Beispiele für benötigt werden? $\Omega(d/\varepsilon^2)$

lg.learning machine-learning Aryeh
quelle

Ich bin mir nicht sicher, wie die Untergrenze aussieht. Man sollte existieren, wenn die Hoefding-Grenze eng ist (und ich denke, das ist es). Diese Grenze besagt, dass für 1 fn, wenn die Fehlerwahrscheinlichkeit p ist, Sie höchstens

Stichproben benötigen , um p auf Fehler + -

whp zu schätzen. Betrachten Sie also jede Konzeptklasse mit 2 Konzepten.

und

und VC-Dimension 2. Nehmen Sie eine Verteilung über Beispiele, so dass

(oder umgekehrt) - dies ist möglich, weil die VC-Dimension 2 ist. Es scheint, dass ein Algorithmus nur

m = O (1 / ϵ^{2})

$m = O(1/\epsilon^2)$

ϵ

$\epsilon$

f_{1}

$f_1$

f_{2}

$f_2$

p_{1} = p_{2} + ϵ

$p_1 = p_2 + \epsilon$

Beispiele würden eine verbesserte Hoefding-Bindung implizieren.

O (1 / ϵ)

$O(1/\epsilon)$

Aaron Roth

Das heißt, ich glaube , das Hoeffding gebunden dicht ist bei

für

. Ich denke, die obigen Überlegungen sind allgemein bekannt ...

p = 1 / 2

$p=1/2$

O (1 / ϵ^{2})

$O(1/\epsilon^2)$

Lev Reyzin

OK - es sieht so aus, als hätte ich noch eine Übung für den ML-Kurs ... :) Danke für die Eingabe, Aaron und Lev!

Aryeh

@ Aaron, vielleicht hätte das eine Antwort sein sollen.

Suresh Venkat

Antworten:

Mir ist jetzt klar, dass Anthony und Bartlett tatsächlich eine Untergrenze festgelegt haben (siehe die Präsentation hier ).

Bearbeiten 24-Sep-2018. Diese Frage hat mich all die Jahre beschäftigt, und kürzlich haben I. Pinelis und ich die exakte optimale Konstante in der unteren Grenze des agnostischen PAC erhalten , die in Ann erscheint. Stat .

Aryeh
quelle

In Ihrem Artikel zitieren Sie diese Arbeit nicht ( jmlr.org/papers/volume17/15-389/15-389.pdf ). Hat die optimale Komplexität der Stichproben im realisierbaren Fall keine Verbindung zu Ihrer Arbeit? Sind diese entsprechenden Obergrenzen für die optimale Probenkomplexität für den agnostischen Fall bekannt?

gradstudent

Ich denke nicht, dass der realisierbare Fall alles ist, was damit zusammenhängt. Im realisierbaren Fall garantiert ERM keine optimalen Raten - daher mussten Hanneke und andere die ganze harte Arbeit aufwenden, um den Log-Faktor zu entfernen, und es ist immer noch unbekannt, ob ein geeigneter Lernender die optimale Rate erreichen kann. Im Gegensatz dazu ist im agnostischen Fall seit langem bekannt, dass ERM die optimale Rate erreicht.

Aryeh