論文の概要: Improved Analysis of Sparse Linear Regression in Local Differential
Privacy Model
- arxiv url: http://arxiv.org/abs/2310.07367v1
- Date: Wed, 11 Oct 2023 10:34:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-12 23:13:53.353705
- Title: Improved Analysis of Sparse Linear Regression in Local Differential
Privacy Model
- Title（参考訳）: 局所微分プライバシーモデルにおけるスパース線形回帰解析の改善
- Authors: Liyang Zhu, Meng Ding, Vaneet Aggarwal, Jinhui Xu, Di Wang
- Abstract要約: 局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。
そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。
その結果, 疎線形回帰問題における非私的ケース, 中央DPモデル, 局所DPモデルとの基本的差異が明らかとなった。
- 参考スコア（独自算出の注目度）: 38.66115499136791
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we revisit the problem of sparse linear regression in the
local differential privacy (LDP) model. Existing research in the
non-interactive and sequentially local models has focused on obtaining the
lower bounds for the case where the underlying parameter is $1$-sparse, and
extending such bounds to the more general $k$-sparse case has proven to be
challenging. Moreover, it is unclear whether efficient non-interactive LDP
(NLDP) algorithms exist. To address these issues, we first consider the problem
in the $\epsilon$ non-interactive LDP model and provide a lower bound of
$\Omega(\frac{\sqrt{dk\log d}}{\sqrt{n}\epsilon})$ on the $\ell_2$-norm
estimation error for sub-Gaussian data, where $n$ is the sample size and $d$ is
the dimension of the space. We propose an innovative NLDP algorithm, the very
first of its kind for the problem. As a remarkable outcome, this algorithm also
yields a novel and highly efficient estimator as a valuable by-product. Our
algorithm achieves an upper bound of
$\tilde{O}({\frac{d\sqrt{k}}{\sqrt{n}\epsilon}})$ for the estimation error when
the data is sub-Gaussian, which can be further improved by a factor of
$O(\sqrt{d})$ if the server has additional public but unlabeled data. For the
sequentially interactive LDP model, we show a similar lower bound of
$\Omega({\frac{\sqrt{dk}}{\sqrt{n}\epsilon}})$. As for the upper bound, we
rectify a previous method and show that it is possible to achieve a bound of
$\tilde{O}(\frac{k\sqrt{d}}{\sqrt{n}\epsilon})$. Our findings reveal
fundamental differences between the non-private case, central DP model, and
local DP model in the sparse linear regression problem.
- Abstract（参考訳）: 本稿では,局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。
非対話的かつシーケンシャルな局所モデルにおける既存の研究は、基礎となるパラメータが$$-sparseである場合の下限を得ることに集中しており、より一般的な$k$-sparseケースへの拡張は困難であることが証明されている。
さらに,非インタラクティブLPP (NLDP) アルゴリズムが存在するかどうかも明らかでない。
これらの問題に対処するために、まず、$\epsilon$非インタラクティブなldpモデルで問題を考察し、$n$がサンプルサイズで$d$が空間の次元であるサブガウスデータに対する$\ell_2$-norm推定誤差に基づいて$\omega(\frac{\sqrt{dk\log d}}{\sqrt{n}\epsilon})を低く設定する。
そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。
驚くべき結果として、このアルゴリズムは価値ある副産物として、新規で高効率な推定器も生み出す。
このアルゴリズムは、データがサブガウジアンである場合の推定誤差に対して$\tilde{o}({\frac{d\sqrt{k}}{\sqrt{n}\epsilon}})$の上限を達成し、サーバがパブリックだがラベル付きデータを持っている場合は$o(\sqrt{d})$の係数でさらに改善することができる。
逐次的対話型 LDP モデルでは、同様の下界の$\Omega({\frac{\sqrt{dk}}{\sqrt{n}\epsilon}})$を示す。
上界については、以前の方法を修正し、$\tilde{O}(\frac{k\sqrt{d}}{\sqrt{n}\epsilon})$ を成立させることができることを示す。
スパース線形回帰問題では,非プライベートケース,中央DPモデル,局所DPモデルと根本的な差異が認められた。
関連論文リスト
- A statistical perspective on algorithm unrolling models for inverse
problems [2.7163621600184777]
観測値の条件分布が$bf y$で、興味のある変数が$bf x$であるような逆問題では、アルゴリズムのアンローリングを考える。
GDNsの最適統計性能に必要なアンローリング深さは、$log(n)/log(varrho_n-1)$で、$n$はサンプルサイズである。
また、潜伏変数 $bf x$ の負の対数密度が単純な近位演算子を持つとき、GDN は深さ $ でアンロールされることを示す。
論文 参考訳（メタデータ） (2023-11-10T20:52:20Z) - Scaling Up Differentially Private LASSO Regularized Logistic Regression
via Faster Frank-Wolfe Iterations [51.14495595270775]
我々は,Frank-Wolfeアルゴリズムを$L_1$のペナル化線形回帰に適応させ,スパース入力を認識し,有効利用する。
この方法では,プライバシパラメータ$epsilon$の値とデータセットの分散度に応じて,最大2,200times$の係数でランタイムを削減できることを示す。
論文 参考訳（メタデータ） (2023-10-30T19:52:43Z) - 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) - (Nearly) Optimal Private Linear Regression via Adaptive Clipping [22.639650869444395]
固定されたガウス型分布から各データ点をサンプリングする微分プライベート線形回帰問題について検討する。
本稿では,各イテレーションの点を置換せずにサンプリングする1パスのミニバッチ勾配勾配法(DP-AMBSSGD)を提案し,解析する。
論文 参考訳（メタデータ） (2022-07-11T08:04:46Z) - Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。
新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
論文 参考訳（メタデータ） (2022-04-22T07:03:13Z) - 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) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。