論文の概要: Average-Case Communication Complexity of Statistical Problems

• arxiv url: http://arxiv.org/abs/2107.01335v1
• Date: Sat, 3 Jul 2021 03:31:37 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-06 14:40:47.213563
• Title: Average-Case Communication Complexity of Statistical Problems
• Title（参考訳）: 統計的問題の平均ケース通信複雑性
• Authors: Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu
• Abstract要約: 通信の複雑さは、ストリーミング、スケッチ、クエリベースのモデルにおける下位境界を証明する主要なツールである。 本稿では,ランダムグラフやマトリクスに植木構造を組み込んだ問題に対して,入力分布を保存する一般還元法を提案する。 我々は,植林した傾斜地を検知・発見するために,二者間・多者間通信の下限を導出する。
• 参考スコア（独自算出の注目度）: 48.03761288397421
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study statistical problems, such as planted clique, its variants, and sparse principal component analysis in the context of average-case communication complexity. Our motivation is to understand the statistical-computational trade-offs in streaming, sketching, and query-based models. Communication complexity is the main tool for proving lower bounds in these models, yet many prior results do not hold in an average-case setting. We provide a general reduction method that preserves the input distribution for problems involving a random graph or matrix with planted structure. Then, we derive two-party and multi-party communication lower bounds for detecting or finding planted cliques, bipartite cliques, and related problems. As a consequence, we obtain new bounds on the query complexity in the edge-probe, vector-matrix-vector, matrix-vector, linear sketching, and $\mathbb{F}_2$-sketching models. Many of these results are nearly tight, and we use our techniques to provide simple proofs of some known lower bounds for the edge-probe model.
• Abstract（参考訳）: 本研究では, 平均ケース通信複雑性の文脈において, 植込み傾斜, 変種, スパース主成分分析などの統計問題について検討する。 私たちの動機は、ストリーミング、スケッチ、クエリベースモデルにおける統計計算上のトレードオフを理解することです。 コミュニケーションの複雑さはこれらのモデルにおける下位境界を証明する主要なツールであるが、多くの先行結果は平均ケース設定では成立しない。 植え付け構造を有するランダムグラフやマトリクスに関する問題に対して、入力分布を保存できる汎用的な還元方法を提供する。 次に,二者間および多者間コミュニケーションの下限を導出して,植栽されたクレーク,二部的なクレーク,および関連する問題を検出し,発見する。 その結果,edge-probe, vector-matrix-vector, matrix-vector, linear sketching, $\mathbb{f}_2$-sketchingモデルにおけるクエリ複雑性の新しい境界が得られる。 これらの結果の多くはほぼ厳密であり、エッジプローブモデルに対する既知の下界の簡単な証明を提供するために我々の手法を用いている。

関連論文リスト

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Entrywise Inference for Missing Panel Data: A Simple and Instance-Optimal Approach [27.301741710016223]
  停滞した採用によって引き起こされたパネルデータの欠落データバージョンに関連する推論的疑問を考察する。 我々は、予め特定されたカバレッジでエントリワイドな信頼区間を構築するためのデータ駆動方式を開発し、分析する。 我々は、欠落したエントリを推定する際に、そのエラーに非漸近的かつ高い確率境界を証明した。
  論文  参考訳（メタデータ） (2024-01-24T18:58:18Z)
• Test Set Sizing Via Random Matrix Theory [91.3755431537592]
  本稿ではランダム行列理論の手法を用いて、単純な線形回帰に対して理想的なトレーニング-テストデータ分割を求める。 それは「理想」を整合性計量を満たすものとして定義し、すなわち経験的モデル誤差は実際の測定ノイズである。 本論文は,任意のモデルのトレーニングとテストサイズを,真に最適な方法で解決した最初の論文である。
  論文  参考訳（メタデータ） (2021-12-11T13:18:33Z)
• Gaussian Graphical Model Selection for Huge Data via Minipatch Learning [1.2891210250935146]
  グラフィカルモデル選択の問題を解決するために,MPGraph (Minipatch Graph) 推定器を提案する。 MPGraphは、観測とノードの両方の小さなランダムなサブセットに適合する閾値グラフ推定器の一般化である。 本アルゴリズムは有限サンプルグラフ選択の整合性を実現する。
  論文  参考訳（メタデータ） (2021-10-22T21:06:48Z)
• T-LoHo: A Bayesian Regularization Model for Structured Sparsity and Smoothness on Graphs [0.0]
  グラフ構造化データでは、構造化されたスパーシリティと滑らかさが団結する傾向にある。 グラフィカルな関係を持つ高次元パラメータに先立って提案する。 構造された空間と滑らかさを同時に検出するために使用します。
  論文  参考訳（メタデータ） (2021-07-06T10:10:03Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)
• Reducibility and Statistical-Computational Gaps from Secret Leakage [19.25775832101647]
  我々は, 秘密リークドライドドライド・ドライド(秘密リークドライド・ドライド・ドライド)の若干の一般化が, 様々な新しい平均ケース・リダクション技術をもたらすことを示した。 特定の種類の秘密漏れクランプに対する植込みクランプ予想の変種を用いて、厳密な統計計算トレードオフを導出する。
  論文  参考訳（メタデータ） (2020-05-16T20:56:09Z)

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

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