2025-11-25T08:04:18.158681

Adaptivity Gaps for Stochastic Probing with Subadditive Functions

Li, Liu, Zhang
In this paper, we study the stochastic probing problem under a general monotone norm objective. Given a ground set $U = [n]$, each element $i \in U$ has an independent nonnegative random variable $X_i$ with known distribution. Probing an element reveals its value, and the sequence of probed elements must satisfy a prefix-closed feasibility constraint $\mathcal{F}$. A monotone norm $f: \mathbb{R}_{\geq 0}^n \to \mathbb{R}_{\geq 0}$ determines the reward $f(X_P)$, where $P$ is the set of probed elements and $X_P$ is the vector with $X_i$ for $i \in P$ and 0 otherwise. The goal is to design a probing strategy maximizing the expected reward $\mathbb{E}[f(X_P)]$. We focus on the adaptivity gap: the ratio between the expected rewards of optimal adaptive and optimal non-adaptive strategies. We resolve an open question posed in [GNS17, KMS24], showing that for general monotone norms, the adaptivity gap is $O(\log^2 n)$. A refined analysis yields an improved bound of $O(\log r \log n / \log\log n)$, where $r$ is the maximum size of a feasible probing sequence. As a by-product, we derive an asymptotically tight adaptivity gap $Θ( \log n/\log\log n)$ for Bernoulli probing with binary-XOS objectives, matching the known lower bound. Additionally, we show an $O(\log^3 n)$ upper bound for Bernoulli probing with general subadditive objectives. For monotone symmetric norms, we prove the adaptivity gap is $O(1)$, improving the previous $O(\log n)$ bound from [PRS23].
academic

Adaptivity Gaps for Stochastic Probing with Subadditive Functions

基本信息

  • 论文ID: 2504.15547
  • 标题: Adaptivity Gaps for Stochastic Probing with Subadditive Functions
  • 作者: Jian Li, Yinchen Liu, Yiran Zhang (清华大学交叉信息研究院)
  • 分类: cs.DS (数据结构与算法)
  • 发表时间: 2024年4月 (arXiv版本，最后更新2025年10月)
  • 论文链接: https://arxiv.org/abs/2504.15547v2

摘要

本文研究一般单调范数目标下的随机探测问题。给定基集 U=[n]U = [n]，每个元素 i∈Ui \in U 关联一个已知分布的独立非负随机变量 XiX_i。探测元素会揭示其值，探测序列必须满足前缀封闭的可行性约束 F\mathcal{F}。单调范数 f:R≥0n→R≥0f: \mathbb{R}_{\geq 0}^n \to \mathbb{R}_{\geq 0} 决定奖励 f(XP)f(X_P)，其中 PP 是探测元素集合。目标是设计探测策略最大化期望奖励。本文重点研究适应性差距：最优适应性策略与最优非适应性策略期望奖励的比值。

研究背景与动机

问题重要性

随机探测问题是不确定性优化中的基础框架，广泛应用于：

  • 贝叶斯机制设计
  • 在线学习
  • 影响力最大化
  • 机器人路径规划
  • 数据库管理

适应性差距的意义

  1. 理论意义：量化适应性的价值，理解何时简单的非适应性策略足够好
  2. 实用价值：非适应性策略更容易表示、分析和实现，避免维护大型决策树的计算开销
  3. 算法设计指导：小的适应性差距证明关注非适应性策略的合理性

现有工作的局限性

  • Gupta等人GNS17对子加性函数的适应性差距提出猜想，认为是多对数的
  • Patton等人PRS23对对称范数证明了 O(log⁡n)O(\log n) 上界，但猜测真实差距可能是常数
  • Kesselheim等人KMS24将猜想扩展到一般单调范数

核心贡献

  1. 解决核心开放问题：证明一般单调范数的适应性差距为 O(log⁡2n)O(\log^2 n)，精化分析得到 O(log⁡rlog⁡n/log⁡log⁡n)O(\log r \log n / \log\log n)
  2. 获得紧致界：对二元XOS目标的伯努利探测，证明适应性差距为 Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n)，与已知下界匹配
  3. 改进子加性函数界：证明伯努利探测下一般子加性目标的适应性差距为 O(log⁡3n)O(\log^3 n)
  4. 常数界结果：对单调对称范数，将适应性差距从 O(log⁡n)O(\log n) 改进到 O(1)O(1)

方法详解

任务定义

随机探测问题：

  • 输入：基集 U=[n]U = [n]，每个元素 ii 关联随机变量 XiX_i，目标函数 ff，可行性约束 F\mathcal{F}
  • 过程：自适应地探测元素，观察实现值，直到达到叶节点
  • 输出：探测元素集合 PP，获得奖励 f(XP)f(X_P)
  • 目标：最大化期望奖励 E[f(XP)]\mathbb{E}[f(X_P)]

适应性差距：最优适应性策略期望奖励最优非适应性策略期望奖励\frac{\text{最优适应性策略期望奖励}}{\text{最优非适应性策略期望奖励}}

核心技术框架

1. 三步约化策略

论文采用系统性的约化方法：

第一步：一般随机变量 → 伯努利设置

  • 使用 λ\lambda-大分解技术
  • 将连续分布离散化为负2次幂
  • 将决策树转换为二元树

第二步：一般XOS → 特殊XOS范数

  • 将权重舍入到负2次幂
  • 构造特殊形式：fxos(S)=max⁡ℓ{∣elt(Aℓ′)∩S∣}f_{xos}(S) = \max_\ell \{|\text{elt}(A'_\ell) \cap S|\}
  • 只损失 O(log⁡r)O(\log r) 因子

第三步：贪心算法分析

  • 设计复杂的标签系统控制深度信息
  • 证明尾概率界限
  • 应用技术不等式

2. 关键算法设计

贪心标签算法：

输入: (ℓ, R)
输出: 标签 B = (m; s; d₁,...,dₘ; e₁,...,eₘ; y₁,...,y⌊s/K⌋)

1. 初始化: s ← |A'_ℓ|, d₁ ← depth(ℓ)
2. 设置深度控制参数 yᵢ
3. 沿路径 Pₓ 向上遍历每个节点 u:
   - 检查 u ∈ R 且存在合适的叶子 ℓ'
   - 如果满足条件，更新标签 B
4. 返回最终标签 B

3. 技术创新点

深度控制机制：

  • 引入参数 K=O(log⁡n)K = O(\log n) 控制 Aℓ′A'_\ell 中元素的深度
  • 对每个 jj，yjy_j 表示 Aℓ′A'_\ell 中第 jKjK 个元素的深度
  • 确保不同叶子间的 Aℓ′A'_\ell 结构相似性

不可能节点识别：

  • 定义 Imp(ℓ,B0)\text{Imp}(\ell, B_0)：给定标签下不能激活的节点集合
  • 证明每个 ℓ∈S(B0)\ell \in S(B_0) 中至少有 s−mKs - mK 个不可能节点
  • 利用这些约束获得指数级小的概率界

技术函数 g(h,p)g(h,p)：

  • 定义 g(h,p)=p⋅exp⁡(−0.1hp1/h)g(h,p) = p \cdot \exp(-0.1h p^{1/h})
  • 证明关键不等式处理根节点在/不在约束集合的情况
  • 比标准 Chernoff 界在 p=n−O(m)p = n^{-O(m)} 时更紧

对称范数的特殊处理

对于对称范数，采用不同的分析策略：

  1. 类别划分：将节点按权重 4−k4^{-k} 分为类别 QkQ_k
  2. 好坏叶子分类：定义 kk-坏叶子，证明其比例指数级小
  3. 直接分析：避免复杂的标签系统，直接分析期望奖励

实验设置

本文是纯理论工作，主要通过数学证明验证结果。论文提供了：

理论验证

  1. 下界匹配：对二元XOS目标，上界 O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) 与 GNS17 的下界 Ω(log⁡n/log⁡log⁡n)\Omega(\log n/\log\log n) 匹配
  2. 参数依赖性：分析了界限对 rr（最大探测序列长度）的依赖
  3. 常数分析：对对称范数给出显式常数界 2050

技术验证

  1. 约化正确性：每步约化的近似比分析
  2. 算法复杂度：虽然算法仅用于分析，但复杂度是合理的
  3. 参数选择：K=O(log⁡n/log⁡log⁡n)K = O(\log n/\log\log n) 的最优性

实验结果

主要理论结果

定理1.2（一般单调范数）： 适应性差距上界为 O(log⁡r⋅log⁡nlog⁡log⁡n)O\left(\log r \cdot \frac{\log n}{\log\log n}\right)

定理1.3（二元XOS目标）： 适应性差距为 Θ(log⁡nlog⁡log⁡n)\Theta\left(\frac{\log n}{\log\log n}\right)（紧致）

定理1.4（对称范数）： 适应性差距为 O(1)O(1)

技术贡献分析

改进幅度：

  • 对称范数：从 O(log⁡n)O(\log n) PRS23 改进到 O(1)O(1)
  • 一般范数：首次获得多对数界，解决开放问题
  • 二元XOS：获得渐近紧致界

方法创新：

  • 深度控制的标签系统
  • 改进的概率分析技术
  • 统一的约化框架

相关工作

历史发展

  1. 早期工作：Gupta-Nagarajan GN13 引入伯努利探测
  2. 子模函数：GNS16, GNS17 证明常数适应性差距
  3. XOS函数：GNS17 证明 O(log⁡W)O(\log W) 界，其中 WW 是XOS宽度
  4. 范数目标：PRS23, KMS24 研究对称范数和超模范数

本文定位

  • 解决 GNS17, KMS24 提出的核心猜想
  • 改进 PRS23 对对称范数的结果
  • 提供统一的技术框架处理不同目标函数

结论与讨论

主要结论

  1. 理论完备性：基本解决了单调范数下随机探测的适应性差距问题
  2. 技术贡献：开发了处理一般目标函数的新技术工具
  3. 实用指导：证明在许多情况下非适应性策略是近似最优的

局限性

  1. 常数因子：对称范数的常数 2050 较大，可能不够紧
  2. log⁡r\log r 差距：与已知下界仍有 O(log⁡r)O(\log r) 的差距
  3. 技术复杂性：证明技术较为复杂，可能难以扩展到其他问题

未来方向

  1. 紧化界限：缩小与下界的差距
  2. 改进常数：获得对称范数的紧致常数
  3. 算法应用：将洞察应用到更广泛的随机组合优化
  4. 计算复杂性：研究计算最优策略的复杂性

深度评价

优点

技术创新：

  1. 深度控制机制：创新性地使用深度信息控制标签结构
  2. 统一框架：提供处理不同目标函数的系统性方法
  3. 精细分析：改进的概率技术获得更紧的界限

理论贡献：

  1. 解决开放问题：回答了领域内的核心猜想
  2. 紧致结果：对二元XOS获得最优界限
  3. 意外改进：对称范数的常数界是意外的强结果

技术质量：

  1. 证明严谨：数学推理清晰完整
  2. 结构清晰：论文组织良好，易于理解
  3. 技术深度：使用了多种高级概率和组合技术

不足

技术局限：

  1. 复杂性：证明技术非常复杂，可能限制进一步发展
  2. 常数问题：某些常数可能不够紧致
  3. 参数依赖：对 rr 的依赖性分析可以更深入

应用局限：

  1. 纯理论：缺乏实际应用的验证
  2. 算法效率：分析算法的计算复杂度较高
  3. 实用性：在实际问题中的应用价值需要进一步验证

影响力

学术影响：

  1. 解决重要问题：回答了多年来的开放问题
  2. 技术推进：为随机优化提供新的分析工具
  3. 启发作用：可能启发其他相关问题的研究

实用价值：

  1. 算法设计指导：为实际算法设计提供理论支撑
  2. 近似保证：证明简单策略的有效性
  3. 应用领域：在机器学习、运筹学等领域有潜在应用

适用场景

  1. 理论研究：随机组合优化、在线算法理论
  2. 算法设计：需要平衡适应性与简单性的场景
  3. 实际应用：资源分配、实验设计、推荐系统等

参考文献

  • GNS17 Gupta, Nagarajan, Singla. "Adaptivity gaps for stochastic probing: submodular and XOS functions"
  • KMS24 Kesselheim, Molinaro, Singla. "Supermodular approximation of norms and applications"
  • PRS23 Patton, Russo, Singla. "Submodular Norms with Applications To Online Facility Location and Stochastic Probing"

这篇论文在随机组合优化领域做出了重要的理论贡献，不仅解决了多个开放问题，还开发了处理一般目标函数的新技术框架。尽管证明技术较为复杂，但其理论价值和对领域的推进作用是显著的。