A note on the richness of convex hulls of VC classes.
On the optimality of the empirical risk minimization procedure for the convex aggregation problem
We study the performance of (ERM), with respect to the quadratic risk, in the context of , in which one wants to construct a procedure whose risk is as close as possible to the best function in the convex hull of an arbitrary finite class . We show that ERM performed in the convex hull of is an optimal aggregation procedure for the convex aggregation problem. We also show that if this procedure is used for the problem of model selection aggregation, in which one wants to mimic the performance...
On the singular values of random matrices
We present an approach that allows one to bound the largest and smallest singular values of an random matrix with iid rows, distributed according to a measure on that is supported in a relatively small ball and linear functionals are uniformly bounded in for some , in a quantitative (non-asymptotic) fashion. Among the outcomes of this approach are optimal estimates of not only in the case of the above mentioned measure, but also when the measure is log-concave or when it a product measure...
On the Optimality of Sample-Based Estimates of the Expectation of the Empirical Minimizer
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 empirical minimizer in a data dependent manner. We establish three main results. First, we provide an algorithm that upper bounds the expectation of the empirical minimizer in a completely data-dependent manner. This bound is based on a structural result due to Bartlett and Mendelson, which relates...
Page 1