Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization

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 \emph{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 \emph{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.

References in corpus (10)

• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• A Universal Catalyst for First-Order Optimization
• Communication Complexity of Distributed Convex Learning and Optimization
• AIDE: Fast and Communication Efficient Distributed Optimization
• Adding vs. Averaging in Distributed Primal-Dual Optimization
• SDCA without Duality, Regularization, and Individual Convexity
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond

Cited by in corpus (7)

• Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding
• Optimal Data Splitting in Distributed Optimization for Machine Learning
• Local Methods with Adaptivity via Scaling
• Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization
• Parallel and Distributed algorithms for ML problems
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning