論文の概要: A residual-based message passing algorithm for constraint satisfaction problems

• arxiv url: http://arxiv.org/abs/2202.12468v1
• Date: Fri, 25 Feb 2022 02:43:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-28 16:17:46.334345
• Title: A residual-based message passing algorithm for constraint satisfaction problems
• Title（参考訳）: 制約満足度問題に対する残差に基づくメッセージパッシングアルゴリズム
• Authors: Chun-Yan Zhao, Yan-Rong Fu, and Jin-Hua Zhao
• Abstract要約: メッセージパッシングアルゴリズムに残差ベースの更新ステップを導入する。 提案アルゴリズムは, メッセージ更新の収束を改善し, 計算コストの低い満足度しきい値付近の解を求める際の成功確率を向上することを示す。
• 参考スコア（独自算出の注目度）: 2.474258157236412
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Message passing algorithms, whose iterative nature captures well complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages, provide a powerful toolkit in tackling hard computational tasks in optimization, inference, and learning problems. In the context of constraint satisfaction problems (CSPs), when a control parameter (such as constraint density) is tuned, multiple threshold phenomena emerge, signaling fundamental structural transitions in their solution space. Finding solutions around these transition points is exceedingly challenging for algorithm design, where message passing algorithms suffer from a large message fluctuation far from convergence. Here we introduce a residual-based updating step into message passing algorithms, in which messages varying large between consecutive steps are given high priority in the updating process. For the specific example of model RB, a typical prototype of random CSPs with growing domains, we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost. Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.
• Abstract（参考訳）: メッセージパッシングアルゴリズムは、複雑なシステムの相互接続変数間のよく複雑な相互作用を捕捉し、繰り返しメッセージの固定点から情報を抽出し、最適化、推論、学習問題においてハードな計算タスクに取り組むための強力なツールキットを提供する。 制約満足度問題(csps)の文脈では、制御パラメータ(制約密度など)がチューニングされると、複数のしきい値現象が発生し、解空間における基本構造遷移を示唆する。 これらの遷移点に関する解を見つけることは、メッセージパッシングアルゴリズムが収束から遠く離れた大きなメッセージ変動に苦しむアルゴリズム設計において非常に難しい。 ここでは、メッセージパッシングアルゴリズムに残差ベースの更新ステップを導入し、更新プロセスにおいて、連続的なステップ間で大きく変化するメッセージに高い優先度が与えられるようにする。 拡張領域を持つランダムなCSPの典型的なプロトタイプであるRBの具体例について、本アルゴリズムはメッセージ更新の収束を改善し、計算コストの低い満足度しきい値付近の解を見つける際の成功確率を高めることを示す。 メッセージパッシングアルゴリズムに対する我々のアプローチは、基底状態の解を見つけ、ハード最適化問題の解空間の詳細な構造を理解するアルゴリズムの開発において、そのパワーを探求する上で価値がある。

関連論文リスト

• Stabilized Proximal-Point Methods for Federated Optimization [20.30761752651984]
  非加速アルゴリズムの通信複雑性は、分散近位点アルゴリズムであるDANEによって達成される。 ハイブリッド射影-近点法に着想を得て,新しい分散アルゴリズムS-DANEを提案する。 S-DANEは、S-DANEと同様の局所計算効率を向上し、分散凸最適化のためのすべての既存手法の中で最もよく知られた通信複雑性を実現する。
  論文  参考訳（メタデータ） (2024-07-09T17:56:29Z)
• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates [28.700663352789395]
  分散変分不等式問題(VIP)に対する通信効率の良い局所訓練手法の統一収束解析を提供する。 提案手法は,いくつかの新しい局所学習アルゴリズムの提案と解析を可能にする推定値に関する一般的な鍵となる仮定に基づいている。 異種データにおける分散変分不等式を解くために,通信複雑性の向上を図った最初の局所降下偏差アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-08T10:58:46Z)
• Q-SHED: Distributed Optimization at the Edge via Hessian Eigenvectors Quantization [5.404315085380945]
  ニュートン型(NT)法は、DO問題における堅牢な収束率の実現要因として提唱されている。 インクリメンタルなヘッセン固有ベクトル量子化に基づく新しいビット割り当て方式を特徴とする、DOのための元のNTアルゴリズムであるQ-SHEDを提案する。 Q-SHEDはコンバージェンスに必要な通信ラウンド数を最大60%削減できることを示す。
  論文  参考訳（メタデータ） (2023-05-18T10:15:03Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。 非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。 詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
  論文  参考訳（メタデータ） (2021-10-04T03:17:41Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  本稿では,シーケンシャルなサブゴールタスクの超指数空間における解を高速に計算するための,Jump-Operator Dynamic Programmingという新しいフレームワークを提案する。 このアプローチでは、時間的に拡張された行動として機能する、再利用可能な目標条件付き警察のアンサンブルを制御する。 すると、この部分空間上の目的関数のクラスを、解がグラウンド化に不変であるものとして特定し、最適ゼロショット移動をもたらす。
  論文  参考訳（メタデータ） (2020-07-06T05:13:20Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)
• Communication-efficient Variance-reduced Stochastic Gradient Descent [0.0]
  通信効率のよい分散最適化の問題を考える。 特に、分散還元勾配に着目し、通信効率を高めるための新しいアプローチを提案する。 実データセットの包括的理論的および数値解析により、我々のアルゴリズムは通信の複雑さを95%減らし、ほとんど顕著なペナルティを伴わないことが明らかとなった。
  論文  参考訳（メタデータ） (2020-03-10T13:22:16Z)
• Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
  本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。 我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。 計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
  論文  参考訳（メタデータ） (2020-01-12T15:54:20Z)

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

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