論文の概要: Privacy-Utility Tradeoff of OLS with Random Projections
- arxiv url: http://arxiv.org/abs/2309.01243v1
- Date: Sun, 3 Sep 2023 19:07:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-06 20:42:51.407470
- Title: Privacy-Utility Tradeoff of OLS with Random Projections
- Title(参考訳): ランダムプロジェクションを用いたolsのプライバシー利用トレードオフ
- Authors: Yun Lu, Malik Magdon-Ismail, Yu Wei, Vassilis Zikas
- Abstract要約: 基本ML問題、線形常用最小二乗(OLS)、すなわち$ell$-regressionの差分プライバシー(DP)について検討する。
我々の重要な結果は、ALS問題に対するランダム化ソリューションであるALS (ALS) (Sarlos, 2006) がプライバシーを保護していることである。
ALSは、代替のプライベートOLSアルゴリズムと比較して、変更やノイズを発生させることなく、より優れたプライバシ/ユーティリティトレードオフを実現する。
- 参考スコア(独自算出の注目度): 8.316835880556104
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the differential privacy (DP) of a core ML problem, linear ordinary
least squares (OLS), a.k.a. $\ell_2$-regression. Our key result is that the
approximate LS algorithm (ALS) (Sarlos, 2006), a randomized solution to the OLS
problem primarily used to improve performance on large datasets, also preserves
privacy. ALS achieves a better privacy/utility tradeoff, without modifications
or further noising, when compared to alternative private OLS algorithms which
modify and/or noise OLS. We give the first {\em tight} DP-analysis for the ALS
algorithm and the standard Gaussian mechanism (Dwork et al., 2014) applied to
OLS. Our methodology directly improves the privacy analysis of (Blocki et al.,
2012) and (Sheffet, 2019)) and introduces new tools which may be of independent
interest: (1) the exact spectrum of $(\epsilon, \delta)$-DP parameters (``DP
spectrum") for mechanisms whose output is a $d$-dimensional Gaussian, and (2)
an improved DP spectrum for random projection (compared to (Blocki et al.,
2012) and (Sheffet, 2019)).
All methods for private OLS (including ours) assume, often implicitly,
restrictions on the input database, such as bounds on leverage and residuals.
We prove that such restrictions are necessary. Hence, computing the privacy of
mechanisms such as ALS must estimate these database parameters, which can be
infeasible in big datasets. For more complex ML models, DP bounds may not even
be tractable. There is a need for blackbox DP-estimators (Lu et al., 2022)
which empirically estimate a data-dependent privacy. We demonstrate the
effectiveness of such a DP-estimator by empirically recovering a DP-spectrum
that matches our theory for OLS. This validates the DP-estimator in a
nontrivial ML application, opening the door to its use in more complex
nonlinear ML settings where theory is unavailable.
- Abstract(参考訳): 基本ML問題、線形常用最小二乗(OLS)、すなわち$\ell_2$-regressionの差分プライバシー(DP)について検討する。
我々の主要な結果は、ALSアルゴリズム (ALS) (Sarlos, 2006) が、主に大規模なデータセットのパフォーマンス向上に使用されるLS問題のランダム化ソリューションであり、プライバシも保護されていることである。
ALSは、OLSを修正または/またはノイズする代替のプライベートOLSアルゴリズムと比較して、変更やノイズを発生させることなく、より優れたプライバシ/ユーティリティトレードオフを実現する。
我々はALSアルゴリズムの最初のDP分析と標準ガウス機構(Dwork et al., 2014)をOLSに適用する。
本手法は, (blocki et al., 2012) と (sheffet, 2019) のプライバシ解析を直接改善し, (1) 出力が $d$-dimensional gaussian である機構に対して $(\epsilon, \delta)$-dp パラメータ (```dp spectrum") の正確なスペクトル, (2) ランダム投影のための dp スペクトルの改善 (blocki et al., 2012) と (sheffet, 2019) という,独立した関心を持つ新しいツールを導入する。
プライベートOLS(うちを含む)のすべてのメソッドは、しばしば暗黙的に、レバレッジと残差のバウンドのような入力データベースに制限を仮定します。
私たちはそのような制限が必要であることを証明します。
したがって、ALSのようなメカニズムのプライバシを計算するには、これらのデータベースパラメータを推定する必要がある。
より複雑なMLモデルでは、DP境界は引けないかもしれない。
データ依存プライバシを実証的に見積もるブラックボックスDP推定器(Lu et al., 2022)が必要である。
OLS理論と一致するDPスペクトルを実証的に復元することにより,そのようなDP推定器の有効性を実証する。
これは非自明なMLアプリケーションでDP推定器を検証し、理論が利用できないより複雑な非線形ML設定で使用するための扉を開く。
関連論文リスト
- Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳(メタデータ) (2024-04-19T06:24:22Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Synthesizing Tight Privacy and Accuracy Bounds via Weighted Model Counting [5.552645730505715]
2つの中核的な課題は、DPアルゴリズムの分布の表現的でコンパクトで効率的な符号化を見つけることである。
プライバシーと正確性に縛られた合成法を開発することで、最初の課題に対処する。
DPアルゴリズムに固有の対称性を活用するためのフレームワークを開発する。
論文 参考訳(メタデータ) (2024-02-26T19:29:46Z) - Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise For Sum, Count, and Vote [54.34628844260993]
本稿では, 総和, カウント, 投票の簡単な問題を考察し, 両方の設定で高速なアルゴリズムを提供する。
我々は、最適偏微分プライベートな$K$-norm機構サンプリング器を構築し、最適な偏微分プライベートなガウス雑音に対する閉形式式を導出する。
論文 参考訳(メタデータ) (2023-09-27T17:09:36Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳(メタデータ) (2023-01-31T18:47:42Z) - Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints [8.261182037130407]
局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
論文 参考訳(メタデータ) (2023-01-09T18:36:49Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳(メタデータ) (2022-12-15T18:27:39Z) - 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) - Shuffle Gaussian Mechanism for Differential Privacy [2.7564955518050693]
$$ epsilon(lambda) leq frac1lambda-1logleft(frace-da/2sigma2ndasum_substackk_+dotsc+k_n=lambda;k_nlambda!k_nlambda!k_nlambda!
論文 参考訳(メタデータ) (2022-06-20T04:54:16Z) - Auditing Differential Privacy in High Dimensions with the Kernel Quantum
R\'enyi Divergence [29.796646032324514]
本稿では,確率分布の新たな相違点に基づく差分プライバシーの緩和を提案する。
正規化カーネル R'enyi の発散は高次元においてもサンプルから推定可能であることを示す。
論文 参考訳(メタデータ) (2022-05-27T12:34:17Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳(メタデータ) (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。