作业一

作业一 第1题

解答

这里的趋近符号似乎含义没有标识清楚，这里默认为是当 趋近于无穷大时的极限关系。

由 Chebyshev’s Inequality 得

综上 ，由夹逼定理得 .

作业一 第2题

解答

记 ，则由 有界且期望为 ，结合课上推论有 是一个鞅。

由 Azuma 不等式及其反向版本，结合条件

可得

题中不等式即证。

作业一 第3题

解答

则 ，即只需证明新聚类的加权中心偏离程度的期望等于原数据的平均偏离程度乘以 。

其中 的拆分来自不放回抽样得到样本均值的方差公式 . 综上

作业一 第4题

解答

作业一 第5题

解答

我们先研究 的分布情况. 记 ，则 .

由 Gaussian 分布的线性组合性质有 ，对于方差可计算得

因此 的每个分量都独立采样自 ，满足引理条件，由引理得

采用 Union bound 技术处理，题中点对的总数为 ，得

综上，

作业二

作业二 第1题

解答

时的情形：全空间都被投影到一个点上 . 因此只需要优化

由二次函数的性质可知，最优解为 ，即重心.

时的情形：全空间被投影到一条直线上 ，其中 为单位向量.

对 求导得

可得最优解为 ，即重心.

作业二 第2题

解答

由正态分布可加性有 ，因此概率上界与距离负相关，即

作业二 第3题

解答

(1) 这是考试题。由于对量化误差上界的限制，考虑先固定量化中心 . 则 的取值范围为以 为球心、半径为 的闭球内部. 由几何性质有在每个子空间中 的投影都依次共线且 取最大值 时平方距离差取到上界，因此全空间中

即得证.

(2)

要使得以上不等式链成立只需使得 .

所以为了在量化后保证近邻关系不被破坏，需要通过增加量化中心个数以降低 、增加中心并优化算法提升量化精度以降低 、或或在保证 和 的前提下降低量化后维度 来取舍.

作业二 第4题

解答

(1) 由不放回抽样事件之间的独立性有

因此由 Hoeffding 不等式有对已知的 ，

由 Union Bound 对任意的 ，有失败事件

因此 ，得证.

(2) 记 . 将上一问的高概率条件应用在 上得

作业三

作业三 第1题

解答

同理，.

将 满足的 coreset 不等式相加得到

因此 是 的一个 .

作业三 第2题

解答

合并两个 并再计算一个 得到的结果满足：

递归地计算可以得到根节点得到的带权集合 满足

由二项式定理容易证明 ，综上满足 ，根节点集合是 的 .

进一步证明：

，因此此时根节点集合是 的 .

作业三 第3题

解答

下界： 对于六个点 ，设置它们的正负类为 .

则我们总能构造出一个符合条件的范围：

因此 .

上界： 对于任意七个点的集合分布，考虑设置在三个坐标轴上取最大、最小值的点为正类，则剩余一个负类点 。由于 一定位于其它点的轴对齐包围盒中，而轴对齐包围盒一定是满足正类条件的 的子集，因此 无法被正确分类，因此无法实现七个点的任意划分，.

综上 .

作业三 第4题

解答

Note: 三角不等式：这里的 对应一个“搬运”操作。把信息从 搬运到 ，再搬运到 ，开销一定比直接搬运到 更大。

定义 为 到 的最优传输多面体，即 ， 同理。构造

易验证 . 接下来证明 .

用对数和不等式可得

再逐项求和即得 . 而对左式的操作为

综上 .

最后

因此 满足三角不等式。

Note: 非严格度量：在信息传输存在干扰的条件下，保持信息不变也需要开销，因此原地不动的开销不一定为零。

我们找到一个反例，不难验证以下 符合要求：

假设 .

结合 的要求有 . 结合搬运条件 有 唯一.

但 ，矛盾。

因此 ， 不是一个严格度量。

作业三 第5题

解答

  • 目标函数
  • 行和约束
  • 列和约束

由此写出拉格朗日函数

令

即得最优化解满足 Sinkhorn 形式.

作业四

作业四 第1题

解答

中心化的一轮更新为

由于求和中项可交换，可验证 MapReduce 的实现是和中心化一致的。

分布式情形下，对于每条跨机器边，需要传输 bits 的信息，因此一轮迭代中需要跨机器传输的通信量为 ，由此降低 可以减少每轮迭代的通信负担，降低通信瓶颈。

作业四 第2题

解答

由每个分量之间的独立性

由不同分布式服务器的独立性假设可证

直接上传所有梯度的通信量为 ，上传二值量化后的通信量为 ，优化了一个因子.

作业四 第3题

解答

  • SGD

    直接沿着最速梯度下降方向更新。缺陷是容易在鞍点震荡、对全局学习率敏感。

  • Momentum

    引入了动量（惯性）机制，以减少方向上的震荡、达到更稳定的优化，解决了鞍点及震荡的问题。

  • Adagrad

    引入了自适应学习率机制，通过累积历史梯度的平方来调整每个参数的学习率，适合稀疏数据，但可能导致学习率过早衰减。

  • RMSProp

    引入了指数加权移动平均机制，使得算法只受近期梯度幅度影响，解决了 Adagrad 学习率过早衰减的问题，适合非平稳目标。

  • Adam

    结合了 动量 + 自适应缩放 + 偏置校正机制，适用于大多数优化问题，具有较快的收敛速度和较好的性能表现。

作业四 第4题

解答

(1)

由此近似目标函数梯度的一个无偏估计为 ，参数更新形式为

(2) 函数的另一重意义是 范数，因此可以按这个思路定义：

可验证 .

参数更新形式为

作业四 第5题

解答

由方差分解定理 ，代入 得

由定义 得

对于 .

由此 会被正确分类到 . 对于 同理.

对于任意 ，其被错误分类的概率为

由此被正确分类的点数至少为 .

作业四 第6题

解答

由于 为 稀疏向量，显然 中非零元素要求必须在 和 的非零元素位置上，因此 最多有 个非零元素， 是 稀疏向量。应用 阶 RIP 即得证

基于 最小化的恢复形式为

由于 空间的复杂性，通常可写成 Lasso 形式：

基于生成模型的恢复形式为

最小化恢复形式实际上假设的是 有较多零元素（稀疏性），从而恢复的结果也应当有尽可能小的 范数。而生成模型假设对 的分布有更好的先验，对采样率要求更低，但受限于生成模型的表达能力，可能无法准确恢复 .

2025 年期末考试 第 4 题

解答

考虑递归地覆盖集合 以得到足够小以能划分所有元素的簇。

每次递归地将集合覆盖成 个直径不超过原来一半的子集，则经过 次划分后，将得到 个子集，所有子集的直径不超过 ，因此每个子集最多包含一个元素。

从而可以自然地导出不等式 .

2025 年期末考试 第 5 题

解答

这是线性插值形式，自然满足重心共线.

References