Existe-t-il des propriétés de distribution qui sont «au maximum» difficiles à tester?

Un algorithme de test de distribution pour une propriété de distribution P (qui n'est qu'un sous-ensemble de toutes les distributions sur [n]) est autorisé à accéder aux échantillons en fonction d'une distribution D, et doit décider (whp) si ou ( voici généralement la distance ). La mesure de complexité la plus courante est le nombre d'échantillons utilisés par l'algorithme. $D\in P$ $d(D,P)>\epsilon$ $d$ $\ell_1$

Maintenant, dans les tests de propriétés standard, où vous avez accès à une requête à un objet, une limite inférieure linéaire sur la complexité de la requête est évidemment la borne inférieure la plus forte possible, car requêtes révéleraient l'objet entier. Est-ce également le cas pour les tests de distribution? $n$

Pour autant que je sache, la limite supérieure "triviale" pour tester les propriétés des distributions est --- par les limites de Chernoff, cela suffit pour "écrire" une distribution D 'qui est proche de D dans distance, et alors nous pouvons simplement vérifier s'il y a des distributions proches de D 'qui sont dans P (cela peut prendre un temps infini, mais ce n'est pas pertinent pour la complexité de l'échantillon). $O(n^2\log n)$ $\ell_1$

Existe-t-il un meilleur test «trivial» pour toutes les propriétés de distribution?
Existe-t-il des propriétés de distribution pour lesquelles nous savons que les limites inférieures de l'échantillon sont plus fortes que linéaires?

cc.complexity-theory machine-learning query-complexity property-testing Yonatan
la source

semble similaire à la preuve des séparations de classes de complexité et comme si cela pouvait être proche d'un problème ouvert connu ...?

vzn

Je viens de voir ça ... Je ne suis pas tout à fait sûr que vous tiriez la borne

, mais notez que les distributions d' apprentissage en fait (sur le domaine de la taille

) à la TV /

la distance

avec une probabilité

en fait peut être fait avec des échantillons

(et c'est serré). Donc, à moins que vous ne regardiez des valeurs non constantes du paramètre de proximité

, il n'y a aucun espoir d'obtenir des bornes inférieures

...

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

Clement C.

Réponses:

Désolé d'avoir déniché ce message - il est assez ancien, mais je me suis dit que la réponse à cette question n'était peut-être pas une si mauvaise idée.

Tout d'abord, il semble que vous ayez effectué votre liaison Chernoff avec un réglage légèrement étrange des paramètres. Notez que pour effectuer votre approche "test par apprentissage" suggérée, il suffit d'apprendre la distribution en distance de variation totale (ou , si vous préférez, qui est la même jusqu'à un facteur 2) à la distance $\ell_1$ . (avant de vérifier "hors ligne" s'il y a une distributionayant la propriétéqui elle-même est à distance au plus $\frac{\varepsilon}{2}$ $p'$ $\mathcal{P}_n$ à partirvotre hypothèse appris ). Cela conduirait naïvement à un $\frac{\varepsilon}{2}$ $\hat{p}$ la complexité de l'échantillon limite supérieure pour cette approche; cependant, il est connu (et "folklore") que l'apprentissage d'une distribution arbitraire sur un domaine de taillejusqu'à la distance(dans la distance de variation totale) ne peut se faire qu'avec $O\big(\frac{n\log n}{\varepsilon^2}\big)$ $n$ $\varepsilon$ échantillons (et c'est serré). $O(\frac{n}{\varepsilon^2})$

Ainsi, la ligne de base devrait en fait être , qui est déjà linéaire en. Maintenant, on peut se poser la question suivante -existe-t-il des propriétés "naturelles" pour lesquelles le test (par exemple, pour la constante) nécessite une dépendance linéaire dans la taille de domaine? $O(\frac{n}{\varepsilon^2})$ $n$ $\varepsilon$ $n$

La réponse est (pour autant que je sache) "pas tout à fait, mais proche". À savoir, à la suite d'une ligne de travail importante sur l'estimation des propriétés des distributions (ou de manière équivalente, des tests de propriété tolérants), les résultats de Valiant et Valiant impliquent (STOCS'11, FOCS'11 et quelques autres) que la propriété plutôt artificielle "étant -proche à uniforme "a une complexité d'échantillon $1/10$ . $\Theta_\varepsilon(\frac{n}{\log n})$

(Notez que c'est un peu "tricher", dans le sens où la propriété est simplement un moyen de prendre une question de test tolérante et de la renommer en testant une propriété ad hoc ).

Si cela n'est pas entièrement suffisant pour étancher votre soif, on peut aussi montrer que pour la propriété (naturelle?) D ' "être un histogramme" (la distribution est-elle constante par morceaux sur un ensemble de intervalles inconnus?), En fixant par exemple, donne également un $k$ $k$ $k=n/10$ borne inférieure(c'est dans un de mes papiers de 2016; la borne inférieure découle d'une réduction assez simple du résultat des Vaillants). Maintenant, si vous considérez "être un $\Omega(\frac{n}{\log n})$ -histogramme "pour être une propriété naturelle est à vous. $\frac{n}{100}$

Clement C.
la source