AF: Small: Online Algorithms and Approximation Methods in Learning

现代机器学习应用旨在准确、快速和大规模地解决困难的计算问题。这导致了重大的算法挑战，这些挑战由于对噪声的鲁棒性和数据的分布式性质等实际考虑而变得更加复杂。该项目的目标是对有效学习的可能性形成正式的理解，并开发新的算法见解。在该项目中开发的技术将导致近似算法，优化，次线性算法和计算复杂性的进步。该项目包括一项开发课程的计划，这些课程将教授本科生和研究生正式推理机器学习系统，并了解它们的力量和局限性。这些课程将帮助培训下一代劳动力，并将在犹他州大学提供，大部分材料都是公开的。该项目旨在解决机器学习推理中的两个核心问题。第一个问题与学习问题的计算难度有关。对于稀疏编码和学习低深度神经网络等问题，所有已知的算法都需要强的结构假设，以获得学习保证。该项目将研究（针对这些问题和其他问题的）方法，使人们能够削弱这些假设，同时获得较弱但实际相关的保证。第二个问题与在线到达模型的学习有关，其动机是推荐系统和信号处理。在此，许多已知的理论结果在数据存在噪声或仅部分观测时就达不到要求，该项目将为这些设置开发正式的模型和算法结果。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern machine-learning applications aim to solve difficult computational problems accurately, quickly and at scale. This has led to significant algorithmic challenges that are compounded by practical considerations like robustness to noise and the distributed nature of data. The goal of the project is to develop a formal understanding of when efficient learning is possible, and to develop novel algorithmic insights. The techniques developed in the project will lead to progress in approximation algorithms, optimization, sublinear algorithms, and computational complexity. The project includes a plan to develop courses that teach undergraduate and graduate students to formally reason about machine-learning systems and to understand their power and limitations. The courses will help train the next generation of the workforce, and will be offered at the University of Utah, with much of the material being publicly accessible.The project aims to address two core questions in reasoning about machine learning. The first one is related to the computational hardness of learning problems. For problems such as sparse coding and learning low-depth neural networks, all the known algorithms require strong structural assumptions in order to obtain learning guarantees. The project will study methods (for these and other problems) that enable one to weaken these assumptions, while obtaining weaker yet practically relevant guarantees. The second question is related to learning in online arrival models, motivated by recommender systems and signal processing. Here, many of the known theoretical results fall short when data is noisy or is only partially observed, and the project will develop formal models and algorithmic results for these settings.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.