ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization

Xiangyi Chen; Sijia Liu; Kaidi Xu; Xingguo Li; Xue Lin; Mingyi Hong; David Cox

Source-linked AI summary

ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization

Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, David Cox

arXiv:1910.06513v2Oct 15, 2019cs.LGmath.OCstat.ML

TL;DR

Black-box optimization lacks usable explicit gradients, motivating a zeroth-order counterpart to adaptive momentum methods. The paper proposes ZO-AdaMM, analyzes its convergence and Mahalanobis projection, and reports faster empirical convergence for black-box adversarial attacks than six state-of-the-art zeroth-order methods.

Problem
Adaptive momentum methods are not suited to black-box optimization when explicit gradients are difficult or infeasible to obtain.
Method
ZO-AdaMM integrates adaptive momentum with zeroth-order gradient estimates and analyzes Mahalanobis-distance projections for constrained optimization.
Results
ZO-AdaMM converges faster to strong black-box adversarial attacks requiring minimum distortion than 6 state-of-the-art zeroth-order methods.
Takeaways & Limitations
The method provides convergence guarantees for convex and nonconvex settings and an empirical benchmark for black-box adversarial attacks.
Takeaways & Limitations
The general constrained nonconvex convergence analysis covers β1,t = 0; the case β1,t ≠ 0 is left for future research.

Abstract

from arXiv · show

The adaptive momentum method (AdaMM), which uses past gradients to update descent directions and learning rates simultaneously, has become one of the most popular first-order optimization methods for solving machine learning problems. However, AdaMM is not suited for solving black-box optimization problems, where explicit gradient forms are difficult or infeasible to obtain. In this paper, we propose a zeroth-order AdaMM (ZO-AdaMM) algorithm, that generalizes AdaMM to the gradient-free regime. We show that the convergence rate of ZO-AdaMM for both convex and nonconvex optimization is roughly a factor of $O(\sqrt{d})$ worse than that of the first-order AdaMM algorithm, where $d$ is problem size. In particular, we provide a deep understanding on why Mahalanobis distance matters in convergence of ZO-AdaMM and other AdaMM-type methods. As a byproduct, our analysis makes the first step toward understanding adaptive learning rate methods for nonconvex constrained optimization. Furthermore, we demonstrate two applications, designing per-image and universal adversarial attacks from black-box neural networks, respectively. We perform extensive experiments on ImageNet and empirically show that ZO-AdaMM converges much faster to a solution of high accuracy compared with $6$ state-of-the-art ZO optimization methods.

1 Introduction

ZO-AdaMM extends adaptive momentum optimization to black-box settings where gradients are unavailable, with theoretical convergence guarantees and strong empirical performance in adversarial attacks.

1 Introduction: ZO-AdaMM generalizes AdaMM to zeroth-order optimization and is analyzed for both convex and nonconvex constrained problems.The method addresses optimization settings where explicit gradients are expensive or infeasible to obtain.
1 Introduction: ZO-AdaMM’s convergence is roughly O(sqrt(d)) slower than first-order AdaMM, where d is the number of optimization variables.The dimension-dependent slowdown is reported for both convex and nonconvex optimization.
1 Introduction: Mahalanobis-distance projection is necessary for the convergence analysis, while Euclidean projection can suffer non-convergence in constrained optimization.The analysis also advances understanding of adaptive learning-rate methods for nonconvex constrained problems.
1 Introduction: ZO-AdaMM is evaluated against 6 state-of-the-art zeroth-order methods for per-image and universal black-box adversarial attacks.The experiments are conducted on ImageNet and are intended as a benchmark for future zeroth-order optimization studies.
1 Introduction: Existing zeroth-order methods face dimension-dependent slowdowns and high noisy-gradient variance, which can reduce convergence performance and query efficiency.Variance reduction and sign-based methods address parts of this challenge but have their own limitations, including neighborhood-only convergence for ZO-signSGD.

2 Preliminaries: Gradient Estimation via ZO Oracle

The paper constructs zeroth-order gradient estimates from function-value differences along random directions, using uniform sampling and a smoothing parameter.

2 Preliminaries: Gradient Estimation via ZO Oracle: The zeroth-order gradient estimate uses a forward difference of function values at a random unit direction.This provides a gradient-free approximation for optimization.
2 Preliminaries: Gradient Estimation via ZO Oracle: The random direction is sampled uniformly from the unit-ball sphere, and μ > 0 controls the smoothing scale.Uniform sampling keeps the estimate in a bounded space, unlike standard Gaussian directions.
2 Preliminaries: Gradient Estimation via ZO Oracle: Although biased for the true gradient, the zeroth-order estimator is unbiased for the gradient of the μ-smoothed objective.The smoothing formulation connects the estimator to a randomized version of the original function.

3 AdaMM from First to Zeroth Order

The paper integrates zeroth-order gradient estimates into AdaMM, combining momentum, adaptive learning rates, and Mahalanobis projection while addressing the resulting analytical difficulties.

3 AdaMM from First to Zeroth Order: The stochastic optimization model allows a differentiable objective, possibly nonconvex, over a closed convex feasible set with environmental randomness.The random variable captures uncertainty in the optimization problem.
3 AdaMM from First to Zeroth Order: AdaMM uses exponential moving averages of past gradients for the descent direction and squared gradients for adaptive learning-rate scaling.The framework is specified through AMSGrad, which has convergence guarantees in convex and nonconvex optimization.
3 AdaMM from First to Zeroth Order: ZO-AdaMM integrates a random gradient estimator into the AdaMM framework with adaptive learning rates, momentum, and Mahalanobis-distance projection.The projection reduces to an ordinary update when the feasible set is the full space.
3 AdaMM from First to Zeroth Order: ZO-AdaMM normalizes its momentum direction by the square root of the accumulated squared-gradient estimate to reduce zeroth-order noise.With suitable parameter choices, it can recover ZO-signSGD and ZO-SGD as special cases.
3 AdaMM from First to Zeroth Order: Analyzing ZO-AdaMM is difficult because stochastic sampling, zeroth-order estimation, momentum, adaptive learning rates, and projection are coupled.Conventional variance bounds are insufficient for the adaptive-learning-rate analysis, making Mahalanobis distance central to the convergence guarantees.

4 Convergence Analysis of ZO-AdaMM for Nonconvex Optimization

ZO-AdaMM’s nonconvex analysis explains why Mahalanobis projection is necessary and establishes dimension-dependent convergence rates for unconstrained and constrained settings. The constrained analysis also exposes variance and momentum-related boundaries.

4.1 Importance of Mahalanobis distance based projection operation: Euclidean projection can converge to a fixed point that is not stationary, whereas Mahalanobis projection supports the intended constrained analysis.For the stated linear program, initialization at [0.5, 0.5]^T with Euclidean projection converges to that fixed point rather than a stationary point.
4.1 Importance of Mahalanobis distance based projection operation: Mahalanobis distance transforms adaptive projected updates into Euclidean projected gradient descent in a linearly transformed coordinate system.The transformation y_t = V_hat_t^1/4 x_t makes the Mahalanobis projection in x equivalent to Euclidean projection in y.
4.2 Unconstrained nonconvex optimization: ZO-AdaMM’s unconstrained nonconvex rate depends on dimension through the ZO gradient-estimate bound G_zo, unlike the dimension-independent FO counterpart.The analysis relates the rate to G_zo = max_t ||g_hat_t||_∞ and bounds its dimension dependence using Lipschitz continuity and sphere concentration.
4.2 Unconstrained nonconvex optimization: Compared with FO-AdaMM’s O(d/T) rate, ZO-AdaMM has an O(d^2/T) convergence term under the conventional measure, with an O(sqrt(d))-scale slowdown.The stated comparison also notes that ZO-AdaMM requires an additional assumption to bound the infinity norm of its ZO gradient estimates.
4.3 Constrained nonconvex optimization: The constrained analysis sets beta_1,t = 0, corresponding to a ZO RMSProp variant, because including momentum makes the coupling substantially more complicated.The paper leaves the full momentum case in constrained nonconvex optimization unresolved.
4.3 Constrained nonconvex optimization: Constrained nonconvex ZO-AdaMM achieves E[||G(x_R)||^2] = O(d/T + d/b + d^2/q), while projection induces a variance-dependent neighborhood.Variance reduction makes the relevant error term diminishing but requires higher query complexity than the basic estimator.

5 Extended Analysis of ZO-AdaMM

The extended analysis compares ZO-AdaMM’s convergence and query trade-offs with other zeroth-order methods, while relating its rates to first-order AdaMM under stated assumptions. It also highlights that the analysis uses bounded gradient estimates and requires stricter assumptions than first-order analysis.

Convex optimization: The ZO-AdaMM convex rate is obtained by relating the original objective to its smoothed version and bounding coordinate-wise gradient-estimate quantities under a prescribed smoothing scale.The supplied analysis states that µ ≤ d^? and gives the resulting rate as O(d^1.5/...).
Comparison with other ZO methods: ZO-AdaMM has worse dimension dependence than several competing ZO methods, but offers milder smoothing-parameter choices, lower query complexity than ZO-SCD, and no T-independent bias versus ZO-signSGD.For constrained nonconvex optimization, its rate is similar to ZO-ProxSGD; for constrained convex optimization, it trades an O(d) worse rate than ZO-SMD for improved dimension dependence in µ.
Comparison with FO AdaMM: The analysis revisits the first-order AdaMM proof and states that ZO-AdaMM incurs an O(√d) slowdown relative to FO AdaMM under stricter bounds on ZO gradient estimates.The passages also note a correction to a prior proof while retaining its conclusion.
Comparison with other ZO methods: Table 1 organizes algorithm comparisons by gradient estimator, smoothing parameter, convergence rate, and function-query complexity over T iterations.The table includes both zeroth-order methods and FO AdaMM for comparison.

6 Applications to Black-Box Adversarial Attacks

The paper evaluates ZO-AdaMM on per-image and universal black-box adversarial attacks against ImageNet images, comparing it with six zeroth-order algorithms. Across both settings, ZO-AdaMM is reported to converge quickly while achieving low distortion and strong attack performance.

Experimental setup: The experiments use Inception V3 on ImageNet and compare ZO-AdaMM with six ZO algorithms under equal queries per iteration.The compared methods include ZO-SGD, ZO-SCD, ZO-signSGD, ZO-PSGD, ZO-SMD, and ZO-NES.
Per-image adversarial perturbation: ZO-AdaMM consistently outperforms other ZO methods on per-image attacks by reaching zero attack loss quickly with relatively small perturbations.The comparison covers constrained and unconstrained problems over 100 randomly selected images; ZO-signSGD and ZO-NES show poor final accuracy in at least one metric.
Universal adversarial perturbation: ZO-AdaMM reaches the fastest convergence and smallest perturbation for universal attacks, then achieves the highest success rate with the lowest distortion.Universal attacks use 100 ImageNet images, with detailed success-rate and distortion results reported over 40,000 iterations.

7 Conclusion

The paper proposes ZO-AdaMM, extending adaptive momentum to zeroth-order optimization with convergence guarantees for convex and nonconvex constrained problems. Its analysis introduces a Mahalanobis-distance convergence measure, and experiments demonstrate strong black-box adversarial-attack performance.

Table 2 summarizes attack success rates and eventual ℓ2 distortion for universal attacks on 100 images after T = 40000 iterations.
ZO-AdaMM integrates adaptive momentum methods with zeroth-order optimization and provides convergence guarantees for convex and nonconvex constrained problems.
A Mahalanobis-distance convergence measure is established as important for characterizing ZO-AdaMM on nonconvex constrained problems.
ZO-AdaMM shows the fastest empirical convergence among 6 state-of-the-art zeroth-order methods for generating strong black-box adversarial attacks.

1 Smoothing Function and Random Gradient Estimate

The smoothing function preserves key regularity properties of the original objective while enabling zeroth-order gradient estimation. The smoothing parameter controls approximation bias and numerical informativeness, whereas zeroth-order estimates retain dimension-dependent variance.

If f is convex or Lipschitz continuous, its smoothing fµ preserves convexity or the same Lipschitz constant; if f has Lipschitz gradient, fµ does too.
The smoothing approximation satisfies |fµ(x) − f(x)| ≤ Lcµ for any x.
The ZO gradient estimate becomes unbiased for ∇f only as µ → 0, but excessively small µ makes empirical function differences too small to represent the differential.
The tolerance on µ is therefore important for convergence performance, while the estimator variance retains a dimension-dependent component.

2 Proof for Nonconvex Optimization

The nonconvex analysis examines how zeroth-order estimation, momentum, adaptive scaling, and constrained projection affect convergence. It establishes technical bounds for the estimator and iterates, while highlighting the role of Mahalanobis geometry in the proof.

Under vanishing momentum parameters, smoothing, and increasing query count, ZO-AdaMM reduces to ZO-signSGD and its gradient estimate approaches an unbiased, zero-variance estimate.
A Euclidean projected sign update can remain fixed at [0.5, 0.5]T while that point is not stationary for the constrained problem.
The analysis bounds the momentum sequence through the ZO-gradient bound, yielding ∥mt∥∞ ≤ Gzo by induction.
The squared update quantity is shown not to depend on stochastic-gradient size, giving a tighter dimension dependence than the cited prior analysis.
The nonconvex proof compares projected points under different distance matrices and uses these bounds within a Mahalanobis-distance convergence analysis.

3 Proof for Convex Optimization

The convex analysis applies the convexity of the smoothed objective and adaptive-momentum bounds to derive convergence for ZO-AdaMM. It also addresses a problematic prior proof step while retaining the cited theorem’s conclusion.

Because the smoothed objective ft,µ is convex, its function gap is bounded by the expected zeroth-order gradient inner product with the iterate difference.
The proof bounds the adaptive-momentum terms using established lemmas and the nondecreasing second-moment sequence of ZO-AdaMM.
The analysis proposes a simpler fix for bounding term C when 0 < β1,t ≤ β1,t−1 ≤ 1.
Although the cited prior proof for term C is problematic, the conclusion of its theorem remains correct.

4 Supplementary Material of Experiments

The supplementary experiments evaluate ZO-AdaMM for per-image and universal black-box adversarial attacks on ImageNet, comparing convergence, distortion, and parameter sensitivity across ZO methods.

Problem and experiment setup: The experiments compare ZO-AdaMM with six ZO algorithms on Inception V3 and ImageNet using equal query cost per iteration.The methods cover unconstrained and constrained attack settings, with the same random gradient estimator, b = 1, and q = 10.
Problem and experiment setup: ZO-AdaMM performs well with β1 ≥ 0.9 and β2 ∈ [0.3, 0.5], whereas the typical β2 > 0.9 choice is not empirically optimal in the ZO setting.Figure A1 reports converged objective values after 1000 iterations for unconstrained per-image, constrained per-image, and universal attacks.
Per-image adversarial perturbation: ZO-SCD has the worst unconstrained per-image performance, requiring the most iterations for a first successful attack and producing the largest final distortion.The comparison covers 100 randomly selected ImageNet images under 1000 iterations.
Per-image adversarial perturbation: ZO-AdaMM achieves the best constrained per-image attack performance, except for a slight drop in attack success rate.ZO-signSGD and ZO-NES show poorer convergence accuracy through increased distortion after the first successful attack.
Universal adversarial perturbation: ZO-AdaMM achieves the strongest universal attack with the least distortion among the compared methods.All methods generate successful black-box adversarial examples, but ZO-AdaMM requires the least distortion strength.
Universal adversarial perturbation: The universal-attack visualization compares perturbations at 1000, 5000, 10000, and 20000 iterations and shows four generated adversarial examples.Color depth represents perturbation strength, with maximum distortion reported for each perturbation.