論文の概要: On Differentially Private Subspace Estimation Without Distributional
Assumptions
- arxiv url: http://arxiv.org/abs/2402.06465v1
- Date: Fri, 9 Feb 2024 15:17:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-12 16:26:57.349271
- Title: On Differentially Private Subspace Estimation Without Distributional
Assumptions
- Title(参考訳): 分布推定のない微分プライベート部分空間推定について
- Authors: Eliad Tsfadia
- Abstract要約: 入力データの特異値ギャップの2つの異なるタイプでプライベート部分空間推定の問題を定式化する。
この結果から,次元に依存しない点の量で部分空間を推定するには,どのギャップが十分で必要なのかが決定される。
- 参考スコア(独自算出の注目度): 3.8888996044605855
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Private data analysis faces a significant challenge known as the curse of
dimensionality, leading to increased costs. However, many datasets possess an
inherent low-dimensional structure. For instance, during optimization via
gradient descent, the gradients frequently reside near a low-dimensional
subspace. If the low-dimensional structure could be privately identified using
a small amount of points, we could avoid paying (in terms of privacy and
accuracy) for the high ambient dimension.
On the negative side, Dwork, Talwar, Thakurta, and Zhang (STOC 2014) proved
that privately estimating subspaces, in general, requires an amount of points
that depends on the dimension. But Singhal and Steinke (NeurIPS 2021) bypassed
this limitation by considering points that are i.i.d. samples from a Gaussian
distribution whose covariance matrix has a certain eigenvalue gap. Yet, it was
still left unclear whether we could provide similar upper bounds without
distributional assumptions and whether we could prove lower bounds that depend
on similar eigenvalue gaps.
In this work, we make progress in both directions. We formulate the problem
of private subspace estimation under two different types of singular value gaps
of the input data and prove new upper and lower bounds for both types. In
particular, our results determine what type of gap is sufficient and necessary
for estimating a subspace with an amount of points that is independent of the
dimension.
- Abstract(参考訳): プライベートデータ分析は次元の呪いとして知られる重要な課題に直面し、コストが増大する。
しかし、多くのデータセットは固有の低次元構造を持っている。
例えば、勾配降下による最適化の間、勾配はしばしば低次元部分空間の近くに存在する。
もし低次元構造が少量の点を使ってプライベートに識別できるなら、高次元の次元に対して(プライバシーと正確性の観点から)支払いを避けることができるだろう。
負の面において、Dwork, Talwar, Thakurta, Zhang (STOC 2014) は、プライベートに推定される部分空間は一般に、次元に依存する点の量を必要とすることを示した。
しかしsinghalとsteinke(neurips 2021)はこの制限を回避し、同分散行列が特定の固有値ギャップを持つガウス分布のサンプルである点を考察した。
しかし、分布的仮定なしで同様の上限を提供できるか、同様の固有値のギャップに依存する下限を証明できるのかは、まだ不明である。
この作業では、両方の方向に前進します。
入力データの2つの異なる特異値ギャップの下でプライベート部分空間推定の問題を定式化し、両タイプの新しい上限と下限を証明した。
特に, 次元に依存しない点の量を持つ部分空間を推定するためには, どの種類のギャップが十分で, 必要かを決定する。
関連論文リスト
- On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。
差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。
アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
論文 参考訳(メタデータ) (2023-02-11T14:45:31Z) - On Projections to Linear Subspaces [0.0]
異なる次元の明示的な部分空間への線形射影の未探検深度について検討する。
その結果はユークリッド距離と内積の新たな境界族となる。
本研究は,これらの境界の質を実証するとともに,本質的次元推定との密接な関係について考察する。
論文 参考訳(メタデータ) (2022-09-26T07:56:59Z) - Intrinsic dimension estimation for discrete metrics [65.5438227932088]
本稿では,離散空間に埋め込まれたデータセットの内在次元(ID)を推定するアルゴリズムを提案する。
我々は,その精度をベンチマークデータセットで示すとともに,種鑑定のためのメダゲノミクスデータセットの分析に応用する。
このことは、列の空間の高次元性にもかかわらず、蒸発圧が低次元多様体に作用することを示唆している。
論文 参考訳(メタデータ) (2022-07-20T06:38:36Z) - A Dimensionality Reduction Method for Finding Least Favorable Priors
with a Focus on Bregman Divergence [108.28566246421742]
そこで本研究では,次元に明示的な有界な有限次元設定に最適化を移動させることができる次元削減法を開発した。
この問題を進展させるため、比較的大きな損失関数、すなわちブレグマンの発散によって引き起こされるベイズ的リスクに限定する。
論文 参考訳(メタデータ) (2022-02-23T16:22:28Z) - Tangent Space and Dimension Estimation with the Wasserstein Distance [10.118241139691952]
ユークリッド空間の滑らかなコンパクト部分多様体の近くで独立にサンプリングされた点の集合を考える。
我々は、その多様体の次元と接空間の両方を推定するために必要なサンプル点の数について数学的に厳密な境界を与える。
論文 参考訳(メタデータ) (2021-10-12T21:02:06Z) - Estimating Graph Dimension with Cross-validated Eigenvalues [5.0013150536632995]
応用統計学では、潜在次元の数を推定したり、クラスターの数を推定することは基本的な問題であり、繰り返し発生する問題である。
この問題に対するクロスバリデーションな固有値アプローチを提供する。
我々の手順は、すべての$k$次元を推定できるシナリオにおいて、一貫して$k$を推定することを証明する。
論文 参考訳(メタデータ) (2021-08-06T23:52:30Z) - Privately Learning Subspaces [16.805122710333826]
本稿では,低次元線形部分空間からサンプルデータを取得し,その部分空間を出力する差分プライベートアルゴリズムを提案する。
これらのアルゴリズムは、他のプロシージャの事前処理ステップとして機能する。
論文 参考訳(メタデータ) (2021-05-28T21:09:23Z) - A Local Similarity-Preserving Framework for Nonlinear Dimensionality
Reduction with Neural Networks [56.068488417457935]
本稿では,Vec2vecという新しい局所非線形手法を提案する。
ニューラルネットワークを訓練するために、マトリックスの近傍類似度グラフを構築し、データポイントのコンテキストを定義します。
8つの実データセットにおけるデータ分類とクラスタリングの実験により、Vec2vecは統計仮説テストにおける古典的な次元削減法よりも優れていることが示された。
論文 参考訳(メタデータ) (2021-03-10T23:10:47Z) - Bypassing the Ambient Dimension: Private SGD with Gradient Subspace
Identification [47.23063195722975]
微分プライベートSGD(DP-SGD)は、微分プライベートな経験的リスク最小化(ERM)を解決する最も一般的な方法の1つである。
各勾配更新におけるノイズの多い摂動のため、DP-SGDの誤差率は、モデル内のパラメータ数である周囲次元$p$でスケールする。
雑音勾配を低次元部分空間に投影することでノイズ低減を行うDP-SGDを提案する。
論文 参考訳(メタデータ) (2020-07-07T22:31:01Z) - Interpolation and Learning with Scale Dependent Kernels [91.41836461193488]
非パラメトリックリッジレス最小二乗の学習特性について検討する。
スケール依存カーネルで定義される推定器の一般的な場合を考える。
論文 参考訳(メタデータ) (2020-06-17T16:43:37Z) - Intrinsic Dimension Estimation via Nearest Constrained Subspace
Classifier [7.028302194243312]
教師付き分類や固有次元推定のために,新しい部分空間に基づく分類器を提案する。
各クラスのデータの分布は、特徴空間の有限個のファイン部分空間の和によってモデル化される。
The proposed method is a generalization of classical NN (Nearest Neighbor), NFL (Nearest Feature Line) and has a close relationship with NS (Nearest Subspace)。
推定次元パラメータが正確に推定された分類器は、一般に分類精度の点で競合より優れている。
論文 参考訳(メタデータ) (2020-02-08T20:54:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。