Optimal Posteriors for Chi-squared Divergence based PAC-Bayesian Bounds and Comparison with KL-divergence based Optimal Posteriors and Cross-Validation Procedure

Puja Sahu, Nandyala HemachandraarXiv 2020 · arXiv

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.

Table 1: Theoretical properties of distance functions, including convexity and global minima/fixed point formulations.

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.

Table 2: Computational comparison of solver outputs and analytical solutions for different distance functions.

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

Abstract

We investigate optimal posteriors for recently introduced \cite{begin2016pac} chi-squared divergence based PAC-Bayesian bounds in terms of nature of their distribution, scalability of computations, and test set performance. For a finite classifier set, we deduce bounds for three distance functions: KL-divergence, linear and squared distances. Optimal posterior weights are proportional to deviations of empirical risks, usually with subset support. For uniform prior, it is sufficient to search among posteriors on classifier subsets ordered by these risks. We show the bound minimization for linear distance as a convex program and obtain a closed-form expression for its optimal posterior. Whereas that for squared distance is a quasi-convex program under a specific condition, and the one for KL-divergence is non-convex optimization (a difference of convex functions). To compute such optimal posteriors, we derive fast converging fixed point (FP) equations. We apply these approaches to a finite set of SVM regularization parameter values to yield stochastic SVMs with tight bounds. We perform a comprehensive performance comparison between our optimal posteriors and known KL-divergence based posteriors on a variety of UCI datasets with varying ranges and variances in risk values, etc. Chi-squared divergence based posteriors have weaker bounds and worse test errors, hinting at an underlying regularization by KL-divergence based posteriors. Our study highlights the impact of divergence function on the performance of PAC-Bayesian classifiers. We compare our stochastic classifiers with cross-validation based deterministic classifier. The latter has better test errors, but ours is more sample robust, has quantifiable generalization guarantees, and is computationally much faster.
BibTeX
@misc{sahu2020optimal,
  author = {Puja Sahu and Nandyala Hemachandra},
  title = {{Optimal Posteriors for Chi-squared Divergence based PAC-Bayesian Bounds and Comparison with KL-divergence based Optimal Posteriors and Cross-Validation Procedure}},
  year = {2020},
  eprint = {2008.07330},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2008.07330},
}
Figure