論文の概要: Differentially Private Nonparametric Regression Under a Growth Condition
- arxiv url: http://arxiv.org/abs/2111.12786v1
- Date: Wed, 24 Nov 2021 20:36:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-29 16:13:57.652066
- Title: Differentially Private Nonparametric Regression Under a Growth Condition
- Title（参考訳）: 成長条件下における個人別非パラメトリック回帰
- Authors: Noah Golowich
- Abstract要約: 実数値仮説クラス $mathcalH$ が与えられた場合、最適な仮説を学習する微分プライベートアルゴリズムが存在する場合の条件について検討する。
緩和条件である$lim inf_eta downarrow 0 eta cdot rm sfat_eta(mathcalH)$ = 0$, $mathcalH$はプライベートに学習可能であることを示す。
- 参考スコア（独自算出の注目度）: 9.416757363901295
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a real-valued hypothesis class $\mathcal{H}$, we investigate under what
conditions there is a differentially private algorithm which learns an optimal
hypothesis from $\mathcal{H}$ given i.i.d. data. Inspired by recent results for
the related setting of binary classification (Alon et al., 2019; Bun et al.,
2020), where it was shown that online learnability of a binary class is
necessary and sufficient for its private learnability, Jung et al. (2020)
showed that in the setting of regression, online learnability of $\mathcal{H}$
is necessary for private learnability. Here online learnability of
$\mathcal{H}$ is characterized by the finiteness of its $\eta$-sequential fat
shattering dimension, ${\rm sfat}_\eta(\mathcal{H})$, for all $\eta > 0$. In
terms of sufficient conditions for private learnability, Jung et al. (2020)
showed that $\mathcal{H}$ is privately learnable if $\lim_{\eta \downarrow 0}
{\rm sfat}_\eta(\mathcal{H})$ is finite, which is a fairly restrictive
condition. We show that under the relaxed condition $\lim \inf_{\eta \downarrow
0} \eta \cdot {\rm sfat}_\eta(\mathcal{H}) = 0$, $\mathcal{H}$ is privately
learnable, establishing the first nonparametric private learnability guarantee
for classes $\mathcal{H}$ with ${\rm sfat}_\eta(\mathcal{H})$ diverging as
$\eta \downarrow 0$. Our techniques involve a novel filtering procedure to
output stable hypotheses for nonparametric function classes.
- Abstract（参考訳）: 実数値付き仮説クラス $\mathcal{h}$ が与えられると、与えられた i.i.d.データから$\mathcal{h}$ から最適な仮説を学ぶ微分プライベートアルゴリズムが存在するかを調べる。
関連するバイナリ分類の設定に関する最近の結果(alon et al., 2019; bun et al., 2020)に触発されて、バイナリクラスのオンライン学習能力はプライベート学習能力に必要で十分であることを示したjung et al. (2020)は、回帰設定においてプライベート学習能力には$\mathcal{h}$のオンライン学習能力が必要であることを示した。
ここで、$\mathcal{H}$のオンライン学習性は、すべての$\eta > 0$に対して$\eta$-sequential fat shattering dimension, ${\rm sfat}_\eta(\mathcal{H})$の有限性によって特徴づけられる。
Jung et al. (2020) は、プライベート可学習性に関する十分な条件について、$\lim_{\eta \downarrow 0} {\rm sfat}_\eta(\mathcal{H})$ が有限であれば、$\mathcal{H}$ がプライベート可学習可能であることを示した。
緩和された条件下では、$\lim \inf_{\eta \downarrow 0} \eta \cdot {\rm sfat}_\eta(\mathcal{H}) = 0$, $\mathcal{H}$はプライベートに学習可能であり、${\rm sfat}_\eta(\mathcal{H})$を$\eta \downarrow 0$として発散させることで、クラスに対する最初の非パラメトリックプライベートな学習性を保証する。
非パラメトリック関数クラスに対して安定な仮説を出力するための新しいフィルタリング手法を含む。
関連論文リスト
- Revisiting Agnostic PAC Learning [30.67561230812141]
PAC学習は、Valiant'84とVapnik and Chervonenkis'64,'74にさかのぼる、教師あり学習を研究するための古典的なモデルである。
経験的リスク最小化(英: Empirical Risk Minimization、ERM)は、訓練データに最も少ない誤りを犯すために$mathcalH$から仮説を出力する自然学習アルゴリズムである。
私たちはPAC学習を再考し、最良仮説の性能を$tau:=Pr_mathcalD[hstar_mathと表すと、ERMが実際は準最適であることを示す。
論文 参考訳（メタデータ） (2024-07-29T08:20:49Z) - 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) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳（メタデータ） (2023-09-29T14:14:53Z) - On the Optimality of Misspecified Kernel Ridge Regression [13.995944403996566]
我々は、$mathcalH$がソボレフ RKHS であるとき、KRR が任意の$sin (0,1)$に対して最小値であることを示す。
論文 参考訳（メタデータ） (2023-05-12T04:12:12Z) - On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
論文 参考訳（メタデータ） (2022-10-06T06:49:48Z) - Littlestone Classes are Privately Online Learnable [28.04975353867202]
プライバシー制約下でのオンライン分類の問題点を考察する。
この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。
学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
論文 参考訳（メタデータ） (2021-06-25T09:08:33Z) - 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) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。