論文の概要: Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization

• arxiv url: http://arxiv.org/abs/2206.00363v1
• Date: Wed, 1 Jun 2022 10:03:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-02 16:42:46.721582
• Title: Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization
• Title（参考訳）: 微分プライベートな最小値最適化のための独自のアルゴリズム
• Authors: Liang Zhang, Kiran Koshy Thekumparampil, Sewoong Oh, Niao He
• Abstract要約: これらの設定の聖杯は、プライバシーと過剰な人口減少の間の最適なトレードオフを保証することです。 微分プライベート・ミニマックス最適化(DP-SMO)問題を解くための一般的なフレームワークを提供する。 我々のフレームワークは、非滑らかな微分プライベート凸最適化(DP-SCO)のための最近提案されたフェイズド・ERM法[20]から着想を得たものである。
• 参考スコア（独自算出の注目度）: 44.52870407321633
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study differentially private (DP) algorithms for smooth stochastic minimax optimization, with stochastic minimization as a byproduct. The holy grail of these settings is to guarantee the optimal trade-off between the privacy and the excess population loss, using an algorithm with a linear time-complexity in the number of training samples. We provide a general framework for solving differentially private stochastic minimax optimization (DP-SMO) problems, which enables the practitioners to bring their own base optimization algorithm and use it as a black-box to obtain the near-optimal privacy-loss trade-off. Our framework is inspired from the recently proposed Phased-ERM method [20] for nonsmooth differentially private stochastic convex optimization (DP-SCO), which exploits the stability of the empirical risk minimization (ERM) for the privacy guarantee. The flexibility of our approach enables us to sidestep the requirement that the base algorithm needs to have bounded sensitivity, and allows the use of sophisticated variance-reduced accelerated methods to achieve near-linear time-complexity. To the best of our knowledge, these are the first linear-time optimal algorithms, up to logarithmic factors, for smooth DP-SMO when the objective is (strongly-)convex-(strongly-)concave. Additionally, based on our flexible framework, we derive a new family of near-linear time algorithms for smooth DP-SCO with optimal privacy-loss trade-offs for a wider range of smoothness parameters compared to previous algorithms.
• Abstract（参考訳）: 確率最小化を副生成物とするスムーズな確率最小最適化のための微分プライベート(DP)アルゴリズムについて検討した。 これらの設定の聖杯は、トレーニングサンプル数の線形時間複雑度を持つアルゴリズムを用いて、プライバシーと過剰な人口損失の間の最適なトレードオフを保証することである。 そこで本研究では,自己のベース最適化アルゴリズムをブラックボックスとして使用することで,プライバシ損失に近いトレードオフを得ることが可能な,差分プライベートな確率的ミニマックス最適化(dp-smo)問題を解決するための汎用フレームワークを提案する。 提案手法は,プライバシ保証のための経験的リスク最小化 (erm) の安定性を生かした非スムース微分的確率凸最適化 (dp-sco) のための最近提案されたphased-erm法 [20] に着想を得たものである。 提案手法の柔軟性により,ベースアルゴリズムが境界感度を持つ必要のある要件を回避し,線形近傍の時間複雑度を達成するために,高度な分散低減高速化手法を利用可能とした。 我々の知る限りでは、これらのアルゴリズムは(強い)凸-(強い)凹凸のときの滑らかなDP-SMOのための対数係数までの最初の線形時間最適アルゴリズムである。 さらに、我々のフレキシブルなフレームワークに基づいて、従来のアルゴリズムと比較して幅広いスムーズなパラメータに対して最適なプライバシー損失トレードオフを持つ、スムーズなDP-SCOのためのニア線形時間アルゴリズムの新たなファミリーを導出する。

関連論文リスト

• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。 微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。 これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-02-13T02:05:45Z)
• Optimal Rates for Robust Stochastic Convex Optimization [12.620782629498812]
  我々は,$epsilon$-contaminationモデルの下で,極小最適過大リスクを実現するアルゴリズムを開発した。 我々のアルゴリズムは制限的な仮定を必要とせず、非滑らかだがリプシッツ人口減少関数を扱える。
  論文  参考訳（メタデータ） (2024-12-15T00:52:08Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• 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)

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

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