Title of Presentation: Random projections in mathematical programming

Abstract:

In the algorithmic trade-off between generality and efficiency, sometimes the only way out is to accept approximate methods. If all else fails, we can always fall back on heuristic methods. But some form of approximation guarantee is usually preferable. In this talk we shall discuss a set of approximating reformulations to various classes of mathematical programming problems involving matrices. Random projections are a dimensionality reduction methodology which projects a set of vectors into a much lower dimensional space, so that the projected vector set is approximately congruent to the original one with high probability. The probability of failure falls exponentially fast as the dimension increases, making this a truly “big data” methodology. We shall show how to apply this methodology to Conic Programming and (bounded) Quadratic Programming, and we shall show applications to Quantile Regression and Error-Correcting Codes.

Bio

Leo Liberti obtained his Ph.D. in Global Optimization at Imperial College London, held a postdoctoral fellowship at Politecnico di Milano, and then moved to Ecole Polytechnique in France, where he became professor and vice-president of his department. After two years as a Research Staff Member at IBM Research in New York, he started serving as Research Director at CNRS and part-time professor at Ecole Polytechnique. His main research interests are mathematical programming with applications to industrial problems, optimization algorithms, and distance geometry. For more information, you can have a look at http://www.lix.polytechnique.fr/~liberti/cv-eng.pdf