技术摘要：裁剪尾部以降低适应代价

问题陈述

本文探讨了无参数随机凸优化 (SCO) 中的一个基本局限性。标准的自适应方法面临着“适应代价”（price of adaptivity）的障碍：在一般假设下，它们无法高效地适应初始到最优点的距离 ($D^\star$) 和 Lipschitz 常数 ($L^\star$) 的巨大不确定性。

现有的下界（例如 Carmon 和 Hinder [6]；Attia 和 Koren [1]；Khaled 和 Jin [16]）表明，对于一般的随机函数 $f(x; s)$，无参数方法会产生一个与 $\min\{\ell, \rho\}$ 成比例的乘性惩罚，其中 $\ell$ 和 $\rho$ 分别代表 $L^\star$ 和 $D^\star$ 的不确定性因子。具体而言，最优差距会以 $\Omega(\min\{\ell, \rho\} \sqrt{\ln(1/\delta)/T})$ 的因子退化。这意味着，在没有精确了解问题参数的情况下，在高度不确定性的情形下实现近优速率，对于一般的 SCO 而言在理论上是不可能的。

然而，作者观察到，这些下界适用于一般形式 $F(x) = \mathbb{E}[f(x; s)]$，但不一定适用于机器学习中普遍存在的模型-损失分解 (model–loss decomposition) 结构：
$$F(x) = \mathbb{E}_{s \sim P}[h(m(x; s); s)]$$
其中 $m$ 是一个模型，$h$ 是一个损失函数。本文研究了利用这种内部结构是否可以规避已建立的下界。

方法论

核心洞察在于，“适应代价”是由尾部事件 (tail events) 驱动的：即那些函数行为与主体分布差异巨大的罕见样本。在一般设定中，这些事件是不可观测且不可控的。在模型-损失设定中，作者提出在应用损失函数之前，在模型输出层面进行干预。

该方法涉及在推理阶段裁剪模型输出 (clipping the model output)。如果模型 $m(x; s)$ 产生的预测值是一个显著偏离参考模型输出的离群值，则将该输出裁剪到一个有界定义域内。这可以防止损失函数放大那些罕见的、高幅度的预测所带来的误差。

本文基于这一原理提出了两种不同的算法：

1. 计算高效型方法 (第 4 节)

该方法优先考虑计算效率（梯度评估次数）而非样本效率。

• 机制： 它通过对超参数（步长、裁剪阈值）进行网格搜索，生成一组候选权重 $\{x_g\}$。
• 模型选择： 它采用了一种可靠的模型选择框架（基于 Lawrence 等人 [18]），以选择与最优裁剪参数 $c$ 配对的最佳候选权重。
• 裁剪策略： 对于每个候选权重，算法会考虑一组基于模型输出偏差经验分布而得出的裁剪参数。它计算每一组（权重，裁剪）对的损失置信区间。
• 结果： 该方法选择一对 $(x, c)$，使验证损失加上风险项后的总和最小化。
• 复杂度： 该方法实现了 $\tilde{O}(L^\star D^\star \sqrt{\ln(1/\delta)/T})$ 的最优差距，其中 $T$ 是梯度评估次数。至关重要的是，其对不确定性的依赖是对数级的，而非多项式级，从而绕过了一般 SCO 的下界。

2. 样本高效型方法 (第 5 节)

该方法优先考虑样本效率（样本数 $N$），并匹配已知参数 SCO 的最优界限。

• 机制： 算法首先使用一组初始样本来估计 Lipschitz 常数的下界 $\hat{L}$。
• 条件化： 然后，它抽取额外的样本，这些样本是以模型为 $\hat{L}$-Lipschitz 为条件的。
• 优化： 它在这个条件分布上求解一个正则化优化问题，以找到一个权重 $x_{perfect}$。
• 输出： 最终输出是权重 $x_{perfect}$ 以及配套的裁剪参数 $\hat{L}\|x_{perfect} - x_0\|_\alpha$。
• 结果： 该方法实现了 $O(L^\star D^\star \sqrt{\ln(1/\delta)/N})$ 的最优差距，即使在不知道 $L^\star$ 或 $D^\star$ 的情况下，也能达到已知参数 SCO 的水平。

核心贡献

1. 识别尾部事件障碍： 作者指出，无参数 SCO 的下界与一般随机设定中的尾部事件密切相关。他们认为，模型-损失结构允许检测并缓解这些事件。
2. 模型输出裁剪： 他们引入了一种在推理时裁剪模型输出的技术，以防止极端的罕见预测主导损失。这有效地“修剪”了梯度噪声分布的重尾部分。
3. 规避下界： 通过利用模型-损失分解，所提出的方法实现了近优的最优差距，且对问题参数不确定性的依赖仅为对数级。这严格优于一般 SCO 中关于不确定性的线性依赖（$\min\{\ell, \rho\}$）。
4. 两种算法范式：
   • 一个使用网格搜索和可靠模型选择的计算高效型方法。
   • 一个使用条件采样和正则化的样本高效型方法。
5. 下界的理论分析： 本文正式分析了哪些下界仍然适用于模型-损失设定。他们证明了对于已知参数的最优速率仍然成立（意味着所提方法是近优的），但依赖于对抗性尾部构造的关于未知参数的下界不再适用，因为裁剪机制中和了对抗优势。

结果

• 计算设定： 所提方法实现了 $\tilde{O}(L^\star D^\star \sqrt{\ln(1/\delta)/T})$ 的最优差距。这击败了 Carmon 和 Hinder [6]、Attia 和 Koren [1] 以及 Khaled 和 Jin [16] 的下界，后者的规模随不确定性参数线性缩放。
• 样本复杂度设定： 所提方法实现了 $O(L^\star D^\star \sqrt{\ln(1/\delta)/N})$ 的最优差距。尽管算法是在处理未知参数，但它达到了已知参数随机凸优化的最优下界。
• 鲁棒性： 研究表明，这些方法不仅对标准 Lipschitz 情况有效，对重尾梯度噪声（二阶矩 Lipschitz 情况）也具有鲁棒性。

意义与主张

本文声称，“适应代价”并非随机优化中固有的基本限制，而是由于缺乏结构性假设而导致的一般问题表述的结果。通过假设机器学习中标准的模型与损失函数分解，并通过输出裁剪进行干预，可以高效地适应 $L^\star$ 和 $D^\star$ 的巨大不确定性。

作者强调，其结果是近优的。他们证明了已知参数下的下界 $\Omega(L^\star D^\star \sqrt{\ln(1/\delta)/\sqrt{N}})$ 在模型-损失设定下依然成立，这意味着其方法无法被进一步显著改进。然而，他们成功消除了困扰一般无参数方法的与参数不确定性相关的乘性惩罚。

这项工作表明，在实际的机器学习场景（例如神经网络）中，由于模型-损失结构无处不在，无参数优化可以比以往在一般理论框架下认为的更加高效。