論文の概要: Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm

• arxiv url: http://arxiv.org/abs/2201.13052v1
• Date: Mon, 31 Jan 2022 08:20:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-01 18:23:29.258501
• Title: Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm
• Title（参考訳）: 帰納行列の完全性:悪質な局所的最小化と高速アルゴリズム
• Authors: Pini Zilber and Boaz Nadler
• Abstract要約: 帰納的行列完備化(IMC)問題に3つの貢献をする。 まず、適切な条件下では、IMC最適化のランドスケープが悪い局所最小値を持たないことを証明する。 第二に、未知行列のランクを推定する理論的保証を持つ単純なスキームを導出する。 第3に、IMC問題を解決するシンプルなガウスニュートン法であるGNIMCを提案する。
• 参考スコア（独自算出の注目度）: 4.997371967242497
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The inductive matrix completion (IMC) problem is to recover a low rank matrix from few observed entries while incorporating prior knowledge about its row and column subspaces. In this work, we make three contributions to the IMC problem: (i) we prove that under suitable conditions, the IMC optimization landscape has no bad local minima; (ii) we derive a simple scheme with theoretical guarantees to estimate the rank of the unknown matrix; and (iii) we propose GNIMC, a simple Gauss-Newton based method to solve the IMC problem, analyze its runtime and derive recovery guarantees for it. The guarantees for GNIMC are sharper in several aspects than those available for other methods, including a quadratic convergence rate, fewer required observed entries and stability to errors or deviations from low-rank. Empirically, given entries observed uniformly at random, GNIMC recovers the underlying matrix substantially faster than several competing methods.
• Abstract（参考訳）: 帰納行列補完(inductive matrix completion, imc)問題は、少数の観測されたエントリから低ランク行列を回収し、その行と列部分空間に関する事前知識を取り入れることである。 本稿では,IMC問題への3つの貢献について述べる。 i) 適切な条件下では、IMC最適化のランドスケープは、悪い局所最小値を持たないことを証明する。 (ii)未知行列の階数を推定するための理論的な保証を伴う単純なスキームを導出する。 (iii) imc問題を解決するための単純なガウスニュートン法であるgnimcを提案し,そのランタイムを分析し,それに対する回復保証を導出する。 GNIMCの保証は、二次収束率、必要な項目の少なさ、エラーに対する安定性、低ランクからの偏差など、他の方法よりもいくつかの面でシャープである。 実験的に、ランダムに一様に観察されたエントリに対して、GNIMCは、基礎となる行列をいくつかの競合する手法よりもかなり高速に回復する。

関連論文リスト

• Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion [14.542166904874147]
  similarity Completion Matrixは多くの機械学習タスクの中核にある基本的なツールとして機能する。 この問題に対処するために、類似行列理論(SMC)法が提案されているが、それらは複雑である。 提案手法は,PSD特性を解析して推定プロセスを導出し,低ランク解を保証するために非低ランク正規化器を組み込む2つの新しい,スケーラブルで効果的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-29T04:27:23Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion [15.128477070895055]
  本稿では,Majorization-Minimization Gauss-Newton (MMGN) と呼ばれる新しい1ビット行列補完法を提案する。 本手法は,元の最適化問題を標準的な低ランク行列補完問題に変換する偏極最小化原理に基づく。
  論文  参考訳（メタデータ） (2023-04-27T03:16:52Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• Stability and Generalization for Markov Chain Stochastic Gradient Methods [49.981789906200035]
  本稿では,最小化問題と最小化問題の両方に対して,MC-SGMの包括的一般化解析を行う。 我々はスムーズかつ非スムーズなケースに対して最適な過剰人口リスク境界を確立する。 コンベックス・コンケーブ問題に対する最初期のほぼ最適な収束率を期待と高い確率で開発する。
  論文  参考訳（メタデータ） (2022-09-16T15:42:51Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number [34.0533596121548]
  データ科学における多くの問題は、高度に不完全で、時には腐敗した観測から低いランクを推定するものとして扱われる。 1つの一般的なアプローチは行列分解に頼り、低ランク行列因子は滑らかな損失に対して一階法によって最適化される。
  論文  参考訳（メタデータ） (2020-10-26T06:21:14Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。 この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。 RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。 本稿では、近年のローワークの動機付けについて述べる。
  論文  参考訳（メタデータ） (2020-08-18T04:46:22Z)
• SimpleMKKM: Simple Multiple Kernel K-means [49.500663154085586]
  単純なマルチカーネルk-means(SimpleMKKM)と呼ばれる,単純で効果的なマルチカーネルクラスタリングアルゴリズムを提案する。 我々の基準は、カーネル係数とクラスタリング分割行列における難解な最小化最大化問題によって与えられる。 クラスタリング一般化誤差の観点から,SimpleMKKMの性能を理論的に解析する。
  論文  参考訳（メタデータ） (2020-05-11T10:06:40Z)

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

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