Universal Online Learning with Bounded Loss: Reduction to Binary Classification
2. července 2022
Řečníci
Moise Blanchard
Řečník · 0 sledujících
Romain Cosson
Řečník · 0 sledujících
O prezentaci
We study universal consistency of non-i.i.d. processes in the context of online learning. A stochastic process is said to admit universal consistency if there exists a learner that achieves vanishing average loss for any measurable response function on this process. When the loss function is unbounded, [1] showed that the only processes admitting strong universal consistency are those taking a finite number of values almost surely. However, when the loss function is bounded, the class of processes admitting strong universal consistency is much richer and its characterization could be dependent on the response setting [2]. In this paper, we show that this class of processes is independent from the response setting thereby closing an open question of [3] (Open Problem 3). Specifically, we show that the class of processes that admit universal online learning is the same for binary classification as for multiclass classification with countable number of classes. Consequently, any output setting with bounded loss can be reduced to binary classification. Our reduction is constructive and practical. Indeed, we show that the nearest neighbor algorithm is transported by our construction. For binary classification on a process admitting strong universal learning, we prove that nearest neighbor successfully learns at least all finite unions of intervals.We study universal consistency of non-i.i.d. processes in the context of online learning. A stochastic process is said to admit universal consistency if there exists a learner that achieves vanishing average loss for any measurable response function on this process. When the loss function is unbounded, [1] showed that the only processes admitting strong universal consistency are those taking a finite number of values almost surely. However, when the loss function is bounded, the class of process…
O organizátorovi (COLT)
The conference is held annually since 1988 and has become the leading conference on Learning theory by maintaining a highly selective process for submissions. It is committed in high-quality articles in all theoretical aspects of machine learning and related topics.
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Optimality and Approximation with Policy Gradient Methods
Zhlédnout později
Improved analysis for the proximal sampler
Zhlédnout později
Sinho Chewi, …
From tree matching to sparse graph alignment
Zhlédnout později
Provably Efficient Reinforcement Learning with Linear Function Approximation
Zhlédnout později
Chi Jin, …
The EM Algorithm is Sample-Optimal for Learning Mixtures of Well-Separated Gaussians
Zhlédnout později
