論文の概要: Distributional PAC-Learning from Nisan's Natural Proofs

• arxiv url: http://arxiv.org/abs/2310.03641v2
• Date: Thu, 30 Nov 2023 21:01:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-04 17:59:32.920346
• Title: Distributional PAC-Learning from Nisan's Natural Proofs
• Title（参考訳）: ニサンの自然証明から学ぶ分布型PAC
• Authors: Ari Karchmer
• Abstract要約: Lambda-circuitsを学習するために、$Lambdaの回路境界の自然な証明は効率的なアルゴリズムを暗示する。 我々は、この意味を$Lambda notsupseteq AC0[p]$、ランダムな例のみを用いて任意の例分布を学習する学習アルゴリズムに一般化できるかどうか検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds for $\Lambda$ imply efficient algorithms for learning $\Lambda$-circuits, but only over \textit{the uniform distribution}, with \textit{membership queries}, and provided $\AC^0[p] \subseteq \Lambda$. We consider whether this implication can be generalized to $\Lambda \not\supseteq \AC^0[p]$, and to learning algorithms which use only random examples and learn over arbitrary example distributions (Valiant's PAC-learning model). We first observe that, if, for any circuit class $\Lambda$, there is an implication from natural proofs for $\Lambda$ to PAC-learning for $\Lambda$, then standard assumptions from lattice-based cryptography do not hold. In particular, we observe that depth-2 majority circuits are a (conditional) counter example to the implication, since Nisan (1993) gave a natural proof, but Klivans and Sherstov (2009) showed hardness of PAC-learning under lattice-based assumptions. We thus ask: what learning algorithms can we reasonably expect to follow from Nisan's natural proofs? Our main result is that all natural proofs arising from a type of communication complexity argument, including Nisan's, imply PAC-learning algorithms in a new \textit{distributional} variant (i.e., an ``average-case'' relaxation) of Valiant's PAC model. Our distributional PAC model is stronger than the average-case prediction model of Blum et al. (1993) and the heuristic PAC model of Nanashima (2021), and has several important properties which make it of independent interest, such as being \textit{boosting-friendly}. The main applications of our result are new distributional PAC-learning algorithms for depth-2 majority circuits, polytopes and DNFs over natural target distributions, as well as the nonexistence of encoded-input weak PRFs that can be evaluated by depth-2 majority circuits.
• Abstract（参考訳）: Carmosino et al. (2016) は、$\Lambda$-circuits の回路下界の自然な証明は、$\Lambda$-circuits を学ぶための暗黙のアルゴリズムであるが、 \textit{the uniform distribution} にのみ適用され、$\AC^0[p] \subseteq \Lambda$ を提供することを示した。 この意味を$\Lambda \not\supseteq \AC^0[p]$と、ランダムな例のみを用いて任意の例分布を学習する学習アルゴリズム(ValiantのPAC学習モデル)に一般化できるかどうかを検討する。 まず、任意の回路クラス $\Lambda$ に対して、$\Lambda$ の自然証明から$\Lambda$ の PAC-learning への帰結がある場合、格子ベースの暗号の標準的な仮定は成立しない。 特に,Nisan (1993) は自然証明を与えたが,Klivans and Sherstov (2009) は格子に基づく仮定の下でのPAC学習の困難さを示した。 私たちは、 nisan の自然な証明から、合理的に従える学習アルゴリズムは何でしょうか? 我々の主な成果は、ValiantのPACモデルにおける新しい‘textit{distributional} 変種(つまり 'average-case''' 緩和)における、Nisan の PAC 学習アルゴリズムを含む、通信複雑性の議論から生じる全ての自然な証明である。 分布pacモデルは,blum et al. (1993) の平均ケース予測モデルやnanashima (2021) のヒューリスティックpacモデルよりも強く,textit{boosting-friendly} のような独立した特性を持つ。 本研究の主な用途は,深度2の多数回路,ポリトープ,DNFの自然分布に対する新しい分散PAC学習アルゴリズム,および深度2の多数回路で評価できるエンコードインプット弱PRFの非存在性である。

関連論文リスト

• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
  論文  参考訳（メタデータ） (2024-09-17T23:09:25Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• 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)
• Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise [10.550885570889527]
  我々は、$mathbbRn$で$K$sparse degree-$d$ PTFsのPAC学習を研究する。 私たちの主な貢献は、時間$(nd/epsilon)O(d)$で実行される新しいアルゴリズムです。 PACは$eta leq O(epsilond)であっても$O(fracK4depsilon2d cdot log5d n)$でエラー率$epsilon$までクラスを学習する
  論文  参考訳（メタデータ） (2023-06-01T13:49:22Z)
• 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)
• Differentially-Private Bayes Consistency [70.92545332158217]
  差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。 ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
  論文  参考訳（メタデータ） (2022-12-08T11:57:30Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。 我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。 我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
  論文  参考訳（メタデータ） (2022-10-12T11:04:22Z)
• 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)

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

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