論文の概要: Learning and Testing Junta Distributions with Subcube Conditioning

• arxiv url: http://arxiv.org/abs/2004.12496v1
• Date: Sun, 26 Apr 2020 22:52:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-09 14:03:27.694852
• Title: Learning and Testing Junta Distributions with Subcube Conditioning
• Title（参考訳）: サブキューブ条件付きユンタ分布の学習とテスト
• Authors: Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
• Abstract要約: 本研究では,一様分布に関して,1,1n$のユンタ分布の学習と試験の問題点について検討する。 主な寄与は、サブキューブ条件付き$k$-junta分布における関連する座標を見つけるアルゴリズムである。
• 参考スコア（独自算出の注目度）: 11.464622619555222
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problems of learning and testing junta distributions on $\{-1,1\}^n$ with respect to the uniform distribution, where a distribution $p$ is a $k$-junta if its probability mass function $p(x)$ depends on a subset of at most $k$ variables. The main contribution is an algorithm for finding relevant coordinates in a $k$-junta distribution with subcube conditioning [BC18, CCKLW20]. We give two applications: 1. An algorithm for learning $k$-junta distributions with $\tilde{O}(k/\epsilon^2) \log n + O(2^k/\epsilon^2)$ subcube conditioning queries, and 2. An algorithm for testing $k$-junta distributions with $\tilde{O}((k + \sqrt{n})/\epsilon^2)$ subcube conditioning queries. All our algorithms are optimal up to poly-logarithmic factors. Our results show that subcube conditioning, as a natural model for accessing high-dimensional distributions, enables significant savings in learning and testing junta distributions compared to the standard sampling model. This addresses an open question posed by Aliakbarpour, Blais, and Rubinfeld [ABR17].
• Abstract（参考訳）: 1,1\}^n$ の分布を一様分布に関して学習・テストする問題について検討する。ここでは、分布 $p$ が $k$-junta であるとは、その確率質量関数 $p(x)$ が最大 $k$ 変数のサブセットに依存する場合である。 主な寄与は、サブキューブ条件付き$k$-junta分布における関連する座標を見つけるアルゴリズムである [BC18, CCKLW20]。 1:$\tilde{o}(k/\epsilon^2) \log n + o(2^k/\epsilon^2)$ subcube条件付きクエリで$k$-junta分布を学習するアルゴリズム、2:$\tilde{o}((k + \sqrt{n})/\epsilon^2)$ subcube条件付きクエリで$k$-junta分布をテストするアルゴリズム。 全てのアルゴリズムは多対数因子に最適である。 その結果,サブキューブコンディショニングは,高次元分布の自然モデルとして,標準サンプリングモデルと比較して,学習やテストにおいて有意な節約が期待できることがわかった。 これはAliakbarpour, Blais, Rubinfeld[ABR17]によって提起されたオープンな問題に対処する。

関連論文リスト

• Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
  非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。 本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
  論文  参考訳（メタデータ） (2024-10-28T18:19:13Z)
• Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
  Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。 それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
  論文  参考訳（メタデータ） (2024-04-02T23:34:39Z)
• 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)
• Near-Optimal Degree Testing for Bayes Nets [6.814860712547177]
  問題の複雑さのサンプルは$tildeTheta (2n/2/varepsilon2)$である。 我々のアルゴリズムは、これまでサンプル最適化テスターの獲得に用いられてきたテスト・バイ・ラーニング・フレームワークに依存している。
  論文  参考訳（メタデータ） (2023-04-13T03:48:31Z)
• Lifting uniform learners via distributional decomposition [17.775217381568478]
  均一分布の下で動作する任意のPAC学習アルゴリズムが、ブラックボックス方式で、任意の未知分布の$mathcalD$の下で動作させるアルゴリズムに変換可能であることを示す。 重要な技術的要素は、前述の$mathcalD$にアクセスすると、$mathcalD$の最適な決定木分解を生成するアルゴリズムである。
  論文  参考訳（メタデータ） (2023-03-27T23:55:25Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
  仮説選択問題に対する最適2ドルの近似学習戦略を導出する。 これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2021-08-17T21:11:20Z)
• 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)
• 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)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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