精读笔记
Problem Setting
这篇论文实际处理的是 constrained blackbox optimization 中 MADS 的并行执行问题，尤其是 evaluation 昂贵、耗时不均、变量维度可能较高时，如何把现代多核/MPI 资源转化为真实 wall-clock speedup。
真正困难点在于 MADS 的有效性来自严格的 mesh/poll 结构和 opportunistic success 逻辑，而并行化会破坏顺序语义：一旦多个点同时发出，opportunism 不再是“找到一个好点就停止”，而变成至少消耗一批 worker 的 evaluation；如果再遇到时间异质 blackbox，同步 barrier 会让所有 worker 被最慢 evaluation 绑定。
以前方法卡住的地方不是不能并行，而是并行策略与 BBO 的实际成本结构错位。对于昂贵黑箱，evaluation budget 与 time budget 不等价；同步批处理可能 evaluation 数看起来节省，但 wall-clock 被长尾拖垮。关键矛盾是：MADS 需要足够有序的 trial-point 接受机制来保留收敛性质，但高效并行又要求打破 iteration 内的严格同步。
Motivation
已有 MADS/NOMAD 已经提供了可靠的 DFO 框架，约束处理、mesh refinement、poll convergence 都不是本文的主要缺口。缺的是：在 blackbox 不可打开、不能内部并行化的情况下，算法层如何利用外部并行资源。
作者的核心观察很实际：在典型 BBO 中，生成 trial points 的时间远小于 objective/constraint evaluation 时间。因此并行化最值得下手的地方不是模型构建或方向生成，而是 evaluation dispatch、worker idle time、cache reuse 和多轨迹探索。
这也解释了为什么论文没有提出一个新的搜索准则，而是系统整理 pMADS-S、pMADS-A、COOP-MADS、PSD-MADS：它们对应的不是不同数学目标，而是不同瓶颈假设。时间异质时需要异步；多模态时需要多轨迹；高维时需要空间分解；低维昂贵问题则更适合同一轨迹内并行评估。
Core Idea
论文真正的核心不是“把 MADS 并行化”，而是把 MADS 的计算过程重新解释为一组可调度的 blackbox evaluation tasks，并在不破坏 mesh/poll 收敛骨架的前提下改变信息流。顺序 MADS 的信息流是：生成点、评估、判断 success、更新 incumbent。并行版本把这个流程拆开，使 evaluation 可以乱序返回，cache 可以成为异步信息汇聚点，incumbent 可以被后到的旧 iteration 结果修正。
最有价值的思想是 pMADS-A 的异步推进：它把 MADS iteration 的时钟从“整批评估完成”改为“任一 worker 返回有用信息”。这相当于引入 test-time compute scheduling bias：优先利用先完成的 evaluation 推进搜索，而不是等待完整批次。这不是新的 optimization inductive bias，而是更匹配昂贵异质 blackbox 的 execution bias。
COOP-MADS 和 PSD-MADS 则分别改变搜索覆盖方式和变量组织方式。前者用多条独立 MADS 轨迹换取 basin coverage，本质接近 structured multi-start 加 shared memory；后者假设高维问题存在可在低维子空间中被捕获的改进方向，用子空间 MADS 降低 poll 规模并提高并行可分配性。
Method
pMADS-S 解决的是最直接的并行评估问题：在同一 MADS iteration 中把 poll/search 点发给多个 worker。它需要同步 barrier 来保持确定性和简单语义，但核心变化有限，本质是 block evaluation。它适合 evaluation 时间相近的场景，不适合长尾耗时。
pMADS-A 解决的是同步 barrier 导致的 worker idle。它允许 master 在某个 worker 返回 success 后立即更新并推进，同时未完成 evaluation 不取消，后续通过 cache search 处理旧 evaluation 产生的新 incumbent。这个机制的必要性在于时间异质 blackbox 中“等待完整批次”是主要浪费源；核心变化是把 MADS 的状态更新变成异步事件驱动。
COOP-MADS 解决的是单条 MADS 轨迹容易过早落入局部 basin 的问题。多个随机种子实例并行运行，通过共享 cache 避免重复 evaluation。它的关键不是并行 poll，而是并行探索路径；核心变化是用资源换搜索覆盖。
PSD-MADS 解决高维下 poll/search 扩展困难的问题。manager 随机选择变量子空间，把子问题交给 workers；regular workers 在子空间内跑 MADS，pollster 在原空间保留收敛所需的全局 poll 角色。这个机制的必要性来自 MADS 在高维中方向数量和 evaluation 需求膨胀；核心变化是把全维局部搜索替换成异步低维子空间改进。
Key Insight / Why It Works
最核心的有效性来源是调度，而不是更强的数学搜索。pMADS-A 的优势来自消除同步 barrier 后对长尾 evaluation time 的鲁棒性：只要有一部分 evaluation 快速返回并产生 success，算法就能继续推进，worker 不再被最慢任务阻塞。这是典型的 systems-level gain，但在 BBO 中它直接转化为 optimization progress per wall-clock time。
这里的关键不是 parallelism 本身，而是 parallelism 与 opportunism 的兼容方式。顺序 MADS 的 opportunism 节省 evaluation budget；同步并行会削弱这一点，因为一批 evaluation 已经发出；异步并行进一步承认 evaluation 已经不可避免地在飞行中，于是把目标从节省 evaluation 数转成最大化时间利用率。这个视角很重要：在并行 BBO 中，time budget 比 evaluation budget 更自然。
COOP-MADS 的收益更像 data coverage / multi-start coverage，而不是算法能力提升。多 seed 带来更多 basin 采样，共享 cache 避免重复点，这会改善多模态问题上的机会，但如果和同等 evaluation budget 的高质量 restart 策略相比，增益来源不清。
PSD-MADS 的有效性依赖 latent low-dimensional structure：如果目标函数在许多坐标方向上可以被局部子空间改进捕获，那么随机子空间 MADS 能显著改善高维可扩展性；如果变量高度耦合，随机分解可能破坏有效方向，pollster 只能保证理论上不丢失收敛框架，但未必带来效率。
论文最实质的贡献是把 NOMAD/MADS 中已有或半已有的并行形态放在统一机制和实证框架下比较。pMADS-A 是最可迁移的 insight：对 expensive heterogeneous blackbox，异步 evaluation scheduling 往往比更复杂的 surrogate/model 更先成为瓶颈解法。
Relation To Prior Work
这篇工作属于 direct search / pattern search 并行化谱系，最接近 APPSPACK/HOPSPACK 的 asynchronous pattern search，以及已有的 PSD-MADS。它不是从 Bayesian optimization、surrogate-assisted optimization 或 trust-region DFO 那条线推进，而是坚持 MADS 的 mesh/poll 收敛结构，通过 execution model 改善实用性。
与 APPS 类方法相比，pMADS-A 的本质差异不在“异步”这个概念，而在它被嵌入 MADS/NOMAD 的 mesh、cache、constraint barrier 和 opportunistic evaluation 语义中。论文把 pMADS-A 描述为 APPSPACK 的简化版本是合理的；这里的新意更多是工程化、NOMAD 语境下的系统整理和 benchmark，而不是新的 convergence theory。
COOP-MADS 看似是 cooperative optimization，但本质更接近 multi-start MADS with shared cache。实质新增的信息是动态预算和跨实例 cache 去重，而不是新的协作学习机制。PSD-MADS 的创新主要来自早期文献，本论文更多是把它放入同一比较框架。
因此，这篇论文的定位应是 parallel MADS implementation and empirical guidance，而不是 algorithmic breakthrough。它的价值在于告诉使用者何时该选哪种并行形态，并明确异步调度在时间异质 blackbox 中是第一优先级。
Dataset / Evaluation
评价覆盖了三类场景：人工控制 evaluation time 的 scalability 测试、真实 solar simulator 的时间异质测试、Moré-Wild 和约束问题集上的 data profile。这个组合基本能支撑论文的工程 claim：并行 MADS 尤其是 pMADS-A 能减少 wall-clock time，并且同步 barrier 在异质 evaluation 下会成为瓶颈。
但 evaluation 对“搜索质量提升”的支持较弱。Moré-Wild 是低维、光滑、无约束 DFO benchmark，对本文的核心异步调度 claim不是最强证据；约束测试展示了 progressive barrier 下的可用性，但没有深入拆解约束处理与并行策略的交互。
真实世界部分主要是 solar4.1，能说明异质 blackbox 的实际存在，但覆盖面有限。PSD-MADS 被定位为高维方法，但实验中对其适用边界的刻画不充分，尤其缺少强耦合高维问题、不同子空间大小、不同变量相关结构下的归因分析。
总体看，实验足以支持“pMADS-A 是实用默认选择”和“同步并行在异质任务上差”，但不足以证明 COOP-MADS 或 PSD-MADS 在广泛问题类别上优于更简单 baseline。部分增益可能主要来自 scaling / data coverage。
Limitation
第一，核心收益依赖 evaluation cost 远大于调度和通信 cost。一旦 blackbox 较便宜，MPI、文件 I/O、cache 管理和 master-worker 通信会吃掉收益。文中虽展示了 1s 与 30s evaluation 的差异，但没有系统给出 break-even 区间。
第二，pMADS-A 牺牲确定性。对工业优化来说，非确定性不仅是复现实验的问题，也会影响调参、debug、regression testing 和性能归因。论文承认这一点，但未充分说明如何在实际部署中管理。
第三，COOP-MADS 的“协作”较弱。共享 cache 主要是 memory reuse / duplicate avoidance，不是策略层面的信息共享。所谓更好探索可能主要来自多随机种子并行和更广覆盖；如果对比强 multi-start baseline，增益来源不清。
第四，PSD-MADS 的可扩展性依赖问题结构。它隐含假设高维空间中存在有效低维子空间改进，或者至少随机子空间能频繁命中有用变量组合。对强变量耦合、约束边界复杂、可行域狭窄的问题，这个假设很可能失败。
第五，evaluation 主要围绕 NOMAD 3 和 MPI 实现，未来 NOMAD 4 shared-memory 实现可能改变 overhead 和 scalability 结论。这里的结论部分是算法层，部分是实现层；文中没有完全分离。
Takeaway
- 1. 对昂贵且 evaluation time 异质的 BBO，异步调度通常比同步 batch 更重要；这类问题里 wall-clock progress 才是首要指标，evaluation count 反而可能误导。
- 2. MADS 的并行化不需要改变收敛骨架，真正要改的是 evaluation 信息流：trial points 可以并行、返回可以乱序、cache 可以承担异步状态修正。
- 3. COOP-MADS 和 PSD-MADS 分别对应两个可迁移方向：用多轨迹扩大 basin coverage，用子空间结构换高维可扩展性。
- 但二者都需要问题结构配合，不能视为通用改进。
一句话总结
这篇论文在 MADS 方向上的贡献不是提出新的搜索理论，而是把并行 evaluation scheduling、shared cache 多轨迹探索和空间分解组织成一套实用框架，其中最有价值的结论是异步 pMADS-A 应成为昂贵异质黑箱优化的默认执行形态。