Нижняя граница выборки агностического PAC

Хорошо известно, что для классического обучения PAC необходимы примеры , чтобы получить границу ошибки whp, где - это VC-размерность концептуального класса. $\Omega(d/\varepsilon)$ $\varepsilon$ $d$

Известно ли, что примеры нужны в агностическом случае? $\Omega(d/\varepsilon^2)$

lg.learning machine-learning Арье
источник

Я не уверен, как выглядит нижняя граница, нужно существовать, если граница Хифдинга жесткая (и я думаю, что это так). Эта граница гласит, что для 1 fn, если вероятность ошибки равна p, вам нужно не более

выборок, чтобы оценить p с точностью до ошибки + -

whp

и VC-размерность 2. Возьмите распределение по примерам, чтобы

(или наоборот) - это возможно, потому что VC-размерность равна 2. Кажется, что алгоритм использует только

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)$

Аарон Рот

А именно, я считаю , что Хёфдинга оценка точна при

для

. Я думаю, что рассуждения выше общеизвестны ...

p = 1 / 2

$p=1/2$

O (1 / ϵ^{2})

$O(1/\epsilon^2)$

Лев Рейзин

ОК - похоже, у меня есть еще одно упражнение для курса ML ... :) Спасибо за вклад, Аарон и Лев!

Арье

@ Аарон, возможно, это должен был быть ответ.

Суреш Венкат

Ответы:

Теперь я понимаю, что Энтони и Бартлетт действительно установили нижнюю границу (см. Презентацию здесь ).

Изменить 24 сентября 2018 года. Этот вопрос занимал меня все эти годы, и недавно мы с И. Пинелисом получили точную оптимальную константу в нижней границе агностического PAC, которая должна появиться в Анне. Стат .

Арье
источник

В своей статье вы не цитируете эту работу ( jmlr.org/papers/volume17/15-389/15-389.pdf ). Является ли оптимальная сложность выборки верхним пределом в реализуемом случае не какой-либо связи с вашей работой? Известны ли эти соответствующие оптимальные верхние границы сложности выборки для агностического случая?

gradstudent

Я не думаю, что возможный случай связан со всем этим. В реализуемом случае ERM не гарантирует оптимальных показателей - следовательно, всю тяжелую работу, которую Ханнеке и другим пришлось потратить, чтобы убрать логарифмический коэффициент, и до сих пор неизвестно, сможет ли соответствующий ученик достичь оптимальной скорости. Наоборот, в агностическом случае давно известно, что ERM достигает оптимальной скорости.

Арье