論文の概要: (Nearly) Optimal Private Linear Regression via Adaptive Clipping

• arxiv url: http://arxiv.org/abs/2207.04686v2
• Date: Tue, 12 Jul 2022 21:09:52 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-14 11:33:58.472345
• Title: (Nearly) Optimal Private Linear Regression via Adaptive Clipping
• Title（参考訳）: 適応クリッピングによる(ほぼ)最適プライベート線形回帰
• Authors: Prateek Varshney, Abhradeep Thakurta, Prateek Jain
• Abstract要約: 固定されたガウス型分布から各データ点をサンプリングする微分プライベート線形回帰問題について検討する。 本稿では,各イテレーションの点を置換せずにサンプリングする1パスのミニバッチ勾配勾配法(DP-AMBSSGD)を提案し,解析する。
• 参考スコア（独自算出の注目度）: 22.639650869444395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of differentially private linear regression where each data point is sampled from a fixed sub-Gaussian style distribution. We propose and analyze a one-pass mini-batch stochastic gradient descent method (DP-AMBSSGD) where points in each iteration are sampled without replacement. Noise is added for DP but the noise standard deviation is estimated online. Compared to existing $(\epsilon, \delta)$-DP techniques which have sub-optimal error bounds, DP-AMBSSGD is able to provide nearly optimal error bounds in terms of key parameters like dimensionality $d$, number of points $N$, and the standard deviation $\sigma$ of the noise in observations. For example, when the $d$-dimensional covariates are sampled i.i.d. from the normal distribution, then the excess error of DP-AMBSSGD due to privacy is $\frac{\sigma^2 d}{N}(1+\frac{d}{\epsilon^2 N})$, i.e., the error is meaningful when number of samples $N= \Omega(d \log d)$ which is the standard operative regime for linear regression. In contrast, error bounds for existing efficient methods in this setting are: $\mathcal{O}\big(\frac{d^3}{\epsilon^2 N^2}\big)$, even for $\sigma=0$. That is, for constant $\epsilon$, the existing techniques require $N=\Omega(d\sqrt{d})$ to provide a non-trivial result.
• Abstract（参考訳）: 本研究では,各データポイントを固定サブガウシアン分布からサンプリングした微分プライベート線形回帰問題について検討する。 我々は,各イテレーションのポイントを置換せずにサンプリングした1パスミニバッチ確率勾配降下法(dp-ambssgd)を提案し,解析する。 DPにはノイズが追加されるが、ノイズ標準偏差はオンラインで推定される。 サブ最適誤差境界を持つ既存の$(\epsilon, \delta)$-dp技術と比較して、dp-ambssgdは、次元$d$、点数$n$、観測におけるノイズの標準偏差$\sigma$といった重要なパラメータの観点で、ほぼ最適な誤差境界を提供できる。 例えば、通常の分布から$d$次元の共変体をサンプリングする場合、プライバシーによるDP-AMBSSGDの過大な誤差は$\frac{\sigma^2 d}{N}(1+\frac{d}{\epsilon^2 N})$、つまり、サンプル数$N= \Omega(d \log d)$が線形回帰の標準的な操作規則であるときに有意である。 対照的に、この設定における既存の効率的なメソッドの誤差境界は、$\mathcal{O}\big(\frac{d^3}{\epsilon^2 N^2}\big)$, even for $\sigma=0$である。 つまり、定数$\epsilon$の場合、既存のテクニックは非自明な結果を与えるために$N=\Omega(d\sqrt{d})$を必要とする。

関連論文リスト

• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model [38.66115499136791]
  局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。 そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。 その結果, 疎線形回帰問題における非私的ケース, 中央DPモデル, 局所DPモデルとの基本的差異が明らかとなった。
  論文  参考訳（メタデータ） (2023-10-11T10:34:52Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
  DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。 準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
  論文  参考訳（メタデータ） (2022-05-27T02:02:17Z)
• SDP Achieves Exact Minimax Optimality in Phase Synchronization [19.909352968029584]
  我々は、ノイズ測定$Y=z*z*+sigma WinmathbbCntimes ntimes nで位相同期問題を研究する。 SDPが誤差境界$ (1+o)fracnp22np$を2乗の$ell$損失で達成することを証明する。
  論文  参考訳（メタデータ） (2021-01-07T03:14:05Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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