# Contextual Search via Intrinsic Volumes

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2018.

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

- [Policy Optimization Using Semi-parametric Models for Dynamic Pricing](https://mlsanity.com/paper/2109.06368/) (2021)
- [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)
- [Contextual Inverse Optimization: Offline and Online Learning](https://mlsanity.com/paper/2106.14015/) (2021)
- [Dynamic pricing and assortment under a contextual MNL demand](https://mlsanity.com/paper/2110.10018/) (2021)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Contextual Recommendations and Low-Regret Cutting-Plane Algorithms](https://mlsanity.com/paper/2106.04819/) (2021)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Doubly Fair Dynamic Pricing](https://mlsanity.com/paper/2209.11837/) (2022)
- [Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets](https://mlsanity.com/paper/2602.01682/) (2026)
- [Learning to Price Against a Moving Target](https://mlsanity.com/paper/2106.04689/) (2021)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization](https://mlsanity.com/paper/2206.07528/) (2022)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026)
- [Efficient Online Inverse Optimization with O(d) Regret](https://mlsanity.com/paper/2609.13440/) (2026)
- [Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand](https://mlsanity.com/paper/2605.05609/) (2026)
- [Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights](https://mlsanity.com/paper/2609.26978/) (2026)
- [Corruption-Robust Lipschitz Contextual Search](https://mlsanity.com/paper/2307.13903/) (2023)
- [Misalignment, Learning, and Ranking: Harnessing Users Limited Attention](https://mlsanity.com/paper/2402.14013/) (2024)
- [Active Learning for Contextual Search with Binary Feedbacks](https://mlsanity.com/paper/2110.01072/) (2021)
- [Margin-Independent Online Multiclass Learning via Convex Geometry](https://mlsanity.com/paper/2111.08057/) (2021)
- [Structured Dynamic Pricing: Optimal Regret in a Global Shrinkage Model](https://mlsanity.com/paper/2303.15652/) (2023)
- [Contextual Dynamic Pricing with Heterogeneous Buyers](https://mlsanity.com/paper/2512.09513/) (2025)
- [Efficient Opportunistic Approachability](https://mlsanity.com/paper/2602.21328/) (2026)
- [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 multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the value of a hidden vector v ∈ [0,1]d. Every round the learner is provided an adversarially-chosen context ut ∈ ℝd, submits a guess pt for the value of langle ut, vrangle, learns whether pt < langle ut, vrangle, and incurs loss ℓ(langle ut, vrangle, pt) (for some loss function ℓ). The learner's goal is to minimize their total loss over the course of T rounds. We present an algorithm for the contextual search problem for the symmetric loss function ℓ(θ, p) = |θ - p| that achieves Od(1) total loss. We present a new algorithm for the dynamic pricing problem (which can be realized as a special case of the contextual search problem) that achieves Od(log log T) total loss, improving on the previous best known upper bounds of Od(log T) and matching the known lower bounds (up to a polynomial dependence on d). Both algorithms make significant use of ideas from the field of integral geometry, most notably the notion of intrinsic volumes of a convex set. To the best of our knowledge this is the first application of intrinsic volumes to algorithm design.