ICML23 - Fundamental Tradeoffs in Learning with Prior Information

本文关注的问题为：为快速学习一项给定的任务，需要多少先验知识？(How much prior knowledge does one require in order to learn quickly on a given task?)

具体来说，本文聚焦于「对于一个给定的问题，先验信息的准确性与学习性能之间的权衡关系 (Fundamental tradeoffs between the accuracy of prior information that a learner has on a given problem and its learning performance)」。

背景知识

本文为详细阐述后文提出的 Prioritized Risk，首先对两种经典的风险评估方式进行了介绍，分别为 Minimax Risk 和 Bayes Risk。

首先对问题进行形式化：

$X$ 为定义在样本空间 $\mathcal{X}$ 中的随机变量，其概率分布 $P_\theta$ 由未知参数 $\theta \in \Theta$ 定义；
学习者 (Learner) $\sigma:\mathcal{X}^n\rightarrow \mathcal{A}$ 在收到数据集 $x_1^n:={x_i}_{i=1}^n$（样本独立同分布）后，将输出相应的 action $a\in \mathcal{A}$，并使用损失函数 $L: \Theta \times \mathcal{A}\rightarrow [0,\infty)$ 进行度量；
The risk of a learner 定义如下：

$$ \mathcal{R}(\sigma, \theta):=\underset{X_1^n \sim P_\theta^n}{\mathbb{E}}\left[L\left(\theta, \sigma\left(X_1^n\right)\right)\right]. $$

需要注意的是，上述形式化可以涵盖多类问题，当 $\mathcal{A}=\Theta$ 时，可以研究 Estimation Problems；当 $\mathcal{A}$ 为假设空间 $\mathcal{H}$，可以研究相应的学习问题。

Minimax Risk

Minimax Risk 主要关注最坏情况下的学习性能，即在所有可能的参数设置下，学习者可能遭受的最大损失，其具体定义如下：

$$ \mathcal{R}_{\operatorname{minimax}}(L ; \Theta):=\inf _\sigma \sup _{\theta \in \Theta} \mathcal{R}(\sigma, \theta). $$

Minimax Risk 是 lowest worst-case risk，其采用了一种稳健的策略，以确保在面对极端不确定性和可能的对抗环境时的性能。它不依赖于对参数的具体先验知识，并准备应对最不利的情况。

Bayes Risk

贝叶斯风险考虑了当 $\theta$ 的取值遵循 $\pi$ 分布时的最小平均损失 (smallest possible average risk)，其定义如下：

$$ \mathcal{R}_{\text {Bayes }}(\pi, L ; \Theta):=\inf _\sigma \int_{\Theta} \mathcal{R}(\sigma, \theta) \pi(d \theta). $$

学习者可以使用贝叶斯推断，基于先验 $\pi$ 和观测数据 $x_1^n$ 达到最优的贝叶斯风险。该方法虽然利用了先验知识来指导学习过程，但其假设非常强，即参数 $\theta$ 服从一个 “真实” 的分布 $\pi$ (“nature’s prior”)，且该分布为学习者所知。该强假设使得贝叶斯风险并不适用于「现实情况与先验不相符」的场景下。

本文贡献：Prioritized Risk

Definition

此处将先验形式化为 $\pi: \Theta\rightarrow \mathbb{R}_{>0}$，且其未必为归一化形式，即积分和可以不为 1，整体定义非常 general。

Prioritized Risk 的具体定义如下：

For a given family of distributions $\{P_\theta\}_{\theta\in\Theta}$, loss function $L$, and prior function $\pi:\Theta \rightarrow \mathbb{R}_{>0}$, the prioritized risk is defined as:

$$ \begin{aligned} \mathcal{R}_{\text {prior }}(\pi, L ; \Theta) & :=\inf _\sigma \sup _{\theta \in \Theta} \pi(\theta) \mathcal{R}(\sigma, \theta) \\ & =\inf _\sigma \sup _{\theta \in \Theta} \pi(\theta) \underset{X_1^n \sim P_\theta^n}{\mathbb{E}}\left[L\left(\theta, \sigma\left(X_1^n\right)\right)\right]. \end{aligned} $$

We will refer to the quantity:

$$ \mathcal{R}_{\text {prior }}^\sigma(\pi, L ; \Theta):=\sup _{\theta \in \Theta} \pi(\theta) \mathcal{R}(\sigma, \theta) $$

as the learner-specific prioritized risk.

在上述形式化中，对于真实的参数 $\theta$ 来说，$\pi(\theta)$ 越大，说明现实与先验越符合；反之，$\pi(\theta)$ 越小，说明现实与先验差别越大。

对于上述定义，可以从「不同的学习算法」和「不同的学习问题」两个维度来进行理解，分别对应于 Prioritized Risk 的上界和下界两个角度。

Implications for Learning Algorithms

当某个 learner $\sigma$ 取得了比较小的 learner-specific prioritized risk，即：

$$ \pi(\theta) \mathcal{R}(\sigma, \theta) \leq \epsilon, \forall \theta \in \Theta. $$

我们可以认为：

当现实与先验越相符时（$\pi(\theta)$ 越大），风险的上界越低，即 $\mathcal{R}(\sigma, \theta)\leq \epsilon/\pi(\theta)$.
算法选择时，应选择 learner-specific prioritized risk 上界更小的算法，因为其在学习性能（即风险）和先验信息的准确性（即 $\theta$ 与先验的一致程度）之间取得了更好的权衡：

$$ \begin{aligned} & \mathcal{R}(\sigma, \theta) \leq \epsilon / \pi(\theta), \forall \theta \in \Theta, \\ & \mathcal{R}\left(\sigma^{\prime}, \theta\right) \leq \epsilon^{\prime} / \pi(\theta)<\epsilon / \pi(\theta), \forall \theta \in \Theta. \end{aligned} $$

Implications for Learning Problems

相比于上界，本篇工作更关注 Prioritized Risk 的下界，即考虑满足下述条件的问题：

$$ \mathcal{R}_{\text {prior }}(\pi, L ; \Theta) \geq \beta. $$

上式说明无论选择什么学习算法 $\sigma$，下式均成立：

$$ \exists \theta \in \Theta \text { such that } \underbrace{\pi(\theta)}_{\begin{array}{c} \text{\scriptsize Prior} \\ \text{\scriptsize (``Nature'')} \end{array}} \underbrace{\mathcal{R}(\sigma, \theta)}_{\begin{array}{c} \text{\scriptsize Learning} \\ \text{\scriptsize (``Nurture'')} \end{array}} \geq \beta . $$

上述 Tradeoff 说明：It is impossible for both the risk and the prior to be low for all $\theta\in \Theta$.

换句话说，对于任意学习算法 $\sigma$，总存在 $\theta\in \Theta$ 使得：If the learner achieves low risk, it must be the case that reality conforms to the learner’s prior (i.e., $\pi(\theta)$ is large).

Relationship to minimax and Bayes risk

The prioritized risk reduces to the minimax risk if $\pi(\theta) \equiv 1$. If $\pi(\theta)\leq 1$ $\forall \theta$, then $\mathcal{R}_{\text{prior}}\leq \mathcal{R}_{\text{minimax}}$.
当 $\Theta$ 为可数集，且 $\pi$ 为归一化后的合法概率分布形式时，有 $\mathcal{R}_{\text {prior }} \leq \mathcal{R}_{\text {Bayes }} \leq \mathcal{R}_{\text {minimax }}$.
当 $\Theta$ 为非可数集时，$\mathcal{R}_{\text {prior }}$ 可能会大于 $\mathcal{R}_{\text {Bayes }}$，因为某些分布的概率密度函数，其最大值超过了 1（例如高斯分布和均匀分布）。

Techniques for Lower Bounds

本文在提出 Prioritized Risk 之后，引入了一些推导其下界 (Lower bound) 的技术，均由 Minimax Risk 的相关下界技术推广而来。此处举两个例子，如果今后遇到推导该 Risk 下界的情况，可以在原论文中找到详细内容。

本文以估计问题 (Estimation Problems) 着手，即满足：$\sigma:\mathcal{X}^n\rightarrow \Theta, L:\Theta\times \Theta \rightarrow [0,\infty)\text{, } \text{e.g., }|\theta-\hat{\theta}|_2.$

在介绍具体技术前，本文首先介绍了 $(\delta,\pi)$-packing 的概念（来源于覆盖数与填充数），具体如下：

${\theta_v}_{v\in\mathcal{V}}$ forms a $(\delta,\pi)$-packing if balls of radius $\delta/(\pi(\theta_v))$ centered around each $\theta_v$ are non-overlapping.

基于上述概念，即可给出如下两个定理：

LeCam’s method (假设 ${\theta_1,\theta_2}$ forms a $(\delta,\pi)$-packing)：

$$ \mathcal{R}_{\text {prior }}(\pi, L ; \Theta) \geq \frac{\delta}{2}\left[1-\left\|P_{\theta_0}^n-P_{\theta_1}^n\right\|_{T V}\right]. $$

Fano’s method (假设 ${\theta_v}_{v\in \mathcal{V}}$ forms a $(\delta,\pi)$-packing，并且随机变量 $V$ 的分布为 $\mathcal{V}$ 上的均匀分布)：

$$ \mathcal{R}_{\text {prior }}(\pi, L ; \Theta) \geq \delta\left[1-\frac{I\left(V ; X_1^n\right)+\log (2)}{\log |\mathcal{V}|}\right]. $$

Discussion & Conclusion

与 PAC-Bayes 对比

PAC-Bayes 理论：提供了 learner 拥有先验信息时的风险上界（upper bound）

PAC-Bayes 中也体现了「先验信息准确性」和「学习性能」之间的权衡，具体来说：如果生成数据的分布 (data-generating distribution) 符合学习者的先验，则可以取得较低的风险上界；但是，如果生成数据的分布不符合学习者的先验，则风险的 PAC-Bayes 上界则较高。

与 PAC-Bayes 对比，本文提出的 Prioritized Risk 更关注 learner 拥有先验信息时的风险下界。

本文主要贡献

Different from the minimax and Bayes risk, the proposed prioritized risk allows us to study fundamental tradeoffs in settings where reality does not conform to the learner’s prior.

具体来说，prioritized risk 的下界说明了：It is impossible for both the risk of a learner and the prior to be low for all distributions，即：

对于任意学习算法 $\sigma$，一定存在一种不符合先验的场景，使得算法 $\sigma$ 取得较大的误差；
换句话说，对于任意学习算法 $\sigma$，不可能在所有不符合先验的场景下，都取得较小的误差。

Future Work

Developing prior-informed learning algorithms that are optimal from the perspective of the prioritized risk would be of practical interest.
Explore if there are settings where the optimal asymptotic dependence on $n$ (number of examples) for prioritized risk and minimax/Bayes risk are different.
例如在 minimax risk 上取得最优结果的学习算法 $\sigma_{\text{minimax}}$ 在 prioritized risk 上未取得最优结果，那相当于可以针对 prioritized risk 设计更优的算法。
Using the prioritized risk framework to understand how much prior information (“nature”) one needs in order to achieve a certain level of learning performance (“nurture”) in a broader set of applications of practical interest.

文中推导所涉及的内容记录

式子推导

Proposition 4.1 的证明中（$\delta$ 为常数）：

$$ \begin{aligned} \sup _{\theta \in \Theta} \underset{X_1^n \sim P_\theta^n}{\mathbb{E}}\left[\pi(\theta) \rho\left(\theta, \sigma\left(X_1^n\right)\right)\right] &\geq \sup _{\theta \in \Theta} \underset{X_1^n \sim P_\theta^n}{\mathbb{E}}\left[\delta \cdot \mathbb{1}\left[\pi(\theta) \rho\left(\theta, \sigma\left(X_1^n\right)\right) \geq \delta\right]\right] \\ &=\sup _{\theta \in \Theta} \delta \cdot P_\theta\left[\pi(\theta) \rho\left(\theta, \sigma\left(X_1^n\right)\right) \geq \delta\right]. \end{aligned} $$

Total Variation Distance（全变差距离）

定义：Let $P_1$ and $P_2$ be arbitrary distributions on a space $\mathcal{X}$. The total variation distance between $P_1$ and $P_2$ is defined as

$$ \delta(P_1,P_2)=\left\|P_1-P_2\right\|_{\mathrm{TV}}:=\sup _{A \subset \mathcal{X}}\left|P_1(A)-P_2(A)\right|. $$

Proposition 2.2.8.（Ref 里的定理，顺带记录一下）The total variation distance satisfies the following relationships: (a) Pinsker’s inequality: for any distributions $P$ and $Q$,

$$ \|P-Q\|_{\mathrm{TV}}^2 \leq \frac{1}{2} D_{\mathrm{kl}}(P \| Q) . $$

(b) The Bretagnolle-Huber inequality: for any distributions $P$ and $Q$,

$$ \|P-Q\|_{\mathrm{TV}} \leq \sqrt{1-\exp \left(-D_{\mathrm{kl}}(P \| Q)\right)} \leq 1-\frac{1}{2} \exp \left(-D_{\mathrm{kl}}(P \| Q)\right). $$

Proposition 2.3.1. Let $\mathcal{X}$ be an arbitrary set. For any distributions $P_1$ and $P_2$ on $\mathcal{X}$, we have

$$ \inf _{\Psi}\left\{P_1(\Psi(X) \neq 1)+P_2(\Psi(X) \neq 2)\right\}=1-\left\|P_1-P_2\right\|_{\mathrm{TV}}, $$

where the infimum is taken over all tests $\Psi: \mathcal{X} \rightarrow{1,2}$.

Tensorization Property of KS, TV and KL Distance

Tensorization: Let $P_1,…,P_n$ and $Q_1,…,Q_n$ be distributions on $\mathcal{X}$ with densities $f_1,…,f_n$ and $g_1,…,g_n$, respectively. Then

$\mathrm{KS}\left(\otimes_{i=1}^n P_i, \otimes_{i=1}^n Q_i\right) \leq \sum_{i=1}^n \mathrm{KS}\left(P_i, Q_i\right)$
$\operatorname{TV}\left(\otimes_{i=1}^n P_i, \otimes_{i=1}^n Q_i\right) \leq \sum_{i=1}^n \operatorname{TV}\left(P_i, Q_i\right)$
$\mathrm{KL}\left(\otimes_{i=1}^n P_i: \otimes_{i=1}^n Q_i\right)=\sum_{i=1}^n \mathrm{KL}\left(P_i, Q_i\right)$

Fano’s Inequality

Corollary 2.3.4. Assume that $X$ is uniform on $\mathcal{X}$. For any Markov chain $X \rightarrow Y \rightarrow \widehat{X}$,

$$ \mathbb{P}(\widehat{X} \neq X) \geq 1-\frac{I(X ; Y)+\log 2}{\log (|\mathcal{X}|)}. $$

Data Processing Inequalities

Proposition 2.1.9. Assuming we have the Markov chain $X\rightarrow Y \rightarrow Z$, we have $I(X ; Z) \leq I(X ; Y)$.

Proof: We expand the mutual information $I(X ; Y, Z)$ in two ways:

$$ \begin{aligned} I(X ; Y, Z) & =I(X ; Z)+I(X ; Y \mid Z) \\ & =I(X ; Y)+\underbrace{I(X ; Z \mid Y)}_{=0}, \end{aligned} $$

where we note that the final equality follows because $X$ is independent of $Z$ given $Y$:

$$ I(X ; Z \mid Y)=H(X \mid Y)-H(X \mid Y, Z)=H(X \mid Y)-H(X \mid Y)=0 . $$

Since $I(X ; Y \mid Z) \geq 0$, this gives the result.

Donsker-Varadhan: Variational Definition of KL-divergence

Theorem 2.3.2. states that for any random variable $Z$, we have the following inequality for all distributions $P$ and $Q$:

$$ \underset{Z \sim P}{\mathbb{E}}[Z] \leq \mathrm{KL}(P \| Q)+\log \underset{Z \sim Q}{\mathbb{E}} \exp (Z). $$

PAC-Bayesian

本篇文章将其提出的理论框架与 PAC-Bayesian 进行了对比，此处放上 PAC-Bayesian bound 的基本形式，供参照。

在 PAC-Bayesian 框架下，学习算法的输出不再为假设空间 $\mathcal{H}$ 中的一个元素，而是假设空间上的分布 $Q$，相应的先验则为假设空间上的分布 $P$。

[Theorem (Generalization bounds)] Let $Q$ and $P$ be distributions on $\mathcal{H}$ and $\mathcal{D}$ be a distribution on $\mathcal{X} \times \mathcal{Y}$. Let also $\ell(h, z) \in[0,1]$ and $S \sim \mathcal{D}^m$ be a sample, then with probability greater or equal to $(1-\delta)$ over $S$ we have

$$ \begin{aligned} & \mathbf{R}(Q) \leq \hat{\mathbf{R}}(Q)+\sqrt{\frac{K L(Q \| P)+\ln \left(\frac{m+1}{\delta}\right)}{2 m}}, \\ & \mathbf{R}(Q) \leq \hat{\mathbf{R}}(Q)+2 \frac{K L(Q \| P)+\ln \left(\frac{m+1}{\delta}\right)}{m}+\sqrt{2 \hat{\mathbf{R}}(Q) \frac{K L(Q \| P)+\ln \left(\frac{m+1}{\delta}\right)}{m}}. \end{aligned} $$

其中 $\mathbf{R}(Q)$ 和 $\hat{\mathbf{R}}(Q)$ 分别表示，在假设空间的分布 $Q$ 下，在数据分布 $\mathcal{D}$ 上的期望泛化损失，以及在数据集 $D$ 上的期望经验损失；具体定义如下：

$$ \begin{aligned} \mathbf{R}(Q) & =\underset{h \sim Q}{\mathbb{E}}[\mathbf{R}(h)]=\underset{h \sim Q}{\mathbb{E}}[\underset{z \sim \mathcal{D}}{\mathbb{E}}[\ell(h, z)]], \\ \hat{\mathbf{R}}(Q) & =\underset{h \sim Q}{\mathbb{E}}[\hat{\mathbf{R}}(h)]=\underset{h \sim Q}{\mathbb{E}}\left[\frac{1}{m} \sum_{i=1}^m \ell(h, z)\right]. \end{aligned} $$

可以发现，在上述 Generalization bounds 中，后验分布 $Q$ 和先验分布 $P$ 之间的距离度量了泛化损失和经验损失之间的差距。

在 PAC-Bayes 学习中，通过定义一个在假设空间 $\mathcal{H}$ 上的先验分布 $P$，就可以得到一个对于任何后验选择 $Q$ 都成立的风险上界。这个上界可以通过固定一个与数据无关的先验 $P$，然后找到一个依赖数据的后验 $Q$ 来最小化 PAC-Bayes 上界来实现。