The goal of the project is to develop a mathematical theory of sparsity in high-dimensional problems of learning theory. These problems are often formulated as penalized empirical risk minimization with convex loss function and convex complexity penalty and they include, in particular, various versions of regression and pattern classification problems. There is a variety of approaches to their solution including many popular machine learning algorithms developed in the recent years (kernel machines, boosting, etc). The problems in question are most often very high-dimensional or even infinite dimensional and the existence of sparse solutions has crucial impact on the generalization performance of the methods, especially, when the amount of training data is small comparing with the dimensionality of the problem. Building upon some recent progress in understanding of the role of sparsity in Computational Harmonic Analysis, Signal Processing and Nonparametric Statistics as well as upon new mathematical approaches to generalization bounds in learning theory utilizing methods of High Dimensional Probability and Asymptotic Geometric Analysis, the investigators study several basic classes of learning algorithms, including optimal aggregation in regression and classification, ensemble learning and kernel machines learning, in order to show that in this type of empirical risk minimization problems the sparsity of the empirical solution can be explicitly related to the sparsity of the true solution. The investigators also study the impact of sparsity on generalization performance and develop learning algorithms that are adaptive to unknown sparsity of the problem.
The project is at the very intersection of several important lines of research in Pure Mathematics, Statistics and Computer Science (Machine Learning). Proving rigorous mathematical results about sparsity is a very challenging problem and solving this problem would require the development of new mathematical tools that are likely to have impact on other developments in these areas. On the other hand, the role of sparsity is crucial in most important applications of machine learning algorithms in such areas as Brain Imaging and Bioinformatics. For instance, in Brain Imaging, it is of great importance to develop methods of automatic classification of activation patterns in fMRI and of automatic selection of features relevant for a particular classification problem. The classification methods taking into account the degree of sparsity of high dimensional objects are directly related to such applications. The project also includes a number of activities that increase its impact on graduate and undergraduate education and facilitate applications of the methods of high-dimensional statistical learning theory.
