CAREER: AF: Models and Algorithms for Beyond Worst-case Analysis of Learning

在正确性、收敛率、鲁棒性、安全性、隐私性等属性上建立理论保证是现代机器学习（ML）的核心挑战。这样的保证对于机器学习系统的部署至关重要，尤其是在敏感领域。虽然传统的算法设计力求获得所有实例（最坏情况）的保证，但由于潜在问题的内在复杂性，这在ML中通常是不可能的。这使得研究人员的思考超越了最坏情况分析，并研究了可以获得正式保证的模型。该项目旨在通过考虑新的问题领域，如跨任务的知识转移和利用在线学习模型中输入的预测，为这一领域做出根本性的贡献。该项目还包括帮助促进算法设计和机器学习的本科生和研究生研究的活动，还包括针对当地高中和社区大学学生的外展活动。该项目将开发超越最坏情况分析的新模型，研究重点如下：(a)设计算法，用于发现数据中潜在结构的问题，重点关注知识转移和数据子集中发现结构等主题，(b)利用在线算法中的“建议”或对未来的预测，并发展一种理论，说明什么样的建议可以改善绩效指标，如竞争比和遗憾，以及(c)发展对非线性图嵌入的理论理解。类似于对随机漫步和谱嵌入的广泛理论研究。这些重点都有一个共同的主题，即需要开发新的分析和建模框架，同时受到具体学习应用程序的推动。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Establishing theoretical guarantees on properties like correctness, convergence rate, robustness, security, privacy, etc. is a central challenge in modern machine learning (ML). Such guarantees are essential for the deployment of machine-learning systems, especially in sensitive domains. While traditional algorithm design strives to obtain guarantees for all instances (worst-case), this is often impossible in ML due to the intrinsic complexity of the underlying problems. This has led researchers to think beyond worst-case analysis, and to study models under which formal guarantees can be obtained. The project aims to make fundamental contributions to this area by considering new problem domains such as the transfer of knowledge across tasks and the leveraging of predictions about inputs in online models of learning. The project also includes activities to help promote undergraduate and graduate research in algorithms design and ML. It also includes outreach activities aimed at students from the local high schools and community colleges.The project will develop new models for going beyond worst-case analysis, with the research having the following main thrusts: (a) designing algorithms for problems of finding latent structure in data, with a focus on topics such as knowledge transfer and finding structure in subsets of data, (b) leveraging "advice" or predictions about the future in online algorithms and developing a theory about what kinds of advice lead to improved performance metrics such as competitive ratio and regret, and (c) developing a theoretical understanding of non-linear graph embeddings, akin to the extensive theoretical work on random walks and spectral embedding. These thrusts share the common theme of requiring the development of new analytical and modeling frameworks, while being motivated by concrete learning applications.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.