Próbkowanie Agnostic PAC w dolnej granicy

Dobrze wiadomo, że do klasycznego uczenia się PAC, przykłady są konieczne, aby osiągnąć granicę błędu whp, gdzie jest wymiarem VC klasy koncepcyjnej. $\Omega(d/\varepsilon)$ $\varepsilon$ $d$

Czy wiadomo, że w przypadku agnostyki potrzebne są przykłady ? $\Omega(d/\varepsilon^2)$

lg.learning machine-learning

— Aryeh
źródło

Nie jestem pewien, jak wygląda dolna granica, należy istnieć, jeśli granica Hoefdinga jest ciasna (i chyba tak jest). To ograniczenie stwierdza, że dla 1 fn, jeśli prawdopodobieństwo błędu wynosi p, to potrzebujesz najwyżej próbek, aby oszacować p do błędu + - whp Więc rozważ dowolną klasę koncepcji z 2 koncepcje, i

i VC wymiaru 2. Należy się rozkład na przykładach, tak że

(lub vice versa) - jest to możliwe, ponieważ VC wymiar 2. wydaje się, że przy użyciu algorytmu tylko

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$

O (1 / ϵ)

$O(1/\epsilon)$ przykłady sugerują ulepszoną oprawę Hoefdinga.

— Aaron Roth,

Mianowicie, myślę Hoeffding jest związany mocno w

. Myślę, że powyższe rozumowanie jest ogólnie znane ...

p = 1 / 2

$p=1/2$

O (1 / ϵ^{2})

$O(1/\epsilon^2)$

— Lew Reyzin

OK - wygląda na to, że mam kolejne ćwiczenie na kurs ML ... :) Dzięki za wkład, Aaron i Lew!

— Aryeh

@Aaron, może to powinna być odpowiedź.

— Suresh Venkat

Teraz zdaję sobie sprawę, że Anthony i Bartlett ustalili dolną granicę (zobacz prezentację tutaj ).

Edytuj 24 września 2018 r. To pytanie zajmowało mnie przez te wszystkie lata, a ostatnio I. Pinelis i ja uzyskaliśmy dokładnie optymalną stałą w agnostycznym dolnym przedziale PAC, aby pojawić się w Ann. Stat .

— Aryeh
źródło

W swoim artykule nie cytujesz tej pracy ( jmlr.org/papers/volume17/15-389/15-389.pdf ). Czy optymalna złożoność próbki górnych granic w możliwym do zrealizowania przypadku nie ma żadnego związku z twoją pracą? Czy te odpowiadające optymalnej złożoności próbki górne granice są znane dla przypadku agnostycznego?

— gradstudent

Nie wydaje mi się, żeby możliwy do zrealizowania przypadek był z tym związany. W możliwym do zrealizowania przypadku ERM nie gwarantuje optymalnych stawek - stąd cała ciężka praca, jaką Hanneke i inni musieli poświęcić, aby usunąć współczynnik logarytmiczny, i nadal nie wiadomo, czy właściwy uczeń może osiągnąć optymalny wskaźnik. Przeciwnie, w przypadku agnostyki od dawna wiadomo, że ERM osiąga optymalną szybkość.

— Aryeh