Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension. (English) Zbl 0818.60005

Haussler, David

J. Comb. Theory, Ser. A 69, No. 2, 217-232 (1995).

Let \(V\) be a subset of the Boolean \(n\)-cube \(\{0,1\}^ n\) with Vapnik-Chervonenkis dimension \(d\). Let \(M(k/n, V)\) denote the cardinality of the largest subset \(W\) of \(V\) such that any two distinct vectors in \(W\) differ on at least \(k\) indices. It is shown that \[ M (k/n, V) \leq e(d + 1) \bigl( 2e (n + 1)/(k + 2d + 2) \bigr)^ d. \] This improves on the best previous result which contained an extra factor \((\log (n/d))^ d\). The new bound is best possible up to a multiplicative constant. There are applications in the theory of empirical processes.

Reviewer: R.Wegmann (Garching)

MSC:

60C05	Combinatorial probability
68U05	Computer graphics; computational geometry (digital and algorithmic aspects)
05B40	Combinatorial aspects of packing and covering

Keywords:

Vapnik-Chervonenkis dimension; empirical processes

References:

[1]	Alon, N.; Haussler, D.; Welzl, E.: Partitioning and geometric embedding of range spaces of finite vapnik-chervonenkis dimension. Proceedings 3rd symp. On computational geometry, 331-340 (June 1987)
[2]	Alon, N.: On the density of sets of vectors. Discrete math. 24, 177-184 (1983)
[3]	Assouad, Patrice: Densité et dimension. Ann. inst. Fourier (Grenoble) 33, No. No. 3, 233-282 (1983) · Zbl 0504.60006
[4]	Alon, N.; Tarsi, M.: Colorings and orientations of graphs. Combinatorica 12, 125-134 (1992) · Zbl 0756.05049
[5]	Ben-David, S.; Cesa-Bianchi, N.; Long, P. M.: Characterizations of learnability for classes of \({0,\dots , n}\)-valued functions. Proceedings of the 1992 workshop on computational learning theory (1992) · Zbl 0827.68095
[6]	Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. K.: Learnability and the vapnik-chervonenkis dimension. J. assoc. Comput. Mach 36, No. No. 4, 929-965 (1989) · Zbl 0697.68079
[7]	Bondy, J. A.: Induced subsets. J. combin. Theory ser. B 12, 201-202 (1972) · Zbl 0211.56901
[8]	Chazelle, B.; Friedman, J.: A deterministic view of random sampling and its use in geometry. Proceedings of the 29th annual symposium on foundations of computer science, 539-549 (1988)
[9]	Chazelle, B.; Welzl, E.: Quasi-optimal range searching and VC-dimensions. Discrete comput. Geom. 4, 467-490 (1989) · Zbl 0681.68081
[10]	Dudley, R. M.: Central limit theorems for empirical measures. Ann. probab. 6, No. No. 6, 899-929 (1978) · Zbl 0404.60016
[11]	Dudley, R. M.: A course on empirical processes. Lecture notes in mathematics 1097, 2-142 (1984) · Zbl 0554.60029
[12]	Dudley, R. M.: Universal donsker classes and metric entropy. Ann. probab. 15, No. No. 4, 1306-1326 (1987) · Zbl 0631.60004
[13]	Edelsbrunner, H.; Guibas, L.; Sharir, M.: The complexity of many faces in arrangements of lines and of segments. Proceedings 4th ann. ACM symp. On computational geometry, 44-55 (1988) · Zbl 0691.68035
[14]	Fulk, M.; Case, J.: Proceedings of the 1990 workshop on computational learning theory. (1990)
[15]	Frankl, P.: On the trace of finite sets. J. combin. Theory ser. A 34, 41-45 (1983) · Zbl 0505.05001
[16]	Frankl, P.: The shifting technique in extremal set theory. Surveys in combinatorics, 81-110 (1987) · Zbl 0633.05038
[17]	Graham, R.; Knuth, D. E.; Patashnik, O.: Concrete mathematics. (1989) · Zbl 0668.00003
[18]	Giné, E.; Zinn, J.: Some limit theorems for empirical processes. Ann. probab. 12, 929-989 (1984) · Zbl 0553.60037
[19]	Haussler, D.: Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inform. and comput. 100, No. No. 1, 78-150 (Sept. 1992) · Zbl 0762.68050
[20]	Haussler, D.; Kearns, M.; Schapire, R.: Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension. Machine learning 14, No. No. 1, 83-114 (1994) · Zbl 0798.68145
[21]	D. Haussler and P. Long, A generalization of Sauer’s lemma, J. Combin. Theory Ser. A, to appear. · Zbl 0831.60011
[22]	Haussler, D.; Littlestone, N.; Warmuth, M.: Predicting \({0, 1}\)-functions on randomly drawn points. Technical report UCSC-CRL-90-54 (December 1990) · Zbl 0938.68785
[23]	Inform. and Comput. to appear.
[24]	Haussler, D.; Pitt, L.: Proceedings of the 1988 workshop on computational learning theory. (1988)
[25]	Haussler, D.; Welzl, E.: Epsilon nets and simplex range queries. Discrete compute geom. 2, 127-151 (1987) · Zbl 0619.68056
[26]	Matousek, J.: Tight upper bounds for the discrepancy of halfspaces. Manuscript (1994)
[27]	Matousek, J.; Seidel, R.; Welzl, E.: How to net a lot with a little: small epsilon-nets for disks and halfspaces. Proceedings 6th ann. ACM symp. On computational geometry (1990)
[28]	Pollard, D.: Convergence of stochastic processes. (1984) · Zbl 0544.60045
[29]	Pollard, D.: Empirical processes: theory and applications. NSF-CBMS regional conference series in probability and statistics 2 (1990) · Zbl 0741.60001
[30]	Rivest, R.; Haussler, D.; Warmuth, M.: Proceedings of the 1989 workshop on computational learning theory. (1989) · Zbl 0741.00077
[31]	Sauer, N.: On the density of families of sets. J. combin. Theory ser. A 13, 145-147 (1972) · Zbl 0248.05005
[32]	Steele, J. M.: Existence of submatrices with all possible columns. J. comb. Theory ser. A 24, 84-88 (1978) · Zbl 0373.05004
[33]	Talagrand, M.: Donsker classes and random geometry. Ann. probab. 15, 1327-1338 (1987) · Zbl 0637.60040
[34]	Talagrand, M.: The glivenko-cantelli problem. Ann. probab. 15, 837-870 (1987) · Zbl 0632.60024
[35]	Talagrand, M.: Donsker classes of sets. Probab. theory related fields 78, 169-191 (1988) · Zbl 0628.60027
[36]	Talagrand, M.: Sharper bounds for Gaussian and empirical processes. Ann. probab. 22, No. No. 1, 28-76 (1994) · Zbl 0798.60051
[37]	Vapnik, V. N.: Estimation of dependences based on empirical data. (1982) · Zbl 0499.62005
[38]	Vapnik, V. N.; Chervonenkis, A. Ya: On the uniform convergence of relative frequencies of events to their probabilities. Theory probab. Appl. 16, No. No. 2, 264-280 (1971) · Zbl 0247.60005
[39]	Valiant, L. G.; Warmuth, M.: Proceedings of the 1991 workshop on computational learning theory. (1991)
[40]	Wernisch, L.: Note on stabbing numbers and sphere packing numbers. Manuscript (1992)
[41]	Welzl, E.: Partition trees for triangle counting and other range search problems. Proceedings 4th ann. ACM symp. On computational geometry, 23-33 (1988)