HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation

• URL: http://arxiv.org/abs/1802.04876v3
• Date: Wed, 05 Mar 2025 18:34:50 GMT
• Title: HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• Authors: Weijie J. Su, Yuancheng Zhu,
• Abstract summary: 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.<n>This paper introduces a novel procedure termed HiGrad to conduct statistical inference for online learning.<n>An R package texttthigrad has been developed to implement the method.
• Score: 27.77529637229548
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [62.69448336714418]
  We study the consistency properties of TD learning with Polyak-Ruppert averaging and linear function approximation.<n>First, we derive a novel high-dimensional probability convergence guarantee that depends explicitly on the variance and holds under weak conditions.<n>We further establish refined high-dimensional Berry-Esseen bounds over the class of convex sets that guarantee faster rates than those in the literature.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• Statistical Inference with Stochastic Gradient Methods under $\phi$-mixing Data [9.77185962310918]
  We propose a mini-batch SGD estimator for statistical inference when the data is $phi$-mixing. The confidence intervals are constructed using an associated mini-batch SGD procedure. The proposed method is memory-efficient and easy to implement in practice.
  arXiv  Detail & Related papers  (2023-02-24T16:16:43Z)
• Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression [14.521929085104441]
  We establish a high-dimensional Central Limit Theorem (CLT) for linear functionals of online gradient descent (SGD) We develop an online approach for estimating the expectation and the variance terms appearing in the CLT, and establish high-probability bounds for the developed online estimator. We propose a two-step fully online bias-correction methodology which together with the CLT result and the variance estimation result, provides a fully online and data-driven way to numerically construct confidence intervals.
  arXiv  Detail & Related papers  (2023-02-20T02:38:36Z)
• Incremental Ensemble Gaussian Processes [53.3291389385672]
  We propose an incremental ensemble (IE-) GP framework, where an EGP meta-learner employs an it ensemble of GP learners, each having a unique kernel belonging to a prescribed kernel dictionary. With each GP expert leveraging the random feature-based approximation to perform online prediction and model update with it scalability, the EGP meta-learner capitalizes on data-adaptive weights to synthesize the per-expert predictions. The novel IE-GP is generalized to accommodate time-varying functions by modeling structured dynamics at the EGP meta-learner and within each GP learner.
  arXiv  Detail & Related papers  (2021-10-13T15:11:25Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling [0.9806910643086042]
  We develop a new method of online inference for a vector of parameters estimated by the Polyak-Rtupper averaging procedure of gradient descent algorithms. Our approach is fully operational with online data and is rigorously underpinned by a functional central limit theorem.
  arXiv  Detail & Related papers  (2021-06-06T15:38:37Z)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  This paper attempts to characterize the particular regularization effect of SGD in the moderate learning rate regime. We show that SGD converges along the large eigenvalue directions of the data matrix, while GD goes after the small eigenvalue directions.
  arXiv  Detail & Related papers  (2020-11-04T21:07:52Z)
• Understanding Gradient Clipping in Private SGD: A Geometric Perspective [68.61254575987013]
  Deep learning models are increasingly popular in many machine learning applications where the training data may contain sensitive information. Many learning systems now incorporate differential privacy by training their models with (differentially) private SGD. A key step in each private SGD update is gradient clipping that shrinks the gradient of an individual example whenever its L2 norm exceeds some threshold.
  arXiv  Detail & Related papers  (2020-06-27T19:08:12Z)
• Extrapolation for Large-batch Training in Deep Learning [72.61259487233214]
  We show that a host of variations can be covered in a unified framework that we propose. We prove the convergence of this novel scheme and rigorously evaluate its empirical performance on ResNet, LSTM, and Transformer.
  arXiv  Detail & Related papers  (2020-06-10T08:22:41Z)
• Online Covariance Matrix Estimation in Stochastic Gradient Descent [10.153224593032677]
  gradient descent (SGD) is widely used for parameter estimation especially for huge data sets and online learning. This paper aims at quantifying statistical inference of SGD-based estimates in an online setting.
  arXiv  Detail & Related papers  (2020-02-10T17:46:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.