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
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.
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
-
2021 Spotlight: Online Active Learning with Surrogate Loss Functions »
Giulia DeSalvo · Claudio Gentile · Tobias Sommer Thune -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2022 Poster: Private and Communication-Efficient Algorithms for Entropy Estimation »
Gecia Bravo-Hermsdorff · Róbert Busa-Fekete · Mohammad Ghavamzadeh · Andres Munoz Medina · Umar Syed -
2022 Poster: Best of Both Worlds Model Selection »
Aldo Pacchiano · Christoph Dann · Claudio Gentile -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 Poster: Batch Active Learning at Scale »
Gui Citovsky · Giulia DeSalvo · Claudio Gentile · Lazaros Karydas · Anand Rajagopalan · Afshin Rostamizadeh · Sanjiv Kumar -
2021 Poster: Online Active Learning with Surrogate Loss Functions »
Giulia DeSalvo · Claudio Gentile · Tobias Sommer Thune -
2021 Poster: Identity testing for Mallows model »
Róbert Busa-Fekete · Dimitris Fotakis · Balazs Szorenyi · Emmanouil Zampetakis -
2021 Poster: Private and Non-private Uniformity Testing for Ranking Data »
Róbert Busa-Fekete · Dimitris Fotakis · Emmanouil Zampetakis -
2021 Poster: Neural Active Learning with Performance Guarantees »
Zhilei Wang · Pranjal Awasthi · Christoph Dann · Ayush Sekhari · Claudio Gentile -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2019 Poster: Flattening a Hierarchical Clustering through Active Learning »
Fabio Vitale · Anand Rajagopalan · Claudio Gentile -
2018 Poster: Online Reciprocal Recommendation with Theoretical Performance Guarantees »
Claudio Gentile · Nikos Parotsidis · Fabio Vitale -
2018 Poster: A no-regret generalization of hierarchical softmax to extreme multi-label classification »
Marek Wydmuch · Kalina Jasinska-Kobus · Mikhail Kuznetsov · Róbert Busa-Fekete · Krzysztof Dembczynski -
2018 Poster: Distributed Stochastic Optimization via Adaptive SGD »
Ashok Cutkosky · Róbert Busa-Fekete -
2015 Poster: Online F-Measure Optimization »
Róbert Busa-Fekete · Balázs Szörényi · Krzysztof Dembczynski · Eyke Hüllermeier -
2015 Poster: Online Rank Elicitation for Plackett-Luce: A Dueling Bandits Approach »
Balázs Szörényi · Róbert Busa-Fekete · Adil Paul · Eyke Hüllermeier -
2011 Poster: An Exact Algorithm for F-Measure Maximization »
Krzysztof Dembczynski · Willem Waegeman · Weiwei Cheng · Eyke Hullermeier