# Robust Online Convex Optimization in the Presence of Outliers

arXiv: https://arxiv.org/abs/2107.01881 · HTML: https://mlsanity.com/paper/2107.01881/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 51 references that are in the map.
- First posted on arXiv 5 Jul 2021.

## Builds on (most cited first, 25 of 25)

- [Adversarial examples in the physical world](https://mlsanity.com/paper/1607.02533/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method](https://mlsanity.com/paper/1907.02707/) (2019)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Data Poisoning Attacks against Online Learning](https://mlsanity.com/paper/1808.08994/) (2018)
- [Sequential estimation of quantiles with applications to A/B-testing and best-arm identification](https://mlsanity.com/paper/1906.09712/) (2019)
- [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020)
- [Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination](https://mlsanity.com/paper/2010.04157/) (2020)

## Built on by (most cited first, 4 of 4)

- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization](https://mlsanity.com/paper/2408.06297/) (2024)
- [Online Conformal Prediction with Corrupted Feedback](https://mlsanity.com/paper/2605.20515/) (2026)
- [Online Distributional Prediction via Latent Cluster Geometry Under Drift and Corruption](https://mlsanity.com/paper/2606.18778/) (2026)

## Abstract (arXiv)

We consider online convex optimization when a number k of data points are outliers that may be corrupted. We model this by introducing the notion of robust regret, which measures the regret only on rounds that are not outliers. The aim for the learner is to achieve small robust regret, without knowing where the outliers are. If the outliers are chosen adversarially, we show that a simple filtering strategy on extreme gradients incurs O(k) additive overhead compared to the usual regret bounds, and that this is unimprovable, which means that k needs to be sublinear in the number of rounds. We further ask which additional assumptions would allow for a linear number of outliers. It turns out that the usual benign cases of independently, identically distributed (i.i.d.) observations or strongly convex losses are not sufficient. However, combining i.i.d. observations with the assumption that outliers are those observations that are in an extreme quantile of the distribution, does lead to sublinear robust regret, even though the expected number of outliers is linear.