技术摘要：DR-次模最大化的 0.4584 近似算法

问题陈述

本文研究了在紧致、凸且向下封闭的集合 $K \subseteq [0, 1]^n$ 上，最大化一个非负、非单调、$L$-光滑 DR-次模函数 $F: [0, 1]^n \to \mathbb{R}_+$ 的问题。该函数满足边际收益递减（DR）性质：即若 $x \le y$，则 $\nabla F(x) \ge \nabla F(y)$（按坐标比较）。

算法运行在一个如下预言机模型中：

1. 值与全梯度查询： 对于单位立方体中的任何 $x$，均可获得 $F(x)$ 和 $\nabla F(x)$ 的精确评估。
2. 线性最大化预言机 (LMO)： 对于任何向量 $c \in \mathbb{R}^n$，预言机返回 $K$ 上 $\langle c, v \rangle$ 的最大化值。
3. 复杂度约束： 算法必须实现关于维度 $n$、精度参数 $\epsilon$ 和 $\delta$ 的一致多项式预言机复杂度，且该复杂度应独立于目标函数或梯度相对于最优值的量级。

目标是找到一个可行向量 $\hat{x} \in K$，使得 $\mathbb{E}[F(\hat{x})] \ge (a - \epsilon) \text{OPT} - \delta L D^2$，其中 $\text{OPT} = \max_{x \in K} F(x)$，$D$ 是 $K$ 的直径，$a$ 是近似比。

方法论

1. 恢复映射与仿射上界

其核心理论贡献在于构建了一个恢复映射 (recovery map) $h: [0, 1]^n \to [0, 1]^n$ 以及一个相应的场向量 (field vector) $g(F, x)$，它们满足全立方体范围内的仿射上界。具体而言，作者寻求一个映射 $h$ 和一个常数 $\Gamma \ge 1$，使得对于所有 $x, o \in [0, 1]^n$：
$$F(o) \le \Gamma F(h(x)) + \langle g(F, x), o - x \rangle$$
该不等式允许将近似误差通过沿算法轨迹的累积线性误差进行界定。

混合恢复映射 (Mixed Recovery Map):
作者通过引入一个混合恢复映射 $h_{b_1}(x)$ 来改进 Aggarwal 的线性分式映射 $h_i(x) = x_i / (1 + x_i)$。该映射根据坐标的大小结合了两个分支：
$$[h_{b_1}(x)]_i = \begin{cases} 1 - e^{-x_i} & \text{若 } x_i < \sigma_1 \\ \frac{x_i}{b_1 + x_i} & \text{若 } x_i \ge \sigma_1 \end{cases}$$
其中 $b_1 \approx 0.9053317$ 是由优化近似比导出的特定超越方程的唯一根，且 $\sigma_1 = 1 - b_1$。

• 小坐标 ($x_i < \sigma_1$) 使用指数分支（$1 - e^{-x_i}$），该分支是向下可行的（$1 - e^{-x} \le x$）。
• 大坐标 ($x_i \ge \sigma_1$) 使用线性分式分支（$x_i / (b_1 + x_i)$）。

场构造 (Field Construction):
场向量 $g(F, x)$ 通过对来自不同恢复路径（“T-界”和“J-界”）的两个仿射上界进行加权平均来构造。这种平均是通过总和为 1 的非负函数 $w_T$ 和 $w_J$ 进行加权的。证明依赖于：

• 坐标级数展开 (Coordinate Telescoping)： 适配 Aggarwal 的带符号坐标级数展开论证。
• DR-次模性： 利用边际收益递减性质来限制方向导数和曲率。
• 解析验证： 证明仿射上界截距的加权平均被 $\Gamma_1 F(h_{b_1}(x))$ 所界定，其中 $\Gamma_1 = 1 + b_1 + 1/(4b_1)$。

2. 算法框架

本文提出了基于 Frank-Wolfe 框架的连续时间算法和离散时间算法。

连续时间算法 (Algorithm 1):

• 动力学： 状态 $x(t)$ 遵循 $\dot{x}(t) = v(t) - x(t)$ 演化，其中 $v(t)$ 通过 LMO 选择，以最大化 $\langle \eta G(t) - x(t), v \rangle$。这里 $G(t) = \int_0^t g(s) ds$ 是累积场。
• 处理不连续性： 由于恢复映射和场存在不连续性（在指数分支与线性分式分支切换处），算法使用松弛的微分包含 (differential inclusion)。它采用极限作用-场对 (limiting action-field pairs) 的可测混合，以确保存在一条能够维持仿射上界的绝对连续轨迹。
• 输出： 输出是从轨迹的作用中均匀采样的随机向量。

离散时间算法 (Algorithm 3):

• 实现： 这是连续动力学的随机化、有限步实现。
• 采样： 在每次迭代中，算法使用 Algorithm 2 采样场向量 $g(F, x_{t-1})$ 的无偏估计量 $q_t$。该采样器根据权重密度 $w_T$ 和 $w_J$ 抽取一个分支（T 或 J）以及一个参数 $\Theta$。
• 更新： 算法执行标准的 Frank-Wolfe 步骤：$x_t = (1-\gamma)x_{t-1} + \gamma v_t$，其中 $v_t$ 最大化使用累积场的线性目标。
• 终止： 算法运行 $T$ 次迭代并返回记录到的最高值的动作。

3. 坐标归一化

为了确保预言机复杂度是统一的，且独立于目标函数相对于最优值的梯度量级，作者引入了宽度归一化 (width normalization) 技术。

• 可行集按每个坐标的最大宽度 $w_i$ 进行缩放。
• 这种变换将归一化后目标函数的梯度限制在 terms of $\text{OPT}$ 和 $LD^2$ 内，使得算法的步长和时界仅取决于维度和精度参数。

关键贡献与结果

1. 改进的近似比

主要的成果是得到了一个近似比 $\alpha_1 \approx 0.4584$。

• 该比例由 $\alpha_1 = \frac{4b_1}{(2b_1 + 1)^2}$ 给出，其中 $b_1 \approx 0.9053317$。
• 这改进了 Aggarwal 基于投影算法所达到的先前最佳比例 $4/9 \approx 0.4444$。
• 论文指出，理论上可以通过二次终端分支精炼将比例提升至 $\approx 0.4584288$，但文中使用了线性终端分支以简化证明。

2. 预言机复杂度与保证

所提算法满足以下保证：
$$\mathbb{E}[F(\hat{x})] \ge (\alpha_1 - \epsilon) \text{OPT} - \delta L D^2$$

• 查询复杂度： 离散时间算法使用 $O(n^5 \beta^{-4})$ 次值/全梯度查询以及 $O(n + n^4 \beta^{-4})$ 次 LMO 调用，其中 $\beta = \min\{\epsilon, \delta\}$。
• 一致性： 该复杂度在所有实例上都是统一的，独立于目标函数或梯度相对于 OPT 的量级。
• 确定性变体： 也提供了一个使用求积法 (quadrature) 的确定性版本，具有相同的保证。

3. 硬度界限与最优性

作者将该预言机模型下的最优近似比 $\alpha^\star$ 置于以下区间内：
$$0.4584 < \alpha_1 \le \alpha^\star \le \beta^\star < 0.4705$$

• 下界由其算法提供。
• 上界 ($\beta^\star$) 源自 Aggarwal 的硬度结果，这些结果即使在存在加性平滑误差时也成立。
• 这表明可实现的比例与理论极限之间的差距非常微小。

4. 离散优化后果

通过将连续结果与标准的多线性采样 (multilinear sampling) 及管道舍入 (pipage rounding) 相结合，本文推导出了在拟阵约束下非负次模集合函数最大化的期望 $(\alpha_1 - \epsilon)$-近似。这实现了从连续领域到离散领域的改进延伸。

意义与主张

本文声称缩小了 DR-次模最大化在向下封闭凸集上的已知近似比与已知硬度界限之间的差距。

• 方法论创新： 其意义在于使用了混合恢复映射（指数 + 线性分式）和标量平均证书 (scalar averaging certificate)。这种方法允许作者构建一个场向量，从而提供比以往纯线性分式映射更紧凑的仿射上界。
• 鲁棒性： 算法通过仅使用普通线性最大化预言机 (LMO) 实现了这一改进，避免了某些高比例算法所需的复杂投影预言机。
• 形式化验证： 文中的数学证明，包括 $b_1$ 唯一根的存在性以及权重函数的符号条件，已使用 Lean 定理证明器 进行了形式化验证，并使用了精确实数运算，确保了解析界的正确性。
• 背景： 本工作建立在 Pedramfar 和 Aggarwal 的“上线性化框架 (upper-linearizable framework)”之上，并利用 Vondrák 的对称间隙 (symmetry-gap) 框架来确立硬度，将这一结果定位为连续优化次模函数领域的一个决定性进展。

作者明确指出，其结果将最优近似比置于狭窄的区间 $[0.4584, 0.4705)$ 内，这表明进一步的显著改进可能需要根本性的新技术或对硬度界限的重新评估。