論文の概要: 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) - Meta-Learning Operators to Optimality from Multi-Task Non-IID Data [1.7587442088965224]
すべてのデータを使って共通の表現関数を学ぶことは、計算の労力と統計的一般化の両方に利益がある。
既存の異方性に依存しないメタラーニングは、表現更新に偏りを生じさせるため、ノイズ項のスケーリングは、ソースタスクの数に好ましくない。
我々は、Collins et al. (2021) で提案された交互化最小化退化スキームの適応 $texttDFW$ を導入し、最適な表現に線形収束を確立する。
論文 参考訳(メタデータ) (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) - ReLU Regression with Massart Noise [52.10842036932169]
本稿では、ReLU回帰の基本的問題として、Rectified Linear Units(ReLU)をデータに適合させることを目標としている。
我々は自然およびよく研究された半ランダムノイズモデルであるMassartノイズモデルにおけるReLU回帰に着目した。
このモデルにおいて,パラメータの正確な回復を実現する効率的なアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-09-10T02:13:22Z) - Understanding the Under-Coverage Bias in Uncertainty Estimation [58.03725169462616]
量子レグレッションは、現実の望ましいカバレッジレベルよりもアンファンダーカバー(enmphunder-cover)する傾向がある。
我々は、量子レグレッションが固有のアンダーカバーバイアスに悩まされていることを証明している。
我々の理論は、この過大被覆バイアスが特定の高次元パラメータ推定誤差に起因することを明らかにしている。
論文 参考訳(メタデータ) (2021-06-10T06:11:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。