Learning Low-complexity Models from the Data – Geometry, Optimization, and Applications

Today we are collecting a massive amount of data in forms of images and videos, that we want to learn from the data themselves to extract useful information and to make predictions. The data are high-dimensional, but often possess certain low-dimensional structures (e.g., sparsity). However, learning these low-complexity models often results in highly nonconvex optimization problems, where in the past our understandings of solving them were very limited. In the worst case, optimizing a nonconvex problem is NP-hard.

In this talk, we present global nonconvex optimization theory and guaranteed algorithms for efficient learning of low-complexity models from high-dimensional data. For several important problems in imaging science (i.e., sparse blind deconvolution) and representation learning (i.e., convolutional/overcomplete dictionary learning), we show that the underlying symmetry and low-complexity structures avoid the worst-case scenarios, leading to benign global geometric properties of the nonconvex optimization landscapes. In particular, for sparse blind deconvolution that aims to jointly learn the underlying physical model and sparse signals from convolutions, the geometric intuitions lead to efficient nonconvex algorithms, with linear convergence to target solutions. Moreover, we extended our geometric analysis to convolutional dictionary learning based on its similarity with overcomplete dictionary learning, providing the first global algorithmic guarantees for both problems. Finally, we demonstrate our methods on several important applications in scientific discovery, and draw connections to learning deep neural networks.

This talk is mainly based on one paper appeared in NeurIPS’19 (spotlight), and two papers accepted by ICLR’20 (one oral).