論文の概要: On Differentially Private Subspace Estimation in a Distribution-Free Setting
- arxiv url: http://arxiv.org/abs/2402.06465v3
- Date: Fri, 25 Oct 2024 19:05:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-29 12:14:13.696186
- Title: On Differentially Private Subspace Estimation in a Distribution-Free Setting
- Title（参考訳）: 分布自由設定における微分プライベート部分空間の推定について
- Authors: Eliad Tsfadia,
- Abstract要約: 入力データセットにおける乗法的特異値ギャップの関数として「容易性」を定量化する最初の尺度を提供する。
特に、この結果は、部分空間を推定するのに十分かつ必要となる、最初のタイプのギャップを決定する。
- 参考スコア（独自算出の注目度）: 3.8888996044605855
- License:
- 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 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 has a polynomial dependency on the dimension. However, their bounds do not rule out the possibility to reduce the number of points for "easy" instances. Yet, providing a measure that captures how much a given dataset is "easy" for this task turns out to be challenging, and was not properly addressed in prior works. Inspired by the work of Singhal and Steinke (NeurIPS 2021), we provide the first measures that quantify "easiness" as a function of multiplicative singular-value gaps in the input dataset, and support them with new upper and lower bounds. In particular, our results determine the first types of gaps that are sufficient and necessary for estimating a subspace with an amount of points that is independent of the dimension. Furthermore, we realize our upper bounds using a practical algorithm and demonstrate its advantage in high-dimensional regimes compared to prior approaches.
- Abstract（参考訳）: プライベートデータ分析は、次元の呪いとして知られる重要な課題に直面し、コストが増大する。
しかし、多くのデータセットは固有の低次元構造を持っている。
例えば、勾配降下による最適化の間、勾配はしばしば低次元部分空間の近くに存在する。
もし低次元構造を少数の点を用いてプライベートに同定できれば、高周囲次元の支払いを避けることができる。
負の面において、Dwork, Talwar, Thakurta, Zhang (STOC 2014) は、プライベートに推定される部分空間は一般に、次元に多項式依存を持つ点の量を必要とすることを証明した。
しかし、それらの境界は "easy" インスタンスの点数を減らす可能性を排除していない。
しかし、与えられたデータセットがどれだけ"簡単"であるかを計測する尺度を提供することで、このタスクは困難であることが判明し、以前の作業では適切に対処されなかった。
Singhal と Steinke の業績 (NeurIPS 2021) に触発され、入力データセットにおける乗法的特異値ギャップの関数として "easiness" を定量化し、それらを新しい上下境界で支援する最初の尺度を提供する。
特に、我々の結果は、次元に依存しない点の量で部分空間を推定するのに十分かつ必要となる最初のタイプのギャップを決定する。
さらに, 実効的なアルゴリズムを用いて上界を実現し, 従来の手法と比較して高次元のレシエーションにおいてその優位性を示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。