精读笔记

Problem Setting

论文标题：Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles（arXiv preprint / 2026-07-21）。

这篇论文不是在提出一个更快的 optimizer，而是在解决 online-to-nonconvex conversion 的接口问题：普通 static regret 是否足以推出随机非凸优化的 stationarity guarantee。关键矛盾是：非凸优化的“好方向”随 x_t 变化，但 static regret 只能和一个固定决策比较。已有方法如果让在线学习器直接选 update direction，就很难避免 dynamic / shifting / discounted regret，因为 comparator 本质上也是动态的。

作者的处理方式是重新定义 OCO oracle 的作用域：它不再选择点或方向，而是选择 preconditioner。这样 identity matrix 成为自然固定 comparator，非凸侧仍由梯度 tracker 提供下降信号。问题从“在线学习器能否追踪非凸最优方向”变成“在线学习器能否比固定 identity preconditioner 更好地调几何”。这个重写是整篇论文真正解决的东西。

Motivation

已有 online-to-nonconvex 路线的问题不是不能得到 rate，而是需要更强、更特殊的 online guarantee：dynamic regret、adaptive regret、shifting regret、discounted regret、optimistic hints、model averaging 或特定 Adam-type 结构。这些东西在理论上有用，但不是普通 OCO black-box static regret；因此 Chen-Hazan 的 open problem 没被真正解决。

作者抓住的缺口是 comparator 的静态化。如果 OCO 直接输出更新方向，identity 这样的固定 comparator 没有意义；但如果 OCO 只输出一个作用在 predictable gradient 上的矩阵，那么 I_d 就是“退化为普通 tracker-SGD”的固定基线。这个观察把 reduction 的难点从“让 static regret 追踪变化方向”转成“让 tracker 处理变化，OCO 只处理几何选择”。这是动机中最有价值的部分。

Core Idea

核心思想可以概括为：把 optimizer design 分解为 gradient prediction 和 online preconditioner selection。m_t 负责把历史 stochastic gradients 压成一个在当前轮之前可测的下降代理；U_t 负责把这个代理映射成实际更新方向；OCO 只看线性损失 L_t(U) = -<s_t, U m_t>/G，用 static regret 学一个固定 comparator 意义下的预条件策略。

这个建模改变了信息流。fresh gradient s_t 不被用来选择当前 U_t，而是在 U_t 和 m_t 固定后用于评价 alignment，再进入下一轮 tracker。这保证了 loss 对当前决策是 unbiased descent feedback，同时避免了 OCO 直接面对非凸轨迹的动态 comparator。和 prior 的本质区别不是多了一个 adaptive matrix，而是把“方向选择”拆成“可预测方向 + 几何变换”，从而让 static regret 有了正确的比较对象。

Method

smooth 情况的关键机制是 tracker-preconditioner coupling。m_t 是 projected exponential moving average，用来平衡 stochastic noise 与 true gradient drift；步长和 averaging rate 绑定，使 x_t 移动不快于 tracker 能跟上的尺度。这个机制解决的是：static regret 本身无法控制非凸梯度变化，必须由 tracker 把变化吸收掉。

OCO loss 的设计解决的是 feedback alignment 问题。L_t(U) = -<s_t, U m_t>/G 是线性的，因此任何 static-regret OCO 都可接入；同时它在条件期望下等于真实一阶下降项。identity comparator 的 loss 直接包含 -<g_t, m_t>，再通过 tracker error 控制得到累计梯度范数。

nonsmooth 扩展的必要机制是 random segment query。没有 smooth descent lemma，就无法用局部梯度加二次项控制 f(x_{t+1})-f(x_t)。作者改为沿实际 displacement 随机采样 y_t，使 E_r <∇f(y_t), δ_t> 精确等于函数差。这是 nonsmooth 部分成立的核心，不是工程技巧。

normalized direction 和 weighted output 是为了构造 Goldstein-style local stationarity certificate。z_t 控制 displacement 半径，weighted output 让 true-gradient tracker 的几何权重和 witness distribution 对齐。它们主要是 proof machinery，但在 nonsmooth reduction 中不可省。

Key Insight / Why It Works

最重要的 insight 是：static regret 不能直接处理非凸方向的时变性，但可以处理固定 identity preconditioner 的相对改进。论文真正有效的原因是把时变部分交给 tracker，把在线学习部分限制在一个固定可比较的几何选择空间。换句话说，OCO 不需要知道“现在该往哪里走”，只需要判断“给定一个可预测方向，哪些坐标/子空间应该被放大或削弱”。

证明的骨架很干净：smoothness 给出 objective progress 下界；static regret 把 played U_t 的 cumulative loss 和 identity comparator 联系起来；identity comparator 的 loss 近似 -||g_t||^2；tracker lemma 保证 m_t 与 g_t 的偏差不会吞掉主项。这里最核心的贡献是 identity comparator correlation 这条链路，而不是 AdaGrad/Shampoo 实例。

这不是 scaling、retrieval、data coverage 或 test-time compute 型贡献；它更像一个 better abstraction / better inductive bias：把 adaptive optimizer 的“几何学习”从“方向生成”中剥离出来。AdaGrad/Shampoo 的增益如果存在，来自它们已有的 data-dependent static regret geometry；conversion 本身保证的是这些几何可以被安全移植到非凸 stationarity 分析中。

需要直接指出的是：论文没有证明这种 preconditioner learning 在实际深度训练中会优于标准 adaptive optimizers。它证明的是一个 black-box theoretical interface。现代 optimizer 的实践收益归因仍不清，可能主要来自已有 adaptive scaling、normalization、momentum 或 architecture/data interaction，而不是这个 reduction。

Relation To Prior Work

最接近的是 Cutkosky et al. 的 online-to-nonconvex conversion、Ahn/Cutkosky 系列对 Adam/SGD 的 online-learning 解释，以及 Chen-Hazan 提出的 black-box reduction open problem。与这些工作的差异在 comparator 结构：prior 常让 online learner 参与 update direction，因而需要 dynamic/shifting/discounted/adaptive regret；本文让 learner 只选 preconditioner，因此可以退回到 undiscounted static regret。

和 online scaled gradient / preconditioner optimization 也很接近，但本文的新增点不是“学 preconditioner”这个想法，而是把它作为 black-box static-regret-to-nonconvex conversion 的接口。AdaGrad/Shampoo 部分看似连接现代 optimizer，其实更多是已有 OCO regret bound 的重组；实质创新在于这些 regret bound 可以通过统一 theorem 直接转译为非凸 stationarity bound。

从技术谱系看，它属于 online learning as optimizer design 的 reduction 分支，而不是新的 stochastic optimization algorithm 分支。它推动的是理论接口的简化：从强 regret / 特化算法走向 static regret / 任意 oracle。

Dataset / Evaluation

这篇论文基本没有传统意义上的 dataset / empirical evaluation。证据主要是 theorem-level：smooth nonconvex、nonsmooth Lipschitz nonconvex、以及 AdaGrad/Shampoo oracle 的实例化。它验证的是“static regret oracle 足够推出已知最优 rate”这一理论 claim，而不是验证某个 optimizer 在真实训练任务中的性能。

从 claim 支撑度看，理论结果支持核心 reduction claim；但不支持更强的实践 claim，例如“解释现代 deep learning optimizer 的主要收益”或“该框架在 LLM 训练中可直接替代现有 optimizer”。AdaGrad/Shampoo 例子只说明接口非空，不能说明真实系统中 preconditioner-space OCO 是更好的实现方式。

没有跨任务 benchmark、真实训练曲线、wall-clock/memory 分析或大规模模型实验。因此 evaluation 的边界很清楚：它是理论可行性与 rate optimality 的验证，不是 empirical optimizer paper。

Limitation

最强限制是 bounded-range 假设。smooth 非凸优化中用全局 range M 作为 progress budget，并由它推出全局梯度范数界；这在理论上常见，但对实际深度网络训练并不自然。参数选择还依赖 M、β、σ 或 L 等尺度，是否能自适应化文中未充分说明。

第二个限制是 preconditioner class 的保守性。U 被要求 compact、convex、包含 I_d、op norm ≤ 1；很多现代 optimizer 的实际机制并不只是一个收缩型 symmetric preconditioner。momentum、sign update、orthogonalization、bias correction、layerwise normalization、weight decay 等都不自然落在这个接口里。

第三，方法可能只是把困难从 nonconvex conversion 转移到“找到合适的 preconditioner-space OCO oracle”。理论上任何 O(√T) static regret oracle 都能恢复 rate，但有用的 data-dependent gain 取决于 oracle 的 geometry 是否匹配问题结构。增益来源不清：如果 learned preconditioner 相比 identity 没有负 regret 或结构优势，最终只是 SGD-rate 的另一种证明。

第四，nonsmooth 算法的 random segment query 和 weighted output 更像理论构造。实际优化中沿每一步 segment 随机采样梯度、再输出加权平均点，不一定符合 deployment 需求。它解决了 stationarity certificate，但不必然给出实用 optimizer。

Takeaway

• 1. 最值得记住的是角色分离：让 tracker 处理非凸轨迹的时变性，让 OCO 只处理固定 comparator 下的几何选择。
• 这是 static regret 能成立的关键。
• 2. identity comparator 是整篇论文的锚点。
• 只要把 baseline 设为 I_d，regret term 就变成“preconditioner 相对普通 tracker-SGD 的适应成本或收益”，理论解释很干净。

一句话总结

这篇论文在 online-to-nonconvex conversion 谱系中把在线学习器从“选更新方向”改造成“选预条件几何”，从而首次用普通 static regret black-box 地推出 smooth 与 nonsmooth 随机非凸 stationarity 保证。