精读笔记
Problem Setting
《First-Order Methods for Solving Convex (Strongly) Concave Minimax Problems with Functional Constraints》（arXiv preprint / 2026）实际解决的是一类结构很具体但此前缺少复杂度理论的 minimax：目标是 convex-concave，x 和 y 各自带一般函数约束，且约束是分离的而非耦合的。难点不是写出 KKT，而是如何在一阶算法中高效调用内层 constrained maximization 的 value/gradient。
如果 y 约束是简单集合，已有 saddle-point / extragradient / mirror-prox 路线可以工作；如果没有 y 约束，可以把 ζ(x)=max_y F(x,y)-h(y) 当作 smooth value function 处理。但这里 p(y)≤0 是一般函数约束，直接求 ζ(x) 的梯度需要解一个 constrained max 子问题，max oracle 本身就和原问题一样难。另一方面，直接把 x、y、z、u 全部放进一个 primal-dual saddle 系统，会丢掉凸函数约束优化中已有的 ε^{-1} ALM 复杂度结构。
关键矛盾是：要利用 convex minimization with functional constraints 的成熟 ALM 理论，就必须把 minimax 的内层约束变成一个可微/近似可微的目标项；但要做到这一点，又必须保证内层 dualization 不破坏全局等价性和梯度可控性。
Motivation
已有路线的缺口很清楚。Minimax 文献大多默认约束可投影或无约束；functional constrained minimization 文献能处理 c(x)≤0，但不处理 objective 是 constrained max value function；随机 expectation constrained minimax 工作如 Yang-Li-Lan 2025 给出 O(ε^{-2}) 型结果，但没有利用确定性 smoothness 与强凹结构。
作者真正抓住的是“分离式约束”这个结构红利。p(y) 只依赖 y，c(x) 只依赖 x，因此内层 y 约束可以先局部对偶化，而不是和 x 约束一起形成耦合 saddle 系统。这一点使问题比一般 coupled constrained minimax 更可解，也解释了为什么论文没有试图处理 q(x,y)≤0。
换句话说，论文缺的不是一个新的加速器，而是一个让已有 ALM 复杂度理论可接入 minimax 的 reformulation。作者的方向选择是：不要正面求 constrained max oracle，而是把它变成 unconstrained penalized max oracle，并把误差预算嵌入 ALM。这个动机是合理的。
Core Idea
核心思想是利用强对偶把内层函数约束吸收到目标里。定义 Q(x,y,u)=F(x,y)-h(y)-1/(2β_y)(||[β_y p(y)+u]_+||^2-||u||^2)，再令 Ψ(x,u)=max_y Q(x,y,u)。在 Slater 条件下，原来的 ζ(x)=max_{p(y)≤0} F(x,y)-h(y) 等于 min_u Ψ(x,u)。于是原问题等价为 min_{x,u} Ψ(x,u)+g(x), s.t. c(x)≤0。
这个重排的本质区别是：它没有把 minimax 直接当作 saddle-point VI，而是把它转成一个带函数约束的凸最小化问题，其中目标的 smooth part 是一个可通过无约束/简单 prox 的强凹 maximization 近似评估的 value function。信息流从“x-y 同时博弈 + 双边约束”改成“y 只服务于提供 Ψ 的梯度，x/u/z 由 ALM 管理”。这使得分析可以沿着 convex ALM 的路径推进。
理论上有效的原因在于强凹给出唯一 y(x,u)，Danskin 定理给出 Ψ 的梯度表达，近似 maximizer 的 stationarity 可以转成 Ψ 梯度误差；而 PALM 的外层 penalty/proximal schedule 把 constraint violation、complementarity、stationarity 同时压到 ε。
Method
方法不是简单的“ALM + APG”堆叠，每一层都有明确的结构功能。
1. y 约束的增广对偶化：解决 constrained maximization 难以作为 oracle 的问题。引入 u 后，p(y)≤0 不再作为 feasible constraint 出现，而通过 [β_y p(y)+u]_+ 进入 Q。核心变化是内层子问题从 constrained max 变成可用一阶/prox 方法近似求解的强凹 max。
2. 对 (x,u) 使用 proximal ALM：解决外层 c(x)≤0 的函数约束。这里没有把 c(x) 做投影，而是用 augmented Lagrangian 和 z 更新处理，这继承了函数约束凸优化中已知的 ε^{-1} 复杂度范式。proximal 项 ρ_t||v-v^t||^2 使每个子问题强凸，便于 accelerated solver 和乘子有界性分析。
3. iAPG 子程序：解决 Ψ 梯度不可精确获得的问题。每次需要 ∇Ψ(x,u) 时，先近似求 y maximizer，再用 ∇_{x,u}Q 作为 inexact gradient。iAPG 的 stopping rule 把 inner error 设为随外层迭代递减的 ω_k/η_t，从而保证误差不会在 ALM stationarity 中积累失控。
4. 乘子界与误差传递分析：这是技术核心。论文花大量篇幅证明 u^t、z^t 有界，并据此控制 Ψ 的 Lipschitz 常数、内层 y 子问题的 smoothness、以及总 y-oracle 数。没有这些界，算法形式仍然成立，但复杂度证明不闭合。
Key Insight / Why It Works
最重要的 insight 是：分离式 inner functional constraints 可以被“局部强对偶化”，从而把一个 constrained minimax 问题降维成 functional constrained minimization with inexact smooth value function。这个转换比算法本身更关键。PALM、APG、augmented penalty 都是成熟工具；真正新增的信息是如何让它们在 minimax + y-constraint 场景中组合后仍有全局 ε-KKT/ε-optimal complexity。
强凹是整个机制的支点。强凹给出 y(x,u) 唯一性，使 Ψ 可微；近似 y 的 stationarity 通过 μ_F 转成距离界 ||y-y(x,u)||，再转成 Ψ 梯度误差。这里不是“更好的 optimization trick”，而是把 inner max 的曲率用作 error-to-gradient 的稳定器。凸-凹情形复杂度退化到 ε^{-3/2}，也正说明强凹不是可有可无的假设，而是复杂度的核心来源。
另一个关键 insight 是 multiplier boundedness。论文证明 u、z 受 Slater margin 与 compactness 控制，这让所有 Lipschitz 常数和 inner APG 复杂度成为可加总的量。这个部分是理论上最费力也最有价值的；否则嵌套算法常见的问题是外层看似收敛，但 inner oracle 成本随乘子爆炸。
哪些可能只是辅助？iAPG 的具体 line-search、η_t/ρ_t/β_t 的几何 schedule 更像为复杂度证明服务的 engineering/theory plumbing，不是本质创新。核心贡献不是用了 Nesterov 加速，而是把 constrained max 的困难变成可控 inexact gradient，并证明 ALM 误差预算能闭合。
这篇没有数据、没有 scaling。不存在 benchmark leakage 或 hidden supervision 问题。若从机制归因看，增益来源几乎完全是结构利用：separable constraints + strong duality + strong concavity，而不是更强计算或经验调参。
Relation To Prior Work
最接近的两条线是：一是 convex-concave minimax 的一阶方法，如 mirror-prox、extragradient、optimistic gradient、primal-dual saddle 方法；二是 functional constrained convex minimization 的 ALM/linearized ALM/inexact PALM。本文实际属于第二条线向 minimax value-function setting 的扩展，而不是第一条线的直接延伸。
和一般 constrained minimax 工作相比，本文的本质差异是避开 coupled constraints。Lu-Mei 2025、Goktas-Greenwald、Dai-Wang-Zhang 等处理更一般或不同类型的约束，但复杂度和可解性都更复杂；Tsaknakis-Hong-Zhang 已指出 coupled constrained minimax 可出现 intractability。本文的创新不是覆盖更一般约束，而是识别出 separable functional constraints 下可恢复 convex optimization-like complexity。
和 Yang-Li-Lan 2025 的 expectation constrained minimax 相比，本文利用 deterministic smoothness、strong concavity 和 ALM 结构，把复杂度从 O(ε^{-2}) 型改善到 Õ(ε^{-1})/Õ(ε^{-3/2})。这不是单纯改进常数，而是 oracle 模型和结构假设不同导致的复杂度阶差异。
看似新的部分中，PALM、APG、augmented Lagrangian 都不是新思想；实质创新在于 reformulation + inexact gradient complexity accounting，尤其是证明从 reformulated problem 的 approximate stationarity 能推出原 minimax 的 ε-KKT 与 primal ε-optimality。
Dataset / Evaluation
这是一篇优化理论论文，基本没有实验评估。文中给了两个 motivating applications：带公平约束的 AUC maximization，以及 robust portfolio selection。这些例子用于说明模型形式覆盖实际问题，而不是用于验证算法性能。
因此 evaluation 的支撑范围是理论复杂度而非 empirical scalability。定理确实验证了核心 claim：在给定结构假设下可以得到 first-order oracle complexity；但没有验证实际运行中三层嵌套是否比直接 primal-dual/penalty 方法更快，也没有展示在大规模机器学习或金融实例中的常数是否可接受。
应用例子本身有一定代表性，但不构成跨场景实证。尤其 robust portfolio 中 ϕ(λ) 的 smoothness 还需要额外非退化或 smoothing 条件，说明实际建模到论文假设之间仍有距离。文中未充分说明算法在这些应用上的数值表现。
Limitation
第一，假设很强。compact domains、Slater condition、prox_g/prox_h 可计算、p/c smooth convex、F smooth convex-concave，以及强凹或人为强凹正则化，都是复杂度证明不可缺的条件。若内层无强凹，论文只能通过 ν-regularization 间接处理，y 侧复杂度退化。
第二，方法只适合 separable constraints。若约束是 q(x,y)≤0，强对偶化不能简单地局部消除 y 约束，且问题可能本身不可 tractable。本文的 generality 上限就在这里。
第三，复杂度常数可能很大。u/z 界依赖 Slater margin p_feas、c_feas；当可行域接近退化时，理论界会恶化。L_Ψ 含 1/μ_F，y-oracle 复杂度含 1/√μ_F；弱强凹或正则化很小都会显著拖慢。
第四，算法是多层嵌套。外层 PALM、内层 iAPG、最内层 y maximization，每层都有 line-search 和递减误差要求。理论上是 first-order，但实际部署时 stopping criterion 和误差预算可能很难调。这里有把原问题困难“转移”到高精度 inner solves 的风险。
第五，凸-凹情形的 ε^{-3/2} 可能不是问题本质下界。作者也承认未知是否可改进到 Õ(ε^{-1})。当前结果更像强凹化 reduction 的自然产物，而不是针对非强凹结构的最优算法。
Takeaway
- 1. 最值得记住的是 reformulation：对 inner functional constraints 使用强对偶/增广对偶化，把 constrained max value function 变成可通过无约束强凹 max 近似求梯度的 Ψ(x,u)。
- 这个技巧可迁移到其他 separable constrained value-function optimization。
- 2. 对这类问题，真正的复杂度瓶颈不是外层 ALM，而是如何控制 inner oracle 的误差与乘子增长。
- 乘子有界性是嵌套一阶方法能否有总复杂度的分水岭。
一句话总结
这篇论文把分离式函数约束 convex-(strongly)-concave minimax 通过内层强对偶化转成带 inexact value-gradient 的函数约束凸最小化，并用 PALM+iAPG 给出接近最优的一阶复杂度，是 functional constrained convex optimization 技术向结构化 minimax 的一次有效迁移。