8397
2021
eng
article
0
--
--
--
Efficient Online-Bandit Strategies for Minimax Learning Problems
Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning
[Namkoong and Duchi, 2016, Curi et al., 2020] or learning with non-standard aggregated losses [Shalev-
Shwartz and Wexler, 2016, Fan et al., 2017]. More specifically, these problems are convex-linear problems
where the minimization is carried out over the model parameters w ∈ W and the maximization over the
empirical distribution p ∈ K of the training set indexes, where K is the simplex or a subset of it. To design
efficient methods, we let an online learning algorithm play against a (combinatorial) bandit algorithm.
We argue that the efficiency of such approaches critically depends on the structure of K and propose two
properties of K that facilitate designing efficient algorithms. We focus on a specific family of sets Sn,k
encompassing various learning applications and provide high-probability convergence guarantees to the
minimax values.
no
publish
Christophe Roux
Roux
Sebastian Pokutta
Elias Wirth
Thomas Kerdreux
MODAL-SynLab
MODAL-Gesamt
Pokutta, Sebastian
AI in Society, Science, and Technology
Roux, Christophe
Math+AA3-7