Abstract
The PAC-Bayesian framework provides a robust theoretical foundation for deriving generalization guarantees in machine learning. While traditionally reliant on Kullback-Leibler (KL) divergence, this study explores the use of $\chi^2$-divergence to construct optimal posteriors for stochastic classifiers, specifically in the context of Support Vector Machines (SVMs). We derive closed-form solutions and fixed-point equations for various distance functions, demonstrating that $\chi^2$-based approaches offer significant computational advantages and natural sparsity compared to KL-based methods and standard cross-validation.
Introduction
A central challenge in machine learning is balancing model complexity with generalization performance. While techniques like Cross-Validation (CV) are widely used for hyperparameter tuning, they are computationally intensive and lack formal mathematical guarantees. The PAC-Bayesian framework addresses this by providing high-probability bounds on the true risk of a "posterior" distribution over models. However, the standard KL-divergence approach often leads to dense distributions and complex optimization landscapes. This research investigates whether $\chi^2$-divergence can provide a more efficient and sparse alternative.
Theoretical Framework
The authors analyze three primary distance functions ($\phi$) to measure the discrepancy between empirical and true risk: linear, squared, and KL-distance. Each function presents different optimization characteristics.
As shown in Table 1, the linear distance function ($\phi_{\text{lin}}$) is convex and yields a closed-form solution for the global minimum. The squared distance ($\phi_{\text{sq}}$) is shown to be quasi-convex under specific conditions, while the traditional KL-distance remains a non-convex problem, often requiring more complex solvers.
Computational Methodology
To solve for the optimal posterior, the study introduces Fixed Point (FP) equations tailored to the PAC-Bayesian bounds. This approach is compared against general-purpose solvers like Ipopt.
The computational analysis (Table 2) reveals that for $\phi_{\text{lin}}$, the global minimum is identified analytically, obviating the need for iterative solvers. For $\phi_{\text{sq}}$, the FP approach consistently matches solver outputs, while for $kl$, it identifies unique stationary points even when general solvers may struggle with multiple local minima or convergence errors at larger scales.
Experimental Evaluation
The proposed methods were evaluated on nine UCI datasets, ranging from linearly separable (e.g., Banknote, Mushroom) to highly inseparable (e.g., Spambase, Bupa).
Key Findings
- Computational Speed: The PAC-Bayesian procedure using $\chi^2$-divergence is over 10 times faster than 5-fold Cross-Validation. Tuning times were reduced from hours to minutes (e.g., 20 to 300 seconds).
- Sparsity: Unlike the exponential decay of weights in KL-based systems, $\chi^2$ posteriors exhibit linear decay and natural "subset support." Models with empirical risk above a certain threshold receive zero weight, simplifying the resulting ensemble.
- Generalization: While CV-tuned deterministic classifiers often achieve slightly lower test errors, the PAC-Bayesian stochastic classifiers provide a quantifiable safety margin through their theoretical bounds.
Conclusion
This work demonstrates that $\chi^2$-divergence is a powerful alternative to KL-divergence in the PAC-Bayesian framework. It enables the derivation of optimal posteriors that are both sparse and computationally efficient to compute. Future research will focus on relaxing the uniform prior assumption and extending these bounds to high-dimensional data regimes.
Summary updated