权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Efficient Algorithms for Nonconvex Regression

AF：小：非凸回归的高效算法

基本信息

批准号：
1909204
负责人：
Adam Klivans
金额：
$ 39.98万
依托单位：
University of Texas at Austin
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2024-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909204&HistoricalAwards=false
关键词：
AF Small Efficient Algorithms Nonconvex

项目摘要

The problem of fitting a line to noisy data, also known as regression, is a classic and fundamental tool from statistics. Fast, provably efficient algorithms for solving regression are at the heart of traditional systems for artificial intelligence and data science. As modeling problems have become more complex, however, linear regression often fails to capture the high-dimensional relationships that arise in modern tasks. As such, researchers rely on sophisticated generalizations of regression, but the computational complexity of solving such problems is typically unknown (or thought to be intractable in general). The primary research goal of this project is to develop provably efficient algorithms for solving non-convex and nonlinear variants of classical linear regression and give applications to related problems in machine learning. Since tools for machine learning are now ubiquitous in science, these algorithms will have broad use across many fields. Also, these algorithms will be benchmarked experimentally against commonly used heuristics, giving rise to a wealth of projects appropriate for students at all levels.The project centers around two open problems. First, is it possible to develop provably efficient algorithms for learning generalized linear models? In this scenario, the goal is to fit a (mildly) nonlinear function to data with respect to square loss, where the nonlinearity arises from a monotone, increasing function applied to the underlying linear form. As it turns out, algorithms for learning generalized linear models give rise to solutions for learning the dependency graph of a graphical model. This means that rich information about the features of a data set can be extracted by fitting a nonlinear function to the conditional distributions. The second problem is performing linear regression but in the presence of adversarially corrupted training sets. For example, if 90% of a data set is fit well by a linear function, it is often useful to remove the remaining 10% as outliers. Finding these outliers, however, is a difficult combinatorial problem. This project explores connections between these robust linear-regression problems and a new subfield of theoretical computer science that applies high-dimensional convex relaxations.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

将一条线拟合到噪声数据的问题，也称为回归，是统计学中的一个经典和基本工具。解决回归问题的快速、可证明有效的算法是人工智能和数据科学传统系统的核心。然而，随着建模问题变得越来越复杂，线性回归往往无法捕捉现代任务中出现的高维关系。因此，研究人员依赖于复杂的回归概括，但解决这些问题的计算复杂性通常是未知的（或被认为是棘手的）。该项目的主要研究目标是开发可证明有效的算法来解决经典线性回归的非凸和非线性变量，并将其应用于机器学习中的相关问题。由于机器学习工具现在在科学中无处不在，这些算法将在许多领域中广泛使用。此外，这些算法将通过实验与常用的算法进行基准测试，从而产生大量适合各个级别学生的项目。该项目围绕两个开放问题展开。首先，是否有可能开发出可证明有效的学习广义线性模型的算法？在这种情况下，目标是将一个（轻度）非线性函数与平方损失相关的数据拟合，其中非线性来自应用于基础线性形式的单调递增函数。事实证明，学习广义线性模型的算法会产生学习图形模型的依赖图的解决方案。这意味着通过将非线性函数拟合到条件分布，可以提取关于数据集特征的丰富信息。第二个问题是执行线性回归，但存在逆向损坏的训练集。例如，如果90%的数据集与线性函数拟合良好，则通常可以将剩余的10%作为离群值删除。然而，找到这些离群值是一个困难的组合问题。该项目探索了这些稳健的线性回归问题与应用高维凸松弛的理论计算机科学新分支之间的联系。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。