Avishek Ghosh

Provable and efficient Alternating Minimization for (structured) Non-convex optimization

Alternating Minimization (AM) is a classical algorithm for non-convex objectives. In this talk, we study statistical properties, including convergence guarantee and speed, of AM for several structured non-convex problems such as max-affine regression, mixture of linear regression etc. The first half of the talk concerns with max-affine regression, which generalizes several well known non-convex problems like phase-retrieval and is an approximation to the non-parametric convex regression problem. We apply AM for max-affine regression and show that the curse of dimensionality can be lifted by obtaining parametric statistical rates. The second part of the talk tackles the `open problem' regarding the convergence speed of AM. For a special case of mixture of 2 linear regression, we discuss the double exponential convergence speed of AM. We conclude with several open problems. We also discuss some results on agnostic learning of mixtures of regressions.