論文の概要: Dataless Quadratic Neural Networks for the Maximum Independent Set Problem

• arxiv url: http://arxiv.org/abs/2406.19532v3
• Date: Wed, 16 Oct 2024 19:31:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-18 13:15:47.769274
• Title: Dataless Quadratic Neural Networks for the Maximum Independent Set Problem
• Title（参考訳）: 最大独立集合問題に対するデータレス2次ニューラルネットワーク
• Authors: Ismail Alkhouri, Cedric Le Denmat, Yingjie Li, Cunxi Yu, Jia Liu, Rongrong Wang, Alvaro Velasquez,
• Abstract要約: pCQO-MISはエッジ数ではなくグラフ内のノード数でスケールすることを示す。 提案手法は,分散の排除,サンプリング,データ中心のアプローチを回避する。
• 参考スコア（独自算出の注目度）: 23.643727259409744
• License:
• Abstract: Combinatorial Optimization (CO) addresses many important problems, including the challenging Maximum Independent Set (MIS) problem. Alongside exact and heuristic solvers, differentiable approaches have emerged, often using continuous relaxations of ReLU-based or quadratic objectives. Noting that an MIS in a graph is a Maximum Clique (MC) in its complement, we propose a new quadratic formulation for MIS by incorporating an MC term, improving convergence and exploration. We show that every maximal independent set corresponds to a local minimizer, derive conditions for the MIS size, and characterize stationary points. To solve our non-convex objective, we propose solving parallel multiple initializations using momentum-based gradient descent, complemented by an efficient MIS checking criterion derived from our theory. Therefore, we dub our method as parallelized Clique-Informed Quadratic Optimization for MIS (pCQO-MIS). Our experimental results demonstrate the effectiveness of the proposed method compared to exact, heuristic, sampling, and data-centric approaches. Notably, our method avoids the out-of-distribution tuning and reliance on (un)labeled data required by data-centric methods, while achieving superior MIS sizes and competitive runtime relative to their inference time. Additionally, a key advantage of pCQO-MIS is that, unlike exact and heuristic solvers, the runtime scales only with the number of nodes in the graph, not the number of edges.
• Abstract（参考訳）: 組合せ最適化(CO)は、最大独立セット(MIS)問題を含む多くの重要な問題に対処する。 厳密でヒューリスティックな解法とともに、しばしばReLUに基づく2次的目的の連続的な緩和を用いて微分可能なアプローチが出現した。 グラフ内のMISがその補集合の最大傾き(MC)であることに注意し、MC項を組み込んだMISの新しい二次定式化を提案し、収束と探索を改善した。 すべての最大独立集合が局所最小化器に対応し、MISサイズの導出条件を導出し、定常点を特徴づけることを示す。 非凸目的を解決するために,モーメントに基づく勾配勾配を用いた並列多重初期化法を提案し,この理論から導出したMIS検査基準を補完する。 そこで本手法は,MIS (pCQO-MIS) の並列化Clique-Informed Quadratic Optimization として提案する。 実験により,提案手法の有効性を,正確な,ヒューリスティック,サンプリング,データ中心アプローチと比較した。 特に,本手法は,データ中心の手法で要求されるラベル付きデータへの非分配的チューニングや依存を回避するとともに,予測時間に対して優れたMISサイズと競合ランタイムを実現する。 さらに、pCQO-MISの重要な利点は、厳密でヒューリスティックな解法とは異なり、ランタイムはエッジの数ではなく、グラフ内のノードの数でしかスケールしないことである。

関連論文リスト

• On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning [85.75164588939185]
  複数モーダルな)自己教師付き表現学習のための連続領域における識別確率モデル問題について検討する。 我々は、自己教師付き表現学習における現在のInfoNCEに基づくコントラスト損失の制限を明らかにするために一般化誤差解析を行う。
  論文  参考訳（メタデータ） (2024-10-11T18:02:46Z)
• From Maximum Cut to Maximum Independent Set [7.250073177017239]
  最大独立集合(MIS)問題も特定のイジングモデルと関係があることは以前から知られていた。 この戦略により、ランダムなエルドホス・ローニイグラフの独立数に対する近似が大幅に改善されることが判明した。 また、コーディング理論から生じるベンチマークで完全なパフォーマンスを示す。
  論文  参考訳（メタデータ） (2024-08-13T09:33:41Z)
• Efficient k-means with Individual Fairness via Exponential Tilting [13.72284501663574]
  位置に基づくリソース割り当てのシナリオでは、全てのポイントを平等に扱うという原則を達成するために、個別に公平なクラスタリングがしばしば用いられる。 本稿では,クラスタリングにおける個別の公平性を実現することを目的とした,新しいアルゴリズムである傾きk平均(TKM)を提案する。
  論文  参考訳（メタデータ） (2024-06-24T11:50:31Z)
• An Efficient Difference-of-Convex Solver for Privacy Funnel [3.069335774032178]
  本稿では,プライバシ・ファンネル(PF)手法の効率的な解法を提案する。 提案した直流分離は, クローズドフォーム更新方程式を導出する。 提案手法をMNISTおよびFashionデータセットを用いて評価する。
  論文  参考訳（メタデータ） (2024-03-02T01:05:25Z)
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers [0.0]
  我々は、Rydberg量子アニールの最適化問題を解くための非ユニットディスクフレームワークを提供する。 我々の構成は、局所制御可能な光シフトを個々の量子ビットに適用する多体相互作用Rydbergシステムからなる。 我々の数値シミュレーションでは、Rydbergアニーラーを所望の多体基底状態に大域的に駆動しながら、局所分解プロトコルを実装している。
  論文  参考訳（メタデータ） (2023-08-15T14:24:45Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• Exploiting Temporal Structures of Cyclostationary Signals for Data-Driven Single-Channel Source Separation [98.95383921866096]
  単一チャネルソース分離(SCSS)の問題点について検討する。 我々は、様々なアプリケーション領域に特に適するサイクロ定常信号に焦点を当てる。 本稿では,最小MSE推定器と競合するU-Netアーキテクチャを用いたディープラーニング手法を提案する。
  論文  参考訳（メタデータ） (2022-08-22T14:04:56Z)
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets [101.5329678997916]
  両プレイヤーゼロサムマルコフゲーム(MG)をオフライン環境で研究する。 目標は、事前収集されたデータセットに基づいて、近似的なナッシュ均衡(NE)ポリシーペアを見つけることである。
  論文  参考訳（メタデータ） (2022-02-15T15:39:30Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Learning What to Defer for Maximum Independent Sets [84.00112106334655]
  本稿では,各段階における解の要素的決定を学習することにより,エージェントが適応的に段階数を縮小あるいは拡張する,新たなDRL方式を提案する。 提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
  論文  参考訳（メタデータ） (2020-06-17T02:19:31Z)

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

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