Timezone: »
Poster
Correlation Clustering with Adaptive Similarity Queries
Marco Bressan · Nicolò Cesa-Bianchi · Andrea Paudice · Fabio Vitale
Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #29
In correlation clustering, we are given $n$ objects together with a binary similarity score between each pair of them.
The goal is to partition the objects into clusters so to minimise the disagreements with the scores.
In this work we investigate correlation clustering as an active learning problem: each similarity score can be learned by making a query, and the goal is to minimise both the disagreements and the total number of queries.
On the one hand, we describe simple active learning algorithms, which provably achieve an almost optimal trade-off while giving cluster recovery guarantees, and we test them on different datasets.
On the other hand, we prove information-theoretical bounds on the number of queries necessary to guarantee a prescribed disagreement bound.
These results give a rich characterization of the trade-off between queries and clustering error.
Author Information
Marco Bressan (Sapienza University of Rome)
Nicolò Cesa-Bianchi (Università degli Studi di Milano)
Andrea Paudice (University of Milan)
Fabio Vitale (University of Lille - INRIA Lille (France))
More from the Same Authors
-
2023 Poster: On the Minimax Regret for Online Learning with Feedback Graphs »
Khaled Eldowa · Emmanuel Esposito · Tom Cesari · Nicolò Cesa-Bianchi -
2023 Poster: Multitask Learning with No Regret: from Improved Confidence Bounds to Active Learning »
Pier Giuseppe Sessa · Pierre Laforgue · Nicolò Cesa-Bianchi · Andreas Krause -
2022 Poster: Active Learning of Classifiers with Label and Seed Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice · Maximilian Thiessen -
2022 Poster: A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs »
Chloé Rouyer · Dirk van der Hoeven · Nicolò Cesa-Bianchi · Yevgeny Seldin -
2022 Poster: Learning on the Edge: Online Learning with Stochastic Feedback Graphs »
Emmanuel Esposito · Federico Fusco · Dirk van der Hoeven · Nicolò Cesa-Bianchi -
2022 Poster: A Regret-Variance Trade-Off in Online Learning »
Dirk van der Hoeven · Nikita Zhivotovskiy · Nicolò Cesa-Bianchi -
2021 Poster: Beyond Bandit Feedback in Online Multiclass Classification »
Dirk van der Hoeven · Federico Fusco · Nicolò Cesa-Bianchi -
2021 Poster: ROI Maximization in Stochastic Online Decision-Making »
Nicolò Cesa-Bianchi · Tom Cesari · Yishay Mansour · Vianney Perchet -
2021 Poster: On Margin-Based Cluster Recovery with Oracle Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice -
2020 Poster: Locally-Adaptive Nonparametric Online Learning »
Ilja Kuzborskij · Nicolò Cesa-Bianchi -
2020 Poster: Exact Recovery of Mangled Clusters with Same-Cluster Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice -
2020 Oral: Exact Recovery of Mangled Clusters with Same-Cluster Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice -
2020 Session: Orals & Spotlights Track 11: Learning Theory »
Dylan Foster · Nicolò Cesa-Bianchi -
2019 Poster: Flattening a Hierarchical Clustering through Active Learning »
Fabio Vitale · Anand Rajagopalan · Claudio Gentile -
2019 Poster: Nonstochastic Multiarmed Bandits with Unrestricted Delays »
Tobias Sommer Thune · Nicolò Cesa-Bianchi · Yevgeny Seldin -
2018 Poster: Online Reciprocal Recommendation with Theoretical Performance Guarantees »
Claudio Gentile · Nikos Parotsidis · Fabio Vitale -
2017 : Poster session »
Nicolò Cesa-Bianchi -
2017 Workshop: Workshop on Prioritising Online Content »
John Shawe-Taylor · Massimiliano Pontil · Nicolò Cesa-Bianchi · Emine Yilmaz · Chris Watkins · Sebastian Riedel · Marko Grobelnik -
2017 Poster: Nonparametric Online Regression while Learning the Metric »
Ilja Kuzborskij · Nicolò Cesa-Bianchi -
2017 Poster: Boltzmann Exploration Done Right »
Nicolò Cesa-Bianchi · Claudio Gentile · Gergely Neu · Gabor Lugosi -
2016 Poster: Efficient Second Order Online Learning by Sketching »
Haipeng Luo · Alekh Agarwal · Nicolò Cesa-Bianchi · John Langford -
2013 Poster: Online Learning with Switching Costs and Other Adaptive Adversaries »
Nicolò Cesa-Bianchi · Ofer Dekel · Ohad Shamir -
2013 Poster: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Oral: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Poster: A Gang of Bandits »
Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2012 Workshop: Multi-Trade-offs in Machine Learning »
Yevgeny Seldin · Guy Lever · John Shawe-Taylor · Nicolò Cesa-Bianchi · Yacov Crammer · Francois Laviolette · Gabor Lugosi · Peter Bartlett -
2012 Poster: A Linear Time Active Learning Algorithm for Link Classification »
Nicolò Cesa-Bianchi · Claudio Gentile · Fabio Vitale · Giovanni Zappella -
2012 Poster: Mirror Descent Meets Fixed Share (and feels no regret) »
Nicolò Cesa-Bianchi · Pierre Gaillard · Gabor Lugosi · Gilles Stoltz -
2011 Workshop: New Frontiers in Model Order Selection »
Yevgeny Seldin · Yacov Crammer · Nicolò Cesa-Bianchi · Francois Laviolette · John Shawe-Taylor -
2011 Poster: Efficient Online Learning via Randomized Rounding »
Nicolò Cesa-Bianchi · Ohad Shamir -
2011 Oral: Efficient Online Learning via Randomized Rounding »
Nicolò Cesa-Bianchi · Ohad Shamir -
2011 Poster: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2011 Spotlight: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2009 Workshop: Learning from Multiple Sources with Applications to Robotics »
Barbara Caputo · Nicolò Cesa-Bianchi · David R Hardoon · Gayle Leen · Francesco Orabona · Jaakko Peltonen · Simon Rogers -
2008 Poster: Linear Classification and Selective Sampling Under Low Noise Conditions »
Giovanni Cavallanti · Nicolò Cesa-Bianchi · Claudio Gentile