Generalization Error of $f$-Divergence Stabilized Algorithms via Duality
This work provides theoretical insights into generalization for machine learning algorithms, but appears incremental as it extends existing regularization methods.
The paper tackles the generalization error of f-divergence stabilized algorithms by introducing a dual formulation for empirical risk minimization with f-divergence regularization, enabling explicit characterizations of generalization error under mild conditions.
The solution to empirical risk minimization with $f$-divergence regularization (ERM-$f$DR) is extended to constrained optimization problems, establishing conditions for equivalence between the solution and constraints. A dual formulation of ERM-$f$DR is introduced, providing a computationally efficient method to derive the normalization function of the ERM-$f$DR solution. This dual approach leverages the Legendre-Fenchel transform and the implicit function theorem, enabling explicit characterizations of the generalization error for general algorithms under mild conditions, and another for ERM-$f$DR solutions.