Published August 2021 | Version v1
Journal article

Box-constrained optimization for minimax supervised learning

Description

In this paper, we present the optimization procedure for computing the discrete boxconstrained minimax classifier introduced in [1, 2]. Our approach processes discrete or beforehand discretized features. A box-constrained region defines some bounds for each class proportion independently. The box-constrained minimax classifier is obtained from the computation of the least favorable prior which maximizes the minimum empirical risk of error over the box-constrained region. After studying the discrete empirical Bayes risk over the probabilistic simplex, we consider a projected subgradient algorithm which computes the prior maximizing this concave multivariate piecewise affine function over a polyhedral domain. The convergence of our algorithm is established.

Abstract (French)

Nous présentons dans cet article le problème d'optimisation lié au calcul d'un classifieur minimax à contrainte de boîte, ainsi que l'algorithme permettant de calibrer ce classifieur, que nous avons introduit dans [1, 2]. Notre approche considère des variables descriptives discrètes ou préalablement discrétisées. Les contraintes de boîte définissent des bornes sur chaque proporition par classe. Le classifieur est calibré en calculant la distribution a priori qui maximise le risque d'erreur minimum sur le simplexe contraint par boîte. Après avoir montré que ce risque d'erreur minimum est une fonction concave affine par morceaux avec un nombre fini de faces sur le simplexe, nous considérons un algorithme de sous-gradient projeté pour calculer la distribution a priori qui maximise ce risque de Bayes discret sur un domaine polyhédral. La convergence de l'algorithme est démontrée.

Abstract

International audience

Additional details

Created:
December 3, 2022
Modified:
November 28, 2023