Corruption-Robust Contextual Search
summary
Contextual search algorithms become corruption-robust by modeling misbehavior as C corruptions and giving near-optimal regret that scales additively with corruption plus the realizable term: one algorithm attains C0 + D log(1/epsilon) (epsilon‑window median with T^D runtime), another uses log-concave sampling to get a polynomial-time guarantee C1 + D log T; core tools are knowledge-set volumetric cuts, Carathéodory-style aggregation (after O(D^2 C) rounds) and multiplicative‑weights–style density updates; pricing loss remains unsettled.
AI-written summary · about
chapters (7)
- 0:00Introduction to the session
- 1:26Contextual search basics
- 7:52Problem scope and noise models
- 13:14Knowledge set-based techniques
- 19:53Robustifying algorithms
- 28:55Density-based approaches
- 39:18Advanced algorithms and Q&A
related talks
12mDistribution-Free Robustness
29mCorruption Robust Exploration in Episodic Reinforcement Learning
01h 04mAlgorithmic High Dimensional Robust Statistics II
01h 08mData Driven Optimization Models and Algorithms
31mRealizing Robustness
01h 00mAlgorithmic High Dimensional Robust Statistics I
09mFrom Robustness to Privacy and Back
09mIntegrating Differential Privacy and Contextual Integrity