Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies balancing average case and worst case performance in a multi-task setting. The authors propose a new algorithm that extends the group DRO algorithm by 1. ) taking task interactions into account 2.) enforcing the maximum entropy principle when breaking ties. The interactions between tasks are modeled by a first order approximation to change in training loss after a single gradient update. Empirically, the authors propose methods to stabilize their estimation of the "task interaction" estimation by a online weight update procedure and also introduce an additional technique that re-normalize gradients to unit norm before calculating the "task interaction" estimation. In addition, the authors observed that the proposed algorithm only needs to update the task interaction estimation periodically during training, which reduces the computational overhead. 

The submission empirically test the proposed algorithm on CIFAR100 and Multilingual Language Modeling. On CIFAR100, the proposed method achieves improved performance for smaller-scale neural networks but does not achieve significant improvement on larger neural networks. On Multilingual Language Modeling, the proposed method achieves best average performance and second best worst case performance (trailing a computationally expensive baseline).
main_review: Overall, I think the submission is novel and addresses an important question in multi-task learning. I believe the algorithm has a clear theoretical motivation but also want to note that the author makes a key simplification (i.e. the first order approximation) in estimating the task interaction, which most likely does not hold for non-convex neural network optimization. My main concerns are with the empirical evaluation of the proposed method, which are detailed below. Currently, my stand for the submission is "marginally below the acceptance threshold" but I can see the potential of the proposed method and could be convinced otherwise if the authors can help answer my questions/requests.

I have the following list of questions:

1. In practice, the loss values from different tasks can be very different. For example, if we learn a neural network to perform image recognition and segmentation simultaneously, the loss values will be of different scales from these two tasks. What would the authors recommend for such use case?
2. The authors propose to renormalize the gradients into one when estimating the "interaction matrix" but provides little intuition and empirical validation so I am not convinced that this is a principled technique. Normalizing the gradients breaks the analysis section 2.5 which creates a gap between the conceptual motivation and the actual algorithm, which is quite disappointing. Can the authors justify this decision? Also, I would like to see ablation study on this design decision. 
3. The authors propose to reduce the computational cost by estimating the interaction matrix periodically. Can I see an ablation study on this hyper-parameter to understand the trade-off here? How much performance do we lose when we set the estimation period to be 1000 steps?
4. The CIFAR100 experiment in the appendix (Figure 5) is quite concerning. I appreciate the honest documentation of this experiment. I wonder if this is because weighting approach in general does not work with overparametrized networks [1]? Can the authors provide more insights on this experiment?
5. Can the authors document the actual wall clock time and memory overhead of the proposed method on their CIFAR and Multilingual LM experiments? 
6. For Table 1, the difference between absolute perplexity and relative perplexity is quite confusing. We observe that DRO achieves the best worst case absolute perplexity but not so much for relative perplexity. I am not entirely sure the "relative perplexity" is the correct metric: perplexity is defined as the inverse of the average probability of predicting the right word so computing the difference and the division does not have a clear definition. I understand the difficult in comparing perplexities across languages. Can the authors provide a table of the full list of perplexity values on different languages in the Appendix so I can better judge the results?
Aside from my current confusion mentioned above, the empirical gain of L-DRO over uniform sampling (static mixing with alpha=0) is quite marginal, which is concerning.
summary_of_the_review: Novel and interesting algorithm that studies a important problem in multi-task learning. Current empirical evaluation of the paper can be furthered improved. Several design decisions in the final version of the algorithm should be better justified.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors study the problem of multi-task learning in the presence of heterogenous tasks when there is an imbalance in the distribution of tasks. In such settings, we can learn models for multi-task learning using two approaches -- a) learn to minimize average loss across tasks, b) learn to minimize the worst case loss. Turns out both the approaches are not ideal. Minimizing average loss can compromise one task a lot and minimizing worst case loss can focus only on one very difficult task at the expense of improvements possible in other tasks. The authors propose a look ahead distributionally optimization based approach to balance the two -- worst case performance and the average performance. In the proposed approach, instead of solving a standard min-max optimization, the authors propose to constrain the min learner to find the optimal weight combination for weighted risk minimization, which leads to the minimum worst case risk.
The authors carry out synthetic and real datasets to demonstrate the efficacy of the approach.
main_review: **Strengths:** The problem is very important. The authors bring the attention of the community of an important shortcoming of both average loss and worst case loss in the settings when there is imbalance in task distribution. The paper for most part is well written. 

**Weaknesses:** I have several concerns that I highlight below: 
1. **Look ahead DRO and role of deterministic algorithm** The exact approach of look ahead DRO is presented in Section 2.4. The approach has several problems that are not clear. If we assume that the deterministic algorithm finds $\theta_{w,\theta_0}$ achieves the global minimum for the weight $w$, then I cannot see how this approach is any different from doing regular min-max optimization. The reason I say is that if you do weighted sum risk minimization, then the loss values for different tasks achieved at the optima for different values of weights cover the entire Pareto boundary of the graph of loss of tasks. The problem amounts to selecting the point on the Pareto boundary that achieves the best worst case risk. 
The authors should show using at least simple 2D illustrations, what point on the Pareto plane DRO achieves, and what point exact look ahead DRO intends to achieve, and contrast with standard sum risk minimization. 
I suspect the exact lookahead DRO is implicitly assumed that it will not find the exact minimum. If that is the case, then there should be a very detailed discussion on it. 

2. **Two baseline approaches** The title of the paper is about balancing worst case accuracy and average accuracy. The title itself suggests that the authors should compare with a simple combination of minimization of worst case together with average risk. This can be stated as 
$$min_{\theta}\Big( max_{k}l^{k}(\theta) + \lambda \sum_{k} l^{k}(\theta)\Big)$$
This gradients of the above can done with the approach of either Oren et al. and also perhaps Sagawa et al.
The above objective exactly tries to optimize what the authors require. It is not clear why there are no comparisons with the above approach since it is the most natural baseline to study. 

The objective in equation (8) in http://proceedings.mlr.press/v139/krueger21a/krueger21a.pdf can also solve the problem that the authors propose. The objective minimizes the average loss across tasks and regularizes it using the variance of the loss across tasks. Hence, if for each task if you compute the loss as the average loss over the data by dividing it by the size of the data for that task, this would be a useful approach to compare against. 

3. **Regarding experiments** In the main real experiment, the baseline-DRO performs the best. The authors claim that its much more computationally expensive. I have two main points to make here
a) Baseline DRO is still a DRO based approach. Why is it able to achieve a much better tradeoff? The entire paper up until this section says that you will achieve a better tradeoff irrespective of the compute budget. This seems to be going against the main idea presented. Even your synthetic experiment at least agrees with your main hypothesis. 

b) You claim that the computational expense is much higher. If that is the case and that is the main source of gain, why not report the wall clock computation times to make the point clear? There is one more reason I ask this is because in Oren et al. (Section 4.2) the authors state " In practice, we use a bigram model, which was fast enough to scale and worked sufficiently well in experiment". What you say seems to contradict their claim. 






 
summary_of_the_review: Overall, the paper addresses an important problem. It proposes an interesting approach to solve it as well. The synthetic experiment is promising. However, there are quite a few weaknesses -- the target that exact lookahead DRO approach seems to be no different than regular DRO (as I explained above), missing natural baselines (without such baselines its hard to even understand if such a lookahead is needed or not),  problems with real data experiments. If the authors can effectively address these concerns, I would be willing to change my score.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper propose one-step look ahead DRO for multitask learning considering the worst task’s performance as the objective. Due to the task’s interaction with each other, directly using gradient-based approach is suboptimal. To overcome, look-ahead DRO estimates the task interaction using Taylor expansion and returns the locally optimal weighting by solving a linear min-max subproblem. Several tricks for mini-batch and online updating version of DRO are proposed.
main_review: Overall, the idea of this paper is well presented and intuition is well explained. Below please find my detailed comments.

Major:
1. Seems for most cases when the worst task’s loss is larger than other losses with a certain margin. This algorithm only performance gradient descent on this worst task. 

The advantage of this algorithm only appears when the top-n worst tasks are very close to each other. In this case, considering task interactions might help. But I was wondering whether such a scenario happens often in practice? 
 
2. Seems there is a significantly simpler algorithm functioning similar to the proposed one:
At each iteration, we find the worst task, performance gradient on this worst task. If the gradient is not zero, we apply the gradient. Else, we apply the uniformly weighted gradient of all the other tasks.

There might be a slight difference between this very simple algorithm and the proposed one. I was wondering how do they compare.

3. No convergence guarantee is shown here. I.e., does this algorithm converges to the Pareto stationary set? What’s the convergence rate interns of worst-case loss?

Minor:
1. There are various criteria to decide the final objective for multi-task learning. There is not much explanation why minimizing the worst loss is a good choice.

summary_of_the_review: I think the general idea of this paper is interesting. However, there are still several important points that need to be clarified. I am happy to have more discussion and adjust my score accordingly if things are properly addrssed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This submission proposes Lookahead-DRO, of which the core idea is to do DRO on the updated weights, i.e., to choose a weight that minimizes the DRO loss in the next step. The computation is not tractable so the authors propose to use first order Taylor expansion approximation. Experiments on synthetic datasets and two real-world datasets demonstrate its effectiveness.
main_review: Strengths:

1. The idea sounds legit, interesting and novel.

2. The writing is clear and easy to follow.

Weaknesses:

1. The empirical improvement does not seem to be very significant, especially on large models.

2. Another concern is with all the approximations, it is no longer clear whether the merit of the proposed method is still held, i.e., can the proposed L-DRO guarantee that $L_{DRO}(\theta_1) < L_{DRO}(\theta_0)$, empirically?

Questions:

1. Does Figure 5 imply the advantage of the proposed L-DRO is mitigated by model with larger capacity?

2. How large is the variance of the experiments? Is 3 runs enough?

3. Can the authors visualize the weights in algorithm 2? Will the trick make the weight $w$ almost consistent across the training?

---- Post Rebuttal

I thank the authors for the response. I would like to keep my original rating as weakly accept, with the reason that 1) I think the novel viewpoint could potentially benefit the community and 2) the diminishing performance of the proposed method when the model gets larger makes the approach less interesting. 
summary_of_the_review: Interesting idea, good writing, moderate empirical results
review_title: null

Meta-review: In general, the reviewers recognized the importance of the question and the innovation in the proposed algorithm, but do not seem to be super excited about the overall contribution of the paper. (One or two reviewers did not seem to respond authors' response after the AC's reminder.) The AC read the reviews and responses and observed that the main concern appears to be the empirical performance --- the improvements are not as strong for larger models or if more computational time is allowed. Modern models are indeed typically large, and it would be good to discuss this point more thoroughly. If the work's focus is limited resource setting, the paper might want to state that upfront. Indeed, one reviewer is still concerned post-rebuttal about a clock-time comparison. Given these considerations, the AC will recommend reject for the paper but encourage the authors to resubmit to a top venue conference after revising the paper.
Decision: Reject