This portal has been archived. Explore the next generation of this technology.
Variance Reduction with Sparse Gradients
lib:96873ce4e451f9a5 (v1.0.0)
Authors: Melih Elibol,Lihua Lei,Michael I. Jordan
Where published: ICLR 2020 1
ArXiv: 2001.09623
Document: PDF DOI
Abstract URL: https://arxiv.org/abs/2001.09623v1
Variance reduction methods such as SVRG and SpiderBoost use a mixture of large and small batch gradients to reduce the variance of stochastic gradients. Compared to SGD, these methods require at least double the number of operations per update to model parameters. To reduce the computational cost of these methods, we introduce a new sparsity operator: The random-top-k operator. Our operator reduces computational complexity by estimating gradient sparsity exhibited in a variety of applications by combining the top-k operator and the randomized coordinate descent operator. With this operator, large batch gradients offer an extra benefit beyond variance reduction: A reliable estimate of gradient sparsity. Theoretically, our algorithm is at least as good as the best algorithm (SpiderBoost), and further excels in performance whenever the random-top-k operator captures gradient sparsity. Empirically, our algorithm consistently outperforms SpiderBoost using various models on various tasks including image classification, natural language processing, and sparse matrix factorization. We also provide empirical evidence to support the intuition behind our algorithm via a simple gradient entropy computation, which serves to quantify gradient sparsity at every iteration.
Where published: ICLR 2020 1
ArXiv: 2001.09623
Document: PDF DOI
Abstract URL: https://arxiv.org/abs/2001.09623v1
Variance reduction methods such as SVRG and SpiderBoost use a mixture of large and small batch gradients to reduce the variance of stochastic gradients. Compared to SGD, these methods require at least double the number of operations per update to model parameters. To reduce the computational cost of these methods, we introduce a new sparsity operator: The random-top-k operator. Our operator reduces computational complexity by estimating gradient sparsity exhibited in a variety of applications by combining the top-k operator and the randomized coordinate descent operator. With this operator, large batch gradients offer an extra benefit beyond variance reduction: A reliable estimate of gradient sparsity. Theoretically, our algorithm is at least as good as the best algorithm (SpiderBoost), and further excels in performance whenever the random-top-k operator captures gradient sparsity. Empirically, our algorithm consistently outperforms SpiderBoost using various models on various tasks including image classification, natural language processing, and sparse matrix factorization. We also provide empirical evidence to support the intuition behind our algorithm via a simple gradient entropy computation, which serves to quantify gradient sparsity at every iteration.
Relevant initiatives
Related knowledge about this paper
Reproduced results (crowd-benchmarking and competitions)
Artifact and reproducibility checklists
- ACM/cTuning artifact appendix and reproducibility checklist
- NeurIPS reproducibility checklist
- SIGPLAN's checklist for empirical evaluation
- Collective Knowledge (organizing research projects based on FAIR principles)