A Combinatorial Characterization of Supervised Online Learnability

Vinod Raman, Unique Subedi, Ambuj Tewari
7/7/2023
cs.LG

No confident code implementation found for this paper.

Abstract

We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. No characterization of online learnability is known at this level of generality. We give a new scale-sensitive combinatorial dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability. In addition, we show that the sequential minimax dimension subsumes most existing combinatorial dimensions in online learning theory.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Online Learning with Set-Valued Feedback

87% match2023

Multiclass Transductive Online Learning

85% match2024

Optimal Learners for Realizable Regression: PAC Learning and Online Learning

85% match2023

List Online Classification

84% match2023

On Computable Online Learning

84% match2023

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem

84% match2024

Cite this paper

@article{raman2023combinatorial,
  title  = {A Combinatorial Characterization of Supervised Online Learnability},
  author = {Vinod Raman and Unique Subedi and Ambuj Tewari},
  year   = {2023},
  eprint = {2307.03816},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2307.03816v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2307.03816.svg)](https://codeofpaper.com/paper/2307.03816)

Discussion