Sharp Analysis of Learning with Discrete Losses
This work addresses the challenge of devising learning strategies for discrete losses like multilabeling and ranking, which is incremental as it builds on existing methods with quantitative improvements.
The authors tackled the problem of learning with discrete losses by proposing a least-squares framework to systematically design algorithms, improving existing results with explicit dependence on label counts and faster rates in low-noise conditions, as validated by experiments on real datasets.
The problem of devising learning strategies for discrete losses (e.g., multilabeling, ranking) is currently addressed with methods and theoretical analyses ad-hoc for each loss. In this paper we study a least-squares framework to systematically design learning algorithms for discrete losses, with quantitative characterizations in terms of statistical and computational complexity. In particular we improve existing results by providing explicit dependence on the number of labels for a wide class of losses and faster learning rates in conditions of low-noise. Theoretical results are complemented with experiments on real datasets, showing the effectiveness of the proposed general approach.