論文の概要: Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
- arxiv url: http://arxiv.org/abs/2610.00422v1
- Date: Wed, 30 Sep 2026 15:23:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 01:19:23.652976
- Title: Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
- Title（参考訳）: ローカルにカバーする学習 - ハードインフォメーションホライゾン下でのグラフニューラルコンビネーション最適化
- Abstract要約: 我々は、各ノードがグローバルなソリューションの共有にコミットするハード情報水平線の下で最適化を研究する。
我々はこれを局所集合被覆として定式化し、重み付きマルチポイントリレー(MPR)選択でインスタンス化する。
- 参考スコア（独自算出の注目度）: 0.44333156307871585
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Neural combinatorial optimization typically assumes a centralized solver that reads the whole instance. We study the opposite: combinatorial optimization under a hard information horizon, where every node commits to its share of a global solution seeing only its $k$-hop neighborhood, and those commitments must compose into a globally feasible solution. We formalize this as local set cover and instantiate it on weighted multipoint relay (MPR) selection, the NP-hard 2-hop covering problem of the Optimized Link State Routing Protocol version 2 (OLSRv2) routing protocol (RFC~7181), whose horizon is imposed by the protocol, not chosen by the modeler. We prove two results. Any deterministic selector whose horizon is one hop short must either fail coverage or land a factor $Δ$ from optimal, and an $L$-layer graph neural network (GNN) read out at the deciding node is exactly an $L$-hop selector, so capacity cannot buy back radius. Conversely, at the horizon a \ac{GNN} of depth $O(Δ)$ reproduces the RFC~7181 covering greedy, and at width $O(c_{\max}Δ)$ its metric-aware weighted analogue, inheriting the $(1+\lnΔ_2)$-approximation in both cases. Empirically, a 3-layer \ac{GATv2} with a coverage-completing decoder, behavior-cloned from the CP-SAT optimum, reaches $\text{cost}/\text{opt}=1.030\pm0.001$ against greedy's $1.138$, closing $79.1\%$ of the gap at $100\%$ coverage. Restricting the same learner to one hop, on identical instances with the same decoder and demonstrations, collapses it to $1.344$, far worse than greedy. Two transfer checks target real-world networks. OLSRv2's unmodified selection code matches our cardinality greedy on $200/200$ unit-cost instances, and on $40{,}308$ instances of real battalion mobility the frozen model closes $48\%$ of the gap at full coverage. The information horizon, not the model capacity, is the most significant variable.
- Abstract（参考訳）: ニューラルネットワークの組合せ最適化は通常、インスタンス全体を読み取る集中型解決器を仮定する。
ハード情報地平線の下での組合せ最適化では、各ノードがグローバルなソリューションの共有にコミットし、その$k$ホップの近所だけを見て、それらのコミットメントはグローバルに実現可能なソリューションに構成されなければならない。
我々はこれを局所集合被覆として定式化し、それを重み付きマルチポイントリレー(MPR)選択、最適化リンク状態ルーティングプロトコルバージョン2(OLSRv2)ルーティングプロトコル(RFC~7181)のNPハード2ホップ被覆問題(モデラーが選択しないプロトコル)でインスタンス化する。
2つの結果が得られます。
水平線が1つのホップショートである決定論的セレクタは、カバーをフェールするか、最適値から$$$$を着陸させなければならないし、決定ノードで読み出される$L$層グラフニューラルネットワーク(GNN)は、正確に$L$ホップセレクタであるため、キャパシティは、半径を戻すことはできない。
逆に地平線では、深さ$O(Δ)$のaac{GNN} が RFC~7181 を写し、幅$O(c_{\max}Δ)$ その計量対応重み付きアナログを再現し、どちらの場合も$(1+\lnΔ_2)$-近似を継承する。
実証的に、CP-SAT最適化から振る舞いをクローズしたカバレッジ補完デコーダを持つ3層 \ac{GATv2} は、greedy の $1.138$ に対して $\text{cost}/\text{opt}=1.030\pm0.001$ に達する。
同じ学習者を1ホップに制限し、同じデコーダとデモを持つ同じインスタンスで、グリーディよりもはるかに悪い1344$に崩壊する。
2つの転送チェックは現実世界のネットワークをターゲットにします。
OLSRv2の未修正の選択コードは、200/200ドルの単価インスタンスで、40{,}308ドルの実際の大隊移動インスタンスでは、凍結されたモデルは、完全なカバレッジでギャップの4,8\%$を閉じる。
情報水平線は、モデルキャパシティではなく、最も重要な変数である。
関連論文リスト
- Matching Rates and Optimal Allocation for Federated Probe-Logit Distillation under Heterogeneous Bandwidth Budgets [12.805268849262243]
言語モデリングでは、$K$ノードはそれぞれ$n$サンプルを保持するが、データのプールや完全な精度勾配や重みの交換はできない。
本研究では,各ノードが1クエリあたり最大$B$ビットを公開プローブセットにアップロードできる場合に,$V$トークンの条件分布を推定できるミニマックスレートについて検討する。
論文 参考訳（メタデータ） (2026-05-28T09:08:39Z) - Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳（メタデータ） (2025-06-30T13:27:39Z) - Regret-Optimal Federated Transfer Learning for Kernel Regression with Applications in American Option Pricing [8.723136784230906]
本稿では、中央プランナーがデータセットにアクセス可能なフェデレーショントランスファー学習のための最適反復スキームを提案する。
我々の目標は、生成されたパラメータの累積偏差を$thetai(t)_t=0T$で最小化することである。
後悔と最適化のアルゴリズム内で対称性を活用することで, $mathcalO(Np2)$少なめの初等演算を伴って動作する,ほぼ後悔のいく$_optimalを開発する。
論文 参考訳（メタデータ） (2023-09-08T19:17:03Z) - Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳（メタデータ） (2023-06-28T17:43:19Z) - Federated Learning in the Presence of Adversarial Client Unavailability [16.201377650598516]
フェデレートラーニング(Federated Learning)は、生データを公開せずにコラボレーティブモデルを可能にする、分散機械学習フレームワークである。
多様なハードウェアソフトウェアに制限があるため、クライアントはサーバからの計算要求に対して常に利用できるとは限らない。
戦場のような厳しい環境では、敵は特定のクライアントを選択的に黙らせることができる。
論文 参考訳（メタデータ） (2023-05-31T15:57:07Z) - Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討した。
目標は、2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-03-03T02:40:26Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive
Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。
AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。
また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文 参考訳（メタデータ） (2021-02-09T07:46:34Z) - Accommodating Picky Customers: Regret Bound and Exploration Complexity
for Multi-Objective Reinforcement Learning [43.75491612671571]
目的と目的のバランスをとる多目的強化学習について、好みを用いて検討する。
我々はこの問題をマルコフ決定過程における叙述的学習問題として定式化する。
モデルに基づくアルゴリズムは、最小限の最小限のリセットを$widetildemathcalObigl(sqrtmind,Scdot H3 SA/epsilon2bigr)$とする。
論文 参考訳（メタデータ） (2020-11-25T21:45:04Z) - Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。
textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
論文 参考訳（メタデータ） (2020-10-12T17:51:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。