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

• arxiv url: http://arxiv.org/abs/2607.08303v1
• Date: Thu, 09 Jul 2026 09:46:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-10 14:45:27.494922
• Title: Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models
• Title（参考訳）: 局所サンプル型グラフィカルモデルによる$\mathsf{AC}^0$の学習
• Authors: Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang,
• Abstract要約: 我々は,強い空間混合と成長を持つグラフィカルモデルの下で,$mathsfAC0$に対して準ポリノミカル時間学習器を提供する。 このフレームワークは、任意の有界グラフ上のハードコアモデルとイジングモデルを含む2スピンシステムの学習者を得る。
• 参考スコア（独自算出の注目度）: 1.4816117998909835
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial, Mansour, and Nisan (J. ACM 1993) presented a quasipolynomial-time learner for $\mathsf{AC}^0$ under the uniform distribution. However, obtaining comparable learning guarantees for broader classes of correlated distributions has remained a longstanding challenge. Recently, Chandrasekaran, Gaitonde, Moitra, and Vasilyan (arXiv 2026) extended these guarantees to Gibbs distributions on bounded-degree graphical models with both strong spatial mixing and polynomial growth. In this paper, we give a quasipolynomial-time learner for $\mathsf{AC}^0$ under graphical models that admit efficient local samplers, circumventing the polynomial-growth requirement in prior work. The key ingredient is a new low-degree approximation for Gibbs distributions, established by simulating and suitably truncating the classical Glauber dynamics. As applications, this framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs, in regimes approaching their respective sampling thresholds.
• Abstract（参考訳）: 一定深度回路の学習問題は、計算学習理論に深い意味を持つ。 その結果、Linial, Mansour, Nisan (J. ACM 1993) という低次アルゴリズムを導入し、準ポリリノミカル時間学習器を均一分布の$\mathsf{AC}^0$に対して提示した。 しかし、より広範な相関分布のクラスに対して同等の学習保証を得ることは、長年にわたる課題である。 近年、Chandrasekaran, Gaitonde, Moitra, Vasilyan (arXiv 2026) はこれらの保証を強い空間混合と多項式成長を持つ有界グラフモデル上のギブズ分布に拡張した。 本稿では, 局所的な局所サンプリングを効率よく行うグラフィカルモデルを用いて, 多項式成長要求を回避できる準多項式時間学習器を提案する。 鍵となる要素はギブス分布に対する新しい低次近似であり、古典的なグラウバー力学をシミュレートし、適切に切り離すことによって確立される。 応用として、このフレームワークは、任意の有界グラフ上のハードコアモデルとイジングモデルを含む2スピンシステムの学習者を、それぞれのサンプリングしきい値に近づく状況下で得る。

関連論文リスト

• Learning $\mathsf{AC}^0$ Under Graphical Models [21.66293630099673]
  我々は,新しいサンプリングアルゴリズムによって,一様条件下での低次近似のステートメントをグラフィカルモデルに転送できることを示す。 私たちのアプローチは、モノトーン関数やハーフスペースのような、他のよく研究された関数クラスに拡張するのに十分な一般性を持っている。
  論文  参考訳（メタデータ） (2026-04-07T17:20:35Z)
• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Structure Learning in Gaussian Graphical Models from Glauber Dynamics [6.982878344925993]
  グラウバー力学に基づいてデータをサンプリングする場合, ガウスモデル選択のための最初のアルゴリズムを提案する。 本稿では,提案アルゴリズムの構造学習性能の計算的および統計的複雑さを保証する。
  論文  参考訳（メタデータ） (2024-12-24T18:49:13Z)
• Differentiable DG with Neural Operator Source Term Correction [0.0]
  圧縮可能なNavier-Stokes方程式を解くためのエンドツーエンドの微分可能なフレームワークを提案する。 この統合アプローチは、微分可能不連続なガレルキン解法とニューラルネットワークのソース項を組み合わせる。 提案するフレームワークの性能を2つの例で示す。
  論文  参考訳（メタデータ） (2023-10-29T04:26:23Z)
• Scalable Bayesian Structure Learning for Gaussian Graphical Models Using Marginal Pseudo-likelihood [2.312692134587988]
  連続時間(生死)および離散時間(可逆ジャンプ)マルコフ連鎖モンテカルロ(MCMC)アルゴリズムを開発し、グラフ空間の後方を効率的に探索する。 アルゴリズムは巨大なグラフ空間にスケールし、1000以上のノードを持つグラフの並列探索を可能にする。
  論文  参考訳（メタデータ） (2023-06-30T20:37:40Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature [61.22680308681648]
  決定論的報酬を有する1層ニューラルネットバンディットにおいても,グローバル収束は統計的に難解であることを示す。 非線形バンディットとRLの両方に対して,オンラインモデル学習者による仮想アセンジ(Virtual Ascent with Online Model Learner)というモデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-08T12:41:56Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  変分法による離散的グラフィカルモデルの推論は困難である。 エビデンス・ロウアーバウンド(ELBO)を推定するためのサンプリングに基づく多くの手法が提案されている。 Sum Product Networks (SPN) のような確率的回路モデルのトラクタビリティを活用する新しい手法を提案する。 選択的SPNが表現的変動分布として適していることを示し、対象モデルの対数密度が重み付けされた場合、対応するELBOを解析的に計算可能であることを示す。
  論文  参考訳（メタデータ） (2020-10-22T05:04:38Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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