Achieving Directional-Stationarity from a Single Random Direction Step¶

会议: NeurIPS 2026
arXiv: 2605.22045
论文: https://arxiv.org/abs/2605.22045
领域: 优化/理论
关键词: 非光滑非凸优化, 方向平稳性, 随机方向探索, DCA, 近端线性算法

一句话总结¶

本文提出了一种与底层优化器解耦的单步随机方向探索机制（REP），在极弱的局部Lipschitz连续与方向导数存在性假设下，保证任意可行优化算法生成的迭代序列聚点几乎必然达到强方向平稳性（d-stationarity），同时完全保持基线算法原有的收敛速率。

研究背景与动机¶

在带凸约束的非光滑非凸优化问题（例如差异凸 DC 规划、非凸正则化稀疏回归等）中，获取严格且具有实用意义的极值性保证历来是理论优化领域的一大难题。现有的标准算法（如 DCA、近端线性法、梯度采样法 INGD 等）往往仅能保证较弱的临界性（criticality）或 Clarke 平稳性。在这些弱平稳点处，目标函数可能仍然存在能够显著降低目标值的可行下降方向，导致算法在鞍点、伪驻点或非最优的折拐处停滞不前。

要达到更强的方向平稳性（d-stationarity，即在可行方向锥内不存在任何严格下降方向），传统理论与算法通常面临严苛的限制。现有实现 d-stationarity 的方案要么严重依赖目标函数显式的有限最大值结构与平滑 DC 分解组件，要求对每一个激活分量分别求解凸子问题；要么仅局限于多面体线性可行集，并且这些理论保证与特定的算法动力学深度绑定。一旦面对未知的黑盒分解、一般闭凸约束或非结构化非光滑复合目标，现有方法便完全失效。

本文打破了“必须依靠特定复杂算法结构才能获得强平稳性”的固有范式。作者提出的切入角度非常纯粹：既然方向平稳性的本质是排除可行下降方向，那么只需在任意基线优化器的迭代过程中，外挂一个极简的随机方向探索探针。核心 idea：将算法迭代更新与极值性强化彻底解耦，在每轮迭代中仅依概率采样一个仿射子空间单位方向与随机步长，若满足正则化充分下降条件则接受该探针，以此轻量步骤即可几乎必然滤除所有伪驻点并渐近达到 d-stationarity，同时完整保留基线优化器的收敛速率。

方法详解¶

整体框架¶

本文构建了一个名为随机探索流程（Random Exploration Procedure, REP）的外挂式框架，用于增强任意产生可行迭代点的基线优化算子 \(\mathcal{O}_C\)。算法在当前迭代点 \(x^k \in C\) 处并行产生两个候选更新：一个是基线算子根据自身机制计算的可行候选点 \(z^{k+1} = \mathcal{O}_C(x^k)\)；另一个是由 REP 在约束集仿射包 \(L\) 上采样随机球面方向 \(v_{ex}\) 和步长 \(\hat{t}\) 生成的探索候选点 \(y^{k+1}\)。算法随后通过贪心比较两者的目标函数值，选择较优者作为下一轮迭代点 \(x^{k+1}\)。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["当前可行迭代点 x^k ∈ C"] --> B["并行生成更新候选"]
    subgraph SG1 ["双路候选生成"]
        direction TB
        B1["基线优化算子 O_C<br/>计算 zk+1 = O_C(x^k)"]
        B2["随机探索过程 REP<br/>采样方向与步长生成 yk+1"]
    end
    B --> B1
    B --> B2
    B1 --> C["正则化下降接受机制<br/>检验可行性与二次下降"]
    B2 --> C
    C --> D["贪心迭代点选择<br/>选取目标函数值更低者"]
    D --> E["下一轮迭代点 xk+1<br/>几乎必然渐近达到 d-平稳性"]

关键设计¶

1. 随机探索过程（REP）：仿射空间球面探索与自适应步长采样

为保证算法在带约束几何区域内的探索完全不脱离约束集的支撑子空间，REP 首先在包含可行集 \(C\) 的仿射包子空间 \(L := \mathrm{aff}(C - x^0)\) 与单位球面的交集 \(S^{n-1} \cap L\) 上采样单位方向 \(v_{ex}\)，要求采样分布 \(\mathcal{D}_v\) 在该交集的任意非零测度子集上赋予正概率。随后在区间 \([0, r]\) 上独立采样试验步长 \(\hat{t} \sim \mathcal{D}_t\)。探索步长 \(t_{ex}\) 的确定严格取决于候选点是否既可行又提供足够的二次正则化下降：

\[t_{ex} = \begin{cases} \hat{t}, & \text{若 } x + \hat{t}v_{ex} \in C \text{ 且 } h(x + \hat{t}v_{ex}) + \frac{\gamma}{2}\hat{t}^2 < h(x), \\ 0, & \text{否则}. \end{cases}\]

返回的探索更新点为 \(y = x + t_{ex}v_{ex}\)。由于当测试失败时 \(t_{ex}=0\) 使得 \(y=x\)，该步骤单调不增，且计算代价极低：每轮至多仅需一次可行性判定和一次目标函数值评估（若点不可行则无需计算函数值）。

2. 贪心极值选择与收敛速率保持：算法解耦与速率继承

在每轮主循环中，算法执行贪心仲裁：

\[x^{k+1} = \arg\min_{u \in \{y^{k+1}, z^{k+1}\}} h(u).\]

这种极简的贪心机制带来了关键的结构分离特性：无论 REP 是否接受探索步，迭代点始终满足 \(h(x^{k+1}) \le h(z^{k+1})\)。对于依赖于单调下降不等式的各类经典优化算子（如强凸分解下的 DCA、近端线性法 Prox-linear 以及梯度采样法 INGD），基线算法推导迭代残差所依赖的核心下降不等式被完整保留，从而直接继承基线算法的收敛速率界（例如 DCA 与 Prox-linear 的 \(\mathcal{O}(1/\sqrt{N})\) 速率界），而无需对原有算子的理论证明做任何侵入式修改。

3. Borel-Cantelli 几何覆盖与累积步长平方可和矛盾反证：渐近 d-平稳性保证

理论分析的核心在于通过概率测度与变分几何的精妙联动，证明所有聚点几乎必然为 d-平稳点。首先，由两点贪心比较与下有界性可知，接受步长的平方和满足 \(\sum_{k=0}^{\infty} (t_{ex}^k)^2 \le \frac{2}{\gamma}(h(x^0) - \inf_C h) < \infty\)，从而迫使 \(t_{ex}^k \to 0\)。

若某个聚点 \(x^*\) 存在非 d-平稳的可行下降方向 \(v_i \in \mathrm{ri}(D_C(x^*)) \cap S^{n-1}\)，使得 \(h'(x^*, v_i) = -\varepsilon < 0\)，根据局部凸锥几何的均匀可行半径引理（Lemma 4.3），在 \(x^*\) 邻域内沿 \(v_i\) 及其邻近方向均存在一致正的容许步长。利用条件 Borel–Cantelli–Lévy 引理，迭代点列访问 \(x^*\) 邻域的同时，在可数稠密集方向与步长区间 \([t^*/2, t^*]\) 内必然以概率 1 发生无穷多次独立采样。在这些无穷多个子序列索引处，局部 Lipschitz 连续性将迫使严格下降条件 \(h(x^j + \hat{t}^j v_{ex}^j) - h(x^j) + \frac{\gamma}{2}(\hat{t}^j)^2 \le -\frac{\varepsilon t^*}{16} < 0\) 恒成立，进而导致 \(t_{ex}^j = \hat{t}^j \ge t^*/2\) 无穷次被强制接受。这直接导出 \(\sum_k (t_{ex}^k)^2 = \infty\) 的致命矛盾，从而严格确立了聚点的几乎必然 d-平稳性。

实验关键数据¶

主实验¶

实验在三类具有鲜明代表性的非光滑非凸基准问题上进行评估：截断 Lasso（Trimmed Lasso，用于检验 DCA 摆脱伪驻点的能力）、最小截断二乘（Least Trimmed Squares, LTS，检验 DCA 在强基线下的安全性）和带有 ReLU 激活的非凸回归（ReLU Regression，检验 Prox-linear 算子的跨范式迁移）。每个问题均对比确定性基线算子与外挂 REP 后的增强算法（3 个随机种子），以差值 \(\Delta = h_{\mathrm{base}} - \mathrm{median}_s h_{\mathrm{aug}, s}\)（正值代表增强版更优）进行成对检验。

实验基准配置	实例数 \(n_{\mathrm{inst}}\)	胜/平/负 (w/t/l)	目标差距均值 \(\Delta\)	胜出时差距中位数	McNemar 检验 \(p\) 值	非 d-平稳点失败数 (Base / Aug)
Trimmed Lasso (\(\lambda=1, m=50, n=100, k=5\))	100	99 / 1 / 0	+0.29	+0.27	\(1.6 \times 10^{-30}\)	99 / 4
LTS (\(\sigma_{\mathrm{clean}}=4, m=100, n=50, q=10\))	100	9 / 91 / 0	+3.96	+52.2	\(2.0 \times 10^{-3}\)	0 / 0
ReLU Regression (\(m=200, n=50, N=1000\))	200	44 / 156 / 0	+0.96	+1.26	\(5.7 \times 10^{-14}\)	0 / 0

消融实验：方向采样几何分布的影响（以 Trimmed Lasso 为例）¶

针对高维非光滑非凸稀疏问题，探索方向的先验分布对有限步收敛行为具有决定性影响。下表对比了均匀球面采样与坐标轴偏置高斯混合分布（Gauss-Axis Sampler，\(\mu=300\)）在 Trimmed Lasso 问题上的表现。

采样机制配置	采样分布支撑与特性	探索步接受率	相对 DCA 目标改进	消除非 d-平稳伪驻点能力
Plain DCA (无探索)	无	-	基准 (0.0)	99% 失败（陷入非 d-平稳临界点）
DCA + Sphere REP	\(v \sim \mathrm{Unif}(S^{n-1})\)	极低（几乎为 0）	0.0（与 DCA 轨迹完全重合）	无实质改善（高维弥散导致下降被稀释）
DCA + Gauss-Axis REP	高斯混合偏置坐标轴 (\(\mu=300\))	稳定触发有效跳跃	99% 实例显著胜出 (\(\Delta \approx +0.29\))	将失败率从 99% 骤降至 4%

关键发现¶

在 Trimmed Lasso 中，经典 DCA 几乎必然收敛到满足 \(\partial f(x) \cap \partial g(x) \neq \emptyset\) 但违反 \(\partial g(x) \subseteq \partial f(x)\) 的弱临界点，非 d-平稳率高达 99%；外挂 REP 后成功脱离停滞平台，将非平稳点降低至 4%，且以 99/1/0 的碾压优势取得更低的目标值。
在 LTS 与 ReLU 回归等基线优化器本身已经较为健全的场景中，增强算法呈现出高度的“非侵入性”：绝大多数实例下保持平局（LTS 平局 91 例，ReLU 平局 156 例），但在出现差异的子集上 100% 优于基线（LTS 胜出 9 例，中位数收益高达 +52.2；ReLU 胜出 44 例），完全没有出现任何一次劣于基线的情况（负例数为 0）。
高维空间下均匀球面采样会使探索向量的 \(\ell_1\) 范数扩散至 \(\mathcal{O}(\sqrt{n})\)，无法匹配坐标稀疏几何的局部下降方向；针对性地引入轴对齐各向异性先验（保持全支撑的前提下）是工程落地的关键策略。

亮点与洞察¶

优美严密的结构解耦：将局部收敛速率与渐近极限性质完全解耦。优化算子负责在光滑或凸子空间内高速推进并给出 \(\mathcal{O}(1/\sqrt{N})\) 迭代复杂度，单步随机探索则作为巡航探针负责清理伪驻点，二者互不干扰。
极简普适的黑盒增强器：每步探索仅消耗一次潜在的可行性检查与一次目标函数值对比，既不需要计算目标函数的梯度/次梯度，也不要求已知的 DC 分解，可以直接无缝外挂到任何现有约束优化器上。
测度论与变分分析的精妙融合：巧妙地利用条件 Borel-Cantelli-Lévy 引理建立稠密方向覆盖，与局部相对内部凸锥可行半径相结合，通过步长平方和有限性构造了无懈可击的反证闭环。

局限与展望¶

渐近保证与有限步复杂度的落差：定理 4.1 给出的 d-stationarity 保证属于几乎必然的渐近性质，无法给出在有限步内达到 \(\epsilon\)-近似 d-平稳点的收敛速率或复杂度界。
高维均匀采样的维度灾难：虽然理论上仅要求采样分布在球面上全支撑即可成立，但在实际高维问题中，均匀球面采样的方向命中率随维度呈指数衰减。若无特定领域先验指导采样器设计，黑盒探索在有限预算下容易处于钝化休眠状态。
未来方向：探索结合动量、历史更新梯度子空间或主动二阶曲率感知的自适应采样分布设计，进一步研究探索增强优化器在有限步逼近 d-平稳点时的非渐近停机准则。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 颠覆了依靠复杂子问题保证 d-平稳性的传统范式，以单步随机探索给出全新的极值性证明体系。
实验充分度: ⭐⭐⭐⭐ 理论分析极其深厚完整，实验涵盖 DCA、近端线性和不同采样先验，若能补充真实大规模深度神经网络非凸测试则更佳。
写作质量: ⭐⭐⭐⭐⭐ 逻辑主线极为清晰，定理推导层层递进，附录构造严密且实验统计检验完备。
价值: ⭐⭐⭐⭐⭐ 为非光滑非凸优化领域提供了极具通用性的即插即用平稳性升级工具，具有深远的理论指导与算法设计参考价值。