New Learning Algorithm Achieves Faster Rates for Swap-Agnostic Proper Losses

Swap-agnostic learning is an advanced machine learning paradigm that extends classical agnostic learning by allowing a comparator to select different hypotheses for each prediction level set. This capability is crucial for scenarios involving prediction-dependent post-processing. However, existing approaches often necessitate solving a separate agnostic learning problem for every possible prediction value, which is computationally intensive. This new work demonstrates that for proper losses, these prediction-level comparisons can be managed jointly. The core contribution is an offline swap-agnostic learner designed for any fixed proper loss. For finite hypothesis classes and smooth proper losses, the method achieves an excess risk of O((log |H|/m)^(2/3)) with 'm' samples, and an online swap-regret bound of O(T^(1/3)(log |H|)^(2/3)) over 'T' time steps. Furthermore, the research provides algorithms that are simultaneously swap-agnostic for entire families of losses. For bounded proper losses, it achieves online and offline rates of O(sqrt(T log |H|)) and O(sqrt(log |H|/m)), respectively. These rates are further improved for convex, 1-Lipschitz proper losses, reaching O(T^(1/3)(log |H|)^(2/3)) online and O((log |H|/m)^(2/3)) offline. These bounds are shown to be tight up to logarithmic factors and represent a significant improvement over prior work.