Sequential Algorithms for Testing Closeness of Distributions

6. prosince 2021

Řečníci

O prezentaci

What advantage do sequential procedures provide over batch algorithms for testing properties of unknown distributions? Focusing on the problem of testing whether two distributions 𝒟_1 and 𝒟_2 on {1,..., n} are equal or ϵ-far, we give several answers to this question. We show that for a small alphabet size n, there is a sequential algorithm that outperforms any batch algorithm by a factor of at least 4 in terms sample complexity. For a general alphabet size n, we give a sequential algorithm that uses no more samples than its batch counterpart, and possibly fewer if the actual distance between 𝒟_1 and 𝒟_2 is larger than ϵ. As a corollary, letting ϵ go to 0, we obtain a sequential algorithm for testing closeness (with no a priori bound on the distance between 𝒟_1 and 𝒟_2) with a sample complexity 𝒪̃(n^2/3/TV(𝒟_1, 𝒟_2)^4/3): this improves over the 𝒪̃(n/log n/TV(𝒟_1, 𝒟_2)^2) tester of [Daskalakis and Kawase 2017] and is optimal up to multiplicative constants. We also establish limitations of sequential algorithms for the problem of testing closeness: they can improve the worst case number of samples by at most a constant factor.

Organizátor

O organizátorovi (NeurIPS 2021)

Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.

Baví vás formát? Nechte SlidesLive zachytit svou akci!

Profesionální natáčení a streamování po celém světě.

Sdílení

Doporučená videa

Prezentace na podobné téma, kategorii nebo přednášejícího

Zajímají Vás podobná videa? Sledujte NeurIPS 2021