論文の概要: How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?

• arxiv url: http://arxiv.org/abs/2006.06915v2
• Date: Thu, 12 Nov 2020 14:49:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-22 02:31:28.205621
• Title: How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Title（参考訳）: 低ランクマトリクスのリカバリでは、サンプル数に価値がありますか?
• Authors: Gavin Zhang, Richard Y. Zhang
• Abstract要約: 非ランク行列回復問題には、急激な局所最小値が含まれない。 初期推定値の品質とそれに対応するデータ要求量の減少との関係を定量化する。
• 参考スコア（独自算出の注目度）: 12.589519278962378
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a sufficiently large amount of labeled data, the non-convex low-rank matrix recovery problem contains no spurious local minima, so a local optimization algorithm is guaranteed to converge to a global minimum starting from any initial guess. However, the actual amount of data needed by this theoretical guarantee is very pessimistic, as it must prevent spurious local minima from existing anywhere, including at adversarial locations. In contrast, prior work based on good initial guesses have more realistic data requirements, because they allow spurious local minima to exist outside of a neighborhood of the solution. In this paper, we quantify the relationship between the quality of the initial guess and the corresponding reduction in data requirements. Using the restricted isometry constant as a surrogate for sample complexity, we compute a sharp threshold number of samples needed to prevent each specific point on the optimization landscape from becoming a spurious local minimum. Optimizing the threshold over regions of the landscape, we see that for initial points around the ground truth, a linear improvement in the quality of the initial guess amounts to a constant factor improvement in the sample complexity.
• Abstract（参考訳）: 十分な量のラベル付きデータが与えられた場合、非凸低ランク行列回復問題はスプリアス局所極小を含まないため、局所最適化アルゴリズムは任意の初期推定からグローバル最小値に収束することが保証される。 しかし、この理論的な保証によって必要とされる実際のデータ量は非常に悲観的である。 対照的に、良い初期推定に基づく事前の作業は、ソリューションの近傍の外に急激な局所的なミニマの存在を可能にするため、より現実的なデータ要求を持つ。 本稿では,初期推定値の品質とそれに対応するデータ要求量の減少との関係を定量化する。 制限アイソメトリ定数をサンプリング複雑性の代理として用いて,最適化ランドスケープ上の各特定の点が急激な局所最小値になるのを防ぐために必要なサンプルのしきい値を算出する。 ランドスケープの領域に対するしきい値の最適化は、基底真理の周りの初期点に対して、初期推測の品質の線形な改善は、サンプル複雑性の一定の因子改善をもたらすことを見出します。

関連論文リスト

• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• Learning minimal volume uncertainty ellipsoids [1.6795461001108096]
  パラメータ推定問題に対する不確実性領域の学習問題を考察する。 連立ガウスデータの仮定により、最適楕円体が条件平均を中心としていることが証明される。 より実践的な場合、最適楕円体を近似計算するための微分可能な最適化手法を提案する。
  論文  参考訳（メタデータ） (2024-05-03T19:11:35Z)
• Characterization of Locality in Spin States and Forced Moves for Optimizations [0.36868085124383626]
  最適化問題において、エネルギーランドスケープにおける局所最小値の存在は、世界最小値を求めるために問題となる。 そこで我々は,局所最小値から効率よく抜け出すアルゴリズムを開発したが,正確なサンプリングは得られなかった。 提案アルゴリズムはリジェクションフリーなアルゴリズムに基づいているため,計算コストは低い。
  論文  参考訳（メタデータ） (2023-12-05T07:21:00Z)
• Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate [14.191310794366075]
  本稿では,機械学習における多種多様な応用を見出した低ランク行列最適化について述べる。 雑音モデルが任意である一般目的関数に対するランダムな汚職に対処できるフレームワークを開発する。 RIP定数が1/3$以上である場合、地平線付近の局所領域における問題の急激な局所最小値の幾何学を特徴付ける。
  論文  参考訳（メタデータ） (2022-03-08T07:44:47Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  ローカル手法は通信時間を短縮する有望なアプローチの1つである。 局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-12T15:12:17Z)
• Minimax rate of consistency for linear models with missing values [0.0]
  多くの実世界のデータセットでは、複数のソースが集約され、本質的に欠落した情報(センサーの故障、調査における未回答の疑問...)が欠落する。 本稿では,広範に研究された線形モデルに焦点をあてるが,不足する値が存在する場合には,非常に難しい課題であることが判明した。 最終的には、多くの学習タスクを解決し、入力機能の数を指数関数的にすることで、現在の現実世界のデータセットでは予測が不可能になる。
  論文  参考訳（メタデータ） (2022-02-03T08:45:34Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。 非テンション依存データ設定の下で, 各種手法の収束点を求める。
  論文  参考訳（メタデータ） (2022-01-05T15:17:35Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。 本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。 実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
  論文  参考訳（メタデータ） (2020-07-20T12:07:48Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  そこで本研究では,対数様比統計量と正規化フローに基づく新しい分布アライメント手法を提案する。 入力領域の局所構造を保存する領域アライメントにおいて,結果の最小化を実験的に検証する。
  論文  参考訳（メタデータ） (2020-03-26T22:10:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。