論文の概要: Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features
- arxiv url: http://arxiv.org/abs/2407.08976v1
- Date: Fri, 12 Jul 2024 04:08:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-16 00:46:38.930620
- Title: Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features
- Title（参考訳）: ランダムフーリエ特徴を持つカーネル2サンプルテストにおける計算統計的トレードオフ
- Authors: Ikjun Choi, Ilmun Kim,
- Abstract要約: MMD(Maximum Mean Discrepancy)テストは、複雑で高次元のデータを扱う効果的なツールとして登場した。
MMD試験と同じ出力保証を準4次時間で達成できるかどうかは不明だ。
準4次時間内にMDD試験と同じミニマックス分離率が得られることを示す。
- 参考スコア（独自算出の注目度）: 3.744589644319257
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent years have seen a surge in methods for two-sample testing, among which the Maximum Mean Discrepancy (MMD) test has emerged as an effective tool for handling complex and high-dimensional data. Despite its success and widespread adoption, the primary limitation of the MMD test has been its quadratic-time complexity, which poses challenges for large-scale analysis. While various approaches have been proposed to expedite the procedure, it has been unclear whether it is possible to attain the same power guarantee as the MMD test at sub-quadratic time cost. To fill this gap, we revisit the approximated MMD test using random Fourier features, and investigate its computational-statistical trade-off. We start by revealing that the approximated MMD test is pointwise consistent in power only when the number of random features approaches infinity. We then consider the uniform power of the test and study the time-power trade-off under the minimax testing framework. Our result shows that, by carefully choosing the number of random features, it is possible to attain the same minimax separation rates as the MMD test within sub-quadratic time. We demonstrate this point under different distributional assumptions such as densities in a Sobolev ball. Our theoretical findings are corroborated by simulation studies.
- Abstract（参考訳）: 近年,2サンプル試験の手法が急増しており,その中の1つは,高次元・高次元データを扱うための有効なツールとして,最大平均離散性(MMD)テスト(Maximum Mean Discrepancy)テスト(英語版))が出現している。
成功と広く採用されているにもかかわらず、MDDテストの主な制限は2次時間の複雑さであり、大規模な分析の課題となっている。
手順の迅速化には様々なアプローチが提案されているが、MDD試験と同等の出力保証を準4次時間で達成できるかどうかは不明である。
このギャップを埋めるために、ランダムなフーリエ特徴を用いて近似MDDテストを再検討し、その計算統計的トレードオフについて検討する。
まず,無作為な特徴数が無限大に近づいた場合にのみ,近似MDDテストがパワーで一意に一致していることを明らかにする。
次に、テストの均一なパワーを検討し、ミニマックステストフレームワークの下でタイムパワートレードオフを研究する。
その結果, ランダムな特徴数を慎重に選択することにより, MMD試験と同一の最小分離率を準4次時間で達成できることが示唆された。
我々は、ソボレフ球の密度のような異なる分布仮定の下でこの点を実証する。
我々の理論的発見はシミュレーション研究によって裏付けられている。
関連論文リスト
- Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。
このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
論文 参考訳（メタデータ） (2024-06-12T06:41:47Z) - Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。
線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
論文 参考訳（メタデータ） (2023-11-01T04:41:16Z) - SMURF-THP: Score Matching-based UnceRtainty quantiFication for
Transformer Hawkes Process [76.98721879039559]
SMURF-THPは,変圧器ホークス過程を学習し,予測の不確かさを定量化するスコアベース手法である。
具体的には、SMURF-THPは、スコアマッチング目標に基づいて、イベントの到着時刻のスコア関数を学習する。
我々は,イベントタイプ予測と到着時刻の不確実性定量化の両方において,広範な実験を行う。
論文 参考訳（メタデータ） (2023-10-25T03:33:45Z) - Partial identification of kernel based two sample tests with mismeasured
data [5.076419064097733]
最大平均離散性(MMD)のような2サンプルテストは、機械学習アプリケーションにおける2つの分布の違いを検出するためにしばしば使用される。
我々は,1つの分布の非ランダムな$epsilon$%が互いに誤ってグループ化されるような,$epsilon$-contaminationに基づくMDDの推定について検討した。
そこで本研究では,これらの境界を推定する手法を提案し,サンプルサイズが大きくなるにつれてMDD上の最も鋭い限界に収束する推定値を示す。
論文 参考訳（メタデータ） (2023-08-07T13:21:58Z) - Boosting the Power of Kernel Two-Sample Tests [4.07125466598411]
最大平均誤差(MMD)に基づくカーネル2サンプルテストは、一般的な距離空間上の2つの分布の違いを検出する最も一般的な方法の1つである。
マハラノビス距離を用いて,複数のカーネル上でMDD推定値を組み合わせることで,カーネルテストのパワーを高める手法を提案する。
論文 参考訳（メタデータ） (2023-02-21T14:14:30Z) - Spectral Regularized Kernel Two-Sample Tests [7.915420897195129]
MMD (maximum mean discrepancy) two-sample test to be optimal to the terms of the separation boundary in the Hellinger distance。
スペクトル正則化に基づくMDD試験の修正を提案し,MMD試験よりも分離境界が小さく,最小限の試験が最適であることを証明した。
その結果,テストしきい値がエレガントに選択されるテストの置換変種が,サンプルの置換によって決定されることがわかった。
論文 参考訳（メタデータ） (2022-12-19T00:42:21Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。
サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。
格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
論文 参考訳（メタデータ） (2022-12-12T15:06:32Z) - A Permutation-free Kernel Two-Sample Test [36.50719125230106]
サンプル分割と学生化に基づく2次時間MDDテスト統計法を提案する。
大きなサンプルサイズの場合、我々の新しいクロスMMDはMDDよりも大幅にスピードアップし、わずかに電力を消費するだけである。
論文 参考訳（メタデータ） (2022-11-27T18:15:52Z) - Efficient Aggregated Kernel Tests using Incomplete $U$-statistics [22.251118308736327]
提案した3つのテストは、複数のカーネル帯域に集約され、さまざまなスケールでnullからの離脱を検出する。
提案した線形時間集約テストは,現在最先端の線形時間カーネルテストよりも高い出力が得られることを示す。
論文 参考訳（メタデータ） (2022-06-18T12:30:06Z) - Nonparametric Conditional Local Independence Testing [69.31200003384122]
条件付き局所独立は、連続的な時間プロセス間の独立関係である。
条件付き地域独立の非パラメトリックテストは行われていない。
二重機械学習に基づく非パラメトリックテストを提案する。
論文 参考訳（メタデータ） (2022-03-25T10:31:02Z) - Maximum Mean Discrepancy Test is Aware of Adversarial Attacks [122.51040127438324]
最大平均誤差(MMD)テストは、原則として2つのデータセット間の分布誤差を検出できる。
MMD検査は敵の攻撃に気づいていないことが示されている。
論文 参考訳（メタデータ） (2020-10-22T03:42:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。