Open Problems:69 - Revision history

Krzysztof Onak: Updating header

2016-01-18T18:36:18Z

Updating header

Krzysztof Onak: Krzysztof Onak moved page Waiting:Clement to Open Problems:69 without leaving a redirect: Moving to main list of problems

2016-01-18T18:35:39Z

Krzysztof Onak moved page Waiting:Clement to Open Problems:69 without leaving a redirect: Moving to main list of problems

Krzysztof Onak: Small edits

2016-01-12T21:29:10Z

Small edits

Ccanonne at 22:13, 10 January 2016

2016-01-10T22:13:33Z

Ccanonne at 22:13, 10 January 2016

2016-01-10T22:13:02Z

Ccanonne at 22:12, 10 January 2016

2016-01-10T22:12:26Z

Ccanonne at 22:08, 10 January 2016

2016-01-10T22:08:12Z

Krzysztof Onak: Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Clément Canonne }} The open problem will appear here."

2016-01-10T04:27:36Z

Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Clément Canonne }} The open problem will appear here."

New page

{{Header
|title=Title of the problem
|source=baltimore16
|who=Clément Canonne
}}
The open problem will appear here.

@@ Line 5: / Line 5: @@
 }}
-Let $p$ be an unknown (discrete) probability distribution over product space $[n]\times [n]$, and $\varepsilon\in(0,1]$. Suppose $p$ is ''$\varepsilon$-close to independent'' (in total variation distance), i.e. there exists a product distribution $q=q_1\times q_2$ on $[n]\times [n]$ such that
+Let $p$ be an unknown (discrete) probability distribution over product space $[n]\times [n]$, and $\varepsilon\in(0,1]$. Suppose $p$ is ''$\varepsilon$-close to independent'' (in total variation distance), i.e., there exists a product distribution $q=q_1\times q_2$ on $[n]\times [n]$ such that
 $$
 d_{\rm TV}(p,q) = \max_{S\subseteq [n]\times[n]} \left( p(S) - q(S)\right) \leq \varepsilon.
 $$
-Given access to independent samples drawn from $p$, the goal is to ''correct'' $p$, that is to provide access to independent samples from a distribution $\tilde{p}$ satisfying (with high probability):
+Given access to independent samples drawn from $p$, the goal is to ''correct'' $p$, that is, to provide access to independent samples from a distribution $\tilde{p}$ satisfying (with high probability):
-# $d_{\rm TV}(p,\tilde{p}) = O(\varepsilon)$ [the corrected distribution is faithful to the original one]
+* $d_{\rm TV}(p,\tilde{p}) = O(\varepsilon)$ (i.e., the corrected distribution is faithful to the original one),
-# $\tilde{p} = \tilde{p}_1\times \tilde{p}_2$  [the corrected distribution is an actual product distribution]
+* $\tilde{p} = \tilde{p}_1\times \tilde{p}_2$  (i.e., the corrected distribution is a product distribution),
 with a ''rate'' as good as possible, where the rate is the number of samples from $p$ required to provide a single sample from $\tilde{p}$.
-Achieving a rate of $2$ is simple: drawing $(x_1,y_1)$ and $(x_2,y_2)$ from $p$ and outputting $(x_1,y_2)$ provides sample access to $\tilde{p} = p_1\times p_2$, which can be shown to be $3\varepsilon$-close to $p$. {{cite|BatuFFKRW-01}}
+Achieving a rate of $2$ is simple: drawing $(x_1,y_1)$ and $(x_2,y_2)$ from $p$ and outputting $(x_1,y_2)$ provides sample access to $\tilde{p} = p_1\times p_2$, which can be shown to be $3\varepsilon$-close to $p$ {{cite|BatuFFKRW-01}}.
-'''Question 1:''' is a rate $r < 2$ achievable? What about an amortized rate (to provide $q=o(n^2)$ samples from the same distribution $\tilde{p}$)<ref>The restriction $o(n^2)$ comes from the fact that, after $n^2$ samples, one can actually learn the distribution $p$, and then compute a good corrected definition $\tilde{p}$ offline. Hence, the range of interest is when having to provide a number of samples negligible in front of what learning $p$ would require.</ref>?
+'''Question 1:''' Is a rate $r < 2$ achievable? What about an amortized rate (to provide $q=o(n^2)$ samples from the same distribution $\tilde{p}$<ref>The restriction $o(n^2)$ comes from the fact that, after $n^2$ samples, one can actually learn the distribution $p$, and then compute a good corrected definition $\tilde{p}$ offline. Hence, the range of interest is when having to provide a number of samples negligible in front of what learning $p$ would require.</ref>)?
-'''Question 2:'''What about the same question, when relaxing the second item to only ask that $p$ be ''improved'': that is, to provide sample access to a distribution $\tilde{p}$ guaranteed to be $\frac{\varepsilon}{2}$-close to a product distribution?
+'''Question 2:''' What about the same question, when relaxing the second item to only ask that $p$ be ''improved'': that is, to provide sample access to a distribution $\tilde{p}$ guaranteed to be $\frac{\varepsilon}{2}$-close to a product distribution?
-'''Note:''' this question fits within the framework of "sampling improvers," as introduced in {{cite|CanonneGR-16}}: where, given access to a probability distribution only close to having a desired property, one aims at providing access to corrected samples from a nearby distribution that exhibits this property.
+'''Note:''' This question fits within the framework of &ldquo;sampling improvers,&rdquo; introduced in {{cite|CanonneGR-16}}. In this framework, given access to a probability distribution only close to having a desired property, one aims at providing access to corrected samples from a nearby distribution that exhibits this property.
 <references />

@@ Line 12: / Line 12: @@
 Given access to independent samples drawn from $p$, the goal is to ''correct'' $p$, that is to provide access to independent samples from a distribution $\tilde{p}$ satisfying (with high probability):
 # $d_{\rm TV}(p,\tilde{p}) = O(\varepsilon)$ [the corrected distribution is faithful to the original one]
-# $\tilde{p} = p_1\times p_2$  [the corrected distribution is an actual product distribution]
+# $\tilde{p} = \tilde{p}_1\times \tilde{p}_2$  [the corrected distribution is an actual product distribution]
 with a ''rate'' as good as possible, where the rate is the number of samples from $p$ required to provide a single sample from $\tilde{p}$.

@@ Line 17: / Line 17: @@
 Achieving a rate of $2$ is simple: drawing $(x_1,y_1)$ and $(x_2,y_2)$ from $p$ and outputting $(x_1,y_2)$ provides sample access to $\tilde{p} = p_1\times p_2$, which can be shown to be $3\varepsilon$-close to $p$. {{cite|BatuFFKRW-01}}
-'''Question:''' is a rate $r < 2$ achievable? What about an amortized rate (to provide $q=o(n^2)$ samples from the same distribution $\tilde{p}$)<ref>The restriction $o(n^2)$ comes from the fact that, after $n^2$ samples, one can actually learn the distribution $p$, and then compute a good corrected definition $\tilde{p}$ offline. Hence, the range of interest is when having to provide a number of samples negligible in front of what learning $p$ would require.</ref>?
+'''Question 1:''' is a rate $r < 2$ achievable? What about an amortized rate (to provide $q=o(n^2)$ samples from the same distribution $\tilde{p}$)<ref>The restriction $o(n^2)$ comes from the fact that, after $n^2$ samples, one can actually learn the distribution $p$, and then compute a good corrected definition $\tilde{p}$ offline. Hence, the range of interest is when having to provide a number of samples negligible in front of what learning $p$ would require.</ref>?
-What about the same question, when relaxing the second item to only ask that $p$ be ''improved'': that is, to provide sample access to a distribution $\tilde{p}$ guaranteed to be $\frac{\varepsilon}{2}$-close to a product distribution?
+'''Question 2:'''What about the same question, when relaxing the second item to only ask that $p$ be ''improved'': that is, to provide sample access to a distribution $\tilde{p}$ guaranteed to be $\frac{\varepsilon}{2}$-close to a product distribution?
-'''Note:''' this question fits within the framework of "sampling improvers," as introduced in [CanonneGR-16]: where, given access to a probability distribution only close to having a desired property, one aims at providing access to corrected samples from a nearby distribution that exhibits this property.
+'''Note:''' this question fits within the framework of "sampling improvers," as introduced in {{cite|CanonneGR-16}}: where, given access to a probability distribution only close to having a desired property, one aims at providing access to corrected samples from a nearby distribution that exhibits this property.
 <references />

@@ Line 17: / Line 17: @@
 Achieving a rate of $2$ is simple: drawing $(x_1,y_1)$ and $(x_2,y_2)$ from $p$ and outputting $(x_1,y_2)$ provides sample access to $\tilde{p} = p_1\times p_2$, which can be shown to be $3\varepsilon$-close to $p$. {{cite|BatuFFKRW-01}}
-'''Question:''' is a rate $r < 2$ achievable? What about an amortized rate (to provide $q=o(n^2)$ samples from the same distribution $\tilde{p}$)<ref>The restriction $o(n^2)$ comes from the fact that, after $n^2$ samples, one can actually learn the distribution $p$, and then compute a good corrected definition $\tilde{p}$ offline.</ref>?
+'''Question:''' is a rate $r < 2$ achievable? What about an amortized rate (to provide $q=o(n^2)$ samples from the same distribution $\tilde{p}$)<ref>The restriction $o(n^2)$ comes from the fact that, after $n^2$ samples, one can actually learn the distribution $p$, and then compute a good corrected definition $\tilde{p}$ offline. Hence, the range of interest is when having to provide a number of samples negligible in front of what learning $p$ would require.</ref>?
 What about the same question, when relaxing the second item to only ask that $p$ be ''improved'': that is, to provide sample access to a distribution $\tilde{p}$ guaranteed to be $\frac{\varepsilon}{2}$-close to a product distribution?
 <references />

@@ Line 1: / Line 1: @@
 {{Header
 |source=baltimore16
 |who=Clément Canonne

← Older revision	Revision as of 18:35, 18 January 2016
(No difference)