Variance-Reduced Stochastic Gradient Descent on Streaming Data
Variance-Reduced Stochastic Gradient Descent on Streaming Data
复制标题
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ellango Jothimurugesan;Ashraf Tahmasbi;Phillip B. Gibbons;Srikanta Tirthapura
中科院分区：
文献类型：
--
作者：
Ellango Jothimurugesan;Ashraf Tahmasbi;Phillip B. Gibbons;Srikanta Tirthapura
我们提出了一种算法 STRSAGA，用于在随时间推移到达的数据点上有效维护机器学习模型，并在观察到新的训练数据时快速更新模型。我们提出了竞争性分析，比较了 STRSAGA 维护的模型与预先给出全部数据的离线算法的次优性，并分析了 STRSAGA 在不同到达模式下的风险竞争力。我们的理论和实验结果表明，STRSAGA 的风险与各种输入到达模式上的离线算法相当，并且其实验性能明显优于适合流数据的现有算法（例如 SGD 和 SSVRG）。
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.