Timezone: »
We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder but pairwise comparisons are easier, and the algorithm can leverage both types of oracles. In this paper, we attempt to characterize how the access to an easier comparison oracle helps in improving the label and total query complexity. We show that the comparison oracle reduces the learning problem to that of learning a threshold function. We then present an algorithm that interactively queries the label and comparison oracles and we characterize its query complexity under Tsybakov and adversarial noise conditions for the comparison and labeling oracles. Our lower bounds show that our label and total query complexity is almost optimal.
Author Information
Yichong Xu (Carnegie Mellon University)
Hongyang Zhang (Carnegie Mellon University)
Aarti Singh (Carnegie Mellon University)
Artur Dubrawski (Carnegie Mellon University)
Kyle Miller (Carnegie Mellon University)
More from the Same Authors
-
2021 : Robust Interpretable Rule Learning to Identify Expertise Transfer Opportunities in Healthcare »
Willa Potosnak · Sebastian Caldas Rivera · Gilles Clermont · Kyle Miller · Artur Dubrawski -
2021 : Predicting Sufficiency for Hemorrhage Resuscitation Using Non-invasive Physiological Data without Reference to Personal Baselines »
Xinyu Li · Michael Pinsky · Artur Dubrawski -
2023 Poster: Feature Learning for Interpretable, Performant Decision Trees »
Jack Good · Torin Kovach · Kyle Miller · Artur Dubrawski -
2020 : ML4D Townhall »
Artur Dubrawski -
2020 Session: Orals & Spotlights Track 33: Health/AutoML/(Soft|Hard)ware »
Dustin Tran · Artur Dubrawski -
2020 Poster: Preference-based Reinforcement Learning with Finite-Time Guarantees »
Yichong Xu · Ruosong Wang · Lin Yang · Aarti Singh · Artur Dubrawski -
2020 Spotlight: Preference-based Reinforcement Learning with Finite-Time Guarantees »
Yichong Xu · Ruosong Wang · Lin Yang · Aarti Singh · Artur Dubrawski -
2019 : Poster Session »
Rishav Chourasia · Yichong Xu · Corinna Cortes · Chien-Yi Chang · Yoshihiro Nagano · So Yeon Min · Benedikt Boecking · Phi Vu Tran · Kamyar Ghasemipour · Qianggang Ding · Shouvik Mani · Vikram Voleti · Rasool Fakoor · Miao Xu · Kenneth Marino · Lisa Lee · Volker Tresp · Jean-Francois Kagy · Marvin Zhang · Barnabas Poczos · Dinesh Khandelwal · Adrien Bardes · Evan Shelhamer · Jiacheng Zhu · Ziming Li · Xiaoyan Li · Dmitrii Krasheninnikov · Ruohan Wang · Mayoore Jaiswal · Emad Barsoum · Suvansh Sanjeev · Theeraphol Wattanavekin · Qizhe Xie · Sifan Wu · Yuki Yoshida · David Kanaa · Sina Khoshfetrat Pakazad · Mehdi Maasoumy -
2019 Poster: Efficient Symmetric Norm Regression via Linear Sketching »
Zhao Song · Ruosong Wang · Lin Yang · Hongyang Zhang · Peilin Zhong -
2019 Poster: Optimal Analysis of Subset-Selection Based L_p Low-Rank Approximation »
Chen Dan · Hong Wang · Hongyang Zhang · Yuchen Zhou · Pradeep Ravikumar -
2019 Poster: Mutually Regressive Point Processes »
Ifigeneia Apostolopoulou · Scott Linderman · Kyle Miller · Artur Dubrawski -
2018 : Introductory remarks »
Artur Dubrawski -
2017 : Introductory remarks »
Artur Dubrawski -
2017 Poster: Sample and Computationally Efficient Learning Algorithms under S-Concave Distributions »
Maria-Florina Balcan · Hongyang Zhang -
2016 Poster: Noise-Tolerant Life-Long Matrix Completion via Adaptive Sampling »
Maria-Florina Balcan · Hongyang Zhang -
2015 Demonstration: An interactive system for the extraction of meaningful visualizations from high-dimensional data »
Madalina Fiterau · Artur Dubrawski · Donghan Wang -
2012 Poster: Projection Retrieval for Classification »
Madalina Fiterau · Artur Dubrawski -
2008 Poster: Learning the Semantic Correlation: An Alternative Way to Gain from Unlabeled Text »
Yi Zhang · Jeff Schneider · Artur Dubrawski