論文の概要: Tensor Estimation with Nearly Linear Samples Given Weak Side Information
- arxiv url: http://arxiv.org/abs/2007.00736v2
- Date: Fri, 10 Sep 2021 19:42:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-14 22:55:35.810137
- Title: Tensor Estimation with Nearly Linear Samples Given Weak Side Information
- Title(参考訳): 弱側情報に基づく近似線形標本を用いたテンソル推定
- Authors: Christina Lee Yu
- Abstract要約: 弱側情報はサンプルを$O(n)$に減らすのに十分であることを示す。
我々は、この側情報を利用して、任意の小さな定数$kappa > 0$に対して$O(n1+kappa)$サンプルを持つ一貫した推定子を生成するアルゴリズムを提供する。
- 参考スコア(独自算出の注目度): 4.264192013842096
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Tensor completion exhibits an interesting computational-statistical gap in
terms of the number of samples needed to perform tensor estimation. While there
are only $\Theta(tn)$ degrees of freedom in a $t$-order tensor with $n^t$
entries, the best known polynomial time algorithm requires $O(n^{t/2})$ samples
in order to guarantee consistent estimation. In this paper, we show that weak
side information is sufficient to reduce the sample complexity to $O(n)$. The
side information consists of a weight vector for each of the modes which is not
orthogonal to any of the latent factors along that mode; this is significantly
weaker than assuming noisy knowledge of the subspaces. We provide an algorithm
that utilizes this side information to produce a consistent estimator with
$O(n^{1+\kappa})$ samples for any small constant $\kappa > 0$.
- Abstract(参考訳): テンソル完了はテンソル推定に必要なサンプルの数の観点から興味深い計算統計的ギャップを示す。
$t$-次テンソルには$\Theta(tn)$自由度しか存在しないが、最もよく知られている多項式時間アルゴリズムは、一貫した推定を保証するために$O(n^{t/2})$サンプルを必要とする。
本稿では,サンプルの複雑さを$O(n)$に抑えるために,弱い側情報が十分であることを示す。
サイド情報は、各モードの重みベクトルからなり、そのモードに沿った潜在因子のいずれかと直交しない。
このサイド情報を利用して、小さな定数 $\kappa > 0$ に対して、$o(n^{1+\kappa})$ の一貫した推定値を生成するアルゴリズムを提供する。
関連論文リスト
- 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) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Robust Sparse Mean Estimation via Incremental Learning [15.536082641659423]
そこで本研究では, 部分的に破損したサンプルの集合から, k$-sparse平均を推定することを目的とする, 頑健な平均推定問題について検討する。
両課題を適度な条件下で克服する簡易平均推定器を提案する。
私たちのメソッドは、スパーシティレベル$k$に関する事前の知識を必要としない。
論文 参考訳(メタデータ) (2023-05-24T16:02:28Z) - On the Accuracy of Hotelling-Type Tensor Deflation: A Random Tensor
Analysis [16.28927188636617]
階数-$r$ の $sum_i=1r beta_i A_i + W$ の非対称スパイクモデルを考える。
本研究では, ホテルリング型デフレに関する研究を行った。
論文 参考訳(メタデータ) (2022-11-16T16:01:56Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳(メタデータ) (2022-11-10T00:40:37Z) - Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。
我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文 参考訳(メタデータ) (2022-09-09T23:35:25Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [48.07596965953344]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に,m = (klog(n))O(t)/alpha と m = (klog(n))O(t)/alpha と、m = (mnt)$ と、m = (klog(n))O(t)/alpha と、m = (1/alpha)O (1/t)$ の誤差を達成する。
論文 参考訳(メタデータ) (2022-06-10T17:38:18Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳(メタデータ) (2022-03-28T23:53:48Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳(メタデータ) (2022-03-18T18:50:52Z) - The Complexity of Sparse Tensor PCA [1.90365714903665]
1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。
PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
論文 参考訳(メタデータ) (2021-06-11T10:57:00Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。