論文の概要: 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つの異なる特異値ギャップの下でプライベート部分空間推定の問題を定式化し、両タイプの新しい上限と下限を証明した。
特に, 次元に依存しない点の量を持つ部分空間を推定するためには, どの種類のギャップが十分で, 必要かを決定する。
関連論文リスト
- Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension [20.431551512846248]
ニューラル・タンジェント・カーネル(NTK)の最小固有値の境界は、ニューラルネットワークの最適化と記憶の解析において重要な要素である。
我々はヘミスフィア・トランスフォーメーションの新たな応用を通してその結果を証明した。
論文 参考訳（メタデータ） (2024-05-23T14:36:52Z) - Relative intrinsic dimensionality is intrinsic to learning [49.5738281105287]
本稿では,データ分布の固有次元の概念を導入し,データの分離性特性を正確に把握する。
この本質的な次元に対して、上の親指の規則は法則となり、高本質的な次元は高度に分離可能なデータを保証する。
本稿では,2進分類問題における学習と一般化の確率について,上界と下界の両方に相対固有次元を与えることを示す。
論文 参考訳（メタデータ） (2023-10-10T10:41:45Z) - Random Smoothing Regularization in Kernel Gradient Descent Learning [24.383121157277007]
古典的ソボレフ空間に属する幅広い基底真理関数を適応的に学習できるランダムなスムーズな正規化のための枠組みを提案する。
我々の推定器は、基礎となるデータの構造的仮定に適応し、次元の呪いを避けることができる。
論文 参考訳（メタデータ） (2023-05-05T13:37:34Z) - Interpretable Linear Dimensionality Reduction based on Bias-Variance
Analysis [45.3190496371625]
本稿では,特徴の解釈可能性を維持するための基本次元削減手法を提案する。
このように、全ての特徴を考慮し、次元性を減らし、解釈可能性を保持する。
論文 参考訳（メタデータ） (2023-03-26T14:30:38Z) - On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。
差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。
アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
論文 参考訳（メタデータ） (2023-02-11T14:45:31Z) - 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) - Intrinsic Dimension Estimation [92.87600241234344]
内在次元の新しい推定器を導入し, 有限標本, 非漸近保証を提供する。
次に、本手法を適用して、データ固有の次元に依存するGAN(Generative Adversarial Networks)に対する新しいサンプル複雑性境界を求める。
論文 参考訳（メタデータ） (2021-06-08T00:05:39Z) - 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) - Online stochastic gradient descent on non-convex losses from
high-dimensional inference [2.2344764434954256]
勾配降下(SGD)は高次元タスクにおける最適化問題に対する一般的なアルゴリズムである。
本稿では,データから非自明な相関関係を推定する。
本稿では、位相探索や一般化モデルの推定といった一連のタスクに適用することで、我々のアプローチを説明する。
論文 参考訳（メタデータ） (2020-03-23T17:34:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。