CaCuSESOP 补上 CaCuTe 留下的缺口
CaCuTe 把三次 Taylor 模型分成两个区域。当二次 Hessian 项较小时，缩放梯度步会降低三次模型，并在该区域成立期间给出 O(k^-2) 速率，一个 Hessian 向量积（HVP）即可检验曲率条件。当二次项占主导时，该证书失效，方法退回标准梯度下降式下降，其一般凸保证只有 O(k^-1)。
论文从第二个区域出发。此时模型接近二次，但仅靠梯度缩放无法有效利用其曲率。问题在于如何用固定数量的 HVP 最小化该模型，而不形成或分解 Hessian。答案是：在一个小的 SESOP 空间内构造三次模型，并最小化该模型而非原目标。收敛性理论只需三个 HVP，因此内层求解不再需要额外的目标预言调用。
由此得到的方法 CaCuSESOP 在固定 HVP 预算下结合了两个区域，并通过重启实现自动局部加速。在实际配置中它使用五方向空间，而文中所述的三方向变体每个接受步最多使用三个 HVP。
用降维三次模型替代精确子空间最小化
经典 SESOP 不规定 HVP 预言：每次外层迭代反而需要在当前子空间上对原目标做精确最小化。在所述光滑凸假设下，这是一个一般低维光滑凸优化问题，没有任何有限统一预言预算能在整个类上返回精确极小点。因此仅凭速率并不能描述子空间方法的代价。
CaCuSESOP 用最小化一个只需解到可计算精度的低维三次上模型，替代对原目标的精确最小化。一旦降维模型系数形成，其精确求解不再需要更多目标预言调用。论文明确指出，这是关于预言代价的陈述，而非声称降维求解有固定算术运算次数。
算法先为缩放梯度步完成一次单 HVP 回溯搜索。若其投影模型残差过大，已算出的 HVP 就成为完整子空间模型的一个方向，其余列随之形成。只有残差检验失败才激活完整子空间回退。三次正则化参数由回溯选择，而非作为光滑性界提供。
全局速率在固定 HVP 预算下成立
CaCuSESOP 以每次迭代固定数量的 Hessian 向量积达到全局速率 O(k^-2)。讨论部分给出的全局速率为 sqrt(log K)/K^2 量级，每次迭代最多三个 HVP，而确定性重启以相同预言代价把全局速率改进为 O(K^-2)。
对比表把全局速率与方向曲率工作量、内问题复杂度分开。对于带受控重启的 CaCuSESOP，表中列出 O(k^-2)、一到五个 HVP、内问题复杂度 O(1)，以及对问题常数无参数依赖。经典 SESOP 列为 O(k^-2)，但精确内求解的最坏情况预算无界；CaCuAdGD 列为 O(k^-1)，一个 HVP。
表中还记录，四个展示的 Cubic SESOP 算法使用三个方向，且推论 4.7 表明可以把上一步作为可选第四实际方向保留，而不改变其理论速率。CaCuSESOP 在实际对比中使用五方向空间，并采用相同的受控重启调度。
局部加速无需提供问题常数
若极小点处 Hessian 正定，CaCuSESOP 自动达到复杂度为 O(sqrt(kappa*) log(1/epsilon)) 的加速局部线性速率。算法并不知道局部强凸参数、条件数 kappa* 或最优值。
论文给出了进入该区域的有限界以及适配重启调度的界。推论 4.6 把代价分成三部分：到达足够小的子水平集、适配轮次长度、以及随后把目标间隙降到所需精度。局部目标阈值为 epsilon_loc = mu*^3 / (2^27 H^2)，足够的接受步数为 O(1 + D_0 sqrt((3/2)(L_0 + sqrt(4 H L_0 D_0))) + (2048/3) H D_0 / epsilon_loc + sqrt(kappa*) [log(2 + kappa*) + log(epsilon_loc / epsilon)])，隐含常数是通用常数。
论文对这项局部结论的性质很谨慎。它是目标间隙的 R 速率，而非每一步都相同的收缩；迭代误差和梯度范数对应的根界指数只有一半。进入代价取决于初始点、Hessian 变化以及极小点处曲率。该界是精度保证，而不是涉及未知最优值的停止检验。
全局 O(k^-2) 指数在该预言类中最优
论文证明，对于所考虑的固定预算梯度/Hessian 向量积线性张成预言类，全局 O(k^-2) 速率是最优的，即使允许动量与无限制内存。讨论部分将其描述为对经典尖锐 CG/Krylov 界的改编，表明全局指数在所述预言类中是尖锐的。
这一尖锐性结论的范围限于论文定义的预言类，而非所有可能的二阶方法。它说明在固定梯度与 HVP 信息预算下，线性张成构造能达到什么，并且即使允许动量与无限制内存也成立。
对比表把它与那些需要不同资源才能获得更快外层速率的替代方法并列：full/exact 行需要 m = d 和稠密 O(d^3) 代数，表中明确拒绝把 m 与 k 合并成一个虚构速率。
W8A 实验在迭代与时间上偏向 CaCuSESOP
在 W8A 上 lambda = 10^-7 的正则化逻辑回归中，CaCuSESOP 在接受的外层迭代数和运行时间上都给出最快下降。图的两个面板使用相同目标、起点和参考值。
该结果背后的机制是单 HVP 梯度分支：只要残差证书通过就避免降维求解；否则五维三次回退只形成一次，并在整个回溯过程中复用。受控重启防止累积的 SESOP 方向失效。
基线按其作者推荐的配置运行，而非在 W8A 上调参。SESOP 使用当前梯度、一个上一步和两个 Nemirovski 方向，受限非线性目标用带 Armijo 回溯的牛顿法最小化，并采用作者 SESOP_PACK 的内层设置：最多七次牛顿迭代、投影梯度阈值 10^-10、初始线搜索步长 1、缩减因子 1/4、最多 40 次线搜索试验。Generic Type-I 使用非加速变体，内存 m = 25、正交前向估计、前向差分步长 h = 10^-9，以及所引附录中的初始正则化规则。2026 年 10 月 1 日检查时链接仓库没有实现，因此该基线是根据已发表算法重新实现的。
保证到哪里为止，以及它们不承诺什么
可选的第四内存方向被允许而不改变理论速率，但论文明确表示，这一陈述并不预测更好的迭代次数或运行时间。它只是允许该内存方向同时保持保证。
降维三次求解不必解到精确极小点。相对稳定性检验只使用已算出的系数，并保持基本、自适应和确定性轮次保证，推论 4.9 把加速重启控制器及其有限时间界扩展到同一准则。所需绝对精度随步长下降，因此固定的绝对求解器容差不能提供这一保证。
局部 PL 结果在没有非退化或唯一极小点的情况下给出线性收敛和有限轨迹长度，但对自适应系数，它假设接受的系数最终有正下界，而算法不需要知道该界。该定理中关于聚点的限定至关重要：目标收敛并不意味着进入任意指定极小点附近。
比较预言预算与内求解代价，而非只看速率
这篇论文中与决策相关的比较不是头条速率，而是速率与预言预算、内问题代价的配对。带受控重启的 CaCuSESOP 列为 O(k^-2)、一到五个 HVP、内问题复杂度 O(1)；经典 SESOP 只有在精确内求解最坏情况预算无界时才达到 O(k^-2)；CaCuAdGD 则是一个 HVP 下的 O(k^-1)。
内问题复杂度约定对读该表很重要。它是在降维问题系数形成之后度量的，排除目标预言调用、子空间基构造，以及把降维解提升回 R^d。按此约定，维度为 r 的稠密降维问题代价为 O(r^3)，因此三、四、五方向 Cubic SESOP 变体的 IPC 为 O(1)，m 维 Krylov 或 Scieur 子问题 IPC 为 O(m^3)，全空间问题 IPC 为 O(d^3)。被排除的基操作代价为形成或正交化稠密基 O(d r^2)，应用它为 O(d r)。
对于判断该方法是否适合某个问题的读者，论文自身的划分是：精度 epsilon 大于或等于 epsilon_loc 时，仅全局估计就足够；而加速局部区域需要推论 4.6 的有限进入与适配预算。实际五方向空间给回退额外两个方向，并施加更强的梯度试验检验，而单 HVP 梯度分支正是在其残差证书通过时避免降维求解的关键。
本文引用的文献
CaCuTe Meets SESOP: Better Theory and Practice with Lipschitz Hessians
CaCuSESOP 把 CaCuTe 与序列子空间优化结合，以每次迭代固定数量的 Hessian 向量积达到全局 O(k^-2) 速率，用只需解到可计算精度的低维三次上模型替代对原目标的精确最小化；当极小点处 Hessian 正定时，它自动达到 O(sqrt(kappa*) log(1/epsilon)) 的加速局部线性速率，而无需提供强凸参数、条件数或最优值。