論文の概要: Learning to Approximate Uniform Facility Location via Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2602.13155v1
• Date: Fri, 13 Feb 2026 18:08:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-16 23:37:54.069157
• Title: Learning to Approximate Uniform Facility Location via Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークによる一様施設位置の近似学習
• Authors: Chendi Qian, Christopher Morris, Stefanie Jegelka, Christian Sohler,
• Abstract要約: 近似アルゴリズムの原理を組み込んだ完全微分可能なMPNNモデルを開発した。 提案手法は,ソリューションの品質の観点から,標準的な非学習近似アルゴリズムよりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 45.627700504265086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There has been a growing interest in using neural networks, especially message-passing neural networks (MPNNs), to solve hard combinatorial optimization problems heuristically. However, existing learning-based approaches for hard combinatorial optimization tasks often rely on supervised training data, reinforcement learning, or gradient estimators, leading to significant computational overhead, unstable training, or a lack of provable performance guarantees. In contrast, classical approximation algorithms offer such performance guarantees under worst-case inputs but are non-differentiable and unable to adaptively exploit structural regularities in natural input distributions. We address this dichotomy with the fundamental example of Uniform Facility Location (UniFL), a variant of the combinatorial facility location problem with applications in clustering, data summarization, logistics, and supply chain design. We develop a fully differentiable MPNN model that embeds approximation-algorithmic principles while avoiding the need for solver supervision or discrete relaxations. Our approach admits provable approximation and size generalization guarantees to much larger instances than seen during training. Empirically, we show that our approach outperforms standard non-learned approximation algorithms in terms of solution quality, closing the gap with computationally intensive integer linear programming approaches. Overall, this work provides a step toward bridging learning-based methods and approximation algorithms for discrete optimization.
• Abstract（参考訳）: ニューラルネットワーク、特にメッセージパッシングニューラルネットワーク(MPNN)の使用に対する関心が高まっている。 しかし、既存の学習に基づくハード組合せ最適化タスクのアプローチは、しばしば教師付きトレーニングデータ、強化学習、勾配推定器に依存し、計算オーバーヘッド、不安定なトレーニング、あるいは証明可能な性能保証の欠如につながる。 対照的に、古典近似アルゴリズムは最悪の場合の入力ではそのような性能保証を提供するが、微分不可能であり、自然な入力分布における構造的規則性を適応的に利用できない。 この二分法は、クラスタリング、データ要約、ロジスティクス、サプライチェーン設計における組合せ的施設配置問題の変種であるUniFL(UniFL)の基本的な例に対処する。 近似アルゴリズムの原理を組み込んだ完全微分可能なMPNNモデルを開発した。 提案手法では,評価可能な近似とサイズ一般化が,トレーニング中に見られるよりもはるかに大きなインスタンスを保証している。 実験により,本手法は,計算集約型整数線形プログラミング手法とのギャップを埋めることにより,解の質の観点から標準的な非学習近似アルゴリズムよりも優れていることを示す。 全体として、この研究は、離散最適化のための学習ベースの手法と近似アルゴリズムをブリッジするステップを提供する。

関連論文リスト

• Learning based convex approximation for constrained parametric optimization [11.379408842026981]
  本稿では、制約付き最適化問題を解決するために、入力ニューラルネットワーク(ICNN)に基づく自己教師付き学習フレームワークを提案する。 厳密な収束解析を行い、このフレームワークが元の問題のKKT近似点に収束することを示す。 提案手法は精度,実現可能性,計算効率の両立を実現している。
  論文  参考訳（メタデータ） (2025-05-07T00:33:14Z)
• Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization [15.102119312523696]
  組合せ最適化(CO)の問題は、医学、物流、製造など幅広い領域で発生する。 本研究では,CO の非学習近似アルゴリズムを学習ベースで拡張する手法を提案する。 本手法は,近似アルゴリズムをブラックボックスとして扱う新しい勾配推定法を用いて,自己教師付き方式でエンドツーエンドに学習する。
  論文  参考訳（メタデータ） (2025-02-26T18:23:07Z)
• Optimization Proxies using Limited Labeled Data and Training Time -- A Semi-Supervised Bayesian Neural Network Approach [3.26805553822503]
  制約付き最適化問題は、在庫管理や電力網など、さまざまなエンジニアリングシステムで発生する。 標準ディープニューラルネットワーク(DNN)ベースの機械学習プロキシは、ラベル付きデータが不足し、トレーニング時間が制限された実用的な環境では有効ではない。
  論文  参考訳（メタデータ） (2024-10-04T02:10:20Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。 本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-04T01:47:37Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  本稿では,UnRolled Federated Learning (SURF)を導入する。 提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
  論文  参考訳（メタデータ） (2023-05-24T17:26:22Z)
• Federated Learning with a Sampling Algorithm under Isoperimetry [9.990687944474738]
  フェデレーション学習は、機械学習アルゴリズムのトレーニングを複数のデバイスに効率的に分散するために、一連のテクニックを使用する。 本稿では,Langevinvin のサンプル Aafteri の通信効率のよい変種を提案する。
  論文  参考訳（メタデータ） (2022-06-02T08:19:03Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。 非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。 詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
  論文  参考訳（メタデータ） (2021-10-04T03:17:41Z)

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

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