A Theory of Optimistically Universal Online Learnability for General Concept Classes
원문 초록
We provide a full characterization of the concept classes that are optimistically universally online learnable with $\{0, 1\}$ labels. The notion of optimistically universal online learning was defined in [Hanneke, 2021] in order to understand learnability under minimal assumptions. In this paper, following the philosophy behind that work, we investigate two questions, namely, for every concept class: (1) What are the minimal assumptions on the data process admitting online learnability? (2) Is there a learning algorithm which succeeds under every data process satisfying the minimal assumptions? Such an algorithm is said to be optimistically universal for the given concept class. We resolve both of these questions for all concept classes, and moreover, as part of our solution, we design general learning algorithms for each case. Finally, we extend these algorithms and results to the agnostic case, showing an equivalence between the minimal assumptions on the data process for learnability in the agnostic and realizable cases, for every concept class, as well as the equivalence of optimistically universal learnability.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Mapping Seven Decades of Philosophy in Colombia: Dynamic Topic Modelling of Ideas y Valores
LLINBO: Trustworthy LLM-in-the-Loop Bayesian Optimization
Streaming 4D Visual Geometry Transformer
Simple is what you need for efficient and accurate medical image segmentation
Time Series Forecasting as Reasoning: A Slow-Thinking Approach with Reinforced LLMs
Sorrel: A simple and flexible framework for multi-agent reinforcement learning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.