Fugu-MT 論文翻訳(概要): Local-Minima-Preserving Continuous Relaxation of Ising Problems

論文の概要: Local-Minima-Preserving Continuous Relaxation of Ising Problems

arxiv url: http://arxiv.org/abs/2606.30333v1
Date: Mon, 29 Jun 2026 14:13:56 GMT
ステータス: 翻訳完了
システム内更新日: 2026-06-30 18:07:16.260549
Title: Local-Minima-Preserving Continuous Relaxation of Ising Problems
Title（参考訳）: ローカル・ミニマ保存型イジング問題の連続緩和
Abstract要約: 我々はイジング問題に対するワンフリップ局所ミニマの概念を考える。緩和の局所ミニマと元のイジング問題のワンフリップミニマとの間には1対1の対応があることが示される。この保証により、スムーズな関数の局所ミニマを見つけることでイジング問題を減らすことができる。
参考スコア（独自算出の注目度）: 11.357919122960732
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The generalized Ising problem captures a broad spectrum of hard combinatorial problems, including MAX-CUT, Number Partitioning (NPP), and Maximum Independent Set. In this work, we consider the notion of one-flip local minima for this problem. We construct a polynomial relaxation and prove the landscape equivalence theorem: there exists a one-to-one correspondence between the local minima of the relaxation and the one-flip minima of the original Ising problem. This guarantee reduces the Ising problem to finding the local minima of a smooth function, allowing us to leverage gradient-based optimizers such as ADAM. We demonstrate that our method is scalable and it achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.
Abstract（参考訳）: 一般化されたイジング問題は、MAX-CUT、NPP(Number Partitioning)、最大独立集合(Maximum Independent Set)など、幅広いハード組合せ問題を捉えている。本研究では,この問題に対する一フリップ局所ミニマの概念について考察する。我々は多項式緩和を構築し、ランドスケープ同値定理を証明し、緩和の局所ミニマと元のイジング問題のワンフリップミニマとの間には1対1の対応が存在する。この保証により、スムーズな関数の局所最小値を見つけることでIsingの問題が軽減され、ADAMのような勾配に基づくオプティマイザを活用することができる。提案手法は, スピングラスモデル, MAX-CUT, NPPなど, 高い性能を示す。

関連論文リスト

Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
State-of-the-art Large Language Model (LLM) プルーニング手法は階層的に動作し、階層ごとのプルーニングエラーを最小限に抑え、完全な再トレーニングを回避する。既存の手法は、刈り上げ対象の重量相互作用を無視する欲求凸に依存する。提案手法は, 層ごとのプルーニング誤差を大幅に低減し, 最先端のGPTアーキテクチャにおいて高いベースラインを達成し, メモリ効率を保っている。
論文参考訳（メタデータ） (2025-10-15T16:13:44Z)
A first-order method for constrained nonconvex--nonconcave minimax problems under a local Kurdyka-Łojasiewicz condition [5.834528275910258]
我々は、内部が潜在的に複雑な制約を伴う制約付き非コンケーブミニマックス問題の研究を行う。元の問題の最大関数は局所的なH"古い性質の滑らかさを楽しむことを示す。本稿では,制約付き最適化問題の解法を提案し,その収束性を局所KL条件下で確立する。
論文参考訳（メタデータ） (2025-10-01T17:54:27Z)
A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Łojasiewicz condition [1.534667887016089]
局所的なクルディカ・ロジャシエヴィチ(KL)条件の内的問題と外的最小化変数が相違する非コンケーブ最小化問題のクラスについて検討する。特に、アルゴリズムが問題の定常点に向かって進むと、KL条件が成立する領域は縮小し、より不規則な風景が生じる。
論文参考訳（メタデータ） (2025-07-02T17:45:10Z)
Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysis [2.1756081703276]
凸制約下での凸最適化のための自然分散低減近位勾配(VRPG)アルゴリズムの挙動を解析する。我々の主な成果は、VRPGアルゴリズムの漸近的でない保証である。我々の保証は、損失関数の複雑さ、雑音の可変性、制約集合の幾何を捉えていることを示す。
論文参考訳（メタデータ） (2024-03-24T14:45:11Z)
Energy Landscapes for the Quantum Approximate Optimisation Algorithm [0.0]
QAOA anszeのエネルギー景観を様々なグラフでナビゲートするために、流域ホットなグローバルな手法を用いています。対応するランドスケープは一般的に単一のファンネル組織を持つため、Max-Cut ソリューションの確率がよい低いミニマを見つけることは比較的容易である。
論文参考訳（メタデータ） (2024-01-09T19:17:01Z)
Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文参考訳（メタデータ） (2023-11-04T11:12:24Z)
Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization [50.10952609321302]
合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
論文参考訳（メタデータ） (2023-08-18T14:57:21Z)
Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems [46.71914490521821]
本稿では,非コンケーブなミニマックス問題のクラスに対して,新たな漸進型アルゴリズムを提案する。提案アルゴリズムは制約付き正規化問題に適用可能である。
論文参考訳（メタデータ） (2023-02-20T08:37:08Z)
Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。本稿では,2種類のミニマックスアルゴリズムを提案する。そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文参考訳（メタデータ） (2023-02-08T01:42:45Z)
Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。予測と高い確率で、新しい過剰なリスク境界を提供する。我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文参考訳（メタデータ） (2022-11-03T12:40:24Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)

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