Correlated Binomial Process

Moïse Blanchard, Doron Cohen, Aryeh Kontorovich
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:551-595, 2024.

Abstract

Cohen and Kontorovich (COLT 2023) initiated the study of what we call here the Binomial Empirical Process: the maximal empirical mean deviation for sequences of binary random variables (up to rescaling, the empirical mean of each entry of the random sequence is a binomial hence the naming). They almost fully analyzed the case where the binomials are independent, which corresponds to all random variable entries from the sequence being independent. The remaining gap was closed by Blanchard and Voráček (ALT 2024). In this work, we study the much more general and challenging case with correlations. In contradistinction to Gaussian processes, whose behavior is characterized by the covariance structure, we discover that, at least somewhat surprisingly, for binomial processes covariance does not even characterize convergence. Although a full characterization remains out of reach, we take the first steps with nontrivial upper and lower bounds in terms of covering numbers.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-blanchard24a, title = {Correlated Binomial Process}, author = {Blanchard, Mo\"{i}se and Cohen, Doron and Kontorovich, Aryeh}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {551--595}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/blanchard24a/blanchard24a.pdf}, url = {https://proceedings.mlr.press/v247/blanchard24a.html}, abstract = {Cohen and Kontorovich (COLT 2023) initiated the study of what we call here the Binomial Empirical Process: the maximal empirical mean deviation for sequences of binary random variables (up to rescaling, the empirical mean of each entry of the random sequence is a binomial hence the naming). They almost fully analyzed the case where the binomials are independent, which corresponds to all random variable entries from the sequence being independent. The remaining gap was closed by Blanchard and Voráček (ALT 2024). In this work, we study the much more general and challenging case with correlations. In contradistinction to Gaussian processes, whose behavior is characterized by the covariance structure, we discover that, at least somewhat surprisingly, for binomial processes covariance does not even characterize convergence. Although a full characterization remains out of reach, we take the first steps with nontrivial upper and lower bounds in terms of covering numbers.} }
Endnote
%0 Conference Paper %T Correlated Binomial Process %A Moïse Blanchard %A Doron Cohen %A Aryeh Kontorovich %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-blanchard24a %I PMLR %P 551--595 %U https://proceedings.mlr.press/v247/blanchard24a.html %V 247 %X Cohen and Kontorovich (COLT 2023) initiated the study of what we call here the Binomial Empirical Process: the maximal empirical mean deviation for sequences of binary random variables (up to rescaling, the empirical mean of each entry of the random sequence is a binomial hence the naming). They almost fully analyzed the case where the binomials are independent, which corresponds to all random variable entries from the sequence being independent. The remaining gap was closed by Blanchard and Voráček (ALT 2024). In this work, we study the much more general and challenging case with correlations. In contradistinction to Gaussian processes, whose behavior is characterized by the covariance structure, we discover that, at least somewhat surprisingly, for binomial processes covariance does not even characterize convergence. Although a full characterization remains out of reach, we take the first steps with nontrivial upper and lower bounds in terms of covering numbers.
APA
Blanchard, M., Cohen, D. & Kontorovich, A.. (2024). Correlated Binomial Process. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:551-595 Available from https://proceedings.mlr.press/v247/blanchard24a.html.

Related Material