精读笔记
Problem Setting
Online Sketched Newton-Raphson 处理的是在线根跟踪与由其诱导的在线优化：每轮环境变动后，只能用上一轮/当前观测做一次快速更新，希望累积误差相对每轮最优点是 sublinear。真正困难点在于，这类动态问题的最优点本身在移动；算法既要快速追踪 path variation，又不能在每轮花 full Newton 的计算成本。
已有二阶 OCO 的短板不是 regret 形式，而是部署代价：完整 Hessian 或 Jacobian Gram 矩阵的求逆在高维实时系统中不现实。相反，一阶方法便宜但对曲率利用弱，在 tracking 场景中常常需要更保守步长。本文抓住的关键矛盾是：二阶信息对动态 tracking 很有价值，但完整二阶信息太贵；能否只用随机子空间里的二阶信息，还保留同阶的 variation-dependent regret。
Motivation
作者的核心观察是，Sketched Newton-Raphson 在离线 root finding 中已经可以通过随机子空间伪逆获得收敛性，而 OCO 中 second-order 方法的主要瓶颈恰好是矩阵求逆。因此，缺的不是一个新的 regret 分解技巧，而是一个能把 sketched Newton 的 contraction 性质接到 online dynamic regret 分析上的桥。
已有路线的不足很明确：online Newton / interior-point 类方法理论好但每轮重；online gradient 类方法轻但曲率弱；已有 online sketching 二阶学习更多停留在经验层面，缺少动态 regret 保证。本文想填的缺口是：给 sketch 后的二阶更新一个可证明的 tracking contraction，然后把它扩展到 unconstrained OCO 和 time-varying equality-constrained OCO。
Core Idea
论文真正的核心不是“把 Hessian 随机采样一下”，而是把 sketched Newton-Raphson 步重新解释为某个随机 residual energy 的梯度步。具体地，定义 H_t^S(x)=S(S^T DF_t(x)^T DF_t(x)S)^†S^T，并令 f_t^{S,y}(x)=1/2 F_t(x)^T H_t^S(y)F_t(x)。这样 sketched NR 更新可以写成 x_{t+1}=x_t-∇f_t^{S_t,x_t}(x_t)。这个重写很关键，因为它让随机 Newton 步进入标准的 descent/contraction 证明模板。
本质区别在于：prior second-order OCO 使用完整曲率矩阵来做每轮局部校正；OSNR 只在随机低维子空间中使用曲率，并把“缺失的曲率信息”吸收到期望意义下的 contraction 假设中。它改变的是每轮信息流：不再构造完整二阶模型，而是采样一个子空间、在该子空间上解小规模伪逆问题、用该方向更新。scalability 来自降低求逆维度；理论可行性来自强 quasar-convex 下的期望收缩，而不是来自 sketch 本身天然无损。
Method
1. Sketched residual geometry：它解决的是 full inverse 太贵的问题。通过在 S_t 选出的子空间里形成 S^T DF^T DF S 的伪逆，每轮只求解 τ 维问题。核心变化是把二阶校正限制在随机子空间中，计算量从 full Newton 的高维求逆转成 O(mτ+nτ^2+τ^3) 量级。
2. OSNR 单步更新：它解决的是在线场景每轮只能快速响应的问题。算法每轮实施 x_t、观察 F_t(x_t)、采样 S_t、做一次 sketched NR 步。作者刻意只分析 one-step-per-round，而不是多次迭代；这保持 OCO 设定干净，但也意味着性能完全依赖单步 contraction。
3. 从 root finding 到 OCO：令 F_t=∇g_t，把根跟踪转成最优性条件跟踪。这个转换的必要性在于 OSNR 原生是 root solver，而 OCO 目标需要通过一阶最优性接入。核心变化是 regret 不直接由目标下降分析得到，而是先控制 x_t 到 x_t^* 的距离，再用 Lipschitz 性转成 loss regret。
4. Equality-constrained extension：对 Ax=b_t，先把当前点投影到新等式超平面，再在 nullspace(A) 中做 OSNR。它解决的是更新方向不能破坏等式结构的问题。核心变化是把 constraint tracking 和 objective tracking 解耦：可行性误差只来自 b_t 的时间滞后，优化误差则在 nullspace 中继承 OSNR contraction。
Key Insight / Why It Works
最关键的 insight 是：动态 regret 的难点可以被拆成“单步收缩 + 最优点路径变化”。只要每轮相对当前零点有期望线性收缩，即 E||x_{t+1}-x_t^*|| ≤ sqrt(1-μ) E||x_t-x_t^*||，那么跨时间的误差累积自然被 V_T 控制。这是整个证明的主干；sketching 只是改变了如何获得这个 contraction。
方法有效的根源不是 sketch 提供了更好的统计泛化，而是它在计算上便宜地保留了足够的二阶校正，并且理论假设直接保证 sketch 后的随机能量仍有强几何结构。换句话说，核心贡献是把 sketched NR 的 expected contraction 变成 online tracking regret；不是发明了新的 OCO regret 技巧，也不是证明一般 sketch 都能无损替代 Newton。
最可能只是辅助/engineering 的部分是 uniform subsampling sketch 本身。文中没有深入比较不同 sketch distribution，也没有给出 sketch size 与 μ 的明确关系，因此“低采样率仍好用”的部分更像 empirical scaling observation。计算加速是真实的，但理论上同阶 regret 的背后隐藏了常数问题：如果 μ 随 τ 下降很快，bound 的常数可能变差，文中未充分说明。
等式约束部分的 insight 很实用：用上一轮可行点加上 b_t-b_{t-1} 的投影修正，使违反量精确等于参数变化 V_b。这不是复杂的新约束优化理论，而是一个干净的状态重置技巧。它适用于固定线性等式，但并不自动推广到不等式或非线性约束。
Relation To Prior Work
这篇工作处在三条线的交叉处：second-order OCO、sketched/randomized Newton-Raphson、time-varying constrained OCO。与 Lesage-Landry/Taylor/Shames 一类 online Newton 方法相比，它的 regret 形式并没有本质突破，主要新增是把 full Newton step 换成 sketched NR step，并证明 expected contraction 足够维持 O(V_T+1)。
与 Pilanci-Wainwright Newton Sketch 或 Yuan-Lazaric-Gower Sketched NR 相比，本文的新意不是 sketching 技术本身，而是在线化：每轮只做一次随机子空间二阶更新，并把离线收敛型结论转译成动态 regret。与 Luo et al. 的 online sketching 二阶学习相比，本文更强调 formal regret analysis。
看似新的地方中，root finding → OCO via F=∇g 是经典转换；nullspace parameterization 处理线性等式也是标准凸优化手段。实质创新在于把这些已有部件组织成一个统一 OSNR/OSNR-EC 框架，并给出与二阶 OCO 同阶的 expected dynamic regret，同时降低求逆维度。
Dataset / Evaluation
实验覆盖两个场景：一个高维非线性 least-squares target tracking，一个 IEEE 300-bus 上的线性化 OPF 变体。覆盖面偏工程数值优化，符合作者 claim 的应用语境，但并不构成广泛 OCO benchmark。
实验基本验证了两个核心经验 claim：低 sketch percentage 下 OSNR/OSNR-EC 仍能保持较好 empirical regret；更新时间随 sketch size 下降，接近一阶方法量级。它也展示了 100% sketch 退化为 full online Newton，可作为 sanity check。
但 evaluation 的限制明显。第一，实验没有系统检验 Assumption 2 是否成立，也没有分析 μ 与 sketch size 的关系。第二，OPF 原问题含 inequality constraints，论文通过指数 penalty 替代线路约束与限额约束，实际验证的是一个 equality-constrained surrogate，而不是完整 OPF。第三，比较基线较有限；target tracking 与 OGD 比较有意义，但 constrained case 基本只和 full sketch/Newton 自身比较。总体上，实验支持 computational scaling 和数值可用性，不足以证明一般在线优化场景的鲁棒优势。
Limitation
最核心的限制是强 quasar-convex 假设。它直接承担了全局收缩的责任，因此理论适用面比标题中的一般 OCO 要窄。对于 F_t=∇g_t 的情形，要求诱导出的 sketched residual objective 满足该条件，这比 g_t 凸、强凸或 smooth 更不直观；文中没有提供可操作的验证准则。
第二，sketch 的理论收益与实际收益之间有断层。复杂度随 τ 降低是明确的，但 regret bound 中的 μ 没有显式依赖 τ；如果小 sketch 导致收缩常数恶化，理论上可能只是把计算复杂度转移到了更差的常数上。文中未充分说明这一点。
第三，结果主要是期望意义，不是高概率或 pathwise guarantee。对控制/电网这类实时系统，随机失败方向和瞬时 constraint violation 可能比期望 regret 更关键。
第四，约束处理能力有限。OSNR-EC 依赖固定 A、线性等式、可求 A A^T 逆和 nullspace basis。不等式约束被明确留作未来工作；OPF 实验通过 penalty 绕开，说明当前框架还没有真正解决工程优化中最难的 active-set/feasibility 问题。
第五，所谓“preserve tight regret bounds”要谨慎理解：阶数保留，但常数和条件可能更强。这里的增益主要来自 numerical linear algebra scaling，而不是更强的在线学习机制。
Takeaway
- 1. 最值得记住的是 proof pattern：如果能把一个随机近似二阶步写成某个随机能量的梯度步，并证明 expected contraction，那么 dynamic regret 可以直接由 contraction + path variation 得到。
- 2. Sketching 在在线优化中的价值更像 test-time compute allocation：每轮用少量随机二阶信息换取接近 full Newton 的 tracking 行为。
- 未来更重要的问题不是“能不能 sketch”，而是如何自适应选择 sketch size/distribution 来控制 contraction 常数。
- 3. Equality-constrained 部分的可迁移 insight 是：把时变约束的可行性维护和目标下降分离，先做最小投影修正，再在 tangent/nullspace 中优化。
一句话总结
Online Sketched Newton-Raphson 是一篇把 sketched Newton-Raphson 的随机子空间二阶校正接入 dynamic OCO regret 分析的工作，核心贡献是用计算降维保留二阶 tracking bound，属于 second-order online optimization 的 scalable engineering-theory bridge。