Acelerando la Optimización Distribuida: Una Perspectiva Primal-Dual sobre Pasos Locales

En el aprendizaje automático distribuido, el entrenamiento eficiente a través de múltiples agentes con diferentes distribuciones de datos presenta desafíos significativos. Incluso con un coordinador centralizado, los algoritmos actuales que logran una complejidad de comunicación óptima típicamente requieren ya sea grandes minibatches o comprometen la complejidad del gradiente. En este trabajo, abordamos tanto configuraciones centralizadas como descentralizadas en objetivos fuertemente convexos, convexos y no convexos. Primero demostramos que un método primal-dual básico, (Acelerado) Ascenso de Gradiente Múltiple con Descenso de Gradiente Estocástico (GA-MSGD), aplicado a la Lagrangiana de la optimización distribuida incorpora inherentemente actualizaciones locales, porque los bucles internos del Descenso de Gradiente Estocástico en la variable primal no requieren comunicación entre agentes. Notablemente, para objetivos fuertemente convexos, mostramos que (Acelerado) GA-MSGD logra una convergencia lineal en rondas de comunicación a pesar de que la Lagrangiana es solo lineal en las variables duales. Esto se debe a una propiedad estructural única donde la variable dual está confinada al span de la matriz de acoplamiento, lo que convierte al problema dual en fuertemente cóncavo. Cuando se integra con el marco Catalyst, nuestro enfoque logra una complejidad de comunicación casi óptima en varias configuraciones sin necesidad de minibatches. Además, en problemas estocásticos descentralizados, alcanza complejidades de comunicación comparables a las de configuraciones deterministas, mejorando sobre los algoritmos existentes.