Vladimir Koltchinskii

Title: Sparse Recovery Problems in Learning Theory


Abstract:

We will consider a problem of learning of a target function based on its noisy observations at random points via penalized empirical risk minimization with convex loss function and convex complexity penalty. Depending on the loss function, this framework includes
various regression problems as well as large margin classification (such as boosting and SVM).

We will be interested in two specific cases. In a more simple case, the target function belongs to the linear span of a very large dictionary of given functions. In a more general case, it belongs to the linear span of a very large number of reproducing kernel Hilbert
spaces (RKHS). This includes several important examples such as aggregation problems for large ensembles of kernel machines
and traditional additive models in Statistics.

In both cases, it is assumed that the target function has a "sparse representation" in the "dictionary" and the goal is to recover the
function with an error that depends on the "sparsity" of the problem (rather than on the size of the dictionary).

We study an approach based on $\ell_1$-type complexity penalization and establish several probabilistic inequalities showing the relationship between the sparsity of the empirical solution and the sparsity of the target function and providing bounds on the excess risk and L2-error that depend on the sparsity of the problem.

(Some parts of this talk are based on a joint work and on discussions with Ming Yuan and with Alexandre Tsybakov).