Communication Efficient Distributed Optimization using an Approximate Newton-type Method
arXiv:1312.7853
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 \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.
References in corpus (8)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Optimal Distributed Online Prediction using Mini-Batches
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- A Reliable Effective Terascale Linear Learning System
- Distributed Coordinate Descent Method for Learning with Big Data
- On the Linear Convergence of the Alternating Direction Method of Multipliers
- Better Mini-Batch Algorithms via Accelerated Gradient Methods
- A Parallel SGD method with Strong Convergence
Cited by in corpus (164)
- Federated Learning: Strategies for Improving Communication Efficiency
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- On the Convergence of FedAvg on Non-IID Data
- SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
- Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
- Communication-Efficient Federated Deep Learning with Asynchronous Model Update and Temporally Weighted Aggregation
- Federated Optimization:Distributed Optimization Beyond the Datacenter
- Federated Optimization in Heterogeneous Networks
- Fair Resource Allocation in Federated Learning
- A Crowdsourcing Framework for On-Device Federated Learning
- Gradient Sparsification for Communication-Efficient Distributed Optimization
- Byzantine Stochastic Gradient Descent
- A Field Guide to Federated Optimization
- Quantile Regression Under Memory Constraint
- Robust Federated Learning in a Heterogeneous Environment
- Overcoming Forgetting in Federated Learning on Non-IID Data
- FedGroup: Efficient Clustered Federated Learning via Decomposed Data-Driven Measure
- Communication Complexity of Distributed Convex Learning and Optimization
- Flexible Clustered Federated Learning for Client-Level Data Distribution Shift
- Federated Learning Based on Dynamic Regularization
- AIDE: Fast and Communication Efficient Distributed Optimization
- Distributed Learning with Compressed Gradient Differences
- Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
- The Non-IID Data Quagmire of Decentralized Machine Learning
- Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
- Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
- Distributed ARIMA Models for Ultra-long Time Series
- Joint Optimization of Communications and Federated Learning Over the Air
- FedSAE: A Novel Self-Adaptive Federated Learning Framework in Heterogeneous Systems
- Natural Compression for Distributed Deep Learning
- Adding vs. Averaging in Distributed Primal-Dual Optimization
- The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning
- A review of distributed statistical inference
- Energy Efficient Federated Learning Over Wireless Communication Networks
- Communication Efficiency in Federated Learning: Achievements and Challenges
- A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
- Tight Complexity Bounds for Optimizing Composite Objectives
- CSAFL: A Clustered Semi-Asynchronous Federated Learning Framework
- Asynchronous Federated Learning on Heterogeneous Devices: A Survey
- Is Local SGD Better than Minibatch SGD?
- Efficient Distributed Learning with Sparsity
- Second-Order Stochastic Optimization for Machine Learning in Linear Time
- Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
- A globally convergent incremental Newton method
- CONDENSE: A Reconfigurable Knowledge Acquisition Architecture for Future 5G IoT
- Stochastic, Distributed and Federated Optimization for Machine Learning
- Communication-Efficient Distributed Statistical Inference
- Distributed High-dimensional Regression Under a Quantile Loss Function
- GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
- Distributed Inference for Linear Support Vector Machine
- Communication-Efficient Local Decentralized SGD Methods
- Proximal-Proximal-Gradient Method
- Communication-Efficient Edge AI: Algorithms and Systems
- Privacy Preservation in Federated Learning: An insightful survey from the GDPR Perspective
- Prototype Guided Federated Learning of Visual Feature Representations
- Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
- FedCM: Federated Learning with Client-level Momentum
- Enhancing the Privacy of Federated Learning with Sketching
- Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis
- Gradient Diversity: a Key Ingredient for Scalable Distributed Learning
- Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
- Communication trade-offs for synchronized distributed SGD with large step size
- Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients
- Distributed Kernel Ridge Regression with Communications
- A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
- Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
- Distributed linear regression by averaging
- Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
- Distributed Multi-Task Learning with Shared Representation
- Blockchained On-Device Federated Learning
- DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
- Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
- Stochastic Nonconvex Optimization with Large Minibatches
- Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver
- Exploiting Unlabeled Data in Smart Cities using Federated Learning
- Distributed Machine Learning via Sufficient Factor Broadcasting
- FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
- Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference
- rTop-k: A Statistical Estimation Approach to Distributed SGD
- Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
- Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
- Distributed Second Order Methods with Fast Rates and Compressed Communication
- Distributed Saddle-Point Problems Under Similarity
- The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
- Privacy-Preserving Blockchain Based Federated Learning with Differential Data Sharing
- Asynchronous Stochastic Proximal Optimization Algorithms with Variance Reduction
- Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent
- FedMAX: Mitigating Activation Divergence for Accurate and Communication-Efficient Federated Learning
- On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
- A Distributed One-Step Estimator
- Local SGD: Unified Theory and New Efficient Methods
- Stochastic Channel-Based Federated Learning for Medical Data Privacy Preserving
- Acceleration in Distributed Optimization under Similarity
- Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
- On Data Dependence in Distributed Stochastic Optimization
- FedDANE: A Federated Newton-Type Method
- Superlinearly Convergent Asynchronous Distributed Network Newton Method
- Nested Distributed Gradient Methods with Adaptive Quantized Communication
- Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
- Balancing Communication and Computation in Distributed Optimization
- Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
- Gradient Perturbation is Underrated for Differentially Private Convex Optimization
- COKE: Communication-Censored Decentralized Kernel Learning
- Distributed Multitask Learning
- Federated and continual learning for classification tasks in a society of devices
- Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization?
- A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
- Distributed Estimation for Principal Component Analysis: an Enlarged Eigenspace Analysis
- 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
- Distributed Newton Can Communicate Less and Resist Byzantine Workers
- An efficient distributed learning algorithm based on effective local functional approximations
- Delay Analysis of Wireless Federated Learning Based on Saddle Point Approximation and Large Deviation Theory
- LocalNewton: Reducing Communication Bottleneck for Distributed Learning
- Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets
- On the Convergence of Nested Decentralized Gradient Methods with Multiple Consensus and Gradient Steps
- A Stochastic Newton Algorithm for Distributed Convex Optimization
- DINO: Distributed Newton-Type Optimization Method
- A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
- Straggler-Agnostic and Communication-Efficient Distributed Primal-Dual Algorithm for High-Dimensional Data Mining
- A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
- Effective Parallelisation for Machine Learning
- CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
- Communication-Efficient Distributed Optimization with Quantized Preconditioners
- Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds
- The Minimax Complexity of Distributed Optimization
- Asynchronous Federated Learning for Sensor Data with Concept Drift
- Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
- FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization
- Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
- Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
- LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
- A general framework for decentralized optimization with first-order methods
- Communication Efficient Parallel Algorithms for Optimization on Manifolds
- Distributed nonparametric regression imputation for missing response problems with large-scale data
- Model Aggregation via Good-Enough Model Spaces
- Trajectory Normalized Gradients for Distributed Optimization
- Bootstrap Model Aggregation for Distributed Statistical Learning
- Stochastic Gradient Made Stable: A Manifold Propagation Approach for Large-Scale Optimization
- Scalable Approximate Inference and Some Applications
- Probabilistic Federated Learning of Neural Networks Incorporated with Global Posterior Information
- Machine Learning on Volatile Instances
- Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization
- HAMSI: A Parallel Incremental Optimization Algorithm Using Quadratic Approximations for Solving Partially Separable Problems
- Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality
- Communication-Efficient Distributed Learning via Sparse and Adaptive Stochastic Gradient
- Distributed Bayesian Matrix Decomposition for Big Data Mining and Clustering
- A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization
- Communication-efficient Byzantine-robust distributed learning with statistical guarantee
- Efficient Estimation for Generalized Linear Models on a Distributed System with Nonrandomly Distributed Data
- Variance-Reduced Stochastic Learning by Networked Agents under Random Reshuffling
- Differential Privacy Meets Federated Learning under Communication Constraints
- CADA: Communication-Adaptive Distributed Adam
- Sparse sketches with small inversion bias
- Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
- On Second-order Optimization Methods for Federated Learning
- L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
- Sensitivity Assisted Alternating Directions Method of Multipliers for Distributed Optimization and Statistical Learning
- Practical Newton-Type Distributed Learning using Gradient Based Approximations
- Distributed Adaptive Huber Regression
- Linear Speedup in Personalized Collaborative Learning
- Newton Method over Networks is Fast up to the Statistical Precision
- Data Dependent Convergence for Distributed Stochastic Optimization
- Generalization Error Bounds for Optimization Algorithms via Stability
- A Fast Sampling Gradient Tree Boosting Framework