LIPIcs.APPROX-RANDOM.2023.4.pdf
- Filesize: 0.86 MB
- 21 pages
Document
Experimental Design for Any p-Norm
Authors
Hong Zhou 
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
Conference: International Conference on Randomization and Computation (RANDOM) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-09-04
File
Document Identifiers
Author Details
Acknowledgements
We thank Mohit Singh for bringing the Φ_p objective function to our attention. We also thank anonymous reviewers of an earlier version of this manuscript for helpful suggestions.
Cite As Get BibTex
Lap Chi Lau, Robert Wang, and Hong Zhou. Experimental Design for Any p-Norm. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.4
Abstract
We consider a general p-norm objective for experimental design problems that captures some well-studied objectives (D/A/E-design) as special cases. We prove that a randomized local search approach provides a unified algorithm to solve this problem for all nonnegative integer p. This provides the first approximation algorithm for the general p-norm objective, and a nice interpolation of the best known bounds of the special cases.
Subject Classification
ACM Subject Classification
- Theory of computation → Approximation algorithms analysis
- Theory of computation → Rounding techniques
Keywords
- Approximation Algorithm
- Optimal Experimental Design
- Randomized Local Search
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal discrete optimization for experimental design: a regret minimization approach. Math. Program., 186(1-2, Ser. A):439-478, 2021. URL: https://doi.org/10.1007/s10107-019-01464-2.
-
Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: a review. Statist. Sci., 10(3):273-304, 1995.
- Michal Derezinski, Feynman T. Liang, and Michael W. Mahoney. Bayesian experimental design using regularized determinantal point processes. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 3197-3207. PMLR, 2020. URL: http://proceedings.mlr.press/v108/derezinski20a.html.
- David A. Freedman. On tail probabilities for martingales. Ann. Probability, 3:100-118, 1975. URL: https://doi.org/10.1214/aop/1176996452.
- Lap Chi Lau, Robert Wang, and Hong Zhou. Experimental design for any p-norm. CoRR, abs/2305.01942, 2020. URL: https://arxiv.org/abs/2305.01942.
- Lap Chi Lau and Hong Zhou. A local search framework for experimental design. SIAM J. Comput., 51(4):900-951, 2022. URL: https://doi.org/10.1137/20M1386542.
- Lap Chi Lau and Hong Zhou. A spectral approach to network design. SIAM J. Comput., 51(4):1018-1064, 2022. URL: https://doi.org/10.1137/20M1330762.
-
Elliott H. Lieb and Walter E. Thirring. Inequalities for the moments of the eigenvalues of the Schrödinger Hamiltonian and their relation to Sobolev inequalities, pages 269-304. Princeton University Press, 1976.
-
Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat, and Weijun Xie. Combinatorial algorithms for optimal design. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2210-2258, Phoenix, USA, 25-28 June 2019. PMLR.
-
Zelda Mariet and Suvrit Sra. Elementary symmetric polynomials for optimal experimental design. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, pages 2136-2145, Red Hook, NY, USA, 2017. Curran Associates Inc.
-
Aleksandar Nikolov, Mohit Singh, and Uthaipon Tao Tantipongpipat. Proportional volume sampling and approximation algorithms for A-optimal design. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 1369-1386, Philadelphia, PA, USA, 2019. Society for Industrial and Applied Mathematics.
- Jack Sherman and Winifred J. Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Statistics, 21:124-127, 1950. URL: https://doi.org/10.1214/aoms/1177729893.
-
Mohit Singh and Weijun Xie. Approximate positive correlated distributions and approximation algorithms for D-optimal design. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 2240-2255, USA, 2018. Society for Industrial and Applied Mathematics.
- Uthaipon Tantipongpipat. λ-regularized A-optimal design and its approximation by λ-regularized proportional volume sampling. CoRR, abs/2006.11182, 2020. URL: https://arxiv.org/abs/2006.11182.
- Joel A. Tropp. Freedman’s inequality for matrix martingales. Electron. Commun. Probab., 16:262-270, 2011. URL: https://doi.org/10.1214/ECP.v16-1624.
-
Richard L. Wheeden and Antoni Zygmund. Measure and integral. Pure and Applied Mathematics (Boca Raton). CRC Press, Boca Raton, FL, second edition, 2015. An introduction to real analysis.