# Shahar Mendelson

Professor

### Research interests

My main research interest is Statistical Learning Theory – the theoretical foundations of Machine Learning; in particular, I study the connections between High Dimensional Statistics/Statistical Learning Theory, Empirical Processes, and Asymptotic Geometric Analysis.

### Groups

Refereed Publications:

Books

⦁ Advanced Lectures on Machine Learning, S. Mendelson and A.J. Smola Editors, Lecture Notes in Computer Sciences 2600, Springer 2003.

⦁ Geometric Aspects of Functional Analysis, Israel Seminar 2006-2010, Bo'az Klartag, Shahar Mendelson and Vitali D. Milman Editors, Lecture notes in Mathematics 2050, Springer 2012.

Refereed Papers (accepted)

Journal papers and refereed book chapters

⦁ S. Mendelson, A new on-line learning model, Neural Computation 13(4), 935-957, 2001.

⦁ S. Mendelson and I. Nelken, Recurrence techniques in the analysis of neural networks, Neural Computation 13(8) 1839-1861, 2001.

⦁ S. Mendelson, $\ell$-norm and its application to Learning Theory, Positivity, 5, 177-191, 2001.

⦁ S. Mendelson, On the size of convex hulls of small sets, Journal of Machine Learning Research 2, 1-18, 2001.

⦁ S. Mendelson, Learnability in Hilbert spaces with Reproducing Kernels, Journal of Complexity, 18(1), 152-170, 2002.

⦁ S. Mendelson, Rademacher averages and phase transitions in Glivenko-Cantelli classes, IEEE Transactions on Information Theory, 48(1), 251-263, 2002.

⦁ S. Mendelson, Improving the sample complexity using global data, IEEE Transactions on Information Theory 48(7), 1977-1991, 2002.

⦁ P.L. Bartlett, S. Mendelson, Rademacher and Gaussian complexities: risk bounds and structural results, Journal of Machine Learning Research 3, 463-482, 2002.

⦁ S. Mendelson, A few notes on Statistical Learning Theory, in Advanced Lectures on Machine Learning, S. Mendeslon and A.J. Smola (Eds.), Lecture notes in computer sciences 2600, Springer, 1-40, 2003.

⦁ S. Mendelson, R. Vershynin, Entropy and the combinatorial dimension, Inventiones Mathematicae, 152(1), 37-55, 2003.

⦁ S. Mendelson, On the performance of kernel classes, Journal of Machine Learning Research, 4, 759-771, 2003.

⦁ G. Lugosi, S. Mendelson, V. Koltchinskii, A note on the richness of convex hulls of VC classes, Electronic Communications in Probability, 8, 167-169, 2003.

⦁ S. Mendelson, R. Vershynin, Remarks on the geometry of coordinate projections in , Israel Journal of Mathematics, 140, 203-220, 2004.

⦁ S. Mendelson, P. Philips, On the importance of "small" coordinate projections, Journal of Machine Learning Research, 5, 219-238, 2004.

⦁ S. Mendelson, Mathematical aspects of learning, Geometric aspects of Functional Analysis, Lecture Notes in Mathematics 1850, 193-236, 2004.

⦁ S. Mendelson, G. Schechtman, The shattering dimension of sets of linear functionals, Annals of Probability 32(3A), 1746-1770, 2004.

⦁ P.L. Bartlett, O. Bousquet, S. Mendelson, Local Rademacher Complexities, Annals of Statistics 33(4) 1497-1537, 2005.

⦁ F. Barthe, O. Guedon, S. Mendelson, A. Naor, A probabilistic approach to the geometry of the ball, Annals of Probability, 33(2), 480-513, 2005.

⦁ S. Mendelson, Embeddings with a Lipschitz function, Random Structures and Algorithms, 27(1) 25-45, 2005.

⦁ B. Klartag, S. Mendelson, Empirical Processes and Random Projections, Journal of Functional Analysis, 225(1) 229-245, 2005.

⦁ S. Mendelson, A. Pajor, M. Rudelson, On the Geometry of random {-1,1}-polytopes, Discrete and Computational Geometry, 33(3) 365-379, 2005.

⦁ S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Reconstruction and subgaussian processes, CRAS 340(12) 885-888, 2005.

⦁ P.L. Bartlett, S. Mendelson, Empirical minimization, Probability Theory and Related Fields, 135, 311-334, 2006.

⦁ S. Mendelson, A. Pajor, On singular values of matrices with independent rows, Bernoulli, 12(5), 761-773, 2006.

⦁ P.L. Bartlett, S. Mendelson, Local Rademacher complexities and empirical minimization, Annals of Statistics, 34, 2657-2663, 2006.

⦁ S. Mendelson, J. Zinn, Modified Empirical CLT's under only pre-Gaussian conditions, in IMS lecture notes monograph series vol 51, 173-184, 2006.

⦁ N. Linial, S. Mendelson, G. Schechtman, A. Schraibman, Complexity measures of sign matrices, Combinatorica, 27(4) 439-463, 2007.

⦁ S. Mendelson, Lipschitz representations of subsets of the cube, Proceedings of the AMS, 135, 1455-1463, 2007.

⦁ S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Reconstruction and subgaussian operators, Geometric and Functional Analysis, 17(4), 1248-1282, 2007.

⦁ O. Guedon, S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Subspaces and orthogonal decompositions generated by bounded orthogonal systems, Positivity, 11(2), 269-283, 2007.

⦁ Y. Gordon, A. Litvak, S. Mendelson, A. Pajor, Gaussian averages of interpolated bodies, Journal of Approximation Theory, 149, 59-73, 2007.

⦁ S. Mendelson, N. Tomczak-Jaegermann, A subgaussian embedding theorem, Israel Journal of Mathematics, 164, 349-364, 2008.

⦁ S. Mendelson, On weakly bounded empirical processes, Math. Annalen, 340(2), 293-314, 2008.

⦁ S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Uniform uncertainty principle for Bernoulli and subgaussian ensembles, Constructive Approximation, 28, 277-289, 2008.

⦁ S. Mendelson, Obtaining fast error rates in nonconvex situations, Journal of Complexity, 24(3), 380-397, 2008.

⦁ S. Mendelson, Lower bounds for the empirical minimization algorithm, IEEE Transactions on Information Theory, 54(8) 3797-3803, 2008.

⦁ O. Guedon, S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Majorizing measures and proportional subsets of bounded orthonormal systems, Revista Mathematica Iberoamricana, 24(3). 1075-1095, 2008.

⦁ G. Lecue, S. Mendelson, Aggregation via Empirical risk minimization, Probability Theory and related Fields, 145, 591-613, 2009.

⦁ P.L. Bartlett, S. Mendelson, P. Philips, Optimal sample based estimates of the expectation of the empirical minimizer, ESAIM, 14, 315-337, 2010.

⦁ S. Mendelson, J. Neeman, Regularization in Kernel Learning, Annals of Statistics, 38(1), 526-565, 2010.

⦁ G. Lecue, S. Mendelson, Sharper bounds on the performance of the empirical minimization algorithm, Bernoulli, 16(3), 605-613, 2010.

⦁ S. Mendelson, Empirical processes with a bounded $\Psi_1$ diameter, Geometric and Functional Analysis, 20(4) 988-1027, 2010.

⦁ S. Mendelson, Discrepancy, Chaining and Subgaussian processes, Annals of Probability, 39(3) 985-1026, 2011.

⦁ P. Bartlett, S. Mendelson, J. Neeman, -regularized linear regression: Persistence and oracle inequalities, Probability Theory and Related Fields, 154, 193-224, 2012.

⦁ G. Lecue, S. Mendelson, General non-exact oracle inequalities in the unbounded case, Annals of Statistics, 40(2), 832-860, 2012.

⦁ S. Mendelson, G. Paouris, On generic chaining and the smallest singular values of random matrices with heavy tails, Journal of Functional Analysis, 262(9), 3775-3811, 2012.

⦁ G. Lecue, S. Mendelson, Optimality of the aggregate with exponential weights for low temperatures, Bernoulli, 19(2) 646-675, 2013.

⦁ G. Lecue, S. Mendelson, On the optimality of the empirical risk minimization procedure for the Convex Aggregation problem, Annales d'IHP, 49(1), 288-306, 2013.

⦁ S. Mendelson, G. Paouris, On the singular values of random matrices, Journal of the European Mathematical Society, 16, 823-834, 2014.

⦁ F. Krahmer, S. Mendelson, H. Rauhut, Suprema of chaos processes and the restricted isometry property, Communications on Pure and Applied Mathematics, 67(11) 1877-1904, 2014.

⦁ Y.C. Eldar, S. Mendelson, Phase Retrieval: Stability and Recovery Guarantees, Applied and computational Harmonic Analysis, 26(3), 473-494, 2014.

⦁ S. Mendelson, A remark on the diameter of random sections of convex bodies, Geometric aspects of Functional Analysis, Lecture notes in Mathematics 2116 (B. Klartag and E. Milman Eds), 395-404, 2014.

⦁ S. Mendelson, Learning without concentration, Journal of the ACM, 62(3), Article No. 21, 1-25, 2015.

⦁ V. Koltchinskii, S. Mendelson, Bounding the smallest singular value of a random matrix without concentration, International Mathematics Research Notices, Vol. 2015 (23), 12991–13008, 2015.

⦁ G. Lecue, S. Mendelson, Minimax rate of convergence and the performance of ERM in phase recovery, Electronic Journal of Probability 20(57), 1-29, 2015.

⦁ G. Lecue, S. Mendelson, Performance of empirical risk minimization in linear aggregation, Bernoulli, 23(3) 1520-1534, 2016.

⦁ S. Mendelson, Upper bounds on product and multiplier empirical processes, Stochastic Processes and their Applications, 126(12), 3652–3680, 2016.

⦁ S. Mendelson, Dvoretzky type theorems for subgaussian coordinate projections, J. Theoretical Probability, 29(4), 1644-1660, 2016.

⦁ G. Lecue, S. Mendelson, Learning subgaussian classes: Upper and minimax bounds, Topics in Learning Theory - Société Mathématique de France, (S. Boucheron and N. Vayatis Eds.), to appear (37 pages).

⦁ G. Lecue, S. Mendelson, Sparse recovery under weak moment assumptions, Journal of the European Mathematical Society, 19(3), 881-904, 2017.

⦁ S. Mendelson, On multiplier processes under weak moment assumptions, Geometric aspects of Functional Analysis, Lecture notes in Mathematics, 2169, 301–318, Springer, 2017.

⦁ S. Mendelson, On aggregation for heavy-tailed classes, Probability Theory and Related Fields, 168(3), 641-674, 2017.

⦁ S. Mendelson, 'local' vs. 'global' parameters – breaking the Gaussian complexity barrier, Annals of Statistics 45(5), 1835-1862, 2017.

⦁ G. Lecue, S. Mendelson, Regularization and the small-ball method II: complexity dependent error rates, Journal of Machine Learning Research, 18(146), 1−48, 2017.

⦁ G. Lecue, S. Mendelson, Regularization and the small-ball method I: sparse recovery, Annals of Statistics, 46(2), 611-641, 2018.

⦁ S. Mendelson, Learning without concentration for general loss functions, Probability Theory and Related Fields, 171(1), 459-502, 2018.

⦁ S. Mendelson, Column normalization of a random measurement matrix, Electronic Communications in Probability, 23, article13, 1-8, 2018.

⦁ S. Mendelson, H. Rauhut, R. Ward, Improved bounds for sparse recovery from subsampled random convolutions, Annals of Applied Probability, 28 (6), 3491-3527, 2018.

⦁ G. Lugosi, S. Mendelson, Sub-Gaussian estimators of the mean of a random vector, Annals of Statistics, 47(2) 783-794, 2019.

⦁ S. Mendelson, E. Milman, G. Paouris, Generalized Sudakov via Dimension Reduction - A Program, Studia Math, 244, 159-202, 2019.

⦁ G. Lugosi, S. Mendelson, Regularization, sparse recovery and median-of-means tournaments, Bernoulli, 25(3) 2075-2106, 2019.

⦁ G. Lugosi, S. Mendelson, Near-optimal mean estimators with respect to general norms, Probability Theory and related Fields, 175(3-4), 957-973, 2019.

⦁ G. Lugosi, S. Mendelson, Mean estimation and regression under heavy-tailed distributions – a survey, Foundations of Computational Mathematics, 19(5), 1145-1190, 2019.

⦁ S. Mendelson, An unrestricted learning procedure, Journal of the ACM, 66(6), article 42, 2019 (42 pages).

⦁ G. Lugosi, S. Mendelson, Risk minimization by median-of-means tournaments, Journal of the European Mathematical Society, 22(3), 925-965, 2020.

⦁ G. Lugosi, S. Mendelson, N. Zhivotovskiy, Concentration of the spectral norm of Erdos-Renyi random graphs, Bernoulli, 26(3), 2253-2274, 2020.

⦁ S. Mendelson, On the geometry of random polytopes, Geometric aspects of Functional Analysis, Lecture notes in Mathematics, 2266, 187-198, 2020.

⦁ S. Mendelson, N. Zhivotovskiy, Robust covariance estimation under L_4-L_2 norm equivalence, Annals of Statistics, 48(3), 1648-1664, 2020.

⦁ S. Mendelson, Approximating the covariance ellipsoid,  Communication in Contemporary Mathematics, 22(8) 1950089, 24 pages, 2020.

⦁ S. Mendelson, Extending the scope of the small-ball method, Studia Mathematica, 256(2), 147-167, 2021.

⦁ G. Lugosi, S. Mendelson, Robust multivariate mean estimation: the optimality of trimmed mean, Annals of Statistics, 49(1), 393-410, 2021.

⦁ S. Dirksen, S. Mendelson, Robust one-bit compressed sensing with non-gaussian measurements,  Journal of the European Mathematical Society, 23(9), 2913-2947, 2021.

S. Mendelson, Learning bounded subsets of Lp , IEEE Transactions on Information Theory, 67(8), 5269-5282, 2021.

S. Mendelson, Approximating  L_p unit balls via random sampling, Advances in Mathematics, vol 386, article 107829, 2021 (21 pages).

O. Guedon, F. Krahmer, C. Kummerle, H. Rauhut, S. Mendelson, On the geometry of polytopes generated by heavy-tailed random vectors, Communications in Contemporary Mathematics, 24(3), article 2150056, 2022 (31 pages).

S. Mendelson, Column randomization and almost-isometric embeddings, Information and Inference: A journal of the IMA, to appear (22 pages).

D. Bartl, S. Mendelson, On Monte-Carlo methods in convex stochastic optimization, Annals of Applied Probability, to appear (53 pages).

D. Bartl, S. Mendelson, Random embeddings with an almost gaussian distortion, Advances in Mathematics, vol 400, article 108261, 2022 (31 pages).

S. Mendelson, An isomorphic Dvoretzky-Milman Theorem using general random ensembles, Journal of Functional Analysis, 283(2), article 109473, 2022 (36 pages).

Refereed Conference Papers

⦁ S. Mendelson, N. Tishby, Statistical Sufficiency for classes in empirical spaces, in Proceedings of the 13th annual conference on Computational Learning Theory COLT00, Nicolo Cesa-Bianchi, Sally A. Goldman (Eds.), Morgan Kaufmann, 81-89, 2000.

⦁ S. Mendelson, Geometric methods in the analysis of Glivenko-Cantelli Classes, in Proceedings of the 14th annual conference on Computational Learning Theory COLT01, David P. Helmbold, Bob Williamson (Eds.), Lecture Notes in Computer Science 2111, Springer, 256-272, 2001.

⦁ S. Mendelson, Learning relatively small classes, in Proceedings of the 14th annual conference on Computational Learning Theory COLT01, David P. Helmbold, Bob Williamson (Eds.), Lecture Notes in Computer Science 2111, Springer, 273-288, 2001.

⦁ P. L. Bartlett, S. Mendelson, Rademacher and Gaussian complexities: risk bounds and structural results, in Proceedings of the 14th annual conference on Computational Learning Theory COLT01, David P. Helmbold, Bob Williamson (Eds.), Lecture Notes in Computer Science 2111, Springer, 224-240, 2001.

⦁ S. Mendelson, R.C. Williamson, Agnostic learning of non-convex classes of functions, in Proceedings of the 15th annual conference on Computational Learning Theory COLT02, Jyrki Kivinen and Robert H. Sloan(Eds.), Lecture Notes in Computer Sciences 2375, Springer, 1-13, 2002.

⦁ S. Mendelson, R. Vershynin, Entropy, combinatorial dimensions and random averages, in Proceedings of the 15th annual conference on Computational Learning Theory COLT02, Jyrki Kivinen and Robert H. Sloan(Eds.), Lecture Notes in Computer Sciences 2375, Springer, 14-28, 2002.

⦁ S. Mendelson, Geometric parameters of kernel machines, in Proceedings of the 15th annual conference on Computational Learning Theory COLT02, Jyrki Kivinen and Robert H. Sloan(Eds.), Lecture Notes in Computer Sciences 2375, Springer, 29-43, 2002.

⦁ P.L. Bartlett, O. Bousquet, S. Mendelson, Localized Rademacher Averages, in Proceedings of the 15th annual conference on Computational Learning Theory COLT02, Jyrki Kivinen and Robert H. Sloan(Eds.), Lecture Notes in Computer Sciences 2375, Springer, 44-58, 2002.

⦁ S. Mendelson, P. Philips, Random subclass bounds, Proceedings of the 16th annual conference on Learning Theory COLT03, Bernhard Scholkopf and Manfred Warmuth (Eds.), Lecture Notes in Computer Sciences 2777, Springer, 329-343, 2003.

⦁ P.L. Bartlett, S. Mendelson, P. Philips, Local complexities for empirical minimization, Proceedings of the 17th annual conference on Learning Theory COLT04, John Shawe-Taylor, Yoram Singer (Eds.), Lecture Notes in Computer Sciences 3120, Springer, 270-284, 2004.

⦁ S. Mendelson, A. Pajor, Approximation with random vectors, Proceedings of the 18th annual conference on Learning Theory COLT05, Peter Auer, Ron Meir (Eds.), Lecture Notes in Computer Sciences 3559, Springer, 429-433, 2005.

⦁ S. Mendelson, On the limitations of embedding methods, Proceedings of the 18th annual conference on Learning Theory COLT05, Peter Auer, Ron Meir (Eds.), Lecture Notes in Computer Sciences 3559, Springer, 353-365, 2005.

⦁ S. Mendelson, Learning without Concentration, Proceedings of the 27th annual conference on Learning Theory COLT14, M.F. Balcan, V. Feldman, C. Szepesvari (Eds.), Journal of Machine Learning Research – Workshop and Conference Proceedings, 35, 25-39, 2014.

Refereed Journal Papers (submitted)

⦁ S. Dirksen, S. Mendelson, Robust one-bit compressed sensing with partial circulant matrices (28 pages).

⦁ S. Mendelson, G. Paouris, Stable recovery and the coordinate small-ball behaviour of random vectors (28 pages).

⦁ G. Lugosi, S. Mendelson, Multivariate mean estimation with direction-dependent accuracy (40 pages).

⦁ S. Dirksen, S. Mendelson, A. Stollenwerk, Sharp estimates on random hyperplane tessellations (25 pages).

⦁ S. Dirksen, S. Mendelson, A. Stollenwerk, Fast metric embedding into the Hamming cube (28 pages).