  The notion of omnipredictors (Gopalan, Kalai, Reingold, Sharan and Wieder
ITCS 2021), suggested a new paradigm for loss minimization. Rather than
learning a predictor based on a known loss function, omnipredictors can easily
be post-processed to minimize any one of a rich family of loss functions
compared with the loss of hypotheses in a class $\mathcal C$. It has been shown
that such omnipredictors exist and are implied (for all convex and Lipschitz
loss functions) by the notion of multicalibration from the algorithmic fairness
literature. In this paper, we introduce omnipredictors for constrained
optimization and study their complexity and implications. The notion that we
introduce allows the learner to be unaware of the loss function that will be
later assigned as well as the constraints that will be later imposed, as long
as the subpopulations that are used to define these constraints are known. We
show how to obtain omnipredictors for constrained optimization problems,
relying on appropriate variants of multicalibration. We also investigate the
implications of this notion when the constraints used are so-called group
fairness notions.

Machine Learning;Computers and Society;Data Structures and Algorithms;Optimization and Control