论文标题
$λ$调查的A-最佳设计及其近似值（按$λ$进行的比例抽样）
$λ$-Regularized A-Optimal Design and its Approximation by $λ$-Regularized Proportional Volume Sampling
论文作者
论文摘要
在这项工作中，我们研究了$λ$的$ a $ a $ - 最佳设计问题，并介绍了$λ$调查的比例抽样算法，该算法从[Nikolov，Singh和Tantipongongpipat，2019]中概括为近似工作，以确保了以前的工作。在这个问题中，我们给我们提供了向量$ v_1，\ ldots，v_n \ in \ mathbb {r}^d $ in $ d $ dimensions，一个预算$ k \ leq n $和常规式参数$λ\ geq0 $ $ \ left（\ sum_ {i \ in s} v_iv_i^\ top +λi_d\ right）该问题是由脊回归中的最佳设计引起的，在山脊回归中，人们试图最大程度地减少基础线性模型中真正系数的脊回归预测变量的预期平方误差。我们介绍了$λ$调查的比例卷采样，并提供其多项式时间实现以解决此问题。我们显示其$（1+ \fracε{\ sqrt {1+λ'}}）$ - $ k =ω\ left（\ fracdε+\ frac {\ frac+\ frac {\ log 1/ε} {\ log log 1/ε} {ε^2} \ right） tantipongpipat，2019年] to case $λ> 0 $，并获得渐近最优性为$λ\ rightarrow \ infty $。
In this work, we study the $λ$-regularized $A$-optimal design problem and introduce the $λ$-regularized proportional volume sampling algorithm, generalized from [Nikolov, Singh, and Tantipongpipat, 2019], for this problem with the approximation guarantee that extends upon the previous work. In this problem, we are given vectors $v_1,\ldots,v_n\in\mathbb{R}^d$ in $d$ dimensions, a budget $k\leq n$, and the regularizer parameter $λ\geq0$, and the goal is to find a subset $S\subseteq [n]$ of size $k$ that minimizes the trace of $\left(\sum_{i\in S}v_iv_i^\top + λI_d\right)^{-1}$ where $I_d$ is the $d\times d$ identity matrix. The problem is motivated from optimal design in ridge regression, where one tries to minimize the expected squared error of the ridge regression predictor from the true coefficient in the underlying linear model. We introduce $λ$-regularized proportional volume sampling and give its polynomial-time implementation to solve this problem. We show its $(1+\fracε{\sqrt{1+λ'}})$-approximation for $k=Ω\left(\frac dε+\frac{\log 1/ε}{ε^2}\right)$ where $λ'$ is proportional to $λ$, extending the previous bound in [Nikolov, Singh, and Tantipongpipat, 2019] to the case $λ>0$ and obtaining asymptotic optimality as $λ\rightarrow \infty$.
