PaperlayerView exact revision on arXiv

Source-linked AI summary

The optimal information complexity of VC learning

Steve Hanneke, Juexiao Wang

arXiv:2610.10600v1stat.MLcs.ITcs.LGmath.ITmath.STstat.TH

TL;DR

The paper asks whether algorithm-dependent information analyses can recover the optimal PAC guarantee for VC classes in the realizable case. It constructs randomized majority-vote learners and shows that Majority-of-5 achieves worst-case eCMI O(d), while Majority-of-3 gives an optimal distributional eCMI guarantee.

  • Problem

    Whether algorithm-dependent CMI analyses can recover the optimal realizable PAC guarantee for VC classes remains an open question.

    Source: §1 · p. 3, §2.3 · p. 6

  • Method

    The paper constructs a randomized Majority-of-5 learner by combining five base learners trained on adjusted disjoint pieces of the sample.

    Source: §3.1 · p. 7

  • Results

    O(d) worst-case eCMI for randomized Majority-of-5 recovers the optimal realizable expected generalization guarantee, and Majority-of-3 achieves the optimal distributional eCMI guarantee.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Optimal realizable PAC generalization for VC classes can be recovered through eCMI using a randomized learner.

    Source: §9 · p. 25

    The Majority-of-5 construction is improper and may output classifiers outside the concept class.

    Source: §1 · p. 4

Abstract

from arXiv · show

Steinke and Zakynthinou(2020) introduces the Conditional Mutual Information (CMI) framework of analyzing the information complexity of learning algorithms based on algorithm-dependent information-theoretic quantities. We study one of these quantities, the evaluated Conditional Mutual Information (eCMI). It has been an interesting question whether the optimal PAC guarantee for VC classes can be recovered from the algorithm-dependent analyses via CMI. And we show that it is possible to recover this guarantee by constructing a learning algorithm whose eCMI is of order O(d) in the realizable case, where d is the VC-dimension of the concept class. Specially, our algorithm is a randomized Majority-of-5 base learners with optimal in-expectation generalization guarantee.

1 Introduction

The paper asks whether algorithm-dependent information analyses can recover the optimal realizable PAC guarantee for VC classes. It answers yes using randomized majority-vote learners with optimal eCMI guarantees.

Motivation

  • The optimal expected realizable PAC error rate for VC classes is O(d/n), while ERM can be suboptimal.Earlier direct algorithm analyses established the optimal expected and high-probability guarantees.Source: §1 · p. 3

Main Result

  • A randomized Majority-of-5 learner achieves worst-case eCMI O(d) and recovers the optimal expected generalization guarantee in the realizable case.The result addresses VC classes of dimension d.Source: §1 · p. 4
  • A Majority-of-3 learner also achieves the optimal distributional eCMI guarantee, while the Majority-of-5 learner is improper and optimal CMI remains open.The Majority-of-3 result uses base learners with optimal expected error rate.Source: §1 · p. 4

Overview of Techniques

  • The Majority-of-5 construction permutes the training data, runs five base learners on adjusted disjoint pieces, and combines their classifiers by majority vote.The adjustment emulates i.i.d. sampling from the empirical distribution.Source: §1 · p. 4
  • Five conditionally independent base classifiers reduce pointwise error so that conditional error entropy sums to O(d) when the base learner has expected error O(d/n).The analysis uses five conditional error regions; where one learner lacks a bound, at least two of the other four must err for the majority vote to err.Source: §1 · p. 4

2 Preliminaries

The preliminaries define evaluated conditional mutual information, connect it to expected generalization, and establish VC-dimension bounds that motivate the paper’s algorithms.

2 Preliminaries

  • The paper introduces eCMI and gives a bound on expected generalization error in terms of it.The section also sets notation for realizable supersamples and losses.Source: §2 · p. 5

2.1 Evaluated CMI

  • eCMI measures information about the random sample swaps through the output’s loss vector evaluated on a 2n-sample supersample.The definition conditions on the supersample and uses the loss vector of the algorithm’s output.Source: §2.1 · p. 5

2.2 Generalization from eCMI

  • Expected loss is bounded by twice expected training loss plus three times distributional eCMI.The result applies to randomized algorithms and bounded loss functions.Source: §2.2 · p. 5

2.3 Bounding eCMI from VC-dimension

  • For ERM, the VC-dimension bound on eCMI is d log n + 2, and the worst-case entropy bound uses a uniform distribution over supersample labelings.The cited prior work also conjectures a distribution-uniform O(d) bound on CMI.Source: §2.3 · p. 6

2.4 Our Contributions

  • The contributions include a Majority-of-5 eCMI bound of 1920·nR(n/5), training error at most 5·R(n/5), and a Majority-of-3 result for distributional eCMI.A separate theorem states an O(d) worst-case eCMI guarantee for a randomized algorithm.Source: §2.4 · p. 6

2.5 Notation

  • The notation defines the majority vote of t classifiers by thresholding their summed binary predictions at t/2.The section also defines conditional entropy and binary entropy for prediction errors.Source: §2.5 · pp. 6–7

3 Our Approach

The approach uses five randomized base learners and a majority vote to obtain an optimal worst-case eCMI guarantee when the base learner has optimal expected error. Its proof bounds eCMI through conditional error entropies and uses conditional independence to control majority-vote errors.

3.1 A randomized Majority-of-5 learner

  • The algorithm randomly permutes the data, divides it into five disjoint pieces, adjusts duplicates to make each training set conditionally i.i.d., and combines the five base classifiers by majority vote.The adjusted training sets are sampled conditionally i.i.d. from the empirical distribution on the n training points.Source: §3.1 · p. 7

3.2 Proof Overview

  • An O(d/n) expected-error base learner yields O(d) worst-case eCMI for the randomized Majority-of-5 learner.The paper identifies this as the minimal, optimal-order guarantee.Source: §3.2 · pp. 8, 10
  • Given the algorithm’s randomness, the base classifiers are conditionally independent, and a majority error requires at least two of the other four classifiers to err.This bounds the majority classifier’s conditional error using a squared conditional error probability, supporting the entropy analysis.Source: §3.2 · pp. 9–10
  • The proof bounds the conditional entropy of errors by a convergent sum, yielding worst-case eCMI of order O(nR(n/5)).Here R(m) is the base learner’s expected error rate; an optimal O(d/n) rate gives the O(d) guarantee.Source: §3.2 · pp. 8, 10

4 Reduction to Conditional entropy

This section reduces eCMI to conditional entropies of losses on a fixed arbitrary supersample. The proof uses information and Shannon entropy identities and inequalities to obtain the bound.

  • For a fixed arbitrary supersample, the eCMI of a randomized learning algorithm is bounded by the sum of conditional entropies of losses.The lemma supplies the reduction used in the subsequent analysis.Source: §4 · p. 10
  • Subadditivity turns the joint entropy expression into a sum of conditional entropy terms for losses on the supersample.Source: §4 · pp. 10–11
  • The proof applies the mutual-information chain rule, non-negativity, the Shannon entropy chain rule, and entropy subadditivity.These steps derive the stated bound from the conditional entropy terms.Source: §4 · pp. 10–11

5 Guarantee on the expected size of the conditional error region

This section uses duplicate-adjusted, conditionally i.i.d. training sets to bound the expected size of a base learner’s j-th conditional error region in terms of its expected errors over the remaining data. These bounds provide an ingredient for the next section’s conditional-entropy analysis.

5.1 Duplicates adjustment

  • DuplicatesAdjustment makes each training set conditionally i.i.d. from the empirical distribution given σ, supporting a worst-case eCMI guarantee for the randomized majority-vote learner.It adjusts duplicates in a uniform sample drawn without replacement.Source: §5.1 · pp. 11–12

5.2 Expected number of errors

  • Each base learner’s expected errors on the other 4n/5 pairs are at most twice its i.i.d. expected-error guarantee on n training points.The bound is over random swaps, permutation, and duplicates adjustment.Source: §5.2 · pp. 13–15

5.3 Expected size of the conditional error region

  • The expected size of the j-th conditional error region is at most 2j · 2nR for each base learner.The bound applies Markov’s inequality to the expected-error guarantee from Lemma 5.2.Source: §5.3 · p. 16
  • The expected size is at most 2^j · 2nR(n/5), by applying Markov’s inequality and then Lemma 5.2.The derivation uses conditional expectation and the law of total expectation to relate the region size to the base learner’s expected errors over the other 4n examples.Source: §5.3 · pp. 16–17

6 Conditional entropy of a randomized Majority-of-5 learner

The section bounds the conditional entropy of errors for a randomized Majority-of-5 learner on a fixed realizable supersample. It uses conditional independence among base learners to control error probabilities.

  • The analysis bounds the conditional entropy of the learner’s errors on all 2n points of a fixed realizable supersample.Source: §6 · p. 17
  • A Majority-of-5 error requires at least two of the other four base classifiers to err, enabling a bound through their conditional error probabilities.Source: §6 · pp. 17–18
  • By permutation symmetry, the conditional entropy over all 2n points is five times the entropy on the first partition part.Source: §6 · p. 18

7 Expected training error rate and Proof of the Main Theorem

The paper derives an expected training-error guarantee for its randomized Majority-of-5 learner and connects that guarantee to optimal PAC learning of VC classes in the realizable case.

  • The randomized Majority-of-5 learner recovers an optimal realizable-case PAC guarantee, with worst-case eCMI tied to the base learner’s i.i.d. expected-error guarantee.Source: §7 · pp. 19–20
  • For the training-error analysis, the random-swap variables are unnecessary, so the proof may take the swap permutation to be the identity.Source: §7 · pp. 19–20
  • When the base learner has an optimal in-expectation generalization guarantee, Theorem 2.3 bounds the Majority-of-5 learner’s expected training-error rate.Source: §7 · pp. 19–20

8 Distributional eCMI

The distributional eCMI analysis shows that a Majority-of-3 construction can achieve an optimal guarantee under a stronger base-learner assumption. It develops this result through bounds on supersample errors, conditional error regions, and training error.

8 Distributional eCMI

  • Three base learners suffice for an optimal distributional eCMI guarantee under the stated expected true-error and training-error bound R(m).Source: §8 · pp. 20–21

8.1 Expected number of errors on a supersample

  • The analysis bounds each base learner’s expected errors on the 2n supersample points using its i.i.d. error guarantee.Source: §8.1 · p. 21

8.2 Expected size of the conditional error region

  • Markov’s inequality converts the expected-error guarantee into a bound on the expected size of each conditional error region.Source: §8.2 · p. 22

8.3 Distributional eCMI of a Majority-of-3 learner

  • The distributional eCMI of Majority-of-3 is bounded through conditional entropy of its evaluated error vector and conditional error-region bounds.Source: §8.3 · p. 23

8.4 Expected training error rate

  • The Majority-of-3 training-error rate is bounded by the expected true-error rates of the other two base learners.Source: §8.4 · pp. 24–25

9 Conclusions

A randomized Majority-of-5 learner achieves worst-case eCMI of order O(d), and this bound combined with its expected training-error guarantee recovers an optimal PAC guarantee for realizable VC learning. The results also cover distributional eCMI and multiclass learning.

  • O(d) worst-case eCMI, together with the learner’s expected training-error guarantee, recovers an optimal PAC guarantee for realizable VC learning.Source: §9 · p. 25
  • A Majority-of-3 of base learners with an optimal in-expectation generalization guarantee suffices for an optimal distributional eCMI guarantee.Source: §9 · p. 25
  • O(dDS) worst-case eCMI is achieved for multiclass learning in the realizable case by the randomized Majority-of-5 learner.The results extend with d taken as the Daniely–Shalev-Shwartz dimension.Source: §9 · p. 25
Loading 2610.10600v1…