有限和单调包含问题的最优预言机复杂度

基于摘要分析。研究针对均方 Lipschitz 连续条件下的有限和单调包含问题，提出 switching regularization 方法，通过在不同正则化阶段切换求解机制，降低分量评估开销，并给出特定预言机模型下匹配的复杂度下界。 核心机制是在正则化强度达到 L/√n 时，切换为 centered stochastic proximal iteration，避免每个正则化阶段重新启动方差缩减求解器带来的额外 n log n 开销。作者报告，通过在后续阶段之间传递算子估计，可将这些阶段的总成本限制为 O(n)。具体更新公式、估计维护方式及参数选择尚未验证。 作者报告，该方法找到点 y 及证书 g∈G(y)，满足 (E‖F(y)+g‖²)¹ᐟ²≤ε，所需期望分量评估次数及 resolvent 评估次数为 O(n+√n LR/ε)。匹配的 Ω(n+√n LR/ε) 下界针对允许自适应停止、采用期望查询预算的随机线性张成分量预言机算法。因此，在 0<ε≤LR/2 时，作者报告其最坏情形期望分量复杂度在该模型内达到最优，差异仅为通用常数；这一结论不应扩展为任意算法或实际运行时间的最优性。n、L、R 的严格定义及完整假设需核对全文。 平台推测（待验证）：若 EEG 研究中的某个优化子问题能够明确写成满足上述条件的有限和单调包含形式，阶段间复用算子估计的思路可能具有参考价值；但不能直接推及一般非凸神经网络训练。是否存在适用的 EEG 问题、相关已有工作及实际计算收益尚未检索确认。证明细节、实验协议、消融及统计信息尚未验证。