論文の概要: A Hardware Accelerator for the Goemans-Williamson Algorithm

• arxiv url: http://arxiv.org/abs/2510.02863v1
• Date: Fri, 03 Oct 2025 10:01:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-06 16:35:52.345272
• Title: A Hardware Accelerator for the Goemans-Williamson Algorithm
• Title（参考訳）: Goemans-Williamsonアルゴリズムのためのハードウェア加速器
• Authors: D. A. Herrera-Martí, E. Guthmuller, J. Fereyre,
• Abstract要約: 凸最適化において, 浮動小数点精度が代数的サブルーチンにどのように組み入れられるかを示す。 内部作業精度の増大は,システムサイズの増加に伴って解法にかかる時間を減少させることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The combinatorial problem Max-Cut has become a benchmark in the evaluation of local search heuristics for both quantum and classical optimisers. In contrast to local search, which only provides average-case performance guarantees, the convex semidefinite relaxation of Max-Cut by Goemans and Williamson, provides worst-case guarantees and is therefore suited to both the construction of benchmarks and in applications to performance-critic scenarios. We show how extended floating point precision can be incorporated in algebraic subroutines in convex optimisation, namely in indirect matrix inversion methods like Conjugate Gradient, which are used in Interior Point Methods in the case of very large problem sizes. Also, an estimate is provided of the expected acceleration of the time to solution for a hardware architecture that runs natively on extended precision. Specifically, when using indirect matrix inversion methods like Conjugate Gradient, which have lower complexity than direct methods and are therefore used in very large problems, we see that increasing the internal working precision reduces the time to solution by a factor that increases with the system size.
• Abstract（参考訳）: 組合せ問題であるMax-Cutは、量子および古典的なオプティマイザの局所探索ヒューリスティック評価のベンチマークとなっている。 平均ケース性能保証のみを提供する局所探索とは対照的に、Goemans と Williamson による Max-Cut の凸緩和は最悪のケース保証を提供するため、ベンチマークの構築と性能批判シナリオへの応用の両方に適している。 凸最適化における代数的サブルーチンへの拡張浮動小数点精度、すなわち Conjugate Gradient のような間接的行列逆転法において、非常に大きな問題の大きさの場合に内点法にどのように組み込むことができるかを示す。 また、拡張精度でネイティブに動作するハードウェアアーキテクチャの解法までの時間の期待加速度を推定する。 具体的には、直接法よりも複雑さが低く、非常に大きな問題に使用される共役勾配のような間接行列逆転法を用いる場合、内部作業精度の増大は、システムサイズの増加に伴って解法にかかる時間を減少させる。

関連論文リスト

• Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learning [1.0282274843007797]
  外部補間(QMME)フレームワークを導入し,その逐次収束特性を確立する。 実効性を示すために,大規模カーネル正規化学習問題にQMMEを適用した。
  論文  参考訳（メタデータ） (2025-07-06T05:17:28Z)
• WENDy for Nonlinear-in-Parameters ODEs [1.9573380763700712]
  WEN(Wak-form Estimation of Non-linear Dynamics)は、非線形インである通常の微分方程式の系に対応するために拡張される。 提案手法の実用的メリットを実証するために,一連のベンチマークシステムに結果を提示する。
  論文  参考訳（メタデータ） (2025-02-13T01:40:21Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
  有界ノルムを持つ埋め込みベクトルに対して$rm SoftMax(XYT)$の正規化定数を計算する線形時間近似を提案する。 本稿では,提案手法が競合手法よりも高い精度あるいは同等の精度を達成できるような事前学習した埋め込みデータセットについて述べる。 提案アルゴリズムは解釈可能で,任意の埋め込み問題に容易に適応できる。
  論文  参考訳（メタデータ） (2023-03-30T15:48:26Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning [87.60600646105696]
  内部最適化問題が凸であるが非滑らかである場合の一階法を研究する。 本研究では, ヤコビアンの近位勾配降下と近位座標降下収率列の前方モード微分が, 正確なヤコビアンに向かって収束していることを示す。
  論文  参考訳（メタデータ） (2021-05-04T17:31:28Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。 平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。 BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
  論文  参考訳（メタデータ） (2021-03-02T16:26:20Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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