論文の概要: Composite Logconcave Sampling with a Restricted Gaussian Oracle
- arxiv url: http://arxiv.org/abs/2006.05976v1
- Date: Wed, 10 Jun 2020 17:43:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-23 05:33:38.529731
- Title: Composite Logconcave Sampling with a Restricted Gaussian Oracle
- Title（参考訳）: 制限ガウス神託を用いた複合ログコンケーブサンプリング
- Authors: Ruoqi Shen, Kevin Tian, Yin Tat Lee
- Abstract要約: 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$
- 参考スコア（独自算出の注目度）: 23.781520510778716
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider sampling from composite densities on $\mathbb{R}^d$ of the form
$d\pi(x) \propto \exp(-f(x) - g(x))dx$ for well-conditioned $f$ and convex (but
possibly non-smooth) $g$, a family generalizing restrictions to a convex set,
through the abstraction of a restricted Gaussian oracle. For $f$ with condition
number $\kappa$, our algorithm runs in $O \left(\kappa^2 d \log^2\tfrac{\kappa
d}{\epsilon}\right)$ iterations, each querying a gradient of $f$ and a
restricted Gaussian oracle, to achieve total variation distance $\epsilon$. The
restricted Gaussian oracle, which draws samples from a distribution whose
negative log-likelihood sums a quadratic and $g$, has been previously studied
and is a natural extension of the proximal oracle used in composite
optimization. Our algorithm is conceptually simple and obtains stronger
provable guarantees and greater generality than existing methods for composite
sampling. We conduct experiments showing our algorithm vastly improves upon the
hit-and-run algorithm for sampling the restriction of a (non-diagonal) Gaussian
to the positive orthant.
- Abstract（参考訳）: d\pi(x) \propto \exp(-f(x) - g(x))dx$ for well-conditioned $f$ and convex (but non-smooth) $g$、制限されたガウス神託の抽象化を通じて凸集合への制限を一般化した族である。
条件番号 $\kappa$ で$f$ の場合、アルゴリズムは$o \left(\kappa^2 d \log^2\tfrac{\kappa d}{\epsilon}\right)$ で実行され、それぞれ$f$ の勾配と制限されたガウスオラクルをクエリし、全変動距離 $\epsilon$ を達成する。
負の対数類似度が2次和と$g$の分布からサンプルを引き出す限定ガウスオラクルは、以前に研究され、合成最適化に使用される近位オラクルの自然な拡張である。
提案アルゴリズムは概念的に単純であり,既存の複合サンプリング法よりも証明可能な保証と一般化が得られる。
提案手法は,正のオータントに対する(非対角的)ガウスの制限をサンプリングするヒット・アンド・ランアルゴリズムを大幅に改善することを示す実験を行う。
関連論文リスト
- 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) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Rényi-infinity constrained sampling with $d^3$ membership queries [2.209921757303168]
本稿では,エレガントな収束保証を有する原理的かつ単純なアルゴリズムである制約付き近位サンプリング手法を提案する。
R'enyi-infinity divergence(mathcal R_infty$)に収束することを示す。
論文 参考訳（メタデータ） (2024-07-17T19:20:08Z) - 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) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Projected Stochastic Gradient Langevin Algorithms for Constrained
Sampling and Non-Convex Learning [0.0]
ランジュバンアルゴリズムは付加ノイズを持つ手法である。
ランジュバンアルゴリズムは何十年もチェーンカルロ(ミロン)で使われてきた
学習にとって、それはそれがそれが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それがそれが事実であるということであり、それがそれがそれが事実であるということであるということであるということが、それが事実であるということであるということが、それが事実であるということであることを示している。
論文 参考訳（メタデータ） (2020-12-22T16:19:20Z) - Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。
凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文 参考訳（メタデータ） (2020-10-07T01:43:07Z) - 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) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。