Open Problems:82 - Revision history

Krzysztof Onak: Making parentheses in an equaition nicer

2017-11-08T06:10:46Z

Making parentheses in an equaition nicer

Krzysztof Onak: Cleaning header, small changes

2017-11-08T06:09:50Z

Cleaning header, small changes

Krzysztof Onak: Krzysztof Onak moved page Waiting:Beyond identity testing to Open Problems:82: The problem is ready for publication

2017-11-08T06:06:43Z

Krzysztof Onak moved page Waiting:Beyond identity testing to Open Problems:82: The problem is ready for publication

Ccanonne at 18:23, 20 October 2017

2017-10-20T18:23:23Z

Ccanonne at 18:22, 20 October 2017

2017-10-20T18:22:55Z

Ccanonne at 18:13, 20 October 2017

2017-10-20T18:13:41Z

Ccanonne: Created page with "{{Header |title=Beyond identity testing |source=focs17 |who=Clément Canonne }} Given access to i.i.d. samples from two unknown probability distributions $p,q$ over a discrete..."

2017-10-20T18:10:56Z

Created page with "{{Header |title=Beyond identity testing |source=focs17 |who=Clément Canonne }} Given access to i.i.d. samples from two unknown probability distributions $p,q$ over a discrete..."

New page

{{Header
|title=Beyond identity testing
|source=focs17
|who=Clément Canonne
}}
Given access to i.i.d. samples from two unknown probability distributions $p,q$ over a discrete domain (say $[n]=\{1,\dots,n\}$) and distance parameter $\varepsilon\in(0,1]$, the ''closeness'' problem asks to distinguish w.h.p. between (i) $p=q$ and (ii) $\operatorname{d}_{\rm TV}(p,q)>\varepsilon$. (The ''identity'' problem is the analogue when $q$ is fixed and explicitly known beforehand.)

Closeness up to a permutation would then be the variant where one must test whether $p,q$ are equal ''up to relabeling of the elements'':
(i) $\exists \pi\in\mathcal{S}_n$ s.t. $p=q\circ\pi$ vs. (ii) $\forall \pi\in\mathcal{S}_n$, $\operatorname{d}_{\rm TV}(p,q\circ \pi)>\varepsilon$. Results of Valiant and Valiant {{cite|ValiantV-11}} imply that this question has sample complexity $\Theta(\frac{n}{\eps^2\log n})$.

The most general question then is
Given a fixed class $\mathcal{F}$ of functions from $[n]$ to $[m]$, distinguish between (i) $\exists \pi\in\mathcal{F}$ s.t. $p=q\circ\pi$ vs. (ii) $\forall \pi\in\mathcal{F}$, $\operatorname{d}_{\rm TV}(p,q\circ \pi)>\varepsilon$.

In particular, one can study how the sample complexity depends on $\mathcal{F}$, or what it is for some classes of interest (e.g., $n=m$ for $\mathcal{F}$ a subgroup of the symmetric group $\mathcal{S}_n$; or $m\ll n$ and $\mathcal{F}$ being a class of "coarsenings," captuing whether $p,q$ are the same distribution but with a different discretization/binning)..

@@ Line 6: / Line 6: @@
 Equivalence up to a permutation would then be the variant where one must test whether $p$ and $q$ are equal ''up to relabeling of the elements'':
-(i) $\exists \pi\in\mathcal{S}_n$ s.t. $p=q\circ\pi$ vs. (ii) $\forall \pi\in\mathcal{S}_n$, $\operatorname{d}_{\rm TV}(p,q\circ \pi)>\varepsilon$. Results of Valiant and Valiant {{cite|ValiantV-11}} imply that this question has sample complexity $\Theta(\frac{n}{\varepsilon^2\log n})$.
+(i) $\exists \pi\in\mathcal{S}_n$ s.t. $p=q\circ\pi$ vs. (ii) $\forall \pi\in\mathcal{S}_n$, $\operatorname{d}_{\rm TV}(p,q\circ \pi)>\varepsilon$. Results of Valiant and Valiant {{cite|ValiantV-11}} imply that this question has sample complexity $\Theta\left(\frac{n}{\varepsilon^2\log n}\right)$.
 The most general question then is:

@@ Line 1: / Line 1: @@
 {{Header
 |source=focs17
 |who=Clément Canonne
 }}
-Given access to i.i.d. samples from two unknown probability distributions $p,q$ over a discrete domain (say $[n]=\{1,\dots,n\}$) and distance parameter $\varepsilon\in(0,1]$, the ''equivalence'' (also known as ''closeness'') testing problem asks to distinguish w.h.p. between (i) $p=q$ and (ii) $\operatorname{d}_{\rm TV}(p,q)>\varepsilon$. (The ''identity'' problem is the analogue when $q$ is fixed and explicitly known beforehand.)
+Given access to i.i.d. samples from two unknown probability distributions $p$ and $q$ over a discrete domain (say $[n]=\{1,\dots,n\}$) and distance parameter $\varepsilon\in(0,1]$, the ''equivalence'' (also known as ''closeness'') testing problem asks to distinguish w.h.p. between (i) $p=q$ and (ii) $\operatorname{d}_{\rm TV}(p,q)>\varepsilon$. (The ''identity'' problem is the analogue when $q$ is fixed and explicitly known beforehand.)
-Equivalence up to a permutation would then be the variant where one must test whether $p,q$ are equal ''up to relabeling of the elements'':
+Equivalence up to a permutation would then be the variant where one must test whether $p$ and $q$ are equal ''up to relabeling of the elements'':
 (i) $\exists \pi\in\mathcal{S}_n$ s.t. $p=q\circ\pi$ vs. (ii) $\forall \pi\in\mathcal{S}_n$, $\operatorname{d}_{\rm TV}(p,q\circ \pi)>\varepsilon$. Results of Valiant and Valiant {{cite|ValiantV-11}} imply that this question has sample complexity $\Theta(\frac{n}{\varepsilon^2\log n})$.
-The most general question then is
+The most general question then is:
 : Given a fixed class $\mathcal{F}$ of functions from $[n]$ to $[m]$, distinguish between (i) $\exists \pi\in\mathcal{F}$ s.t. $p=q\circ\pi$ vs. (ii) $\forall \pi\in\mathcal{F}$, $\operatorname{d}_{\rm TV}(p,q\circ \pi)>\varepsilon$.
-In particular, one can study how the sample complexity depends on $\mathcal{F}$, or what it is for some classes of interest (e.g., $n=m$ for $\mathcal{F}$ a subgroup of the symmetric group $\mathcal{S}_n$; or $m\ll n$ and $\mathcal{F}$ being a class of "coarsenings," capturing whether $p,q$ are the same distribution but with a different discretization/binning).
+In particular, one can study how the sample complexity depends on $\mathcal{F}$, or what it is for some classes of interest (e.g., $n=m$ for $\mathcal{F}$ a subgroup of the symmetric group $\mathcal{S}_n$; or $m\ll n$ and $\mathcal{F}$ being a class of &ldquo;coarsenings,&rdquo; capturing whether $p$ and $q$ are the same distribution but with a different discretization/binning).

@@ Line 6: / Line 6: @@
 Given access to i.i.d. samples from two unknown probability distributions $p,q$ over a discrete domain (say $[n]=\{1,\dots,n\}$) and distance parameter $\varepsilon\in(0,1]$, the ''equivalence'' (also known as ''closeness'') testing problem asks to distinguish w.h.p. between (i) $p=q$ and (ii) $\operatorname{d}_{\rm TV}(p,q)>\varepsilon$. (The ''identity'' problem is the analogue when $q$ is fixed and explicitly known beforehand.)
-Closeness up to a permutation would then be the variant where one must test whether $p,q$ are equal ''up to relabeling of the elements'':
+Equivalence up to a permutation would then be the variant where one must test whether $p,q$ are equal ''up to relabeling of the elements'':
 (i) $\exists \pi\in\mathcal{S}_n$ s.t. $p=q\circ\pi$ vs. (ii) $\forall \pi\in\mathcal{S}_n$, $\operatorname{d}_{\rm TV}(p,q\circ \pi)>\varepsilon$. Results of Valiant and Valiant {{cite|ValiantV-11}} imply that this question has sample complexity $\Theta(\frac{n}{\varepsilon^2\log n})$.

← Older revision	Revision as of 06:06, 8 November 2017
(No difference)