The extended Ville's inequality for nonintegrable nonnegative supermartingales

• URL: http://arxiv.org/abs/2304.01163v3
• Date: Tue, 08 Oct 2024 17:12:13 GMT
• Title: The extended Ville's inequality for nonintegrable nonnegative supermartingales
• Authors: Hongjian Wang, Aaditya Ramdas,
• Abstract summary: We rigorously present an extended theory of nonnegative supermartingales requiring neither integrability nor finiteness. We derive a key maximal inequality foreshadowed by Robbins, which we call the extended Ville's inequality. We derive an extension of the method of mixtures, which applies to $sigma$-finite mixtures of our extended nonnegative supermartingales.
• Score: 30.14855064043107
• License:
• Abstract: Following the initial work by Robbins, we rigorously present an extended theory of nonnegative supermartingales, requiring neither integrability nor finiteness. In particular, we derive a key maximal inequality foreshadowed by Robbins, which we call the extended Ville's inequality, that strengthens the classical Ville's inequality (for integrable nonnegative supermartingales), and also applies to our nonintegrable setting. We derive an extension of the method of mixtures, which applies to $\sigma$-finite mixtures of our extended nonnegative supermartingales. We present some implications of our theory for sequential statistics, such as the use of improper mixtures (priors) in deriving nonparametric confidence sequences and (extended) e-processes.

Related papers

• Continuous K-Max Bandits [54.21533414838677]
  We study the $K$-Max multi-armed bandits problem with continuous outcome distributions and weak value-index feedback. This setting captures critical applications in recommendation systems, distributed computing, server scheduling, etc. Our key contribution is the computationally efficient algorithm DCK-UCB, which combines adaptive discretization with bias-corrected confidence bounds.
  arXiv  Detail & Related papers  (2025-02-19T06:37:37Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  We study high-probability convergence in online learning, in the presence of heavy-tailed noise. Compared to state-of-the-art, who only consider clipping and require noise with bounded $p$-th moments, we provide guarantees for a broad class of nonlinearities.
  arXiv  Detail & Related papers  (2024-10-17T18:25:28Z)
• Tighter Constraints of Multi-Qubit Entanglement in Terms of Nonconvex Entanglement Measures LCREN and LCRENoA [1.2070981561059435]
  The monogamy property of characterizing multipart quantum entanglement is an intriguing feature. Measures satisfying the monogamy inequality are turned out to violate our constraints.
  arXiv  Detail & Related papers  (2024-02-01T09:55:14Z)
• Positive Semidefinite Matrix Supermartingales [30.14855064043107]
  We explore the convergence and nonasymptotic maximal inequalities of supermartingales and backward submartingales in the space of positive semidefinite matrices. Our results lead to new concentration inequalities for either martingale dependent or exchangeable random symmetric matrices under a variety of tail conditions. These inequalities are usually expressed in the boundsner order, are sometimes valid simultaneously for all sample sizes or at an arbitrary data-dependent stopping time, and can often be tightened via an external randomization factor.
  arXiv  Detail & Related papers  (2024-01-28T04:22:43Z)
• Taming under isoperimetry [0.0]
  In this article we propose a Langevin-based scheme calledmathbfsTULA$ to sample from distributions with growing log. We derive non-asymientKL and consequently consequently satisfy a Log-Sobolev inequality.
  arXiv  Detail & Related papers  (2023-11-15T14:44:16Z)
• Unified framework for continuity of sandwiched Rényi divergences [0.0]
  We prove continuity bounds for entropic quantities related to sandwiched R'enyi divergences. In a separate contribution, we use the ALAFF method to study the stability of approximate quantum Markov chains.
  arXiv  Detail & Related papers  (2023-08-23T21:09:54Z)
• Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise [9.76321513479048]
  We establish maximal concentration bounds for the iterates generated by an approximation (SA) under a contractive operator. We consider two settings where the iterates are potentially unbounded: SA with bounded multiplicative noise and SA with sub-Gaussian additive noise.
  arXiv  Detail & Related papers  (2023-03-28T05:32:30Z)
• Exact Non-Oblivious Performance of Rademacher Random Embeddings [79.28094304325116]
  This paper revisits the performance of Rademacher random projections. It establishes novel statistical guarantees that are numerically sharp and non-oblivious with respect to the input data.
  arXiv  Detail & Related papers  (2023-03-21T11:45:27Z)
• 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)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  This paper characterizes the maximum mean discrepancies (MMD) that metrize the weak convergence of probability measures for a wide class of kernels. We prove that, on a locally compact, non-compact, Hausdorff space, the MMD of a bounded continuous Borel measurable kernel k, metrizes the weak convergence of probability measures if and only if k is continuous.
  arXiv  Detail & Related papers  (2020-06-16T15:49:33Z)

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.