The optimal information complexity of VC learning
The research investigates if algorithm-dependent information measures, specifically evaluated Conditional Mutual Information (eCMI), can recover the optimal PAC guarantee for learning VC classes. The study shows that a randomized Majority-of-5 learner achieves an optimal worst-case eCMI of order O(d) in the realizable case, which recovers the best expected generalization guarantee.