論文の概要: On the Expressive Power of GNNs to Solve Linear SDPs

• arxiv url: http://arxiv.org/abs/2604.27786v2
• Date: Mon, 04 May 2026 09:48:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-05 20:33:49.430444
• Title: On the Expressive Power of GNNs to Solve Linear SDPs
• Title（参考訳）: 線形SDPを解くGNNの表現力について
• Authors: Chendi Qian, Christopher Morris,
• Abstract要約: 半有限プログラム(SDP)は凸最適化のための強力なフレームワークである。 本研究では, 最適SDP解の回復に有効な表現力について検討する。 我々は、SDPのキー構造を捉える表現力のあるアーキテクチャを特定し、特に標準一階解決器の更新をエミュレートする。
• 参考スコア（独自算出の注目度）: 11.574125752787156
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Semidefinite programs (SDPs) are a powerful framework for convex optimization and for constructing strong relaxations of hard combinatorial problems. However, solving large SDPs can be computationally expensive, motivating the use of machine learning models as fast computational surrogates. Graph neural networks (GNNs) are a natural candidate in this setting due to their sparsity-awareness and ability to model variable-constraint interactions. In this work, we study what expressive power is sufficient to recover optimal SDP solutions. We first prove negative results showing that standard GNN architectures fail on recovering linear SDP solutions. We then identify a more expressive architecture that captures the key structure of SDPs and can, in particular, emulate the updates of a standard first-order solver. Empirically, on both synthetic and \textsc{SdpLib} benchmarks of various classes of SDPs, this more expressive architecture achieves consistently lower prediction error and objective gap than theoretically weaker baselines. Finally, using the learned high-quality predictions to warm-start the first-order solver yields practical speedups of up to 80%.
• Abstract（参考訳）: 半定値プログラム(SDP)は凸最適化のための強力なフレームワークであり、ハード組合せ問題の強い緩和を構築するためのものである。 しかし、大規模SDPの解決には計算コストがかかり、機械学習モデルを高速な計算サロゲートとして活用する動機となっている。 グラフニューラルネットワーク(GNN)は、その疎さと可変制約相互作用をモデル化する能力のために、この設定において自然な候補である。 本研究では, 最適SDP解の回復に有効な表現力について検討する。 まず,標準GNNアーキテクチャが線形SDP解の回復に失敗することを示す。 次に、より表現力のあるアーキテクチャを特定し、SDPのキー構造をキャプチャし、特に標準一階解決器の更新をエミュレートする。 実験的に、SDP の様々なクラスの合成および \textsc{SdpLib} ベンチマークにおいて、このより表現力のあるアーキテクチャは理論上より弱いベースラインよりも一貫して低い予測誤差と客観的ギャップを達成する。 最後に、学習した高品質な予測を用いて1次解法を暖房し、実効速度を最大80%向上させる。

関連論文リスト

• Warm-starting active-set solvers using graph neural networks [4.309217525488745]
  本稿では,グラフニューラルネットワーク(GNN)を用いた二元能動集合解法DAQPの能動集合の予測手法を提案する。 問題のサイズは様々であり、GNNはコールドスタートに比べてソルバイテレーションの数を一貫して減らしている。 様々な問題サイズを訓練したGNNは、柔軟性とスケーラビリティを実証し、目に見えない次元に効果的に一般化する。
  論文  参考訳（メタデータ） (2025-11-17T09:22:45Z)
• A Distributed Training Architecture For Combinatorial Optimization [0.0]
  最適化のための分散グラフニューラルネットワーク(GNN)に基づくトレーニングフレームワークを提案する。 実大規模ソーシャルネットワークデータセットと合成された高複雑性グラフの両方で実験を行った。 我々のフレームワークは、ソリューションの品質と計算効率の両方において最先端のアプローチより優れています。
  論文  参考訳（メタデータ） (2025-11-12T12:22:10Z)
• The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models [75.33431791218302]
  ディープニューラルネットワーク(DNN)モデルは、プログラミング目的に使用される。 本稿では,凸型神経回復モデルについて検討する。 定常的非次元目的物はすべて,グローバルサブサンプリング型凸解法プログラムとして特徴付けられることを示す。 また, 静止非次元目的物はすべて, グローバルサブサンプリング型凸解法プログラムとして特徴付けられることを示す。
  論文  参考訳（メタデータ） (2023-12-19T23:04:56Z)
• Reducing the Need for Backpropagation and Discovering Better Optima With Explicit Optimizations of Neural Networks [4.807347156077897]
  本稿では,ニューラルネットワークの最適化のための計算効率のよい代替案を提案する。 我々は、単純なフィードフォワード言語モデルに対する明確な解決策を導出する。 実験では,明示的な解がほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2023-11-13T17:38:07Z)
• Efficient and Flexible Neural Network Training through Layer-wise Feedback Propagation [49.44309457870649]
  レイヤワイドフィードバックフィードバック(LFP)は、ニューラルネットワークのような予測器のための新しいトレーニング原則である。 LFPはそれぞれの貢献に基づいて個々のニューロンに報酬を分解する。 提案手法は,ネットワークの有用な部分と有害な部分の弱体化を両立させる手法である。
  論文  参考訳（メタデータ） (2023-08-23T10:48:28Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• 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)
• GradInit: Learning to Initialize Neural Networks for Stable and Efficient Training [59.160154997555956]
  ニューラルネットワークを初期化するための自動化およびアーキテクチャ手法であるgradinitを提案する。 各ネットワーク層の分散は、SGDまたはAdamの単一ステップが最小の損失値をもたらすように調整される。 また、学習率のウォームアップを伴わずに、オリジナルのPost-LN Transformerを機械翻訳用にトレーニングすることもできる。
  論文  参考訳（メタデータ） (2021-02-16T11:45:35Z)
• Predictive Coding Approximates Backprop along Arbitrary Computation Graphs [68.8204255655161]
  我々は、コア機械学習アーキテクチャを予測的符号化に翻訳する戦略を開発する。 私たちのモデルは、挑戦的な機械学習ベンチマークのバックプロップと同等に機能します。 本手法は,ニューラルネットワークに標準機械学習アルゴリズムを直接実装できる可能性を高める。
  論文  参考訳（メタデータ） (2020-06-07T15:35:47Z)

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

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