# PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoders

arXiv: https://arxiv.org/abs/2512.12905 · HTML: https://mlsanity.com/paper/2512.12905/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 55 references that are in the map.
- First posted on arXiv 15 Dec 2025.

## Builds on (most cited first, 22 of 22)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Variational Autoencoders for Collaborative Filtering](https://mlsanity.com/paper/1802.05814/) (2018)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Are We Really Making Much Progress? A Worrying Analysis of Recent Neural Recommendation Approaches](https://mlsanity.com/paper/1907.06902/) (2019)
- [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015)
- [Embarrassingly Shallow Autoencoders for Sparse Data](https://mlsanity.com/paper/1905.03375/) (2019)
- [PAC-Bayesian Theory Meets Bayesian Inference](https://mlsanity.com/paper/1605.08636/) (2016)
- [SimpleX: A Simple and Strong Baseline for Collaborative Filtering](https://mlsanity.com/paper/2109.12613/) (2021)
- [Generalization Bounds: Perspectives from Information Theory and PAC-Bayes](https://mlsanity.com/paper/2309.04381/) (2023)
- [PAC-Bayes unleashed: generalisation bounds with unbounded losses](https://mlsanity.com/paper/2006.07279/) (2020)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022)
- [Towards a Better Understanding of Linear Models for Recommendation](https://mlsanity.com/paper/2105.12937/) (2021)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Improved PAC-Bayesian Bounds for Linear Regression](https://mlsanity.com/paper/1912.03036/) (2019)
- [PAC-Bayes-Chernoff bounds for unbounded losses](https://mlsanity.com/paper/2401.01148/) (2024)
- [Bayesian methods for low-rank matrix estimation: short survey and theoretical study](https://mlsanity.com/paper/1306.3862/) (2013)
- [From bilinear regression to inductive matrix completion: a quasi-Bayesian analysis](https://mlsanity.com/paper/2210.15290/) (2022)
- [It's Enough: Relaxing Diagonal Constraints in Linear Autoencoders for Recommendation](https://mlsanity.com/paper/2305.12922/) (2023)

## Built on by (most cited first, 3 of 3)

- [Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds](https://mlsanity.com/paper/2601.08100/) (2026)
- [Generalizing Linear Autoencoder Recommenders with Decoupled Expected Quadratic Loss](https://mlsanity.com/paper/2603.07402/) (2026)
- [A PAC-Bayesian View of Generalisation for Physics-Informed Machine Learning](https://mlsanity.com/paper/2605.26341/) (2026)

## Abstract (arXiv)

Linear Autoencoders (LAEs) have shown strong performance in state-of-the-art recommender systems. However, this success remains largely empirical, with limited theoretical understanding. In this paper, we investigate the generalizability -- a theoretical measure of model performance in statistical learning -- of multivariate linear regression and LAEs. We first propose a PAC-Bayes bound for multivariate linear regression, extending the earlier bound for single-output linear regression by Shalaeva et al., and establish sufficient conditions for its convergence. We then show that LAEs, when evaluated under a relaxed mean squared error, can be interpreted as constrained multivariate linear regression models on bounded data, to which our bound adapts. Furthermore, we develop theoretical methods to improve the computational efficiency of optimizing the LAE bound, enabling its practical evaluation on large models and real-world datasets. Experimental results demonstrate that our bound is tight and correlates well with practical ranking metrics such as Recall@K and NDCG@K.