論文の概要: Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization
- arxiv url: http://arxiv.org/abs/2503.18317v1
- Date: Mon, 24 Mar 2025 03:51:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-25 14:34:43.962389
- Title: Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization
- Title(参考訳): 微分プライベート非凸-ストロングリ-コンケーブ最小値最適化の高速化
- Authors: Ruijia Zhang, Mingxi Lei, Meng Ding, Zihang Xiang, Jinhui Xu, Di Wang,
- Abstract要約: 差分プライバシー(DP)モデルにおける最小値最適化の問題について検討する。
経験的リスク関数の Descent $l$-norm が $tO(n)(n)$ で上界となる推定器を得ることが可能である。
- 参考スコア(独自算出の注目度): 10.913566070767596
- License:
- Abstract: In this paper, we study the problem of (finite sum) minimax optimization in the Differential Privacy (DP) model. Unlike most of the previous studies on the (strongly) convex-concave settings or loss functions satisfying the Polyak-Lojasiewicz condition, here we mainly focus on the nonconvex-strongly-concave one, which encapsulates many models in deep learning such as deep AUC maximization. Specifically, we first analyze a DP version of Stochastic Gradient Descent Ascent (SGDA) and show that it is possible to get a DP estimator whose $l_2$-norm of the gradient for the empirical risk function is upper bounded by $\tilde{O}(\frac{d^{1/4}}{({n\epsilon})^{1/2}})$, where $d$ is the model dimension and $n$ is the sample size. We then propose a new method with less gradient noise variance and improve the upper bound to $\tilde{O}(\frac{d^{1/3}}{(n\epsilon)^{2/3}})$, which matches the best-known result for DP Empirical Risk Minimization with non-convex loss. We also discussed several lower bounds of private minimax optimization. Finally, experiments on AUC maximization, generative adversarial networks, and temporal difference learning with real-world data support our theoretical analysis.
- Abstract(参考訳): 本稿では,差分プライバシー(DP)モデルにおける最小値最適化の問題について検討する。
ポリアック・ロジャシエヴィチ条件を満たす(強く)凸凹の設定や損失関数に関する以前の研究とは異なり、ここでは、深いAUCの最大化のような深層学習において多くのモデルをカプセル化する非凸凸凸函数に主に焦点をあてる。
具体的には、まずSGDA(Stochastic Gradient Descent Ascent)のDPバージョンを分析し、経験的リスク関数の勾配の$l_2$-normが$\tilde{O}(\frac{d^{1/4}}{({n\epsilon})^{1/2}} の上界を持つDP推定器を得ることが可能であることを示す。
次に、勾配雑音の分散を小さくし、上限を$\tilde{O}(\frac{d^{1/3}}{(n\epsilon)^{2/3}})$に改善する手法を提案する。
また、プライベートミニマックス最適化のいくつかの下限についても論じている。
最後に、AUCの最大化、生成的敵ネットワーク、実世界のデータを用いた時間差学習に関する実験が、我々の理論解析を支持した。
関連論文リスト
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates [15.27596975662702]
重み付き勾配を用いたDP最適化の最適速度を達成するアルゴリズムについて検討する。
その結果,DP下での凸最適化の理論的限界が達成可能であることを示す。
論文 参考訳(メタデータ) (2024-08-19T11:07:05Z) - Near-Optimal differentially private low-rank trace regression with guaranteed private initialization [0.0]
RRd_1times d$におけるランク-r$行列$Mの差分プライベート(DP)推定をトレース回帰モデルの下で検討する。
我々はまた、リーマン最適化(DP-RGrad)に基づいて$M$を推定する微分プライベートアルゴリズムを提案する。
DP-RGradで与えられる推定器は、微分プライバシーというより弱い概念において最適収束率に達することが示されている。
論文 参考訳(メタデータ) (2024-03-24T03:57:21Z) - DIFF2: Differential Private Optimization via Gradient Differences for
Nonconvex Distributed Learning [58.79085525115987]
以前の研究でよく知られたユーティリティ境界は$widetilde O(d2/3/(nvarepsilon_mathrmDP)4/3)$である。
本稿では,差分プライベートフレームワークを構築した mphDIFF2 (DIFFerential private via DIFFs) という新しい差分プライベートフレームワークを提案する。
大域的な降下を持つ$mphDIFF2は$widetilde O(d2/3/(nvarepsilon_mathrmDP)4/3の効用を達成する
論文 参考訳(メタデータ) (2023-02-08T05:19:01Z) - Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problems [26.676582181833584]
ミニマックス問題は、多くの機械学習モデルに広く応用されているため、近年大きな注目を集めている。
そこで我々は,アセンチュムミニマックス問題に対する分散分散勾配降下法を新たに開発した。
我々の研究は、この種のミニマックス問題に対してそのような理論的複雑さを最初に達成するものである。
論文 参考訳(メタデータ) (2022-12-06T03:25:44Z) - Estimating the minimizer and the minimum value of a regression function
under passive design [72.85024381807466]
最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。
2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
論文 参考訳(メタデータ) (2022-11-29T18:38:40Z) - Restricted Strong Convexity of Deep Learning Models with Smooth
Activations [31.003601717265006]
本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。
Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。
深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
論文 参考訳(メタデータ) (2022-09-29T21:24:26Z) - 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) - KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。
我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
論文 参考訳(メタデータ) (2022-05-27T19:39:24Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳(メタデータ) (2020-06-24T06:01:24Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳(メタデータ) (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。