PaperlayerView exact revision on arXiv

Source-linked AI summary

A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning

Sijia Liu, Pin-Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred Hero, Pramod K. Varshney

arXiv:2006.06224v2cs.LGeess.SPstat.ML

TL;DR

ZO optimization addresses black-box settings where only function evaluations are available, not explicit gradient expressions. This survey reviews ZO variants, algorithms, complexities, and applications, including black-box attacks and signal-processing systems.

  • Problem

    ZO optimization considers optimization with only function evaluations when explicit gradient expressions are unavailable for black-box models.

  • Method

    The survey discusses variants of ZO optimization, including min-max and distributed formulations, and compares their iteration and function-query complexities.

  • Results

    ZO methods can be as effective as state-of-the-art white-box attacks despite accessing only black-box models.

  • Takeaways & Limitations

    The survey identifies emerging ZO applications in signal processing and machine learning, including adversarial attacks and related black-box model analyses.

Abstract

from arXiv · show

Zeroth-order (ZO) optimization is a subset of gradient-free optimization that emerges in many signal processing and machine learning applications. It is used for solving optimization problems similarly to gradient-based methods. However, it does not require the gradient, using only function evaluations. Specifically, ZO optimization iteratively performs three major steps: gradient estimation, descent direction computation, and solution update. In this paper, we provide a comprehensive review of ZO optimization, with an emphasis on showing the underlying intuition, optimization principles and recent advances in convergence analysis. Moreover, we demonstrate promising applications of ZO optimization, such as evaluating robustness and generating explanations from black-box deep learning models, and efficient online sensor management.

I. INTRODUCTION

ZO optimization addresses difficult black-box optimization problems by estimating gradients from function evaluations rather than requiring analytical gradients. The paper reviews its principles, convergence analysis, advantages over conventional derivative-free methods, and applications across signal processing and machine learning.

  • Motivation: ZO optimization solves black-box problems using function-value-based gradient estimates instead of directly computed gradients.Its iterative process supports optimization when gradients are difficult or infeasible to obtain.
  • Motivation: Conventional derivative-free methods are difficult to scale, often lack convergence-rate analysis, and may require application-specific customization.For example, COBYLA supports a maximum of 216 variables, smaller than a single ImageNet image.
  • ZO optimization: ZO offers easier implementation, computationally efficient derivative approximations, and convergence rates comparable to first-order algorithms.These advantages arise from modifying commonly used gradient-based algorithms while using function evaluations.
  • Applications: ZO methods support black-box adversarial attacks that can be as effective as state-of-the-art white-box attacks using only targeted-network inputs and outputs.They can also reveal the most susceptible features of deep learning systems.
  • Scope and applications: The paper reviews ZO gradient estimators, algorithms, convergence developments, and applications including explanations, automated machine learning, and online sensor management.The review also covers uses involving private or intractable gradients and computationally efficient alternatives to second-order optimization.

II. GRADIENT ESTIMATION VIA ZO ORACLE

ZO gradient estimation uses only function evaluations to approximate gradients through randomized perturbations, with one-point and multi-point estimators trading query cost against accuracy.

  • ZO methods estimate gradients from function evaluations at perturbed points rather than requiring analytical gradients.The framework targets optimization with black-box objective functions.
  • ZO gradient estimates form the descent direction, and estimators are categorized as one-point or multi-point according to queried function evaluations.More evaluations are expected to improve accuracy but increase query complexity.
  • The one-point estimator is unbiased for the gradient of a smoothed function, not generally for the true gradient of f.Its expectation corresponds to the gradient of the smoothed objective.
  • In practice, one-point estimation is less common because its estimation bias can slow convergence.

B. Multi-point ZO estimate

Multi-point ZO estimators improve gradient approximation by averaging directional differences, while their accuracy depends on the smoothing parameter, dimension, and number of queries.

  • The two-point estimator uses directional function differences to approximate a gradient and can be implemented with randomized or deterministic directions.
  • Smaller smoothing parameter µ generally improves approximation, but excessively small µ makes function differences vulnerable to system noise.Careful µ selection is therefore important for convergence.
  • Averaging b random directions reduces variance, whereas the approximation-error term is independent of b.
  • When function evaluations reach the problem dimension d, coordinate-wise estimation yields approximation error of order O(dµ2).
  • Multi-point estimates are commonly implemented with 2 ≤ b ≤ d and may use forward or central differences with similar approximation errors.
  • The paper presents a unified framework and surveys ZO methods across problem settings and factors influencing their behavior.

A. The generic form of the ZO algorithm

The generic ZO algorithm repeatedly estimates gradients from stochastic function samples, computes a descent direction, and updates the constrained iterate.

  • A. The generic form of the ZO algorithm: The stochastic problem optimizes x ∈ R^d over a closed convex set X for a possibly nonconvex objective with stochastic data or noise ξ.When X = R^d, the problem becomes unconstrained.
  • A. The generic form of the ZO algorithm: Algorithm 1 initializes x0, gradient and direction operations, iteration count T, and learning rates ηt before iterating.
  • 1. Gradient estimation: ˆgt = φ({f(xt; ξj)}t: Gradient estimation applies φ to function evaluations from a mini-batch of stochastic samples at iteration t.The estimate is built from per-sample ZO gradient estimates and the mini-batch cardinality.
  • 1. Gradient estimation: ˆgt = φ({f(xt; ξj)}t: The generic iteration computes a descent direction mt from the gradient estimates and updates the point through ΠX subject to x ∈ X.
  • 1) ZO algorithms for unconstrained optimization:: ZO-SGD uses the current gradient estimate, while full-batch sampling yields ZO-GD; coordinate-wise estimates define ZO-SCD.
  • 1) ZO algorithms for unconstrained optimization:: ZO-signSGD uses element-wise signs of the current estimate, scaling down coordinate-wise estimation errors.
  • 1) ZO algorithms for unconstrained optimization:: ZO-SVRG combines the current estimate with a reduced-variance control variate, while ZO-Hess incorporates a Hessian approximation into the direction.
  • 1) ZO algorithms for unconstrained optimization:: ZO-Hess may construct its Hessian approximation using second-order Gaussian Stein’s identity or diagonalization-based approximation, including ZO-SCRN.

2) ZO algorithms for constrained optimization:

ZO methods extend to composite, min-max, and constrained optimization by combining black-box objectives with regularization, feasible updates, or alternating procedures.

  • Constrained ZO algorithms include projected SGD, stochastic mirror descent, stochastic conditional gradient, and adaptive momentum methods.
  • ZO-SMD uses Bregman divergence, whereas ZO-AdaMM uses momentum, adaptive learning rates, and Mahalanobis-distance projection.
  • ZO-AdaMM can balance convergence speed and accuracy but requires additional hyperparameter tuning beyond learning-rate and smoothing parameters.
  • Composite ZO problems combine a possibly nonconvex black-box smooth function f with a white-box nonsmooth regularizer g.Constraint sets can be represented by an indicator function added to the objective.
  • This composite formulation appears in sparsity-promoted applications including adversarial attack generation and online sensor management.
  • ZO-ProxSGD and ZO-ADMM were developed for nonsmooth composite optimization.
  • In black-box poisoning attacks, an attacker injects samples into training data to manipulate a predictive model’s results.
  • ZO min-max methods address nonconvex outer minimization over x and strongly concave inner maximization over y, with sub-linear convergence rates reported.

3) ZO distributed optimization:

ZO distributed optimization addresses network objectives formed by summing local costs while using only local function evaluations and enforcing agreement among connected agents. Recent analyses extend these methods across convex, nonconvex, constrained, and structured high-dimensional settings.

  • Distributed formulation: Distributed ZO optimization minimizes a network cost given by the sum of local objective functions while neighboring agents agree on shared variables.The network is assumed connected, with every pair of distinct nodes linked by a path.
  • Algorithmic developments: ZO distributed algorithms include ZO (sub)gradient and mirror-descent methods for nonsmooth convex optimization, plus consensus-based methods for unconstrained nonconvex problems.A Kiefer–Wolfowitz-type method was also proposed for distributed black-box objectives under stated objective-function assumptions.
  • High-dimensional challenges: ZO algorithms typically suffer convergence slowdowns proportional to problem size d when the objective is convex.This motivates methods exploiting gradient sparsity, functional sparsity, or low-dimensional manifold structure.
  • High-dimensional remedies: Poly-logarithmic dimensional dependence is obtained under gradient sparsity, functional sparsity, or low-dimensional structure, including LASSO-based gradient estimation and direct-search methods.Riemannian ZO methods instead depend on the manifold’s intrinsic dimension.
  • Convergence analysis: Convergence is assessed using optimality gaps, cumulative regret, stationary-point measures, gradient-mapping norms, or Frank–Wolfe duality gaps, depending on the problem setting.Analyses relate error to iterations T and may account for randomness from gradient approximation and stochastic sampling.

4) Constrained nonconvex optimization:

ZO methods support constrained and nonconvex optimization by measuring suitable stationarity or feasibility-aware convergence criteria and by enabling black-box adversarial attack generation. In the reported attack comparison, ZO-PSGD converges fastest, whereas ZO-AdaMM attains the smallest distortion.

  • Convergence criteria: Convergence analyses use gradient norms, projected-gradient mappings, Frank–Wolfe gaps, and iteration-dependent errors across different ZO problem settings.The projected-gradient mapping represents a feasible update, while second-order conditions help distinguish local optima from saddle points.
  • Algorithm comparison: Table I compares ZO algorithms by problem structure, gradient estimator, smoothing parameter, convergence error, and function-query complexity.The listed estimators include Gaussian, uniform-sphere, and coordinate-wise partial-derivative approximations.
  • Black-box setting: Black-box attacks interact with deep-learning systems only through submitted inputs and returned predictions, unlike white-box attacks with complete system access.This application therefore evaluates ZO methods under restricted model visibility.
  • Black-box attacks: ZO optimization formulates black-box adversarial-example generation as minimizing an attack loss with regularization over a normalized input space.The regularizer can penalize perturbation sparsity or structure, while the attack changes the model prediction from the true label.
  • Attack results: ZO-PSGD typically has the fastest convergence to a valid adversarial attack, while ZO-AdaMM has the best convergence accuracy.The latter is defined by requiring the smallest distortion to fool the neural model.

V. APPLICATION: ONLINE SENSOR MANAGEMENT

ZO optimization is applied to online sensor selection, where the goal is to balance sensor activations against parameter-estimation accuracy. ZO-ADMM converges more slowly than FO-ADMM but approaches its accuracy and achieves almost the same estimation MSE.

  • Application objective: Online sensor selection seeks an optimal tradeoff between the number of activated sensors and estimation accuracy over time.The application is relevant to smart grids, communication systems, and wireless sensor networks.
  • Optimization formulation: The sensor-selection objective is a log determinant of the maximum-likelihood error covariance matrix, with x encoding which sensors are selected.The formulation constrains the selection variables by their total count and uses continuous relaxation before hard thresholding.
  • Motivation for ZO-ADMM: Large-matrix inversions required by conventional projected-gradient and interior-point methods create a computational bottleneck, especially for high-dimensional online optimization.ZO-ADMM is presented as a way to circumvent this computational burden for mixed equality and inequality constraints.
  • Convergence comparison: ZO-ADMM has a slower convergence rate than FO-ADMM but approaches FO-ADMM’s accuracy as the number of iterations increases.Figure 2 compares their ADMM primal-dual residuals against iteration number.
  • Estimation accuracy: ZO-ADMM yields almost the same MSE as FO-ADMM for parameter estimation using m0 activated sensors.The comparison varies the total number of selected sensors and uses thresholded continuous-selection solutions.

A. Model-agnostic constrastive explanations. Explaining

ZO optimization provides model-agnostic tools for contrastive explanations and other black-box machine-learning applications without requiring input gradients. Contrastive explanations identify pertinent features supporting a prediction or changes that would alter it, while related applications include policy search and AutoML.

  • Model-agnostic explanations: ZO optimization enables local explanations through model queries, avoiding platform-specific gradient computation when developing multi-platform explanation methods.This is useful for models whose internal states or input gradients are unavailable through access-limited APIs or rule-based systems.
  • Digit classification: For handwritten digits, ZO-GD identifies pixel subsets whose presence supports the original prediction and whose absence is necessary to change it.The PP and PN together form the contrastive explanation.
  • Contrastive explanation formulation: Contrastive explanations contain a pertinent positive that minimally supports the original prediction and a pertinent negative that minimally alters it.Finding both is formulated as a sparsity-driven, data-perturbation optimization problem guided by model prediction outcomes.
  • Loan approval: For loan approval, a pertinent negative explains feature modifications that would change Alice’s model recommendation from ‘denial’ to ‘approval’.The example uses a neural-network model trained on the FICO explainable machine-learning challenge dataset.
  • Policy search: ZO policy search directly optimizes policy parameters using finite differences without exploiting first-order information from the policy, reward, or dynamics.It has been observed to perform better empirically than policy-gradient methods in settings where models do not provide more information.
  • Automated ML: ZO optimization can replace the internal first-order solver used in Bayesian optimization to fit Gaussian-process parameters for AutoML.The internal solver is slow because computing the log-likelihood gradient with respect to Gaussian-process parameters is difficult.

VII. OPEN QUESTIONS AND DISCUSSIONS

Despite substantial progress in ZO optimization’s design, theory, and applications, many questions remain, including nonsmooth objectives, black-box constraints, and computational trade-offs.

  • Many questions and challenges remain despite progress in ZO optimization’s design, theoretical analysis, and applications.
  • Nonsmooth objectives: Randomized smoothing makes fµ smooth even when f is non-smooth, while double randomization avoids sampling points from non-smooth regions.
  • Computational trade-offs: Double randomization increases function query complexity, whereas model-based interpolation increases computation cost through nested regression.
  • Computational trade-offs: Nested regression is required by model-based interpolation, increasing computation cost despite avoiding extra assumptions on the objective function.
  • ZO optimization with black-box constraints: Current work commonly considers black-box objectives with white-box constraints, leaving black-box constraint optimization as an open issue.
  • ZO optimization with black-box constraints: Barrier functions or multiplier-based regularization are potential ways to reformulate black-box constraints within the objective.

C. ZO optimization for privacy-preserving distributed

The paper identifies privacy-preserving distributed learning, derivative bottlenecks, discrete domains, convergence rates, and broader applications as important directions for ZO optimization.

  • ZO optimization for privacy-preserving distributed learning: ZO optimization conceals gradient information and permits noisy gradient estimates, motivating questions about privacy guarantees in distributed learning.
  • ZO optimization and automatic differentiation: ZO optimization may be integrated with automatic differentiation when sub-derivatives are infeasible or difficult to compute.
  • ZO optimization and automatic differentiation: ZO optimization could help overcome the derivative bottleneck when high-order derivatives are required, such as in model-agnostic meta-learning.
  • Discrete-domain optimization: Future work should explore ZO algorithms that operate directly on discrete domains, alongside relaxation to continuous values.
  • Tight convergence rates of ZO methods: Open questions include optimal rates and tight lower bounds for general cases of ZO constrained nonconvex optimization.
  • Conclusions: The survey reviews ZO gradient estimators, their statistical modeling, algorithmic complexities, emerging applications, unsolved challenges, and future directions.
Loading 2006.06224v2…