論文の概要: Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

• arxiv url: http://arxiv.org/abs/2611.03442v1
• Date: Mon, 02 Nov 2026 16:55:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 04:31:46.026697
• Title: Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
• Title（参考訳）: Subpolynomial-Query Proximal Smpling over Log-Concavity
• Abstract要約: 勾配クエリの複雑さは、密度$(x)proptomathrme-V(x)$ on $mathbbRd$から研究される。 我々は,[OpenAI 2026]の高次ノイズ条件付きサンプルを用いて観測チェーンを実装した。
• 参考スコア（独自算出の注目度）: 39.60626649358539
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $β$-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If $π$ satisfies a log-Sobolev inequality (LSI) with constant $α$, then for every fixed $ν>0$, there is a finite constant $C_ν$ depending only on $ν$ such that the algorithm returns a sample within total-variation distance $\varepsilon$ using at most $C_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν$ queries, where $κ=β/α$ and $x_0$ is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.
• Abstract（参考訳）: 密度$π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ have a $β$-Lipschitz gradient, but not be convex。 提案手法では,ガウス摂動と雑音観測に基づく位置条件のサンプリングを交互に行う。 我々は,[OpenAI 2026]の高次ノイズ条件付きサンプルを用いて観測チェーンを実装し, 機能的不等式下での次元依存性の向上を図った。 もし$π$が対数ソボレフ不等式(LSI)を定数$α$で満たすなら、すべての固定$ν>0$に対して、アルゴリズムが全変量距離内のサンプルを返すような$ν$のみに依存する有限定数$C_ν$が存在し、最も高い$C_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν$クエリを使用すると、$κ=β/α$と$x_0$は初期化の任意の基準点となる。 解析は、正確な近位履歴に沿って中心依存性の局所誤差を制御し、条件付き復号により最終観測ノイズを除去する。 ポアンカレの不等式(英: Poincaré inequality, PI)の下では、熱いスタートから対応する保証を得る。 オラクルの下限は、LSIの下で十分である定常点のみがPIの下では不十分であることを示している。

関連論文リスト

• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• A proximal gradient algorithm for composite log-concave sampling [9.11122093402205]
  我々は、$mathbbRd$、すなわち$propto e-f-g$という形の密度の合成対数分布からサンプリングするアルゴリズムを提案する。 さらに、(1)$が非log-concaveであるが、 Poincaré あるいは log-Sobolev の不等式を満たす場合、(2)$f$ が非smooth であるが Lipschitz である場合にも結果を拡張します。
  論文  参考訳（メタデータ） (2026-05-12T17:48:09Z)
• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
  密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。 広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
  論文  参考訳（メタデータ） (2025-02-10T06:54:16Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
  本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。 また、ディキンウォークの「ソフトパイ」バージョンも提示する。
  論文  参考訳（メタデータ） (2021-11-07T13:44:50Z)

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

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