Communication Efficient Distributed Optimization using an Approximate Newton-type Method

2013/12/30 by Ohad Shamir, Nathan Srebro, Shamir, Ohad +3 · 11 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1312.7853

openalex publication_date 2013/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a novel Newton-type method for distributed optimization, which is particularly well suited for stochastic optimization and learning problems. For quadratic objectives, the method enjoys a linear rate of convergence which provably improves with the data size, requiring an essentially constant number of iterations under reasonable assumptions. We provide theoretical and empirical evidence of the advantages of our method compared to other approaches, such as one-shot parameter averaging and ADMM.

Citations

• A Parallel SGD method with Strong Convergence
• Making Gradient Descent Optimal for Strongly Convex Stochastic\n Optimization
• On the Linear Convergence of the Alternating Direction Method of Multipliers
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

Cited by

• Non-Convex Federated Optimization under Cost-Aware Client Selection
• HBNET-GIANT: A communication-efficient accelerated Newton-type fully distributed optimization algorithm
• Provable local acceleration in HbNet-GIANT: an accelerated Newton-type distributed optimization algorithm
• A Unified Convergence Analysis for Semi-Decentralized Learning: Sampled-to-Sampled vs. Sampled-to-All Communication
• CoCoL: A Communication Efficient Decentralized Collaborative Method for Multi-Robot Systems
• Convergence of Agnostic Federated Averaging
• A Fully Adaptive Frank-Wolfe Algorithm for Relatively Smooth Problems and Its Application to Centralized Distributed Optimization
• Centroid Approximation for Byzantine-Tolerant Federated Learning
• Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization
• Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization
• Accelerated Training of Federated Learning via Second-Order Methods

Related

• Weight Design of Distributed Approximate Newton Algorithms for\n Constrained Optimization
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Distributed Approximate Newton Algorithms and Weight Design for Constrained Optimization
• A Distributed Newton Method for Large Scale Consensus Optimization