APAnkit Pensia

Ankit Pensia

*This is an algorithmically generated author record based on publicly available information.

Ankit Pensia has a total of 4 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination

    by Ilias Diakonikolas, Chao Gao, Daniel M. Kane, John Lafferty, Ankit Pensia

    We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d.\ samples from a distribution $(x, y)$ on $\mathbb{R}^d \times \mathbb{R}$ with $x \sim \mathcal{N}(0,\mathbf{I}_d)$ and $y = x^\top β+ z$, where $z$ is drawn independently of $x$ from an unknown distribution $E$. Moreover, $z$ satisfies $\mathbb{P}_E[z = 0] = α>0$. The goal is to accurately recover the regressor $β$ to small $\ell_2$-error. Ignoring computational considerations, this problem is known to be solvable using $O(d/α)$ samples. On the other hand, the best known polynomial-time algorithms require $Ω(d/α^2)$ samples. Here we provide formal evidence that the quadratic dependence in $1/α$ is inherent for efficient algorithms. Specifically, we show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $\tildeΩ(d^{1/2}/α^2)$.