Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
arXiv:1902.06332
Abstract
How can we efficiently mitigate the overhead of gradient communications in distributed optimization? This problem is at the heart of training scalable machine learning models and has been mainly studied in the unconstrained setting. In this paper, we propose Quantized-Frank-Wolfe (QFW), the first projection-free and communication-efficient algorithm for solving constrained optimization problems at scale. We consider both convex and non-convex objective functions, expressed as a finite-sum or more generally a stochastic optimization problem, and provide strong theoretical guarantees on the convergence rate of QFW. This is accomplished by proposing novel quantization schemes that efficiently compress gradients while controlling the noise variance introduced during this process. Finally, we empirically validate the efficiency of QFW in terms of communication and the quality of returned solution against natural baselines.
References in corpus (12)
- QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
- Sparsified SGD with Memory
- Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
- Convergence Rate of Frank-Wolfe for Non-Convex Objectives
- Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
- Variance-Reduced and Projection-Free Stochastic Optimization
- Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
- Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms
- Deep Frank-Wolfe For Neural Network Optimization
- A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
- Constrained Deep Learning using Conditional Gradient and Applications in Computer Vision
- Neural Conditional Gradients