Cómo Hacer que los Gradientes Pequeños Privadamente: Mejores Tasas para la Optimización No Convexa Diferencialmente Privada

Proporcionamos un marco simple y flexible para diseñar algoritmos diferencialmente privados que encuentran puntos estacionarios aproximados de funciones de pérdida no convexas. Nuestro marco se basa en usar un minimizador de riesgo aproximado privado para "iniciar" otro algoritmo privado para encontrar puntos estacionarios. Usamos este marco para obtener tasas mejoradas, y a veces óptimas, para varias clases de funciones de pérdida no convexas. Primero, obtenemos tasas mejoradas para encontrar puntos estacionarios de funciones de pérdida empírica no convexas suaves. En segundo lugar, nos especializamos en funciones cuasar-convexas, que generalizan las funciones estrella-convexas y surgen en el aprendizaje de sistemas dinámicos y en el entrenamiento de algunas redes neuronales. Logramos la tasa óptima para esta clase. En tercer lugar, presentamos un algoritmo óptimo para encontrar puntos estacionarios de funciones que satisfacen la condición de Kurdyka-Lojasiewicz (KL). Por ejemplo, las redes neuronales sobreparametrizadas a menudo satisfacen esta condición. Cuarto, proporcionamos nuevas tasas de vanguardia para puntos estacionarios de funciones de pérdida poblacional no convexas. Quinto, obtenemos tasas mejoradas para modelos lineales generalizados no convexos. Una modificación de nuestro algoritmo logra tasas casi iguales para puntos estacionarios de segundo orden de funciones con Hessiano Lipschitz, mejorando el estado del arte anterior para cada uno de los problemas mencionados.