Descenso-a-Borrar: Métodos Basados en Gradientes para el Desaprendizaje de Máquinas

Estudiamos el problema de eliminación de datos para modelos convexos. Al aprovechar técnicas de optimización convexa y muestreo por reservorio, presentamos los primeros algoritmos de eliminación de datos que son capaces de manejar una secuencia arbitrariamente larga de actualizaciones adversariales, garantizando tanto un tiempo de ejecución por eliminación como un error en estado estacionario que no crece con la longitud de la secuencia de actualizaciones. También introducimos varias nuevas distinciones conceptuales: por ejemplo, podemos pedir que después de una eliminación, todo el estado mantenido por el algoritmo de optimización sea estadísticamente indistinguible del estado que habría resultado si hubiéramos retrainado, o podemos pedir la condición más débil de que solo la salida observable sea estadísticamente indistinguible de la salida observable que habría resultado del retraining. Podemos proporcionar algoritmos de eliminación más eficientes bajo este criterio de eliminación más débil.