GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization

• URL: http://arxiv.org/abs/2508.06899v1
• Date: Sat, 09 Aug 2025 09:12:06 GMT
• Title: GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization
• Authors: Yanchen Deng, Xinrun Wang, Bo An,
• Abstract summary: Local search is an important class of incomplete algorithms for solving Distributed Constraint Optimization Problems (DCOPs)<n>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.<n>Our empirical results on various standard benchmarks demonstrate the great superiority of DGLS over state-of-the-art baselines.
• Score: 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.

Related papers

• WS-GRPO: Weakly-Supervised Group-Relative Policy Optimization for Rollout-Efficient Reasoning [67.45237332694025]
  Group Relative Policy Optimization is effective for training language models on complex reasoning.<n>We propose Weakly Supervised GRPO, which improves rollout efficiency by converting terminal rewards into correctness-aware guidance.
  arXiv  Detail & Related papers  (2026-02-19T02:43:35Z)
• Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding [58.92526489742584]
  We propose provably lossless.<n> verification method that significantly boosts the expected number of accepted tokens.<n>We show that HSD yields consistent improvements in acceptance rates across diverse model families and benchmarks.
  arXiv  Detail & Related papers  (2026-01-09T11:10:29Z)
• Multi-Armed Bandits with Minimum Aggregated Revenue Constraints [27.081997104464012]
  We design and analyze algorithms that either optimistically prioritize performance or pessimistically enforce constraint satisfaction.<n>We establish a lower bound demonstrating that the dependence on the time horizon in our results is optimal in general.
  arXiv  Detail & Related papers  (2025-10-14T13:47:34Z)
• FedLoDrop: Federated LoRA with Dropout for Generalized LLM Fine-tuning [65.26899091946417]
  Fine-tuning large language models (LLMs) is crucial for adapting general-purpose models to specific tasks.<n>This paper proposes Federated LoRA with Dropout (FedLoDrop), a new framework that applies dropout to the rows and columns of the trainable matrix in Federated LoRA.
  arXiv  Detail & Related papers  (2025-10-14T02:40:45Z)
• Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization [96.97196425604893]
  Existing theory suggests that for linear regression problems categorized by capacity and source conditions, gradient descent (GD) is always minimax optimal.<n>This work provides instance-wise comparisons of the finite-sample risks for these algorithms on any well-specified linear regression problem.
  arXiv  Detail & Related papers  (2025-09-21T22:02:38Z)
• Generalization and Optimization of SGD with Lookahead [20.363815126393884]
  Lookahead enhances deep learning models by employing a dual-weight update mechanism.<n>Most theoretical studies focus on its convergence on training data, leaving its generalization capabilities less understood.
  arXiv  Detail & Related papers  (2025-09-19T09:02:09Z)
• Nonconvex Optimization Framework for Group-Sparse Feedback Linear-Quadratic Optimal Control: Penalty Approach [3.585860184121598]
  This paper develops a unified non optimization framework for the design groupsparse feedback controllers in infinite-horizon linearquadratic (LQ) problems.
  arXiv  Detail & Related papers  (2025-07-24T05:55:28Z)
• NDCG-Consistent Softmax Approximation with Accelerated Convergence [67.10365329542365]
  We propose novel loss formulations that align directly with ranking metrics.<n>We integrate the proposed RG losses with the highly efficient Alternating Least Squares (ALS) optimization method.<n> Empirical evaluations on real-world datasets demonstrate that our approach achieves comparable or superior ranking performance.
  arXiv  Detail & Related papers  (2025-06-11T06:59:17Z)
• Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming [18.371947752008744]
  We show that Certainty Equivalent achieves uniformly near-optimal regret under mild assumptions on the underlying distribution.<n>Our result implies that, contrary to prior belief, CE effectively beats the curse of degeneracy for a wide range of problem instances.<n>These techniques may find potential applications in broader online decision-making contexts.
  arXiv  Detail & Related papers  (2025-01-03T09:21:27Z)
• Stability and Generalization for Distributed SGDA [70.97400503482353]
  We propose the stability-based generalization analytical framework for Distributed-SGDA. We conduct a comprehensive analysis of stability error, generalization gap, and population risk across different metrics. Our theoretical results reveal the trade-off between the generalization gap and optimization error.
  arXiv  Detail & Related papers  (2024-11-14T11:16:32Z)
• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  We study problems as pure exploration in multi-armed bandits with unknown linear constraints. First, we propose a Lagrangian relaxation of the sample complexity lower bound for pure exploration under constraints. Second, we leverage the Lagrangian lower bound and the properties of convex to propose two computationally efficient extensions of Track-and-Stop and Gamified Explorer, namely LATS and LAGEX.
  arXiv  Detail & Related papers  (2024-10-24T15:26:14Z)
• Conservative DDPG -- Pessimistic RL without Ensemble [48.61228614796803]
  DDPG is hindered by the overestimation bias problem. Traditional solutions to this bias involve ensemble-based methods. We propose a straightforward solution using a $Q$-target and incorporating a behavioral cloning (BC) loss penalty.
  arXiv  Detail & Related papers  (2024-03-08T23:59:38Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  We study to what extent may gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining a good fit training data. We analyze the closely related with-replacement SGD, for which an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate.
  arXiv  Detail & Related papers  (2022-02-27T13:25:01Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.