Timezone: »

Min-Max Optimization without Gradients: Convergence and Applications to Black-Box Evasion and Poisoning Attacks
Sijia Liu · Songtao Lu · Xiangyi Chen · Yao Feng · Kaidi Xu · Abdullah Al-Dujaili · Mingyi Hong · Una-May O'Reilly

Tue Jul 14 07:00 AM -- 07:45 AM & Tue Jul 14 06:00 PM -- 06:45 PM (PDT) @ None #None

In this paper, we study the problem of constrained min-max optimization in a 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 sublinear convergence rate under mild conditions and scales gracefully with problem size. We also 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.

Author Information

Sijia Liu (MIT-IBM Watson AI Lab)

Sijia Liu is a Research Staff Member at MIT-IBM Watson AI Lab, IBM research. Prior to joining in IBM Research, he was a Postdoctoral Research Fellow at the University of Michigan, Ann Arbor. He received the Ph.D. degree (with All University Doctoral Prize) in electrical and computer engineering from Syracuse University, NY, USA, in 2016. His recent research interests include deep learning, adversarial machine learning, gradient-free optimization, nonconvex optimization, and graph data analytics. He received the Best Student Paper Finalist Award at Asilomar Conference on Signals, Systems, and Computers (Asilomar'13). He received the Best Student Paper Award at the 42nd IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP'17). He served as a general chair of the Symposium 'Signal Processing for Adversarial Machine Learning' at GlobalSIP, 2018. He is also the co-chair of the workshop 'Adversarial Learning Methods for Machine Learning and Data Mining' at KDD, 2019.

Songtao Lu (IBM Research)
Xiangyi Chen (University of Minnesota)
Yao Feng (Tsinghua University)
Kaidi Xu (Northeastern University)
Abdullah Al-Dujaili (CSAIL)
Mingyi Hong (University of Minnesota)
Una-May O'Reilly (MIT)

More from the Same Authors