Yang, L;
Chen, YZJ;
Hajiesmaili, MH;
Herbster, M;
Towsley, D;
(2022)
Hierarchical Learning Algorithms for Multi-scale Expert Problems.
Proceedings of the ACM on Measurement and Analysis of Computing Systems
, 6
(2)
pp. 1-29.
10.1145/3530900.
Preview |
Text
HetHedge_Sigmetrics2022__Camera_ready_.pdf - Accepted Version Download (2MB) | Preview |
Abstract
In this paper, we study the multi-scale expert problem, where the rewards of different experts vary in different reward ranges. The performance of existing algorithms for the multi-scale expert problem degrades linearly proportional to the maximum reward range of any expert or the best expert and does not capture the non-uniform heterogeneity in the reward ranges among experts. In this work, we propose learning algorithms that construct a hierarchical tree structure based on the heterogeneity of the reward range of experts and then determine differentiated learning rates based on the reward upper bounds and cumulative empirical feedback over time. We then characterize the regret of the proposed algorithms as a function of non-uniform reward ranges and show that their regrets outperform prior algorithms when the rewards of experts exhibit non-uniform heterogeneity in different ranges. Last, our numerical experiments verify our algorithms' efficiency compared to previous algorithms.
| Type: | Article |
|---|---|
| Title: | Hierarchical Learning Algorithms for Multi-scale Expert Problems |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1145/3530900 |
| Publisher version: | https://doi.org/10.1145/3530900 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10165538 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
