DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate

Abstract

In this paper, we consider distributed algorithms for solving the empirical risk minimization problem under the master/worker communication model. We develop a distributed asynchronous quasi-Newton algorithm that can achieve superlinear convergence. To our knowledge, this is the first distributed asynchronous algorithm with superlinear convergence guarantees. Our algorithm is communication-efficient in the sense that at every iteration the master node and workers communicate vectors of size $O(p)$, where $p$ is the dimension of the decision variable. The proposed method is based on a distributed asynchronous averaging scheme of decision vectors and gradients in a way to effectively capture the local Hessian information of the objective function. Our convergence theory supports asynchronous computations subject to both bounded delays and unbounded delays with a bounded time-average. Unlike in the majority of asynchronous optimization literature, we do not require choosing smaller stepsize when delays are huge. We provide numerical experiments that match our theoretical results and showcase significant improvement comparing to state-of-the-art distributed algorithms.

References in corpus (13)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Communication Complexity of Distributed Convex Learning and Optimization
• Decentralized Quasi-Newton Methods
• AIDE: Fast and Communication Efficient Distributed Optimization
• Distributed Delayed Stochastic Optimization
• CoCoA: A General Framework for Communication-Efficient Distributed Optimization
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Adding vs. Averaging in Distributed Primal-Dual Optimization
• A globally convergent incremental Newton method
• Distributed Mini-Batch SDCA
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Distributed Stochastic Optimization via Adaptive SGD

Cited by in corpus (3)

• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• A Newton Tracking Algorithm with Exact Linear Convergence Rate for Decentralized Consensus Optimization
• L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method