論文の概要: Learning $\mathsf{AC}^0$ Under Graphical Models

• arxiv url: http://arxiv.org/abs/2604.06109v1
• Date: Tue, 07 Apr 2026 17:20:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-08 17:42:09.962212
• Title: Learning $\mathsf{AC}^0$ Under Graphical Models
• Title（参考訳）: グラフモデルによる$\mathsf{AC}^0$の学習
• Authors: Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, Arsen Vasilyan,
• Abstract要約: 我々は,新しいサンプリングアルゴリズムによって,一様条件下での低次近似のステートメントをグラフィカルモデルに転送できることを示す。 私たちのアプローチは、モノトーン関数やハーフスペースのような、他のよく研究された関数クラスに拡張するのに十分な一般性を持っている。
• 参考スコア（独自算出の注目度）: 21.66293630099673
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the uniform distribution. Their work has had a deep and lasting legacy in computational learning theory, in particular introducing the $\textit{low-degree algorithm}$. However, an important critique of many results and techniques in the area is the reliance on product structure, which is unlikely to hold in realistic settings. Obtaining similar learning guarantees for more natural correlated distributions has been a longstanding challenge in the field. In particular, we give quasipolynomial-time algorithms for learning $\mathsf{AC}^0$ substantially beyond the product setting, when the inputs come from any graphical model with polynomial growth that exhibits strong spatial mixing. The main technical challenge is in giving a workaround to Fourier analysis, which we do by showing how new sampling algorithms allow us to transfer statements about low-degree polynomial approximation under the uniform setting to graphical models. Our approach is general enough to extend to other well-studied function classes, like monotone functions and halfspaces.
• Abstract（参考訳）: 目覚ましい結果として、Linial, Mansour and Nisan (J. ACM 1993) は、一様分布の下でラベル付き標本を与えられた定数深度回路を学習するための準ポリノミカル時間アルゴリズムを与えた。 彼らの研究は、特に$\textit{low-degree algorithm}$を導入して、計算学習理論において深い、そして永続的な遺産を持っていた。 しかし、この分野における多くの成果と技術に対する重要な批判は、製品構造への依存であり、現実的な環境では成り立たない。 より自然な相関分布に対する同様の学習保証を得ることは、この分野における長年の課題である。 特に、入力が強い空間混合を示す多項式成長を持つ任意のグラフィカルモデルから来るとき、$\mathsf{AC}^0$をかなり越えて学習するための準ポリノミカル時間アルゴリズムを与える。 主な技術的課題はフーリエ解析の回避であり、新しいサンプリングアルゴリズムによって、均一な設定下での低次多項式近似に関するステートメントをグラフィカルモデルに転送できることを示す。 私たちのアプローチは、モノトーン関数やハーフスペースなど、他のよく研究された関数クラスにまで拡張できるほど一般的です。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Learning with Exact Invariances in Polynomial Time [43.81087760363805]
  本稿では,カーネル回帰を用いて,正確な不変性(あるいは対称性)を学習するための統計的・計算的トレードオフについて検討する。 提案手法は,元のカーネル回帰問題と同じ過大な集団リスクを実現する。
  論文  参考訳（メタデータ） (2025-02-27T04:49:52Z)
• Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
  低次しきい値関数 (PTF) の, 対向汚職の一定割合の存在下での効率的な学習性について検討した。 提案アルゴリズムは,線形しきい値関数の学習に使用されていた局所化手法に着想を得た反復的手法を用いている。
  論文  参考訳（メタデータ） (2024-03-31T02:03:35Z)
• 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)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)

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

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