Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization
Not on the map. Why?
Abstract (arXiv)
The minimax excess risk optimization (MERO) problem is a new variation of the traditional distributionally robust optimization (DRO) problem, which achieves uniformly low regret across all test distributions under suitable conditions. In this paper, we propose a zeroth-order stochastic mirror descent (ZO-SMD) algorithm available for both smooth and non-smooth MERO to estimate the minimal risk of each distrbution, and finally solve MERO as (non-)smooth stochastic convex-concave (linear) minimax optimization problems. The proposed algorithm is proved to converge at optimal convergence rates of Oleft(1/√tright) on the estimate of Ri^* and Oleft(1/√tright) on the optimization error of both smooth and non-smooth MERO. Numerical results show the efficiency of the proposed algorithm.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 40 of its 62 references that are in the map. First posted on arXiv 22 Aug 2024.
Builds on
40 of 62 references.
References · 40
- 2019Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalizationcited by 1,232
- 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
- 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 334
- 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
- 2015Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulationscited by 285
- 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
- 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
- 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
- 2016Statistics of Robust Optimization: A Generalized Empirical Likelihood Approachcited by 182
- 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
- 2019Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learningcited by 169
- 2016Variance-based regularization with convex objectivescited by 153
28 more
- 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
- 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
- 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
- 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
- 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
- 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
- 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
- 2020An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectivescited by 42
- 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
- 2021Non-convex Distributionally Robust Optimization: Non-asymptotic Analysiscited by 39
- 2022Minimax Regret Optimization for Robust Machine Learning under Distribution Shiftcited by 31
- 2020Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexitiescited by 21
- 2021Zeroth order optimization with orthogonal random directionscited by 21
- 2017Stochastic Recursive Gradient Algorithm for Nonconvex Optimizationcited by 20
- 2021Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimizationcited by 18
- 2018Inexact SARAH Algorithm for Stochastic Optimizationcited by 12
- 2019Optimistic Distributionally Robust Optimization for Nonparametric Likelihood Approximationcited by 12
- 2018SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithmscited by 10
- 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 10
- 2014Oracle-Based Robust Optimization via Online Learningcited by 9
- 2019Min-Max Optimization without Gradients: Convergence and Applications to Adversarial MLcited by 9
- 2017Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parametercited by 8
- 2022Stochastic Zeroth order Descent with Structured Directionscited by 8
- 2020Zeroth-Order Algorithms for Smooth Saddle-Point Problemscited by 7
- 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemscited by 7
- 2023Efficient Stochastic Approximation of Minimax Excess Risk Optimizationcited by 4
- 2020Geometry-Aware Universal Mirror-Proxcited by 2
- 2023Robust Analysis of Almost Sure Convergence of Zeroth-Order Mirror Descent Algorithmcited by 1
Built on by
Citing papers per year: 2025: 1.
1 paper.