精读笔记
Problem Setting
这篇论文实际处理的是标准 primal-dual SDP 上 PDHG 的局部收敛机制。不是问 PDHG 能不能收敛，也不是问 ergodic residual 有多快，而是问：当迭代已经靠近某个 KKT 点后，什么几何条件会把一阶方法从全局慢速区间带入线性区间。
困难点在 PSD cone 的非多面体性。LP 中 active set 一旦识别，投影是 piecewise affine，Hoffman error bound 给了天然 sharpness；SDP 在零特征值处的投影不是分段仿射，零特征空间会产生曲率和非线性慢方向。关键矛盾是：PDHG 的 resolvent 结构本身给了非扩张和下降，但这不足以给线性率；线性率必须来自 KKT 点附近的额外几何 regularity。
Motivation
已有路线的缺口很明确。全局 PDHG 理论只给 sublinear 复杂度，无法解释高精度阶段的线性衰减；LP 的两阶段理论依赖多面体结构，遇到 SDP 的奇异谱块就失效；ADMM for SDP 虽然已有局部线性理论，但它分析的是 Douglas-Rachford/ADMM operator，不是 PDHG 的 primal-dual resolvent。
作者的核心观察是：PDHG 的局部行为应该由“算法度量中的 resolvent 下降”与“PSD cone/KKT mapping 的局部误差界”共同决定。缺的不是新算法，而是一个能把 SDP 的谱几何和 PDHG fixed-point map 对齐的局部理论。
Core Idea
论文的核心思想是换建模方式：不把 PDHG 当作普通 primal-dual gradient iteration，而是当作 reduced KKT inclusion 的 P-metric preconditioned proximal point method。这样算法本身提供 firm nonexpansiveness 和 descent inequality，收敛率问题转化为：在极限 KKT 点附近，fixed-point residual 是否能控制到解集或解点的距离。
严格互补和 primal-dual nondegeneracy 是两条不同的 regularization 路线。严格互补让 Z*=X*−τS* 没有零特征值，PSD 投影在该点附近光滑，于是可以线性化 PDHG map，并证明切向方向正好是 KKT manifold，法向方向被压缩。非退化不要求投影光滑，而是通过 KKT mapping 的 strong metric subregularity 直接给 error bound。这是和 prior 的本质区别：不是把 LP 的 active-set 证明硬搬过来，而是把“局部线性率”重新组织为 resolvent descent + cone/KKT regularity。
Method
第一，P-metric resolvent 表示解决的是“用哪个度量看 PDHG 才是下降方法”的问题。P 的 block 结构吸收了 A 和步长耦合，使 PDHG 等价于 0 ∈ F_KKT(z_{k+1}) + P(z_{k+1}−z_k)。核心变化是把算法分析从欧氏迭代变成 monotone inclusion resolvent 分析。
第二，严格互补分支解决的是 PSD 投影不可微的问题。若 X*+S* 正定，则 Z*=X*−τS* 非奇异，投影 Π_{S_+} 在局部可微。作者利用投影微分中的谱权重 Θ∈(0,1)，证明 fixed directions 恰好等于 local KKT manifold 的切空间；非切向分量在 P-正交意义下收缩。这里真正关键的是“法向收缩”，不是 rank identification 本身。
第三，非退化分支解决的是不想依赖投影光滑时如何得到线性率。primal-dual nondegeneracy 等价/导出 KKT mapping 的 strong regularity/strong metric subregularity，于是 residual 控制距离。结合 resolvent 的 firm nonexpansiveness，直接得到到唯一 KKT 点的 Q-linear contraction。
第四，反例的作用不是 benchmark，而是说明缺 regularity 时 PSD 投影的零谱非线性可以产生慢流形。局部归约 α_{+}=α−α^3+O(α^5) 很有信息量：这说明慢速不是 proof artifact，而可能是 SDP cone 曲率真实引入的局部动力学。
Key Insight / Why It Works
最重要的 insight 是：PDHG 的线性收敛不来自“算法更聪明”，而来自局部 KKT 几何把 resolvent 的非扩张升级成收缩。PDHG 本身只保证不会扩张；严格互补或非退化提供缺失的 sharpness/error bound。
严格互补下，真正起作用的是 signed matrix Z*=X*−τS* 的 spectral gap。这个 gap 让 PSD projection 局部像一个光滑谱函数，避免零特征块导致的非线性退化。投影微分里的 off-block 权重 Θ 在 (0,1) 内，这使得混合正负谱空间的方向被严格削弱；而保持不变的方向正是沿着 KKT manifold 移动的切向自由度。因此，若解不孤立，只能得到到解流形的 R-linear；若解局部孤立，才变成到点的 Q-linear。
非退化下，核心贡献是把 strong metric subregularity 接到 PDHG residual 上。这里最干净：P(z−Rz) 是 KKT residual 的一个 admissible element，error bound 给 ||Rz−z*|| ≤ μ||z−Rz||，firm nonexpansiveness 给 Pythagorean-type descent，两者合并就是 contraction。这个证明机制比严格互补分支更抽象，也更接近 proximal point theory。
rank identification 是有价值的附带 insight，但不是线性收敛的根因。它依赖 spectral gap，说明 X_k 的 rank 会有限步稳定；但论文也明确给出 dual slack S_k 不一定 rank-stabilize。更重要的是，rank 已识别后仍可能缺少收缩/误差界，因此不能把 SDP 中的线性阶段简单类比成 LP 的 basis identification 后线性阶段。
这篇没有 scaling、data coverage、retrieval、hidden supervision 这类机器学习式增益来源。它的贡献主要是 better local geometric bias：选择了正确的变量 Z、正确的 P-metric、正确的 KKT regularity，把已有 variational analysis 工具接到了 PDHG 的动力学上。可能比较 engineering 的部分只在实验：步长选择、实例缩放、停止标准会影响观察到的线性区间，但不是理论增益来源。
Relation To Prior Work
最接近的三条线是 PDHG for LP、ADMM for SDP、proximal splitting 的 error-bound/metric-subregularity 理论。
和 LP 的本质差异在于：LP 的锥是多面体，投影 piecewise affine，active set 后局部动力学天然线性；SDP 的 PSD cone 在零特征值处有曲率，投影可能产生 α−α^3 这类慢动力学。所以本文不是 LP 结果的直接推广，而是在非多面体锥上找替代 regularity。
和 ADMM for SDP 的差异在算法变量和度量。ADMM 分析通常在 signed matrix Z 和 Douglas-Rachford operator 上做，度量更接近 Frobenius/投影到 Range(A*)；本文的 PDHG map 作用在 (X,y)，自然度量是 P。两者共享“PSD projection 局部谱几何 + fixed space/normal contraction”的思想，但收缩分解和 residual 估计是算法特定的。
看似新的部分有不少是已有 variational analysis 的重组：strong regularity、metric subregularity、strict complementarity、partial smoothness 都不是新概念。实质创新在于把这些条件精确接到 PDHG resolvent 上，并给出严格互补下的局部线性化/fixed-direction 识别。这是理论组织上的贡献，不是新优化算法。
Dataset / Evaluation
实验覆盖了几类 SDP：MaxCut、quartic-over-sphere relaxation、synthetic non-SC but ND、structure-from-motion，以及若干困难实例。覆盖面足以支持“不同正则性 profile 下可观察到局部线性行为”这个现象性 claim，也能展示接近严格互补失败时高精度困难。
但 evaluation 主要是理论现象验证，不是 solver competitiveness 评估。没有必要也没有充分证据说明 PDHG 比现有 SDP solver 更好；论文也基本没有声称这一点。实验没有给出系统的 regularity certificate，尤其大规模真实实例上 strict complementarity 多依赖最终 Z 的最小绝对特征值诊断，nondegeneracy 往往不验证。
困难实例的解释仍不完全闭合。残差不降到 1e-8 可能是 contraction factor 接近 1，也可能还没进入局部区间，也可能步长/缩放造成实际慢速。文中未充分说明如何区分这些机制。因此实验支持理论方向，但不构成对必要条件或 sharp rate 的强验证。
Limitation
第一，理论是局部且以后验极限点为条件。Assumption 2/3 都要求 PDHG 已经收敛到满足 strict complementarity 或 primal-dual nondegeneracy 的 KKT 点；全局进入该区域的时间、极限点选择机制、多个 KKT 点下选择哪个 regularity profile，文中未充分说明。
第二，strict complementarity 和 primal-dual nondegeneracy 是充分条件，不是精确边界。论文有一个退化 sublinear 例子，但它没有证明“二者都失败必然非线性”，也没有给出统一的 necessary-and-sufficient condition。真正的边界很可能是 PDHG fixed-point map 相对于 local solution set 的某种 metric subregularity/second-order spectral condition。
第三，严格互补分支依赖投影可微性和 fixed face structure，因此对接近零谱 gap 的实例很脆弱。gap 很小时理论仍可能成立，但 contraction factor 可以接近 1，局部区间也可能非常小；这正是实验中困难实例的可能来源。
第四，步长条件限制在 τσ||A||^2<1 和 fully extrapolated PDHG，因为证明强依赖 proximal point interpretation。更宽的 relaxed PDHG 参数区间不被覆盖。这里增益来源不清：实践中更激进步长或缩放可能显著影响进入局部区间的速度，但理论没有解释。
第五，反例的 sublinear 结论是 formal local reduction 加数值证据，不是完整 invariant manifold 证明。它非常有启发性，但严格性仍低于主定理。
Takeaway
- 1. 对 SDP 上的一阶 primal-dual 方法，局部线性率的核心不是全局复杂度，而是极限 KKT 点附近 PSD cone 的谱几何和 KKT mapping 的 error bound。
- 2. strict complementarity 和 primal-dual nondegeneracy 是两种不同机制：前者让投影局部光滑并产生法向收缩；后者直接给 strong metric subregularity。
- 它们不应被混成一个“regularity assumption”。
- 3. SDP 和 LP 的两阶段图景不能简单类比。
一句话总结
这篇论文把 PDHG for SDP 的高精度局部行为从“经验上有时线性”提升为“resolvent 下降 + SDP KKT 几何 regularity 导致线性收缩”的理论框架，是 PDHG 从 LP 多面体理论走向 SDP 非多面体谱几何理论的一步。