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: https://arxiv.org/abs/1711.05174