¿Hay propiedades de distribución que son "máximamente" difíciles de probar?

Un algoritmo de prueba de distribución para una propiedad de distribución P (que es solo un subconjunto de todas las distribuciones sobre [n]) puede acceder a las muestras de acuerdo con alguna distribución D, y se requiere que decida (whp) si $D\in P$ o $d(D,P)>\epsilon$ ( $d$ aquí suele ser la distancia ). La medida más común de complejidad es el número de muestras utilizadas por el algoritmo. $\ell_1$

Ahora, en las pruebas de propiedad estándar, donde tiene acceso de consulta a algún objeto, un límite inferior lineal en la complejidad de la consulta es obviamente el límite inferior más fuerte posible, ya que consultas revelarían todo el objeto. ¿Es este el caso de las pruebas de distribución también? $n$

Según tengo entendido, el límite superior "trivial" para probar las propiedades de las distribuciones es --- según los límites de Chernoff, esto es suficiente para "escribir" una distribución D 'que está cerca de D en distancia, y luego podemos verificar si hay distribuciones cercanas a D 'que están en P (esto puede tomar un tiempo infinito, pero esto es irrelevante para la complejidad de la muestra). $O(n^2\log n)$ $\ell_1$

¿Existe una mejor prueba "trivial" para todas las propiedades de distribución?
¿Hay alguna propiedad de distribución para la cual sepamos que los límites inferiores de la muestra son más fuertes que los lineales?

cc.complexity-theory machine-learning query-complexity property-testing Yonatan
fuente

parece similar a probar separaciones de clase de complejidad y podría estar cerca de algún problema abierto conocido ...?

vzn

Acabo de ver esto ... no estoy muy seguro de cómo se deriva el límite

, pero tenga en cuenta que en realidad las distribuciones de aprendizaje (más del dominio de tamaño

) a la TV /

distancia

con una probabilidad de

en realidad se puede hacer con muestras de

(y esto es estricto). Así que a menos que usted está buscando en los valores no constantes del parámetro de proximidad

, no hay ninguna esperanza de conseguir

los límites inferiores ...

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.

Respuestas:

Perdón por desenterrar esta publicación, es bastante antigua, pero pensé que tenerla respondida podría no ser una mala idea.

Primero, parece que realizaste tu límite de Chernoff con una configuración de parámetros ligeramente extraña. Tenga en cuenta que para realizar el enfoque sugerido de "prueba por aprendizaje", es suficiente aprender la distribución en la distancia de variación total (o , si lo prefiere, que es igual hasta un factor 2) a la distancia $\ell_1$ . (antes de marcar "fuera de línea" si hay alguna distribucióntenga la propiedadque a su vez esté a distancia como máximo $\frac{\varepsilon}{2}$ $p'$ $\mathcal{P}_n$ de su hipótesis aprendido ). Esto ingenuamente conduciría a una $\frac{\varepsilon}{2}$ $\hat{p}$ complejidad de muestra límite superior para este enfoque; sin embargo, se sabe (y "folklore") que aprender una distribución arbitraria sobre un dominio de tamañohasta la distancia(en la distancia de variación total) se puede hacer solo con $O\big(\frac{n\log n}{\varepsilon^2}\big)$ $n$ $\varepsilon$ muestras (y esto es ajustado). $O(\frac{n}{\varepsilon^2})$

Entonces la línea de base debería ser , que ya es lineal en. Ahora, uno puede hacer la siguiente pregunta:¿hay propiedades "naturales" para las cuales la prueba (digamos, para la constante) requiere una dependencia lineal en el tamaño del dominio? $O(\frac{n}{\varepsilon^2})$ $n$ $\varepsilon$ $n$

La respuesta es (hasta donde yo sé) "no del todo, pero cerca". Es decir, siguiendo una línea de trabajo significativa en la estimación de propiedades de distribuciones (o, de manera equivalente, pruebas de propiedades tolerantes), los resultados de Valiant y Valiant implican (STOCS'11, FOCS'11 y algunos otros) que la propiedad más bien artificial "es -close to uniform "tiene una complejidad muestral $1/10$ . $\Theta_\varepsilon(\frac{n}{\log n})$

(Tenga en cuenta que es un poco "trampa", en el sentido de que la propiedad es simplemente una forma de tomar una pregunta de prueba tolerante y volver a etiquetarla como prueba de una propiedad ad hoc ).

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

Clemente C.
fuente