Approximation Algorithms for D-optimal Design
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912143949955072 |
|---|---|
| author | Singh, Mohit Xie, Weijun |
| author_facet | Singh, Mohit Xie, Weijun |
| contents | Experimental design is a classical statistics problem and its aim is to estimate an unknown $m$-dimensional vector $β$ from linear measurements where a Gaussian noise is introduced in each measurement. For the combinatorial experimental design problem, the goal is to pick $k$ out of the given $n$ experiments so as to make the most accurate estimate of the unknown parameters, denoted as $\hatβ$. In this paper, we will study one of the most robust measures of error estimation - $D$-optimality criterion, which corresponds to minimizing the volume of the confidence ellipsoid for the estimation error $β-\hatβ$. The problem gives rise to two natural variants depending on whether repetitions of experiments are allowed or not. We first propose an approximation algorithm with a $\frac1e$-approximation for the $D$-optimal design problem with and without repetitions, giving the first constant factor approximation for the problem. We then analyze another sampling approximation algorithm and prove that it is $(1-ε)$-approximation if $k\geq \frac{4m}ε+\frac{12}{ε^2}\log(\frac{1}ε)$ for any $ε\in (0,1)$. Finally, for $D$-optimal design with repetitions, we study a different algorithm proposed by literature and show that it can improve this asymptotic approximation ratio. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1802_08372 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithms for D-optimal Design Singh, Mohit Xie, Weijun Machine Learning Data Structures and Algorithms Experimental design is a classical statistics problem and its aim is to estimate an unknown $m$-dimensional vector $β$ from linear measurements where a Gaussian noise is introduced in each measurement. For the combinatorial experimental design problem, the goal is to pick $k$ out of the given $n$ experiments so as to make the most accurate estimate of the unknown parameters, denoted as $\hatβ$. In this paper, we will study one of the most robust measures of error estimation - $D$-optimality criterion, which corresponds to minimizing the volume of the confidence ellipsoid for the estimation error $β-\hatβ$. The problem gives rise to two natural variants depending on whether repetitions of experiments are allowed or not. We first propose an approximation algorithm with a $\frac1e$-approximation for the $D$-optimal design problem with and without repetitions, giving the first constant factor approximation for the problem. We then analyze another sampling approximation algorithm and prove that it is $(1-ε)$-approximation if $k\geq \frac{4m}ε+\frac{12}{ε^2}\log(\frac{1}ε)$ for any $ε\in (0,1)$. Finally, for $D$-optimal design with repetitions, we study a different algorithm proposed by literature and show that it can improve this asymptotic approximation ratio. |
| title | Approximation Algorithms for D-optimal Design |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/1802.08372 |