Online Prediction of Stochastic Sequences with High Probability Regret Bounds

• URL: http://arxiv.org/abs/2602.16236v1
• Date: Wed, 18 Feb 2026 07:26:37 GMT
• Title: Online Prediction of Stochastic Sequences with High Probability Regret Bounds
• Authors: Matthias Frey, Jonathan H. Manton, Jingge Zhu,
• Abstract summary: We revisit the classical problem of universal prediction of sequences with a finite time horizon $T$ known to the learner.<n>We propose vanishing regret bounds that hold with high probability, complementing existing bounds from the literature that hold in expectation.<n>For the case of universal prediction of a process over a countable alphabet, our bound states a convergence rate of $mathcalO(T-1/2 -1/2)$ with probability as least $1-$ compared to prior known in-expectation bounds of the order $mathcalO(T-1/2)$.
• Score: 16.68585810113338
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the classical problem of universal prediction of stochastic sequences with a finite time horizon $T$ known to the learner. The question we investigate is whether it is possible to derive vanishing regret bounds that hold with high probability, complementing existing bounds from the literature that hold in expectation. We propose such high-probability bounds which have a very similar form as the prior expectation bounds. For the case of universal prediction of a stochastic process over a countable alphabet, our bound states a convergence rate of $\mathcal{O}(T^{-1/2} δ^{-1/2})$ with probability as least $1-δ$ compared to prior known in-expectation bounds of the order $\mathcal{O}(T^{-1/2})$. We also propose an impossibility result which proves that it is not possible to improve the exponent of $δ$ in a bound of the same form without making additional assumptions.

Related papers

• A Refinement of Vapnik--Chervonenkis' Theorem [0.0]
  Vapnik--Chervonenkis' theorem is a seminal result in machine learning.<n>We revisit the probabilistic component of the classical argument.
  arXiv  Detail & Related papers  (2026-01-23T02:57:29Z)
• Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
  Temporal Difference Learning (TD(0)) is fundamental in reinforcement learning.<n>We provide the first high-probability, finite-sample analysis of vanilla TD(0) on mixing Markov data.
  arXiv  Detail & Related papers  (2025-02-08T22:01:02Z)
• High Probability Guarantees for Random Reshuffling [4.794366598086316]
  We consider the gradient method with random reshuffling ($mathsfRR$) for tackling optimisation problems.<n>We provide first-order complexity guarantees for the method.<n>We derive that $mathsfp$-$mathsfRR$provably escapes strict points and a high tail.
  arXiv  Detail & Related papers  (2023-11-20T15:17:20Z)
• A Novel Bayes' Theorem for Upper Probabilities [7.527234046228324]
  In their seminal 1990 paper, Wasserman and Kadane establish an upper bound for the Bayes' posterior probability of a measurable set $A$. In this paper, we introduce a generalization of their result by additionally addressing uncertainty related to the likelihood.
  arXiv  Detail & Related papers  (2023-07-13T15:50:49Z)
• High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
  We show convergence with bounds depending on the initial distance to the optimal solution. We demonstrate that our techniques can be used to obtain high bound for AdaGrad-Norm.
  arXiv  Detail & Related papers  (2023-02-28T18:42:11Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• A lower confidence sequence for the changing mean of non-negative right heavy-tailed observations with bounded mean [9.289846887298854]
  A confidence sequence produces an adapted sequence of sets for a predictable parameter sequence with a time-parametric coverage guarantee. This work constructs a non-asymptotic lower CS for the running average conditional expectation whose slack converges to zero.
  arXiv  Detail & Related papers  (2022-10-20T09:50:05Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  We propose a new, simplified high probability analysis of AdaGrad for smooth, non- probability problems. We present our analysis in a modular way and obtain a complementary $mathcal O (1 / TT)$ convergence rate in the deterministic setting. To the best of our knowledge, this is the first high probability for AdaGrad with a truly adaptive scheme, i.e., completely oblivious to the knowledge of smoothness.
  arXiv  Detail & Related papers  (2022-04-06T13:50:33Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  We find an algorithm which finds. epsilon$-approximate stationary point (with $|nabla F(x)|le epsilon$) using. $(epsilon,gamma)$surimate random random points. Our lower bounds here are novel even in the noiseless case.
  arXiv  Detail & Related papers  (2020-06-24T04:41:43Z)

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.