MSPA-MCS: Sparsity in High-Dimensional Learning Problems

MSPA-MCS：高维学习问题的稀疏性

• 批准号: 0624841
• 负责人: Vladimir Koltchinskii
• 金额: $ 30.06万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-10-15 至 2010-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0624841&HistoricalAwards=false
• 关键词: MSPA; MCS; Sparsity; Dimensional; Learning

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.

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