Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization

Hadrien Hendrikx, Lin Xiao, Sebastien Bubeck, Francis Bach, Laurent Massoulie
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:4203-4227, 2020.

Abstract

We consider the setting of distributed empirical risk minimization where multiple machines compute the gradients in parallel and a centralized server updates the model parameters. In order to reduce the number of communications required to reach a given accuracy, we propose a preconditioned accelerated gradient method where the preconditioning is done by solving a local optimization problem over a subsampled dataset at the server. The convergence rate of the method depends on the square root of the relative condition number between the global and local loss functions. We estimate the relative condition number for linear prediction models by studying uniform concentration of the Hessians over a bounded domain, which allows us to derive improved convergence rates for existing preconditioned gradient methods and our accelerated method. Experiments on real-world datasets illustrate the benefits of acceleration in the ill-conditioned regime.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-hendrikx20a, title = {Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization}, author = {Hendrikx, Hadrien and Xiao, Lin and Bubeck, Sebastien and Bach, Francis and Massoulie, Laurent}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {4203--4227}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/hendrikx20a/hendrikx20a.pdf}, url = {https://proceedings.mlr.press/v119/hendrikx20a.html}, abstract = {We consider the setting of distributed empirical risk minimization where multiple machines compute the gradients in parallel and a centralized server updates the model parameters. In order to reduce the number of communications required to reach a given accuracy, we propose a preconditioned accelerated gradient method where the preconditioning is done by solving a local optimization problem over a subsampled dataset at the server. The convergence rate of the method depends on the square root of the relative condition number between the global and local loss functions. We estimate the relative condition number for linear prediction models by studying uniform concentration of the Hessians over a bounded domain, which allows us to derive improved convergence rates for existing preconditioned gradient methods and our accelerated method. Experiments on real-world datasets illustrate the benefits of acceleration in the ill-conditioned regime.} }
Endnote
%0 Conference Paper %T Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization %A Hadrien Hendrikx %A Lin Xiao %A Sebastien Bubeck %A Francis Bach %A Laurent Massoulie %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-hendrikx20a %I PMLR %P 4203--4227 %U https://proceedings.mlr.press/v119/hendrikx20a.html %V 119 %X We consider the setting of distributed empirical risk minimization where multiple machines compute the gradients in parallel and a centralized server updates the model parameters. In order to reduce the number of communications required to reach a given accuracy, we propose a preconditioned accelerated gradient method where the preconditioning is done by solving a local optimization problem over a subsampled dataset at the server. The convergence rate of the method depends on the square root of the relative condition number between the global and local loss functions. We estimate the relative condition number for linear prediction models by studying uniform concentration of the Hessians over a bounded domain, which allows us to derive improved convergence rates for existing preconditioned gradient methods and our accelerated method. Experiments on real-world datasets illustrate the benefits of acceleration in the ill-conditioned regime.
APA
Hendrikx, H., Xiao, L., Bubeck, S., Bach, F. & Massoulie, L.. (2020). Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:4203-4227 Available from https://proceedings.mlr.press/v119/hendrikx20a.html.

Related Material