精读笔记

Problem Setting

论文标题：Adaptive Proximal Methods for Weakly Convex Optimization with Unknown Parameter: Deterministic and Stochastic Guarantees（arXiv preprint / 2026）。

这篇论文实际处理的是 weakly convex optimization 中一个很具体但经常被掩盖的问题：proximal 方法的可分析性依赖 γρ<1，但 ρ 通常未知。若 γ 选得过小，方法变成过度正则化的保守 prox-point；若 γ 过大，proximal subproblem 可能非凸，prox map 不唯一，Moreau envelope 也不能作为光滑 surrogate 使用。过去很多结果默认知道 ρ，或者要求 Lipschitz / smoothness / composite structure / monotone schedule，从而避开了这个断点。

关键矛盾是：算法需要 γ 足够大以获得有效进展，但理论需要 γ 足够小以保证 subproblem 强凸。更麻烦的是，算法无法观测 safe threshold 1/(2ρ)。随机设置下，这个矛盾被放大：候选点可能是错的，函数下降估计可能 biased/heavy-tailed，算法甚至无法可靠判断一次下降测试是否真实成立。

Motivation

已有路线不够的地方在于，它们大多把“知道一个安全 γ”作为 proximal framework 的前提。parameter-free 方法虽然存在，但常见代价是额外假设：全局 Lipschitz、有界 subgradient、smooth finite-sum、特定 composite structure，或者使用预设 schedule。这类方法没有真正回答：如果只知道函数 weakly convex 且 bounded below，但不知道 ρ，proximal parameter 应如何在线选择？

作者的核心观察是，safe/unsafe boundary 不一定要被算法识别。只要有一个可观测的下降测试，safe step 在足够准确时会自动通过；unsafe step 如果通过，也必须带来可计费的函数下降；如果不通过，则 γ 被缩小并逐渐回到 safe region。也就是说，ρ 不再是一个需要估计的常数，而是一个在分析中定义 good/bad regime 的 latent threshold。

这个动机是合理的：它把 weakly convex proximal 方法和 stochastic adaptive line-search / trust-region 的思想接上了。但这里不是简单移植，因为非光滑 weakly convex 的 γ 不只是 stepsize，而是决定 proximal subproblem 是否强凸的结构参数。

Core Idea

APS 的真正核心是把 proximal parameter selection 变成一个反馈控制问题：每次尝试当前 γ 下的一个 candidate，如果观测下降足够大且 residual 不太小，则接受并增大 γ；否则拒绝并减小 γ。算法不试图估计 ρ，不维护上界，也不做多次 backtracking；每轮只有一次 candidate trial。

这个机制改变了信息流：prior proximal methods 通常先用 ρ 设定理论安全区，再在安全区内证明下降；APS 反过来，只看下降是否发生，由下降测试决定 γ 的方向，而 safe threshold 只在证明中出现。其 inductive bias 是“可验证下降比模型正确性更重要”：在 unsafe regime 中，oracle 可以完全错误，但只要通过下降测试就用函数值预算支付；不能通过就通过 γ dynamics 自动纠偏。

和 prior 的本质区别不是 O(ε^-2) 这个 rate，而是允许 safe/unsafe 混合运行且算法不知道边界。它不像单调 schedule 那样保守，也不像标准 backtracking 那样只朝一个方向调整；bidirectional update 使其理论上可以利用局部较好结构，即局部上更大的 γ 仍能产生下降。

Method

方法上只需要抓住几个机制。

1. Descent-based accept/reject：测试形式是 estimated decrease ≥ σ/2·γ||d||² − slack，并要求 ||d||≥ε_rej。它解决的是 oracle 可能返回无意义 candidate 的问题；尤其在 stochastic case，如果没有 residual safeguard，坏 oracle 返回 y=x 也可能伪装成可接受。

2. Bidirectional γ dynamics：成功后 γ 增大，失败后 γ 减小。它解决的是未知 ρ 下无法预设 safe γ 的问题。成功增大 γ 不是为了理论必要，而是为了避免长期停留在过度保守 regime；失败减小 γ 则保证一旦过 aggressive，会回到 safe side。

3. Safe/unsafe split only in analysis：safe iteration 中，prox gap 控制 candidate 与 true prox 的距离，从而 d 近似 Moreau gradient；unsafe iteration 中完全不要求 oracle 正确，只看是否产生足够下降。这个切分是全文的主要技术组织方式。

4. Log-scale accounting：用 γ 相对 hidden threshold 的 log-distance 计数。safe true iterations 会推动成功，unsafe rejected iterations 会减少 γ，unsafe accepted iterations 消耗函数下降。复杂度本质上来自这个离散势函数与函数值下降的双重预算。

5. Stochastic true iteration：随机设置中把一次迭代是否可靠抽象成 indicator I_k，只要求 conditional probability ≥p。随后用 Azuma/Fuk-Nagaev/Bernstein 控制 true-iteration 数量和累计 difference noise。这是把 stochastic adaptive optimization 的 unreliable oracle 框架搬到 weakly convex prox setting。

Key Insight / Why It Works

最关键 insight 是：无需知道当前 γ 是否 safe，也能证明算法不会被 unsafe regime 拖死。原因有两个不变量。第一，在 safe regime，如果 proximal candidate 足够准确且尚未 stationary，那么 sufficient descent test 必然通过；也就是说 safe+reliable 自动等于 successful。第二，在 unsafe regime，successful step 不能免费发生，它至少带来 h_des 级别的函数下降；由于 f bounded below，unsafe successful 的总数有限。unsafe unsuccessful 则会缩小 γ，帮助回到 safe regime。

这使得算法的复杂度不是依赖“每步都正确”，而是依赖“足够多 safe true steps 出现，并且错误/unsafe 行为可计费”。这个思想比具体常数更重要。它把 weakly convex optimization 中的未知 ρ 问题转化为一个 stochastic process drift 问题：γ 在 log scale 上需要有正漂移，函数值下降负责限制过多 aggressive accepted moves。

真正的核心贡献是 two-regime accounting，而不是 proximal oracle 或 minibatch construction。SPO/SDO 的实现相对标准，更多是为了证明抽象 oracle 可实例化。确定性 O(ε^-2) rate 本身也不是新 rate；新意在于 exact prox 只需 safe calls 正确，unsafe calls 可 arbitrary。

随机高概率结果的理论包装很强，但实际增益需要谨慎看。它不是通过 better stochastic gradient efficiency 获得优势，而是通过更弱 oracle model 和 adaptive γ 获得 robustness。若从 sample complexity 看，raw SDO 的 O(ε^-6) 反而较重。因此这里的价值更偏理论 generality / unreliable oracle robustness，而不是直接的 computational scaling。

所谓“利用 favorable local structure”的说法在理论中只被间接支持：如果大 γ 下 candidate 仍通过下降测试，就会被接受。但文中没有实验证明这种 bidirectional adaptation 在具体问题上显著优于保守 schedule；这部分增益来源不清，可能主要是机制上的可能性而非已验证的实际收益。

Relation To Prior Work

这篇最接近三条谱系：weakly convex proximal / Moreau envelope 方法，parameter-free 或 backtracking proximal 方法，以及 stochastic adaptive line-search/trust-region with unreliable oracles。

与 Davis-Drusvyatskiy / Davis-Grimmer 一类 stochastic weakly convex 方法相比，APS 不把 ρ 作为算法输入，也不要求全局 Lipschitz；但代价是引入 proximal oracle 和 difference oracle，并且 stochastic guarantee 是 Moreau-envelope stationarity。与 prox-linear backtracking 相比，APS 不依赖 composite structure，也不需要 deterministic exact line-search 式评估。与 4WD-Catalyst / adaptive regularization upward 方法相比，APS 的 γ 是双向调节，而不是只把 regularization 增大到足够安全。

看似新的部分中，accept/reject、probabilistic true iteration、high-probability martingale 分析都来自已有 stochastic adaptive optimization 谱系；实质新增在于把这些思想嵌入 weakly convex proximal setting，并处理 γ 穿越 unknown safe boundary 后 proximal theory 失效的问题。也就是说，创新不是发明了一种全新优化 primitive，而是重新组织了 proximal parameter uncertainty 的分析方式。

Dataset / Evaluation

这篇基本是理论论文，没有通常意义上的 dataset / benchmark evaluation。第 6 节给的是 expected-risk objective 下 oracle 的构造：paired minibatch difference estimator 和 stochastic subgradient inner solver。它验证的是抽象 oracle assumptions 的可实现性，而不是算法在真实任务上的 empirical superiority。

因此 evaluation 对核心 claim 的支持是有限的：它支持“存在一类标准 stochastic setting 满足 oracle model”，但没有验证 bidirectional γ adaptation 是否在实际 weakly convex learning / signal recovery 问题中更快、更稳，或是否真的能利用 local favorable geometry。没有跨任务实验、没有真实大规模系统成本比较、没有与 parameter-free weakly convex baselines 的 empirical ablation。若论文声称 practical adaptivity，这部分证据明显不足；若定位为理论 framework，则尚可接受。

Limitation

第一，deterministic setting 的 exact prox on safe calls 很强。对一般非光滑非凸 weakly convex 函数，safe subproblem 虽强凸但未必便宜，exact prox 可能本身就是主要难题。算法把未知 ρ 的问题解决了，但把计算负担放到了 proximal oracle。

第二，stochastic setting 虽允许 heavy-tailed biased difference estimates，但仍需要 ϵ_f 相对 h_des=Θ(ε²/ρ) 足够小，否则 p>p0 失败，目标精度存在下限。用普通 minibatch 控制这个 bias/absolute error 会导致每轮 Θ(ε^-4) 样本，整体 SDO sample complexity Θ(ε^-6)。这在实际 stochastic optimization 中可能不具竞争力。

第三，stationarity guarantee 在 deterministic 与 stochastic 情形不一致：前者给 dist(0,∂f)≤ε，后者给 ||∇f_{\barγ}||≤ε。后者是标准但更间接，而且依赖分析中的 \barγ=1/(2ρ)，算法虽不知道 ρ，但 guarantee 本身仍以 unknown reference envelope 表述。

第四，bidirectional update 的实际收益文中未充分说明。理论保证允许 γ 上下漂移，但没有证明它比 monotone schedule 有更好的 worst-case order，也没有 empirical evidence 显示更好的常数或局部适应性。所谓 exploit favorable local structure 在当前文本中更像直觉，而非被系统验证的结论。

第五，oracle independence / conditional probability / moment assumptions 虽然形式弱，但在真实 ML loss 中是否 uniform over adaptive queries 成立并不轻松。尤其是 paired difference 的 q-th moment uniform bound 和 proximal subproblem 的 growth condition，可能在非 Lipschitz、heavy-tailed data 下仍是实质限制。

Takeaway

• 1. 最值得迁移的 insight 是：未知结构常数不一定要估计，可以作为 hidden regime boundary，只用 observable progress 做在线控制，并在分析中分别计费 good regime 与 bad regime。
• 2. 对 weakly convex proximal 方法，γ 的自适应不应只做 conservative backtracking；双向更新能在理论上兼顾安全回退与局部放大步长，尽管实际收益仍需验证。
• 3. 这篇推动的是理论 robustness：oracle 可以在 unsafe regime arbitrary、在 safe regime 只需常数概率可靠，仍能给 high-probability hitting time。
• 这对设计 unreliable-oracle optimization framework 有参考价值。

一句话总结

这篇论文把 unknown-ρ weakly convex proximal optimization 从“先估计安全参数”改写成“用下降测试在线控制 proximal 参数并对 safe/unsafe 行为分别计费”的 adaptive-oracle 理论框架，核心贡献在分析机制而非新的求解器。