2019/09/02 by Nicholas J. A. Harvey, Christopher Liaw, Harvey, Nicholas J. A. +3 · 3 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques #cs.LG #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.1909.00843
arxiv created 2019/09/02 · openalex publication_date 2019/09/02 · arxiv updated 2019/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider stochastic gradient descent algorithms for minimizing a non-smooth, strongly-convex function. Several forms of this algorithm, including suffix averaging, are known to achieve the optimal O(1/T) convergence rate in expectation. We consider a simple, non-uniform averaging strategy of Lacoste-Julien et al. (2011) and prove that it achieves the optimal O(1/T) convergence rate with high probability. Our proof uses a recently developed generalization of Freedman's inequality. Finally, we compare several of these algorithms experimentally and show that this non-uniform averaging strategy outperforms many standard techniques, and with smaller variance.