Timezone: »

Variance-Reduced Stochastic Gradient Descent on Streaming Data
Ellango Jothimurugesan · Ashraf Tahmasbi · Phillip Gibbons · Srikanta Tirthapura

Wed Dec 05 07:45 AM -- 09:45 AM (PST) @ Room 210 #80

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.

Author Information

Ellango Jothimurugesan (CMU)
Ashraf Tahmasbi (Iowa State University)
Phillip Gibbons (CMU)
Srikanta Tirthapura (Iowa State University)

More from the Same Authors