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
- 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) - Laplace Matching for fast Approximate Inference in Generalized Linear
Models [27.70274403550477]
We propose an approximate inference framework primarily designed to be computationally cheap while still achieving high approximation quality.
The concept, which we call emphLaplace Matching, involves closed-form, approximate, bi-directional transformations between the parameter spaces of exponential families.
This effectively turns inference in GLMs into conjugate inference (with small approximation errors)
arXiv Detail & Related papers (2021-05-07T08:25:17Z) - 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) - Scalable Approximate Inference and Some Applications [2.6541211006790983]
In this thesis, we propose a new framework for approximate inference.
Our proposed four algorithms are motivated by the recent computational progress of Stein's method.
Results on simulated and real datasets indicate the statistical efficiency and wide applicability of our algorithm.
arXiv Detail & Related papers (2020-03-07T04:33:27Z) - 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.