2020/07/16 by Feihu Huang, Huang, Feihu, Lue Tao +3 · 8 citations
Computer Science · Mathematics · #Algorithm #Applied mathematics #Combinatorics #Computer Vision and Pattern Recognition (cs.CV) #Computer science #FOS: Computer and information sciences #FOS: Mathematics #Function (biology) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Order (exchange) #Projection (relational algebra) #Stochastic Gradient Optimization Techniques #Stochastic optimization #cs.CV #cs.LG #math.OC
paper · pdf · doi:10.48550/arxiv.2007.12625
published in arXiv (Cornell University) 1, 4519-4530 (Cornell University) · Accepted to ICML 2020, 34 pages
openalex publication_date 2020/07/16 · arxiv created 2020/08/10 · arxiv updated 2020/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the paper, we propose a class of accelerated stochastic gradient-free and projection-free (a.k.a., zeroth-order Frank-Wolfe) methods to solve the constrained stochastic and finite-sum nonconvex optimization. Specifically, we propose an accelerated stochastic zeroth-order Frank-Wolfe (Acc-SZOFW) method based on the variance reduced technique of SPIDER/SpiderBoost and a novel momentum accelerated technique. Moreover, under some mild conditions, we prove that the Acc-SZOFW has the function query complexity of O(d√(n)ε-2) for finding an ε-stationary point in the finite-sum problem, which improves the exiting best result by a factor of O(√(n)ε-2), and has the function query complexity of O(dε-3) in the stochastic problem, which improves the exiting best result by a factor of O(ε-1). To relax the large batches required in the Acc-SZOFW, we further propose a novel accelerated stochastic zeroth-order Frank-Wolfe (Acc-SZOFW*) based on a new variance reduced technique of STORM, which still reaches the function query complexity of O(dε-3) in the stochastic problem without relying on any large batches. In particular, we present an accelerated framework of the Frank-Wolfe methods based on the proposed momentum accelerated technique. The extensive experimental results on black-box adversarial attack and robust black-box classification demonstrate the efficiency of our algorithms.