論文の概要: Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+
- arxiv url: http://arxiv.org/abs/2406.10407v2
- Date: Wed, 7 Aug 2024 20:10:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-09 19:57:18.306992
- Title: Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+
- Title（参考訳）: トレースバウンドSDPに対するサブ最適境界は、高速でスケーラブルな低ランクSDPソルバSDPLR+を可能にする
- Authors: Yufan Huang, David F. Gleich,
- Abstract要約: 半定プログラム(SDP)は、機械学習とデータサイエンスに多くの応用がある強力なツールである。
SDPソルバは、正の半定値決定変数がn×n$密度行列であるため、困難である。
20年前、Burer氏とMonteiro氏は、完全な行列の代わりに低ランクの分解を最適化したSDPソルバを開発した。
- 参考スコア（独自算出の注目度）: 3.7507283158673212
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Semidefinite programs (SDPs) and their solvers are powerful tools with many applications in machine learning and data science. Designing scalable SDP solvers is challenging because by standard the positive semidefinite decision variable is an $n \times n$ dense matrix, even though the input is often $n \times n$ sparse matrices. However, the information in the solution may not correspond to a full-rank dense matrix as shown by Barvinok and Pataki. Two decades ago, Burer and Monteiro developed an SDP solver $\texttt{SDPLR}$ that optimizes over a low-rank factorization instead of the full matrix. This greatly decreases the storage cost and works well for many problems. The original solver $\texttt{SDPLR}$ tracks only the primal infeasibility of the solution, limiting the technique's flexibility to produce moderate accuracy solutions. We use a suboptimality bound for trace-bounded SDP problems that enables us to track the progress better and perform early termination. We then develop $\texttt{SDPLR+}$, which starts the optimization with an extremely low-rank factorization and dynamically updates the rank based on the primal infeasibility and suboptimality. This further speeds up the computation and saves the storage cost. Numerical experiments on Max Cut, Minimum Bisection, Cut Norm, and Lov\'{a}sz Theta problems with many recent memory-efficient scalable SDP solvers demonstrate its scalability up to problems with million-by-million decision variables and it is often the fastest solver to a moderate accuracy of $10^{-2}$.
- Abstract（参考訳）: 半定プログラム(SDP)とその解法は、機械学習とデータサイエンスに多くの応用がある強力なツールである。
スケーラブルなSDPソルバの設計は、正の半定値決定変数が$n \times n$高密度行列であるのに対して、入力はしばしば$n \times n$スパース行列であるにもかかわらず、困難である。
しかし、この解の情報は、バルビノクとパタキによって示されるようなフルランク密度行列と一致しないかもしれない。
20年前、Burer と Monteiro は完全行列の代わりに低ランクの分解を最適化する SDP ソルバ $\texttt{SDPLR}$ を開発した。
これにより、ストレージコストが大幅に削減され、多くの問題に対してうまく機能する。
元の解法である $\texttt{SDPLR}$ は、解の原始的実現可能性のみをトラックし、適度な精度の解を生成するための技法の柔軟性を制限する。
我々は、トレースバウンドSDP問題に対するサブ最適性を用いて、進捗をよりよく追跡し、早期終了を可能にする。
次に$\texttt{SDPLR+}$を開発し、極端に低ランクな因数分解で最適化を開始し、原始的不実現性と準最適性に基づいてランクを動的に更新する。
これにより計算が高速化され、ストレージコストが削減される。
近年のメモリ効率のよいスケーラブルなSDPソルバでは、最大カット、最小分割、カットノルム、Lov\'{a}sz Theta問題に関する数値実験が行われ、そのスケーラビリティが100万の判定変数の問題に匹敵することを示した。
関連論文リスト
- A practical, fast method for solving sum-of-squares problems for very large polynomials [10.645318208507213]
正方形最適化(SOS:Sum of squares)は、 as の正則性を強制しなければならない問題を解くための強力な手法である。
私たちのゴールは、現在より大きく、より複雑な問題に対処できるアプローチを考案することにあります。
論文 参考訳（メタデータ） (2024-10-21T12:47:42Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。
USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文 参考訳（メタデータ） (2023-12-19T02:27:22Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Lossy compression of matrices by black-box optimisation of mixed-integer
non-linear programming [1.1066593559733056]
エッジコンピューティングでは、データサイズを抑制することは、自律運転のような複雑なタスクを実行する機械学習モデルの課題である。
行列データの効率的な損失圧縮は、それを整数と実行列の積に分解することで実現されている。
本稿では,最近開発された整数変数に対するIsingソルバを用いたブラックボックス最適化アルゴリズムを利用して,この最適化を改善する。
論文 参考訳（メタデータ） (2022-04-22T08:58:36Z) - FKreg: A MATLAB toolbox for fast Multivariate Kernel Regression [5.090316990822874]
非一様FFT(NUFFT)を用いた高速多変量カーネル回帰のための新しいツールボックスを提案する。
NUFFTは$Oleft(N+Mlog M right)$複雑さと精度制御性を備えた$M$グリッドポイントのアルゴリズムを実装している。
帯域幅選択問題は、Fast Monte-Carloを用いて自由度を推定する。
論文 参考訳（メタデータ） (2022-04-16T04:52:44Z) - Neural Stochastic Dual Dynamic Programming [99.80617899593526]
我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。
$nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
論文 参考訳（メタデータ） (2021-12-01T22:55:23Z) - STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One
Semidefinite Relaxations [27.353023427198806]
我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。
POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。
我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2021-05-28T18:07:16Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。