CIF: Small: Learning and estimation with rough non-convex objectives: Fundamental limits and efficient algorithms

Stanford University, Stanford CA

Investigators

Abstract

A large number of problems in signal processing, statistics and machine learning require minimizing a cost function with many unknown variables. In a general setting, this task is computationally hard, unless the cost function has the mathematical property called convexity, a case that has attracted a large amount of work over the last fifty years. On the other hand, modern applications often rely on the more complex non-convex formulations, which are optimized using simple algorithms that are not necessarily optimal. This project explores the hypothesis that, for a broad class of non-convex cost functions, one can find optimal solutions in the typical instances of these functions, even if the worst case might be impossible to optimize. The outcomes will have impacts on all scientific fields and real-world problems that feature non-convex cost functions. This project aims at studying probabilistic models of cost functions that are of `mean-field' type, namely they do not have a latent low-dimensional structure. This setting is quite common in high-dimensional statistics and machine learning: Each degree of freedom is equally likely to interact (or not) with every other one. The conjectured connection between the geometry of sublevel sets and tractability was recently established in special cases by developing new algorithms that achieve the desired optimization goal. These algorithms are based on message passing ideas and free energy approximations. This project develops these new methods in a broader domain and investigates precise conditions for their applicability. Furthermore, it develops potential alternatives and improvements. 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.