論文の概要: On the Partial Convexification for Low-Rank Spectral Optimization: Rank
Bounds and Algorithms
- arxiv url: http://arxiv.org/abs/2305.07638v2
- Date: Wed, 21 Jun 2023 02:22:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-22 17:15:26.009688
- Title: On the Partial Convexification for Low-Rank Spectral Optimization: Rank
Bounds and Algorithms
- Title（参考訳）: 低ランクスペクトル最適化のための部分凸化について:ランク境界とアルゴリズム
- Authors: Yongchun Li and Weijun Xie
- Abstract要約: 低ランクスペクトル最適化問題(LSOP)は、複数の二辺行列の不等式を対象とする線形対象を最小化する。
LSOPの解法は一般にNPハードであるが、「LSOP-R」と呼ばれる部分凸化はしばしば抽出可能であり、高品質な解が得られる。
- 参考スコア（独自算出の注目度）: 1.7640556247739623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective
subject to multiple two-sided linear matrix inequalities intersected with a
low-rank and spectral constrained domain set. Although solving LSOP is, in
general, NP-hard, its partial convexification (i.e., replacing the domain set
by its convex hull) termed "LSOP-R," is often tractable and yields a
high-quality solution. This motivates us to study the strength of LSOP-R.
Specifically, we derive rank bounds for any extreme point of the feasible set
of LSOP-R and prove their tightness for the domain sets with different matrix
spaces. The proposed rank bounds recover two well-known results in the
literature from a fresh angle and also allow us to derive sufficient conditions
under which the relaxation LSOP-R is equivalent to the original LSOP. To
effectively solve LSOP-R, we develop a column generation algorithm with a
vector-based convex pricing oracle, coupled with a rank-reduction algorithm,
which ensures the output solution satisfies the theoretical rank bound.
Finally, we numerically verify the strength of the LSOP-R and the efficacy of
the proposed algorithms.
- Abstract（参考訳）: 低ランクスペクトル最適化問題(lsop)は、低ランクおよびスペクトル制約領域集合と交わる複数の2面線型行列不等式に対する線形目的対象を最小化する。
LSOPを解くことは一般にNPハードであるが、その部分凸化(すなわち、凸包で設定された領域をLSOP-Rと置き換える)は、しばしば取り外し可能であり、高品質な解が得られる。
これはLSOP-Rの強さを研究する動機となる。
具体的には、LSOP-R の可能な集合の任意の極点に対する階数境界を導出し、異なる行列空間を持つ領域集合に対するそれらの厳密性を証明する。
提案したランク境界は,文献中の2つのよく知られた結果を新しい角度から回収し,緩和LSOP-Rが元のLSOPと同値である十分な条件を導出することを可能にする。
LSOP-Rを効果的に解くために,ベクトルベースの凸価格オラクルを用いた列生成アルゴリズムとランク推論アルゴリズムを併用し,出力解が理論的なランク境界を満たすことを保証する。
最後に,LSOP-Rの強度と提案アルゴリズムの有効性を数値的に検証する。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
本研究では,RPMアルゴリズムの最小化目的関数を用いて要求を満たす手法を提案する。
分岐とバウンド(BnB)アルゴリズムが考案され、パラメータのみに分岐し、収束率を高める。
実験による評価は,非剛性変形,位置雑音,外れ値に対する提案手法の高剛性を示す。
論文 参考訳（メタデータ） (2024-05-14T13:28:57Z) - ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。
本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。
本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
論文 参考訳（メタデータ） (2023-12-04T19:00:07Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Performance of $\ell_1$ Regularization for Sparse Convex Optimization [10.37112414795167]
ベクトル値特徴を持つスパース凸最適化のためのグループLASSOの最初のリカバリ保証を与える。
この結果は、一般入力インスタンス下での凸関数に対するグループLASSOの経験的成功を理論的に説明する最初のものである。
この問題に対する一般損失関数の第一結果は、強い凸性や滑らかさに制限されるだけである。
論文 参考訳（メタデータ） (2023-07-14T15:31:45Z) - An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
本稿では,複合最適化問題のクラスについて述べる。
合成構造を利用することで、ポテンシャル関数が反復列において1/2$のKL特性を持つ条件を与える。
論文 参考訳（メタデータ） (2023-03-29T16:15:34Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained
Optimization Problems [1.7640556247739623]
i) 極点の完全性 -- 極点の全ては RCOP 集合に属する; (ii) 極点の完全性 -- 任意の m 側線型行列の不等式に対する DWR RCOP の完全性; (iii) 公正学習のための完全性。
これらの条件は、公正な学習のために2つの同質な二面的正確性を持つ不均一な制約を許容する問題に対する極端に正確性を含む、新しい結果を特定するのに非常に有用である。
論文 参考訳（メタデータ） (2022-10-28T14:57:13Z) - Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。
交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
論文 参考訳（メタデータ） (2021-09-13T16:13:13Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。