Asymptotic optimality theory of confidence intervals of the mean
Vikas Deep, Achal Bassamboo, Sandeep Juneja · 2025
Read Asymptotic optimality theory of confidence intervals of the mean by Vikas Deep, Achal Bassamboo, Sandeep Juneja (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-19126.txt.
Introduction
Vikas Deep, Achal Bassamboo, and Sandeep Juneja revisit a basic task in statistics: giving an interval that should hold the true mean of some quantity, in a 2025 paper. The interval must be right with a set level of trust, using a limited pool of samples.
The authors map three regimes based on how fast the sample pool may grow as the trust level rises. With slow growth, no method can beat the full spread of the data. With matched growth, they pin down the best width exactly. With fast growth, the interval can shrink to the true mean. Intervals built on a standard divergence measure reach the best width in the last two regimes.
Catalog record
| CREATOR | Vikas Deep, Achal Bassamboo, Sandeep Juneja |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-19126
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymptotic optimality theory of confidence intervals of the mean Vikas Deep, Achal Bassamboo, Sandeep Juneja Abstract We address the classical problem of constructing confidence intervals (CIs) for the mean of a distribution, given N N i.i.d. samples, such that the CI contains the true mean with probability at least 1 − δ 1-\delta , where δ ∈ ( 0 , 1 ) \delta\in(0,1) . We characterize three distinct learning regimes based on the minimum achievable limiting width of any CI as the sample size N δ → ∞ N_{\delta}\to\infty and δ → 0 \delta\to 0 . In the first regime, where N δ N_{\delta} grows slower than log ( 1 / δ ) \log(1/\delta) , the limiting width of any CI equals the width of the distribution’s support, precluding meaningful inference. In the second regime, where N δ N_{\delta} scales as log ( 1 / δ ) \log(1/\delta) , we precisely characterize the minimum limiting width, which depends on the scaling constant. In the third regime, where N δ N_{\delta} grows faster than log ( 1 / δ ) \log(1/\delta) , complete learning is achievable, and the limiting width of the CI collapses to zero, converging to the true mean. We demonstrate that CIs derived from concentration inequalities based on Kullback-Leibler (KL) divergences achieve asymptotically optimal performance, attaining the minimum limiting width in both sufficient and complete learning regimes for distributions in two families: single-parameter exponential and bounded support. Additionally, these results extend to one-sided CIs, with the width notion adjusted appropriately. Finally, we generalize our findings to settings with random per-sample costs, motivated by practical applications such as stochastic simulators and cloud service selection. Instead of a fixed sample size, we consider a cost budget C δ C_{\delta} , identifying analogous learning regimes and characterizing the optimal CI construction policy. 1 Introduction and main contribution The problem of constructing a confidence interval (CI) for the mean of a distribution with a coverage guarantee—ensuring that the mean lies within the CI with probability at least 1-\delta for a pre-specified \delta\in(0,1) —is well-studied in the statistics literature. This problem has significant applications in A/B testing, experimentation, data analytics, and simulation. Typically, this is achieved using concentration inequalities for the mean, given a sample size of N i.i.d. observations from a probability distribution (see Hoeffding, 1994 , Waudby-Smith and Ramdas, 2024 , Maurer and Pontil, 2009 , Audibert et al., 2009 , Boucheron and Gassiat, 2009 , Catoni, 2012 , Chen et al., 2021 and Bennett, 1962 ). In this paper, we primarily aim to address an important element absent from the literature on CI. While there are various methods to construct a confidence interval for the mean of a distribution, there are no results that characterize the optimal CI with minimum width. In this paper, we characterize three learning regimes based on the minimum limiting width achievable for any CI construction policy as N_{\delta}\to\infty when \delta\to 0 , under a mild assumption of stability of policies (as defined in Definition 2 ). In a nutshell, under this assumption, the limiting width of CI of mean becomes a deterministic constant for any CI construction policy, allowing analysis to be tractable. The three regimes are defined as follows: 1) No learning regime: If \lim_{\delta\to 0}\frac{N_{\delta}}{\log(1/\delta)}\to 0 , the limiting width of the CI is the length of the support of the mean for any stable CI construction policies. This implies that no learning is possible as the sample size is not sufficient. 2) Sufficient learning regime: If \lim_{\delta\to 0}\frac{N_{\delta}}{\log(1/\delta)}\to k for k\in(0,\infty) , we have a sharp characterization of the lower bound on limiting width that involves terms with KL divergences for any stable CI construction policies. This lower bound on limiting width shrinks as k increases. Further, we show that constructing CI via inverting concentration inequality based on KL divergences matches the lower bound of the limiting width. Hence, this lower bound result on the limiting width is tight as \delta\to 0 and N_{\delta}\to\infty . 3) Complete learning regime: If \lim_{\delta\to 0}\frac{N_{\delta}}{\log(1/\delta)}\to\infty , the limiting CI width trivially converges to zero. Furthermore, we prove that constructing CIs by inverting concentration inequalities based on KL divergences also results in a zero limiting width. In this regime, we further analyze the rate at which the width converges to zero and demonstrate that our proposed policy achieves the fastest rate of convergence. Our results apply to both parametric and non-parametric families of probability distributions. For parametric cases, we consider a canonical single-parameter exponential family, while for non-parametric cases, we assume the distribution has bounded support. We assume only that the unknown underlying distribution belongs to this known family. If a CI construction policy, that matches the lower bound on the limiting width in the sufficient learning regime and the complete learning regime, is called an asymptotically optimal CI construction policy. Next, we state the recipe for asymptotically optimal CI construction policies. 1.1 Recipe for asymptotically optimal CI construction policies To construct an asymptotically optimal CI construction policy, when the probability distribution belongs to a canonical single-parametric exponential family (see ( 1 )), we develop a novel concentration bound on the deviation of the maximum likelihood estimator (MLE) of the mean from the true mean, measured in terms of the KL divergence (see Eq. ( 5 )). Inverting this concentration inequality to construct a CI for the mean leads to an asymptotically optimal CI construction policy. The proof idea utilizes the construction of a martingale and Markov’s inequality. For the non-parametric setting, Agrawal, 2022 and Orabona and Jun, 2023 provide a confidence interval which is constructed via inverting a concentration inequality based on KL divergences. In this setting, we prove the optimality of the CI provided by them. In summary, we prove that the CIs constructed via inverting concentration inequality based on KL divergences are the best CIs in a reasonable asymptotic regime. 1.2 One-sided CI setting One-sided confidence intervals are useful in many applications such as quality control (see cai2005one ). To extend the results of CI for the mean in this setting, we define a notion of “half-width”. To understand this, consider constructing a one-sided CI greater than some threshold. This notion of “half-width” essentially captures the distance between this threshold and the true mean of the distribution. In this setting as well, we identify three learning regimes and characterize the asymptotically optimal policy. An interesting finding is that the minimum limiting width of the CI (main setting of the paper) is the sum of the limiting minimum half-widths of the two types of one-sided CIs (greater than some threshold and less than some threshold). 1.3 Random sampling cost setting The above results assume that the cost of each sample is fixed and equal to one. However, in many practical situations, this assumption may not hold. For instance, in simulation studies, the cost can represent the time required to simulate the performance of a system design, which may vary depending on system complexity and randomness (see Chick and Inoue, 2001 ). Similarly, in real-world applications, online bidding optimization in sponsored search (see Amin et al., 2012 , Xia et al., 2015 and Tran-Thanh et al., 2014 ), the cost of acquiring