Year: 2021

Abstract:
We prove that minimizing a weighted mean results in optimizing the higher-order moments of the loss distribution such as the variance, skewness, and kurtosis. By optimizing the higher-order moments, one can tighten the upper bound of the loss mean deviating from the true expectation and improve the robustness against outliers. Such types of optimization problems often lead to non-convex objectives, therefore, we explore the extent to which the proposed weighted mean trick preserves convexity, albeit at times at a decrease in efficiency. Experimental results show that the weighted mean trick exhibits similar performance with other specialized robust loss functions when training on noisy datasets while providing a stronger theoretical background. The proposed weighted mean trick is a simple yet powerful optimization framework that is easy to integrate into existing works.

heading: 1 INTRODUCTION
text: The most common objective in machine learning is to minimize the average loss. However, by doing this it implies that all samples are equal. The goal of this work is to convince the reader that from the perspective of the model, not all samples are equal and optimizing a weighted mean is a more progressive approach. For instance, at the end of the training, few samples are left uncaptured by the model which yield large loss values. One might choose to put more weight on those samples to help the model learn (individual fairness), or consider them noise and assign them less weight (robustness). The decision will also be reflected by the loss variance; it will decrease when hard samples are weighted more and increase otherwise.
Before introducing more formally the weighted mean, we first justify theoretically the impact of variance penalization. Using the empirical Bernstein bound (Maurer & Pontil, 2009) for i.i.d. loss values Z and bounded variance we have with probability 1− δ:
E[Z]− 1 n n∑ i=1 Zi ≤ C1
√ 2Vn[Z] ln 2/δ
n + C2
7 ln 2/δ
3(n− 1) (1)
where C1, C2 are problem depended constants. This inequality reveals two things. First, we have with high probability that the empirical mean is close to the theoretical value. This bound along with similar PAC-Bayes bounds (Seldin et al., 2012; Tolstikhin & Seldin, 2013) justifies the practical success of the empirical risk minimization (ERM) which has the objective to minimize the mean loss value (Namkoong & Duchi, 2017). Secondly, the difference between the two is bounded in terms of the empirical variance. This second implication led to a large and growing body of studies that investigate variance penalization (Maurer & Pontil, 2009; Namkoong & Duchi, 2017; Duchi & Namkoong, 2019; Staib et al., 2019; Lam, 2019; Heinze-Deml & Meinshausen, 2021; Hu et al., 2018). Moreover, by penalizing the variance, the intrinsic bias-variance tradeoff of the ERM can be controlled. Two studies influential for this paper are that of Duchi & Namkoong (2019) and Li et al. (2021). Duchi & Namkoong (2019) proposed taking the expectation with respect to a different distribution which allowed penalizing variance while preserving the convexity of the objective. Similarly, Li et al. (2021) investigated optimizing a tilted empirical risk which is equivalent to penalizing all the higher-order moments simultaneously. In summary, previous methods either penalize only one moment or all the higher-order moments but are not flexible enough to penalize any desired combination of the higher-order moments.
Inspired by the above works, we propose to optimize a weighted mean and prove that for certain weights, it is equivalent to optimizing any higher-order moments of the loss distribution such as variance, skewness, and kurtosis. Our approach generalizes that of Duchi & Namkoong (2019); Li et al. (2021) while simplifying the optimization procedure and enabling separate penalization of the higher-order moments.
In particular, we will construct the weights w such that optimizing the weighted mean of the loss ` is equivalent to applying a variance penalization:
E[w`] = E[`] + λV[`] (2)
or penalization of other central moments (e.g., skewness, kurtosis). Construction of these weights are treated by Theorems 1 and 3 from section 3, which require minimal computational resources. Important note, penalizing directly the variance preserves convexity only for values of λ within a very narrow range (Maurer & Pontil, 2009). However, the weighted mean method yields a convex objective for any positive values of λ.
In detail, our contributions are as follows:
(C1) We build upon the work of Duchi & Namkoong (2019) and prove that optimizing a weighted mean is equivalent to reducing or amplifying both variance (Theorem 1) and higher-order moments (Theorem 3).
(C2) We derive the limits of the penalization interval which preserves convexity (Lemma 2) and also show how to penalize with values outside this interval while still maintaining convexity (Lemma 4).
(C3) We connect the variance and higher-order moments penalization using weighted mean to the robustification of loss functions (Lemma 5 and Lemma 6).
(C4) We develop a convex version of the variance penalized cross-entropy loss which provides a higher accuracy in high noise scenarios with class dependent noise.
(C5) We show experimentally that a negative variance penalization improves model accuracy when training with noisy labels.
The implications of the weighted mean are much broader than what we investigate in this work. We limit the scope of this paper to classification using deep neural networks trained with noisy labels. But the mathematical framework also covers the control of the bias-variance trade-off and can also be applicable to regression problems.
In the sequel, we start by introducing the notation in section 2, then in section 3 we present the moment penalization strategy and the weighted mean trick which is a computational technique to make moment penalization practical. Next, in section 4, we illustrate the application of moment penalization using the weighted mean formulation to optimize for robustness when training with noisy labels.

heading: 2 NOTATIONS
text: In subsequent sections we will use the following notation. A training data set is defined as D = {(xi, yi)}ni=1 where xi ∈ X are the features and yi ∈ Y = {1, . . . , k} represent the class labels. A classifier f(x; θ) is a mapping f : X ×Θ→ V from the feature space to the probability simplex V parameterized by θ. A loss function ` : V × Y → [0,∞) gives a penalty `(v, y) when the model predicted the value v and label y was observed. A weight function w : V × Y → R assigns to each sample a weight. As we are interested in optimizing the model output value v that minimizes the penalty, we will focus our investigation on loss functions `(v, y) that are convex in v and seek to preserve the convexity when optimizing the weighted mean. In ERM, we are interested with finding the model parameters θ that minimize the empirical risk calculated as ED[`(f(xi; θ), yi)] and the weighted form ED[w(`(f(xi; θ), yi))`(f(xi; θ), yi)]. To simplify the notation, we will drop the dataset D from the expectation subscript and the arguments of the loss and the weight function, i.e., E[`] ⇔ ED[`(f(xi; θ), yi)] and E[w`] ⇔ ED[w(`(f(xi; θ), yi))`(f(xi; θ), yi)]. Similarly, the notation for minimum is simplified as min `⇔ minxi,yi∈D `(f(xi; θ), yi).
−3 0 3 −3
0
3
0.0
0.0
0.2
0.2
1.0
1.0
2.02.0 3.9
3.9
−3 0 3
0.0
0.0
0.5 0.5
1.0
1.0
1.3
1.3
−3 0 3
λ < 0
λ = 0 λ > 0
λ > 0 λ < 0
1Figure 1: Variance penalization for classification problems. Contour lines of the weights distribution for positive λ are shown on the left and for negative on the center plot. The right plot shows the use of variance penalization for outlier suppression or amplification (robustification versus generalization).

heading: 3 PENALIZING MOMENTS
text: In ERM, the impact on the model parameters of a sample is determined by the balance between its loss value and the average of the training batch. Especially observed in the latter stages of the training when majority of samples have a small loss value except few which are left uncaptured by the model. Case in which we consider them as unlearned samples and amplify their impact or as outliers and suppress their impact on the model. The weighted mean trick consist in assigning weights to each sample based on the loss value to either amplify or suppress their impact on training. This is similar to dropout (Hinton et al., 2012) but for losses. However, weighted mean trick is a deterministic process and the weights are not restricted to 0 or 1 but can take any non-negative value.
In what follows, we apply the weighted mean trick to extend the ERM framework to multi-objective optimization of the mean and higher-order moments of the loss function. First, we show that for some distinct weights, optimizing the weighted mean is equivalent to a simultaneous optimization of the mean and variance. Theorem 1 (Variance Expansion). Let ` be a loss function with finite E[`] and finite V[`] and let w(v, y) = 1 + λ(`(v, y)− E[`(v, y)]), then we have:
E[w`] = E[`] + λV[`] (3)
Proof. Replacing w with the definition and using the linearity property of the expectation along with Proposition 7 we get: E[w`] = E[`]+λE [ (`−E[`])` ] = E[`]+λE [ (`−E[`])2 ] = E[`]+λV[`]
Thus, switching from mean to weighted mean allows us to control the bias-variance tradeoff through λ to improve the distributional robustness of the model (Maurer & Pontil, 2009). However, the range of λ values that preserve the convexity of the objective depends on the average and the minimum penalty returned by the loss function ` as shown by the next lemma. Lemma 2. As introduced in Theorem 1, the variance expansion of a convex loss function `(v, y) in v yields a new objective that is also convex in v if λ ∈ [0, λmax], where λmax = 1/(E[`]−min `).
Proof is provided in Appendix A. This lemma precisely shows why directly penalizing the variance does not preserve convexity besides when λ takes values in a narrow interval. Moreover, directly penalizing the variance as part of a numeric optimization objective, the upper limit of the interval, λmax, is not constant and changes with each iteration of the optimization algorithm. Note that the further the minimum value min ` is from the average loss value E[`], the narrower the interval is. Conversely, when E[`] = min ` results that ` is constant and V[`] = 0 thus the objective is convex for λ > 0. However, using the weighted mean trick the objective remains convex for any positive λ irrespective if V[`] = 0.
Figure 1 shows the weights distribution for different values of λ. When λ is positive (left plot) samples closer to the decision boundary (which also means with larger loss values) receive more weight. On the other hand, when λ is negative (center plot) samples with larger loss values receive
less weight. Of note, for λ < 0 the objective is not convex, however as we will show later will still converge to an optimal solution. The right plot shows a binary classification problem where each class consists of two clusters, squares and circles. The parameter λ controls the placement of the decision boundary with respect to these two clusters. Positive λ values place more weight on the cluster of squares which is closer to the decision boundary and as a result the boundary is horizontally aligned. On the other hand, negative λ values place more weight on samples farther from the boundary and in this case the cluster of circles. Therefore, this aligns the decision boundary with respect to the cluster of circles oriented diagonally.
Variance is not the only central moment that can be penalized using the weighted mean. In fact, any combination of the moments can be penalized. The next result generalizes Theorem 1.
Theorem 3 (Moments Expansion). Let ` be a loss function with finite first m central moments and define w(v, y) = ∑m i=1 λi(`(v, y)− E[`(v, y)])i−1, then we have:
E[w`] = λ1E[`] + m∑ i=2 λ̃iE [ (`− E[`])i ] (4)
where λ̃i = λi + λi+1E[`] for i < m and λ̃m = λm
Proof is provided in Appendix A. We notice that penalizing moments higher than two incurs an additional penalization of the previous moment. For example, penalizing skewness by λ3 incurs a variance penalization of λ3E[`].
Theorem 3 also has an algebraic interpretation. Note that the formula for weights is nothing more than a polynomial in `(v, y) translated by E[`]. When penalizing the variance, λ2 controls the slope of the linear equation, and when penalizing the skewness, λ3 controls the curvature of the quadratic equation. Moreover, the penalization factors λi also define the placement of the roots of the polynomial and the convexity of the weighted mean objective.
Lemma 4 (Convexity of Moments Expansion). Let `(v, y) be a loss function convex in v and p : R→ [0,∞) be a non negative and differentiable convex function and M ≥ 0, then the weighted objective w(v, y)`(v, y) with w(v, y) = p(`(v, y)−M) is convex in v if p is non decreasing.
Proof is provided in Appendix A. The above result lists two requirements on the polynomial function p such that the weighted mean objective remains convex. First, the function must be non-negative, thus, the negative weights must be clipped to 0. Secondly, when the function takes positive values, p must be non decreasing and convex. Of note, this result is similar in scope to Lemma 2 but does not generalize it as the weights are non negative. Figure 2 shows several examples of polynomials. Variance penalization implies p is an affine function, and thus, convex. However, for λ1 > 0 the polynomial is non decreasing (left plot) and for λ1 < 0 the polynomial is non increasing (center plot). Thus, only positive variance penalization will result in a convex objective. Of note, Lemma 2 upper bounds λ1 if weights are not clipped to 0, however, if clipping is used λ1 is not upper bounded. When penalizing skewness, p is a quadratic function (right plot). In this case, if λ2 > 0 then p is convex and non decreasing only on a restricted interval instead of the entire real line. Thus, convexity can be preserved by appropriately adjusting the roots of the polynomial such that p is convex on [min `− E[`],+∞]. Clipping negative weights to 0 prevents the optimization objective to switch from minimization to maximization, usually an undesirable behavior. Consequently, the samples with a corresponding zero weight reach their maximum contribution in the moments penalization. Further increasing the factors λi, will have no effect on those samples and only samples with non-zero weights will participate in the training. As a result, the efficiency of the moments penalization will slightly fall. Moreover, the samples with zero weight will be excluded from training, technique used in the past by multiple studies. Rockafellar & Uryasev (2000) used a similar clipping technique to optimize only for samples that are part of the tail of the distribution.
The Moments Expansion Theorem extends the variance expansion proposed by Duchi & Namkoong (2019) to include higher-order moments. However, even when only the variance is penalized, the two methods are still slightly different. Moments Expansion Theorem computes the weights directly from the loss values, whereas the variance expansion of Duchi & Namkoong (2019) solves a secondary optimization problem to find the weights. The use of a secondary optimization problem has the
−1 0 1 −1
0
1
2
3
λ2 = 2 λ1 = 1 λ4 = 1 λ3 = 2.5 λ2 = 3 λ1 = 1
−1 0 1 λ2 = −2 λ1 = 1
−1 0 1 λ3 = 1 λ2 = 0.5 λ1 = −0.5
1Figure 2: Polynomial functions for moments penalization. Dotted lines show the complete polynomialwhereas solid lines the clipped version. Left plot shows two convex and non decreasing polynomials. Center plot shows a convex but non increasing polynomial and thus will result in a non convex objective. Right plot shows a convex and non decreasing polynomial on the interval [−1,+∞], and thus will yield a convex objective when min(`)− E[`] ≥ −1.
advantage of penalizing the variance more consistently despite being more computationally expensive. On the contrary, when using the moments expansion, the penalized variance can be slightly lower depending on the number of weights that are 0. However, the advantage is that the direct computation of the weights makes it easier to include the method into existing analysis frameworks. A similar method that extends the optimization objective to include penalization factors for higher-order moments was proposed by Li et al. (2021). The proposed method replaces the ERM objective with a tilted version calculated as 1tK(t) = 1 t logE[e
t`] where K(t) is the cumulant-generating function of the loss `. The penalization of the higher order moments of the tilted ERM can be recovered from the power series expansion of K(t). The distinction between the two is that the moments penalization introduced in this paper represents a generalization of the tilted ERM as it allows any combination of the higher order moments to be penalized whereas tilted ERM uses a single parameter that governs the penalization factors. In summary, the moments penalization implemented using the weighted mean trick is more flexible, however, it comes at a cost as there are more parameters to tune when penalizing multiple moments compared to tilted ERM of Li et al. (2021).
Convergence and convergence rates. The moments penalization problem along with variance expansion of Duchi & Namkoong (2019) fall under the class of distributional robust stochastic programsSun & Xu (2016) (DRSP) which is a subclass of ambiguity programsRoyset & Wets (2017) (AP) where the general objective is:
AP: min θ∈Θ sup P∈D(θ) ϕ(θ, P ) (5)
where Θ is the set of model parameters and D(θ) is the ambiguity set. In DSRP, the bivariate function ϕ(θ, P ) = EP [`] where ` is the loss function and the ambiguity set D(θ) is a set of probability distributions. In the case of moments penalization problem, the ambiguity set D(θ) depends on the model parameters and is a singleton as the weights uniquely transform the empirical distribution. As a result, the optimal value of the inner maximization problem becomes supP∈D(θ) ϕ(θ, P ) = EP [`]. Intuitively, a model will converge if changes in its parameters will cause minor changes in the distribution P , and with each step the distribution will approach the optimum distribution P ∗. Formally, to quantify the changes in the distribution, we would need a distance or a metric. Sun & Xu (2016) use the total variation metric and a pseudometric to prove uniform convergence, possibly at an exponential rate, if P converges to P ∗ under total variation metric and ` is uniformly bounded (see Sun & Xu, 2016, Th. 1 and Prop. 3). Royset & Wets (2017) proposed a hypo-distance metric and proved lop-convergence given that the bivariate function ϕ(θ, P ) satisfies some assumptions, (see Royset & Wets (2017) Def. 4.1). Duchi & Namkoong (2019) provide guarantees for a number of stochastic risk minimization problems when only the variance is penalized and P is in the local neighborhood of the empirical distribution defined using the χ2-divergence. We refer the reader to the works of Sun & Xu (2016) and Royset & Wets (2017) and the references therein for additional guarantees if more information about the problem structure is available, or if other metrics are used. For the moments penalization problem, the moments penalization factors λi for i ≥ 2 determine how
much the distribution P changes when the loss changes. Small values of the penalization factors will keep P in the neighborhood of the empirical distribution, whereas large values will make the weights sensitive to changes in the loss values that can cause stability or convergence issues. The exact values depend on the empirical distribution of the data and the choice of the model and loss function.
Weighted mean trick in practice. To apply the method in practice, the classical batch training algorithm must be extended to include an additional step, the weights calculation. Instead of directly calculating the average loss, the user will calculate the loss value for each sample in the batch and then use the expression from Theorem 3 to compute the weights and the weighted mean. The moments penalization factors λi are the hyper-parameters and are tuned in ascending order with respect to i. However, penalizing higher-order moments might affect the impact of the lower-order ones, and thus, it might require a few iterations to find the optimal combination. The implementation of this algorithm in Pytorch (Paszke et al., 2019) is available on GitHub.1 Since the gradient of the weighted mean is the weighted gradient of the elements, this allows weights to control the impact of each sample on the model parameters. Of note, the theoretical results hold when switching from expectation to sample expectation, En[`] = 1n ∑n i=1 `(f(xi, θ), yi).
Algorithm 1: Training with Moments Penalization
input : f(x; θ) – model to be trained {xi, yi}n1 – batch of training data {λ}m1 – penalization factors `(v, y) – loss function
while stopping criteria not reached do for i← 1 to n do
zi ← `(f(xi, θ), yi) ; /* sample loss */ w ← [∑m j=1 λj(z − En[z])j−1 ] +
Lw ← 1n ∑n i=1 wizi ; /* weighted mean */ θ ← θ − γ∇θLw ; /* update model parameters */

heading: 4 ROBUST CLASSIFICATION
text: In this section, we will explore the robustification of the cross-entropy function under label noise by bounding the loss values using negative variance penalization. In this case, the resulting objective will not be convex. However, for small penalization factors the objective remains convex on almost the entirety of the domain (Figure 3) and does not hinder the convergence. Moreover, we also develop a convex version of the variance penalized cross-entropy though for a minor price in performance.
The objective of robust classification is to learn an optimal classifier f∗ that minimize the average loss for both clean and noisy data. Formally, f∗ = argminE[`(f(x, θ), ŷ)] where ŷ represents noisy labels. The noise considered in this paper corrupts the class labels with probability P(ŷi 6= yi) = η or preserves it with probability P(ŷi = yi) = 1− η, where η ∈ [0, 1]. We investigate two scenarios: when η does not depend on the class label (class independent or uniform noise), and when η depends on the class label (class dependent or asymmetric noise). In what follows, we show that using a negative variance penalization factor, λ2 < 0, bounds the loss function. By bounding the loss function the impact of misclassification of noisy samples on the average loss will decrease, and thus reduce the noise impact on the model during training.
Ghosh et al. (2017) outlined the distribution independent sufficient conditions for a loss function to be robust under both, class dependent and class independent noise. Specifically, if the loss function satisfies the symmetry constraint:
k∑ i=1 `(f(x, θ), i) = C (6)
where k is the number of classes, C is a constant, and the equality holds ∀f, ∀θ,∀x ∈ X , then ` is noise tolerant for class independent noise when η < k−1k (see Theorem 1 of Ghosh et al. (2017)).
1For this phase we submit the source code as part of supplementary materials to preserve anonymity, however, the final version will contain a link to our GitHub repository.
Moreover, if the population risk of the optimum classifier E[`(f∗(x, θ), ŷ)] = 0 then ` is also noise tolerant for class dependent noise. Among the commonly used losses, only the mean absolute error (MAE) satisfies the symmetry constraint. On the other end, the cross-entropy (CE) loss which is widely used for classification, not only does not satisfy the above constraint, but is also an unbounded loss making it extremely susceptible to noise. Specifically, as noise makes the predicted probability of the correct class approach zero, its cross-entropy loss will approach infinity.
Following the work of Ghosh et al. (2017), many studies (Zhang & Sabuncu, 2018; Feng et al., 2020; Wang et al., 2019b; Ma et al., 2020; Wang et al., 2019a) found that models trained with MAE struggle to converge and proposed novel losses that rely on boundedness to achieve robustness instead of the symmetry constraint to avoid convergence problems.
In the following, we use the weighted mean trick to bound a loss function to improve its noise robustness. The next lemma specify the requirements for the weights:
Lemma 5. Let `(v, y) represent an unbounded loss function and w(v, y) a corresponding nonnegative and bounded weight function, then the product w(v, y)`(v, y) is bounded if there exists a finite threshold L0 such that when `(v, y) ≥ L0 the corresponding weights w(v, y) are 0.
Proof. Since when `(v, y) ≥ L0 the corresponding weights w(v, y) = 0 the product w(v, y)`(v, y) is also 0. When `(v, y) < L0 since the weights are bounded the product w(v, y)`(v, y) is also bounded and thus 0 ≤ w(v, y)`(v, y) ≤ B where B is a positive constant that depends on the weight and loss function.
The simplest solution that satisfies the above requirement is the negative variance penalization, λ2 < 0, as the next lemma shows:
Lemma 6. For weights w(v, y) computed using Theorem 3 with λ1 > 0, λ2 < 0, λi = 0,∀i > 2 and with negative weights clipped to 0, penalties `(v, y) ≥ L0 with L0 = E[`] − λ1λ2 will have an associated weight of 0.
Proof. From Theorem 3 the weights are calculated as w(v, y) = λ1 + λ2(`(v, y)− E[`(v, y)]) from which we can determine the threshold value L0 = E[`]− λ1λ2 . Thus due to the non-negativity constraint `(v, y) ≥ L0 will have an associated weight of 0.
Of note, bounding an unbounded loss function is achieved through clipping, however, the resulting loss function is not convex as shown in Figure 3. With parameters λ1 and λ2 along with E[`] establishing which samples are considered noise and excluded from training. Since for λ2 < 0 the threshold L0 = E[`] − λ1λ2 is greater than E[`], thus all excluded samples have a loss value above average. Moreover, the higher the magnitude of λ2, the closer the threshold L0 is to E[`]. This can be seen in the left plot of Figure 3. Moreover, the magnitude of λ2 dictates by how much the loss values below average are amplified and the ones above average suppressed. In practice, using larger values for λ2 will decrease the impact of misclassified samples and those near the separating hyperplane on the placement of the decision boundary. Lemma 6 can be extended to include other higher-order moments. In this case, the roots of the weights polynomial will determine which samples participate in the optimization problem and which are considered noise. For example, if the decision boundary should be decided by samples with average loss values then a possible solution is to penalize skewness. Since in this case the weights are defined by a quadratic equation, and using a negative value for λ3 will make the parabola open downwards and thus assign non-zero weights only to samples around the mean.
Moreover, we also develop a convex version of the variance penalized cross-entropy by constraining the second derivative of the weighted loss function to be non-negative. The cross-entropy loss is defined as `ce(v, y) = − log v[y] where v[y] represents the predicted probability of sample having the label y. To simplify the notation, we will rewrite the cross-entropy loss as `ce(u) = − log u where u = v[y] and similarly rewrite the weight function as w(u) = λ1 + λ2(`(u)−E[`(u)]). We note that the second derivative of the weighted loss w(u)`(u) is 0 for u = uc with uc = exp ( 1 + λ12λ2 − E[`] 2
) and is negative for u < uc. To constrain the second derivative be non-negative we linearly interpolate w(u)`(u) for u < uc using the derivative of w(u)`(u) at uc. The weight function for u < uc
0 1 0
1
2
3
E[`ce] = 1.7
λ2 = −0.1 λ1 = 1 λ2 = −0.2 λ1 = 1
0 1
E[`ce] = 2.5
E[`ce] = 0.5
λ2 = −0.15 λ1 = 1 λ2 = −0.15 λ1 = 1
0 1
λ2 = −0.15 λ1 = 1 λ2 = −0.15 λ1 = 1
1Figure 3: Bounding the cross-entropy loss function using negative variance penalization. Classical cross-entropy function is shown a dotted line. The impact of the λ2 parameter on the loss shape when the average loss is constant is shown on the left plot and the impact of the average loss on the shape in the center plot. Right plot shows the convex version of the variance penalized cross-entropy loss.
is w(u) = [ w(uc)`(uc) + d duw(u)`(u)|u=uc(u− uc) ] /`(u) with the resulting convex objective shown on the right plot of Figure 3. The black dot marks the transition point uc from the weighted cross-entropy on the right to the linear interpolation on the left of the dot. Of note, the resulting objective is still bounded albeit with a higher upper bound.
In general, methods for training of neural networks in the presence of noise can be classified into two broad categories: noise model-free and noise model-based strategies. Noise model-free methods focus on reducing the impact of outliers and the two main subcategories are: robust losses (Bartlett et al., 2006; Ghosh et al., 2017; Wang et al., 2019a; Zhang & Sabuncu, 2018; Wang et al., 2019b; Natarajan et al., 2013; Mnih & Hinton, 2012; Xu et al., 2019; Patrini et al., 2016; Rooyen et al., 2015; Feng et al., 2020; Ma et al., 2020) and learning management such as meta-learning or regularization (Li et al., 2017; Szegedy et al., 2016; Hendrycks et al., 2019; Liu et al., 2020; Harutyunyan et al., 2020; Lugosi & Mendelson, 2021; Laforgue et al., 2021; Lecué et al., 2020; Li, 2017). On the other hand, noise model-based methods estimate the properties of the noise and use this information when train the model. Noise model-based methods can be further divided into: using noise transition matrix (Patrini et al., 2017; Hendrycks et al., 2018; Chen & Gupta, 2015; Bekker & Goldberger, 2016; Goldberger & Ben-Reuven, 2017; Sukhbaatar et al., 2015; Xia et al., 2019; Yao et al., 2019; Wang et al., 2020; Xia et al., 2020; Yao et al., 2020; Lukasik et al., 2020), noise mitigation requiring a clean dataset (Jiang et al., 2018; Ren et al., 2018; Veit et al., 2017; Zhang et al., 2020; Yuan et al., 2018; Vahdat, 2017; Mirzasoleiman et al., 2020), or incrementally estimating the distribution of clean data (Liu et al., 2017; Zheng et al., 2020; Arazo et al., 2019; Zhang et al., 2017; Ghosh & Lan, 2021; Zhang et al., 2021; Wu et al., 2020).
Experimental results. The procedure adopted for all the experiments and elaborated in Appendix B is similar to other studies investigating robust losses (Zhang & Sabuncu, 2018; Feng et al., 2020; Wang et al., 2019b; Ma et al., 2020). The source code to reproduce our results is available online.1
The model accuracy for clean data when training with both, class independent and class dependent noise, are summarized in Table 1. Of note, we report the accuracy results of the model at the end of the training to capture the overfitting on noise for some models. We observe that the training with moments penalization outperforms other methods in low to moderate noise level scenarios and falls behind in high noise scenarios but still above the classical cross-entropy. The performances of the convex version and non-convex version are very similar, however, the convex version shows better results in high noise scenarios under class dependent noise. Additional results when penalizing higher-order moments are provided in Appendix C.
In case of CIFAR datasets, for class independent noise and for η = 0.2 the proposed method improves the accuracy of the classical cross-entropy by 6%, the highest improvement among the investigated methods. However, this improvement decreases as the noise ratio increases and approaches the accuracy of the classical cross entropy loss for η = 0.8. To note, the convex version of the moments method for η = 0.8 underpeformed by 0.8% compared to the classical cross-entropy, however, in
1For this phase we submit the source code as part of supplementary materials to preserve anonymity, however, the final version will contain a link to our GitHub repository.
all other scenarios it had a higher accuracy. High noise scenarios turned out to be challenging for all losses with the Taylor and Generalized cross-entropy losses not converging on CIFAR-10 for η = 0.8 and the best accuracy was registered by Symmetric cross-entropy loss proposed by Wang et al. (2019b). For class dependent noise, the moments penalization registered the highest accuracy for CIFAR-10 when η = 0.1 and η = 0.2 but had the lowest accuracy for η = 0.4. To further investigate this behavior, we reran the experiments and monitored the accuracy for each individual class. The classical cross-entropy recorded similar accuracy as the robust methods on classes affected by noise and outperformed them on classes 6 and 8, both not targeted by class dependent noise. The poor performance of robust methods can be justified by using parameters tuned for low and moderate noise. In case of Fashion-MNIST dataset, as similar behavior as with CIFAR datasets was observed.

heading: 5 CONCLUSION
text: The main goal of the current work was to investigate the optimization of a weighted mean and the flexibility it provides in enforcing properties such as robustness when training with noisy labels. In addition, we extended previous variance penalization methods to include higher-order moments while eliminating some of their limitations. One of the significant findings to emerge from this study was that we can control the final distribution of the loss values by penalizing higher-order moments. In particular, by enforcing the distribution of the cross-entropy to have a higher variance through negative variance penalization, we improved the models’ accuracy when trained with noisy labels. Although this paper centers on classification problems, the framework can also control the bias-variance trade-off and can also be applicable to regression problems.

heading: A PROOFS AND ADDITIONAL THEORETICAL RESULTS
text: First, we present a proposition used in the proof of Theorem 1.
Proposition 7. Let U and V be two random variables, and let U and V denote their expectation, then:
E [( U − U ) V ] = E [( U − U ) ( V − V )] (7)
Proof. To prove we write V as ( V − V ) + V and then use the linear property of the expectation operator:
E [( U − U ) V ] = E [( U − U ) (( V − V ) + V )] = E [( U − U ) ( V − V )] + E [( U − U ) V ]
= E [( U − U ) ( V − V )] + V ( E [U ]− U ) = E [( U − U ) ( V − V )]
Next we present two propositions used in the proofs of the main theorems of this paper.
Proposition 8. Let ` : Rn → [0,∞) and p : R → R two convex functions, then the composition w(x) = p(`(x)−M) where M ≥ 0 is convex if p is non decreasing.
Proof. Using the convexity of ` for any x, y ∈ Rn and α ∈ [0, 1] we have:
`(αx+ (1− α)y) ≤ α`(x) + (1− α)`(y) (8)
Using the fact that p is non decreasing along we the above inequality we obtain:
p(`(αx+ (1− α)y)) ≤ p(α`(x) + (1− α)`(y)) (9)
and using convexity of p for the term on the right we get:
p(α`(x) + (1− α)`(y)) ≤ αp(`(x)) + (1− α)p(`(y)) (10)
Combining the two inequalities leads to the following result (`(αx + (1 − α)y)) ≤ αp(`(x)) + (1− α)p(`(y)) which proves the composition p(`(x)) is convex. Moreover, since p is convex and `(x)−M is in the domain of p then p(`(x)−M) is also convex as it is a composition with an affine mapping. This proves that w(x) is convex.
Proposition 9. Let f, g : Rn → [0,∞) be two convex function taking non-negative values then their product h(x) = f(x)g(x) is convex if [f(x)− f(y)][g(x)− g(y)] ≥ 0,∀x, y ∈ Rn.
Proof. The function h is convex if it satisfies the following inequality where α ∈ [0, 1]:
0 ≤ αh(x) + (1− α)h(y)− h(αx+ (1− α)y) (11) 0 ≤ α(fg)(x) + (1− α)(fg)(y)− (fg)(αx+ (1− α)y) (12)
Note that since the two functions are convex the following inequalities hold:
f(αx+ (1− α)y) ≤ αf(x) + (1− α)f(y) (13) g(αx+ (1− α)y) ≤ αg(x) + (1− α)g(y) (14)
Given that the two functions take non-negative values we can multiply the above two inequalities.
f(αx+ (1− α)y)g(αx+ (1− α)y) ≤ [αf(x) + (1− α)f(y)] [g(x) + (1− α)g(y)] (15) (fg)(αx+ (1− α)y) ≤ [αf(x) + (1− α)f(y)] [g(x) + (1− α)g(y)] (16)
Substituting (fg)(αx+ (1− α)y) from 16 in inequality 11 we obtain: 0 ≤ α(fg)(x) + (1− α)(fg)(y)− [αf(x) + (1− α)f(y)] [g(x) + (1− α)g(y)] (17)
Multiplying the two square brackets and then grouping the terms we get:
0 ≤ α(1− α) [f(x)− f(y)] [g(x)− g(y)] (18)
We complete the proof by noting that α ≥ 0 and thus the product of two convex functions is convex if [f(x)− f(y)] [g(x)− g(y)] ≥ 0.
Lemma 2. As introduced in Theorem 1, the variance expansion of a convex loss function `(v, y) in v yields a new objective that is also convex in v if λ ∈ [0, λmax], where λmax = 1/(E[`]−min `).
Proof. Since y are constants and take finite values we can index both, loss and weight functions, using y as `y(v) = `(v, y) and wy(v) = w(v, y). We note that wy(v) = p(`y(v)−E[`]) where p is a polynomial of degree 1 with p(t) = λt+ 1. First we use the result of Proposition 8 and get that wy(v) is convex if λ is non negative thus the lower bound of the interval. Next, we use Proposition 9 which states that wy(v)`y(v) is convex if [wy(v)− wy(u)] [`y(v)− `y(u)] ≥ 0 and wy(v) is non negative. Since p is a linear function we can use the equality p(a)− p(b) = λ(a− b), with a = `y(v)− E[`] and b = `y(u)− E[`] and replace wy in the previous inequality to obtain λ[`(x)− `(y)]2 ≥ 0 which is always true for λ > 0. However, wy(v) is non negative only for λ ≤ 1/(min ` − E[`]) which proves the upper bound of the interval.
Theorem 3 (Moments Expansion). Let ` be a loss function with finite first m central moments and define w(v, y) = ∑m i=1 λi(`(v, y)− E[`(v, y)])i−1, then we have:
E[w`] = λ1E[`] + m∑ i=2 λ̃iE [ (`− E[`])i ] (4)
where λ̃i = λi + λi+1E[`] for i < m and λ̃m = λm
Proof. In this case, for i ≥ 2 we cannot apply Lemma 7 since the expression (` − E[`])i is not guaranteed to have zero mean and as a result it incurs an additional penalization of the previous moment. The proof follows the same steps as Theorem 1:
E[W`] = E [ m∑ i=1 λi(`− E[`])i−1` ]
= m∑ i=1 λiE [ (`− E[`])i−1` ] = λ1E[`] +
m∑ i=2 λiE [ (`− E[`])i−1` ] = λ1E[`] +
m∑ i=2 λiE [ (`− E[`])i−1(`− E[`] + E[`]) ] = λ1E[`] +
m∑ i=2 λiE [ (`− E[`])i ] + m∑ i=2 λiE[`]E [ (`− E[`])i−1 ] = λ1E[`] +
m−1∑ i=1 λ̃iE [ (`− E[`])i ] + λmE [(`− E[`])m]
For the last step, we combine the two sums by matching the E [ (`− E[`])i ] terms and consolidate
the penalization factors as λ̃i = λi + λi+1E[`].
Lemma 4 (Convexity of Moments Expansion). Let `(v, y) be a loss function convex in v and p : R→ [0,∞) be a non negative and differentiable convex function and M ≥ 0, then the weighted objective w(v, y)`(v, y) with w(v, y) = p(`(v, y)−M) is convex in v if p is non decreasing.
Proof. Since y are constants and take finite values we can index both, loss and weight functions, using y such as `y(v) = `(v, y) and wy(v) = w(v, y). With wy(v) = p(`y(v) −M) and using the result of Proposition 8 we obtain that wy(v) is convex as p is non decreasing. Next, from Proposition 9 and since p takes non negative values we get that the product wy(v)`y(v) is convex if [wy(v)− wy(u)] [`y(v)− `y(u)] ≥ 0. Since p is convex and differentiable we use the first order condition p(a)− p(b) ≥ p′(b)(a− b) with a = `y(v)−M and b = `y(u)−M to obtain:
p(`y(v)−M)− p(`y(u)−M) ≥ p′(`y(u)−M)[`y(v)−M − `y(u) +M ] (19) wy(v)− wy(u) ≥ p′(`y(u)−M)[`y(v)− `y(u)] (20)
Substituting this result in the requirement from Proposition 9 we obtain:
p′(`y(v)−M)[`y(v)− `y(u)]2 ≥ 0 (21)
Given that p is non decreasing implies p′(`(y) −M) ≥ 0 and proves that the inequality always holds.

heading: B EXPERIMENTAL DETAILS
text: After we corrupt the training datasets (CIFAR-10, CIFAR-100, Fashion-MNIST) with noise we retain 10% as a secondary validation dataset. This allows us to detect when the model is overfitting on noise by comparing the performance on clean versus noisy validation data. For the class independent noise, we flip the label to any other class with equal probability such that the ratio of noisy labels is η. For class dependent noise, for CIFAR-10 and Fashion-MNIST we only flip the label in the source classes {9, 2, 3, 5, 4} to the corresponding target class {1, 0, 5, 3, 7} given the noise ratio η. And for CIFAR-100 we flip between two randomly selected subclasses withing each superclass. We use the same modes as in Wang et al. (2019b) when training on CIFAR-10 which is an 8 layer network composed of 6 convolutional layers followed by 2 fully connected layers. For Fashion-MNIST the model contains 4 convolutional layers followed by 3 fully connected layers. For CIFAR-100 the model we use is ResNet-34 (He et al., 2016). We train using SGD with 0.9 momentum, 0.005 weight decay for the convolutional layers and 0.01 for the fully connected layers, and a starting learning rate of 0.01 which we divide by 10 every 20 epochs for a total of 60 training epochs for CIFAR datasets and every 5 epochs for a total of 15 training epochs for Fashion-MNIST. The training batch size is 128 samples.
We compare our solution for robustification of the loss function through moments penalization against five other state of the art methods: i) Tilted empirical risk minimization (TERM) introduced by Li et al. (2021), ii) Taylor expansion of cross entropy (Taylor) proposed by Feng et al. (2020), iii) Normalized cross entropy coupled with reverse cross entropy (Normalized) investigated by Ma et al. (2020), iv) Symmetric cross entropy (Symmetric) studied by Wang et al. (2019b), and v) Generalized cross entropy (Generalized) explored by Zhang & Sabuncu (2018).
Zhang & Sabuncu (2018) proposed a generalized cross-entropy loss parameterized by q that recovers CE loss for q → 0 and MAE for q = 1. For intermediate values of q, the loss is bounded and trades robustness for convergence. Feng et al. (2020) found that the first two terms of the Taylor series expansion for the CE loss are the MAE and MSE, respectively. And suggested adjusting the number of terms in the Taylor expansion for the CE to balance noise robustness and convergence. Wang et al. (2019b) proposed using a two term loss, complimenting the CE loss with a secondary reverse cross-entropy term that satisfies the symmetry constraint. The research by Ma et al. (2020) extended the concept of two term loss combining a robust “active” loss and a robust “passive” loss.
For these methods, when possible we used the same parameters suggested by their authors, however, when the method underperfomed we used cross-validation to find better ones. When training on CIFAR-10 and Fashion-MNIST datasets we used: λ1 = 1, λ2 = −0.5 for Moments and its convex version, t = −0.5 for TERM, t = 2 for Taylor, α = 10, β = 1 for Normalized, α = 0.1, β = 1 for Symmetric, and q = 0.7 for Generalized. When training on CIFAR-100 the parameters where: λ1 = 1, λ2 = −0.5 for Moments and its convex version, t = −0.5 for TERM, t = 6 for Taylor, α = 10, β = 0.1 for Normalized, α = 6.0, β = 0.1 for Symmetric, and q = 0.7 for Generalized.

heading: C ADDITIONAL EXPERIMENTAL RESULTS
text: Table 2 shows the results when penalizing the third (skewness) and fourth (kurtosis) central moments. The resulting polynomial and the corresponding weighted cross-entropy loss are illustrated in Figure 4. When penalizing the third central moment samples with loss values close to the mean receive most weight and the one deviating most from the mean receive the least weight. Experimental results on CIFAR-10 dataset show that when increasing the magnitude of λ3 the accuracy for class independent noise rates η = 0.2 and η = 0.4 improves by around 1%. Moreover, in both cases the resulting accuracy is higher than that of the classical CE. Similarly, for class dependent noise, the accuracy increased by around 1% when penalizing with λ3 = −0.5 for noise rates η = 0.2 and η = 0.3. Likewise, when increasing the magnitude of λ4 the accuracy for class independent noise rates η = 0.2 and η = 0.4 improves by up to 3.5%. However, for class dependent noise the results are similar.
1

Review summaries:
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.

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.

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