技术摘要：含整数变量的随机优化样本复杂度

1. 问题陈述

本文研究了决策变量 $x$ 被约束为整数向量的随机优化问题的样本复杂度。基本问题表述为：
$$\min_{x \in X} F_D(x) := \mathbb{E}_{z \sim D}[f(x; z)]$$
其中 $X \subseteq \mathbb{R}^d$ 是约束集（具体关注球的整数子集），$f: X \times Z \to \mathbb{R}$ 是损失函数，$D$ 是可测空间 $Z$ 上的未知概率分布。目标是利用来自 $D$ 的有限个独立同分布（i.i.d.）样本，以高概率（$1-\delta$）找到一个 $\epsilon$-近似解。

作者旨在刻画整数性要求如何影响与相应连续优化问题相比所需的样本数量。他们分析了三种标准的样本复杂度概念：

1. 一致收敛 (UC)：为使经验风险 $F_S(x)$ 在整个定义域内与总体风险 $F_D(x)$ 在 $\epsilon$ 范围内一致逼近所需的样本数量。
2. 经验风险最小化 (ERM)：为确保最小化经验风险能产生总体风险的 $\epsilon$-最优解所需的样本数量。
3. 任意数据驱动算法：任何基于样本输出解的算法（不仅限于 ERM）所能达到的最优样本复杂度。

2. 方法论与框架

作者结合了信息论下界和经验过程理论（用于上界）。

• 下界：证明依赖于构造困难的分布实例（通常涉及隐藏符号向量或有偏硬币翻转），并将优化问题归约到假设检验或参数估计任务。所用工具包括 Fano 不等式、KL 散度界（Pinsker 不等式）以及打包论证（构造具有较大成对距离的点集）。
• 上界：作者利用括号和链式论证来界定经验过程的一致偏差。对于强凸情形，他们利用了局部化现象，表明误差由随机过程在最优解附近小邻域内的行为控制，而非整个定义域。
• 锚定一致收敛：为了处理优化的平移不变性（即在目标函数上添加常数不改变最小化器），作者定义了“锚定”目标 $\bar{f}(x; z) = f(x; z) - f(0; z)$，确保样本复杂度是有限的且定义良好。

3. 主要贡献与结果

本文建立了三个不同区域的紧样本复杂度界（至多相差常数因子），揭示了整数性的影响高度依赖于定义域的几何形状以及目标函数的平滑性/凸性。

A. $\ell_\infty$ 球上的 Lipschitz 目标（盒约束）

设定：$X \subseteq B^{(\infty)}_R$（半径为 $R$ 的盒子），$f(\cdot; z)$ 关于 $\ell_\infty$ 范数是 1-Lipschitz 的。
结果：样本复杂度为 $\Theta\left(\frac{R^2}{\epsilon^2}(d + \log(1/\delta))\right)$。
意义：

• 该速率适用于盒子的任何可行子集，包括混合整数集（$X = C \cap (\mathbb{Z}^n \times \mathbb{R}^{d-n})$）和纯整数集（$X = B^{(\infty)}_R \cap \mathbb{Z}^d$）。
• 关键在于，整数性并未改变样本复杂度。在此设定下，一般随机混合整数、非线性、非凸优化的复杂度与带边界约束的简单随机线性规划完全相同。
• 即使对于线性函数，下界也能达到，这意味着“难度”源于盒顶点的几何结构，而这对连续和整数情形是相同的。

B. $\ell_2$ 球上的 Lipschitz 目标（欧几里得约束）

设定：$X \subseteq B^{(2)}_R$（半径为 $R$ 的欧几里得球），$f(\cdot; z)$ 关于 $\ell_2$ 范数是 1-Lipschitz 的。
结果：

• 连续情形：样本复杂度为 $\Theta\left(\frac{R^2}{\epsilon^2}(d + \log(1/\delta))\right)$。
• 整数情形：样本复杂度为 $\Theta\left(\frac{R^2}{\epsilon^2}(H_2(d, R) + \log(1/\delta))\right)$，其中 $H_2(d, R)$ 是一个几何项，定义为：
  $$H_2(d, R) = \begin{cases} 0 & 0 < R < 1 \\ \min\{d, \lfloor R^2 \rfloor\} \log\left(\frac{ed}{\min\{d, \lfloor R^2 \rfloor\}}\right) & R \ge 1 \end{cases}$$
  意义：
• 整数性可能更容易：当 $R^2 < d$ 时，项 $H_2(d, R) < d$。这意味着整数约束的随机优化可能比连续对应情形需要严格更少的样本。
• 机制：这种优势源于小欧几里得球内整数点的凸包具有与球本身不同（更稀疏）的几何结构。整数点具有稀疏支撑（最多 $\lfloor R^2 \rfloor$ 个非零坐标），从而降低了搜索空间的有效维度，相比于完整的连续球。
• 非凸性：与 ERM 可以比一致收敛严格更高效的凸设定不同，在此非凸 Lipschitz 设定下，UC、ERM 和任意算法的样本复杂度是相同的。

C. 强凸且平滑的目标

设定：$f(\cdot; z)$ 是 $\mu$-强凸且 $L$-平滑的。定义域要么是盒子 $B^{(\infty)}_R$，要么是整个空间 $\mathbb{R}^d$。作者引入了次高斯增量条件来处理无界定义域，因为标准的 Lipschitz 假设对无界强凸函数失效。
结果：

• 整数情形：ERM 的样本复杂度为 $\Theta\left(\frac{\sigma^2 d \min\{\kappa, \lfloor R \rfloor^2\}}{\epsilon^2}(d + \log(1/\delta))\right)$，其中 $\kappa = L/\mu$ 是条件数。
• 连续情形：ERM 的样本复杂度为 $\Theta\left(\frac{\sigma^2 d}{\mu \epsilon}(d + \log(1/\delta))\right)$。
  意义：
• 整数性使问题更难：在此区域，整数优化需要 $\Omega(1/\epsilon^2)$ 个样本，而连续优化实现了更快的 $O(1/\epsilon)$ 速率。
• 局部化与舍入：连续情形受益于“加速”速率，因为强凸性允许算法将搜索局部化到一个小区域而无需承担舍入误差。在整数情形中，“局部化”受限于离散网格；算法必须解析特定的整数点，这会产生额外的损失，从而阻碍了 $1/\epsilon$ 速率的实现。
• 一致收敛与 ERM：对于无界整数定义域，一致收敛具有无限的样本复杂度（无法用有限样本在整个整数集上一致逼近目标函数），但 ERM 却能以有限样本成功。这是一种独特的分离现象，由于局部化现象，ERM 比一致收敛严格更强大。

4. 意义与主张

本文声称填补了文献中关于整数随机优化统计（样本复杂度）方面的空白，该领域历史上主要关注算法或渐近复杂度。

1. 情境化难度：作者证明了整数随机优化的难度并非单一不变的。它完全取决于约束集的几何形状（$\ell_\infty$ 与 $\ell_2$）与目标函数的正则性（Lipschitz 与强凸/平滑）之间的相互作用。
2. 反直觉的发现：
   • 在 $\ell_\infty$ 设定中，整数性在统计上是中立的。
   • 在 $\ell_2$ 设定中，由于稀疏性，整数性在统计上可能是有利的（需要更少的样本）。
   • 在强凸设定中，由于在局部化步骤中无法避免舍入误差，整数性在统计上是不利的（收敛速率更慢）。
3. 方法论贡献：本文提供了非凸连续随机优化的首个紧样本复杂度界（与 $\ell_\infty$ 和 $\ell_2$ Lipschitz 结果相匹配），并确立了无界强凸问题中次高斯增量条件的必要性。

作者保持了谦逊的语调，指出他们的结果提供了对连续与离散随机优化相对难度的“定量”理解，而非提出新的算法或应用。这项工作作为这些设定中统计上可实现性的理论基准。