Statistical Query Lower Bounds for List-Decodable Linear Regression

• URL: http://arxiv.org/abs/2106.09689v1
• Date: Thu, 17 Jun 2021 17:45:21 GMT
• Title: Statistical Query Lower Bounds for List-Decodable Linear Regression
• Authors: Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas, Alistair Stewart
• Abstract summary: We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Our main result is a Statistical Query (SQ) lower bound of $dmathrmpoly (1/alpha)$ for this problem.
• Score: 55.06171096484622
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Specifically, we are given a set $T$ of labeled examples $(x, y) \in \mathbb{R}^d \times \mathbb{R}$ and a parameter $0< \alpha <1/2$ such that an $\alpha$-fraction of the points in $T$ are i.i.d. samples from a linear regression model with Gaussian covariates, and the remaining $(1-\alpha)$-fraction of the points are drawn from an arbitrary noise distribution. The goal is to output a small list of hypothesis vectors such that at least one of them is close to the target regression vector. Our main result is a Statistical Query (SQ) lower bound of $d^{\mathrm{poly}(1/\alpha)}$ for this problem. Our SQ lower bound qualitatively matches the performance of previously developed algorithms, providing evidence that current upper bounds for this task are nearly best possible.

Related papers

• How to Inverting the Leverage Score Distribution? [16.744561210470632]
  Despite leverage scores being widely used as a tool, in this paper, we study a novel problem, namely the inverting leverage score. We use iterative shrinking and the induction hypothesis to ensure global convergence rates for the Newton method. This important study on inverting statistical leverage opens up numerous new applications in interpretation, data recovery, and security.
  arXiv  Detail & Related papers  (2024-04-21T21:36:42Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
  We explore algorithms and limitations for sparse optimization problems such as sparse linear regression and robust linear regression. Specifically, the sparse linear regression problem seeks a $k$-sparse vector $xinmathbbRd$ to minimize $|Ax-b|$. The robust linear regression problem seeks a set $S$ that ignores at most $k$ rows and a vector $x$ to minimize $|(Ax-b)_S|$.
  arXiv  Detail & Related papers  (2022-06-29T01:40:38Z)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  We develop a novel, conceptually simpler technique for list-decodable sparse mean estimation. In particular, for distributions with "certifiably bounded" $t-th moments in $k$-sparse directions, our algorithm achieves error of $(1/alpha)O (1/t)$ with sample complexity $m = (klog(n))O(t)/alpha(mnt)$. For the special case of Gaussian inliers, our algorithm achieves the optimal error guarantee of $Theta (sqrtlog
  arXiv  Detail & Related papers  (2022-06-10T17:38:18Z)
• Robust Testing in High-Dimensional Sparse Models [0.0]
  We consider the problem of robustly testing the norm of a high-dimensional sparse signal vector under two different observation models. We show that any algorithm that reliably tests the norm of the regression coefficient requires at least $n=Omegaleft(min(slog d,1/gamma4)right) samples.
  arXiv  Detail & Related papers  (2022-05-16T07:47:22Z)
• Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
  We study synchronous Q-learning with Polyak-Ruppert averaging (a.k.a., averaged Q-leaning) in a $gamma$-discounted MDP. We establish normality for the iteration averaged $barboldsymbolQ_T$. In short, our theoretical analysis shows averaged Q-Leaning is statistically efficient.
  arXiv  Detail & Related papers  (2021-12-29T14:47:56Z)
• On the Power of Preconditioning in Sparse Linear Regression [24.140675945592704]
  We show that a preconditioned Lasso can solve a large class of sparse linear regression problems nearly optimally. For the first time, we construct random-design instances which are provably hard for an optimally preconditioned Lasso.
  arXiv  Detail & Related papers  (2021-06-17T02:12:01Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.