Near-optimal Delta-convex Estimation of Lipschitz Functions

问题陈述
本文探讨了随机设计设置下非参数回归的基本问题。目标是从 $n$ 个独立同分布（i.i.d.）的有噪声观测值 $(X_i, Y_i)$ 中估计一个未知的实值回归函数 $f^*$，其中 $Y_i = f^*(X_i) + \xi_i$。假设 $f^*$ 在一个未知的定义域 $X^* \subseteq \mathbb{R}^d$ 上关于欧几里得范数是 $\lambda^*$-Lipschitz 连续的，但 Lipschitz 常数 $\lambda^*$ 是未知的。该方法的性能通过平方损失下的超额风险（excess risk）进行评估。该问题的理论基准是 $\Theta(n^{-2/(2+d^*)})$ 的极小极大收敛速率，其中 $d^*$ 是数据的内在维度。虽然目前已存在针对凸形状限制回归（使用 max-affine 函数）和通用 Lipschitz 回归（使用最近邻或核方法）的方法，但在寻找无需预知 $\lambda^*$ 或外部模型选择程序（如交叉验证）即可实现近极小极大速率的可处理算法方面，文献中仍存在空白。

方法论：Delta-凸拟合 (DCF)
作者提出了一种名为 Delta-凸拟合（Delta-Convex Fitting, DCF）的可处理算法。该方法的核心是通过利用一种非线性特征展开，将函数映射到 delta-凸（DC）函数的一个子类，从而将凸回归中的 max-affine 方法扩展到通用的 Lipschitz 设置中。DC 函数被定义为两个凸函数的差。

该算法分为三个主要阶段：

1. 自适应划分：算法首先使用自适应最远点聚类（Adaptive Farthest-Point Clustering, AFPC）方法计算一组有限的中心点集 $\hat{X}_K$。这一步根据协变量数据的内在维度 $d^*$ 自适应地确定划分规模 $K$，旨在使 $K \approx n^{d^*/(2+d^*)}$。
2. 凸初始化：算法在函数类 $F_p(\hat{X}_K)$ 上求解一个正则化经验风险最小化（ERM）问题。这些函数被定义为由若干个仿射函数与范数项（例如 $\|x - \hat{x}_k\|_p$）增强而成的最大值。该优化问题是一个二阶锥规划（SOCP），它是凸的且可在多项式时间内求解。至关重要的是，算法仅在中心点处施加约束，这导致产生了 $K^2$ 个约束，而非类似方法中典型的 $nK$ 个约束，从而显著降低了计算复杂度。
3. 精炼与剪枝：可选的精炼步骤执行局部优化，以最小化经验风险加上惩罚项，并以凸解作为初始化。最后，算法剪掉对经验风险没有影响的参数，并对估计量进行中心化，以确保平均响应值与数据均值一致。

一个关键的创新在于其正则化机制。该算法不需要了解真实的 Lipschitz 常数 $\lambda^*$。相反，它使用基于惩罚的正则化来限制估计量的一致 Lipschitz 常数，从而使该方法能够适应目标函数的未知光滑度。

核心贡献

• 近最优收敛速率：本文证明了在平方损失和亚高斯噪声假设下，DCF 估计量在内在维度 $d^*$ 下实现了 $O(n^{-2/(2+d^*)} \cdot \text{polylog}(n))$ 的近极小极大收敛速率。这对于随机设计设置下的亚高斯分布均成立。
• 可处理性：不同于以往可能依赖非凸优化或缺乏理论保证的 Lipschitz 回归方法，DCF 将估计过程转化为一个可处理的凸优化问题（SOCP）。
• 无需外部选择的自适应性：该方法通过 AFPC 步骤自适应数据的内在维度，并且不需要依靠外部模型选择程序（如交叉验证或样本拆分）来获得近最优保证。
• 未知的 Lipschitz 常数：该算法在无需预知 Lipschitz 常数 $\lambda^*$ 的情况下运行，这相对于需要函数或其导数具有一致界限的方法而言是一个显著优势。
• 向凸回归的扩展：该框架被证明可以适配于凸形状限制回归，为所有 $n \geq 2$ 的情况提供了概率近似正确（PAC）界限，且无需知道 $\lambda^*$，改进了以往局限于特定维度或渐近概率界限的结果。

结果与实验表现
理论分析确认，当使用特定的正则化参数时，DCF 估计量满足近极小极大速率。证明依赖于函数类 $F_p(\hat{X}_K)$ 的逼近性质，该类函数可以以与中心点覆盖半径成正比的误差一致地逼近任何 Lipschitz 函数。

在 Delve Project 数据集（cpusmall, pumadyn-8nm, pumadyn-8nh）上的实验评估将 DCF 与 k-最近邻（k-NN）、Nadaraya-Watson (NW) 核回归、普通最小二乘法 (OLS)、随机森林 (RF) 和 XGBoost 进行了比较。

• 使用对称函数类（delta-max-affine）的 DCF 变体实现了与 k-NN 和 NW 相当甚至更优的均方误差（MSE），并且与基于树的方法（RF, XGBoost）相当。
• 实验强调了 DCF 对正则化参数 $\theta_2$ 的敏感性。较强的正则化可以在有噪声的设置中防止过拟合，但如果划分规模较小，则可能导致欠拟合。
• 在计算方面，对于中等样本量，DCF 的训练时间与核方法（NW）相当，且由于参数剪枝的存在，推理速度很快。

意义
本文声称填补了文献中的一个关键空白，即提供了第一种在随机设计设置下，无需了解 Lipschitz 常数或外部模型选择即可实现近极小极大速率的、可处理的通用 Lipschitz 函数估计方法。通过将 max-affine 方法扩展到 delta-凸设置，作者架起了凸回归的理论最优性与通用 Lipschitz 函数所需的更广泛适用性之间的桥梁。这项工作证明了构建既具有计算效率（多项式时间）又具有统计最优性（近极下极大）的估计量是可能的，为通常需要启发式调优或缺乏如此强理论保证的划分方法或核方法提供了一个稳健的替代方案。