Our algorithm can also be modified slightly to obtain a fully adaptive algorithm with sample complexity O˜(log log n). This matches the best-known bound in this setting by [FJO+15].
In the original formulation, our algorithm sequentially examines all log n possible values of t to find a particular value, t ∗. At t ∗, one of our subroutines-either EstProb or EstTail-will Reject if the input distributions significantly differ.
Employing a binary search for t ∗ reduces the number of queries to O˜(log log n). However, this process requires adaptivity at each iteration.
Collection
[
|
...
]