Technical Summary: Bound to Disagree: Generalization Bounds via Certifiable Surrogates

Problem Statement

Deep learning models, particularly over-parameterized neural networks, have demonstrated empirical success that contradicts classical statistical learning theory, which often predicts overfitting. Despite extensive research into generalization bounds based on VC dimension, Rademacher complexity, information theory, and PAC-Bayes theory, existing bounds for deep neural networks suffer from three primary limitations:

1. Vacuousness: Many bounds yield values greater than 1 (or trivial upper bounds) when applied to medium-to-large networks.
2. Non-computability: Some bounds rely on universal constants that cannot be computed or require intractable assumptions about the input space.
3. Restrictiveness: Many valid bounds apply only to modified versions of the model (e.g., pruned or quantized) rather than the original predictor, or they require specific architectural constraints (e.g., gated activations).

The paper addresses the need for generalization bounds that are computable, non-vacuous, and applicable to any predictor without modifying the target model or its training procedure.

Methodology

The authors propose a framework that decouples the certification of a complex target model from the derivation of the bound itself. The core strategy involves:

1. Surrogate Modeling: Training a simpler "surrogate" model that enjoys tight, computable generalization guarantees. This surrogate is designed to mimic the behavior of the target model.
2. Disagreement Bounding: Measuring the gap between the true risk of the target model ($f$) and the surrogate model ($h$) using a "disagreement" metric evaluated on a small, unlabeled dataset ($U$) not used during training.
3. Risk Aggregation: Combining the tight generalization bound of the surrogate with the disagreement bound to upper-bound the true risk of the target model.

Theoretical Contributions

The paper formalizes three specific disagreement-based bounds depending on the loss function:

• Zero-One Loss (Theorem 5): For the zero-one loss, the disagreement is defined as the empirical frequency of differing predictions between $f$ and $h$ on the unlabeled set. The bound utilizes the binomial tail inversion (Langford, 2005) to upper-bound the true risk gap.
  $$R_D(f) \leq R_D(h) + \text{Bin}(m \cdot d_U^{0-1}(f, h), m, \delta)$$
• Lipschitz-Continuous Losses (Theorem 6): For losses like Huber or logistic loss (which are Lipschitz with respect to the softmax output), the disagreement is measured via the $L_1$ distance between the softmax distributions of the two models. This bound employs the Chernoff bound for variables in the unit interval.
  $$L_D(f) \leq \mathbb{E}_{h \sim Q}[L_D(h)] + 2K_\ell \cdot kl^{-1}\left(\frac{\mathbb{E}_{h \sim Q}[d_U^{K_\ell}(f, h)]}{2}, \frac{\log(1/\delta)}{m}\right)$$
• Non-Lipschitz Losses (Theorem 7): For losses like cross-entropy (which may not be Lipschitz without constraints), the authors propose using a small labeled held-out set to measure the absolute difference in loss values between the models.
  $$L_D(f) \leq \mathbb{E}_{h \sim Q}[L_D(h)] + \lambda_\ell \cdot kl^{-1}\left(\frac{\mathbb{E}_{h \sim Q}[d_L(f, h)]}{\lambda_\ell}, \frac{\log(1/\delta)}{m}\right)$$

Framework Integration

The methodology is agnostic to the specific framework used to certify the surrogate. The authors demonstrate versatility by integrating their disagreement bounds with three distinct theoretical frameworks:

1. Sample Compression: Using algorithms like Pick-To-Learn or Coreset selection (e.g., Random Coreset, k-Center Greedy) to define a surrogate based on a subset of training data.
2. Model Compression: Utilizing techniques like SubLoRA (Subspace Low-Rank Adaptation) and quantization to reduce the description length of the surrogate.
3. PAC-Bayes Theory: Training stochastic neural networks where the surrogate is a distribution over hypotheses, bounded via KL divergence from a prior.

Key Results

The authors empirically evaluated their framework on MNIST, CIFAR10, and the Amazon Polarity dataset (using DistilBERT and GPT2).

• Tightness: The proposed disagreement-based bounds are significantly tighter than existing computable bounds. For instance, on CIFAR10, norm-based bounds were vacuous (values $> 10^{21}$), and partition-based bounds were trivial (approx. 90% error). In contrast, the new bounds achieved non-vacuous results (e.g., 28.13% for PAC-Bayes surrogates on CIFAR10).
• Versatility: The approach successfully certified targets across different architectures (CNNs, ResNets, Transformers) and loss functions (zero-one, cross-entropy, Huber).
• Surrogate Selection: The experiments revealed that the Random Coreset approach often yielded the tightest bounds for sample compression, while SubLoRA was effective for model compression. Interestingly, minimizing the disagreement on the unlabeled set did not always yield the tightest final bound; in some cases, surrogates with the tightest intrinsic generalization bounds (even with higher disagreement) performed better.
• Use Cases:
  • Certification: Providing non-vacuous bounds for standard deterministic models.
  • Distillation: Certifying the risk of a distilled model while minimizing disagreement.
  • Quantization: Bounding the performance gap between a target model and its quantized version, ensuring that compression does not lead to significant performance drops.

Significance and Claims

The paper claims to provide a fully computable, non-vacuous, and assumption-free framework for generalization bounds. Its primary significance lies in:

1. Decoupling Complexity: It allows the certification of complex, arbitrary models by shifting the burden of theoretical guarantees to a simpler, certifiable surrogate.
2. Minimal Data Requirements: The approach requires only a small unlabeled dataset (which is cheaper and easier to obtain than labeled data) to evaluate the disagreement, making it practical for large-scale applications.
3. No Modification Required: Unlike prior works that require pruning, quantization, or architectural changes to the target model to derive bounds, this method applies to the model "as-is."
4. Broad Applicability: The framework is not restricted to specific loss functions or model classes, accommodating zero-one, Lipschitz, and non-Lipschitz losses, as well as deterministic and stochastic predictors.

The authors acknowledge limitations, noting that the tightness of the final bound is inherently dependent on the quality of the surrogate's own generalization guarantee. Furthermore, finding a surrogate that is both certifiable and sufficiently close to a highly complex target remains a challenge. However, the work establishes a new paradigm where generalization guarantees are achieved via "disagreement" rather than direct complexity analysis of the target model.