論文の概要: Neural Certificate Pricing for Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2607.01185v1
• Date: Wed, 01 Jul 2026 17:17:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-02 19:56:08.002767
• Title: Neural Certificate Pricing for Combinatorial Optimization Problems
• Title（参考訳）: 組合せ最適化問題に対するニューラルネットワーク証明書の価格設定
• Abstract要約: 我々は、教師なし学習フレームワークの下で、この非対称性を利用するニューラルネットワーク認証価格(NCP)を導入する。 ニューラルネットワークは証明書レベルの二重価格を予測するように訓練され、構造化されたリカバリ層は誘導された原始的限界を構成する。 NCPは、最先端の神経ベースラインを大きなマージンで上回るか、ほんの少しの時間でそれらと一致し、より強力な分布外一般化を示す。
• 参考スコア（独自算出の注目度）: 8.245195486032502
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization (CO) problems are difficult because certifiable discrete structure induces exponential search. One needs to search over the set exponentially many candidates to certify optimality, however, the structural feasibility of a path, packing, or cover can be verified in polynomial time once supplied. In this study, we introduce Neural Certificate Pricing (NCP) that exploits this asymmetry under an unsupervised learning framework. A neural network is trained to predict certificate-level dual prices, while a structured recovery layer constructs the induced primal marginal. NCP can be viewed as amortized separation: instead of enumerating violated inequalities, it learns the residual prices through which their aggregate effect enters recovery. When the certificate-consistency condition holds, the recovered marginal is globally feasible, and a local theory shows that first-order errors in the predicted price induce only second-order loss in objective value. Across three classes of CO problems, NCP either outperforms state-of-the-art neural baselines by large margins or matches them at a fraction of the computation time, and shows stronger out-of-distribution generalization.
• Abstract（参考訳）: 証明可能な離散構造が指数探索を引き起こすため、組合せ最適化(CO)問題は困難である。 最適性を証明するために指数関数的に多くの候補を探索する必要があるが、経路、梱包、カバーの構造的実現性は一度供給された多項式時間で検証できる。 本研究では、教師なし学習フレームワークの下で、この非対称性を利用するニューラルネットワーク認証価格(NCP)を導入する。 ニューラルネットワークは証明書レベルの二重価格を予測するように訓練され、構造化されたリカバリ層は誘導された原始的限界を構成する。 NCPは不等式を列挙する代わりに、その集合効果が回復する残高を学習する。 証明整合条件が成立すると、回収された限界は世界規模で実現可能となり、局所理論では、予測された価格の1次誤差は目的値の2次損失のみを誘導する。 CO問題の3つのクラスにまたがって、NCPは最先端のニューラルベースラインを大きなマージンで上回るか、計算時間のごく一部で一致させるか、より強いアウト・オブ・ディストリビューションの一般化を示す。

関連論文リスト

• Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting [21.347076448562863]
  コードコンピューティングは、分散コンピューティングシステムにおけるストラグリングワーカーの影響を軽減するための強力なパラダイムとして登場した。 General Coded Computing (GCC) は、コード化された計算をエンドツーエンドの平均二乗誤差損失によって定式化する。 2つの相補的なストラグラー体制の下で理論的性能を確立する。
  論文  参考訳（メタデータ） (2026-08-28T22:18:22Z)
• Exact Certification of (Graph) Neural Networks Against Label Poisoning [50.87615167799367]
  グラフニューラルネットワーク(GNN)におけるラベルフリップの正確な認証手法を提案する。 本稿では,ノード分類タスクにおける広範囲なGNNアーキテクチャの認証に本手法を適用した。 私たちの研究は、ニューラルネットワークによって引き起こされた毒殺攻撃に対する最初の正確な認証を提示します。
  論文  参考訳（メタデータ） (2024-11-30T17:05:12Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Towards Demystifying the Generalization Behaviors When Neural Collapse Emerges [132.62934175555145]
  Neural Collapse(NC)は、トレーニング末期(TPT)におけるディープニューラルネットワークのよく知られた現象である 本稿では,列車の精度が100%に達した後も,継続訓練がテストセットの精度向上に繋がる理由を理論的に説明する。 我々はこの新たに発見された性質を「非保守的一般化」と呼ぶ。
  論文  参考訳（メタデータ） (2023-10-12T14:29:02Z)
• On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networks [13.2844023993979]
  フェデレートラーニング(FL)は、ローカルデータを共有せずに複数のクライアントから機械学習モデルを協調的に作成するための分散パラダイムである。 本稿では,FedAvgが世界規模で世界規模で収束していることを示す。
  論文  参考訳（メタデータ） (2023-10-09T07:56:56Z)
• On Excess Risk Convergence Rates of Neural Network Classifiers [8.329456268842227]
  本稿では,ニューラルネットワークを用いた2値分類におけるプラグイン分類器の性能を,その過大なリスクによって測定した。 ニューラルネットワークの推定と近似特性を分析し,次元自由で均一な収束率を求める。
  論文  参考訳（メタデータ） (2023-09-26T17:14:10Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  データ分布が適切に分離された場合、DNNは分類のためのベイズ最適テスト誤差を達成できることを示す。 よりスムーズな関数との補間により、より一般化できることを示す。
  論文  参考訳（メタデータ） (2023-05-30T19:37:44Z)
• Controlling the Complexity and Lipschitz Constant improves polynomial nets [55.121200972539114]
  多項式ネットの結合CP分解(CCP)モデルとNested Coupled CP分解(NCP)モデルに対する新しい複雑性境界を導出する。 本研究では、6つのデータセットで実験的に評価し、モデルが逆摂動に対して頑健であるとともに精度も向上することを示す。
  論文  参考訳（メタデータ） (2022-02-10T14:54:29Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network [20.132432350255087]
  タンジェント降下(GD)によってトレーニングされた過度にパラメータ化されたニューラルネットワークは、任意のトレーニングデータを確実に過度に適合させることができる。 本稿では、過度にパラメータ化されたニューラルネットワークが、ランダムノイズの存在下での真のターゲット関数をいかに回復するかを考察する。
  論文  参考訳（メタデータ） (2020-07-06T01:02:23Z)
• A Revision of Neural Tangent Kernel-based Approaches for Neural Networks [34.75076385561115]
  ニューラルネットワークカーネルを使用して、ネットワークが任意の有限トレーニングサンプルに完全に適合できることを示す。 単純で解析的なカーネル関数は、完全に訓練されたネットワークと同等のものとして導出された。 より厳密な分析により,スケーリングの問題が解決され,元のNTKに基づく結果の検証が可能となった。
  論文  参考訳（メタデータ） (2020-07-02T05:07:55Z)

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

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