Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.14957 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909617921982464 |
|---|---|
| author | Li, Yongchun |
| author_facet | Li, Yongchun |
| contents | We study the Regularized A-optimal Design (RAOD) problem, which selects a subset of $k$ experiments to minimize the inverse of the Fisher information matrix, regularized with a scaled identity matrix. RAOD has broad applications in Bayesian experimental design, sensor placement, and cold-start recommendation. We prove its NP-hardness via a reduction from the independent set problem. By leveraging convex envelope techniques, we propose a new convex integer programming formulation for RAOD, whose continuous relaxation dominates those of existing formulations. More importantly, we demonstrate that our continuous relaxation achieves bounded optimality gaps for all $k$, whereas previous relaxations may suffer from unbounded gaps. This new formulation enables the development of an exact cutting-plane algorithm with superior efficiency, especially in high-dimensional and small-$k$ scenarios. We also investigate scalable forward and backward greedy algorithms for solving RAOD, each with provable performance guarantees for different $k$ ranges. Finally, our numerical results on synthetic and real data demonstrate the efficacy of the proposed exact and approximation algorithms. We further showcase the practical effectiveness of RAOD by applying it to a real-world user cold-start recommendation problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_14957 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strong Formulations and Algorithms for Regularized A-optimal Design Li, Yongchun Optimization and Control We study the Regularized A-optimal Design (RAOD) problem, which selects a subset of $k$ experiments to minimize the inverse of the Fisher information matrix, regularized with a scaled identity matrix. RAOD has broad applications in Bayesian experimental design, sensor placement, and cold-start recommendation. We prove its NP-hardness via a reduction from the independent set problem. By leveraging convex envelope techniques, we propose a new convex integer programming formulation for RAOD, whose continuous relaxation dominates those of existing formulations. More importantly, we demonstrate that our continuous relaxation achieves bounded optimality gaps for all $k$, whereas previous relaxations may suffer from unbounded gaps. This new formulation enables the development of an exact cutting-plane algorithm with superior efficiency, especially in high-dimensional and small-$k$ scenarios. We also investigate scalable forward and backward greedy algorithms for solving RAOD, each with provable performance guarantees for different $k$ ranges. Finally, our numerical results on synthetic and real data demonstrate the efficacy of the proposed exact and approximation algorithms. We further showcase the practical effectiveness of RAOD by applying it to a real-world user cold-start recommendation problem. |
| title | Strong Formulations and Algorithms for Regularized A-optimal Design |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2505.14957 |