論文の概要: Entropy Equivalence Testing
- arxiv url: http://arxiv.org/abs/2605.23225v1
- Date: Fri, 22 May 2026 04:35:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-25 17:29:20.200018
- Title: Entropy Equivalence Testing
- Title（参考訳）: エントロピー等価テスト
- Authors: Clément L. Canonne, Yash Pote, Jonathan Scarlett, Joy Qiping Yang,
- Abstract要約: 本稿では,確率分布のエンヘントロピー同値検定の問題を紹介する。
この課題に対する最適なサンプルの複雑さは、クローズネステストよりも著しく低いことを示します。
我々はこの結果を利用して、低次EmphBayesianネットワークの(標準)クローズネスに対する最初の非自明なテストアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 43.089793195592115
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the problem of \emph{entropy equivalence testing} for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions $p,q$ and a parameter $\varepsilon \in(0,1/2]$, between $p=q$ and $|H(p)-H(q)| \geq \varepsilon$ (where $H$ denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree \emph{Bayesian networks}, which significantly improves on either the sample or time complexity of a baseline based on full learning.
- Abstract（参考訳）: 確率分布に対する \emph{entropy equivalence testing} の問題、よく研究された近接性テスト問題の緩和、すなわち分布テストアルゴリズムは2つの未知の分布から与えられたサンプルを$p,q$と$\varepsilon \in(0,1/2]$、$p=q$と$|Hで区別することしか要求されない。
(p)-H
(q)| \geq \varepsilon$(ここで$H$はシャノンエントロピーを表す)
本稿では,このタスクの時間的およびサンプル効率のよいアルゴリズムを提案し,このタスクの最適なサンプル複雑性が,クローズネステストよりも著しく低いことを示す。
アプリケーションとして、この結果を利用して、低次 'emph{Bayesian network} の(標準的な)近接性に対する最初の非自明なテストアルゴリズムを提供する。
関連論文リスト
- Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Replicable Uniformity Testing [1.5883812630616523]
この研究は、アルゴリズムの複製性という枠組みの下で一様性テストを再考する。
我々は, $tildeO(sqrtn varepsilon-2 rho-1)$サンプルのみを用いて複製可能なテスタを得る。
論文 参考訳（メタデータ） (2024-10-12T02:55:17Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Near-Optimal Degree Testing for Bayes Nets [6.814860712547177]
問題の複雑さのサンプルは$tildeTheta (2n/2/varepsilon2)$である。
我々のアルゴリズムは、これまでサンプル最適化テスターの獲得に用いられてきたテスト・バイ・ラーニング・フレームワークに依存している。
論文 参考訳（メタデータ） (2023-04-13T03:48:31Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。