Timezone: »
Oral
Distributed Learning with Sublinear Communication
Jayadev Acharya · Christopher De Sa · Dylan Foster · Karthik Sridharan
In distributed statistical learning, $N$ samples are split across $m$ machines and a learner wishes to use minimal communication to learn as well as if the examples were on a single machine.
This model has received substantial interest in machine learning due to its scalability and potential for parallel speedup. However, in the high-dimensional regime, where the number examples is smaller than the number of features (``dimension''), the speedup afforded by distributed learning may be overshadowed by the cost of communicating a single example. This paper investigates
the following question: When is it possible to learn a $d$-dimensional model in the distributed setting with total communication sublinear in $d$?
Starting with a negative result, we show that for learning the usual variants
of (sparse or norm-bounded) linear models, no algorithm can obtain optimal error
until communication is linear in dimension. Our main result is to show
that by slightly relaxing the standard statistical assumptions for
this setting we can obtain distributed algorithms that enjoy optimal
error and communication logarithmic in dimension. Our upper
bounds are based on family of algorithms that combine mirror descent
with randomized sparsification/quantization of iterates, and extend to
the general stochastic convex optimization model.
Author Information
Jayadev Acharya (Cornell University)
Christopher De Sa (Cornell)
Dylan Foster (MIT)
Karthik Sridharan (Cornell University)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Distributed Learning with Sublinear Communication »
Thu. Jun 13th 01:30 -- 04:00 AM Room Pacific Ballroom #181
More from the Same Authors
-
2021 : Remember What You Want to Forget: Algorithms for Machine Unlearning »
Ayush Sekhari · Ayush Sekhari · Jayadev Acharya · Gautam Kamath · Ananda Theertha Suresh -
2022 : Interaction-Grounded Learning with Action-inclusive Feedback »
Tengyang Xie · Akanksha Saran · Dylan Foster · Lekan Molu · Ida Momennejad · Nan Jiang · Paul Mineiro · John Langford -
2023 Poster: Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL »
Zakaria Mhammedi · Dylan Foster · Alexander Rakhlin -
2023 Poster: Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games »
Dylan Foster · Noah Golowich · Sham Kakade -
2023 Oral: Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL »
Zakaria Mhammedi · Dylan Foster · Alexander Rakhlin -
2022 : MCTensor: A High-Precision Deep Learning Library with Multi-Component Floating-Point »
Tao Yu · Wentao Guo · Canal Li · Tiancheng Yuan · Christopher De Sa -
2022 Workshop: Updatable Machine Learning »
Ayush Sekhari · Gautam Kamath · Jayadev Acharya -
2022 : Riemannian Residual Neural Networks »
Isay Katsman · Eric Chen · Sidhanth Holalkere · Aaron Lou · Ser Nam Lim · Christopher De Sa -
2022 Poster: Contextual Bandits with Large Action Spaces: Made Practical »
Yinglun Zhu · Dylan Foster · John Langford · Paul Mineiro -
2022 Poster: Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation »
Chris Dann · Yishay Mansour · Mehryar Mohri · Ayush Sekhari · Karthik Sridharan -
2022 Spotlight: Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation »
Chris Dann · Yishay Mansour · Mehryar Mohri · Ayush Sekhari · Karthik Sridharan -
2022 Spotlight: Contextual Bandits with Large Action Spaces: Made Practical »
Yinglun Zhu · Dylan Foster · John Langford · Paul Mineiro -
2022 Poster: Low-Precision Stochastic Gradient Langevin Dynamics »
Ruqi Zhang · Andrew Wilson · Christopher De Sa -
2022 Spotlight: Low-Precision Stochastic Gradient Langevin Dynamics »
Ruqi Zhang · Andrew Wilson · Christopher De Sa -
2022 : Q&A II »
Dylan Foster · Alexander Rakhlin -
2022 : Bridging Learning and Decision Making: Part II »
Dylan Foster -
2022 : Q&A »
Dylan Foster · Alexander Rakhlin -
2022 Tutorial: Bridging Learning and Decision Making »
Dylan Foster · Alexander Rakhlin -
2021 Poster: Robust Testing and Estimation under Manipulation Attacks »
Jayadev Acharya · Ziteng Sun · Huanyu Zhang -
2021 Poster: Principal Bit Analysis: Autoencoding with Schur-Concave Loss »
Sourbh Bhadane · Aaron Wagner · Jayadev Acharya -
2021 Spotlight: Principal Bit Analysis: Autoencoding with Schur-Concave Loss »
Sourbh Bhadane · Aaron Wagner · Jayadev Acharya -
2021 Spotlight: Robust Testing and Estimation under Manipulation Attacks »
Jayadev Acharya · Ziteng Sun · Huanyu Zhang -
2021 Poster: Variance Reduced Training with Stratified Sampling for Forecasting Models »
Yucheng Lu · Youngsuk Park · Lifan Chen · Yuyang Wang · Christopher De Sa · Dean Foster -
2021 Spotlight: Variance Reduced Training with Stratified Sampling for Forecasting Models »
Yucheng Lu · Youngsuk Park · Lifan Chen · Yuyang Wang · Christopher De Sa · Dean Foster -
2021 Poster: Low-Precision Reinforcement Learning: Running Soft Actor-Critic in Half Precision »
Johan Björck · Xiangyu Chen · Christopher De Sa · Carla Gomes · Kilian Weinberger -
2021 Spotlight: Low-Precision Reinforcement Learning: Running Soft Actor-Critic in Half Precision »
Johan Björck · Xiangyu Chen · Christopher De Sa · Carla Gomes · Kilian Weinberger -
2021 Poster: Optimal Complexity in Decentralized Training »
Yucheng Lu · Christopher De Sa -
2021 Oral: Optimal Complexity in Decentralized Training »
Yucheng Lu · Christopher De Sa -
2020 Poster: Naive Exploration is Optimal for Online LQR »
Max Simchowitz · Dylan Foster -
2020 Poster: Improved Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance »
Blair Bilodeau · Dylan Foster · Daniel Roy -
2020 Poster: Moniqua: Modulo Quantized Communication in Decentralized SGD »
Yucheng Lu · Christopher De Sa -
2020 Poster: Logarithmic Regret for Adversarial Online Control »
Dylan Foster · Max Simchowitz -
2020 Poster: Context Aware Local Differential Privacy »
Jayadev Acharya · Kallista Bonawitz · Peter Kairouz · Daniel Ramage · Ziteng Sun -
2020 Poster: Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles »
Dylan Foster · Alexander Rakhlin -
2020 Poster: Differentiating through the Fréchet Mean »
Aaron Lou · Isay Katsman · Qingxuan Jiang · Serge Belongie · Ser Nam Lim · Christopher De Sa -
2019 Poster: Communication-Constrained Inference and the Role of Shared Randomness »
Jayadev Acharya · Clément Canonne · Himanshu Tyagi -
2019 Oral: Communication-Constrained Inference and the Role of Shared Randomness »
Jayadev Acharya · Clément Canonne · Himanshu Tyagi -
2019 Poster: Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters »
Jayadev Acharya · Ziteng Sun -
2019 Poster: SWALP : Stochastic Weight Averaging in Low Precision Training »
Guandao Yang · Tianyi Zhang · Polina Kirichenko · Junwen Bai · Andrew Wilson · Christopher De Sa -
2019 Poster: A Kernel Theory of Modern Data Augmentation »
Tri Dao · Albert Gu · Alexander J Ratner · Virginia Smith · Christopher De Sa · Christopher Re -
2019 Poster: Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints »
Andrew Cotter · Maya Gupta · Heinrich Jiang · Nati Srebro · Karthik Sridharan · Serena Wang · Blake Woodworth · Seungil You -
2019 Poster: Improving Neural Network Quantization without Retraining using Outlier Channel Splitting »
Ritchie Zhao · Yuwei Hu · Jordan Dotzel · Christopher De Sa · Zhiru Zhang -
2019 Oral: Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters »
Jayadev Acharya · Ziteng Sun -
2019 Oral: SWALP : Stochastic Weight Averaging in Low Precision Training »
Guandao Yang · Tianyi Zhang · Polina Kirichenko · Junwen Bai · Andrew Wilson · Christopher De Sa -
2019 Oral: Improving Neural Network Quantization without Retraining using Outlier Channel Splitting »
Ritchie Zhao · Yuwei Hu · Jordan Dotzel · Christopher De Sa · Zhiru Zhang -
2019 Oral: Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints »
Andrew Cotter · Maya Gupta · Heinrich Jiang · Nati Srebro · Karthik Sridharan · Serena Wang · Blake Woodworth · Seungil You -
2019 Oral: A Kernel Theory of Modern Data Augmentation »
Tri Dao · Albert Gu · Alexander J Ratner · Virginia Smith · Christopher De Sa · Christopher Re -
2018 Poster: Minibatch Gibbs Sampling on Large Graphical Models »
Christopher De Sa · Vincent Chen · Wong -
2018 Oral: Minibatch Gibbs Sampling on Large Graphical Models »
Christopher De Sa · Vincent Chen · Wong -
2018 Poster: Representation Tradeoffs for Hyperbolic Embeddings »
Frederic Sala · Christopher De Sa · Albert Gu · Christopher Re -
2018 Poster: Practical Contextual Bandits with Regression Oracles »
Dylan Foster · Alekh Agarwal · Miroslav Dudik · Haipeng Luo · Robert Schapire -
2018 Oral: Representation Tradeoffs for Hyperbolic Embeddings »
Frederic Sala · Christopher De Sa · Albert Gu · Christopher Re -
2018 Oral: Practical Contextual Bandits with Regression Oracles »
Dylan Foster · Alekh Agarwal · Miroslav Dudik · Haipeng Luo · Robert Schapire -
2018 Poster: INSPECTRE: Privately Estimating the Unseen »
Jayadev Acharya · Gautam Kamath · Ziteng Sun · Huanyu Zhang -
2018 Oral: INSPECTRE: Privately Estimating the Unseen »
Jayadev Acharya · Gautam Kamath · Ziteng Sun · Huanyu Zhang -
2017 Poster: A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions »
Jayadev Acharya · Hirakendu Das · Alon Orlitsky · Ananda Suresh -
2017 Talk: A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions »
Jayadev Acharya · Hirakendu Das · Alon Orlitsky · Ananda Suresh