論文の概要: Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity

• arxiv url: http://arxiv.org/abs/2204.07526v2
• Date: Sat, 20 Jan 2024 20:00:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-24 00:24:59.556687
• Title: Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity
• Title（参考訳）: テンソルPCAにおける統計計算トレードオフと通信複雑度による関連問題
• Authors: Rishabh Dudeja and Daniel Hsu
• Abstract要約: 本稿では,PCAにおける通信複雑性を用いたメモリバウンドアルゴリズムの実行時間に対する計算的低バウンドを導出する。 下限は反復時間アルゴリズムを除外しないが、勾配降下法やパワー法のような多くのよく使われるアルゴリズムは、サンプルサイズが十分に大きくない場合、より高いカウントを持つ必要があることを示唆している。
• 参考スコア（独自算出の注目度）: 19.939448881052453
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tensor PCA is a stylized statistical inference problem introduced by Montanari and Richard to study the computational difficulty of estimating an unknown parameter from higher-order moment tensors. Unlike its matrix counterpart, Tensor PCA exhibits a statistical-computational gap, i.e., a sample size regime where the problem is information-theoretically solvable but conjectured to be computationally hard. This paper derives computational lower bounds on the run-time of memory bounded algorithms for Tensor PCA using communication complexity. These lower bounds specify a trade-off among the number of passes through the data sample, the sample size, and the memory required by any algorithm that successfully solves Tensor PCA. While the lower bounds do not rule out polynomial-time algorithms, they do imply that many commonly-used algorithms, such as gradient descent and power method, must have a higher iteration count when the sample size is not large enough. Similar lower bounds are obtained for Non-Gaussian Component Analysis, a family of statistical estimation problems in which low-order moment tensors carry no information about the unknown parameter. Finally, stronger lower bounds are obtained for an asymmetric variant of Tensor PCA and related statistical estimation problems. These results explain why many estimators for these problems use a memory state that is significantly larger than the effective dimensionality of the parameter of interest.
• Abstract（参考訳）: テンソルpca(tensor pca)は、モンタナリとリチャードが高次モーメントテンソルから未知のパラメータを推定する計算の難しさを研究するために導入した定式化された統計推論問題である。 行列と異なり、Tensor PCAは統計計算のギャップ、すなわち、問題は情報理論的に解けるが計算的に難しいと推測されるサンプルサイズ状態を示す。 本稿では,通信複雑性を用いたテンソルpcaのメモリ有界アルゴリズムの実行時の計算下限を導出する。 これらの下位境界は、データサンプルのパス数、サンプルサイズ、テンソルPCAの解決に成功するアルゴリズムに必要なメモリ間のトレードオフを規定している。 下限は多項式時間アルゴリズムを除外しないが、勾配降下やパワー法のような多くのよく使われるアルゴリズムは、サンプルサイズが十分でない場合、イテレーション数が高くなければならないことを暗示している。 低次モーメントテンソルが未知のパラメータに関する情報を持たない統計量推定問題である非ガウス成分分析において、同様の下限が得られる。 最後に、テンソルPCAの非対称変種と関連する統計的推定問題に対して、より強い下界を求める。 これらの結果は、多くの推定者が興味のあるパラメータの有効次元よりもはるかに大きいメモリ状態を使用する理由を説明する。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Quasi-Newton Updating for Large-Scale Distributed Learning [0.32228025627337864]
  統計的,計算,通信効率に優れた分散準ニュートン(DQN)フレームワークを開発した。 DQN法ではヘッセン行列の逆転や通信は不要である。 理論上, 得られた推定量は, 軽度条件下での少数の反復に対して統計的に効率的であることを示す。
  論文  参考訳（メタデータ） (2023-06-07T02:33:20Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  ガウスのプロセスはデータセットのサイズとともに違法にスケールする。 多くの近似法が開発されており、必然的に近似誤差を導入している。 この余分な不確実性の原因は、計算が限られているため、近似後部を使用すると完全に無視される。 本研究では,観測された有限個のデータと有限個の計算量の両方から生じる組合せ不確実性を一貫した推定を行う手法の開発を行う。
  論文  参考訳（メタデータ） (2022-05-30T22:16:25Z)
• Stochastic Approximation for Online Tensorial Independent Component Analysis [98.34292831923335]
  独立成分分析(ICA)は統計機械学習や信号処理において一般的な次元削減ツールである。 本稿では,各独立成分を推定する副産物オンライン時系列アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-28T18:52:37Z)
• Statistical and computational thresholds for the planted $k$-densest sub-hypergraph problem [13.808053718325635]
  我々は,$d$-uniform ハイパーグラフ上に$k$-densest サブハイパーグラフを植え付けることで回復する問題を考察する。 この根本的な問題は、例えば、コミュニティの検出、平均ケースの複雑さ、神経科学の応用など、様々な文脈に現れる。
  論文  参考訳（メタデータ） (2020-11-23T16:02:12Z)
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
  我々は,高次元仮説テストの文脈において,最も普及している2つの制限された計算モデル,統計クエリフレームワークと低次コローラについて検討した。 テスト問題に関する穏やかな条件下では、2種類のアルゴリズムは本質的にはパワーで等価である。 提案手法では, スパースPCA, テンソルPCA, および植木クリッド問題のいくつかの変種に対して, 新たな統計的クエリローバウンドを求める。
  論文  参考訳（メタデータ） (2020-09-13T22:55:18Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits [9.427635404752936]
  我々は2つのクラスタリングモデル、定数高階クラスタリング(CHC)とランク1高階クラスタリング(ROHC)に焦点を当てる。 我々は,CHCとROHCの検出/回復が統計的に可能である信号対雑音比の境界を同定する。 信号対雑音比がしきい値以上である場合に、信頼性の高い検出と回復を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-21T15:53:44Z)
• An Optimal Statistical and Computational Framework for Generalized Tensor Estimation [10.899518267165666]
  本稿では,低ランクテンソル推定問題に対するフレキシブルなフレームワークについて述べる。 計算画像、ゲノミクス、ネットワーク解析の応用から多くの重要な例を含む。
  論文  参考訳（メタデータ） (2020-02-26T01:54:35Z)

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

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