論文の概要: Closure Properties for Private Classification and Online Prediction
- arxiv url: http://arxiv.org/abs/2003.04509v3
- Date: Wed, 13 May 2020 03:50:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-24 20:36:03.207073
- Title: Closure Properties for Private Classification and Online Prediction
- Title（参考訳）: プライベート分類とオンライン予測のためのクロージャ特性
- Authors: Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer
- Abstract要約: オンライン学習とプライベートPAC学習のための閉鎖特性を導出する。
実現可能な場合において、関数のクラスを学習する任意のプライベートアルゴリズムは、その場合のクラスを学習するプライベートアルゴリズムに変換可能であることを示す。
- 参考スコア（独自算出の注目度）: 31.115241685486392
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Let~$\cH$ be a class of boolean functions and consider a {\it composed class}
$\cH'$ that is derived from~$\cH$ using some arbitrary aggregation rule (for
example, $\cH'$ may be the class of all 3-wise majority-votes of functions in
$\cH$). We upper bound the Littlestone dimension of~$\cH'$ in terms of that
of~$\cH$. As a corollary, we derive closure properties for online learning and
private PAC learning.
The derived bounds on the Littlestone dimension exhibit an undesirable
exponential dependence. For private learning, we prove close to optimal bounds
that circumvents this suboptimal dependency. The improved bounds on the sample
complexity of private learning are derived algorithmically via transforming a
private learner for the original class $\cH$ to a private learner for the
composed class~$\cH'$. Using the same ideas we show that any ({\em proper or
improper}) private algorithm that learns a class of functions $\cH$ in the
realizable case (i.e., when the examples are labeled by some function in the
class) can be transformed to a private algorithm that learns the class $\cH$ in
the agnostic case.
- Abstract（参考訳）: $\cH'$ をブール関数の類とし、任意のアグリゲーション規則を用いて~$\cH'$ から派生した {$\cH'$ を考える(例えば、$\cH'$ は $\cH$ の3つの多元関数全体のクラスであるかもしれない)。
我々はリトルストーン次元の~$\cH'$を~$\cH$の項で上界する。
本稿では,オンライン学習とプライベートPAC学習のクロージャ特性について考察する。
リトルストーン次元の導出境界は、望ましくない指数依存性を示す。
プライベート学習では、この準最適依存性を回避する最適境界に近いことが証明される。
プライベート学習のサンプル複雑性に関する改善された境界は、オリジナルのクラス$\cH$のプライベート学習者を、合成クラス~$\cH'$のプライベート学習者に変換することでアルゴリズム的に導出される。
同じ考えを用いることで、実現可能な場合(例がクラス内のある関数によってラベル付けされた場合)で$\ch$の関数のクラスを学習する({\em properまたは不適切な)プライベートアルゴリズムは、非依存の場合で$\ch$のクラスを学習するプライベートアルゴリズムに変換できることを示した。
関連論文リスト
- Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。
DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。
本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
論文 参考訳（メタデータ） (2024-11-27T00:48:48Z) - Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文 参考訳（メタデータ） (2023-08-15T21:50:40Z) - Differentially Private Nonparametric Regression Under a Growth Condition [9.416757363901295]
実数値仮説クラス $mathcalH$ が与えられた場合、最適な仮説を学習する微分プライベートアルゴリズムが存在する場合の条件について検討する。
緩和条件である$lim inf_eta downarrow 0 eta cdot rm sfat_eta(mathcalH)$ = 0$, $mathcalH$はプライベートに学習可能であることを示す。
論文 参考訳（メタデータ） (2021-11-24T20:36:01Z) - FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。
$cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。
$mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
論文 参考訳（メタデータ） (2021-10-19T17:43:50Z) - 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) - 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) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-16T16:12:10Z) - Differentially Private Release and Learning of Threshold Functions [27.612916837481485]
我々は、$(epsilon, delta)$微分プライベートアルゴリズムのサンプル複雑性に対して、新しい上界と下界を証明した。
完全に順序付けられたドメイン上のしきい値関数$c_x$は$c_x(y) = 1$ if $y le x$と評価され、$0$と評価される。
論文 参考訳（メタデータ） (2015-04-28T16:15:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。