English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We develop machinery to design efficiently computable and consistentestimators, achieving estimation error approaching zero as the number ofobservations grows, when facing an oblivious adversary that may corruptresponses in all but an $\alpha$ fraction of the samples. As concrete examples,we investigate two problems: sparse regression and principal component analysis(PCA). For sparse regression, we achieve consistency for optimal sample size$n\gtrsim (k\log d)/\alpha^2$ and optimal error rate $O(\sqrt{(k\log d)/(n\cdot\alpha^2)})$ where $n$ is the number of observations, $d$ is the number ofdimensions and $k$ is the sparsity of the parameter vector, allowing thefraction of inliers to be inverse-polynomial in the number of samples. Prior tothis work, no estimator was known to be consistent when the fraction of inliers$\alpha$ is $o(1/\log \log n)$, even for (non-spherical) Gaussian designmatrices. Results holding under weak design assumptions and in the presence ofsuch general noise have only been shown in dense setting (i.e., general linearregression) very recently by d'Orsi et al. [dNS21]. In the context of PCA, weattain optimal error guarantees under broad spikiness assumptions on theparameter matrix (usually used in matrix completion). Previous works couldobtain non-trivial guarantees only under the assumptions that the measurementnoise corresponding to the inliers is polynomially small in $n$ (e.g., Gaussianwith variance $1/n^2$).  To devise our estimators, we equip the Huber loss with non-smoothregularizers such as the $\ell_1$ norm or the nuclear norm, and extend d'Orsiet al.'s approach [dNS21] in a novel way to analyze the loss function. Ourmachinery appears to be easily applicable to a wide range of estimationproblems.

Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers