Fetching the paper…

Reading the bibliography…

2021

Primal and Dual Combinatorial Dimensions

Kleer, Pieter, Simon, Hans

Original
PDF
Post on X

Understand

We give tight bounds on the relation between the primal and dual of various combinatorial dimensions, such as the pseudo-dimension and fat-shattering dimension, for multi-valued function classes.

These dimensional notions play an important role in the area of learning theory.
We first review some (folklore) results that bound the dual dimension of a function class in terms of its primal, and after that give (almost) matching lower bounds.
In particular, we give an appropriate generalization to multi-valued function classes of a well-known bound due to Assouad (1983), that relates the primal and dual VC-dimension of a binary function class.

Primal and Dual Combinatorial Dimensions · Around

Built on

On uniform convergence of the frequencies of events to their probabilities
Vladimir Naumovich Vapnik and Aleksei Yakovlevich Chervonenkis · 1971
Earlier work this paper cites.
Densité et dimension
Patrick Assouad · 1983
Earlier work this paper cites.
Inductive principles of the search for empirical dependences (methods based on weak convergence of probability measures)
Vladimir Naumovich Vapnik · 1989
Earlier work this paper cites.
Empirical processes: theory and applications
David Pollard · 1990
Earlier work this paper cites.

Similar

Decision theoretic generalizations of the pac model for neural net and other learning applications
David Haussler · 1992
Cited alongside, same era.
Efficient distribution-free learning of probabilistic concepts
Michael J Kearns and Robert E Schapire · 1994
Cited alongside, same era.
Characterizations of learnability for classes of [n]-valued functions
Shai Ben-David, Nicolo Cesabianchi, David Haussler, and Philip M Long · 1995
Cited alongside, same era.
Scale-sensitive dimensions, uniform convergence, and learnability
Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler · 1997
Cited alongside, same era.

Then

Lectures on discrete geometry
Jiří Matoušek · 2002
Later among the works it cites.
Sample compression schemes for VC
Shay Moran and Amir Yehudayoff · 2016
Later among the works it cites.
Sample compression for real-valued learners
Steve Hanneke, Aryeh Kontorovich, and Menachem Sadigurschi · 2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…