The Power of Adaptivity in Identifying Statistical Alternatives
This paper studies the trade-off between two different kinds of pure exploration: breadth versus depth. We focus on the most biased coin problem, asking how many total coin flips are required to identify a "heavy" coin from an infinite bag containing both "heavy" coins with mean ✓ 1 2 (0, 1), and "light" coins with mean ✓ 0 2 (0, ✓ 1 ), where heavy coins are drawn from the bag with proportion ↵ 2 (0, 1/2). When ↵, ✓ 0 , ✓ 1 are unknown, the key difficulty of this problem lies in distinguishing whether the two kinds of coins have very similar means, or whether heavy coins are just extremely rare. While existing solutions to this problem require some prior knowledge of the parameters ✓ 0 , ✓ 1 , ↵, we propose an adaptive algorithm that requires no such knowledge yet still obtains near-optimal sample complexity guarantees. In contrast, we provide a lower bound showing that non-adaptive strategies require at least quadratically more samples. In characterizing this gap between adaptive and nonadaptive strategies, we make connections to anomaly detection and prove lower bounds on the sample complexity of differentiating between a single parametric distribution and a mixture of two such distributions.
This paper studies a heavy-coin detection problem where there are (potentially infinite) many coins, of which $1-alpha$ percent are light coins with parameter $theta_0$ and $alpha$ percent are heavy coins with parameter $theta_1(>theta_0)$. This paper proposes an adaptive strategy that is based on estimation (of theta's)-and-exploration (to find heavy coins), but also improves upon it using a doubling trick. Hardness results for other alternatives (particularly the baseline estimation-and-exploration without the doubling trick) are used as evidence towards the novelty of this contribution.
This problem is interesting and there is a history of discussion on similar topics in EE/ML/TCS proceedings particularly in the multi-armed bandits community. There are certain novelty in this paper that can be a nice contribution. However, my biggest problems with the paper are in the organization of the materials and a lack of discussions with some key papers that are very relevant.  The authors discussion on the background is not entirely comprehensive. For example, eq (1) is fairly common knowledge in the multi-armed bandits dating back to Lai and Robbins 1985. A very relevant literature for discovery of all heavy coins in a finite-arm case is studied in Bubeck et al., ICML 2013. Additionally, these papers do not require knowledge of $theta_0, theta_1$ either and further allow each coin to have its own parameter while the result is adaptive with the actual realization (e.g., if the parameters fit the model in the paper under review, then an equivalent of (1) can be obtained). Nonetheless, the paper under review bears some novelty because the other two papers focused on discovery of all "heavier coins" whereas this paper is able to find one heavy coin using only amortized complexity.  The connection to hypothesis test (P1) is also unclear -- unless the authors suggest that there are many distributions that are either H_0 or H_1 and one wants to find one distribution that belongs to H_1. I am not sure if this is the idea of a hypothesis test. Also, why would I only want just one example distribution from H_1 instead of finding all distributions belonging to H_1?  The second equality in the line above (2) contains a typo. It makes sense to write dP/dQ as Radon-Nikodym derivative when P is absolutely continuous on Q; however, it makes no sense to write dP in isolation in the integrand. I would instead write it in terms of pdf or pmf.  Section 3 is tedious and confusing. I would put them in the appendix, but only state why each term should appear in the result (instead of explaining how one should go about proving the theorems). The paragraph below 3.2 is particularly confusing. I directly skipped to Table 1.   In Section 4, what is SPRT? Algorithm 3 may need better introduction as my understanding of it is an informed guess based on the term doubling trick. I did not check for the proofs of Theorem 5; it seems to be a core part of the paper but it is also at the very end of the paper. I can read it further upon request.  As for novelty/impact if I only perceive this paper as an algorithm that finds one heavy coin with sample complexity that equals the amortized cost to find all heavy coins (and assuming the proofs are correct): it has some novelty. However, the setting is rather restrictive (there are only two types of arms). As the authors suggest, neither this paper nor the Carpentier and Valko paper (assuming arm parameter having exponential distribution) covers the full flexibility of the original best-arm identification problem. These assumptions on the arm distribution may hinder real-world applications. The author should also revise the paper for clarify and emphasize on the algorithms and some real-world motivations.