論文の概要: Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers

• arxiv url: http://arxiv.org/abs/2510.13444v1
• Date: Wed, 15 Oct 2025 11:42:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-16 20:13:28.65161
• Title: Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers
• Title（参考訳）: 正方形のニューラルサム:変圧器を用いた多項式の非負性証明
• Authors: Nico Pelleriti, Christoph Spiegel, Shiwei Liu, David Martínez-Rubio, Max Zimmer, Sebastian Pokutta,
• Abstract要約: 二次体の非負性証明はよく知られたNPハード問題である。 非負性に対する十分条件は、200平方 (SOS) の性質である。 本稿では,SOS基準を認証する最初の学習用トランスフォーマー学習アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 33.99209000786153
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Certifying nonnegativity of polynomials is a well-known NP-hard problem with direct applications spanning non-convex optimization, control, robotics, and beyond. A sufficient condition for nonnegativity is the Sum of Squares (SOS) property, i.e., it can be written as a sum of squares of other polynomials. In practice, however, certifying the SOS criterion remains computationally expensive and often involves solving a Semidefinite Program (SDP), whose dimensionality grows quadratically in the size of the monomial basis of the SOS expression; hence, various methods to reduce the size of the monomial basis have been proposed. In this work, we introduce the first learning-augmented algorithm to certify the SOS criterion. To this end, we train a Transformer model that predicts an almost-minimal monomial basis for a given polynomial, thereby drastically reducing the size of the corresponding SDP. Our overall methodology comprises three key components: efficient training dataset generation of over 100 million SOS polynomials, design and training of the corresponding Transformer architecture, and a systematic fallback mechanism to ensure correct termination, which we analyze theoretically. We validate our approach on over 200 benchmark datasets, achieving speedups of over $100\times$ compared to state-of-the-art solvers and enabling the solution of instances where competing approaches fail. Our findings provide novel insights towards transforming the practical scalability of SOS programming.
• Abstract（参考訳）: 多項式の非負性性の証明は、非凸最適化、制御、ロボット工学などの直接的な応用においてよく知られたNPハード問題である。 非負性性の十分条件は、正方形の Sum of Squares (SOS) 性、すなわち他の多項式の平方の和として書くことができる。 しかし、実際には、SOS基準の証明には計算コストがかかり、SOS表現の単項基底の大きさで次元が2次的に増大する半確定プログラム(SDP)を解くことも多いため、単項基底のサイズを減らす様々な方法が提案されている。 本研究では,SOS基準を認証する最初の学習拡張アルゴリズムを提案する。 この目的のために、与えられた多項式に対して、ほぼ最小の単項基底を予測するトランスフォーマーモデルを訓練し、その結果、対応するSDPのサイズを大幅に削減する。 提案手法は,1億以上のSOS多項式の効率的なトレーニングデータセット生成,対応するTransformerアーキテクチャの設計とトレーニング,正しい終了を保証するための体系的なフォールバック機構の3つの重要な構成要素から構成され,理論的に解析する。 200以上のベンチマークデータセットにアプローチを検証し、最先端のソルバと比較して100ドル以上のスピードアップを実現し、競合するアプローチが失敗するインスタンスのソリューションを可能にしました。 本研究は,SOSプログラミングの実践的スケーラビリティを変革するための新たな洞察を提供する。

関連論文リスト

• Training Deep Learning Models with Norm-Constrained LMOs [56.00317694850397]
  線形最小化オラクル(LMO)を用いて問題の幾何学に適応する新しいアルゴリズム群を提案する。 我々は,Adamに頼らずに,我々のアルゴリズムであるScionを用いたナノGPTトレーニングの大幅な高速化を示す。
  論文  参考訳（メタデータ） (2025-02-11T13:10:34Z)
• 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)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Sparse resultant based minimal solvers in computer vision and their connection with the action matrix [17.31412310131552]
  いくつかのカメラ幾何問題に対して、我々の余剰手法は、最先端のGrobnerベースベースの解法よりも小さく、より安定な解法をもたらすことを示した。 コンピュータビジョンにおける最小限の問題に対して、一般的なベースベースの方法に代わる競争力のある代替手段を提供する。
  論文  参考訳（メタデータ） (2023-01-16T14:25:19Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Message Passing Neural PDE Solvers [60.77761603258397]
  我々は、バックプロップ最適化されたニューラル関数近似器で、グラフのアリーデザインのコンポーネントを置き換えるニューラルメッセージパッシング解決器を構築した。 本稿では, 有限差分, 有限体積, WENOスキームなどの古典的手法を表現的に含んでいることを示す。 本研究では, 異なる領域のトポロジ, 方程式パラメータ, 離散化などにおける高速, 安定, 高精度な性能を, 1次元, 2次元で検証する。
  論文  参考訳（メタデータ） (2022-02-07T17:47:46Z)
• Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias [27.06618125828978]
  本稿では,潜伏変数と選択バイアスの存在下での観測データからシステムの因果MAGを学習する問題を考察する。 本稿では,音と完全性を備えた計算効率のよい制約ベースの新しい手法を提案する。 提案手法と人工と実世界の両方の構造に関する技術の現状を比較した実験結果を提供する。
  論文  参考訳（メタデータ） (2021-10-22T19:49:59Z)
• A block-sparse Tensor Train Format for sample-efficient high-dimensional Polynomial Regression [0.0]
  低ランクテンソルは高次元問題の確立された枠組みである。 ブロックスパーシティの概念を含めることで、このフレームワークを拡張することを提案する。 これにより、既知のサンプル結果に合致するようにアンサッツ空間を適応させることができる。
  論文  参考訳（メタデータ） (2021-04-29T10:57:53Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)

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

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