Theory Lunch Seminar

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

Location:

ASA Conference Room 6115 Gates Hillman Centers

Speaker:

YINING WANG, Ph.D. Student http://yining-wang.com/

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).

Reference

Event Website:

http://www.cs.cmu.edu/~theorylunch/20171122.html

For More Information, Contact:

Keywords:

Seminar Series