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

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.