精读笔记

Problem Setting

论文标题：Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback（arXiv preprint / 2026）。

这篇论文实际解决的是：在 hidden-convex online learning 中，普通 OGD 是否能像 OCO 一样达到 Θ(√T) regret。这里 learner 在原参数 x 上行动，损失 ℓ_t(x)=h_t(q(x)) 一般非凸，但隐藏变量 z=q(x) 上的 h_t 是凸的；q 未知，因此不能直接把问题变成 OCO。

真正困难点不是 hidden convexity 本身，而是算法坐标错配：在 z 空间最自然的是 OMD，在 x 空间可执行的是 OGD。连续时间下二者可由几何条件精确等价，但离散时间会产生 reparameterization discretization error。prior 卡在这里：Ghai et al. 只能证明每步 OGD-OMD discrepancy 为 O(η^{3/2})，累计后只能给 O(T^{2/3}) regret，无法判断这是分析损失还是问题本身的代价。

关键矛盾是：非凸参数化隐藏了凸性，但 learner 又不能使用隐藏凸坐标；如果 OGD 的隐式几何足够像某个 mirror descent，那么非凸性只是坐标表象，否则 adversary 可以利用几何非保守性制造循环 regret。

Motivation

已有路线不够的地方很明确：algorithmic equivalence 只证明了“近似模拟”，但近似精度不足以保留 OCO 的最优 √T regret。由于 identity q 会退化为普通 OCO，任何比 √T 更慢的上界都可能只是分析松。

作者的核心观察是：Ghai et al. 的损失来自比较 perturbed objectives 的 sup-norm，再通过强凸性转成 minimizer distance，这天然带来平方根级别的松弛。若直接比较一阶最优性条件，强凸性给的是线性稳定性，可以把离散误差压到 O(η²)。

另一个动机是厘清 diagonal-Jacobian 条件的地位。对 OGD-OMD equivalence 真正重要的不是 Jacobian 是否 diagonal，而是 induced inverse metric 是否来自某个 Hessian potential。也就是说，问题本质是 Riemannian metric 的 integrability，而不是坐标可分性。

Core Idea

论文真正的核心思想是：把 mapped OGD 当作 hidden-space OMD 的 perturbed trajectory，并把 perturbation 控制在足够小的 O(η²) 量级。为此，作者不再把 OGD 和 OMD 看成两个全局不同的更新，而是在每一步局部化到 O(η) 邻域内，把二者都展开成同一个强凸二次模型 Φ_t 加高阶余项。Hessian compatibility 让两个二次主项完全一致，剩下差异只来自 R 的三阶余项和 q^{-1} 的二阶余项。

这改变的是分析坐标和误差组织方式：prior 证明“两个目标函数很接近”，本文证明“两个最优性方程的残差梯度很小”。这一区别是实质性的，因为 minimizer stability 在强凸问题中由 gradient residual 控制，避免了 O(η^{3/2}) 的松弛。其本质不是 scaling，也不是更强 oracle，而是对 latent geometry 的更精确利用。

论文还补上了反方向：如果 induced metric 不是 Hessian-compatible，OGD 在隐藏空间中对应的向量场可能非保守，adversary 可以让轨迹沿闭合回路运动并积累非零 circulation，从而线性 regret。这说明 Hessian compatibility 不是为了证明方便，而是 OGD 这类欧氏方法能否继承 OMD regret 的几何屏障。

Method

1. Hessian-compatible reparameterization：解决的是 OGD 在 x 空间与 OMD 在 z 空间的一阶几何对齐问题。条件 [∇²R(q(x))]^{-1}=J_q(x)J_q(x)^T 使得 x 空间欧氏二次项经 q^{-1} 展开后，主项正好变成 z 空间 Bregman 二次项。没有它，二者不是同一个局部 metric 下的算法。

2. 局部共同二次模型：作者把 OMD 更新写成 Φ_t(y)+ε_t^{OMD}(y) 的 minimizer，把 mapped OGD 写成 Φ_t(y)+ε_t^{OGD}(y) 的 minimizer。Φ_t 是共享的 1/η-strongly convex quadratic model；两个 ε 分别来自 Bregman divergence 和 q^{-1} 的 Taylor remainder。这一步的作用是把算法差异压缩到高阶余项。

3. 一阶条件比较：核心技术是用 normal cone monotonicity 和 Φ_t 的强凸性得到 ||y_{t+1}-z_{t+1}|| ≤ η ||∇ε^{OGD}-∇ε^{OMD}||。由于两个点都在 O(η) 邻域，余项梯度是 O(η)，所以一步差异是 O(η²)。这是全文最关键的技术提升。

4. Perturbed OMD regret：将 mapped OGD 视为每步带 O(η²) perturbation 的 OMD。regret 上界由 classical OMD 的 D_1/η+ηT 加上 perturbation 项 (T/η)O(η²) 组成；η≈T^{-1/2} 后三项同阶，得到 O(√T)。

5. Geometry characterization 与 barrier：Proposition 1 用 cross-partial 条件刻画 M(z)=[J_qJ_q^T]^{-1} 是否为 Hessian field；Theorem 2 用 polar-like reparameterization q(x)=e^{x_1}(cos x_2,sin x_2) 构造非 Hessian metric，使 OGD hidden dynamics 产生可被 adversary 利用的非保守环流。

6. Bandit extension：BOGD 使用 one-point spherical estimator。分析上引入 ghost hidden estimator J_q(x_t)^{-T}g_t，并沿用 pathwise OGD-OMD coupling。新增误差是 domain shrinkage、smoothing loss、estimator bias 和 inflated gradient norm。机制上是把 classical bandit OCO 分解嫁接到 hidden geometry coupling 上。

Key Insight / Why It Works

最重要的 insight 是：hidden convexity 对 OGD 有用，不是因为非凸损失“局部像凸”，而是因为 reparameterization induced metric 正好是某个 mirror map 的 Hessian metric。也就是说，OGD 实际上在执行一种未显式写出的 OMD。这个 latent mirror descent 解释了为什么一个不知道 q 的算法还能获得 convex regret。

论文真正有效的部分是 O(η²) one-step coupling。这个改进足够精确，因为 OMD regret 对 per-step perturbation 的容忍度大约是 (T/η)C_η；若 C_η=O(η^{3/2})，平衡得到 T^{2/3}；若 C_η=O(η²)，就回到 √T。这里没有统计泛化、数据覆盖或 benchmark trick，纯粹是离散动力系统误差阶数的改变。

Hessian compatibility 是第二个核心 insight。它把“是否可模拟 OMD”转化为“metric 是否 integrable”。若 metric 不是 Hessian field，隐藏空间中的 OGD vector field 可以有 curl；adversary 沿闭合路径驱动迭代，regret 等价于离散 line integral。只要 circulation 非零，就能每圈积累线性级别损失。这个 lower bound 很有解释力：失败不是因为 smoothness 不够，而是因为缺少 potential structure。

bandit 部分相对更像 engineering/theory transfer。它的关键不是新 estimator，而是证明 OGD-OMD coupling 对任意 bounded vector pathwise 成立，因此可以把 bandit gradient estimator 当作输入向量塞进去。T^{3/4} 率主要来自 classical one-point bandit smoothing 的 bias-variance tradeoff，而不是 hidden-convex 结构的新收益。

如果要判断贡献权重：full-information 的 sharp coupling 和 geometry barrier 是实质创新；Proposition 1 是重要的几何澄清；bandit extension 有价值但更像把成熟 OCO bandit machinery 与本文 coupling 拼接。

Relation To Prior Work

最接近的是 Ghai et al. 2022 的 non-convex online learning via algorithmic equivalence，以及 Amid & Warmuth 关于 gradient flow 与 mirror flow 的 reparameterization equivalence。本文不是提出新算法，而是把这条 equivalence 线推进到最优 regret，并把几何条件说清楚。

与 Ghai et al. 的本质差异在分析精度和几何定位。Ghai et al. 已经有 OGD≈OMD 的框架，但使用较粗的 perturbation 控制，导致 T^{2/3}；本文通过 first-order residual comparison 得到 O(η²) coupling，从而达到 √T。这是实质理论改进，不是常数优化。

关于几何条件，Ghai et al. 的 diagonal-Jacobian 是容易构造 regularizer 的充分条件；本文指出真正条件是 M(z) 是否是 Hessian。这个从“坐标可分”到“metric integrability”的提升更 general，也更接近 differential geometry 本质。

与一般 online nonconvex learning 相比，本文不试图处理任意非凸损失，也不依赖 optimization oracle / sampling oracle；它属于 structured nonconvexity + algorithmic equivalence 谱系。与 offline hidden-convex optimization 相比，本文关注 regret 而不是 convergence，因此 adversarial sequence 和 comparator competition 让离散误差成为核心。

bandit 部分与 Flaxman et al. 2005 的一点评估法最接近。新意不在 bandit estimator，而在证明 hidden-convex OGD-OMD equivalence 可以承受随机估计向量并转移到 expected regret。

Dataset / Evaluation

本文没有数据集或实验评估，evaluation 完全是 theorem-level。对于这类学习理论论文，这是合理的；核心 claim 是 regret rate、几何必要性和 bandit extension，理论证明比实验更直接。

不过需要注意，理论验证覆盖的是高度结构化的 hidden-convex setting，而不是实际机器学习模型中的广泛 hidden convexity。文中给出若干 reparameterization 例子和非 diagonal Jacobian 示例，但没有展示这些条件在现代应用如 neural networks、RL、games 中如何系统验证。因此 empirical relevance 文中未充分说明。

Theorem 2 的 lower bound 很好地支持“compatibility 对 OGD 不是 proof artifact”这一 claim，但它只针对 OGD 且 adversary 是 adaptive 的。Theorem 3 支持“one-point bandit 可保持 classical O(T^{3/4}) rate”这一 claim，但 rate 本身主要继承自 bandit OCO，不能说明 hidden-convex bandit 问题已达到最优。

Limitation

第一，方法成立高度依赖 exact Hessian compatibility。q 必须诱导一个 Hessian metric；这比一般 hidden convexity 强得多。很多真实 reparameterization 即使让目标凸化，也未必满足该 integrability 条件。

第二，算法声称不需要知道 q，但理论需要 q、R 以及各种 smoothness/diameter 常数存在且有界。换言之，学习者无需显式 q，但 guarantee 的适用性仍由隐藏几何决定；这更像“算法对某类几何自动适配”，不是可检验的 black-box guarantee。

第三，lower bound 的结论范围有限。它证明 OGD 在非 Hessian geometry 下会失败，不证明所有算法都会失败。也就是说，本文给的是 OGD 的 geometric barrier，不是 OHCO 的 information-theoretic barrier。

第四，bandit extension 的上限明显：一点评估导致 d、M、δ 的标准膨胀，T^{3/4} 是 classical smoothing tradeoff。这里没有利用 hidden convexity 获得比 convex bandit 更强的 rate，也没有高概率界或 minimax optimality。

第五，Assumption 2/3/4/5/6 较重：q、q^{-1}、R 到三阶导数、Bregman diameter、loss smoothness/boundedness都要控制。理论上干净，但真实问题中这些常数可能非常差，√T 率可能被巨大几何常数淹没。

第六，projection 和 domain issues 被假设处理得比较理想。特别是 bandit 中 shrinked domain 经 q 后的几何性质由分析使用，但 learner 并不知道 q；算法可执行性没问题，但实际可调参数和 feasibility 依赖标准归一化，文中没有深入讨论部署层面的鲁棒性。

Takeaway

• 1. hidden-convex online learning 中，OGD 能否达到 convex-like regret 的关键不是 convexification 本身，而是 reparameterization induced metric 是否为 Hessian metric。
• 2. 对 algorithmic equivalence 类证明，比较一阶最优性残差往往比比较目标函数扰动更 sharp；这里它直接把 regret 从 T^{2/3} 推到 √T。
• 这个 proof pattern 可迁移到其他“离散算法近似连续几何流”的问题。
• 3. 非 Hessian geometry 下的失败机制是非保守环流：如果算法隐式动力学不来自 potential，adversary 可以通过循环路径积累 regret。

一句话总结

这篇论文把 hidden-convex online learning 中 OGD≈OMD 的几何等价从 T^{2/3} 分析提升到最优 √T regret，并证明 Hessian-integrable geometry 是 OGD 能继承凸优化 regret 的真实边界。