Abstract
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.
Original language | English (US) |
---|---|
Title of host publication | 37th International Conference on Machine Learning, ICML 2020 |
Editors | Hal Daume, Aarti Singh |
Publisher | International Machine Learning Society (IMLS) |
Pages | 6238-6249 |
Number of pages | 12 |
ISBN (Electronic) | 9781713821120 |
State | Published - 2020 |
Event | 37th International Conference on Machine Learning, ICML 2020 - Virtual, Online Duration: Jul 13 2020 → Jul 18 2020 |
Publication series
Name | 37th International Conference on Machine Learning, ICML 2020 |
---|---|
Volume | PartF168147-9 |
Conference
Conference | 37th International Conference on Machine Learning, ICML 2020 |
---|---|
City | Virtual, Online |
Period | 7/13/20 → 7/18/20 |
Bibliographical note
Publisher Copyright:© 2020 37th International Conference on Machine Learning, ICML 2020. All rights reserved.