跳到正文
原文

非凸优化的零阶随机方差缩减

Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization

arXiv· arXiv:1805.10367· Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting, Shiyu Chang, Lisa AminiMIT-IBM Watson AI Lab, IBM Research; Lawrence Livermore National Laboratory; University of Michigan, Ann Arbor本站收录· 23 天前· 原文发表攻击

论文速读

攻击

据论文 PDF 整理(AI 生成),以原文为准

作者提出 ZO-SVRG 及两个加速变体,将 SVRG 引入零阶非凸优化,作者称其在黑盒材料分类和黑盒对抗样本生成上优于已有 ZO 算法。

威胁模型在对抗样本生成实验中,目标 DNN 的参数隐藏、梯度不可得,攻击者只能访问模型的输入输出对应关系(zeroth order attacks),通过迭代查询模型生成对 n=10 张 MNIST 图像的通用对抗扰动。

问题
零阶(无梯度)优化在只能查询函数值的场景(如黑盒对抗攻击、黑盒材料分类)越来越重要,但现有 ZO 算法方差大、收敛慢,且多针对凸问题;一阶方差缩减方法 SVRG 依赖梯度无偏假设,不能直接搬到 ZO 场景。
方法
作者提出 ZO-SVRG,把 SVRG 的梯度混合与两点随机梯度估计器结合,并给出非凸收敛分析;针对分析中出现的 O(1/b) 附加误差,提出用 Avg-RandGradEst 和 CoordGradEst 的两个加速变体 ZO-SVRG-Ave 与 ZO-SVRG-Coord。
实验与结果
理论上 ZO-SVRG 达到 O(d/T + δn/b),两个变体分别改进到 O(d/T + δn/(b min{d,q})) 和 O(d/T)。实验上,材料分类中 ZO-SVRG (b=40) 测试误差 11.18% 低于 ZO-SGD 的 12.56%;黑盒 MNIST 攻击中 ZO-SVRG-Ave (q=30) 的 ℓ2 失真 3.67,低于 ZO-SGD 的 5.22。
局限与可以继续做的
作者指出误差界 O(d/T + δn/b) 的紧性未被证明,只是猜想对 T 和 b 的依赖可能最优;CoordGradEst 类方法需要 d 倍函数查询,查询预算固定时性能退化。实验只覆盖两个应用、一个 MNIST 目标模型,攻击实验仅 n=10 张图像、未报告重复次数。
实验设置well-trained DNN (MNIST handwritten digit classification, carlini/nn_robust_attacks) · Open Quantum Materials Database、MNIST · E[k∇f(x̄)k²₂]、testing error 等
被测模型
well-trained DNN (MNIST handwritten digit classification, carlini/nn_robust_attacks)
基准
Open Quantum Materials DatabaseMNIST
指标
E[k∇f(x̄)k²₂]testing errorattack lossℓ2 distortionfunction query complexity
AI 导读ZO-SVRG 是面向非凸优化的方差缩减零阶优化算法。分析发现零阶梯度估计不再满足无偏假设,两点随机梯度估计器可能带来 O(1/b) 额外误差(b 为小批量大小),两个加速版本达到零阶随机优化已知最优的迭代率。实验涵盖黑盒化学材料分类与黑盒深度神经网络对抗样本生成,优于其他最先进零阶算法,兼顾收敛速度与函数查询复杂度。

ZO-SVRG 是面向非凸优化的方差缩减零阶优化算法。分析发现零阶梯度估计不再满足无偏假设,两点随机梯度估计器可能带来 O(1/b) 额外误差(b 为小批量大小),两个加速版本达到零阶随机优化已知最优的迭代率。实验涵盖黑盒化学材料分类与黑盒深度神经网络对抗样本生成,优于其他最先进零阶算法,兼顾收敛速度与函数查询复杂度。

深度解读

6个问题,点开问题读完整回答

  1. 这篇论文试图解决什么问题?

    作者研究如何为非凸零阶优化设计方差缩减、更快收敛的算法,并提出 ZO-SVRG 及其加速变体。

    核心问题:如何为零阶(gradient-free)非凸随机优化设计带方差缩减、收敛更快的算法。

    • 问题场景与重要性:零阶优化用于梯度难以或无法获得的机器学习问题,作者列举的例子包括仅用目标 DNN 的输入输出生成黑盒对抗样本、时变约束下的网络控制、黑盒系统参数推断。
    • 现有方法的不足:作者称已有 ZO 算法普遍受 ZO 梯度估计方差大的困扰,收敛速率受限;且大多针对凸设置设计,限制了在非凸机器学习问题上的适用性。
    • 核心观察与难点:一阶方法 SVRG 通过方差缩减把 SGD 的速率从 O(1/√T) 提升到 O(1/T),但它依赖随机梯度是真实梯度的无偏估计这一假设,而 ZO 梯度估计是有偏的,该假设不再成立;作者称 ZO 方差缩减能否带来更快收敛此前是开放问题。
    • 论文的贡献:提出 ZO-SVRG(将 SVRG 与 ZO 梯度估计器结合)并给出非凸收敛分析;针对分析中暴露的 O(1/b) 附加误差,提出两个加速变体 ZO-SVRG-Ave 与 ZO-SVRG-Coord;并在黑盒化学材料分类和黑盒 DNN 对抗样本生成两个应用上做了实验评估。
    • 威胁模型(对抗样本生成实验):
      • 攻击者目标:生成对 n 张自然图像的通用对抗扰动,使目标模型误分类,同时扰动在视觉上不可察觉。
      • 知识与能力:目标模型参数隐藏、梯度不可得,攻击者只能访问模型的输入输出对应关系(论文称 zeroth order attacks),通过迭代查询模型评估来优化。
      • 受害系统:MNIST 手写数字分类任务上一个训练好的 DNN,自然样本测试准确率 99.4%。
  2. 有哪些相关研究?

    相关工作分三组:凸 ZO 算法、非凸 ZO 算法、一阶方差缩减方法;论文定位 ZO-SVRG 为更一般的框架。

    凸设置下的 ZO 算法

    • Duchi 等 [14] 提出 ZO mirror descent,速率为 O(√d/√T)(d 为变量数);bandit 凸优化 [15] 和 ZO 在线 ADMM [5] 达到同样速率。
    • 论文指出这些工作大多局限于凸问题;作者概括称 ZO 算法的迭代复杂度通常与一阶算法一致,最多差一个关于 d 的低次多项式。

    非凸 ZO 算法

    • Nesterov 与 Spokoiny [13] 提出 ZO-GD 用于确定性非凸规划,速率 O(d/T);Ghadimi 与 Lan [24] 的 ZO-SGD 达到 O(√d/√T)。
    • Hajinezhad 等 [25] 的 ZO 分布式算法用于多智能体优化,速率 O(1/T + d/q);Lian 等 [7] 的异步 ZO-SCD 达到 O(√d/√T)。
    • Gu 等 [26] 的 ZO-SVRC 把速率从 O(√d/√T) 提升到 O(d/T);论文指出该工作虽用了方差缩减,但只研究了坐标下降加坐标式(确定性)梯度估计器,这促使作者研究更一般的 ZO-SVRG 框架。

    一阶方差缩减

    • Johnson 与 Zhang [19] 提出 SVRG;Reddi 等 [20] 给出非凸 SVRG 的 O(1/T) 速率,本文的 ZO-SVRG 基于其 mini-batch 变体。
    • Lei 等 [23] 的 SCSG 采用无放回采样,本文两种采样策略都考虑。

    基线与基准:实验对比的基线算法是 ZO-SGD [24] 和 ZO-SVRC [26];应用数据集为 Open Quantum Materials Database 的 1000 种晶体材料(材料分类)和 MNIST(黑盒对抗攻击)。

    作者将本文定位为填补 ZO 优化与 SVRG 之间的空白:在多种 ZO 梯度估计器下系统分析 ZO-SVRG 的迭代复杂度与函数查询复杂度,并称方法能在两者之间取得平衡。

  3. 论文如何解决这个问题?

    ZO-SVRG 把 SVRG 的梯度混合替换为 ZO 梯度估计,再用低方差估计器构造两个加速变体消除 O(1/b) 误差。

    整体思路:把一阶 SVRG 的方差缩减机制移植到零阶场景,用基于函数值的梯度估计器替代真实梯度,并针对由此产生的有偏性做收敛分析、再用低方差估计器加速。方法名为 ZO-SVRG 及变体 ZO-SVRG-Ave、ZO-SVRG-Coord。

    问题设定与假设

    • 求解非凸有限和问题 f(x) := 1/n∑i=1n fi(x),其中各 fi 非凸,x ∈ R^d。
    • 假设 A1:各 fi 有 L-Lipschitz 连续梯度(L-smooth);假设 A2:随机梯度方差有界 σ²,作者称 A2 比有界梯度假设更弱。

    ZO 梯度估计器

    • RandGradEst:两点随机梯度估计,(d/µ)[fi(x+µuᵢ) − fi(x)]uᵢ,uᵢ 取自单位球面均匀分布,µ 为平滑参数;它是对真实梯度的有偏近似,µ 越小偏差越小,但 µ 过小时函数差会被系统噪声淹没。
    • Avg-RandGradEst:对 q 个 i.i.d. 随机方向取平均,降低方差。
    • CoordGradEst:沿 d 个坐标方向做两点差分,是确定性的,方差更低,但函数查询次数是 RandGradEst 的 d 倍。

    ZO-SVRG 算法(Algorithm 2)

    • 结构同 SVRG:外层 S 个 epoch,每个 epoch 在参考点 x̃ 处计算一次全批量 ZO 梯度估计 ĝ,内层 m 步迭代。
    • 内层用 ZO 梯度混合:v̂ = ∇̂f_I(x) − ∇̂f_I(x̃) + ĝ,其中 I 是大小为 b 的 mini-batch(有放回或无放回采样都考虑),再按 x ← x − ηv̂ 更新。
    • 与 SVRG 的唯一区别是所有梯度(批量、mini-batch、混合梯度)都换成 ZO 估计;作者强调这一看似微小的差别使无偏假设失效,构成分析的核心难点。

    收敛分析与加速设计

    • Proposition 1 给出混合 ZO 梯度估计的二阶矩上界,相比 SVRG 多出 O(dσ²/b) 的误差项(b < n 时)。
    • Theorem 1 与 Corollary 1:在 µ = 1/√(dT)、η = ρ/(Ld)、m = ⌈d/(31ρ)⌉ 的设置下,ZO-SVRG 满足 E[k∇f(x̄)k²₂] ≤ O(d/T + δn/b),其中 δn = 1(有放回或 b < n),仅当 mini-batch 等于全集时 δn = 0、退化为 ZO-GD。
    • ZO-SVRG-Ave(Theorem 2):用 Avg-RandGradEst,速率改进为 O(d/T + δn/(b min{d, q})),q ≥ d 后收益不再提升。
    • ZO-SVRG-Coord(Theorem 3):用 CoordGradEst,速率达到 O(d/T),消除了 O(1/b) 项,作者称这是 ZO 随机优化已知最好的迭代复杂度;代价是查询复杂度变为 O(d(nS + bT))。
    • 三种估计器单次梯度估计的查询量分别为 O(1)、O(q)、O(d);Table 1 汇总了各方法的速率与查询复杂度权衡。

    应用中的成功判定

    • 材料分类:非线性最小二乘,fi(x) = (yi − φ(x; ai))²,φ 是只返回函数值的黑盒(DFT 模拟器),指标为训练损失与测试误差。
    • 黑盒对抗攻击:把通用扰动建模为问题 (1),攻击损失采用 hinge 式损失加 ℓ2 失真正则(c = 1),用 tanh 变换保证扰动后的图像在合法像素空间内;衡量攻击损失与成功扰动的最小 ℓ2 失真。附录 A.11 给出完整的目标函数形式。
  4. 论文做了哪些实验?

    两组应用实验:材料分类上 ZO-SVRG (b=40) 测试误差最低;黑盒 MNIST 攻击上 ZO-SVRG-Ave 失真更小。

    实验设置

    • 对比算法:ZO-SVRG、ZO-SVRG-Coord、ZO-SVRG-Ave,基线为 ZO-SGD [24] 和 ZO-SVRC [26](材料分类);黑盒攻击实验只比较 ZO-SGD 与 ZO-SVRG-Ave。
    • 材料分类数据:Open Quantum Materials Database 的 N = 1000 种晶体材料,每个 d = 145 维化学特征,标签(导体 0 / 绝缘体 1)由 DFT 模拟器确定;均分为 n = 500 训练、500 测试。
    • 材料分类参数:epoch 长度 m = 50,mini-batch b = 10(ZO-SVRG 另测 b ∈ {1, 10, 40}),q = 10,µ = O(1/√(dT)),步长 η = O(1/d),ZO-SVRC 每迭代更新 J = 1 个坐标(附录 A.10)。
    • 黑盒攻击设置:目标模型为 MNIST 上训练好的 DNN(自然样本测试准确率 99.4%);从数字 "1" 类选 n = 10 张原本分类正确的图像,生成通用扰动;两种方法都用 b = 5、恒定步长 30/d(d = 28×28),ZO-SVRG-Ave 设 m = 10、q ∈ {10, 20, 30}。
    • 指标:材料分类看训练损失(对 epoch 数和函数查询数)与测试误差;攻击看攻击损失(对 epoch 数)与成功扰动的最小 ℓ2 失真。
    • 论文未报告实验重复次数和方差。

    主结果

    材料分类,固定 7.3×10⁶ 次函数查询下的测试误差(Table 2):

    方法epoch 数测试误差
    ZO-SGD1460012.56%
    ZO-SVRC10023.70%
    ZO-SVRG (b=40)292011.18%
    ZO-SVRG-Coord5020.67%
    ZO-SVRG-Ave36515.26%
    • 作者解读:CoordGradEst 类方法(ZO-SVRC、ZO-SVRG-Coord)因构造坐标式梯度估计消耗大量查询,在固定查询预算下性能退化;随机梯度估计类方法整体更好,但 ZO-SGD 消耗的迭代数(14600 个 epoch)远大于其他方法。
    • 作者称 ZO-SVRG (b=40) 与 ZO-SVRG-Ave 在迭代复杂度和查询复杂度之间取得了更好的平衡。
    • Figure 2-(a) 显示 ZO-SVRG 的收敛误差随 b 增大而减小;b ≤ 10 时作者称它很可能只收敛到某个临界点的邻域,与 Corollary 1 一致。

    黑盒对抗样本生成

    • 测了什么:ZO-SGD 与 ZO-SVRG-Ave(q ∈ {10, 20, 30})生成对 10 张 MNIST 图像的通用扰动,比较攻击损失收敛与 ℓ2 失真(Figure 3)。
    • 结果:ℓ2 失真 ZO-SGD 为 5.22,ZO-SVRG-Ave 依次为 4.91(q=10,改进 6%)、3.91(q=20,25%)、3.67(q=30,30%)。
    • 代价:达到相同攻击损失(论文举例 7),ZO-SVRG-Ave 需要的函数评估次数约为 ZO-SGD 的 30×(q=10)、77×(q=20)、380×(q=30)。
    • 作者解读:ZO-SVRG-Ave 收敛更快、解更精确,且 q 越大收敛轨迹越稳(因 Avg-RandGradEst 方差更小);攻击损失的骤降可能来自 hinge 式损失在攻击成功后变为 0。附录 A.11 的 Table 3、Table 4 给出数字 "1" 和 "4" 两类的对抗图像及误分类标签。

    其他消融与分析

    • mini-batch 大小 b(Figure 2-(a)):ZO-SVRG 在 b ∈ {1, 10, 40} 下,b 越大收敛误差越小。
    • 方向样本数 q(Figure 3):q 从 10 增到 30,ℓ2 失真从 4.91 降到 3.67,但函数评估倍数从约 30× 升到约 380×。
    • 理论对比(Table 1):ZO-SGD 查询复杂度最低但速率最差 O(√d/√T);ZO-SVRG-Coord 速率最好 O(d/T) 但查询复杂度 O(d(nS+bT)) 最高。
  5. 有什么可以进一步探索的点?

    作者指出误差界紧性未证明、CoordGradEst 查询开销大;实验仅覆盖两个应用和一个目标模型。

    作者指出的局限与后续方向

    • 误差界紧性未证明(第 4 节 Corollary 1 后):作者称 O(d/T + δn/b) 这一误差界的紧性没有被证明,只是猜想对 T 和 b 的依赖可能最优,理由是形式与 SVRG 一致。
    • CoordGradEst 的查询代价(第 5 节 Theorem 3 后):作者指出 CoordGradEst 的缺点是梯度估计需要 RandGradEst 的 d 倍函数查询。
    • µ 的实际约束(第 3.2 节):作者指出实际系统中 µ 过小时函数差会被系统噪声主导,无法代表函数微分。
    • 论文未设专门的 Limitations 或 Future Work 小节,以上为正文中明确写出的不足。

    实验覆盖范围

    • 实验覆盖两个应用:黑盒化学材料分类(1000 种材料、145 维特征、500 训练 / 500 测试)和黑盒 MNIST 通用对抗扰动生成。
    • 材料分类对比了 5 种算法(ZO-SGD、ZO-SVRC、ZO-SVRG、ZO-SVRG-Coord、ZO-SVRG-Ave);黑盒攻击实验只比较 ZO-SGD 与 ZO-SVRG-Ave 两种。
    • 攻击实验的目标模型只有一个 MNIST DNN(测试准确率 99.4%),图像取自数字 "1" 类、n = 10 张,附录另展示数字 "4" 类的生成结果。
    • 论文未报告任何实验的重复次数、运行时间或跨多次运行的方差。
    • 理论分析基于假设 A1(L-smooth)和 A2(方差有界),收敛结果为期望意义下的上界。
  6. 总结一下论文的主要内容

    ZO-SVRG 把 SVRG 引入零阶非凸优化,理论给出速率与查询复杂度的权衡,两个应用实验支持其有效性。

    一篇零阶非凸优化论文,提出 ZO-SVRG:把一阶方差缩减方法 SVRG 与两点随机梯度估计器结合,解决 ZO 算法方差大、收敛慢的问题,并给出系统的收敛分析。

    • 要解决的问题:ZO 梯度估计有偏,SVRG 依赖的无偏假设失效,ZO 场景下能否做方差缩减此前是开放问题。
    • 方法要点:ZO-SVRG 用 ZO 估计替换 SVRG 中的全部梯度;分析发现相比一阶 SVRG 多出 O(1/b) 量级的附加误差(b 为 mini-batch 大小)。为此提出两个加速变体:ZO-SVRG-Ave(q 个随机方向平均)把误差降到 O(1/(b min{d,q})),ZO-SVRG-Coord(坐标式估计)消除该项、达到 O(d/T),作者称这是 ZO 随机优化已知最好的迭代复杂度,但查询开销高 d 倍。
    • 材料分类结果:固定 7.3×10⁶ 次函数查询,ZO-SVRG (b=40) 测试误差 11.18%,低于 ZO-SGD 的 12.56% 和 ZO-SVRC 的 23.70%(Table 2);坐标式方法因查询开销在固定预算下退化。
    • 黑盒攻击结果:对 MNIST DNN(自然样本准确率 99.4%)生成 10 张图像的通用扰动,ZO-SVRG-Ave (q=30) 的 ℓ2 失真 3.67,比 ZO-SGD 的 5.22 改进 30%,但达到相同攻击损失需约 380× 的函数评估(Figure 3)。
    • 作者的结论:ZO-SVRG 把 ZO-SGD 的速率从 O(1/√T) 提升到 O(1/T) 量级,ZO-SVRG 与 ZO-SVRG-Ave 在迭代复杂度与函数查询复杂度之间取得平衡;作者同时指出 O(1/b) 误差界的紧性未被证明,仅为猜想。

相关论文

共同使用 MNIST
再看 3 篇
共同使用 MNIST
阅读原文arxiv.org