Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications

Abstract

In this work, we study a novel class of projection-based algorithms for linearly constrained problems (LCPs) which have a lot of applications in statistics, optimization, and machine learning. Conventional primal gradient-based methods for LCPs call a projection after each (stochastic) gradient descent, resulting in that the required number of projections equals that of gradient descents (or total iterations). Motivated by the recent progress in distributed optimization, we propose the delayed projection technique that calls a projection once for a while, lowering the projection frequency and improving the projection efficiency. Accordingly, we devise a series of stochastic methods for LCPs using the technique, including a variance reduced method and an accelerated one. We theoretically show that it is feasible to improve projection efficiency in both strongly convex and generally convex cases. Our analysis is simple and unified and can be easily extended to other methods using delayed projections. When applying our new algorithms to federated optimization, a newfangled and privacy-preserving subfield in distributed optimization, we obtain not only a variance reduced federated algorithm with convergence rates better than previous works, but also the first accelerated method able to handle data heterogeneity inherent in federated optimization.

References in corpus (26)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning with Non-IID Data
• On the Convergence of FedAvg on Non-IID Data
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Federated Optimization in Heterogeneous Networks
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• A Universal Catalyst for First-Order Optimization
• On the Convergence of Local Descent Methods in Federated Learning
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Communication Complexity of Distributed Convex Learning and Optimization
• Optimization with First-Order Surrogate Functions
• AIDE: Fast and Communication Efficient Distributed Optimization
• Variance Reduced Local SGD with Lower Communication Complexity
• FedSplit: An algorithmic framework for fast federated optimization
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Adding vs. Averaging in Distributed Primal-Dual Optimization
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Optimal Black-Box Reductions Between Optimization Objectives
• Is Local SGD Better than Minibatch SGD?
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• ASVRG: Accelerated Proximal SVRG
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization

Cited by in corpus (1)

• FedPower: Privacy-Preserving Distributed Eigenspace Estimation