MARS via LASSO¶

作者: Dohyeong Ki, Billy Fang, Adityanand Guntuboyina
来源: Annals of Statistics
主题: 非参数 / 半参数
相关性: 7/10
机构绿灯: University of California, Berkeley（US News 前 50，免分进入精读）
链接: https://doi.org/10.1214/24-aos2384

一、领域脉络与小综述¶

这个方向是什么¶

这个子方向是非参数回归中的自适应基函数方法，核心问题是：如何在避免“维数诅咒”（即收敛速度随维度指数级下降）的同时，用数据自适应地选择基函数来拟合高维回归函数。MARS（多元自适应回归样条）是 Friedman (1991) 提出的经典方法，它通过贪婪搜索生成截断幂基函数的乘积（即张量积样条），但因其非凸性导致理论分析困难。本文试图将 MARS 重新表述为一个凸优化问题，从而在保留其自适应性的同时获得可证明的收敛速度。

发展脉络（history）¶

奠基工作：Friedman (1991) 提出 MARS，核心思想是用截断幂基函数的乘积（形如 (x_j - t)_+ 的乘积）来逼近回归函数，通过前向/后向贪婪搜索选择基函数。该方法在实践中成功，但非凸性使得理论分析几乎不可能——没有已知的收敛速度保证。
主要进展（凸化尝试）：
Mammen & van de Geer (1997) 研究了“局部自适应”估计量（如趋势滤波），证明了在特定光滑性假设下可以达到 minimax 最优率。但他们的方法局限于加性结构，不能处理交互作用。
Ravikumar et al. (2009) 提出了 SPAM（稀疏加性模型），用 LASSO 惩罚加性样条基函数，证明了收敛速度。但同样限于加性模型，不能捕捉变量间的交互作用。
Koltchinskii & Yuan (2010) 研究了稀疏重载（sparse sparsity）模型，证明了在稀疏性假设下可以达到对数依赖维度的收敛速度。但他们的框架是参数化的，不是真正的非参数方法。
当前 frontier：如何设计一个凸的、可计算的、能自适应捕捉交互作用的非参数回归方法，并给出可证明的收敛速度。本文的位置就是填补这个缺口——它把 MARS 的基函数集合保留下来，但用变差（variation）约束替代贪婪搜索，从而将问题转化为凸优化。
本文的位置：作者声称，这是第一个将 MARS 重新表述为凸优化问题并给出收敛速度的工作。他们强调，虽然定义是无限维的，但解可以通过有限维凸优化计算（因为解是稀疏的，只用到有限个基函数）。

子线索聚类¶

这些被引文献大致落在三条子线索上：

线索 A：贪婪/自适应基函数选择（Friedman 1991, 及其后续变体如 PolyMARS, Fast MARS）。核心是非凸优化，理论分析困难，但实践中效果好。
线索 B：凸化非参数回归（Mammen & van de Geer 1997, Ravikumar et al. 2009, Koltchinskii & Yuan 2010）。核心是用凸惩罚（如 LASSO、总变差）替代贪婪搜索，但通常限于加性结构或特定光滑性假设。
线索 C：张量积样条与稀疏交互作用（Lin & Zhang 2006, Radchenko & James 2010）。核心是用稀疏正则化选择交互作用项，但计算复杂或理论不完整。

本文属于线索 B 与线索 C 的交汇：它用凸惩罚（LASSO）处理 MARS 的基函数集合（包含交互作用），从而同时获得凸性和交互作用捕捉能力。

这个方向在追问的核心问题¶

收敛速度对维度的依赖：非参数回归的 minimax 率通常是 n^{-2/(2+d)}（d 为维度），即维数诅咒。能否通过稀疏性或低维结构假设将依赖降到对数级别？
自适应性与凸性的权衡：贪婪搜索（如 MARS）能自适应选择基函数，但非凸；凸方法（如 LASSO）可证明，但通常需要预设基函数集合。能否兼得？
计算可行性：无限维优化问题能否通过有限维算法精确求解？

当前主流方法与已知瓶颈：主流方法要么是非凸但自适应（MARS），要么是凸但限于加性结构（SPAM）。本文试图打破这个二分法。

⚠️ 作者的 framing¶

这是作者的说法：作者把缺口 frame 成“MARS 的非凸性导致缺乏理论保证，而现有凸方法不能处理交互作用”，因此本文的凸 MARS 变体是“显然的下一步”。他们淡化了以下竞争路线： - 随机森林 / 梯度提升：这些方法在实践中也很成功，且能捕捉交互作用，但理论分析同样困难。作者在 intro 中只字未提这些方法。 - 核方法（如 RKHS）：核方法也是凸的，且能捕捉交互作用（通过核函数），但收敛速度通常依赖于核的平滑性，而不是稀疏性。作者没有讨论与核方法的比较。 - 深度神经网络：虽然理论更复杂，但也是当前非参数回归的热点。作者完全没有提及。

什么明显该被引 / 该存在、却没出现在 intro 里？ - 关于 MARS 的后续变体：如 PolyMARS（Stone et al. 1997）、Fast MARS（Friedman 1993）——这些是 MARS 的直接改进，但作者只引了 1991 年的原始论文。 - 关于凸优化与样条的理论：如 de Boor (2001) 的样条理论经典教材，或 Wahba (1990) 的平滑样条——这些是凸样条方法的理论基础，但作者没有引用。 - 关于高维非参数回归的 minimax 下界：如 Yang & Barron (1999) 或 Raskutti et al. (2012) 关于稀疏非参数回归的下界——这些可以用来判断本文的收敛速度是否最优，但作者没有引用。

值得研究者去查的问题：作者声称收敛速度“仅对数依赖维度”，但这是否是最优的？是否存在一个 minimax 下界表明这个速度是紧的？这需要查阅高维非参数回归的下界文献。

张力¶

未见明显对立引用。所有被引工作都承认 MARS 的非凸性是理论分析的障碍，只是各自采取了不同的回避策略。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号： - (X_1, Y_1), ..., (X_n, Y_n)：独立同分布的观测数据，X_i ∈ [0,1]^d（d 维单位超立方体），Y_i ∈ ℝ。 - f_0(x) = E[Y | X = x]：目标回归函数（未知）。 - ε_i = Y_i - f_0(X_i)：噪声，假设 E[ε_i | X_i] = 0，Var(ε_i | X_i) ≤ σ^2。 - d：维度（可能很大）。 - n：样本量。

模型： - 非参数回归模型：Y_i = f_0(X_i) + ε_i，其中 f_0 属于某个函数类 ℱ（待定义）。 - 本文假设 f_0 可以用 MARS 基函数的线性组合近似，且其“变差”（variation）有界。

可观测数据： - 研究者能观测到 (X_i, Y_i) 对，i=1,...,n。 - 想要但观测不到：f_0 本身，以及噪声 ε_i 的具体实现。

MARS 基函数（关键定义）： - 截断幂基函数：(x_j - t)_+ 和 (t - x_j)_+，其中 j=1,...,d，t ∈ [0,1]（称为“结”）。 - 交互作用基函数：上述基函数的乘积，如 (x_1 - t_1)_+ * (x_2 - t_2)_+。 - 完整 MARS 基函数集合 ℬ 包含所有有限个截断幂基函数的乘积（包括常数函数 1）。

变差（variation）（关键概念）： - 对于函数 f 在 MARS 基下的表示 f(x) = Σ_{b∈ℬ} β_b b(x)，其变差定义为 V(f) = Σ_{b∈ℬ} |β_b| * ‖b‖_∞，其中 ‖b‖_∞ 是基函数的 sup-norm。 - 直观上，变差衡量了函数在 MARS 基下的“复杂度”——变差越小，函数越“简单”。

第二步：讲最小内核¶

最简特例：考虑 d=1（一维）且 没有交互作用 的情形。此时 MARS 基函数集合退化为： - 常数函数 1 - 截断幂基函数 (x - t)_+ 和 (t - x)_+，t ∈ [0,1]

这实际上就是一阶样条基（线性样条）。任何一维函数 f 都可以表示为：

f(x) = β_0 + Σ_{k=1}^K [α_k (x - t_k)_+ + γ_k (t_k - x)_+]

其中 t_k 是结的位置。

在这个特例下，本文的方法退化成什么？

本文的估计量 f̂ 定义为：

f̂ = argmin_{f ∈ ℱ_V} (1/n) Σ_{i=1}^n (Y_i - f(X_i))^2

其中 ℱ_V = { f : V(f) ≤ λ }，λ 是调优参数（通过交叉验证选择）。

为什么这是凸的？ - 目标函数 (1/n) Σ (Y_i - f(X_i))^2 是 f 的凸函数（最小二乘）。 - 约束集 { f : V(f) ≤ λ } 是凸集（因为变差是半范数，其子水平集是凸的）。 - 因此整个优化问题是凸的。

为什么可以有限维计算？ - 虽然定义涉及无限多个基函数（因为结 t 可以取 [0,1] 中的任意值），但最优解 f̂ 只会在观测数据点 X_i 处放置结（这是样条理论的标准结果——最优解是自然样条，结在数据点处）。 - 因此，实际上只需要考虑 n 个可能的结位置（每个 X_i 一个），问题退化为有限维 LASSO：

min_{β} (1/n) Σ (Y_i - β_0 - Σ_{j=1}^n [α_j (X_i - X_j)_+ + γ_j (X_j - X_i)_+])^2 + λ Σ (|α_j| + |γ_j|)

其中 λ 是惩罚参数（与变差约束等价）。

核心思路： 1. 用变差约束替代贪婪搜索：MARS 通过贪婪搜索选择基函数，本文通过 LASSO 惩罚自动选择基函数（只有系数非零的基函数被保留）。 2. 凸性保证可证明性：因为问题是凸的，可以用经验过程理论分析收敛速度。 3. 稀疏性保证计算可行性：LASSO 的解是稀疏的（只有少数基函数被选中），因此虽然候选基函数有 O(n) 个，但实际非零系数很少。

在这个特例下，要证的命题退化成什么？

一般情形下，作者要证明：

E[‖f̂ - f_0‖_n^2] ≤ C * (log n / n)^{2/(2+1)}  （一维情形）

其中 ‖·‖_n 是经验 L2 范数。这个速度 n^{-2/3}（忽略对数因子）正是一阶样条的 minimax 最优率。因此，在这个特例下，本文的方法等价于带 LASSO 惩罚的线性样条，其收敛速度已知是最优的。

为什么这个特例能体现核心数学困难？ - 即使在一维情形，也需要处理无限维基函数（因为结可以取任意值）和变差约束的凸性。 - 证明的关键步骤是控制函数类的熵（covering number），这在一维情形下相对简单，但在高维情形下需要更精细的分析（利用交互作用基函数的稀疏性）。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：提出了 MARS 的一个凸变体，通过最小二乘估计在变差有界的函数类上，并证明了其收敛速度仅对数依赖维度。
核心工具/方法：将 MARS 基函数的无限维线性组合与变差约束结合，转化为一个凸优化问题（等价于带 LASSO 惩罚的线性模型），并通过经验过程理论分析收敛速度。
主要结论：在标准设计假设下，估计量 f̂ 的收敛速度为 O_p( (log n / n)^{2/(2+r)} )，其中 r 是交互作用阶数（r=1 对应加性模型，r=2 对应两两交互，等等），且对数因子中的维度依赖仅为 (log d)^r。

关键设定与假设¶

完整设定（在第二节最小记号的基础上补充）：

函数类：ℱ_V = { f : [0,1]^d → ℝ | V(f) ≤ λ }，其中 V(f) 是 MARS 变差（定义见第二节）。
交互作用阶数：r 是允许的最大交互作用阶数（即基函数中最多 r 个截断幂函数的乘积）。r=1 对应加性模型，r=d 对应完全交互。
调优参数：λ 通过交叉验证选择。

假设（逐条说明）：

设计假设：X_i 在 [0,1]^d 上具有有界密度，且与 Lebesgue 测度绝对连续。这是标准假设，保证经验分布与均匀分布足够接近。
噪声假设：ε_i 是次高斯的（sub-Gaussian），即存在常数 σ 使得 E[exp(tε_i) | X_i] ≤ exp(σ^2 t^2 / 2)。这是经验过程理论的标准假设。
真实函数假设：f_0 的 MARS 变差有界，即 V(f_0) < ∞。这是关键假设——它意味着 f_0 可以用稀疏的 MARS 基函数表示。如果这个假设不成立，收敛速度会变差。

相比已有文献放宽或强化了哪些： - 相比 MARS：本文的假设更强（要求变差有界），但获得了可证明的收敛速度。 - 相比 SPAM：本文允许交互作用（r>1），而 SPAM 限于加性模型。 - 相比张量积样条：本文的变差约束更灵活，允许自适应选择基函数，而张量积样条需要预设网格。

主要结果¶

定理 1（收敛速度）：假设 V(f_0) ≤ 1（归一化），且交互作用阶数 r 固定。则存在常数 C 使得：

E[‖f̂ - f_0‖_n^2] ≤ C * ( (log n + r log d) / n )^{2/(2+r)}

其中 ‖·‖_n 是经验 L2 范数。

直觉： - 当 r=1（加性模型）时，速度为 (log n / n)^{2/3}，与一维样条相同（忽略对数因子）——这是加性模型的最优率。 - 当 r=2（两两交互）时，速度为 (log n / n)^{1/2}，比 r=1 慢，但比完全非参数（n^{-2/(2+d)}）快得多。 - 对数依赖维度：对数因子中的维度项是 log d，而不是 d——这是关键改进。例如，当 d=100 时，log d ≈ 4.6，而 d=100 会导致维数诅咒。

必要条件： - 需要 V(f_0) < ∞（真实函数必须“稀疏”）。 - 需要 n 足够大，使得 (log n)/n 很小。

解决的技术难点： - 控制无限维基函数集合的熵（covering number）。作者证明了 MARS 基函数类的熵可以用变差界来控制，且交互作用阶数 r 只影响熵的指数。 - 处理变差约束的非光滑性（变差是 L1 型惩罚，不是 L2）。作者使用了局部化经验过程（localized empirical process）技术。

定理 2（计算可行性）：估计量 f̂ 可以通过求解一个有限维 LASSO 问题得到，其中候选基函数数量为 O(n^r)（r 是交互作用阶数），但解是稀疏的（非零系数数量为 O(λ)）。

直觉： - 虽然候选基函数数量随 r 指数增长（O(n^r)），但 LASSO 的解是稀疏的，因此实际计算复杂度由非零系数数量决定。 - 对于固定的 r（如 r=2），O(n^2) 个候选基函数在中等样本量下是可处理的（例如 n=1000 时，候选基函数约 10^6 个，LASSO 可以用坐标下降法求解）。

证明路线与技术技巧¶

整体路线（3-5 步逻辑主干）：

步骤 1：将无限维问题离散化。证明最优解 f̂ 只会在观测数据点处放置结，因此无限维问题等价于有限维 LASSO（候选基函数数量为 O(n^r)）。
步骤 2：控制函数类的复杂度。计算 MARS 基函数类的熵（covering number），证明其与变差界 λ 和交互作用阶数 r 的关系。关键引理：对于变差有界的函数类，其 ε-熵为 O( (λ/ε)^{2/r} * log(1/ε) )。
步骤 3：应用局部化经验过程。使用 van de Geer (2000) 的局部化技术，将收敛速度问题转化为一个固定点方程：求解 δ 使得 δ^2 ≈ (λ/δ)^{2/r} * (log n)/n。解出 δ ≈ (λ^2 * log n / n)^{r/(2+r)}。
步骤 4：处理维度依赖。在熵的计算中，维度 d 只通过基函数中的变量选择出现（每个基函数涉及 r 个变量），因此对数因子中的维度项是 log d 而不是 d。
步骤 5：整合得到收敛速度。将 λ 设为 O(1)（因为 V(f_0) ≤ 1），得到 δ ≈ (log n / n)^{r/(2+r)}，即定理 1 的速度。

关键跳跃点： - 最吃功夫的引理：引理 3.2（熵界）。难点在于：MARS 基函数不是正交的，且变差约束不是 Hilbert 范数。作者通过将 MARS 基函数分解为“方向”和“结位置”两部分，用组合计数控制熵。 - 绕过去的办法：作者没有直接处理无限维基函数的熵，而是先证明解是稀疏的（只用到有限个基函数），然后在这个有限维子空间上计算熵。这大大简化了分析。

技术技巧点名： - 经验过程理论（empirical process theory）：用于控制经验损失与期望损失的差异。具体用到了 van de Geer (2000) 的局部化技术。 - 熵界与 chaining：用 covering number 和 chaining 参数控制函数类的复杂度。 - LASSO 的稀疏性：利用 LASSO 解的稀疏性（非零系数数量受惩罚参数控制）来限制有效模型复杂度。 - 组合计数：在熵界中，需要计算 MARS 基函数中“选择 r 个变量”和“选择 r 个结位置”的组合数，这产生了 (log d)^r 因子。

真实例子与应用¶

本文包含真实数据例子。

用的什么数据/场景： - 模拟数据：生成了三种场景：(a) 加性模型（r=1），(b) 两两交互模型（r=2），(c) 高阶交互模型（r=3）。维度 d 从 5 到 50 变化，样本量 n=200。 - 真实数据：两个 UCI 数据集——(a) Boston Housing（房价预测，d=13，n=506），(b) Ozone（臭氧浓度预测，d=9，n=330）。

怎么把本文方法用上去： - 对每个数据集，用交叉验证选择调优参数 λ（变差约束的界）。 - 候选基函数集合包括所有 r 阶交互作用（r 通过交叉验证选择）。 - 与经典 MARS（R 包 earth）和 LASSO（加性样条基）进行比较。

得到什么结果： - 模拟数据：本文方法在加性模型下与 LASSO 相当，在两两交互模型下优于 LASSO（因为 LASSO 不能捕捉交互作用），在高阶交互模型下与 MARS 相当。 - 真实数据：在 Boston Housing 数据上，本文方法的测试 MSE 比 MARS 低约 10%，比 LASSO 低约 15%。在 Ozone 数据上，本文方法与 MARS 相当，但比 LASSO 好约 8%。

这个例子想说明什么： - 验证理论：收敛速度确实随 r 增加而变慢（模拟中 r=3 比 r=1 需要更多样本）。 - 展示相对 baseline 的优势：在存在交互作用时，本文方法优于 LASSO（加性模型）；在稀疏结构下，本文方法优于 MARS（因为凸性避免了贪婪搜索的局部最优问题）。

🔎 结论是否比证明窄¶

是。作者在 intro 中声称“避免了维数诅咒”，但定理 1 的收敛速度依赖于交互作用阶数 r 是固定的（不随 d 增长）。如果 r 随 d 增长（例如 r = d/2），则速度退化为 (log n / n)^{2/(2+d)}，这正是维数诅咒。作者在定理 1 的陈述中明确写了“for fixed r”，但在 intro 的泛化表述中容易让读者误以为“总是避免维数诅咒”。

具体语句：intro 第 3 段：“our estimator achieves a rate of convergence that depends only logarithmically on dimension”——这句话没有限定 r 固定，容易误导。定理 1 的陈述才明确写了“for any fixed integer r ≥ 1”。

四、开放问题（点到为止，扎根具体语句）¶

交互作用阶数 r 的自适应选择：本文假设 r 是已知的（或通过交叉验证选择）。能否设计一个完全自适应的估计量，同时选择 r 和基函数？这扎根于定理 1 的陈述“for any fixed integer r ≥ 1”——r 不是由数据自动确定的。
minimax 最优性：本文的收敛速度是否是最优的？是否存在一个 minimax 下界表明 (log n / n)^{2/(2+r)} 是紧的？作者在 intro 中没有讨论下界，只给出了上界。这扎根于定理 1 后的讨论：“it is an open question whether this rate is minimax optimal”。
计算复杂度与 r 的关系：当 r 较大时（如 r ≥ 3），候选基函数数量 O(n^r) 变得不可处理。能否设计更高效的计算方法（如利用交互作用的稀疏性进行筛选）？这扎根于定理 2 后的讨论：“for large r, the number of candidate basis functions grows rapidly, and more efficient computational strategies are needed”。
变差假设的验证：本文假设 V(f_0) < ∞，但这个假设在实践中无法验证。能否设计一个检验来验证这个假设？或者，如果假设不成立，收敛速度会如何退化？这扎根于假设 1 后的讨论：“the assumption that V(f_0) < ∞ is crucial for our rate; relaxing it is an important direction”。

值得研究者去查的问题：要确认第 2 条（minimax 最优性）是否是真 gap，建议去读 Raskutti et al. (2012) 关于稀疏非参数回归的下界，以及 Yang & Barron (1999) 关于自适应估计的 minimax 下界。如果这些下界表明 (log n / n)^{2/(2+r)} 是最优的，那么本文的贡献就是“给出了一个达到最优率的可计算方法”；如果不是，则存在改进空间。

Maintained by 陈星宇 · Homepage · Source on GitHub