Algorithms for Budget-Constrained D-Optimal Design

D-optimal experimental design is a classical statistical problem in which one chooses a collection of data vectors, from some available large pool, in order to maximize a measure of predictive quality. In the classical formulation, the only constraint is on the cardinality of the collection, that is, the number of vectors chosen. We study a more general budget-constrained variant in which vectors have heterogeneous costs, and develop four new algorithms (two deterministic and two randomized) with approximation guarantees. Our methods handle heterogeneous costs using a novel exchange rule that interchanges packs of data vectors whose total costs are similar (up to some controlled amount of rounding error). The algorithms outperform the only existing method for this problem from both theoretical and empirical standpoints. Funding: The first and third authors gratefully acknowledge support from the National Science Foundation (NSF) Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI-2112828]. The second author gratefully acknowledges support from the NSF Division of Computing and Communication Foundations [Grant CCF-2246417] and Office of Naval Research [Grant N00014-24-1-2066].