論文の概要: 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)階層を呼び出すことによって階層を得る。 これにより、他のエルミート最適化手法を実際の最適化に利用し、より一般的な制約のある実最適化問題に対してスペクトル階層を開発するための道を開くことができる。 この目的のために,本手法を用いて実テンソルスペクトルノルムを計算するための固有計算の階層を構築する。

関連論文リスト

• Multilayer Correlation Clustering [12.492037397168579]
  相関クラスタリング(Bansal et al., FOCS '02)の新たな一般化である多層相関クラスタリングを確立する。 本稿では、共通集合である$V$に対して相関クラスタリング(層と呼ばれる)の一連の入力を与えられる。 目的は、不一致ベクトルの$ell_p$-norm(pgeq 1$)を最小化する$V$のクラスタリングを見つけることである。
  論文  参考訳（メタデータ） (2024-04-25T15:25:30Z)
• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。 本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
  論文  参考訳（メタデータ） (2023-05-23T15:26:36Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。 結果がminimaxアプリケーションよりも難しいことを示します。
  論文  参考訳（メタデータ） (2021-02-07T21:46:29Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction [19.540926205375857]
  本稿では,SARAH型分散低減技術を用いたGT-SARAHと呼ばれる一階勾配法について述べる。 特に、$n = O(Nfrac12(lambda)3)$のようなビッグデータでは、ネットワークの複雑さとは無関係に、この複雑さは$O(Nfrac12Lepsilon-2)$に減少する。 さらに、局所的なミニバッチサイズの適切な選択は、勾配複雑性と通信複雑性のトレードオフをバランスさせる。
  論文  参考訳（メタデータ） (2020-08-17T15:51:32Z)
• Latent Factor Analysis of Gaussian Distributions under Graphical Constraints [5.575141499952048]
  CMTFA のランクは 1 ドル、ランクは n-1 ドルのいずれかであり、その間には何の問題もない。 特に、CMTFA のランクは 1 ドル、ランクは n-1 ドルのいずれかであり、その間には何も持たないことが示されている。
  論文  参考訳（メタデータ） (2020-01-08T19:36:44Z)

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

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