論文の概要: On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and Fourier-based Algorithms

• arxiv url: http://arxiv.org/abs/2102.06277v1
• Date: Thu, 11 Feb 2021 21:28:55 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-15 13:00:40.429018
• Title: On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and Fourier-based Algorithms
• Title（参考訳）: $\mathcal{L}_2$-polynomial Regression とフーリエに基づくアルゴリズムを用いたAgnostic PAC学習について
• Authors: Mohsen Heidari and Wojciech Szpankowski
• Abstract要約: 構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。 0-1の損失を持つPAC学習はヒルベルト空間領域における最適化と同値であることを示す。
• 参考スコア（独自算出の注目度）: 10.66048003460524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a framework using Hilbert spaces as a proxy to analyze PAC learning problems with structural properties. We consider a joint Hilbert space incorporating the relation between the true label and the predictor under a joint distribution $D$. We demonstrate that agnostic PAC learning with 0-1 loss is equivalent to an optimization in the Hilbert space domain. With our model, we revisit the PAC learning problem using methods based on least-squares such as $\mathcal{L}_2$ polynomial regression and Linial's low-degree algorithm. We study learning with respect to several hypothesis classes such as half-spaces and polynomial-approximated classes (i.e., functions approximated by a fixed-degree polynomial). We prove that (under some distributional assumptions) such methods obtain generalization error up to $2opt$ with $opt$ being the optimal error of the class. Hence, we show the tightest bound on generalization error when $opt\leq 0.2$.
• Abstract（参考訳）: 構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。 共同分布 $D$ の下で、真のラベルと予測値の関係を組み込んだヒルベルト空間を考える。 0-1 の損失を持つ無依存pac学習はヒルベルト空間領域の最適化と同値である。 本モデルでは,$\mathcal{l}_2$多項式回帰やlinialの低次アルゴリズムなどの最小二乗法に基づく手法を用いてpac学習問題を再検討する。 半空間や多項式近似クラス(すなわち、定次多項式で近似された関数)などのいくつかの仮説クラスに関する学習について研究する。 そのような手法が(いくつかの分布仮定の下で)クラス最適誤差である$opt$と最大2opt$の一般化誤差を得ることを示す。 したがって、$opt\leq 0.2$ のとき、最も厳しい一般化誤差を示す。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions [39.97534972432276]
  本稿では,$[0,1]$-valued関数のクラスを学習するための新しい汎用アルゴリズムを提案する。 このアルゴリズムの絶対誤差の一般上界を証明した。 本研究は, 学習の複雑さに関する一般化された一般境界を得るために, 両方のパッキングバウンドをどう適用するかを示す。
  論文  参考訳（メタデータ） (2023-04-21T15:51:35Z)
• Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression [9.732863739456036]
  計算複雑性の低いフーリエ展開に基づく新しいPAC学習アルゴリズムを提案する。 我々は,PAC学習を0-1の損失と最小2乗推定問題とを結びつけることで,その結果を実証する。 MMSE誤差から0-1損失の優雅な上限を導出し、MMSEの符号がMMSEを含む任意の概念クラスに対するPAC学習者であることを示す。
  論文  参考訳（メタデータ） (2023-03-08T19:54:07Z)
• On the complexity of PAC learning in Hilbert spaces [0.0]
  ヒルベルト空間における凸多面体学習の観点から二項分類の問題を考察する。 本稿では,分布の少なくとも1-varepsilon$を正しく分類する多面体学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-03T16:16:11Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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