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.
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.
- A. Kontorovich, M. Raginsky. Concentration of measure without independence: a unified approach via the martingale method, 2016
- L. Gottlieb, A. Kontorovich, R. Krauthgamer. Adaptive Metric Dimensionality Reduction. Invited to Theoretical Computer Science, 105-118, 2016. Extended abstract appeared in ALT 2013.
- A. Kontorovich, Roi Weiss. A Bayes consistent 1-NN classifier, AISTATS 2015.
- L. Gottlieb, A. Kontorovich, P. Nisnevitch. Near-optimal sample compression for nearest neighbors, NIPS 2014.
- D. Berend, A. Kontorovich. A finite sample analysis of the Naive Bayes classifier, JMLR 16, 1519-1545, 2015. A preliminary version, titled "Consistency of weighted majority votes" appeared in NIPS 2014.
- A. Kontorovich, Roi Weiss. Maximum Margin Multiclass Nearest Neighbors, ICML 2014.
- A. Kontorovich. Concentration in unbounded metric spaces and algorithmic stability, ICML 2014. follow-up notes
- 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
- 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"]
- A. Kontorovich, A. Trachtenberg. Deciding unique decodability of bigram counts via finite automata. Journal of Computer and System Sciences 80(2), 450–456, 2014.
- D. Angluin, J. Aspnes, S. Eisenstat, A. Kontorovich. On the Learnability of Shuffle Ideals. Journal of Machine Learning Research 14, 1513−1531, 2013.
- D. Berend, A. Kontorovich. A Sharp Estimate of the Binomial Mean Absolute Deviation with Applications. Statistics and Probability Letters 83(4), 1254-1259, 2013.
- D. Berend, A. Kontorovich. On the Concentration of the Missing Mass. Electronic Communications in Probability 18(3), 1-7, 2013.
- A. Kontorovich. Obtaining Measure Concentration from Markov Contraction. Markov Processes and Related Fields 18, 613–638, 2012.
- A. Kontorovich. Statistical estimation with bounded memory. Statistics and Computing 22(5), 1155-1164, 2012. [follow-up notes]
- A. Kontorovich, B. Nadler. Universal Kernel-Based Learning with Applications to Regular Languages. Journal of Machine Learning Research 10, 997-1031, 2009.
- A. Kontorovich, C. Cortes, M. Mohri. Kernel Methods for Learning Languages. Invited to Theoretical Computer Science 405, 223-236, 2008. [follow-up notes]
- A. Kontorovich, K. Ramanan. Concentration Inequalities for Dependent Random Variables via the Martingale Method. Annals of Probability 36(6), 2126-2158, 2008.
- A. Kontorovich. Uniquely Decodable n-gram Embeddings. Theoretical Computer Science 329, 271-284, 2004.
- C. R. Shalizi, A. Kontorovich. Predictive PAC Learning and Process Decompositions. In NIPS 2013.
- A. Kontorovich, B. Nadler, R. Weiss. On learning parametric-output HMMs. In ICML 2013.
- L. Gottlieb, A. Kontorovich, R. Krauthgamer. Efficient classification for metric data. IEEE Transactions on Information Theory 60(9), 5750-5759, 2014. [Conference version: COLT 2010.]
- C. Cortes, A. Kontorovich, M. Mohri. Learning Languages with Rational Kernels. In COLT 2007.