# Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach

arXiv: https://arxiv.org/abs/1711.05174 · HTML: https://mlsanity.com/paper/1711.05174/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2017.

## Built on by (most cited first, 19 of 19)

- [Representation-Based Exploration for Language Models: From Test-Time to Post-Training](https://mlsanity.com/paper/2510.11686/) (2025)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Partition-Based Active Learning for Graph Neural Networks](https://mlsanity.com/paper/2201.09391/) (2022)
- [Additive Causal Bandits with Unknown Graph](https://mlsanity.com/paper/2306.07858/) (2023)
- [DAVED: Data Acquisition via Experimental Design for Data Markets](https://mlsanity.com/paper/2403.13893/) (2024)
- [Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning](https://mlsanity.com/paper/2407.06120/) (2024)
- [Near Instance Optimal Model Selection for Pure Exploration Linear Bandits](https://mlsanity.com/paper/2109.05131/) (2021)
- [Reinforcement Learning with Segment Feedback](https://mlsanity.com/paper/2502.01876/) (2025)
- [Robust Offline Active Learning on Graphs](https://mlsanity.com/paper/2408.07941/) (2024)
- [Experimental Design for Any p-Norm](https://mlsanity.com/paper/2305.01942/) (2023)
- [MASS-DPO: Multi-negative Active Sample Selection for Direct Policy Optimization](https://mlsanity.com/paper/2605.10784/) (2026)
- [Experimental Design Using Interlacing Polynomials](https://mlsanity.com/paper/2410.11390/) (2024)
- [Sparse Linear Bandits with Blocking Constraints](https://mlsanity.com/paper/2410.20041/) (2024)
- [Breaking the log(1/Delta2) Barrier: Better Batched Best Arm Identification with Adaptive Grids](https://mlsanity.com/paper/2501.17370/) (2025)
- [Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming](https://mlsanity.com/paper/2509.16915/) (2025)
- [Guiding the Recommender: Information-Aware Auto-Bidding for Content Promotion](https://mlsanity.com/paper/2601.20422/) (2026)
- [The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression](https://mlsanity.com/paper/2607.06642/) (2026)
- [Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms](https://mlsanity.com/paper/2608.14319/) (2026)

## Abstract (arXiv)

The experimental design problem concerns the selection of k points from a potentially large design pool of p-dimensional vectors, so as to maximize the statistical efficiency regressed on the selected k design points. Statistical efficiency is measured by optimality criteria, including A(verage), D(eterminant), T(race), E(igen), V(ariance) and G-optimality. Except for the T-optimality, exact optimization is NP-hard. We propose a polynomial-time regret minimization framework to achieve a (1+varepsilon) approximation with only O(p/varepsilon2) design points, for all the optimality criteria above. In contrast, to the best of our knowledge, before our work, no polynomial-time algorithm achieves (1+varepsilon) approximations for D/E/G-optimality, and the best poly-time algorithm achieving (1+varepsilon)-approximation for A/V-optimality requires k = Omega(p2/varepsilon) design points.