AF: Small: Online Algorithms and Approximation Methods in Learning

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

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.