Abstract
Deep Probabilistic Programming (DPP) enables the construction of powerful models based on recursive computation, optimized through deep-learning techniques. This paper introduces a framework for representing and learning flexible PAC-Bayes bounds as stochastic programs within the DPP paradigm. By leveraging the compositionality of DPP, we derive higher-order generalization bounds that serve as principled training objectives for complex probabilistic programs. We define a novel class of "second-order complexity" bounds based on learned measures of model failure and demonstrate how these can be efficiently optimized using variational techniques. Our framework is evaluated across single- and multi-task settings, including synthetic benchmarks and psychiatric genomics data, showing improved generalization prediction and performance in transfer-learning scenarios.
Introduction
In modern machine learning, the goal is to develop models that generalize effectively from training data to unseen examples. Generalization bounds provide the mathematical guarantees for this behavior, typically establishing an upper limit on the expected drop in performance. However, traditional bounds—such as those derived from PAC-Bayes theory—often rely on rigid, pre-defined assumptions about model complexity. These are frequently measured by the divergence between a posterior and a fixed prior distribution.
In the context of Deep Probabilistic Programming (DPP), where models are often recursive and highly non-linear, standard bounds become mathematically intractable or too loose to provide meaningful guidance. This research addresses the gap by reimagining generalization bounds not as static formulas, but as "first-class" stochastic programs that can be learned and optimized alongside the models themselves.
Methodology: Bounds as Programs
The Stochastic Type System
The core of this framework is a Stochastic Type System that treats inference algorithms, models, and generalization bounds as the same category of object: stochastic programs. This unified perspective allows for "compositionality," where complex bounds are constructed from simpler components.
Higher-Order (h-o) Generalization Bounds
We define higher-order bounds as functions that return other functions acting as generalization guarantees. This abstraction naturally encompasses various learning paradigms:
- Single-task learning: Standard generalization guarantees.
- Transfer learning: Moving knowledge from a source task to a target task.
- Meta-learning: Learning a shared prior across a distribution of tasks.
Second-Order Complexity
The most significant innovation is the introduction of "second-order complexity" bounds. Rather than using a fixed mathematical penalty for complexity (like a standard KL-divergence), we train a separate "generalization classifier" ($g$). This auxiliary model analyzes the features of a trained classifier to predict its likelihood of failure on new data. By replacing an arbitrary prior with this learned complexity measure, the bound becomes data-dependent and significantly more adaptive.
Variational PAC-Bayes Objectives
To ensure these bounds are practical for deep learning, we derive variational forms of the PAC-Bayes objectives. Because the KL-divergence is often impossible to calculate for complex DPPs, these variational approximations allow the bounds to be optimized efficiently using standard gradient-based optimization tools.
Experimental Evaluation
Synthetic 2D Data
To test the framework in a controlled environment, we utilized synthetic datasets featuring multi-scale decision boundaries and varying levels of label noise. The goal was to determine how well the bounds could predict actual test-set error. The results were striking: the novel second-order complexity bound achieved a correlation of $r = 0.46$ with true test error, more than doubling the performance of traditional PAC-Bayes bounds ($r = 0.22$).
Psychiatric Genomics (PsychENCODE)
We applied the framework to real-world RNA-Seq gene expression data from the PsychENCODE project, which includes samples from patients with Schizophrenia (SCZ), Bipolar Disorder (BPD), and Autism Spectrum Disorder (ASD).
In this multi-task setting, the DPP-based meta-learning approach outperformed traditional Gaussian models. The framework proved particularly effective at "transferring" biological insights between disorders—for instance, using a prior learned from Schizophrenia data to improve the accuracy of an Autism classifier. This reflects the shared underlying biological architecture of these conditions and demonstrates the framework's utility in high-stakes, small-sample-size domains.
Discussion and Future Work
Insights
By treating bounds as programs, we move toward a more flexible theory of generalization. The "aha moment" of this research is the realization that a bound can be "thunked" (suspended) and "sampled" (executed) just like the model it describes. Learning the complexity measure via a meta-model of failure allows the system to recognize overfitting patterns that traditional formulas might miss.
Limitations
Current theoretical validity relies on certain independence assumptions, often requiring auxiliary data or hold-out sets. Future iterations may incorporate Differential Privacy techniques to relax these constraints. Additionally, while this work focuses on discrete program settings, extending the framework to continuous spaces (via Quasi-Borel spaces) is a priority for applications in fields like physics and finance. Finally, increasing the complexity of the generalization classifier ($g$) could lead to even tighter, more predictive bounds.
Summary updated