Heating up decision boundaries: isocapacitory saturation, adversarial scenarios and generalization bounds

Bogdan Georgiev, Lukas Franken, Mayukh MukherjeeICLR 2021

Introduction

Deep neural networks are notoriously sensitive to adversarial attacks—small, calculated perturbations that can drastically flip a model's prediction. To understand why these vulnerabilities exist, researchers often study the decision boundary: the high-dimensional "fence" separating different classes of data.

Existing methods for analyzing these boundaries typically rely on distance-based metrics, such as calculating how far a data point is from the nearest error region. However, these metrics act as "coarse lenses." A decision boundary might be far away on average but remain extremely jagged or "spiky," leaving it highly susceptible to noise.

Visualization of a decision boundary 'heating up' over time.

To address this, this paper introduces a novel "heat-diffusion" framework. The authors seek a more sensitive, "soft" geometric measure capable of detecting the fine-scale complexity that distance metrics miss, ultimately linking this geometry to a model's ability to generalize to unseen data.

Methodology: The Thermal Analogy

The core of the paper's approach relies on a "thermal" analogy. Imagine placing a heat source directly on the decision boundary and measuring how much of that heat reaches a specific data point within a given timeframe.

Brownian Motion & Feynman-Kac Duality

Solving the heat equation directly in high-dimensional spaces is computationally intractable. To bypass this, the authors utilize a mathematical shortcut known as the Feynman-Kac duality. Under this principle, the probability of "heat" reaching a specific point is mathematically equivalent to the probability of a Brownian motion path (a random walk) starting at that point and eventually hitting the boundary.

Diagram of a Brownian motion path starting at point x and hitting the decision boundary.

Isocapacitory Saturation ($\tau$)

The paper introduces a key novel metric called Isocapacitory Saturation, denoted as $\tau$. This metric compares the volume of the "error set" (the region where the model predicts incorrectly) to the "heat" it emits.

  • Low $\tau$: Suggests a "tame," thick boundary, akin to a flat, smooth wall.
  • High $\tau$: Indicates a "spiky" or "wiggly" boundary, similar to a dense forest of needles. This type of boundary has a high surface area relative to its volume, making it highly complex.

By using these hitting probabilities, the authors prove that "noise-stable" models can be compressed into smaller, simpler versions. Mathematically, this implies that models with smoother boundaries will generalize better to unseen data.

Key Insights and Results

The researchers evaluated their methods across several datasets, including MNIST, CIFAR-10, and planar 2D toy datasets used to visualize how boundaries "heat up" over time.

The Persistence of "Wiggles"

Previous research suggested that adversarial defense training (such as Projected Gradient Descent, or PGD) "flattens" the decision boundary. This paper reveals a more nuanced reality: while the boundary might appear flatter on a macro scale (isoperimetric saturation), it remains highly complex and "wiggly" on a fine scale (isocapacitory saturation). In CIFAR-10 evaluations, adversarial training improved overall flatness but failed to significantly reduce the "wiggliness" ($\tau$). This explains why models often remain susceptible to certain types of noise even after rigorous defense training.

Sensitivity and Generalization

Heat diffusion proves to be a much more sensitive probe than straight-line distance. Brownian particles naturally "find" thin spikes or hidden pockets in the boundary that traditional distance calculations ignore.

Crucially, there is a direct link between the "smoothness" of the boundary—as measured by heat—and the model's generalization error. The authors derived new generalization bounds showing that lower "heat quantities" at sample points lead to significantly tighter bounds on expected loss. If a model is stable under Brownian perturbations, it is fundamentally less complex and more likely to perform well on new data. Furthermore, they demonstrated that models with these controlled, tame boundaries can be compressed to a logarithmically smaller number of parameters without sacrificing performance.

Limitations and Future Work

While the heat-diffusion framework offers powerful new insights, it comes with challenges:

  • Computational Intensity: Simulating thousands of Brownian paths for every single data point is computationally expensive, particularly in high-dimensional spaces.
  • The "Curse of Dimensionality": Although hitting probabilities effectively reduce the problem to lower dimensions, sampling in extremely high-dimensional spaces remains a hurdle for numerical stability.
  • Transferring Bounds: The generalization bounds established in the paper are initially derived for the compressed version of the model. Transferring these bounds back to the original, full-sized neural network requires complex techniques that the authors highlight as an important direction for future research.

Summary updated

BibTeX
@inproceedings{georgiev2021heating,
  author = {Bogdan Georgiev and Lukas Franken and Mayukh Mukherjee},
  title = {{Heating up decision boundaries: isocapacitory saturation, adversarial scenarios and generalization bounds}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
}
Figure