論文の概要: High Dimensional Differentially Private Stochastic Optimization with
Heavy-tailed Data
- arxiv url: http://arxiv.org/abs/2107.11136v1
- Date: Fri, 23 Jul 2021 11:03:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-26 18:39:10.976081
- Title: High Dimensional Differentially Private Stochastic Optimization with
Heavy-tailed Data
- Title（参考訳）: 重み付きデータを用いた高次元微分プライベート確率最適化
- Authors: Lijie Hu and Shuo Ni and Hanshen Xiao and Di Wang
- Abstract要約: 本研究では,高次元空間における重み付きデータを用いたDP-SCOの問題に関する最初の研究を行う。
損失関数が滑らかで、その勾配が第二次モーメントに有界ならば、$epsilon$-DPモデルで$tildeO(fraclog d(nepsilon)frac13)$の(高い確率)誤差境界(過剰な集団リスク)を得ることが可能である。
論文の第2部では,重み付きデータを用いたスパース学習について検討した。
- 参考スコア（独自算出の注目度）: 8.55881355051688
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: As one of the most fundamental problems in machine learning, statistics and
differential privacy, Differentially Private Stochastic Convex Optimization
(DP-SCO) has been extensively studied in recent years. However, most of the
previous work can only handle either regular data distribution or irregular
data in the low dimensional space case. To better understand the challenges
arising from irregular data distribution, in this paper we provide the first
study on the problem of DP-SCO with heavy-tailed data in the high dimensional
space. In the first part we focus on the problem over some polytope constraint
(such as the $\ell_1$-norm ball). We show that if the loss function is smooth
and its gradient has bounded second order moment, it is possible to get a (high
probability) error bound (excess population risk) of $\tilde{O}(\frac{\log
d}{(n\epsilon)^\frac{1}{3}})$ in the $\epsilon$-DP model, where $n$ is the
sample size and $d$ is the dimensionality of the underlying space. Next, for
LASSO, if the data distribution that has bounded fourth-order moments, we
improve the bound to $\tilde{O}(\frac{\log d}{(n\epsilon)^\frac{2}{5}})$ in the
$(\epsilon, \delta)$-DP model. In the second part of the paper, we study sparse
learning with heavy-tailed data. We first revisit the sparse linear model and
propose a truncated DP-IHT method whose output could achieve an error of
$\tilde{O}(\frac{s^{*2}\log d}{n\epsilon})$, where $s^*$ is the sparsity of the
underlying parameter. Then we study a more general problem over the sparsity
({\em i.e.,} $\ell_0$-norm) constraint, and show that it is possible to achieve
an error of $\tilde{O}(\frac{s^{*\frac{3}{2}}\log d}{n\epsilon})$, which is
also near optimal up to a factor of $\tilde{O}{(\sqrt{s^*})}$, if the loss
function is smooth and strongly convex.
- Abstract（参考訳）: 機械学習、統計学、微分プライバシーにおける最も基本的な問題の1つとして、ディファレンシャル・プライベート・確率凸最適化(DP-SCO)が近年広く研究されている。
しかし、以前の研究のほとんどは、低次元空間の場合の正規データ分布または不規則データのみを扱うことができる。
本稿では,不規則なデータ分布から生じる課題をよりよく理解するために,高次元空間における重み付きデータを用いたDP-SCO問題に関する最初の研究を行う。
最初の部分では、ポリトープ制約($\ell_1$-norm ボールなど)よりも問題に焦点を当てています。
損失関数が滑らかで、その勾配が2次モーメントに有界であれば、$n$がサンプルサイズであり、$d$が基礎空間の次元である$\epsilon$-dpモデルにおいて、$\tilde{o}(\frac{\log d}{(n\epsilon)^\frac{1}{3}})$の(高い確率)誤差バウンド(外人口リスク)を得ることができる。
次に、LASSO に対して、4階のモーメントが有界なデータ分布は $(\epsilon, \delta)$-DP モデルにおいて $\tilde{O}(\frac{\log d}{(n\epsilon)^\frac{2}{5}})$ となる。
論文の第2部では,重み付きデータを用いたスパース学習について検討した。
まず、スパース線形モデルを再検討し、出力が$\tilde{o}(\frac{s^{*2}\log d}{n\epsilon})$(ここで$s^*$ はパラメータのスパース性である)の誤差を達成することのできる切断dp-iht法を提案する。
次に、スパーシリティ上のより一般的な問題 ({\em i.e.,} $\ell_0$-norm) について研究し、損失関数が滑らかで強凸であれば、$\tilde{O}(\frac{s^{*\frac{3}{2}}\log d}{n\epsilon})$が$\tilde{O}{(\sqrt{s^*})}$に近く最適であることを示す。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。
我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
論文 参考訳（メタデータ） (2024-03-05T12:28:00Z) - 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) - Improved Analysis of Sparse Linear Regression in Local Differential
Privacy Model [38.66115499136791]
局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。
そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。
その結果, 疎線形回帰問題における非私的ケース, 中央DPモデル, 局所DPモデルとの基本的差異が明らかとなった。
論文 参考訳（メタデータ） (2023-10-11T10:34:52Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳（メタデータ） (2023-03-30T02:50:49Z) - 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) - Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。
新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
論文 参考訳（メタデータ） (2022-04-22T07:03:13Z) - Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed
Data [22.233705161499273]
我々は$epsilon$-DPモデルにおける$ell_1$-norm線形回帰に注目した。
我々は高い確率で$tildeO(sqrtfracdnepsilon)$の上限を達成することができることを示す。
我々のアルゴリズムは、データの各座標が有界なモーメントを持つような、よりリラックスしたケースにも拡張できる。
論文 参考訳（メタデータ） (2022-01-10T08:17:05Z) - 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) - On Differentially Private Stochastic Convex Optimization with
Heavy-tailed Data [18.351352536791453]
本稿では,重み付きデータを用いた凸最適化(SCO)のためのDPアルゴリズムの設計について考察する。
このようなデータの不規則性は、ほとんど全ての既存のDP-SCOおよびDP-ERM法で使われるいくつかの重要な仮定に反する。
我々は,データの不規則性に起因する課題に対して,アルゴリズムが効果的に対処可能であることを示す。
論文 参考訳（メタデータ） (2020-10-21T15:45:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。