  This manuscript introduces a new optimization framework for machine learning
and AI, named {\bf empirical X-risk minimization (EXM)}. X-risk is a term
introduced to represent a family of compositional measures or objectives, in
which each data point is compared with a large number of items explicitly or
implicitly for defining a risk function. It includes surrogate objectives of
many widely used measures and non-decomposable losses, e.g., AUROC, AUPRC,
partial AUROC, NDCG, MAP, precision/recall at top $K$ positions, precision at a
certain recall level, listwise losses, p-norm push, top push, global
contrastive losses, etc. While these non-decomposable objectives and their
optimization algorithms have been studied in the literature of machine
learning, computer vision, information retrieval, and etc, optimizing these
objectives has encountered some unique challenges for deep learning. In this
paper, we present recent rigorous efforts for EXM with a focus on its
algorithmic foundations and its applications. We introduce a class of
algorithmic techniques for solving EXM with smooth non-convex objectives. We
formulate EXM into three special families of non-convex optimization problems
belonging to non-convex compositional optimization, non-convex min-max
optimization and non-convex bilevel optimization, respectively. For each family
of problems, we present some strong baseline algorithms and their complexities,
which will motivate further research for improving the existing results.
Discussions about the presented results and future studies are given at the
end. Efficient algorithms for optimizing a variety of X-risks are implemented
in the LibAUC library at \url{www.libauc.org}.
