論文の概要: The Cost of Shuffling in Private Gradient Based Optimization

• arxiv url: http://arxiv.org/abs/2502.03652v1
• Date: Wed, 05 Feb 2025 22:30:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-07 14:32:09.199427
• Title: The Cost of Shuffling in Private Gradient Based Optimization
• Title（参考訳）: プライベートグラディエント最適化におけるシャッフルコスト
• Authors: Shuli Jiang, Pranay Sharma, Zhiwei Steven Wu, Gauri Joshi,
• Abstract要約: その結果, DP-ShuffleGはDP-SGDと比較して, データのシャッフル処理により過大なリスクが生じることがわかった。 我々は、プライベートな最適化に公開データサンプルを統合するハイブリッドアプローチである textitInterleaved-ShuffleG を提案する。
• 参考スコア（独自算出の注目度）: 40.31928071333575
• License:
• Abstract: We consider the problem of differentially private (DP) convex empirical risk minimization (ERM). While the standard DP-SGD algorithm is theoretically well-established, practical implementations often rely on shuffled gradient methods that traverse the training data sequentially rather than sampling with replacement in each iteration. Despite their widespread use, the theoretical privacy-accuracy trade-offs of private shuffled gradient methods (\textit{DP-ShuffleG}) remain poorly understood, leading to a gap between theory and practice. In this work, we leverage privacy amplification by iteration (PABI) and a novel application of Stein's lemma to provide the first empirical excess risk bound of \textit{DP-ShuffleG}. Our result shows that data shuffling results in worse empirical excess risk for \textit{DP-ShuffleG} compared to DP-SGD. To address this limitation, we propose \textit{Interleaved-ShuffleG}, a hybrid approach that integrates public data samples in private optimization. By alternating optimization steps that use private and public samples, \textit{Interleaved-ShuffleG} effectively reduces empirical excess risk. Our analysis introduces a new optimization framework with surrogate objectives, adaptive noise injection, and a dissimilarity metric, which can be of independent interest. Our experiments on diverse datasets and tasks demonstrate the superiority of \textit{Interleaved-ShuffleG} over several baselines.
• Abstract（参考訳）: 本稿では,差分プライベート (DP) 凸凸の実証的リスク最小化 (ERM) の問題について考察する。 標準のDP-SGDアルゴリズムは理論上は確立されているが、実際の実装では、各イテレーションで置換してサンプリングするのではなく、トレーニングデータを順次トラバースするシャッフル勾配法に頼っていることが多い。 広く使われているにもかかわらず、プライベートシャッフル勾配法(\textit{DP-ShuffleG})の理論的プライバシーと精度のトレードオフは理解されていないままであり、理論と実践の間にギャップが生じる。 本研究では,反復によるプライバシ増幅(PABI)と,Steinの補題の新たな応用を活用し,textit{DP-ShuffleG} の実証的過剰リスク境界を提供する。 以上の結果から,データシャッフルはDP-SGDと比較すると,<textit{DP-ShuffleG} に対する経験的過剰リスクを悪化させることが示された。 この制限に対処するために,公開データサンプルをプライベートな最適化で統合するハイブリッドアプローチである \textit{Interleaved-ShuffleG} を提案する。 プライベートとパブリックのサンプルを使用する最適化ステップを交互に行うことで、‘textit{Interleaved-ShuffleG} は経験的過剰リスクを効果的に低減する。 本分析では,サロゲート目的,適応ノイズ注入,および独立性のある相似性測定値を備えた新しい最適化フレームワークを提案する。 多様なデータセットとタスクに関する実験は、いくつかのベースライン上での \textit{Interleaved-ShuffleG} の優位性を実証している。

関連論文リスト

• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
  我々は、差分プライベート(DP)を保証する重み付きデータに対する差分プライベート凸最適化について検討する。 我々は,制約付きおよび制約なし凸問題に対するAClipped-dpSGDというアルゴリズムに対して,新たな収束結果を確立し,複雑性境界を改善した。
  論文  参考訳（メタデータ） (2022-06-27T01:39:15Z)
• On Private Online Convex Optimization: Optimal Algorithms in $\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
  本研究では,分散分布からサンプリングしたストリーミングデータを用いてDPの凸最適化問題について検討し,逐次到着する。 また、プライベート情報に関連するパラメータを更新し、新しいデータ(しばしばオンラインアルゴリズム)に基づいてリリースする連続リリースモデルについても検討する。 提案アルゴリズムは,1pleq 2$のときの最適余剰リスクと,2pleqinfty$のときの非プライベートな場合の最先端の余剰リスクを線形時間で達成する。
  論文  参考訳（メタデータ） (2022-06-16T12:09:47Z)
• Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates [34.023599653814415]
  ユーザレベルのプライバシの下で、差分的プライベート(DP)行列補完の問題について検討する。 本稿では,Alternating-Least-Squares (ALS) 方式の差分型を設計する。
  論文  参考訳（メタデータ） (2021-07-20T23:19:11Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training [12.386462516398469]
  強力な過剰なリスク境界を提供する効率的で実装が容易な差分プライベート(DP)アルゴリズムを見つけることは、現代の機械学習において重要な問題である。 我々は、滑らかさと強い凸性の存在下で、最もよく知られた$(epsilon, 0)$-DP人口損失境界と最速ランタイムを提供する。 我々はこの理論を2つの学習フレームワーク、傾きERMと逆学習フレームワークに適用する。
  論文  参考訳（メタデータ） (2021-02-09T08:47:06Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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