A Stochastic Newton Algorithm for Distributed Convex Optimization

Abstract

We propose and analyze a stochastic Newton algorithm for homogeneous distributed stochastic convex optimization, where each machine can calculate stochastic gradients of the same population objective, as well as stochastic Hessian-vector products (products of an independent unbiased estimator of the Hessian of the population objective with arbitrary vectors), with many such stochastic computations performed between rounds of communication. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance, by proving convergence guarantees for quasi-self-concordant objectives (e.g., logistic regression), alongside empirical evidence.

References in corpus (11)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Optimal Distributed Online Prediction using Mini-Batches
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• AIDE: Fast and Communication Efficient Distributed Optimization
• First Analysis of Local GD on Heterogeneous Data
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• LocalNewton: Reducing Communication Bottleneck for Distributed Learning