5
$\begingroup$

Given a non-negative sequence $p=(p_i)_{i\in\mathbb{N}}\in \ell_1$ such that $\lVert p\rVert_1 = 1$,we define the two following quantities, for every $\varepsilon \in (0,1]$.

  1. Assuming, without loss of generality, that $p$ is non-increasing, let $k \geq 1$ be the smallest integer such that $\sum_{i\geq k} \leq \varepsilon$. Then we define $$ \Phi(\varepsilon, p) := \left( \sum_{i=2}^{k-1} p_i^{2/3} \right)^{3/2} \tag{1} $$ i.e., the $2/3$-quasinorm $\lVert p_{-\varepsilon}^{-\max{}} \rVert_{2/3}$ of the vector $p^{-\max{}}_{-\varepsilon}$ obtained by removing the largest element and the $\varepsilon$-tail of $p$.
  2. Defining, for $t>0$, the $K$-functional between $\ell_1$ and $\ell_2$ $$ \kappa_p(t) = \inf_{a+b=p} \lVert a\rVert_1 + t \rVert b\rVert_2 $$ and letting $$ \Psi(\varepsilon, p) := \kappa_p^{-1}(1-\varepsilon) \tag{2} $$ (right inverse, IIRC)

then can we prove upper and lower bounds relating (1) and (2)? Recent works of Valiant and Valiant [1] and Blais, Canonne, and Gur [2] imply such relation [see at the end] in a rather roundabout way (for $p$'s nontrivially point masses, i.e., say, $\lVert p\rVert_2 < 1/2$) (by showing both quantities "roughly characterize" the sample complexity of a particular hypothesis testing problem on $p$ seen as a discrete probability distribution), but a direct proof of such a relation isn't known (at least to me), even only a loose one.

Is there a direct proof relating (upper and lower bounds) $\Phi(\cdot, p)$ and $\Psi(\cdot, p)$, of the form $$ \forall p \text{ s.t. } \lVert p\rVert_2 \ll 1,\forall x, \qquad x^\alpha \Phi(c x, p) \leq \Psi(c x, p) \leq x^\beta \Phi(C x, p) $$ ?


A third related quantity, the $Q$-norm: [2] (following some previous work of Montgomery-Smith [3]) does show a relation between (2) and a third quantity interpolating between $\ell_1$ and $\ell_2$ norms, $$ T\in\mathbb{N} \mapsto \lVert p\rVert_{Q(T)} := \sup\{ \sum_{j=1}^T \left( \sum_{i\in A_j p_i^2 }\right)^{1/2} A_1,\dots,A_T \text{ partition of }\mathbb{N}\} \tag{3} $$ as, for all $t>0$ such that $t^2\in \mathbb{N}$, $$ \lVert p\rVert_{Q(t^2)} \leq \kappa_p(t) \leq \lVert p\rVert_{Q(2t^2)}. $$


The inequalities established in a roundabout way: The relation between the two quantities shown by combining [1] and [2] (which both establish sample complexity upper and lower bounds for the same hypothesis testing problem) can be rewritten as $$ \forall p, \forall \varepsilon \in(0,1/9),\qquad 1\vee \Phi(9\varepsilon,p) \lesssim 1\vee \Psi(\varepsilon,p) \lesssim 1\vee \frac{\Phi(\varepsilon/32,p)}{\varepsilon} \tag{4} $$ where $\lesssim$ is an inequality, up to some (absolute) positive constant factor.


[1] Gregory Valiant and Paul Valiant. An Automatic Inequality Prover and Instance Optimal Identity Testing. SIAM Journal on Computing 46:1, 429-455. 2017.

[2] Eric Blais, Clément Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory (TOCT), 11(2), 2019.

[3] Stephen J. Montgomery-Smith. The distribution of Rademacher sums. Proceedings of the American Mathematical Society, 109(2):517–522, 1990.

$\endgroup$
1
$\begingroup$

$\newcommand{\vp}{\varepsilon}$ $\Psi$ is not majorized by $\Phi$. Indeed, let $p=(1,0,0,\dots)$ and $\vp\in(0,1)$. Then $\Phi(\vp,p)=0$, whereas $\kappa_p(t)=1\wedge t:=\min(1,t)$ for $t>0$ and $\Psi(\vp,p)=1-\vp$.

$\endgroup$
  • $\begingroup$ That's true, and I should have seen that coming. The relations above basically all assume the quantities are at least some small constant, which I assume should follow from assuming that $p$ is not a point mass (i.e., assuming $\lVert p\rVert_2 < 1/2$ or so) $\endgroup$ – Clement C. May 21 at 0:05
  • $\begingroup$ Sorry about this. I have edited my question. $\endgroup$ – Clement C. May 21 at 0:07
  • $\begingroup$ In your edit, what do you mean by $\ll1$? $\endgroup$ – Iosif Pinelis May 21 at 1:53
  • $\begingroup$ Bounded away from one: at most $c$ for a sufficiently small constant $c>0$. $\endgroup$ – Clement C. May 21 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.