161 reads
How to Obtain A Fully Adaptive Algorithm With Sample Complexity O˜(log log n)
by Computational Technology for AllDecember 9th, 2024
Too Long; Didn't Read
The paper considered the problem of equivalence testing of two distributions (over [n]) in the conditional sampling model. Presented by a simple algorithm with sample complexity O˜(log n).
Authors:
(1) Diptarka Chakraborty, National University of Singapore, Singapore
(2) Sourav Chakraborty, Indian Statistical Institute, Kolkata;
(3) Gunjan Kumar, National University of Singapore, Singapore;
(4) Kuldeep S. Meel, University of Toronto, Toronto.
Table of Links
4 An Efficient One-Round Adaptive Algorithm and 4.1 High-Level Overview
6 Acknowledgements and References
B An O(log log n)-query fully adaptive algorithm
5 Conclusion
We considered the problem of equivalence testing of two distributions (over [n]) in the conditional sampling model. We presented a simple algorithm with sample complexity O˜(log n). While our algorithm is not fully non-adaptive, it is only one-round adaptive. This shows that even a limited amount of adaptiveness can help to significantly reduce the sample/query complexity. Our algorithm can also be modified slightly to obtain a fully adaptive algorithm with sample complexity O˜(log log n), matching the best bound in this setting.
One limitation of our algorithm is the presence of large constants and a worsened dependency on the parameter ε compared to the previous algorithm by [KT19]. Investigating methods to reduce this dependency on ε while maintaining the O˜(log n) dependency with respect to the parameter n poses an intriguing open direction of research.
This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license.
L O A D I N G
. . . comments & more!
. . . comments & more!
