This project focused on developing new theories and techniques for reasoning about algorithmic problems that arise in machine learning, and optimization though a beyond worst-case analysis lens. Traditional paradigms in theoretical computer science have focused on worst-case analysis of algorithms which can be pessimistic. Real-world instances of computational problems are unlikely to be in degenerate or pathological configurations. On the research side, the project led to the development of new models of real-world instances, new techniques to prove guarantees, and efficient algorithms that were also robust to different modeling errors and corruptions. These research outcomes were complemented with new courses and educational material on related topics, and the training of several PhD students and undergraduate students on beyond worst-case paradigms.  

On the research front, one of the highlights was the development of new smoothed analysis techniques for many basic problems in machine learning and high-dimensional data analysis that are computationally intractable in the worst-case. In smoothed analysis, the algorithm is analyzed on a small random perturbation of an arbitrary input. Smoothed analysis guarantees show that the bad instances for the algorithm are isolated – qualitatively they represent the strongest possible algorithmic guarantees in the absence of worst-case guarantees. In a sequence of works that also involved PhD students (funded by the project) and undergraduate students at Northwestern, we developed new techniques that are broadly useful for proving smoothed analysis guarantees (Bhaskara et al. FOCS 2019, Math Programming 2021, and STOC 2024). We developed new probabilistic ideas for establishing lower bounds on the least singular value of random matrices with limited randomness. Least singular value bounds often involve showing strong anti-concentration inequalities that are intricate and much less understood compared to concentration (or large deviation) bounds. These techniques allowed us to resolve open questions in smoothed analysis for well-studied problems like learning hidden Markov models, tensor decompositions, subspace clustering, learning mixtures of non-spherical decompositions and several other problems. Moreover, we used these ideas to also develop new that gave the first polynomial time algorithmic guarantees (through smoothed analysis) for learning depth-2 neural networks with general ReLU activation (Awasthi et al., NeurIPS 2021). Finally, in a sequence of recent projects (Johnston, Lovitz and Vijayaraghavan QIP 2022, FOCS 2023), we studied a broad class of algorithmic problems in algebraic geometry that capture important problems in quantum information and on low-rank tensor decompositions. While problem is known to be NP-hard in the worst-case, we showed that we could design efficient algorithms with smoothed analysis guarantees.

Another highlight of this project was the development of more realistic average-case models called semi-random models for common machine learning tasks. Semi-random models provide a framework to reason about robustness of algorithms to modeling errors by incorporating both adversarial and random choices in instance generation. In two different works (Awasthi and Vijayaraghvan FOCS 2018, NeurIPS 2018) we studied new semi-random models for two important problems in unsupervised learning: dictionary learning, and clustering mixtures of Gaussians, and designed efficient algorithms with robustness guarantees for these problems. This focus on robustness also led to the development of machine learning algorithms with provable guarantees in the presence of adversarial attacks and perturbations.  Adversarial robustness of machine learning methods is important from a reliability and security standpoint. In a sequence of works (Awasthi et al. COLT 2020, NeurIPS 2020, COLT 2021) we designed algorithms for basic machine learning primitives like finding low-dimensional data representations that are robust to adversarial perturbations. We gave polynomial time algorithms with approximately optimal guarantees, and also gave similar guarantees for downstream tasks. This approach was also used to get better adversarial robustness for deep neural networks in image classification. 

The project involved overall 6 PhD students (3 of whom graduated) and 3 undergraduate students (all went on to do PhDs). There were several graduate courses on related topics that were developed, along with a new undergraduate course on mathematical foundations that covered linear algebra, probability and optimization foundations for computer science. Finally, the PI was also involved in outreach activities in the broader Chicago area that targeted K-12 students, particularly from underrepresented minorities.

The project also supported organized activities and workshops for the broader scientific community. One of these workshops was the Junior Theorists Workshop, which provided opportunities for some of the best junior researchers (PhD students and postdoctoral researchers, who are not in faculty positions) to showcase their research. The research that came out of the project has also been published in several conferences and journals for dissemination, and in publicly accessible repositories like ArXiv. The PI also authored a publicly-accessible survey on smoothed analysis for tensor decompositions that also became a chapter in the book on Beyond the Worst-Case Analysis of Algorithms.  Finally, videos of many of the seminar talks and workshop talks have been made available publicly.

Last Modified: 07/02/2024
Modified by: Aravindan Vijayaraghavan