論文の概要: Accelerating Certifiable Estimation with Preconditioned Eigensolvers
- arxiv url: http://arxiv.org/abs/2207.05257v1
- Date: Tue, 12 Jul 2022 02:00:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-13 14:02:17.072563
- Title: Accelerating Certifiable Estimation with Preconditioned Eigensolvers
- Title（参考訳）: 事前条件付き固有解法による認証評価の高速化
- Authors: David M. Rosen
- Abstract要約: 多くの最先端 (Burer-Monteiro 因数分解に基づく) 推定手法における主要なコストは、解の検証である。
本稿では,この検証ステップを著しく高速化する方法を示し,検証手法の全体的な高速化について述べる。
事前条件付き固有解法を用いてこの問題に対処する方法を示す。
- 参考スコア（独自算出の注目度）: 2.1701691499017812
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Convex (specifically semidefinite) relaxation provides a powerful approach to
constructing robust machine perception systems, enabling the recovery of
certifiably globally optimal solutions of challenging estimation problems in
many practical settings. However, solving the large-scale semidefinite
relaxations underpinning this approach remains a formidable computational
challenge. A dominant cost in many state-of-the-art (Burer-Monteiro
factorization-based) certifiable estimation methods is solution verification
(testing the global optimality of a given candidate solution), which entails
computing a minimum eigenpair of a certain symmetric certificate matrix. In
this paper, we show how to significantly accelerate this verification step, and
thereby the overall speed of certifiable estimation methods. First, we show
that the certificate matrices arising in the Burer-Monteiro approach
generically possess spectra that make the verification problem expensive to
solve using standard iterative eigenvalue methods. We then show how to address
this challenge using preconditioned eigensolvers; specifically, we design a
specialized solution verification algorithm based upon the locally optimal
block preconditioned conjugate gradient (LOBPCG) method together with a simple
yet highly effective algebraic preconditioner. Experimental evaluation on a
variety of simulated and real-world examples shows that our proposed
verification scheme is very effective in practice, accelerating solution
verification by up to 280x, and the overall Burer-Monteiro method by up to 16x,
versus the standard Lanczos method when applied to relaxations derived from
large-scale SLAM benchmarks.
- Abstract（参考訳）: 凸緩和(具体的には半定値)は、堅牢な機械認識システムを構築するための強力なアプローチを提供し、多くの実践的な設定において、挑戦的な推定問題の世界的な最適解の回復を可能にする。
しかし、このアプローチの基盤となる大規模な半定値緩和の解決は、依然として強力な計算課題である。
多くの最先端の証明可能な推定手法における支配的なコストは、ある対称証明行列の最小固有値を計算することを伴う解検証(与えられた候補解のグローバル最適性を検証する)である。
本稿では,この検証ステップを著しく高速化する方法を示し,検証手法の全体的な高速化について述べる。
まず,Burer-Monteiro 法で生じる証明行列は,標準反復固有値法を用いて検証問題を解くのにコストがかかるようなスペクトルを包含していることを示す。
そこで我々は, 局所最適ブロック条件付き共役勾配(LOBPCG)法と, 単純で高効率な代数的前処理器を併用した, 特殊解検証アルゴリズムを設計した。
シミュレーションおよび実世界の様々な実例に対する実験評価により,提案手法は,大規模SLAMベンチマークから導出した緩和法に適用した場合に,最大280倍までの解検証を高速化し,Burer-Monteiro法を最大16倍まで高速化することを示す。
関連論文リスト
- PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates [17.777466668123886]
PROMISE ($textbfPr$econditioned $textbfO$ptimization $textbfM$ethods by $textbfI$ncorporating $textbfS$calable Curvature $textbfE$stimates)はスケッチベースの事前条件勾配アルゴリズムである。
PROMISEには、SVRG、SAGA、およびKatyushaのプレコンディション版が含まれている。
論文 参考訳（メタデータ） (2023-09-05T07:49:10Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - No-Regret Constrained Bayesian Optimization of Noisy and Expensive
Hybrid Models using Differentiable Quantile Function Approximations [0.0]
Constrained Upper Quantile Bound (CUQB) は、制約近似を避けるための概念的に単純で決定論的アプローチである。
CUQBは制約のある場合と制約のない場合の両方において従来のベイズ最適化よりも著しく優れることを示す。
論文 参考訳（メタデータ） (2023-05-05T19:57:36Z) - Scalable Bayesian Meta-Learning through Generalized Implicit Gradients [64.21628447579772]
Inlicit Bayesian Meta-learning (iBaML) 法は、学習可能な事前のスコープを広げるだけでなく、関連する不確実性も定量化する。
解析誤差境界は、明示的よりも一般化された暗黙的勾配の精度と効率を示すために確立される。
論文 参考訳（メタデータ） (2023-03-31T02:10:30Z) - A Simple and Scalable Tensor Completion Algorithm via Latent Invariant
Constraint for Recommendation System [6.125831939376033]
本研究では,ユーザ評価の低さを考慮に入れた,観測不能な個人の嗜好に対するモデルのパラメータを効率的に,かつ正確に学習する手法を提案する。
テンソル分解を1つの潜在不変量で正規化することにより、信頼できるレコメンダシステムに対して3つの特性を達成する。
論文 参考訳（メタデータ） (2022-06-27T15:03:18Z) - Certified Symmetry and Dominance Breaking for Combinatorial Optimisation [13.333957453318744]
本研究では,対称性と支配的破壊が容易に表現可能な最適化問題に対する認証手法を開発した。
提案手法は,提案手法が幅広い問題に適用可能であることを示す概念実証として,最大斜め解法と制約法に適用する。
論文 参考訳（メタデータ） (2022-03-23T08:45:35Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳（メタデータ） (2020-11-05T08:04:34Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Density Fixing: Simple yet Effective Regularization Method based on the
Class Prior [2.3859169601259347]
本稿では,教師付き・半教師付き学習によく用いられる密度固定法という正規化手法の枠組みを提案する。
提案手法は,モデルの事前分布や発生頻度を近似させることで,一般化性能を向上させる。
論文 参考訳（メタデータ） (2020-07-08T04:58:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。