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

In this work we revisit two classic high-dimensional online learningproblems, namely linear regression and contextual bandits, from the perspectiveof adversarial robustness. Existing works in algorithmic robust statistics makestrong distributional assumptions that ensure that the input data is evenlyspread out or comes from a nice generative model. Is it possible to achievestrong robustness guarantees even without distributional assumptionsaltogether, where the sequence of tasks we are asked to solve is adaptively andadversarially chosen?  We answer this question in the affirmative for both linear regression andcontextual bandits. In fact our algorithms succeed where conventional methodsfail. In particular we show strong lower bounds against Huber regression andmore generally any convex M-estimator. Our approach is based on a novelalternating minimization scheme that interleaves ordinary least-squares with asimple convex program that finds the optimal reweighting of the distributionunder a spectral constraint. Our results obtain essentially optimal dependenceon the contamination level $\eta$, reach the optimal breakdown point, andnaturally apply to infinite dimensional settings where the feature vectors arerepresented implicitly via a kernel map.

Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination