# Corruption-Robust Lipschitz Contextual Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 26 references that are in the map.
- First posted on arXiv 26 Jul 2023.

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

- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Learning Prices for Repeated Auctions with Strategic Buyers](https://mlsanity.com/paper/1311.6838/) (2013)
- [Adversarial Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2002.03839/) (2020)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [Improved Corruption Robust Algorithms for Episodic Reinforcement Learning](https://mlsanity.com/paper/2102.06875/) (2021)
- [Contextual Search in the Presence of Adversarial Corruptions](https://mlsanity.com/paper/2002.11650/) (2020)
- [Learning to Price Against a Moving Target](https://mlsanity.com/paper/2106.04689/) (2021)
- [Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization](https://mlsanity.com/paper/2206.07528/) (2022)

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

- [Contextual Dynamic Pricing with Heterogeneous Buyers](https://mlsanity.com/paper/2512.09513/) (2025)

## Abstract (arXiv)

I study the problem of learning a Lipschitz function with corrupted binary signals. The learner tries to learn a L-Lipschitz function f: [0,1]d rightarrow [0, L] that the adversary chooses. There is a total of T rounds. In each round t, the adversary selects a context vector xt in the input space, and the learner makes a guess to the true function value f(xt) and receives a binary signal indicating whether the guess is high or low. In a total of C rounds, the signal may be corrupted, though the value of C is unknown to the learner. The learner's goal is to incur a small cumulative loss. This work introduces the new algorithmic technique agnostic checking as well as new analysis techniques. I design algorithms which: for the symmetric loss, the learner achieves regret L· O(Clog T) with d = 1 and L· Od(Clog T + T(d-1)/d) with d > 1; for the pricing loss, the learner achieves regret L· widetildeO (Td/(d+1) + C· T1/(d+1)).