論文の概要: Tight Sample Bounds for Renyi and Min-Entropy Estimation

• arxiv url: http://arxiv.org/abs/2607.16966v1
• Date: Sat, 18 Jul 2026 21:01:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-21 18:48:37.312353
• Title: Tight Sample Bounds for Renyi and Min-Entropy Estimation
• Title（参考訳）: Renyi と Min-Entropy 推定のためのタイトサンプル境界
• Abstract要約: サンプルからエントロピーを推定することは、情報理論とプロパティテストにおいて基礎となる。 定数加法精度に対する最小エントロピー推定が標本複雑性$(klog k)$であることを証明する。
• 参考スコア（独自算出の注目度）: 4.866431869728017
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a $k$-symbol alphabet using $Θ(k/\log k)$ samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-$α$ R'{e}nyi entropy, $H_α$. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for $k$ and integer $α>1$; our lower bounds also hold for noninteger $α\ge1.001$. We prove that min-entropy estimation to constant additive accuracy has sample complexity $Θ(k\log k)$. The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires $Θ(\log^2 k)$ more samples than Shannon entropy and corrects a previously stated $Θ(k/\log k)$ characterization. For every integer $2\leα\le c_0\log k$, we prove the matching fixed-accuracy bound $Θ_{c_0}(αk^{1-1/α})$. Previous results gave $Ω_α(k^{1-1/α})$ for fixed integer $α>1$ and $O_{c_0}(α^2k^{1-1/α})$ for all integer $α>1$. Our upper bound analyzes an unbiased falling-factorial estimator based on $α$-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor $α$ is unavoidable. For every real $1.001\leα\le c_0\log k$, we prove the uniform lower bound $Ω_{c_0}(αk^{1-1/α})$. Finally, since $0\le H_α(p)-H_\infty(p)\le\log k/(α-1)$, min-entropy uniformly approximates $H_α$ when $α$ is a sufficiently large multiple of $\log k$. Combining this reduction with our min-entropy bounds gives $Θ_\varepsilon(k\log k)$ sample complexity in the high-order regime.
• Abstract（参考訳）: サンプルからエントロピーを推定することは、情報理論とプロパティテストにおいて基礎となる。 シャノンエントロピーは平均不確かさを測り、$(k/\log k)$サンプルを用いて$k$-シンボルアルファベットに対して一定の加算精度を推定することができる。 最小エントロピーは最も可能性の高い記号にのみ依存する。 どちらも位数-$α$ R'{e}nyi entropy, $H_α$の特別な場合である。 我々は、min-エントロピーとR'{e}nyiエントロピーを$k$と整数$α>1$で推定するサンプルの複雑さを特徴づける。 我々は、定数加法精度に対する最小エントロピー推定がサンプル複雑性を持つことを証明している。 上界は、ダイアドグルーピングによる最大の経験周波数と濃度を使用する。 一致した下界は、一様ランダムな位置にわずかに重いシンボルを隠している。 したがって、min-エントロピーはシャノンエントロピーよりも$(\log^2 k)$多くのサンプルを必要とし、前述した$(k/\log k)$特徴づけを補正する。 任意の整数 $2\leα\le c_0\log k$ に対して、一致する固定精度の有界を証明します。 以前の結果は、固定整数$α>1$に対して$Ω_α(k^{1-1/α})$と全ての整数$α>1$に対して$O_{c_0}(α^2k^{1-1/α})$を与えた。 我々の上界は、$α$-wayの衝突に基づく不偏分解係数推定器を解析し、一方、隠れ重重座標構造は、一致する下界を与え、$α$が避けられないことを示す。 すべての実数 $1.001\leα\le c_0\log k$ に対して、一様下界 $Ω_{c_0}(αk^{1-1/α})$ を証明する。 最後に、$0\le H_α(p)-H_\infty(p)\le\log k/(α-1)$であるため、min-エントロピーは$H_α$を、$α$が$\log k$の十分大きい倍数であるときに一様近似する。 この還元をミンエントロピー境界と組み合わせることで、高次状態におけるサンプルの複雑さは$\_\varepsilon(k\log k) となる。

関連論文リスト

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• The Sample Complexity of Fidelity Estimation to a Known Rank-$r$ Reference State Is $\widetildeΘ(r^2/\varepsilon^2)$ [0.0]
  量子スペクトル推定の精度を一定に抑えるために、ほぼ四分法以下の$widetilde(r2)$を証明した。 また、量子スペクトル推定を一定精度で行うために、ほぼ四分法以下の$widetilde(r2)$を証明した。
  論文  参考訳（メタデータ） (2026-08-03T06:43:01Z)
• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity [6.812247730094931]
  任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。 また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
  論文  参考訳（メタデータ） (2023-09-25T09:50:15Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Estimation of Entropy in Constant Space with Improved Sample Complexity [14.718968517824756]
  サンプルの複雑さを$(k/epsilon2)cdot textpolylog (1/epsilon)$に削減する新しい定数メモリスキームを提供する。 これは$textpolylog (1/epsilon)$ factorまで最適であると推測する。
  論文  参考訳（メタデータ） (2022-05-19T18:51:28Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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