論文の概要: Testing Distributions Against Bounded Distinguishers
- arxiv url: http://arxiv.org/abs/2607.15645v1
- Date: Fri, 17 Jul 2026 05:40:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-20 17:56:52.753804
- Title: Testing Distributions Against Bounded Distinguishers
- Title（参考訳）: 境界分散器に対する分散性試験
- Abstract要約: 高次元領域や連続領域上で分布をテストすることの難しさに感銘を受け、微分器の有界クラスに対する分布試験について検討する。
提案手法は, 高次元設定においても, サンプリング効率のよいアルゴリズムを許容する自然計算問題に留まらないことを示す。
- 参考スコア（独自算出の注目度）: 6.765217760066939
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by the challenge of testing distributions over high-dimensional or continuous domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples from an unknown distribution $P$ over a very large domain to decide between two cases: $P = P_{\mathsf{ref}}$ for a fixed reference distribution $P_{\mathsf{ref}}$, or there exists a distinguisher $f$ in a bounded class $\mathcal{F}$ which witnesses the separation $|\mathbf{E}_P[f] - \mathbf{E}_{P_{\mathsf{ref}}}[f]| > ε$. This is the task of identity testing with respect to fooling distance, a name inspired by the conceptual connection with pseudorandomness. (Formally, our model instantiates integral probability metrics from Boolean classes of bounded expressivity.) We show that testing with respect to fooling distance is not only a natural computational problem that admits sample-efficient algorithms even in high-dimensional settings, but also one that reveals and underlies connections between three seemingly unrelated areas of study: testable learning, verification of learning algorithms, and testing of structured distributions (whose "$\mathcal{A}_k$-testing" model our framework extends). These connections yield new results for all of these models, including: 1. Testable proper learners using membership queries for halfspaces and decision trees. 2. A lower bound for testable PAC verification in terms of Rademacher complexity, and a distribution-free verification protocol for disjoint unions of $k$ multidimensional rectangles. 3. Identity testers (with respect to total variation distance) for decision tree distributions and distributions with low-degree polynomial densities, over Boolean and continuous hypercube domains.
- Abstract（参考訳）: 高次元あるいは連続的な領域上の分布をテストするという課題に動機付けられ、微分器の有界クラスに対する分布テストについて研究する。
P = P_{\mathsf{ref}}$ for a fixed reference distribution $P_{\mathsf{ref}}$, or a bounded class $\mathcal{F}$ where witnesses the separation $|\mathbf{E}_P[f] - \mathbf{E}_{P_{\mathsf{ref}}}[f]| > ε$。
これは、疑似ランダム性の概念的な結びつきから着想を得た、愚かな距離に関するアイデンティティテストのタスクである。
(形式的には、我々のモデルは有界表現率のブール類から積分確率メトリクスをインスタンス化する) ドローイング距離に関するテストは、高次元の設定においてもサンプリング効率のアルゴリズムを許容する自然な計算問題であるだけでなく、テスト可能な学習、学習アルゴリズムの検証、構造化分布の試験("$\mathcal{A}_k$-testing"モデル)の3つの非関連領域間の接続を明らかにするものである。
1) ハーフスペースと決定ツリーのメンバシップクエリを使用したテスト可能な適切な学習者。
2.Rademacher複雑性の観点からの検証可能なPAC検証の低い境界、および$k$多次元矩形結合の分散のない検証プロトコル。
3) 決定木分布と低次多項式密度の分布について, ブールおよび連続超キューブ領域上での同一性テスタ(全変動距離)。
関連論文リスト
- When Are Trade-Off Functions Testable from Finite Samples? [4.706977254727891]
2つの未知確率分布のトレードオフ関数に対する有限サンプル推論について検討する。
テストの反転により、トレードオフ曲線全体に対する同時信頼バンドも得られる。
論文 参考訳（メタデータ） (2026-05-11T16:07:48Z) - Collaborative non-parametric two-sample testing [55.98760097296213]
目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。
グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。
提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
論文 参考訳（メタデータ） (2024-02-08T14:43:56Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文 参考訳（メタデータ） (2023-11-25T23:57:45Z) - Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling [5.3098033683382155]
本研究では,高次元分布におけるアイデンティティテスト問題について検討する。
私たちは、$mathsfCoordinate Oracle$という、非常に弱い条件付きサンプリングオラクルを考えています。
エントロピーの近似テンソル化(英語版)として知られる解析的性質が$n$-次元可視分布$mu$に対して成り立つならば、$tildeO(n/varepsilon)$クエリを使用して、隠れ分布$pi$に対して効率的なアイデンティティテストアルゴリズムが存在することを証明している。
論文 参考訳（メタデータ） (2022-07-19T06:49:24Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Neural Bayes: A Generic Parameterization Method for Unsupervised
Representation Learning [175.34232468746245]
本稿ではニューラルベイズと呼ばれるパラメータ化手法を提案する。
これは一般に計算が難しい統計量の計算を可能にする。
このパラメータ化のための2つの独立したユースケースを示す。
論文 参考訳（メタデータ） (2020-02-20T22:28:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。