Search this site
Embedded Files
Aryeh Kontorovich -- all publications

google scholar | dblp

⚠ Notice

The paper versions given here are the most current, arxiv and other sources notwithstanding.

Errata may be found in the follow-up notes (when these are posted).

Please observe all copyright laws.

Preprints

  • A. Avital, K. Efremenko, A. Kontorovich, D. Toplin, B. Waggoner. Non-parametric binary regression in metric spaces with KL loss

  • I. Katav, A.Kontorovich. ParallelTime: Dynamically Weighting the Balance of Short- and Long-Term Temporal Dependencies

Journals

  1. H. Pratt, A. Polyakov, A. Kontorovich. Evidence for Separate Processing in the Human Brainstem of Interaural Intensity and Temporal Disparities for Sound Lateralization. Hearing Research 108, 1-8, 1997.

  2. A. Kontorovich. Uniquely Decodable n-gram Embeddings. Theoretical Computer Science 329, 271-284, 2004.

  3. A. Kontorovich, K. Ramanan. Concentration Inequalities for Dependent Random Variables via the Martingale Method. Annals of Probability 36(6), 2126-2158, 2008.

  4. A. Kontorovich. Constructing processes with prescribed mixing coefficients. Statistics and Probability Letters 78, 2910-2915, 2008.

  5. A. Kontorovich, C. Cortes, M. Mohri. Kernel Methods for Learning Languages. Invited to Theoretical Computer Science 405, 223-236, 2008. [follow-up notes]

  6. A. Kontorovich, B. Nadler. Universal Kernel-Based Learning with Applications to Regular Languages. Journal of Machine Learning Research 10, 997-1031, 2009.

  7. B. Nadler, A. Kontorovich. Model Selection for Sinusoids in Noise: Statistical Analysis and a New Penalty Term. IEEE Transactions on Signal Processing 59(4), 1333-1345, 2011.

  8. A. Kontorovich. Statistical estimation with bounded memory. Statistics and Computing 22(5), 1155-1164, 2012. [follow-up notes]

  9. L. Gottlieb, A. Kontorovich, E. Mossel. VC bounds on the cardinality of nearly orthogonal function classes. Discrete Mathematics 312(10), 1766-1775, 2012.

  10. D. Berend, A. Kontorovich. The Missing Mass Problem. Statistics and Probability Letters 82(6), 1102-1110, 2012.

  11. A. Kontorovich. Obtaining Measure Concentration from Markov Contraction. Markov Processes and Related Fields 18, 613-638, 2012.

  12. A. Kontorovich, A. Brockwell. A Strong Law of Large Numbers for Strongly Mixing Processes. Communications in Statistics - Theory and Methods 43(18), pp. 3777-3796, 2014.

  13. L. Chekina, D. Gutfreund, A. Kontorovich, L. Rokach, B. Shapira. Exploiting Label Dependencies for Improved Sample Complexity. Machine Learning 1-42, 2012.

  14. A. Kontorovich. An Explicit Bound on the Transportation Cost Distance. Communications in Mathematical Analysis 14(1), 1-14, 2013.

  15. A. Kontorovich. An inequality involving the $ell_1$, $ell_2$ and $ell_infty$ norms. Analysis and Applications 11(6), 2013.

  16. D. Berend, A. Kontorovich. On the Concentration of the Missing Mass. Electronic Communications in Probability 18(3), 1-7, 2013.

  17. D. Berend, A. Kontorovich. A Sharp Estimate of the Binomial Mean Absolute Deviation with Applications. Statistics and Probability Letters 83(4), 1254-1259, 2013.

  18. T. Becker, A. Greaves-Tunnell, A. Kontorovich, S. J. Miller, K. Shen. Virus Dynamics on Starlike Graphs. Journal of Nonlinear Systems and Applications 4(1), 53-63, 2013.

  19. D. Angluin, J. Aspnes, S. Eisenstat, A. Kontorovich. On the Learnability of Shuffle Ideals. Journal of Machine Learning Research 14, 1513-1531, 2013.

  20. A. Kontorovich, A. Trachtenberg. Deciding unique decodability of bigram counts via finite automata. Journal of Computer and System Sciences 80(2), 450-456, 2014.

  21. D. Berend, P. Harremoës, A. Kontorovich. Minimum KL-divergence on complements of $L_1$ balls. IEEE Transactions on Information Theory 60(6), 3172-3177, 2014. [Former title: "A Reverse Pinsker Inequality"]

  22. A. Kontorovich, Roi Weiss. Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes. Journal of Applied Probability 51, 1-14, 2014. follow-up notes

  23. O. Asor, H. Duan, A. Kontorovich. On the Additive Properties of the Fat-Shattering Dimension. IEEE Transactions on Neural Networks and Learning Systems 25(12), 2309-2312, 2014.

  24. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient classification for metric data. IEEE Transactions on Information Theory 60(9), 5750-5759, 2014.

  25. D. Berend, A. Kontorovich. A finite sample analysis of the Naive Bayes classifier, Journal of Machine Learning Research 16, 1519-1545, 2015. corrigendum

  26. D. Gordon, D. Hendler, A. Kontorovich, L. Rokach. Local-shapelets for fast classification of spectrographic measurements, Expert Systems with Applications 42, 3150-3158, 2015.

  27. D. Gutfreund, A. Kontorovich, R. Levy, M. Rosen-Zvi. Boosting Conditional Probability Estimators. Annals of Mathematics and Artificial Intelligence 1-16, 2015.

  28. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Adaptive Metric Dimensionality Reduction. Invited to Theoretical Computer Science, 105-118, 2016.

  29. D. Berend, A. Kontorovich. The state complexity of random DFAs, Theoretical Computer Science, 102-108, 2016.

  30. L. Gottlieb, A. Kontorovich, P. Nisnevitch. Nearly optimal classification for semimetrics. Journal of Machine Learning Research 18(37):1−22, 2017.

  31. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. IEEE Transactions on Information Theory 63(8):4838-4849, 2017.

  32. D. Berend, A. Kontorovich, G. Zagdanski. The expected missing mass under an entropy constraint. Entropy 19(7):315, 2017.

  33. A. Kontorovich, S. Sabato, R. Urner. Active Nearest-Neighbor Learning in Metric Spaces. Journal of Machine Learning Research 18: 195:1-195:38, 2017.

  34. L. Gottlieb, A. Kontorovich, P. Nisnevitch. Near-optimal sample compression for nearest neighbors. IEEE Transactions on Information Theory 64(6): 4120-4128, 2018.

  35. A. Kontorovich, I. Pinelis. Exact Lower Bounds for the Agnostic Probably-Approximately-Correct (PAC) Machine Learning Model. Annals of Statistics 47(5):2822-2854, 2019.

  36. D. Hsu, A. Kontorovich, D. Levin, Y. Peres, C. Szepesvári, G. Wolfer. Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path. Annals of Applied Probability 29(4), 2439-2480, 2019.

  37. S. Hanneke, A. Kontorovich. Optimality of SVM: Novel Proofs and Tighter Bounds. Theoretical Computer Science 796, 99–113, 2019.

  38. D. Berend, A. Kontorovich, L. Reyzin, T. Robinson. On Biased Random Walks, Corrupted Intervals, and Learning Under Adversarial Design. Annals of Mathematics and Artificial Intelligence 2020.

  39. G. Wolfer, A. Kontorovich. Statistical Estimation of Ergodic Markov Chain Kernel over Discrete State Space. Bernoulli 27(1), 532–553 2021.

  40. S. Hanneke, A. Kontorovich, S. Sabato, R. Weiss. Universal Bayes consistency in metric spaces. Ann. Stat. 49(4):2129-2150, 2021.

  41. Gottlieb, Kontorovich. Non-uniform packings. Information Processing Letters, 2022.

  42. Gottlieb, Kaufman,Kontorovich. Apportioned margin approach for cost sensitive large margin classifiers. Annals of Mathematics and Artificial Intelligence, 2021.

  43. Gottlieb, Kaufman, Kontorovich, Nivasch. Learning convex polyhedra with margin. IEEE Transactions on Information Theory, 2021.

  44. Levi, Attias, Kontorovich. Domain Invariant Adversarial Learning. Transactions on Machine Learning Research, 2022.

  45. Györfi, Kontorovich, Weiss. Tree density estimation. IEEE Transactions on Information Theory, 2022.

  46. Cohen, Kontorovich, Koolyk, Wolfer. Dimension-Free Empirical Entropy Estimation. IEEE Transactions on Information Theory. 2023+

  47. Wolfer, Kontorovich. Improved Estimation of Relaxation Time in Non-reversible Markov Chains. Annals of Applied Probability. 34(1A): 249-276, 2024.

  48. H. Zaichyk, A Biess, A. Kontorovich, Y. Makarychev. Regression via Kirszbraun Extension. Mathematical Programming, 2024.

  49. I. Attias, A. Kontorovich. Fat-Shattering Dimension of k-fold Aggregations. JMLR, 2024

  50. A. Kontorovich. On the tensorization of the variational distance. to appear in Electronic Communications in Probability, 2025+

  51. A. Kontorovich, A. Painsky. Distribution Estimation under the Infinity Norm. to appear in JMLR 2025+


Refereed Conferences and Workshops

  1. A. Kontorovich, C. Cortes, M. Mohri. Learning Linearly Separable Languages. In ALT 2006. [follow-up notes]

  2. C. Cortes, A. Kontorovich, M. Mohri. Learning Languages with Rational Kernels. In COLT 2007.

  3. A. Kontorovich. A Universal Kernel for Learning Regular Languages. In MLG 2007 (distinguished contribution award). [watch video]

  4. D. Angluin, D. Eisenstat, A. Kontorovich, L. Reyzin. Lower Bounds on Learning Random Structures with Statistical Queries. In ALT 2010.

  5. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient classification for metric data. In COLT 2010.

  6. A. Kontorovich, D. Hendler, E. Menahem. Metric Anomaly Detection Via Asymmetric Risk Minimization. In SIMBAD 2011.

  7. A. Kontorovich, A. Trachtenberg. String reconciliation with unknown edit distance. In ISIT 2012.

  8. D. Angluin, J. Aspnes, A. Kontorovich. On the Learnability of Shuffle Ideals. In ALT 2012.

  9. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. In SIMBAD 2013.

  10. A. Filtser, J. Jin, A. Kontorovich, A. Trachtenberg. Efficient determination of the unique decodability of a string. In ISIT 2013.

  11. A. Kontorovich, B. Nadler, R. Weiss. On learning parametric-output HMMs. In ICML 2013.

  12. L. Gottlieb, A. Kontorovich, R. Krauthgamer. Adaptive Metric Dimensionality Reduction. In ALT 2013.

  13. C. R. Shalizi, A. Kontorovich. Predictive PAC Learning and Process Decompositions. In NIPS 2013.

  14. D. Gutfreund, A. Kontorovich, R. Levy, M. Rosen-Zvi. Boosting Conditional Probability Estimators. Invited to ISAIM Theory of Machine Learning Special Session, 2014.

  15. A. Kontorovich. Concentration in unbounded metric spaces and algorithmic stability, ICML 2014.

  16. A. Kontorovich, Roi Weiss. Maximum Margin Multiclass Nearest Neighbors, ICML 2014.

  17. D. Berend, A. Kontorovich. Consistency of weighted majority votes, NIPS 2014.

  18. L. Gottlieb, A. Kontorovich, P. Nisnevitch. Near-optimal sample compression for nearest neighbors, NIPS 2014.

  19. A. Kontorovich, Roi Weiss. A Bayes consistent 1-NN classifier. AISTATS 2015. Erratum

  20. D. Hsu, A. Kontorovich, C. Szepesvári. Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path. NIPS 2015.

  21. L. Gottlieb, A. Kontorovich, P. Nisnevitch. Nearly optimal classification for semimetrics. AISTATS (Oral) 2016.

  22. A. Kontorovich, S. Sabato, R. Urner. Active Nearest-Neighbor Learning in Metric Spaces. NIPS 2016. Long version

  23. M. Levi, Y. Allouche, A. Kontorovich. Advanced Analytics for Connected Cars Cyber Security. Vehicular Technology Conference 2018.

  24. A. Kontorovich, S. Sabato, R. Weiss. Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions. NIPS 2017. corrigendum

  25. L. Gottlieb, E. Kaufman, A. Kontorovich, G. Nivasch. Learning convex polytopes with margin. NIPS 2018.

  26. E. Gutflaish, A. Kontorovich, S. Sabato, O. Biller, O. Sofer. Temporal anomaly detection: calibrating the surprise. AAAI 2019.

  27. G. Wolfer, A. Kontorovich. Minimax Learning of Ergodic Markov Chains. ALT 2019.

  28. S. Hanneke, A. Kontorovich. A Sharp Lower Bound for Agnostic Learning with Sample Compression Schemes. ALT 2019.

  29. S. Hanneke, A. Kontorovich, M. Sadigurschi. Sample Compression for Real-Valued Learners. ALT 2019.

  30. I. Attias, A. Kontorovich, Y. Mansour. Improved generalization bounds for robust learning. ALT 2019. errata

  31. G. Wolfer, A. Kontorovich. Estimating the Mixing Time of Ergodic Markov Chains. COLT 2019.

  32. G. Wolfer, A. Kontorovich. Minimax Testing of Identity to a Reference Ergodic Markov Chain. AISTATS 2020.

  33. K. Efremenko, A. Kontorovich, M. Noivirt. Fast and Bayes-consistent nearest neighbors. AISTATS 2020.

  34. D. Cohen, A. Kontorovich, G. Wolfer. Learning discrete distributions with infinite support. NIPS 2020.

  35. S. Hanneke, A. Kontorovich. Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound. ALT 2021.

  36. A. Gottlieb, E. Kaufman, A. Kontorovich. Piecewise Linear Regression Using A Nested Barycentric Coordinate System. AISTATS 2021.

  37. Y. Ashlagi, L. Gottlieb, A. Kontorovich. Functions with average smoothness: structure, algorithms, and learning. COLT 2021.

  38. D. Tsir Cohen, A. Kontorovich. Learning with metric losses. COLT 2022.

  39. A. Kontorovich, M. Sadigurschi, U. Stemmer. Adaptive Data Analysis with Correlated Observations. ICML 2022.

  40. Doron Cohen, A. Kontorovich. Local Glivenko-Cantelli. COLT 2023.

  41. S. Hanneke, A. Kontorovich, G. Kornowski. Near-optimal learning with average Hölder smoothness. NIPS 2023

  42. M. Levi, A. Kontorovich. Splitting the Difference on Adversarial Training. USENIX 2024.

  43. S.Hanneke, A. Kontorovich, G. Kornowski. Efficient Agnostic Learning with Average Smoothness. ALT2024

  44. I. Attias, S. Hanneke, A. Kontorovich, M. Sadigurschi. Agnostic Sample Compression Schemes for Regression. ICML 2024

  45. M. Blanchard, D. Cohen, A. Kontorovich. Correlated Binomial Process. COLT 2024

  46. A. Kontorovich, A. Avital. Sharp bounds on aggregate expert error. ALT 2025

  47. Doron Cohen, A. Kontorovich, R. Weiss. The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli. ICML 2025.

Refereed chapters and proceedings

  1. A. Kontorovich, M. Raginsky. Concentration of measure without independence: a unified approach via the martingale method. Invited to The IMA volumes in mathematics and its applications, 2016.

  2. A. Kontorovich, S. Kpotufe. Nearest-Neighbor methods: A modern perspective. Invited to Handbook of Machine Learning for Data Science, 2022+.

  3. G. Wolfer, A. Kontorovich. Learning and Identity Testing of Markov Chains. Invited to Handbook of Handbook of Statistics, 2023+. 

Unrefereed

  • A. Kontorovich. Measure Concentration of Strongly Mixing Processes with Applications, PhD thesis. [follow-up notes]

  • A. Kontorovich, J. Lafferty, D. Blei. Variational Inference and Learning for a Unified Model of Syntax, Semantics and Morphology, CMU technical report, 2006.

  • A. Kontorovich, D. Ron, Y. Singer. A Markov Model for the Acquisition of Morphological Structure. CMU technical report, 2003.


⏎ Main


Google Sites
Report abuse
Page details
Page updated
Google Sites
Report abuse