論文の概要: Noisy Low-rank Matrix Optimization: Geometry of Local Minima and
Convergence Rate
- arxiv url: http://arxiv.org/abs/2203.03899v1
- Date: Tue, 8 Mar 2022 07:44:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-09 14:20:28.034288
- Title: Noisy Low-rank Matrix Optimization: Geometry of Local Minima and
Convergence Rate
- Title（参考訳）: 雑音の多い低ランク行列最適化:局所最小値と収束速度の幾何学
- Authors: Ziye Ma, Somayeh Sojoudi
- Abstract要約: 本稿では,機械学習における多種多様な応用を見出した低ランク行列最適化について述べる。
雑音モデルが任意である一般目的関数に対するランダムな汚職に対処できるフレームワークを開発する。
RIP定数が1/3$以上である場合、地平線付近の局所領域における問題の急激な局所最小値の幾何学を特徴付ける。
- 参考スコア（独自算出の注目度）: 14.191310794366075
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper is concerned with low-rank matrix optimization, which has found a
wide range of applications in machine learning. This problem in the special
case of matrix sense has been studied extensively through the notion of
Restricted Isometry Property (RIP), leading to a wealth of results on the
geometric landscape of the problem and the convergence rate of common
algorithms. However, the existing results are not able to handle the problem
with a general objective function subject to noisy data. In this paper, we
address this problem by developing a mathematical framework that can deal with
random corruptions to general objective functions, where the noise model is
arbitrary. We prove that as long as the RIP constant of the noiseless objective
is less than $1/3$, any spurious local solution of the noisy optimization
problem must be close to the ground truth solution. By working through the
strict saddle property, we also show that an approximate solution can be found
in polynomial time. We characterize the geometry of the spurious local minima
of the problem in a local region around the ground truth in the case when the
RIP constant is greater than $1/3$. This paper offers the first set of results
on the global and local optimization landscapes of general low-rank
optimization problems under arbitrary random corruptions.
- Abstract（参考訳）: 本稿では,機械学習における多種多様な応用を見出した低ランク行列最適化について述べる。
行列感覚の特別な場合におけるこの問題は、制限等長性(rip)の概念を通じて広く研究され、問題の幾何学的景観と一般的なアルゴリズムの収束率に多くの結果をもたらした。
しかし,既存の結果ではノイズデータに基づく汎用関数では問題に対処できない。
本稿では,雑音モデルが任意である一般目的関数に対するランダムな汚職に対処できる数学的枠組みを開発することにより,この問題に対処する。
雑音のない対象の RIP 定数が 1/3$ 未満である限り、雑音の多い最適化問題の任意の急激な局所解は、基底真理解に近くなければならない。
また,厳密な鞍の性質を通すことにより,近似解が多項式時間で見つかることを示した。
我々は RIP 定数が 1/3$ を超える場合において, 基底真理付近の局所領域における問題の急激な局所最小値の幾何学を特徴付ける。
本稿では,ランダムな腐敗下での一般低ランク最適化問題に対する大域的および局所的最適化の展望に関する最初の結果について述べる。
関連論文リスト
- Characterization of Locality in Spin States and Forced Moves for
Optimizations [0.36868085124383626]
最適化問題において、エネルギーランドスケープにおける局所最小値の存在は、世界最小値を求めるために問題となる。
そこで我々は,局所最小値から効率よく抜け出すアルゴリズムを開発したが,正確なサンプリングは得られなかった。
提案アルゴリズムはリジェクションフリーなアルゴリズムに基づいているため,計算コストは低い。
論文 参考訳（メタデータ） (2023-12-05T07:21:00Z) - Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。
この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文 参考訳（メタデータ） (2023-11-04T11:12:24Z) - Run Time Analysis for Random Local Search on Generalized Majority
Functions [1.0965065178451106]
我々は、その性質の1つ、中立性がランダムな局所探索の実行時間にどのように影響するかを研究する。
我々は、多くの最適化アルゴリズムに適用可能な定理を提案し、MAJORITYの実行時間と対称バージョンHASMAJORITYをリンクする。
論文 参考訳（メタデータ） (2022-04-27T08:40:33Z) - Distributed stochastic proximal algorithm with random reshuffling for
non-smooth finite-sum optimization [28.862321453597918]
非滑らかな有限サム最小化は機械学習の基本的な問題である。
本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
論文 参考訳（メタデータ） (2021-11-06T07:29:55Z) - Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery
Problems with Corrupted Measurements [18.16299386229588]
一般の低ランク行列回復問題と, 雑音による線形測定を両立させる問題を示す。
任意の RIP 定数を持つ問題に対する局所的な保証を示す。
論文 参考訳（メタデータ） (2021-05-18T02:17:59Z) - Why Do Local Methods Solve Nonconvex Problems? [54.284687261929115]
非使用最適化は、現代の機械学習においてユビキタスである。
機械学習問題の場合、厳格に定式化します。
我々はこの現象の統一的な説明を仮定する。
論文 参考訳（メタデータ） (2021-03-24T19:34:11Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。
本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
論文 参考訳（メタデータ） (2020-04-09T01:45:05Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳（メタデータ） (2020-03-31T16:54:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。