論文の概要: User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates

• arxiv url: http://arxiv.org/abs/2311.03797v1
• Date: Tue, 7 Nov 2023 08:26:51 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-08 16:28:14.307525
• Title: User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates
• Title（参考訳）: ユーザレベルの微分プライベート確率凸最適化:最適レートの効率的なアルゴリズム
• Authors: Hilal Asi, Daogao Liu
• Abstract要約: 我々は,実行時において凸関数と強凸関数の両方に対して最適なレートを求める,ユーザレベルのDP-SCOの新しいアルゴリズムを開発した。 我々のアルゴリズムは、時間内に非滑らかな関数に対して最適な速度を得る最初の方法である。
• 参考スコア（独自算出の注目度）: 16.958088684785668
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study differentially private stochastic convex optimization (DP-SCO) under user-level privacy, where each user may hold multiple data items. Existing work for user-level DP-SCO either requires super-polynomial runtime [Ghazi et al. (2023)] or requires the number of users to grow polynomially with the dimensionality of the problem with additional strict assumptions [Bassily et al. (2023)]. We develop new algorithms for user-level DP-SCO that obtain optimal rates for both convex and strongly convex functions in polynomial time and require the number of users to grow only logarithmically in the dimension. Moreover, our algorithms are the first to obtain optimal rates for non-smooth functions in polynomial time. These algorithms are based on multiple-pass DP-SGD, combined with a novel private mean estimation procedure for concentrated data, which applies an outlier removal step before estimating the mean of the gradients.
• Abstract（参考訳）: ユーザレベルのプライバシの下で,各ユーザが複数のデータアイテムを保持可能なDP-SCOについて検討した。 既存のDP-SCOの作業には、スーパーポリノミカルランタイム(Ghazi et al. (2023))が必要か、さらに厳密な仮定(Bassily et al. (2023))を伴って、問題の次元と多項式的に成長するユーザ数を必要とする。 我々は,多項式時間における凸関数と強凸関数の両方の最適レートを求めるDP-SCOの新しいアルゴリズムを開発し,各次元の対数的にしか成長しないユーザ数を求める。 さらに, このアルゴリズムは多項式時間における非滑らか関数の最適値を得る最初の方法である。 これらのアルゴリズムはマルチパスdp-sgdに基づいており、集中データに対する新しいプライベート平均推定法と組み合わせて、勾配の平均を推定する前に外れ値除去ステップを適用する。

関連論文リスト

• Faster Algorithms for User-Level Private Stochastic Convex Optimization [16.59551503680919]
  ユーザレベルの差分プライバシー制約の下で,プライベート凸最適化(SCO)について検討する。 ユーザレベルのDP SCOの既存のアルゴリズムは多くの大規模機械学習シナリオでは実用的ではない。 我々は、最先端の過剰リスクと実行時保証を備えた新しいユーザレベルのDPアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-10-24T03:02:33Z)
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。 我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-05-28T19:02:30Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。 近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。 ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
  論文  参考訳（メタデータ） (2023-09-21T21:51:55Z)
• Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization [44.52870407321633]
  これらの設定の聖杯は、プライバシーと過剰な人口減少の間の最適なトレードオフを保証することです。 微分プライベート・ミニマックス最適化(DP-SMO)問題を解くための一般的なフレームワークを提供する。 我々のフレームワークは、非滑らかな微分プライベート凸最適化(DP-SCO)のための最近提案されたフェイズド・ERM法[20]から着想を得たものである。
  論文  参考訳（メタデータ） (2022-06-01T10:03:20Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。 我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。 我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
  論文  参考訳（メタデータ） (2020-06-12T05:00:44Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Private Stochastic Convex Optimization: Efficient Algorithms for Non-smooth Objectives [28.99826590351627]
  本稿では,プライバシパラメータがサンプル数に比例する場合に,一階降下を実現する雑音ミラーに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-22T03:03:43Z)

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

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