論文の概要: A new perspective on low-rank optimization
- arxiv url: http://arxiv.org/abs/2105.05947v1
- Date: Wed, 12 May 2021 20:22:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-14 14:03:00.168399
- Title: A new perspective on low-rank optimization
- Title(参考訳): 低ランク最適化の新しい視点
- Authors: Dimitris Bertsimas, Ryan Cory-Wright, Jean Pauphilet
- Abstract要約: 最適化、機械学習、統計学を通じて多くの低ランク問題の鍵となる問題は、単純な低ランク集合の凸殻を特徴づけることである。
我々は,視線関数の行列アナログである行列パースペクティブ関数を起動し,低ランク制約下での凸二次グラフ,行列指数関数,行列パワー関数の凸殻を明示的に特徴付ける。
これらの緩和は半定値および行列パワーコーンの制約によってモデル化でき、従ってトラクタブルに最適化できる。
- 参考スコア(独自算出の注目度): 3.136861161060885
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A key question in many low-rank problems throughout optimization, machine
learning, and statistics is to characterize the convex hulls of simple low-rank
sets and judiciously apply these convex hulls to obtain strong yet
computationally tractable convex relaxations. We invoke the matrix perspective
function - the matrix analog of the perspective function-and characterize
explicitly the convex hull of epigraphs of convex quadratic, matrix
exponential, and matrix power functions under low-rank constraints. Further, we
exploit these characterizations to develop strong relaxations for a variety of
low-rank problems including reduced rank regression, non-negative matrix
factorization, and factor analysis. We establish that these relaxations can be
modeled via semidefinite and matrix power cone constraints, and thus optimized
over tractably. The proposed approach parallels and generalizes the perspective
reformulation technique in mixed-integer optimization, and leads to new
relaxations for a broad class of problems.
- Abstract(参考訳): 最適化、機械学習、統計学を通じて多くの低ランク問題において重要な問題は、単純な低ランク集合の凸船体を特徴づけ、これらの凸船体を巧みに応用して、強力で計算的に抽出可能な凸緩和を得ることである。
我々は,視線関数の行列アナログである行列パースペクティブ関数を起動し,低ランク制約下での凸二次グラフ,行列指数関数,行列パワー関数の凸殻を明示的に特徴付ける。
さらに,これらの特徴を応用して,階数回帰,非負行列因子分解,因子分析など,様々な低ランク問題に対して強い緩和を与える。
これらの緩和は半定値および行列パワーコーンの制約によってモデル化でき、従ってトラクタブルに最適化できる。
提案手法は,混合整数最適化における視点再構成手法を並列化し一般化し,幅広い問題に対して新たな緩和をもたらす。
関連論文リスト
- $\ell_1$-norm rank-one symmetric matrix factorization has no spurious second-order stationary points [20.82938951566065]
この問題の2階定常点(つまり局所最小点)は、実際には大域的に最適であることを示す。
我々の手法は、様々な高度な非滑らかな学習問題の最適化状況の分析に応用できる可能性がある。
論文 参考訳(メタデータ) (2024-10-07T13:25:37Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳(メタデータ) (2024-06-28T02:56:22Z) - Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and
Eigenvector Disjunctions [6.537257913467247]
低ランク行列の完備化は、与えられた観測セットをできるだけ正確に回復する最小の複雑さの行列からなる。
新たな凸緩和は、既存の方法に比べて最大値を大幅に下げる。
論文 参考訳(メタデータ) (2023-05-20T22:04:34Z) - An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
本稿では,複合最適化問題のクラスについて述べる。
合成構造を利用することで、ポテンシャル関数が反復列において1/2$のKL特性を持つ条件を与える。
論文 参考訳(メタデータ) (2023-03-29T16:15:34Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。
この問題は楕円分布のペナルティ化された最大推定値として表される。
楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
論文 参考訳(メタデータ) (2022-10-21T13:19:45Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-30T19:17:35Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳(メタデータ) (2021-04-13T23:21:01Z) - Robust Low-rank Matrix Completion via an Alternating Manifold Proximal
Gradient Continuation Method [47.80060761046752]
ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。
この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。
RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。
本稿では、近年のローワークの動機付けについて述べる。
論文 参考訳(メタデータ) (2020-08-18T04:46:22Z) - A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix
Completion [60.52730146391456]
そこで我々は,適応的かつ音質の高い"核フロベニウスノルム"と呼ばれる新しい非スケーラブルな低ランク正規化器を提案する。
特異値の計算をバイパスし、アルゴリズムによる高速な最適化を可能にする。
既存の行列学習手法では最速でありながら、最先端の回復性能が得られる。
論文 参考訳(メタデータ) (2020-08-14T18:47:58Z) - Ideal formulations for constrained convex optimization problems with
indicator variables [2.578242050187029]
本研究では,指標変数と指標に対する制約を用いた凸最適化問題のクラスを凸化することを検討した。
スパース回帰問題の凸化に関する従来の研究とは異なり、非線形非分離対象、指標変数、制約を同時に検討する。
階層性,多行性,空間性制約といった問題に対する理想的な凸化を導出する。
論文 参考訳(メタデータ) (2020-06-30T21:07:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。