論文の概要: Fast and Accurate Estimation of Low-Rank Matrices from Noisy
Measurements via Preconditioned Non-Convex Gradient Descent
- arxiv url: http://arxiv.org/abs/2305.17224v2
- Date: Wed, 28 Feb 2024 04:14:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-29 19:11:36.292870
- Title: Fast and Accurate Estimation of Low-Rank Matrices from Noisy
Measurements via Preconditioned Non-Convex Gradient Descent
- Title(参考訳): 事前条件付き非凸勾配勾配による騒音測定による低ランク行列の高速・高精度推定
- Authors: Gavin Zhang, Hong-Ming Chiu, Richard Y. Zhang
- Abstract要約: 非勾配降下は、雑音測定から低ランクn基底真理行列を推定する一般的な方法である。
本稿では,局所収束を最小限の最適度に加速させるため,雑音測定のためのプレコンディショニングをいかに行うべきかを述べる。
- 参考スコア(独自算出の注目度): 11.74020933567308
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Non-convex gradient descent is a common approach for estimating a low-rank
$n\times n$ ground truth matrix from noisy measurements, because it has
per-iteration costs as low as $O(n)$ time, and is in theory capable of
converging to a minimax optimal estimate. However, the practitioner is often
constrained to just tens to hundreds of iterations, and the slow and/or
inconsistent convergence of non-convex gradient descent can prevent a
high-quality estimate from being obtained. Recently, the technique of
preconditioning was shown to be highly effective at accelerating the local
convergence of non-convex gradient descent when the measurements are noiseless.
In this paper, we describe how preconditioning should be done for noisy
measurements to accelerate local convergence to minimax optimality. For the
symmetric matrix sensing problem, our proposed preconditioned method is
guaranteed to locally converge to minimax error at a linear rate that is immune
to ill-conditioning and/or over-parameterization. Using our proposed
preconditioned method, we perform a 60 megapixel medical image denoising task,
and observe significantly reduced noise levels compared to previous approaches.
- Abstract(参考訳): 非凸勾配降下 (non-convex gradient descent) は、ノイズ測定から低ランクの$n\times n$ ground truth matrixを推定する一般的なアプローチである。
しかし、実践者は数十から数百のイテレーションに制限されることがしばしばあり、非凸勾配勾配勾配の遅いあるいは矛盾しない収束は、高品質な推定値を得るのを防ぐことができる。
近年,無騒音時の非凸勾配降下の局所収束の促進にプリコンディショニング技術が有効であることが示されている。
本稿では, 局所収束を最小化するために, ノイズ測定にプリコンディショニングをいかに行うべきかについて述べる。
対称行列検出問題に対して, 提案手法は, 異常条件や過パラメータ化に応答しない線形速度で, 極小誤差に局所収束することが保証される。
提案手法を用いて,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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。