Elementary Symmetric Polynomials for Optimal Experimental Design

Zelda Mariet, Suvrit Sra

TL;DR

This paper introduces ESP-design, a new framework for Optimal Experimental Design that uses elementary symmetric polynomials to bridge the gap between the two most popular design standards: A-optimality and D-optimality. By proving that these polynomials possess a rare mathematical property called "geodesic log-convexity," the authors develop efficient algorithms that offer a tunable "middle ground" for researchers needing to balance average variance against global volume constraints.

What Problem Does This Paper Address?

In the world of statistics and machine learning, Optimal Experimental Design (OED) is about being smart with your budget. If you have $n$ possible experiments but can only afford to run $k$ of them, which ones will help you estimate a hidden parameter $\theta$ most accurately?

Traditionally, researchers choose between two extremes:

  1. A-optimal design: Minimizes the average variance (the trace of the inverse covariance matrix). It’s great for precision but can be sensitive to outliers.
  2. D-optimal design: Minimizes the volume of the uncertainty ellipsoid (the determinant). It’s more robust but doesn't focus on individual parameter precision.

The problem is that there has been no formal way to navigate the space between these two. You were either summing eigenvalues (A-opt) or multiplying them (D-opt). This paper fills that "mathematical void" by providing a graded interpolation between the two.

Methods

The authors leverage Elementary Symmetric Polynomials (ESPs). If you think of eigenvalues as the "dimensions" of your uncertainty, the trace is the sum of these dimensions, and the determinant is the product of all of them. An ESP of order $\ell$ is the sum of all possible products of $\ell$ eigenvalues.

  • When $\ell = 1$, you get A-optimality.
  • When $\ell = m$ (the total number of parameters), you get D-optimality.
  • For any $\ell$ in between, you get a "partial volume" measure.

The Technical Breakthrough: The authors prove that ESPs are geodesically log-convex on the manifold of positive definite matrices. This is a significant theoretical result because it guarantees that a "continuous relaxation" of the problem (where you allow fractional experiments) is a convex optimization problem that can be solved efficiently using projected gradient descent.

They propose two main algorithmic paths:

  1. Convex Relaxation + Sampling: Solve the smooth version of the problem and then "round" the results to pick $k$ discrete experiments.
  2. Greedy Removal: Start with all possible experiments and greedily discard the least useful ones one by one. They provide a provable approximation guarantee for this approach, extending previous work that only applied to the trace.

Datasets

The paper evaluates the algorithms on:

  • Synthetic Data: Multivariate Gaussian distributions with varying "sparsity" (how connected the parameters are) to test how the algorithms handle different noise structures.
  • Real-World Data: The Concrete Compressive Strength dataset (from the UCI repository). This contains 1030 potential experiments involving 8 physical parameters (like cement, water, and age) used to predict concrete strength.

Key Insights and Ideas

  • The "Middle Ground" is Tunable: By changing the order $\ell$ of the polynomial, a researcher can decide exactly how much they care about "average" vs "volume" error.
  • Geometric Interpolation: Geometrically, ESP-design seeks an ellipsoid with the smallest average volume for $\ell$-dimensional slices. This provides a much more nuanced geometric control than traditional methods.
  • Greedy is Good: One of the "curious phenomena" noted is that the greedy removal algorithm performs exceptionally well—often matching the quality of the gold-standard Fedorov exchange algorithm but running in a fraction of the time.
  • Sparsity vs. Accuracy: On real data, the authors found that increasing $\ell$ (moving toward D-optimality) actually increased the sparsity of the design matrix. This suggests that ESP-design can be used to "tune" side effects, like identifying which experimental parameters are actually unnecessary.

Key Results

  • Efficiency: The greedy algorithm ($O(m^2 n^3)$) is significantly faster than the traditional Fedorov exchange method ($O(n^3)$ or more per iteration) while producing designs of nearly identical quality.
  • Approximation Guarantees: The authors provide the first theoretical bounds for greedy ESP-design, showing that the error is bounded by a factor related to the number of experiments and parameters.
  • Performance: In synthetic tests, as the budget $k$ increases, the simple sampling method becomes highly competitive with more complex greedy approaches, suggesting that for large-scale problems, the convex relaxation is extremely powerful.

Limitations and Future Work

  • The Dual Problem: For D-optimality, there is a famous "dual" problem called the Minimum Volume Covering Ellipsoid. While the authors derived a dual formulation for ESP-design, it involves a complex function $a(H)$ that currently lacks a closed-form solution for general $\ell$. Finding this would unlock deeper geometric insights.
  • Computational Cost: While faster than some alternatives, the greedy algorithm still scales with $n^3$. For truly massive datasets (millions of potential experiments), even more efficient stochastic or distributed versions would be needed.
  • Non-linear settings: This work focuses on the linear dependency setting. Extending these ESP-based models to non-linear experimental design remains an open challenge.

Summary updated

Abstract

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.
BibTeX
@inproceedings{mariet2017elementary,
  author = {Zelda Mariet and Suvrit Sra},
  title = {{Elementary Symmetric Polynomials for Optimal Experimental Design}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=HkEx7KZ_-r},
}
Figure