論文の概要: A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut

• arxiv url: http://arxiv.org/abs/2505.13405v4
• Date: Mon, 16 Jun 2025 14:31:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 15:15:31.088843
• Title: A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut
• Title（参考訳）: Max-Cutにおける超平面最適化のためのデータレス強化学習手法
• Authors: Gabriel Maliakal, Ismail Alkhouri, Alvaro Velasquez, Adam M Alessio, Saiprasad Ravishankar,
• Abstract要約: エージェントが改良された丸みを帯びた超平面を選択し、ゴーマンス・ウィリアムソン(GW)アルゴリズムで生成されたものよりも優れたカットを得られるように学習する、非エポゾディック強化学習の定式化に基づくトレーニングデータフリーアプローチを提案する。 提案手法は, 密度や次数分布の異なる大規模グラフに対して, より優れたカットを一貫して達成する。
• 参考スコア（独自算出の注目度）: 13.43661547732185
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Maximum Cut (MaxCut) problem is NP-Complete, and obtaining its optimal solution is NP-hard in the worst case. As a result, heuristic-based algorithms are commonly used, though their design often requires significant domain expertise. More recently, learning-based methods trained on large (un)labeled datasets have been proposed; however, these approaches often struggle with generalizability and scalability. A well-known approximation algorithm for MaxCut is the Goemans-Williamson (GW) algorithm, which relaxes the Quadratic Unconstrained Binary Optimization (QUBO) formulation into a semidefinite program (SDP). The GW algorithm then applies hyperplane rounding by uniformly sampling a random hyperplane to convert the SDP solution into binary node assignments. In this paper, we propose a training-data-free approach based on a non-episodic reinforcement learning formulation, in which an agent learns to select improved rounding hyperplanes that yield better cuts than those produced by the GW algorithm. By optimizing over a Markov Decision Process (MDP), our method consistently achieves better cuts across large-scale graphs with varying densities and degree distributions.
• Abstract（参考訳）: 最大カット(MaxCut)問題はNP-Completeであり、最悪の場合、最適解を得るのはNP-hardである。 その結果、ヒューリスティックベースのアルゴリズムは一般的に使用されるが、その設計には重要なドメインの専門知識が必要であることが多い。 最近では、大規模な(未)ラベル付きデータセットで訓練された学習ベースの手法が提案されているが、これらのアプローチは一般化性と拡張性に苦慮することが多い。 MaxCut の近似アルゴリズムとしてよく知られたのが Goemans-Williamson (GW) アルゴリズムであり、これは擬似非制約バイナリ最適化 (QUBO) の定式化を半定値プログラム (SDP) に緩和するものである。 GWアルゴリズムは、ランダムな超平面を均一にサンプリングして、SDP溶液をバイナリノード割り当てに変換することで、超平面の丸めを施す。 本稿では,非エポゾディック強化学習の定式化に基づく学習データフリーな手法を提案する。 マルコフ決定過程 (MDP) を最適化することにより, 様々な密度と次数分布を持つ大規模グラフの切断精度を常に向上する。

関連論文リスト

• Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization [15.102119312523696]
  組合せ最適化(CO)の問題は、医学、物流、製造など幅広い領域で発生する。 本研究では,CO の非学習近似アルゴリズムを学習ベースで拡張する手法を提案する。 本手法は,近似アルゴリズムをブラックボックスとして扱う新しい勾配推定法を用いて,自己教師付き方式でエンドツーエンドに学習する。
  論文  参考訳（メタデータ） (2025-02-26T18:23:07Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Are Graph Neural Networks Optimal Approximation Algorithms? [26.5364112420121]
  最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。 我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
  論文  参考訳（メタデータ） (2023-10-01T00:12:31Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
  有界ノルムを持つ埋め込みベクトルに対して$rm SoftMax(XYT)$の正規化定数を計算する線形時間近似を提案する。 本稿では,提案手法が競合手法よりも高い精度あるいは同等の精度を達成できるような事前学習した埋め込みデータセットについて述べる。 提案アルゴリズムは解釈可能で,任意の埋め込み問題に容易に適応できる。
  論文  参考訳（メタデータ） (2023-03-30T15:48:26Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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