Feasible Learning
Authors: name: Juan Ramirez, name: Ignacio Hounie, name: Juan Elenter, name: Jose Gallego-Posada, name: Meraj Hashemizadeh, name: Alejandro Ribeiro, name: Simon Lacoste-Julien

We introduce Feasible Learning (FL), a sample-centric learning paradigm where
models are trained by solving a feasibility problem that bounds the loss for
each training sample. In contrast to the ubiquitous Empirical Risk Minimization
(ERM) framework, which optimizes for average performance, FL demands
satisfactory performance on every individual data point. Since any model that
meets the prescribed performance threshold is a valid FL solution, the choice
of optimization algorithm and its dynamics play a crucial role in shaping the
properties of the resulting solutions. In particular, we study a primal-dual
approach which dynamically re-weights the importance of each sample during
training. To address the challenge of setting a meaningful threshold in
practice, we introduce a relaxation of FL that incorporates slack variables of
minimal norm. Our empirical analysis, spanning image classification, age
regression, and preference optimization in large language models, demonstrates
that models trained via FL can learn from data while displaying improved tail
behavior compared to ERM, with only a marginal impact on average performance.