A Randomized Algorithm to Solve Reduced Rank Operator Regression¶
作者: Giacomo Turri, Vladimir Kostic, Pietro Novelli, Massimiliano Pontil
来源: SIAM Journal on Mathematics of Data Science
主题: 统计计算 / 算法
相关性: 6/10
机构绿灯: University College London(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本文所处的子方向是大规模/无限维空间中的低秩算子回归(reduced rank operator regression)。其根本问题可以概括为:给定输入空间 \(\mathcal{X}\) 与输出空间 \(\mathcal{Y}\)(可能都是无限维的 RKHS),如何从有限样本中高效地估计一个低秩的线性算子 \(A: \mathcal{H} \to \mathcal{G}\),使得期望风险(1.1)最小。这个问题的难度在于:当特征空间维数极高甚至无限时,传统的求解方法(如直接求解广义特征值问题)计算代价过高,而随机化线性代数(randomized linear algebra)提供了一条"以少量精度换取大幅加速"的路径。该方向当前处于方法成熟但理论-计算接口仍在发展的阶段:低秩回归的统计理论(学习界、minimax 率)已经比较完善,但如何将随机化算法无缝嵌入并保持统计最优性,是近年来的活跃议题。
发展脉络(history)¶
- 奠基工作:有限维低秩回归。Izenman (1975) [14] 提出了经典的 reduced rank regression(RRR),将多元线性回归中的系数矩阵约束为低秩,通过奇异值分解求解。这是整个方向的起点,其核心思想——"先求全秩解,再截断到低秩"——至今仍是标准做法。
- 正则化与核化:向无限维扩展。Mukherjee & Zhu (2011) [23] 提出了 reduced rank ridge regression,将岭正则化与低秩约束结合,并首次将其推广到 RKHS 设定。这一步的关键贡献在于:通过核技巧,将原本只适用于有限维矩阵的方法推广到了无限维特征空间,使得非线性低秩回归成为可能。但该方法的计算瓶颈在于需要求解大规模(且可能非对称的)广义特征值问题。
- 算子回归的统计框架。Kostić et al. (2022) [16] 将 RRR 进一步推广到 Koopman 算子回归的语境,建立了"风险最小化 → 算子谱分解估计"的完整统计框架,并给出了 i.i.d. 与非 i.i.d. 两种设定下的学习界。这篇工作的重要性在于:它把低秩算子回归从一个纯优化问题提升为一个有统计保证的估计问题,并明确了"秩约束 + 正则化"的双重作用。
- 随机化线性代数的理论成熟。Diouane et al. (2022) [11] 提供了随机化低秩近似的通用误差分析框架(在谱范数与 Frobenius 范数下),这为本文的定理 4.2 提供了直接的理论工具。该工作将 Halko–Martinsson–Tropp 的经典结果推广到了更一般的设定,使得"随机投影 + 幂迭代"的误差可控性有了统一的刻画。
- 本文的位置:Turri et al. (2023) 站在上述两条线的交汇处——将随机化 SVD 技术(源自 [11])应用于算子回归问题(源自 [16]),并针对无限维设定设计了避免显式计算算子平方根的 primal/dual 两种算法。本文的贡献不是提出新的统计模型,而是在保持统计目标不变的前提下,将计算复杂度从"求解大规模 GEP"降为"求解小规模 GEP + 矩阵乘法",并给出期望意义下的风险界。
子线索聚类¶
被引文献大致落在三条子线索上:
- 低秩回归的统计理论([14], [23], [16], [5]):这一簇关注"给定秩约束与正则化,估计量的统计性质如何"。核心问题是学习界的推导、秩的选择、以及输出空间结构(如输出正则性假设)对收敛速率的影响。Brogat-Motte et al. (2022) [5] 特别关注输出空间的"正则性假设"如何影响低秩方法的优势。
- 随机化低秩近似的算法与误差分析([11], [33], [20]):这一簇关注"如何用随机投影快速计算低秩分解,且误差可控"。核心工具是 Gaussian sketching、幂迭代(power iteration)、以及子空间投影的误差界。Martinsson & Tropp (2020) [20] 是该领域的综述性奠基文献。
- 算子回归的应用驱动([16], [32], [9], [21]):这一簇关注"哪些实际问题可以转化为算子回归"。包括 Koopman 算子学习([16])、条件均值嵌入([32])、结构化预测([9])、一般线性算子回归([21])。这些应用共同的特点是:输入/输出空间维数极高,且目标算子天然低秩。
这个方向在追问的核心问题¶
- 统计-计算权衡的定量刻画:随机化引入的近似误差,与统计估计误差(由有限样本引起)之间如何权衡?是否存在一个"最优随机化程度"使得总误差最小?本文给出了期望风险界的初步回答,但高概率界(而非期望界)尚未给出。
- 无限维设定的算法可行性:当特征空间无限维时,哪些操作是可行的(如矩阵-向量乘法),哪些是不可行的(如显式构造协方差算子)?本文通过 primal/dual 两种算法分别处理了"特征维数 ≤ n"与"n < 特征维数"两种情形,但中间情形(特征维数略大于 n)的算法设计仍是开放的。
- 秩的选择与自适应:本文假设秩 r 是给定的超参数。如何从数据中自适应地选择 r(例如通过交叉验证或信息准则),并与随机化过程交互,是一个未解决的问题。
- 非平方损失与非线性算子:本文仅处理平方损失下的线性算子回归。对于非平方损失(如分类、分位数回归)或非线性算子(如神经算子),随机化技术的适用性尚不清楚。
⚠️ 作者的 framing(这是作者的说法)¶
作者在引言中将缺口 frame 为:"经典 RRR 的求解需要解决大规模(且可能非对称的)广义特征值问题,计算代价过高;我们提出随机化版本,在期望意义下可以任意接近最优风险。" 也就是说,作者把问题定义为计算瓶颈,而非统计瓶颈。被淡化的竞争路线包括:(a) 基于 Nyström 近似的核方法(作者仅在结论中提及作为未来方向);(b) 基于随机特征(random features)的近似——作者完全未提及;(c) 分布式/流式计算方法——未提及。值得研究者去查的问题:为什么作者选择 Gaussian sketching 而非其他随机化方案(如 SRFT、稀疏投影)?这些方案在算子回归设定下的误差界是否已有研究?另外,作者引用了 [11] 的定理但未讨论其与 Halko–Martinsson–Tropp 经典结果的差异在何处——这可能是理解本文理论贡献边界的关键。
张力¶
未见明显对立引用。但有一个微妙的张力值得注意:Kostić et al. (2022) [16] 强调 RRR 在 Koopman 算子学习中的统计优势(通过秩约束降低方差),而本文的随机化版本在计算上更快,但引入了额外的近似误差。这两者之间的权衡——即"随机化节省的计算时间是否值得牺牲的统计精度"——在文中没有直接讨论,而是通过数值实验间接展示。这是一个值得研究者深挖的潜在张力点。
二、最核心、最简单的例子 / 数学问题¶
第一步:把符号、模型、可观测数据交代清楚¶
符号(逐个点名):
- \(\mathcal{H}, \mathcal{G}\):输入与输出的 RKHS,可能无限维。这是函数空间,不是数据空间。
- \(\phi: \mathcal{X} \to \mathcal{H}\)、\(\psi: \mathcal{Y} \to \mathcal{G}\):特征映射。将原始数据映射到 RKHS。
- \(A: \mathcal{H} \to \mathcal{G}\):目标算子,要估计的未知量。假设 \(A\) 是 Hilbert–Schmidt 算子且秩 ≤ r。
- \(\rho\):\(\mathcal{X} \times \mathcal{Y}\) 上的未知联合分布。不可观测,只能通过样本近似。
- \(D_n = \{(x_i, y_i)\}_{i=1}^n\):可观测样本,i.i.d. 来自 \(\rho\)。
- \(S: \mathcal{H} \to \mathbb{R}^n\)、\(Z: \mathcal{G} \to \mathbb{R}^n\):采样算子(sampling operators)。\(S h = \frac{1}{\sqrt{n}}[\langle h, \phi(x_i)\rangle]_{i \in [n]}\),将函数映射为它在样本点上的取值向量。
- \(C := S^*S\):输入协方差算子(\(\mathcal{H}\) 上的算子)。
- \(D := Z^*Z\):输出协方差算子(\(\mathcal{G}\) 上的算子)。
- \(T := S^*Z: \mathcal{G} \to \mathcal{H}\):交叉协方差算子。
- \(K := SS^*\)、\(L := ZZ^*\):\(n \times n\) 核矩阵(Gram 矩阵)。
- \(C_\gamma := C + \gamma I\):Tikhonov 正则化的输入协方差。
- \(r\):目标秩(超参数,给定)。
- \(s\):过采样参数(超参数,给定)。
- \(p\):幂迭代次数(超参数,给定)。
- \(\Omega\):随机 sketching 矩阵(Gaussian)。
- \(A_{r,\gamma}\):精确的秩约束正则化经验风险最小化解(公式 1.2 的解),基准对象。
- \(A^{s,p}_{r,\gamma}\):随机化算法输出的估计量,本文的主角。
- \(R_\gamma(A)\):正则化经验风险(公式 2.1 定义的泛函)。
- \([\cdot]_r\):秩 r 截断 SVD 算子。
- \(\pi(\cdot)\):正交投影算子。
模型(数据生成机制):
- 存在未知分布 \(\rho\),样本 \((x_i, y_i) \overset{\text{i.i.d.}}{\sim} \rho\)。
- 特征映射 \(\phi, \psi\) 是已知的(由研究者选择,如线性、多项式、RBF 核)。
- 目标:最小化期望风险 \(\mathcal{E}(A) = \mathbb{E}_{(x,y)\sim\rho}\|\psi(y) - A\phi(x)\|^2_{\mathcal{G}}\)。
- 由于 \(\rho\) 未知,用经验风险 \(\hat{\mathcal{E}}(A) = \frac{1}{n}\sum_{i=1}^n \|\psi(y_i) - A\phi(x_i)\|^2\) 代替。
- 加上两个约束:秩(A) ≤ r(低秩假设)和 \(\|A\|^2_{HS}\) 正则化(Tikhonov)。
可观测数据:只有 \(D_n = \{(x_i, y_i)\}_{i=1}^n\)。不可观测:\(\rho\)、期望风险 \(\mathcal{E}(A)\)、真算子 \(A^*\)(如果存在)。
关键点:本文处理的是固定设计(fixed design)问题——即忽略样本随机性,只关注"给定这 n 个点,如何高效求解优化问题 (1.2)"。统计学习率(样本外误差)不是本文的主题(见结论部分"open question")。
第二步:讲最小内核¶
最小内核:把问题剥到只剩"如何用随机化方法近似一个矩阵的截断 SVD,且误差可控"。
最简特例:设 \(\mathcal{H} = \mathbb{R}^d\),\(\mathcal{G} = \mathbb{R}^d\),\(\phi = \psi = \text{identity}\)。则问题 (1.2) 退化为经典的有限维 reduced rank ridge regression:
其中 \(X \in \mathbb{R}^{d \times n}\),\(Y \in \mathbb{R}^{d \times n}\) 是数据矩阵。
精确解(已知结果):\(A_{r,\gamma} = [Y X^\top (X X^\top + \gamma I)^{-1}]_r\),即先计算岭估计 \(\hat{A} = Y X^\top (X X^\top + \gamma I)^{-1}\),再取其秩 r 截断 SVD。
计算瓶颈:当 \(d\) 很大(如 \(d = 10^5\))时,直接计算 \(\hat{A}\) 的 SVD 需要 \(O(d^3)\) 时间,不可行。
本文的核心思想(在最小特例下):
- 不用直接算 \(\hat{A}\) 的 SVD,而是先用一个随机矩阵 \(\Omega \in \mathbb{R}^{d \times (r+s)}\) 去"探测" \(\hat{A}\) 的值域。
- 构造 \(M = (\hat{A}\hat{A}^\top)^p \hat{A} \Omega\)(幂迭代,\(p\) 次),使得 \(M\) 的值域逼近 \(\hat{A}\) 的前 \(r\) 个奇异向量张成的子空间。
- 对 \(M\) 做 QR 分解得到正交基 \(Q\),然后计算小矩阵 \(Q^\top \hat{A}\) 的 SVD(尺寸 \((r+s) \times d\),远小于 \(d \times d\))。
- 最后恢复 \(\hat{A}\) 的近似截断 SVD。
为什么成立:Gaussian sketching 的核心性质是——随机矩阵 \(\Omega\) 的列向量在 \(\hat{A}\) 的奇异向量方向上的投影,以高概率"均匀覆盖"前 \(r\) 个奇异方向。幂迭代进一步压制了非前 \(r\) 个奇异值方向的贡献(衰减因子 \((\sigma_{r+1}/\sigma_r)^{2p}\))。因此,\(M\) 的值域以高概率逼近 \(\hat{A}\) 的前 \(r\) 个左奇异向量张成的子空间。
在最小特例下,本文要证明的命题退化为:
对任意 \(\epsilon > 0\),存在 \(s = O(r)\) 和 \(p = O(\log(1/\epsilon))\),使得
\[\mathbb{E}_\Omega [R_\gamma(A^{s,p}_{r,\gamma})] - R_\gamma(A_{r,\gamma}) \le \epsilon \cdot \sigma_1^2\]其中 \(\sigma_1\) 是 \(\hat{A}\) 的最大奇异值。
证明怎么走(在最小特例下):
- 第一步(确定性不等式):利用命题 4.1,将风险差转化为投影误差 \(\|(I - \pi(M))[\hat{A}]_r\|^2_F\)。这一步是纯代数的,不涉及随机性。
- 第二步(随机性分析):利用定理 4.2(来自 [11]),对 Gaussian sketching 矩阵 \(\Omega\) 的随机性取期望,得到投影误差的期望上界。关键工具是子空间嵌入(subspace embedding)性质:Gaussian 矩阵以高概率保持低维子空间的范数。
- 第三步(合并):将两步合并,得到期望风险差的显式上界(定理 4.3 和 4.5)。
为什么难:难点在于无限维。当 \(\mathcal{H}\) 无限维时,\(\hat{A}\) 是无限维算子,不能直接写成矩阵。本文的处理技巧是:通过采样算子 \(S, Z\) 将问题转化为有限维核矩阵问题(primal 情形),或通过引入辅助随机矩阵 \(\Omega\) 将问题限制在有限维子空间(dual 情形)。关键观察:虽然 \(\hat{A}\) 是无限维的,但它的值域落在由 \(\{\phi(x_i)\}\) 张成的 n 维子空间内(因为 \(\hat{A}\) 是经验风险的解)。因此,所有操作都可以在 n 维空间中完成。
一句话总结最小内核:本文做的事情是——用 Gaussian 随机投影构造一个低维子空间,使得目标算子在该子空间上的投影以高概率逼近其最优秩 r 近似,从而将大规模 GEP 求解转化为小规模 SVD 计算,并给出期望意义下的误差界。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:如何高效求解无限维空间中的秩约束正则化经验风险最小化问题(公式 1.2),即 reduced rank operator regression 的随机化版本。
- 核心工具/方法:将随机化 SVD(Gaussian sketching + 幂迭代)嵌入算子回归的求解流程,设计了 primal(适用于特征维数 ≤ n)和 dual(适用于 n < 特征维数)两种算法,避免了直接求解大规模广义特征值问题。
- 主要结论:在期望意义下,随机化估计量 \(A^{s,p}_{r,\gamma}\) 的正则化经验风险可以任意接近最优值 \(R_\gamma(A_{r,\gamma})\),且误差随过采样参数 \(s\) 和幂迭代次数 \(p\) 的增加而指数衰减(定理 4.3 和 4.5)。
关键设定与假设¶
- 设定:固定设计(fixed design),即忽略样本随机性,只关注优化问题的求解。数据 \(D_n\) 给定,目标是高效计算 (1.2) 的解。
- 假设:
- \(\mathcal{H}, \mathcal{G}\) 是 RKHS,可能无限维。
- 目标算子 \(A\) 的秩 ≤ r(低秩假设)。
- 正则化参数 \(\gamma > 0\),秩 r 给定。
- 随机 sketching 矩阵 \(\Omega\) 的列服从标准 Gaussian 分布(各向同性)。
- 核矩阵 \(K\) 和 \(L\) 可计算(即核函数可求值)。
- 相比已有工作的变化:
- 相比 [14](有限维 RRR):本文处理无限维 RKHS。
- 相比 [23](核化 RRR):本文引入随机化,避免求解大规模 GEP。
- 相比 [16](Koopman 算子回归):本文关注计算效率而非统计学习率,且不要求算子具有特殊谱结构。
主要结果¶
定理 4.3(primal 情形):设 \(r \le \text{rank}(T)\),\(s \ge 2\),\(p \ge 1\)。则对 primal R4 算法输出的 \(A^{s,p}_{r,\gamma}\),有
定理 4.5(dual 情形):在 \(n < \dim(\mathcal{H})\) 的设定下,对 dual R4 算法输出的 \(A^{s,p}_{r,\gamma}\),有类似的期望风险界(公式 4.10),其中 \(a_r\) 和 \(b_r\) 由公式 (4.11) 和 (4.12) 给出。
关键观察: - 当 \(p \to \infty\) 时,\((\sigma_{r+1}/\sigma_r)^{4p} \to 0\),因此 \(a_r, b_r \to 0\)。这意味着增加幂迭代次数可以使风险差任意小。 - 当 \(s \to \infty\) 时,\(1/(s-1) \to 0\),同样使风险差趋于零。这意味着增加过采样参数也可以使风险差任意小。 - 风险差以线性速率(在 \(s\) 中)和指数速率(在 \(p\) 中)衰减。
证明路线:
- 命题 4.1(确定性约简):将风险差 \(\mathbb{E}[R_\gamma(A^{s,p}_{r,\gamma})] - R_\gamma(A_{r,\gamma})\) 上界为 \(\mathbb{E}\|(I - \pi(M))[B]_r\|^2_F\)。这一步的关键是公式 (2.1) 的风险分解,以及 \(A_{r,\gamma}\) 的最优性。
- 引理 3.1(算子-矩阵对应):证明算子层面的随机化 SVD 可以等价地转化为矩阵层面的随机化 SVD。具体地,\(B = C_\gamma^{-1/2}T\) 的奇异值分解与 \(B = K^{1/2}K_\gamma^{-1}L^{1/2}\) 的奇异值分解一一对应。
- 定理 4.2(引用 [11] 的矩阵随机化误差界):对 Gaussian sketching 矩阵 \(M\),给出 \(\mathbb{E}\|(I - \pi(M))[B]_r\|^2_F\) 的上界。这是整个证明的核心技术工具。
- 定理 4.3 和 4.5(合并):将上述步骤合并,代入 \(a_r\) 和 \(b_r\) 的表达式,得到最终的风险界。
技术技巧点名:
- Gaussian sketching:用随机 Gaussian 矩阵 \(\Omega\) 探测算子的值域,是随机化线性代数的标准技巧。作用:将高维问题投影到低维子空间。
- 幂迭代(power iteration):通过 \((BB^\top)^p\) 放大前 \(r\) 个奇异值方向的信号,压制其余方向。作用:提高子空间估计的精度。
- 子空间嵌入(subspace embedding):Gaussian 矩阵以高概率保持低维子空间的范数,这是定理 4.2 的数学基础。
- 算子-矩阵对应(引理 3.1):通过采样算子 \(S, Z\) 将无限维算子问题转化为有限维矩阵问题。作用:使随机化 SVD 的矩阵理论可以直接应用。
- QR 分解(经济型):用于正交化 sketching 后的基,保证数值稳定性。
真实例子与应用¶
例子 1:合成线性回归(第 5.1 节) - 数据:\(Y = AX + \xi\),\(A \in \mathbb{R}^{100 \times 100}\) 为低秩矩阵(秩 10),\(X \sim N(0, I)\),\(\xi \sim N(0, 0.1)\)。 - 方法:比较 R3(精确 GEP 求解)与 R4(随机化)的风险与运行时间。 - 结果:R4 的风险与 R3 几乎相同(差距 < 1%),但运行时间快约 8.6 倍(图 2 右)。风险差随 \(s\) 和 \(p\) 的增加而减小,验证了定理 4.3 和 4.5 的预测。
例子 2:大规模神经科学数据集(NSD)(第 5.2 节) - 数据:Natural Scenes Dataset,包含 8 名受试者的 fMRI 记录,每名受试者约 10000 个图像刺激。输入特征为图像嵌入(如 AlexNet 或 DINOv2 特征),输出为 fMRI 体素活动(约 20000 维)。 - 方法:使用 R4 学习从图像特征到 fMRI 活动的低秩映射,并与 R3 及基线(PCA + 线性回归)比较。 - 结果:R4 在预测精度(相关系数)上与 R3 几乎一致,但训练时间显著降低(图 3)。使用 DINOv2 特征时,R4 的预测性能优于 AlexNet 特征,说明特征质量对结果影响更大。
例子 3:Koopman 算子回归(第 5.3 节) - 数据:带噪声的逻辑斯蒂映射 \(x_{t+1} = (4x_t(1-x_t) + \xi_t) \mod 1\)。 - 方法:用 R4 学习 Koopman 算子的低秩近似,估计其特征值。 - 结果:R4 估计的特征值与 R3 几乎重合(图 4 右),且与真实特征值 \(\{1, -0.193 \pm 0.191i\}\) 一致。说明随机化方法在动力系统应用中也有效。
这些例子想说明什么: - 合成实验验证了理论界的紧性(风险差随 \(s, p\) 衰减)。 - NSD 实验展示了 R4 在大规模真实数据上的实用性(精度几乎无损,速度大幅提升)。 - Koopman 实验展示了 R4 在非线性动力系统中的应用潜力,说明低秩算子回归不仅是一个抽象的数学问题。
🔎 结论是否比证明窄¶
是的,存在几处"证明窄、声称宽"的地方:
-
期望界 vs 高概率界:定理 4.3 和 4.5 给出的是期望意义下的风险界(\(\mathbb{E}[R_\gamma]\)),但摘要和引言中使用了"arbitrarily close"(任意接近)这样的表述,暗示了更强的结论。实际上,从期望界并不能直接推出高概率界(需要额外的集中不等式)。具体语句:摘要中 "the resulting regularized empirical risk is, in expectation w.r.t. randomness of a sketch, arbitrarily close to the optimal value"——这里明确说了 "in expectation",所以摘要没有过度声称;但引言中 "efficient and accurate" 的表述略显宽泛。
-
固定设计 vs 随机设计:全文只处理固定设计(忽略样本随机性),但引言中 "we aim to find low rank solutions to the problem (1.1)" 中的期望风险 \(\mathbb{E}_{(x,y)\sim\rho}\) 暗示了随机设计。作者在结论中承认 "An important open question for future research is how to combine the results of this work with statistical learning rates",说明统计学习率确实不在本文范围内。但:引言第 1 段将 (1.1) 定义为期望风险最小化,而全文只分析了经验风险(固定设计),这两者之间的 gap 没有被明确讨论。
-
Gaussian 假设的普适性:定理 4.2 要求 sketching 矩阵 \(\Omega\) 是 Gaussian 的。作者在推论 4.4 中给出了两种构造 Gaussian sketching 的方式(通过 \(T\Omega\) 或 \(R\Lambda^{1/2}\Omega\)),但没有讨论其他分布(如 Rademacher、稀疏 sketching)是否也适用。这是一个明确的限制,但作者没有在结论中提及。
-
秩 r 的选择:全文假设 r 是给定的。但实际应用中 r 通常未知。作者没有讨论如何选择 r,也没有给出自适应算法。这是一个明显的"声称宽于证明"的地方——摘要中 "low-rank" 的表述暗示了秩的选择是问题的一部分,但全文没有涉及。
四、开放问题¶
-
高概率界:定理 4.3 和 4.5 只给出期望界。能否推导出高概率界(即 \(\mathbb{P}(R_\gamma(A^{s,p}_{r,\gamma}) - R_\gamma(A_{r,\gamma}) > \epsilon) \le \delta\))?这需要更精细的集中不等式分析,扎根于定理 4.3 的证明(第 4 节)。
-
统计-计算权衡的完整刻画:本文只分析了计算误差(随机化引入的近似误差)。将统计误差(有限样本引起的估计误差)纳入统一框架,推导"总误差 = 统计误差 + 计算误差"的联合界,是自然的下一步。扎根于结论段 "An important open question for future research is how to combine the results of this work with statistical learning rates"。
-
自适应秩选择:如何从数据中自动选择秩 r?是否可以结合随机化过程(例如在 sketching 后通过奇异值阈值选择 r)?扎根于第 1 节 "we assume that r is given" 的隐含设定。
-
非 Gaussian sketching:定理 4.2 依赖 Gaussian 假设。能否推广到其他分布(如 Rademacher、稀疏 sketching)?这需要重新推导误差界,扎根于定理 4.2 的引用 [11]。
-
与 Nyström 方法的结合:作者在结论中提及 "combining our results with different strategies, such as Nyström subsampling or random features"。这是一个明确的未来方向,但具体如何结合(例如在 sketching 阶段使用 Nyström 近似)尚不清楚。
-
非平方损失:本文仅处理平方损失。对于非平方损失(如 logistic 损失、分位数损失),随机化技术的适用性需要重新分析。扎根于第 1 节 "beyond the square loss" 的表述。
提醒:要确认上述开放问题是否是真 gap,建议去读以下近期论文的引言部分(各约 5 篇):(a) 随机化低秩近似的统计学习理论(如 "Randomized low-rank approximation for kernel methods" 系列);(b) Koopman 算子回归的近期工作(如 [16] 的后续引用);(c) 无限维设定下的随机化算法(如 "Randomized algorithms for operator regression")。如果这些论文的引言都指向同一个未解决问题,那大概率是真 gap;如果各说各话,则需要谨慎。
Maintained by 陈星宇 · Homepage · Source on GitHub