Convolutional Relative-Gradient Experiments

Reproducible experiments translating relative-gradient optimization to periodic invertible convolutions.

This is not a new invertible-convolution architecture. The periodic layer, Fourier block decomposition, exact log-determinant, and blockwise inverse are from Hoogeboom, van den Berg, and Welling (2019). Natural and relative optimization of convolutional filters also has substantial earlier precedent in convolutive ICA and blind deconvolution. The repository's role is to connect these lines of work in normalizing-flow notation, verify the implementation, and provide controlled optimizer experiments. See the prior-art and novelty audit.

This repository accompanies the research note “Jacobians, Global Invertibility, and a Convolutional Relative Gradient”. It contains:

• exact determinant, Fourier-factorization, and gradient checks;
• linear-Gaussian density-model benchmarks;
• matched periodic and non-periodic zero-padded data-generating processes;
• full circular, compact circular, and causal Toeplitz model families;
• ordinary projected-gradient and relative/natural-gradient training;
• a five-seed conditioning sweep;
• a 1,024-dimensional multichannel 2D FFT/autodiff scale-up;
• tutorial-quality commented code for the main frequency-block experiment;
• committed raw JSON/CSV results and print-ready reports.

The original algebraic and linear-density experiments use only the Python standard library. The optional image-shaped scale-up uses pinned NumPy and PyTorch versions; it runs on CPU and does not require a GPU or external data.

TL;DR

The modeling benchmarks support four conclusions.

1. Relative optimization reaches the same likelihood optimum faster. In the matched periodic benchmark it reaches 99% of the improvement in a median of 3 steps instead of 5. For the exactly specified compact kernel the comparison is 2 steps instead of 4.
2. The advantage grows sharply with conditioning. At true condition number 19, the ordinary method reaches the 400-iteration cap, while the relative method converges in 15 iterations. Median wall time is 1.96 s versus 0.145 s on the reference run.
3. Boundary conditions are a modeling issue, not an optimizer issue. On data generated by a zero-padded causal convolution, circular models retain approximately 0.142-0.145 population excess NLL and 0.0428 leading-edge variance MAE. The causal Toeplitz model reduces those to 0.0057 and 0.0042.
4. The result survives a 2D multichannel scale-up. On a 4 x 16 x 16 flow (1,024 dimensions), the ordinary method reaches its 200-step ceiling while the relative method converges in a median of 16 iterations. Median reference wall time is 13.47 s versus 1.36 s.

The compact-support result uses the exact natural gradient induced by the relative metric on the supported kernel coordinates. A naive full relative step followed by truncation is not guaranteed to be a descent direction, because compact support is not closed under convolution.

These are controlled synthetic results, not a comparison with Hoogeboom et al.'s complete flow architecture or Adamax training. They establish neither a new convolutional layer nor a first convolutional natural-gradient algorithm.

Reproduce everything

make test
make reproduce

Or run the two experiment suites directly:

python3 experiments/algebraic_checks.py > results/algebraic_checks.json
python3 experiments/modeling_benchmarks.py \
  --dimension 24 \
  --samples 2048 \
  --steps 250 \
  --seeds 5 \
  --output results/modeling_benchmark.json

modeling_benchmarks.py automatically gives the conditioning sweep a 400-iteration ceiling.

Reproduce the FFT/autodiff scale-up

Create an isolated environment and install the two pinned dependencies:

uv venv --python 3.11
uv pip install --python .venv/bin/python -r requirements-scaleup.txt
make scaleup

The central implementation is experiments/tutorial_fft_image_flow.py. It is written as executable research documentation: descriptive variable names, section-level docstrings, and comments explaining the determinant, frequency-block relative update, projection normalization, line search, and evaluation metrics. See SCALEUP.md for a guided code walk-through.

Scale-up result

The true 4-channel circular whitening convolution has condition number 17.91. Each train/test split contains 512 synthetic 16 x 16 images, and medians are reported across three fixed seeds.

Optimizer	Total iterations	Steps to shared 99% target	Test NLL / dimension	Precision error	Inverse error	Wall time
Ordinary projected	200 (cap)	67	1.432003	0.1462	3.23e-16	13.47 s
Relative	16	8	1.430360	0.0900	3.48e-16	1.36 s

This is a 12.5x reduction in total iterations and a 9.88x reduction in reference wall time. The FFT relative direction is independently checked against the explicit dense formula P(G A^T) A on a tiny multichannel image.

Experimental design

Every fitted model is a linear Gaussian normalizing flow

z = A x,     z ~ Normal(0, I)
NLL(A) = 0.5 tr(A S A^T) - log|det A| + constant

where S is the empirical covariance. This deliberately small setting makes the likelihood, inverse, Jacobian determinant, population optimum, and condition number independently measurable.

The two true whitening transforms use the same kernel [1.25, -0.62, 0.24]:

• periodic: the kernel defines a full circular matrix;
• non-periodic: the kernel defines a lower-triangular causal Toeplitz matrix, equivalent to zero padding at the leading boundary.

Each train/test split contains 2,048 samples in 24 dimensions. Results are aggregated across seeds 0-4.

Key results

Benchmark/model	Method	Excess NLL	Steps to 99%	Median iterations	Edge variance MAE
Periodic/full circular	Ordinary	0.00330	5	33	0.00508
Periodic/full circular	Relative	0.00330	3	7	0.00508
Periodic/compact circular	Ordinary	0.000333	4	26	0.00508
Periodic/compact circular	Relative metric	0.000333	2	9	0.00508
Non-periodic/full circular	Ordinary	0.145	6	32	0.0428
Non-periodic/full circular	Relative	0.145	3	7	0.0428
Non-periodic/causal Toeplitz	Ordinary	0.00570	5	41	0.00422
Non-periodic/causal Toeplitz	Relative	0.00570	3	10	0.00422

All likelihood values are per 24-dimensional observation, not per dimension. Ordinary and relative methods agree at the family optimum to the precision shown. Timings are reference timings from one machine and should be interpreted as an internal comparison, not as a cross-machine performance claim.

Repository map

experiments/
  algebraic_checks.py          determinant and convolution geometry checks
  modeling_benchmarks.py       density benchmarks and conditioning sweep
  test_modeling_benchmarks.py  numerical unit tests
  tutorial_fft_image_flow.py   commented 2D multichannel FFT/autodiff scale-up
  test_tutorial_fft_image_flow.py  dense-reference and FFT tests
results/
  modeling_benchmark.json      complete trajectories and variance profiles
  modeling_benchmark*.csv      flat per-run and aggregate tables
  conditioning_sweep*.csv      conditioning results
  fft_image_flow.json/.csv     scale-up trajectories and scalar metrics
report/
  algebraic-report.html/.pdf   original 12-page visual research note
  empirical-report.html/.pdf   follow-up modeling evidence

Scope

These experiments establish exact algebraic identities and give controlled modeling evidence, including an autodiff implementation on image-shaped 1,024-dimensional fields. They do not yet establish an advantage on nonlinear image flows or natural-image datasets. The next scale-up is to insert the frequency-block update into a nonlinear flow architecture and test standard image-density benchmarks.

The historical scope is equally important. The FFT layer operations reproduce Hoogeboom et al.'s periodic convolution. The relative update specializes the 2020 matrix method to that established layer, while older convolutive-ICA and blind-deconvolution papers provide strong precedent for natural/relative optimization of FIR filters. Accordingly, this repository should be cited as a reproducible synthesis and implementation, not as proof of architectural or algorithmic priority.

References

• Gresele, Fissore, Javaloy, Schölkopf, and Hyvärinen (2020), Relative gradient optimization of the Jacobian term in unsupervised deep learning.
• Hoogeboom, van den Berg, and Welling (2019), Emerging Convolutions for Generative Normalizing Flows.
• Amari, Douglas, Cichocki, and Yang (1997), Multichannel Blind Deconvolution and Equalization Using the Natural Gradient.
• Bronstein, Bronstein, Zibulevsky, and Zeevi (2004), Fast Relative Newton Algorithm for Blind Deconvolution of Images.
• Gunther and Moon (2006), A Natural Gradient Algorithm for Multichannel Blind Deconvolution: Frequency Domain Criteria and Time Domain Updates.
• Papamakarios et al. (2021), Normalizing Flows for Probabilistic Modeling and Inference.

License

MIT. See LICENSE.