論文の概要: Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression

• arxiv url: http://arxiv.org/abs/2303.04859v1
• Date: Wed, 8 Mar 2023 19:54:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-10 17:07:47.185297
• Title: Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression
• Title（参考訳）: L2-ポリリノミアル回帰を用いたk-juntasのAgnostic PAC学習
• Authors: Mohsen Heidari, and Wojciech Szpankowski
• Abstract要約: 計算複雑性の低いフーリエ展開に基づく新しいPAC学習アルゴリズムを提案する。 我々は,PAC学習を0-1の損失と最小2乗推定問題とを結びつけることで,その結果を実証する。 MMSE誤差から0-1損失の優雅な上限を導出し、MMSEの符号がMMSEを含む任意の概念クラスに対するPAC学習者であることを示す。
• 参考スコア（独自算出の注目度）: 9.732863739456036
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many conventional learning algorithms rely on loss functions other than the natural 0-1 loss for computational efficiency and theoretical tractability. Among them are approaches based on absolute loss (L1 regression) and square loss (L2 regression). The first is proved to be an \textit{agnostic} PAC learner for various important concept classes such as \textit{juntas}, and \textit{half-spaces}. On the other hand, the second is preferable because of its computational efficiency, which is linear in the sample size. However, PAC learnability is still unknown as guarantees have been proved only under distributional restrictions. The question of whether L2 regression is an agnostic PAC learner for 0-1 loss has been open since 1993 and yet has to be answered. This paper resolves this problem for the junta class on the Boolean cube -- proving agnostic PAC learning of k-juntas using L2 polynomial regression. Moreover, we present a new PAC learning algorithm based on the Boolean Fourier expansion with lower computational complexity. Fourier-based algorithms, such as Linial et al. (1993), have been used under distributional restrictions, such as uniform distribution. We show that with an appropriate change, one can apply those algorithms in agnostic settings without any distributional assumption. We prove our results by connecting the PAC learning with 0-1 loss to the minimum mean square estimation (MMSE) problem. We derive an elegant upper bound on the 0-1 loss in terms of the MMSE error and show that the sign of the MMSE is a PAC learner for any concept class containing it.
• Abstract（参考訳）: 多くの従来の学習アルゴリズムは、計算効率と理論の扱いやすさのために自然0-1損失以外の損失関数に依存する。 その中でも絶対損失(L1回帰)と正方損失(L2回帰)に基づくアプローチがある。 1つ目は、 \textit{juntas} や \textit{half-spaces} のような重要な概念クラスに対する \textit{agnostic} PAC 学習者であることが証明されている。 一方,第2の計算効率は試料サイズが線形であることから好適である。 しかし、PACの学習性はまだ不明であり、保証は分布制限下でのみ証明されている。 L2レグレッションが0-1の損失に対して無知のPAC学習者であるかどうかという問題は1993年から始まっている。 本稿では, ブール立方体上のユンタクラスに対するこの問題を解決し, L2多項式回帰を用いたk-ユンタの非依存なPAC学習を実現する。 さらに,計算複雑性の低いブールフーリエ拡張に基づく新しいPAC学習アルゴリズムを提案する。 Linial et al. (1993)のようなフーリエベースのアルゴリズムは、一様分布のような分布制限の下で使われてきた。 適切な変更によって、分散的な仮定なしに、これらのアルゴリズムを無依存な設定で適用できることを示す。 PAC学習と0-1の損失を最小平均二乗推定(MMSE)問題に結びつけて結果を証明した。 MMSE誤差から0-1損失の優雅な上限を導出し、MMSEの符号がMMSEを含む任意の概念クラスに対するPAC学習者であることを示す。

関連論文リスト

• Is Transductive Learning Equivalent to PAC Learning? [0.9012198585960443]
  PACモデルとトランスダクティブモデルは、本質的には非依存のバイナリ分類に等価であることを示す。 我々は,2番目の結果が2進分類を超えて拡張可能かどうかという興味深い疑問を残して,トランスダクティブモデルとPACモデルがより広範に等価であることを示す。
  論文  参考訳（メタデータ） (2024-05-08T16:26:49Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Distributional PAC-Learning from Nisan's Natural Proofs [0.0]
  Lambda-circuitsを学習するために、$Lambdaの回路境界の自然な証明は効率的なアルゴリズムを暗示する。 我々は、この意味を$Lambda notsupseteq AC0[p]$、ランダムな例のみを用いて任意の例分布を学習する学習アルゴリズムに一般化できるかどうか検討する。
  論文  参考訳（メタデータ） (2023-10-05T16:13:29Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and Fourier-based Algorithms [10.66048003460524]
  構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。 0-1の損失を持つPAC学習はヒルベルト空間領域における最適化と同値であることを示す。
  論文  参考訳（メタデータ） (2021-02-11T21:28:55Z)
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [47.81107898315438]
  そこで我々は,二元性LPを用いて,多種多様な問題に対するサンプルのハードファミリーを見つける手法を開発した。 L1$-regression は本質的には最適であり、概念クラスを学習する際の計算困難さは、クラスから任意の関数を近似するのに要する次数と密接に関連していることが示される。
  論文  参考訳（メタデータ） (2021-02-08T18:06:32Z)
• Statistical-Query Lower Bounds via Functional Gradients [19.5924910463796]
  我々は、寛容$n- (1/epsilon)b$の統計クエリアルゴリズムは、一定の$bに対して少なくとも$2nc epsilon$クエリを使用する必要があることを示す。 実数値学習では珍しいSQ学習アルゴリズムが一般的である(相関学習とは対照的に)。
  論文  参考訳（メタデータ） (2020-06-29T05:15:32Z)
• 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)
• Supervised Learning: No Loss No Cry [51.07683542418145]
  教師付き学習は最小化するために損失関数の仕様を必要とする。 本稿では,Kakade et al. (2011)のSLIsotronアルゴリズムを新しいレンズで再検討する。 損失を学習するための原則的な手順をいかに提供するかを示す。
  論文  参考訳（メタデータ） (2020-02-10T05:30:52Z)

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

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