Fugu-MT 論文翻訳(概要): Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions

論文の概要: Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions

arxiv url: http://arxiv.org/abs/2507.11236v1
Date: Tue, 15 Jul 2025 12:06:11 GMT
ステータス: 翻訳完了
システム内更新日: 2025-07-16 19:46:03.099943
Title: Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions
Title（参考訳）: 非log-concave分布に対するサンプリングアルゴリズムの改善とポアンカレ不等式
Authors: Yuchen He, Zhehan Lei, Jianan Shao, Chihao Zhang,
Abstract要約: これは$d$と$frac1epsilon$である。 $L=mathcalO(1)$と$M=mathrmpoly(d)$である。
参考スコア（独自算出の注目度）: 1.9753732769115382
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the problem of sampling from a distribution $\mu$ with density $\propto e^{-V}$ for some potential function $V:\mathbb R^d\to \mathbb R$ with query access to $V$ and $\nabla V$. We start with the following standard assumptions: (1) The potential function $V$ is $L$-smooth. (2) The second moment $\mathbf{E}_{X\sim \mu}[\|X\|^2]\leq M$. Recently, He and Zhang (COLT'25) showed that the query complexity of sampling from such distributions is at least $\left(\frac{LM}{d\epsilon}\right)^{\Omega(d)}$ where $\epsilon$ is the desired accuracy in total variation distance, and the Poincar\'e constant can be arbitrarily large. Meanwhile, another common assumption in the study of diffusion based samplers (see e.g., the work of Chen, Chewi, Li, Li, Salim and Zhang (ICLR'23)) strengthens the smoothness condition (1) to the following: (1*) The potential function of *every* distribution along the Ornstein-Uhlenbeck process starting from $\mu$ is $L$-smooth. We show that under the assumptions (1*) and (2), the query complexity of sampling from $\mu$ can be $\mathrm{poly}(L,d)\cdot \left(\frac{Ld+M}{\epsilon^2}\right)^{\mathcal{O}(L+1)}$, which is polynomial in $d$ and $\frac{1}{\epsilon}$ when $L=\mathcal{O}(1)$ and $M=\mathrm{poly}(d)$. This improves the algorithm with quasi-polynomial query complexity developed by Huang et al. (COLT'24). Our results imply that the seemly moderate strengthening of the smoothness condition (1) to (1*) can lead to an exponential gap in the query complexity of sampling algorithms. Moreover, we show that together with the assumption (1*) and the stronger moment assumption that $\|X\|$ is $\lambda$-sub-Gaussian for $X\sim\mu$, the Poincar\'e constant of $\mu$ is at most $\mathcal{O}(\lambda)^{2(L+1)}$. As an application of our technique, we obtain improved estimate of the Poincar\'e constant for mixture of Gaussians with the same covariance.
Abstract（参考訳）: 我々は、あるポテンシャル関数 $V:\mathbb R^d\to \mathbb R$ に対して密度 $\propto e^{-V}$ の分布 $\mu$ からサンプリングする問題を、$V$ と $\nabla V$ へのクエリアクセスで研究する。 1) ポテンシャル関数 $V$ は $L$-smooth である。 2) 第二モーメント $\mathbf{E}_{X\sim \mu}[\|X\|^2]\leq M$。最近、He and Zhang (COLT'25) は、そのような分布からのサンプリングのクエリの複雑さが少なくとも$\left(\frac{LM}{d\epsilon}\right)^{\Omega(d)}$であることを示した。一方、拡散に基づくサンプリングの研究における別の一般的な仮定(例えば、Chen, Chewi, Li, Li, Salim and Zhang (ICLR'23))は、滑らかさ条件 (1) を次のように強化する: (1*) オルンシュタイン-ウレンベック過程に沿った *every* 分布のポテンシャル関数は、$\mu$ から始まる$L$-smooth である。仮定 (1*) と (2) の下で、$\mu$ からのサンプリングのクエリ複雑性は $\mathrm{poly}(L,d)\cdot \left(\frac{Ld+M}{\epsilon^2}\right)^{\mathcal{O}(L+1)}$ であり、$L=\mathcal{O}(1)$ と $M=\mathrm{poly}(d)$ の多項式である。これにより、Huang et al (COLT'24)によって開発された準多項式クエリの複雑さによってアルゴリズムが改善される。その結果,(1)から(1*)への滑らかさ条件の適度な強化が,サンプリングアルゴリズムのクエリ複雑性の指数的ギャップを生じさせる可能性が示唆された。さらに、$\|X\|$ が $\lambda$-sub-Gaussian for $X\sim\mu$ であるという仮定 (1*) と強いモーメント仮定とともに、$\mu$ の Poincar\'e 定数は少なくとも $\mathcal{O}(\lambda)^{2(L+1)}$ であることを示す。この手法の応用として、同じ共分散を持つガウス多様体の混合に対するポアンカル定数の改善された推定値を得る。

関連論文リスト

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)
Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文参考訳（メタデータ） (2024-09-05T16:59:56Z)
Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文参考訳（メタデータ） (2024-08-10T04:26:19Z)
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文参考訳（メタデータ） (2023-09-20T21:41:59Z)
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)
On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
論文参考訳（メタデータ） (2022-10-25T11:37:11Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文参考訳（メタデータ） (2022-03-28T23:53:48Z)
Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文参考訳（メタデータ） (2022-03-17T23:52:08Z)
Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文参考訳（メタデータ） (2020-07-16T06:44:44Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文参考訳（メタデータ） (2020-04-13T08:06:29Z)

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

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