精读笔记
Problem Setting
论文标题：Constrained Online Convex Optimization without Slater's Condition（arXiv preprint / 2026-07-01）。
这篇论文实际处理的是随机约束 COCO 中的 regularity-free guarantee：loss 可以 adversarial，constraint 是 i.i.d. stochastic，comparator 只要求期望可行。困难点在于，这个 comparator 在每个 realized round 上可能违反约束，因此 adversarial-constraint 文献中依赖 g_t(x*)<=0 逐轮成立的分析不能直接用。
以前 stochastic COCO 的主线依赖 Slater 或有界 Lagrange multiplier，本质上是在假设 dual optimal set 不会跑太远。这个假设在边界可行、无严格内点、或可行域退化时非常脆弱，且常数会随 Slater margin 退化。关键矛盾是：自然 comparator 太弱，不能给逐轮负项；但没有负项，dual queue 又难以稳定。
Motivation
已有路线不够的地方不是 regret analysis，而是 dual stability 的来源不干净。Yu et al. 依靠 Slater 产生负漂移；Wei et al. 用 bounded multiplier 弱化 Slater，但仍把稳定性外包给问题实例的 regularity。adversarial constraints 的算法看似摆脱 Slater，但那是因为 comparator 被要求逐轮可行，weighted comparator constraint term 直接消失。
作者的核心观察是：Slater 在证明中扮演的是“稳定 dual process”的角色，而非 COCO 问题本身不可或缺的结构。如果算法能自己制造稳定性，就不必向问题假设借稳定性。缺口正是：在 expectation-feasible comparator 下，如何处理 sum Phi'_t(Q_t) g_t(x*) 这个随机加权项，同时不让 dual queue 爆炸。
Core Idea
核心思想是把 dual update 从纯累计 violation 的 queue 改造成带自适应泄压的 queue。算法仍然是 primal-dual：primal 走 surrogate loss f_t + Phi'_t(Q_t) g_t 的 projected gradient；dual 更新则不是 Q_{t+1}=Q_t+g_t(x_t)，而是 Q_{t+1}=Q_t+g_t(x_t)-R_t。R_t 的作用不是 heuristic shrinkage，而是精确匹配证明中出现的累计 Lyapunov-gradient norm。
这相当于把原本依赖 Slater negative drift 的部分替换成一个算法内生的 regularization budget。它引入的 inductive bias 是：dual variable 的增长必须为未来的 Lyapunov-weighted optimization error 付费；queue 不能无成本膨胀。和 prior 的本质区别在于，prior 要么靠实例几何稳定 dual，要么靠强 comparator 消掉随机项；本文靠 adaptive regularizer 重新组织 primal regret、dual drift、comparator feasibility 三者之间的信息流。
Method
1. 指数 Lyapunov：使用 Phi_t(x)=exp(gamma_t x)-1，而不是二次 Lyapunov。它解决的是 surrogate convexity 和 queue tail 控制问题；因为 Phi'_t(Q_t)>0，f_t + Phi'_t(Q_t)g_t 保持凸，且指数势能可以把 Q_t 的增长转化为 log 级反推。
2. Adaptive regularizer R_t：R_t 被设计成 12 gamma_t G^2 加上 Psi 累计增量除以 Phi'_t(Q_t)。它解决的是分析中出现的 sqrt(sum Phi'^2) 无法自然消失的问题；乘回 Phi'_t(Q_t) 后，sum Phi'_t(Q_t)R_t 可以 telescope 成 Psi(sum Phi'^2)，从而抵消 surrogate regret 的关键正项。
3. 高概率 Psi：期望分析中 comparator constraint term 在条件期望下非正；高概率分析中它会产生 martingale deviation。作者把该 deviation 的 anytime concentration bound 放进 Psi，使 R_t 额外抵消随机波动。这是比较干净的设计：不是先证明再 union-bound 修补，而是让算法参数直接覆盖高概率噪声预算。
4. Strong convexity 只改变 primal step size：强凸收益来自 surrogate OGD/AdaGrad 部分的 regret 改进，而不是来自新的 dual 机制。因此 O(log T) regret 是 primal 侧收益；violation 仍受 dual stabilization 与 R_t 累积控制限制，没有同步变成 logarithmic。
5. Adversarial hard violation 通过 [g_t]_+ 化处理：这是机制上的自然改写，把累计对象从 signed violation 换成 hard violation。这里创新性较弱，更像说明框架兼容 adversarial setting；核心难题仍在 stochastic expectation-feasible comparator。
Key Insight / Why It Works
最关键的 insight 是：无 Slater 的困难可以被表述为一个“缺少可抵消项”的证明结构问题。组合 Lyapunov drift 与 surrogate regret 后，会出现三类项：optimization error sqrt(sum Phi'^2)、regularizer payoff -sum Phi'R、以及 weighted comparator constraint sum Phi'g_t(x*)。在 stochastic expectation-feasible setting 下，第三项只有期望非正或高概率可控，不能逐轮归零；第一项如果没有东西抵消，会导致 dual process 失稳。R_t 的设计让第二项精确吃掉第一项，必要时连第三项的 deviation 也吃掉。
这篇最核心的贡献不是“用了指数势函数”，也不是“用了 AdaGrad step size”，而是识别出应该 regularize dual update 的哪个量：不是 Q_t 本身，也不是 g_t(x_t) 的简单 clipping，而是 Lyapunov derivative 的累计平方。这个量正是 primal surrogate regret 和 dual drift 共同暴露出来的 coupling term。
哪些部分可能只是辅助：time-varying gamma_t、AdaGrad-type eta_t、高概率 peeling 主要是把 anytime 与 sharp-ish rate 做出来；它们重要但不是概念核心。adversarial extension 也更像框架复用，不是主要创新。
这不是 scaling、retrieval、data coverage 或 representation alignment 类型的工作；它是一个 proof-driven algorithmic regularization。增益来自更好的 inductive bias：dual queue 的增长必须被一个可 telescope 的 budget 约束。直白说，论文把 Slater margin 提供的外生稳定性替换成了算法设计提供的内生稳定性。
Relation To Prior Work
最接近的是三条线：Yu et al. 2017 的 stochastic COCO with Slater，Wei et al. 2020 的 bounded-multiplier/SELM，Sinha and Vaze 2024 及后续的 adversarial constraints without Slater。
和 Yu et al. 的本质差异是 dual stability 的来源不同。Yu et al. 的 quadratic Lyapunov drift 依赖 Slater 产生 -epsilon Phi'(Q_t)；本文不需要严格可行点，而是用 R_t 在每轮主动扣除稳定性预算。
和 Wei et al. 的差异是没有把难点转移到 bounded Lagrange multiplier。SELM 弱于 Slater，但仍是 regularity assumption；本文试图完全避免这类常数进入 guarantee。
和 adversarial-constraint 工作的差异在 comparator。Sinha and Vaze 可以让 comparator term 为零，因为 g_t(x*)<=0 逐轮成立；本文面对的是 E[g_t(x*)]<=0，因此必须处理随机加权 comparator term。这也是本文真正新增的信息：把 adversarial setting 中的 exponential Lyapunov 思路改造成能服务 stochastic expectation-feasible comparator 的机制。
看似新的部分中，指数 Lyapunov、AdaGrad、supermartingale concentration 都是已有工具；实质创新在于把它们通过 R_t 的 telescoping regularizer 拼成一个不依赖 Slater 的 dual-stabilization 模板。
Dataset / Evaluation
这是一篇理论论文，基本没有传统意义上的 dataset / empirical evaluation。评价主要由 theorem coverage 构成：stochastic constraints 的 expected 与 high-probability guarantee、convex 与 strongly convex losses、以及 adversarial constraints 下 hard violation 的扩展。
这些理论结果确实支撑核心 claim：不依赖 Slater 或 bounded multiplier，也能得到近最优 regret / violation。尤其 stochastic comparator 只需 expectation-feasible，这比直接套 adversarial constraint 算法更符合随机约束问题本身。
但 evaluation 的 limitation 也明显：没有数值实验展示 regularizer 在有限样本中的实际行为，也没有比较 dual queue 是否更稳定、R_t 是否过于保守、常数是否可用。对于一篇理论论文这不是致命问题，但如果关心 deployment，文中没有验证 projection cost、参数常数敏感性、多约束规模化、非 i.i.d. constraint drift 等现实因素。
Limitation
第一，去掉 Slater 不等于完全 assumption-free。算法仍依赖 compact convex decision set、bounded constraint values、bounded subgradients、i.i.d. stochastic constraints、loss 与 constraint randomness 的独立性、以及 full-information feedback。这些条件在实际在线系统里不一定比 Slater 更容易满足。
第二，violation bound 仍是 O(sqrt(T) log T) 或高概率下带额外 log 项。文中没有充分说明 log 因子是否不可避免；从机制看，一部分 log 来自指数 Lyapunov / anytime gamma / concentration peeling，可能是分析或算法保守性，而非问题下界。
第三，R_t 既稳定 dual，也会增加 violation decomposition 中的 sum R_t。论文证明其累积次线性，但这暴露了一个本质 trade-off：稳定性不是免费的，只是被控制在可接受量级。若 Psi 为高概率噪声留出过大预算，有限 T 下可能保守。
第四，多约束情形文中未充分展开。单约束下 Phi'_t(Q_t)^2 的 scalar 累积很干净；多约束若使用 vector queue、norm potential 或 coordinate-wise regularizer，cross-coupling 可能改变结论。
第五，adversarial extension 的 comparator 仍是 round-wise feasible，这是该方向已有的强限制；本文没有突破 Mannor-style impossibility 下更自然 sample-path comparator 的困难。
Takeaway
- 1. 这篇真正推动的是 stochastic COCO 的 regularity-free 理论，而不是提出一个更快的 OCO implementation。
- 2. 可迁移 insight：当 primal-dual 分析中某个 Lyapunov-weighted norm 项无法由问题结构吸收时，可以把它显式写进 dual regularizer，并通过 telescoping 让算法自己支付稳定性预算。
- 3. Slater condition 在很多在线约束问题中可能只是 dual stability 的一种 sufficient mechanism；未来更值得研究的是如何系统性设计内生稳定机制，而不是继续寻找更弱的外生 regularity assumption。
- 4. 下一步真正有价值的是 multi-constraint、projection-free、non-i.i.d. stochastic constraints、bandit feedback 和 dynamic regret；这些会检验该 regularizer 是一个通用模板，还是单约束全信息 setting 下的精巧证明构造。
一句话总结
这篇论文把随机约束 COCO 中原本由 Slater condition 提供的 dual 稳定性，替换为一个可 telescope 的自适应 dual regularizer，是从“依赖问题 regularity”走向“算法内生稳定化”的理论型方法演化。