論文の概要: Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability
- arxiv url: http://arxiv.org/abs/2507.17316v2
- Date: Thu, 30 Oct 2025 11:32:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-31 22:45:08.966317
- Title: Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability
- Title（参考訳）: 確率の高いKullback-Leiblerダイバージェンスにおける極小離散分布推定
- Authors: Dirk van der Hoeven, Julia Olkhovskaia, Tim van Erven,
- Abstract要約: クルバック・リーブラー分岐の確率が高い大きさの領域で離散分布を推定する問題を考察する。
最適率は$big(K + ln(K)ln(K) + ln(K)ln(1/delta)big) /n$ at error probability $delta$ and sample size $n$, which pins down the rate up the doublely logarithmic factor $ln ln K$ that multiplies $K$。
- 参考スコア（独自算出の注目度）: 11.180770249745791
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the fundamental problem of estimating a discrete distribution on a domain of size~$K$ with high probability in Kullback-Leibler divergence. We provide upper and lower bounds on the minimax estimation rate, which show that the optimal rate is between $\big(K + \ln(K)\ln(1/\delta)\big) /n$ and $\big(K\ln\ln(K) + \ln(K)\ln(1/\delta)\big) /n$ at error probability $\delta$ and sample size $n$, which pins down the rate up to the doubly logarithmic factor $\ln \ln K$ that multiplies $K$. Our upper bound uses techniques from online learning to construct a novel estimator via online-to-batch conversion. Perhaps surprisingly, the tail behavior of the minimax rate is worse than for the squared total variation and squared Hellinger distance, for which it is $\big(K + \ln(1/\delta)\big) /n$, i.e.\ without the $\ln K$ multiplying $\ln (1/\delta)$. As a consequence, we cannot obtain a fully tight lower bound from the usual reduction to these smaller distances. Moreover, we show that this lower bound cannot be achieved by the standard lower bound approach based on a reduction to hypothesis testing, and instead we need to introduce a new reduction to what we call weak hypothesis testing. We investigate the source of the gap with other divergences further in refined results, which show that the total variation rate is achievable for Kullback-Leibler divergence after all (in fact by he maximum likelihood estimator) if we rule out outcome probabilities smaller than $O(\ln(K/\delta) / n)$, which is a vanishing set as $n$ increases for fixed $K$ and~$\delta$. This explains why minimax Kullback-Leibler estimation is more difficult than asymptotic estimation.
- Abstract（参考訳）: クルバック・リーブラー分岐の確率が高い大きさの領域〜$K$の離散分布を推定する根本的な問題を考える。
最適値は $\big(K + \ln(K)\ln(1/\delta)\big) /n$ と $\big(K\ln\ln(K) + \ln(K)\ln(1/\delta)\big) /n$ 誤差確率 $\delta$ とサンプルサイズ $n$ の間にあることを示す。
上層部ではオンライン学習の手法を用いて,オンライン・バッチ変換による新しい推定手法を構築している。
おそらく、ミニマックスレートの尾の挙動は、正方形全体の変動と正方形ヘリンジャー距離よりも悪く、その場合は$\big(K + \ln(1/\delta)\big) /n$、すなわち$\ln K$乗算が$\ln (1/\delta)$である。
結果として、通常の還元からより小さな距離まで完全に厳密な下界を得ることはできない。
さらに、この下限は仮説テストの削減に基づく標準的な下限アプローチでは達成できないことを示し、代わりに弱い仮説テストと呼ぶものに新たな還元を導入する必要がある。
この結果から, 結果確率が$O(\ln(K/\delta) / n)$より小さい場合, クルバック・リーブラー偏差の総変動率は, 固定$K$および~$$\delta$に対して$n$増加として消滅する。
このことは、minimax Kullback-Leibler 推定が漸近的推定よりも難しい理由を説明する。
関連論文リスト
- Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
論文 参考訳（メタデータ） (2025-06-06T20:33:57Z) - On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm [54.28350823319057]
本稿では、$ell_$ノルムで測定されたAdamWの収束率$frac1Ksum_k=1KEleft[|nabla f(xk)|_1right]leq O(fracsqrtdCK1/4)を確立する。
論文 参考訳（メタデータ） (2025-05-17T05:02:52Z) - Estimating the Mixing Coefficients of Geometrically Ergodic Markov
Processes [5.00389879175348]
実数値の幾何学的エルゴード的マルコフ過程の個々の$beta$-mixing係数を1つのサンプルパスから推定する。
予想される誤差率は$mathcal O(log(n) n-1/2)$である。
論文 参考訳（メタデータ） (2024-02-11T20:17:10Z) - Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
我々はKarpとKleinbergのノイズの多いバイナリ検索モデルを再検討する。
我々は[ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta)右から1-delta$の確率で成功するアルゴリズムを作成する。
論文 参考訳（メタデータ） (2023-11-01T20:45:13Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳（メタデータ） (2023-09-29T14:14:53Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Fitting an ellipsoid to a quadratic number of random points [10.208117253395342]
問題 $(mathrmP)$ が $n$ の標準ガウス確率ベクトルを $mathbbRd$ で中心楕円体の境界に収まることを $n, d to infty$ とみなす。
任意の$varepsilon > 0$ に対して、$n leq (1 - varepsilon) d2 / 4$ ならば、$(mathrmP)$ は高い確率の解を持つ。
論文 参考訳（メタデータ） (2023-07-03T17:46:23Z) - On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
カーネル群に基づく暗黙の空間性誘導機構について述べる。
アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
論文 参考訳（メタデータ） (2021-10-12T09:36:41Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳（メタデータ） (2021-09-21T13:19:04Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。