Replicabilidad en Estadísticas de Alta Dimensión

La crisis de replicabilidad es un problema importante en casi todas las áreas de la ciencia empírica, lo que demanda el estudio formal de la replicabilidad en estadísticas. Motivados en este contexto, Impagliazzo, Lei, Pitassi y Sorrell STOC 2022 introdujeron la noción de algoritmos de aprendizaje replicables, y proporcionaron procedimientos básicos para tareas unidimensionales que incluyen consultas estadísticas. En este trabajo, estudiamos el costo computacional y estadístico de la replicabilidad para varias tareas fundamentales de estadísticas de alta dimensión, incluyendo pruebas de multi-hipótesis y estimación de medias. Nuestra principal contribución establece una equivalencia computacional y estadística entre algoritmos replicables óptimos y recubrimientos isoperimétricos de alta dimensión. Como consecuencia, obtenemos límites superiores e inferiores de complejidad de muestra coincidentes para la estimación replicable de medias de distribuciones con covarianza acotada, resolviendo un problema abierto de Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sivakumar y Sorrell, STOC2023, y para el Problema de N-Monedas, resolviendo un problema de Karbasi, Velegkas, Yang y Zhou, NeurIPS2023 hasta factores logarítmicos. Aunque nuestra equivalencia es computacional, lo que nos permite reducir factores logarítmicos en la complejidad de muestra de los mejores algoritmos eficientes conocidos, no se conocen recubrimientos isoperimétricos eficientes. Para sortear esto, introducimos varios paradigmas relajados que permiten algoritmos que son eficientes tanto en muestra como computacionalmente, incluyendo el preprocesamiento, adaptabilidad y replicabilidad aproximada. En estos casos, proporcionamos algoritmos eficientes que igualan o superan la mejor complejidad de muestra conocida para la estimación de medias y el problema de las monedas, incluyendo un procedimiento genérico que reduce el overhead cuadrático estándar de la replicabilidad a lineal en expectativa.