論文の概要: Differentially Private Optimization with Sparse Gradients

• arxiv url: http://arxiv.org/abs/2404.10881v1
• Date: Tue, 16 Apr 2024 20:01:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-18 18:02:19.148237
• Title: Differentially Private Optimization with Sparse Gradients
• Title（参考訳）: スパース勾配を用いた微分プライベート最適化
• Authors: Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Ravi Kumar, Pasin Manurangsi,
• Abstract要約: 微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 60.853074897282625
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optimal bounds for the classic mean estimation problem but with sparse data, improving upon existing algorithms particularly for the high-dimensional regime. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for stochastic convex optimization with sparse gradients; the former represents the first nearly dimension-independent rates for this problem. Finally, we study the approximation of stationary points for the empirical loss in approximate-DP optimization and obtain rates that depend on sparsity instead of dimension, modulo polylogarithmic factors.
• Abstract（参考訳）: 大規模埋め込みモデルの適用により、個々の勾配の空間性の下で、微分プライベート(DP)最適化問題を研究する。 まず,従来の平均推定問題に対する新しい近似境界から始めるが,スパースデータにより,特に高次元構造に対する既存のアルゴリズムの改善を行う。 これに基づいて,スパース勾配の確率凸最適化にほぼ最適である純粋および近似DPアルゴリズムが得られ,前者はこの問題に対する最初のほぼ次元に依存しない速度を表す。 最後に、近似DP最適化における経験的損失に対する定常点の近似について検討し、次元、モジュラー多元対数因子の代わりに空間に依存する速度を求める。

関連論文リスト

• User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates [16.958088684785668]
  我々は,実行時において凸関数と強凸関数の両方に対して最適なレートを求める,ユーザレベルのDP-SCOの新しいアルゴリズムを開発した。 我々のアルゴリズムは、時間内に非滑らかな関数に対して最適な速度を得る最初の方法である。
  論文  参考訳（メタデータ） (2023-11-07T08:26:51Z)
• Parameter-free projected gradient descent [0.0]
  我々は、射影勾配 Descent (PGD) を用いて、閉凸集合上の凸関数を最小化する問題を考える。 本稿では,AdaGradのパラメータフリーバージョンを提案する。これは初期化と最適化の距離に適応し,下位段階の平方ノルムの和に適応する。 提案アルゴリズムはプロジェクションステップを処理でき、リスタートを伴わず、従来のPGDと比較して軌道に沿ってリウィーディングや追加評価を行うことができる。
  論文  参考訳（メタデータ） (2023-05-31T07:22:44Z)
• Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
  我々は、差分プライベート(DP)を保証する重み付きデータに対する差分プライベート凸最適化について検討する。 我々は,制約付きおよび制約なし凸問題に対するAClipped-dpSGDというアルゴリズムに対して,新たな収束結果を確立し,複雑性境界を改善した。
  論文  参考訳（メタデータ） (2022-06-27T01:39:15Z)
• 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 Adaptive Gradient Methods for Convex Optimization [32.3523019355048]
  適応的なステップサイズを持つグラディエント Descent (SGD) アルゴリズムの差分プライベート変種を提案・解析する。 両アルゴリズムの後悔に関する上限を与え、その境界が最適であることを示す。
  論文  参考訳（メタデータ） (2021-06-25T16:46:45Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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