# Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 33 references that are in the map.
- First posted on arXiv 15 Jun 2022.

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

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Dynamic Pricing in High-dimensions](https://mlsanity.com/paper/1609.07574/) (2016)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Corruption-Tolerant Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2003.01971/) (2020)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [Stochastic Linear Optimization with Adversarial Corruption](https://mlsanity.com/paper/1909.02109/) (2019)
- [Logarithmic Regret in Feature-based Dynamic Pricing](https://mlsanity.com/paper/2102.10221/) (2021)
- [Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise](https://mlsanity.com/paper/2201.11341/) (2022)
- [Perishability of Data: Dynamic Pricing under Varying-Coefficient Models](https://mlsanity.com/paper/1701.03537/) (2017)
- [Semi-parametric dynamic contextual pricing](https://mlsanity.com/paper/1901.02045/) (2019)
- [Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2103.12487/) (2021)
- [Learning Product Rankings Robust to Fake Users](https://mlsanity.com/paper/2009.05138/) (2020)
- [Robust Dynamic Assortment Optimization in the Presence of Outlier Customers](https://mlsanity.com/paper/1910.04183/) (2019)
- [Contextual Search in the Presence of Adversarial Corruptions](https://mlsanity.com/paper/2002.11650/) (2020)
- [Computing Walrasian Equilibria: Fast Algorithms and Structural Properties](https://mlsanity.com/paper/1511.04032/) (2015)

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

- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets](https://mlsanity.com/paper/2602.01682/) (2026)
- [Corruption-Robust Lipschitz Contextual Search](https://mlsanity.com/paper/2307.13903/) (2023)
- [Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time](https://mlsanity.com/paper/2605.08290/) (2026)

## Abstract (arXiv)

We study the problem of contextual search, a generalization of binary search in higher dimensions, in the adversarial noise model. Let d be the dimension of the problem, T be the time horizon and C be the total amount of adversarial noise in the system. We focus on the ε-ball and the symmetric loss. For the ε-ball loss, we give a tight regret bound of O(C + d log(1/ε)) improving over the O(d3 log(1/ε) log2(T) + C log(T) log(1/ε)) bound of Krishnamurthy et al (Operations Research '23). For the symmetric loss, we give an efficient algorithm with regret O(C+d log T). To tackle the symmetric loss case, we study the more general setting of Corruption-Robust Convex Optimization with Subgradient feedback, which is of independent interest. Our techniques are a significant departure from prior approaches. Specifically, we keep track of density functions over the candidate target vectors instead of a knowledge set consisting of the candidate target vectors consistent with the feedback obtained.