Fugu-MT 論文翻訳(概要): Near-Optimal Degree Testing for Bayes Nets

論文の概要: Near-Optimal Degree Testing for Bayes Nets

arxiv url: http://arxiv.org/abs/2304.06733v1
Date: Thu, 13 Apr 2023 03:48:31 GMT
ステータス: 処理完了
システム内更新日: 2023-04-17 15:49:47.989927
Title: Near-Optimal Degree Testing for Bayes Nets
Title（参考訳）: ベイズネットの至近度試験
Authors: Vipul Arora, Arnab Bhattacharyya, Cl\'ement L. Canonne, Joy Qiping Yang
Abstract要約: 問題の複雑さのサンプルは$tildeTheta (2n/2/varepsilon2)$である。我々のアルゴリズムは、これまでサンプル最適化テスターの獲得に用いられてきたテスト・バイ・ラーニング・フレームワークに依存している。
参考スコア（独自算出の注目度）: 6.814860712547177
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper considers the problem of testing the maximum in-degree of the Bayes net underlying an unknown probability distribution $P$ over $\{0,1\}^n$, given sample access to $P$. We show that the sample complexity of the problem is $\tilde{\Theta}(2^{n/2}/\varepsilon^2)$. Our algorithm relies on a testing-by-learning framework, previously used to obtain sample-optimal testers; in order to apply this framework, we develop new algorithms for ``near-proper'' learning of Bayes nets, and high-probability learning under $\chi^2$ divergence, which are of independent interest.
Abstract（参考訳）: 本稿では、サンプルアクセスが $p$ であることから、未知の確率分布が $p$ over $\{0,1\}^n$ となるベイズネットの最大内度をテストする問題を考察する。問題のサンプル複雑性は$\tilde{\Theta}(2^{n/2}/\varepsilon^2)$であることを示す。このフレームワークを適用するために,ベイズネットの'near-proper'学習のための新しいアルゴリズムを開発し,独立した関心を持つ$\chi^2$ divergence の下で高確率学習を行う。

関連論文リスト

Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文参考訳（メタデータ） (2024-06-18T08:54:04Z)
Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文参考訳（メタデータ） (2023-11-25T23:57:45Z)
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)
A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文参考訳（メタデータ） (2023-02-26T01:15:32Z)
Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文参考訳（メタデータ） (2021-08-17T21:11:20Z)
Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-14T16:09:17Z)
Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文参考訳（メタデータ） (2020-06-11T14:25:02Z)
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)
Learning and Testing Junta Distributions with Subcube Conditioning [11.464622619555222]
本研究では,一様分布に関して,1,1n$のユンタ分布の学習と試験の問題点について検討する。主な寄与は、サブキューブ条件付き$k$-junta分布における関連する座標を見つけるアルゴリズムである。
論文参考訳（メタデータ） (2020-04-26T22:52:53Z)
Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文参考訳（メタデータ） (2020-02-21T18:30:48Z)

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