Solving Stochastic Fixed-Point Equations with High Probability

arXiv:2607.09097 · math.OC, cs.DS, cs.LG, stat.ML · Submitted 2026-07-10 · Read on arXiv

Jelena Diakonikolas

math.OC, cs.DS, cs.LG, stat.ML

Submitted: 2026-07-10

Code: https://github.com/freegs-plasma/freegs

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Sample Complexity — 23× in this paper · explained in 15 episodes
• Median-of-Means Estimator — 6× in this paper
• Reinforcement Learning — 6× in this paper · explained in 4 episodes
• Q-learning — 5× in this paper · explained in 3 episodes
• Adaptation — 3× in this paper · explained in 1 episode
• Hilbert Space — 3× in this paper · explained in 2 episodes
• Sample Complexity Scaling — 3× in this paper · explained in 2 episodes
• Accuracy — 2× in this paper · explained in 1 episode
• Consistency — 2× in this paper · explained in 3 episodes
• Core — 2× in this paper · explained in 2 episodes
• Abstraction — 1× in this paper · explained in 1 episode
• Ambient Dimension — 1× in this paper · explained in 1 episode
• Generalization — 1× in this paper · explained in 13 episodes
• Lyapunov function — 1× in this paper · explained in 2 episodes
• Regret — 1× in this paper · explained in 3 episodes
• Regularization — 1× in this paper · explained in 3 episodes
• Reinforcement Learning (RL) — 1× in this paper · explained in 25 episodes
• Uncertainty Quantification — 1× in this paper · explained in 8 episodes

Sources

• Dimension-free PAC-Bayesian bounds for the estimation of the mean of a random vector
• Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansion
• Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces
• Optimal variance-reduced stochastic approximation in Banach spaces
• Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions
• Stochastic approximation with cone-contractive operators: Sharp $\ell_\infty$-bounds for $Q$-learning
• Mean Estimation in Banach Spaces Under Infinite Variance and Martingale Dependence

Related papers

• Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
• Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
• Incremental Learning in Mirror Flows
• Online Control via Counterfactual Tracking
• Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability
• Petrov-Galerkin operator inference with application to stability-encouraging identification