論文の概要: Structured Logconcave Sampling with a Restricted Gaussian Oracle
- arxiv url: http://arxiv.org/abs/2010.03106v4
- Date: Fri, 22 Oct 2021 06:25:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-09 23:04:17.550450
- Title: Structured Logconcave Sampling with a Restricted Gaussian Oracle
- Title(参考訳): 制限付きガウスOracleによるロジコンケーブサンプリング
- Authors: Yin Tat Lee, Ruoqi Shen, Kevin Tian
- Abstract要約: 我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。
凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
- 参考スコア(独自算出の注目度): 23.781520510778716
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give algorithms for sampling several structured logconcave families to
high accuracy. We further develop a reduction framework, inspired by proximal
point methods in convex optimization, which bootstraps samplers for regularized
densities to improve dependences on problem conditioning. A key ingredient in
our framework is the notion of a "restricted Gaussian oracle" (RGO) for $g:
\mathbb{R}^d \rightarrow \mathbb{R}$, which is a sampler for distributions
whose negative log-likelihood sums a quadratic and $g$. By combining our
reduction framework with our new samplers, we obtain the following bounds for
sampling structured distributions to total variation distance $\epsilon$. For
composite densities $\exp(-f(x) - g(x))$, where $f$ has condition number
$\kappa$ and convex (but possibly non-smooth) $g$ admits an RGO, we obtain a
mixing time of $O(\kappa d \log^3\frac{\kappa d}{\epsilon})$, matching the
state-of-the-art non-composite bound; no composite samplers with better mixing
than general-purpose logconcave samplers were previously known. For logconcave
finite sums $\exp(-F(x))$, where $F(x) = \frac{1}{n}\sum_{i \in [n]} f_i(x)$
has condition number $\kappa$, we give a sampler querying $\widetilde{O}(n +
\kappa\max(d, \sqrt{nd}))$ gradient oracles to $\{f_i\}_{i \in [n]}$; no
high-accuracy samplers with nontrivial gradient query complexity were
previously known. For densities with condition number $\kappa$, we give an
algorithm obtaining mixing time $O(\kappa d \log^2\frac{\kappa d}{\epsilon})$,
improving the prior state-of-the-art by a logarithmic factor with a
significantly simpler analysis; we also show a zeroth-order algorithm attains
the same query complexity.
- Abstract(参考訳): 複数の構造化logconcaveファミリを高精度にサンプリングするアルゴリズムを提供する。
さらに,問題条件の依存度を改善するために,正規化密度のスプリサーをブートストラップする,凸最適化における近点法に触発された還元フレームワークの開発を行った。
我々のフレームワークの重要な要素は、$g: \mathbb{r}^d \rightarrow \mathbb{r}$に対する「制限されたガウス神託」(rgo)の概念である。
還元フレームワークと新しいサンプリング器を組み合わせることで、構造化分布を全変動距離$\epsilon$にサンプリングするための以下の境界を求める。
複合密度 $\exp(-f(x) - g(x))$, ここで$f$ は条件番号 $\kappa$ を持ち、convex (しかしおそらく非smooth) $g$ は rgo を許容するので、o(\kappa d \log^3\frac{\kappa d}{\epsilon})$ という混合時間が得られる。
logconcave有限和 $\exp(-f(x))$, where $f(x) = \frac{1}{n}\sum_{i \in [n]} f_i(x)$ 条件数 $\kappa$ を持つ場合、$\widetilde{o}(n + \kappa\max(d, \sqrt{nd}))$gradient oracles to $\{f_i\}_{i \in [n]}$; 以前は、非自明な勾配クエリの複雑さを持つ高精度のサンプルは知られていなかった。
条件数 $\kappa$ を持つ密度に対して、混合時間 $o(\kappa d \log^2\frac{\kappa d}{\epsilon})$ を得るアルゴリズムを与える。
関連論文リスト
- A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity [6.812247730094931]
任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。
また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
論文 参考訳(メタデータ) (2023-09-25T09:50:15Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。
我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文 参考訳(メタデータ) (2022-09-09T23:35:25Z) - 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) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳(メタデータ) (2022-03-28T23:53:48Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳(メタデータ) (2021-10-21T18:43:00Z) - 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) - Composite Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
dpi(x) propto exp(-f(x) - g(x)dx)$ for well-conditioned $f$ and convex (しかし、おそらくは非滑らか) $g$ である。
for $f$ with condition number $kappa$, our algorithm run in $O left(kappa2 d log2tfrackappa depsilonright)$, each querying a gradient of $f$
論文 参考訳(メタデータ) (2020-06-10T17:43:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。