Analyse et Accélération des Descentes de Gradient et des Algorithmes de Gossip

Motivated by the recent interest in statistical learning and distributed computing, we study stochastic convex optimization and gossip algorithms in parallel. This joint study is enabled by rigorous relationships that are made between the structures of optimization problems and their equivalents for gossip algorithms. The strong convexity of an optimization problem corresponds to the spectral gap between the two smallest eigenvalues of the graph Laplacian for gossip algorithms. The capacity and source conditions of a least-squares problem, that describe power-law scalings for the eigenvalues and for the projection of the optimum against the eigenvectors, correspond to the spectral dimension of the graph for gossip algorithms.In this common framework, our first contribution is to study the convergence rates of naive algorithms: stochastic gradient descent and the simple gossip algorithm. We largely focus on obtaining non-parametric rates in the noiseless case, typical of interpolation problems. As the naive methods prove to be suboptimal, we propose two new techniques to accelerate them.First, we propose so-called continuized accelerations to tackle the problem of asynchrony in accelerating distributed algorithms, like gossip algorithms. We model this asynchrony by assuming that communications and gradient steps happen at random times, and we adapt classical accelerations to this setting. Interestingly, the resulting continuized framework gives an insightful perspective even on the classical centralized acceleration of Nesterov.Second, we propose an acceleration of gossip algorithms—called the Jacobi Polynomial Iteration—depending on the spectral dimension of the communication network. This contrasts with previous accelerations based on the spectral gap; taking into account the spectral dimension brings a significant improvement on large networks, in the non-asymptotic regime. This acceleration is derived in two different ways: using parallel techniques in optimization called polynomial-based iterative methods, or through its scaling on large graphs to a partial differential equation that mixes quickly.Motivés par l’intérêt récent porté à l’apprentissage statistque et au calcul distribué, nous étudions l’optimisation convexe stochastique et les algorithmes de gossip en parallèle. Cette étude jointe est rendue possible grâce à des relations rigoureuses qui sont faites entre les structures de problèmes d’optimisation et leurs équivalents pour les algorithmes de gossip. La forte convexité d’un problème d’optimisation correspond au trou spectral entre les deux plus petites valeurs propes du Laplacien pour les algorithmes de gossip. Les conditions de capacité et de source d’un problème de moindres carrés, qui décrivent les lois de puissance des valeurs propres et de la projection de l’optimum sur les vecteurs propres, correspondent à la dimension spectrale du graphe pour les algorithmes de gossip.Dans ce cadre commun, notre première contribution est d’étudier les vitesses de convergence des algorithmes naïfs : la descente de gradient stochastique et l’algorithme de gossip simple. On se concentre principalement sur l’obtention de taux non-paramétriques dans le cas sans bruit additif, qui est typique des problèmes d’interpolation.Comme les méthodes naïves se révèlent être sous-optimales, nous proposons deux techniques pour les accélérer.Premièrement, nous proposons des accélérations dites continuisées pour résoudre le problème de l’asynchronie dans l’accélération des algorithmes distribués tels que les algorithmes de gossip. Nous modélisons cette asynchronie en faisant l’hypothèses que les communications et les pas de gradient ont lieu à des instants aléatoires, et nous adaptons les accélérations classiques à ce scénario. Curieusement, ce cadre continuisé apporte une perspective intuitive même pour l’accélération centralisée classique de Nesterov.Deuxièmement, nous proposons une accélération des algorithmes de gossip, appelée itération des polynômes de Jacobi, qui dépend de la dimension spectrale du réseau de communication. Cela contraste avec les accélérations précédentes basées sur le trou spectral ; prendre en compte la dimension spectrale apporte une amélioration significative sur des grands réseaux, dans un régime non-asymptotique. Cette accélération est construite de deux manières différentes : en utilisant des techniques parallèles en optimisation appelées méthodes itératives par polynômes, et au travers de sa limite d’échelle sur des grands graphes vers une équation aux dérivées partielles qui mélange rapidement