An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem
Authors: Gang Qiao, Ambuj Tewari
TMLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we provide numerical experiments to demonstrate the empirical behavior of the algorithm matches our theoretical results for realistic time horizons. |
| Researcher Affiliation | Academia | Gang Qiao EMAIL Department of Statistics University of Michigan, Ann Arbor Ambuj Tewari EMAIL Department of Statistics University of Michigan, Ann Arbor |
| Pseudocode | Yes | Algorithm 1 Thompson-CHM Algorithm 2 d-dimensional Thompson-CHM (d >= 2) |
| Open Source Code | No | The paper does not contain any explicit statements about releasing code, nor does it provide links to a code repository or mention code in supplementary materials. |
| Open Datasets | No | We consider 7 Bernoulli bandits with means µ = (0.1, 0.2, , 0.7) and δ = e 3, and we consider Beta(1,1) prior and different γ s to compare the sample complexity and sample weights to the theoretical results in both feasible and infeasible cases. |
| Dataset Splits | No | The paper describes generating data based on 7 Bernoulli bandits with specified means and running 100 independent trials for different parameters, but it does not specify conventional dataset splits (e.g., train/test/validation percentages or sample counts). |
| Hardware Specification | No | The paper mentions numerical experiments but does not provide any specific details about the hardware (e.g., CPU, GPU models, memory) used for these experiments. |
| Software Dependencies | No | The paper references a threshold function from another work and its empirical implementation, and mentions using a Beta(1,1) prior, but it does not specify any particular software, libraries, or their version numbers (e.g., Python, PyTorch, TensorFlow, specific solvers) used for implementation. |
| Experiment Setup | Yes | We consider 7 Bernoulli bandits with means µ = (0.1, 0.2, , 0.7) and δ = e 3, and we consider Beta(1,1) prior and different γ s to compare the sample complexity and sample weights to the theoretical results in both feasible and infeasible cases. We choose γ to be (0.15, 0.25, 0.35, 0.45, 0.55, 0.65) for the feasible case and (0.75, 0.8, 0.85, 0.9, 0.95) for the infeasible case. Figure 1 demonstrates the efficiency of the algorithm Thompson-CHM. In both feasible and infeasible cases, the sample complexity of Thompson CHM matches the theoretical results proved in Theorem 1 well for realistic time horizons. We use the threshold function developed in Kaufmann et al. (2018): Thresh(δ, r) = ln(1 + ln(r)) + T(ln(1/δ)) and T : R+ R+ is a function defined by T(x) = 2h 1 1 + h 1(1+x)+ln ζ(2) h(u) = u ln(u) for u 1 and ζ(s) = P n=1 n s. We also adopt the empirical implementation of T(x) from Kaufmann et al. (2018) in our experiments. The property of the threshold function is verified in Kaufmann et al. (2018). For each δ, we run 100 independent trials and report the average sample complexity. |