論文の概要: Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe

• arxiv url: http://arxiv.org/abs/2609.25728v1
• Date: Tue, 22 Sep 2026 05:59:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-23 18:04:04.236881
• Title: Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe
• Title（参考訳）: Frank-Wolfeによる制約付き自己監督型組合せ最適化
• Abstract要約: 本稿では,ニューラルネットワークが任意の連続ベクトルを予測できる一般的な枠組みを提案する。 これらの予測は、フランク=ウルフ法に基づく幾何分解アルゴリズムと近似カラテオドイ結果を用いて、実現可能な解の凸結合によって近似される。 この分解は、離散目的物の期待値として定義される、a.e.微分可能な自己教師付き損失を誘導する。
• 参考スコア（独自算出の注目度）: 13.727490124905685
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Self-supervised learning for combinatorial optimization has emerged as a promising paradigm for solving discrete optimization problems with neural networks, but a central challenge remains: handling hard combinatorial constraints within continuous, gradient-based training. Continuously extending combinatorial objectives to convex domains is a powerful technique, yet existing approaches often require projection steps that constrain neural network outputs to lie inside the feasible polytope and rely on ad-hoc and problem-specific constructions. We propose a general framework in which the neural network is allowed to predict arbitrary continuous vectors that could potentially lie outside of the feasible polytope. These predictions are then approximated by sparse convex combinations of feasible solutions using a geometric decomposition algorithm based on Frank--Wolfe methods and approximate Caratheodory results. This decomposition induces an a.e.-differentiable, self-supervised loss defined as the expected value of the discrete objective. The same procedure provides an automatic rounding guarantee at inference time. We demonstrate strong empirical performance across multiple combinatorial problems, including the Quadratic Assignment Problem, Maximum Coverage, and the Traveling Salesperson Problem.
• Abstract（参考訳）: 組合せ最適化のための自己教師付き学習は、ニューラルネットワークで離散最適化問題を解決するための有望なパラダイムとして登場したが、中心的な課題は、連続的な勾配ベースのトレーニングにおけるハード組合せ制約の処理である。 コンベックスドメインへの組合せ目的の連続的な拡張は強力なテクニックであるが、既存のアプローチでは、ニューラルネットワークの出力が実現可能なポリトープ内に配置され、アドホックや問題固有の構造に依存するように制約するプロジェクションステップを必要とすることが多い。 本稿では,ニューラルネットワークが任意の連続ベクトルを予測できる一般的な枠組みを提案する。 これらの予測は、フランク=ウルフ法に基づく幾何分解アルゴリズムと近似カラテオドイ結果を用いて、実現可能な解のスパース凸結合によって近似される。 この分解は、離散目的物の期待値として定義される、a.e.微分可能な自己教師付き損失を誘導する。 同じ手順は、推論時に自動ラウンド保証を提供する。 擬似アサインメント問題,最大カバレッジ問題,旅行セールスパーソン問題など,複数の組合せ問題にまたがる強烈な経験的パフォーマンスを示す。

関連論文リスト

• Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization [57.66069228055418]
  本稿では,計算制約付き多段階合成最適化アルゴリズムについて述べる。 目的関数はスムーズなネスト関数の合成であり、決定は凸かつ閉である。 ステージワイズ設計を用いることで、フランク=ウルフギャップの同じ複雑さを保ったパラメータフリーな変種を導出する。
  論文  参考訳（メタデータ） (2026-09-14T14:53:18Z)
• Geometric Algorithms for Neural Combinatorial Optimization with Constraints [46.17172939797694]
  Self-Supervised Learning for Combinatorial Optimization (CO)は、ニューラルネットワークを使って問題を解決するための新しいパラダイムである。 ニューラルネットワークによる離散的な制約付き最適化問題の解決を可能にする、エンドツーエンドの微分可能なフレームワークを設計する。
  論文  参考訳（メタデータ） (2025-10-28T03:49:01Z)
• An Enhanced Zeroth-Order Stochastic Frank-Wolfe Framework for Constrained Finite-Sum Optimization [15.652261277429968]
  本稿では,制約付き有限サム最適化問題に対処するため,ゼロ階凸計算を改良したFrank-Wolfeを提案する。 本手法では,ゼロ次オラクルによる近似を効果的に低減する新しい二重分散低減フレームワークを提案する。
  論文  参考訳（メタデータ） (2025-01-13T10:53:19Z)
• The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models [75.33431791218302]
  ディープニューラルネットワーク(DNN)モデルは、プログラミング目的に使用される。 本稿では,凸型神経回復モデルについて検討する。 定常的非次元目的物はすべて,グローバルサブサンプリング型凸解法プログラムとして特徴付けられることを示す。 また, 静止非次元目的物はすべて, グローバルサブサンプリング型凸解法プログラムとして特徴付けられることを示す。
  論文  参考訳（メタデータ） (2023-12-19T23:04:56Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Convex mixed-integer optimization with Frank-Wolfe methods [20.37026309402396]
  混合整数非線形最適化は理論的および計算的課題を示す。 本稿では,凸ノード緩和を用いた分岐結合アルゴリズムに基づいて,これらの問題の解法を提案する。
  論文  参考訳（メタデータ） (2022-08-23T14:46:54Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)

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

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