論文の概要: Faster Algorithms for User-Level Private Stochastic Convex Optimization

• arxiv url: http://arxiv.org/abs/2410.18391v1
• Date: Thu, 24 Oct 2024 03:02:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-25 16:43:38.797326
• Title: Faster Algorithms for User-Level Private Stochastic Convex Optimization
• Title（参考訳）: ユーザレベルプライベート確率凸最適化のための高速アルゴリズム
• Authors: Andrew Lowy, Daogao Liu, Hilal Asi,
• Abstract要約: ユーザレベルの差分プライバシー制約の下で,プライベート凸最適化(SCO)について検討する。 ユーザレベルのDP SCOの既存のアルゴリズムは多くの大規模機械学習シナリオでは実用的ではない。 我々は、最先端の過剰リスクと実行時保証を備えた新しいユーザレベルのDPアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 16.59551503680919
• License:
• Abstract: We study private stochastic convex optimization (SCO) under user-level differential privacy (DP) constraints. In this setting, there are $n$ users (e.g., cell phones), each possessing $m$ data items (e.g., text messages), and we need to protect the privacy of each user's entire collection of data items. Existing algorithms for user-level DP SCO are impractical in many large-scale machine learning scenarios because: (i) they make restrictive assumptions on the smoothness parameter of the loss function and require the number of users to grow polynomially with the dimension of the parameter space; or (ii) they are prohibitively slow, requiring at least $(mn)^{3/2}$ gradient computations for smooth losses and $(mn)^3$ computations for non-smooth losses. To address these limitations, we provide novel user-level DP algorithms with state-of-the-art excess risk and runtime guarantees, without stringent assumptions. First, we develop a linear-time algorithm with state-of-the-art excess risk (for a non-trivial linear-time algorithm) under a mild smoothness assumption. Our second algorithm applies to arbitrary smooth losses and achieves optimal excess risk in $\approx (mn)^{9/8}$ gradient computations. Third, for non-smooth loss functions, we obtain optimal excess risk in $n^{11/8} m^{5/4}$ gradient computations. Moreover, our algorithms do not require the number of users to grow polynomially with the dimension.
• Abstract（参考訳）: ユーザレベルの差分プライバシー(DP)制約下で,個人確率凸最適化(SCO)について検討した。 この設定では、ユーザ(例えば携帯電話)が$n$で、それぞれが$m$のデータアイテム(例えば、テキストメッセージ)を持っている。 ユーザレベルのDP SCOの既存のアルゴリズムは、多くの大規模機械学習シナリオでは実用的ではない。 一 損失関数の滑らか度パラメータに制限的な仮定をし、パラメータ空間の次元と多項式的に成長させるユーザ数を要求すること。 (ii)非滑らかな損失に対して少なくとも$(mn)^{3/2}$勾配計算と$(mn)^3$非滑らかな損失に対する$(mn)^3$計算を必要とする。 これらの制約に対処するため、厳密な仮定を伴わずに、最先端の過剰リスクと実行時保証を備えた新しいユーザレベルのDPアルゴリズムを提供する。 まず,非自明な線形時間アルゴリズムに対して,過大なリスクを負う線形時間アルゴリズムを軽度な滑らかさ仮定の下で開発する。 2つ目のアルゴリズムは任意の滑らかな損失に適用し、$\approx (mn)^{9/8}$グラデーション計算において最適余剰リスクを達成する。 第三に、非滑らかな損失関数に対しては、$n^{11/8} m^{5/4}$勾配計算の最適余剰リスクを得る。 さらに,本アルゴリズムでは,次元とともに多項式的に成長するユーザ数を必要としない。

関連論文リスト

• Efficient Sparse Least Absolute Deviation Regression with Differential Privacy [10.414082115202003]
  頑健な回帰問題に対する高速なプライバシー保護学習ソリューションを開発した。 本アルゴリズムは,スパースLAD問題をペナル化最小二乗推定問題として修正し,高速な推定を実現する。 我々のアルゴリズムは、最先端のプライバシ保存回帰アルゴリズムと比較して、より優れたプライバシーと統計的精度のトレードオフを実現することができることを示す。
  論文  参考訳（メタデータ） (2024-01-02T17:13:34Z)
• User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates [16.958088684785668]
  我々は,実行時において凸関数と強凸関数の両方に対して最適なレートを求める,ユーザレベルのDP-SCOの新しいアルゴリズムを開発した。 我々のアルゴリズムは、時間内に非滑らかな関数に対して最適な速度を得る最初の方法である。
  論文  参考訳（メタデータ） (2023-11-07T08:26:51Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
  雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。 私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
  論文  参考訳（メタデータ） (2021-03-01T19:48:44Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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