О состоянии обучаемости внутри

Я пытаюсь понять сложность функций, которые можно выразить через пороговые элементы, и это привело меня к . В частности, мне интересно, что в настоящее время известно об обучении в , так как я не эксперт в этой области. $\mathsf{TC}^0$ $\mathsf{TC}^0$

На данный момент я обнаружил, что:

Все из могут быть изучены в квазиполиномиальное время при равномерном распределении через Линиал-Мансур-Нисан . $\mathsf{AC}^0$
В их статье также указывается, что существование генератора псевдослучайных функций препятствует обучению, и это, в сочетании с более поздним результатом Наора-Рейнгольда о том, что допускает PRFG, предполагает, что представляет пределы обучаемости (по крайней мере, в PAC-смысле) $\mathsf{TC}^0$ $\mathsf{TC}^0$
Есть статья Джексона / Кливанса / Серведио 2002 года, в которой можно выучить фрагмент (с большинством полилогарифмических контрольных элементов). $\mathsf{TC}^0$

Я сделал обычное изучение Google, но я надеюсь, что коллективная мудрость cstheory может иметь более быстрый ответ:

Является ли то, что я описал состояние техники для нашего понимания сложности обучения (с точки зрения того, какие классы сэндвич эффективные ученики)? И есть ли хороший обзор / ссылка, которая отображает текущее состояние ландшафта?

cc.complexity-theory reference-request cr.crypto-security lg.learning boolean-functions Суреш Венкат
источник

+1 Хороший вопрос. У Ланса не было связанного сообщения в блоге некоторое время назад?

Каве

Вы имеете в виду это (гостевой пост Райана О'Доннелла): blog.computationalcomplexity.org/2005/08/…

Суреш Венкат

Может быть, это: blog.computationalcomplexity.org/2013/08/…

Суреш Венкат

Возможно, в NC0 есть псевдослучайные генераторы .

$\:$ (В частности, я считаю очень маловероятным, что псевдослучайный генератор, как известно, предотвращает обучение.)

$\;\;\;$ С другой стороны, наличие карт

x \mapsto F (r, x)

$\: x\mapsto F(r\hspace{-0.03 in},x) \:$ для псевдослучайной функции семейство

препятствует обучению.

F

$F$

Линиал-Мансур-Нисан показывает, что

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

{AC}^{0}

$\text{AC}^0$

Робин Котари

Ответы:

Главное, чего не хватает в вашем списке, - это прекрасная газета 2006 года Кливанса и Шерстова . Они показывают, что PAC-обучение даже пороговых контуров глубины 2 так же сложно, как решить проблему приближенного кратчайшего вектора.

Скотт Ааронсон
источник

Какое самое быстрое время работы известно для изучения таких схем LTF? (или что-нибудь внутри

)

T C^{0}

$TC^0$

gradstudent

Depth-2 TC0, вероятно, не может быть изучен PAC за субэкспоненциальное время по равномерному распределению со случайным доступом оракула. Я не знаю ссылки на это, но вот мое рассуждение: мы знаем, что четность едва изучаема, в том смысле, что класс функций четности сам по себе обучаем, но как только вы сделаете что-нибудь с ним (например, добавляя немного случайного шума), он перестает быть обучаемым. Но TC0 глубины 2 достаточно силен, чтобы представлять все функции четности, и достаточно силен, чтобы представлять возмущенные версии четностей, поэтому я думаю, что можно с уверенностью предположить, что TC0 глубины 2 не может быть изучен PAC.

Тем не менее, паритеты и пики с шумом могут быть изучены за полиномиальное время, если нам дадут оракул членства. Так что было бы интересно проверить, можно ли узнать TC0 глубины-2 с помощью оракула членства. Я не был бы полностью удивлен, если ответ - да. С другой стороны, я сомневаюсь, что -глубина TC0 может быть изучена с помощью запросов членства. Было бы хорошо начать с AC0 [6] (или даже с AC0 [2]) и перейти оттуда. $O(1)$

пельмени мобиус
источник