精读笔记
Problem Setting
论文研究 stochastic variational inequality：求 x*∈X 使 <H(x*),x-x*>≥0，其中 H=E[T(ξ,x)] 只能通过采样访问。关键不是 SVI 本身，而是只假设期望算子 H 在 X 上伪单调，T(ξ,·) 以及算法实际用到的 sample average operator 都可以不是伪单调。
这点决定了分析难度：标准伪单调 VI 的 extragradient 下降依赖于 H 的结构，但算法每一步实际看到的是 H_{ξ^k}, H_{η^k}。因此不能简单把 sampled problem 当成 deterministic pseudomonotone VI，也不能直接套确定性 Anderson-accelerated VI 的分析。
以前方法主要卡在两处：一是 stochastic extragradient 可以处理伪单调 H，但加速机制较弱；二是 Anderson acceleration 在 fixed-point / deterministic VI 中有效，但随机环境下外推会放大 oracle noise，且外推点不一定保留 Fejér 下降。本文的关键矛盾是：想利用历史信息加速，但又不能让历史噪声破坏随机近似收敛。
Motivation
已有 SA/SEG 路线的理论比较稳，但迭代保守，尤其在伪单调而非强单调场景只能给子线性 residual 收敛。SAA 路线则把问题转成大规模 deterministic VI，样本量大时计算与存储不友好。
作者的核心观察是：SVI 可看成 fixed-point residual r_t(x)=||P_X(x-tH(x))-x|| 的求零问题，而 Anderson acceleration 本质上是在 fixed-point residual 上做低维历史外推。既然 deterministic pseudomonotone VI 中已有 extragradient + Anderson 的成功尝试，那么自然问题是：能否把这种 memory reuse 放进 stochastic extragradient，同时只要求 H 伪单调？
关键缺口在于理论：sample average operator 不伪单调时，Anderson 步不能被解释为对某个 sampled VI 的合法加速。论文要补的是一个“sample operator 无结构，但 expectation 有结构”的收敛证明框架。
Core Idea
真正核心思想是把 Anderson(1) 从“加速 fixed-point 迭代的主更新”降级为“有保护的候选外推”。每轮先执行随机 extragradient，得到一个标准 SEG 候选 y_{k+1}；然后根据 residual 下降与阈值条件决定是否使用 Anderson 型组合 x_{k+1}=α_k x_k+(1-α_k)y_{k+1}。如果条件不满足，则完全退回 SEG。
这改变了 Anderson 在算法中的角色：它不是理论递推的主引擎，而是一个被接受准则约束的扰动项。证明中真正维持收敛的是 SEG 的伪单调下降结构和 sample error 的可求和控制；Anderson 只要不破坏这个 almost-supermartingale 结构即可。
与 prior 的本质区别是：确定性 Anderson-VI 可以依赖实际 operator 的伪单调性；这里不能。本文把所有 sampled-operator 的非结构性都视为 oracle error，并通过增长 batch、独立双采样、BDG 型矩界和阈值衰减来吸收。
Method
关键机制有四个。
1. 双采样 stochastic extragradient：ξ^k 用于中间投影 y_{k+1/2}，η^k 用于第二次投影 y_{k+1}。它解决的是 stochastic extragradient 中条件期望解耦的问题，使第二阶段 oracle error ε_2^k 相对合适的 filtration 成为 martingale difference。没有这个独立性，核心误差项很难闭合。
2. 随机线搜索：用 sampled operator H_{ξ^k} 检查 t_k ||H_{ξ^k}(x_k)-H_{ξ^k}(y_{k+1/2})|| ≤ μ ||x_k-y_{k+1/2}||。它解决未知 Lipschitz 常数问题，同时在分析里提供一个局部 cocoercive-like 控制，把 extragradient 的交叉项压到 -(1-3μ^2)||x_k-y_{k+1/2}||^2。
3. Anderson(1) 受控外推：当 ||y_{k+1}-x_k|| 同时小于第一步 residual 和 νθ_k^{-τ} 时，计算 α_k 并做线性组合；否则退回 SEG。这个机制解决的是 Anderson 可能过冲和放大噪声的问题。阈值 νθ_k^{-τ} 的作用不是调参，而是让 Anderson 步带来的额外误差 ρ_k 可求和。
4. 增长 batch schedule：要求 ∑ 1/√S_k < ∞。这是收敛证明的实际支柱之一，因为所有 sample error 在递推中以 1/√S_k 进入。没有足够快的 batch 增长，almost-supermartingale 条件不成立。
Key Insight / Why It Works
最重要的 insight 是：在随机伪单调 SVI 中，不需要 sampled operator 本身伪单调；只要能把 sampled update 写成“期望伪单调 extragradient 下降 + 可求和噪声 + 可求和 Anderson 扰动”，就可以通过 Robbins–Siegmund 收敛。
具体来说，Lemma 3.3 是核心下降关系：对 SEG 候选 y_{k+1}，利用 H 的伪单调性而不是 H_{ξ^k}/H_{η^k} 的伪单调性，得到关于 ||y_{k+1}-x*||^2 的下降，其中 sampled operator 只作为 ε_1, ε_2, ε_3 出现。随后 Lemma 3.4 把 Anderson 更新纳入同一个递推，但代价是引入 M、β_hat 和 ρ_k。也就是说，Anderson 并未贡献新的 Lyapunov 结构；它只是被证明不会破坏原有结构。
真正有效的理论机制是三者叠加：extragradient 负责处理伪单调；line search 负责把未知 Lipschitz 变成可用局部不等式；batch growth 负责让噪声可求和。Anderson 的理论地位相对弱：它是经验加速器，在证明里主要体现为 bounded perturbation / memory reuse，而不是带来更好阶数。
因此，这篇论文的核心贡献更偏“把 Anderson 安全接入 stochastic pseudomonotone SEG 并证明不崩”，而不是“证明 Anderson 在随机 SVI 中有本质复杂度加速”。速率仍是 O(1/N)，oracle complexity 的主导项来自 S_k 增长。所谓 acceleration 的增益来源不清，实验上可能来自 Anderson memory reuse，也可能来自接受准则带来的隐式 restart / damping，或者只是某些实例中 SEG 本身较慢。
Relation To Prior Work
它最接近三条线：Iusem et al. 的 stochastic extragradient for pseudomonotone SVI；variance-based SEG with line search；以及 Qu et al. 的 deterministic extragradient Anderson acceleration for pseudomonotone VI。
相对 Iusem/variance-based SEG，新增的是 Anderson(1) 外推与接受机制。但理论阶数没有改善，主要是经验迭代数减少。相对 deterministic Anderson-VI，实质差异是 sampled operators 不需要伪单调，证明不能沿用 deterministic operator 的结构，只能走 stochastic approximation + martingale error control。
看似新的部分中，line search、双采样、BDG 控制、Robbins–Siegmund 递推都是已有 SA/SEG 理论组件；真正新增的信息是如何把 Anderson 外推包装成可求和 perturbation，并在非伪单调 sample operator 下维持残差下降。
所以它属于“robustified Anderson acceleration for stochastic operator problems”这条谱系，而不是新的 VI 复杂度理论。它更像把一个实践中有效的 acceleration heuristic 放入严格 SA 框架。
Dataset / Evaluation
实验覆盖了两个合成 SVI / stochastic complementarity 类问题，以及一个真实金融数据上的 Markowitz portfolio selection 应用。对照主要是带同类 line search 的 SEG。
实验基本支持一个窄 claim：在这些设置下，Anderson(1)-SEG 往往比 SEG 更少迭代、更少 CPU 时间。尤其在 fractional convex quadratic 示例中差距较明显，说明 memory reuse 对某些平滑伪单调问题确实有用。
但 evaluation 对核心理论 claim 的验证有限。首先，实验中还使用了不满足理论 Assumption 3 的较小 batch schedule，并观察到仍可工作，这很有价值，但也说明理论条件可能偏保守。其次，没有充分 ablation：缺少固定 line search + 无 Anderson、不同接受阈值、不同 M/ν/τ、固定 batch 与增长 batch 的系统分解。因此增益归因不清。
portfolio 部分更像应用展示，不是严格验证 SVI 算法优势。与 naive equal-weight portfolio 比较门槛较低，缺少与标准 convex QP solver、projected gradient、SAA solution、或金融上常见 regularized portfolio baseline 的对照。它说明算法能跑真实数据，但不能证明金融决策优势来自 Anderson-SEG 本身。
Limitation
第一，理论依赖强 batch growth：∑1/√S_k<∞ 意味着 S_k 至少近似 k^2 log^{2+}k 级别。这样每轮 oracle 成本快速增大，实际 scalability 上限会受样本成本支配。论文给出 oracle complexity，但 Anderson 对这个复杂度没有本质改善。
第二，Anderson 的“加速”没有理论速率体现。最终 residual rate 仍是 O(1/N)，和 SEG 系列同阶。证明策略实际上把 Anderson 当作 bounded perturbation，而不是利用其多步拟牛顿/GMRES-like 性质。因此理论上它证明的是安全性，不是加速性。
第三，接受准则可能过于保守且依赖超参数。M、ν、τ、μ、ρ 的选择影响 Anderson 步频率与稳定性，但论文没有充分解释这些参数如何影响性能。实验中括号里的 Anderson step 数显示并非每步都接受；哪些情况下 Anderson 真正被触发、触发后贡献多少，文中未充分说明。
第四，样本算子不伪单调虽然是亮点，但代价是较强矩条件与 Lipschitz random modulus 假设。对于 heavy-tailed stochastic oracle 或非全局 Lipschitz operator，当前证明不直接适用。
第五，portfolio 实验的结论不能过度解读。Naive baseline 太弱，且金融 out-of-sample 表现易受数据切分、资产筛选和约束设定影响。所谓更好 SR/AR 可能主要来自 Markowitz 模型本身，而不是算法 superiority。
Takeaway
- 1. 这篇论文最值得记住的是一种分析模板：把随机 Anderson 外推视为可控扰动，而不是试图证明 sampled Anderson step 本身下降。
- 2. 对 stochastic VI / stochastic fixed-point 问题，若只在 expectation 层面有结构，算法设计应优先保证 filtration 解耦、误差可求和和 fallback 稳定性；加速器必须被安全门控。
- 3. Anderson 在随机优化中的理论化可能不会先表现为更好 worst-case rate，而是表现为“不破坏收敛 + 实践减少迭代”。
- 这类结果的下一步应是解释何时 Anderson step 被接受、它与局部线性化谱性质的关系，而不是继续堆经验结果。
一句话总结
这篇论文把 Anderson(1) 作为受控 memory-reuse perturbation 安全接入 stochastic extragradient，首次在仅期望算子伪单调、样本算子无伪单调性的 SVI 中给出几乎必然收敛和 O(1/N) residual 理论，但其“加速”主要仍是经验层面的。