Conference proceeding
ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019), Vol.32
Advances in Neural Information Processing Systems
01 Jan 2019
Abstract
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(root 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 blackbox 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.
Metrics
1 Record Views
Details
- Title
- ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
- Creators
- Xiangyi Chen - University of MinnesotaSijia Liu - IBMKaidi Xu - Northeastern UniversityXingguo Li - Princeton UniversityXue LinMingyi Hong - University of MinnesotaDavid Cox - IBM Res, MIT IBM Watson Lab, Minneapolis, MN USA
- Contributors
- H Wallach (Editor)H Larochelle (Editor)A Beygelzimer (Editor)F d'Alche-Buc (Editor)E Fox (Editor)R Garnett (Editor)
- Publication Details
- ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019), Vol.32
- Series
- Advances in Neural Information Processing Systems
- Publisher
- Neural Information Processing Systems (Nips)
- Number of pages
- 12
- Grant note
- CNS-1932351 / National Science Foundation; National Science Foundation (NSF) CMMI-172775; CIF-1910385 / NSF; National Science Foundation (NSF) 73202-CS / ARO
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Identifiers
- 991021871465604721
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
Source: InCites
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Industry collaboration
- Domestic collaboration
- Web of Science research areas
- Computer Science, Artificial Intelligence