HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation

Abstract

Stochastic gradient descent (SGD) is an immensely popular approach for online learning in settings where data arrives in a stream or data sizes are very large. However, despite an ever-increasing volume of work on SGD, much less is known about the statistical inferential properties of SGD-based predictions. Taking a fully inferential viewpoint, this paper introduces a novel procedure termed HiGrad to conduct statistical inference for online learning, without incurring additional computational cost compared with SGD. The HiGrad procedure begins by performing SGD updates for a while and then splits the single thread into several threads, and this procedure hierarchically operates in this fashion along each thread. With predictions provided by multiple threads in place, a $t$-based confidence interval is constructed by decorrelating predictions using covariance structures given by a Donsker-style extension of the Ruppert--Polyak averaging scheme, which is a technical contribution of independent interest. Under certain regularity conditions, the HiGrad confidence interval is shown to attain asymptotically exact coverage probability. Finally, the performance of HiGrad is evaluated through extensive simulation studies and a real data example. An R package \texttt{higrad} has been developed to implement the method.

Appeared in JMLR

References in corpus (16)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Online EM Algorithm for Latent Data Models
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Stochastic Gradient Descent as Approximate Bayesian Inference
• Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm
• Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
• Statistical Inference for Model Parameters in Stochastic Gradient Descent
• Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity
• Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradients
• A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
• Asymptotic Optimality in Stochastic Optimization
• Convergence diagnostics for stochastic gradient descent with constant step size
• On Scalable Inference with Stochastic Gradient Descent

Cited by in corpus (16)

• Scalable Uncertainty Quantification for Deep Operator Networks using Randomized Priors
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling
• A generalization of regularized dual averaging and its dynamics
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
• Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic
• Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT
• Approximate Newton-based statistical inference using only stochastic gradients
• Online Covariance Matrix Estimation in Stochastic Gradient Descent
• Understanding and Detecting Convergence for Stochastic Gradient Descent with Momentum
• Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Error Estimation for Sketched SVD via the Bootstrap
• Statistical Estimation and Inference via Local SGD in Federated Learning
• Bootstrapping the error of Oja's algorithm