精读笔记

Problem Setting

这篇论文真正解决的是 derivative-free nonsmooth optimization 中“如何把函数值采样转化为可用于下降和停机的近似一阶结构”。目标函数只假设局部 Lipschitz，可能非凸、非光滑，无法访问梯度、子梯度或 active-index 信息。关键矛盾是：非光滑优化需要某种 generalized first-order 信息来判断 stationarity 和构造下降方向，但 derivative-free 场景只能通过函数值间接估计；估计过少则方向不可靠，估计过多则采样成本爆炸。以前两类路线各有瓶颈：MADS/polling 类方法理论稳健但方向使用较保守；离散梯度/gradient sampling 类方法能更主动利用局部结构，但模型质量、采样稳定性和方向生成策略决定了上限。本文切入的是后者：不是放弃近似子梯度，而是把近似子梯度模型做成 Goldstein-style stationarity proxy，再在其上引入 memory-enhanced search direction。

Motivation

作者的核心动机不是重新定义 stationarity，而是认为现有 DFNO 中“模型”和“方向”的连接太保守。离散梯度可以给出一批近似子梯度，凸包最小范数可以给出 Goldstein stationarity residual，但如果搜索方向始终接近 -v_k，本质仍是局部 steepest descent，容易在高维或非光滑折面结构中低效。另一方面，光滑优化中的 CG/Quasi-Newton 思想证明了历史方向复用可以显著改善搜索效率，但传统 CG 的 scalar beta 在 nonsmooth derivative-free 场景没有直接可用的一阶信息基础。本文看到的缺口是：需要一种能利用离散梯度模型、又能复用历史搜索信息、同时不破坏下降性的方向机制。矩阵参数的提出就是为了给 CG correction 更大的表达自由度；但这也是风险点，因为在近似子梯度上谈“conjugacy”很弱，必须靠 safeguard 把方向重新约束回可信区域。

Core Idea

核心思想可以概括为：先用函数值采样构造有限离散梯度集合，把其凸包当作 Goldstein 子微分的可计算近似；再求该凸包中离原点最近的向量 v_k，用 ||v_k|| 作为 stationarity residual，并用 v_k 给搜索方向提供局部一阶锚点。这个步骤把非光滑的一阶信息从“单个差分方向”提升为“局部子微分模型”，避免把某个 noisy finite difference 误当成梯度。

真正区别在方向层：论文不直接使用 -v_k，而是用 MatCSG 方向 -v_k + B_k d_{k-1}，其中 B_k 是稀疏/结构化矩阵记忆项。直觉上，这相当于在非光滑近似子梯度空间里加入一个 limited-memory transport：v_k 决定当前下降锥，B_k d_{k-1} 复用历史方向以获得更长程的搜索惯性。为了防止历史项把方向带离下降区域，作者再用 bounded-angle correction 把方向投影/平移回与 v_k 形成足够负夹角的位置。因此，方法的 inductive bias 是“局部 Goldstein 模型给可靠性，矩阵记忆给效率，角度 safeguard 给收敛性”。

Method

方法中真正必要的机制有四个。第一，离散梯度构造解决 derivative-free 下无法访问子梯度的问题；它通过多点函数值差分生成近似子梯度，但其成立依赖额外正则性和一致性，不是局部 Lipschitz 自动保证。第二，凸包最小范数 QP 解决 stationarity 度量问题；它把一组采样向量压缩为 v_k，使停机准则和方向锚点都来自同一个 Goldstein-style 模型。第三，MatCSG direction 解决 steepest-descent 信息利用不足的问题；矩阵 memory correction 比 scalar beta 有更高自由度，理论上可表达坐标间不同尺度和历史方向交互，但在本文中更像 safeguarded heuristic，而不是严格的非光滑共轭机制。第四，two-point line search with enrichment 解决模型失配问题；如果当前方向不能产生足够下降，就不只是缩步，而是返回新的离散梯度加入模型，从而把失败样本转化为 Goldstein 模型补充。bounded-angle correction 是整个方向机制的安全阀：没有它，矩阵记忆项很容易摧毁下降性。

Key Insight / Why It Works

最重要的 insight 是把“失败的 line search”解释为“当前子微分模型覆盖不足”，而不是单纯的步长问题。对于非光滑函数，沿某方向不下降往往意味着局部存在未采到的 active piece 或 Clarke subgradient；two-point enrichment 正好把这些信息补回凸包模型。这个机制比单纯 finite-difference descent 更接近 gradient sampling/bundle 的精神，也是理论能闭合的关键。

真正可能有效的部分有两个：一是最小范数凸包模型，它给出比单个离散梯度更稳定的 stationarity 和方向参考；二是 line-search enrichment，它让模型在下降失败时自我修正。矩阵 MatCSG 可能改善高精度阶段的搜索效率，但其独立贡献没有被充分剥离。论文中的 diagonal scaling、coefficient damping、dominance control、matrix-stability safeguards 很可能贡献了大量工程稳定性；高精度优势可能不完全来自“matrix conjugacy”。更直接地说，核心能力主要是 better local model + memory reuse + aggressive safeguarding 的组合，而不是一个干净的共轭梯度理论突破。

从机制归因看，这不是 retrieval、data coverage 或 latent representation 类方法；它更像 test-time compute 与 local model refinement 的优化算法版本。采样越充分，Goldstein 模型越可信；enrichment 越有效，方向越接近真实非光滑下降结构；memory correction 越稳定，越可能减少局部 zig-zag。上限也很清楚：如果离散梯度一致性差、采样方向覆盖不足、函数噪声高，整个 stationarity residual 可能只是模型内 stationarity，而不是真实 Clarke stationarity。

Relation To Prior Work

它最接近三条谱系的交叉：离散梯度方法 DGM/LDGB/DDG-Bundle，Goldstein/gradient-sampling/subgradient-enrichment 方法，以及 nonlinear CG / Dai-Liao / matrix-parameter CG。与 MADS/polling 的本质区别是本文显式构造 generalized first-order model，而不是只靠方向集几何密化。与传统离散梯度方法的区别是它把离散梯度集合组织成凸包最小范数 stationarity model，并把 line-search failure 用作模型 enrichment。与 Maleknia 和 Soleimani-Damaneh 的 exact-subgradient framework 的区别是把 exact subgradient sampling 替换成 derivative-free discrete gradients，并额外加入 MatCSG memory direction。

看似新的部分中，Goldstein 子微分凸包、最小范数元素、两点 Mifflin-style line search、enrichment 都是已有思想的重组或 derivative-free 改写。实质新增主要在“用矩阵参数的 CG-like memory correction 生成近似子梯度方向，并用 bounded-angle/matrix safeguards 把它嵌入离散梯度 Goldstein 框架”。不过，文中所谓 matrix conjugacy 在非光滑近似模型下理论含义较弱，更准确地说是 safeguarded matrix memory search，而不是严格意义的共轭子梯度法。

Dataset / Evaluation

评估使用有限最大值 nonsmooth 测试环境，包含真实数据生成问题和合成大规模问题，维度到 1000，比较对象包括 DGM、LDGB、DDG-Bundle 等相关 DFNO solver。这个 benchmark 能验证一件事：在 finite-max、局部 Lipschitz、相对结构化的 nonsmooth 测试集上，提出方法尤其是 MatCSG variant 在固定函数评估和时间预算下有较好 robustness。

但 evaluation 对核心 claim 的支撑仍有限。首先，所有问题基本围绕 finite-max 结构，这与一般黑箱非光滑函数、噪声函数、仿真型目标之间有距离。其次，性能 profile 说明“整体 solver 变强”，但不能说明增益来自矩阵参数；因为 scaling、safeguards、line-search enrichment、采样策略都同时存在。第三，f_opt 来自 hitlist/best-known reference，只是 benchmarking metric，不影响公平性但限制了实际部署解释。第四，缺少足够消融来排除“可能主要来自 scaling / data / benchmark structure”的解释。

Limitation

最大理论限制是条件强：离散梯度近似 Clarke/Goldstein 子微分需要额外正则性、semismooth-like 假设和采样一致性；A5 的方向模型误差要求在实际算法中并不可直接验证。也就是说，理论保证不是“任意局部 Lipschitz 黑箱函数上成立”，而是“在离散梯度模型足够一致且采样误差消失时成立”。

scalability 上限也明显。每个离散梯度可能需要 O(n) 级函数调用，凸包最小范数 QP 随采样数增长，enrichment 在困难区域可能频繁触发。虽然作者强调维度到 1000，但对于昂贵黑箱函数、强噪声仿真或更高维问题，成本可能不可接受。矩阵参数若不是强结构化/limited-memory，也会迅速变成负担。

增益归因不清是最关键的实证限制。MatCSG 高精度更稳可能来自 memory reuse，也可能来自 diagonal scaling、bounded-angle correction、damping、dominance control、matrix stability checks 或测试集与 finite-max 模型的适配。文中未充分说明各 safeguard 的必要性和独立贡献。所谓 matrix conjugate-subgradient 的理论新意也偏弱：最终下降性主要由 angle correction 保证，而不是由矩阵共轭结构自然产生。

Takeaway

• 第一，DFNO 中值得迁移的核心不是矩阵 CG 公式本身，而是“stationarity model 与 search direction 解耦”：用凸包最小范数模型判断局部非光滑 stationarity，再允许方向层加入 memory 或 scaling，只要最后用角度条件保护。
• 第二，line-search failure as model enrichment 是一个强 insight：非光滑优化里失败样本常常是缺失子梯度信息，应被纳入局部模型，而不是简单丢弃。
• 第三，未来真正值得做的是低成本采样、adaptive model management 和消融清楚的 memory mechanism，而不是继续堆 safeguard。
• 第四，这篇工作推动的是离散梯度方法向“model-based + memory-enhanced + safeguarded”方向演化，但还没有证明矩阵参数本身是不可替代的核心。

一句话总结

这篇论文把离散梯度 Goldstein 子微分模型、两点 enrichment 和 safeguarded matrix-memory 搜索方向组合成一个 derivative-free nonsmooth solver，真正贡献在于把近似子梯度模型与历史方向复用系统化连接，而非单独提出了一个干净的新共轭理论。