論文の概要: Complexity of zigzag sampling algorithm for strongly log-concave distributions

• arxiv url: http://arxiv.org/abs/2012.11094v1
• Date: Mon, 21 Dec 2020 03:10:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-27 06:40:19.711617
• Title: Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Title（参考訳）: 強対数凹分布に対するジグザグサンプリングアルゴリズムの複雑さ
• Authors: Jianfeng Lu and Lihan Wang
• Abstract要約: 強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。 ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
• 参考スコア（独自算出の注目度）: 6.336005544376984
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. The zigzag process has the advantage of not requiring time discretization for implementation, and that each proposed bouncing event requires only one evaluation of partial derivative of the potential, while its convergence rate is dimension independent. Using these properties, we prove that the zigzag sampling algorithm achieves $\varepsilon$ error in chi-square divergence with a computational cost equivalent to $O\bigl(\kappa^2 d^\frac{1}{2}(\log\frac{1}{\varepsilon})^{\frac{3}{2}}\bigr)$ gradient evaluations in the regime $\kappa \ll \frac{d}{\log d}$ under a warm start assumption, where $\kappa$ is the condition number and $d$ is the dimension.
• Abstract（参考訳）: 強対数凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討した。 zigzagプロセスは、実装に時間的離散化を必要とせず、それぞれのバウンシングイベントはポテンシャルの部分微分の1つの評価しか必要とせず、その収束率は次元に依存しないという利点がある。 これらの特性を用いて、ジグザグサンプリングアルゴリズムは、計算コストが$O\bigl(\kappa^2 d^\frac{1}{2}(\log\frac{1}{\varepsilon})^{\frac{3}{2}}\bigr)$gradient evaluations in the regime $\kappa \ll \frac{d}{\log d}$ in a warm start assumption, where $\kappa$ is the condition number and $d$ is the dimension.

関連論文リスト

• Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• Convergence and Complexity of Stochastic Block Majorization-Minimization [0.0]
  Relaxing Majorization-minimization (SMM)は、Majorization-minimizationの原則のオンライン拡張である。 本稿では,後者の収束ブロックの最大化最小化について述べる。
  論文  参考訳（メタデータ） (2022-01-05T15:17:35Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• On the Sample Complexity of Batch Reinforcement Learning with Policy-Induced Data [80.47164498884271]
  有限マルコフ決定過程(MDP)におけるよい政策を学習する際のサンプル複雑性の基本的な問題について検討する。 本研究の主目的は,計画的地平線$H$が有限である場合,適切な政策を得るのに必要な最小限の遷移数であるサンプル複雑性が,関連する量の指数関数であることを示す。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• The query complexity of sampling from strongly log-concave distributions in one dimension [14.18847457501901]
  Omega(loglogkappa)$の最初の厳密な下限を、強い対数凹と対数平滑な分布のクラスからサンプリングするクエリに設定する。 本稿では,この指数的ギャップを埋めるリジェクションに基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-29T00:51:17Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。 この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。 本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。 我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
  論文  参考訳（メタデータ） (2021-05-27T23:41:01Z)
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations [0.3553493344868413]
  エルゴード微分方程式のイン分布と強い対数凸の場合の分布との間のワッサースタイン距離について検討した。 これにより、過減衰および過減衰ランジュバン力学の文献で提案されている多くの異なる近似を統一的に研究することができる。
  論文  参考訳（メタデータ） (2021-04-26T07:50:04Z)

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

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