論文の概要: Fast and Minimax Optimal Estimation of Low-Rank Matrices via Non-Convex
Gradient Descent
- arxiv url: http://arxiv.org/abs/2305.17224v1
- Date: Fri, 26 May 2023 19:32:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 21:15:24.446775
- Title: Fast and Minimax Optimal Estimation of Low-Rank Matrices via Non-Convex
Gradient Descent
- Title(参考訳): 非凸勾配降下による低ランク行列の高速・最小最適推定
- Authors: Gavin Zhang, Hong-Ming Chiu, Richard Y. Zhang
- Abstract要約: 雑音測定から低ランク行列を推定する問題は、極小誤差を達成するという特定の目的を持っている。
本稿では,最小限の最適性を確実に保ちながら,収束の遅い問題を修復するアルゴリズムを提案する。
提案アルゴリズムを用いて医用イメージングアプリケーションと,それ以前のアプローチについて検討した。
- 参考スコア(独自算出の注目度): 10.65673380743972
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of estimating a low-rank matrix from noisy measurements,
with the specific goal of achieving minimax optimal error. In practice, the
problem is commonly solved using non-convex gradient descent, due to its
ability to scale to large-scale real-world datasets. In theory, non-convex
gradient descent is capable of achieving minimax error. But in practice, it
often converges extremely slowly, such that it cannot even deliver estimations
of modest accuracy within reasonable time. On the other hand, methods that
improve the convergence of non-convex gradient descent, through rescaling or
preconditioning, also greatly amplify the measurement noise, resulting in
estimations that are orders of magnitude less accurate than what is
theoretically achievable with minimax optimal error. In this paper, we propose
a slight modification to the usual non-convex gradient descent method that
remedies the issue of slow convergence, while provably preserving its minimax
optimality. Our proposed algorithm has essentially the same per-iteration cost
as non-convex gradient descent, but is guaranteed to converge to minimax error
at a linear rate that is immune to ill-conditioning. Using our proposed
algorithm, we reconstruct a 60 megapixel dataset for a medical imaging
application, and observe significantly decreased reconstruction error compared
to previous approaches.
- Abstract(参考訳): 本研究では,ミニマックス最適誤差の達成を目的とし,ノイズ測定から低ランク行列を推定する問題について検討する。
実際には、この問題は大規模な実世界のデータセットにスケールできるため、非凸勾配勾配降下を用いて一般に解決される。
理論上、非凸勾配降下はミニマックス誤差を達成することができる。
しかし実際には、しばしば非常にゆっくりと収束し、適度な時間内に控えめな精度の見積もりをすることさえできない。
一方、再スケーリングやプリコンディショニングによる非凸勾配降下の収束性を改善する手法は、測定ノイズを大きく増幅し、理論上はminimax最適誤差で達成可能なものよりも桁違いに精度の低い推定となる。
本稿では,最小限の最適性を維持しつつ,収束の遅い問題を解消する通常の非凸勾配降下法を若干修正することを提案する。
提案アルゴリズムは,非凸勾配降下法と基本的に同一の点定コストを有するが,線形速度でミニマックス誤差に収束することが保証されている。
提案アルゴリズムを用いて,60メガピクセルの医用画像用データセットを再構成し,従来の手法に比べて大幅な再構成誤差の低減を図った。
関連論文リスト
- Using non-convex optimization in quantum process tomography: Factored
gradient descent is tough to beat [11.893324664457552]
我々のアルゴリズムは、設定と雑音耐性の両面において、アートを述べるよりも早く収束し、高い忠実性を達成する。
我々のアルゴリズムは、設定と雑音耐性の両面において、より高速に収束し、技術よりも高い忠実性を達成する。
論文 参考訳(メタデータ) (2023-12-03T07:44:17Z) - Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled
Gradient Descent, Even with Overparameterization [48.65416821017865]
この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。
低ランク物体の条件数に依存しない定数速度で直線的に収束する。
様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
論文 参考訳(メタデータ) (2023-10-09T21:16:57Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳(メタデータ) (2023-06-02T04:21:59Z) - Limitations of Information-Theoretic Generalization Bounds for Gradient
Descent Methods in Stochastic Convex Optimization [48.12845778927164]
凸最適化の設定において,勾配勾配降下の最小値設定の見通しを考察する。
勾配法の研究においてよく用いられる手法として、最終回はガウス雑音によって劣化し、ノイズの多い「代理」アルゴリズムが生成される。
以上の結果から,情報理論を用いた勾配降下解析には新たな考え方が必要であることが示唆された。
論文 参考訳(メタデータ) (2022-12-27T17:16:48Z) - Computationally Efficient and Statistically Optimal Robust Low-rank
Matrix and Tensor Estimation [15.389011827844572]
低ランク線形収縮推定法では, どちらも統計的に困難である。
本稿では,計算効率だけでなく,統計的に最適である新しいサブオリエント(RsGrad)を提案する。
論文 参考訳(メタデータ) (2022-03-02T09:05:15Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Near-optimal inference in adaptive linear regression [60.08422051718195]
最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。
我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。
我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
論文 参考訳(メタデータ) (2021-07-05T21:05:11Z) - An Optimal Multistage Stochastic Gradient Method for Minimax Problems [8.615625517708324]
滑らかかつ強凸な凹凸配置におけるミニマックス最適化問題について検討する。
まず, 定常ステップサイズでグラディエントDescent Ascent (GDA) 法を解析した。
本稿では,学習速度の減衰スケジュールを多段階に設定した多段階型GDAを提案する。
論文 参考訳(メタデータ) (2020-02-13T18:01:18Z) - Support recovery and sup-norm convergence rates for sparse pivotal
estimation [79.13844065776928]
高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。
非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
論文 参考訳(メタデータ) (2020-01-15T16:11:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。