UTOPEST · Unified Theory of Efficient Optimization and Estimation

The goal of this project is to make progress toward a unified theory of efficientoptimization and estimation. In many computing applications, especially machine learning,optimization and estimation problems play an increasingly important role. For that reason, a largeresearch effort is devoted to developing and understanding the limitations of efficient algorithmsfor these problems. For many of these problems, achieving the best known provable guaranteesrequired the use of algorithms that are tailored to problem specifics. In recent years, the PI’sresearch with collaborators has shown that for many optimization problems, the conceptuallysimple sum-of-squares meta-algorithm, despite not being tailored to problem specifics, can matchand often significantly outperform previous efficient algorithms in terms of provable guarantees.This project aims to better understand the capabilities and limitations of this meta-algorithm,especially for estimation problems, which have only recently begun to be studied in this light.In this way, the project will establish new algorithmic guarantees for basic optimization andestimation problems even in the face of non-convexity and adversarial outliers. In the same way,the project will shed light on the limitations of efficient algorithms for basic average-case problemslike planted clique and stochastic block models.The project also aims to transfer the obtained theoretical insights into practical algorithmsbuilding on recent works by the PI and collaborators. Toward this goal the project will developnew algorithms with close to linear running times that match the guarantees of the best knownpolynomial-time algorithms. In order to assess their practicality, the project will perform systematicempirical evaluations of these algorithms.