論文の概要: Littlestone Classes are Privately Online Learnable
- arxiv url: http://arxiv.org/abs/2106.13513v1
- Date: Fri, 25 Jun 2021 09:08:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-28 12:53:43.763207
- Title: Littlestone Classes are Privately Online Learnable
- Title（参考訳）: Littlestoneクラスはプライベートにオンライン学習可能
- Authors: Noah Golowich and Roi Livni
- Abstract要約: プライバシー制約下でのオンライン分類の問題点を考察する。
この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。
学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
- 参考スコア（独自算出の注目度）: 28.04975353867202
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of online classification under a privacy constraint.
In this setting a learner observes sequentially a stream of labelled examples
$(x_t, y_t)$, for $1 \leq t \leq T$, and returns at each iteration $t$ a
hypothesis $h_t$ which is used to predict the label of each new example $x_t$.
The learner's performance is measured by her regret against a known hypothesis
class $\mathcal{H}$. We require that the algorithm satisfies the following
privacy constraint: the sequence $h_1, \ldots, h_T$ of hypotheses output by the
algorithm needs to be an $(\epsilon, \delta)$-differentially private function
of the whole input sequence $(x_1, y_1), \ldots, (x_T, y_T)$. We provide the
first non-trivial regret bound for the realizable setting. Specifically, we
show that if the class $\mathcal{H}$ has constant Littlestone dimension then,
given an oblivious sequence of labelled examples, there is a private learner
that makes in expectation at most $O(\log T)$ mistakes -- comparable to the
optimal mistake bound in the non-private case, up to a logarithmic factor.
Moreover, for general values of the Littlestone dimension $d$, the same mistake
bound holds but with a doubly-exponential in $d$ factor. A recent line of work
has demonstrated a strong connection between classes that are online learnable
and those that are differentially-private learnable. Our results strengthen
this connection and show that an online learning algorithm can in fact be
directly privatized (in the realizable setting). We also discuss an adaptive
setting and provide a sublinear regret bound of $O(\sqrt{T})$.
- Abstract（参考訳）: プライバシー制約下でのオンライン分類の問題点を考察する。
この設定では、学習者はラベル付きサンプルのストリームを逐次観察し、各イテレーションで$(x_t, y_t)$, for $1 \leq t \leq t$, and return at each iteration $t$ a hypothesis $h_t$ を返します。
学習者のパフォーマンスは、既知の仮説クラス$\mathcal{H}$に対する後悔によって測定される。
アルゴリズムが出力する仮説のシーケンス$h_1, \ldots, h_T$は$(\epsilon, \delta)$-differentially private function of the whole input sequence $(x_1, y_1), \ldots, (x_T, y_T)$である必要がある。
実現可能な設定のために、最初の非自明な後悔を与える。
具体的には、クラス $\mathcal{H}$ が定数のリトルストーン次元を持つなら、ラベル付き例の曖昧な列が与えられた場合、最大$O(\log T)$ミスを期待するプライベートラーナーが存在する。
さらに、リトルストーン次元の一般値 $d$ に対して、同じ誤り境界は成り立つが、$d$因子の二重指数を持つ。
最近の研究は、オンライン学習可能なクラスと、微分プライベート学習可能なクラスの間に強いつながりを示している。
この関係を強化し、オンライン学習アルゴリズムが(実現可能な設定で)直接民営化可能であることを示す。
また,適応的な設定を議論し,o(\sqrt{t})$ の劣線形後悔値を与える。
関連論文リスト
- Agnostic Smoothed Online Learning [5.167069404528051]
本稿では,$mu$の事前知識を必要とせずに,オンライン学習を円滑に行うためのサブ線形後悔を保証するアルゴリズムを提案する。
R-Coverは、次元$d$を持つ関数クラスに対して、適応的後悔$tilde O(sqrtdT/sigma)$を持つ。
論文 参考訳（メタデータ） (2024-10-07T15:25:21Z) - 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) - A Trichotomy for Transductive Online Learning [32.03948071550447]
我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。
この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
論文 参考訳（メタデータ） (2023-11-10T23:27:23Z) - Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文 参考訳（メタデータ） (2023-08-15T21:50:40Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
論文 参考訳（メタデータ） (2022-10-06T06:49:48Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳（メタデータ） (2021-09-29T14:07:21Z) - 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) - Closure Properties for Private Classification and Online Prediction [31.115241685486392]
オンライン学習とプライベートPAC学習のための閉鎖特性を導出する。
実現可能な場合において、関数のクラスを学習する任意のプライベートアルゴリズムは、その場合のクラスを学習するプライベートアルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2020-03-10T02:34:16Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。