Communication Efficient Distributed Optimization using an Approximate Newton-type Method

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 (3)

• 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 (163)

• 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
• Communication Efficiency in Federated Learning: Achievements and Challenges
• Energy Efficient Federated Learning Over Wireless Communication Networks
• CSAFL: A Clustered Semi-Asynchronous Federated Learning Framework
• A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
• Tight Complexity Bounds for Optimizing Composite Objectives
• 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
• Distributed High-dimensional Regression Under a Quantile Loss Function
• Communication-Efficient Distributed Statistical Inference
• Stochastic, Distributed and Federated Optimization for Machine Learning
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Communication-Efficient Local Decentralized SGD Methods
• Distributed Inference for Linear Support Vector Machine
• Proximal-Proximal-Gradient Method
• Privacy Preservation in Federated Learning: An insightful survey from the GDPR Perspective
• Communication-Efficient Edge AI: Algorithms and Systems
• 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
• Distributed Kernel Ridge Regression with Communications
• Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients
• Communication trade-offs for synchronized distributed SGD with large step size
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• Distributed Multi-Task Learning with Shared Representation
• Distributed linear regression by averaging
• Blockchained On-Device Federated Learning
• DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
• Stochastic Nonconvex Optimization with Large Minibatches
• Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver
• Exploiting Unlabeled Data in Smart Cities using Federated Learning
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• Distributed Machine Learning via Sufficient Factor Broadcasting
• Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• rTop-k: A Statistical Estimation Approach to Distributed SGD
• Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
• Distributed Saddle-Point Problems Under Similarity
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Asynchronous Stochastic Proximal Optimization Algorithms with Variance Reduction
• Privacy-Preserving Blockchain Based Federated Learning with Differential Data Sharing
• FedMAX: Mitigating Activation Divergence for Accurate and Communication-Efficient Federated Learning
• A Distributed One-Step Estimator
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
• Local SGD: Unified Theory and New Efficient Methods
• Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent
• Stochastic Channel-Based Federated Learning for Medical Data Privacy Preserving
• Acceleration in Distributed Optimization under Similarity
• FedDANE: A Federated Newton-Type Method
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• On Data Dependence in Distributed Stochastic Optimization
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Superlinearly Convergent Asynchronous Distributed Network Newton Method
• Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
• Gradient Perturbation is Underrated for Differentially Private Convex Optimization
• Balancing Communication and Computation in Distributed Optimization
• Nested Distributed Gradient Methods with Adaptive Quantized Communication
• Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization?
• COKE: Communication-Censored Decentralized Kernel Learning
• Distributed Multitask Learning
• Federated and continual learning for classification tasks in a society of devices
• Distributed Estimation for Principal Component Analysis: an Enlarged Eigenspace Analysis
• A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
• Distributed Newton Can Communicate Less and Resist Byzantine Workers
• Delay Analysis of Wireless Federated Learning Based on Saddle Point Approximation and Large Deviation Theory
• 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
• On the Convergence of Nested Decentralized Gradient Methods with Multiple Consensus and Gradient Steps
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• LocalNewton: Reducing Communication Bottleneck for Distributed Learning
• Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets
• DINO: Distributed Newton-Type Optimization Method
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• Straggler-Agnostic and Communication-Efficient Distributed Primal-Dual Algorithm for High-Dimensional Data Mining
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Communication Efficient Parallel Algorithms for Optimization on Manifolds
• Bootstrap Model Aggregation for Distributed Statistical Learning
• Effective Parallelisation for Machine Learning
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
• Stochastic Gradient Made Stable: A Manifold Propagation Approach for Large-Scale Optimization
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• Trajectory Normalized Gradients for Distributed Optimization
• The Minimax Complexity of Distributed Optimization
• Model Aggregation via Good-Enough Model Spaces
• Asynchronous Federated Learning for Sensor Data with Concept Drift
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
• A general framework for decentralized optimization with first-order methods
• LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
• Distributed nonparametric regression imputation for missing response problems with large-scale data
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds
• FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization
• Probabilistic Federated Learning of Neural Networks Incorporated with Global Posterior Information
• Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization
• Machine Learning on Volatile Instances
• Scalable Approximate Inference and Some Applications
• Communication-Efficient Distributed Learning via Sparse and Adaptive Stochastic Gradient
• Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality
• CADA: Communication-Adaptive Distributed Adam
• Differential Privacy Meets Federated Learning under Communication Constraints
• 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
• A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization
• Distributed Bayesian Matrix Decomposition for Big Data Mining and Clustering
• HAMSI: A Parallel Incremental Optimization Algorithm Using Quadratic Approximations for Solving Partially Separable Problems
• Sparse sketches with small inversion bias
• Practical Newton-Type Distributed Learning using Gradient Based Approximations
• On Second-order Optimization Methods for Federated Learning
• L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
• Distributed Adaptive Huber Regression
• Linear Speedup in Personalized Collaborative Learning
• Newton Method over Networks is Fast up to the Statistical Precision
• Generalization Error Bounds for Optimization Algorithms via Stability
• Sensitivity Assisted Alternating Directions Method of Multipliers for Distributed Optimization and Statistical Learning
• Data Dependent Convergence for Distributed Stochastic Optimization
• A Fast Sampling Gradient Tree Boosting Framework
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters