論文の概要: Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry

• arxiv url: http://arxiv.org/abs/2411.05198v1
• Date: Thu, 07 Nov 2024 21:45:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-11 14:55:53.420215
• Title: Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry
• Title（参考訳）: 確率的サドル点と変分不等式のための私的アルゴリズム:ユークリッド幾何学を超えて
• Authors: Raef Bassily, Cristóbal Guzmán, Michael Menart,
• Abstract要約: 我々は、$(epsilon,delta)$-differential privacy(DP)の制約の下で、サドル点問題(SSP)と変分不等式(SVI)を研究する。 強いSPギャップ上の$tildeObig(frac1sqrtn + fracsqrtdnepsilonbig)$のバウンドを得る。 我々は、$の強いVI-ギャップ上の有界値を得る最初の解析を提供する。
• 参考スコア（独自算出の注目度）: 20.068722738606287
• License:
• Abstract: In this work, we conduct a systematic study of stochastic saddle point problems (SSP) and stochastic variational inequalities (SVI) under the constraint of $(\epsilon,\delta)$-differential privacy (DP) in both Euclidean and non-Euclidean setups. We first consider Lipschitz convex-concave SSPs in the $\ell_p/\ell_q$ setup, $p,q\in[1,2]$. Here, we obtain a bound of $\tilde{O}\big(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}\big)$ on the strong SP-gap, where $n$ is the number of samples and $d$ is the dimension. This rate is nearly optimal for any $p,q\in[1,2]$. Without additional assumptions, such as smoothness or linearity requirements, prior work under DP has only obtained this rate when $p=q=2$ (i.e., only in the Euclidean setup). Further, existing algorithms have each only been shown to work for specific settings of $p$ and $q$ and under certain assumptions on the loss and the feasible set, whereas we provide a general algorithm for DP SSPs whenever $p,q\in[1,2]$. Our result is obtained via a novel analysis of the recursive regularization algorithm. In particular, we develop new tools for analyzing generalization, which may be of independent interest. Next, we turn our attention towards SVIs with a monotone, bounded and Lipschitz operator and consider $\ell_p$-setups, $p\in[1,2]$. Here, we provide the first analysis which obtains a bound on the strong VI-gap of $\tilde{O}\big(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}\big)$. For $p-1=\Omega(1)$, this rate is near optimal due to existing lower bounds. To obtain this result, we develop a modified version of recursive regularization. Our analysis builds on the techniques we develop for SSPs as well as employing additional novel components which handle difficulties arising from adapting the recursive regularization framework to SVIs.
• Abstract（参考訳）: 本研究では, ユークリッド系および非ユークリッド系において, 確率的サドル点問題 (SSP) と確率的変分不等式 (SVI) を$(\epsilon,\delta)$-differential privacy (DP) の制約の下で体系的に研究する。 最初に、Lipschitz convex-concave SSPsを$\ell_p/\ell_q$ setup, $p,q\in[1,2]$とみなす。 ここでは、強いSPギャップ上の$\tilde{O}\big(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}\big)$の有界値を得る。 この値は任意の$p,q\in[1,2]$に対してほぼ最適である。 滑らか性や線形性といった追加の仮定がなければ、DPの下での事前の作業は、$p=q=2$(つまりユークリッドのセットアップでのみ)のときにのみ得られる。 さらに、既存のアルゴリズムは、それぞれ$p$と$q$の特定の設定でのみ動作し、損失と実現可能な集合に関する特定の仮定の下でのみ動作することが示され、一方、$p,q\in[1,2]$ のとき、DP SSPに対して一般的なアルゴリズムを提供する。 その結果,再帰正則化アルゴリズムの新たな解析によって得られた。 特に,独立性のある一般化を解析するための新しいツールを開発する。 次に、単調で有界なリプシッツ作用素でSVIに注意を向け、$\ell_p$-setups, $p\in[1,2]$を考える。 ここでは、$\tilde{O}\big(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}\big)$ の強い VI-ギャップ上の有界値を求める最初の解析を行う。 p-1=\Omega(1)$の場合、この値は既存の下界のためにほぼ最適である。 この結果を得るために、再帰正規化の修正版を開発する。 我々の分析は、SSP向けに開発した技術に基づいており、再帰的正規化フレームワークをSVIに適応させることによって生じる困難に対処する新しいコンポーネントも採用しています。

関連論文リスト

• Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap [12.446156563700482]
  凸凹型リプシッツサドル点問題は、$(epsilon,delta)$differential privacyの制約の下で解決可能であることを示す。 また、安定性と精度の間には根本的なトレードオフがあることも示している。
  論文  参考訳（メタデータ） (2023-02-24T21:50:02Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Private Convex Optimization via Exponential Mechanism [16.867534746193833]
  我々は、$ellcave2$ regularizerを$F(x)$に追加することで指数的なメカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を$(epsilon,delta)$-DPで回復することを示した。 また、DP-SCOに対して$widetildeO(n min(d, n))クエリを使って$f_i(x)にこのメカニズムを実装する方法を示す。
  論文  参考訳（メタデータ） (2022-03-01T06:51:03Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
  雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。 私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
  論文  参考訳（メタデータ） (2021-03-01T19:48:44Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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