Variable Selection is Hard

Dean Foster, Howard Karloff, Justin Thaler

Variable selection for sparse linear regression is the problem of finding, given an m x p matrix B and a target vector y, a sparse vector x such that Bx approximately equals y. Ass…