Learning from time-dependent streaming data with online stochastic algorithms
It addresses optimization challenges in streaming data for machine learning applications, but is incremental as it builds on existing methods with theoretical extensions.
This paper tackles stochastic optimization for streaming data with time-dependent and biased gradients, analyzing methods like SGD and mini-batch SGD to show that time-varying mini-batch SGD can break dependence structures and biased SGD matches unbiased performance, with Polyak-Ruppert averaging accelerating convergence.
This paper addresses stochastic optimization in a streaming setting with time-dependent and biased gradient estimates. We analyze several first-order methods, including Stochastic Gradient Descent (SGD), mini-batch SGD, and time-varying mini-batch SGD, along with their Polyak-Ruppert averages. Our non-asymptotic analysis establishes novel heuristics that link dependence, biases, and convexity levels, enabling accelerated convergence. Specifically, our findings demonstrate that (i) time-varying mini-batch SGD methods have the capability to break long- and short-range dependence structures, (ii) biased SGD methods can achieve comparable performance to their unbiased counterparts, and (iii) incorporating Polyak-Ruppert averaging can accelerate the convergence of the stochastic optimization algorithms. To validate our theoretical findings, we conduct a series of experiments using both simulated and real-life time-dependent data.