Timezone: »
This paper presents a new class of gradient methods for distributed machine learning that adaptively skip the gradient calculations to learn with reduced communication and computation. Simple rules are designed to detect slowly-varying gradients and, therefore, trigger the reuse of outdated gradients. The resultant gradient-based algorithms are termed Lazily Aggregated Gradient --- justifying our acronym LAG used henceforth. Theoretically, the merits of this contribution are: i) the convergence rate is the same as batch gradient descent in strongly-convex, convex, and nonconvex cases; and, ii) if the distributed datasets are heterogeneous (quantified by certain measurable constants), the communication rounds needed to achieve a targeted accuracy are reduced thanks to the adaptive reuse of lagged gradients. Numerical experiments on both synthetic and real data corroborate a significant communication reduction compared to alternatives.
Author Information
Tianyi Chen (University of Minnesota)
Georgios Giannakis (University of Minnesota)
Tao Sun (National university of defense technology)
College of Science, National University of Defense Technology, PRC.
Wotao Yin (University of California, Los Angeles)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Spotlight: LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning »
Thu. Dec 6th 08:40 -- 08:45 PM Room Room 517 CD
More from the Same Authors
-
2021 Spotlight: Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems »
Tianyi Chen · Yuejiao Sun · Wotao Yin -
2022 Poster: Finite-Time Analysis of Adaptive Temporal Difference Learning with Deep Neural Networks »
Tao Sun · Dongsheng Li · Bao Wang -
2023 Poster: An Alternating Optimization Method for Bilevel Problems under the Polyak-Ćojasiewicz Condition »
Quan Xiao · Songtao Lu · Tianyi Chen -
2023 Poster: Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance »
Lisha Chen · Heshan Fernando · Yiming Ying · Tianyi Chen -
2023 Poster: Enhancing Sharpness-Aware Optimization Through Variance Suppression »
Bingcong Li · Georgios Giannakis -
2022 Poster: A Single-timescale Analysis for Stochastic Approximation with Multiple Coupled Sequences »
Han Shen · Tianyi Chen -
2022 Poster: Understanding Benign Overfitting in Gradient-Based Meta Learning »
Lisha Chen · Songtao Lu · Tianyi Chen -
2021 Poster: Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems »
Tianyi Chen · Yuejiao Sun · Wotao Yin -
2021 Poster: CAFE: Catastrophic Data Leakage in Vertical Federated Learning »
Xiao Jin · Pin-Yu Chen · Chia-Yi Hsu · Chia-Mu Yu · Tianyi Chen -
2021 Poster: Heavy Ball Momentum for Conditional Gradient »
Bingcong Li · Alireza Sadeghi · Georgios Giannakis -
2020 Poster: Decentralized TD Tracking with Linear Function Approximation and its Finite-Time Analysis »
Gang Wang · Songtao Lu · Georgios Giannakis · Gerald Tesauro · Jian Sun -
2019 Poster: General Proximal Incremental Aggregated Gradient Algorithms: Better and Novel Results under General Scheme »
Tao Sun · Yuejiao Sun · Dongsheng Li · Qing Liao -
2019 Poster: Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradients »
Jun Sun · Tianyi Chen · Georgios Giannakis · Zaiyue Yang -
2018 Poster: Breaking the Span Assumption Yields Fast Finite-Sum Minimization »
Robert Hannah · Yanli Liu · Daniel O'Connor · Wotao Yin -
2018 Poster: On Markov Chain Gradient Descent »
Tao Sun · Yuejiao Sun · Wotao Yin -
2018 Poster: Theoretical Linear Convergence of Unfolded ISTA and Its Practical Weights and Thresholds »
Xiaohan Chen · Jialin Liu · Zhangyang Wang · Wotao Yin -
2018 Spotlight: Theoretical Linear Convergence of Unfolded ISTA and Its Practical Weights and Thresholds »
Xiaohan Chen · Jialin Liu · Zhangyang Wang · Wotao Yin -
2017 Poster: Straggler Mitigation in Distributed Optimization Through Data Encoding »
Can Karakus · Yifan Sun · Suhas Diggavi · Wotao Yin -
2017 Poster: Asynchronous Coordinate Descent under More Realistic Assumptions »
Tao Sun · Robert Hannah · Wotao Yin -
2017 Spotlight: Straggler Mitigation in Distributed Optimization Through Data Encoding »
Can Karakus · Yifan Sun · Suhas Diggavi · Wotao Yin -
2017 Poster: Solving Most Systems of Random Quadratic Equations »
Gang Wang · Georgios Giannakis · Yousef Saad · Jie Chen -
2016 Poster: Solving Random Systems of Quadratic Equations via Truncated Generalized Gradient Flow »
Gang Wang · Georgios Giannakis