Accelerating Stratified Sampling SGD by Reconstructing Strata
Abstract
In this paper, a novel stratified sampling strategy is designed to accelerate the mini-batch SGD. We derive a new iteration-dependent surrogate which bound the stochastic variance from above. To keep the strata minimizing this surrogate with high probability, a stochastic stratifying algorithm is adopted in an adaptive manner, that is, in each iteration, strata are reconstructed only if an easily verifiable condition is met. Based on this novel sampling strategy, we propose an accelerated mini-batch SGD algorithm named SGD-RS. Our theoretical analysis shows that the convergence rate of SGD-RS is superior to the state-of-the-art. Numerical experiments corroborate our theory and demonstrate that SGD-RS achieves at least 3.48-times speed-ups compared to vanilla minibatch SGD.
Cite
Text
Liu et al. "Accelerating Stratified Sampling SGD by Reconstructing Strata." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/378Markdown
[Liu et al. "Accelerating Stratified Sampling SGD by Reconstructing Strata." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/liu2020ijcai-accelerating/) doi:10.24963/IJCAI.2020/378BibTeX
@inproceedings{liu2020ijcai-accelerating,
title = {{Accelerating Stratified Sampling SGD by Reconstructing Strata}},
author = {Liu, Weijie and Qian, Hui and Zhang, Chao and Shen, Zebang and Xie, Jiahao and Zheng, Nenggan},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {2725-2731},
doi = {10.24963/IJCAI.2020/378},
url = {https://mlanthology.org/ijcai/2020/liu2020ijcai-accelerating/}
}