Theory Lunch Seminar

Wednesday, November 22, 2017 - 12:00pm to 1:00pm


ASA Conference Room 6115 Gates Hillman Centers


YINING WANG, Ph.D. Student

Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach

In this talk we consider "experimental design" problems, which have wide applications in statistics and machine learning. Mathematically, the problem consists of a class of discrete (combinatorial) optimization problems whose exact solutions are generally NP-hard, but their continuous relaxations are usually computationally tractable. I will discuss connections between this problem and the graph sparsification problem, and how the recently developed tools for one-sided unweighed graph sparsification can be applied to get polynomial-time 1+eps approximations of the discrete optimization problem, with mild additional assumptions on the problem parameters.

Based on joint work with Zeyuan Allen-Zhu (Microsoft Research Redmond), Yuanzhi Li (Princeton University) and Aarti Singh (CMU).


Event Website:

For More Information, Contact:


Seminar Series