APAnkit Pensia
Ankit Pensia
*This is an algorithmically generated author record based on publicly available information.
Research Subjects
Ankit Pensia has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Chao Gao
Department of Statistics University of Chicago Chicago USA
1 shared publication - Daniel M. Kane
University of California San Diego
1 shared publication - Ilias Diakonikolas
University of Wisconsin-Madison University of California San Diego
1 shared publication - John Lafferty
Department of Statistics & Data Science Yale University
1 shared publication
Latest Publications
- Open Access
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
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)$.Open AccessInformation-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
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)$.