×

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

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.

MSC:

60C05 Combinatorial probability
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05B40 Combinatorial aspects of packing and covering
PDF BibTeX XML Cite
Full Text: DOI

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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.