Sample Complexity Lower Bounds for Generic Algorithms in Contaminated PAC Learning

Interactive exploration of information-theoretic lower bounds in the iterative contaminated PAC model. Adjust parameters to see how bounds, channel capacity, and empirical errors change.

VC Dimension d 5

Contamination Rate α 0.30

Samples per Round n 50

Number of Rounds T 50

Key Quantities

Fano Lower Bound

d / (nT H(α))

Channel Capacity Bound

d / (nT C(α))

Conjectured Tight Bound

√(d / ((1-α)nT))

Channel Capacity

C(α) = 1 - H(α) bits

Gap Factor

Upper / Best lower bound

Bounds vs. Round Number

Phase Transition: Bounds vs. Contamination Rate

Channel Capacity & Entropy

Scaling: Bounds vs. Total Samples nT

Bound Comparison Table

α	T	Fano LB	Info LB	Le Cam LB	Conjectured	Upper Bound	Gap