精读笔记
Problem Setting
论文标题：Single-loop approaches to nonsmooth bilevel optimisation（arXiv preprint / 2026）。
这篇论文实际解决的是：内层问题只能通过集值参数化约束 0∈G(u,x) 表示时，如何为双层优化构造可用的一阶型 optimality condition 和 single-loop 算法。这里 G 可以是非光滑内层目标的次微分，也可以是 primal-dual optimality system；因此内层解映射 S(x)={u|0∈G(u,x)} 不必单值、不必光滑，甚至局部几何也可能只满足 metric subregularity。
真正困难点在两个层面。理论上，传统 hypergradient 依赖 S'(x) 或 implicit function theorem，而这些在 set-valued nonsmooth setting 下基本失效；即便用 Mordukhovich coderivative，也需要处理链式法则方向、qualification condition、optimistic/pessimistic selection。算法上，bilevel 本身已经昂贵，如果每个外层步都要精确解内层和伴随系统，则对 TV inverse problems 这种大规模非光滑问题不现实。
以前方法卡在：要么要求 G smooth、inner problem strongly convex with differentiable structure；要么通过 proximal reformulation 把非光滑性藏进 prox map，再要求 prox reformulation 有足够可微性或能 exact/near-exact 求 coderivative；要么走 value function/MPCC，但 value function 本身和 constraint qualification 都很麻烦。本文的关键矛盾是：在弱正则、非光滑、集值的环境里，既要有可解释的 generalized hypergradient，又要允许 single-loop inexact inner/adjoint steps。
Motivation
已有路线不够的根本原因不是“不知道怎么写 KKT”，而是这些 KKT/implicit differentiation 在 nonsmooth bilevel 中不是稳定的计算对象。对 smooth G，adjoint equation 本质上是 G_u^* w = −J'(u)，x*=G_x^*w；但当 G 是次微分或 primal-dual inclusion 时，G_u 不存在，S'(x) 也不存在。强行平滑会改变问题；精确求解解映射的 coderivative 又太贵。
作者的核心观察是：外层算法实际只需要一个能产生下降/站点性的 differential estimate，而不必显式得到完整的 solution-map derivative。这个 estimate 可以通过 G 的 coderivative adjoint inclusion 直接定义。换句话说，把“对 S 求导”的问题转移成“在 graph G 的 normal geometry 上找一个 adjoint certificate”。
关键缺口是 Fréchet coderivative calculus 在这种 optimistic/pessimistic bilevel selection 下不够现成，single-loop 误差传播也没有和 nonsmooth coderivative adjoint 系统接起来。本文补的正是这条链：calculus → optimality condition → adjoint inclusion → tracking-based single-loop convergence。
Core Idea
核心思想是把 nonsmooth bilevel 的外层一阶信息定义为 coderivative adjoint certificate，而不是 derivative of solution map。对于 0∈G(u,x)，若能找到 w 和 x* 使得 (−J'(u),x*)∈D*G(u,x|0)(w)，则 x* 可以作为 J∘S 的 generalized differential estimate；在 smooth 情况下这退化为经典 adjoint hypergradient，因此不是另起炉灶，而是把 smooth adjoint 推广到 graph-normal/coderivative 层面。
算法上的核心是 single-loop tracking：每轮只推进内层求解器一步或固定步、推进 adjoint solver 一步或固定步，然后用得到的 x* 做外层 proximal-gradient/forward-backward 更新。理论不是要求每一步 estimate 足够精确，而是要求 estimate error 能被 inner/adjoint tracking errors 控制，并且这些 errors 对外层参数变化有收缩响应。这个组织方式本质上是 memory reuse / continuation：利用上一轮内层和伴随状态作为当前问题的 warm start，把外层缓慢变化转化为可跟踪的动态系统。
和 prior 的本质区别在于，prior 多把 nonsmoothness 变成 prox differentiation 或 exact coderivative of S；本文则把信息流改为 G-level coderivative adjoint + tracking error control。它更 scalable 的原因不是某个新 solver 特别强，而是避免 nested exact solves，并允许 PDPS 这类匹配内层结构的算法参与 single-loop。
Method
1. Optimistic / pessimistic calculus：解决集值 S 下 J∘S 的选择问题。Inf J∘S 与 Sup J∘S 对应不同 bilevel interpretation；Fréchet subdifferential/coderivative 的包含方向天然区分 optimistic necessary condition 和 pessimistic sufficient-for-necessary condition。这不是装饰性定义，而是为了避免把集值 selection 的微分当成单值函数微分。
2. Nonsmooth adjoint inclusion：核心 optimality condition 写成 0∈H(u,x,x*,w)，其中包含 G(u,x)、D*G(u,x|0)(w)+(J'(u),−x*)、x*+∂R(x)。这一步把外层 stationarity 和内层 inclusion 统一到一个 graph geometry 系统中。它带来的变化是从“求 S 的 generalized derivative”变成“求 G 的 coderivative range”。
3. Single-loop tracking abstraction：inner tracking 控制 u_{k+1} 到 S_u(x_k) 的误差；adjoint tracking 控制 w_{k+1} 到 adjoint selection S_w(x_k) 的误差；differential transformation 控制 estimated x* 到 target x* 的误差。这个抽象的作用是把具体算法细节剥离，只保留足以证明外层 residual 收敛的误差动力学。
4. Contractivity under metric subregularity：作者用 metric subregularity 替代更强的二阶增长/强凸性来证明 forward-backward 和 PDPS 类型内层步骤的收缩。这是理论上重要的一点：它解释了为什么非精确 inner step 仍可被 tracking，而不必要求全局线性收敛到唯一解。
5. TV inverse problem adjoint construction：对 TV 正则化，作者显式推导 ∂δ_ball 的 Fréchet/limiting coderivative，得到可求解的 adjoint quadratic constrained problem。这里的价值在于把抽象 coderivative inclusion 落到 primal-dual TV 结构上；但这一部分更偏 problem-specific calculus，而不是通用算法创新。
Key Insight / Why It Works
最重要的 insight 是：bilevel hypergradient 的计算瓶颈并不一定要通过 differentiating the solver 或 differentiating S 来解决；可以直接在内层最优性映射 G 的 graph normal 上求一个 adjoint certificate。这个 certificate 在 smooth case 与经典 adjoint 完全一致，在 nonsmooth case 则自然变成 coderivative inclusion。有效性来自 variational analysis 的链式包含：只要 qualification/regularity 足够，G-level coderivative 能提供 S-level coderivative，再提供 J∘S 的 generalized differential。
第二个关键是 tracking，而不是 exactness。single-loop 能成立的机制类似 continuation/warm-start：x_k 变化小，则 S(x_k)、Z(x_k) 也变化小；如果 inner/adjoint solver 对固定参数有收缩，则上一轮状态足以跟踪当前解。这本质上是 memory reuse + slowly varying parameter dynamics，而不是某种新的优化魔法。
最可能的核心贡献是 nonsmooth adjoint inclusion 与 tracking theory 的耦合。optimistic/pessimistic Fréchet calculus 是必要的理论支架，但对实际算法影响较间接。TV coderivative 推导是重要应用实例，但偏特化。数值增益最可能来自 single-loop 避免 nested exact solves，属于 compute scheduling / engineering efficiency 与理论保证的结合，不应解读为算法在优化景观上更强。
需要直说的是，许多 convergence assumptions 很强且不易验证。文中对 TV 实例的完整理论闭环并未完全给出，尤其 adjoint solution mapping 的 Lipschitz-like 性质、adjoint existence、set-valued descent inequality 的普适验证。实验中的加速基本验证了“少解内层/伴随更快”，但并不能单独证明 coderivative framework 在广泛 nonsmooth bilevel 中都稳定。
Relation To Prior Work
最接近的谱系有三条：一是 smooth bilevel single-loop / single-timescale hypergradient 方法，本文继承其 tracking 思想，但把 smooth adjoint 替换为 coderivative adjoint inclusion；二是 nonsmooth implicit differentiation / proximal reformulation，例如 SparseHO、Bolte/Pauwels 系列、Vilches 等，本文不同在于不要求把内层改写成足够可微的 prox residual，也不依赖 finite-dimensional a.e. differentiability；三是 variational analysis 的 coderivative optimality conditions，本文把这些分析工具推进到可运行的 single-loop algorithm。
看似新的部分中，single-loop tracking 本身来自作者前作和相关 smooth bilevel 工作；PDPS 作为内层求解器也不是新算法；forward-backward outer step 也标准。实质新增的信息是：如何在 G set-valued、S set-valued、J∘S nonsmooth 的情况下，定义合适的 adjoint differential estimate，并说明它对应 optimistic/pessimistic optimality condition；以及如何把这个 estimate 纳入 single-loop convergence proof。
相对 MPCC/value-function reformulation，本文的优势是没有把问题改造成更脆弱的约束系统，也不需要显式 value function。相对 exact implicit/coderivative methods，优势是计算结构更适合大规模 inverse problems。代价是理论条件被转移到 metric subregularity、Aubin-like properties 和 adjoint tracking 上；问题没有消失，只是换到了更 variational 的正则性假设里。
Dataset / Evaluation
实验覆盖 denoising 和 deblurring 两个 TV-regularized inverse imaging toy-to-small-scale 场景，使用 Kodak 图像裁剪和模拟噪声/模糊。任务选择合理，因为 TV 正则内层确实非光滑，且 primal-dual solver 比 naive forward-backward 更自然；这能展示框架的应用价值。
但 evaluation 的范围有限：没有真实传感器数据，没有多种内层非光滑结构，没有大规模多任务 hyperparameter learning，也没有系统比较更多 nonsmooth bilevel baselines。所谓 implicit baseline 本质是同一算法框架中把 inner/adjoint steps 设得很多，因此比较主要验证 single-loop vs near-exact nested 的计算节省，而不是证明相对所有 prior 的优势。
实验支持的 claim 是“该方法在 TV inverse problem 上可实现，并且固定少量 inner/adjoint steps 可以更快降低 stationarity estimate/outer objective”。它没有充分支持更强 claim，例如一般 nonsmooth bilevel 的鲁棒性、limiting coderivative 分支非凸时的稳定性、或理论条件在实际问题中自动满足。文中未充分说明超参数选择的敏感性，增益来源也可能主要来自 computational budget allocation。
Limitation
最大限制是理论假设的可验证性。收敛证明依赖 inner solution mapping 的 one-sided Lipschitz/Aubin-like 性质、adjoint solution mapping 的 bi-Lipschitz-like 性质、differential transformation 的 inner Lipschitz、metric subregularity、set-valued descent inequality、level-set boundedness 等。这些条件不是普通用户能直接检查的，尤其对 primal-dual TV system 更复杂。文中在 Section 5.3 也基本承认完整验证需要 case-by-case analysis。
第二，optimality notion 较弱。结果主要是 inf_{x*∈dE+∂R}||x*||→0 或 proximal residual vanishing，不保证全局最优，不保证强收敛，也不保证极限点存在，除非再加 compactness/outer semicontinuity。对于非凸 outer landscape，这可能停在很差的 stationary region；一维例子中作者也指出可能停在 E 常数区间的局部最优。
第三，Fréchet vs limiting coderivative 的角色并不完全干净。Fréchet 版本更贴近 pessimistic sufficient-for-necessary 条件，但可能为空；limiting 版本给 optimistic necessary condition，但伴随约束可能非凸，算法求解稳定性更微妙。这里存在理论-算法选择的 tension，文中没有完全消解。
第四，实验没有证明泛化。图像任务小、模拟、结构强，且算法参数 trial-and-error。single-loop 优势可能主要来自少做内层/伴随迭代的 scaling/engineering，而不是更本质的 estimator quality。真实 deployment 中外层步长、tracking 常数、adjoint branch selection 的稳定性仍是开放风险。
Takeaway
- 1. 对 nonsmooth bilevel，最值得迁移的不是某个 TV 推导，而是“G-level coderivative adjoint certificate 替代 S-level derivative”的建模方式。
- 它提供了一条不平滑化内层问题的 hypergradient 路线。
- 2. Single-loop 的本质是 tracking slowly varying inclusions。
- 未来如果能系统证明更多问题的 solution/adjoin mapping stability，这类方法会比 nested implicit differentiation 更适合大规模非光滑 inverse problems。
一句话总结
这篇论文把 smooth single-loop bilevel hypergradient 方法推进到 set-valued nonsmooth variational setting，真正贡献是用 coderivative adjoint inclusion 和 tracking theory 组织非精确内层/伴随计算，而不是提出一个单纯更快的工程算法。