Fall 2021

Optimal Iterative Algorithms for Problems With Random Data

Friday, Aug. 27, 2021 3:15 pm4:15 pm PDT

Add to Calendar


Andrea Montanari (Stanford)



I will consider two families computational problems with different motivation:

(i) Quadratic optimization with non-convex constraints.
(ii) Statistical estimation in low-rank plus noise models.

I will describe the construction of iterative algorithms for each of these classes of problems. Although these constructions appear at first sight somewhat arbitrary, they are in fact highly constrained, which suggest that they correspond to yield optimal iterative algorithms in each of these cases. I will discuss rigorous evidence supporting this belief. I will finally discuss generalizations.