論文の概要: Efficiently Sampling the PSD Cone with the Metric Dikin Walk

• arxiv url: http://arxiv.org/abs/2307.12943v1
• Date: Mon, 24 Jul 2023 17:15:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-25 13:21:53.641606
• Title: Efficiently Sampling the PSD Cone with the Metric Dikin Walk
• Title（参考訳）: 距離ディキンウォークによるpsdコーンの効率的なサンプリング
• Authors: Yunbum Kook, Santosh S. Vempala
• Abstract要約: 半定値プログラムは効率的な計算のフロンティアを表す。 サンプリングのための既知の時間アルゴリズムの直接適用は、極めて高い実行時間をもたらす。 我々は、自己調和関数の洗練された概念を導入し、異なるメトリクスを組み合わせるためのルールを与える。
• 参考スコア（独自算出の注目度）: 10.577988224813653
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Semi-definite programs represent a frontier of efficient computation. While there has been much progress on semi-definite optimization, with moderate-sized instances currently solvable in practice by the interior-point method, the basic problem of sampling semi-definite solutions remains a formidable challenge. The direct application of known polynomial-time algorithms for sampling general convex bodies to semi-definite sampling leads to a prohibitively high running time. In addition, known general methods require an expensive rounding phase as pre-processing. Here we analyze the Dikin walk, by first adapting it to general metrics, then devising suitable metrics for the PSD cone with affine constraints. The resulting mixing time and per-step complexity are considerably smaller, and by an appropriate choice of the metric, the dependence on the number of constraints can be made polylogarithmic. We introduce a refined notion of self-concordant matrix functions and give rules for combining different metrics. Along the way, we further develop the theory of interior-point methods for sampling.
• Abstract（参考訳）: 半定義プログラムは効率的な計算のフロンティアを表す。 半定値最適化には多くの進歩があり、中程度のインスタンスは、現在インテリアポイント法で解決可能であるが、半定値解をサンプリングする基本的な問題は、依然として非常に難しい課題である。 一般凸体をサンプリングするための既知の多項式時間アルゴリズムの半定サンプリングへの直接適用は、極めて高い実行時間をもたらす。 さらに、既知の一般的な方法は、前処理として高価な丸めフェーズを必要とする。 ここではダイキンウォークを分析し、まず一般的なメトリクスに適応し、次にアフィン制約のあるpsdコーンに適したメトリクスを考案する。 結果として生じる混合時間とステップ毎の複雑さはかなり小さく、計量の適切な選択により、制約数への依存を多元対数化することができる。 自己調和行列関数の洗練された概念を導入し、異なるメトリクスを組み合わせるためのルールを与える。 その過程で, サンプリングのための内点法の理論をさらに発展させる。

関連論文リスト

• Harmonic Path Integral Diffusion [0.4527270266697462]
  本稿では,連続多変量確率分布から抽出する新しい手法を提案する。 本手法では,状態空間の起点を中心とするデルタ関数を$t=0$とし,ターゲット分布に$t=1$で変換する。 これらのアルゴリズムは他のサンプリング手法、特にシミュレートおよびパス積分サンプリングと対比し、解析制御、精度、計算効率の点でそれらの利点を強調した。
  論文  参考訳（メタデータ） (2024-09-23T16:20:21Z)
• Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
  非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。 対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。 我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
  論文  参考訳（メタデータ） (2024-05-27T00:53:18Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Plug-and-Play split Gibbs sampler: embedding deep generative priors in Bayesian inference [12.91637880428221]
  本稿では, 後方分布から効率的にサンプリングするために, 可変分割を利用したプラグアンドプレイサンプリングアルゴリズムを提案する。 後方サンプリングの課題を2つの単純なサンプリング問題に分割する。 その性能は最近の最先端の最適化とサンプリング手法と比較される。
  論文  参考訳（メタデータ） (2023-04-21T17:17:51Z)
• Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling [34.66940399825547]
  本稿では,Langevinアルゴリズムの定常分布に対する混合時間の特徴について述べる。 本稿では,差分プライバシー文献からサンプリング文献へのアプローチを紹介する。
  論文  参考訳（メタデータ） (2022-10-16T05:11:16Z)
• A Proximal Algorithm for Sampling from Non-smooth Potentials [10.980294435643398]
  非滑らかなポテンシャルからのサンプリングのための新しいMCMCアルゴリズムを提案する。 本手法は, 近似バンドル法と交互サンプリングフレームワークに基づく。 この研究の重要な貢献は、任意の凸非滑らかポテンシャルに対して制限されたガウスオラクルを実現する高速アルゴリズムである。
  論文  参考訳（メタデータ） (2021-10-09T15:26:07Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  ガウス過程後部をシミュレーションするための従来のアプローチでは、有限個の入力位置のプロセス値の限界分布からサンプルを抽出する。 この分布中心の特徴づけは、所望のランダムベクトルのサイズで3次スケールする生成戦略をもたらす。 条件付けのこのパスワイズ解釈が、ガウス過程の後部を効率的にサンプリングするのに役立てる近似の一般族をいかに生み出すかを示す。
  論文  参考訳（メタデータ） (2020-11-08T17:09:37Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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