Optimal variance-reduced stochastic approximation in Banach spaces
We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. Focusing on a stochastic query model that provides noisy evaluations of the operator, we analyze a variance-reduced stochastic approximation scheme, and establish non-asymptotic bounds for both the operator defect and the estimation error, measured in an arbitrary semi-norm. In contrast to worst-case guarantees, our bounds are instance-dependent, and achieve the local asymptotic minimax risk non-asymptotically. For linear operators, contractivity can be relaxed to multi-step contractivity, so that the theory can be applied to problems like average reward policy evaluation problem in reinforcement learning. We illustrate the theory via applications to stochastic shortest path problems, two-player zero-sum Markov games, as well as policy evaluation and $Q$-learning for tabular Markov decision processes.
Code (0)
등록된 구현이 없습니다.
Tasks
Q-LearningSimilar Papers 제목 키워드 기반
A Universal Banach--Bregman Framework for Stochastic Iterations: Unifying Stochastic Mirror Descent, Learning and LLM Training
Stochastic optimization powers the scalability of modern artificial intelligence, spanning machine learning, deep learning, reinforcement learning, and large language model training. Yet, existing theory remains largely …
Stochastic OptimizationReinforcement LearningSparse LearningStochastic approximation in infinite dimensions
Stochastic Approximation (SA) was introduced in the early 1950's and has been an active area of research for several decades. While the initial focus was on statistical questions, it was seen to have applications to sign…
Conditioning of Banach Space Valued Gaussian Random Variables: An Approximation Approach Based on Martingales
We investigate the conditional distributions of two Banach space valued, jointly Gaussian random variables. In particular, we show that these conditional distributions are again Gaussian and that their means and covarian…
Gaussian ProcessesA Variance Reduced Stochastic Newton Method
Quasi-Newton methods are widely used in practise for convex loss minimization problems. These methods exhibit good empirical performance on a wide variety of tasks and enjoy super-linear convergence to the optimal soluti…
Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation
Stochastic estimators are fundamental to large-scale optimization, where population quantities must be inferred from noisy oracle observations. Although influential methods such as momentum, SPIDER, STORM, and PAGE have …
Stochastic Optimization