Corruption-Robust Lipschitz Contextual Search

Event Type

Seminar/Symposium

Sponsor

Siebel School of Computing and Data Science

Location

Thomas M. Siebel Center for Computer Science, 201 North Goodwin Avenue, Urbana, IL 61801, room# 3401

Date

Sep 9, 2024   10:00 am  

Speaker

Shiliang Zuo (UIUC)

Contact

Michael A Forbes

E-Mail

miforbes@illinois.edu

Phone

217-300-0454

Views

127

Originating Calendar

Siebel School Speakers Calendar

This work studies Lipschitz contextual search with adversarial corruptions.  Contextual search is a generalization of the classic binary search to higher dimensions, with applications in dynamic pricing and personalized medicine. We study contextual search in a non-parametric setting, where a learner tries to learn a L-Lipschitz function f:[0,1]^d→[0,L] that the adversary chooses. There is a total of T rounds, in each round the adversary presents the learner with context x, and the learner makes a guess to f(x) and can observe whether his guess is low or high. We further allow some signals to be corrupted. In at most C rounds the signal may be flipped, though the value of C is unknown to the learner. The learner's goal is to incur a small cumulative loss that degrade gracefully as C increases.

>> 

>>       This work introduces a new algorithmic technique “agnostic corruption checks” as well as new analysis techniques. We design algorithms which: for the absolute loss, the learner achieves regret L⋅O(ClogT) when d=1 and L⋅O_d(ClogT+T^(d−1)/d) when d>1; for the pricing loss, the learner achieves regret L⋅Õ(T^d/(d+1)+C⋅T^1/(d+1)).