Strong Duality Relations in Nonconvex Risk-Constrained Learning
Dionysis Kalogerias Spyridon Pougkakiotis
We establish strong duality relations for functional two-step compositional
risk-constrained learning problems with multiple nonconvex loss functions
and/or learning constraints, regardless of nonconvexity and under a minimal set
of technical assumptions. Our results in particular imply zero duality gaps
within the class of problems under study, both extending and improving on the
state of the art in (risk-neutral) constrained learning. More specifically, we
consider risk objectives/constraints which involve real-valued convex and
positively homogeneous risk measures admitting dual representations with
bounded risk envelopes, generalizing expectations and including popular
examples, such as the conditional value-at-risk (CVaR), the mean-absolute
deviation (MAD), and more generally all real-valued coherent risk measures on
integrable losses as special cases. Our results are based on recent advances in
risk-constrained nonconvex programming in infinite dimensions, which rely on a
remarkable new application of J. J. Uhl's convexity theorem, which is an
extension of A. A. Lyapunov's convexity theorem for general, infinite
dimensional Banach spaces. By specializing to the risk-neutral setting, we
demonstrate, for the first time, that constrained classification and regression
can be treated under a unifying lens, while dispensing certain restrictive
assumptions enforced in the current literature, yielding a new state-of-the-art
strong duality framework for nonconvex constrained learning.