精读笔记
Problem Setting
论文实际挑战的是一个看似自然但并不成立的泛化：把非复合 smooth/Hölder-smooth 场景中 AdaGrad 的自适应收敛率结论，直接迁移到 proximal composite objective。困难点不在 prox update 是否合理，而在 AdaGrad 的累积量是否仍代表接近最优性。复合最优性由 ∇f+∂φ 决定，单独的 ∇f 可以在最优点非零；因此标准 AdaGrad 的 denominator 可能持续增长，即使真实 composite residual 已经趋零。以前结果卡在它们本质上分析的是 ∇f(x*)=0 的世界，这个等式在 composite splitting 下消失了。关键矛盾是：update 使用 composite geometry，但 adaptivity 仍使用 non-composite stationarity signal。
Motivation
已有路线默认“梯度变小”与“接近解”同步，因此累积梯度范数既是历史尺度估计，也是优化进展的 proxy。作者的核心观察是，在 composite objective 中这个同步关系断裂：smooth part 的梯度可能只是被 φ 的一阶项抵消，而不是自己消失。缺口不是缺一个更精细的 proof，而是标准 AdaGrad metric 选错了对象。由此自然想到构造一个 φ 足够简单、甚至完全光滑/仿射的例子，排除 nonsmoothness 作为解释，把失败直接归因到 splitting-induced stationarity mismatch。
Core Idea
论文的核心思想是把目标函数设计成 F=f+φ=g_{p,c}，但让 f 本身包含一个线性偏移 -x，φ 再用 +x 抵消它。这样真实目标的最优点是 0，迭代动力学通过 prox 把线性项抵消后确实朝 0 走；可是 AdaGrad 累积器看到的是 f'(x)=g'_{p,c}(x)-1，在 x→0 时趋向 -1，而不是 0。
这个构造改变的不是优化问题本身的难度，而是 algorithmic bookkeeping：同一个 composite update 中，step direction 与 metric 使用了不一致的 stationarity notion。prior 的 AdaGrad universality 依赖累积项随解附近变小；这里作者强行让累积项在解附近保持常数，迫使有效步长退化为 1/√n。它的本质区别在于：不是证明一个新算法更好，而是证明标准 gradient accumulation 的 inductive bias 与 composite optimality 不兼容。
Method
第一，构造 f(x)=g_{p,c}(x)-x 与 φ(x)=x，解决的是如何让 F 的最优点处 ∇f 不为零；必要性在于只有这样才能让 AdaGrad denominator 与真实 stationarity 脱钩；核心变化是把失败来源从 nonsmooth φ 转移到 splitting 本身。
第二，选择 g_{p,c} 在原点附近像 |x|^p、远离原点线性截断，解决的是同时获得凸性、全局 Lipschitz gradient 和可控局部动力学；这保证反例属于所有 C^{1,ν}，避免被解释为 smoothness 不足。
第三，利用 prox_{γφ}(v)=v-γ，使更新变成 x_{n+1}=x_n-γ_n g'_{p,c}(x_n)。这一步很关键：算法的实际位置更新像是在优化 g，但 γ_n 的生成仍由 |g'(x_n)-1| 控制。
第四，证明 |f'(x)| 被夹在 1-c 与 1+c 之间，所以 w_n 线性累积平方后为 Θ(√n)。这直接锁死了 effective stepsize 的尺度。
第五，通过局部递推 r_{n+1}=r_n-γ_n c r_n^{p-1} 推出 objective gap 的多项式下界。调节 p 可以让慢速指数落在任意 α∈(1/2,(1+ν)/2)，从而否定 Hölder-adaptive rate。
Key Insight / Why It Works
最核心 insight 是：AdaGrad 的“自适应”并不是抽象地适应 objective smoothness，而是适应它所累积的信号；如果信号不是正确的 optimality residual，自适应会稳定地产生错误尺度。这里不是步长调得不够好，而是 denominator 被一个不会消失的 smooth-gradient offset 污染，所以算法越接近解，越继续像未接近解一样缩小步长。
反例成立的关键不是 one-dimensional trick，而是 composite optimality 与 component gradient 的非等价性。φ 是仿射函数这一点很强：它说明问题不是 prox 处理 nonsmooth regularizer 的技术细节，而是任何把 objective 拆成 f+φ 后只累积 ∇f 的方案都可能遇到的结构性失配。
最可能的核心贡献是这个 clean separation：更新方向可以是 composite-correct 的，但 metric 可以是 composite-wrong 的。辅助部分是具体 p 参数化和下界指数调节，它让结论覆盖任意 ν，但技术上更像把 pathology 调到目标 rate 区间。
这不是 scaling、data coverage、retrieval、memory reuse 或 test-time compute 贡献；它是一个关于 adaptive metric inductive bias 的负面理论结果。它提醒后续算法设计：所谓 universality 不能只看 update class，还要看被累积的量是否与问题的 stationarity notion 对齐。
Relation To Prior Work
它最接近三条线：Duchi et al. 的 composite AdaGrad、Levy/Orabona 的 smooth/Hölder universality、以及近期 gradient mapping accumulation / AdaGrad-Diff。与 Duchi-style composite AdaGrad 的差异是，原始 nonsmooth Lipschitz 结果目标是 O(1/√n)，而本文指出当 smoothness 更好时，标准累积机制并不会自动利用它。与 Orabona 的非复合 Hölder result 的本质差异是 ∇f(x*)=0 是否成立；本文正是通过破坏这个前提否定直接迁移。
看似新的地方不是构造一维下界本身，而是把“累积什么”提升为 composite adaptivity 的核心变量。gradient mapping accumulation 不是简单替换公式，而是把 metric 对齐到 composite residual；gradient-difference accumulation 则避免累积非零极限梯度。本文的实质创新是给这些替代路线提供了一个不可忽略的必要性论证：它们不是 cosmetic variants，而是在修正标准 AdaGrad 的 stationarity mismatch。
Dataset / Evaluation
没有数据集、实验或 benchmark；evaluation 是理论反例与下界。对于本文的核心 claim，这种 evidence 是足够直接的：只要存在一个满足假设的凸 composite Hölder-smooth 问题使 AdaGrad 慢于 O(n^{-(1+ν)/2})，一般性适配性就被否定。
但它没有验证 practical prevalence。它不能说明真实 ML benchmark 上 standard AdaGrad/Adam 类方法一定因该机制失败，也没有比较 gradient mapping accumulation 或 AdaGrad-Diff 的实证收益。换言之，evaluation 精准支持“理论 guarantee 不成立”，不支持“实际训练中普遍有显著性能损失”这类更强 claim。
Limitation
该结果依赖一个 adversarial splitting：F 本身很简单，但被拆成 f 与 φ 后制造了 ∇f(x*)≠0。实际问题中 splitting 通常由建模语义给定，如 loss + regularizer 或 constraint indicator；文中未充分说明这些自然 splitting 中该非零 smooth-gradient offset 是否常见到足以影响实践。
下界是 worst-case，并且 η 需要足够小。它足以推翻 universality theorem，但不等于说明所有步长、所有初始化、所有 coordinate-wise variant 都同样慢。高维 diagonal AdaGrad、stochastic gradients、momentum/Adam-style normalization 下是否有同构 pathology，文中未充分说明。
对替代累积机制的讨论偏概念性。gradient mapping 与 gradient-difference 的确避开这个反例，但二者在复杂 composite settings 中的代价、稳定性、coordinate-wise 可分性和 sharp rate 是否同样理想，不是本文解决的问题。
更深的限制是：它证明了“累积 ∇f 不够”，但没有给出唯一正确的 replacement。gradient mapping 是自然 residual，但依赖 step parameter；gradient difference 避免非零极限，但是否总能表达 composite stationarity，仍需要更系统的理论。
Takeaway
- 1. 复合优化里的 adaptive metric 必须对齐 composite optimality，而不是默认沿用 smooth part gradient。
- 2. AdaGrad 的 universality 不是一个与 problem formulation 无关的性质；splitting 会改变梯度信号的语义，即使 F 本身不难。
- 3. gradient mapping accumulation 和 gradient-difference accumulation 的价值在于修正 stationarity proxy，而不只是 engineering variant。
- 4. 后续值得做的不是继续证明标准 gradient accumulation 的更精细 bound，而是系统刻画哪些 residual 可以同时支持 composite structure、Hölder smoothness、stochasticity 和 coordinate-wise adaptivity。
一句话总结
这篇论文用一个极简凸复合反例说明：标准 AdaGrad 在 composite setting 中失败的根因是累积了错误的 stationarity signal，因此它属于 adaptive optimization 从“梯度范数累积”转向“composite residual 对齐”的负面理论分水岭。