Fugu-MT 論文翻訳(概要): Reheated Gradient-based Discrete Sampling for Combinatorial Optimization

論文の概要: Reheated Gradient-based Discrete Sampling for Combinatorial Optimization

arxiv url: http://arxiv.org/abs/2503.04047v1
Date: Thu, 06 Mar 2025 03:01:25 GMT
ステータス: 翻訳完了
システム内更新日: 2025-03-07 16:00:52.576764
Title: Reheated Gradient-based Discrete Sampling for Combinatorial Optimization
Title（参考訳）: 組合せ最適化のための再熱勾配型離散サンプリング
Authors: Muheng Li, Ruqi Zhang,
Abstract要約: 勾配に基づく離散サンプリングは、様々な最適化(CO)問題に対する高効率で汎用的な解法として登場した。本稿では,この制限を克服することを目的とした,臨界温度と物理における比熱の概念から着想を得た新しい再加熱機構を導入する。
参考スコア（独自算出の注目度）: 12.572876283514095
License:
Abstract: Recently, gradient-based discrete sampling has emerged as a highly efficient, general-purpose solver for various combinatorial optimization (CO) problems, achieving performance comparable to or surpassing the popular data-driven approaches. However, we identify a critical issue in these methods, which we term ''wandering in contours''. This behavior refers to sampling new different solutions that share very similar objective values for a long time, leading to computational inefficiency and suboptimal exploration of potential solutions. In this paper, we introduce a novel reheating mechanism inspired by the concept of critical temperature and specific heat in physics, aimed at overcoming this limitation. Empirically, our method demonstrates superiority over existing sampling-based and data-driven algorithms across a diverse array of CO problems.
Abstract（参考訳）: 近年、勾配に基づく離散サンプリングは、様々な組合せ最適化(CO)問題に対する高効率で汎用的な解法として登場し、一般的なデータ駆動手法に匹敵する性能を達成している。しかし,これらの手法では,「輪郭を乱す」という重要な問題が指摘されている。この振る舞いは、長い間非常に類似した目標値を共有する新しい異なる解をサンプリングすることであり、計算の非効率性と潜在的な解の準最適探索に繋がる。本稿では,この制限を克服することを目的とした,臨界温度と物理における比熱の概念から着想を得た新しい再加熱機構を提案する。実験により,本手法はCO問題にまたがる既存のサンプリングベースおよびデータ駆動アルゴリズムよりも優れていることを示す。

関連論文リスト

Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems [0.5156484100374059]
過度にパラメータ化された状態における深度最適化のための最近の線探索手法と運動量方向との関係について検討する。モーメントパラメータの定義にデータ持続性、共役型ルールの混合を利用するアルゴリズムを導入する。結果のアルゴリズムは、他の一般的な手法よりも優れていることを実証的に示している。
論文参考訳（メタデータ） (2024-11-11T16:26:33Z)
Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
論文参考訳（メタデータ） (2024-09-02T12:55:27Z)
Structure-inspired Ansatz and Warm Start of Variational Quantum Algorithms for Quadratic Unconstrained Binary Optimization Problems [0.18874331450711404]
本稿では、変分量子固有解器を用いて2次非制約二元最適化問題に対処する構造に着想を得たアンザッツを提案する。本稿では,想像的時間進化に基づく新しいウォームスタート手法を提案する。このウォームスタート法は成功率を著しく向上させ,変分量子固有解法の収束に必要なイテレーション数を削減できることを実証する。
論文参考訳（メタデータ） (2024-07-02T18:00:05Z)
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文参考訳（メタデータ） (2023-10-08T23:39:38Z)
An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文参考訳（メタデータ） (2023-06-10T08:25:16Z)
Sampling with Mollified Interaction Energy Descent [57.00583139477843]
モーフィファイド相互作用エネルギー降下(MIED)と呼ばれる新しい最適化に基づくサンプリング手法を提案する。 MIEDは、モル化相互作用エネルギー(MIE)と呼ばれる確率測度に関する新しいクラスのエネルギーを最小化する我々は,制約のないサンプリング問題に対して,我々のアルゴリズムがSVGDのような既存の粒子ベースアルゴリズムと同等に動作することを示す。
論文参考訳（メタデータ） (2022-10-24T16:54:18Z)
The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
論文参考訳（メタデータ） (2022-09-27T09:27:29Z)
Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文参考訳（メタデータ） (2021-11-29T15:10:09Z)
COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization [4.970364068620608]
我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
論文参考訳（メタデータ） (2021-09-07T17:21:09Z)
Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文参考訳（メタデータ） (2020-12-21T17:29:58Z)
GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文参考訳（メタデータ） (2020-02-17T20:21:20Z)

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