論文の概要: 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 推定が漸近的推定よりも難しい理由を説明する。

関連論文リスト

• Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis [3.8357180714081327]
  単純だが効果的な操作である勾配クリッピングは、この新しい課題をうまく処理することが知られている。 我々の研究は2つの面で既存のアプローチを改善している: 重尾雑音下でのクリップ誤りに対するフリードマンの不等式とより微細な境界のより良い利用である。 この研究を補完するために、我々は高確率と非観測収束の両方のための新しい下界を確立する。
  論文  参考訳（メタデータ） (2025-12-29T03:35:53Z)
• 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)
• Sample complexity of Schrödinger potential estimation [6.385485865934912]
  本研究では,経験的KL(Kulback-Leibler)リスク最小化器の対数ポテンシャルクラスに対する能力一般化について検討する。 サンプルサイズ$n$が無限大になる場合、過剰なKLリスクは$O(log2 n / n)$に減少する可能性がある。
  論文  参考訳（メタデータ） (2025-06-03T16:26:03Z)
• 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)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions [11.222970035173372]
  カーネルベースのスコア推定器は$widetildeOleft(n-1 t-fracd+22(tfracd2 vee 1)rightの最適平均二乗誤差を達成する 核を用いたスコア推定器は,拡散モデルで生成した試料の分布の総変動誤差に対して,極小ガウスの下での最大平均2乗誤差を$widetildeOleft(n-1/2 t-fracd4right)$上界で達成することを示す。
  論文  参考訳（メタデータ） (2024-02-23T20:51:31Z)
• 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)
• Better and Simpler Lower Bounds for Differentially Private Statistical Estimation [7.693388437377614]
  任意の$alpha le O(1)$に対して、ガウスの共分散をスペクトル誤差まで推定するには$tildeOmegaleft(fracd3/2alpha varepsilon + fracdalpha2right)$サンプルが必要である。 次に、有界な$k$thモーメントで重み付き分布の平均を推定するには$tildeOmegaleft(fracdalphak/(k-1) varepsilon +
  論文  参考訳（メタデータ） (2023-10-10T04:02:43Z)
• 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)
• Robust Nonparametric Regression under Poisoning Attack [13.470899588917716]
  敵攻撃者は、$N$のトレーニングデータセットから最大$q$のサンプル値を変更することができる。 初期解法はハマー損失最小化に基づくM推定器である。 最後の見積もりは、任意の$q$に対してほぼ最小値であり、最大$ln N$ factorまでである。
  論文  参考訳（メタデータ） (2023-05-26T09:33:17Z)
• Estimating the minimizer and the minimum value of a regression function under passive design [72.85024381807466]
  最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。 2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
  論文  参考訳（メタデータ） (2022-11-29T18:38:40Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• 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)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• 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)
• Analysis of KNN Density Estimation [56.29748742084386]
  kNN密度推定は、サポートセットが知られている場合、$ell_infty$と$ell_infty$の条件の両方で最小限最適である。 $ell_infty$エラーはミニマックス下限に到達しないが、カーネル密度推定よりは優れている。
  論文  参考訳（メタデータ） (2020-09-30T03:33:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。