論文の概要: Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems

• arxiv url: http://arxiv.org/abs/2104.02988v1
• Date: Wed, 7 Apr 2021 08:37:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-08 19:47:02.289341
• Title: Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems
• Title（参考訳）: 微分的確率的単調変分不等式と鞍点問題に対する最適アルゴリズム
• Authors: Digvijay Boob and Crist\'obal Guzm\'an
• Abstract要約: 差分プライバシー制約下における変動不等式(SVI)とサドル点不等式問題の最初の系統的研究--(DP) NISPP(Noisy Inexact Proximal Point)とNSEG(Noisy Extragradient)の2つのアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 5.051036968777244
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we conduct the first systematic study of stochastic variational inequality (SVI) and stochastic saddle point (SSP) problems under the constraint of differential privacy-(DP). We propose two algorithms: Noisy Stochastic Extragradient (NSEG) and Noisy Inexact Stochastic Proximal Point (NISPP). We show that sampling with replacement variants of these algorithms attain the optimal risk for DP-SVI and DP-SSP. Key to our analysis is the investigation of algorithmic stability bounds, both of which are new even in the nonprivate case, together with a novel "stability implies generalization" result for the gap functions for SVI and SSP problems. The dependence of the running time of these algorithms, with respect to the dataset size $n$, is $n^2$ for NSEG and $\widetilde{O}(n^{3/2})$ for NISPP.
• Abstract（参考訳）: 本研究では,確率的変動不等式(SVI)と確率的サドル点(SSP)の問題を,差分プライバシー(DP)の制約下で初めて体系的に研究する。 本稿では,NISPP(Nuisy Inexact Stochastic Proximal Point)とNSEG(Nuisy Stochastic Exgradient)の2つのアルゴリズムを提案する。 dp-sviとdp-sspの最適リスクは,これらのアルゴリズムの置換型によるサンプリングが達成できることを示す。 解析の鍵となるのはアルゴリズムの安定性境界の研究であり、どちらも非プライベートの場合においても新しいものであり、SVI問題とSSP問題のギャップ関数に対する新しい「安定性は一般化を示唆する」結果である。 これらのアルゴリズムの実行時間の依存は、データセットサイズ$n$に対して、NSEGでは$n^2$、NISPPでは$\widetilde{O}(n^{3/2})$である。

関連論文リスト

• SOREL: A Stochastic Algorithm for Spectral Risks Minimization [1.6574413179773761]
  スペクトルリスクは機械学習、特に現実世界の意思決定において幅広い応用がある。 異なるサンプルポイントの損失に異なる重みを割り当てることで、平均的なパフォーマンスと最悪のパフォーマンスの間にモデルのパフォーマンスを配置することができる。 SORELはスペクトルリスク最小化のための収束保証をもつ最初の勾配に基づくアルゴリズムである。
  論文  参考訳（メタデータ） (2024-07-19T18:20:53Z)
• Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction [26.9632099249085]
  AdaSPSとAdaSLSと呼ばれる2種類の新しいSPSとSLSを提案し、非補間条件における収束を保証する。 我々は, AdaSPS と AdaSLS に新しい分散低減技術を導入し, $smashwidetildemathcalO(n+1/epsilon)$グラデーション評価を必要とするアルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-08-11T10:17:29Z)
• Accelerated stochastic approximation with state-dependent noise [7.4648480208501455]
  勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。 このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。 SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
  論文  参考訳（メタデータ） (2023-07-04T06:06:10Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• 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)
• 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)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)

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

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