精读笔记

Problem Setting

论文标题：Inexactly Smooth Performance Estimation and New Optimized Gradient Methods（arXiv preprint / 2026-06-02）。

这篇论文处理的是凸优化一阶方法在“非精确光滑”函数类上的最坏情形分析与算法设计。这里的对象不是单独的 L-smooth，也不是单独的 Lipschitz/nonsmooth，而是一类满足 f(y) ≤ f(x)+<g_x,y-x> + L(δ)/2 ||y-x||² + δ 的 convex functions。关键是 L(δ) 不是常数，而是一条误差—曲率 tradeoff curve。

真正困难点在于：PEP 的核心依赖 interpolation theorem。对 L-smooth convex functions，Taylor-Hendrickx-Glineur 的插值条件给了 exact finite-dimensional SDP；对 nonsmooth Lipschitz 或 Hölder smooth，中间没有同样干净、统一、tight 的插值几何。因此以前要么针对 smooth 写一套 PEP，要么针对 Lipschitz/nonsmooth 写另一套 lower-bound/dual construction，要么使用 Nesterov universal method 的分析技巧但不能直接变成统一的 algorithm design pipeline。

这篇论文的关键矛盾是：想要一个足够 general 的函数类来覆盖 smooth、nonsmooth、Hölder、混合结构；但 PEP 又要求函数类必须有有限轨迹插值刻画，否则 worst-case program 只是形式化定义，不能求解、不能对偶、不能反推出算法。本文的贡献就是把这个矛盾压缩到 L(δ)-inexact smoothness 和对应的 interpolation constant c_L 上。

Motivation

已有路线的问题不是缺少 universal rate。Nesterov UFGM、Devolder-Glineur-Nesterov 的 inexact oracle 已经能处理 Hölder smoothness，并给出常数因子内的最优速率。缺的是一个可用于 PEP 的函数类几何：给定有限个观测点 (x_i,f_i,g_i)，什么时候存在一个满足该正则性的凸函数插值它们？没有这个，就无法系统地做 exact worst-case analysis，也无法把 Drori-Taylor 的 constructive approach 扩展到更一般的正则性。

作者的核心观察是：Hölder smoothness 被 universal methods 使用时，本质上并不是直接用 ||g_x-g_y||≤β||x-y||^p，而是通过“任意 δ 下的 inexact quadratic upper bound”在工作。既然如此，与其把 Hölder 当主对象，不如把这个 upper model 本身抽象成定义。这样 smooth 是 L(δ)=L，p=0 bounded subgradient variation 是 L(δ)=β²/(2δ)，一般 Hölder 是 L(δ)=κ/δ^q，smooth+nonsmooth sum 是 L(δ)=L_s + M²/(2δ)。

关键缺口是：这个抽象是否只是分析方便，还是能形成完整 calculus + interpolation + PEP duality + algorithm construction。本文基本回答是肯定的，但精确性只在部分端点成立；中间 Hölder 情形仍有常数 gap。

Core Idea

核心思想是把“函数正则性”重写成一条可优化的局部模型预算曲线。传统 smooth analysis 中，所有步都由固定 L 的 quadratic model 控制；nonsmooth/subgradient analysis 中，更多依赖梯度范数或 Lipschitz 常数。本文让算法和分析在每对轨迹点之间选择一个 tolerance δ：用 δ 买一个曲率 L(δ)，从而把不同正则性统一为同一个 quadratic-majorization 语言。

这带来的本质变化是：PEP 里的约束不再是单一 smooth interpolation inequality，而是 f_i-f_j-<g_j,x_i-x_j> - ||g_i-g_j||²/(2L(δ)) + δ ≥ 0, ∀δ。 对 δ 取 supremum 后得到 θ_L^*(||g_i-g_j||) 形式的凸约束。这相当于把正则性信息从 primal distance side 转移到 gradient-difference side，并通过 Fenchel/conjugate 结构组织起来。

和 prior 的本质区别在于：Nesterov universal method 是“算法不知道 p，但分析可适配 p”；本文更像是“PEP 和算法设计语言不知道具体正则性，只需要 L(δ)”。这使得 algorithm design 可以从 dual certificate 自动生成，而不是人工为每个 p 或每类 sum structure 重写 estimate sequence。

Method

1. L(·)-inexact smooth calculus：解决“这个函数类是不是稳定”的问题。作者要求 L finite on δ>0、convex、lsc、nonincreasing、且 -1/L convex。这个假设不是装饰，它保证 θ_L(s)=inf_δ L(δ)s²/2+δ 的凸性、共轭表达、以及 PEP 约束的凸性。核心变化是把 smooth calculus 平移到 inexact setting：缩放、线性复合、求和、inf-projection、共轭强凸性都能保留。

2. interpolation theorem：解决“PEP 是否真实对应某个函数类”的问题。必要条件来自 inexact cocoercivity；充分性通过构造 r=(max_i r_i^*)^*，其中 r_i(x)=f_i+<g_i,x-x_i>+θ_L(||x-x_i||)。这是论文最关键的数学构造。它把 finite observations 包成一族 radial bump 的共轭最大值，再取共轭回到 primal。代价是 smoothness 从 L 变为 c_L L(·/c_L)，且 c_L≤2。

3. inexact PEP：解决“如何计算 worst-case”的问题。将轨迹点和梯度内积 Gram 化后，PEP 变成 F,G 上的凸优化问题。它不一定是 SDP，因为 θ_L^* 可能不是二次/线性矩阵约束，但仍可凸对偶。Theorem 3.6 在 W 对角非零和维度 d≥N+2 下给 strong duality。

4. constructive algorithm design：解决“如何从 PEP 反推出算法”的问题。作者把 Drori-Taylor 的 GFOM/SSEP 思路搬到 inexact PEP：先解 GFOM 的 dual certificate，再构造一个 fixed-step method 继承同一证明。机制上不是 heuristic acceleration，而是 proof-carrying algorithm synthesis。

5. 三个算法实例：p=0 时得到 exact minimax optimal method；L(δ)=κ/δ^q 时得到 asymptotically optimized OGM-like method；未知 L 时得到 UOBL，通过 backtracking 寻找足够大的 local L_n，并付出 ε-level additive tolerance。

Key Insight / Why It Works

最核心的有效性来自一个几何事实：inexact smoothness 的真正可插值约束不是 primal quadratic upper bound，而是其等价的 inexact cocoercivity / conjugate inexact strong convexity。这个转换使得有限轨迹信息只需要约束 f_i-f_j、<g_j,x_i-x_j> 和 ||g_i-g_j||，从而能进入 Gram/PEP 框架。没有这一步，L(δ) 只是一堆无限 δ 的 upper-model inequalities，很难用于算法设计。

第二个关键 insight 是 θ_L 的角色。θ_L(s)=inf_δ L(δ)s²/2+δ 是“距离 s 下最便宜的 upper-model error”；θ_L^*(u)=sup_δ u²/(2L(δ))-δ 则是“梯度差 u 下必须支付的 function gap”。这几乎就是把未知正则性压缩成一个 convex penalty。PEP 可行性因此变成了一种 Bregman-like / Fenchel-like gap accounting。

最实质的贡献我认为是 Theorem 3.3 的插值构造，而不是后面的算法公式。算法 1/2/3 很多结构都继承自 OGM、OBL、UFGM、SSEP；真正新增的信息是：这些结构为什么可以在 inexact smooth class 中合法地被 PEP 证明和自动优化。

p=0 exact minimax optimal 是本文最干净的结果。因为 p=0 的 interpolation 恰好退化为 convexity inequalities + ||g_i-g_j||≤β，没有 c_L 损失。这里算法改进不是 scaling，而是函数类建模不同于 classical M-Lipschitz：bounded subgradient variation 是 tilt-invariant，和 Lipschitz continuity 只在有 minimizer/zero subgradient 时常数等价。这个 distinction 有实际理论意义。

一般 Hölder 的 Algorithm 2 更像是对 OGM proof weights 的 tolerance scaling 优化。它的 gain 主要来自更精细地分配 δ_{n-1,n}，而不是新的 acceleration mechanism。作者给出的 leading coefficient optimality 是 conjectural；目前证据是数值 PEP 趋近，增益来源相对清楚但最优性未闭合。

UOBL 的作用是把 L(δ) 未知性转化为 backtracking + target ε。它本质上属于 test-time adaptivity / line-search compute，而非新的 minimax construction。其理论保证有 Δ_N accumulated error，这个项在实际中可能温和，但文中没有充分说明其可控性边界。若 Δ_N 大，universal guarantee 的可解释性会变弱。

这不是 data/scaling/retrieval 类工作；核心完全是 better inductive bias for worst-case analysis：把各种正则性统一编码为 L(δ) 曲线，并让 PEP 的 dual certificate 自动决定误差预算如何流动。

Relation To Prior Work

最接近的谱系有三条。

第一是 Devolder-Glineur-Nesterov / Nesterov universal gradient methods。它们已经使用 inexact quadratic upper bound 分析 Hölder smoothness，但没有把它发展成插值理论和 PEP 框架。本文把这个分析技巧提升为函数类定义，并给出 calculus 与 interpolation。

第二是 Taylor-Hendrickx-Glineur / Drori-Teboulle 的 PEP。经典 PEP 的强项是 smooth convex 上的 exact SDP 和 tight worst-case bounds。本文真正新增的是：在非精确光滑函数类上构造 PEP，且一般是 convex program 而不一定是 SDP。它牺牲一部分 exactness，换取更大的函数类覆盖。

第三是 Drori-Taylor constructive approach / OGM / OBL。本文后半部分明显继承了这一脉络：GFOM PEP → dual multipliers → SSEP fixed-step method。新意不在 SSEP 本身，而在证明这套 machinery 可以在 L(δ)-inexact smoothness 下运行，并产出 p=0 exact optimal、general Hölder asymptotic optimized、universal backtracking variants。

一些看似新的算法形式其实是已有 OGM/OBL 结构的再参数化：Algorithm 2 结构上就是 OGM-like，Algorithm 3 是 OBL 的 inexact/universal extension。实质创新在函数类建模和插值，而不是迭代公式本身。

与 Lipschitz nonsmooth literature 的关系也值得注意。p=0 Hölder smoothness 与 M-Lipschitz convex minimization 常数等价但不是同一模型。本文明确利用 bounded subgradient variation 的 tilt-invariance，得到与 Lipschitz optimal subgradient methods 相似但不同的 minimax method。这是一个细但重要的建模差异。

Dataset / Evaluation

这篇是优化理论论文，没有传统 dataset。evaluation 主要包括：理论 worst-case bound、minimax lower bound、PEP 数值解与曲线比较。

p=0 部分的 evaluation 最强：有上界算法和匹配 lower-bound hard instance，因此 exact minimax optimality 支撑充分。这个结论不依赖数值实验。

一般 Hölder / L(δ)=κ/δ^q 部分，数值 PEP 用来支持作者猜测的 asymptotic leading coefficient。它验证的是“constructive GFOM PEP 解与所提 tolerance schedule 接近”，而不是完整证明最优性。benchmark 范围覆盖不同 q 和 N，但仍属于离线 worst-case convex program 验证；没有真实问题实例，也不需要真实部署。

UOBL 的 claim 是 universal / parameter-free。理论上覆盖任意满足假设的 L(δ)，包括 Hölder 和混合 smooth+nonsmooth。evaluation 没有充分展示在复杂混合正则性或大规模实际问题上 backtracking 行为如何，尤其 Δ_N 是否小、line-search 成本是否可忽略，文中未充分说明。

总体上，evaluation 足以支持“理论框架可运行”和“部分端点 tight”；不足以支持“一般 Hölder leading constant 已最优”或“universal method 在实际场景明显优于已有方法”。

Limitation

1. 插值理论不是一般 exact。Theorem 3.3 的充分性带 c_L≤2，Hölder p∈(0,1) 还因为 inexact quadratic relaxation 本身存在至少 ((p+1)/(2p))^p 的 gap。因此该框架对中间 Hölder 类不是精确几何刻画，而是一个常数近似 envelope。

2. 一般 Hölder optimality 未闭合。Algorithm 2 的 asymptotic coefficient 看起来好，但 Conjecture 4.4 仍未证明。这里不能把数值 PEP 趋势当成 minimax optimality。增益来源主要是 tolerance schedule 的优化，是否达到信息复杂度极限仍不清楚。

3. PEP 可计算性上限不清。经典 smooth PEP 是 SDP，工具链成熟；这里一般是 convex program，θ_L^* 可能带非线性锥/非标准约束。大 N、复杂 L(δ)、多组件组合时是否 scalable，文中未充分说明。

4. UOBL 把未知正则性转移成 backtracking 和 ε。它是 universal，但不是免费 universal。保证中含 Δ_N，且 L_n doubling 的累计成本和梯度范数项可能影响实际表现。文中没有给出足够强的 a priori bound 来说明 Δ_N 总是低阶。

5. L(δ) 假设有选择性。convex、nonincreasing、-1/L convex 保证理论闭合，但也排除了某些可能自然的 irregular smoothness profiles。该条件是为 calculus/PEP convexity 服务的，不一定是最宽的函数正则性模型。

6. 框架目前主要是 unconstrained convex first-order oracle。proximal composite、约束、随机噪声、相对光滑、mirror geometry、non-Euclidean norm 等扩展并非直接完成。很多现代优化问题需要这些结构。

7. 算法公式可能不是最重要收益。除 p=0 外，后续方法更像 OGM/OBL 的重新加权版本；如果只关心实际算法，收益可能没有理论框架那么大。

Takeaway

• 1. 最值得记住的是 L(δ) 视角：很多“介于 smooth 与 nonsmooth 之间”的正则性，本质上可以看成用 additive error 购买 quadratic curvature 的预算曲线。
• 这是一个可迁移的建模方式。
• 2. 插值定理是核心资产。
• 只要能为某个函数类建立 finite observation interpolation，就能把 PEP、dual proof、algorithm synthesis 串起来。

一句话总结

这篇论文把 Hölder/smooth/nonsmooth/混合凸优化的正则性统一为 L(δ)-inexact smoothness，并用近 tight 插值定理把 PEP 与 constructive algorithm design 扩展到该类问题，是一篇以“函数类几何重建”推动 optimized first-order methods 的理论工作。