論文の概要: A computational phase transition for learning-to-sample from Ising models

• arxiv url: http://arxiv.org/abs/2605.24752v1
• Date: Sat, 23 May 2026 22:04:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-26 19:50:18.362915
• Title: A computational phase transition for learning-to-sample from Ising models
• Title（参考訳）: イジングモデルからの学習とサンプルの計算位相遷移
• Authors: Andrej Risteski, Thuy-Duong Vuong,
• Abstract要約: 生成モデリングの基礎となる基本的なアルゴリズム的タスクであるemphlearning-to-sampleについて検討する。 我々は、スペクトルしきい値のすぐ向こうにある常に有界幅のイジングモデルの族を構築する。 その結果,学習からサンプルへの学習はパラメータ学習よりも困難であることが示唆された。
• 参考スコア（独自算出の注目度）: 26.34581413505931
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study \emph{learning-to-sample} -- a basic algorithmic task underlying generative modeling -- for Ising models, a standard testbed for algorithmic ideas in both theoretical computer science and machine learning. Given i.i.d. samples of an unknown target distribution, the goal of learning-to-sample is to learn a computationally efficient generation procedure that produces new samples following approximately the same distribution. We construct a family of Ising models of constantly bounded-width which lie just beyond the spectral threshold $λ_{\max}(J)-λ_{\min}(J)=1$, and show that learning-to-sample for this family is computationally hard under standard cryptographic assumptions, even when the learner is given both polynomially many i.i.d. samples from the model and explicit access to its parameters. Combined with results of [AJKPV24,KLV25] showing tractability of learning-to-sample below the spectral threshold, this establishes a sharp computational phase transition at the spectral threshold. Moreover, combined with prior results on parameter learning for bounded-width Ising models [KM17,WSD19,VML20], this shows that learning-to-sample can be more difficult than parameter learning. Finally, we show that any efficient learner for these hard instances exhibits a natural memorization-hallucination dichotomy: the learner must either output configurations that, after a simple transformation, match the (transformed) training data or place substantial mass on configurations of negligible probability under the target distribution.
• Abstract（参考訳）: 我々は、理論計算機科学と機械学習の両方におけるアルゴリズム的アイデアの標準的なテストベッドであるIsingモデルに対して、生成モデリングの基礎となる基本的なアルゴリズム的タスクである「emph{learning-to-sample」について研究する。 未知のターゲット分布のサンプル(d.d. sample of a unknown target distribution)を考えると、学習からサンプルへの学習の目的は、ほぼ同じ分布に従って新しいサンプルを生成する計算効率の良い生成手順を学ぶことである。 我々は、スペクトルしきい値である$λ_{\max}(J)-λ_{\min}(J)=1$を超える常に有界幅のイジングモデルのファミリーを構築し、学習者がモデルからのサンプルを多項式的に多く与えられ、そのパラメータへの明示的なアクセスの両方を与えられたとしても、このファミリーの学習対サンプルは標準的な暗号的仮定の下で計算的に困難であることを示す。 AJKPV24,KLV25]のスペクトル閾値以下での学習とサンプルのトラクタビリティを示す結果と組み合わせることで、スペクトル閾値での鋭い計算相転移が確立される。 さらに,有界幅Isingモデル [KM17,WSD19,VML20] に対するパラメータ学習の先行結果と組み合わせることで,学習からサンプルへの学習がパラメータ学習よりも難しいことを示す。 学習者は、単純な変換の後、(変換された)トレーニングデータと一致する構成を出力するか、あるいはターゲット分布の下で無視可能な確率の構成にかなりの質量を配置しなければならない。

関連論文リスト

• A Neuro-inspired Interpretation of Unlearning in Large Language Models through Sample-level Unlearning Difficulty [12.382999548648726]
  既存の研究では、サンプル全体にわたって一様でない学習困難が想定されている。 本稿では,サンプルレベルの未学習難易度を定量化するためのメモリ除去困難度(mathrmMRD$)尺度を提案する。 また、既存の未学習アルゴリズムを最適化するために、$mathrmMRD$ベースの重み付きサンプリング手法を提案する。
  論文  参考訳（メタデータ） (2025-04-09T07:48:10Z)
• Learning to sample fibers for goodness-of-fit testing [0.0]
  離散指数族モデルに対する完全適合性テストを構築することの問題点を考察する。 この問題をマルコフ決定プロセスに変換し、サンプリングのための「よい動きを学ぶための強化学習アプローチ」を示す。 提案アルゴリズムは,評価可能な収束性を持つアクタ・クリティカル・サンプリング方式に基づいている。
  論文  参考訳（メタデータ） (2024-05-22T19:33:58Z)
• Limits of Transformer Language Models on Learning to Compose Algorithms [77.2443883991608]
  我々は,LLaMAモデルのトレーニングと,複数の個別サブタスクの合成学習を必要とする4つのタスクにおけるGPT-4とGeminiの促進について検討した。 その結果,現在最先端のTransformer言語モデルにおける構成学習は,非常に非効率なサンプルであることが示唆された。
  論文  参考訳（メタデータ） (2024-02-08T16:23:29Z)
• The Languini Kitchen: Enabling Language Modelling Research at Different Scales of Compute [66.84421705029624]
  本稿では,アクセル時間で測定された等価計算に基づくモデル比較を可能にする実験的プロトコルを提案する。 私たちは、既存の学術的ベンチマークを上回り、品質、多様性、文書の長さで上回る、大規模で多様で高品質な書籍データセットを前処理します。 この研究は、GPT-2アーキテクチャから派生したフィードフォワードモデルと、10倍のスループットを持つ新しいLSTMの形式でのリカレントモデルという2つのベースラインモデルも提供する。
  論文  参考訳（メタデータ） (2023-09-20T10:31:17Z)
• Towards Automated Imbalanced Learning with Deep Hierarchical Reinforcement Learning [57.163525407022966]
  不均衡学習はデータマイニングにおいて基本的な課題であり、各クラスにトレーニングサンプルの不均等な比率が存在する。 オーバーサンプリングは、少数民族のための合成サンプルを生成することによって、不均衡な学習に取り組む効果的な手法である。 我々は,異なるレベルの意思決定を共同で最適化できる自動オーバーサンプリングアルゴリズムであるAutoSMOTEを提案する。
  論文  参考訳（メタデータ） (2022-08-26T04:28:01Z)
• Pairwise Learning via Stagewise Training in Proximal Setting [0.0]
  非平滑凸対損失関数の収束保証と、適応的なサンプルサイズとペアワイズ学習のための重要サンプリング手法を組み合わせる。 それぞれに逆のインスタンスをサンプリングすると勾配の分散が減少し、収束が加速することを示した。
  論文  参考訳（メタデータ） (2022-08-08T11:51:01Z)
• Exploring Complementary Strengths of Invariant and Equivariant Representations for Few-Shot Learning [96.75889543560497]
  多くの現実世界では、多数のラベル付きサンプルの収集は不可能です。 少ないショット学習はこの問題に対処するための主要なアプローチであり、目的は限られた数のサンプルの存在下で新しいカテゴリに迅速に適応することです。 幾何学的変換の一般集合に対する等分散と不変性を同時に強制する新しい訓練機構を提案する。
  論文  参考訳（メタデータ） (2021-03-01T21:14:33Z)
• Goal-directed Generation of Discrete Structures with Conditional Generative Models [85.51463588099556]
  本稿では,強化学習目標を直接最適化し,期待される報酬を最大化するための新しいアプローチを提案する。 提案手法は、ユーザ定義プロパティを持つ分子の生成と、所定の目標値を評価する短いピソン表現の同定という2つのタスクで検証する。
  論文  参考訳（メタデータ） (2020-10-05T20:03:13Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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