精读笔记

Problem Setting

论文实际处理的是 fully-stochastic 非凸等式约束优化：f、c、∇f、∇c 都只能通过随机 oracle 访问，目标是达到随机 ε-KKT。这个设定比 semi-stochastic 难的地方在于 constraint value 本身也有噪声，而 feasibility residual 又是 KKT 判据的一部分；因此 constraint-value sampling 不是辅助成本，而是主复杂度瓶颈。

以前方法主要卡在 merit 机制上。Smooth quadratic penalty / ALM 容易下降分析，但通常要让 penalty 随 ε 变大，导致步长变小、oracle complexity 变坏；nonsmooth exact penalty 避免大 penalty，却把随机 constraint value 的精度需求放大。关键矛盾是：要 smooth 才能低方差一阶推进，要 exact / bounded penalty 才能不牺牲 feasibility complexity。

Motivation

作者瞄准的缺口很明确：fully-stochastic 场景下，已有方法在 stochastic constraint function evaluations 上通常比 stochastic gradients 更贵，常见为 ε^{-5} 或 ε^{-6}。这说明瓶颈不是方向计算本身，而是 merit/penalty 对 constraint noise 的放大方式。

核心观察是 Fletcher augmented Lagrangian 处在 smooth ALM 和 exact penalty 的中间地带：它不是维护独立 multiplier，而是令 multiplier 成为 primal variable 的连续函数 λ(x)。在强 LICQ 下，这让 stationarity residual 变成切向投影残差，同时 penalty 参数可以有界。作者本质上是在寻找一个不会把可行性推进外包给 ε-dependent penalty 的 smooth merit。

Core Idea

论文的核心不是“用了 SPIDER”或“用了 ALM”，而是把 fully-stochastic constrained descent 改写成切向 stationarity 与法向 feasibility 的同步控制问题。方向 s=-P_V∇f-w∇c c 把优化目标和约束残差分流：切向分量不破坏一阶可行流形，法向分量直接压缩 constraint violation。随机版本用 sampled Jacobian 构造相同结构。

Fletcher AL 是这个分解能够形成全局进度量的关键。普通 ALM 需要追踪 multiplier；这里 λ(x)=-(∇c(x))†∇f(x) 把 multiplier 消除为 primal-dependent mapping，使 merit 的下降能直接绑定到 ||P_V∇f||^2+||c||^2。和 prior 的本质区别是：它不是靠更强的 variance reduction 硬压误差，而是换了 merit geometry，使 constraint-value oracle 不再被 nonsmooth penalty 或 growing penalty 参数系统性放大。

Method

关键机制一：decomposed stochastic direction。它解决的是目标下降和可行性改善互相干扰的问题；切向投影对应 KKT stationarity，法向 correction 对应 constraint violation 下降。核心变化是把 KKT 残差拆成两个几何正交的量，而不是用一个 penalty gradient 混合处理。

关键机制二：Fletcher augmented Lagrangian merit。它解决的是 smoothness 与 exactness 的冲突；λ(x) 替代显式 dual update，使 merit 在 strong LICQ 下可微且 penalty 有界。核心变化是把 multiplier 估计内生化为 Jacobian least-squares 解。

关键机制三：good/bad event decomposition。它解决随机 Jacobian 可能瞬时奇异的问题；在 good event 上 pseudoinverse 和 projection perturbation 可控，在 bad event 上用小概率吸收。没有这个分解，随机投影方向的均方误差很难闭合。

关键机制四：truncated SPIDER estimators。它解决每步 conditional variance control 的需求，而不是单纯降低平均方差。截断主要用于维持有界性和处理 bad event 上的粗界，属于证明稳定性的工程化理论装置。

Key Insight / Why It Works

最核心 insight 是：fully-stochastic constraint complexity 的瓶颈来自 merit geometry，而不只是 estimator variance。只要 merit 迫使 penalty 随 ε 增长，或者使用 nonsmooth ||c|| penalty，constraint value 的采样精度都会被放大。Fletcher AL 把 multiplier 写成 λ(x)，让 stationarity residual 变为切向投影，从而用有界 penalty 同时控制 stationarity 和 feasibility。

真正有效的部分大概率是 Fletcher AL + directional decomposition 的组合。切向/法向分解提供 residual-level alignment；Fletcher AL 提供可下降的 smooth scalar potential；事件分解则让随机 Jacobian 的 pseudoinverse 分析不崩。SPIDER 是必要的复杂度工具，但不是概念贡献，它主要负责把每步估计误差压到 O(ε)，从而与 K=O(ε^{-2}) 配合得到 O(ε^{-3})。

这不是 scaling 故事，也不是 data coverage 或 hidden supervision；它是 merit function 设计带来的复杂度改进。比较像在非凸约束优化里引入更好的 inductive bias：算法被强制沿 constraint manifold 的切向和法向分别组织信息，而不是让 penalty gradient 自己学习这种几何结构。

辅助性较强的部分包括截断、具体 ρ 更新常数、batch-size ceiling 公式。这些对证明重要，但不太像可迁移 insight。可迁移的是：当 stochastic constraints 同时影响 feasibility 和 direction stability 时，应优先设计能把 KKT residual 几何分解的 merit，而不是直接堆 variance reduction。

Relation To Prior Work

它最接近三条线：stochastic SQP 的切向/法向思想、stochastic ALM/penalty 方法的 merit descent、SPIDER/SARAH 类递归估计。论文的新意不是从零发明方向，而是把这些元素用 Fletcher AL 重新粘合，使 fully-stochastic constraint-value complexity 降到与 gradients 同阶。

相对 stochastic SQP，它不解标准二次子问题，也不依赖 Hessian/Lagrangian Hessian approximation，而是用 identity metric 下的投影方向加法向修正；这牺牲了一些二阶建模能力，换来更干净的一阶复杂度。

相对 ALM/penalty，关键差别是 multiplier 不再作为外部随机过程更新，而是 λ(x) 的 deterministic mapping。这个变化看似小，但它改变了理论闭环：stationarity residual 可以直接由 P_V∇f 表示，penalty 参数也不需要随 ε 爆炸。

相对 exact penalty 方法，它避免 nonsmooth merit，因此不需要为 ||c|| 的随机近似付出更高 constraint-value sampling 代价。实质创新主要在 Fletcher-AL geometry 与随机 Jacobian 事件分解的结合；SPIDER 部分更像已有工具的必要嵌入。

Dataset / Evaluation

评估分两类：CUTEst 等式约束问题加合成高斯 oracle noise，以及 fairness-constrained classification 的真实数据例子。覆盖面对于优化论文是合理的：既有标准 nonlinear programming benchmark，也有一个 expectation-constrained ML 场景。

但实验并不能严格验证 O(ε^{-3}) 的复杂度 claim。CUTEst 的 stochasticity 是人为加噪，未必反映真实 stochastic constraints 的结构；fairness 实验还把 inequality 通过 slack 转为 equality，和理论设定存在转换差距。比较方法和参数调优较充分，但结果更多说明该方向在有限 sample budget 下表现稳定，而不是证明复杂度优势来自 Fletcher AL 而非调参或实现细节。

没有大段消融来隔离 Fletcher AL、direction decomposition、SPIDER、event-aware ρ 更新各自贡献，因此增益归因在实验层面不完全清晰。理论归因清楚，实验归因一般。

Limitation

最大限制是 strong LICQ。λ(x) 和 P_V 都依赖 pseudoinverse，常数中 ν^{-1} 以高阶出现；一旦约束 Jacobian 接近退化，Fletcher AL 的 smoothness、projection stability 和 bad-event 控制都会迅速变差。论文通过事件分解处理 sampled Jacobian 退化，但没有真正解决 true Jacobian 退化。

第二个限制是 smoothness 假设偏强。为了证明 λ(x) 的 Jacobian Lipschitz 和 merit gradient Lipschitz，作者需要二阶导 Lipschitz；这比许多 stochastic first-order setting 更重。若应用中 oracle 只满足较弱 mean-squared smoothness，理论不直接适用。

第三个限制是复杂度为 expected complexity，且 batch size 依赖局部步长 ||x_k-x_{k-1}||^2。这个设计在分析上漂亮，但实际部署中很可能用固定 batch 或启发式 batch；理论复杂度和实际 recipe 之间存在鸿沟。

第四，方法主要针对 equality constraints。论文实验通过 slack 处理 inequality，但 active-set 变化、complementarity 和 degeneracy 没被理论正面处理；直接推广到一般 inequality-constrained stochastic nonconvex problem 并不自动成立。

Takeaway

• 第一，fully-stochastic constrained optimization 的 constraint-value complexity 可能更应该从 merit geometry 入手，而不是单纯堆 variance reduction。
• 第二，Fletcher AL 在强 LICQ 下提供了一个有价值的模板：把 multiplier 内生化为 primal mapping，用 smooth merit 同时获得 bounded penalty 和 KKT residual alignment。
• 第三，随机 Jacobian 下的 pseudoinverse 分析需要显式事件分解；这是处理 stochastic constraint geometry 的可迁移技术。
• 第四，未来真正值得做的是弱化 LICQ、处理 inequality/active-set 结构、给出 high-probability bound，并验证复杂度优势在真实 stochastic constraints 而非合成噪声中是否仍然存在。

一句话总结

这篇论文是 fully-stochastic 非凸等式约束优化中一次以 Fletcher augmented Lagrangian 重塑 merit geometry 的复杂度改进：核心贡献不是新的随机估计器，而是用 primal-dependent multiplier 和切向/法向分解把 constraint-value oracle complexity 降到与梯度同阶的 O(ε^{-3})。