Algorithms for Budget-Constrained D-Optimal Design
成果类型：
Article; Early Access
署名作者：
Wang, Jiaqi; Xie, Weijun; Ryzhov, Ilya O.
署名单位：
University System of Georgia; Georgia Institute of Technology; University System of Maryland; University of Maryland College Park
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2024.0467
发表日期：
2025
关键词：
摘要：
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.