Balazs Szorenyi — accepted AI-conference papers

2022

Regret Bounds for Multilabel Classification in Sparse Label Regimes

Robert Istvan Busa-Fekete, Heejin Choi, Krzysztof Dembczynski, Claudio Gentile, Henry William Reeve, Balazs Szorenyi

NeurIPS 2022accept

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@$…

Cited by 2 Source ↗PDF ↗Scholar ↗

2021

Identity testing for Mallows model

Robert Istvan Busa-Fekete, Dimitris Fotakis, Balazs Szorenyi, Manolis Zampetakis

NeurIPS 2021poster

In this paper, we devise identity tests for ranking data that is generated from Mallows model both in the \emph{asymptotic} and \emph{non-asymptotic} settings. First we consider the case when the central ranking is known, and devise two algorithms for testing the spread parameter of the Mallows mode…

Cited by 6 Source ↗PDF ↗Scholar ↗

2019

Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case

Alina Beygelzimer, David Pal, Balazs Szorenyi, Devanathan Thiruvenkatachari, Chen-Yu Wei, Chicheng Zhang

ICML 2019oral

We study the problem of efficient online multiclass linear classification with bandit feedback, where all examples belong to one of $K$ classes and lie in the $d$-dimensional Euclidean space. Previous works have left open the challenge of designing efficient algorithms with finite mistake bounds whe…

Cited by 18 Source ↗PDF ↗Scholar ↗

2019

The information-theoretic value of unlabeled data in semi-supervised learning

Alexander Golovnev, David Pal, Balazs Szorenyi

ICML 2019oral

We quantify the separation between the numbers of labeled examples required to learn in two settings: Settings with and without the knowledge of the distribution of the unlabeled data. More specifically, we prove a separation by $\Theta(\log n)$ multiplicative factor for the class of projections ove…

Cited by 13 Source ↗PDF ↗Scholar ↗

2016

Distributed Clustering of Linear Bandits in Peer to Peer Networks

Nathan Korda, Balazs Szorenyi, Shuai Li

ICML 2016poster

We provide two distributed confidence ball algorithms for solving linear bandit problems in peer to peer networks with limited communication capabilities. For the first, we assume that all the peers are solving the same linear bandit problem, and prove that our algorithm achieves the optimal asympto…

Cited by 193 Source ↗PDF ↗Scholar ↗

2015

Qualitative Multi-Armed Bandits: A Quantile-Based Approach

Balazs Szorenyi, Robert Busa-Fekete, Paul Weng, Eyke Hüllermeier

ICML 2015poster

We formalize and study the multi-armed bandit (MAB) problem in a generalized stochastic setting, in which rewards are not assumed to be numerical. Instead, rewards are measured on a qualitative scale that allows for comparison but invalidates arithmetic operations such as averaging. Correspondingly,…

Cited by 60 Source ↗PDF ↗Scholar ↗