$ ell_r $ normの離散分布を学習する

$ P =(p_1、 ldots、p_d)$を$ [d] $の分布とする。 $ n $ iidが$ P
$から引き出されたとすると、我々は経験的推定値 $ hat P_n =( hat p_ {n、1}、 ldots、 hat
p_ {n、d})$です。 $ r $ -riskを定義しましょう によって $$ J_n ^ r = sum_ {i = 1}
^ d | p_i- hat p_ {n、i} | ^ r。 $$

それは知られている(例えば、補助定款2.4 ここを参照) $ hat P_n
$が最尤(すなわち経験的頻度)推定量であるとき、 $ r ge2 $、 我々は持っています $ mathbb {E} [J_n
^ r] le1/n $である。特に、予想される$ r $は、無次元の率で減衰する。

$ r = 1 $の場合、リスクは$ Theta( sqrt
{d/n})$のミニマックス・レートで減衰することも知られています。

Question: what is known for $1

ベストアンサー

ClémentCanonneと私はある時点でこれを解決しました。

Let $X_j$ be the number of realizations of $j in [d]$. So
$mathbb{E} X_j = np_j$. begin{align*} mathbb{E} J_n^r &=
mathbb{E} |hat{P}_n – P |_r^r \ &= frac{1}{n^r}
sum_{j=1}^d mathbb{E} |X_j – mathbb{E}X_j|^r \ &leq
frac{1}{n^r} sum_{j=1}^d 3mathbb{E} X_j & (*) \ &=
frac{3}{n^{r-1}} . end{align*} We get $(*)$ by a slightly tedious
argument you can find in Theorem 5.1 of [1] or I can add here
later. It just uses the extreme cases of $r=1$ or $r=2$.

特にこれは次元のない境界を与える。しかし、標準$ p $ -normの不等式と、$ 2 $
-normの上限を使用するだけで、次元に依存する上限を得ることができます。観測値の数に比べて次元が小さい場合、次元依存境界はより良いでしょう。$
d leq O(n ^ {1/q})$のときは信じますが、二重チェック($ q = 1 – 1/r $)。

[1]: “$ell_p$ Testing and Learning of Discrete Distributions”
(Bo Waggoner, ITCS 2015), https://arxiv.org/abs/1412.2314

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です