Published on Wed May 29 2019

Zeroth-Order Stochastic Alternating Direction Method of Multipliers for Nonconvex Nonsmooth Optimization

Feihu Huang, Shangqian Gao, Songcan Chen, Heng Huang

Alternating direction method of multipliers (ADMM) is a popular optimization tool for the composite and constrained problems in machine learning. In many machine learning problems such as black-box attacks and bandit feedback, ADMM could fail because the explicit gradients of these problems are difficult or infeasible.

0
0
0
Abstract

Alternating direction method of multipliers (ADMM) is a popular optimization tool for the composite and constrained problems in machine learning. However, in many machine learning problems such as black-box attacks and bandit feedback, ADMM could fail because the explicit gradients of these problems are difficult or infeasible to obtain. Zeroth-order (gradient-free) methods can effectively solve these problems due to that the objective function values are only required in the optimization. Recently, though there exist a few zeroth-order ADMM methods, they build on the convexity of objective function. Clearly, these existing zeroth-order methods are limited in many applications. In the paper, thus, we propose a class of fast zeroth-order stochastic ADMM methods (i.e., ZO-SVRG-ADMM and ZO-SAGA-ADMM) for solving nonconvex problems with multiple nonsmooth penalties, based on the coordinate smoothing gradient estimator. Moreover, we prove that both the ZO-SVRG-ADMM and ZO-SAGA-ADMM have convergence rate of , where denotes the number of iterations. In particular, our methods not only reach the best convergence rate for the nonconvex optimization, but also are able to effectively solve many complex machine learning problems with multiple regularized penalties and constraints. Finally, we conduct the experiments of black-box binary classification and structured adversarial attack on black-box deep neural network to validate the efficiency of our algorithms.

Tue Jul 30 2019
Machine Learning
Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
Zeroth-order methods powerful optimization tools for solving many machine learning problems. They only need function values (not gradient) in the optimization. We propose a class of faster zerOTH-order stochastic alternating direction method of multipliers (ADMM) methods (ZO-SPIDER-ADMM), to solve the nonconvex finite-sum problems.
0
0
0
Tue Oct 15 2019
Machine Learning
ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
The adaptive momentum method (AdaMM) 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. We propose a
0
0
0
Mon Sep 30 2019
Machine Learning
Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
In this paper, we study the problem of constrained robust (min-max)optimization in a black-box setting. We show that the proposed framework, referred to as ZO-Min-Max, has a sub-linear convergence rate under mildly conditions.
0
0
0
Sun Jun 02 2019
Machine Learning
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
We consider nonconvex-concave minimax problems. The celebrated gradient descent ascent (GDA) algorithm is widely used in machine learning, control theory and economics. To the best our knowledge, this is the first nonasymptotic analysis for two-time-scale GDA.
0
0
0
Sun Aug 01 2021
Machine Learning
Zeroth-Order Alternating Randomized Gradient Projection Algorithms for General Nonconvex-Concave Minimax Problems
Zeroth-order algorithms for nonconvex-concave minimax problems have attracted widely attention in machine learning, signal processing and many other fields in recent years. We propose a zerOTH-order.alternating randomized gradient projection (ZO-AGP) algorithm for smooth.nonconveX-Concave minimax problems.
8
0
0
Wed May 30 2018
Machine Learning
Stochastic Zeroth-order Optimization via Variance Reduction method
Derivative-free optimization has become an important technique used in machine learning for optimizing black-box models. We introduce a novel Stochastic Zeroth-order method with Variance Reduction under Gaussian smoothing (SZVR-G)
0
0
0