A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noise

We revisit heavy-tailed corrupted least-squares linear regression assuming to have a corrupted n-sized label-feature sample of at most ε n arbitrary outliers. We wish to estimate a p-dimensional parameter b^* given such sample of a label-feature pair (y,x) satisfying y=langle x,b^*rangle+xi with heavy-tailed (x,xi). We only assume x is L4-L2 hypercontractive with constant L>0 and has covariance matrix Sigma with minimum eigenvalue 1/μ2>0 and bounded condition number kappa>0. The noise xi can be arbitrarily dependent on x and nonsymmetric as long as xi x has finite covariance matrix Xi. We propose a near-optimal computationally tractable estimator, based on the power method, assuming no knowledge on (Sigma,Xi) nor the operator norm of Xi. With probability at least 1-δ, our proposed estimator attains the statistical rate μ2VertXiVert1/2(fracpn+fraclog(1/δ)n+ε)1/2 and breakdown-point εlesssimfrac1L4kappa2, both optimal in the ℓ2-norm, assuming the near-optimal minimum sample size L4kappa2(plog p + log(1/δ))lesssim n, up to a log factor. To the best of our knowledge, this is the first computationally tractable algorithm satisfying simultaneously all the mentioned properties. Our estimator is based on a two-stage Multiplicative Weight Update algorithm. The first stage estimates a descent direction hat v with respect to the (unknown) pre-conditioned inner product langleSigma(·),·rangle. The second stage estimate the descent direction Sigmahat v with respect to the (known) inner product langle·,·rangle, without knowing nor estimating Sigma.