VC bounds on the cardinality of nearly orthogonal function classes
By Lee-Ad Gottlieb, Aryeh Kontorovich, Elchanan Mossel. 2010
12 citations recorded by the source corpus.
We bound the number of nearly orthogonal vectors with fixed VC-dimension over {-1,1}^n. Our bounds are of interest in machine learning and empirical process theory and improve previous bounds by Haussler. The bounds are based on a simple projection argument and they generalize to other product spaces. Along the way we derive tight bounds on the sum of binomial coefficients in terms of the entropy function.
Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Battista Biggio
- Fabio Roli
- Blaine Nelson
- Giorgio Fumera
- Benjamin I. P. Rubinstein
- Anthony D. Joseph
- J. Doug Tygar
- Ling Huang
In Computational Mechanics
In Computer Networks and Communications
- Blaine Nelson
- Battista Biggio
- Fabio Roli
- Benjamin I. P. Rubinstein
- Anthony D. Joseph
- Ling Huang
- J. Doug Tygar
- Satish Rao
Citations in the corpus
- Query Strategies for Evading Convex-Inducing Classifiers (2010, background): “Gottlieb et al. (2011) present a better entropy bound on this sum of binomial coefficients, but it is unnecessary for our result.”