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

13

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

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

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

  • Есть ли лучший "тривиальный" тест для всех свойств распространения?
  • Существуют ли какие-либо свойства распределения, для которых мы знаем выборочные нижние оценки сильнее линейных?
Йонатан
источник
похоже на доказательство разделения классов сложности и похоже, что это может быть близко к известной открытой проблеме ...?
ВЗН
Только видел это ... Я не совсем уверен , как вы вывели связанный , но учтите , что на самом деле обучение распределений (над областью размера п ) к TV / 1 расстояние е с вероятностью 2 / 3 на самом деле может быть сделано с O ( n / ε 2 ) образцов (и это плотно). Поэтому, если вы не посмотрите на непостоянные значения параметра близости ε , нет никакой надежды получить ω ( n ) нижних границ ...O(n2logn)n1ε2/3O(n/ε2)εω(n)
Клемент С.

Ответы:

5

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

Во-первых, похоже, что вы выполнили привязку по Чернову с некоторыми странными настройками параметров. Обратите внимание, что для выполнения предложенного вами подхода «тестирование с помощью обучения» достаточно изучить распределение по общему расстоянию изменения (или , если вы предпочитаете, что одинаково с точностью до множителя 2) для расстояния ε.1 . (перед проверкой "офлайн", если есть какое-либо распределениеp',имеющее свойствоPn,которое само находится на расстоянии не болееεε2pPn из вашей гипотезы узнали р ). Это наивно привело бы кO(nlognε2p^верхняя граница сложности образца для этого подхода; однако известно (и «фольклор»), что изучение произвольного распределения в области размераnдо расстоянияε(в общем расстоянии изменения) может быть выполнено только сO(nO(nlognε2)nεобразцы (и это плотно).O(nε2)

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

Ответ (насколько я знаю) «не совсем, но близко». А именно, после значительной работы по оценке свойств распределений (или, что то же самое, тестированию допустимых свойств), результаты Valiant и Valiant предполагают (STOCS'11, FOCS'11 и некоторые другие), что довольно надуманным свойством "является близко к униформе» имеет сложность выборки Θ ε ( n1/10.Θε(nlogn)

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

kkk=n/10Ω(nlogn)n100

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