2019/10/14 by Xiangyi Chen, Chen, Xiangyi, Sijia Liu +11 · 15 citations
Computer Science · Engineering · #Advanced Neural Network Applications #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1910.06513
openalex publication_date 2019/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The adaptive momentum method (AdaMM), which uses past gradients to update\ndescent directions and learning rates simultaneously, has become one of the\nmost popular first-order optimization methods for solving machine learning\nproblems. However, AdaMM is not suited for solving black-box optimization\nproblems, where explicit gradient forms are difficult or infeasible to obtain.\nIn this paper, we propose a zeroth-order AdaMM (ZO-AdaMM) algorithm, that\ngeneralizes AdaMM to the gradient-free regime. We show that the convergence\nrate of ZO-AdaMM for both convex and nonconvex optimization is roughly a factor\nof O(\√(d)) worse than that of the first-order AdaMM algorithm, where d\nis problem size. In particular, we provide a deep understanding on why\nMahalanobis distance matters in convergence of ZO-AdaMM and other AdaMM-type\nmethods. As a byproduct, our analysis makes the first step toward understanding\nadaptive learning rate methods for nonconvex constrained optimization.\nFurthermore, we demonstrate two applications, designing per-image and universal\nadversarial attacks from black-box neural networks, respectively. We perform\nextensive experiments on ImageNet and empirically show that ZO-AdaMM converges\nmuch faster to a solution of high accuracy compared with 6 state-of-the-art\nZO optimization methods.\n