Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization
Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
C. Maheshwari;Chih-Yuan Chiu;Eric V. Mazumdar;S. Sastry;L. Ratliff
中科院分区：
文献类型：
--
作者：
C. Maheshwari;Chih-Yuan Chiu;Eric V. Mazumdar;S. Sastry;L. Ratliff
最小最大优化正在成为一个关键的框架，用于分析问题的鲁棒性，以战略和对抗性生成的数据。提出了一种基于随机重排的无梯度乐观梯度下降-上升算法，用于求解具有有限和结构的凹凸极大极小问题。我们证明了该算法具有与求解凸极小化问题的零阶算法相同的收敛速度。我们进一步专门的算法来解决分布鲁棒性，决策相关的学习问题，梯度信息是不容易获得的。通过说明性的模拟，我们观察到，我们提出的方法学习的模型，同时对敌对的分布变化和战略决策的数据源，并优于现有的方法从战略分类文献。
Min-max optimization is emerging as a key framework for analyzing problems of robustness to strategically and adversarially generated data. We propose a random reshuffling-based gradient free Optimistic Gradient Descent-Ascent algorithm for solving convex-concave min-max problems with finite sum structure. We prove that the algorithm enjoys the same convergence rate as that of zeroth-order algorithms for convex minimization problems. We further specialize the algorithm to solve distributionally robust, decision-dependent learning problems, where gradient information is not readily available. Through illustrative simulations, we observe that our proposed approach learns models that are simultaneously robust against adversarial distribution shifts and strategic decisions from the data sources, and outperforms existing methods from the strategic classification literature.