PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoders

AI summary

Authors: Ruixin Guo, Ruoming Jin, Xinyu Li (Kent State University); Yang Zhou (Auburn University) arXiv: 2512.12905v1 [stat.ML], 15 Dec 2025

Overview

Research area: Statistical learning theory (PAC-Bayes generalization bounds) applied to multivariate (multi-output) linear regression and to Linear Autoencoders (LAEs) used in recommender systems.

Technical level: Advanced. The paper is written in the language of measure-theoretic probability, matrix analysis, and PAC-Bayes theory, with most results stated as theorems, lemmas, propositions and formal assumptions.

Scope: The paper derives, adapts, and makes computationally tractable a PAC-Bayes generalization bound for LAE-based recommenders such as EASE, and reports that the bound correlates with ranking metrics on real-world datasets.

What This Paper Is About

Linear autoencoders like EASE and EDLAE perform strongly in recommender systems, but almost all of that evidence is empirical — there is little theory explaining why they generalize. The authors build a PAC-Bayes bound for multivariate linear regression first, then show that an LAE evaluated under a relaxed mean squared error is a constrained multivariate linear regression problem on bounded data, so the bound carries over. They also develop computational shortcuts so the bound can actually be evaluated on large models and real-world data, and test whether the bound tracks practical ranking metrics such as Recall@K and NDCG@K.

Key Contributions

1. A PAC-Bayes bound for multivariate linear regression. The authors generalize Shalaeva et al.'s Gaussian data assumption (Shalaeva et al., 2020) to the multi-output setting with potentially dependent outputs and possibly degenerate input covariance (Assumption 3.1), and derive a corresponding bound (Theorem 3.2). Shalaeva's single-output bound is recovered as the special case p = 1, μ_x = 0, Σ_x = σ_x²I, Σ_e = σ_e².

2. Sufficient conditions for convergence. They formalize the convergence analysis that Shalaeva et al. presented informally, showing that extra conditions are needed to justify swapping the limit and the expectation (Theorem 3.3), and give concrete examples of (λ, π) pairs that satisfy these conditions (Examples 3.4 and 3.5).

3. An LAE-specific bound. They introduce a relaxed mean squared error for LAE evaluation, show that under this loss an LAE is a constrained multivariate linear regression model on bounded data, and adapt the bound by replacing the Gaussian assumption with a bounded-support assumption (Assumption 4.1) while incorporating the hold-out constraint on data and the zero-diagonal constraint on weights.

4. Computationally efficient bound optimization. They restrict prior and posterior to entry-wise Gaussian distributions (Assumption 5.1, following Dziugaite and Roy), obtain a closed-form expression for the tightest bound (Theorem 5.2), and derive a practical upper bound with reduced complexity to offset the cost introduced by the zero-diagonal constraint (Theorem 5.4).

Main Findings

• Generalized bound with a tighter Ψ term: Under Assumption 3.1, the multivariate bound of Theorem 3.2 upper-bounds Ψ_{π,D}(λ, m) by ln E_{W~π} exp(2λ²‖Σ_W‖_F²/m), where Σ_W = (W* − W)Σ_x(W* − W)^T + Σ_e. This recovers Shalaeva's bound when p = 1.

• Convergence needs an extra condition: Theorem 3.3 states that if E_{W~π}[exp(λ‖(Σ_x + μ_x μ_x^T)^{1/2}(W* − W)‖F²)] < ∞, then lim{m→∞} Ψ_{π,D}(λ, m) = 0. The authors note that this condition was not discussed in Shalaeva et al.'s original paper, and that without it convergence is not guaranteed.

• Two verified prior families: Example 3.4 shows a bounded-support prior satisfies the condition for any λ > 0; Example 3.5 shows an entry-wise Gaussian prior with variance σ² satisfies it for any λ ∈ (0, 1/(2ν₁σ²)), where ν₁ is the largest eigenvalue of Σ_x + μ_x μ_x^T.

• LAE-as-regression equivalence: Under the relaxed MSE of equation (8), where the mask on the prediction is removed so all predicted interactions participate in evaluation, an LAE is a multivariate linear regression with output dimension p = n subject to two constraints: entries X_ij and Y_ij are 0 or 1 but cannot both be 1, and optionally diag(W) = 0.

• Closed-form cross-correlation matrices: Lemma 4.4 gives Σ_xx = p²Σ_hh + p(1−p)(I ⊙ Σ_hh), Σ_yy = (1−p)²Σ_hh + p(1−p)(I ⊙ Σ_hh), and Σ_xy = p(1−p)(Σ_hh − I ⊙ Σ_hh), where Σ_hh is the cross-correlation of a multivariate Bernoulli distribution for user vectors and p is the retained fraction of observed interactions. Σ_xx is positive definite when Σ_hh is.

• Explicit true-risk expression: Lemma 4.2 expresses R^true(W) as ‖WΣ_xx^{1/2} − Σ_xy^T Σ_xx^{−1/2}‖_F² − ‖Σ_xy^T Σ_xx^{−1/2}‖_F² + tr(Σ_yy), and Proposition 4.3 upper-bounds Ψ by ln C · E_π[exp(λ‖WΣ_xx^{1/2} + B‖_F²)] with B = −Σ_xy^T Σ_xx^{−1/2} and C = exp(λ(tr(Σ_yy) − ‖Σ_xy^T Σ_xx^{−1/2}‖_F²)). This upper bound is independent of m — the authors note it therefore does not ensure convergence, but it simplifies computation.

• Empirical tightness and correlation reported, but numbers not given in available content: The abstract states that experimental results on real-world datasets show the bound is tight and correlates well with Recall@K and NDCG@K. The paper references a Table 2 for large real-world datasets and mentions that LAE models can contain hundreds of millions of parameters, but the specific dataset names, dataset sizes, table contents, and numerical bound/metric values are not present in the truncated content provided, so they cannot be reported here.

Methodology in Plain English

The authors work in the PAC-Bayes framework, which bounds the expected performance on unseen data by combining three things: the model's error on the training data, a complexity term measuring how far the learned distribution (posterior) moves from a prior belief (KL divergence), and a data-dependent term Ψ that captures how much the true risk could differ from the empirical risk. The general recipe is Alquier's bound.

They proceed in stages. First, they state a Gaussian data assumption general enough to allow multiple correlated outputs and a singular input covariance, derive the resulting Ψ term for multivariate linear regression, and identify exactly what extra condition makes Ψ vanish as the number of samples m grows — the gap they found in the earlier single-output analysis. The condition is essentially that a particular exponential moment under the prior must be finite, and they show two prior families (bounded support, and Gaussian with a restricted λ range) that satisfy it.

Second, because recommendation data are binary rather than Gaussian, they switch to a bounded-support assumption characterized only by three cross-correlation matrices (Σ_xx, Σ_xy, Σ_yy). They then rewrite the LAE's evaluation. Standard MSE only scores held-out interactions; the authors drop the mask on the prediction, producing a "relaxed MSE" that also penalizes recommending unobserved-and-uninteresting items and re-recommending already-observed items. This makes the LAE objective identical in form to the empirical risk of a linear regression — at which point the earlier theory applies, with the hold-out and zero-diagonal constraints added.

Third, to make the bound numerically usable, they follow the Dziugaite–Roy approach of using entry-wise Gaussian prior and posterior distributions, which makes the KL divergence analytically computable. Rather than jointly optimizing prior, posterior, and the trade-off parameter λ (which they describe as generally intractable), they fix λ and the prior, compute the optimal posterior in closed form, and pick the combination giving the tightest bound. A final, looser but cheaper upper bound is derived to reduce the cost of enforcing the zero-diagonal constraint.

Why This Matters

Impact on research. Recommender systems research has been criticized in the paper's own framing for relying on weak baselines and unreliable sampled metrics, making results biased and hard to reproduce. A generalization bound tied to ranking metrics offers a theory-side check on reported performance. The paper also closes a formal gap in prior PAC-Bayes work on linear regression by making the convergence conditions explicit, and it establishes an equivalence between LAEs and constrained multivariate linear regression that other theorists can build on.

Real-world applications:

• Large-scale e-commerce and media recommendation, where LAE-family models are already deployed and a cheap theoretical performance estimate could complement expensive A/B testing.
• Cold-start and sparse-interaction settings, where held-out evaluation is noisy and a bound could give a more stable signal.
• Model selection among LAE variants (for example EASE, EDLAE, ELSA) without repeatedly running full ranking evaluations.
• Auditing recommender behavior, since the relaxed MSE explicitly penalizes re-recommending already-observed items and recommending items unlikely to interest the user.

Industry relevance. The paper targets practical feasibility directly — the motivation for the efficiency section is that LAE models can contain hundreds of millions of parameters and run on large real-world datasets. A bound that only works on toy problems would be of little use, so the closed-form posterior and reduced-complexity upper bound are the parts most likely to matter to practitioners.

Future Directions

• Tightening the gap to ranking metrics. The analysis uses mean squared error as a proxy for discrete ranking metrics like Recall@K and NDCG@K. Closing this gap theoretically would strengthen the link between the bound and what practitioners actually measure.
• Reconciling the m-independent upper bound. Proposition 4.3's Ψ upper bound is convenient but, by the authors' own statement, does not converge. Deriving a computationally cheap bound that also converges is an open problem.
• Joint optimization of prior, posterior, and λ. The paper explicitly optimizes only over the posterior for fixed λ and π, calling the joint problem generally intractable. Better procedures or approximations could yield tighter bounds.
• Extending beyond the zero-diagonal and hold-out constraints. The framework is built for EASE-style constraints; whether other LAE variants (EDLAE, ELSA have different regularizers or relaxed diagonal constraints) fit the same template is a natural extension.

Target Audience

Researchers in statistical learning theory and PAC-Bayes analysis; recommender systems researchers interested in the theoretical foundations of linear autoencoders; and graduate students or practitioners with a strong linear algebra and probability background who want to understand why simple linear models generalize well. Readers looking primarily for benchmark numbers or implementation guidance will find the paper's contributions are theoretical, and the numerical experimental results are not available in the provided content.

Authors’ abstract

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.