Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.05287 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911055107588096 |
|---|---|
| author | Deng, Samuel Hsu, Daniel Liu, Jingwen |
| author_facet | Deng, Samuel Hsu, Daniel Liu, Jingwen |
| contents | We study the problem of online multi-group learning, a learning model in which an online learner must simultaneously achieve small prediction regret on a large collection of (possibly overlapping) subsequences corresponding to a family of groups. Groups are subsets of the context space, and in fairness applications, they may correspond to subpopulations defined by expressive functions of demographic attributes. In contrast to previous work on this learning model, we consider scenarios in which the family of groups is too large to explicitly enumerate, and hence we seek algorithms that only access groups via an optimization oracle. In this paper, we design such oracle-efficient algorithms with sublinear regret under a variety of settings, including: (i) the i.i.d. setting, (ii) the adversarial setting with smoothed context distributions, and (iii) the adversarial transductive setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05287 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Group-wise oracle-efficient algorithms for online multi-group learning Deng, Samuel Hsu, Daniel Liu, Jingwen Machine Learning Computer Science and Game Theory We study the problem of online multi-group learning, a learning model in which an online learner must simultaneously achieve small prediction regret on a large collection of (possibly overlapping) subsequences corresponding to a family of groups. Groups are subsets of the context space, and in fairness applications, they may correspond to subpopulations defined by expressive functions of demographic attributes. In contrast to previous work on this learning model, we consider scenarios in which the family of groups is too large to explicitly enumerate, and hence we seek algorithms that only access groups via an optimization oracle. In this paper, we design such oracle-efficient algorithms with sublinear regret under a variety of settings, including: (i) the i.i.d. setting, (ii) the adversarial setting with smoothed context distributions, and (iii) the adversarial transductive setting. |
| title | Group-wise oracle-efficient algorithms for online multi-group learning |
| topic | Machine Learning Computer Science and Game Theory |
| url | https://arxiv.org/abs/2406.05287 |