Graduate Student, Princeton University
Email
Abstract
Nonnegative polynomials, and applications to learning
The problem of recognizing nonnegativity of a multivariate polynomial has a celebrated history, tracing back to Hilberts 17th problem. In recent years, there has been much renewed interest in the topic because of a multitude of applications in applied and computational mathematics and the observation that one can optimize over an interesting subset of nonnegative polynomials using “sum of squares (SOS) optimization”. In this talk, we give a brief overview of the developments in this field and show how they can be applied to two problems at the interface of machine learning and polynomial optimization. In part (i), we study the problem of learning a monotone polynomial from data. This is motivated by regression problems where the underlying function to be learned is monotone (consider, e.g., the price of a car as a function of its fuel efficiency). In part (ii), we study the problem of optimally decomposing a multivariate polynomials as the difference of two convex polynomials. This is motivated by certain majorization-minimization algorithms used in nonconvex optimization that require such a decomposition.
Bio
Georgina Hall is a sixth-year graduate student and a Gordon Wu fellow in the department of Operations Research and Financial Engineering at Princeton University, under the supervision of Professor Amir Ali Ahmadi. She was the valedictorian of Ecole Centrale, Paris, where she obtained a B.S. and an M.S., in 2011 and 2013 respectively. Her interests lie in convex relaxations of NP-hard problems, particularly those arising in polynomial optimization. She is a recipient of the Princeton University’s Engineering Council Teaching Award, the university-wide Excellence in Teaching Award of the Graduate School, and the Médaille de l’Ecole Centrale from the French Académie des Sciences. Her paper “DC decomposition of nonconvex polynomials using algebraic techniques” is the recent recipient of the 2016 Informs Computing Society Prize for Best Student Paper.