基于结构化损失函数的数据驱动多超参数调优的紧确界

# 带有结构化损失函数的数据驱动多超参数调优的紧界  
来源：https://arxiv.org/html/2608.17343  

###### 摘要  
数据驱动的算法设计将超参数调优构建为统计学习问题，但由于模型性能对超参数的隐式、非光滑依赖性，建立泛化保证仍然具有挑战性。在分段多项式假设下的现有多维界在理论上仍然宽松，且缺乏全面的下界。我们通过建立多维数据驱动调优的紧伪维度界来解决这一问题。首先，我们利用实代数几何改进了学习理论的上界；通过分析块消元过程中不变的连通符号单元，而非孤立的符号向量，我们避免了拓扑过计数，从而推导出严格更优的样本复杂度。其次，我们提出了一个将组合容量和代数容量解耦的多区间下界框架。通过构造跨越不同区间的破碎问题实例，我们证明了我们的上界是紧密饱和的。最后，我们将拓扑框架扩展到适用于一般双层验证损失调优和更广泛的半代数应用。  

## 1 引言  
现代机器学习的成功在很大程度上依赖于对超参数的精心选择[27]([链接]); [1]([链接])。尽管超参数在模型部署中起着核心作用，但它主要被视为一种经验技艺，而非严格的分析学科。传统方法，如穷举网格搜索或随机搜索，将连续参数空间离散化，通过经验验证来识别高性能配置。虽然在实践中简单直接，但这些暴力方法在理论上缺乏原则，并且无法在连续超参数空间上提供形式化的泛化保证。为自动化这一过程，从业者通常依赖复杂的启发式搜索策略，包括贝叶斯优化[14]([链接])和谱方法[18]([链接])。然而，这些技术通常依赖于限制性的结构假设，例如将损失曲面建模为平滑的高斯过程，而这往往无法捕捉现代目标函数的高度波动、非凸特性。此外，像Hyperband[22]([链接])这样的资源分配策略通过提前停止在计算效率上表现出色，但它们主要关注离散搜索空间和固定的问题实例。因此，这些框架缺乏理论工具来描述识别最优连续超参数的基本统计复杂性。  

为弥合理论差距，数据驱动的算法设计范式[17]([链接]); [8]([链接])将超参数调优构建为在未知的、应用特定的问题分布 $\mathcal{D}$ 上的正式统计学习问题。给定来自问题空间 $\mathcal{X}$ 的分布 $\mathcal{D}$ 的有限训练实例样本 $S \sim \mathcal{D}^N$，目标是识别一个超参数配置，该配置可证明能泛化到来自同一分布的未见问题实例 $x \sim \mathcal{D}$。此过程本质上是双层的：诱导损失 $\ell_{\alpha}(x) = \inf_{\theta \in \mathcal{S}(x, \alpha)} g(x, \alpha, \theta)$ 在目标验证目标 $g$ 上评估，而模型参数 $\theta$ 在代理训练目标 $f$ 上优化，即 $\mathcal{S}(x, \alpha) = \arg\min_{\theta \in \Theta} f(x, \alpha, \theta)$。例如，在岭回归中，问题实例 $x = (A, b, A', b') \in \mathcal{X}$ 包括训练集和验证集。超参数 $\alpha$ 显式正则化训练目标 $f(x, \alpha, \theta) = \|A\theta - b\|_2^2 + \alpha \|\theta\|_2^2$，但通过最优权重 $\theta \in \mathcal{S}(x, \alpha)$ 仅隐式地影响验证目标 $g(x, \alpha, \theta) = \|A'\theta - b'\|_2^2$。界定这种非光滑依赖性的统计复杂性（其中 $\alpha$ 仅通过辅助问题的 argmin 起作用）是我们面临的基本理论障碍。  

为克服这一挑战，我们利用统计学习理论来界定超参数诱导的损失函数类 $\mathcal{L} = \{\ell_{\alpha}: \mathcal{X} \rightarrow [-H, H] \mid \alpha \in \mathcal{A}\}$ 的泛化能力，该能力通过伪维度衡量。我们的分析依赖于一个结构性观察：对于许多实际的机器学习问题，训练目标 $f_x(\alpha, \theta) \triangleq f(x, \alpha, \theta)$ 在超参数 $\alpha$ 和模型参数 $\theta$ 两者上都具有分段多项式结构；例如，参见定义7的正式定义和图2的简单示例。这种分段多项式假设非常普遍：它已在经典学习理论[11]([链接]); [24]([链接]); [10]([链接])和最近的数据驱动算法设计框架[5]([链接]); [7]([链接]); [25]([链接])的广泛领域中被严格确立。  

尽管这种结构普遍存在，现有的泛化保证仍然存在根本性限制。[3]([链接])为此设置提供了第一个正式框架，但其特设的低维几何分析高度受限：它仅适用于一维超参数（$\alpha \in \mathbb{R}$）和单层目标（$f \equiv g$）。[21]([链接])成功地将此分析扩展到多维超参数（$\alpha \in \mathbb{R}^p$）和一般双层目标（$f \not\equiv g$），使用了模型论方法。然而，他们的统计界已被证明是次优的。他们严重依赖量化消去（QE）[13]([链接])，随后是Goldberg-Jerrum（GJ）框架[9]([链接])，由于拓扑欠计数和放大的代数依赖性，他们的方法产生了过于保守的上界。此外，他们未能建立捕捉问题真实组合容量的下界，特别是随分段结构复杂性（如分段数量和边界数量）缩放的下界。这些未解决的理论差距直接激发了本工作开发的紧界技术。  

**贡献**。在这项工作中，我们通过建立多维设置下的改进伪维度界，解决了先前数据驱动超参数调优框架的理论限制。我们的核心贡献是：  
- • 我们在定理4.2中确立，如果一个损失函数在多项式一阶逻辑（FOL）中可定义，则其伪维度由嵌套块消元过程的拓扑复杂度紧密界定。通过分析不变的连通符号单元，此方法绕过了先前量化消去方法[21]([链接])放大的代数依赖性。  
- • 我们将嵌套块消元框架应用于标准训练损失设置（$f \equiv g$），其中底层目标 $f(x, \alpha, \theta)$ 表现出分段多项式结构（定理5.1）。通过将诱导损失 $\ell_{\alpha}(x) = \min_{\theta \in \Theta} f(x, \alpha, \theta)$ 表示为多项式FOL，我们推导出严格更优的伪维度界，直接解决了先前工作[21]([链接])次优的多维保证。  
- • 我们在引理5.2和5.3中用新颖的多区间下界框架补充了我们的上界。通过独立分析组合（$T_f, M_f$）和代数（$\Delta_f$）容量，我们证明了我们的上界相对于 $T_f$ 和 $\Delta_f$ 是紧的，相对于 $M_f$ 是近似紧的。这确立了我们理论保证中每个结构参数的基本必要性。  
- • 我们将框架扩展到一般双层验证损失设置和更广泛的半代数应用（定理6.1和7.1）。通过将嵌套块消元应用于验证损失调优，我们消除了先前工作放大的代数依赖性。此外，我们通过分析加权Group Lasso展示了框架的多功能性，适应了超越分段多项式的结构，并将现有样本复杂度界严格改进了一个因子 $p$。  

**技术差异与概述**。界定多维双层超参数调优的泛化能力需要捕捉验证损失对超参数的隐式、非光滑依赖性。先前的模型论工作通过应用标准量化消去（QE）然后使用Goldberg-Jerrum框架[21]([链接])来处理此问题。然而，由于严重的拓扑过计数，此策略产生了高度次优的统计界。为解决此问题，我们引入了一个基于嵌套块消元的新几何框架。我们不是评估孤立的符号条件，而是递归地构建一个嵌套的块符号轮廓，以跟踪多项式公式在完整连通符号单元上的逻辑不变性。这种拓扑转变完全绕过了标准QE固有的代数膨胀，使我们能够为多维调优问题推导出严格更优、最优的样本复杂度保证。详见附录A.2的详细讨论。  

**符号**。对于实值 $t \in \mathbb{R}$，我们定义 $\text{sign}(t) = 0$ 若 $t = 0$，$\text{sign}(t) = 1$ 若 $t > 0$，否则 $\text{sign}(t) = -1$。对于变量 $z \in \mathbb{R}^k$，我们用 $\mathbb{R}[z]$ 表示 $z$ 的多项式环，包含 $z$ 的所有（多元）多项式；例如，对于 $z \in \mathbb{R}^2$，$P(z) = z_1^2 + z_2^2 \in \mathbb{R}[z]$。给定多项式 $P(z)$，我们用 $\deg(P)$ 表示 $P(z)$ 的次数；例如，对于 $P(z) = z_1^2 + z_2^2$，$\deg(P) = 2$。对于一个同时以 $z$ 和 $x$ 为输入变量的函数 $h(z, x)$，我们用 $h_x(z) \triangleq h(z, x)$ 表示当 $x$ 固定而 $z$ 变化时的诱导函数。对于逻辑句子 $A$，我们用 $\mathbb{I}(A) = 1$ 若 $A$ 为真，否则为 0；例如，$\mathbb{I}(1 > 0) = 1$，且 $\mathbb{I}(0 > 1) = 0$。  

### 1.1 相关工作  
##### 数据驱动的算法设计。数据驱动的算法设计[17]([链接]); [8]([链接])将超参数调整为特定的问题分布，而不是依赖最坏情况实例。这一范式在包括草图[23]([链接]); [19]([链接])、线性和混合整数规划[29]([链接]); [25]([链接]); [4]([链接]); [15]([链接]); [20]([链接])以及正则化调优[6]([链接]); [7]([链接])在内的多个领域取得了显著的实证成功。  
##### 数据驱动算法设计的理论保证。受实证成功的激励，近期工作寻求为数据驱动的算法设计建立统计保证[5]([链接]); [9]([链接]); [2]([链接])。然而，非光滑、可能不连续的超参数曲面 $\ell_x(\alpha)$ 使得这具有挑战性，导致大多数分析避免了在模型参数 $\theta$ 上的内层优化。虽然[3]([链接])解决了这个更难的双层情况，但他们的框架仅限于一维超参数（$\alpha \in \mathbb{R}$）和单层目标（$f \equiv g$）。[21]([链接])最近将其扩展到多维（$\alpha \in \mathbb{R}^p$）和一般双层设置（$f \not\equiv g$），但他们的复杂性界在理论上仍然宽松且缺乏下界；这些正是我们在本工作中解决的差距。  

## 2 预备知识  
### 2.1 学习理论背景  
我们首先回顾学习理论中的一些标准结果，这些结果在本工作中起着核心作用。  

###### 定义 1（伪维度[26]([链接])）。  
考虑一个由 $\alpha \in \mathcal{A}$ 参数化的实值函数类 $\mathcal{L} = \{\ell_{\alpha}: \mathcal{X} \rightarrow \mathbb{R} \mid \alpha \in \mathcal{A}\}$。给定输入集合 $S = (x_1, \dots, x_N) \subset \mathcal{X}$，如果存在实值阈值 $\tau_1, \dots, \tau_N \in \mathbb{R}$ 使得 $\left| \{ (\mathbb{I}(\ell_{\alpha}(x_1) \geq \tau_1), \dots, \mathbb{I}(\ell_{\alpha}(x_N) \geq \tau_N)) \mid \ell_{\alpha} \in \mathcal{L} \} \right| = 2^N$，则称 $S$ 被 $\mathcal{L}$ 打破。$\mathcal{L}$ 的伪维度，记为 $\text{Pdim}(\mathcal{L})$，是 $\mathcal{L}$ 能够打破的最大输入集合大小 $N$。有限的伪维度通过经验风险最小化（ERM）保证一致收敛。  

###### 定理 2.1 ([26]([链接]))。  
考虑一个由 $\alpha \in \mathcal{A}$ 参数化的实值函数类 $\mathcal{L} = \{\ell_{\alpha}: \mathcal{X} \rightarrow [-H, H] \mid \alpha \in \mathcal{A}\}$。假设 $\text{Pdim}(\mathcal{L})$ 是有限的。则对于任意 $\epsilon > 0$ 和 $\delta \in (0, 1)$，存在 $N \geq N(\epsilon, \delta)$，其中 $N(\epsilon, \delta) = \mathcal{O}\left( \frac{H^2}{\epsilon^2} (\text{Pdim}(\mathcal{L}) + \log(1/\delta)) \right)$。