論文の概要: PAC Verification of Statistical Algorithms
- arxiv url: http://arxiv.org/abs/2211.17096v1
- Date: Mon, 28 Nov 2022 23:57:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-01 16:05:26.907917
- Title: PAC Verification of Statistical Algorithms
- Title（参考訳）: PACによる統計的アルゴリズムの検証
- Authors: Saachi Mutreja, Jonathan Shafer
- Abstract要約: 我々は、$Omega(sqrtd)$ i.i.d.のPAC検証の低い境界を証明する。
本稿では,その課題に対して提案したプロトコルを改善するために,$mathbbR$以上の間隔の和集合をPACで検証するプロトコルを提案する。
最終結果は,クエリの制約を満たす統計的クエリアルゴリズムの検証のためのプロトコルである。
- 参考スコア（独自算出の注目度）: 0.30458514384586394
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Goldwasser et al.\ (2021) recently proposed the setting of PAC verification,
where a hypothesis (machine learning model) that purportedly satisfies the
agnostic PAC learning objective is verified using an interactive proof. In this
paper we develop this notion further in a number of ways. First, we prove a
lower bound for PAC verification of $\Omega(\sqrt{d})$ i.i.d.\ samples for
hypothesis classes of VC dimension $d$. Second, we present a protocol for PAC
verification of unions of intervals over $\mathbb{R}$ that improves upon their
proposed protocol for that task, and matches our lower bound. Third, we
introduce a natural generalization of their definition to verification of
general statistical algorithms, which is applicable to a wider variety of
practical algorithms beyond agnostic PAC learning. Showcasing our proposed
definition, our final result is a protocol for the verification of statistical
query algorithms that satisfy a combinatorial constraint on their queries.
- Abstract（参考訳）: goldwasser et alの略。
2021)は、最近PAC検証の設定を提案し、そこでは、非依存的なPAC学習目標を満たす仮説(機械学習モデル)を対話的証明を用いて検証した。
本稿では,この概念をさらに様々な方法で展開する。
まず、VC 次元 $d$ の仮説クラスに対する $\Omega(\sqrt{d})$ i.i.d.\ サンプルの PAC 検証に対する下界を証明する。
第二に、このタスクに対する提案したプロトコルを改善し、下位境界にマッチする$\mathbb{R}$を超える間隔の和のPAC検証のためのプロトコルを提案する。
第3に,その定義の自然な一般化を一般統計アルゴリズムの検証に導入する。
提案した定義を裏付ける上で,我々の最終結果は,クエリの組合せ制約を満たす統計的クエリアルゴリズムの検証のためのプロトコルである。
関連論文リスト
- Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。
提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
論文 参考訳（メタデータ） (2024-10-02T08:46:34Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets [25.250314934981233]
我々はまず,データ依存仮説セットを出力するトレーニングアルゴリズムを前提として,厳密な方法でPAC-Bayesianフレームワークを適用した。
このアプローチにより、多くのコンテキストに適用可能な、データ依存のバウンダリを証明できます。
論文 参考訳（メタデータ） (2024-04-26T14:28:18Z) - Private Truly-Everlasting Robust-Prediction [22.662255469977598]
プライベート・エバースト・予測(Private Everlasting Prediction, PEP)は、学習者が仮説を公開しない、微分プライベート学習のモデルである。
PEPは、初期トレーニングセットと、エンドツーエンドの分類クエリストリームの両方に対して、プライバシを提供する。
我々は, PEPの定義に対する2つの概念的修正と, 従来の作業よりも大幅に改善された新しい構成を提案する。
論文 参考訳（メタデータ） (2024-01-09T02:00:55Z) - Distributional PAC-Learning from Nisan's Natural Proofs [0.0]
Lambda-circuitsを学習するために、$Lambdaの回路境界の自然な証明は効率的なアルゴリズムを暗示する。
我々は、この意味を$Lambda notsupseteq AC0[p]$、ランダムな例のみを用いて任意の例分布を学習する学習アルゴリズムに一般化できるかどうか検討する。
論文 参考訳（メタデータ） (2023-10-05T16:13:29Z) - SHAP@k:Efficient and Probably Approximately Correct (PAC) Identification
of Top-k Features [16.99004256148679]
本稿では,トップk識別問題(TkIP)を紹介し,最も高いSHAP値を持つk特徴を特定することを目的とする。
我々の研究の目的は、TkIP解決の文脈において、既存の手法のサンプル効率を改善することである。
論文 参考訳（メタデータ） (2023-07-10T18:42:45Z) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳（メタデータ） (2022-08-17T18:49:53Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - A Limitation of the PAC-Bayes Framework [32.24251308425503]
我々はPAC-Bayesフレームワークの制限を提示する。
PAC-Bayes解析には適さない簡単な学習課題を実演する。
論文 参考訳（メタデータ） (2020-06-24T06:36:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。