📊 statistics

PAC--Bayes Bounds on Quotient Parameter Spaces: Geometry-induced Implicit-Bias Priors

This paper proposes a geometry-induced implicit-bias prior on quotient predictor spaces to eliminate redundant KL divergence from parameter symmetries in overparameterized models, thereby tightening PAC-Bayes generalization bounds and demonstrating significant empirical improvements in Fourier regression and Query-Key attention tasks.

Original authors: Nicola Aladrah, Fabio Anselmi

Published 2026-07-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nicola Aladrah, Fabio Anselmi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Map, the Territory, and the Hidden Compass

Imagine you are trying to teach a robot to recognize cats. You give it a massive notebook full of rules (parameters) to figure out what a cat looks like. In modern machine learning, these notebooks are often "overparameterized," meaning they have way more rules than there are actual cats to learn from. Here's the twist: sometimes, different combinations of rules can produce the exact same result. It's like having two different recipes that both make the exact same chocolate cake. One recipe might say "use 2 cups of flour and 1 cup of sugar," while another says "use 4 cups of flour and 2 cups of sugar." If you double everything, the cake tastes identical. In math terms, these are called "symmetries"—different settings that lead to the same predictor.

To judge if our robot is actually learning or just memorizing, scientists use a tool called a PAC-Bayes bound. Think of this as a "safety certificate" or a speed limit sign. It tells us, with high probability, how well the robot will perform on new, unseen cats. This certificate has two parts: how well the robot did on the training data (the "empirical risk") and a "complexity penalty." The penalty is a measure of how much the robot's final settings differ from a starting guess (the "prior"). If the robot wanders too far from the starting guess in a way that doesn't help, the penalty goes up, and the safety certificate gets worse. The big question is: if we have a million different ways to write the same recipe, should we count all of them as different, or should we realize they are just the same cake?

The Paper's Big Idea: Collapsing the Map

This paper, titled "PAC–Bayes Bounds on Quotient Parameter Spaces," tackles that exact question. The authors, Nicola Aladrah and Fabio Anselmi, argue that when we calculate our safety certificate, we shouldn't be looking at the messy notebook of individual parameters. Instead, we should look at the "quotient space."

Imagine the parameter space as a giant, multi-dimensional landscape. In this landscape, there are entire valleys where every single point represents the exact same predictor (the same cake recipe). The authors suggest we should "squash" these valleys down into single points. This process is called quotienting. By doing this, we remove the "noise" of having multiple ways to write the same thing.

Here is the magic trick: When you squash these valleys, the robot's performance on the training data (the risk) stays exactly the same. However, the complexity penalty (the KL divergence) gets smaller. Why? Because the penalty was previously charging extra fees for the robot choosing one version of a recipe over another identical version. Once you squash the valleys, those fees disappear. The paper proves mathematically that this new certificate is always at least as good as the old one, and often much tighter (better).

The Hidden Compass: Geometry as a Bias

But there's a catch. Just squashing the valleys doesn't tell us which single point to pick as the representative for each recipe. We need a "prior"—a starting guess. The authors introduce a clever second step: using the geometry of the landscape to create a "compass."

They discovered that the way the robot learns (using a method called Stochastic Gradient Descent, or SGD) naturally prefers certain paths over others, even without us telling it to. This is called "implicit bias." It's like walking through a forest; even if you don't have a map, the path of least resistance might naturally lead you to a specific clearing. The authors show that the "volume" of the redundant parameter paths creates a geometric weight. They use this weight to build a new, smarter prior that aligns with where the robot actually wants to go.

Think of it like this: If you have a neutral prior, it's like saying, "I have no idea where you'll end up, so I'll guess randomly." The new "implicit-bias prior" is like saying, "I know the terrain, and the path of least resistance naturally leads to this specific spot, so I'll guess there."

What They Found: It Depends on the Terrain

The authors tested this idea in two different "forests" (experiments) to see if their new compass actually made the safety certificate tighter.

The Fourier-Hadamard Experiment: They used a model where the symmetry was very strong and spread out across many dimensions (like a forest with many parallel paths). Here, the results were dramatic. By using their geometry-induced prior, they reduced the "complexity penalty" (the KL divergence) by 40.69%. This made the final safety certificate (the bound) 21.40% tighter. In plain English, the certificate became much more confident and precise because they stopped counting the same recipe variations as different mistakes.
The Query-Key Attention Experiment: They tested this on a model used for attention mechanisms (like those in large language models). Here, the symmetry was more limited. The improvement was much smaller: the complexity penalty dropped by only 1.09%, and the certificate improved by 0.43%.

Why the difference? The paper explains that the "implicit bias" only helps if the robot's final path is actually aligned with the geometry the authors predicted. In the first experiment, the robot's path matched the geometry perfectly, so the new prior was a great guess. In the second, the match was weaker, so the benefit was smaller.

The Takeaway

The paper doesn't claim to have solved machine learning or to have found a magic bullet that works everywhere. Instead, it offers a precise, mathematical way to clean up our safety certificates. It shows that if we stop counting the same predictor multiple times (by using quotient spaces) and if we use the natural geometry of the learning process to pick a smarter starting guess, we can get a much clearer picture of how well our models will actually perform.

The key finding is conditional: the new method works best when the "implicit bias" of the learning algorithm aligns with the geometry of the problem. When it does, the safety certificate tightens significantly, giving us more confidence in our overparameterized models. When it doesn't, the improvement is modest, but the method never makes things worse. It's a tool for making our math more honest about what the model is actually learning, rather than just how it's written down.

Technical Summary: PAC–Bayes Bounds on Quotient Parameter Spaces

Problem Statement

Modern overparameterized machine learning models frequently exhibit continuous parameter symmetries, where distinct parameter vectors define the exact same predictor function. For instance, in models with rescaling symmetries, different combinations of weights can yield identical input-output mappings. Standard PAC–Bayesian analysis, which bounds the population risk of a randomized predictor using the Kullback–Leibler (KL) divergence between a data-dependent posterior ( $Q$ ) and a sample-independent prior ( $P$ ), operates directly on the parameter space.

This approach introduces a fundamental flaw in the presence of symmetries: the KL divergence term ( $KL(Q \parallel P)$ ) penalizes discrepancies in how the prior and posterior distribute probability mass among equivalent parameter representations (i.e., within the same symmetry orbit), even though these differences have no effect on the predictor's performance or risk. Consequently, the complexity term mixes genuine predictor-level complexity with "representational complexity" arising solely from non-identifiable degrees of freedom, potentially leading to loose generalization certificates.

Methodology

The paper proposes a two-stage methodological framework to address this issue:

Quotient Space Formulation:
The authors reformulate the PAC–Bayesian analysis on the quotient parameter space ( $U = B/\mathcal{G}$ ), where $B$ is the parameter space and $\mathcal{G}$ is the symmetry group. In this space, all parameters representing the same predictor are identified as a single element (an orbit).
- Risk Preservation: The authors prove that pushing the prior and posterior forward through the quotient map preserves the empirical and population Gibbs risks. The expected risk remains identical whether computed over the original parameters or the quotient predictors.
- Complexity Reduction: The KL divergence on the quotient space is shown to be less than or equal to the KL divergence on the original parameter space. Specifically, $KL(Q_b \parallel P_b) = KL(Q_u \parallel P_u) + \Delta_\phi$ , where $\Delta_\phi$ represents the non-negative KL divergence within the symmetry orbits. By moving to the quotient, this "within-orbit" discrepancy is removed, tightening the complexity term without altering the risk bounds.
Geometry-Induced Implicit-Bias Priors:
While quotienting removes redundancy, it does not inherently dictate which prior to use on the quotient space. The authors introduce a canonical prior derived from the geometry of the symmetry breaking.
- Drawing on previous geometric analysis of stochastic learning, they utilize the volume correction associated with symmetry breaking. This correction arises from the geometry of the parameter manifold and the choice of a symmetry-breaking slice (a representative set for each orbit).
- This geometric factor defines an implicit-bias prior ( $P_{IB}$ ) on the quotient space. This prior is data-independent but reflects the model's architecture and the implicit bias induced by optimization dynamics (e.g., SGD).
- The paper derives a prior-improvement criterion: The implicit-bias prior yields a tighter PAC–Bayes certificate than a neutral reference prior if and only if the KL divergence between the learned posterior and the implicit-bias prior is smaller than that between the posterior and the neutral prior. This condition is explicitly calculated as $\Delta KL = \mathbb{E}_{Q}[L_\chi] + \log Z_\chi$ , where $L_\chi$ is the geometric loss derived from the symmetry-breaking map.

Key Contributions

General PAC–Bayesian Reduction: The paper establishes that for any predictor-preserving parameter symmetry, applying the PAC–Bayes inequality on the quotient space preserves risk terms while strictly reducing (or maintaining) the complexity term. This separates predictor-level complexity from representational redundancy.
Construction of Implicit-Bias Priors: The authors construct a specific, data-independent prior on the quotient space that encodes the geometric volume of equivalent parameterizations. This prior captures the implicit bias of the model architecture without requiring explicit regularization during training.
Exact Improvement Criterion: The paper provides a precise, verifiable condition ( $\Delta KL \leq 0$ ) under which the geometry-induced prior improves the generalization bound compared to a neutral prior. This clarifies that the benefit of the implicit-bias prior is conditional on the alignment between the learned posterior and the geometric structure.

Experimental Results

The authors validate their theory using two experiments with ordinary Stochastic Gradient Descent (SGD) and no explicit regularizers:

Sparse Fourier Regression (Hadamard Parameterization):
- Setup: A regression task using a Hadamard parameterization ( $w = a \odot c$ ) with a 64-dimensional cosine basis.
- Findings: Replacing a neutral Gaussian prior with the implicit-bias prior on the quotient space reduced the mean KL divergence by 40.69% (from ~585.6 to ~347.3). Consequently, the mean PAC–Bayes certificate tightened by 21.40%.
- Condition: The improvement was consistent across all tested prior scales, indicating the learned posterior was well-aligned with the geometry-induced prior.
Query–Key Attention:
- Setup: A single-head attention model where the symmetry acts on the Query and Key matrices.
- Findings: The improvement was significantly smaller. The mean KL divergence decreased by only 1.09%, and the certificate tightened by 0.43%.
- Condition: The improvement was scale-dependent. For small prior scales ( $s_0 < 1$ ), the implicit-bias prior did not improve the bound (positive $\Delta KL$ ). Improvement only occurred at larger scales. The authors attribute this to the fact that the symmetry correction in this model acts on a smaller subset of parameters (the head dimension) compared to the total parameter count, making the relative impact on the total KL divergence smaller.

Significance and Claims

The paper claims to provide a rigorous theoretical framework for handling parameter symmetries in PAC–Bayesian analysis. Its primary significance lies in demonstrating that:

Redundancy is a source of looseness: Ignoring parameter symmetries leads to unnecessarily loose generalization bounds due to the inclusion of non-predictive complexity in the KL term.
Geometry is a prior: The geometric structure of the parameter space, specifically the volume of symmetry orbits, naturally induces a preference (implicit bias) that can be formalized as a prior.
Conditional Tightening: The resulting certificates are tighter exactly when the learned posterior aligns with this geometry-induced prior. The paper does not claim that this prior is universally optimal or that it guarantees better generalization in all cases; rather, it provides a mechanism to construct a prior that can yield tighter bounds when the posterior distribution matches the model's implicit geometric bias.

The work suggests a path toward "inverse learning" of implicit bias, where model architectures could be designed to induce priors that are well-matched to specific classes of posteriors, though the authors note this as a direction for future work rather than a current contribution.