論文の概要: 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の非存在性である。
関連論文リスト
- 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) - Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。
Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
論文 参考訳(メタデータ) (2023-02-02T18:59:30Z) - Differentially-Private Bayes Consistency [70.92545332158217]
差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。
ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
論文 参考訳(メタデータ) (2022-12-08T11:57:30Z) - PAC Verification of Statistical Algorithms [0.10878040851637999]
本研究では,PAC学習目標を満たす仮説(機械学習モデル)を対話的証明を用いて検証する,PAC検証の設定を開発する。
我々は、$mathbbR$を超える間隔の和のPAC検証のためのプロトコルを提案し、そのタスクの提案したプロトコルを改善し、より低い境界の$d$への依存と一致させる。
最終結果は,クエリの制約を満たす統計的アルゴリズムの検証のためのプロトコルである。
論文 参考訳(メタデータ) (2022-11-28T23:57:27Z) - When are Local Queries Useful for Robust Learning? [25.832511407411637]
本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。
我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。
我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
論文 参考訳(メタデータ) (2022-10-12T11:04:22Z) - Boosting in the Presence of Massart Noise [49.72128048499074]
マスアートノイズを伴う(分布に依存しない)PACモデルにおいて、弱い学習者の精度を高める問題について検討する。
我々の主な成果は、Massartノイズの存在下で最初の計算効率の良いブースティングアルゴリズムである。
正の結果の簡単な応用として、高次元矩形の和に対して、第一に効率的なMassart学習者を与える。
論文 参考訳(メタデータ) (2021-06-14T22:21:25Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。