論文の概要: Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

• arxiv url: http://arxiv.org/abs/2609.12590v1
• Date: Fri, 11 Sep 2026 08:44:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-15 07:38:31.685989
• Title: Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions
• Title（参考訳）: 固定次元の確率勾配オラクルによるタイトサンプリング複雑度
• Abstract要約: ポテンシャルは$$-strongly convexと$L$-smoothであり、原点に関する半径$-1/2$の球に未知のモードがある。 Nstar_textTV=!left(log(1+)+ frac2right), ] $:=frac L$は条件数である。
• 参考スコア（独自算出の注目度）: 5.603202398374589
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in any fixed Euclidean dimension. The potential is $μ$-strongly convex and $L$-smooth, with an unknown mode in the ball of radius $μ^{-1/2}$ about the origin. We have access to unbiased stochastic oracles with the variance at most $σ^2$. For every $σ^2\ge0$ and total variation (TV) accuracy $0<\varepsilon\le1/10$, we prove that the tight complexity of sampling a distribution within $ε$-TV distance from the target distribution is \[ N^\star_{\text{TV}}=Θ\!\left(\log(1+κ)+ \frac{σ^2}{με}\right), \] where $κ:=\frac Lμ$ is the condition number. Note that this complexity bound is simultaneously tight for the condition number $κ$ and accuracy $ε$. Besides, our tight complexity bound is adaptive to noiseless setting $σ=0$, which is $ N^\star_{\text{TV}}=Θ\!\left(\log(1+κ)\right)$.
• Abstract（参考訳）: 任意の固定ユークリッド次元におけるスムーズな対数対数分布のサンプリングの確率的・漸進的クエリ複雑性について検討する。 ポテンシャルは$μ$-strongly convexと$L$-smoothであり、原点に関する半径$μ^{-1/2}の球の未知モードを持つ。 偏差が最大$σ^2$であるような偏りのない確率的オラクルにアクセスできる。 すべての$σ^2\ge0$と全変分(TV)精度$0<\varepsilon\le1/10$に対して、ターゲット分布から$ε$-TVの範囲内で分布をサンプリングする厳密な複雑さは \[N^\star_{\text{TV}}= ! \left(\log(1+κ)+ \frac{σ^2}{με}\right), \] ここで $κ:=\frac Lμ$ は条件数である。 この複雑性境界は条件番号 $κ$ と精度 $ε$ に対して同時に厳密であることに注意。 さらに、我々の厳密な複雑性境界は、ノイズのない設定に適応する$σ=0$、つまり$ N^\star_{\text{TV}}= ! \left(\log(1+κ)\right)$

関連論文リスト

• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces [0.0]
  半空間の平滑化学習の複雑性について,KM25のモデルにおける一様限界の下で検討した。
  論文  参考訳（メタデータ） (2026-05-04T08:53:40Z)
• 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)
• Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions [2.959331374750817]
  これは$d$と$frac1epsilon$である。 $L=mathcalO(1)$と$M=mathrmpoly(d)$である。
  論文  参考訳（メタデータ） (2025-07-15T12:06:11Z)
• 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)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
  多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。 具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。 本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
  論文  参考訳（メタデータ） (2023-11-22T04:34:09Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24: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)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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