Elementary Symmetric Polynomials for Optimal Experimental Design
We revisit the classical problem of optimal experimental design (OED) under a new mathematical model grounded in a geometric motivation. Specifically, we introduce models based on elementary symmetric polynomials; these polynomials capture "partial volumes" and offer a graded interpolation between the widely used A-optimal design and D-optimal design models, obtaining each of them as special cases. We analyze properties of our models, and derive both greedy and convex-relaxation algorithms for computing the associated designs. Our analysis establishes approximation guarantees on these algorithms, while our empirical results substantiate our claims and demonstrate a curious phenomenon concerning our greedy method. Finally, as a byproduct, we obtain new results on the theory of elementary symmetric polynomials that may be of independent interest.
The authors present a novel objective for experiment design that interpolates A- and D-optimality. They present a convex relaxation for the problem which includes novel results on elementary symmetric polynomials, and an efficient greedy algorithm based on the convex relaxation with performance guarantees for the original task. They present results on synthetic data, and present results on a concrete compressive strength task.
		  I am not an expert in this area but I believe I understand the contribution and that it is significant.
		  The paper is extremely well-presented, with minor points of clarification needed that I have identified below.
		  
		  The main suggestion I have is that the authors more explicitly explain the benefits of the new method in terms of the properties of solutions that interpolate between A and D -- In 6.2, the authors present the ability to use their method to get a spars(er) design matrix as an important feature. This should be stated at the beginning of the paper if it is a true aim (and not simply an interesting side-effect) and the authors should review other methods for obtaining a sparse design matrix. (I presume that there are e.g. L1 penalized methods that can achieve sparsity in this area but I do not know.) In general, a more explicit statement of the practical benefits of the contributions in the paper would be useful for the reader.
		  
		  l21. is a bit confusing regarding use of "vector" -- \epsilon_i is a scalar, yes?
		  l22. Gauss-Markov doesn't require \epsilon_i be Gaussian but it *does* require homoskedasticity. Clarify.
		  l45. "deeply study" - studied
		  l77. I think (2.1) is confusing with v as vectors unless the product is element-wise. Is this intended?
		  l107. "Clearly..." - Make a more precise statement. Is an obvious special case hard? What problem of known hardness reduces to this problem? If you mean "no method for finding an exact solution is known" or "we do not believe an efficient exact solution is possible" then say that.