Optimal approximations made easy. (English) Zbl 1483.68509
Summary: The fundamental result of
Y. Li et al. [J. Comput. Syst. Sci. 62, No. 3, 516–527 (2001; Zbl 0990.68081)]
on approximations of set systems has become a key tool across several communities such as learning theory, algorithms, computational geometry, combinatorics, and data analysis.
The goal of this paper is to give a modular, self-contained, intuitive proof of this result for finite set systems. The only ingredient we assume is the standard Chernoff’s concentration bound. This makes the proof accessible to a wider audience, readers not familiar with techniques from statistical learning theory, and makes it possible to be covered in a single self-contained lecture in a geometry, algorithms or combinatorics course.
The goal of this paper is to give a modular, self-contained, intuitive proof of this result for finite set systems. The only ingredient we assume is the standard Chernoff’s concentration bound. This makes the proof accessible to a wider audience, readers not familiar with techniques from statistical learning theory, and makes it possible to be covered in a single self-contained lecture in a geometry, algorithms or combinatorics course.
MSC:
| 68W40 | Analysis of algorithms |
| 60C05 | Combinatorial probability |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Citations:
Zbl 0990.68081References:
| [1] | Anthony, M.; Bartlett, P. L., Neural Network Learning: Theoretical Foundations (2009), Cambridge University Press |
| [2] | Alon, N.; Spencer, J., The Probabilistic Method (2012), John Wiley |
| [3] | Brönnimann, H.; Chazelle, B.; Matoušek, J., Product range spaces, sensitive sampling, and derandomization, (Proc. Symposium on Foundations of Computer Science (1993)), 400-409 |
| [4] | Chazelle, B., The Discrepancy Method: Randomness and Complexity (2000), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 0960.65149 |
| [5] | Devroye, L.; Györfi, L.; Lugosi, G., A Probabilistic Theory of Pattern Recognition (1996), Springer: Springer Berlin · Zbl 0853.68150 |
| [6] | Frieze, A.; Karoński, M., Introduction to Random Graphs (2016), Cambridge University Press · Zbl 1328.05002 |
| [7] | Haussler, D., Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension, J. Comb. Theory, Ser. A, 69, 2, 217-232 (1995) · Zbl 0818.60005 |
| [8] | Har-Peled, S., Geometric Approximation Algorithms (2011), American Mathematical Society: American Mathematical Society Boston, MA, USA · Zbl 1230.68215 |
| [9] | Har-Peled, S.; Sharir, M., Relative \((p, \epsilon)\)-approximations in geometry, Discrete Comput. Geom., 45, 3, 462-496 (2011) · Zbl 1220.68106 |
| [10] | Haussler, D.; Welzl, E., ε-nets and simplex range queries, Discrete Comput. Geom., 2, 127-151 (1987) · Zbl 0619.68056 |
| [11] | Komlós, J.; Pach, J.; Woeginger, G., Almost tight bounds for ε-nets, Discrete Comput. Geom., 7, 163-173 (1992) · Zbl 0765.68209 |
| [12] | Kolmogorov, A. N.; Tikhomirov, V. M., ϵ-entropy and ϵ-capacity, Usp. Mat. Nauk, 14, 3-86 (1959) · Zbl 0090.33503 |
| [13] | Kearns, M. J.; Vazirani, U. V., An Introduction to Computational Learning Theory (1994), MIT Press |
| [14] | Li, Y.; Long, P. M.; Srinivasan, A., Improved bounds on the sample complexity of learning, J. Comput. Syst. Sci., 62, 3, 516-527 (2001) · Zbl 0990.68081 |
| [15] | Matoušek, J., Geometric Discrepancy: An Illustrated Guide (1999), Springer · Zbl 0930.11060 |
| [16] | Matoušek, J., Lectures in Discrete Geometry (2002), Springer-Verlag: Springer-Verlag New York, NY · Zbl 0999.52006 |
| [17] | Matoušek, J.; Welzl, E.; Wernisch, L., Discrepancy and approximations for bounded VC-dimension, Combinatorica, 13, 4, 455-466 (1993) · Zbl 0795.05105 |
| [18] | Mustafa, N. H., A Simple Proof of the Shallow Packing Lemma, Discrete Comput. Geom., 55, 3, 739-743 (2016) · Zbl 1385.60018 |
| [19] | Mustafa, N. H., Sampling in Combinatorial and Geometric Set Systems (2022), AMS Press · Zbl 1489.68003 |
| [20] | Talagrand, M., Sharper bounds for Gaussian and empirical processes, Ann. Probab., 22, 28-76 (1994) · Zbl 0798.60051 |
| [21] | Talagrand, M., Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems (2016), Springer Berlin Heidelberg |
| [22] | Vapnik, V.; Chervonenkis, A., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 2, 264-280 (1971) · Zbl 0247.60005 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
