MSPA-MCS: Sparsity in High-Dimensional Learning Problems

该项目的目标是在学习理论的高维问题中发展稀疏性的数学理论。这些问题通常被表述为带有凸损失函数和凸复杂性惩罚的惩罚经验风险最小化问题，它们特别包括各种版本的回归和模式分类问题。有各种各样的方法来解决它们，包括近年来开发的许多流行的机器学习算法（核机器、boosting等）。所讨论的问题通常是非常高维甚至无限维的，并且稀疏解的存在对方法的推广性能具有至关重要的影响，特别是，当训练数据量与问题的维数相比很小时。基于最近在理解稀疏性在计算谐波分析，信号处理和非参数统计中的作用方面取得的一些进展，以及利用高维概率和渐近几何分析方法在学习理论中推广边界的新数学方法，研究人员研究了几类基本的学习算法，包括回归和分类中的最佳聚集，集成学习和核机器学习，以表明在这种类型的经验风险最小化问题中，经验解的稀疏性可以明确地与真实解的稀疏性相关。研究人员还研究稀疏性对泛化性能的影响，并开发适应未知稀疏性问题的学习算法。该项目是纯数学，统计学和计算机科学（机器学习）几个重要研究领域的交叉点。证明关于稀疏性的严格数学结果是一个非常具有挑战性的问题，解决这个问题需要开发新的数学工具，这些工具可能会对这些领域的其他发展产生影响。另一方面，稀疏性的作用在脑成像和生物信息学等领域的机器学习算法的最重要应用中至关重要。例如，在脑成像中，开发功能磁共振成像中激活模式的自动分类方法和自动选择与特定分类问题相关的特征的方法非常重要。考虑到高维对象的稀疏程度的分类方法直接关系到这样的应用。该项目还包括一些活动，增加其对研究生和本科生教育的影响，并促进高维统计学习理论方法的应用。

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 regressionand 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, Statisticsand 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.