技术摘要：凸函数的采样与重构

1. 问题陈述

本文研究了定义在单位立方体 $\Omega = [0, 1]^d$ 上的多元凸函数的最优恢复问题。给定 $n$ 个点样本 $\Lambda = \{x_1, \dots, x_n\}$ 以及对应的观测向量 $w = (f(x_1), \dots, f(x_n))$，目标是构造一个近似函数 $\tilde{f}$，以最小化 $L_p$ 范数（$1 \le p \le \infty$）下的最坏情况恢复误差。

研究聚焦于两类特定的凸函数模型：

1. 类 $B(\Omega)$： 均匀受限于 1 的凸函数（即 $|f(x)| \le 1$）。
2. 类 $L(\Omega)$： 均匀受限于 1 且次梯度也均匀受限于 1 的凸函数（即对于所有 $v \in \partial f(x)$，有 $|v| \le 1$），这等价于 1-Lipschitz 函数。

主要目标是确定采样数 $\rho_n(K)_{L_p}$，其定义为所有可能的采样点选择和所有恢复算法的最坏情况误差的下确界。论文还研究了线性采样数 $\rho_n^\ell(K)_{L_p}$，其中恢复算法被限制为线性算法。

2. 方法论

作者结合了逼近理论、凸几何和概率方法，来建立采样数的上界和下界。

2.1 张量积网格与线性方法

首先，本文分析了标准均匀张量积网格和分片多线性插值的性能。

• 上界： 对于类 $L$，均匀网格产生的误差率为 $O(n^{-r/d})$，其中 $r = 1 + 1/p$。对于类 $B$，则需要非均匀的张量网格（在边界附近进行梯度划分）才能达到相同的速率。
• 下界： 作者通过构建特定的反例（使用“铰链”函数或修改后的凸函数）来证明，如果被限制在张量积网格或线性恢复方法内，这些速率是最优的。

2.2 非线性与非张量采样

为了确定真正的最优速率，论文超越了张量网格。

• 最优集合的存在性： 利用概率论论证，作者证明了特定数据点集 $\Lambda_n^*$（它们不是张量积网格）的存在性，这些集合满足两个关键几何属性：
  1. 任何内部不包含采样点的闭凸集的体积被限制在 $O(\frac{\log n}{n})$。
  2. 该集合构成一个 $\epsilon$-网，其中 $\epsilon \approx n^{-1/d}$。
• 误差分析： 通过分析两个在这些特定点上相等的凸函数之间的差异，作者推导出了更精确的采样数上界。这涉及用凸集覆盖函数不同的区域，并利用次梯度和极集（引用 Mahler 不等式）的性质。

2.3 构造性恢复算法

虽然最优速率的存在性依赖于非构造性的概率证明，但第 6 节提出了一种计算可行且接近最优的恢复算法。

• 上确界性质： 该算法利用了类 $L$ 和 $B$ 在逐点上确界下封闭的特性。
• 公式化： 恢复映射 $A_\Lambda(w)$ 被定义为满足数据约束（以及有界性约束）的模型类中所有函数的逐点上确界。
• 实现： 这个无穷维优化问题被简化为一个有限维问题。恢复函数被证明是一组满足线性（针对 $B$）或锥约束（针对 $L$）的仿射函数的上确界。这使得恢复可以通过线性规划（针对 $B$）或锥规划（针对 $L$）来计算。

3. 主要贡献与结果

3.1 标准方法的次优性

一个核心发现是，对于凸函数，适用于经典光滑度类（如 Sobolev 或 Hölder 空间）的标准程序是次优的。

• 张量网格： 对于 $1 < p < \infty$ 且 $d \ge 2$，在均匀张量积网格上采样的速率为 $n^{-(1+1/p)/d}$。然而，最优速率更快。
• 线性方法： 线性恢复方法的表现明显差于非线性方法。具体而言，对于 $p=2$，线性采样数的衰减速度为 $n^{-3/2d}$，而最优非线性速率为 $n^{-2/d}$（忽略对数因子）。

3.2 最优采样速率

论文确定了采样数 $\rho_n(K)_{L_p}$ 的最优衰减速率（忽略对数因子）：

• 对于 $1 \le p \le d$： 速率为 $n^{-2/d}$。
• 对于 $p \ge d$： 速率为 $n^{-(1+d/p)/d}$。
• 综合： 最优速率由 $n^{-\tilde{r}/d}$ 表征，其中 $\tilde{r} = \min\{2, 1 + d/p\}$。

这些速率是通过使用特定的、非张量积的采样集和非线性重构方法实现的。

3.3 特定情形

• $p=1$ 和 $p=\infty$： 最优速率可以使用张量积网格和线性方法实现。
• $p=2$： 线性采样数 $\rho_n^\ell(L)_{L_2}$ 衰减为 $n^{-3/2d}$，而最优非线性速率为 $n^{-2/d}$。这突显了凸函数在 $p=2$ 时线性恢复与非线性恢复之间存在实质性的差距。
• 类 $B$ 与 类 $L$： 虽然 $L \subset B$，但对于 $p < \infty$，两类的最优采样速率基本相同。然而，对于 $p=\infty$，类 $B$ 的采样数并不趋于零（$\rho_n(B)_{L_\infty} \asymp 1$），而类 $L$ 的采样数则按 $n^{-1/d}$ 衰减。

4. 意义与主张

本文声称刻画了凸函数采样数的最佳衰减速率，解决了标准基于网格的方法与理论最优值之间的差异。

• 非线性是本质： 该工作表明，对于凸函数，非线性重构方法在大多数 $p$ 值下显著优于线性方法和标准的张量网格采样。这与经典的光滑度类形成对比，在那些类别中，均匀网格上的线性方法通常是最优的。
• 与熵的联系： 推导出的最优采样速率（对于 $p \le d$ 为 $n^{-2/d}$）与这些类的熵数（entropy numbers）的衰减速率相匹配。这表明，凸函数的采样数受熵所控制的相同复杂度度量的支配，这与某些经典光滑度类不同（在那些类中，采样数可能比熵数衰减得更快）。
• 构造性算法： 论文提供了一种基于凸优化（仿射函数的上确界）的实用、稳定且接近最优的恢复算法，即使对于含噪声的数据也适用。

作者指出，虽然最优采样集的存在性是通过概率方法证明的，但此类集合的显式构造仍是一个开放领域，尽管所提出的恢复算法对于任何点集都有效，并且当点集根据理论要求选取时，能达到近乎最优的性能。