2023/07/31 by Yuqian Cheng, Daniel M. Kane, Cheng, Yuqian +3
Computer Science · Mathematics · #62G10 #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #G.3 #Machine Learning (cs.LG) #Machine Learning and Algorithms #Statistical Methods and Inference #Statistical Methods in Clinical Trials #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2308.00089
openalex publication_date 2023/07/31 · openalex created_date 2023/08/03 · openalex updated_date 2026/07/28
We develop a new technique for proving distribution testing lower bounds for properties defined by inequalities involving the bin probabilities of the distribution in question. Using this technique we obtain new lower bounds for monotonicity testing over discrete cubes and tight lower bounds for log-concavity testing. Our basic technique involves constructing a pair of moment-matching families of distributions by tweaking the probabilities of pairs of bins so that one family maintains the defining inequalities while the other violates them.