論文の概要: On the computational and statistical complexity of over-parameterized
matrix sensing
- arxiv url: http://arxiv.org/abs/2102.02756v1
- Date: Wed, 27 Jan 2021 04:23:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-13 20:01:59.252570
- Title: On the computational and statistical complexity of over-parameterized
matrix sensing
- Title（参考訳）: 過パラメータマトリクスセンシングの計算的および統計的複雑性について
- Authors: Jiacheng Zhuo, Jeongyeol Kwon, Nhat Ho, Constantine Caramanis
- Abstract要約: FGD法(Factorized Gradient Descend)を用いた低ランク行列検出の解法を検討する。
分解行列 $mathbff$ を分離列空間に分解することにより、$|mathbff_t - mathbff_t - mathbfx*|_f2$ が統計誤差に収束することを示す。
- 参考スコア（独自算出の注目度）: 30.785670369640872
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider solving the low rank matrix sensing problem with Factorized
Gradient Descend (FGD) method when the true rank is unknown and over-specified,
which we refer to as over-parameterized matrix sensing. If the ground truth
signal $\mathbf{X}^* \in \mathbb{R}^{d*d}$ is of rank $r$, but we try to
recover it using $\mathbf{F} \mathbf{F}^\top$ where $\mathbf{F} \in
\mathbb{R}^{d*k}$ and $k>r$, the existing statistical analysis falls short, due
to a flat local curvature of the loss function around the global maxima. By
decomposing the factorized matrix $\mathbf{F}$ into separate column spaces to
capture the effect of extra ranks, we show that $\|\mathbf{F}_t \mathbf{F}_t -
\mathbf{X}^*\|_{F}^2$ converges to a statistical error of $\tilde{\mathcal{O}}
({k d \sigma^2/n})$ after
$\tilde{\mathcal{O}}(\frac{\sigma_{r}}{\sigma}\sqrt{\frac{n}{d}})$ number of
iterations where $\mathbf{F}_t$ is the output of FGD after $t$ iterations,
$\sigma^2$ is the variance of the observation noise, $\sigma_{r}$ is the $r$-th
largest eigenvalue of $\mathbf{X}^*$, and $n$ is the number of sample. Our
results, therefore, offer a comprehensive picture of the statistical and
computational complexity of FGD for the over-parameterized matrix sensing
problem.
- Abstract（参考訳）: 我々は,FGD法を用いて,真のランクが未知かつ過剰に特定された場合の低ランク行列センシング問題を,過パラメータ行列センシング(over-parameterized matrix sensor)と呼ぶ。
基底真理信号 $\mathbf{X}^* \in \mathbb{R}^{d*d}$ が階数 $r$ であるなら、$\mathbf{F} \mathbf{F}^\top$ ここで $\mathbf{F} \in \mathbb{R}^{d*k}$ と $k>r$ を用いてそれを回復しようとするが、既存の統計解析は、大域極大周辺の損失関数の平坦な局所曲率のため、不足する。
By decomposing the factorized matrix $\mathbf{F}$ into separate column spaces to capture the effect of extra ranks, we show that $\|\mathbf{F}_t \mathbf{F}_t\mathbf{X}^*\|_{F}^2$ converges to a statistical error of $\tilde{\mathcal{O}} ({k d \sigma^2/n})$ after $\tilde{\mathcal{O}}(\frac{\sigma_{r}}{\sigma}\sqrt{\frac{n}{d}})$ number of iterations where $\mathbf{F}_t$ is the output of FGD after $t$ iterations, $\sigma^2$ is the variance of the observation noise, $\sigma_{r}$ is the $r$-th largest eigenvalue of $\mathbf{X}^*$, and $n$ is the number of sample.
その結果,超パラメータ行列センシング問題に対するfgdの統計的・計算的複雑性の包括的図式が得られた。
関連論文リスト
- In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting [21.002519159190538]
我々は分散アルゴリズムを解析し、$N$クライアント上で低ランク行列の分解を計算する。
グローバルな$mathbfV$ in $mathbbRd times r$をすべてのクライアントに共通とし、ローカルな$mathbfUi$ in $mathbbRn_itimes r$を得る。
論文 参考訳（メタデータ） (2024-09-13T12:28:42Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳（メタデータ） (2023-10-02T16:44:47Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Beyond Independent Measurements: General Compressed Sensing with GNN
Application [4.924126492174801]
我々は、ノイズコーン観測からmathbbRn$の構造化信号$mathbfxを復元する問題を考察する。
実効的な$mathbfB$は測定値のサロゲートとして用いられる可能性がある。
論文 参考訳（メタデータ） (2021-10-30T20:35:56Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳（メタデータ） (2021-06-27T17:25:24Z) - Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
ノイズの多いサンプルの有限集合から$mathbbRD$の$d$次元部分多様体を推定する問題を検討する。
点推定では$n-frack2k + d$、接空間の推定では$n-frack-12k + d$の収束率を推定する。
論文 参考訳（メタデータ） (2021-05-11T02:29:33Z) - On the Optimal Weighted $\ell_2$ Regularization in Overparameterized
Linear Regression [23.467801864841526]
線形モデル $mathbfy = mathbfX mathbfbeta_star + mathbfepsilon$ with $mathbfXin mathbbRntimes p$ in the overparameterized regime $p>n$ を考える。
予測リスク $mathbbE(y-mathbfxThatmathbfbeta_lambda)2$ in proportional limit $p/n の正確なキャラクタリゼーションを提供する。
論文 参考訳（メタデータ） (2020-06-10T12:38:43Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。