New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions

技术摘要：零阶硬阈值中方差缩减的新见解

问题陈述
本文解决了$\ell_0$约束优化问题的挑战，该问题对于在高维机器学习任务中实现稀疏学习至关重要。具体问题被表述为在满足$\|\theta\|_0 \leq k$的条件下，最小化正则化经验风险$F(\theta) = \frac{1}{n}\sum_{i=1}^n f_i(\theta)$。虽然硬阈值迭代算法对$\ell_0$约束有效，但它们传统上需要访问真实梯度。在许多现代场景中——例如 bandit 问题、黑盒对抗攻击和强化学习——梯度是不可访问的，因此必须依赖基于函数评估的零阶（ZO）优化方法。

该设定下现有的最先进算法是随机零阶硬阈值（SZOHT），但它存在一个关键局限性。作者指出了 ZO 梯度估计器的偏差（误差）与硬阈值算子的扩张性（非非扩张性）之间固有的冲突。为了确保收敛，SZOHT 对用于梯度估计的随机方向数量（$q$）和稀疏度水平（$k$）施加了严格的条件。这些条件对于实际应用往往过于苛刻，限制了算法的实用性。

方法论
本文提出了一种通过聚焦于方差缩减来解决 ZO 梯度与硬阈值之间冲突的新视角。作者认为，冲突的根本在于硬阈值算子与梯度估计的方差之间，而非估计误差本身。

为此，本文引入了一个名为pM-SZHT（p-记忆随机零阶硬阈值）的通用框架。该框架利用历史梯度来减少方差，类似于 SAGA 和 SVRG 等一阶方差缩减技术，但针对 ZO 设定进行了调整。其核心组件包括：

1. 广义迭代表达式：算法遵循更新规则$\theta^{(r+1)} = H_k(\theta^{(r)} - \eta \hat{g}^{(r)}(\theta^{(r)}))$，其中$\hat{g}^{(r)}$是包含方差缩减的广义梯度估计。
2. p-记忆：该框架采用一种记忆机制，在每次迭代中更新随机子集的梯度估计，使算法能够利用历史信息来稳定 ZO 估计。
3. 具体算法：在此框架内，作者实例化了具体算法，包括VR-SZHT（SVRG 的 ZO 适配版）和SARAH-SZHT（SARAH 的 ZO 适配版）。

理论分析
本文在标准稀疏学习假设下提供了全面的收敛性分析：限制强凸性（RSC）和限制强平滑性（RSS）。

• 冲突缓解：分析表明，通过使用方差缩减，算法可以消除对收敛所需的随机方向数量（$q$）的严格依赖。在 SZOHT 中，$q$必须足够大以满足相对于$k$的特定界限；而在所提出的方法中，只要其他参数（如学习率）选择正确，即可保证对任意$q > 0$的收敛。
• 收敛速率：理论结果表明，所提出的算法实现了比 SZOHT 更优的收敛速率。具体而言，VR-SZHT 的查询复杂度推导为$O([n + \frac{\kappa^3}{\kappa^2+1}] \log(1/\epsilon))$，这代表了相对于 SZOHT 的$O((k + d/s^2)\kappa^2 \log(1/\epsilon))$复杂度的显著改进，特别是在条件数$\kappa$较大时。
• 与$q$的独立性：一个关键的理论发现是，方差缩减将收敛条件与随机方向的数量解耦，从而允许更灵活的参数选择。

实验结果
作者在两个主要任务上验证了他们的方法：

1. 岭回归：使用合成数据，所提出的方差缩减算法（VR-SZHT、SAGA-SZHT、SARAH-SZHT）始终优于普通 SZOHT 和全梯度 ZOHT（FGZOHT）。它们以更少的硬阈值操作（NHT）实现了更低的目标函数值，并具有竞争力的零阶预言机调用次数（IZO）。
2. 黑盒对抗攻击：该方法被应用于在 CIFAR-10 数据集上针对黑盒分类器生成稀疏通用对抗扰动。结果表明，与 SZOHT 相比，方差缩减方法（特别是 SARAH-SZHT 和 SAGA-SZHT）实现了更高的攻击成功率和更低的损失值。例如，SARAH-SZHT 成功攻击了“飞机”类别中的 10 张图像中的 7 张，优于 SZOHT。

意义与主张
本文声称提供了关于方差缩减的“新见解”，将其不仅视为一种加速机制，更视为缓解 ZO 估计器与硬阈值算子之间独特矛盾的必备工具。这项工作的意义在于：

• 放宽约束：它消除了 SZOHT 中对随机方向数量（$q$）的禁止性限制，使 ZO 硬阈值适用于更广泛的现实世界问题。
• 通用框架：它建立了一个通用的分析框架（pM-SZHT），涵盖了各种方差缩减 ZO 方法，提供了统一的理论理解。
• 实用价值：对抗攻击和回归的实验结果表明，这些方法在保持稀疏性约束的同时，能够实现与最先进 ZO 算法相当或更优的性能。

作者总结道，他们的方法有效地增强了现有的稀疏零阶优化算法，为梯度不可访问的场景提供了一种更灵活、更具弹性的解决方案。