线性稀疏支持向量机（SVM）的近端梯度法线性收敛性及其统计计算意义分析

本文系统研究了?1惩罚线性支持向量机（SVM）的优化算法与统计收敛性质。尽管铰链损失函数非强凸且非强光滑，作者通过近端梯度法（Proximal Gradient Method）结合正则化参数路径追踪，证明了算法在O(log s)迭代次数内达到统计误差范围内的线性收敛，其中s为真实系数的稀疏度。该研究首次实现了数值收敛与统计收敛的同步分析，为高维稀疏分类模型提供了计算效率保证。

　　

Highlight

尽管铰链损失函数既不强凸也不强光滑，我们建立了稀疏线性支持向量机（SVM）达到统计精度范围内的线性收敛速率。所用算法是针对复合函数的近端梯度法，应用于正则化参数序列以在网格上计算近似解路径。与强凸强光滑损失函数的研究不同，这里我们并非线性收敛到精确解，但能够证明在统计误差范围内向总体真值的线性收敛（我们同时考虑了数值收敛和统计收敛）。对于所选递减序列中的任何正则化参数，我们表明估计量在O(log s)次迭代后处于精确解的小邻域内，其中s是模型真实系数的稀疏度，且总共需要O(log n)个阶段（即使用长度为O(log n)的正则化参数序列）以达到近Oracle统计速率，其中n为样本量。

Methodology

在继续之前，我们回顾凸函数可能不可微时的次微分和次梯度使用。β处的次微分?f(β)是包含所有g∈R^p的非空集合，满足f(β′) ≥ f(β) + 〈g, β′ ? β〉，?β′。?f(β)中的任何元素称为f在β处的次梯度。当函数在β处可微时，?f(β)包含唯一元素?f(β)，即梯度。即使在不可微点，我们仍使用?f(β)表示特定次梯度。

Theoretical results

在本节中，我们陈述并证明所获解的收敛性和统计性质。我们首先说明所使用的假设。

• •
  (A1) EL(β)的最小化器β₀存在且唯一，∥β₀∥₀ = s^* ≥ 1，且算法中的R选择得足够大以使∥β₀∥ ≤ R/2。
• •
  (A2) ∥E[x]∥_∞有界，且x是次高斯的，即E exp{a^T(x ? E[x])} ≤ exp{C∥a∥²}, ?a∈R^p。我们进一步假设y x^Tβ的密度在集合B(R) ? {0} = {∥β∥ ≤ R, β ≠ 0, ∥β∥₀ ≤ C s^*}上于[0.9,1.1]一致有界。

Numerical results

在本节中，我们呈现数值结果以评估基于近端梯度下降（PG-SVM）所提方法的实际性能。

Conclusion and Discussion

在本文中，我们详细分析了在正则化参数序列上高效计算的稀疏线性SVM的近端梯度算法。我们表明，在对数次迭代后，估计量收敛到真实参数的邻域，该邻域大小与给定样本量的近Oracle统计误差相同。我们预计此处对SVM进行的分析可以推广到其他非光滑模型，如分位数回归。