Zeroth-Order Methods for Convex-Concave Minmax Problems: Learning from Strategically Generated Data
summary
Recasts decision dependent robustness into a finite dimensional convex concave min max via Wasserstein DRO and a strategic agent model where utility equals positive classification gain minus a convex cost to change features. Proposes a practical zeroth-order optimistic GDA with random reshuffling, using one point and two point gradient estimators. Proves a one point rate ~T^{-1/4}, two point improves to O(d^2 / sqrt T), and first order reshuffling gives 1/√T. Synthetic GLM tests show reshuffling helps and the robust solution degrades much slower under perturbations.
AI-written summary · about
chapters (22)
- 0:00Introduction
- 0:26Machine learning overview
- 2:17Challenges in ML
- 6:17Problem formulation
- 7:48Game theoretic framework
- 11:01Wasserstein robustness
- 14:15Zeroth order methods
- 15:36Min-max optimization
- 17:21Algorithm overview
- 19:03Optimistic gradient descent
- 20:43Zeroth order estimator
- 24:03Random reshuffling
- 26:58Convergence metric
- 28:47Convergence analysis
- 31:24Proof sketches
- 34:09Proximal point method
- 37:03Proof completion
- 39:01Q&A on coupling
- 43:54Numerical experiments
- 47:24Open problems
- 50:56Conclusion
- 52:03Final Q&A
related talks
01h 01mRobustness, Stochastics, Uncertainty 2
01h 08mData Driven Optimization Models and Algorithms
58mFirst-Order Stochastic Optimization
46mCan Non-Convex Optimization be Robust?
42mWhat (Doesn't) Make Learning Algorithms Generalize?
01h 01mOptimization's Untold Gift to Learning: Implicit Regularization
09mTowards Credible and Effective Data-Driven Decision-Making
42mA Primal-dual Analysis of Margin Maximization by Steepest Descent Methods