Существуют ли свойства распределения, которые «максимально» сложно проверить?

Алгоритм тестирования распределения для свойства распределения P (которое является лишь некоторым подмножеством всех распределений по [n]) разрешает доступ к выборкам в соответствии с некоторым распределением D и должен решить (whp), если или ( здесь, как правило, расстояние). Наиболее распространенным показателем сложности является количество выборок, используемых алгоритмом. $D\in P$ $d(D,P)>\epsilon$ $d$ $\ell_1$

Теперь в стандартном тестировании свойств, где у вас есть доступ к какому-либо объекту, линейная нижняя граница сложности запроса, очевидно, является самой сильной из возможных нижних границ, поскольку при запросах будет открыт весь объект. Это касается и дистрибутивного тестирования? $n$

Насколько я понимаю, «тривиальная» верхняя граница для проверки свойств распределений равна --- по оценкам Чернова, этого достаточно, чтобы «записать» распределение D ', близкое к D на расстоянии , и тогда мы можем просто проверить, есть ли какие-либо распределения, близкие к D ', которые находятся в P (это может занять бесконечное время, но это не имеет отношения к сложности выборки). $O(n^2\log n)$ $\ell_1$

Есть ли лучший "тривиальный" тест для всех свойств распространения?
Существуют ли какие-либо свойства распределения, для которых мы знаем выборочные нижние оценки сильнее линейных?

cc.complexity-theory machine-learning query-complexity property-testing Йонатан
источник

похоже на доказательство разделения классов сложности и похоже, что это может быть близко к известной открытой проблеме ...?

ВЗН

Только видел это ... Я не совсем уверен , как вы вывели связанный

, но учтите , что на самом деле обучение распределений (над областью размера

) к TV /

расстояние

с вероятностью

на самом деле может быть сделано с

образцов (и это плотно). Поэтому, если вы не посмотрите на непостоянные значения параметра близости

, нет никакой надежды получить

нижних границ ...

O (n^{2} \log n)

$O(n^2\log n)$

n

$n$

ℓ_{1}

$\ell_1$

ε

$\varepsilon$

2 / 3

$2/3$

O (n / ε^{2})

$O(n/\varepsilon^2)$

ε

$\varepsilon$

ω (n)

$\omega(n)$

Клемент С.

Ответы:

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

Во-первых, похоже, что вы выполнили привязку по Чернову с некоторыми странными настройками параметров. Обратите внимание, что для выполнения предложенного вами подхода «тестирование с помощью обучения» достаточно изучить распределение по общему расстоянию изменения (или , если вы предпочитаете, что одинаково с точностью до множителя 2) для расстояния $\ell_1$ . (перед проверкой "офлайн", если есть какое-либо распределениеимеющее свойствокоторое само находится на расстоянии не более $\frac{\varepsilon}{2}$ $p'$ $\mathcal{P}_n$ из вашей гипотезы узнали ). Это наивно привело бы к $\frac{\varepsilon}{2}$ $\hat{p}$ верхняя граница сложности образца для этого подхода; однако известно (и «фольклор»), что изучение произвольного распределения в области размерадо расстояния(в общем расстоянии изменения) может быть выполнено только с $O\big(\frac{n\log n}{\varepsilon^2}\big)$ $n$ $\varepsilon$ образцы (и это плотно). $O(\frac{n}{\varepsilon^2})$

Таким образом, базовая линия должна быть на самом деле , которая уже линейна по. Теперь можно задать следующий вопрос -существуют ли «естественные» свойства, для которых проверка (скажем, на постоянную) требует линейной зависимости размера домена? $O(\frac{n}{\varepsilon^2})$ $n$ $\varepsilon$ $n$

Ответ (насколько я знаю) «не совсем, но близко». А именно, после значительной работы по оценке свойств распределений (или, что то же самое, тестированию допустимых свойств), результаты Valiant и Valiant предполагают (STOCS'11, FOCS'11 и некоторые другие), что довольно надуманным свойством "является близко к униформе» имеет сложность выборки $1/10$ . $\Theta_\varepsilon(\frac{n}{\log n})$

(Обратите внимание, что это немного «обман», в том смысле, что свойство - это просто способ ответить на вопрос о толерантности тестирования и переименовать его в тестирование свойства ad hoc ).

$k$ $k$ $k=n/10$ $\Omega(\frac{n}{\log n})$ $\frac{n}{100}$

Климент С.
источник