# Stochastic Linear Optimization with Adversarial Corruption

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2019.

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

- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks](https://mlsanity.com/paper/2106.02978/) (2021)
- [Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes](https://mlsanity.com/paper/2212.05949/) (2022)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2110.12615/) (2021)
- [Improved Corruption Robust Algorithms for Episodic Reinforcement Learning](https://mlsanity.com/paper/2102.06875/) (2021)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [Robust Lipschitz Bandits to Adversarial Corruptions](https://mlsanity.com/paper/2305.18543/) (2023)
- [Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds](https://mlsanity.com/paper/2302.12370/) (2023)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)
- [Bias-Robust Bayesian Optimization via Dueling Bandits](https://mlsanity.com/paper/2105.11802/) (2021)
- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)
- [Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback](https://mlsanity.com/paper/2404.10776/) (2024)
- [Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification](https://mlsanity.com/paper/2410.07533/) (2024)
- [Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions](https://mlsanity.com/paper/2106.04207/) (2021)
- [Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization](https://mlsanity.com/paper/2206.07528/) (2022)
- [Robust Causal Bandits for Linear Models](https://mlsanity.com/paper/2310.19794/) (2023)
- [Online Corrupted User Detection and Regret Minimization](https://mlsanity.com/paper/2310.04768/) (2023)
- [Improved Bound for Robust Causal Bandits with Linear Models](https://mlsanity.com/paper/2405.07795/) (2024)
- [Robust and differentially private stochastic linear bandits](https://mlsanity.com/paper/2304.11741/) (2023)
- [Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise](https://mlsanity.com/paper/2603.15596/) (2026)
- [Corruption-Robust Sparse Linear Contextual Bandits with Knapsack Constraints](https://mlsanity.com/paper/2609.37189/) (2026)

## Abstract (arXiv)

We extend the model of stochastic bandits with adversarial corruption (Lykouriset al., 2018) to the stochastic linear optimization problem (Dani et al., 2008). Our algorithm is agnostic to the amount of corruption chosen by the adaptive adversary. The regret of the algorithm only increases linearly in the amount of corruption. Our algorithm involves using L"owner-John's ellipsoid for exploration and dividing time horizon into epochs with exponentially increasing size to limit the influence of corruption.