Optimal Confidence Regions for the Multinomial Parameter

• URL: http://arxiv.org/abs/2002.01044v2
• Date: Fri, 29 Jan 2021 18:58:14 GMT
• Title: Optimal Confidence Regions for the Multinomial Parameter
• Authors: Matthew L. Malloy, Ardhendu Tripathy, Robert D. Nowak
• Abstract summary: Construction of tight confidence regions and intervals is central to statistical inference and decision making. This paper develops new theory showing minimum average volume confidence regions for categorical data.
• Score: 15.851891538566585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Construction of tight confidence regions and intervals is central to statistical inference and decision making. This paper develops new theory showing minimum average volume confidence regions for categorical data. More precisely, consider an empirical distribution $\widehat{\boldsymbol{p}}$ generated from $n$ iid realizations of a random variable that takes one of $k$ possible values according to an unknown distribution $\boldsymbol{p}$. This is analogous to a single draw from a multinomial distribution. A confidence region is a subset of the probability simplex that depends on $\widehat{\boldsymbol{p}}$ and contains the unknown $\boldsymbol{p}$ with a specified confidence. This paper shows how one can construct minimum average volume confidence regions, answering a long standing question. We also show the optimality of the regions directly translates to optimal confidence intervals of linear functionals such as the mean, implying sample complexity and regret improvements for adaptive machine learning algorithms.

Related papers

• Optimal score estimation via empirical Bayes smoothing [13.685846094715364]
  We study the problem of estimating the score function of an unknown probability distribution $rho*$ from $n$ independent and identically distributed observations in $d$ dimensions. We show that a regularized score estimator based on a Gaussian kernel attains this rate, shown optimal by a matching minimax lower bound.
  arXiv  Detail & Related papers  (2024-02-12T16:17:40Z)
• Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond $1+\alpha$ Moments [10.889739958035536]
  We introduce a new definitional framework to analyze the fine-grained optimality of algorithms. We show that median-of-means is neighborhood optimal, up to constant factors. It is open to find a neighborhood-separated estimator without constant factor slackness.
  arXiv  Detail & Related papers  (2023-11-21T18:50:38Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  In many bandit problems, the maximal reward achievable by a policy is often unknown in advance. We consider the problem of estimating the optimal policy value in the sublinear data regime before the optimal policy is even learnable. We present a more practical, computationally efficient algorithm that estimates a problem-dependent upper bound on $V*$.
  arXiv  Detail & Related papers  (2023-02-19T01:09:24Z)
• Generalized Differentiable RANSAC [95.95627475224231]
  $nabla$-RANSAC is a differentiable RANSAC that allows learning the entire randomized robust estimation pipeline. $nabla$-RANSAC is superior to the state-of-the-art in terms of accuracy while running at a similar speed to its less accurate alternatives.
  arXiv  Detail & Related papers  (2022-12-26T15:13:13Z)
• Useful Confidence Measures: Beyond the Max Score [9.189382034558657]
  We derive several confidence measures that depend on information beyond the maximum score. We show that when models are evaluated on the out-of-distribution data out of the box'', using only the maximum score to inform the confidence measure is highly suboptimal.
  arXiv  Detail & Related papers  (2022-10-25T14:54:44Z)
• Pitfalls of Gaussians as a noise distribution in NCE [22.23473249312549]
  Noise Contrastive Estimation (NCE) is a popular approach for learning probability density functions parameterized up to a constant of proportionality. We show that the choice of $q$ can severely impact the computational and statistical efficiency of NCE.
  arXiv  Detail & Related papers  (2022-10-01T04:42:56Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
  We present a novel estimator with sub-Gaussian convergence. Our estimator does not require prior knowledge of the variance. Our estimator construction and analysis gives a framework generalizable to other problems.
  arXiv  Detail & Related papers  (2020-11-17T02:47:24Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification. Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
  arXiv  Detail & Related papers  (2020-06-29T21:06:52Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  We study BQO under distributional uncertainty in which the underlying probability distribution is unknown except for a limited set of its i.i.d. samples. A standard BQO approach maximizes the Monte Carlo estimate of the true expected objective given the fixed sample set. We propose a novel posterior sampling based algorithm, namely distributionally robust BQO (DRBQO) for this purpose.
  arXiv  Detail & Related papers  (2020-01-19T12:00: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.