Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Distribution Testing Lower Bounds via Reductions from Communication Complexity

Distribution Testing Lower Bounds via Reductions from Communication Complexity We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [15], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove new distribution testing lower bounds, as well as to provide simple proofs of known lower bounds. Our main result is concerned with testing identity to a specific distribution, p, given as a parameter. In a recent and influential work, Valiant and Valiant [55] showed that the sample complexity of the aforementioned problem is closely related to the 2/3-quasinorm of p. We obtain alternative bounds on the complexity of this problem in terms of an arguably more intuitive measure and using simpler proofs. More specifically, we prove that the sample complexity is essentially determined by a fundamental operator in the theory of interpolation of Banach spaces, known as Peetre’s K-functional. We show that this quantity is closely related to the size of the effective support of p (loosely speaking, the number of supported elements that constitute the vast majority of the mass of p). This result, in turn, stems from an unexpected connection to functional analysis and refined concentration of measure inequalities, which arise naturally in our reduction. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Distribution Testing Lower Bounds via Reductions from Communication Complexity

Download PDF
37 pages

Loading next page...
 
/lp/association-for-computing-machinery/distribution-testing-lower-bounds-via-reductions-from-communication-O01caYeHVR
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3305270
Publisher site
See Article on Publisher Site

Abstract

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [15], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove new distribution testing lower bounds, as well as to provide simple proofs of known lower bounds. Our main result is concerned with testing identity to a specific distribution, p, given as a parameter. In a recent and influential work, Valiant and Valiant [55] showed that the sample complexity of the aforementioned problem is closely related to the 2/3-quasinorm of p. We obtain alternative bounds on the complexity of this problem in terms of an arguably more intuitive measure and using simpler proofs. More specifically, we prove that the sample complexity is essentially determined by a fundamental operator in the theory of interpolation of Banach spaces, known as Peetre’s K-functional. We show that this quantity is closely related to the size of the effective support of p (loosely speaking, the number of supported elements that constitute the vast majority of the mass of p). This result, in turn, stems from an unexpected connection to functional analysis and refined concentration of measure inequalities, which arise naturally in our reduction.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Feb 11, 2019

Keywords: Communication complexity

References

  • A chasm between identity and equivalence testing with conditional queries
    Acharya, Jayadev; Canonne, Clément L.; Kamath, Gautam
  • Competitive closeness testing
    Acharya, Jayadev; Das, Hirakendu; Jafarpour, Ashkan; Orlitsky, Alon; Pan, Shengjun
  • Testing poisson binomial distributions
    Acharya, Jayadev; Daskalakis, Constantinos
  • Optimal testing for properties of distributions
    Acharya, Jayadev; Daskalakis, Constantinos; Kamath, Gautam
  • Learning and testing junta distributions
    Aliakbarpour, Maryam; Blais, Eric; Rubinfeld, Ronitt
  • Rademacher functions in symmetric spaces
    Astashkin, Sergey V.
  • The complexity of approximating the entropy
    Batu, Tuğkan; Dasgupta, Sanjoy; Kumar, Ravi; Rubinfeld, Ronitt
  • Testing random variables for independence and identity
    Batu, Tuğkan; Fischer, Eldar; Fortnow, Lance; Kumar, Ravi; Rubinfeld, Ronitt; White, Patrick
  • Testing that distributions are close
    Batu, Tuğkan; Fortnow, Lance; Rubinfeld, Ronitt; Smith, Warren D.; White, Patrick
  • Testing closeness of discrete distributions
    Batu, Tuğkan; Fortnow, Lance; Rubinfeld, Ronitt; Smith, Warren D.; White, Patrick
  • Sublinear algorithms for testing monotone and unimodal distributions
    Batu, Tuğkan; Kumar, Ravi; Rubinfeld, Ronitt
  • Interpolation of Operators
    Bennett, Colin; Sharpley, Robert C.
  • Testing closeness with unequal sized samples
    Bhattacharya, Bhaswar B.; Valiant, Gregory
  • Testing monotonicity of distributions over general partial orders
    Bhattacharyya, Arnab; Fischer, Eldar; Rubinfeld, Ronitt; Valiant, Paul
  • Property testing lower bounds via communication complexity
    Blais, Eric; Brody, Joshua; Matulef, Kevin
  • Lower bounds for testing computability by small width OBDDs
    Brody, Joshua; Matulef, Kevin; Wu, Chenggang
  • Big data on the rise? testing monotonicity of distributions
    Canonne, Clément L.
  • A survey on distribution testing: Your data is big
    Canonne, Clément L.
  • Are few bins enough: Testing histogram distributions
    Canonne, Clément L.
  • Testing shape restrictions of discrete distributions
    Canonne, Clément L.; Diakonikolas, Ilias; Gouleakis, Themis; Rubinfeld, Ronitt
  • Testing probability distributions using conditional samples
    Canonne, Clément L.; Ron, Dana; Servedio, Rocco A.
  • On the power of conditional samples in distribution testing
    Chakraborty, Sourav; Fischer, Eldar; Goldhirsh, Yonatan; Matsliah, Arie
  • Optimal algorithms for testing closeness of discrete distributions
    Chan, Siu-On; Diakonikolas, Ilias; Valiant, Gregory; Valiant, Paul
  • Testing -modal distributions: Optimal algorithms via reductions
    Daskalakis, Constantinos; Diakonikolas, Ilias; Servedio, Rocco A.; Valiant, Gregory; Valiant, Paul
  • Sample-optimal identity testing with high probability
    Diakonikolas, Ilias; Gouleakis, Themis; Peebles, John; Price, Eric
  • A new approach for testing properties of discrete distributions
    Diakonikolas, Ilias; Kane, Daniel M.
  • Optimal algorithms and lower bounds for testing closeness of structured distributions
    Diakonikolas, Ilias; Kane, Daniel M.; Nikishkin, Vladimir
  • Testing identity of structured distributions
    Diakonikolas, Ilias; Kane, Daniel M.; Nikishkin, Vladimir
  • Faster algorithms for testing under conditional sampling (JMLR Workshop and Conference Proceedings), Vol
    Falahatgar, Moein; Jafarpour, Ashkan; Orlitsky, Alon; Pichapathi, Venkatadheeraj; Suresh, Ananda Theertha
  • Improving and extending the testing of distributions for shape-restricted properties
    Fischer, Eldar; Lachish, Oded; Vasudev, Yadu
  • The uniform distribution is complete with respect to testing identity to a fixed distribution
    Goldreich, Oded
  • Property testing and its connection to learning and approximation
    Goldreich, Oded; Goldwasser, Shafi; Ron, Dana
  • On testing expansion in bounded-degree graphs
    Goldreich, Oded; Ron, Dana
  • On the Rademacher series
    Hitczenko, Paweł; Kwapień, Stanisław
  • Interpolation of quasi-normed spaces
    Holmstedt, Tord
  • Approximating and testing k-histogram distributions in sub-linear time
    Indyk, Piotr; Levi, Reut; Rubinfeld, Ronitt
  • Order-optimal estimation of functionals of discrete distributions
    Jiao, Jiantao; Venkat, Kartik; Weissman, Tsachy
  • Discrete Multivariate Distributions
    Johnson, Norman Lloyd; Kotz, Samuel; Balakrishnan, Narayanaswamy
  • Testing properties of collections of distributions
    Levi, Reut; Ron, Dana; Rubinfeld, Ronitt
  • The distribution of Rademacher sums
    Montgomery-Smith, Stephen J.
  • Property testing of massively parametrized problems—A survey
    Newman, Ilan
  • Public vs
    Newman, Ilan; Szegedy, Mario
  • Estimating entropy on m bins given fewer than m samples
    Paninski, Liam
  • A coincidence-based test for uniformity given very sparsely sampled discrete data
    Paninski, Liam
  • A Theory of Interpolation of Normed Spaces
    Peetre, Jaak
  • Asymptopia
    Pollard, David
  • Strong lower bounds for approximating distributions support size and the distinct elements problem
    Raskhodnikova, Sofya; Ron, Dana; Shpilka, Amir; Smith, Adam
  • Taming big probability distributions
    Rubinfeld, Ronitt
  • Testing monotone high-dimensional distributions
    Rubinfeld, Ronitt; Servedio, Rocco A.
  • Robust characterization of polynomials with applications to program testing
    Rubinfeld, Ronitt; Sudan, Madhu
  • A CLT and tight lower bounds for estimating entropy
    Valiant, Gregory; Valiant, Paul
  • Estimating the unseen: A sublinear-sample canonical estimator of distributions
    Valiant, Gregory; Valiant, Paul
  • Estimating the unseen: An n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs
    Valiant, Gregory; Valiant, Paul
  • The power of linear estimators
    Valiant, Gregory; Valiant, Paul
  • An automatic inequality prover and instance optimal identity testing
    Valiant, Gregory; Valiant, Paul
  • Testing symmetric properties of distributions
    Valiant, Paul
  • Minimax rates of entropy estimation on large alphabets via best polynomial approximation
    Wu, Yihong; Yang, Pengkun
  • Assouad, fano, and le cam
    Yu, Bin