Empirical Risk Minimization with -Divergence Regularization
arXiv:2601.13191
Abstract
In this paper, the solution to the empirical risk minimization problem with -divergence regularization (ERM-DR) is presented and conditions under which the solution also serves as the solution to the minimization of the expected empirical risk subject to an -divergence constraint are established. The proposed approach extends applicability to a broader class of -divergences than previously reported and yields theoretical results that recover previously known results. Additionally, the difference between the expected empirical risk of the ERM-DR solution and that of its reference measure is characterized, providing insights into previously studied cases of -divergences. A central contribution is the introduction of the normalization function, a mathematical object that is critical in both the dual formulation and practical computation of the ERM-DR solution. This work presents an implicit characterization of the normalization function as a nonlinear ordinary differential equation (ODE), establishes its key properties, and subsequently leverages them to construct a numerical algorithm for approximating the normalization factor under mild assumptions. Further analysis demonstrates structural equivalences between ERM-DR problems with different -divergences via transformations of the empirical risk. Finally, the proposed algorithm is used to compute the training and test risks of ERM-DR solutions under different -divergence regularizers. This numerical example highlights the practical implications of choosing different functions in ERM-DR problems.
Submitted to IEEE Transactions on Information Theory. arXiv admin note: substantial text overlap with arXiv:2502.14544, arXiv:2508.03314