論文の概要: Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT

• arxiv url: http://arxiv.org/abs/2610.19043v1
• Date: Tue, 13 Oct 2026 18:32:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.759563
• Title: Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
• Title（参考訳）: 計算制約のないMAX-CUTにおける局所オプティマスの回避を可能にするグラフ粗大化
• Abstract要約: 粗いグラフ粗いアプローチで,ポリ粒子粒子(時間%連続的再編成)のランドスケープを温める方法を示す。 離散的な局所的な神経リファインメントを持つ拡張変種は、最近の最適分岐法によって評価された60のBik Macインスタンスの全てに公開される。
• 参考スコア（独自算出の注目度）: 30.519031050302814
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Because its binary optimization landscape contains exponentially many local optima, MAX-CUT is highly sensitive to initialization. We study Particle Polynomial Relaxation (PPR), a moment-based nonconvex continuous reformulation possessing an advantageous optimization landscape. We warm-start PPR with Combinatorial Multigrid (CMG), a spectral graph-coarsening method that produces structure-aware initial solutions in near-linear time without training data. On \texttt{t2g20} ($n=400$), benchmark instance with known exact optimum, the combined CMG+PPR pipeline reaches $97.5\%$ of optimum on average and $98.4\%$ on the best run. An extended variant with discrete local-search refinement reaches the published optimum on all sixty Biq Mac instances evaluated by a recent neural branch-and-bound method. Using a sparse CSR representation, the same approach scales to G-set instances with up to $20{,}000$ vertices reducing memory requirements by up to $3333\times$ while maintaining a consistent improvement over the CMG warm start. Gains are largest on sparse weighted graphs; on dense graphs we complement the pipeline with spectral sparsification.
• Abstract（参考訳）: バイナリ最適化のランドスケープは指数関数的に多くの局所最適化を含んでいるため、MAX-CUTは初期化に非常に敏感である。 PPR(Particle Polynomial Relaxation, Particle Polynomial Relaxation)について検討した。 我々は,学習データなしでほぼ直線時間で構造を意識した初期解を生成するスペクトルグラフ粗大化法である Combinatorial Multigrid (CMG) でPPRをウォームスタートする。 既知の正確な最適化を持つベンチマークインスタンスであるtexttt{t2g20}$n=400$では、組み合わせたCMG+PPRパイプラインは、平均で97.5\%、ベストランで987.4\%に達する。 離散局所探索による拡張変種は、最近のニューラルブランチ・アンド・バウンド法で評価された60のBik Macインスタンスすべてに対して、公開された最適値に達する。 スパースCSR表現を使用して、同じアプローチは、最大20$$000$頂点でGセットインスタンスにスケールし、CMGウォームスタートに対する一貫した改善を維持しながら、メモリ要求を最大3333\times$に削減する。 利得はスパース重み付きグラフ上で最大であり、高密度グラフでは、パイプラインをスペクトルスカラー化で補完する。

関連論文リスト

• GraphGP: Scalable Gaussian Processes with Vecchia's Approximation [0.0]
  ヴェッキア近似(Vecchia approximation)は、定常、崩壊する核に対するスパース精度行列近似である。 線形時間とメモリ要求で10億近いパラメータにスケールする,Vecchia近似のアルゴリズムであるGraphGPを提案する。
  論文  参考訳（メタデータ） (2026-06-09T19:50:27Z)
• Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
  永続性に基づく位相最適化は、点クラウド $X の部分集合 mathbbRd$ を $L(X) = ell(mathrmDgm(X))$ という形の目的を最小化することによって変形する。 実際、最適化は2つの結合した問題によって制限される: 永続ホモロジーは典型的にはサブサンプル上で計算され、結果として生じる位相勾配は非常にスパースであり、非ゼロ更新を受けるアンカーポイントはわずかである。
  論文  参考訳（メタデータ） (2026-05-09T15:47:20Z)
• A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation [5.137643077079792]
  一般グラフと任意の固定ラウンド$pge2$に対して、所定の角度での固定ラウンドQAOAの期待を正確に評価することは、$mathrmNP$-hardであることを示す。 フレームワークを汎用バイナリ非制約組合せ最適化(BUCO)に拡張する。
  論文  参考訳（メタデータ） (2025-11-25T11:35:37Z)
• Graph Random Features for Scalable Gaussian Processes [52.89901965157282]
  離散入力空間上のスケーラブルなガウス過程へのグラフランダム特徴(GRF)の適用について検討する。 我々は、(穏やかな仮定の下で) GRF に対するベイズ的推論が、正確なカーネルに対して$O(N3)$のノード数に対して$O(N3/2)$の時間複雑性を楽しむことを証明した。
  論文  参考訳（メタデータ） (2025-09-03T20:13:23Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Using Distance Correlation for Efficient Bayesian Optimization [0.0]
  距離相関と呼ばれる2つの確率変数の相関関係の統計的尺度とBOを統合したBOスキームBDCを提案する。 BDCの探索は自動的にバランスと利用のバランスを保ち、手動のハイパーパラメータチューニングを必要としない。 我々はBDCを様々なベンチマークテストで評価し、一般的なBO法と同等に動作することを観察する。
  論文  参考訳（メタデータ） (2021-02-17T19:37:35Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。 本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
  論文  参考訳（メタデータ） (2021-02-02T16:18:29Z)

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

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