Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Pointwise Bounds for Distribution Estimation under Communication
  Constraints   We consider the problem of estimating a $d$-dimensional discrete distribution
from its samples observed under a $b$-bit communication constraint. In contrast
to most previous results that largely focus on the global minimax error, we
study the local behavior of the estimation error and provide \emph{pointwise}
bounds that depend on the target distribution $p$. In particular, we show that
the $\ell_2$ error decays with $O\left(\frac{\lVert p\rVert_{1/2}}{n2^b}\vee
\frac{1}{n}\right)$ (In this paper, we use $a\vee b$ and $a \wedge b$ to denote
$\max(a, b)$ and $\min(a,b)$ respectively.) when $n$ is sufficiently large,
hence it is governed by the \emph{half-norm} of $p$ instead of the ambient
dimension $d$. For the achievability result, we propose a two-round
sequentially interactive estimation scheme that achieves this error rate
uniformly over all $p$. Our scheme is based on a novel local refinement idea,
where we first use a standard global minimax scheme to localize $p$ and then
use the remaining samples to locally refine our estimate. We also develop a new
local minimax lower bound with (almost) matching $\ell_2$ error, showing that
any interactive scheme must admit a $\Omega\left( \frac{\lVert p
\rVert_{{(1+\delta)}/{2}}}{n2^b}\right)$ $\ell_2$ error for any $\delta > 0$.
The lower bound is derived by first finding the best parametric sub-model
containing $p$, and then upper bounding the quantized Fisher information under
this model.
  Our upper and lower bounds together indicate that the $\mathcal{H}_{1/2}(p) =
\log(\lVert p \rVert_{{1}/{2}})$ bits of communication is both sufficient and
necessary to achieve the optimal (centralized) performance, where
$\mathcal{H}_{{1}/{2}}(p)$ is the R\'enyi entropy of order $2$. Therefore,
under the $\ell_2$ loss, the correct measure of the local communication
complexity at $p$ is its R\'enyi entropy.

32
The categories of this paper are: atom-ph
29
The categories of this paper are: funct-an
22
The categories of this paper are: chao-dyn
25
The categories of this paper are: patt-sol
9
The categories of this paper are: nlin
31
The categories of this paper are: ao-sci
19
The categories of this paper are: eess
30
The categories of this paper are: q-alg
21
The categories of this paper are: adap-org
13
The categories of this paper are: quant-ph
14
The categories of this paper are: math-ph
8
The categories of this paper are: hep-ex
17
The categories of this paper are: q-fin
10
The categories of this paper are: q-bio
3
The categories of this paper are: physics
23
The categories of this paper are: solv-int