On the near-optimality of betting confidence sets for bounded means

• URL: http://arxiv.org/abs/2310.01547v2
• Date: Sat, 25 Nov 2023 01:53:57 GMT
• Title: On the near-optimality of betting confidence sets for bounded means
• Authors: Shubhanshu Shekhar and Aaditya Ramdas
• Abstract summary: We show that an alternative betting-based approach for defining confidence intervals (CIs) has been shown to be empirically superior to the classical methods. We establish two lower bounds that characterize the minimum width achievable by any method for constructing CIs/CSs in terms of certain inverse information projections. Overall these results imply that the betting CI(and CS) admit stronger theoretical guarantees than existing state-of-the-art EB-CI(and) regimes.
• Score: 42.460619457560334
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constructing nonasymptotic confidence intervals (CIs) for the mean of a univariate distribution from independent and identically distributed (i.i.d.) observations is a fundamental task in statistics. For bounded observations, a classical nonparametric approach proceeds by inverting standard concentration bounds, such as Hoeffding's or Bernstein's inequalities. Recently, an alternative betting-based approach for defining CIs and their time-uniform variants called confidence sequences (CSs), has been shown to be empirically superior to the classical methods. In this paper, we provide theoretical justification for this improved empirical performance of betting CIs and CSs. Our main contributions are as follows: (i) We first compare CIs using the values of their first-order asymptotic widths (scaled by $\sqrt{n}$), and show that the betting CI of Waudby-Smith and Ramdas (2023) has a smaller limiting width than existing empirical Bernstein (EB)-CIs. (ii) Next, we establish two lower bounds that characterize the minimum width achievable by any method for constructing CIs/CSs in terms of certain inverse information projections. (iii) Finally, we show that the betting CI and CS match the fundamental limits, modulo an additive logarithmic term and a multiplicative constant. Overall these results imply that the betting CI~(and CS) admit stronger theoretical guarantees than the existing state-of-the-art EB-CI~(and CS); both in the asymptotic and finite-sample regimes.

Related papers

• Learning Identifiable Structures Helps Avoid Bias in DNN-based Supervised Causal Learning [56.22841701016295]
  Supervised Causal Learning (SCL) is an emerging paradigm in this field. Existing Deep Neural Network (DNN)-based methods commonly adopt the "Node-Edge approach"
  arXiv  Detail & Related papers  (2025-02-15T19:10:35Z)
• Rectified Diffusion Guidance for Conditional Generation [62.00207951161297]
  We revisit the theory behind CFG and rigorously confirm that the improper configuration of the combination coefficients (i.e., the widely used summing-to-one version) brings about expectation shift of the generative distribution. We propose ReCFG with a relaxation on the guidance coefficients such that denoising with ReCFG strictly aligns with the diffusion theory. That way the rectified coefficients can be readily pre-computed via traversing the observed data, leaving the sampling speed barely affected.
  arXiv  Detail & Related papers  (2024-10-24T13:41:32Z)
• Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications [11.3631620309434]
  We conduct an in-depth analysis of two-timescale approximation (TTSA) under controlled Markovian noise via central limit (CLT) We uncover the dynamics of TTSA influenced by the underlying Markov chain, which has not been addressed by previous CLT results of TTSA only with Martingale difference noise. In addition, we leverage our CLT result to deduce the statistical properties of GTD algorithms with nonlinear function approximation using Markovian samples and show their identical performance, a perspective not evident from current finite-time bounds.
  arXiv  Detail & Related papers  (2024-01-17T17:01:08Z)
• Exploiting Structure for Optimal Multi-Agent Bayesian Decentralized Estimation [4.320393382724066]
  Key challenge in Bayesian decentralized data fusion is the rumor propagation' or double counting' phenomenon. We show that by exploiting the probabilistic independence structure in multi-agent decentralized fusion problems a tighter bound can be found. We then test our new non-monolithic CI algorithm on a large-scale target tracking simulation and show that it achieves a tighter bound and a more accurate estimate.
  arXiv  Detail & Related papers  (2023-07-20T05:16:33Z)
• Targeted Separation and Convergence with Kernel Discrepancies [61.973643031360254]
  kernel-based discrepancy measures are required to (i) separate a target P from other probability measures or (ii) control weak convergence to P. In this article we derive new sufficient and necessary conditions to ensure (i) and (ii) For MMDs on separable metric spaces, we characterize those kernels that separate Bochner embeddable measures and introduce simple conditions for separating all measures with unbounded kernels.
  arXiv  Detail & Related papers  (2022-09-26T16:41:16Z)
• A New Central Limit Theorem for the Augmented IPW Estimator: Variance Inflation, Cross-Fit Covariance and Beyond [0.9172870611255595]
  Cross-fit inverse probability weighting (AIPW) with cross-fitting is a popular choice in practice. We study this cross-fit AIPW estimator under well-specified outcome regression and propensity score models in a high-dimensional regime. Our work utilizes a novel interplay between three distinct tools--approximate message passing theory, the theory of deterministic equivalents, and the leave-one-out approach.
  arXiv  Detail & Related papers  (2022-05-20T14:17:53Z)
• Mathematical Properties of Continuous Ranked Probability Score Forecasting [0.0]
  We study the rate of convergence in terms of CRPS of distributional regression methods. We show that the k-nearest neighbor method and the kernel method for the distributional regression reach the optimal rate of convergence in dimension $dgeq2$.
  arXiv  Detail & Related papers  (2022-05-09T15:01:13Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Estimating means of bounded random variables by betting [39.98103047898974]
  This paper derives confidence intervals (CI) and time-uniform confidence sequences (CS) for the classical problem of estimating an unknown mean from bounded observations. We present a general approach for deriving concentration bounds, that can be seen as a generalization and improvement of the celebrated Chernoff method. We show how to extend these ideas to sampling without replacement, another heavily studied problem.
  arXiv  Detail & Related papers  (2020-10-19T17:22:03Z)

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.