Publications

Reseach Papers

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

• S. Mendelson, l-norm and its application to Learning Theory, Positivity, 5, 177-191, 2001.

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

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

• 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.

• S. Mendelson, Learnability in Hilbert spaces with Reproducing Kernels, Journal of Complexity, 18(1), 152-170, 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, R. Vershynin, Entropy and the combinatorial dimension, Inventiones Mathematicae, 152(1), 37-55, 2003.

• S. Mendelson, A few notes on Statistical Learning Theory, In Advanced Lectures in Machine Learning, (S. Mendelson, A.J. Smola Eds), LNCS 2600, 1-40, Springer 2003.

• S. Mendelson, Estimating 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, G. Schechtman, The shattering dimension of sets of linear functionals, Annals of Probability, 32(3A), 1746-1770, 2004.

• S. Mendelson, Geometric parameters in Learning Theory. GAFA lecture notes, LNM 1850, 193-236, 2004.

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

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

• F. Barthe, O. Guedon, S. Mendelson, A. Naor, A probabilistic approach to the geometry of the \ell_p^n 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.

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

• P.L. Bartlett, O. Bousquet, S. Mendelson, Local Rademacher Complexities, Annals of Statistics, 33(4) 1497-1537, 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.

• 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, High Dimensional Probability, 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, A. Pajor, N. Tomczak-Jaegermann, Reconstruction and subgaussian operators in Asymptotic Geometric Analysis, Geometric and Functional Analysis, 17(4), 1248-1282, 2007.

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

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

• O. Guedon, S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Subspaces and orthogonal decompositions generated by bounded orthogonal systems, Positivity, 11(2), 269-283, 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.

• Y. Gordon, A. Litvak, S. Mendelson, A. Pajor, Gaussian averages of interpolated bodies, Journal of Approximation Theory, 149, 59-73, 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.

• 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.

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

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

• P. Bartlett, S. Mendelson, J. Neeman, \ell_1-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 dIHP, 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 (GAFA Seminar Notes, B. Klartag and E. Milman Eds.), Lecture notes in Mathematics 2116, 395-404, 2014.

• S. Mendelson, Learning without concentration, Journal of the ACM, 62(3), Article No. 21, 1-25, 2015. doi:10.1145/2699439.

• 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, Journal of Theoretical Probability, 29(4), 1644-1660, 2016.

• 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 a general loss function, Probability Theory and Related Fields, 171(1), 459-502, 2018.

• S. Mendelson, Column normalization of a random measurement matrix, Electronic Communications in Probability, 23, article 13, 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), art 42, 2019 (44 pages).

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

• S. Mendelson, On the geometry of random polytopes, Geometric aspects of Functional Analysis, Lecture notes in Mathematics, 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, Communications in Contemporary Mathematics, 22(8) 1950089, 24 pages, 2020.

• G. Lugosi, S. Mendelson, N. Zhivotovskiy, Concentration of the spectral norm and Erdos-Renyi random graphs, Bernoulli, 26(3), 2253-2274, 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 L_p, 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.

• 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.

• S. Mendelson, Column randomization and almost-isometric embeddings, Information and Inference: A journal of the IMA, https://doi.org/10.1093/imaiai/iaab028, 2022.

• D. Bartl, S. Mendelson, On Monte-Carlo methods in convex stochastic optimization, Annals of Applied Probability, 32(4) 3146-3198, 2022.

• D. Bartl, S. Mendelson, Random embeddings with an almost gaussian distortion, Advances in Mathematics, 400, article 108261, 2022.

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

• S. Dirksen, S. Mendelson, A. Stollenwerk, Sharp estimates on random hyperplane tessellations, SIAM Journal on Mathematics of Data Science, 4(4), 1396-1419, 2022.

• S. Dirksen, S. Mendelson, Robust one-bit compressed sensing with partial circulant matrices, Annals of Applied Probability, 33(3), 1874-1903, 2023.

• S. Mendelson, G. Paouris, Stable recovery and the coordinate small-ball behaviour of random vectors, Geometric aspects of Functional Analysis, Lecture notes in Mathematics, Lecture Notes in Math., 2327, Springer, 231–267, 2023. 

• S. Dirksen, S. Mendelson, A. Stollenwerk, Fast metric embedding into the Hamming cube, SIAM Journal on Computing, 53(2), 315-345, 2024.

• D. Bartl, S. Mendelson, Optimal non-gaussian Dvoretzky-Milman embeddings, International Mathematics Research Notices, 10, 8459-8480, 2024.

• G. Lugosi, S. Mendelson, Multivariate mean estimation with direction-dependent accuracy, Journal of the European Mathematical Society, 26(6) 2211-2247, 2024.

• A. S. Bandeira, A. Maillard, S. Mendelson, E. Paquette, Fitting an ellipsoid to a quadratic number of random points, ALEA Lat. Am. J. Probab. Math. Stat. 21(2), 1835–1852, 2024.

• D. Bartl, S. Mendelson,  Empirical approximation of the gaussian distribution in R^d, Advances in Mathematics, Volume 460, 110041, 2025, (30 pages).

• D. Bartl, S. Mendelson, Structure preservation via the Wasserstein distance, Journal of Functional Analysis, 288(7) 2025, article 110810

• P. Abdalla, S. Mendelson, Covariance estimation with direction dependence accuracy, Probability Theory and Related Fields 194, 371–409, 2026.

• D. Bartl, S. Mendelson, A uniform Dvoretzky-Kiefer-Wolfowitz inequality, Probability Theory and Related Fields, 193(1-2), 335-374, 2025.

• D. Bartl, S. Mendelson, Uniform mean estimation via generic chaining, Advances in Mathematics, to appear (20 pages). 

• S. Mendelson, G. Paouris, R. Vershynin, Can you spot a fake?, SIAM Journal on Mathematics of Data Science (SIMODS), to appear (16 pages).

Preprints

• D. Bartl, S. Mendelson, Do we really need the Rademacher complexities?, (35 pages).

•  D. Bartl, S. Mendelson, On the structure of marginals in high dimensions, (30 pages).

Books

• Advanced Lectures in Machine Learning, (S. Mendelson, A.J. Smola Eds), LNCS 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.

Other publications

• S. Mendelson, N. Tishby, Statistical Sufficiency for classes in empirical L2 spaces, Proceedings of the 13th annual conference on Computational Learning Theory COLT00, 81-89, 2000.

• S. Mendelson, Geometric Methods in the Analysis of Glivenko-Cantelli Classes, Proceedings of the 14th annual conference on Computational Learning Theory COLT01, 256-272, 2001.

• S. Mendelson, Learning Relatively Small Classes, Proceedings of the 14th annual conference on Computational Learning Theory COLT01, 273-288, 2001.

• P. L. Bartlett, S. Mendelson, Rademacher and gaussian complexities: risk bounds and structural results, Proceedings of the 14th annual conference on Computational Learning Theory COLT01, 224-240, 2001.

• S. Mendelson, R.C. Williamson, Agnostic learning of non-convex classes of functions, Proceedings of the 15th annual conference on Computational Learning Theory COLT02, 1-13, 2002.

• S. Mendelson, R. Vershynin, Entropy, combinatorial dimensions and random averages, Proceedings of the 15th annual conference on Computational Learning Theory COLT02, 14-28, 2002.

• S. Mendelson, Geometric parameters of kernel machines, Proceedings of the 15th annual conference on Computational Learning Theory COLT02, 29-43, 2002.

• P.L. Bartlett, O. Bousquet, S. Mendelson, Localized Rademacher Averages, Proceedings of the 15th annual conference on Computational Learning Theory COLT02, 44-58, 2002.

• S. Mendelson, P. Philips, Random subclass bounds, Proceedings of the 16th annual conference on Learning Theory COLT03, Lecture Notes in Computer Sciences 2777, Springer, 329-343, 2003.

• P.L. Bartlett, S. Mendelson, P. Philips, Local complexities for empirical risk minimization, Proceedings of the 17th annual conference on Learning Theory COLT04, Lecture Notes in Computer Sciences 3120, Springer, 270-284, 2004.

• S. Mendelson, A. Pajor, Ellipsoid approximation with random vectors, Proceedings of the 18th annual conference on Learning Theory COLT05, 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, 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, Journal of Machine Learning Research – Workshop and Conference Proceedings, 35, 25-39, 2014.

• D. Bartl, S. Mendelson, On a variance dependent Dvoretsky-Kiefer-Wolfowitz inequality, (17 pages).

• G. Lecue, S. Mendelson, Learning subgaussian classes: Upper and minimax bounds,  (37 pages).