Removal of Redundant Candidate Points for the Exact D-Optimal Design Problem
Radoslav Harman, Samuel Rosa · 2025
Read Removal of Redundant Candidate Points for the Exact D-Optimal Design Problem by Radoslav Harman, Samuel Rosa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00719.txt.
Introduction
Radoslav Harman and one co-author, Samuel Rosa, speed up exact D-optimal design, a statistical problem of choosing experimental runs to maximize information. Approximate designs can be computed efficiently with convex methods, but exact finite-sample designs require hard integer optimization on large candidate sets.
Harman and Rosa derive necessary conditions, based on approximate designs, that every support point of an exact D-optimal design must satisfy. These conditions rapidly eliminate redundant candidates without losing optimality, cutting memory and runtime. They also prove that for large samples, exact design supports lie inside a typically small maximum-variance set. Benchmarks with candidate sets up to one hundred million points shrink by several orders of magnitude, enabling exact solutions with guarantees.
Catalog record
| CREATOR | Radoslav Harman, Samuel Rosa |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-00719
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Removal of Redundant Candidate Points for the Exact D-Optimal Design Problem Radoslav Harman, Samuel Rosa Abstract One of the most common problems in statistical experimentation is computing D-optimal designs on large finite candidate sets. While optimal approximate (i.e., infinite-sample) designs can be efficiently computed using convex methods, constructing optimal exact (i.e., finite-sample) designs is a substantially more difficult integer-optimization problem. In this paper, we propose necessary conditions, based on approximate designs, that must be satisfied by any support point of a D-optimal exact design. These conditions enable rapid elimination of redundant candidate points without loss of optimality, thereby reducing memory requirements and runtime of subsequent exact design algorithms. In addition, we prove that for sufficiently large sample sizes, the supports of D-optimal exact designs are contained in a typically small maximum-variance set. We demonstrate the approach on randomly generated benchmark models with candidate sets up to 100 million points, and on commonly used constrained mixture models with up to one million points. The proposed approach reduces the initial candidate sets by several orders of magnitude, thereby making it possible to compute exact D-optimal designs for these problems via mixed-integer second-order cone programming, which provides optimality guarantees. MSC Classification]62K05 keywords Statistical Experiments; D-optimal design; Approximate design; Exact design; Candidate-set reduction; Mixed-integer second-order cone programming pacs [ 1 Introduction 1.1 Optimal design of experiments An experiment is commonly understood as a set of n trials, each yielding an observation. The field of optimal experimental design seeks to select these trials so as to maximize information obtained from the experiment as a whole (see, e.g., the monographs Fedorov 1972 , Pázman 1986 , Pukelsheim 2006 , Atkinson et al. 2007 , Goos and Jones 2011 , Pronzato and Pázman 2013 , and López-Fidalgo 2023 ). A central component of any experiment is a set \mathcal{X} that represents the conditions under which individual trials may be conducted. We call the elements of \mathcal{X} candidate points or candidates. Often, they correspond to all permissible combinations of the levels of several controllable factors. In this paper, we assume that \mathcal{X} contains a finite number N\geq 2 of candidates: \mathcal{X}=\{\mathbf{x}_{1},\ldots,\mathbf{x}_{N}\} . While a finite \mathcal{X} is usually the only realistic or meaningful choice, its size N can be very large. We denote the required number of trials by n and formally represent a size- n design by a nonnegative vector \mathbf{w}=(w_{1},\ldots,w_{N})^{\top} , such that \sum_{i=1}^{N}w_{i}=1 and nw_{1},\ldots,nw_{N} are nonnegative integers. Here, n\mathbf{w} is the vector of replications, i.e., its components are the numbers of trials performed at \mathbf{x}_{1},\ldots,\mathbf{x}_{N} . The set of all such size- n designs \mathbf{w} is the set \Xi_{n} of lattice points of the probability simplex in \mathbb{R}^{N} , consisting of \binom{N+n-1}{N-1} vectors whose components are integer multiples of 1/n . In the field of optimal experimental design, it is also common to consider the full probability simplex in \mathbb{R}^{N} , which we denote by \Xi_{\infty} . A vector \mathbf{w}\in\Xi_{\infty} represents the proportions of trials at \mathbf{x}_{1},\ldots,\mathbf{x}_{N} , without any integrality constraint. Since the real-valued proportions specified by \mathbf{w} can, in general, be realized only as the number of trials tends to infinity, such designs are referred to as approximate. In contrast, the size- n designs in \Xi_{n} are called exact. Under our formalization we have \Xi_{n}\subseteq\Xi_{\infty} ; therefore, if we use the term design without any qualifier, we cover both approximate and exact designs. An important set associated with a design \mathbf{w} is its support \mathcal{S}(\mathbf{w}):=\{i\in[N]:w_{i}>0\}, where [N]:=\{1,\ldots,N\} . Each \ell\in\mathcal{S}(\mathbf{w}) is called a support index of \mathbf{w} . The quality of a design \mathbf{w} , with respect to its ability to provide precise estimates of the parameters of an underlying statistical model, is measured via its information matrix. The most common form of the information matrix is \mathbf{M}(\mathbf{w}):=\sum_{i=1}^{N}w_{i}\mathbf{f}_{i}\mathbf{f}_{i}^{\top}, where \mathbf{f}_{1},\ldots,\mathbf{f}_{N}\in\mathbb{R}^{m} are known vectors. This matrix typically represents a normalized version of the Fisher information matrix for the m -dimensional model parameter, and its additive form arises from the assumption that the observations are independent across trials. The vectors \mathbf{f}_{1},\ldots,\mathbf{f}_{N} are based on the model; for instance, for the most common case, i.e., the linear regression with uncorrelated and homoscedastic observations y having expectation \mathbf{f}^{\top}(\mathbf{x})\boldsymbol{\theta} for any \mathbf{x}\in\mathcal{X} , we simply have \mathbf{f}_{i}=\mathbf{f}(\mathbf{x}_{i}) for all i\in[N] . However, the same form of the information matrix also appears in the locally optimal design approach for nonlinear models (e.g., Chapter 3 of López-Fidalgo 2023 ) and for generalized linear models (e.g., Khuri et al. 2006 ). Also, it covers heteroscedastic models via standard transformations (see, e.g., Remark 2.1 in López-Fidalgo 2023 ). In summary, the considered form of the information matrix is relevant for the majority of real applications. Throughout, we restrict attention to settings in which \mathbf{M}(\mathbf{w}) is nonsingular for some \mathbf{w}\in\Xi_{n} . This assumption ensures that there exists at least one experimental design for which the model parameters are estimable. It also implies n\geq m . Any design with a nonsingular information matrix is called nonsingular. For simplicity, we confine our attention to the nontrivial case m\geq 2 . To compare designs based on the size of their information matrices, we consider the criterion \Phi of D -optimality, defined by \Phi(\mathbf{M}):=\left(\det(\mathbf{M})\right)^{1/m} for all positive semidefinite m\times m matrices \mathbf{M} . For the exact design problem, D -optimality was introduced by Wald in Wald 1943 and has since served as a cornerstone of optimal design applications, due to its unique statistical and analytic properties (e.g., Section 6.2 of Pukelsheim 2006 or Chapter 11 of Atkinson et al. 2007 ). Statistically, maximizing \Phi is equivalent to minimizing the generalized variance of the parameter estimates, or the volume of the confidence ellipsoid for the unknown model parameter. Analytically, \Phi is continuous, concave, and positively homogeneous on the set of all positive semidefinite matrices, as well as differentiable and strictly log-concave on the set of all positive definite m\times m matrices. An approximate design \mathbf{w}^{*}_{\infty} is D -optimal if it maximizes \Phi(\mathbf{M}(\mathbf{w}_{\infty})) over all \mathbf{w}_{\infty}\in\Xi_{\infty} ; the set of all such designs is denoted by \Xi^{*}_{\infty} . Likewise, an exact design \mathbf{w}_{n}^{*}\in\Xi_{n} is a D -optimal size- n design if it maximizes \Phi(\mathbf{M}(\mathbf{w}_{n})) over all \mathbf{w}_{n}\in\Xi_{n} . We denote the set of D -optimal size- n designs by \Xi^{*}_{n} . Since D -optimality is the only criterion considered in this paper, we omit the prefix “ D -” and simply refer to an optimal design. Our assumptions ensure the existence of at least one optimal approximate design and at least one optimal size- n design, and that the information matrices of these optimal designs are nonsingular. However, there may be infinitely many optimal approximate designs (see, e.g., Harman et al. 2024 ) and multiple optimal size- n designs. The strict log-concavity of \Phi on the set of positive definite matrices implies that all optimal approximate designs \mathbf{w}^{*}_{\infty} have the same information matrix, which we denote \mathbf{M}_{*} . In contrast, different optimal size- n designs may have distinct information matrices. For any nonsingular design \mathbf{w} we define v_{i}(\mathbf{w}):=\mathbf{f}_{i}^{\top}\mathbf{M}^{-1}(\mathbf{w})\mathbf{f}_{i},\>i\in[N]. Viewed as a function of i , v_{i}(\mathbf{w}) is sometimes called the variance function, because for a nonsingular size- n design \mathbf{w}_{n} , the quantity (\sigma^{2}/n)\cdot v_{i}(\mathbf{w}_{n}) equals the variance of the best linear unbiased estimator \widehat{\mathbf{f}_{i}^{\top}\boldsymbol{\theta}} of the mean