論文の概要: Preference-Based Gradient Estimation for ML-Based Approximate Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2502.19377v1
- Date: Wed, 26 Feb 2025 18:23:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-27 14:58:50.986861
- Title: Preference-Based Gradient Estimation for ML-Based Approximate Combinatorial Optimization
- Title（参考訳）: MLに基づく近似組合せ最適化のための優先度に基づく勾配推定
- Authors: Arman Mielke, Uwe Bauknecht, Thilo Strauss, Mathias Niepert,
- Abstract要約: 近似アルゴリズムをパラメータ化し、グラフニューラルネットワーク(GNN)をトレーニングし、最適な解につながるパラメータ値を予測する。
我々のパイプラインは、勾配推定を用いて自己教師付きでエンドツーエンドに訓練され、近似アルゴリズムをブラックボックスとして扱う。
我々は,旅行セールスマン問題と最小kカット問題という,よく知られた2つの最適化問題に対するアプローチを検証する。
- 参考スコア（独自算出の注目度）: 15.102119312523696
- License:
- Abstract: Combinatorial optimization (CO) problems arise in a wide range of fields from medicine to logistics and manufacturing. While exact solutions are often not necessary, many applications require finding high-quality solutions quickly. For this purpose, we propose a data-driven approach to improve existing non-learned approximation algorithms for CO. We parameterize the approximation algorithm and train a graph neural network (GNN) to predict parameter values that lead to the best possible solutions. Our pipeline is trained end-to-end in a self-supervised fashion using gradient estimation, treating the approximation algorithm as a black box. We propose a novel gradient estimation scheme for this purpose, which we call preference-based gradient estimation. Our approach combines the benefits of the neural network and the non-learned approximation algorithm: The GNN leverages the information from the dataset to allow the approximation algorithm to find better solutions, while the approximation algorithm guarantees that the solution is feasible. We validate our approach on two well-known combinatorial optimization problems, the travelling salesman problem and the minimum k-cut problem, and show that our method is competitive with state of the art learned CO solvers.
- Abstract（参考訳）: 組合せ最適化(CO)の問題は、医療から物流、製造まで幅広い分野に発生する。
正確なソリューションは必要ないことが多いが、多くのアプリケーションは高品質なソリューションを素早く見つける必要がある。
そこで本稿では,CO に対する既存の非学習近似アルゴリズムを改善するためのデータ駆動型手法を提案する。
近似アルゴリズムをパラメータ化し、グラフニューラルネットワーク(GNN)をトレーニングし、最適な解につながるパラメータ値を予測する。
我々のパイプラインは、勾配推定を用いて自己教師付きでエンドツーエンドに訓練され、近似アルゴリズムをブラックボックスとして扱う。
そこで我々は,この目的のための新しい勾配推定手法を提案し,これを選好に基づく勾配推定と呼ぶ。
我々のアプローチはニューラルネットワークと非学習近似アルゴリズムの利点を組み合わせる: GNNはデータセットからの情報を活用して近似アルゴリズムがより良い解を見つけるのを可能にし、近似アルゴリズムは解が実現可能であることを保証します。
我々は,2つのよく知られた組合せ最適化問題,旅行セールスマン問題と最小kカット問題に対するアプローチを検証し,この手法が最先端のCOソルバと競合することを示す。
関連論文リスト
- Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。
我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。
この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文 参考訳（メタデータ） (2024-11-25T17:31:34Z) - Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-04-16T20:01:10Z) - 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) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - AskewSGD : An Annealed interval-constrained Optimisation method to train
Quantized Neural Networks [12.229154524476405]
我々は、深層ニューラルネットワーク(DNN)を量子化重みでトレーニングするための新しいアルゴリズム、Annealed Skewed SGD - AskewSGDを開発した。
アクティブなセットと実行可能な方向を持つアルゴリズムとは異なり、AskewSGDは実行可能な全セットの下でのプロジェクションや最適化を避けている。
実験結果から,AskewSGDアルゴリズムは古典的ベンチマークの手法と同等以上の性能を示した。
論文 参考訳（メタデータ） (2022-11-07T18:13:44Z) - The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。
我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
論文 参考訳（メタデータ） (2022-09-27T09:27:29Z) - Consistent Approximations in Composite Optimization [0.0]
我々は最適化問題の一貫した近似のためのフレームワークを開発する。
このフレームワークは幅広い最適化のために開発されている。
プログラム解析法は、拡張非線形プログラミングソリューションを例証する。
論文 参考訳（メタデータ） (2022-01-13T23:57:08Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-04T00:26:56Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:09:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。