2018/04/09 by Renato Paes Leme, Jon Schneider, Leme, Renato Paes +1 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Metric Geometry (math.MG) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1804.03195
openalex publication_date 2018/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ⟨ ut, v⟩, learns whether pt < ⟨ ut, v⟩, and incurs loss ℓ(⟨ ut, v⟩, 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.