PAC-Bayes Bounds for Multivariate Linear Regression and Linear Autoencoders

Theoretical Claims: All risk bound theorems provided in this paper are incorrectly stated... Alquier's THM is much stronger that this statement. It holds for all $\rho$ and does not require $\rho$ be any specific distribution.

Answer: We appreciate you pointing out this issue. The original Alquier's bound [1] is indeed of the form $P(\forall \rho, ...) > 1 - \delta$. We followed Shalaeva's setting $\forall \rho, P(...) > 1 - \delta$ but overlooked this issue.

Let $\textsf{E}(\rho)$ be an event related to $\rho$. It is true that $P(\forall \rho, \textsf{E}(\rho)) > 1 - \delta \Longrightarrow \forall \rho, P(\textsf{E}(\rho)) > 1 - \delta$, since the probability on the left applies to an intersection of events while the probability on the right applies to a single event. Thus, Alquier's bound makes a stronger claim; we will revise its statement accordingly. Shalaeva's bound and our bounds remain valid, as they are derived from a weaker form of Alquier's bound; we think fixing their statements is unnecessary.

Experimental Designs Or Analyses: A risk bound should be computed on the training set only, not the testing set. See Langford, JMLR 2005, ``Tutorial on Practical Prediction Theory for Classification''.

Answer: In Langford's setting, the same loss function is applied to both training set and test set, so both training error and test error are empirical risks. However, in some cases, training and testing metrics differ. For example, recommender system models like EASE or EDLAE are trained by minimizing an averaged loss (e.g., squared Frobenius norm), but evaluated using an averaged ranking (e.g., Recall@K and NDCG@K).

Since both averaged loss and averaged ranking are evaluated on finite samples, they represent two different types of empirical risk. However, as the ultimate goal is to enhance model performance on the test set, the empirical risk on the test set is typically the most relevant. In this case, it is sufficient to develop a generalization bound solely for the test set. Some generalization bounds have even been formulated directly on test metrics like AUC [2].

Experimental Designs Or Analyses: I have not understood exactly how the authors have applied algorithm 1 for the computation of their PAC-Bayes bounds in their experimental section (Section 6). ... Moreover, it should be computed for the stochastic Gibbs predictor, not for the deterministic predictor W returned by the EASE optimization problem of equation 2.

Answer: In our experiment, after obtaining a deterministic predictor $W$ by solving the EASE problem, we set it as the expectation of $\pi$, i.e., $\pi = \bar{\mathcal{N}}(W, \sigma^2J)$, similar to the approach of Dziugaite and Roy [3]. This $\pi$ is then fed into Algorithm 1 to solve for the optimal $\rho$. The predictor in our bound is always stochastic, as both its prior distribution $\pi$ and posterior distribution $\rho$ are Gaussian. While a Gaussian $\rho$ may not be optimal (i.e., it may not approximate the Gibbs posterior [4]), we believe it is sufficient to verify the tightness of the bound.

Other Strengths And Weaknesses: The novelty of their risk bound comes from the assumption that the data-generating distribution is known, which is never the case in practice.

Answer: We use an unbounded loss in our linear regression setting. To our knowledge, it is typical to assume that the data-generating distribution is known when deriving a PAC-Bayes bound for unbounded losses, as seen in two recent works [5][6]. This is because unbounded losses require assumptions (such as a bounded CGF [4]) to characterize their tail distributions, and without knowing the data distribution, such assumptions in general cannot be formed. This nature makes such bounds inevitably oracle-based.

While most of such oracle bounds remain theoretical, our approach shows that they can be computed with certain assumptions applied, and we have identified which assumptions simplify the computation. Furthermore, we have shown that the computation can be highly efficient, as evidenced by empirical validation on large real-world datasets. Although not fully practical yet, we believe our computational methods can inspire future work in this area.

References:

[1] Alquier et al. On the properties of variational approximations of gibbs posteriors. JMLR 2016.

[2] Shivani Agarwal et al. Generalization Bounds for the Area Under the ROC Curve. JMLR, 2005.

[3] Dziugaite and Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv, 2017.

[4] Borja Rodrıguez-Galvez et al. More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity. JMLR, 2024.

[5] Maxime Haddouche et al. PAC-Bayes unleashed: Generalisation bounds with unbounded losses. Entropy, 2021.

[6] Ioar Casado et al. PAC-Bayes-Chernoff bounds for unbounded losses. NIPS, 2024.

&\text{S1}: \\; P(\forall \rho, \textsf{E}(\rho)) > 1 - \delta \\\\
&\text{S2}: \\; \forall \rho, P(\textsf{E}(\rho)) > 1 - \delta \\\\
&\text{S3}: \\; \rho \text{ is a Gibbs posterior}, P(\textsf{E}(\rho)) > 1 - \delta \\\\
&\text{S4}: \\; \rho \text{ is a Guassian posterior}, P(\textsf{E}(\rho)) > 1 - \delta

Question 1: Is it possible to instead derive an empirical PAC-Bayes bound, as alluded to? Would this be desirable?

Answer: The loss in our linear regression setting is assumed to be unbounded. According to [1], existing empirical PAC-Bayes bounds, such as Catoni's bound and Seeger's bound, are primarily designed for bounded loss. They cannot be directly applied to our linear regression setting.

Developing an empirical PAC-Bayes bound for unbounded loss is challenging. The reason is that, unbounded losses requires extra assumptions, such as a bounded cumulant generating function (CGF) [2], to characterize their tail behavior. These assumptions typically assume the data distribution is known -- for example, the CGF inherently contains the true risk -- which naturally involves oracle information. As a result, the PAC-Bayes bounds derived under these unbounded loss assumptions are oracle-based.

It remains an important open question that whether unbounded loss assumptions can be made without relying on oracle information, thereby allowing us to derive a fully empirical PAC-Bayes bound.

Question 2 and Question 3: As mentioned, recommender systems are often evaluated using other metrics than squared loss. Is it possible to at least empirically investigate the correlation of the bound to such metrics?

Answer: Yes. We have added the experimental results of Recall@50 and NDCG@100 using the same test sets and models in Table 2 of our paper. Both Recall@50 and NDCG@100 are recommendation metrics used in the EASE paper [3]. The results are as follows:

Recall@50:

NDCG@100:

Comparing the two tables with Table 2 in our paper, we observe that on each dataset, as $\gamma$ increases, LH and RH decrease, while Recall@50 and NDCG@100 increase. This confirms the expected correlation between LH, RH and Recall@50, NDCG@100, suggesting that our metrics LH and RH correctly reflect the model performance. (Note that LH and RH are losses, smaller value represents better model performance; Recall@50 and NDCG@100 are rankings, larger value represents better model performance.)

Hence, we have empirically validated the correctness of this correlation. We will add these results to our paper. Additionally, we believe that analyzing this correlation theoretically is challenging.

Essential References Not Discussed: The paper “PAC-Bayes unleashed: generalisation bounds with unbounded losses” by Haddouche et al includes bounds for linear regression ...

Answer: Thanks for sharing the two papers. We will add them into our related works.

In Haddouche et al's paper, we notice that they use the $L_1$ norm to define the loss in linear regression, which is not typical. The $L_1$ norm may help satisfy HYPE, an essential assumption in their PAC-Bayes bounds. However, we believe that the squared $L_2$ (Frobenius) norm we used is a more standard loss for linear regression problems.

Other Strengths And Weaknesses: In (10), it is argued that one can find the optimal posterior. Can this be compared to normal or regularized linear regression?

Answer: We think that they are not directly comparable. In normal or regularized linear regression, the optimal predictor is a constant, known as a deterministic predictor. In Eq (10), the optimal predictor $W$ is a random variable following the posterior distribution $\rho$, making it a stochastic predictor. Since they represent two different type of predictors, direct comparison between them is not straightforward.

References:

[1] Pierre Alquier. User-friendly introduction to pac-bayes bounds. arXiv:2110.11216, 2021.

[2] Borja Rodrıguez-Galvez et al. More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity. JMLR, 2024.

[3] Harald Steck. Embarrassingly shallow autoencoders for sparse data. WWW, 2019.

Question 1: Why is there no convergence analysis for the PAC-Bayes bound in the bounded data case?

Answer: Because the bounded data assumption (Assumption 4.1) alone is not sufficient to guarantee the convergence. The reason is as follows:

First, the convergence of Alquier's bound does not hold for all choices of $\pi$ and $\mathcal{D}$: Our bound in Theorem 1 is a specialization of Alquier's bound, and we have shown in Section 3.2 that certain choices of $(\pi, \mathcal{D})$ can cause divergence.

Next, the bounded data case (Eq (7)) is another specialization of Alquier's bound, derived under Assumption 4.1. Assumption 4.1 imposes a constraint on $\mathcal{D}$, which defines a subset of $(\pi, \mathcal{D})$ in the set of all $(\pi, \mathcal{D})$. However, Assumption 4.1 does not imply that every choice of $(\pi, \mathcal{D})$ in this subset guarantees the convergence.

Question 2: In section 4.2, the paper seems to assume that each element $x = (x\_1, x\_2, ..., x\_n) \in \\{0, 1\\}^n$ of the input independently affect its output $y = (y\_1, y\_2, ..., y\_n) \in \\{0, 1\\}^n$ in i.e., only $x_i$ affect the value of $y\_i$ for each $i = 1, 2, ..., n$. Is there a reason for this choice of data distribution?

Answer: We would like to clarify that $y = (y\_1, y\_2, ..., y\_n) \in \\{0, 1\\}^n$ is the target, $\hat{y} = (\hat{y}\_1, \hat{y}\_2, ..., \hat{y}\_n) \in \mathbb{R}^n$ is the output of the LAE model $W\in \mathbb{R}^{n\times n}$, with $\hat{y} = Wx$, and $x = (x\_1, x\_2, ..., x\_n) \in \\{0, 1\\}^n$ is the input. The loss between $y$ and $\hat{y}$ is given by $\|\|y - \hat{y}\|\|\_F^2$.

For the output, $\hat{y}\_i$ is not independently affected by $x\_i$ but by the entire vector $x$, since $\hat{y}\_i = W\_{i*}x$.

For the target, we assume that $y_i$ depends only on $x_i$ for simplicity. This assumption is sufficient to describe the constraint that either $x\_i = 1, y\_i = 0$ or $x\_i = 0, y\_i = 1$. While one could assume a more complicated distribution for $y\_i$ (e.g., $y\_i$ depends on the entire $x$) to describe the same constraint, it is unnecessary.

Theoretical Claims: I do have an issue with how the paper reuse the $\eta\_j$ symbol to mean different things in different sections which is quite confusing.

Answer: We apologize for any confusion caused by the reuse of symbols. The $\eta\_j$ in Section 2 represents an eigenvalue of $\Sigma\_W$, and in Section 5.2, it is redefined as an eigenvalue of $A$. We acknowledge that a clarification regarding this redefinition is missing and will add it to our paper.

Methods And Evaluation Criteria: It would be more efficient to use an optimization method such as stochastic gradient descend to find the optimal value for $\lambda$.

Answer: It is generally considered impossible for optimizing the right hand side of a PAC-Bayes bound with respect to $\lambda$ [1][2]. The reason is as follows: Let $S$ be the dataset, which is a random variable. In PAC-Bayes bounds, $\lambda$ is assumed to be a constant independent of $S$. However, if optimizing the right hand side of a PAC-Bayes bound with respect to $\lambda$, then the optimal $\lambda$ may depend on $S$, which contradicts the assumption.

There are several ways addressing this issue. One way is the grid search method we used, primarily following [1]. The grid search is simple but may not be efficient. Another way is to derive an upper bound for the RH of Eq (14) that does not depend on $\lambda$, which is used by Rodríguez-Gálvez et al [2].

References:

[1] Pierre Alquier. User-friendly introduction to pac-bayes bounds. arXiv:2110.11216, 2021.

[2] Borja Rodrıguez-Galvez et al. More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity. JMLR, 2024.

Question 1: The KL divergence $D(\rho||\pi)$ is not defined in the paper.

Answer: Thanks for pointing out this issue. We will add this into our paper: Suppose $\pi$ and $\rho$ are continuous probability distributions on $\mathbb{R}^d$. The KL-Divergence is defined as

$

D(\rho||\pi) = \mathbb{E}\_{\theta \sim \rho}\left[\log \frac{\rho(\theta)}{\pi(\theta)}\right]

$

where $\rho(\theta)$ and $\pi(\theta)$ denote the probability density function of $\rho$ and $\pi$, respectively. We assume for any $\theta \in \mathbb{R}^d$, $\pi(\theta) = 0$ implies $\rho(\theta) = 0$.

Question 2: You should also check the technique in Theorem 12 of [1], which results in potentially tighter optimization of $\lambda$ without too many complications.

Answer: Thanks for sharing Rodríguez-Gálvez et al's work. We find the ideas in this paper both interesting and inspiring.

Based on our understanding, Rodríguez-Gálvez et al address the difficulty of optimizing $\lambda$ by proposing an upper bound that is independent of $\lambda$. Their method constructs this upper bound by partitioning the event space based on the KL-divergence $D(\rho||\pi)$: the event $\mathcal{E} = \\{D(\rho||\pi) \le m\\}$ is split into sub-events $\\{\mathcal{E}\_k\\}_{k=1}^m$ where $\mathcal{E}\_k = \\{D(\rho||\pi) \le k\\}$. Then the bound is optimized by conditioning on each $\mathcal{E}\_k$.

While this is an elegant theoretical contribution, implementing and evaluating it in our context would require significant additional work that is not feasible within the rebuttal period. We plan to reference this approach in our final revision and explore it more thoroughly in future work.

Additionally, we believe our current method based on a grid search of $\lambda$ provides satisfactory results at a low computational cost, especially given our evaluation on large real-world datasets. While a tighter bound may be achievable, it would come at the expense of increased computational cost.

Other Strengths And Weaknesses: The only clear weakness is the experimental part: since the bound is an oracle one, the empirical evaluation needs many compromises and extra assumptions (such as the one in line 422 regarding $\Sigma\_{rr}$), which is a bit disappointing. However, I recognize that working out fully empirical PAC-Bayes bounds (especially for unbounded losses) is not easy.

Answer: Thanks for your understanding.

Indeed, in our linear regression setting, the loss is unbounded, and we recognize the inherent difficulty in developing fully empirical PAC-Bayes bounds under such conditions. Unbounded loss requires extra assumptions, such as a bounded cumulant generating function (CGF) [1], to characterize their tail behavior. These assumptions typically presuppose the data distribution is known -- for example, the CGF inherently contains the true risk -- which naturally involves oracle information. As a result, the PAC-Bayes bounds derived under these assumptions are oracle-based. Whether unbounded loss assumptions can be made without oracle information remains an important open question, as it is crucial for developing a fully empirical bound.

We would like to highlight an additional strength of our method. In our supplemental experiments addressing the Question 2 from reviewer TXNp, we empirically verified that the decrease in LH and RH of our oracle bound Eq (14) correlates correctly with the increase in Recall@K and NDCG@K. This suggests that LH and RH can correctly reflect model performance. Although LH and RH contain oracle information, they are easier to analyze statically than Recall@K and NDCG@K, making them potentially better evaluation metrics for LAEs.

References:

[1] Borja Rodrıguez-Galvez et al. More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity. JMLR, 2024.