A generalization of regularized dual averaging and its dynamics

Abstract

Excessive computational cost for learning large data and streaming data can be alleviated by using stochastic algorithms, such as stochastic gradient descent and its variants. Recent advances improve stochastic algorithms on convergence speed, adaptivity and structural awareness. However, distributional aspects of these new algorithms are poorly understood, especially for structured parameters. To develop statistical inference in this case, we propose a class of generalized regularized dual averaging (gRDA) algorithms with constant step size, which improves RDA (Xiao, 2010; Flammarion and Bach, 2017). Weak convergence of gRDA trajectories are studied, and as a consequence, for the first time in the literature, the asymptotic distributions for online l1 penalized problems become available. These general results apply to both convex and non-convex differentiable loss functions, and in particular, recover the existing regret bound for convex losses (Nemirovski et al., 2009). As important applications, statistical inferential theory on online sparse linear regression and online sparse principal component analysis are developed, and are supported by extensive numerical analysis. Interestingly, when gRDA is properly tuned, support recovery and central limiting distribution (with mean zero) hold simultaneously in the online setting, which is in contrast with the biased central limiting distribution of batch Lasso (Knight and Fu, 2000). Technical devices, including weak convergence of stochastic mirror descent, are developed as by-products with independent interest. Preliminary empirical analysis of modern image data shows that learning very sparse deep neural networks by gRDA does not necessarily sacrifice testing accuracy.

References in corpus (18)

• Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science
• Generalized power method for sparse principal component analysis
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Optimal Solutions for Sparse Principal Component Analysis
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Sparse Principal Component Analysis via Variable Projection
• Adaptive Bound Optimization for Online Convex Optimization
• Proofs of the martingale FCLT
• Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
• On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning
• Sparse Q-learning with Mirror Descent
• Regularized Off-Policy TD-Learning
• Diffusion Approximations for Online Principal Component Estimation and Global Convergence

Cited by in corpus (5)

• AutoFIS: Automatic Feature Interaction Selection in Factorization Models for Click-Through Rate Prediction
• Directional Pruning of Deep Neural Networks
• Online Covariance Matrix Estimation in Stochastic Gradient Descent
• Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
• Structured Directional Pruning via Perturbation Orthogonal Projection