Min-Max Optimization without Gradients: Convergence and Applications to Black-Box Evasion and Poisoning Attacks
Min-Max Optimization without Gradients: Convergence and Applications to Black-Box Evasion and Poisoning Attacks
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Sijia Liu;Songtao Lu;Xiangyi Chen;Yao Feng;Kaidi Xu;Abdullah Al-Dujaili;Mingyi Hong;Una-May O’Reilly
中科院分区：
文献类型：
--
作者：
Sijia Liu;Songtao Lu;Xiangyi Chen;Yao Feng;Kaidi Xu;Abdullah Al-Dujaili;Mingyi Hong;Una-May O’Reilly
在本文中，我们研究了在黑盒设置，所需的优化器不能访问目标函数的梯度，但可以查询其值的约束最小-最大优化问题。我们提出了一个原则性的优化框架，将零阶（ZO）梯度估计与交替投影随机梯度下降-上升方法相结合，前者只需要少量的函数查询，后者只需要一步下降/上升更新。我们表明，所提出的框架，简称为ZO-Min-Max，具有次线性收敛速度在温和的条件下，并优雅地与问题的大小规模。我们还探索了对抗性机器学习（ML）中黑盒最小-最大优化与黑盒规避和中毒攻击之间有希望的联系。我们对这些用例的经验评估证明了我们的方法的有效性及其可扩展性，禁止使用最近的黑盒求解器。
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 sub-linear 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.