論文の概要: Private Geometric Median in Nearly-Linear Time

• arxiv url: http://arxiv.org/abs/2505.20189v1
• Date: Mon, 26 May 2025 16:32:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 19:27:26.943484
• Title: Private Geometric Median in Nearly-Linear Time
• Title（参考訳）: 身近な幾何学的メディア
• Authors: Syamantak Kumar, Daogao Liu, Kevin Tian, Chutong Yang,
• Abstract要約: データセットの幾何学的中央値の推定は、計算幾何学の基本的な問題である。 [HSU24]は幾何中央値の目的に対して$alpha$-multiplicative近似を与えた。 同じ近似品質を得るアルゴリズムを改良する。
• 参考スコア（独自算出の注目度）: 11.537965585323304
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Estimating the geometric median of a dataset is a robust counterpart to mean estimation, and is a fundamental problem in computational geometry. Recently, [HSU24] gave an $(\varepsilon, \delta)$-differentially private algorithm obtaining an $\alpha$-multiplicative approximation to the geometric median objective, $\frac 1 n \sum_{i \in [n]} \|\cdot - \mathbf{x}_i\|$, given a dataset $\mathcal{D} := \{\mathbf{x}_i\}_{i \in [n]} \subset \mathbb{R}^d$. Their algorithm requires $n \gtrsim \sqrt d \cdot \frac 1 {\alpha\varepsilon}$ samples, which they prove is information-theoretically optimal. This result is surprising because its error scales with the \emph{effective radius} of $\mathcal{D}$ (i.e., of a ball capturing most points), rather than the worst-case radius. We give an improved algorithm that obtains the same approximation quality, also using $n \gtrsim \sqrt d \cdot \frac 1 {\alpha\epsilon}$ samples, but in time $\widetilde{O}(nd + \frac d {\alpha^2})$. Our runtime is nearly-linear, plus the cost of the cheapest non-private first-order method due to [CLM+16]. To achieve our results, we use subsampling and geometric aggregation tools inspired by FriendlyCore [TCK+22] to speed up the "warm start" component of the [HSU24] algorithm, combined with a careful custom analysis of DP-SGD's sensitivity for the geometric median objective.
• Abstract（参考訳）: データセットの幾何中央値の推定は、平均推定に匹敵する堅牢なものであり、計算幾何学における根本的な問題である。 最近、[HSU24] は$(\varepsilon, \delta)$-differentially private algorithm を与え、幾何的中央値の目的に対する $\alpha$-multiplicative approximation を得る。 $\frac 1 n \sum_{i \in [n]} \|\cdot - \mathbf{x}_i\|$ は、データセット $\mathcal{D} := \mathbf{x}_i\}_{i \in [n]} \subset \mathbb{R}^d$ を与える。 それらのアルゴリズムには$n \gtrsim \sqrt d \cdot \frac 1 {\alpha\varepsilon}$サンプルが必要である。 この結果は、最悪の場合の半径ではなく、$\mathcal{D}$(つまり、ほとんどの点を捕獲するボール)のemph{ Effective radius}でスケールするため、驚くべきものである。 我々は、同じ近似品質を得るアルゴリズムを改良し、$n \gtrsim \sqrt d \cdot \frac 1 {\alpha\epsilon}$サンプルを使用するが、時間では$\widetilde{O}(nd + \frac d {\alpha^2})$である。 我々のランタイムはほぼ直線的であり、[CLM+16]による最も安価な非プライベートな1次メソッドのコストも高い。 この結果を得るために,FriendlyCore[TCK+22]にヒントを得たサブサンプリングと幾何集約ツールを用いて,[HSU24]アルゴリズムの"ウォームスタート"コンポーネントを高速化する。

関連論文リスト

• Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior [28.71736321665378]
  一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。 We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。 また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
  論文  参考訳（メタデータ） (2025-03-26T03:36:36Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
  準多項式依存のMDSに対する最初の近似アルゴリズムをDeltaに与える。 本アルゴリズムは,シェラリ・アダムスLPの条件付きラウンドリングの幾何学的認識に基づく新しい解析法である。
  論文  参考訳（メタデータ） (2023-11-29T17:42:05Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。 近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。 副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
  論文  参考訳（メタデータ） (2022-02-22T04:14:45Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
  ノイズの多いサンプルの有限集合から$mathbbRD$の$d$次元部分多様体を推定する問題を検討する。 点推定では$n-frack2k + d$、接空間の推定では$n-frack-12k + d$の収束率を推定する。
  論文  参考訳（メタデータ） (2021-05-11T02:29:33Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。 最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
  論文  参考訳（メタデータ） (2020-11-24T22:39:21Z)

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

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