論文の概要: GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization

• arxiv url: http://arxiv.org/abs/2508.06899v1
• Date: Sat, 09 Aug 2025 09:12:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 21:23:28.60464
• Title: GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization
• Title（参考訳）: GDBAが再考:分散制約最適化のためのガイド付きローカル検索のパワーを開放
• Authors: Yanchen Deng, Xinrun Wang, Bo An,
• Abstract要約: 局所探索は分散制約最適化問題(DCOP)を解決するための不完全アルゴリズムの重要なクラスである 我々はDCOPのための新しいGLSフレームワークであるDistributed Guided Local Search (DGLS)を提案する。 各種標準ベンチマークにおける実験結果は、最先端のベースラインよりもDGLSが優れていることを示す。
• 参考スコア（独自算出の注目度）: 23.069147641568467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Local search is an important class of incomplete algorithms for solving Distributed Constraint Optimization Problems (DCOPs) but it often converges to poor local optima. While GDBA provides a comprehensive rule set to escape premature convergence, its empirical benefits remain marginal on general-valued problems. In this work, we systematically examine GDBA and identify three factors that potentially lead to its inferior performance, i.e., over-aggressive constraint violation conditions, unbounded penalty accumulation, and uncoordinated penalty updates. To address these issues, we propose Distributed Guided Local Search (DGLS), a novel GLS framework for DCOPs that incorporates an adaptive violation condition to selectively penalize constraints with high cost, a penalty evaporation mechanism to control the magnitude of penalization, and a synchronization scheme for coordinated penalty updates. We theoretically show that the penalty values are bounded, and agents play a potential game in our DGLS. Our extensive empirical results on various standard benchmarks demonstrate the great superiority of DGLS over state-of-the-art baselines. Particularly, compared to Damped Max-sum with high damping factors (e.g., 0.7 or 0.9), our DGLS achieves competitive performance on general-valued problems, and outperforms it by significant margins (\textbf{3.77\%--66.3\%}) on structured problems in terms of anytime results.
• Abstract（参考訳）: 局所探索は分散制約最適化問題(DCOP)を解決するための重要な不完全アルゴリズムのクラスであるが、しばしば局所最適化に収束する。 GDBAは、未熟な収束を避けるための包括的なルールを提供するが、その経験的利点は一般的な価値のある問題に及ばない。 本研究は,GDBAを体系的に検討し,過剰な攻撃的制約違反条件,非拘束的ペナルティ蓄積,非調整的ペナルティ更新といった,パフォーマンスの低下につながる可能性のある3つの要因を同定する。 これらの問題に対処するために、DCOPの新しいGLSフレームワークであるDistributed Guided Local Search (DGLS)を提案する。 理論的には、ペナルティ値が有界であることを示し、エージェントは我々のDGLSで潜在的なゲームをする。 各種標準ベンチマークの広範な実験結果は、最先端のベースラインよりもDGLSが優れていることを示す。 特に、高減衰率(例えば0.7または0.9)のDamped Max-sumと比較して、我々のDGLSは一般に評価された問題に対する競争性能を達成し、任意の時間結果の観点から構造化された問題に対してかなりの差(\textbf{3.77\%--66.3\%})で上回る。

関連論文リスト

• Nonconvex Optimization Framework for Group-Sparse Feedback Linear-Quadratic Optimal Control: Penalty Approach [3.585860184121598]
  本稿では,無限水平線形四元数(LQ)問題における設計グループパースフィードバックコントローラの統一的非最適化フレームワークを開発する。
  論文  参考訳（メタデータ） (2025-07-24T05:55:28Z)
• NDCG-Consistent Softmax Approximation with Accelerated Convergence [67.10365329542365]
  本稿では,ランキングの指標と直接一致した新たな損失定式化を提案する。 提案したRG損失を高効率な Alternating Least Squares (ALS) 最適化手法と統合する。 実世界のデータセットに対する実証的な評価は、我々のアプローチが同等または上位のパフォーマンスを達成することを示す。
  論文  参考訳（メタデータ） (2025-06-11T06:59:17Z)
• Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming [18.371947752008744]
  この結果から,不確実性等価性は分布の微妙な仮定の下で一様に近い最適後悔を達成できることが示唆された。 以上の結果から,CE は従来の信念とは対照的に,幅広い問題事例に対する退化の呪いを効果的に打ち負かしていると考えられる。 これらの手法は、より広範なオンライン意思決定コンテキストにおける潜在的な応用を見出すことができる。
  論文  参考訳（メタデータ） (2025-01-03T09:21:27Z)
• Stability and Generalization for Distributed SGDA [70.97400503482353]
  分散SGDAのための安定性に基づく一般化分析フレームワークを提案する。 我々は, 安定性の誤差, 一般化ギャップ, 人口リスクの包括的分析を行う。 理論的結果から,一般化ギャップと最適化誤差のトレードオフが明らかになった。
  論文  参考訳（メタデータ） (2024-11-14T11:16:32Z)
• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。 まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。 第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
  論文  参考訳（メタデータ） (2024-10-24T15:26:14Z)
• Conservative DDPG -- Pessimistic RL without Ensemble [48.61228614796803]
  DDPGは過大評価バイアス問題によって妨げられている。 このバイアスに対する伝統的な解決策は、アンサンブルに基づく方法を含んでいる。 本稿では,Q$-targetと行動クローン(BC)損失ペナルティを組み込んだ簡単なソリューションを提案する。
  論文  参考訳（メタデータ） (2024-03-08T23:59:38Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。 類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
  論文  参考訳（メタデータ） (2022-02-27T13:25:01Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  本稿では,実効的かつ理論的に証明可能なアルゴリズムであるオフラインRLに対するfalSe Correlation Reduction (SCORE)を提案する。 SCOREは、標準ベンチマーク(D4RL)において、様々なタスクにおいて3.1倍の高速化でSoTA性能を達成することを実証的に示す。
  論文  参考訳（メタデータ） (2021-10-24T15:34:03Z)

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

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