在线非单调DR-次模最大化：匹配离线$0.401$因子

# 在线下非单调 DR-次模最大化的在线匹配：达成离线0.401因子
来源: https://arxiv.org/html/2609.02145

## 在线非单调 DR-次模最大化的离线0.401因子匹配

###### 摘要
我们研究在d维单位立方体的紧致凸闭向下子集上，非负非单调 DR-次模函数的在线最大化问题。在相应的元可解性假设下，已知最佳的构造性离线逼近因子为0.401，而与之相当的对抗性在线保证则一直停留在1/e。我们证明，这一因子在在线情形下同样可以达成。在后决策完全信息值预言机模型中，我们的算法在值预言机反馈条件无偏且有界的情况下，达到了0.401因子，并具有次线性近似遗憾。该在线算法并未在变化的目标上运行离线构造。取而代之的是，它用一个加权在线学习器替代了离线的依赖于目标的盒步骤，该学习器累积地控制所需的残余项。一个精确的非对称平衡定理在对抗性变化下保留了离线系数。其直接实现具有 \(O(T^{3/4})\) 遗憾，每轮使用 \(O(dT^{1/4})\) 次预言机调用。更一般地，对于每个 \(\delta \in [0, 1/4]\)，批处理给出每轮 \(O(T^{\delta})\) 次调用和 \(O(T^{4/5 - \delta/5})\) 遗憾，包括一个单次调用 \(O(T^{4/5})\) 的端点。在正锚条件下，随机阻塞保留了0.401因子，并具有 \(O(T^{5/6})\) 单点赌博机遗憾。

## 1 引言
DR-次模函数是具有边际收益递减性质的连续目标函数：增加一个坐标只会降低增加另一个坐标的边际价值。当决策的坐标编码可分配资源、激活概率或连续强度时，它们提供了一个自然的模型。非单调性在许多此类模型中至关重要，因为分配更多资源可能导致拥塞、冗余或干扰，从而降低目标值。向下闭的约束捕捉了这种互补可行性原则：减少分配量可以保持可行性。

在在线问题中，学习者反复选择一个可行点，而奖励函数随时间变化。在第t轮的行动必须在获得来自 \(f_t\) 的任何反馈之前就确定，性能是与事后最佳固定可行点进行比较的。这种设置结合了两种真正不同的损失来源。首先，目标函数是非凹的，因此即使是一个预先知道单个函数的离线算法，通常也只能提供近似保证。其次，学习者必须从过去的观察中估计有用的方向和结构性选择，这会产生一个加性遗憾项。一个令人满意的在线结果应该将这两种效应分开：时间变化应该贡献次线性加性损失，而不应不必要地降低最佳可用的逼近因子。

##### 在线/离线差距。本文的核心问题是一个逼近因子问题。
对于向下闭凸约束下的非单调 DR-次模最大化，已知最佳的构造性离线因子是0.401：Buchbinder 和 Feldman 通过使用延迟连续贪心构造结合一个非对称盒最大化步骤来获得这一保证[10 (https://arxiv.org/html/2609.02145#bib.bib10)]。本文及全文中，0.401指的是在[10 (https://arxiv.org/html/2609.02145#bib.bib10)]的相应元可解性假设下已知的最佳构造性离线保证；我们的比较关注的是近似系数，而非完全相同的算法或预言机假设。

然而，相当的对抗性在线结果一直停留在1/e。从 Thang 和 Srivastav 开始，后来的后决策值预言机、一次性、无投影和赌博机方法改进了遗憾和预言机复杂度，但并未改善领先的1/e系数[19 (https://arxiv.org/html/2609.02145#bib.bib19), 24 (https://arxiv.org/html/2609.02145#bib.bib24), 29 (https://arxiv.org/html/2609.02145#bib.bib29), 30 (https://arxiv.org/html/2609.02145#bib.bib30)]。Lu 等人明确指出突破这一障碍是一个开放问题[30 (https://arxiv.org/html/2609.02145#bib.bib30)]。我们的问题是：已知最佳的构造性离线因子在当前目标可用前必须选择行动的对抗性时间变化下能否存续？我们的回答是肯定的：

\[
\boxed{\text{在线逼近因子} = 0.401} \quad (1)
\]

该保证具有次线性近似遗憾，因此匹配了已知最佳的0.401构造性离线逼近因子。我们并非声称0.401是最优的。一个相关的值预言机 hardness 基准是0.478：在向下闭多面体上的多线性扩展最大化，即使对于一个划分拟阵多面体，也无法近似超过此值，且在基数约束下该阈值同样成立[12 (https://arxiv.org/html/2609.02145#bib.bib12), 13 (https://arxiv.org/html/2609.02145#bib.bib13)]。因此，0.401是当前的构造性离线基准，而已知的 hardness 阈值更高；我们的结果表明，在当前的值预言机模型中，这一构造性基准同样可以在在线达成。

##### 激励性设置。我们模型的要素出现在多个既有的应用类别中。
连续次模目标已被用于具有连续赋值的影响力最大化、传感器能量管理和设施选址[2 (https://arxiv.org/html/2609.02145#bib.bib2)]；鲁棒连续预算分配给出了一个密切相关的影响力最大化模型[3 (https://arxiv.org/html/2609.02145#bib.bib3)]。非单调 DR-次模目标出现在行列式点过程的 MAP 推断和概率次模模型的可证明均值场推断中[1 (https://arxiv.org/html/2609.02145#bib.bib1), 4 (https://arxiv.org/html/2609.02145#bib.bib4)]。在线连续次模优化由 Chen, Hassani 和 Karbasi 开创[20 (https://arxiv.org/html/2609.02145#bib.bib20)]；时变 DR-次模福利也出现在在线资源分配和共享出行再平衡中[21 (https://arxiv.org/html/2609.02145#bib.bib21)]，而赌博机 DR-次模方法已被用于推导对抗性次模赌博机保证[25 (https://arxiv.org/html/2609.02145#bib.bib25)]。这些论文激励了各自的建模要素；它们并非都施加了我们完全相同的组合：非单调性、向下闭可行性和对抗性值反馈。

表1 [ (https://arxiv.org/html/2609.02145#S1.T1)]  isolation 出了激励本文的逼近因子比较。表2 [ (https://arxiv.org/html/2609.02145#S1.T2)] 则仅记录了在线值反馈保证；它没有将离线进展混入在线遗憾比较。我们展示了 Lu 等人[30 (https://arxiv.org/html/2609.02145#bib.bib30)] 报告的 FF-预言机行，而非一阶梯度反馈结果。

**表1：** 离线基准与主要在线结果。离线行使用了[10 (https://arxiv.org/html/2609.02145#bib.bib10)] 的元可解性假设；在线行具有次线性近似遗憾。比较是在逼近系数之间，而非完全相同的预言机模型之间。
**表2：** 在向下闭凸集上的非单调 DR-次模最大化的在线值反馈保证。问题依赖常数和低阶项被省略。“PD值-预言机”表示后决策完全信息值-预言机反馈：在承诺执行所采取的行动后，学习者可以调用不同于所执行行动的点处的预言机；在赌博机模型中，单一观察是所执行行动的有噪声值，其真实值是获得的奖励。

更一般地，对于每个 \(\delta \in [0, 1/4]\)，我们的批处理值预言机结果每轮物理调用 \(O(T^{\delta})\) 次，并具有 \(O(T^{4/5 - \delta/5})\) 遗憾。端点 \(\delta = 0\) 使用一次调用，而 \(\delta = 1/4\) 给出最佳遗憾率。维度和正则性因子在本表中被吸收到常数中，“逼近α”列是公式 (9 [ (https://arxiv.org/html/2609.02145#S3.E9)]) 中基准的系数，这是一个在注3.2 [ (https://arxiv.org/html/2609.02145#S3.Thmtheorem2)] 意义下的渐近量，而非有限视界近似比。我们的赌博机行另外假设了第5节 [ (https://arxiv.org/html/2609.02145#S5)] 中陈述的正锚条件。我们的行允许具有有界误差 \(\sigma \ge 0\) 的条件无偏预言机，并假设一个无知对抗者。近似因子是近似遗憾中的主导量级项。

如果 \(\operatorname{OPT}_T := \max_{o \in K} \sum_{t=1}^T f_t(o) = \Theta(T)\)，那么将 \(1/e\) 替换为0.401将保证的奖励提高了约 \(0.0331 \operatorname{OPT}_T\)，这是一个线性于 \(T\) 的项。相比之下，表2 [ (https://arxiv.org/html/2609.02145#S1.T2)] 中的每个遗憾项对于固定的问题参数都是 \(o(T)\)。因此，因子和遗憾率不可互换：逼近因子决定了基准的渐近比例，而遗憾决定了算法接近该比例的速度。在这个确切意义上，跨越逼近障碍是一个更根本的进展，即使有限视界性能仍然取决于遗憾指数、维度、预言机预算和隐藏常数。

##### 为什么在线比离线更难。标准的 \(1/e\) 分析与在线学习异常兼容。
测量连续贪心产生一个局部线性证书，而在线线性优化算法可以在对轮次求和后控制其依赖于比较器的线性项。更强的离线构造以质的不同方式使用信息。它处理一个在整个计算过程中可用的固定目标，其局部搜索和盒最大化查询可能反复适应于同一个目标。给定 \(f\) 和一个外部点 \(x\)，它解决一个非对称盒问题，其答案依赖于完整的函数。该答案提供两个非线性值，以抵消延迟轨迹证书中的负项。这个修正步骤在在线不可用。

在第t轮，外部状态 \(x_t\)、盒决策和执行的行动都必须在获得来自 \(f_t\) 的任何反馈之前选定。在观察到 \(f_t\) 之后选择离线盒解将违反协议，而在对抗性变化序列上使用前一轮的解是无用的。此外，对当前执行点的逐点线性化无法保留那两个超越 \(1/e\) 的非对称值项。这就是为什么离线证明无法通过黑盒转换为在线，即使是在后决策完全信息值-预言机反馈下：额外的查询可以更新未来状态，但它们无法追溯性地改变当前行动。特别是，支撑0.401保证的离线构造不能简单地插入到一个在线包装器中。它的盒最大化步骤从在线角度看是前瞻性的：它必须在选定修正点之前检查当前函数。在第t轮之后运行该步骤产生的行动为时已晚，无法从 \(f_t\) 赏励，而在过去或平均目标上运行它无法控制对抗性变化下的当前奖励。因此，现有的离线保证本身并不能通过跟随领导者、延迟执行或标准的离线到在线黑盒归约产生在线保证。

因此，在线构造并不在变化的目标上运行离线算法。它转移了延迟轨迹不等式和非对称系数要求，然后用一个独立的在线无约束最大化状态替换了不可用的每轮盒最优。它的证书是累积的：它在对序列求和后支付延迟轨迹债务，而不是逐点消除它们。这种摊销是离线系数在变化目标下可以被保留的概念原因。

##### 在线组合。核心技术贡献是链：
\[
\boxed{f_t \;\longrightarrow\; G_t(a) = f_t(x_t \odot a) \;\longrightarrow\; \text{加权在线USM} \;\longrightarrow\; \text{外部延迟轨迹}.} \quad (2)
\]
这里 USM 表示无约束次模最大化。结构不等式揭示了变换目标 \(G_t\) 必须控制的债务；加权在线 USM 学习器恰好实现了累积支付这些债务所需的非对称系数；而外部在线学习器吸收了剩余的线性项。然后在内部和外部候选点之间的随机选择产生奖励保证，而无需沿着无效方向使用凹性。

##### 在线时序。对抗者在游戏开始前固定 \(f_1, \ldots, f_T\)。
在第t轮开始时，历史决定了外部状态 \(x_t\) 和所有加权在线 USM 学习器的状态。仅使用这些状态和新的内部随机性，内部学习器选择 \(a_t\)；然后算法形成 \(x_t \odot a_t\) 和 \(Y_1(x_t)\)，抛掷其混合硬币，并承诺执行的行动 \(p_t\)。只有在此承诺之后，\(f_t\) 才可用，并且仅通过调用有噪声的预言机。这些观察更新内部学习器并构建用于形成 \(x_{t+1}\) 的字段。因此，\(x_t, a_t, p_t\) 都是在没有当前轮反馈的情况下选定的，而 \(f_t\) 仅用于未来决策。将每个预言机调用严格置于该轮每个决策之后也是使噪声分析得以通过的原因：给定整个轮次的决策，每个估计是条件无偏的，这是引理4.13 [ (https://arxiv.org/html/2609.02145#S4.Thmtheorem13)] 的假设。

外部要素是 Buchbinder 和 Feldman[10 (https://arxiv.org/html/2609.02145#bib.bib10)] 开发的延迟连续贪心比较的一个比较器均匀特化；附录D [ (https://arxiv.org/html/2609.02145#A4)] 提供了本文所用精确形式的自包含证明。对于外部状态 \(x \in K\)，延迟参数 \(s\)，以及可行终点 \(Y_1(x)\)，不等式具有示意形式：
\[
f(Y_1(x)) \ge \theta_s f(o) - \chi_s f(x \odot o) - 2\zeta_s f(x) - \left\langle \widetilde{q}_s(f,x), o - x \right\rangle. \quad (3)
\]
这里 \(o \in K\) 是任意固定比较器，\(\theta_s, \chi_s, \zeta_s\) 是延迟的显式标量函数，\(\odot\) 表示坐标乘法，\(\widetilde{q}_s(f,x)\) 是一个路径积分梯度场。第一项包含所需的比较器值。接下来两项是必须偿还的*结构性债务*，最后一项是关于 \(o-x\) 线性的。外部学习器使用 \(\widetilde{q}_s\) 执行投影在线梯度上升。因此，をたたる紛紛たる紛紛紛紛紛紛�紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛紛