Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation

• URL: http://arxiv.org/abs/2410.15057v1
• Date: Sat, 19 Oct 2024 10:27:26 GMT
• Title: Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation
• Authors: Chuhan Xie, Kaicheng Jin, Jiadong Liang, Zhihua Zhang,
• Abstract summary: We study time-uniform statistical inference for parameters in approximation (SA) We analyze the almost-sure convergence rates of the averaged iterates to a scaled sum of Gaussians in both linear and nonlinear SA problems.
• Score: 23.89036529638614
• License:
• Abstract: We study time-uniform statistical inference for parameters in stochastic approximation (SA), which encompasses a bunch of applications in optimization and machine learning. To that end, we analyze the almost-sure convergence rates of the averaged iterates to a scaled sum of Gaussians in both linear and nonlinear SA problems. We then construct three types of asymptotic confidence sequences that are valid uniformly across all times with coverage guarantees, in an asymptotic sense that the starting time is sufficiently large. These coverage guarantees remain valid if the unknown covariance matrix is replaced by its plug-in estimator, and we conduct experiments to validate our methodology.

Related papers

• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [62.69448336714418]
  Temporal Difference (TD) learning, arguably the most widely used for policy evaluation, serves as a natural framework for this purpose. In this paper, we study the consistency properties of TD learning with Polyak-Ruppert averaging and linear function approximation, and obtain three significant improvements over existing results.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• Probabilistic Conformal Prediction with Approximate Conditional Validity [81.30551968980143]
  We develop a new method for generating prediction sets that combines the flexibility of conformal methods with an estimate of the conditional distribution. Our method consistently outperforms existing approaches in terms of conditional coverage.
  arXiv  Detail & Related papers  (2024-07-01T20:44:48Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Convergence Conditions of Online Regularized Statistical Learning in Reproducing Kernel Hilbert Space With Non-Stationary Data [4.5692679976952215]
  We study the convergence of regularized learning algorithms in the reproducing kernel HilbertRKHS with dependent and non-stationary online data streams. For independent and non-identically distributed data streams, the algorithm achieves the mean square consistency.
  arXiv  Detail & Related papers  (2024-04-04T05:35:59Z)
• Adaptive Linear Estimating Equations [5.985204759362746]
  In this paper, we propose a general method for constructing debiased estimator. It makes use of the idea of adaptive linear estimating equations, and we establish theoretical guarantees of normality. A salient feature of our estimator is that in the context of multi-armed bandits, our estimator retains the non-asymptotic performance.
  arXiv  Detail & Related papers  (2023-07-14T12:55:47Z)
• Non-Parametric Learning of Stochastic Differential Equations with Non-asymptotic Fast Rates of Convergence [65.63201894457404]
  We propose a novel non-parametric learning paradigm for the identification of drift and diffusion coefficients of non-linear differential equations. The key idea essentially consists of fitting a RKHS-based approximation of the corresponding Fokker-Planck equation to such observations.
  arXiv  Detail & Related papers  (2023-05-24T20:43:47Z)
• The Stochastic Proximal Distance Algorithm [5.3315823983402755]
  We propose and analyze a class of iterative optimization methods that recover a desired constrained estimation problem as a penalty parameter. We extend recent theoretical devices to establish finite error bounds and a complete characterization of convergence rates. We validate our analysis via a thorough empirical study, also showing that unsurprisingly, the proposed method outpaces batch versions on popular learning tasks.
  arXiv  Detail & Related papers  (2022-10-21T22:07:28Z)
• Time-uniform central limit theory and asymptotic confidence sequences [34.00292366598841]
  Confidence sequences (CS) provide valid inference at arbitrary stopping times and incur no penalties for "peeking" at the data. CSs are nonasymptotic, enjoying finite-sample guarantees but not the aforementioned broad applicability of confidence intervals. Asymptotic CSs forgo nonasymptotic validity for CLT-like versatility and (asymptotic) time-uniform guarantees.
  arXiv  Detail & Related papers  (2021-03-11T05:45:35Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance [1.52292571922932]
  We study the convergence and finite-time analysis of the nonlinear two-time-scale approximation. In particular, we show that the method achieves a convergence in expectation at a rate $mathcalO (1/k2/3)$, where $k$ is the number of iterations.
  arXiv  Detail & Related papers  (2020-11-03T17:43:39Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.