Given $n$ independent replicates of a jointly distributed pair $(X,Y) \in {\cal R}^d \times {\cal R}$, we wish to select from a fixed sequence of model classes ${\cal F}_1, {\cal F}_2, \ldots$ a deterministic prediction rule $f: {\cal R}^d \to {\cal R}$ whose risk is small. We investigate the...

This paper addresses the problem of reconstructing a low-rank signal matrix observed with additive Gaussian noise. We first establish that, under mild assumptions, one can restrict attention to orthogonally equivariant reconstruction methods, which act only on the singular values of the observed...

We obtain Vapnik-Chervonenkis type upper bounds for the uniform deviation of probabilities from their expectations. The bounds sharpen previously known probability inequalities.

Given an i.i.d. sample drawn from a density "f" on the real line, the problem of testing whether "f" is in a given class of densities is considered. Testing procedures constructed on the basis of minimizing the "L"₁-distance between a kernel density estimate and any density in the hypothesized...

We present a new general concentration-of-measure inequality and illustrate its power by applications in random combinatorics. The results find direct applications in some problems of learning theory.