Optimal Dimension-Free Sampling for Regularized Classification¶

会议: NeurIPS 2026
arXiv: 2605.23726
OpenReview: https://openreview.net/forum?id=Gv4HMpqs8v
论文: https://arxiv.org/abs/2605.23726
领域: 其他
关键词: 样本复杂度, 维度无关采样, 核心子集, 经验过程, 正则化分类

一句话总结¶

本文针对带正则化项的宽泛 Lipschitz 分类损失函数（包含 Logistic、Sigmoid、Hinge 与 ReLU），提出了一种基于行范数与均匀混合采样的维度无关采样框架，借助经验过程高阶矩与度量熵链式积分将此前立方阶界限突破至紧致的线性 $\tilde{\Theta}(k/\varepsilon^2)$ 与二次 $\Theta(k^2/\varepsilon^2)$ 阶，并给出了匹配的下界与不可行性证明。

研究背景与动机¶

在大规模机器学习与高维统计推断中，线性分类器的样本复杂度是量化泛化误差与数据压缩极限的核心基石。经典的统计学习理论依托 Vapnik-Chervonenkis (VC) 维或 Rademacher 复杂度，给出的样本界通常显式线性依赖于特征空间维度 $d$。然而在现代数十亿参数大模型或超高维全基因组分析中，特征维度 $d$ 往往远超样本量，甚至在再生核希尔伯特空间 (RKHS) 中维度可扩展至无穷大，这使得依赖维度的样本界丧失了实际指导意义。此外，传统的 PAC 学习框架主要提供绝对加性误差界，当优化算法逐渐逼近损失极小值点时，其相对误差会急剧发散，无法为下游高精度优化提供鲁棒的相对近似保证。

为了摆脱维度诅咒并提供 $(1\pm\varepsilon)$ 相对乘性误差保证，近年来的核心子集 (coreset) 研究引入了显式正则化项 $\mathcal{R}(x)/k$，通过将模型参数的模长隐式约束在紧致区域内来实现维度无关的数据子采样。然而，现有的维度无关方法深陷多重理论与算法瓶颈：一方面，传统敏感度采样 (sensitivity sampling) 依赖于对每个样本点全局影响力的复杂上界估计，其计算开销巨大；另一方面，既有的 Rademacher 复杂度分析框架在控制经验过程上界时存在严重的过度计数 (overcounting)，导致样本复杂度停留在较差的三次方阶 $O(k^3/\varepsilon^2)$（如 Alishahi 与 Phillips 在 ICML 2024 的代表性工作），未能揭示正则化分类问题在不同正则项与损失函数相互作用下的本质极限。

本文的研究切入点在于重构经验过程极值的矩控制机制，探索何时能够以最简单的采样策略达成理论最优的样本规模。作者发现，根本无需复杂的敏感度估计，仅需将均匀采样与欧氏范数采样进行均衡混合，即可完全控制高范数异常样本对相对误差的支配作用；更关键的是，借助经验过程的高阶矩不等式、Dudley 度量熵积分与反集中对抗构造，能够精确刻画出从线性到二次、乃至不可行样本界的全景图谱。核心 idea：摒弃依赖 VC 维的传统敏感度采样框架，采用均匀采样与行范数采样的均衡混合策略，结合高阶矩方法、Talagrand 收缩不等式与分层度量熵积分，证明了带正则化分类损失函数的维度无关相对误差采样复杂度主要由导数有界性与原点非零性决定，并在各类正则项下分别达成了紧致的线性 $\tilde{\Theta}(k/\varepsilon^2)$、二次 $\Theta(k^2/\varepsilon^2)$ 上下界以及 ReLU 岭正则下的不可行性下界。

方法详解¶

整体框架¶

本文的目标是从未知分布 $\mathcal{P}$（或具有 $n$ 个样本的有限数据集）中抽取 $m$ 个带权样本点 $\{(a_i, w_i)\}_{i=1}^m$，构建加权经验近似目标函数 $f_S(x) = \frac{1}{m}\sum_{i=1}^m w_i g(\langle a_i, x \rangle) + \mathcal{R}(x)/k$，以确保在整个参数空间 $\mathbb{R}^d$ 上一致满足相对误差保证： $$\forall x \in \mathbb{R}^d: \left| f(x) - f_S(x) \right| \le \varepsilon f(x)$$ 其中原目标函数为 $f(x) = f_0(x) + \mathcal{R}(x)/k = \int g(\langle a, x \rangle) d\mathcal{P}(a) + \mathcal{R}(x)/k$，$g(\cdot)$ 为 $L$-Lipschitz 单调损失函数（如 Logistic、Sigmoid、Hinge、ReLU），$\mathcal{R}(x) \in \{\|x\|_2^2, \|x\|_2, \|x\|_1\}$ 分别代表岭正则 (Ridge)、二范数正则与 Lasso 正则。

整个算法与分析流水线包含四个核心模块：首先通过混合范数采样消除敏感度计算并压制高范数点权重；其次利用对称化将相对误差上确界转化为高阶经验过程，并运用 Khintchine-Kahane 与 Talagrand 压缩不等式推导普适的二次界；随后在特定几何与光滑性条件下，通过二进分层切片与覆盖数积分证明最优线性上界；最后针对各组合构造极值几何对抗实例证明匹配的下界。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入数据分布 P 与正则化分类目标 f(x)"] --> B["混合范数重要性采样与流式权重控制"]
    B --> C["经验过程高阶矩与 Lipschitz 收缩界"]
    C --> D["分层切片与度量熵覆盖数精细积分"]
    D --> E["极值对抗构造与反集中下界分析"]
    E --> F["输出：紧致的线性/二次相对误差采样界与不可行性判定"]

关键设计¶

1. 混合范数重要性采样与流式权重控制：解决敏感度难以估计与高范数点误差主导问题 传统的相对误差核心子集构建往往需要先计算每个样本点在参数空间上的敏感度上界，这一过程在高维或流式环境下计算复杂度极高且依赖于复杂的几何嵌入。本文指出，相对误差发散的主导根源在于高欧氏范数的数据点在内积 $\langle a, x \rangle$ 发生剧烈扰动时会导致损失函数产生超额漂移。为此，本文设计了一种极其简捷的提议分布 $\mathcal{Q}$，将基准数据分布 $\mathcal{P}$ 与基于打分函数 $s(a)$ 的重要性分布进行 $1:1$ 均衡混合： $$d\mathcal{Q}(a) = \left( \frac{s(a)}{2S} + \frac{1}{2} \right) d\mathcal{P}(a) = \frac{s(a) + S}{2S} d\mathcal{P}(a)$$ 其中打分函数对于二范数或一范数正则设定为 $s(a) \ge \|a\|_2 + 1$，对于平方二范数正则设定为 $s(a) \ge \|a\|_2^2 + 2$，$S = \int s(a) d\mathcal{P}(a)$ 为全概率空间的总得分期望。对应抽样点的修正权重设为 $w_i = \frac{2S}{s(a_i) + S}$。该设计的绝妙之处在于保证了权重具有均匀上界 $w_i \le 2$，同时强制乘积项满足 $w_i \|a_i\|_2 \le S$。在流式算法场景中，该分布可借由蓄水池采样 (reservoir sampling) 或转向采样 (turnstile row-norm sampling) 以黑盒方式完全离线或在线实现，彻底摆脱了此前依赖数据维度与复杂敏感度评分的沉重负担。

2. 经验过程高阶矩与 Lipschitz 收缩界：突破传统敏感度框架过度计数与三次阶瓶颈 在理论分析层面，此前 Alishahi 与 Phillips (2024) 采用 Rademacher 复杂度分析导致采样量退化至 $O(k^3/\varepsilon^2)$，其症结在于将整个参数空间上的经验过程极值粗糙地用一致覆盖数结合统一方差界予以放大。本文通过对称化技巧将相对误差上确界 $E \coloneqq \sup_{x \in \mathbb{R}^d} |f_0(x) - \frac{1}{m}\sum_{i=1}^m w_i g(\langle a_i, x \rangle)| / f(x)$ 映射为 Rademacher 随机变量 $\sigma_i \sim U\{-1, +1\}$ 驱动的经验过程。为了控制尾部概率，文章不走常规的联立一致收敛，而是推导该经验过程的 $\ell$ 阶高阶矩（取 $\ell = O(\ln(1/\delta))$）： $$\mathbb{E}[E^\ell] \le \left( \frac{SL\sqrt{\ell}}{\sqrt{m}} \cdot \sup_{x \in \mathbb{R}^d} \left( \frac{\|x\|_2}{OPT + \mathcal{R}(x)/k} \right) \right)^\ell$$ 利用 Ledoux-Talagrand 的 Lipschitz 收缩引理消除非线性损失函数 $g$ 的影响，再结合 Khintchine-Kahane 不等式精确约束 $\mathbb{E}[|\sum \sigma_i w_i \langle a_i, x \rangle|^\ell]$，从而将范数期望项化简为 $\mathbb{E}[(\ell \sum w_i^2 \|a_i\|_2^2)^{\ell/2}]$。由于前述权重控制使 $w_i \|a_i\|_2 \le S$，上式极值完全转化为确定性的几何比率 $\sup_{x} \frac{\|x\|_2}{OPT + \mathcal{R}(x)/k}$。对于 $\mathcal{R}(x) = \|x\|_2$，该几何极值为 $2k$；对于 $\mathcal{R}(x) = \|x\|_2^2$，极值为 $\sqrt{k/OPT}$。由于在 $g(0) > 0$ 时全局极小值满足 $OPT \ge \Omega(1/k)$，直接运用 Markov 不等式 $\Pr(E \ge \varepsilon) \le \mathbb{E}[E^\ell]/\varepsilon^\ell \le 2^{-\ell} \le \delta$，便以极其优雅清晰的方式确立了普适的 $O(k^2/\varepsilon^2)$ 二次上界，直接击碎了旧有分析的三次方障碍。

3. 分层切片与度量熵覆盖数精细积分：实现岭正则与 Lasso 下的线性阶采样上界 为了在二次界的基础上进一步下探至线性采样复杂度 $O(k/\varepsilon^2)$，本文在特定损失与正则组合下引入了基于高斯过程与 Dudley 度量熵积分的精细化局部经验过程分析。分析的核心在于将无界参数空间按目标函数值划分为二进切片层 $T_\alpha = \{x \in \mathbb{R}^d \mid \alpha \le f(x) \le 2\alpha\}$，并在每一层上度量高斯过程诱导的伪度量 $d_X(s, t)$。对于岭正则 $\mathcal{R}(x) = \|x\|_2^2$，当损失函数具备有界导数性质（即对所有标量均满足 $|g'(r)| \le g(r)$，如 Logistic 与 Sigmoid 损失）时，伪度量可被嵌入至加权样本子空间的 $\ell_\infty$ 范数。作者利用半高斯变量极大值的对数增长特性结合 Sudakov 对偶极小化定理，对大半径球与小半径网格进行分段积分，推导出度量熵积分满足： $$\mathcal{E} = \int_0^\infty \sqrt{\log E(T_\alpha, \|\cdot\|_X, t)} \, dt \le \tilde{O}\left( G \alpha \sqrt{\frac{SLk}{m}} \right)$$ 与此同时，切片内的度量直径 $\mathcal{D}$ 同样被严格控制在 $O(G \alpha \sqrt{SLk/m})$。通过平衡直径与度量熵，成功借助 Woodruff 与 Yasuda 的高阶高斯过程矩界消解了对 $OPT$ 的倒数依赖，在二进切片层上达成局部线性界，并通过沿几何级数 $\alpha \ge OPT \ge \Omega(1/k)$ 的并集界延拓至全空间。对于 Lasso 正则 $\mathcal{R}(x) = \|x\|_1$，作者更进一步巧妙避开了对导数有界性的苛刻要求，利用极值行聚合法与矩阵秩的自由度反向约束高斯复杂度，证明了一般 Lipschitz 损失在齐次分解 $g = h + b$ 下同样享有近乎紧致的线性采样复杂度 $\tilde{O}(k/\varepsilon^2)$。

4. 极值对抗构造与反集中下界分析：确立二次下界、对数匹配下界及不可行性结果 为了验证上述上界的最优性，本文系统设计了一套利用离散正交基向量与循环多胞形 (cyclic polytope) 的对抗几何分布。对于二次下界，针对 Logistic/Sigmoid 结合二范数正则，作者构造了支撑在 $n = \Theta((k/\varepsilon)^2)$ 个标准正交基上的均匀分布；若样本量 $m \le n/2$，则必有一半维度的坐标未被命中。设计对抗查询向量 $x = \sum_{i \notin S} e_i$，使得原目标函数被正则项主导为 $O(1/\varepsilon)$，而抽样近似因缺失支撑点导致损失部分严重失真，相对误差必然超过 $\varepsilon$。在 Hinge 与 ReLU 损失下，由于其导数在零点产生跳变、不具备 $|g'| \le g$ 条件，该几何构造在岭正则下同样迫使误差达到 $\Omega(k^2/\varepsilon^2)$。对于线性下界，作者构造了 $N = \Theta(k)$ 个支撑点的极端分布，将多项式抽样频次的偏差转化为 Feller 反集中不等式下的指数级单点失败概率；由于多项分布坐标的负关联性 (negative association)，迫使全局失误率控制在 $\delta$ 内的必要样本量必须达到 $\Omega(\varepsilon^{-2} k \log k)$ 或 $\Omega(\varepsilon^{-2} k / \log k)$。最惊人的发现出现在 ReLU 损失与岭正则的组合中：由于 $g(0) = \text{ReLU}(0) = 0$，当在原点附近以极小尺度 $\eta \to 0$ 查询被分离点时，岭正则以 $\eta^2$ 速度收敛至 0，其正则效应完全被线性的 $\Theta(\eta)$ ReLU 损失淹没。通过将样本点配置在有理矩曲线上形成循环多胞形，任何子采样都面临“赠券收集问题”(coupon collector's problem)，从而严格证明了无论数据维度如何，样本量必须满足 $\Omega(n \log n)$，彻底宣告了该设定下维度无关以及次线性采样保证的不可能性。

损失函数 / 训练策略¶

本文的方法主要作为前置离线数据压缩或在线流式数据提炼器使用，其算法伪代码与执行策略如下： 1. 采样权重预处理：给定流式或静态数据流，以先验常数或均值计算打分阈值 $S$（若在未知分布下，先通过 $O(D^p \ln(1/\delta)/\varepsilon^2)$ 规模的极小均匀预采样估计 $\hat{S} = (1\pm\varepsilon)S$）。 2. 两阶段抛硬币筛选机制：对于每个输入样本点 $a \sim \mathcal{P}$，独立抛掷一枚公正硬币。若为正面，直接无条件保留进入核心子集并赋予权重 $w(a)$；若为反面，则执行拒绝采样，以概率 $s(a)/S$ 决定是否接纳。 3. 经验优化求解：在抽取得到的容量为 $m$ 的带权核心子集 $S$ 上，使用任意现成的凸/非凸优化器（如拟牛顿法 L-BFGS 或随机方差缩减梯度下降 SVRG）最小化目标函数： $$\min_{x \in \mathbb{R}^d} \left\{ \frac{1}{m} \sum_{i=1}^m w_i g(\langle a_i, x \rangle) + \frac{\mathcal{R}(x)}{k} \right\}$$ 由于相对误差界在全空间严格成立，该核心子集上的经验风险最小化解可直接作为全量数据真实经验风险最小化解的 $(1\pm O(\varepsilon))$ 强近似，且训练开销降低数个数量级。

实验关键数据¶

主实验¶

论文以严密完备的数学定理形式对各类代表性分类损失函数与经典正则项进行了系统性的全景复杂度刻画，下表总结了本文建立的理论样本规模与先前 SOTA 结果（Alishahi & Phillips, ICML 2024）的全面对比（其中所有界均包含隐式 $\varepsilon^{-2}$ 因子，记 $\widetilde{k} \coloneqq k(\log k)^3 \log\log k$）：

正则化项 $\mathcal{R}(\cdot)$	损失函数类别	本文上界 $m_0$	本文匹配下界	先前 SOTA (ICML'24)	渐近紧致性判定
岭正则 $\\|x\\|_2^2/k$	Logistic 损失	$O(\widetilde{k} \varepsilon^{-2})$	$\Omega(k (\log k)^{-1} \varepsilon^{-2})$	$\tilde{O}(k^3 \varepsilon^{-2})$	近乎紧致（仅差对数因子）
岭正则 $\\|x\\|_2^2/k$	Sigmoid 损失	$O(\widetilde{k} \varepsilon^{-2})$	$\Omega(k (\log k)^{-3} \varepsilon^{-2})$	$\tilde{O}(k^3 \varepsilon^{-2})$	近乎紧致（仅差对数因子）
岭正则 $\\|x\\|_2^2/k$	Hinge (SVM) 损失	$\Theta(k^2 \varepsilon^{-2})$	$\Omega(k^2 \varepsilon^{-2})$	$\tilde{O}(k^3 \varepsilon^{-2})$	严格紧致 $\Theta(k^2/\varepsilon^2)$
岭正则 $\\|x\\|_2^2/k$	ReLU 损失	$\infty$ (无维度无关界)	$\Omega(n \log n)$	$\tilde{O}(k^3 \varepsilon^{-2})$* (需人工下界)	证明维度无关完全不可行
Lasso 正则 $\\|x\\|_1/k$	Logistic / Sigmoid	$O(\widetilde{k} \varepsilon^{-2})$	$\Omega(k (\log k)^{\pm 1} \varepsilon^{-2})$	$\tilde{O}(k^3 \varepsilon^{-2})$	近乎紧致（仅差对数因子）
Lasso 正则 $\\|x\\|_1/k$	Hinge / ReLU	$O(\widetilde{k} \varepsilon^{-2})$	$\Omega(k \log k \varepsilon^{-2})$	$\tilde{O}(k^3 \varepsilon^{-2})$	近乎紧致（仅差对数因子）
二范数正则 $\\|x\\|_2/k$	任意 Lipschitz 损失	$\Theta(k^2 \varepsilon^{-2})$	$\Omega(k^2 \varepsilon^{-2})$	$\tilde{O}(k^3 \varepsilon^{-2})$	严格紧致 $\Theta(k^2/\varepsilon^2)$

*注：ICML 2024 的结果对于 ReLU 设定必须强加 $f(x) \ge c_0 > 0$ 的非平凡下界假设，否则同样发散。

消融实验¶

为了理清决定样本复杂度阶数（线性 vs 二次 vs 不可行）的核心数学条件，下表给出了各关键假设性质在理论推导中的作用消融与退化机制：

分析维度 / 假设条件	满足该条件的典型配置	样本复杂度	失效或违背时的退化行为	理论瓶颈机制与消融分析
**导数有界条件 $	g'	\le g$**	岭正则 + Logistic / Sigmoid	线性 $\tilde{O}(k/\varepsilon^2)$
原点正值条件 $g(0) > 0$	Hinge ($g(0)=1$), Logistic ($g(0)=\ln 2$)	维度无关有限界	退化为样本量 $\Omega(n \log n)$	当 $g(0)=0$ (ReLU) 时，原点处目标函数值完全归零；微小扰动下正则项 $\Theta(\eta^2)$ 衰减快于损失项 $\Theta(\eta)$，相对误差发散
齐次性可分解 $g = h + b$	Lasso 正则 + 任意常见损失	全空间 $\mathbb{R}^d$ 线性界	仅在有界切片 $f(x) \le \frac{g(0)}{\varepsilon}$ 成立	齐次部分可直接做尺度缩放，有界部分误差受常数截断；若函数不可分解，全空间大尺度区域相对误差无法闭合
混合重要性分布 $s(a) \propto \\|a\\|_2 + 1$	全体正则分类设定	鲁棒无界支撑集	若仅用均匀采样，退化为需假设 $\\|a\\|_2 \le D$	均匀采样极易漏抽高范数关键几何顶点，导致内积扰动下相对误差无界；范数打分强制 $w_i \\|a_i\\| \le S$，压制异常点

关键发现¶

二范数正则的固有脆弱性：二范数正则 $\|x\|_2/k$ 是三类正则项中约束能力最弱的一种。无论是光滑的 Logistic 还是非光滑的 Hinge，其样本复杂度在下界构造中均被牢牢钉死在 $\Omega(k^2/\varepsilon^2)$，无法借助经验过程度量熵细化获得任何渐近提升。
正则化与损失尺度的局部失配：ReLU 与岭正则的组合展现了深刻的病态特性——由于在原点处 $f(0) = 0$，只要沿特定对抗方向引入微小尺度因子 $\eta \to 0$，一阶损失项与二阶正则项的衰减速度失配会完全抹除正则化的几何稳定效应，导致即使是简单凸优化问题，其相对误差采样也无法摆脱全量样本的赠券收集下界。
Lasso 正则对几何复杂度的天然压制：一范数正则通过将对偶范数约束在高维正方体（$\ell_\infty$ 极值球）内，配合矩阵子空间行聚合引理，天然规避了高维空间中维度的显式扩张，从而使非光滑损失（Hinge 与 ReLU）在 Lasso 下依然能够达到最优的近线性复杂度 $\tilde{O}(k/\varepsilon^2)$。

亮点与洞察¶

算法极简性与免参数敏感度：本框架算法层面仅需基于简单行范数的拒绝抽样或蓄水池抽样，完全无需计算复杂的子空间杠杆得分 (leverage scores) 或 Lewis 权重，大幅降低了流式和分布式数据缩减的实现门槛。
打破统计学习界的“过度计数”范式：以往文献过度依赖 VC 维或粗糙的局部 Rademacher 复杂度，将全参数空间的联合波动粗暴地放缩至全局最坏方差，从而引入了无意义的高阶多项式因子。本文通过严格推导经验过程的高阶矩不等式并精细结合度量切片技术，为数据子采样理论树立了极高精度的分析标杆。
对无限维核学习的天然兼容：只要输入样本在特征空间中内积有界（例如标准的高斯核、Laplace 核、余弦相似度核或网络层归一化 LayerNorm），其平均范数 $B$ 和最大范数 $D$ 均严格为 1，此时本框架的采样界完全无需修改即可天然推广至无限维 RKHS 空间中。

局限与展望¶

相对误差在原点退化时的不可行边界：对于 $g(0) = 0$ 的非负单调损失函数（例如纯正半轴截断函数），由于原点处相对误差基准完全消失，乘性近似天然失效。未来的理论延伸可考虑混合加权误差度量（例如 $|f(x) - f_S(x)| \le \varepsilon f(x) + \tau$）以拯救此类临界退化问题。
非线性假设下的多分类与结构预测扩展：当前分析框架强依赖于一维内积 $\langle a, x \rangle$ 的纯标量映射与凸/单调性质，对于多分类 Softmax 交叉熵损失或图结构预测等复合向量值损失，高维度量熵的链式积分与收缩引理将面临更高的代数复杂度。
常数因子与高阶对数项的理论闭合：尽管线性界在 $k$ 的主阶数上达到最优，但理论界中仍残留有 $(\log k)^3 \log\log k$ 等多重对数因子，未来工作有望借助更前沿的泛函不等式或链式法则将多对数因子进一步压缩至单个对数项。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 彻底解决了正则化分类维度无关采样的基本复杂度界限，首次给出从线性、二次到不可行性的完整理论分类。
实验充分度: ⭐⭐⭐⭐⭐ 理论证明极其严谨扎实，正反双向闭环，涵盖高阶矩推导、度量熵积分、反集中对抗构造与几何多胞形分析。
写作质量: ⭐⭐⭐⭐⭐ 符号系统极其清晰统一，技术直觉阐释透彻，主干脉络与附录推导组织高度严谨。
价值: ⭐⭐⭐⭐⭐ 为核心子集理论、经验过程分析以及高维/核化机器学习提供了里程碑式的基石理论贡献。

正则化项 \(\mathcal{R}(\cdot)\)	损失函数类别	本文上界 \(m_0\)	本文匹配下界	先前 SOTA (ICML'24)	渐近紧致性判定
岭正则 \(\\|x\\|_2^2/k\)	Logistic 损失	\(O(\widetilde{k} \varepsilon^{-2})\)	\(\Omega(k (\log k)^{-1} \varepsilon^{-2})\)	\(\tilde{O}(k^3 \varepsilon^{-2})\)	近乎紧致（仅差对数因子）
岭正则 \(\\|x\\|_2^2/k\)	Sigmoid 损失	\(O(\widetilde{k} \varepsilon^{-2})\)	\(\Omega(k (\log k)^{-3} \varepsilon^{-2})\)	\(\tilde{O}(k^3 \varepsilon^{-2})\)	近乎紧致（仅差对数因子）
岭正则 \(\\|x\\|_2^2/k\)	Hinge (SVM) 损失	\(\Theta(k^2 \varepsilon^{-2})\)	\(\Omega(k^2 \varepsilon^{-2})\)	\(\tilde{O}(k^3 \varepsilon^{-2})\)	严格紧致 \(\Theta(k^2/\varepsilon^2)\)
岭正则 \(\\|x\\|_2^2/k\)	ReLU 损失	\(\infty\) (无维度无关界)	\(\Omega(n \log n)\)	\(\tilde{O}(k^3 \varepsilon^{-2})\)* (需人工下界)	证明维度无关完全不可行
Lasso 正则 \(\\|x\\|_1/k\)	Logistic / Sigmoid	\(O(\widetilde{k} \varepsilon^{-2})\)	\(\Omega(k (\log k)^{\pm 1} \varepsilon^{-2})\)	\(\tilde{O}(k^3 \varepsilon^{-2})\)	近乎紧致（仅差对数因子）
Lasso 正则 \(\\|x\\|_1/k\)	Hinge / ReLU	\(O(\widetilde{k} \varepsilon^{-2})\)	\(\Omega(k \log k \varepsilon^{-2})\)	\(\tilde{O}(k^3 \varepsilon^{-2})\)	近乎紧致（仅差对数因子）
二范数正则 \(\\|x\\|_2/k\)	任意 Lipschitz 损失	\(\Theta(k^2 \varepsilon^{-2})\)	\(\Omega(k^2 \varepsilon^{-2})\)	\(\tilde{O}(k^3 \varepsilon^{-2})\)	严格紧致 \(\Theta(k^2/\varepsilon^2)\)