Nonconvex Optimization for High Dimensional Learning: From Phase Retrieval to Submodular Maximization

Many problems of contemporary interest in signal processing and machine learning involve highly non- convex optimization problems. While nonconvex optimization problems are known to be intractable in general, simple local search heuristics such as (stochastic) gradient descent are often surprisingly effective at finding global optima on real or randomly generated data. In this talk I will discuss some results explaining the success of these heuristics focusing on two problems.

The first problem, concerns the recovery of a structured signal from under-sampled quadratic measurements. I will show that projected gradient descent on a natural nonconvex formulation finds globally optimal solutions with a near minimal number of samples, breaking through local sample complexity barriers that have emerged in recent literature. I will also discuss how these new mathematical developments pave the way for a new generation of data-driven phaseless imaging systems that can utilize prior information to significantly reduce acquisition time and enhance image reconstruction, enabling nano-scale imaging at unprecedented speeds and resolutions. The second problem, focuses on submodular optimization problems that emerge in a variety of areas in machine learning, including utility functions in active learning and sensing, matrix approximations and network inference. I will show how to cast this highly discrete optimization problem as a continuous nonconvex optimization problem. I will then discuss new local search heuristics based on this continuous formulation that lead to fast algorithms for submodular maximization. Despite the apparent lack of convexity in such functionals I will show that these new local search heuristics lead to approximation guarantees on par (or sometimes better) than state of the art. This talk is based on joint work with collaborators that will be properly introduced during the talk.

Download Slides

Dr. Mahdi Soltanolkotabi

University of Southern California

Date: June 19, 2017 at 1:30 PM

Location: 3002 EB2

Interdisciplinary Distinguished Seminar Series

The Department of Electrical and Computer Engineering hosts a regularly scheduled seminar series with preeminent and leading reseachers in the US and the world, to help promote North Carolina as a center of innovation and knowledge and to ensure safeguarding its place of leading research.