Elementary Symmetric Polynomials for Optimal Experimental Design

Zelda E. Mariet, Suvrit Sra

Introduction

In Optimal Experimental Design (OED), researchers face a fundamental challenge: how to select a subset of $k$ experiments from $n$ possibilities to estimate a hidden parameter $ heta$ with the highest possible precision. Precision is typically measured by the inverse of the variance-covariance matrix. Because matrices cannot be strictly ordered, scalar "optimality criteria" are used to rank different experimental designs.

Historically, the two most popular criteria have been treated as separate islands:

  1. A-optimality (Trace): Minimizes the average variance. It is intuitive but can be overly sensitive to outliers.
  2. D-optimality (Determinant): Minimizes the volume of the confidence ellipsoid. It is robust but can sometimes ignore important statistical nuances.

This paper introduces ESP-design, a unified framework that uses elementary symmetric polynomials (ESPs) to bridge the gap between A-optimal and D-optimal designs. By providing a "graded interpolation" between these extremes, the authors offer a tunable approach to experiment selection backed by strong theoretical guarantees and efficient algorithms.

The ESP-Design Framework

The authors propose using Elementary Symmetric Polynomials of the eigenvalues of the covariance matrix to evaluate designs.

They define the ESP-design objective as $f_\ell(S) = \frac{1}{\ell} \log E_\ell((X_S^\top X_S)^{-1})$, where $E_\ell$ is the $\ell$-th elementary symmetric polynomial.

  • When $\ell=1$, the model recovers A-optimality.
  • When $\ell=m$ (the dimension of the parameter), the model recovers D-optimality.
  • Intermediate values of $\ell$ provide a spectrum of designs that capture "partial volumes" of the confidence ellipsoid.

Geometrically, ESPs represent the sum of the volumes of all $\ell$-dimensional slices of the confidence ellipsoid, giving the parameter $\ell$ a clear, interpretable meaning.

Optimization Strategies

Selecting the best $k$ experiments is a notoriously hard combinatorial problem. To tackle this, the authors provide two distinct optimization paths:

  1. Convex Relaxation: The authors prove that the objective function is geodesically log-convex on the manifold of positive definite matrices. This is a significant theoretical contribution to matrix theory, allowing for efficient continuous optimization via projected gradient descent.
  2. Greedy Removal: They introduce an algorithm that starts with a full set of experiments and greedily removes the least useful ones, proving that this approach maintains a strong multiplicative approximation guarantee.

Key Results and Insights

The framework was evaluated on synthetic multivariate Gaussian data and the real-world Concrete Compressive Strength dataset from the UCI repository.

The Sparsity vs. Error Trade-off

A fascinating insight from the paper is the trade-off between predictive error and design sparsity. Moving toward D-optimality (higher $\ell$) tends to produce "sparser" designs—meaning the design relies on fewer unique types of experiments. Conversely, leaning toward A-optimality (lower $\ell$) yields lower predictive error (Mean Squared Error).

Trade-off between MSE and Sparsity across different $\ell$ values.

By varying $\ell$, practitioners can smoothly tune their experimental design to prioritize either minimal error or maximal sparsity depending on their specific domain constraints.

Performance of Greedy Pruning

While greedy addition is standard in many machine learning tasks, this paper demonstrates that greedy removal is remarkably effective for OED.

Runtime comparison of the Greedy algorithm versus exchange methods.

The greedy algorithm performed just as well as the "gold standard" Fedorov exchange algorithm but ran in a fraction of the time. As shown in the runtime table above, for a budget of $k=200$, the greedy approach completed in roughly 52 seconds ($5.2 \times 10^1$), compared to 4,700 seconds ($4.7 \times 10^3$) for the Fedorov exchange method.

Limitations and Future Work

While ESP-design offers a powerful new paradigm, some challenges remain:

  • The Dual Problem: For D-optimality, the dual problem is the well-known "Minimum Volume Covering Ellipsoid." The authors derive a dual for ESP-design, but it involves a function that currently lacks a closed-form solution for intermediate values of $\ell$. Finding this closed form could unlock even faster optimization techniques.
  • Computational Complexity: Although the greedy algorithm is significantly faster than exchange methods, its $O(m^2 n^3)$ scaling might still be prohibitive for extremely large-scale "Big Data" settings.

Overall, ESP-design successfully unifies A- and D-optimality, providing both theoretical depth and practical tunability for modern experimental design.

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 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 algorithm. 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 E. 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},
}

Loading related content...

Figure