Editing Open Problems:83
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 20: | Line 20: | ||
$$ | $$ | ||
Results of Daskalakis, Kamath, and Wright {{cite|DaskalakisKW-18}} show that the ''worst-case'' sample complexity remains $\Theta(\sqrt{n}/\varepsilon^2)$. Moreover, due to the quadratic dependence between Hellinger and total variation distances, both instance-specific bounds mentioned above apply, yet with possibly a quadratic gap between upper and lower bounds in terms of $\varepsilon$: leading to bounds on the instance-specific sample complexity $\Psi_{\rm H}$ of Hellinger identity testing of | Results of Daskalakis, Kamath, and Wright {{cite|DaskalakisKW-18}} show that the ''worst-case'' sample complexity remains $\Theta(\sqrt{n}/\varepsilon^2)$. Moreover, due to the quadratic dependence between Hellinger and total variation distances, both instance-specific bounds mentioned above apply, yet with possibly a quadratic gap between upper and lower bounds in terms of $\varepsilon$: leading to bounds on the instance-specific sample complexity $\Psi_{\rm H}$ of Hellinger identity testing of | ||
− | $$\Psi_{\rm TV}(q,\varepsilon) \leq \Psi_{\rm H}(q,\varepsilon) \leq \Psi_{\rm TV}(q,\varepsilon^2) | + | $$\Psi_{\rm TV}(q,\varepsilon) \leq \Psi_{\rm H}(q,\varepsilon) \leq \Psi_{\rm TV}(q,\varepsilon^2)$$. |
What is the right dependence on $\varepsilon$ of $\Psi_{\rm H}$? | What is the right dependence on $\varepsilon$ of $\Psi_{\rm H}$? | ||
''Note that in both instance-specific bounds obtained for $\Psi_{\rm TV}$, there exist (simple) examples of $q$ where $\varepsilon$ ends up ''in the exponent,'' so this quadratic gap is not innocuous even for constant $\varepsilon$.'' | ''Note that in both instance-specific bounds obtained for $\Psi_{\rm TV}$, there exist (simple) examples of $q$ where $\varepsilon$ ends up ''in the exponent,'' so this quadratic gap is not innocuous even for constant $\varepsilon$.'' |