2019/10/25 by Yakup Ceki Papo, Papo, Yakup Ceki
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1910.11868
arxiv created 2019/10/25 · openalex publication_date 2019/10/25 · arxiv updated 2019/10/28 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
This paper provides a framework to analyze stochastic gradient algorithms in a mean squared error (MSE) sense using the asymptotic normality result of the stochastic gradient descent (SGD) iterates. We perform this analysis by taking the asymptotic normality result and applying it to the finite iteration case. Specifically, we look at problems where the gradient estimators are biased and have reduced variance and compare the iterates generated by these gradient estimators to the iterates generated by the SGD algorithm. We use the work of Fabian to characterize the mean and the variance of the distribution of the iterates in terms of the bias and the covariance matrix of the gradient estimators. We introduce the sliding window SGD (SW-SGD) algorithm, with its proof of convergence, which incurs a lower MSE than the SGD algorithm on quadratic and convex problems. Lastly, we present some numerical results to show the effectiveness of this framework and the superiority of SW-SGD algorithm over the SGD algorithm.