論文の概要: Subspace Recovery from Heterogeneous Data with Non-isotropic Noise

• arxiv url: http://arxiv.org/abs/2210.13497v1
• Date: Mon, 24 Oct 2022 18:00:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-26 14:21:01.721233
• Title: Subspace Recovery from Heterogeneous Data with Non-isotropic Noise
• Title（参考訳）: 非等方性雑音を伴う異種データからの部分空間の復元
• Authors: John Duchi, Vitaly Feldman, Lunjia Hu, Kunal Talwar
• Abstract要約: この問題の基本的な定式化について研究する:主成分分析(PCA) 私たちの目標は、すべてのユーザからのデータポイントを使用して、$mu_i$で共有される線形部分空間を復元することです。 非球面およびユーザ依存雑音下で効率よく計算可能な推定器を設計する。
• 参考スコア（独自算出の注目度）: 43.44371292901258
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recovering linear subspaces from data is a fundamental and important task in statistics and machine learning. Motivated by heterogeneity in Federated Learning settings, we study a basic formulation of this problem: the principal component analysis (PCA), with a focus on dealing with irregular noise. Our data come from $n$ users with user $i$ contributing data samples from a $d$-dimensional distribution with mean $\mu_i$. Our goal is to recover the linear subspace shared by $\mu_1,\ldots,\mu_n$ using the data points from all users, where every data point from user $i$ is formed by adding an independent mean-zero noise vector to $\mu_i$. If we only have one data point from every user, subspace recovery is information-theoretically impossible when the covariance matrices of the noise vectors can be non-spherical, necessitating additional restrictive assumptions in previous work. We avoid these assumptions by leveraging at least two data points from each user, which allows us to design an efficiently-computable estimator under non-spherical and user-dependent noise. We prove an upper bound for the estimation error of our estimator in general scenarios where the number of data points and amount of noise can vary across users, and prove an information-theoretic error lower bound that not only matches the upper bound up to a constant factor, but also holds even for spherical Gaussian noise. This implies that our estimator does not introduce additional estimation error (up to a constant factor) due to irregularity in the noise. We show additional results for a linear regression problem in a similar setup.
• Abstract（参考訳）: データから線形部分空間を復元することは統計学と機械学習における基本的な重要なタスクである。 フェデレーション学習環境における不均一性により動機づけられた主成分分析(PCA)の基本的な定式化について検討し,不規則雑音に対処することに焦点を当てた。 われわれのデータは$n$ユーザーからで、$i$は$d$-dimensionalディストリビューションからデータサンプルを寄付し、$\mu_i$です。 我々の目標は、すべてのユーザからのデータポイントを使用して、$\mu_1,\ldots,\mu_n$で共有される線形部分空間を復元することである。 すべてのユーザから1つのデータポイントしか持たなければ、ノイズベクトルの共分散行列が非球形になり得る場合、サブスペースリカバリは情報理論的に不可能である。 各ユーザから少なくとも2つのデータポイントを利用すれば,非球面およびユーザ依存ノイズ下で効率的に計算可能な推定器を設計できる。 本研究では,ユーザ間でデータポイント数やノイズ量が異なる場合の一般的なシナリオにおいて推定誤差の上限を証明し,上限値から定数値までの値に一致するだけでなく,球面ガウス雑音に対しても保持する情報理論上の誤差を証明した。 これは,雑音の不規則性による推定誤差(定数係数まで)が付加されないことを示唆している。 同様の設定で線形回帰問題に対するさらなる結果を示す。

関連論文リスト

• A Combinatorial Approach to Robust PCA [18.740048806623037]
  敵の汚職下でのガウスデータの回復問題について検討する。 ガウスノイズは未知の$k$-次元部分空間$U subseteq mathbbRd$と、各データポイントのランダムに選択された座標が敵の制御に該当すると仮定する。 我々の主な結果は、$ks2 = O(d)$のとき、期待して$tilde O(ks/d)$のほぼ最適エラーまですべてのデータポイントを復元する効率的なアルゴリズムです。
  論文  参考訳（メタデータ） (2023-11-28T01:49:51Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data [4.971690889257356]
  コリンズとナイアーとヴァスワニによって提案された交互最小化・退化スキームの適応について紹介する。 iidにおいてもバニラ変動最小化降下は破滅的に失敗するが, 軽度に非等方性データは得られない。 我々の分析は、事前の作業を統一し、一般化し、幅広いアプリケーションに柔軟なフレームワークを提供する。
  論文  参考訳（メタデータ） (2023-08-08T17:56:20Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Optimizing the Noise in Self-Supervised Learning: from Importance Sampling to Noise-Contrastive Estimation [80.07065346699005]
  GAN(Generative Adversarial Networks)のように、最適な雑音分布はデータ分布に等しくなると広く想定されている。 我々は、この自己教師型タスクをエネルギーベースモデルの推定問題として基礎づけるノイズ・コントラスト推定に目を向ける。 本研究は, 最適雑音のサンプリングは困難であり, 効率性の向上は, データに匹敵する雑音分布を選択することに比べ, 緩やかに行うことができると結論付けた。
  論文  参考訳（メタデータ） (2023-01-23T19:57:58Z)
• Pitfalls of Gaussians as a noise distribution in NCE [22.23473249312549]
  ノイズコントラスト推定(NCE)は,比例定数までパラメータ化された確率密度関数を学習するための一般的な手法である。 我々は、$q$の選択がNCEの計算効率と統計効率に大きな影響を及ぼすことを示した。
  論文  参考訳（メタデータ） (2022-10-01T04:42:56Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  この仮定から逸脱すると、実際により良い統計的推定結果が得られることが示される。 特に、最適な雑音分布は、データと異なり、また、別の家族からさえも異なる。
  論文  参考訳（メタデータ） (2022-03-02T13:59:20Z)
• Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers [13.244654316770815]
  我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。 スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。 PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
  論文  参考訳（メタデータ） (2021-11-04T15:59:44Z)
• Noise-robust Clustering [2.0199917525888895]
  本稿では,教師なし機械学習におけるノイズロバストクラスタリング手法を提案する。 ノイズ、一貫性、その他の曖昧性に関する不確実性は、データ分析において深刻な障害となる可能性がある。
  論文  参考訳（メタデータ） (2021-10-17T17:15:13Z)
• Understanding the Under-Coverage Bias in Uncertainty Estimation [58.03725169462616]
  量子レグレッションは、現実の望ましいカバレッジレベルよりもアンファンダーカバー(enmphunder-cover)する傾向がある。 我々は、量子レグレッションが固有のアンダーカバーバイアスに悩まされていることを証明している。 我々の理論は、この過大被覆バイアスが特定の高次元パラメータ推定誤差に起因することを明らかにしている。
  論文  参考訳（メタデータ） (2021-06-10T06:11:55Z)

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

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