Formalization of a Stochastic Approximation Theorem

• URL: http://arxiv.org/abs/2202.05959v1
• Date: Sat, 12 Feb 2022 02:31:14 GMT
• Title: Formalization of a Stochastic Approximation Theorem
• Authors: Koundinya Vajjha, Barry Trager, Avraham Shinnar, Vasily Pestun
• Abstract summary: approximation algorithms are iterative procedures which are used to approximate a target value in an environment where the target is unknown. Originally introduced in a 1951 paper by Robbins and Monro, the field of approximation has grown enormously and has come to influence application domains.
• Score: 0.22940141855172028
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic approximation algorithms are iterative procedures which are used to approximate a target value in an environment where the target is unknown and direct observations are corrupted by noise. These algorithms are useful, for instance, for root-finding and function minimization when the target function or model is not directly known. Originally introduced in a 1951 paper by Robbins and Monro, the field of Stochastic approximation has grown enormously and has come to influence application domains from adaptive signal processing to artificial intelligence. As an example, the Stochastic Gradient Descent algorithm which is ubiquitous in various subdomains of Machine Learning is based on stochastic approximation theory. In this paper, we give a formal proof (in the Coq proof assistant) of a general convergence theorem due to Aryeh Dvoretzky, which implies the convergence of important classical methods such as the Robbins-Monro and the Kiefer-Wolfowitz algorithms. In the process, we build a comprehensive Coq library of measure-theoretic probability theory and stochastic processes.

Related papers

• Likelihood approximations via Gaussian approximate inference [3.4991031406102238]
  We propose efficient schemes to approximate the effects of non-Gaussian likelihoods by Gaussian densities. Our results attain good approximation quality for binary and multiclass classification in large-scale point-estimate and distributional inferential settings. As a by-product, we show that the proposed approximate log-likelihoods are a superior alternative to least-squares on raw labels for neural network classification.
  arXiv  Detail & Related papers  (2024-10-28T05:39:26Z)
• A quantitative Robbins-Siegmund theorem [0.0]
  We provide a quantitative version of the Robbins-Siegmund theorem, establishing a bound on how far one needs to look in order to locate a region of metastability in the sense of Tao. Our proof involves a metastable analogue of Doob's theorem for $L_$-supermartingales along with a series of technical lemmas that make precise how quantitative information propagates through sums and products of processes.
  arXiv  Detail & Related papers  (2024-10-21T13:16:29Z)
• Uncertainty Quantification with Bayesian Higher Order ReLU KANs [0.0]
  We introduce the first method of uncertainty quantification in the domain of Kolmogorov-Arnold Networks, specifically focusing on (Higher Order) ReLUKANs. We validate our method through a series of closure tests, including simple one-dimensional functions. We demonstrate the method's ability to correctly identify functional dependencies introduced through the inclusion of a term.
  arXiv  Detail & Related papers  (2024-10-02T15:57:18Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• Gaussian Processes and Statistical Decision-making in Non-Euclidean Spaces [96.53463532832939]
  We develop techniques for broadening the applicability of Gaussian processes. We introduce a wide class of efficient approximations built from this viewpoint. We develop a collection of Gaussian process models over non-Euclidean spaces.
  arXiv  Detail & Related papers  (2022-02-22T01:42:57Z)
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm [10.936043362876651]
  In the last decade, estimating or training in several machine learning models has become synonymous with running gradient algorithms. We first establish a central limit for Polyak-Ruppert averaged gradient algorithm in the zeroth-order setting.
  arXiv  Detail & Related papers  (2021-02-10T00:47:20Z)
• Mean-Field Approximation to Gaussian-Softmax Integral with Application to Uncertainty Estimation [23.38076756988258]
  We propose a new single-model based approach to quantify uncertainty in deep neural networks. We use a mean-field approximation formula to compute an analytically intractable integral. Empirically, the proposed approach performs competitively when compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-06-13T07:32:38Z)
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
  We establish a provably efficient reinforcement learning algorithm with general value function approximation. We show that our algorithm achieves a regret bound of $widetildeO(mathrmpoly(dH)sqrtT)$ where $d$ is a complexity measure. Our theory generalizes recent progress on RL with linear value function approximation and does not make explicit assumptions on the model of the environment.
  arXiv  Detail & Related papers  (2020-05-21T17:36:09Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)

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.