論文の概要: Over-Parametrized Matrix Factorization in the Presence of Spurious
Stationary Points
- arxiv url: http://arxiv.org/abs/2112.13269v1
- Date: Sat, 25 Dec 2021 19:13:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-29 06:51:35.179601
- Title: Over-Parametrized Matrix Factorization in the Presence of Spurious
Stationary Points
- Title（参考訳）: スプリアス定常点の存在下での過パラメータ行列分解
- Authors: Armin Eftekhari
- Abstract要約: この研究は、過度にパラメータ化された行列分解の計算的側面について考察する。
本研究では,対応する有理関数の勾配流が大域最小化器に収束することを確かめる。
原始双対アルゴリズムにインスパイアされた勾配流の離散化がランダムに成功したことを数値的に観察する。
- 参考スコア（独自算出の注目度）: 20.515985046189268
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by the emerging role of interpolating machines in signal processing
and machine learning, this work considers the computational aspects of
over-parametrized matrix factorization. In this context, the optimization
landscape may contain spurious stationary points (SSPs), which are proved to be
full-rank matrices. The presence of these SSPs means that it is impossible to
hope for any global guarantees in over-parametrized matrix factorization. For
example, when initialized at an SSP, the gradient flow will be trapped there
forever. Nevertheless, despite these SSPs, we establish in this work that the
gradient flow of the corresponding merit function converges to a global
minimizer, provided that its initialization is rank-deficient and sufficiently
close to the feasible set of the optimization problem. We numerically observe
that a heuristic discretization of the proposed gradient flow, inspired by
primal-dual algorithms, is successful when initialized randomly. Our result is
in sharp contrast with the local refinement methods which require an
initialization close to the optimal set of the optimization problem. More
specifically, we successfully avoid the traps set by the SSPs because the
gradient flow remains rank-deficient at all times, and not because there are no
SSPs nearby. The latter is the case for the local refinement methods. Moreover,
the widely-used restricted isometry property plays no role in our main result.
- Abstract（参考訳）: 信号処理や機械学習における補間機械の役割の台頭により、過度にパラメータ化された行列分解の計算的側面を考える。
この文脈では、最適化のランドスケープは、フルランク行列であることが証明された突発的な定常点(SSP)を含むかもしれない。
これらの SSP の存在は、過度にパラメータ化された行列分解における大域的な保証を期待することは不可能であることを意味する。
例えば、SSPで初期化されると、勾配流は永遠にそこに閉じ込められる。
にもかかわらず、これらのsspsにもかかわらず、この研究では、対応するメリット関数の勾配フローが大域的最小化に収束することを確立し、その初期化がランク不足であり、最適化問題の実現可能な集合に十分近いことを仮定する。
原始双対アルゴリズムにインスパイアされた勾配流のヒューリスティックな離散化がランダムに初期化されると成功することを数値的に観察する。
その結果,最適化問題の最適集合に近い初期化を必要とする局所的改良法とは対照的である。
より具体的には、SSPが設定したトラップは、勾配流が常にランク不足であり、近くにSSPがないためではないため、うまく回避できる。
後者は局所的改良法の場合である。
さらに、広く使われている制限等尺性は、本研究の主な成果には何の役割も果たさない。
関連論文リスト
- Implicit regularization in AI meets generalized hardness of
approximation in optimization -- Sharp results for diagonal linear networks [0.0]
直交線形ネットワークの勾配流による暗黙の正規化について, 鋭い結果を示す。
これを近似の一般化硬度における相転移現象と関連付ける。
結果の非シャープ性は、基礎追従最適化問題に対して、GHA現象が起こらないことを意味する。
論文 参考訳（メタデータ） (2023-07-13T13:27:51Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Convergence of the mini-batch SIHT algorithm [0.0]
Iterative Hard Thresholding (IHT)アルゴリズムはスパース最適化の効果的な決定論的アルゴリズムとして広く検討されている。
スパースミニバッチSIHTが生成したシーケンスはスーパーマーチンゲールシーケンスであり、確率1と収束することを示す。
論文 参考訳（メタデータ） (2022-09-29T03:47:46Z) - Optimization on manifolds: A symplectic approach [127.54402681305629]
本稿では、最適化問題を解くための一般的な枠組みとして、ディラックの制約付きハミルトン系理論の散逸拡張を提案する。
我々の(加速された)アルゴリズムのクラスは単純で効率的なだけでなく、幅広い文脈にも適用できる。
論文 参考訳（メタデータ） (2021-07-23T13:43:34Z) - Small random initialization is akin to spectral learning: Optimization
and generalization guarantees for overparameterized low-rank matrix
reconstruction [35.585697639325105]
本稿では,小さなランダム初期化が完全には理解されていないことを示す。
我々は、小さな乱数行列から勾配を再構成し、低い乱数行列から最適勾配に類似した解を求める。
論文 参考訳（メタデータ） (2021-06-28T22:52:39Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - A Dynamical Systems Approach for Convergence of the Bayesian EM
Algorithm [59.99439951055238]
我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。
本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。
高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
論文 参考訳（メタデータ） (2020-06-23T01:34:18Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳（メタデータ） (2020-03-31T16:54:22Z) - Stochastic Zeroth-order Riemannian Derivative Estimation and
Optimization [15.78743548731191]
多様体非線型性の非線型性の難しさを克服するために、ガウス滑らか化関数のオラクル版を提案する。
ニューラルネットワークに対するロボティクスとブラックボックス攻撃に対するブラックボックス剛性制御における,結果によるアルゴリズムの適用性と実世界の応用を実証する。
論文 参考訳（メタデータ） (2020-03-25T06:58:19Z) - Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart
for Nonconvex Optimization [73.38702974136102]
アルゴリズムの高速化のために,パラメータ再起動方式が提案されている。
本論文では,非滑らかな問題を解くアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:06:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。