論文の概要: Escaping Saddle Points in Ill-Conditioned Matrix Completion with a
Scalable Second Order Method
- arxiv url: http://arxiv.org/abs/2009.02905v1
- Date: Mon, 7 Sep 2020 06:51:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-21 03:36:40.669437
- Title: Escaping Saddle Points in Ill-Conditioned Matrix Completion with a
Scalable Second Order Method
- Title（参考訳）: スケーラブルな第2次手法による不条件行列補完における鞍点のエスケープ
- Authors: Christian K\"ummerle, Claudio M. Verdun
- Abstract要約: 低ランク行列に対する反復アルゴリズムを提案する。
多くの最先端の手法とは異なり、我々の手法は少数のサンプルから最大10ドルの条件数で非常に不調な条件を満たすことができることを示す数値実験で示している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an iterative algorithm for low-rank matrix completion that can be
interpreted as both an iteratively reweighted least squares (IRLS) algorithm
and a saddle-escaping smoothing Newton method applied to a non-convex rank
surrogate objective. It combines the favorable data efficiency of previous IRLS
approaches with an improved scalability by several orders of magnitude. Our
method attains a local quadratic convergence rate already for a number of
samples that is close to the information theoretical limit. We show in
numerical experiments that unlike many state-of-the-art approaches, our
approach is able to complete very ill-conditioned matrices with a condition
number of up to $10^{10}$ from few samples.
- Abstract（参考訳）: 本研究では,irlsアルゴリズムと非凸ランクサーロゲート目的に適用したサドルエスケープ平滑化ニュートン法の両方として解釈可能な,低ランク行列補完のための反復アルゴリズムを提案する。
これは、以前のIRLSアプローチの好ましいデータ効率と、数桁のスケーラビリティの改善を組み合わせたものです。
本手法は, 情報理論上の限界に近いサンプル数に対して, 既に局所二次収束率を達成する。
数値実験では, 現状の多くの手法と異なり, 条件数10^{10}$の極めて条件の悪い行列を, 少数のサンプルから解くことが可能であることが示されている。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Recovering Simultaneously Structured Data via Non-Convex Iteratively
Reweighted Least Squares [0.8702432681310401]
線形観測から多種多様低次元構造に固執するデータを復元する新しいアルゴリズムを提案する。
IRLS法は,低/複合状態の計測に好適であることを示す。
論文 参考訳（メタデータ） (2023-06-08T06:35:47Z) - Stochastic Gradient Methods with Preconditioned Updates [47.23741709751474]
このような問題に対するアルゴリズムはいくつかあるが、既存の手法は、スケールが悪く、あるいは条件が悪ければ、しばしばうまく機能しない。
ここではハッチンソンの対角ヘッセン近似のアプローチに基づく前提条件を含む。
我々は滑らかさとPL条件が仮定されるときの収束性を証明する。
論文 参考訳（メタデータ） (2022-06-01T07:38:08Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - A Scalable Second Order Method for Ill-Conditioned Matrix Completion
from Few Samples [0.0]
低ランク行列補完のための反復アルゴリズムを提案する。
ほとんどサンプルから最大10ドルの条件数で、非常に不調な行列を完遂することができる。
論文 参考訳（メタデータ） (2021-06-03T20:31:00Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。