論文の概要: Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap

• arxiv url: http://arxiv.org/abs/2302.12909v2
• Date: Thu, 29 Jun 2023 16:22:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-30 16:55:32.925073
• Title: Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap
• Title（参考訳）: 強ギャップに対する最適速度をもつ確率的サドル点問題に対する微分プライベートアルゴリズム
• Authors: Raef Bassily and Crist\'obal Guzm\'an and Michael Menart
• Abstract要約: 凸凹型リプシッツサドル点問題は、$(epsilon,delta)$differential privacyの制約の下で解決可能であることを示す。 また、安定性と精度の間には根本的なトレードオフがあることも示している。
• 参考スコア（独自算出の注目度）: 12.446156563700482
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that convex-concave Lipschitz stochastic saddle point problems (also known as stochastic minimax optimization) can be solved under the constraint of $(\epsilon,\delta)$-differential privacy with \emph{strong (primal-dual) gap} rate of $\tilde O\big(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}\big)$, where $n$ is the dataset size and $d$ is the dimension of the problem. This rate is nearly optimal, based on existing lower bounds in differentially private stochastic optimization. Specifically, we prove a tight upper bound on the strong gap via novel implementation and analysis of the recursive regularization technique repurposed for saddle point problems. We show that this rate can be attained with $O\big(\min\big\{\frac{n^2\epsilon^{1.5}}{\sqrt{d}}, n^{3/2}\big\}\big)$ gradient complexity, and $\tilde{O}(n)$ gradient complexity if the loss function is smooth. As a byproduct of our method, we develop a general algorithm that, given a black-box access to a subroutine satisfying a certain $\alpha$ primal-dual accuracy guarantee with respect to the empirical objective, gives a solution to the stochastic saddle point problem with a strong gap of $\tilde{O}(\alpha+\frac{1}{\sqrt{n}})$. We show that this $\alpha$-accuracy condition is satisfied by standard algorithms for the empirical saddle point problem such as the proximal point method and the stochastic gradient descent ascent algorithm. Further, we show that even for simple problems it is possible for an algorithm to have zero weak gap and suffer from $\Omega(1)$ strong gap. We also show that there exists a fundamental tradeoff between stability and accuracy. Specifically, we show that any $\Delta$-stable algorithm has empirical gap $\Omega\big(\frac{1}{\Delta n}\big)$, and that this bound is tight. This result also holds also more specifically for empirical risk minimization problems and may be of independent interest.
• Abstract（参考訳）: n$ がデータセットサイズであり、$d$ が問題の次元である場合、convex-concave lipschitz stochastic saddle point problem (stochastic minimax optimization) は $(\epsilon,\delta)$-differential privacy with \emph{strong (primal-dual) gap} rate of $\tilde o\big(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}\big)$ で解くことができる。 この速度はほぼ最適であり、微分プライベート確率最適化の既存の下限に基づいている。 具体的には,サドル点問題に対する再帰正則化手法の斬新な実装と解析を通じて,強いギャップの強い上限を証明した。 この値は、損失関数が滑らかであれば、$O\big(\min\big\{\frac{n^2\epsilon^{1.5}}{\sqrt{d}}, n^{3/2}\big\}\big)$勾配複雑性、$\tilde{O}(n)$勾配複雑性で達成できることを示す。 この手法の副産物として,経験的目的に対して一定の$\alpha$素数的精度保証を満たしたサブルーチンへのブラックボックスアクセスを与えられた場合,確率的サドルポイント問題に対して,$\tilde{o}(\alpha+\frac{1}{\sqrt{n}})$という強いギャップを持つ解を与える汎用アルゴリズムを開発した。 この$\alpha$-accuracy条件は、近位点法や確率勾配降下昇降法のような経験的鞍点問題に対する標準アルゴリズムによって満たされていることを示す。 さらに,単純な問題であっても,アルゴリズムがゼロの弱ギャップを持ち,$\Omega(1)$強ギャップに悩まされることが示されている。 また、安定性と精度の間には根本的なトレードオフがあることも示している。 具体的には、任意の$\Delta$-stableアルゴリズムは経験的ギャップ$\Omega\big(\frac{1}{\Delta n}\big)$であり、この境界は厳密であることを示す。 この結果は、経験的リスク最小化の問題にも特に当てはまり、独立した関心を持つ可能性がある。

関連論文リスト

• Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
  多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。 我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
  論文  参考訳（メタデータ） (2024-03-05T12:28:00Z)
• Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates [33.46648653842542]
  我々は,KL(Kurdyka-Lojasiewicz)条件を満たす損失に対する個人的経験的リスク問題について検討した。 近似点法のプライベート実装で$tildeObig(big(fracsqrtdnsqrtrhobig)kappabig)を実現できることを示す。
  論文  参考訳（メタデータ） (2023-11-22T15:12:42Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization [47.27237492375659]
  双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。 Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
  論文  参考訳（メタデータ） (2022-01-19T05:56:19Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• No quantum speedup over gradient descent for non-smooth convex optimization [22.16973542453584]
  ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。 私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。 下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
  論文  参考訳（メタデータ） (2020-10-05T06:32:47Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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