論文の概要: Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed
Data
- arxiv url: http://arxiv.org/abs/2201.03204v1
- Date: Mon, 10 Jan 2022 08:17:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-11 20:58:39.226465
- Title: Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed
Data
- Title（参考訳）: 重み付きデータを用いた微分プライベート$\ell_1$-norm線形回帰
- Authors: Di Wang and Jinhui Xu
- Abstract要約: 我々は$epsilon$-DPモデルにおける$ell_1$-norm線形回帰に注目した。
我々は高い確率で$tildeO(sqrtfracdnepsilon)$の上限を達成することができることを示す。
我々のアルゴリズムは、データの各座標が有界なモーメントを持つような、よりリラックスしたケースにも拡張できる。
- 参考スコア（独自算出の注目度）: 22.233705161499273
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of Differentially Private Stochastic Convex Optimization
(DP-SCO) with heavy-tailed data. Specifically, we focus on the $\ell_1$-norm
linear regression in the $\epsilon$-DP model. While most of the previous work
focuses on the case where the loss function is Lipschitz, here we only need to
assume the variates has bounded moments. Firstly, we study the case where the
$\ell_2$ norm of data has bounded second order moment. We propose an algorithm
which is based on the exponential mechanism and show that it is possible to
achieve an upper bound of $\tilde{O}(\sqrt{\frac{d}{n\epsilon}})$ (with high
probability). Next, we relax the assumption to bounded $\theta$-th order moment
with some $\theta\in (1, 2)$ and show that it is possible to achieve an upper
bound of $\tilde{O}(({\frac{d}{n\epsilon}})^\frac{\theta-1}{\theta})$. Our
algorithms can also be extended to more relaxed cases where only each
coordinate of the data has bounded moments, and we can get an upper bound of
$\tilde{O}({\frac{d}{\sqrt{n\epsilon}}})$ and
$\tilde{O}({\frac{d}{({n\epsilon})^\frac{\theta-1}{\theta}}})$ in the second
and $\theta$-th moment case respectively.
- Abstract（参考訳）: 重み付きデータを用いた微分プライベート確率凸最適化(dp-sco)の問題について検討する。
具体的には、$\epsilon$-DPモデルにおける$\ell_1$-norm線形回帰に焦点を当てる。
前回の研究のほとんどは損失関数がリプシッツである場合に焦点を当てているが、ここでは変数が有界なモーメントを持つと仮定するだけでよい。
まず、データの$\ell_2$ノルムが2次モーメントに有界な場合について検討する。
指数関数機構に基づくアルゴリズムを提案し,高い確率で$\tilde{o}(\sqrt{\frac{d}{n\epsilon}})$(高い確率で)の上限を達成することができることを示した。
次に、ある$\theta\in (1, 2)$で有界な$\theta$-第2次順序モーメントへの仮定を緩和し、$\tilde{O}(({\frac{d}{n\epsilon}})^\frac{\theta-1}{\theta})$の上限を達成することができることを示す。
我々のアルゴリズムは、データの各座標が有界なモーメントを持つようなよりゆるやかなケースにも拡張することができ、上界の$\tilde{O}({\frac{d}{\sqrt{n\epsilon}}})$と$\tilde{O}({\frac{d}{({n\epsilon})^\frac{\theta-1}{\theta}}})$をそれぞれ第2のモーメントケースと$\theta$-thのモーメントケースで得ることができる。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Profile Reconstruction from Private Sketches [13.929335175122265]
$mathcalD$から$n$のアイテムの多重集合が与えられたとき、強調される再構成問題は、$t = 0, 1, dots, n$ に対して、$mathcalD$ のアイテムの分数 $vecf[t]$ を正確に $tfty 倍と見積もることである。
分散空間制約付き環境での個人プロファイル推定について検討し,マルチセットの更新可能なプライベートスケッチを維持したいと考える。
LPベースの手法の高速化方法を示します
論文 参考訳（メタデータ） (2024-06-03T09:51:28Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳（メタデータ） (2023-04-05T07:24:19Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。
第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
論文 参考訳（メタデータ） (2021-07-31T22:23:39Z) - High Dimensional Differentially Private Stochastic Optimization with
Heavy-tailed Data [8.55881355051688]
本研究では,高次元空間における重み付きデータを用いたDP-SCOの問題に関する最初の研究を行う。
損失関数が滑らかで、その勾配が第二次モーメントに有界ならば、$epsilon$-DPモデルで$tildeO(fraclog d(nepsilon)frac13)$の(高い確率)誤差境界(過剰な集団リスク)を得ることが可能である。
論文の第2部では,重み付きデータを用いたスパース学習について検討した。
論文 参考訳（メタデータ） (2021-07-23T11:03:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。