論文の概要: Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching

• arxiv url: http://arxiv.org/abs/2312.11801v1
• Date: Tue, 19 Dec 2023 02:27:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-20 17:26:46.831285
• Title: Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching
• Title（参考訳）: スペクトルバンドルとスケッチによる高速でスケーラブルで温かい半定型プログラミング
• Authors: Rico Angell and Andrew McCallum
• Abstract要約: 我々は、大規模なSDPを解決するための、証明可能な正確で高速でスケーラブルなアルゴリズムであるSpecBMを提案する。 本アルゴリズムは,収束速度を維持しつつ,従来の作業のスケーラビリティを劇的に向上させる。 提案手法は16コアで128GBのRAMを持たない1台のマシン上で1013以上の決定変数を持つSDPを解く。
• 参考スコア（独自算出の注目度）: 53.91395791840179
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While semidefinite programming (SDP) has traditionally been limited to moderate-sized problems, recent algorithms augmented with matrix sketching techniques have enabled solving larger SDPs. However, these methods achieve scalability at the cost of an increase in the number of necessary iterations, resulting in slower convergence as the problem size grows. Furthermore, they require iteration-dependent parameter schedules that prohibit effective utilization of warm-start initializations important in practical applications with incrementally-arriving data or mixed-integer programming. We present SpecBM, a provably correct, fast and scalable algorithm for solving massive SDPs that can leverage a warm-start initialization to further accelerate convergence. Our proposed algorithm is a spectral bundle method for solving general SDPs containing both equality and inequality constraints. Moveover, when augmented with an optional matrix sketching technique, our algorithm achieves the dramatically improved scalability of previous work while sustaining convergence speed. We empirically demonstrate the effectiveness of our method, both with and without warm-starting, across multiple applications with large instances. For example, on a problem with 600 million decision variables, SpecBM achieved a solution of standard accuracy in less than 7 minutes, where the previous state-of-the-art scalable SDP solver requires more than 16 hours. Our method solves an SDP with more than 10^13 decision variables on a single machine with 16 cores and no more than 128GB RAM; the previous state-of-the-art method had not achieved an accurate solution after 72 hours on the same instance. We make our implementation in pure JAX publicly available.
• Abstract（参考訳）: 半定値プログラミング(SDP)は伝統的に中程度の問題に限られてきたが、近年、行列スケッチ技術で拡張されたアルゴリズムにより、より大きなSDPを解けるようになった。 しかし、これらの手法は必要なイテレーション数の増加を犠牲にしてスケーラビリティを実現し、問題のサイズが大きくなると収束が遅くなる。 さらに、インクリメンタルアレーブデータや混合インテガープログラミングで実用上重要なウォームスタート初期化の有効利用を禁止するイテレーション依存パラメータスケジュールが必要となる。 提案するSpecBMは,暖化開始初期化を利用して収束をさらに加速する,大規模SDPを解くための,証明可能な正確かつ高速でスケーラブルなアルゴリズムである。 提案アルゴリズムは,等式制約と不等式制約の両方を含む一般SDPを解くためのスペクトル束法である。 さらに,任意の行列スケッチ手法で拡張すると,コンバージェンス速度を維持しつつ,従来の作業のスケーラビリティを劇的に向上させる。 大規模インスタンスを持つ複数のアプリケーションに対して,本手法の有効性を実証的に実証した。 例えば、6億の意思決定変数を持つ問題において、SpecBMは7分以内で標準精度のソリューションを達成し、以前の最先端のスケーラブルなSDPソルバは16時間以上を要する。 提案手法は,16コアで128GBのRAMを持つ1台のマシン上で10^13以上の決定変数を持つSDPを解く。 私たちは純粋なJAXで実装を公開しています。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Accelerated nonlinear primal-dual hybrid gradient algorithms with applications to machine learning [0.0]
  原始双対ハイブリッド勾配(PDHG)は、サドル点構造を持つ凸最適化問題をより小さなサブプロブレムに分割する一階法である。 PDHGは、手前の問題に対して微調整されたステップサイズパラメータを必要とする。 我々は,機械学習に関連する幅広い最適化問題に対して,PDHGアルゴリズムの高速化された非線形変種を導入する。
  論文  参考訳（メタデータ） (2021-09-24T22:37:10Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs [12.7944665592057]
  本稿では,制約付き半有限計画法(SDP)を高速化した非自明なプログラムを用いて大規模に解くための,新しい,実用的で証明可能なアプローチを提案する。
  論文  参考訳（メタデータ） (2021-06-16T13:35:40Z)
• 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)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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