論文の概要: Linear-Sample Learning of Low-Rank Distributions

• arxiv url: http://arxiv.org/abs/2010.00064v1
• Date: Wed, 30 Sep 2020 19:10:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-12 23:27:42.321540
• Title: Linear-Sample Learning of Low-Rank Distributions
• Title（参考訳）: 低ランク分布の線形サンプル学習
• Authors: Ayush Jain, Alon Orlitsky
• Abstract要約: ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 56.59844655107251
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many latent-variable applications, including community detection, collaborative filtering, genomic analysis, and NLP, model data as generated by low-rank matrices. Yet despite considerable research, except for very special cases, the number of samples required to efficiently recover the underlying matrices has not been known. We determine the onset of learning in several common latent-variable settings. For all of them, we show that learning $k\times k$, rank-$r$, matrices to normalized $L_{1}$ distance $\epsilon$ requires $\Omega(\frac{kr}{\epsilon^2})$ samples, and propose an algorithm that uses ${\cal O}(\frac{kr}{\epsilon^2}\log^2\frac r\epsilon)$ samples, a number linear in the high dimension, and nearly linear in the, typically low, rank. The algorithm improves on existing spectral techniques and runs in polynomial time. The proofs establish new results on the rapid convergence of the spectral distance between the model and observation matrices, and may be of independent interest.
• Abstract（参考訳）: コミュニティ検出、コラボレーティブフィルタリング、ゲノム解析、NLPなど、多くの潜在変数アプリケーションは、低ランク行列によって生成されたモデルデータである。 しかし、非常に特殊なケースを除いて、基礎となるマトリックスを効率的に回収するために必要なサンプルの数は分かっていない。 いくつかの一般的な潜在変数設定で学習の開始を決定する。 それらすべてについて、$k\times k$, rank-$r$, matrices to normalized $l_{1}$ distance $\epsilon$ requires $\omega(\frac{kr}{\epsilon^2})$ sample を学習し、${\cal o}(\frac{kr}{\epsilon^2}\log^2\frac r\epsilon)$ sample, a number linear in the high dimension, but almost linear in the low, rank を用いるアルゴリズムを提案する。 このアルゴリズムは既存のスペクトル技術を改善し、多項式時間で走る。 これらの証明は、モデルと観測行列の間のスペクトル距離の急速な収束に関する新しい結果を確立し、独立した興味を持つかもしれない。

関連論文リスト

• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
  疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。 我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
  論文  参考訳（メタデータ） (2024-02-21T19:55:01Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Dictionary Learning for the Almost-Linear Sparsity Regime [0.0]
  辞書学習は、信号処理やデータ科学における応用においてますます重要になっている。 SPORADIC (SPectral ORAcle DICtionary Learning) は、重み付けされた共分散行列の族に対する効率的なスペクトル法である。 高次元において、SPORADICはよく知られた制限等尺性(RIP)を満たす過剰完備(K > M$)辞書を復元できることを示す。 これらの精度保証は、未知のスパースベクトル $mathbfx_i$ の支持と符号が、高い確率で正確に復元され、任意に閉じることができるような「オラクル特性」を持つ。
  論文  参考訳（メタデータ） (2022-10-19T19:35:50Z)
• Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing [9.264464791978362]
  Alternating Least Squares (ALS) は $O(log n + log (1/varepsilon)) $ iterations において $varepsilon$-accuracy で真の解に収束することを示す。 我々の証明の鍵となるのは、ALSの軌道が反復する観察は、ランダムな測定行列の特定のエントリのみに非常に軽度に依存することである。
  論文  参考訳（メタデータ） (2022-04-25T08:55:38Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。 最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-30T10:42:48Z)
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices [23.15629681360836]
  雑音線形観測から係数ベクトル$x_0$ in$RN$を学習する問題を考察する。 平均二乗誤差に対する明示的な式を厳密に導出する。 我々の予測は、非常に適度なサイズであっても、数値と非常によく一致していることを示す。
  論文  参考訳（メタデータ） (2020-02-11T13:43:32Z)

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

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