論文の概要: 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の最もよく知られた収束)。
より一般に、実テンソルと球面セグレ・ヴェロネーゼ多様体の要素との間の内積を最小化する最小固有値計算の収束階層を導入する。
例えば、(実)テンソルスペクトルノルムを計算し、球面上の二乗形式を最小化するための階層を得る。
より一般的な制約付き多項式最適化問題に対する固有計算の階層について論じる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。