paint-brush
How to Obtain A Fully Adaptive Algorithm With Sample Complexity O˜(log log n)by@computational
185 reads

How to Obtain A Fully Adaptive Algorithm With Sample Complexity O˜(log log n)

by Computational Technology for All
Computational Technology for All HackerNoon profile picture

Computational Technology for All

@computational

Computational: We take random inputs, follow complex steps, and hope...

December 9th, 2024
Read on Terminal Reader
Read this story in a terminal
Print this story
Read this story w/o Javascript
Read this story w/o Javascript
tldt arrow

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).
featured image - How to Obtain A Fully Adaptive Algorithm With Sample Complexity O˜(log log n)
1x
Read by Dr. One voice-avatar

Listen to this story

Computational Technology for All HackerNoon profile picture
Computational Technology for All

Computational Technology for All

@computational

Computational: We take random inputs, follow complex steps, and hope the output makes sense. And then blog about it.

Learn More
LEARN MORE ABOUT @COMPUTATIONAL'S
EXPERTISE AND PLACE ON THE INTERNET.

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.

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.


L O A D I N G
. . . comments & more!

About Author

Computational Technology for All HackerNoon profile picture
Computational Technology for All@computational
Computational: We take random inputs, follow complex steps, and hope the output makes sense. And then blog about it.

TOPICS

THIS ARTICLE WAS FEATURED IN...

Permanent on Arweave
Read on Terminal Reader
Read this story in a terminal
 Terminal
Read this story w/o Javascript
Read this story w/o Javascript
 Lite
Hackernoon
Bsky