論文の概要: 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（参考訳）: 近似サンプリングのためのテスト時間学習の力
• 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の原理的理論フレームワークの開発の出発点となる。

関連論文リスト

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• 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)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• 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)
• Faster high-accuracy log-concave sampling via algorithmic warm starts [6.117084972237769]
  実際には、古典的なメトロポリス調整ランゲヴィンアルゴリズム(MALA)のような高精度なサンプリング器は事実上のゴールド標準のままである。 我々は,このサンプリング問題の次元依存性を$tildeO(d1/2)$に改善し,MALAでは$tildeO(d1/2)$とした。 我々の主な技術的貢献は、離散化アンダーダム化ランゲヴィン拡散に対する最初の$tildeO(d1/2)$ R'enyi混合速度を確立することでこの問題を解決することである。
  論文  参考訳（メタデータ） (2023-02-20T19:27:21Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Rejection sampling from shape-constrained distributions in sublinear time [14.18847457501901]
  離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討した。 本研究は,アルファベットサイズに比例して複雑度が増大するサンプリングのための新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-29T01:00:42Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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