Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies weighted Empirical Risk Minimization (ERM), where the weight at data point $(x_i, y_i)$ is a (polynomial) function of the loss value $\ell(f(x_i), y_i)$. For affine functions, the authors show that it is equivalent to perform variance penalization (Theorem 1 and Lemma 2). Polynomials with higher degrees involve higher order moments of the losses (Theorem 3 and Lemma 4). The authors also propose an iterative algorithm to perform the weighted ERM (Algorithm 1). In Section 3, a different choice of weights is proposed, that ensure the convexity of the cross-entropy criterion despite a negative $\lambda_1$, and experiments are presented.
main_review: The problem studied is interesting, but the provided answer seems very limited to me, especially at the theoretical level. In particular,

**I am a bit puzzled by the negative $\lambda$**:
- it seems to me that it allows to do pretty much everything. For instance, the initial motivation is provided by eq. 1 (on another note, the link between eq. 1 and minimizing eq. 3 could be better explained, as it is not immediate to me). However, eq. 3 only makes sense if $\lambda$ is positive, but Section 3 is all about negative $\lambda$.
- the sentence "Case in which we consider them as unlearned samples and amplify their impact or as outliers and
suppress their impact on the model" is very revealing to me, as it shows you can do one thing and its opposite, but the most difficult question remains: is the data point an outlier or unlearned? How can you answer this?
- what is the motivation/intuition/incentive for minimizing eq. 4 instead of the standard sum of losses?
- it is a bit disappointing that so much effort is put in Section 2 to show convexity properties, that are totally omitted in Section 3. The weights used are actually completely different from the family studied in Section 2, breaking the coherence of the paper
- overall, my feeling is that we have a motivation for variance penalization (eq. 1), but the approach proposed is the complete opposite as a negative $\lambda$ is used. As for higher order moments, I struggle to see any similar justification...

**About practical aspects**:
- the weights depend on expectations that are unknown. Although it is specified that the results stated still hold with the empirical distribution, then one has to relate the minimized empirical quantity to the true risk, which seems nontrivial.
- as highlighted by the authors, considering higher order moments also multiply the number of hyperparameters. I wonder to what extent it is not always possible to find a combination of (positive or negative) $\lambda_i$ such that there is an improvement
- do authors have any convergence guarantee about Algorithm 1?
- about Algorithm 1: why not defining $\tilde{\ell}_i = w_i \cdot \ell_i$ and perform Gradient Descent on $\tilde{\ell}$?

**Two relevant papers/ideas**:
- "Robust multivariate mean estimation: the optimality of trimmed mean" by Lugosi & Mendelson (2021). One could imagine a weighted ERM procedure with 0/1 weights determined by the Trimmed Mean approach on the loss values. How would this approach compare to the one developed in this paper? Some thresholding ideas seem to be shared
- "Robust classification via MOM minimization" by Lecué et al. (2020). MoM-minimization can be seen a weighted ERM, with nontrivial 0/1 weights that depend on the median operator, see in particular Algorithm 1 therein. MoM-minimization has been recently shown to be robust to the corruption model presented at the beginning of Section 3 ("Generalization Bounds in the Presence of Outliers: a Median-of-Means Study" by Laforgue et al. 2021). How can it be related to the weighted approach proposed?

**Minor comments**:
- notation inconsistency: $n$ refers both to the number of samples (eq. 1, Algorithm 1, empirical expectation above Alg. 1), the highest order for the moments (Theorem 3), and the dimension of the input set (Lemma 4)
- "is bounded by the variance" --> "is bounded in terms of the variance"
- *with respect to* (2nd paragraph)
- $W$ is not defined in eq. 2
- the second sentence of Section 2 is not understandable
- $\lambda_{min}$ in Figure 1 is never defined
- I find the $W$ notation a bit confusing (in Theorem 1 for instance), as capital letters usually refer to matrices. Why not using $w = 1 + \lambda(\ell - \mathbb{E}[\ell])$, $w\ell$ (or $w \cdot \ell$) and $w(x)\ell(x)$?
- in Theorems 1/3, replace "taking the weighted mean of $\ell$ with weights $W$ is equivalent to" by "we have"
- Theorem 1 should be capitalized, i.e., not theorem 1 (Lemma 2, above Theorem 3)
- "changes with each iteration of the optimization algorithm" is not clear at all (at least at this point where Alg. 1 is not yet introduced)
- about the comments on the interval in Lemma 2, you could add that when $\mathbb{E}[\ell] = \min \ell$, you actually have $\ell$ constant, i.e., $\mathbb{V}(\ell) = 0$, and the admissible interval is $\mathbb{R}^+$, which makes sense since $\mathbb{V}(\ell) = 0$ and the "penalized" criterion is actually always equal to the original one, which is convex
- "the three central points aligned across a horizontal line" is not clear: the other cluster seems to have much more that 3 points, which ones are they? why are other points present?
- Figure 2: $\lambda_0$ is not defined, it starts at $\lambda_1$ in the given definition
- in Lemma 4, I would definitely use $w(x)\ell(x)$, to show that $W$ depends on $x$
- could be nice to highlight that Lemma 4 does not generalize Lemma 2, as you assume here $p$ to have positive values
- ~When~ clipping negative weights to 0 ~it~ prevents...
- Agorithm 1: $\mathfrak{L}$ is not defined, nor $k$ and $\gamma$
- Eq. 5 is pretty unclear: what is $k$ here? the loss is not taken w.r.t. to $i$, not $y_i$? Also there is always a $C$ satisfying the equation (the one equal to the left hand side), so what is the condition upon? Should $C$ be independent of some parameters?
- Lemma 5: Let $\ell, W$ **be**. Also $\ell$ must be positive
- Proof of Lemma 2: using $p(t)$ instead of $p(x)$ would be less confusing. Also, you provide a proof for a general $p$ while we have $p(t) = 1 + \lambda t$ at the beginning, this is also confusing. In particular the inequality $p(a) - p(b) \ge \lambda (a- b)$ holds with equality for instance. Next, we use Proposition **9**
- Proof of Lemma 4: it seems that you need $p$ to be (sub)differentiable
summary_of_the_review: Interesting problem but insufficient theoretical contribution. The provided insights are made confused by the fact that both positive and negative $\lambda$ are considered, with completely opposite effects. The technical derivations are basic computations.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The paper studies the role and implications of weighted empirical risk minimization, where one can also choose the weight of each sample instead of fixing it to be equal.
The paper then shows that specific choices of weights lead to variance penalization and higher-order moments penalization (Theorems 1 and 3). Lemma 2 and 4 study the regimes for which these chosen weights also preserve the convexity of the original loss functions.
This framework is then empirically validated through multiple experiments.
main_review: In the first section, the paper motivates the moments penalization by showing that variance penalization leads to tighter confidence intervals (Maurer and Pontil, 2009). In the context of learning, the goal then becomes to find a 
$\theta \in \Theta$ that minimizes the following (focusing on second moments for simplicity):
$$ E_n [\ell(X; \theta)] + \lambda V_n(\ell(X; \theta)), \qquad \qquad (1) $$
where $E_n$ and $V_n$ denote empirical mean and covariance respectively of $X \sim P_n$, the empirical distribution.
Hence the objective is to find a choice of weights $W(X;\theta)$, that may depend on $\theta$, so that the following holds:
$$ E_n[W(X;\theta) \ell(X; \theta)] =  E_n [\ell(X; \theta)] + \lambda V_n(\ell(X; \theta)) \qquad \qquad (2).$$

Theorem 1 shows that if one chooses $W(X;\theta) = 1 + \lambda (\ell(X;\theta) - E_n[\ell(X;\theta)] )$, then (2) above holds.

At this point, this result is not useful unless it is easy to minimize $E_n[W(X;\theta) \ell(X; \theta)]$:  as Theorem 1 shows equality with (1), one could have directly tried optimizing (1) above. This is where Lemma 2 comes in (preserving convexity). 

However, the paper just drops the dependence on $\theta$ everywhere in the paper: If $W$ were to depend on $\theta$, which it does, then I do not think Lemma 2 is true, i.e., $E_n[W(X;\theta) \ell(X; \theta)]$ might not be convex in $\theta$. As $W$ clearly depends on $\theta$, I do not even understand what Lemma $2$ means when $W$ does not depend on $\theta$ --- convex in which parameter? I would appreciate if authors can clarify if my arguments are incorrect.

After hiding this dependence on $\theta$, the theoretical results in the paper ---Theorem 1, Lemma 2, Theorem 3 --- become straight-forward.
Even in the experiments section, as noted on Page 4, Section 2, the operations for computing weights are not part of the computation graph, and it is not clear what Algorithm 1 is minimizing.

It is possible that Algorithm 1, by detaching weights from the computation graph, is approximately optimizing the desired objective of (1), but I don't see any immediate connection at this moment. Investigating this connection might be a possible research direction for future but it is beyond the scope of the submitted paper. 

Though paper claims that it builds and extends the works of Duchi and Namkoong (2019) and Li et al. (2021), this limitation of the present paper is not present there.

I would be happy to increase my scores if my understanding of the results in the paper is flawed, and authors can clarify their contributions.  


## Minor Comments

1. Since the goal is to penalize by empirical variance, first section should cite the results from (Maurer and Pontil, 2009) who showed that penalizing from empirical variance also works (instead of true variance as is cited in Equation (1) from Hoeffding's inequality). 
3. Proposition 7 is a basic fact in probability and certainly not attributed to Duchi and Namkoong (2019).


summary_of_the_review: In my current understanding, the paper seems to study a simplistic setting (and hence the theoretical results of the paper are immediate) and it is not clear to me how the results/framework extends to the general setting. Hence, I do not think the paper is fit for ICLR in its current form. I will be happy to increase my score if my understanding is incorrect.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In the paper, the authors proposed minimizing a simple weighted mean, which leads to an optimization problem of the high-order moments of the loss distribution. Experiment results show the weighted mean trick has similar performance as other robust loss functions.
main_review: Here are my comments on the paper:

(1) Theorem 1 assumes that the first moment of $\ell$ exists. What if $\ell$ has heavy-tailed distribution and its mean may not even exist?  

(2) The statement of Lemma 2 is quite weird. I think $\ell$ is a random variable. What do the authors mean by "convex objective $\ell$"? What does $\min(\ell)$ mean? Does that notation stand for the minimum coordinate of $\ell$?

(3) " When using the weighted mean trick to penalize the variance and clip the negative weights to 0 then the objective remains convex for any positive": Why is it true?

(4) When using the weighted mean trick, what is the concentration behavior of the samples from $W \ell$ around their expectation $E(W \ell)$? I also have a similar question for moments expansion in Theorem 3.

(5) When the weights are clipped to zero due to their negative values, will the expansions in Theorems 1 and 3 still hold?

(6) "However, for moderately small penalization factors the objective remains convex on almost the entirety of the domain and does not hinder the convergence": I am not so sure about how to quantify "moderately small". The authors need to explain this point further.

(7) "In what follows, we show that using a negative variance penalization factor,  $\lambda_{2} < 0$, bounds the loss function": I wonder the relation of $\lambda_{2}$ and $\eta$, which is class label misspecification probability. Intuitively, $\lambda_{2}$ should depend on $\eta$.

(8) I do not understand the writing in Page 7. Several parts are written without proper explanation. The authors may consider rewriting the writing in Page 7 to improve the readability of the paper.
summary_of_the_review: In my opinion, the contribution of the paper is quite marginal and the paper is quite hard to understand, which causes by the poor writing and lacks of proper explanation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors demonstrate that minimizing the weighted mean results in higher oder moments of the loss distribution. 

They do this by explicitly demonstrating specific choices for the weights such that the expected weighted loss actually corresponds to minimizing the original loss regularized by a linear combination of the higher moments. They also note the ranges of the regularization parameter that preserve convexity. 

The authors state their work in the context of two recent papers [1], [2] which attempt. to control the bias-variance tradeoff in different ways, effectively controlling either just the variance, or all the higher moments. In contrast, this technique allows them to control any specific combination of higher moments. 

[1] "Variance-based regularization with convex objectives" Duchi, Namkoong'19

[2] "Tilted Empirical Risk Minimization" Li, Beirami, Sanjabi, Smith'20
main_review: Strengths: 
I think this is an interesting observation and could potentially have consequences in several robust learning algorithms. 

Weaknesses:
I would have liked to see some applications to existing results that optimize the weights to solve estimation problems in outlier-robust settings -- for instance [1]. But there are several other works that also do such things. 

[1] "Robust Sparse Estimation Tasks in High Dimensions" Li'17 
summary_of_the_review: I think this is an interesting paper and vote to accept it. I think the observation carries value and might have several applications down the line. 

The only detracting aspect is that the theorems are relatively straightforward, and so I would have liked to see more consequences of this observation in the context of other algorithms that exist in the literature.
review_title: null

Meta-review: The paper investigates weighted empirical risk minimization where the weights on an example in the training set is given by a polynomial function evaluated on the loss on the given example. Authors show that the choice of the weighting function induces a data-dependent variance penalization in the training objective. Authors present an algorithm for weighted ERM and empirical results to support their claims. While the problem setting is broadly relevant and the approach the authors take in this paper is interesting, several questions remain unanswered. First, the authors argue that variance penalization helps but do not compare with other regularized ERM approaches. Second, it is not clear if the proposed algorithm is indeed gradient descent on the weighted ERM objective as pointed out by one of the reviewers. Finally, the writing can be improved with more emphasis on the novelty and significance of the contributions. I believe the initial comments from the reviewers has already helped improve the quality of the paper. I encourage the authors to further incorporate the feedback and work towards a stronger submission.
Decision: Reject