Communication Efficient Distributed Optimization using an Approximate Newton-type Method
Ohad Shamir, Nathan Srebro, Tong Zhang · arXiv (Cornell University) · 2013
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 \emph{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.
Cited by 354 works. doi:10.48550/arxiv.1312.7853 Open-access PDF
Authors
References
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Parallelized Stochastic Gradient Descent
- Problem complexity and method efficiency in optimization
- Mirror descent and nonlinear projected subgradient methods for convex optimization
- A Reliable Effective Terascale Linear Learning System
- Stochastic dual coordinate ascent methods for regularized loss
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- Better Mini-Batch Algorithms via Accelerated Gradient Methods