Optimality and computational barriers in variable selection under dependence
依赖结构下变量选择的最优性与计算壁垒
We study the optimal sample complexity of variable selection in linear regression under general design covariance, and show that subset selection is optimal while under standard complexity assumptions, efficient algorithms for this problem do not exist. Specifically, we analyze the variable selection problem and provide the optimal sample complexity with exact dependence on the problem parameters for both known and unknown sparsity settings. Moreover, we establish a sample…