論文の概要: Near-Optimal differentially private low-rank trace regression with guaranteed private initialization
- arxiv url: http://arxiv.org/abs/2403.15999v1
- Date: Sun, 24 Mar 2024 03:57:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-26 20:12:47.731525
- Title: Near-Optimal differentially private low-rank trace regression with guaranteed private initialization
- Title（参考訳）: プライベート初期化を保証した準最適個人差分低ランクトレースレグレッション
- Authors: Mengyue Zha,
- Abstract要約: RRd_1times d$におけるランク-r$行列$Mの差分プライベート(DP)推定をトレース回帰モデルの下で検討する。
我々はまた、リーマン最適化(DP-RGrad)に基づいて$M$を推定する微分プライベートアルゴリズムを提案する。
DP-RGradで与えられる推定器は、微分プライバシーというより弱い概念において最適収束率に達することが示されている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study differentially private (DP) estimation of a rank-$r$ matrix $M \in \RR^{d_1\times d_2}$ under the trace regression model with Gaussian measurement matrices. Theoretically, the sensitivity of non-private spectral initialization is precisely characterized, and the differential-privacy-constrained minimax lower bound for estimating $M$ under the Schatten-$q$ norm is established. Methodologically, the paper introduces a computationally efficient algorithm for DP-initialization with a sample size of $n \geq \wt O (r^2 (d_1\vee d_2))$. Under certain regularity conditions, the DP-initialization falls within a local ball surrounding $M$. We also propose a differentially private algorithm for estimating $M$ based on Riemannian optimization (DP-RGrad), which achieves a near-optimal convergence rate with the DP-initialization and sample size of $n \geq \wt O(r (d_1 + d_2))$. Finally, the paper discusses the non-trivial gap between the minimax lower bound and the upper bound of low-rank matrix estimation under the trace regression model. It is shown that the estimator given by DP-RGrad attains the optimal convergence rate in a weaker notion of differential privacy. Our powerful technique for analyzing the sensitivity of initialization requires no eigengap condition between $r$ non-zero singular values.
- Abstract（参考訳）: 我々は、ガウス測度行列を用いたトレース回帰モデルの下で、ランク-r$行列$M \in \RR^{d_1\times d_2}$の微分プライベート(DP)推定について検討した。
理論的には、非プライベートスペクトル初期化の感度を正確に評価し、Schatten-$q$ノルムの下でM$を推定するための差分プライバシー制約されたミニマックス下限を定めている。
提案手法は,DP初期化を計算効率よく行うアルゴリズムであり,サンプルサイズは$n \geq \wt O (r^2 (d_1\vee d_2))$である。
一定の規則性条件の下では、DP初期化はM$を囲む局所球に該当する。
また,DP-初期化とサンプルサイズが$n \geq \wt O(r (d_1 + d_2))$とほぼ最適な収束率が得られるような,リーマン最適化(DP-RGrad)に基づいて$M$を推定する微分プライベートアルゴリズムを提案する。
最後に,ミニマックス下界と低ランク行列推定の上界との非自明なギャップをトレース回帰モデルで論じる。
DP-RGradで与えられる推定器は、微分プライバシーというより弱い概念において最適収束率に達することが示されている。
初期化の感度を分析する強力な手法は、$r$非ゼロ特異値間の固有ギャップ条件を必要としない。
関連論文リスト
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions [19.008521454738425]
重み付き勾配を持つ差分プライベート凸最適化(DP-SCO)の問題を考察し、一様境界ではなく、サンプル関数のリプシッツ定数上の$ktextth$-momentを仮定する。
Gcdot frac 1 sqrt n + G_k cdot (fracsqrt dnepsilon) 1 の誤差を達成し、重み付け設定における第1次最適率(対数係数まで)を得るための新しい還元ベースのアプローチを提案する。
論文 参考訳（メタデータ） (2024-06-04T21:26:29Z) - Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。
我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
論文 参考訳（メタデータ） (2024-05-30T18:20:35Z) - Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-04-16T20:01:10Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy [23.12198546384976]
後方サンプリングは$varepsilon$-pure差分プライバシー保証を提供する。
これは、$(varepsilon,delta)$-approximate DPによって引き起こされた潜在的に束縛されていないプライバシー侵害に悩まされない。
しかし実際には、マルコフ連鎖モンテカルロのような近似的なサンプリング手法を適用する必要がある。
論文 参考訳（メタデータ） (2023-10-23T07:54:39Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - 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) - 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) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。