CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity
Not on the map. Why?
Abstract (arXiv)
With distributed machine learning being a prominent technique for large-scale machine learning tasks, communication complexity has become a major bottleneck for speeding up training and scaling up machine numbers. In this paper, we propose a new technique named Common randOm REconstruction(CORE), which can be used to compress the information transmitted between machines in order to reduce communication complexity without other strict conditions. Especially, our technique CORE projects the vector-valued information to a low-dimensional one through common random vectors and reconstructs the information with the same random noises after communication. We apply CORE to two distributed tasks, respectively convex optimization on linear models and generic non-convex optimization, and design new distributed algorithms, which achieve provably lower communication complexities. For example, we show for linear models CORE-based algorithm can encode the gradient vector to O(1)-bits (against O(d)), with the convergence rate not worse, preceding the existing results.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 49 of its 74 references that are in the map. First posted on arXiv 23 Sep 2023.
Builds on
49 of 74 references.
References · 49
- 2015Deep Residual Learning for Image Recognitioncited by 51,809
- 2018Large Scale GAN Training for High Fidelity Natural Image Synthesiscited by 2,609
- 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
- 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
- 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 471
- 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
- 2019An Investigation into Neural Net Optimization via Hessian Eigenvalue Densitycited by 289
- 2014Sketching as a Tool for Numerical Linear Algebracited by 285
- 2017Empirical Analysis of the Hessian of Over-Parametrized Neural Networkscited by 283
- 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
- 2017Sparse Communication for Distributed Gradient Descentcited by 243
- 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 234
37 more
- 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 199
- 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 178
- 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
- 2016Eigenvalues of the Hessian in Deep Learning: Singularity and Beyondcited by 156
- 2020On Biased Compression for Distributed Learningcited by 140
- 2018ATOMO: Communication-efficient Learning via Atomic Sparsificationcited by 135
- 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
- 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
- 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
- 2019Distributed Learning with Compressed Gradient Differencescited by 110
- 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 98
- 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
- 2019Natural Compression for Distributed Deep Learningcited by 88
- 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
- 2019Communication-efficient distributed SGD with Sketchingcited by 81
- 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
- 2018Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimizationcited by 76
- 20211-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speedcited by 74
- 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
- 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
- 2015A Universal Catalyst for First-Order Optimizationcited by 54
- 2018Distributed learning with compressed gradientscited by 53
- 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
- 2021DRIVE: One-bit Distributed Mean Estimationcited by 52
- 2020Adaptive Gradient Quantization for Data-Parallel SGDcited by 43
- 2019A Distributed Synchronous SGD Algorithm with Global Top-k Sparsification for Low Bandwidth Networkscited by 36
- 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
- 2022EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compressioncited by 28
- 20223PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregationcited by 27
- 2015Even Faster Accelerated Coordinate Descent Using Non-Uniform Samplingcited by 23
- 2021CANITA: Faster Rates for Distributed Convex Optimization with Communication Compressioncited by 23
- 2021Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimizationcited by 21
- 2022GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexitycited by 17
- 2022DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronizationcited by 15
- 2021When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpointcited by 12
- 2023Zeroth-order Optimization with Weak Dimension Dependencycited by 11
- 2020Sketching Datasets for Large-Scale Learning (long version)cited by 6
Built on by
Citing papers per year: 2024: 1.
1 paper.