How to Obtain A Fully Adaptive Algorithm With Sample Complexity O˜(log 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 Abstract and 1 Introduction 2 Notations and Preliminaries 3 Related Work 4 An Efficient One-Round Adaptive Algorithm and 4.1 High-Level Overview 4.2 Algorithm Description 4.3 Technical Analysis 5 Conclusion 6 Acknowledgements and References A Missing Proofs 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. 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. Authors: 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 Abstract and 1 Introduction Abstract and 1 Introduction 2 Notations and Preliminaries 2 Notations and Preliminaries 3 Related Work 3 Related Work 4 An Efficient One-Round Adaptive Algorithm and 4.1 High-Level Overview 4 An Efficient One-Round Adaptive Algorithm and 4.1 High-Level Overview 4.2 Algorithm Description 4.2 Algorithm Description 4.3 Technical Analysis 4.3 Technical Analysis 5 Conclusion 5 Conclusion 6 Acknowledgements and References 6 Acknowledgements and References A Missing Proofs A Missing Proofs B An O(log log n)-query fully adaptive algorithm 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. This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. available on arxiv