Timezone: »

 
Poster
Regret Bounds for Multilabel Classification in Sparse Label Regimes
Róbert Busa-Fekete · Heejin Choi · Krzysztof Dembczynski · Claudio Gentile · Henry Reeve · Balazs Szorenyi

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #810
in Poster Session 2 »
Multi-label classification (MLC) has wide practical importance, but the theoretical understanding of its statistical properties is still limited. As an attempt to fill this gap, we thoroughly study upper and lower regret bounds for two canonical MLC performance measures, Hamming loss and Precision@$\kappa$. We consider two different statistical and algorithmic settings, a non-parametric setting tackled by plug-in classifiers \`a la $k$-nearest neighbors, and a parametric one tackled by empirical risk minimization operating on surrogate loss functions. For both, we analyze the interplay between a natural MLC variant of the low noise assumption, widely studied in binary classification, and the label sparsity, the latter being a natural property of large-scale MLC problems. We show that those conditions are crucial in improving the bounds, but the way they are tangled is not obvious, and also different across the two settings.
Keywords: sparse multilabel classification · regret bounds
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Róbert Busa-Fekete (Google Research)
Heejin Choi (Google)
Krzysztof Dembczynski (Yahoo Research)
Claudio Gentile (Google Research)
Henry Reeve (Bristol University)
Balazs Szorenyi (Yahoo Research)

* 2018 - Research Scientist at Yahoo Research * 2014-2017 Academic visitor at Technion * 2012-2013 Postdoc at Inria Lille * 2008-2009 Postdoc at Ruhr-University Bochum * 2003-2017 Research Assistant/Fellow at Research Group on AI at the University of Szeged Industrial projects: * developing/implementing ML solutions for prediction in online advertising Academic interests: * theoretical problems in machine learning * bandits * reinforcement learning

More from the Same Authors