Untergrenze der agnostischen PAC-Probenahme

10

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

Ist bekannt, dass im agnostischen Fall Beispiele für benötigt werden?Ω(d/ε2)

Aryeh
quelle
3
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. f 1 und f 2 und VC-Dimension 2. Nehmen Sie eine Verteilung über Beispiele, so dass p 1 = p 2 + ϵ (oder umgekehrt) - dies ist möglich, weil die VC-Dimension 2 ist. Es scheint, dass ein Algorithmus nur O verwendetm=O(1/ϵ2)ϵf1f2p1=p2+ϵ Beispiele würden eine verbesserte Hoefding-Bindung implizieren. O(1/ϵ)
Aaron Roth
1
Das heißt, ich glaube , das Hoeffding gebunden dicht ist bei für O ( 1 / ε 2 ) . Ich denke, die obigen Überlegungen sind allgemein bekannt ...p=1/2O(1/ϵ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:

6

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