Local algorithms like gradient descent are widely used in non-convex optimization, typically with few guarantees on performance. In this talk we consider the class of problems given by
min_{U,V} f(UV’)
where f is a convex function on the space of matrices. The problem is non-convex, but “only” because we adopt the bi-linear factored representation UV’, with tall matrices U,V.
