論文の概要: Smoothed Score Queries and the Complexity of Sampling
- arxiv url: http://arxiv.org/abs/2605.27769v1
- Date: Tue, 26 May 2026 23:38:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-28 17:38:55.607042
- Title: Smoothed Score Queries and the Complexity of Sampling
- Title（参考訳）: 平滑なスコアクエリとサンプリングの複雑さ
- Authors: Jingbo Liu,
- Abstract要約: 勾配情報を用いた高次元ガウス分布からのサンプリングのクエリ複雑性について検討する。
総変分エラー(_rm TV)に対するスムーズなスコアクエリは、(sqrt)から対数への条件数依存性を改善する。
また、有限ビット勾配オラクルも研究している。
- 参考スコア（独自算出の注目度）: 17.319855487817257
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the query complexity of sampling from high-dimensional Gaussian distributions using gradient information. In the standard oracle model, exact gradients expose only matrix-vector products with the precision matrix, leading to polynomial approximation barriers and a characteristic \(\sqrtκ\) dependence on the condition number. We show that this barrier disappears when the sampler is allowed to query \emph{smoothed scores}, namely gradients of the logarithms of the Gaussian-convolved densities. For a Gaussian target with precision matrix \(Λ\), a smoothed-score query at noise level \(τ\) gives access to the resolvent \((Λ+τ^{-1}I)^{-1}\). Combining geometrically spaced noise levels with sinc-quadrature rational approximation, we obtain a sampler with $q=O\!\left(\bigl(\logκ+\log(e\sqrt d/δ_{\rm TV})\bigr)\log(e\sqrt d/δ_{\rm TV})\right)$ smoothed-score queries for total variation error \(δ_{\rm TV}\), improving the condition-number dependence from \(\sqrtκ\) to logarithmic. We also study finite-bit gradient oracles. Using coordinatewise quantization of the transformed smoothed-score answers and a final dithering step, we obtain a sampling scheme whose total communicated gradient information is polylogarithmic in \(κ\); in particular, for fixed dimension and accuracy, the bit complexity is \(O(\log^2κ)\). To complement these upper bounds, we introduce a channel-synthesis, or reverse-Shannon, converse technique for sampling lower bounds. This converts total-variation simulation guarantees into communication requirements and yields an \(Ω(\logκ)\) lower bound on the required gradient information. Together, these results identify smoothed scores as a provably more informative oracle for sampling and give nearly matching upper and lower bounds for its finite-bit complexity.
- Abstract（参考訳）: 勾配情報を用いた高次元ガウス分布からのサンプリングのクエリ複雑性について検討する。
標準的なオラクルモデルでは、正確な勾配は行列ベクトル積のみを精度行列で露出し、多項式近似障壁と条件数への特性 \(\sqrtκ\) 依存をもたらす。
この障壁は、サンプルが \emph{smoothed scores} を問うことを許されたときに消失する。
精度行列 \(\) を持つガウス的対象に対して、ノイズレベル \(τ\) における滑らかなスコアのクエリは、分解剤 \()+τ^{-1}I)^{-1}\ へのアクセスを与える。
幾何空間雑音レベルとシンク四分法有理近似を組み合わせることで、$q=O\!
\left(\bigl(\logκ+\log(e\sqrt d/δ_{\rm TV})\bigr)\log(e\sqrt d/δ_{\rm TV})\right)$ smoothed-score query for total variation error \(δ_{\rm TV}\)。
また、有限ビット勾配オラクルも研究している。
変換されたスムーズなスコア回答の座標量子化と最終ディザリングステップを用いて、全通信された勾配情報が \(κ) において多対数的なサンプリングスキームを得る。
これらの上界を補うために、下界をサンプリングするためのチャネル合成(リバースシャノン)コンバース技術を導入する。
これにより、全変量シミュレーションの保証を通信要求に変換し、要求される勾配情報に対して \(Ω(\logκ)\) 以下の境界を与える。
これらの結果は、スムーズなスコアをサンプリングのための証明可能なより情報的なオラクルとして識別し、その有限ビットの複雑さに対してほぼ一致する上と下の境界を与える。
関連論文リスト
- High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
サブエクスフォデンシャルテールの繰り返し勾配を用いて,ログコンケーブサンプリングの精度保証が達成可能であることを示す。
また、このフレームワークは、0番目の順序(値)クエリの下でも、同様の高精度な保証を提供する。
論文 参考訳（メタデータ） (2026-02-15T23:19:07Z) - Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models [55.07411490538404]
本稿では,次元$d$の適応的複雑性依存性を改善する並列サンプリング手法を提案する。
我々の手法は科学計算による並列シミュレーション技術に基づいている。
論文 参考訳（メタデータ） (2024-12-10T11:50:46Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Samplet basis pursuit: Multiresolution scattered data approximation with sparsity constraints [0.0]
我々は,$ell_1$-regularization を用いたサンプルト座標における分散データ近似について検討する。
Riesz isometry を用いて、標本を再現されたカーネルヒルベルト空間に埋め込む。
組込みサンプルベースに対してスパースな信号のクラスは、カーネル翻訳の基盤に関してスパースな信号のクラスよりもかなり大きいと論じる。
論文 参考訳（メタデータ） (2023-06-16T21:20:49Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data [7.513100214864646]
収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。
適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
論文 参考訳（メタデータ） (2022-03-29T17:59:10Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。