Estimando el promedio en tiempo polinomial

20

Sea sea ​​una función. Queremos estimar el promedio de ; es decir: .f E [ f ( n ) ] = 2 - nx { 0 , 1 } n f ( x )f:{0,1}n(2n,1]fE[f(n)]=2nx{0,1}nf(x)

NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if not, forget it!)

Sea el algoritmo estimador (aleatorio). Suponga que tiene acceso de caja negra a . Denotamos esto por .EEEfEf

Hay dos condiciones:

1) Tiempo de ejecución del estimador: existe un único polinomio tal que para todos y todos , el tiempo de ejecución de E f ( 1 n ) está limitado por p ( n )p()nfEf(1n)p(n)E[f(n)] .

2) Precisión del estimador con confianza δ : existe un solo polinomio q() , de modo que para todos n y todos f , tenemos 1q(n)<Ef(1n)E[f(n)]<q(n)con probabilidad de al menosδ.

NOTE: The confidence δ was not in the OP. The parameter δ is in (0,1), and may depend on n. For instance, it may be 1-1/2^n.

¿Existen tales estimadores?

Antecedentes y Motivación

No mencioné mi motivación al principio, ya que requiere una gran cantidad de conocimientos previos. De todos modos, para los entusiastas, lo describo brevemente: la necesidad de tales estimadores surge en el contexto de "Pruebas de capacidad", tal como se define en el siguiente artículo:

Mihir Bellare, Oded Goldreich. Prueba de capacidad computacional , 1992. Manuscrito no publicado.

Específicamente, en la parte inferior de la página 5, los autores asumieron implícitamente la existencia de tales estimadores (no se menciona la precisión y el tiempo de ejecución no está definido con precisión; sin embargo, el contexto define claramente todo).

Mi primer intento fue leer " Una muestra de muestreadores --- Una perspectiva computacional sobre el muestreo ". Se trata de un problema muy similar, pero la probabilidad de error definida es aditiva, mientras que la nuestra es multiplicativa. (No leí completamente el periódico, tal vez menciona lo que necesito en alguna parte).

EDITAR (según la solicitud de Tsuyoshi): de hecho, la definición de "Pruebas de capacidad computacional" requiere la existencia de un "extractor de conocimiento" cuyo tiempo de ejecución (esperado) es . Como no conocemosE[f(n)], queremos estimarlo; sin embargo, esto no debe cambiar el tiempo de ejecución considerablemente: debería cambiarlo a un factor polinómico. La condición de precisión intenta capturar tal requisito.p(n)E[f(n)]E[f(n)]

MS Dousti
fuente
No puedo entender la condición de precisión. ¿Qué impide que el algoritmo E emita siempre 1? ¿Quiso decir 1 / q (n) <(valor verdadero) / (valor estimado) <q (n)?
Tsuyoshi Ito
Parece que p (n) = q (n) = O (1) y el algoritmo trivial que genera "1" debería funcionar. Su tiempo de ejecución es O (1), que está limitado por p ( n )Ef(1n) . Y su precisión es <= 1, que es menor que q (n). p(n)E[f(n)]
Robin Kothari
@ Tsuyoshi y Robin: Lo siento muchachos, perdí una condición en la precisión. ¡Échale un vistazo ahora!
MS Dousti
Además, supongo que el estimador es aleatorio (solo porque parece imposible de lo contrario). ¿Es este el caso? Además, si es así, ¿qué requieren exactamente la condición de tiempo de ejecución y la condición de precisión?
Tsuyoshi Ito
1
Creo que no entiendo claramente la pregunta. ¿Por qué una muestra ingenua con un límite de chernoff no es un buen estimador?
Sylvain Peyronnet

Respuestas:

15

EDITAR: Esto resuelve la versión del problema donde f solo produce 0 o 1. Pero creo que la solución se puede adaptar para que funcione para el caso más general.

Tal vez no entendí bien la pregunta, pero esto no parece demasiado difícil.

En lugar de estimar el promedio, pensemos en estimar el número de 1s y llamar a ese número k. Deje . Entonces el promedio es k / N. Desea estimar esto dentro de un factor multiplicativo polinómico en el tiempo O (N polylog (N) / k).N=2n

Creo que esto también se puede hacer dentro de cualquier factor multiplicativo constante. Por ejemplo, supongamos que desea estimar esto dentro de un factor de 2. Por lo tanto, la salida del algoritmo estará entre k / 2 y 2k.k

Dibujaré un algoritmo, que debería tener el tiempo de ejecución apropiado. Primero verifique si k está entre N / 2 y N. Esto es fácil, solo muestree algunos valores aleatorios y si obtiene más de la mitad 1, entonces está en este intervalo. Entonces tienes una aproximación de 2. De lo contrario, verifique si está entre N / 4 y N / 2. Y así. Cada vez que reduce el intervalo, es más costoso estimar si k se encuentra en ese rango. Pero el costo es inversamente proporcional a lo pequeño que es el intervalo.

Por ejemplo, si está verificando si k está entre y 2 N / 2 q , entonces necesita hacer consultas sobre O ( 2 q ) . De todos modos, después de repetir este procedimiento suficientes veces, debe obtener el intervalo en el que se encuentra k. Digamos que k se encuentra entre N / 2 q y 2 N / 2 q . Entonces k es aproximadamente N / 2 q . Entonces 2 qN/2q2N/2qO(2q)N/2q2N/2qN/2q2qse trata de k / N. Entonces, en este paso, gastaríamos consultas O (k / N). Pero llegar a este paso requirió q otros pasos, pero eso es solo un factor polylog (N) adicional. Entonces, el tiempo de ejecución general es O (N polylog (N) / k), para una aproximación de 2.

(Uno realmente tendría que hacer una amplificación de error para obtener una precisión decente en cada paso. Pero eso es solo un factor adicional de polylog).


La razón por la que me gusta pensar en este proceso de varias etapas es que resalta el proceso como un proceso de conjetura y verificación. Si alguien le dijo que está entre N / 2 q y 2 n / 2 q , entonces podría estimarlo con mayor precisión sabiendo este hecho, en el tiempo prometido. Por lo tanto, debemos eliminar el paso de adivinar k . Esto se realiza mediante búsqueda binaria en todos los intervalos posibles de ese tipo.kN/2q2n/2qk

Para que esto funcione para el caso de salidas no booleanas, en lugar de contar el número de 1s, solo suma los valores vistos. Trataré de encontrar una referencia para demostrar que esto funciona rigurosamente.

Robin Kothari
fuente
(1) Dado que la función f puede tomar valores no integrales, probablemente desee usar la suma de los valores en lugar del número de 1s. (2) ¿Tenemos que estimar etapa por etapa? Supongo que podemos hacer esto en una sola etapa, solo repitiendo hasta que la suma exceda un polinomio fijo. Vea también mi comentario a la pregunta.
Tsuyoshi Ito
Oh, no noté que el rango es [0,1]. Pensé que era {0,1}. Pero supongo que el mismo procedimiento funciona. Tal vez podamos reducir un problema a otro ya que podemos "contar" el número de 1s en una posición particular de la representación binaria de la salida con suficiente precisión. Sobre (2), creo que su procedimiento es equivalente. Pienso en esto de esta manera, ya que se siente como un proceso de adivinar y verificar, es decir, dada una pésima estimación de k, obtenga una mejor. Agregaré esto a mi respuesta.
Robin Kothari
Estoy de acuerdo en que los dos algoritmos son esencialmente lo mismo. Además, en cuanto a [0,1] y {0,1}, su algoritmo probablemente funciona como se indica después de reemplazar cada evaluación de un valor no integral f (x) por un lanzamiento de moneda (1 wp f (x) y 0 wp 1 − f (x)).
Tsuyoshi Ito
@Robin: Gracias por la respuesta. Algo tampoco está claro para mí: Usted dijo: "Simplemente muestree algunos valores aleatorios y si obtiene más de la mitad 1, entonces está en este intervalo". Creo que esto debe cuantificarse: ¿cuántas muestras dan como resultado con qué precisión? (Cambié OP para considerar tal confianza. ¡De lo contrario, sería imposible diseñar la muestra requerida!)
MS Dousti
@Sadeq: eso es un límite de chernoff. si espera que k sea n / 2 (una moneda justa, por ejemplo), puede escribir rápidamente un límite de cola para ver más de n (1 + eps) / 2 y de manera similar para el límite inferior.
Suresh Venkat
3

Supongamos que denotan los valores de f aplicados a una secuencia infinita de muestras aleatorias (con reemplazo) de { 0 , 1 } n . Deje que k sea el número entero positivo tal que menos Σ k i = 1 f iM para algún valor M , quizás M = p o l y l o g ( n ) . Supongo que el estimador M /f1,f2,f{0,1}nki=1kfiMMM=polylog(n) debes lograr lo que quieres.M/k

Para el análisis, no puede aplicar los límites de Chernoff directamente a la variable aleatoria pero de todos modos hay un truco que le permite usar Chernoff. Supongamos que μ denota la expectativa desconocida E ( f ) . Encuentre las constantes k l o w y k h i g h (funciones de μ ) de modo que con probabilidad al menos 1 - δ tengamos k l o w i = 1 f i < M y k hkμE(f)klowkhighμ1δi=1klowfi<M. Esas sumas defis pueden acotarse usando Chernoff. Se deduce queklow<k<khighcon una probabilidad de al menos1-δy, por lo tanto, el estimadorM/kestá bien concentrado.i=1khighfi>Mfiklow<k<khigh1δM/k

Warren Schudy
fuente