Summary
This paper studies the online multi-group learning problem, and considers it in both smoothed context and general ($\gamma$-approximatable) settings. Unlike the traditional online learning setting, this paper considers achieve low regrets for all groups (subsequences). It utilizes the adversary moves first (AMF) framework for multi-objective online learning from [Lee+22] and the follow-the-perturbed-leader (FTPL) algorithm to handle the large number of groups. Through subtle algorithmic design and analysis, the paper achieved computationally-efficient and oracle-efficient learning.
Strengths
The paper studied the multi-group online learning problem, which is related to fair learning and subgroup robustness literature, both are significant. Under the smoothed setting, it achieves $\tilde{O}(\sqrt{dT/\sigma})$ regret; while under the general setting where $\gamma$-approximability is guaranteed, it achieves $\tilde{O}(\sqrt{NT_{g}\log\lvert H\rvert \lvert G\rvert})$ for each group $g$.
It first considers the i.i.d setting (both offline and online) then quickly moves forward to the smoothed online setting. Under the AMF framework, it considers two players: $(G,H)$-player (adversary that has access to an optimization oracle $\text{OPT}^{\alpha}_{(G,H)}$ that maximizes the learner's loss) and the $H$-player. Under such a game-theoretic perspective, the paper proposes algorithms that achieves bounded regret. It then adapts the algorithm to broader settings (non-smoothed settings), where the $\gamma$-approximability is assumed. For groups with different densities, the algorithm can achieve low regret for each group $g$. The algorithmic designs are subtle and the analysis is sound to the review.
Weaknesses
The main text in Section 2 and after are fine, while Section 1 needs improvement. Specifically, some descriptions are unclear.
For example, the bound $\tilde{O}(\sqrt{NT_{g}\log\lvert H\rvert \lvert G\rvert})$ is achieved for each group $g$, but this is not brought forward in summary of result (Line 76) and the last time $g$ is mentioned as one group is in Line 18.
Line 54-55, if $G$ is rich and expressive, then all subgroups well-approximated by a group $g$ in $G$ will be "covered" by whom? What does this sentence mean?