Newton Method over Networks is Fast up to the Statistical Precision

Abstract

We propose a distributed cubic regularization of the Newton method for solving (constrained) empirical risk minimization problems over a network of agents, modeled as undirected graph. The algorithm employs an inexact, preconditioned Newton step at each agent's side: the gradient of the centralized loss is iteratively estimated via a gradient-tracking consensus mechanism and the Hessian is subsampled over the local data sets. No Hessian matrices are thus exchanged over the network. We derive global complexity bounds for convex and strongly convex losses. Our analysis reveals an interesting interplay between sample and iteration/communication complexity: statistically accurate solutions are achievable in roughly the same number of iterations of the centralized cubic Newton method, with a communication cost per iteration of the order of $\tilde{\mathcal{O}}(1/\sqrt{1-\rho })$, where $\rho$ characterizes the connectivity of the network. This demonstrates a significant communication saving with respect to that of existing, statistically oblivious, distributed Newton-based methods over networks.

arXiv commentIn proceedings of the 38th International Conference on Machine Learning, PMLR 139, 2021

References in corpus (13)

• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Communication Complexity of Distributed Convex Learning and Optimization
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• AIDE: Fast and Communication Efficient Distributed Optimization
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Recent theoretical advances in decentralized distributed convex optimization
• Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
• Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks