Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
This work addresses black-box min-max optimization, which is crucial for adversarial ML applications, but it is incremental as it builds on existing zeroth-order and gradient descent-ascent methods.
The paper tackles constrained robust min-max optimization in a black-box setting without gradient access, proposing the ZO-Min-Max framework that achieves sub-linear convergence and scales well with problem size. Empirical results show effectiveness in adversarial ML applications, such as evasion and poisoning attacks, with scalability to high dimensions where other solvers fail.
In this paper, we study the problem of constrained robust (min-max) optimization ina black-box setting, where the desired optimizer cannot access the gradients of the objective function but may query its values. We present a principled optimization framework, integrating a zeroth-order (ZO) gradient estimator with an alternating projected stochastic gradient descent-ascent method, where the former only requires a small number of function queries and the later needs just one-step descent/ascent update. We show that the proposed framework, referred to as ZO-Min-Max, has a sub-linear convergence rate under mild conditions and scales gracefully with problem size. From an application side, we explore a promising connection between black-box min-max optimization and black-box evasion and poisoning attacks in adversarial machine learning (ML). Our empirical evaluations on these use cases demonstrate the effectiveness of our approach and its scalability to dimensions that prohibit using recent black-box solvers.