Theory Lunch Seminar

  • Gates Hillman Centers
  • ASA Conference Room 6115
  • Ph.D. Student
  • Machine Learning Department
  • Carnegie Mellon University

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


For More Information, Please Contact: