Encuentre una argmax aproximada utilizando solo consultas máximas aproximadas

10

Considere el siguiente problema.

nv1,,vnRS{1,,n}maxiSvi

Este problema es fácil: podemos usar la búsqueda binaria para encontrar el argmax con consultas O(logn) . es decir, construir un árbol binario completo con n hojas correspondientes a los índices. Comienza en la raíz y camina hacia una hoja de la siguiente manera. En cada nodo, consulte el valor máximo en los subárboles derecho e izquierdo y luego muévase al niño en el lado con la respuesta más grande. Al llegar a una hoja, genera su índice.

La siguiente versión ruidosa de este problema apareció en mi investigación.

Hay n valores desconocidos v1,,vn . Se puede acceder a estos con consultas en las que se especifica un conjunto S{1,,n} y se devuelve una muestra de N(maxiSvi,1) . El objetivo es identificar i{1,,n} modo que E[vi]maxivi1 utilizando la menor cantidad de consultas posible. (Se espera más de la elección de i , que depende tanto de las monedas del algoritmo como de las respuestas de consulta ruidosas).

Supongamos que intentamos resolver esto usando la misma estrategia de búsqueda binaria que antes (pero con respuestas ruidosas). Es razonablemente fácil demostrar que esto logra y que esto es estricto en el peor de los casos. Podemos reducir el error al deseado repitiendo cada consulta veces y usando el promedio (que reduce la varianza). Esto proporciona un algoritmo que utiliza consultas .E[vi]maxiviO(logn)1O(log2n)O(log3n)

¿Hay un mejor algoritmo? Supongo que las consultas son suficientes. Y creo que puedo probar un límite inferior . Además, el problema se vuelve fácil, es decir, consultas de mediante búsqueda binaria, bajo la promesa de que hay una brecha de entre el valor más grande y el segundo valor más grande. Si ayuda, puede asumir que todos los valores están entre y .O(log2n)Ω(log2n)O~(logn)Ω(1)0O(logn)

Thomas
fuente
¿Qué pasa con una búsqueda binaria que en cada nivel hace pares de consultas O (log n) (uno para el máximo del lado izquierdo, uno para el máximo del lado derecho) y registra quién gana. Luego, después de que O (log n) se redondea, el algoritmo procede recursivamente del lado que "ganó" la mayoría de las veces. Un breve cálculo en mi cabeza parecía indicar que esto funcionaba con una probabilidad en la configuración donde una entrada es y todas las demás son ... aunque podría estar muy lejos. 11/nc20
daniello
@daniello Eso funciona cuando hay una brecha entre el mayor y el segundo mayor valor. Sin embargo, el caso general parece ser más difícil.
Thomas
Nota personal: lea la pregunta completa antes de comentar
daniello

Respuestas:

1

Comentario extendido de una idea o dos hacia un límite inferior. Deje , diga (aunque la mejor opción puede ser diferente), y deje . Considere dibujar la entrada seleccionando una permutación de estos valores de manera uniforme al azar.B=Θ(logn){v1,,vn}={1nB,,n1nB,B}

La idea debería ser que si fijamos los índices de todos los valores, excepto los valores y , entonces deberíamos poder mostrar la diferencia en la probabilidad del algoritmo de elegir uno versus el otro es muy pequeño: la distancia de variación entre los resultados de las consultas de los algoritmos es muy pequeña dada la distribución 50-50 de las asignaciones de estos valores a los dos índices disponibles y los resultados de cualquier secuencia de consultas.Bn1nB

Este argumento es válido para cada par de valores adyacentes, por lo que obtenemos una cadena de restricciones sobre la probabilidad de que el algoritmo elija los valores más altos, segundos más altos, ... Esto proporciona un límite superior en el valor esperado del algoritmo, por lo que establecemos ese límite superior en y vemos cuál debe ser el número de consultas.B1

Todavía no pude mejorar en con el enfoque anterior, pero creo que podría obtener si puede aprovechar el hecho de que las consultas no pueden ayudar con varios pasos a la vez. Es decir, si una consulta cambia cuando movemos el valor más alto a un índice diferente, entonces una de esas veces no cambia cuando movemos cualquier otro valor a un índice diferente.logn(logn)2

La privacidad diferencial podría ser útil para uno de estos pasos, por ejemplo, si solo pensamos en el caso en el que intercambiamos la ubicación de los dos valores más altos, la "sensibilidad" de esta consulta es solo y luego avanza La composición puede ser útil.Bn

Lo siento, esto está medio cocido, ¡pero espero que pueda ser útil!

usul
fuente
Realmente no he pensado mucho en los límites inferiores, ya que espero un límite superior. :) mantiene incluso en el caso silencioso. Creo que deberíamos poder probar un límite inferior . Ω(logn)Ω(log2n)
Thomas
OKAY. Tengo un boceto de un límite inferior , pero es un poco complicado. Ω(log2n)
Thomas