論文の概要: The Power of Test-Time Training for Approximate Sampling

• arxiv url: http://arxiv.org/abs/2606.11437v1
• Date: Tue, 09 Jun 2026 20:48:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-11 16:42:38.175735
• Title: The Power of Test-Time Training for Approximate Sampling
• Title（参考訳）: 近似サンプリングのためのテスト時間学習の力
• Authors: Noah Golowich, Ankur Moitra, Dhruv Rohatgi,
• Abstract要約: 本稿では,所定の確率測定値からサンプルを生成する問題として,テストタイムトレーニング(TTT)の形式化を提案する。 まず、$star$から$hat$へのクエリアクセスをサンプリングする際の、クエリの複雑さの2次的に低い境界を示します。 次に、$F$ の大きさが適切に有界であれば、この下限は回避可能であることを示す。
• 参考スコア（独自算出の注目度）: 31.241924302093736
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Efficiently sampling from a complex probability distribution is a fundamental problem which has become increasingly pertinent in recent years with the rise of generative AI, as sophisticated sampling procedures from LLMs have been proposed to solve challenging reasoning problems. The efficacy of such sampling algorithms is limited, however, by the relationship between the LLM and the particular sampling task at hand, which has motivated the framework of test-time training (TTT). TTT works by updating a model's weights in response to partial generations and reward feedback received at inference time, thus adapting to the particular problem. In this work, we propose a formalization for TTT as the problem of producing a sample from a given probability measure $μ^\star$ belonging to a known class ${F}$ of distributions, given an oracle $\hat μ$ which yields approximate density estimates for $μ^\star$. This is closely related to the problem of reducing sampling to approximate counting studied in seminal works of Jerrum, Valiant & Vazirani (1986) and Jerrum & Sinclair (1989): namely, when ${F}$ is the class of all distributions, it coincides exactly with the aforementioned counting-to-sampling reduction. In this paper, we first show a quadratic lower bound on the query complexity of sampling from $μ^\star$ given query access to $\hat μ$ (for sufficiently large classes ${F}$), thus showing that the random walk approach proposed by Jerrum & Sinclair (1989) and refined by Hayes & Sinclair (2010), is optimal. This answers an open question posed by Hayes & Sinclair. We then show that this lower bound can be circumvented if the size of ${F}$ is bounded appropriately. As we discuss, this latter result can be viewed as an abstraction of TTT, and thus represents a starting point for the development of a principled theoretical framework for TTT.
• Abstract（参考訳）: 複雑な確率分布からの効率的なサンプリングは、LLMの洗練されたサンプリング手順が、難解な推論問題を解くために提案されているため、生成的AIの台頭により近年ますます重要になっている根本的な問題である。 このようなサンプリングアルゴリズムの有効性は, テストタイムトレーニング(TTT)の枠組みを動機づけた, LLMと手前の特定のサンプリングタスクの関係によって制限されている。 TTTは、部分的な世代に対応するモデルの重みを更新し、推論時に受け取った報奨フィードバックを処理し、特定の問題に適応する。 本研究では,ある確率測度$μ^\star$から分布の既知のクラス${F}$に属するサンプルを生成する問題として TTT の形式化を提案する。 これは、Jerrum, Valiant & Vazirani (1986) と Jerrum & Sinclair (1989) の楽譜で研究された近似数え上げにサンプリングを還元する問題と密接に関連している。 本稿では、まず、$μ^\star$から$\hat μ$(十分に大きなクラスに対して${F}$)へのクエリアクセスをサンプリングする際のクエリ複雑性の2次的下限を示すので、Jerrum & Sinclair (1989) が提案し、Hayes & Sinclair (2010) が洗練したランダムウォークアプローチが最適であることを示す。 これはHayes & Sinclair氏によるオープンな質問に答える。 次に、${F}$ の大きさが適切に有界であれば、この下界は回避可能であることを示す。 本稿で論じるとおり、後者の結果はTTTの抽象化と見なすことができ、TTTの原理的理論フレームワークの開発の出発点となる。

関連論文リスト

• Entropy Equivalence Testing [43.089793195592115]
  本稿では,確率分布のエンヘントロピー同値検定の問題を紹介する。 この課題に対する最適なサンプルの複雑さは、クローズネステストよりも著しく低いことを示します。 我々はこの結果を利用して、低次EmphBayesianネットワークの(標準)クローズネスに対する最初の非自明なテストアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2026-05-22T04:35:04Z)
• O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions [6.76974373198208]
  最小の仮定の下で,拡散確率モデル(DDPM)の高速収束理論を確立する。 収束率は$O(k/T)$に改善され、$k$は対象データ分布の内在次元であることを示す。 これはDDPMが未知の低次元構造に自動的に適応する能力を強調している。
  論文  参考訳（メタデータ） (2024-09-27T17:59:10Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning [34.4255062106615]
  トンプソンサンプリング(TS)は、使用が容易で、経験的性能に訴えるため、シーケンシャルな意思決定に広く用いられている。 バッチ化された$textitLangevin Thompson Sampling$アルゴリズムを提案する。 アルゴリズムは計算効率が高く,MABでは$mathcalO(log T)$,RLでは$mathcalO(sqrtT)$と同じオーダー最適後悔保証を維持している。
  論文  参考訳（メタデータ） (2023-06-15T01:16:29Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

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

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