neural-compression-convergence

Proving bounds on how close a neural image codec with N parameters trained on M images can get to the information-theoretic rate-distortion limit R(D).

Overview

This research package provides rigorous, numerically-verifiable bounds on the gap between the rate achieved by a learned neural image codec and the optimal rate-distortion function R(D). The central result decomposes the gap into three interpretable components:

R_achieved − R(D) = ε_approx(N) + ε_est(M) + ε_opt
                     ↑ finite width    ↑ finite data   ↑ non-convexity

Theoretical Pillars

Pillar	Controls	Bound
PAC-Bayes	Estimation gap (finite M)	O(√((KL + ln(1/δ)) / M))
Rademacher complexity	Estimation gap (hypothesis class richness)	O(√(N/M))
NTK analysis	Optimisation gap (non-convexity)	O(exp(−η·λ_min(Θ)·T))
Approximation theory	Approximation gap (finite N)	O(N^{−1/d_eff})

Main Theorem (Theorem 7)

With probability ≥ 1−δ over M i.i.d. training samples:

R_achieved(w*) − R(D) ≤ C₁·N^{−α} + C₂·√((N + ln(1/δ))/M) + C₃·e^{−η·λ_min(Θ^∞)·T}

where α = 1/d_eff is the effective approximation rate. See proofs/main_theorem.tex for the full proof.

Installation

# From source
git clone git@github.com:drwjkirkpatrick-web/neural-compression-convergence.git
cd neural-compression-convergence
pip install -e ".[dev]"

# Or just install dependencies
pip install -r requirements.txt

Quick Start

from neural_compression_convergence import (
    pac_bayes_bound,
    rademacher_complexity,
    total_gap_bound,
    gap_decomposition,
)

# PAC-Bayes bound on the estimation gap (bits)
pb = pac_bayes_bound(N=1_000_000, M=100_000, delta=0.05)
print(f"PAC-Bayes estimation gap: {pb:.4f} bits")

# Rademacher complexity of the codec hypothesis class
rad = rademacher_complexity(N=1_000_000, M=100_000, depth=4)
print(f"Rademacher complexity:    {rad:.4f}")

# Full gap decomposition
approx, estim, optim = gap_decomposition(N=1_000_000, M=100_000, T=10000)
print(f"Approximation gap: {approx:.4f} bits")
print(f"Estimation gap:    {estim:.4f} bits")
print(f"Optimisation gap:  {optim:.4f} bits")
print(f"Total gap:         {approx+estim+optim:.4f} bits")

Running Tests

pytest -v

All 40+ tests verify:

• PAC-Bayes bound properties (positivity, monotonicity in N/M/δ, √(KL/M) scaling)
• Rademacher complexity (√(N/M) scaling, depth effects, monotonicity)
• NTK optimisation gap (convex/non-convex regimes, width and T dependence)
• Gap decomposition (non-negativity, summation, individual monotonicities)
• Numerical verification utilities (end-to-end sanity checks)
• Edge cases (minimum/large inputs, extreme δ, degenerate architectures)

Package Structure

neural-compression-convergence/
├── neural_compression_convergence/
│   ├── __init__.py          # Public API exports
│   └── core.py              # Core theory (PAC-Bayes, Rademacher, NTK, gap decomposition)
├── tests/
│   └── test_core.py         # Comprehensive test suite (40+ tests)
├── proofs/
│   └── main_theorem.tex     # Formal LaTeX proof of the main convergence theorem
├── pyproject.toml
├── requirements.txt
├── .gitignore
└── README.md

Key Mathematical Content

Rate-Distortion Lagrangian

The neural codec optimises:

L(w) = E[−log P_k(x; w)] + λ · d(x, x̂(x; w))

where P_k is the entropy-coded latent representation and d is the distortion measure.

PAC-Bayes Bound

With probability 1−δ, for any posterior Q over weights:

E_{w∼Q}[L(w)] − E_{w∼Q}[L̂(w)] ≤ √((KL(Q||P) + ln(2√M/δ)) / (2M)) · Δ_L

Rademacher Complexity

For N-parameter ReLU networks with bounded spectral norms:

R_M(F_N) = O(√(N/M))

NTK Convergence

In the infinite-width limit, the NTK Θ makes the loss landscape convex:

L(w_T) − L(w*) ≤ L_0 · exp(−η · λ_min(Θ^∞) · T)

Gap Decomposition

Total gap = Approximation (N^{−α}) + Estimation (√(N/M)) + Optimisation (e^{−ηλT})

License

MIT

Author

Walker Kirkpatrick