Algorithmic Foundation of Deep X-Risk Optimization
X-risk is a term introduced to represent a family of compositional measures
or objectives, in which each data point is compared with a set of data points
explicitly or implicitly for defining a risk function. It includes many widely
used measures or objectives, e.g., AUROC, AUPRC, partial AUROC, NDCG, MAP,
top-$K$ NDCG, top-$K$ MAP, listwise losses, p-norm push, top push,
precision/recall at top $K$ positions, precision at a certain recall level,
contrastive objectives, etc. While these measures/objectives and their
optimization algorithms have been studied in the literature of machine
learning, computer vision, information retrieval, and etc, optimizing these
measures/objectives has encountered some unique challenges for deep learning.
In this technical report, we survey our recent rigorous efforts for deep X-risk
optimization (DXO) by focusing on its algorithmic foundation. We introduce a
class of techniques for optimizing X-risk for deep learning. We formulate DXO
into three special families of non-convex optimization problems belonging to
non-convex min-max optimization, non-convex compositional 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 www.libauc.org.