Fetching the paper…
Reading the bibliography…
We extend a recently proposed 1-nearest-neighbor based multiclass learning algorithm and prove that our modification is universally strongly Bayes-consistent in all metric spaces admitting any such learner, making it an "optimistically universal" Bayes-consistent learner.
1906
Earlier work this paper cites.
[author] Ulam, Stanislaw MarcinS. M. (1930). Zur Masstheorie in der allgemeinen Mengenlehre. Uniwersytet, seminarjum matematyczne
1930
Earlier work this paper cites.
[author] Stone, Arthur HaroldA. H. (1962). Non-separable Borel sets. General Topology and its Relations to Modern Analysis and Algebra 341–342
1962
Earlier work this paper cites.
[author] Cover, Thomas M.T. M. and Hart, Peter E.P. E. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory 13 21–27
1967
Earlier work this paper cites.
[author] Billingsley, PatrickP. (1968). Convergence of probability measures, first ed. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons Inc., New York. A Wiley-Interscience Publication. MR1700749 (2000e:60008)
1968
Earlier work this paper cites.
[author] Kolmogorov, A. N.A. N. and Fomin, S. V.S. V. (1970). Introductory Real Analysis. Prentice Hall
1970
Earlier work this paper cites.
[author] Stone, Charles J.C. J. (1977). Consistent Nonparametric Regression. The Annals of Statistics 5 595–620. 10.1214/aos/1176343886
1977
Earlier work this paper cites.
[author] Preiss, DavidD. (1979). Invalid Vitali theorems. Abstracta. 7th Winter School on Abstract Analysis 58–60
1979
Earlier work this paper cites.
[author] Preiss, DavidD. (1981). Gaussian measures and the density theorem. Comment. Math. Univ. Carolin. 22 181–193. 609946
1981
Earlier work this paper cites.
[author] Littlestone, NickN. and Warmuth, Manfred K.M. K. (1986). Relating Data Compression and Learnability. Unpublished
1986
Earlier work this paper cites.
[author] Fix, EvelynE. and Hodges, Jr.J. J. L. (1989). Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties. International Statistical Review / Revue Internationale de Statistique 57 pp. 238-247
1989
Earlier work this paper cites.
[author] Gitik, MotiM. and Shelah, SaharonS. (1989). Forcings with ideals and simple forcing notions. Israel Journal of Mathematics 68 129–160
1989
Earlier work this paper cites.
Fremlin, D. H
1993
Earlier work this paper cites.
[author] Kechris, A. S.A. S. (1995). Classical Descriptive Set Theory. Springer-Verlag New York
1995
Earlier work this paper cites.
[author] Kulkarni, Sanjeev R.S. R. and Posner, Steven E.S. E. (1995). Rates of convergence of nearest neighbor estimation under arbitrary sampling. IEEE Trans. Inform. Theory 41 1028–1039. 10.1109/18.391248
1995
Earlier work this paper cites.
[author] Schervish, Mark J.M. J. (1995). Theory of statistics. Springer Series in Statistics. Springer-Verlag, New York. 10.1007/978-1-4612-4250-5 1354146
1995
Earlier work this paper cites.
[author] Devroye, LucL., Györfi, LászlóL. and Lugosi, GáborG. (1996). A probabilistic theory of pattern recognition. Springer-Verlag New York, Inc
1996
Earlier work this paper cites.
[author] Barbati, AlbertoA., Costantini, CamilloC. et al. (1997). On the density of the hyperspace of a metric space. Commentationes Mathematicae Universitatis Carolinae 38 349–360
1997
Cited alongside, same era.
[author] Dudley, Richard M.R. M. (1999). Uniform Central Limit Theorems. Cambridge Studies in Advanced Mathematics. Cambridge University Press
1999
Cited alongside, same era.
[author] Hrbacek, KarelK. and Jech, ThomasT. (1999). Introduction to set theory. Crc Press
1999
Cited alongside, same era.
[author] Fremlin, David HeaverD. H. (2000). Measure theory 1-5. Torres Fremlin
2000
Cited alongside, same era.
[author] Györfi, L.L., Kohler, M.M., Krzyżak, A.A. and Walk, H.H. (2002). A Distribution-Free Theory of Nonparametric Regression. Springer-Verlag New York, Inc
2002
Cited alongside, same era.
[author] Pelillo, MarcelloM. (2014). Alhazen and the nearest neighbor rule. Pattern Recognition Letters 38 34–37. 10.1016/j.patrec.2013.10.022
2013
Later among the works it cites.
Chaudhuri, K
2014
Later among the works it cites.
[author] Gottlieb, Lee-AdL., Kontorovich, AryehA. and Krauthgamer, RobertR. (2014). Efficient Classification for Metric Data (extended abstract COLT 2010). IEEE Transactions on Information Theory 60 5750–5759. 10.1109/TIT.2014.2339840
2014
Later among the works it cites.
Kontorovich, A
2014
Later among the works it cites.
[author] Shalev-Shwartz, ShaiS. and Ben-David, ShaiS. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press
2014
Later among the works it cites.
Kontorovich, A
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
[author] Jech, ThomasT. (2003). Set theory. Springer Monographs in Mathematics. Springer-Verlag, Berlin The third millennium edition, revised and expanded. 1940513
2003
Cited alongside, same era.
[author] Tišer, JaroslavJ. (2003). Vitali covering theorem in Hilbert space. Trans. Amer. Math. Soc. 355 3277–3289. 10.1090/S0002-9947-03-03296-3 1974687
2003
Cited alongside, same era.
[author] Biau, GérardG., Bunea, FlorentinaF. and Wegkamp, Marten H.M. H. (2005). Functional classification in Hilbert spaces. IEEE Trans. Inform. Theory 51 2163–2172. 10.1109/TIT.2005.847705 2235289
2005
Cited alongside, same era.
[author] Graepel, ThoreT., Herbrich, RalfR. and Shawe-Taylor, JohnJ. (2005). PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification. Machine Learning 59 55–76
2005
Cited alongside, same era.
[author] Abraham, ChristopheC., Biau, GérardG. and Cadre, BenoîtB. (2006). On the kernel rule for function classification. Ann. Inst. Statist. Math. 58 619–633. 10.1007/s10463-006-0032-1 2327897
2006
Cited alongside, same era.
[author] Cérou, FrédéricF. and Guyader, ArnaudA. (2006). Nearest neighbor classification in infinite dimension. ESAIM: Probability and Statistics 10 340–355
2006
Cited alongside, same era.
Maurer, A
2009
Cited alongside, same era.
2015
Later among the works it cites.
[author] Gottlieb, Lee-AdL.-A., Kontorovich, AryehA. and Nisnevitch, PinhasP. (2017). Nearly optimal classification for semimetrics (extended abstract AISTATS 2016). Journal of Machine Learning Research 18 1-22
2016
Later among the works it cites.
[author] Kontorovich, AryehA., Sabato, SivanS. and Urner, RuthR. (2017). Active Nearest-Neighbor Learning in Metric Spaces (extended abstract: NIPS 2016). Journal of Machine Learning Research 18 195:1–195:38
2016
Later among the works it cites.
2017
Later among the works it cites.
Kontorovich, A
2017
Later among the works it cites.
2017
Later among the works it cites.
[author] Kpotufe, SamoryS. and Verma, NakulN. (2017). Time-accuracy tradeoffs in kernel prediction: controlling prediction quality. Journal of Machine Learning Research 18 1443–1471
2017
Later among the works it cites.
[author] Gottlieb, Lee-AdL., Kontorovich, AryehA. and Nisnevitch, PinhasP. (2018). Near-optimal sample compression for nearest neighbors. IEEE Trans. Information Theory 64 4120–4128. 10.1109/TIT.2018.2822267
2018
Later among the works it cites.
[author] Ben-David, ShaiS., Hrubes, PavelP., Moran, ShayS., Shpilka, AmirA. and Yehudayoff, AmirA. (2019). Learnability can be undecidable. Nature Machine Intelligence 1 44-48. 10.1038/s42256-018-0002-3
2019
Closest in time.
Hanneke, S
2019
Closest in time.
[author] Hanneke, SteveS., Kontorovich, AryehA., Sabato, SivanS. and Weiss, RoiR. (2019). Supplementary material for “Universal Bayes consistency in metric spaces”
2019
Closest in time.