Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization
<|reference_start|>Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization: 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.<|reference_end|>
@article{gu2024zeroth-order,
    title={Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess
  Risk Optimization},
    author={Zhihao Gu and Zi Xu},
    journal={arXiv preprint arXiv:2408.12209},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.12209},
    primaryClass={math.OC cs.LG stat.ML}
}