Research map / Learning theory and algorithms / Kernels and regression theory

PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoders

NeurIPS 2025 · Learning theory and algorithms › Kernels and regression theory · approach: PAC-Bayes bounds · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends Shalaeva's single-output PAC-Bayes bound to multivariate linear regression and linear autoencoders (LAEs like EASE) on bounded recommendation data, with closed-form optimal posterior and a reduced-complexity computation.

Problem

Theoretical generalization guarantees for multivariate linear regression and linear autoencoder recommenders (LAEs), which perform strongly empirically but lack theory; existing PAC-Bayes linear regression bounds handle only single-output Gaussian data and are costly to optimize for large models.

Approach

Generalizes Shalaeva's Gaussian PAC-Bayes bound to multi-output data with dependent outputs, proves a dominated-convergence condition for convergence, reinterprets LAEs under a relaxed MSE as constrained multivariate regression on bounded data, and uses Gaussian priors/posteriors to get a closed-form optimal posterior and an O(n^3) computation instead of O(n^4).

Key results

• On ML 20M, Netflix and MSD, the PAC-Bayes bound RH is within 3 times LH across all EASE models (gamma 50 to 5000), versus up to 10x in Dziugaite and Roy's bound.
• Across datasets, models with lower LH/RH generally have higher Recall@50 and NDCG@100; e.g., ML 20M gamma=2000 gives Recall@50 0.3510 and NDCG@100 0.4487 with RH 119.34.
• Bound computation uses a closed-form optimal Gaussian posterior and reduces the zero-diagonal case from O(n^4) to O(n^3).

Measured effects reported in the paper

Surprising findings

• The best bound values (LH/RH) on MSD occur at gamma=1000 while the best Recall@50/NDCG@100 occur at gamma=500, a minor misalignment.

Limitations

• Upper bound on Psi replaces the m-dependent term with a looser m-independent one for the computed RH, and the zero-diagonal case uses a simplified bound.
• Bound computed only with a fixed prior scale sigma=0.001 and grid over lambda; optimization of lambda, pi, rho jointly is intractable and not done.
• Requires Sigma_hh from a population distribution, which is an assumption when the true distribution is unknown; relaxed MSE differs from ranking metrics actually used.

Experimental setup

Datasets: MovieLens 20M Netflix MSD

Benchmarks: MovieLens 20M Netflix MSD

Metrics: PAC-Bayes bound LH and RH Recall@50 NDCG@100

Baselines: EASE EDLAE ELSA Dziugaite and Roy non-vacuous bound

Builds on: Shalaeva PAC-Bayes bound Alquier PAC-Bayes bound Germain et al. linear regression PAC-Bayes Dziugaite and Roy PAC-Bayes bounds EASE

Closest papers by meaning

• Block-Sample MAC-Bayes Generalization Bounds (ICLR 2026 · similarity 0.87)
• Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound (NeurIPS 2024 · similarity 0.86)
• A Limitation of the PAC-Bayes Framework (NeurIPS 2020 · similarity 0.86)
• Improved PAC-Bayesian Bounds for Linear Regression (AAAI 2020 · similarity 0.86)
• Generalization Bounds for Causal Regression: Insights, Guarantees and Sensitivity Analysis (ICML 2024 · similarity 0.84)
• Learning via Surrogate PAC-Bayes (NeurIPS 2024 · similarity 0.84)