Continuized Accelerations of Deterministic and Stochastic Gradient Descents, and of Gossip Algorithms

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 powerlaw 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. Francis et Pierre, un grand merci pour votre encadrement bienveillant tout au long de cette expérience. Vous avez su me guider astucieusement tout en me laissant la dose d'exploration, de liberté et d'erreurs qui permettent de se construire une curiosité, un esprit critique et une modestie (respectivement). J'espère tirer le meilleur de votre enseignement et imiter votre pédagogie patiente et discrète à l'avenir. Ensuite, je remercie tous les membres du jury-Anatoli Judistky, Lorenzo Rosasco, Prateek Jain et Gabriel Peyré-qui me font l'honneur d'examiner ma thèse. Le précieux retour des rapporteurs m'a permis de mieux appréhender comment mes travaux pouvaient être reçus, et d'améliorer de nombreux points de ce manuscrit. Merci à Andrea Montanari et Gérard Ben Arous qui m'ont offert des expériences exceptionnelles de recherche à l'étranger. Ces voyages ont forgé ma motivation. Merci à l'équipe Willow-Sierra-Dyogene de l'Inria, où j'ai pu trouver d'excellents collaborateurs, des collègues extraordinaires pour demander un coup de pouce scientifique ou jouer avec une belle idée, mais aussi des complices pour m'initier à l'escalade, randonner dans les calanques à Marseille, se baigner dans une piscine de fluide non-Newtonien, mettre le plus de piment possible dans un banane plantain, etc. Vous restez le groupe qui a le plus déliré sur le jeu du "hip" (sans les dents), et pour moi ça veut dire beaucoup. J'ai aussi eu l'immense chance de rencontrer un autre cluster de l'Inria-la "team admin" dans ma tête-qui a su apporter de la légèreté et une autre forme de gossip à une thèse avec ses inévitables hauts et bas. Je m'excuse encore une fois auprès de Julien et Antoine pour les nombreuses défaites qu'ils ont dû essuyer contre Loucas et moi au babyfoot ; l'humiliation n'était pas intentionnelle. Mais bref, merci à tous d'avoir été aussi joyeux et généreux. Enfin, merci à mes (autres) amis et à ma famille, pour votre présence et votre soutien constant. Acknowledgements. This thesis was funded by Inria and the DGA.