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

Abstract

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.

IEEE Signal Processing Magazine

References in corpus (21)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Practical Bayesian Optimization of Machine Learning Algorithms
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• Black-box Adversarial Attacks with Limited Queries and Information
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Structured Adversarial Attack: Towards General Implementation and Better Interpretability
• Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
• Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems
• A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
• ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
• Transfer Learning without Knowing: Reprogramming Black-box Machine Learning Models with Scarce Data and Limited Resources
• Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective
• Towards Gradient Free and Projection Free Stochastic Optimization
• Stochastic Zeroth-order Optimization via Variance Reduction method
• Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction

Cited by in corpus (7)

• Optimizing Molecules using Efficient Queries from Property Evaluations
• Personalized Optimization with User's Feedback
• Voice2Series: Reprogramming Acoustic Models for Time Series Classification
• Don't Forget to Sign the Gradients!
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Hard-label Manifolds: Unexpected Advantages of Query Efficiency for Finding On-manifold Adversarial Examples