Variance-Reduced Stochastic Gradient Descent on Streaming Data
Ellango Jothimurugesan, Ashraf Tahmasbi, Phillip Gibbons, Srikanta Tirthapura
Abstract
We present an algorithm STRSAGA for efficiently maintaining a machine learning model over data points that arrive over time, quickly updating the model as new training data is observed. We present a competitive analysis comparing the sub-optimality of the model maintained by STRSAGA with that of an offline algorithm that is given the entire data beforehand, and analyze the risk-competitiveness of STRSAGA under different arrival patterns. Our theoretical and experimental results show that the risk of STRSAGA is comparable to that of offline algorithms on a variety of input arrival patterns, and its experimental performance is significantly better than prior algorithms suited for streaming data, such as SGD and SSVRG.
BibTeX
@inproceedings{NEURIPS2018_cebd648f,
author = {Jothimurugesan, Ellango and Tahmasbi, Ashraf and Gibbons, Phillip and Tirthapura, Srikanta},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Variance-Reduced Stochastic Gradient Descent on Streaming Data},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/cebd648f9146a6345d604ab093b02c73-Paper.pdf},
volume = {31},
year = {2018}
}