Risk Bounds for Randomized Sample Compressed Classifiers
Mohak Shah, McGill University

Poster ID: M36

Settings:

Consider Sample Compression (SC) algorithm that output a posterior Q on the classifier space SC Classifiers defined by Compression set and Message Strings, Data-dependent classifier space

PROBLEM: Derive Bounds for specific SC classifier chosen according to Q
Current Approach:

Derive uniform risk bounds on the Expectation over the risk of SC Gibbs Classifiers, e.g., PAC-Bayes strategy But: No Bounds for the chosen (randomized) classifier ~ Q

Our Approach:

Extend Occam's Hammer to data-dependent settings Identify region of samples where the risk bound does not hold Bound the risk over this region (bad event)