Fugu-MT 論文翻訳(概要): Adversarial Laws of Large Numbers and Optimal Regret in Online Classification

論文の概要: Adversarial Laws of Large Numbers and Optimal Regret in Online Classification

arxiv url: http://arxiv.org/abs/2101.09054v1
Date: Fri, 22 Jan 2021 11:15:19 GMT
ステータス: 処理完了
システム内更新日: 2021-03-20 17:26:38.128793
Title: Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
Title（参考訳）: オンライン分類における大数の逆法則と最適後悔
Authors: Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, Eylon Yogev
Abstract要約: サンプリングプロセスにおける多数の法則について検討し,それらが作用し,相互作用する環境に影響を及ぼす可能性について検討した。我々の特徴は,統計的学習における学習可能性と一様収束の等価性のオンラインアナログとして解釈できる。
参考スコア（独自算出の注目度）: 32.16217148059578
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We study laws of large numbers in sampling processes that can affect the environment they are acting upon and interact with it. Specifically, we consider the sequential sampling model proposed by Ben-Eliezer and Yogev (2020), and characterize the classes which admit a uniform law of large numbers in this model: these are exactly the classes that are \emph{online learnable}. Our characterization may be interpreted as an online analogue to the equivalence between learnability and uniform convergence in statistical (PAC) learning. The sample-complexity bounds we obtain are tight for many parameter regimes, and as an application, we determine the optimal regret bounds in online learning, stated in terms of \emph{Littlestone's dimension}, thus resolving the main open question from Ben-David, P\'al, and Shalev-Shwartz (2009), which was also posed by Rakhlin, Sridharan, and Tewari (2015).
Abstract（参考訳）: 大きな数の法則により、ある集団から十分な量のサンプルが与えられた場合、固定されたサブ集団の測度は標本の頻度によってよく推定される。サンプリングプロセスにおける多数の法則について検討し,それらが作用し,相互作用する環境に影響を及ぼす可能性について検討した。具体的には、ben-eliezer と yogev (2020) によって提案された逐次サンプリングモデルを検討し、このモデルで大数の一様法則を許すクラスを特徴づける: これらはちょうど \emph{online learnable} である。我々の特徴は,統計的学習における学習可能性と一様収束の等価性のオンラインアナログとして解釈できる。サンプル-複素性境界は、多くのパラメーターレジームに対して厳密であり、応用として、オンライン学習において最適の後悔境界を決定する。これは、'emph{Littlestone's dimension} の項で述べられており、Ben-David, P\'al, and Shalev-Shwartz (2009) から主要な開質問を解き、Rahlin, Sridharan, Tewari (2015) によっても提起された。