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

• arxiv url: http://arxiv.org/abs/2310.17827v1
• Date: Fri, 27 Oct 2023 00:28:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-30 15:09:04.443663
• Title: A hierarchy of eigencomputations for polynomial optimization on the sphere
• Title（参考訳）: 球面上の多項式最適化のための固有計算の階層
• Authors: Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan
• Abstract要約: 球面上の実同質性の最小値上の下界の収束階層を導入する。 我々の階層は、レベル$k$で$O(1/k)$として収束し、SOS(sum-of-squares)階層の最もよく知られた収束と一致することを証明している。 より一般に、実テンソルと球状セグレ・ヴェローネ多様体の要素の間の内積を最小化する最小固有値計算の収束階層を導入する。
• 参考スコア（独自算出の注目度）: 10.850101961203752
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a convergent hierarchy of lower bounds on the minimum value of a real homogeneous polynomial over the sphere. The main practical advantage of our hierarchy over the sum-of-squares (SOS) 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 SOS. In practice, this allows us to go to much higher levels than are computationally feasible for the SOS hierarchy. For both hierarchies, the underlying space at the $k$-th level is the set of homogeneous polynomials of degree $2k$. We prove that our hierarchy converges as $O(1/k)$ in the level $k$, matching the best-known convergence of the SOS hierarchy when the number of variables $n$ is less than the half-degree $d$ (the best-known convergence of SOS when $n \geq d$ is $O(1/k^2)$). More generally, we introduce a convergent hierarchy of minimum eigenvalue computations for minimizing the inner product between a real tensor and an element of the spherical Segre-Veronese variety, with similar convergence guarantees. As examples, we obtain hierarchies for computing the (real) tensor spectral norm, and for minimizing biquadratic forms over the sphere. Hierarchies of eigencomputations for more general constrained polynomial optimization problems are discussed.
• Abstract（参考訳）: 球面上の実同次多項式の最小値上の下界の収束階層を導入する。 SOS(sum-of-squares)階層に対する階層構造の主な実用的利点は、SOSの各レベルに必要な完全半定値プログラム(SDP)とは対照的に、最小の固有値計算によって階層構造の各レベルにおける下位境界が得られることである。 実際には、SOS階層で計算可能なものよりもはるかに高いレベルに進むことができます。 どちらの階層に対しても、$k$-階の基底空間は次数2k$の斉次多項式の集合である。 我々の階層はレベル$k$で$O(1/k)$として収束し、変数数$n$が半次$d$より小さいときのSOS階層の最もよく知られた収束と一致する($n \geq d$が$O(1/k^2)$であるときのSOSの最もよく知られた収束)。 より一般に、実テンソルと球面セグレ・ヴェロネーゼ多様体の要素との間の内積を最小化する最小固有値計算の収束階層を導入する。 例えば、(実)テンソルスペクトルノルムを計算し、球面上の二乗形式を最小化するための階層を得る。 より一般的な制約付き多項式最適化問題に対する固有計算の階層について論じる。

関連論文リスト

• 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)

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

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