論文の概要: Fast John Ellipsoid Computation with Differential Privacy Optimization

• arxiv url: http://arxiv.org/abs/2408.06395v1
• Date: Mon, 12 Aug 2024 03:47:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-14 19:38:59.964031
• Title: Fast John Ellipsoid Computation with Differential Privacy Optimization
• Title（参考訳）: 微分プライバシー最適化を用いた高速ジョン・エリプソイド計算
• Authors: Jiuxiang Gu, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Junwei Yu,
• Abstract要約: 高速なジョン楕円体計算のための微分プライベートアルゴリズムを提案する。 提案手法は, ノイズ摂動とスケッチ処理を統合し, スコアサンプリングを活用し, 効率とプライバシの両立を図る。
• 参考スコア（独自算出の注目度）: 34.437362489150246
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Determining the John ellipsoid - the largest volume ellipsoid contained within a convex polytope - is a fundamental problem with applications in machine learning, optimization, and data analytics. Recent work has developed fast algorithms for approximating the John ellipsoid using sketching and leverage score sampling techniques. However, these algorithms do not provide privacy guarantees for sensitive input data. In this paper, we present the first differentially private algorithm for fast John ellipsoid computation. Our method integrates noise perturbation with sketching and leverage score sampling to achieve both efficiency and privacy. We prove that (1) our algorithm provides $(\epsilon,\delta)$-differential privacy, and the privacy guarantee holds for neighboring datasets that are $\epsilon_0$-close, allowing flexibility in the privacy definition; (2) our algorithm still converges to a $(1+\xi)$-approximation of the optimal John ellipsoid in $O(\xi^{-2}(\log(n/\delta_0) + (L\epsilon_0)^{-2}))$ iterations where $n$ is the number of data point, $L$ is the Lipschitz constant, $\delta_0$ is the failure probability, and $\epsilon_0$ is the closeness of neighboring input datasets. Our theoretical analysis demonstrates the algorithm's convergence and privacy properties, providing a robust approach for balancing utility and privacy in John ellipsoid computation. This is the first differentially private algorithm for fast John ellipsoid computation, opening avenues for future research in privacy-preserving optimization techniques.
• Abstract（参考訳）: John ellipsoid - 凸ポリトープに含まれる最大のボリューム楕円体 - を決定することは、機械学習、最適化、データ分析におけるアプリケーションの根本的な問題である。 近年の研究では、スケッチを用いてジョン楕円体を近似し、スコアサンプリング技術を活用するための高速アルゴリズムが開発されている。 しかし、これらのアルゴリズムは機密入力データに対するプライバシー保証を提供していない。 本稿では,高速なジョン楕円体計算のための微分プライベートアルゴリズムを提案する。 提案手法は, ノイズ摂動とスケッチ処理を統合し, スコアサンプリングを活用し, 効率とプライバシの両立を図る。 我々は、(1)アルゴリズムが$(\epsilon,\delta)$-differential privacyを提供し、(2)プライバシー定義の柔軟性を許容する近隣データセットに対して、プライバシー保証が成り立つことを証明した; (2) アルゴリズムは、なおも$(1+\xi)$-approximation of the optimal John ellipsoid in $O(\xi^{-2}(\log(n/\delta_0) + (L\epsilon_0)^{-2}) において、最適なJohn ellipsoidの$O(\xi^{-2}(\log(n/\delta_0) + (L\epsilon_0)^{-2}) に収束する。 我々の理論的分析はアルゴリズムの収束性とプライバシ特性を示し、ジョン楕円体計算におけるユーティリティとプライバシのバランスをとるための堅牢なアプローチを提供する。 これはジョン楕円体計算のための最初の微分プライベートアルゴリズムであり、将来のプライバシー保護最適化技術の研究への道を開く。

関連論文リスト

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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