Summary
The paper studies efficient and practical algorithms for group-wise regret-minimization online learning. The problem is a variate of the classical online problem, in which a hypothesis class $H$ is fixed, and a sequence of individuals/features ${x_{1}, \cdots, x_{T}}$ and their labels ${y_1, \cdots, y_T}$ are chosen by an adversary. The algorithm has to make predictions at each time step $t \in [T]$. The classical notion of measuring a ''good’’ algorithm is *regret*, which is defined as the cumulative gap between the cost induced by the online learning algorithm and the cost induced by the best fixed model in the hypothesis class. The group-wise regret minimization problem further requires binding the regret for each group, which, mathematically, can be viewed as a collection of subsequences indexed by the ``mapping’’ of different groups.
The work of BL [ITCS’20] has shown that it is possible to achieve small regret w.r.t. the best model $f_{g}$ for every fixed group $g$ by reducing the problem to the sleeping expert problem. This implies for a large family of online learning problems, there exist algorithms with group-wise $1+o(1)$-multiplicative regret that run in time polynomial of $|G|$ and $|H|$. However, while the size of $G$ is usually small, even some ``elementary’’ models, e.g., linear models, have quite large sizes of $H$, which prevents the algorithm of BL [ITCS’20] from being practical.
The main contribution of the paper is to improve the runtime of the group-wise regret minimization algorithm of BL [ITCS’20], and, in particular, remove the dependence on $|H|$ for the run time. To this end, the paper observes that we can actually solve each policy sub-sequence by external regret algorithms, which require far less time to compute, and treat each ``expert’’ in the overall algorithm as the output of the external regret algorithms. In doing so, the algorithm avoids enumerating over the hypothesis class $|H|$, and only scales w.r.t. $|G|$. The paper then provides some implementations on both synthetic and real-world datasets, and the experimental results of their algorithms are strong.
Strengths
Overall, I like this paper as it provides the practical algorithm for a problem where the existence of the solution (or even, a theoretically-efficient algorithm) has been known, but no practically-efficient algorithm was proposed. This serves as a nice ``bridge’’ between theory and practice. As the paper itself has mentioned, practical group-wise regret-minimization algorithms have various downstream applications, including algorithmic fairness.
I also read through the analysis in Appendix B, and I think they are correct, barring some presentation issues (mentioned in the ``weakness’’ section). Although the technical idea is simple and somehow straightforward to come up with, I do think the result itself is neat and cute. Finally, the experimental results of the paper are quite strong, although the comparison is somehow tailored to your algorithm since the benchmark as they are not designed for group-wise regret minimization.
Weaknesses
One criticism I have when reading the paper is that the paper is not presented in a fully self-contained and rigorous manner. For instance, the proposed algorithm uses AdaNormalHedge as a black box, but the guarantee of such an algorithm is never formally described. (I am aware of the description in Appendix B, but there is no proposition + proper citation for this.) Similarly, when citing external regret minimization algorithms for applications, the formal quantifiers and guarantees for those algorithms are not provided.
Similarly, the introduction is written in a very informal way. I understand this might be a result for the authors to accommodate the broader readership of the conference; however, I think it actually adds to confusion. For instance, when defining the notion of diminishing group-wise regret, it would be much more helpful to include the actual mathematical definition of ''squared error’’ and ''best model in H on that sequence’’. (Also, why the notion is limited to squared error but not general loss functions?)
The same applies to the statement of Theorem 1, in which the notion of ``computationally efficient’’ is not defined(!) The phrase ''best model on hindsight’’ is used in a very informal way – I think you should properly define this notion (overall vs. on group-wise sequences) with the proper quantifiers.
A note for presentation problems in Appendix B: the usage of expectation notation $\mathbb{E}[]$ is rather confusing in this section. Your derivation crucially relies on the control of which coins the expectation is taken upon. I think in this case, the expectation notation should have subscript explicitly stating the source of randomness. Furthermore, the way you talk about $p_{t}^{I} $ vs $z_{t}^{I}$ is not rigorous enough. If I understand it correctly, $p_{t}^{I}$ is a random variable whose supports are some realizations denoted as $z_{t}^{I}$. In light of this, should the term in the first inequality be $\mathbb{E}[\sum_{t} I(t) \ell(p_{t}^{I}, y_{t})]$? Overall, I do think this section has quite some room for improvement.
Questions
Is your notion of computationally efficient in Theorem 1 defined as polynomial time in $T$, $d$, and $n$ (or some other input-related size)? If I understand correctly, what you want to say is that it is reasonable to assume $|G|$ is of polynomial sizes of the input, but $|H|$ is usually quite large. Therefore, your algorithm that does not scale with $|H|$ implies poly-time efficiency.
I don’t quite understand the term ``diminishing/vanishing regret’’ – in your Theorem 2, the term $\sqrt{T_{T} \log(|G|)}$ is not $o(1)$ itself. Are you implicitly enforcing a lower bound on the $\alpha_{I}$?
A MISC comments: The discussion on the technical front by comparing your work with BL [ITCS’20] looks nice. I think you can expand this discussion to give more details, and present it earlier in the paper.
Rating
8: accept, good paper
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Ethics concerns
I do not have any ethics concerns for this work.