Abstract: We show that a modified Empirical process converges to the limiting Gaussian process whenever the limit is continuous. The modification depends on the properties of the limit via...
Subspaces and orthogonal decompositions generated by bounded orthogonal systems, Positivity (2008)
Olivier Guédon, Shahar Mendelson, Alain Pajor
We investigate properties of subspaces of L2 spanned by subsets of a finite orthonormal system bounded in the L ∞ norm. We first prove that there exists an arbitrarily large subset of this...
A subgaussian embedding theorem (2008)
Shahar Mendelson, Nicole Tomczak-jaegermann
We prove a subgaussian extension of a Gaussian result on embedding subsets of a Euclidean space into normed spaces. Using the concentration of a random subgaussian vector around its mean we obtain an...
Reconstruction and subgaussian operators in Asymptotic Geometric Analysis, Geom (2008)
Shahar Mendelson, Alain Pajor, Nicole Tomczak-jaegermann
We present a randomized method to approximate any vector v from some set T ⊂ R n. The data one is given is the set T, vectors (Xi) k i=1 of R n and k scalar products (〈Xi, v〉) k i=1, where (Xi)...
Geometric parameters in Learning Theory Contents (2008)
2 Glivenko-Cantelli classes and Learnability 7 2.1 The classical approach........................ 7
Obtaining fast error rates in nonconvex situations (2008)
We show that under mild assumptions on the learning problem, one can obtain a fast error rate for every reasonable fixed target function even if the base class is not convex. To that end, we show...
Analyse fonctionnelle/Functional Analysis Reconstruction and subgaussian processes (2008)
Shahar Mendelson, Alain Pajor, Nicole Tomczak-jaegermann
Abstract. This Note presents a randomized method to approximate any vector v from some set T ⊂ R n. The data one is given is the set T, and k scalar products (〈Xi, v〉) k i=1, where (Xi) k i=1...
Entropy, Combinatorial Dimensions and Random Averages (2008)
Shahar Mendelson, Roman Vershynin
Abstract. In this article we introduce a new combinatorial parameter which generalizes the VC dimension and the fat-shattering dimension, and extends beyond the function-class setup. Using this...
Peter Bartlett, Evarist Giné, Vladimir Koltchinskii, Gábor Lugosi, Shahar Mendelson, Vitali Milman, ...
Berkeley) Acknowledgements. The Mathematical Foundations of Learning Theory is supported by the “Ministerio de Ciencia y Tecnología ” (ref. BFM2002-11039-E).
LIPSCHITZ REPRESENTATIONS OF SUBSETS OF THE CUBE (2008)
(Communicated by N. Tomczak-Jaegermann) Abstract. We show that for any class of uniformly bounded functions H with a reasonable combinatorial dimension, the vast majority of small subsets of the...
A few notes on Statistical Learning Theory Contents (2008)
2 Glivenko-Cantelli Classes 5
Embeddings with a lipschitz function (2008)
We investigate a new notion of embedding of subsets of {−1, 1} n in a given normed space, in a way which preserves the structure of the given set as a class of functions on {1,..., n}. This notion...
Majorizing measures and proportional subsets of bounded orthonormal systems (2008)
Guedon, Olivier, Mendelson, Shahar, Pajor, Alain, Tomczak-Jaegermann, Nicole
In this article we prove that for any orthonormal system $(\vphi_j)_{j=1}^n \subset L_2$ that is bounded in $L_{\infty}$, and any $1 < k
Regularization in Kernel Learning (2008)
Shahar Mendelson, Joseph Neeman
Under mild assumptions on the kernel, we obtain the best known error rates in a regularized learning scenario taking place in the corresponding reproducing kernel Hilbert space. The main novelty in...
Noise Tolerant Learnability via the Dual Learning Problem (2007)
Shai Fine, Ran Gilad-bachrach, Shahar Mendelson, Naftali Tishby
. Much of the research in machine learning and neural computation assumes that the teacher gives the correct answers to the learning algorithm. However, in many cases this assumption is doubtful,...
Statistical Suciency for Classes in Empirical (2007)
Spaces Shahar Mendelson, Shahar Mendelson, Naftali Tishby
We explore the notion of " sucient linear statistics for a class of real valued functions. We show that for function classes with a polynomial rate of the Parametric Pollard dimension one can nd...
Scott Axelrod, Shai Fine, Ran Gilad-bachrach, Shahar Mendelson, Naftali Tishby
A fundamental problem in learning theory is bounding the information gained by an example about the unknown target concept. This problem is most critical in the context of active learning, when the...
Tishby: Statistical Suciency for classes in empirical L 2 spaces (2007)
Shahar Mendelson, Naftali Tishby
We explore the notion of " sucient linear statistics for a class of real valued functions. We show that for function classes with a polynomial rate of the Parametric Pollard dimension one...
Peter Bartlett, Shahar Mendelson
Abstract. In this article we investigate the behaviour of the global and local Rademacher averages. We present new error bounds which are based on the localized averages and indicate how...
Manuscript number: 1963 A new on-line learning model (2007)
In this paper we introduce a new supervised learning model which is a non-homogeneous Markov process and investigate its properties. We are interested in conditions which ensure that the process...
On the geometry of Glivenko{Cantelli classes (2007)
We explore the geometric structure of sets of functions which satisfy the law of large numbers uniformly. Such classes are called Uniform Glivenko{Cantelli (GC) classes. We focus on the structure of...
Shie Mannor, Ron Meir, Shahar Mendelson
Boosting algorithms have been shown to perform well on many realworld problems, although they sometimes tend to overfit in noisy situations. While excellent finite sample bounds are known, it has not...
On the Importance of Small Coordinate Projections (2007)
Shahar Mendelson, Petra Philips
It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm choses its hypotheses is \small" in the sense that the Rademacher...
Agnostic Learning Nonconvex Function Classes (2007)
Shahar Mendelson And, Shahar Mendelson, Robert C. Williamson
We consider the sample complexity of agnostic learning with respect to squared loss. It is known that if the function class F used for learning is convex then one can obtain better sample complexity...
Bartlett, Peter L., Mendelson, Shahar
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Aggregation versus Empirical Risk Minimization (2007)
Guillaume Lecué, Shahar Mendelson
Given a finite set F of estimators, the problem of aggregation is to construct a new estimator that has a risk as close as possible to the risk of the best estimator in F. It was conjectured that...
Discrepancy, Chaining and Subgaussian Processes (2007)
We show that a typical coordinate projection of a subgaussian empirical process satisfies that inf (εi) supf∈F | �k i=1 εif(Xi) | is asymptotically smaller than the expectation over signs (εi)...
Empirical Processes �theory (2007)
Let F be a class of functions on a probability space (Ω, µ) and let X1,..., Xk be independent random variables distributed according to µ. We establish an upper bound that holds with high...
Modified empirical CLT's under only pre-Gaussian conditions (2006)
We show that a modified Empirical process converges to the limiting Gaussian process whenever the limit is continuous. The modification depends on the properties of the limit via Talagrand's...
On singular values of matrices with independent rows (2006)
Mendelson, Shahar, Pajor, Alain
We present deviation inequalities of random operators of the form . We use these inequalities to estimate the singular values of random matrices with independent rows (without assuming that the...
Uniform uncertainty principle for Bernoulli and subgaussian ensembles (2006)
Mendelson, Shahar, Pajor, Alain, Tomczak-Jaegermann, Nicole
We present a simple solution to a question posed by Candes, Romberg and Tao on the uniform uncertainty principle for Bernoulli random matrices. More precisely, we show that a rectangular k*n random...
1 Relating Empirical and Real Structures: Additive and Multiplicative Results (2006)
Peter L. Bartlett, Shahar Mendelson
The key issue investigated in Vladimir Koltchinskii’s paper is the behavior of an empirical minimizer ˆ f ∈ F, that is a function f in F with minimal sample average, Pnf = 1 n� f(Xi), n i=1...
On weakly bounded empirical processes (2005)
Let $F$ be a class of functions on a probability space $(\Omega,\mu)$ and let $X_1,...,X_k$ be independent random variables distributed according to $\mu$. We establish high probability tail...
Local Rademacher complexities (2005)
Bartlett, Peter L., Bousquet, Olivier, Mendelson, Shahar
We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical...
Local Rademacher complexities (2005)
Bartlett, Peter L., Bousquet, Olivier, Mendelson, Shahar
We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical...
Reconstruction and subgaussian operators (2005)
Mendelson, Shahar, Pajor, Alain, Tomczak-Jaegermann, Nicole
We present a randomized method to approximate any vector $v$ from some set $T \subset \R^n$. The data one is given is the set $T$, and $k$ scalar products $(\inr{X_i,v})_{i=1}^k$, where...
A probabilistic approach to the geometry of the \ell_p^n-ball (2005)
Barthe, Franck, Guedon, Olivier, Mendelson, Shahar, Naor, Assaf
This article investigates, by probabilistic methods, various geometric questions on B_p^n, the unit ball of \ell_p^n. We propose realizations in terms of independent random variables of several...
A probabilistic approach to the geometry of the ℓpn-ball (2005)
Barthe, Franck, Guédon, Olivier, Mendelson, Shahar, Naor, Assaf
This article investigates, by probabilistic methods, various geometric questions on Bpn, the unit ball of ℓpn. We propose realizations in terms of independent random variables of several...
Optimal Sample-Based Estimates of the Expectation of the Empirical Minimizer (2005)
Peter L. Bartlett, Shahar Mendelson, Petra Philips
We study sample-based estimates of the expectation of the function produced by the empirical minimization algorithm. We investigate the extent to which one can estimate the rate of convergence of the...
On the limitations of embedding methods (2005)
Abstract. We show that for any class of functions H which has a reasonable combinatorial dimension, the vast majority of small subsets of the combinatorial cube can not be represented as a Lipschitz...
A probabilistic approach to the geometry of the ℓ n p ball, Annals of Probability (2005)
Franck Barthe, Olivier Guédon, Shahar Mendelson, Assaf Naor
This article investigates, by probabilistic methods, various geometric questions on. We propose realizations in terms of independent random vari-Bn p, the unit ball of ℓnp ables of several...
A probabilistic approach to the geometry of the ℓ n p ball, Annals of Probability (2005)
Franck Barthe, Olivier Guédon, Shahar Mendelson, Assaf Naor
This article investigates, by probabilistic methods, various geometric questions on B n p, the unit ball of ℓ n p. We propose realizations in terms of independent random variables of several...
Optimal Sample-Based Estimates of the (2005)
Expectation Of The, Peter L. Bartlett, Shahar Mendelson, Petra Philips
We study sample-based estimates of the expectation of the function produced by the empirical minimization algorithm. We investigate the extent to which one can estimate the rate of convergence of the...
Optimal sample-based estimates of the expectation of the empirical minimizer (2005)
Peter L. Bartlett, Shahar Mendelson, Petra Philips
We study sample-based estimates of the expectation of the function produced by the empirical minimization algorithm. We investigate the extent to which one can estimate the rate of convergence of the...
Complexity measures of sign matrices (2005)
Nati Linial, Shahar Mendelson, Gideon Schechtman
z Department of Mathematics,
Lipschitz representations of subsets of the cube (2005)
We show that for any class of uniformly bounded functions H with a reasonable combinatorial dimension, the vast majority of small subsets of the n-dimensional combinatorial cube can not be...
The shattering dimension of sets of linear functionals (2004)
Mendelson, Shahar, Schechtman, Gideon
We evaluate the shattering dimension of various classes of linear functionals on various symmetric convex sets. The proofs here relay mostly on methods from the local theory of normed spaces and...
The shattering dimension of sets of linear functionals (2004)
Mendelson, Shahar, Schechtman, Gideon
We evaluate the shattering dimension of various classes of linear functionals on various symmetric convex sets. The proofs here relay mostly on methods from the local theory of normed spaces and...
Local complexities for empirical risk minimization (2004)
Bartlett, Peter L, Mendelson, Shahar, Philips, Petra
We present sharp bounds on the risk of the empirical minimization algorithm under mild assumptions on the class. We introduce the notion of isomorphic coordinate projections and show that this leads...
Peter L. Bartlett, Olivier Bousquet, Shahar Mendelson
We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical...
Local Complexities for Empirical Risk Minimization (2004)
Peter L. Bartlett, Shahar Mendelson, Petra Philips
Abstract. We present sharp bounds on the risk of the empirical minimization algorithm under mild assumptions on the class. We introduce the notion of isomorphic coordinate projections and show that...
On the importance of ”small” coordinate projections (2004)
Shahar Mendelson, Petra Philips
It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm chooses its hypotheses is “small ” in the sense that the Rademacher...
A note on the richness of convex hulls of VC classes (2003)
Lugosi, Gàbor; Pompeu Fabra University, Spain; Lugosi@upf.es, Mendelson, Shahar; The Australian National University, Australia; Shahar.mendelson@anu.edu.au, Koltchinskii, Vladimir; The University Of New Mexico, USA; Vlad@math.unm.edu
We prove the existence of a class A of subsets of Rd of VC dimension 1 such that the symmetric convex hull F of the class of characteristic functions of sets in A is rich in the following sense. For...
The shattering dimension of sets of linear functionals (2003)
Shahar Mendelson, Gideon Schechtman
We evaluate the shattering dimension of various classes of linear functionals on various symmetric convex sets. The proofs here relay mostly on methods from the Local Theory of Normed Spaces and...
A note on the richness of convex hulls of VC classes (2003)
Gábor Lugosi, Shahar Mendelson, Vladimir Koltchinskii
We prove the existence of a class A of subsets of Rd of vc dimension 1 such that the symmetric convex hull F of the class of characteristic functions of sets in A is rich in the following sense. For...
Peter L. Bartlett, Shahar Mendelson
We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either...
On the Performance of Kernel Classes (2003)
Shahar Mendelson, Thore Graepel, Ralf Herbrich
We present sharp bounds on the localized Rademacher averages of the unit ball in a reproducing kernel Hilbert space in terms of the eigenvalues of the integral operator associated with the kernel. We...
Peter Bartlett Division, Peter L. Bartlett, Shahar Mendelson
We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either...
Peter L. Bartlett, Shahar Mendelson
We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either...
COMMUNICATIONS in PROBABILITY A NOTE ON THE RICHNESS OF CONVEX HULLS OF VC CLASSES (2003)
Gábor Lugosi, Shahar Mendelson, Vladimir Koltchinskii
We prove the existence of a class A of subsets of Rd of vc dimension 1 such that the symmetric convex hull F of the class of characteristic functions of sets in A is rich in the following sense. For...
Peter L. Bartlett, Shahar Mendelson
We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either...
Geometric Parameters in Learning Theory (2003)
this article would encourage mathematicians to investigate these seemingly "applied" problems, which are, in fact, linked to interesting theoretical questions
A few notes on Statistical Learning Theory (2003)
this article is on the theoretical side and not on the applicative one; hence, we shall not present examples which may be interesting from the practical point of view but have little theoretical...
On the performance of kernel classes (2003)
Shahar Mendelson, Thore Graepel, Ralf Herbrich
We present sharp bounds on the localized Rademacher averages of the unit ball in a reproducing kernel Hilbert space in terms of the eigenvalues of the integral operator associated with the kernel. We...
Shahar Mendelson, Petra Philips
Abstract. It has been recently shown that sharp generalization bounds can be obtained when the function class from which the algorithm chooses its hypotheses is “small ” in the sense that the...
Local Rademacher complexities (2002)
Peter L. Bartlett, Olivier Bousquet, Shahar Mendelson
We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical...
Rademacher and Gaussian complexities: risk bounds and structural results (2002)
Peter L. Bartlett, Shahar Mendelson, M. Long
We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and gaussian complexities. In a decision theoretic setting, we prove general risk...
Local Rademacher complexities (2002)
Peter L. Bartlett, Olivier Bousquet, Shahar Mendelson
We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical...
Rademacher and Gaussian complexities: risk bounds and structural results (2002)
Peter L. Bartlett, Shahar Mendelson, M. Long
We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and gaussian complexities. In a decision theoretic setting, we prove general risk...
Learnability in Hilbert spaces with Reproducing Kernels (2002)
We explore the question of learnability of classes of functions contained in a Hilbert space which has a reproducing kernel. We show that if the evaluation functionals are uniformly bounded and if...
Rademacher averages and phase transitions in Glivenko-Cantelli classes (2002)
We introduce a new parameter which may replace the fat-shattering dimension. Using this parameter we are able to provide improved complexity estimates for the agnostic learning problem with respect...
Rademacher and Gaussian complexities: risk bounds and structural results (2002)
Peter L. Bartlett, Shahar Mendelson
Abstract. We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and gaussian complexities. In a decision theoretic setting, we prove...
Risk Bounds And, Peter L. Bartlett, Shahar Mendelson, M. Long
We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities. In a decision theoretic setting, we prove general risk...
Risk Bounds And, Peter L. Bartlett, Shahar Mendelson, M. Long
We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities. In a decision theoretic setting, we prove general risk...
Local Rademacher complexities (2002)
L. Bartlett, Olivier Bousquet, Shahar Mendelson
We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical...
Local Rademacher Complexities (2002)
Peter L. Bartlett, Olivier Bousquet, Shahar Mendelson
We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical...
Local Rademacher complexities (2002)
Peter L. Bartlett, Olivier Bousquet, Shahar Mendelson
Abstract. We investigate the behaviour of global and local Rademacher averages. We present new error bounds which are based on the local averages and indicate how data-dependent local averages can be...
On the size of convex hulls of small sets (2001)
We investigate two dierent notions of \size " which appear naturally in Statistical Learning Theory. We present quantitative estimates on the fat-shattering dimension and on the covering...
On the size of convex hulls of small sets (2001)
We investigate two dierent notions of \size " which appear naturally in Statistical Learning Theory. We present quantitative estimates on the fatshattering dimension and on the covering...
Goemetric methods in the analysis of Glivenko-Cantelli classes (2001)
Abstract. We use geometric methods to investigate several fundamental problems in machine learning. We present a new bound on the Lp covering numbers of Glivenko-Cantelli classes for 1 p 1 in terms...
Learning relatively small classes (2001)
Abstract. We study the sample complexity of proper and improper learning problems with respect to dierent Lq loss functions. We improve the known estimates for classes which have relatively small...
Statistical Sufficiency for Classes in Empirical L 2 Spaces (2000)
Shahar Mendelson, Naftali Tishby
We explore the notion of epsilon sufficient linear statistics for a class of real valued functions. We show that for function classes with a polynomial rate of the Parametric Pollard dimension one...
Geometric Parameters of Kernel Machines
We investigate the fat-shattering dimension and the localized Rademacher averages of kernel machines and their connection to the eigenvalues associated with the kernel. 1
The Shattering Dimension of Sets of Linear Functionals
Shahar Mendelson, Gideon Schechtman
We evaluate the shattering dimension of various classes of linear functionals on various symmetric convex sets. This is applied in two di#erent directions. The first is the determination of whether...
Peter L. Bartlett, Shahar Mendelson
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]