次线性遗憾

玻尔百科

核心要点

次线性遗憾保证了在线算法的平均性能收敛于事后看来最佳的固定行为的性能。
像在线梯度下降这样的算法，通过以精心衰减的步长沿损失梯度反方向迈出小步，实现了 O(√T) 的遗憾。
更强的问题假设，如强凸性或数据可分性，允许以对数甚至常数遗憾界限进行更快的学习。
该原理在推荐系统、科学发现、博弈论中有着广泛应用，甚至与卡尔曼滤波器等经典方法建立了联系。

引言

在一个充满不确定性的世界里，我们如何能够随着时间的推移持续做出好的决策？无论是选择购买哪只股票、走哪条路线，还是检验哪个科学假说，我们都不断地在信息不完整的情况下被迫行动。目标不可能是每天都做出完美的选择，因为那需要预知未来。这就提出了一个根本性的挑战：在这样的在线环境中，“学习”的有效性究竟意味着什么？我们又该如何衡量我们的进步？

本文通过探索次线性遗憾这一强大概念来回答这个问题。我们不再追求不可能的完美，而是采用一个更实际的基准：将我们的累积表现与事后看来最佳的单一固定决策进行比较。次线性遗憾是一个保证，即我们的学习策略的平均性能将收敛到这个“有远见的专家”的性能。这是一个我们必然会学习的数学承诺。

为了理解这一非凡的保证，我们将开启一段分为两部分的旅程。第一章“原理与机制”将解析使次线性遗憾得以实现的核心算法，如在线梯度下降。我们将研究步长的关键作用，探索算法如何适应问题的几何结构，并发现特定的结构特性如何能够带来指数级更快的学习速度。随后，“应用与跨学科联系”一章将揭示这一原理惊人的广泛应用，展示它如何驱动从个性化推荐系统、自优化软件到加速生物技术发现，并统一博弈论和工程学中不同思想的一切。

原理与机制

想象一下，你正在与宇宙玩一场游戏。每一天，你都必须做出一个决定——投资哪只股票，走哪条路上班，合成哪种候选药物。在你做出选择后，宇宙会通过给你一个“损失”来揭示你的选择有多好。高损失意味着坏选择，低损失意味着好选择。棘手的是，宇宙是不可预测的。今天最好的股票可能明天就成了最差的。你没有水晶球。你怎么可能希望玩好这场游戏呢？

这就是在线学习的挑战。我们的目标不是在任何一天都做到完美。那是不可能的。相反，我们玩的是一个更微妙的游戏。我们将自己在多个回合（比如 $T$ 个回合）中的总累积损失与一个假设的、神一般的专家进行比较。这位专家拥有一个神奇的优势：他们可以预先看到所有 $T$ 天的情况，并选择在整个期间内本应做出的单一最佳固定决策。这个固定决策会在事后看来使其总损失最小化。我们的总损失与这位专家的总损失之间的差额，就称为遗憾 (regret)。

我们的目标不是实现零遗憾；那需要时间旅行。我们谦虚而强大的目标是确保我们的遗憾增长速度慢于我们玩的回合数。我们希望我们的遗憾 $R_T$ 相对于 $T$ 是次线性的。这意味着每轮的平均遗憾 $R_T/T$ 会随着时间的推移而趋近于零。从本质上讲，我们保证能够学习。随着时间的推移，我们的平均表现将与那位从一开始就知道唯一最佳答案的“有远见的专家”一样好。这就是实现次线性遗憾的非凡承诺。但这样的壮举是如何实现的呢？

最简单的策略：向正确的方向迈出一步

让我们思考一下我们每天获得的信息。在我们做出选择后，比如我们从一组可能的决策中选择了一个点 $w_t$ ，宇宙会揭示一个损失函数 $\ell_t$ 。现在，我们假设这个函数是凸的——形状有点像一个碗。这是一个极好的性质，因为它意味着在我们选择的点 $w_t$ 上，我们可以计算一个梯度。梯度是一个向量，指向“上坡”的方向，即损失增加最快的方向。

如果我们想在下一次做得更好，最自然的做法就是朝着与梯度相反的方向迈出一小步。这就是在线梯度下降 (Online Gradient Descent, OGD) 的核心思想。在每一轮 $t$ ，我们通过从当前决策 $w_t$ 开始，并朝着负梯度方向移动一小步来更新下一轮的决策 $w_{t+1}$ ：

w'_{t+1} = w_t - \eta_t g_t

在这里， $g_t$ 是损失 $\ell_t$ 在 $w_t$ 处的梯度， $\eta_t$ 是一个称为步长或学习率的小正数，它控制我们迈出的步子有多大。如果我们的新点 $w'_{t+1}$ 恰好落在了我们允许的决策集之外，我们只需将其投影回集合内最近的点，得到我们最终的 $w_{t+1}$ 。

这似乎过于简单了。它真的有效吗？其魔力在于一段优美的数学分析。通过追踪我们的迭代 $w_t$ 与专家最优选择 $u$ 之间的距离，可以证明 $T$ 轮后的遗憾有一个上界，其形式大致如下：

R_T(u) \le \frac{D^2}{2\eta_T} + \frac{G^2}{2}\sum_{t=1}^T \eta_t

在这里， $D$ 是我们决策空间的“直径”（两个可能的决策之间可以相距多远），而 $G$ 是梯度陡峭程度的界限。

仔细观察这个公式。它揭示了一种根本性的张力，这是学习核心的一种权衡。第一项 $\frac{D^2}{2\eta_T}$ ，如果我们的最终步长 $\eta_T$ 较大，它就会变小。第二项，涉及所有步长的总和，如果我们的步长较小，它就会变小。为了最小化我们的遗憾，我们需要平衡这两种相互竞争的力量。事实证明，完美的折衷方案是选择一个随时间衰减的步长。一个经典的选择是设置 $\eta_t$ 与 $1/\sqrt{t}$ 成正比。通过这种选择，界限中的两项最终都以 $\sqrt{T}$ 的速度增长。于是，我们得到了：总遗憾 $R_T$ 的量级为 $\sqrt{T}$ 。这是次线性的！我们的平均遗憾 $R_T/T \approx 1/\sqrt{T}$ ，随着 $T$ 的增长而消失。这个简单、直观的策略，即沿着负梯度方向，以精心选择的衰减步长前进，保证能够学习。

适应地形

$1/\sqrt{t}$ 的步长是一个通用的解决方案，但这有点像在任何场合都穿同样尺码的鞋子。有时，一个方向的地形比另一个方向更崎岖。想象一下，你正在浓雾中探索一个山脉。每走一步，你都能得到当地陡峭程度的读数。如果你一直发现南北方向极其陡峭，而东西方向则很平坦，你自然会开始在向北或向南移动时采取更小、更谨慎的步伐，而在向东或向西移动时采取更大、更自信的步伐。

像 AdaGrad 这样的自适应算法正是这样做的。它们不是使用预设的衰减计划，而是根据梯度的历史来调整学习率。规则很简单：如果算法过去看到了大的梯度，它就会为后续步骤缩小学习率。一种常见的方法是将时间 $t$ 的学习率设置为与迄今为止所见所有梯度平方范数之和的平方根成反比：

\eta_t \propto \frac{1}{\sqrt{\sum_{i=1}^t \|g_i\|_2^2 + \epsilon}}

其中 $\epsilon$ 是一个极小的数，以防止除以零。这使得算法能够自动“调整”自身以适应问题的几何结构，通常能带来比固定衰减计划好得多的实际性能。

当世界更友善时：寻找智慧的捷径

$O(\sqrt{T})$ 的遗憾是一个强大的保证，因为它即使在宇宙很“刁难”（但不是完全恶意）的情况下也成立。它对损失函数序列的假设非常少。但是，如果世界更有结构，或者说“更友善”呢？我们能学得更快吗？答案是肯定的。

可分世界与感知机

考虑一个简单的二元分类问题。在每一轮，我们得到一个数据点 $x_t$ 和一个标签 $y_t \in \{-1, +1\}$ 。我们的任务是学习一个权重向量 $w$ ，使得 $w^T x_t$ 的符号与标签 $y_t$ 相匹配。如果世界如此友善，以至于存在一个完美的“专家”向量 $u$ ，它能以一个舒适的安全边界正确分类每一个数据点呢？也就是说，对于每一轮 $t$ ，都有 $y_t(u^T x_t) \ge \gamma$ ，其中 $\gamma > 0$ 是某个正的间隔。

在这个结构美好的世界里，我们可以使用一个非常简单的算法：感知机 (Perceptron)。我们从 $w_1 = 0$ 开始。在每一步，如果我们犯了错误，我们就通过加上被错误分类的点来更新我们的权重： $w_{t+1} = w_t + y_t x_t$ 。如果我们做对了，我们什么也不做。

这个算法的分析是学习理论中最优雅的结果之一。通过同时追踪我们的权重向量范数 $\|w_t\|^2$ 如何增长（每次犯错它只能增加这么多）以及它与完美专家 $u$ 的对齐程度如何（每次犯错它必须变得更加对齐），我们可以证明算法所犯的错误总数是有限的，并由一个常数界定：

\text{总错误数} \le \left(\frac{R}{\gamma}\right)^2

其中 $R$ 是数据点 $x_t$ 的最大大小。错误的总数根本不依赖于时间跨度 $T$ ！这意味着遗憾不仅仅是次线性的，它是 $O(1)$ ——它变成了一个常数。经过有限次数的更新后，算法达到完美，不再犯错。这个优美的结果表明，有了更强的假设，就有可能获得显著更好的性能。

弯曲世界与对数遗憾

世界友善的另一种方式是损失函数具有更多的“曲率”。一个标准的凸函数可以有很大的平坦区域，就像一个宽阔平底峡谷的底部。在这些区域，梯度很小，几乎不提供关于真实最小值在哪里的信息。

但如果损失函数是强凸的呢？这意味着它们的形状像一个漂亮的、陡峭的碗，有一个清晰、唯一的最小值。这种额外的曲率是一份礼物。它意味着即使离最小值很远，梯度也能提供一个指向它的强烈信号。算法可以利用这种结构更积极地“锁定”目标。

对于这类强凸问题，我们可以设计出实现 $O(\log T)$ 遗憾的算法。这相对于 $O(\sqrt{T})$ 是一个指数级的改进。对于 $T=1,000,000$ ， $\sqrt{T}$ 是 1,000，而 $\log T$ 大约只有 14。一个很好的例子是使用像在线牛顿步 (Online Newton Step) 这样的复杂方法来处理逻辑斯谛回归，其损失函数具有一种称为 exp-凹性的性质，这与强凸性类似。这使得对数遗憾成为可能，而对于曲率较小的损失（如 hinge 损失），简单方法则被困在 $\sqrt{T}$ 的速率上。

在黑暗中学习：当梯度成为一种奢侈

到目前为止，我们一直假设在做出决策后，我们能看到梯度。这告诉我们本应朝哪个方向走。但如果反馈更为有限呢？如果我们只知道我们选择的那个点的损失值，而其他一无所知呢？这被称为赌博机反馈 (bandit feedback)。这就像一个厨师试图通过只品尝最终的蛋糕来完善食谱，而完全不知道改变糖或面粉的用量会如何影响味道。

我们如何可能仅凭一个函数值来估计梯度呢？最简单的想法是在一个随机方向 $u$ 上“戳”一下函数，看看会发生什么。我们可以构建一个单点估计量：

g_t^{(1)} = \frac{d}{\delta} f_t(x_t+\delta u) u

在这里，我们在一个随机方向 $u$ 上将我们的点 $x_t$ 扰动一个微小的量 $\delta$ ，并使用得到的函数值来估计梯度。这个估计量是无偏的（它的平均值是函数平滑版本的真实梯度），但它非常嘈杂。它的方差，衡量其噪声程度的指标，会像 $1/\delta^2$ 一样爆炸性增长。这种高方差污染了我们的学习过程，我们能期望的最好遗憾是相当令人失望的 $O(T^{3/4})$ 。

我们能做得更好吗？是的，只需一点点聪明才智。与其采样一个点，不如在我们当前选择的点周围对称地采样两个点： $x_t + \delta u$ 和 $x_t - \delta u$ 。然后我们可以基于它们的差值构建一个两点估计量：

g_t^{(2)} = \frac{d}{2\delta}\big(f_t(x_t+\delta u)-f_t(x_t-\delta u)\big) u

这是对导数的“中心差分”近似，是微积分中一个熟悉的概念。这对方差的影响是巨大的。因为我们取的是差值，函数值中大的、恒定的部分被抵消了。这个新估计量的方差不再依赖于 $1/\delta^2$ ；事实上，它根本不依赖于 $\delta$ ！这个更稳定的梯度估计使我们能够恢复熟悉的 $O(\sqrt{T})$ 遗憾界，即使在具有挑战性的赌博机设定中也是如此。这是一个绝佳的例子，说明算法设计中的微小改变可以对性能产生深远的影响。

对于评估成本非常高的函数，例如在材料科学或药物发现中，即使是两点查询也可能太多。在这里，更复杂的方法如贝叶斯优化 (Bayesian Optimization) 就派上用场了。这些算法为未知函数建立一个完整的统计模型（如高斯过程），利用值（均值）和不确定性（方差）来引导搜索。这个原则，即“面对不确定性时的乐观主义”，是相同的：在利用已知信息和探索未知信息之间取得平衡。

有风格地学习：追求简约

在许多现代问题中，尤其是在基因组学或金融等领域，我们处理大量的特征。我们可能试图学习一个有数百万参数的模型。在这种情况下，我们通常更喜欢一个简单或稀疏的解决方案——一个大多数参数都恰好为零的方案。稀疏模型更易于解释、评估速度更快，且不易过拟合。

我们能否在鼓励稀疏性的同时实现次线性遗憾？是的，通过使用复合损失 (composite losses)。我们在损失中加入一个正则化项，最流行的是 $\ell_1$ -范数， $\lambda \|x\|_1$ 。总损失变为 $f_t(x) + \lambda \|x\|_1$ 。

标准的梯度步长会难以处理 $\ell_1$ -范数在零点的“拐点”。解决方案是在线近端梯度下降 (Online Proximal Gradient Descent)。更新在概念上分为两步。首先，我们对损失的光滑部分 $f_t$ 进行正常的梯度步长。然后，我们应用一个特殊的“近端”步骤来处理 $\ell_1$ -范数。 $\ell_1$ -范数的这个近端算子是一个简单而优雅的函数，称为软阈值 (soft-thresholding)：

(\text{prox}(v))_i = \text{sign}(v_i) \max\{|v_i| - \theta, 0\}

对于我们向量的每个分量，这个算子从其大小中减去一个阈值 $\theta$ ，如果结果为负，它就将该分量精确地设置为零。这就是关键。这是一个能自然产生稀疏解的更新规则。值得注意的是，这种近端方法的遗憾分析与之前一样，得出了标准的 $O(\sqrt{T})$ 界。我们两全其美：既有学习的保证，又有找到简单、稀疏模型的趋势。

最后一点警示：遗憾没有告诉你的事

我们已经看到，实现次线性遗憾是一个强大而普遍的保证。它告诉我们，平均而言，我们将做得和事后看来最佳的固定决策一样好。但至关重要的是要理解这个保证没有说什么。

考虑一个多臂赌博机问题，你必须在两台老虎机之间做出选择。一台比另一台稍好一些，但它们平均回报的差异，即“间隙” $\Delta$ ，非常非常小。像 UCB（置信上界）这样的算法已知可以实现次线性遗憾。它会很快学会偏爱更好的那台机器，但因为间隙太小，它仍然会觉得有必要偶尔“检查”一下另一台机器，以确保万无一失。这种探索对于保持低遗憾是必要的。

现在，让我们通过让间隙 $\Delta_T$ 随着我们的时间跨度 $T$ 的增长而缩小，来使问题变得越来越难。我们可以构建一个场景，其中我们的遗憾是优美的次线性的，也许以 $O(T^{1/4})$ 的速度增长，但我们需要自信地识别哪台机器更好所需的样本数量却随时间增长，也许像 $O(T^{1/2})$ 。

这揭示了一个微妙但关键的区别。遗憾最小化是关于在长期内确保良好的累积性能。最佳臂识别（一种PAC 学习）是关于尽快以高置信度找到唯一的最佳选项。低遗憾并不自动意味着快速识别。一个算法可以在平均意义上学会表现良好，但对于绝对的真相仍然可能在很长一段时间内保持不确定，尤其是在差异微弱的时候。理解这种区别是明智地将这些强大的思想应用于现实世界的关键。

应用与跨学科联系

“我能够接受怀疑、不确定和未知。我认为，活在未知中比拥有可能是错误的答案有趣得多。” Richard Feynman 的这句优美表达，正是科学探究的灵魂。但是，尽管我们可以与不确定性共存，我们仍然必须行动。我们必须做出决策。那么，核心问题就是，当并非掌握所有事实时，如何做出尽可能好的决策？

在上一章中，我们揭示了一个深刻的数学原理来做到这一点：次线性遗憾。我们发现，可以为在时间跨度 $T$ 内的重复决策设计策略，这些策略在非常精确的意义上是“保证能学习”的。虽然我们不可避免地会犯一些错误，但这些错误的总成本——我们的累积遗憾——可以被控制得增长得如此之慢，以至于我们的每轮平均遗憾 $\frac{1}{T} \sum_{t=1}^T (\text{loss}_{\text{our},t} - \text{loss}_{\text{oracle},t})$ 会随着时间的推移而消失。我们的表现变得与一个从一开始就知道正确答案的神话般的“神谕”无法区分。

这是一个强有力的论断。但这仅仅是一个局限于抽象方程世界的理论奇珍吗？还是说这个原理正在我们周围的世界中发挥作用？我们已经锻造了一把万能钥匙。现在，让我们带着它去散散步，看看它究竟能打开多少扇不同的门。我想你会发现，结果是相当惊人的。

我们栖身的数字世界

让我们从你可能几分钟前刚经历过的事情开始：个性化的互联网。每当你打开一个新闻应用、一个流媒体服务或一个社交媒体信息流，一个决策正在被做出。在一个包含 $n$ 篇文章、视频或帖子的宇宙中，应该向你呈现哪 $k$ 个项目？服务提供商并不完全了解你的品味。它面临一个巨大的“多臂赌博机”问题。每一条内容都是一个“老虎机”，而你的点击就是“头奖”。它应该如何选择向你展示什么呢？

如果它只根据过去的行为（纯利用）向你展示它认为你喜欢的东西，它可能会错过一个你本会爱上的全新类型。如果它只向你展示随机的东西来了解你（纯探索），你的信息流会感觉混乱和不相关。要取得成功，服务必须平衡这种权衡。而做得最好的算法，恰恰是那些保证次线性遗憾的算法。它们使用像“面对不确定性时的乐观主义”这样的原则来智能地探索，确保总遗憾——他们获得的互动量与他们本可以通过完美了解你的品味而获得的互动量之间的累积差异——呈次线性增长。这意味着随着时间的推移，系统会成为你的专家，而其最初无知的成本变得可以忽略不计。我们现在习以为常的流畅、个性化的体验，在很多方面，都是次线性遗憾实践力量的证明。

计算本身的艺术

也许更令人惊讶的是，这种学习原理不仅用于优化我们与计算机的互动；计算机也可以用它来优化自身。思考一个基本任务，比如乘以两个非常大的 $n$ 位数。有不同的方法可以做到。我们在学校学到的方法很简单，但很慢。Karatsuba 算法更快，其复杂度大约为 $O(n^{\log_2 3})$ 。对于真正巨大的数字，基于快速傅里叶变换 (FFT) 的算法甚至更快，大约为 $O(n \log n)$ 。

一个软件库应该使用哪一种？答案取决于数字的大小。存在一些“交叉点”，在这些点上一个算法变得比另一个更好。我们可以尝试手动找出这些点，但如果我们把它框定为一个学习问题呢？我们可以将每个可能的交叉点视为一个给我们建议的“专家”。每当程序需要做一次乘法时，它在某种意义上可以询问专家。通过使用像乘法权重更新法这样的简单次线性遗憾算法，程序可以听取这些专家的意见，看看他们的建议表现如何，并动态更新对他们的信任。在很短的时间内，系统学会了信任哪个专家——也就是说，它根据其在运行机器上的实际性能自动找到了最佳的交叉点。其花费的总时间保证几乎与一个神谕从一开始就告诉它最佳设置一样好。

这个想法可以被进一步推进。一个任务的最佳算法可能不依赖于像输入大小这样简单的事情，而是依赖于数据本身更微妙的结构特性，比如它的香农熵 $H(P)$ 。通过将在“运行中”估计这些属性的流式算法与学习框架相结合，我们可以构建自适应程序，实时为工作选择最佳工具，同样地，为其做出错误选择的遗憾被证明是最小的。机器学会了如何学习。

科学发现的新引擎

到目前为止，我们看到的应用都非常了不起，但它们都存在于计算机内部。当我们采取的“行动”不是选择比特，而是操纵原子时，会发生什么？同样的原则也适用，其后果对科学是变革性的。

考虑定向进化的挑战，这是一种用于为药物或工业酶工程改造新蛋白质的技术。科学家创造了巨大的突变基因库，然后面临着找到少数具有所需特性的“命中”的艰巨任务。实验预算总是有限的。你应该测试哪些突变体？这又是一个多臂赌博机问题，但这次是在宏大的生物学尺度上。每个变体库都是老虎机的一个臂。一次实验测试就是拉动一次臂。一个成功的新蛋白质就是头奖。像 UCB（置信上界）和 Thompson 抽样这样的次线性遗憾算法为分配宝贵的实验预算提供了一个正式的方案。它们规定了一种精确的方式来平衡测试当前最有希望的变体（利用）和探索那些被忽视的奇怪变体（探索）。这种数学指导极大地加速了生物技术领域的发现步伐。

这一范式延伸到了生物学最前沿的领域。想象一下，你想通过删除所有非必需基因为细菌创建一个“最小基因组”，这是合成生物学中的一个核心挑战。或者，你正试图找到数十种生长因子的完美组合，以诱导干细胞形成复杂的类器官，比如培养皿中的微型大脑。在这两种情况下，可能性的空间都大得惊人，而且每个实验都极其昂贵和耗时。

这些不再是简单的赌博机问题，因为选择不是独立的。删除一个基因可能与删除其在染色体上的邻居有相似的效果。一种生长因子的效果平滑地依赖于另一种的浓度。在这里，我们可以使用更复杂的学习模型，如高斯过程，来捕捉这些相关性。但核心哲学保持不变。算法为未知景观建立一个概率性的“代理”地图。然后它使用一个采集函数——UCB 思想的直系后代——来决定下一步在哪里采样，明确地在利用已知高产区域和探索高不确定性区域之间进行权衡。这一系列技术，被称为贝叶斯优化，是次线性遗憾思维方式的直接应用。它使科学家能够在几十次实验中找到最佳的基因设计或分化方案，而暴力方法可能需要数百万次 [@problem_-id:2741561]。它是科学发现的新引擎，将不确定性从障碍变成了向导。

学习系统的无形统一

到目前为止，你可能已经感受到了这个想法的普遍性。它似乎无处不在。让我们通过几个例子来结束，揭示它作为一个深刻、统一的原则的角色。

首先，考虑我们经常面临的复杂的组合选择。它并不总是关于挑选一个最佳选项，而是关于选择一个选项团队来完成一项工作——比如一个物流公司选择一组每日的送货路线来覆盖所有目的地，而每条路线上的交通状况是未知且波动的。这是一个“组合赌博机”问题。在这里，“面对不确定性时的乐观主义”原则也可以被扩展，以引导公司走向一个接近最优的路线策略，其总成本被证明与一个无所不知的神谕相近。

接下来，让我们转向博弈论。想象一下两个玩家在一场竞争性的零和博弈中。他们不知道对方的策略。他们应该如何玩？一个引人入胜的结果表明，如果两个玩家都使用一个次线性遗憾算法来根据过去几轮的结果更新他们的策略，整个系统将收敛到一个纳什均衡——一个稳定的状态，其中没有玩家有单方面改变策略的动机。每个玩家的累积遗憾直接关系到游戏离这个均衡有多远。这是一个在复杂系统中寻找平衡的美妙的、去中心化的机制。甚至学习算法的几何结构——无论是用欧几里得距离还是信息论散度来思考——也巧妙地影响着通往均衡的路径，这是一个优美理论中的优美细节。这不仅适用于棋盘游戏，也适用于理解拍卖、金融市场甚至生态竞争中的动态。

最后，也许是最深刻的，考虑一下卡尔曼滤波器。半个多世纪以来，这个算法一直是工程和应用科学的基石。它是 GPS 接收器、天气预报模型和航天器导航背后幕后的数学奇才。它是一种通过不断地将物理模型的预测与嘈杂的测量值相融合来跟踪动态变化系统（如卫星位置）的方法。它是数据同化的黄金标准。

另一方面，在线学习领域的发展在很大程度上是独立的，专注于机器学习任务的遗憾最小化。然而，如果你深入研究，会发现两者之间有着深刻的联系。卡尔曼滤波器的核心数学更新可以被证明等同于解决一个特定的在线学习问题：一个在线版本的岭回归。在被跟踪的系统实际上是静态的特殊情况下，卡尔曼滤波器的性能保证可以用次线性遗憾的语言重新解读。事实证明，这个著名的工程工具，在某种意义上，一直都是一个伪装的次线性遗憾算法。还有什么比这更能震撼地展示科学思想的统一性呢？两个不同的社群，从不同的问题出发——跟踪导弹与预测用户点击——最终得到了相同的基本数学结构。

从个性化我们的新闻推送，到优化我们的算法，到发现新药，到在游戏中找到平衡，再到在轨道上跟踪卫星——次线性遗憾的原则是一条共同的线索。它是一种关于乐观主义和好奇心的形式化理论。它教导我们，虽然我们无法消除不确定性，但我们可以智能地与之互动，确保我们在未知中的旅程是高效的。对次线性遗憾的追求，无非就是如何学习的数学形式化。