Selective Labeling in Learning with Expert Advice

Anh Truong, S. Rasoul Etesami, Negar Kiyavash

Research output: Chapter in Book/Report/Conference proceedingConference contribution


An online active learning mechanism using the expert advice framework is considered where the goal is to learn the correct labels of a sequence of revealed items. The learning scheme's efficiency is measured in terms of the regret bound and reduced data labeling queries based on experts' predictions. Two efficient randomized algorithms EPSL and EPAL are proposed in which the opinion ranges of experts are examined in order to decide whether to acquire a label from users for a given instance. It is shown that both algorithms obtain nearly optimal regret bounds and up to a constant factor depending on the characteristics of experts' predictions. While EPSL yields a better regret bound than EPAL, it requires extra prior knowledge of experts' predictions. Relaxing this assumption, EPAL provides a more practical scheme by implying an adaptive time-varying learning rate whose regret is at worst \sqrt{2} times of that for EPSL. Experimental results justify the outperformance of the proposed algorithms compared to the existing ones in this setting.

Original languageEnglish (US)
Title of host publication2021 American Control Conference, ACC 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781665441971
StatePublished - May 25 2021
Event2021 American Control Conference, ACC 2021 - Virtual, New Orleans, United States
Duration: May 25 2021May 28 2021

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619


Conference2021 American Control Conference, ACC 2021
Country/TerritoryUnited States
CityVirtual, New Orleans

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Selective Labeling in Learning with Expert Advice'. Together they form a unique fingerprint.

Cite this