論文の概要: On the Power of Interactive Proofs for Learning
- arxiv url: http://arxiv.org/abs/2404.08158v1
- Date: Thu, 11 Apr 2024 23:16:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-15 16:15:01.687083
- Title: On the Power of Interactive Proofs for Learning
- Title（参考訳）: 学習のための対話型証明の力について
- Authors: Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar,
- Abstract要約: 我々は、PAC学習を検証するための2倍効率の証明システムの研究を継続する。
任意の関数$f colon 0,1n から 0,1$ までの最大フーリエ文字を任意に小さな誤りまで学習するための対話的プロトコルを構築する。
二重効率証明系を主張しないならば、モデルは自明になる。
- 参考スコア（独自算出の注目度）: 3.785008536475385
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We continue the study of doubly-efficient proof systems for verifying agnostic PAC learning, for which we obtain the following results. - We construct an interactive protocol for learning the $t$ largest Fourier characters of a given function $f \colon \{0,1\}^n \to \{0,1\}$ up to an arbitrarily small error, wherein the verifier uses $\mathsf{poly}(t)$ random examples. This improves upon the Interactive Goldreich-Levin protocol of Goldwasser, Rothblum, Shafer, and Yehudayoff (ITCS 2021) whose sample complexity is $\mathsf{poly}(t,n)$. - For agnostically learning the class $\mathsf{AC}^0[2]$ under the uniform distribution, we build on the work of Carmosino, Impagliazzo, Kabanets, and Kolokolova (APPROX/RANDOM 2017) and design an interactive protocol, where given a function $f \colon \{0,1\}^n \to \{0,1\}$, the verifier learns the closest hypothesis up to $\mathsf{polylog}(n)$ multiplicative factor, using quasi-polynomially many random examples. In contrast, this class has been notoriously resistant even for constructing realisable learners (without a prover) using random examples. - For agnostically learning $k$-juntas under the uniform distribution, we obtain an interactive protocol, where the verifier uses $O(2^k)$ random examples to a given function $f \colon \{0,1\}^n \to \{0,1\}$. Crucially, the sample complexity of the verifier is independent of $n$. We also show that if we do not insist on doubly-efficient proof systems, then the model becomes trivial. Specifically, we show a protocol for an arbitrary class $\mathcal{C}$ of Boolean functions in the distribution-free setting, where the verifier uses $O(1)$ labeled examples to learn $f$.
- Abstract（参考訳）: 本研究は,2倍効率のPAC学習検証システムの研究を継続し,以下の結果を得た。
任意の関数$f \colon \{0,1\}^n \to \{0,1\}$を任意の小さなエラーまで学習するための対話的プロトコルを構築し、検証者は$\mathsf{poly}(t)$ランダムな例を使用する。
これは、Goldwasser, Rothblum, Shafer, and Yehudayoff (ITCS 2021) の対話型 Goldreich-Levin プロトコルにより改善され、サンプル複雑性は$\mathsf{poly}(t,n)$である。
- 均一分布の下でクラス $\mathsf{AC}^0[2]$ を不可知的に学習するために、Carmosino, Impagliazzo, Kabanets, and Kolokolova (APPROX/RANDOM 2017) の作業に基づいて対話的プロトコルを設計し、関数 $f \colon \{0,1\}^n \to \{0,1\}$ が与えられたとき、検証者は、準ポノミカルに多くのランダムな例を用いて、最も近い仮説を$\mathsf{polylog}(n)$乗法係数で学習する。
対照的に、このクラスは、ランダムな例を使って現実的な学習者(証明者なしで)を構築することさえも、悪名高い。
-一様分布の下で$k$-juntasを不可知的に学習するために、我々は対話的プロトコルを得る。そこで検証者は与えられた関数$f \colon \{0,1\}^n \to \{0,1\}$に対して$O(2^k)$ランダム例を使用する。
重要なことに、検証器のサンプルの複雑さは$n$とは独立である。
また、二重効率証明系を主張しないならば、モデルは自明になることを示す。
具体的には、任意のクラス $\mathcal{C}$ の Boolean 関数のプロトコルを配布不要の設定で示し、検証者は$O(1)$ ラベル付き例を使って$f$ を学ぶ。
関連論文リスト
- Upper Bounds for Learning in Reproducing Kernel Hilbert Spaces for Orbits of an Iterated Function System [1.1510009152620668]
学習理論における重要な問題は、ある入力$x$と対応する出力$y$の関係を近似した関数$f$を計算することである。
この近似はサンプル点 $(x_t,y_t)_t=1m$ に基づいている。
論文 参考訳（メタデータ） (2024-10-10T20:34:22Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。
我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
論文 参考訳（メタデータ） (2022-05-31T17:59:09Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Reward-Free Model-Based Reinforcement Learning with Linear Function
Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。
計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。
任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文 参考訳（メタデータ） (2021-10-12T23:03:58Z) - On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。
簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
論文 参考訳（メタデータ） (2021-06-15T11:21:06Z) - Downsampling for Testing and Learning in Product Distributions [24.48103093661132]
未知確率分布が $mathbbRd$ 上の積分布であるような分布自由なプロパティテストと学習問題について検討する。
ハーフスペースの交叉、しきい値関数、凸集合、および$k$交互関数などの多くの重要な関数のクラスでは、既知のアルゴリズムは、分布のサポートサイズに依存する複雑さを持つ。
本稿では,これらの問題を解消する一般手法として,ダウンログ(downlog)を提案する。
論文 参考訳（メタデータ） (2020-07-15T02:46:44Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-11T00:55:35Z) - 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) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。