The optimal information complexity of VC learning
Hanneke et al.
A randomised majority vote of five learners reaches the optimal generalisation guarantee, with conditional mutual information of order of the VC dimension.
In the Daily Brief of 11 October 2026
Information-theoretic generalisation bounds control a learner's error through how much information its output reveals about the training sample. This paper measures that information with evaluated conditional mutual information and asks how small it can be for classes of finite VC dimension.
In the realizable case, the authors show that a randomised majority vote of five base learners has evaluated conditional mutual information of order \(d\), the VC dimension, and achieves the optimal in-expectation generalisation guarantee.
The result reconciles information-theoretic bounds with classical VC theory, and it is majority voting that makes the construction work.