論文の概要: Private Truly-Everlasting Robust-Prediction
- arxiv url: http://arxiv.org/abs/2401.04311v1
- Date: Tue, 9 Jan 2024 02:00:55 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-10 17:15:53.353646
- Title: Private Truly-Everlasting Robust-Prediction
- Title（参考訳）: 自己エバースト型ロバスト予測
- Authors: Uri Stemmer
- Abstract要約: プライベート・エバースト・予測(Private Everlasting Prediction, PEP)は、学習者が仮説を公開しない、微分プライベート学習のモデルである。
PEPは、初期トレーニングセットと、エンドツーエンドの分類クエリストリームの両方に対して、プライバシを提供する。
我々は, PEPの定義に対する2つの概念的修正と, 従来の作業よりも大幅に改善された新しい構成を提案する。
- 参考スコア（独自算出の注目度）: 22.662255469977598
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Private Everlasting Prediction (PEP), recently introduced by Naor et al.
[2023], is a model for differentially private learning in which the learner
never publicly releases a hypothesis. Instead, it provides black-box access to
a "prediction oracle" that can predict the labels of an endless stream of
unlabeled examples drawn from the underlying distribution. Importantly, PEP
provides privacy both for the initial training set and for the endless stream
of classification queries. We present two conceptual modifications to the
definition of PEP, as well as new constructions exhibiting significant
improvements over prior work. Specifically,
(1) Robustness: PEP only guarantees accuracy provided that all the
classification queries are drawn from the correct underlying distribution. A
few out-of-distribution queries might break the validity of the prediction
oracle for future queries, even for future queries which are sampled from the
correct distribution. We incorporate robustness against such poisoning attacks
into the definition of PEP, and show how to obtain it.
(2) Dependence of the privacy parameter $\delta$ in the time horizon: We
present a relaxed privacy definition, suitable for PEP, that allows us to
disconnect the privacy parameter $\delta$ from the number of total time steps
$T$. This allows us to obtain algorithms for PEP whose sample complexity is
independent from $T$, thereby making them "truly everlasting". This is in
contrast to prior work where the sample complexity grows with $polylog(T)$.
(3) New constructions: Prior constructions for PEP exhibit sample complexity
that is quadratic in the VC dimension of the target class. We present new
constructions of PEP for axis-aligned rectangles and for decision-stumps that
exhibit sample complexity linear in the dimension (instead of quadratic). We
show that our constructions satisfy very strong robustness properties.
- Abstract（参考訳）: Private Everlasting Prediction (PEP) - Naorらによって最近導入された。
2023]は,学習者が公に仮説を公表しない,微分的プライベート学習のモデルである。
その代わりに、"prediction oracle"へのブラックボックスアクセスを提供し、基盤となるディストリビューションから引き出されたラベルなし例の終りのないストリームのラベルを予測できる。
重要な点として、PEPは初期トレーニングセットとエンドツーエンドの分類クエリストリームの両方に対してプライバシを提供する。
我々は, PEPの定義に対する2つの概念的修正と, 従来の作業よりも大幅に改善された新しい構成を提案する。
具体的には、(1)ロバスト性: PEPは、すべての分類クエリが正しい基底分布から引き出されることを前提として、精度のみを保証する。
いくつかのアウトオブディストリビューションクエリは、正しい分布からサンプリングされた将来のクエリであっても、将来のクエリに対するoracleの予測の有効性を損なう可能性がある。
我々は、このような毒殺に対する堅牢性をPEPの定義に組み込み、その入手方法を示す。
2) プライバシーパラメータの依存性 $\delta$ in the time horizon: 私たちは、PEPに適した緩和されたプライバシー定義を提示します。
これにより、サンプルの複雑さが$t$から独立しているpepのアルゴリズムを得ることができます。
これは、サンプルの複雑さが$polylog(T)$で増加する以前の作業とは対照的である。
(3)新しい構成: PEPの以前の構成は、ターゲットクラスのVC次元において二次的なサンプル複雑性を示す。
軸整列矩形に対する PEP の新たな構成と、(二次的ではなく)次元において線形なサンプル複雑性を示す決定文について述べる。
我々の構成は強固な堅牢性特性を満たしている。
関連論文リスト
- Private Everlasting Prediction [25.11710918054182]
個人学習者は、ラベル付きポイントのサンプルに基づいて訓練され、新しくサンプリングされたポイントのラベルを予測するのに使用できる仮説を生成する。
民間の学習者は、非民間の学習者よりもはるかに高いサンプルの複雑さを示す必要があるかもしれない。
本稿では,PACモデルにおけるプライベート永遠予測器の汎用的な構成について述べる。
論文 参考訳（メタデータ） (2023-05-16T16:26:49Z) - Differentially-Private Bayes Consistency [70.92545332158217]
差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。
ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
論文 参考訳（メタデータ） (2022-12-08T11:57:30Z) - PAC Verification of Statistical Algorithms [0.10878040851637999]
本研究では,PAC学習目標を満たす仮説(機械学習モデル)を対話的証明を用いて検証する,PAC検証の設定を開発する。
我々は、$mathbbR$を超える間隔の和のPAC検証のためのプロトコルを提案し、そのタスクの提案したプロトコルを改善し、より低い境界の$d$への依存と一致させる。
最終結果は,クエリの制約を満たす統計的アルゴリズムの検証のためのプロトコルである。
論文 参考訳（メタデータ） (2022-11-28T23:57:27Z) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - Probabilistic Conformal Prediction Using Conditional Random Samples [73.26753677005331]
PCPは、不連続な予測セットによって対象変数を推定する予測推論アルゴリズムである。
効率的で、明示的または暗黙的な条件生成モデルと互換性がある。
論文 参考訳（メタデータ） (2022-06-14T03:58:03Z) - Metric Entropy Duality and the Sample Complexity of Outcome
Indistinguishability [7.727052811126007]
結果の不一致性において、目標は、ターゲット予測子と区別できない予測子を出力することである。
結果の不一致性のサンプル複雑性は、$P$ w.r.tの計量エントロピーによって特徴づけられる。
この同値性は凸幾何学における長年の計量エントロピー双対性予想と興味深い関係を持つ。
論文 参考訳（メタデータ） (2022-03-09T06:02:31Z) - Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
本研究は,局所的差分プライバシー(LDP)の制約の下で,集団平均の非パラメトリック,非漸近的統計的推測を行う手法を導出する。
民営化データへのアクセスのみを与えられた場合、$mustar$に対して信頼区間(CI)と時間一様信頼シーケンス(CS)を提示する。
論文 参考訳（メタデータ） (2022-02-17T16:04:49Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。
この結果は Bun et al の質問に答えます。
(FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文 参考訳（メタデータ） (2020-12-07T18:17:46Z) - Testing Determinantal Point Processes [0.0]
配電体の特性試験という新たな視点からDPPについて検討する。
DPPをテストするための最初のアルゴリズムを提案する。
より一般的な対数-部分モジュラ分布のクラスをテストする問題に対して、新しい硬度結果を示す。
論文 参考訳（メタデータ） (2020-08-09T04:45:16Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z) - De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and
Non-smooth Predictors [21.59277717031637]
決定論的非平滑予測(ReLU-nets)のための非ランダム化PACの族を示す。
また、セットサイズやラベルの変更に対する境界の実証的な結果も提示する。
論文 参考訳（メタデータ） (2020-02-23T17:54:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。