A Mosco sufficient condition for intrinsic stability of non-unique convex Empirical Risk Minimization
This work addresses stability issues in ERM for machine learning practitioners dealing with non-unique convex losses, offering theoretical guarantees for set-valued solutions, but it is incremental as it builds on existing stability concepts.
The paper tackles the problem of stability in empirical risk minimization (ERM) for convex non-strict losses, which yield set-valued minimizers, by identifying Painlevé-Kuratowski upper semicontinuity as the intrinsic stability notion and showing that Mosco-consistent perturbations and locally bounded minimizers imply this stability, with quadratic growth providing explicit quantitative deviation bounds.
Empirical risk minimization (ERM) stability is usually studied via single-valued outputs, while convex non-strict losses yield set-valued minimizers. We identify Painlevé-Kuratowski upper semicontinuity (PK-u.s.c.) as the intrinsic stability notion for the ERM solution correspondence (set-level Hadamard well-posedness) and a prerequisite to interpret stability of selections. We then characterize a minimal non-degenerate qualitative regime: Mosco-consistent perturbations and locally bounded minimizers imply PK-u.s.c., minimal-value continuity, and consistency of vanishing-gap near-minimizers. Quadratic growth yields explicit quantitative deviation bounds.