Online Boosting for Multilabel Ranking with Top-k Feedback
This work addresses a practical limitation in online learning for multilabel ranking, offering an incremental improvement for scenarios with partial feedback.
The paper tackles the problem of multilabel ranking with limited top-k feedback by proposing online boosting algorithms that use a novel surrogate loss and unbiased estimator, achieving performance bounds close to full-information methods with a small performance gap in experiments.
We present online boosting algorithms for multilabel ranking with top-k feedback, where the learner only receives information about the top k items from the ranking it provides. We propose a novel surrogate loss function and unbiased estimator, allowing weak learners to update themselves with limited information. Using these techniques we adapt full information multilabel ranking algorithms (Jung and Tewari, 2018) to the top-k feedback setting and provide theoretical performance bounds which closely match the bounds of their full information counterparts, with the cost of increased sample complexity. These theoretical results are further substantiated by our experiments, which show a small gap in performance between the algorithms for the top-k feedback setting and that for the full information setting across various datasets.