Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization
This work addresses robust optimization for machine learning under distribution shifts, but it appears incremental as it adapts existing methods to a new problem variant.
The paper tackles the minimax excess risk optimization (MERO) problem, a variation of distributionally robust optimization, by proposing a zeroth-order stochastic mirror descent algorithm that achieves optimal convergence rates of O(1/√t) for both smooth and non-smooth cases, as demonstrated numerically.
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 $\mathcal{O}\left(1/\sqrt{t}\right)$ on the estimate of $R_i^*$ and $\mathcal{O}\left(1/\sqrt{t}\right)$ on the optimization error of both smooth and non-smooth MERO. Numerical results show the efficiency of the proposed algorithm.