論文の概要: Public-data Assisted Private Stochastic Optimization: Power and
Limitations
- arxiv url: http://arxiv.org/abs/2403.03856v1
- Date: Wed, 6 Mar 2024 17:06:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 14:10:52.466280
- Title: Public-data Assisted Private Stochastic Optimization: Power and
Limitations
- Title(参考訳): 公開データ支援プライベート確率最適化:力と限界
- Authors: Enayat Ullah, Michael Menart, Raef Bassily, Crist\'obal Guzm\'an,
Raman Arora
- Abstract要約: 本稿では,PA-DPアルゴリズムの限界と限界について検討する。
完全な/ラベル付き公開データについては、$tildeOmegabig(minbigfrac1sqrtn+fracsqrtdnepsilon big big)$が過剰なリスクを持つことを示す。
また,PA-DPによる教師あり学習について,テキスト非ラベル公開サンプルを用いて検討した。
- 参考スコア(独自算出の注目度): 30.298342283075172
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the limits and capability of public-data assisted differentially
private (PA-DP) algorithms. Specifically, we focus on the problem of stochastic
convex optimization (SCO) with either labeled or unlabeled public data. For
complete/labeled public data, we show that any $(\epsilon,\delta)$-PA-DP has
excess risk
$\tilde{\Omega}\big(\min\big\{\frac{1}{\sqrt{n_{\text{pub}}}},\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\epsilon}
\big\} \big)$, where $d$ is the dimension, ${n_{\text{pub}}}$ is the number of
public samples, ${n_{\text{priv}}}$ is the number of private samples, and
$n={n_{\text{pub}}}+{n_{\text{priv}}}$. These lower bounds are established via
our new lower bounds for PA-DP mean estimation, which are of a similar form. Up
to constant factors, these lower bounds show that the simple strategy of either
treating all data as private or discarding the private data, is optimal. We
also study PA-DP supervised learning with \textit{unlabeled} public samples. In
contrast to our previous result, we here show novel methods for leveraging
public data in private supervised learning. For generalized linear models (GLM)
with unlabeled public data, we show an efficient algorithm which, given
$\tilde{O}({n_{\text{priv}}}\epsilon)$ unlabeled public samples, achieves the
dimension independent rate $\tilde{O}\big(\frac{1}{\sqrt{{n_{\text{priv}}}}} +
\frac{1}{\sqrt{{n_{\text{priv}}}\epsilon}}\big)$. We develop new lower bounds
for this setting which shows that this rate cannot be improved with more public
samples, and any fewer public samples leads to a worse rate. Finally, we
provide extensions of this result to general hypothesis classes with finite
fat-shattering dimension with applications to neural networks and non-Euclidean
geometries.
- Abstract(参考訳): 公開データ支援微分プライベート(pa-dp)アルゴリズムの限界と能力について検討した。
具体的には、ラベル付きまたはラベルなしの公開データを用いた確率凸最適化(SCO)の問題に焦点を当てる。
完全/ラベルの公開データについては、任意の$(\epsilon,\delta)$-pa-dp が余剰リスク $\tilde{\omega}\big(\min\big\{\frac{1}{\sqrt{n_{\text{pub}}}},\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\epsilon} \big\} \big)$,ただし $d$ は次元、${n_{\text{pub}}}$ は公開サンプル数、${n_{\text{priv}}}$ はプライベートサンプル数、$n={n_{\text{pub}}}+{n_{\text{priv}}}$である。
これらの下界は、同様の形式であるpa-dp平均推定のための新しい下界を介して確立される。
これらの下限は、すべてのデータをプライベートとして扱うか、プライベートデータを破棄するという単純な戦略が最適であることを示している。
また,<textit{unlabeled>公開サンプルを用いたPA-DP指導学習についても検討した。
これまでの結果とは対照的に,私的教師付き学習における公開データ活用の新たな手法を示す。
ラベルなしの公開データを持つ一般化線形モデル (glm) に対して、$\tilde{o}({n_{\text{priv}}}\epsilon)$ ラベルなしの公開サンプルが与えられた場合、次元独立レート $\tilde{o}\big(\frac{1}{\sqrt{{n_{\text{priv}}}}} + \frac{1}{\sqrt{{{n_{\text{priv}}}\epsilon}}\big)$ が得られる効率的なアルゴリズムを示す。
我々は、この設定に対する新しい下限を開発し、この値は、よりパブリックなサンプルでは改善できず、より少ないパブリックなサンプルでは、より悪いレートにつながることを示す。
最後に、この結果をニューラルネットワークや非ユークリッド測地への応用を含む有限脂肪散乱次元の一般仮説クラスに拡張する。
関連論文リスト
- Improved Analysis of Sparse Linear Regression in Local Differential
Privacy Model [38.66115499136791]
局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。
そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。
その結果, 疎線形回帰問題における非私的ケース, 中央DPモデル, 局所DPモデルとの基本的差異が明らかとなった。
論文 参考訳(メタデータ) (2023-10-11T10:34:52Z) - PLAN: Variance-Aware Private Mean Estimation [12.779570691818751]
差分的にプライベートな平均推定は、データ分析と機械学習のためのプライバシ保護アルゴリズムの重要な構成要素である。
ベクトル $boldsymbolsigma$ のスキューを利用する方法を示し、$ell$エラーで(ゼロ桁の)微分プライベート平均推定値を得る。
PLANの有効性を検証するため,合成データと実世界のデータの両方で精度を実証的に評価した。
論文 参考訳(メタデータ) (2023-06-14T21:04:50Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-19T01:09:24Z) - 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) - Efficient Private SCO for Heavy-Tailed Data via Clipping [31.37972684061572]
差分プライベート(DP)の勾配を保証した重み付きデータの凸最適化について検討する。
一般的な凸問題では、過剰な集団リスクを$TildeOleft(fracd1/7sqrtlnfrac(n epsilon)2beta d(nepsilon)2/7right)$と$TildeOleft(fracd1/7lnfrac(nepsilon)2beta d(nepsilon)2
論文 参考訳(メタデータ) (2022-06-27T01:39:15Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳(メタデータ) (2022-06-17T09:24:41Z) - DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。
準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
論文 参考訳(メタデータ) (2022-05-27T02:02:17Z) - User-Level Private Learning via Correlated Sampling [49.453751858361265]
我々は、各ユーザが$m$のサンプルを持ち、プライバシ保護が各ユーザのデータレベルで実施される設定について検討する。
この設定では、より少ない数のユーザーで学習できることが示されます。
論文 参考訳(メタデータ) (2021-10-21T15:33:53Z) - Private Query Release Assisted by Public Data [96.6174729958211]
本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。
我々は、$d/alpha$公開サンプルと$sqrtpd3/2/alpha2$プライベートサンプルのみを用いて、有限VC次元のクエリクラス$mathcalH$の問題を解くことができることを示した。
論文 参考訳(メタデータ) (2020-04-23T02:46:37Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。