NDLI: An Automatic Inequality Prover and Instance Optimal Identity Testing

Please wait, while we are loading the content...

An Automatic Inequality Prover and Instance Optimal Identity Testing

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Valiant, Paul Valiant, Gregory
Copyright Year	2017
Abstract	We consider the problem of verifying the identity of a distribution: Given the description of a distribution over a discrete finite or countably infinite support, $p=(p_1,p_2,\ldots)$, how many samples (independent draws) must one obtain from an unknown distribution, $q$, to distinguish, with high probability, the case that $p=q$ from the case that the total variation distance ($L_1$ distance) $\\|p-q\\|_1 \ge \epsilon$? We resolve this question, up to constant factors, on an instance by instance basis: there exist universal constants $c,c'$ and a function $f(p,\epsilon)$ on the known distribution $p$ and error parameter $\epsilon$, such that our tester distinguishes $p=q$ from $\\|p-q\\|_1\ge \epsilon$ using $f(p,\epsilon)$ samples with success probability $>2/3$, but no tester can distinguish $p=q$ from $\\|p-q\\|_1\ge c\cdot \epsilon$ when given $c'\cdot f(p,\epsilon)$ samples. The function $f(p,\epsilon)$ is upper-bounded by a multiple of $\frac{\\|p\\|_{2/3}}{\epsilon^2}$ but is more complicated. This result generalizes and tightens previous results: since distributions of support at most $n$ have $L_{2/3}$ norm bounded by $\sqrt{n},$ this result immediately shows that for such distributions, $O(\sqrt{n}/{\epsilon^2})$ samples suffice, tightening the previous bound of $O(\frac{\sqrt{n}\ {\rm polylog}\ n}{\epsilon^4})$ and matching the (tight) results for the case that $p$ is the uniform distribution of support $n$. The analysis of our very simple testing algorithm involves several hairy inequalities. To facilitate this analysis, we give a complete characterization of a general class of inequalities---generalizing Cauchy--Schwarz, Hölder's inequality, and the monotonicity of $L_p$ norms. Specifically, we characterize the set of sequences of triples $(a,b,c)_i=(a_1,b_1,c_1),\ldots,(a_r,b_r,c_r)$ for which it holds that for all finite sequences of positive numbers $(x)_j=x_1,\ldots$ and $(y)_j=y_1,\ldots,$ $\prod_{i=1}^r ( \sum_j x_j^{a_i} y_j^{b_i})^{c_i} \ge 1.$ For example, the standard Cauchy--Schwarz inequality corresponds to the triples $(a,b,c)_i=(1,0,\frac{1}{2}),$ $\,(0,1,\frac{1}{2}),$ $\,(\frac{1}{2},\frac{1}{2},-1)$. Our characterization is constructive and algorithmic, leveraging linear programming to prove or refute an inequality, which would otherwise have to be investigated, through trial and error, by hand. We hope the computational nature of our characterization will be useful to others and facilitate analyses like the one here.
Sponsorship	Alfred P. Sloan Foundation. National Science Foundation
Starting Page	429
Ending Page	455
Page Count	27
File Format	PDF
ISSN	00975397
DOI	10.1137/151002526
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1 (Special Section on the Fifty-Fifth Annual ACM Symposium on Foundations of Computer Science (FOCS 2014))
Volume Number	46
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2017-02-28
Access Restriction	Subscribed
Subject Keyword	Hypothesis testing identity testing Analysis of algorithms and problem complexity Theorem proving chi-squared test Inequalities for sums, series and integrals inequality prover Holder's inequality property testing instance optimality Algorithmic information theory
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Automatic Inequality Prover and Instance Optimal Identity Testing

Some Weighted Ostrowski Type Inequalities

Generalizations of Holder's and some related integral inequalities on fractal space

Brascamp-Lieb inequality and quantitative versions of Helly's theorem

Godzilla - a new approach for automatic theorem proving in combinatorics.

A Bayesian Chi-squared test for hypothesis testing

Generalization of Popoviciu-Type Inequalities Via Fink’s Identity

An optimal Hardy-Morrey inequality

Generalizations of Sherman’s inequality

An Automatic Inequality Prover and Instance Optimal Identity Testing

Similar Documents

An Automatic Inequality Prover and Instance Optimal Identity Testing

Some Weighted Ostrowski Type Inequalities

Generalizations of Holder's and some related integral inequalities on fractal space

Brascamp-Lieb inequality and quantitative versions of Helly's theorem

Godzilla - a new approach for automatic theorem proving in combinatorics.

A Bayesian Chi-squared test for hypothesis testing

Generalization of Popoviciu-Type Inequalities Via Fink’s Identity

An optimal Hardy-Morrey inequality

Generalizations of Sherman’s inequality

An Automatic Inequality Prover and Instance Optimal Identity Testing