論文の概要: A hierarchy of eigencomputations for polynomial optimization on the sphere

• arxiv url: http://arxiv.org/abs/2310.17827v2
• Date: Sat, 16 Nov 2024 18:01:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-19 14:26:25.471578
• Title: A hierarchy of eigencomputations for polynomial optimization on the sphere
• Title（参考訳）: 球面上の多項式最適化のための固有計算の階層構造
• Authors: Benjamin Lovitz, Nathaniel Johnston,
• Abstract要約: 単位球面上の実形式の最小値に下界の収束階層を導入する。 実和-二乗階層に対する我々の階層の主な実用的利点は、各レベルの下限が最小の固有値によって得られることである。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We introduce a convergent hierarchy of lower bounds on the minimum value of a real form over the unit sphere. The main practical advantage of our hierarchy over the real sum-of-squares (RSOS) hierarchy is that the lower bound at each level of our hierarchy is obtained by a minimum eigenvalue computation, as opposed to the full semidefinite program (SDP) required at each level of RSOS. In practice, this allows us to compute bounds on much larger forms than are computationally feasible for RSOS. Our hierarchy outperforms previous alternatives to RSOS, both asymptotically and in numerical experiments. We obtain our hierarchy by proving a reduction from real optimization on the sphere to Hermitian optimization on the sphere, and invoking the Hermitian sum-of-squares (HSOS) hierarchy. This opens the door to using other Hermitian optimization techniques for real optimization, and gives a path towards developing spectral hierarchies for more general constrained real optimization problems. To this end, we use our techniques to develop a hierarchy of eigencomputations for computing the real tensor spectral norm.
• Abstract（参考訳）: 単位球面上の実形式の最小値に下界の収束階層を導入する。 実総和(RSOS)階層に対する階層構造の主な実用上の利点は、階層構造の各レベルにおける下限は、RSOSの各レベルで必要とされる半定値プログラム(SDP)に対して、最小の固有値計算によって得られることである。 実際には、RSOSで計算可能なよりもはるかに大きな形式で境界を計算することができる。 我々の階層は、漸近的にも数値実験においても、RSOSの代替品よりも優れています。 我々は、球面上の実最適化から球面上のエルミート最適化への還元を証明し、Hermitian sum-of-squares(HSOS)階層を呼び出すことによって階層を得る。 これにより、他のエルミート最適化手法を実際の最適化に利用し、より一般的な制約のある実最適化問題に対してスペクトル階層を開発するための道を開くことができる。 この目的のために,本手法を用いて実テンソルスペクトルノルムを計算するための固有計算の階層を構築する。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace [4.917399520581689]
  本稿では、ランツォス過程の助けを借りて、低次元近似クリロフ部分空間の列を構築する。 構成された部分空間は、動的かつ漸進的にヘッセン逆ベクトル積を近似することができる。 また,小さな三角形線形系を解くための中心ステップとして,二段階問題に対する改良可能な部分空間ベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-04-04T09:57:29Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning [45.78238792836363]
  本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。 既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
  論文  参考訳（メタデータ） (2022-09-01T11:05:26Z)
• Synthesizing Optimal Parallelism Placement and Reduction Strategies on Hierarchical Systems for Deep Learning [0.3345437353879254]
  本稿では,複数並列化形式を階層型加速器系にマッピングする手法を提案する。 我々は、これらのマッピングが全再現性能(最大448倍)に与える影響を実験的に検証した。 我々は1つ以上の並列化軸を集合列に分解できる新しい構文誘導型プログラム合成フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-10-20T13:05:49Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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