Dealing with Unknown Variances in Best-Arm Identification
- URL: http://arxiv.org/abs/2210.00974v1
- Date: Mon, 3 Oct 2022 14:42:48 GMT
- Title: Dealing with Unknown Variances in Best-Arm Identification
- Authors: Marc Jourdan, R\'emy Degenne, Emilie Kaufmann
- Abstract summary: We introduce and analyze two approaches to deal with unknown variances, either by plugging in the empirical variance or by adapting the transportation costs.
We illustrate the theoretical and empirical performances of our two sampling rule wrappers on Track-and-Stop and on a Top Two algorithm.
- Score: 11.975934323118752
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The problem of identifying the best arm among a collection of items having
Gaussian rewards distribution is well understood when the variances are known.
Despite its practical relevance for many applications, few works studied it for
unknown variances. In this paper we introduce and analyze two approaches to
deal with unknown variances, either by plugging in the empirical variance or by
adapting the transportation costs. In order to calibrate our two stopping
rules, we derive new time-uniform concentration inequalities, which are of
independent interest. Then, we illustrate the theoretical and empirical
performances of our two sampling rule wrappers on Track-and-Stop and on a Top
Two algorithm. Moreover, by quantifying the impact on the sample complexity of
not knowing the variances, we reveal that it is rather small.
Related papers
- Towards Self-Supervised Covariance Estimation in Deep Heteroscedastic Regression [102.24287051757469]
We study self-supervised covariance estimation in deep heteroscedastic regression.
We derive an upper bound on the 2-Wasserstein distance between normal distributions.
Experiments over a wide range of synthetic and real datasets demonstrate that the proposed 2-Wasserstein bound coupled with pseudo label annotations results in a computationally cheaper yet accurate deep heteroscedastic regression.
arXiv Detail & Related papers (2025-02-14T22:37:11Z) - Partial identification of kernel based two sample tests with mismeasured
data [5.076419064097733]
Two-sample tests such as the Maximum Mean Discrepancy (MMD) are often used to detect differences between two distributions in machine learning applications.
We study the estimation of the MMD under $epsilon$-contamination, where a possibly non-random $epsilon$ proportion of one distribution is erroneously grouped with the other.
We propose a method to estimate these bounds, and show that it gives estimates that converge to the sharpest possible bounds on the MMD as sample size increases.
arXiv Detail & Related papers (2023-08-07T13:21:58Z) - Skeptical binary inferences in multi-label problems with sets of
probabilities [0.0]
We consider the problem of making distributionally robust, skeptical inferences for the multi-label problem.
By skeptical we understand that we consider as valid only those inferences that are true for every distribution within this set.
We study in particular the Hamming loss case, a common loss function in multi-label problems, showing how skeptical inferences can be made in this setting.
arXiv Detail & Related papers (2022-05-02T05:37:53Z) - A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
Binary density ratio estimation (DRE) provides the foundation for many state-of-the-art machine learning algorithms.
We develop a general framework from the perspective of Bregman minimization divergence.
We show that our framework leads to methods that strictly generalize their counterparts in binary DRE.
arXiv Detail & Related papers (2021-12-07T01:23:20Z) - Deconfounded Score Method: Scoring DAGs with Dense Unobserved
Confounding [101.35070661471124]
We show that unobserved confounding leaves a characteristic footprint in the observed data distribution that allows for disentangling spurious and causal effects.
We propose an adjusted score-based causal discovery algorithm that may be implemented with general-purpose solvers and scales to high-dimensional problems.
arXiv Detail & Related papers (2021-03-28T11:07:59Z) - Squared $\ell_2$ Norm as Consistency Loss for Leveraging Augmented Data
to Learn Robust and Invariant Representations [76.85274970052762]
Regularizing distance between embeddings/representations of original samples and augmented counterparts is a popular technique for improving robustness of neural networks.
In this paper, we explore these various regularization choices, seeking to provide a general understanding of how we should regularize the embeddings.
We show that the generic approach we identified (squared $ell$ regularized augmentation) outperforms several recent methods, which are each specially designed for one task.
arXiv Detail & Related papers (2020-11-25T22:40:09Z) - 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) - DEMI: Discriminative Estimator of Mutual Information [5.248805627195347]
Estimating mutual information between continuous random variables is often intractable and challenging for high-dimensional data.
Recent progress has leveraged neural networks to optimize variational lower bounds on mutual information.
Our approach is based on training a classifier that provides the probability that a data sample pair is drawn from the joint distribution.
arXiv Detail & Related papers (2020-10-05T04:19:27Z) - A One-step Approach to Covariate Shift Adaptation [82.01909503235385]
A default assumption in many machine learning scenarios is that the training and test samples are drawn from the same probability distribution.
We propose a novel one-step approach that jointly learns the predictive model and the associated weights in one optimization.
arXiv Detail & Related papers (2020-07-08T11:35:47Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
We propose a novel technique for analyzing adaptive sampling called the em Simulator.
We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors.
Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
arXiv Detail & Related papers (2017-02-16T23:42:02Z)
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.