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

• arxiv url: http://arxiv.org/abs/2310.03641v1
• Date: Thu, 5 Oct 2023 16:13:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-06 15:32:11.062803
• Title: Distributional PAC-Learning from Nisan's Natural Proofs
• Title（参考訳）: ニサンの自然証明から学ぶ分布型PAC
• Authors: Ari Karchmer
• Abstract要約: 本稿では,Lambdaの自然証明が,ValiantのPACモデルにおけるLambdaの学習アルゴリズムを示唆するかどうかを検討する。 我々の主な結果は、通信複雑性の議論から生じる特定の自然証明は、ヴァリアントのモデルの新たな分布変種におけるPAC学習を暗示しているということである。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: (Abridged) Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds for \Lambda imply efficient algorithms for learning \Lambda-circuits, but only over the uniform distribution, with 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 in Valiant's PAC model, which use only random examples and learn over arbitrary example distributions. We give results of both positive and negative flavor. On the negative side, we observe that if, for every circuit class \Lambda, the implication from natural proofs for \Lambda to learning \Lambda-circuits in Valiant's PAC model holds, then there is a polynomial time solution to O(n^{1.5})-uSVP (unique Shortest Vector Problem), and polynomial time quantum solutions to O(n^{1.5})-SVP (Shortest Vector Problem) and O(n^{1.5})-SIVP (Shortest Independent Vector Problem). This indicates that whether natural proofs for \Lambda imply efficient learning algorithms for \Lambda in Valiant's PAC model may depend on \Lambda. On the positive side, our main result is that specific natural proofs arising from a type of communication complexity argument (e.g., Nisan (1993), for depth-2 majority circuits) imply PAC-learning algorithms in a new distributional variant of Valiant's 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 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 の回路下界の自然な証明は \Lambda-circuits を学ぶための効率的なアルゴリズムを暗示するが、一様分布上のみであり、メンバーシップクエリを持ち、 \AC^0[p] \subseteq \Lambda を提供した。 この含意が \lambda \not\supseteq \ac^0[p] に一般化できるかどうかと、ランダムな例のみを使用して任意の例分布を学習するvaliantのpacモデルにおける学習アルゴリズムを考える。 正味と負味の両方の結果が得られます。 負の側では、すべての回路クラス \lambda に対して、\lambda の自然証明から valiant の pac モデルにおける学習 \lambda-circuits への含意が成立するならば、o(n^{1.5})-usvp (unique shortest vector problem) の多項式時間解と o(n^{1.5})-svp (shortest vector problem) と o(n^{1.5})-sivp (shortest independent vector problem) の多項式時間量子解が存在する。 このことは、バリアントのpacモデルにおける \lambda の自然証明が効率的な学習アルゴリズムを意味するかどうかが \lambda に依存する可能性があることを示している。 正の面では、通信複雑性の議論(例えば、深度2多数回路のNisan (1993) など)から生じる特定の自然証明は、新しい分散変種ValiantモデルのPAC学習アルゴリズムを示唆している。 分布pacモデルは,blum et al (1993) の平均ケース予測モデルやnanashima (2021) のヒューリスティックpacモデルよりも強力であり,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)

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

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