Tilted Empirical Risk Minimization
Authors: Tian Li
Ahmad Beirami
Maziar Sanjabi
Virginia Smith
Venue: ICLR 2021 Poster (2021)
Keywords: exponential tilting
models of learning and generalization
label noise robustness
fairness

Abstract: Empirical risk minimization (ERM) is typically designed to perform well on the average loss, which can result in estimators that are sensitive to outliers, generalize poorly, or treat subgroups unfairly. While many methods aim to address these problems individually, in this work, we explore them through a unified framework---tilted empirical risk minimization (TERM). In particular, we show that it is possible to flexibly tune the impact of individual losses through a straightforward extension to ERM using a hyperparameter called the tilt. We provide several interpretations of the resulting framework: We show that TERM can increase or decrease the influence of outliers, respectively, to enable fairness or robustness; has variance-reduction properties that can benefit generalization; and can be viewed as a smooth approximation to a superquantile method. We develop batch and stochastic first-order optimization methods for solving TERM, and show that the problem can be efficiently solved relative to common alternatives. Finally, we demonstrate that TERM can be used for a multitude of applications, such as enforcing fairness between subgroups, mitigating the effect of outliers, and handling class imbalance. TERM is not only competitive with existing solutions tailored to these individual problems, but can also enable entirely new applications, such as simultaneously addressing outliers and promoting fairness.

Published as a conference paper at ICLR 2021
TILTED EMPIRICAL RISK MINIMIZATION
Tian Li CMU
Ahmad Beirami Facebook AI beirami fb.com
Maziar Sanjabi Facehook Al maziars @ ff.com
Virginia Smith CMU
tianli @cmuedu
smithy @ cmmu.edu
ABSTRACT
Empirical risk minimization (ERM) is typically designed to perform well on the average loss, which can result in estimators that are sensitive outliers, generalize poorly, or treat subgroups unfairly. While many methods aim to address these problems individually, in this work, we explore them through unified framework- tilted empirical risk minimization (TERM). In particular, we show that it is possible flexibly tune the impact of individual losses through a straightforward extension to ERM using hyperparameter called the tilt. We provide several interpretations of the resulting framework: We show that TERM can increase or decrease the influence of outliers, respectively, to enable fairness robustness; has variance- reduction properties that can benefit generalization; and can be viewed as a smooth approximation to superquantile method. We develop batch and stochastic first- order optimization methods for solving TERM, and show that the problem can be efficiently solved relative common alternatives. Finally, we demonstrate that TERM can be used for multitude of applications, such as enforcing fairness between subgroups, mitigating the effect of outliers, and handling class imbalance. TERM is not only competitive with existing solutions tailored to these individual problems, but can also enable entirely new applications, such as simultaneously addressing outliers and promoting faireess.
INTRODUCTION
Many statistical estimation procedures rely the concept of empirical risk minimization (ERM), in which the parameter of interest, 0=Ac Rd is estimated by minimizing an average loss over the data:
R(0) = N
Σ f(z50)) M
(1)
While ERM is widely used and has nice statistical properties, it can perform poorly in situations where average performance not an appropriate surrogate for the problem of interest. Significant
research has thus been devoted developing alternatives to traditional ERM for diverse applications,
such as learning in the presence of noisy/corrupted data (Jiang et al. 2018 Khetan et al.) 2018),
performing classification with imbalanced data (Lin et al. 2017 Malisiewicz al. 201 1), ensuring that subgroups within population are treated fairly (Hashimoto et al.] (Smad et all 2018)) or
developing solutions with favorable -f-mpll performance (Namkoong Duchi [0117)
In this paper, we suggest that deficiencies in ERM can be flexibly addressed via a unified framework, tilted empirical risk minimization (TERM). TERM encompasses family of objectives, parameterized by a real-valued hyperparameter, For R the i-tilted loss (TERM objective) is given by:
i 0) = t
1
log
Σ ic[M]
N
TERM generalizes ERM as the O-tilted loss recovers the average loss, i.e., 0) also recovers other popular alternatives such as the max-loss (L-++0) and min-loss (t~-o0) (1 (Lemma?) 2). For ビ 0, the objective is common form of exponential smoothing, used to approximate the max (Kort & Bertsekas 1972, Pee & Royset 201T). Variants of tilting have been studied in several contexts,
* *Equal contribution.
(O; 0) is defined in
via the continuous extension of R(t; 0).

---

Published as a conference paper at ICLR 2021
point estimation
linear regression
logistic regression
2.0
18-
155
10
1.
sample mean
0.5
plometric mediam
00
-2
0.0
15.0
10
1.0
15
[xx:0] T0 2z)
f1., v: 7 (0 x- y)
f(r.3: log(1 e--00
Toy examples illustrating TERM as function of t: (a) finding a point estimate from a set of 2D samples, (b) linear regression with outliers, and (c) logistic regression with imbalanced classes. While positive values of t magnify outliers, negative values suppress them. Setting t=0 recovers the original ERM objective I
Figure I:
including robust regression (Wang et al., 2013) (l~0), importance sampling (Wainwright et al. 2005 sequential decision making (Howard & Matheson 1972, Nass et al.) 2019), and large deviations theory (Beirami et al. 2018). However, despite the rich history of tilted objectives, they have not seen widespread use in machine learning. In this work, aim to bridge this gap by: (i) rigorously studying the objective in a general form, and (ii) exploring its utility for a number of ML applications. Surprisingly, we find that this simple extension to ERM is competitive for wide range of problems.
To highlight how the TERM objective can help with issues such as outliers or imbalanced classes, we discuss three motivating examples below, which are illustrated in Figure []
(a) Point estimation: As a first example, consider determining a point estimate from a set of samples that contain some outliers. We plot an example 2D dataset in Figure with data centered at (1,1). Using traditional ERM (i.e., TERM with 1 = 0) recovers the sample mean, which can be biased towards outlier data. By setting of the largest losses (i.c., points that are far from the estimate) in (2). A specific value of t < 0 can in fact approximately recover the geometric median, as the objective in (2) can be viewed as approximately optimizing specific loss quantiles (a connection which we make explicit in Section 2)
TERM can suppress outliers by reducing the relative impact
In contrast, if these 'outlier' points are important to estimate, setting t > 0 will push the solution towards a point that aims to minimize variance, as we prove more rigorously in Section 2
Theorem 4
(b) Linear regression: A similar interpretation holds for the case of linear regression (Figure 2b). As i - x0, TERM finds line of best while ignoring outliers. However, this solution may not be preferred if we have reason to believe that these 'outliers' should not be ignored. As t - +00, TERM recovers the min-max solution, which aims to minimize the worst loss, thus ensuring the model is reasonable fit for all samples (at the expense of possibly being a worse fit for many). Similar criteria have been used, e.g., in defining notions of fairness (Hashimoto et al., 2018 [Samadi al. 2018). We explore several use-cases involving robust regression and fairness in more detail in Section
(c) Logistic regression: Finally, we consider a binary classification problem using logistic regression (Figure 2c). For t E R. the TERM solution varies from the nearest cluster center (t~>-oo). to the logistic regression classifier (t=0), towards classifier that magnifies the misclassified data (t-++00) We note that it is common to modify logistic regression classifiers by adjusting the decision threshold from 0.5, which is equivalent to moving the intercept of the decision boundary. This fundamentally different than what is offered by TERM (where the slope is changing). As we show in Section 5 this added flexibility affords TERM with competitive performance on a number of classification problems, such as those involving noisy data, class imbalance, or a combination of the two.
Contributions. In this work, we explore TERM as a simple, unified framework to flexibly address various challenges with empirical risk minimization. We first analyze the objective and its solutions, showcasing the behavior of d'TERM with varying (Section Our analysis provides novel connections between tilted objectives and superquantile methods. We develop efficient methods for solving TERM (Section 4. and show via numerous case studies that TERM is competitive with existing, problem- specific state-of-the-ard solutions (Section ()). We also extend TERM handle compound issues, such as the simultaneous existence of noisy samples and imbalanced classes (Section Our results demonstrate the effectiveness and versatility of tilted objectives in machine learning.
2

---

Published as a conference paper at ICLR 2021
2 TERM: PROPERTIES & INTERPRETATIONS
To better understand the performance of the i-tilted losses in 2 we provide several interpretations of the TERM solutions, leaving the full statements of theorems and proofs to the appendix. We make no distributional assumptions on the data, and study properties of TERM under the assumption that the loss function forms generalized linear model, e.g., Le loss and logistic loss (Appendix D). However, we also obtain favorable empirical results using TERM with other objectives such as deep neural networks and PCA in Section motivating the extension of our theory beyond GLMs in future work.
General properties. We begin by noting several gen- eral properties of the TERM objective (2). Given a
1:08 (180--9+-007 (040 0.2/ (6 18- 122
smooth [x; 9). the t-tilted loss is smooth for all finite t
(Lemmal 4p. If (2;; 0) is strongly convex, the f-tilted loss
is strongly convex for & > 0 (Lemma 5). We visualize the solutions to TERM for a toy problem in Figure 2 which allows us to illustrate several special cases of the general framework. As discussed in S TERM can recover traditional ERM (l=0), the max-loss (L-++-00, and the min-loss (1- (l) As we demonstrate Section []] pro- viding smooth tradeoff between these specific losses can be beneficial for a number of practical use-cases- both in terms of the resulting solution and the difficulty of solving the problem itself. Interestingly, we additionally show that the TERM solution can be viewed as a smooth approximation to a superquantile method, which aims to minimize quantiles of losses such as the median loss. In Figure 2, it is clear to see why this may be beneficial, as the median loss (orange) can be highly non-smonee non-smooth in practice. We make these rough connections more explicit via the interpretations below.
moax-
1.0
avg loss
R 01
0.5
mediinn-loss
00
00000
-0.75 -0.00 -0.35 0.00
0.75
1.00
1.25
1.50
0
Figure 2: TERM objectives squared loss problem with N 3. As moves from -00 to +00 t-tilted losses recover min-loss, avg- loss, and max-loss. TERM is smooth for all finite and convex for positive t.
(Interpretation 1) Re-weighting samples to magnifylsuppress outliers. As discussed via the toy examples in Section the TERM objective can be tuned (using !) to magnify or suppress the influence of outliers. We make this notion rigorous by exploring the grudient of the l-tilted loss in order to reason about the solutions to the objective defined in (2.
Lemma 1 (Tilted gradient, proof in Appendix B). For a smooth loss function fx;; 0),
vol((1;0)= Σ v((::))o[[(;;)) where w.(t:0)== Ejsnn - -(((0:0)) (3) (E[
e'f(xx0))
1 N
From this, we can observe that the tilted gradient is a weighted average of the gradients of the original individual losses, where each data point is weighted exponentially proportional to the value of its loss. Note that t = 0 recovers the uniform weighting associated with ERM, i.e., w, 0) = L/N. For positive t, it magnifies the outliers maaples--sampls samples with large losses- by assigning more weight them, and for negative t, it suppresses the outliers by assigning less weight to them.
(Interpretation 2) Tradeoff between average-loss and min/maa-loss. To put Interpretation / in context and understand the limits of TERM, a benefit of the framework is that it offers a continuum of solutions between the min and max losses. Indeed, for positive values of L, TERM enables a smooth tradeoff between the average-loss and max-loss (as we demonstrate in Figure TO Appendix I].. Hence, TERM can selectively improve the worst-performing losses by paying a penalty on average performance, thus promoting notion of uniformity or fairness (Hashimoto et al.) 2018). On the other hand, for negative f, the solutions achieve a smooth tradeoff between average-loss and min-loss, which have the benefit of focusing on the 'best' losses, ignoring outliers (Theorem 3 Appendix (D).
Theorem (Formal statement and proof in Appendix D Theorem 3). Let Ö(t) be the minimizer of R((:;), referred as t-tiled solution. Then, for > max-loss, R((()), is non-increasing with I.
while the average loss R(O(t)), non-decreasing with
(Interpretation 3) Empirical bias/variance tradeoff. Another key property of the TERM solutions is that the empirical variance of the loss across all samples decreases as / increases (Theorem
3

---

Published as a conference paper at ICLR 2021
Hence, by increasing it is possible to trade off between optimizing the average loss vs. reducing variance, allowing the solutions to potentially achieve a better Dias-variame tradeoff for generaliza- tion (Benneti 1962 [Hoefdiing 1994; Maurer & Pontil 2009) (Figure TO Appendix D We use this property to achieve better generalization in classification in Section 5 We also prove that the cosine similarity between the loss vector and the all-ones vector monotonically increases with t (Theorem S which shows that larger t promotes more uniform performance across all losses and can have implications for fairness defined as representation disparity (Hashimoto al. 2018 (Section 5.2).
Theorem (Formal statement and proof in Appendix D Theorem
Let f(0)
0)) be the loss vector for parameter 0. Then, the variance of the vector f(O(t)) is non-increasing with while its average, i.e., R(((t)), is non-decreasing with t.
(Interpretation 4) Approximate superquantile method. Finally, we show that TERM is related to superquantile-bass based objectives, which aim to minimize specific quantiles of the individual losses that exceed certain value (Rockafellar al. 2000). For example, optimizing for 90% of the individual losses (ignoring the worst-performing 10%) could be a more reasonable practical objective than the pessimistic min-max objective. Another common application of this is to use the median in contrast to the mean in the presence of noisy outliers. As we discuss in Appendix G superquantile methods can be reinterpreted minimizing the k-loss, defined as the k-th smallest loss of N (i.e., 1-loss is the min-loss, N-loss is the max-loss, (N-1)/2-loss is the median-loss). While minimizing the k-loss is more desirable than ERM in many applications, the kollsss is non-smooth (and generally non-convex), and is challenging to solve for large-scale problems (Jin et al. 2020 Nouiched et al. 2019b).
Theorem (Formal statement and proof in Appendix G Theorem 10P. The quantile of the losses that exceed a given value is upper bounded by smooth function of the TERM objective. Further, the t-tilted solutions are good approximate solutions of the superquantile (k-loss) optimization.
3 TERM EXTENDED: HIERARCHICAL MULTI- TILTING
We also consider extension of TERM that can be used to address practical applications requiring multiple objectives, e.g., simultancously achieving robustness to noisy data and ensuring fair perfor- mance across subgroups. Existing approaches typically aim to address such problems isolation. To handle multiple objectives with TERM, let each sample x be associated with group g e [G), i.e., x g- These groups could related to the labels (e.g., classes in a classification task), or may depend only on features. For any L, r I, we define multi-objective TERM as:
[(I. = log
1
1 N
Σ gE[G]
(g(10)
where Rg(T; log
1 Σ (T(liz)) (4) zeg
and |g| is the size of group g. Multi-objective TERM recovers sample-level TERM special case for r = (Appendix, Lemma 7) and reduces to group-level TERM with T - 0. Note that all properties discussed Section carry over to group-level TERM. Similar the tilted gradient (3). the multi-objective tilted gradient is a weighted sum of the gradients (Appendix, Lemma making similarly efficient to solve. We validate the effectiveness of hierarchical tilting empirically in Section 5.3 where we show that TERM can significantly outperform baselines to handle class imbalance and noisy outliers simultaneously.
4 SOLVING TERM
To solve TERM, we suggest batch and stochastic variants of traditional first-order gradient- based optimization methods. TERM in the batch setting (Batch TERM) is summarized in Algorithm [ in the context of solving multi-objective hierarchical TERM 44) for full generality. The main steps include computing the tilted gradients of the hierarchical objective defined in (4). Note that Batch TERM with t reduces to solving the sample-level tilted objective
2 We also provide a stochastic variant in Algorithm] Appendix H At a high level, at each iteration, group-level tilting is addressed by choosing group based on the tilted weight vector estimated via stochastic dynamics. Sample-level tilting is then incorporated by re- re-weighting the samples in a uniformly drawn mini-batch. We find that these methods perform well empirically on variety of tasks (Section
4

---

Published as a conference paper at ICLR 2021
Algorithm 1: Batch TERM
Input: T,
while stopping criteria not reached do
for g E [G] do
compute the loss [x; 0) and gradient Vof(z; 0) for all E
Rg. + r-tilted loss (4) on group Vo Rg 1
1
Exey R Vos(:
end
Ja,r log N Ege Ig]e lolet whir Igle
0 - 1 N S we Vo VoRg
end
We defer readers Appendix H for general properties of TERM (smoothness, convexity) that may vary with / and affect the convergence of gradient-based methods used to solve the objective.
5 TERM IN PRACTICE: USE CASES
In this section, we showcase the flexibility, wide applicability, and competitive performance of the TERM framework through empirical results a variety of real-world problems such as handling outliers 3.ID.. ensuring fairness and improving generalization (Section 5.2). and addressing compound issues (Section 5.3). Despite the relatively straightforward modification TERM makes to traditional ERM, we show that f-tilted losses not only outperform ERM, but either outperform or are competitive with state-of-the-art, problem-specific tailored baselines on a wide range of applications.
We provide implementation details in Appendix J available github. com/ it an 9 TERM For experiments with positive (Section (.2). we tune E {0.1, 0.5, 1, 5, 10, 50, 100, 200} on the validation set. In our initial robust regression experiments, we find that the performance is robust to various t's, and we thus use a fixed -2 for all experiments involving negative t (Section [.] and Section 5.3).. For all values of t tested, the number of iterations required to solve TERM within 2x that standard ERM.
All code, datasets, and experiments are publicly
5.1 MITIGATING NOISY OUTLIERS
We begin by investigating TERM's ability to find robust solutions that reduce the effect of noisy outliers. We note that we specifically focus on the setting of 'robustness' involving random additive noise; the applicability of TERM to more adversarial forms of robustness would be an interesting direction of future work. We do not compare with approaches that require additional clean validation data (e.g.. [Hendryeks et al. 2018 Ren et al. 2018 Roh al. 2020 Veit et al. 2017). as such data
can be costly to obtain in practice.
Robust regression. We first consider regression task with noise corrupted targets, where we aim to minimize the root mean square error (RMSE) on samples from the Drug Discovery dataset (Diakoniko) las et 2019 Olier al. 2018). The task to predict the bioactivities given set of chemical compounds. We compare against linear regression with an Le loss, which we view as the 'standard" ERM solution for regression, well as with losses commonly used mitigate outliers-the L1 loss and Huber loss (Huber, 1964). We also compare with consistent robust regression (CRR) (Bhatia al. 2017) and STIR Mukkhoty et al., 2019). recent state-of of of-the-art methods specifically designed for label noise in robust regression. In this particular problem, TERM is equivalent to exponential squared loss, studied (Wang et al., (003). We apply TERM at the sample level with an L-2 loss, and generate noisy outliers by assigning random targets drawn from (5, 5) fraction of the samples.
In Table I. we report RMSE on clean test data for each objective and under different noise levels. We also present the performance of an oracle method (Genie ERM) which has access to all of the clean data samples with the noisy samples removed. Note that Genie ERM is not a practical algorithm and is solely presented to set the expected performance limit in the noisy setting. The results indicate that TERM is competitive with baselines on the 20% noise level. and achieves better robustness with moderate-to-extren noise. We observe similar trends in scenarios involving both
5

---

Published as a conference paper at ICLR 2021
noisy features and targets (Appendix L.2
CRR tends to run slowly as it scales cubicly with the while solving TERM is roughly as efficient as ERM.
number of dimensions (Bhatia et al. 2017
Table 1: TERM is competitive with robust regres- sion baselines, particularly in high noise regimes.
Table 2: TERM is competitive with robust classification
baselines, and superior high noise regimes.
objectives
RMSE (Drug Discovery)
objectives
test accuracy (CTPART 0. Inception)
20% noise 40% noise
80% noise
20% noise
40% noise
80% noise
ERM
1.87 con
2.83 c/o
4.74 ,80
ERM
0.775 use
0.719 use
0.284 ca4)
En
1.15
1.70
4.78
RandomRoct Ren et al. 2018
0.744
0.699
0,384 caol
Huber Huber 1964
1.16 con
1.78 cI1)
4.7
SelfPaced Kumnar m0 2010
0.784 use
0.733 use
0.272 c04)
STIR
(iiukaay al. 2019
1.16
1.75
4.74
MentorNet miing et mr 2018
0.798
0.731
0,312 can)
CRR (Thana et al. 2017]
1.10 com
1.51 698)
4.07 190
GCE (hhang Sahinen 2018
0.805 ree
0.750
cam
TERM
1.08
1.30
1,68
TERM
0.795
0,768
0,455
Gonie ERM
1.02
1,07
1.04
Genic ERM
0.828 usei
0.820 (KA)
0.792 (304)
Note that the outliers considered here unstructured with random noise, and not adversarial. This makes it possible for the methods to find the underlying structure of clean data even if the majority of the samples are noisy outliers. To gain more intuition on these cases, we also generate synthetic two-dimensional data points and test the performance of TERM under 0%, 20%, 40%, and 80% noise for linear regression. TERM with & 2 performs well in all noise levels (Figure I and 2 in Appendix I.2). However, as might be expected, in Figure 14 (Appendix (.2) we show that TERM may overfit to noisy samples when the noise is structured and the noise values are large (e.g., 80%).
Robust classification. It is well-known that deep neural networks can easily overfit to corrupted labels (e.g..ZZhang et al. 2017). While the theoretical properties we study for TERM (Section 2 do not directly cover objectives with neural network function approximations, we show that TERM can be applied empirically to DNNs to achieve robustness to noisy training labels. MentorNet (Jiang et al. 2018) is popular method in this setting, which learns to assign weights to samples based on feedback from a student net. Following the setup in Jiang et al, (2018). we explore classification on CIFARIO (Krizhevsky et al.] (009) when fraction of the training labels are corrupted with uniform
noise- coise-comparing TERM with ERM and several state-of-the-arr approaches (Krizhessky et al. 2009)
Kumar et al. 2010: Ren al. 2018, iZhang & Sabuncu 2018). As shown in Table TERM performs competitively with 20% noise, and outperforms all baselines in the high noise regimes. We use MentorNet-PD baseline since it does not require clean validation data. In Appendix [12], we show that TERM also matches the performance of MentorNet-DD, which requires clean validation data, To help reason about the performance of TERM, we also explore simpler, two-dimensional logistic regression problem in Figure [3] Appendix I.2 finding that TERM with t=-2 is similarly robust across the considered noise regimes.
Low-quality annotators. It is not uncommon for practitioners to obtain human-labeled data for their learning tasks from crowd-sourcing platforms. However, these labels are usually noisy in part due to the varying quality of the human annotators. Given a collection of labeled samples from crowd-workers, we aim to learn statistical models that are robust the potentially low-quality annotators. As a case study. following the setup of (Khetan et al., 2018). we take the CIFAR- 10 dataset and simulate 100 annotators where 20 of them are hammers (i.e., always correct) and 80 of them are spammers (i.e., assigning labels uniformly at random). We apply TERM at the annotator group level in (4 which equivalent to assigning annotator-leve weights based on the aggregate value of their loss. As shown in Figure 3 TERM is able to achieve the test accuracy limit set by Genie ERM, i.c., the ideal performance obtained by completely removing the known outliers. We note in particular that the accuracy reported by (Khetan et al. 2018) (0.777) is lower than TERM (0.825) in the same setup, even though their approach is a two pass algorithm requiring at least to double the training time. We provide full empirical details and investigate additional noisy annotator scenarios in Appendix 1.2
5.2 FAIRNESS AND GENERALIZATION
In this section, we show that positive values of in TERM can help promote faimesss (e.g., via learning fair representations), and offer variance reduction for better generalization.

---

Published as a conference paper at ICLR 2021
CIFAR10
Credit
MNIST and 9 digits
Winks sieeaa TERM b-200 Halis TERN -200
Unit accurkey
test accurnicy
TERM
Lcannoovaate (Pon
TERM sole
614
aciee
3.30
Hardhinn (Ma
Ganic ERM
Focal (Lin al)
MBEM (Kieiin d.
3.50 L/Md
epachs
terget dimension
class
Figure 3: TERM (t=-2) com- pletely removes the impact of noisy annotators, reaching the perfor- mance limit set by Genie ERM.
Figure 4: TERM-PCA flexibly trades the performance on the high (H) edu group for the performance on the low (L) edu group.
Figure 5: TERM (t= 100) com- petitive with sfate-of-the-ase meth- ods for classification with imbal- anced classes.
Fair principal component analysis (PCA), We explore the flexibility of TERM in learning fair representations using PCA. In fair PCA, the goal is learn now-dimensional representations which are fair to all considered subgroups (e.g., yielding similar reconstruction errors) (Kamani ct al. 2019; (Samadi et al. 2018 Tantipongpipat al. 2019). Despite the non-convexity of the fair PCA problem, we apply TERM to this task, referring to the resulting objective as TERM-PCA. We tilt the same
loss function as in (Samadi et al. 8): [(X:U) = [XT (Ix- - XUU (UX-XUUT P3-
where |X -
x13)
X Ruxd is subset (group) of data, U R is the current projection, and X Raxd is the optimal rank-r approximation of X. Instead of solving a more complex min-max problem using semi-definite programming as in (Samadi et al. 2018), which scales poorly with problem dimension, we apply gradient-based methods, re-weighting the gradients at each iteration based on the loss on each group. In Figure 4 we plot the aggregate loss for two groups (high vs. low education) in the Default Credit dataset (Ych & Lien| 2009) for different target dimensions r. By varying t, we achieve 200) recovers the min-max results of (Samadi et al.) (011)) by forcing the losses on both groups to be (almost) identical, while TERM (t- 10) offers the flexibility of reducing the performance gap less aggressively.
varying degrees of performance improvement on different groups groups- TERM
Handling class imbalance. Next, we show that TERM can reduce the performance variance across classes with extremely imbalanced data when training deep neural networks. We compare TERM with several baselines which re-weight samples during training, including assigning weights inversely proportional to the class size (InverseRatio), focal loss (Lin et al. 2017)) HardMine (Malisiewicz et al. 20 and LearnReweight (Ren et al., 2018). Following (Ren et al. 2018), the datasets are composed of imbalanced and 9 digits from MNIST (LeCun et al. (998). In Figure 5]
we see that TERM obtains similar (or higher) final accuracy on the clean test data as the state-of-the-e methods. We note that compared with LearnReweight, which optimizes the model over an additional balanced validation set and requires three gradient calculations for each update, TERM neither requires such balanced validation data nor does it increase the per-iteration complexity.
Improving generalization via variance reduction. A common alternative to ERM is to consider a distributionally robust objective, which optimizes for the worst-case training loss over a set of distri- butions, and has been shown to offer variance-reduction properties that benefit generalization (e.g.. Namkoong Duchi 2017) Sinha et al., (2088). While not directly developed for distributional robust- TERM also enables variance reduction for positive values of t (Theorem 4). which can be used to strike a better bias variance tradeoff for generalization. We compare TERM with several baselines including robustly regularized risk (RobustRegRisk) (Namkoong & Duchi 2017), linear SVM (Ren
et al. 2018). LearnRewight (Ren et al. 2018). FocalLoss (Lin et al. (017). D. and HRM (Leqi et al.
2019
The results and detailed discussions are presented in Appendix 1.2
5.3
SOLVING COMPOUND ISSUES: HIERARCHICAL MULTI-OBJECTIV TILTING
Finally, in this section, we focus on settings where multiple issues, e.g., class imbalance and label noise, exist in the data simultaneously. We discuss two possible instances of hierarchical multi- objective TERM to tackle such problems. One can think of other variants in this hierarchical tilting space which could be useful depending on applications at hand. However, we not aware of other
7

---

Published as a conference paper at ICLR 2021
prior work that aims to simultaneously handle multiple goals, e.g., suppressing noisy samples and addressing class imbalance, in a unified framework without additional validation data.
We explore the HIV-1 dataset (Rögnvaldsson 2013), as in Section 5.2 We report both overall accuracy and accuracy on the rare class in four scenarios: (a) clean and 1:4, the original dataset that is naturally slightly imbalanced with rare samples represented 1:4 with respect to the common class; (b) clean and 1:20, where we subsample to introduce a 1 1:20 imbalance ratio; (c) noisy and 1:4, which is the original dataset with labels associated with 30% of the samples randomly reshuffled; and (d) noisy and 1:20, where 30% of the labels of the 1: 1:20 imbalanced dataset are reshuffled.
Table 3: Hicrarchical TERM can address both class imbalance and noisy samples.
test accuracy (HIV
objectives
clean data
30% noise
1:20
1:4
1:20
Y
overall
Y
0 overall
Y
0 overall
Y 0
overall
ERM
0,822 (09) 0,934 cm0
0.503 (res)
0.888 (00) 0.656 cnr 0.911 com0
0,240
0.831 .0rs
GCE (Zhang& & Sabuncu
2018
0,822 (e9) 0.934 uso
0.503 crs
0.888 (e8)
0.732 omn 0.925 cop
0.324 om/ 0.849 use
Learnkewerght (Ken 2018
0.841
0,934
0.800 coo 0.904
0.721
0.856
0,532
0.856 cm)
RobusiRegRisk (Nankoong & Duchi 2017
0.844 mm) 0.939 cme
0.622 (20))
0.906 (05)
0.634 care: 0.907 (00
0.051 omn
0.792 c012)
Focall oss [Lin et
0.834 (m))) 0.937
0.806
0.918
0.638
0.908
0.565
0.890..om
TERM
0.840 u02 0.937 usu
0.836 (205)
0.921
(862)
0.852
0.924 c000
0.778
uxei
0.900 use:
TERM
0.844 (m0 0.938 (X94)
0.834 (231)
0.918
(003)
0.846
cnus) 0.933
c000
0.806
uzz 0.901 c000
In Table 3, hicrarchical TERM is applied at the sample level and class level (TERMac). where we use the sample-level tilt of r=-2 for noisy data, We use class-level tilt of t=0.1 for the 1:4 case and t=50 for the 1:20 case. We compare against baselines for robust classification and class imbalance (discussed previously in Sections|5.JJann 5.2). where we tune them for best performance (Appendix[].
Similar the experiments in Section 5.1 we avoid using baselines that require clean validation data (e.g.. Roh et al., 2020). While different baselines perform well in their respective problem settings, TERM is far superior all baselines when considering noisy samples and class imbalance simultancously (rightmost column in Table 3) Finally, in the last row of Table 3 we simulate the noisy annotator setting of Section [.. Jssuming that the data is coming from 10 annotators, i.e., in the 30% noise case we have 7 hammers and 3 spammers. In this case, we apply hierarchical TERM at both class and annotator levels (TERM ) where we perform the higher level tilt at the annotator (group) level and the lower level tilt at the class level (with no sample-level tilting). We show that this approach can benefit noisy/imbalanced data even further (far right, Table 3. while suffering only a small performance drop the clean and noiscless data (far left, Table 3
6 RELATED WORK
Alternate aggregation schemes: exponential smootiingssupeqqaaniiie methods. common alternative to the standard average loss in empirical risk minimization is to consider a min-max objective, which aims to minimize the max-loss, Min-max objectives are commonplace in machine learning, and have been used for wide range of applications, such as ensuring fairness across subgroups (Hashimoto et al., 2018 Mohri et al. 2019 Samadi et al. 2018 Stelmakh et al. 2019 Tantipongpipat et al.) 2019), enabling robustness under small perturbations (Sinha et al. 2018). or generalizing to unseen domains (Volpi et al., 2018). As discussed in Section 2 the TERM objective can be viewed as a minimax smoothing (Kort & Bertsekas) 1972, Pee & Royset 2011 with the
added flexibility of a tunable / to allow the user to optimize utility for different quantiles of loss
similar superquantile approaches (Laguel et al.) 2202 Rockafellar et al. 2000), directly trading off between robustness/farnness and utility for positive and negative values of (see Appendix G for these connections). However, the TERM objective remains smooth (and efficiently solvable) for moderate values of t, resulting in faster convergence even when the resulting solutions are effectively the same as the min-max solution or other desired quantiles of the loss (as we demonstrate in the experiments of Section Such smooth approximations to the max often appear through LogSumExp functions, with applications in geometric programming (Calafiore & El Ghaoui 2014, Sec. 9.7), and boosting (Mason et al. 1999| (Shen & Li 2010). Interestingly, Cohen al. introduce Simnets (Cohen & Shashual (2044] Cohen et al., 2016), with a similar exponential smoothing operator, though for a differing purpose of achieving layer-wise operations between sum and max in deep neural networks.
8

---

Published as a conference paper at ICLR 2021
Alternate loss functions. Rather than modifying the way the losses aggregated, as in (smoothed) min-max or superquantile methods, it is also quite common to modify the losses themselves. For example, in robust regression, it is common to consider losses such the L loss, Huber loss. or general Messtmmators (Holland & Ikeda 2019) as a way to mitigate the effect of outliers (Bhatia et al. 2015). (Wang al.] 2013) studies similar exponentially tilted loss for robust regression, though it is limited to the squared loss and only corresponds to t<0 Losses can also be modified
to address outliers by favoring small losses (Yu et al. 2012: Zhang & Sabuneu 2018) or gradient clipping (Menon et al.) 2020). On the other extreme, the largest losses can be magnified to encourage focus on hard samples (Li et al.] 2020b Lin al. 2017] Wang et al. (016), which is a popular
approach for curriculum learning. Constraints could also be imposed to promote fairness (Baharlouei
jet al. 2020 Donini et al., 2018 Hardt et al., 2016 Rezaei et al. 2020 Zafar et al., 2017). Ignoring the log portion of the objective in (2. TERM can be viewed as an alternate loss function exponentially shaping the loss to achieve both of these goals with a single objective, i.c., magnifying hard examples with > 0 and suppressing outliers with < 0. In addition, we show that TERM can even achieve both goals simultaneously with hierarchical multi-objective optimization (Section 5.33.
Sample re-weighting schemes. Finally, there exist approaches that implicitly modify the underlying ERM objective by re-weighting the influence of the samples themselves. These re-weighting schemes can be enforced in many ways. A simple and widely used example is subsample training points in different classes. Alternatively, one can re-weight examples according to their loss function when using a stochastic optimizer, which can be used to put more emphasis on "hard" examples (Jiang iet al. 2019: (Katharopoulos & Fleuret 2017 2017 Legi ct al. 2019 Shrivastava et al. 2016). Re-weighting can also be implicitly enforced via the inclusion of a regularization parameter (Abdelkarim al.
2020), loss clipping (Yang et al. 2010), or modelling crowd- wowd-woreer qualities (Khetan et al. [0 8)
Such an explicit re- weightinng has been explored for other applications (e.g.. [hga.n et al. 2017 Gao
al. 2015 Jiang et al., 2018 Lin et al. 2017]] Ren et al. 2018 Shu et al., (2019), though in contrast to these methods, TERM is applicable to a general class of loss functions, with theoretical guarantees.
TERM is equivalent to dynamic re- se-weighting of the samples based on the values of the objectives
(Lemma D}. which could be viewed as a convexified version of loss clipping. We compare to several sample re- w-eeighting schemes empirically in Section 5
7 CONCLUSION
In this paper, we examined tilted empirical risk minimization (TERM) a flexible extension to the ERM framework. We explored, both theoretically and empirically, TERM's ability to handle various known issues with ERM, such as robustness to noise, class imbalance, fairness, and generalization, as well as more complex issues like the simultaneous existence of class imbalance and noisy outliers. Despite the straightforward modification TERM makes traditional ERM objectives, the framework consistently outperforms ERM and delivers competitive performance with specific methods on a wide range of applications. Our work highlights the effectiveness and versatility of tilted objectives in machine learning. Building on the analyses and empirical study provided herein, in future work, would be interesting to investigate generalization bounds for TERM as a function of t, and to derive theoretical convergence guarantees for our proposed stochastic solvers.
problem-
ACKNOWLEDGEMENT
We are grateful to Arun Sai Suggala and Adarsh Prasad (CMU) for their helpful comments on robust regression; to Zhiguang Wang, Dario Garcia Garcia, Alborz Geramifard, and other members of Facebook AI for productive discussions and feedback and pointers to prior work (Cohen & Shashua
2014 Cohen et al.) 2016: RRocafellar et al. 2000; Wang et al. 2016): and to Mcisam Razaviyayn
(USC) for helpful discussions and pointers to exponential smoothing (Kort & Bertsekas 1972 Pee &
Royset 2011). Value-at-Risk (Nouiehed et al. 2019a Rockafellar & Uryasev 2002). and general
properties of gradient-based methods in non-convex optimization problems (Ge et al. 2015 Jin
ct al. 2017 2020; Ostrovskii et al., 2020). The work of TL and VS was supported in part by the National Science Foundation grant IIS1838017 a Google Faculty Award, Carnegie Bosch Institute Research Award, and the CONIX Research Center. Any opinions. findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the National Science Foundation or any other funding agency.

---

Published as a conference paper at ICLR 2021
REFERENCES
Sherif Abdelkarim, Panos Achlioptas. Jiaji Huang, Boyang Li. Kenneth Church, Mohamed Elhoseiny. Long-tail visual relationship recognition with a visiolinguistic hubless loss, arXiv preprint ar arxiv:204.0004. 2020.
Sina Baharlouei, Maher Nouiched, Ahmad Beirami, and Meisam Razaviyayn. Rényi fair inference. International Conference on Learning Representations, 2020.
Ahmad Beirami, Robert Calderbank, Mark M Christiansen, Ken R Dufty, and Muriel Médard. characterization of guesswork on swiftly tilting curves. IEEE Transactions on Information Theory, 2018.
George Bennett. Probability inequalities for the sum independent random variables, Journal of the American Statistical Association, 1962.
Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression via hard thresholding, In Advances in Neural Information Processing Systems, 2015.
Kush Bhatia, Prateck Jain, Parameswaran Kamalaruban, and Purushottam Kar. Consistent robust regression. In Advances in Neural Information Processing Systems, 2017.
Giuseppe C Calafiore and Laurent EI Ghaoui. Optimization Models. Cambridge University Press, 2014.
Haw-Shiuan Chang, Erik Searned-Milles and Andrew McCallum. Active bias: Training more accurate neural networks by emphasizing high variance samples. In Advances in Neural Information Processing Systems, 2017.
Nadav Cohen and Amnon Shashua. Simnets: A generalization of convolutional networks. arXiv preprint arXiv: 1410.004,, 2014.
Nadav Cohen, Or Sharir, and Amnon Shashua. Deep simnets. In Conference on Computer Vision and Pattern Recognition, 2016.
A. Dembo and O. Zeitouni. Large deviations techniques and applications. Springer Science & Business Media, 2009.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: robust meta-algorithm for stochastic optimization. In International Conference on Machine Learning, 2019.
Michele Donini, Luca Oneto, Shai Ben-David, John Shawe-Tayy Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. In Advances in Neural Information Processing Systems, 2018.
D Dua and C Graff. UCI machine learning repository [http://archive. ics. uci. edu/ml]. https://archive. ics. uci. edu/ml/datsees. 2019.
Marco Duarte and Yu Hen Hu. Vehicle classification in distributed sensor networks. Journal of Parallel and Distributed Computing. 2004.
Jinyang Gao, HV Jagadish, and Beng Chin Ooi. Active sampler: Light-weight accelcrator for complex data analytics at scale. arXiv preprint urXiv:1512.03550 2015.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online stochastic gradient for tensor decomposition. In Conference on Learning Theory, 2015.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, 2016.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographies in repeated loss minimization. In International Conference on Machine Learning, 2018.
Dan Hendrycks, Mantas Mazeika, Duncan Wilson, and Kevin Gimpel. Using trusted data to train deep networks on labels corrupted by severe noise. In Advances in Neural Information Processing Systems, 2018.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding. 1994.
Matthew Holland and Kazushi Ikeda. Better generalization with less data using robust gradient descent. In International Conference on Machine Learning, 2019.
10

---

Published as a conference paper at ICLR 2021
Ronald A Howard and James E Matheson. Risk-sensitive markov decision processes. Management science, 1972.
Peter J Huber. Robust estimation of location parameter. The Annals of Mathematical Staristics, 1964.
Angela H Jiang, Daniel L-K Wong, Giulio Zhou, David G Andersen, Jeffrey Dean, Gregory R Ganger, Gauri Joshi, Michael Kaminksy, Michael Kozuch, Zachary C Lipton, al. Accelerating deep learning by focusing on the biggest losers. arXiv preprint
2019.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. MentorNet: Learning data-driven curriculum for very deep neural networks on corrupted labels. In International Conference Machine Learning, 2018.
Chi Jin, Rong Ge, Pranecth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference Machine Learning, 2017.
Chi Jin, Pranceth Netrapalli, and Michael Jordan. What is local optimality in noncomvex-nonncomaav minimax optimization? In International Conference on Machine Learning, 2020.
Mohammad Mahdi Kamani, Farzin Haddadpour, Rana Forsati, and Mehrdad Mahdavi. Efficient fair principal 2019.
component analysis. arXiv preprint arXiv:1911.044
Hamed Karimi, Julie Nutini, and Mark Schmidt, Linear convergence of gradient and proximal mookial--gradeent methods under the volyak-tojasiewicz condition. In Joint European Conference Machine Learning and Knowledge Discovery in Databoses, 2016.
Angelos Katharopoulos and François Fleuret. Biased importance sampling for deep neural network training.
arXiv preprint arXiv:/706. 706.00043. 2017.
Ashish Khetan, Zachary C Lipton, and Anima Anandkumar. Learning from noisy singly-labeled data. In International Conference on Learning Representations, 2018
Barry W Kort and Dimitri P Bertsekas, A new penalty function method for constrained minimization. In IEEE Conference on Decision and Control and 11hh Symposium on Adaptive Processes, 1972
Alex Krizhevsky, Geoffrry Hinton, et al. Learning multiple layers of features from tiny images. 2009.
M Pawan Kumar, Benjamin Packer, and Daphne Koller, Belf-paced learning for latent variable models. In Advances in Neural Information Processing Systems, 2010.
Yassine Laguel. Krishna Pillutla. Jérôme Malick, and Zaid Harchaoui. A superquantile approach for federated learning with heterogeneous devices. In Annual Conference on Information Sciences and Systems, 2021.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998.
Liu Leqi, Adarsh Prasad, and Pradcep K Ravikumar, On human-aligned risk minimization. In Advances Neural Information Processing Systems, 2019.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEFE Signal Processing Magazine, 2020a.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations, 2020b.
Tsung-Yl Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In International Conference on Computer Vision, 2017.
Tomasz Malisiewicz, Abhinav Gupta, and Alexei A Efros. Ensemble of exemplar-SVMs for object detection and beyond. In International Conference on Computer Vision, 2011.
Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms gradient descent. Advances Neural Information Processing Systems, 1999.
Andreas Maurer and Massimiliano Pontil. Empirical bermstein bounds and sample variance penalization. arXiv preprint arXiv:0907. .3740, 2009.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agúera Arcas. Communication- efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statisties, 2017.
11

---

Published as a conference paper at ICLR 2021
Aditya Krishna Menon, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Can gradient clipping mitigate label noise? In International Conference on Learning Representations, 2020.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, 2019.
Bhaskar Mukhoty, Govind Gopakumar, Prateek Jain, and Purushottam Kar. Globally-converger iteratively reweighted least squares for robust regression problems. In International Conference on Artificial Intelligence and Statistics, 2019.
Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. In Advances in Neural Information Processing Systems, 2017.
David Nass, B. Belousov, and Jan Peters. Entropic risk measure in policy search. International Conference on Intelligent Robots and Systems, 2019.
Maher Nouiehed, Jong-Shi Pang, and Meisam Razaviyayn. On the pervasiveness of difference-convexityy in optimization and statistics. Mathematical Programming, 2019a.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee. and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. In Advances Neural Information Processing Systems, 2019b.
Ivan Olier, Noureddin Sadawi, G Richard Bickerton, Joaquin Vanschoren, Crina Grosan, Larisa Soldatova, and Ross D King. Meta-qsar: large-scale application of meta-Icaming drug design and discovery. Machine Learning, 2018.
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex-coneave smooth min-max problems. arXiv preprint arXiv:2002.0791 2020.
R Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 1997.
EY Pee and Johannes O Royset. On solving large-scale finite minimax problems using exponential smoothing. Journal of Optimization Theory and Applications, 201
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International Conference Machine Learning, 2018.
Ashkan Rezaei, Rizal Fathony, Omid Memarrast, and Brian D Ziebart. Fairness for robust log loss classification. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
R Tymell Rockafellar and Stanislav Uryasev. Conditional value-at-risk for general loss distributions. Journal of Banking & Finance, 2002.
R Tyrelll Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at risk. Journal risk, 2000.
Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh. Fr-train: A mutual information-based approach to fair and robust training. International Conference on Machine Learning, 2020.
Thorsteinn Rögnvaldsson. https://rrcive.. iis..ic..i........... htw.d//wwwlaataeaee//ot/teeeeeee
UCI repository of machine learning
datahases.
2013.
Samira Samadi, Uthaipon Tantipongpipat, Jamie H Morgenstem, Mohit Singh, and Santosh Vempala. The price of fair PCA: One extra dimension. In Advances Neural Information Processing Systems, 2018.
Chunhua Shen and Hanxi Li. On the dual formulation of boosting algorithms. IEEE Transactions Pattern Analysis and Machine Intelligence, 2010.
Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region-based object detectors with online hard example mining. In Conference Computer Vision and Pattern Recognition, 2016.
Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng. Meta-weight-net, Learning an explicit mapping for sample weighting. In Advances Neural Information Processing Systems, 2019.
Aman Sinha, Hongscok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018
Ivan Stelmakh, Nihar B Shah, and Aarti Singh. Peerreview4all:: Fair and accurate reviewer assignment in peer review. In Algorithmic Learning Theory, 2019.
12

---

Published as a conference paper at ICLR 2021
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Conference on Computer Vision and Pattern Recognition, 2016.
Uthaipon Tantipongpipat, Samira Samadi, Mohit Singh, Jamie H Morgenstern, and Santosh Vempala. Multi- criteria dimensionality reduction with applications to fairnsss. Advances in Neural Information Processing Systems, 2019.
Andreas Veit, Neil Alldrin, Gal Chechik, Ivan Krasin, Abhinav Gupta, and Serge Belongie. Learning from noisy large-scale datasets with minimal supervision. In Conference on Computer Vision and Pattern Recognition, 2017.
Riccardo Volpi, Hongscok Namkoong, Ozan Sener, John C Duchi, Vittorio Murino, and Silvio Savarese. Generalizing to unseen domains via adversarial data augmentation. In Advances in Neural Information Processing Systems, 2018.
Martin J Wainwright and Michael I Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 2008.
Martin Wainwright, Tommi S Jaakkola, and Alan S Willsky, A new class of upper bounds on the log partition function. IEEE Transactions on Information Theory, 2005.
Xueqin Wang. Yunlu Jiang, Mian Huang, and Heping Zhang. Robust variable selection with exponential squared loss. Journal of the American Statistical Association, 2013.
Zhiguang Wang, Tim Oates, and James Lo. Adaptive normalized risk-averting training for deep neural networks. In AAAI Conference on Artificial Intelligence, 2016.
Hermann Weyl. Das asymptotische verteilungsgesetz der cigenwerte lincarer partieller differeentalgleichungen (mit einer anwendung auf die thcoric der hohiraumstrahlung) Mathematische Annalen, 1912.
Min Yang. Linli Xu, Martha White, Dale Schuurmans, and Yao-liang Yu. Relaxed clipping: A global training method for robust regression and classification. In Advances in Neural Information Processing Systems, 2010.
I-Cheng Yeh and Che- Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 2009.
Yao-liang Yu, Özlem Aslan, and Dale Schuurmans. A polynomial-time time form of robust regression. In Advances in Neural Information Processing Systems, 2012.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fairesss beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In Conference on World Wide Web, 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Representations, 2017.
Zhilu Zhang and Mert Sabuneu. Generalized cross entropy loss for training deep neural networks with noisy labels. Advances in Neural Information Processing Systems, 2018
13

---

Published as a conference paper at ICLR 2021
APPENDIX
In this appendix we provide full statements and proofs of the analyses presented in Section (Appendix --) details on the methods we propose for solving TERM (Appendix H): complete
empirical results and details of our empirical setup (Appendix J. and discussion on the broader impacts (both positive and negative) of TERM and the research herein (Appendix K).
We provide
table of contents below for easier navigation.
CONTENTS
A Notation & Assumptions
15
Basic Properties of the TERM Objective
16
Hierarchical Multi-Ohjective Tilting
19
General Properties of the Objective for GLMs
21
General Properties of TERM Solutions for GLMs
23
Connections Between TERM and Exponential Tilting
30
TERM as an Approximate Superquantile Method
31
Algorithms for Solving TERM
34
H.I
Convergence with
35
Additional Experiments
37
I.1 Experiments to showcase properties of TERM
37
Complete case studies
38
J
Experimental Details
J.1 Datasets and models
42
J.2 Hyperparameters
42
Discussion
44
14

---

Published as a conference paper at ICLR 2021
A NOTATION & ASSUMPTIONS
In this section, we provide the notation and the assumptions that are used throughout our theoretical analyses.
The results in this paper are derived under one of the following four assumptions:
Assumption (Smoothness condition). We assume that for e [M] loss function f 0) is in differentiabiliity class C' (i.e., continuously differentiable with respect E θ IR
Assumption (Strong convexity condition). We assume that Assumption iis satisfied. In addition, we assume that for any i E [N]. (1,;; 0) is in differentiability class C² (i.e., twice differentiable with continuous Hessian) with respect
We further assume that there exist 8min Brax RR+ such that for E [N] and any 0 E θ = RR.
Buin
V V0001(1;;00
Smax
(5)
where I the identity matrix of appropriate size (in this case d d). We further assume that there does not exist any 0 E θ such that Vol 0) = 0 for all i [N].
Assumption 3 (Generalized linear model condition (Wainwright & Jordan 2008)). We assume that Assumption satisfied. We further assume that the loss function [(x;;) is given by
[(x; 0) A
(6)
where A()) is convex such that there exists Buax such that for any f θ RR.
8min 3 Vi0 A(0) = SmaxI.
We also assume that
Σ T(x:)T(I:) > O. SE[N]
(8)
This nest set of assumptions become the most restrictive with Assumption which essentially requires that the loss be the negative log-likelihood of exponential family. While the assumption is stated using the natural parameter of exponential family for ease of presentation, the results hold for a bijective and smooth reparameterization of the exponential family. Assumption 3s satisfied by the commonly used Le loss for regression and logistic loss for classification (see toy examples (b) and (c) in Figure D. While the assumption is not satisfied when
neural network function approximators Section 5.1 we observe favorable numerical results motivating the extension of these results beyond the cases that theoretically studied in this paper.
In the sequel, many of the results are concerned with characterizing the t-tilted solutions defined as the parametric set of solutions of (-tiled losses by sweeping / R,
((t) arg min R(t: 0), bee
where θ = Idd is an open subset of Rd We state assumption on this set below.
Assumption 4 (Strict saddle property (Definition 4 in (Ge et al., 2015)). We assume that the set arg mingen R((:; 0) is non-ene non-empty for all t E R. Further, we assume that for all e TR R((:; 0) is "strict saddle" as a function 0, for all local minima, Vig Re(1; 0) 00, for all other stationary 08 R(t; 0)) < 0, where Xmin() )) is the minimum eigenvalue of the matrix.
solutions, Amin 2
We use the strict saddle property in order to reason about the properties of the f-tilted solutions. In particular, since we are solely interested in the local minima of R(t: 0), the strict saddle property implies that for every 0(t) arg mingee R(t: f), for sufficiently small r. for all A e B()(t),
V R(t: 8) > O.
(10)
where B((()),)) denotes a d-ball of radius r around O(1)-
We will show later that the strict saddle property is readily verified for L IR+ under Assumption
15

---

Published as a conference paper at ICLR 2021
B BASIC PROPERTIES OF THE TERM OBJECTIVE
In this section, we provide the basic properties of the TERM objective.
Proof of Lemma Lemma which provides the gradient of the tilted objective, has been studied previously in the context of exponential smoothing (see (Pee & Royset, [201]] Proposition 2.1)). We
provide brief derivation here under Assumption for completeness. We have:
vol((1;0) Va
log
Σ iE|N
(11)
EielNT Vol ( Eie(n] ets(a
(12)
Lemma 2. Under Assumption
R(-00;0) == lim R(t:0) R(()).
(13)
R(0; 0) := lim R(t;0) = R(00) (-U
(14)
R(+00; 0)= == lim R(I: P((O),
(15)
+++0
where f((0)) is the max-loss and R(0) is the min-loss
R(()) == max f(x;;)). [c[N]
R(0) = min f(z;;)) 0).
(16)
a[[N]
Proof. For t - 0,
lim R(t 0) lim log Σ (((;)))) -
[E[N]
Ene[ fzx (())))))0))
lim
(17)
EieNy e!f(x10)
Σ f(a;0).
(18)
[N
where 17 due to L'Hôpital's rule applied to t as the denominator and log ( Eiesy e( the numerator.
For 000 we proceed as follows:
lim R(t: 0) = lim 1--000
log
Σ
60-0 3 t
N
ie[M]
> lim
log
1
Σ
4 [iin f(zy:0)
(19)
t 80
N
iE[N]
min f(x;; 0).
(20)
[N[N]
'When the argument of the max-loss the min-loss is unique, for the purpose of differentiating the loss function, we define R(0) the average of the individual losses that achieve the maximum, and R(()) as the average of the individual losses that achieve the minimum.
16

---

Published as a conference paper at ICLR 2021
On the other hand,
lim R(t;0)= = lim
log
Σ e elf(a))))
---o0 I
N
lim log
e minje(() f(13)0)
(21)
(- 00 t
N
min (zz;;)
lim
NogNN
log N
(22)
ie[N]
6--50
min fzx;;))
(23)
Ke[N]
Hence, the proof follows by putting together
20 and
The proof proceeds similarly to t -00 for t and is omitted for brevity.
Note that Lemma 2 has been previously observed in (Cohen & Shashua 2014). This lemma also implies that 0(0) is the ERM solution, 0(++oo) is the min-max solution, and 0(-o0) is the min-min solution.
Lemma (Tilted Hessian and strong convexity for L R+). Under Assumption 2 for any / E R,
V2 G0T R(t;0) = Σ
(Vef(x;;)) Voli(t:0)(Vof(a;.)) V T ()(()))))) R(t:0))
iE[N]
(24)
Σ
oor f1:;; -)
(25)
[E[N]
In particular, for all A E and all 1. E RC+, the t-tilted objective is strongly corvex. That is
Vigr R(t: > IminI.
(26)
Proof. Recall that
LieM [M] Vof (f
voR(t;
(27)
EieLN e(f(z())
Σ
Vol ((xs))
(28)
The proof of the first part is completed by differentiating again with respect to 6, followed by algebraic manipulation. To prove the second part, notice that the term in (24 is positive semi-definite, whereas the term in 25 is positive definite and lower bounded by Buin I (see Assumption 2 Eq.
Lemma (Smoothness of R(t; 8) in the vicinity of the final solution ((t)). For any t R. let B(t) be the smoothness parameter in the vicinity of the final solution:
B(t) = sup
Xmax ((tt((tt))))
(29)
(eB((()).r)
where 2 R(t: 8) is the Hessian of Ri(t: f) at 0, )max(.) denotes the largest eigenvalue, and B( r) denotes a d-ball of radius r around 0. Under Assumption function of f. Further, for t E RR,, at the vicinity of i(t).
2 for any R. R(t; 0) is a -moothh
B(t) < 3maxi
(30)
anrfoor IR*
3(t)
lim
+00.
(31)
17

---

Published as a conference paper at ICLR 2021
Proof. Let us first provide proof for t R Invokinn Lemma 3 and Weyl's inequality (Weyl 1912), we have
Amax
(oer R(t:0)
Amax
Σ
(Vof(zn0)-
(o - VoR(t: ()) ( R((:0))
[E[N]
(32)
+ Amax
Σ KE[N]
Voo fax;; (f(=))) R((:0))
(33)
Bmaxx
(34)
where we have used the fact that the term in 24 is negative semi-definite for / < 0, and that the term (25) is positive definite for all with smoothness bounded by Binx (see Assumption Eq.
For e R following Lemma and Weyl's inequality (Weyl 1912), we have
+
Amax (Voo- R(1:))
Amax
Σ
(of(2;;)) v.R(t:0) voR(t: e((((=(0)-R(1000)
(
EENN]
(35)
(1) Amax
f(x;; 0(:
(36)
[
Consequently,
lim
Amax Vooo R((:: R(( +00.
(37)
On the other hand, following Weyl's inequality (Weyl 1912).
Amax (vào- R((t; 0))
3 DAmax
(Vo((z;;) 0) Vo VoR((:)))(Vo/(<: - voN((t: OT ((((())))) T -((:00)) M=[M]
Σ
(38)
and hence,
()) Xmmas (V) R(::R(t:))) 8)) > 0,
lim 60000
(39)
where we have used the fact that no solution 0 exists that would make all fi's vanish (Assumption
Under the strict saddle property (Assumption 4p. it known that gradient-basse methods would con- verge to a local minimum (Ge al. 2015), i.c., O(t) would be obtained using gradient descent (GD).
The rate of convergence of GD scales linearly with the smoothness parameter of the optimization landscape, which characterized by Lemma
Lemma (Strong convexity of R(t: 8) in R R+). Under Assumption 2 for any e R. R(t; 0) is
strongly convex function of 0. That is for lE Rt,
V2ga R(1:0) I.
(40)
Proof. The result follows by invoking Lemma with R+, and considering (5)
(Assumption
This lemma also implics that under Assumption 2 the strict saddle assumption (Assumption is readily verified.
18

---

Published as a conference paper at ICLR 2021
C HIERARCHICAL MULTI-OBJECTIVE TILTING
We start by stating the hierarchical multi-objective tilting for hierarchy of depth 3. While we don't t directly use this form, is stated to clarify the experiments in Section 5 where tilting is done at class level and annotator level, and the sample-level tilt value could be understood to be 0.
t;; log
l
emJa(r:0)
(41)
N
Ge[GG]
gE[G]
Jo(l,T;0)== = log
1
R
(42)
Eye[on lg|
gE[G]
(T: log
1
e (x:00)
(43)
meg
Next, we continue by evaluating the gradient of the hierarchical multi-ohjective tilt for hierarchy of depth 2.
Lemma (Hicrarchical oulti-objective tilted gradient). Under Assumption
VoJ(t,T;)) = Σ Σ
T: (1
(44)
oe [c]] wEg
where
[ol Even eTf(x:0)) (1-1)
(45)
Eyee(a lo'l
Too E elvoe))
Proof. We proceed follows. First notice that by invoking Lemma
voJ(1,;;0)) Σ
wg(4, (),,;;))v (o
(46)
gE|G|
where
Igle (T
Wg(t, 0)
(47)
Eg'etcy Ig (
where (T; is defined in (4), and is reproduced here:
(
Rg(T; 0) = T
1 log
Σ eT((=0))
(48)
[g|
zEg
On the other hand, by invoking Lemmal
VeRg(T:
Σ Wg.a Vo)((2;
(49)
where
e {xx:0)
Wg. (T:
(50)
Σ Tyy eTi(u:0)
Hence, combining (46) and 49).
[t, = Σ
r; (1
(51)
gE[G] DEg
The proof is completed by algebraic manipulations to show that
Wg (t, 0) wo (t, r: 0 a 0).
(52)
19

---

Published as a conference paper at ICLR 2021
Lemma 7 (Sample-level TERM is special case of hierarchical multi-objective TERM). Under Assumption ! hierarchical multi obbectvveeeeivee TERM recovers TERM as a special case for t = т. That is
t1, 1; R)(
(53)
Proof. The proof is completed by noticing that setting in 45 (Lemma 6
recovers the original
sample-level tilted gradient.
20

---

Published as a conference paper at ICLR 2021
D GENERAL PROPERTIES OF THE OBJECTIVE FOR GLMS
In this section, even if not explicitly stated, all results are derived under Assumption B with generalized linear model and loss function of the form (6), effectivvely assuming that the loss function the negative log-likelihood of an exponential family (Wainwright & Jordan 2008).
Definition (Empirical cumulant generating function). Let
A(t; 0) Lf((1;
(54)
Definition (Empirical oog-pariiionn function Wainwwriht et al. 2005)).
Let l(t: 0) be
-00 T(a.)
0(t:0) log
(55)
dc[M]
Thus, we have
R(::0) A(0) + { log
Σ [E[N]
10 T(z))
= A(0) T1:
(56)
Definition 3 (Empirical mean and empirical variance of the sufficient statistic). Let M and V denote the mean and the variance of the sufficient statistic, and be given by
M(t:0)
Σ
T(x:)e 18 T(a))))((())
(57)
ie[N]
V(t:0) = N
Σ (T(x:) -
- M(t:0)) ((0=0)))-0000
(58)
[E[M]
Lemma 8. For all t E R, we have V(t: 0) > 0.
Next we state few key relationships that we will use in our characterizations. The proofs are straightforward and omitted for brevity.
Lemma (Partial derivatives l'). For all t E R and all 0 θ,
r(t:0) = -0- M(;t0), δ1
_
(59)
Vo[(t:0) = -IM(I:: 0)-
(60)
Lemma 10 (Partial derivatives of M). For all E R and all 0 E O
6 àt
M(t: 0) ();
(61)
vaM(1:0) -IV(1:0).
(62)
The next few lemmas characterize the partial derivatives of the cumulant generating function. Lemma 11. (Derivative of A with t) For all t IR and all O,
A(: A(O) 0 M(1:0).
(63)
π1
Proof. The proof is carried out by
A(t:0) A(0) T Σ T(z:)e-10 ( -(ee)--)- T(a))- A(O) TJ M(t:0).
(64)
NE[N]
Lemma 12 (Second derivative of A with t). For all e R and all 0 O
A(t;0) = ((t
(65)
0+2
21

---

Published as a conference paper at ICLR 2021
Lemma 13 (Gradient of A with 0). For all t E R and all 0 O
VoA(t; 0) = (0) - O)
(66)
Lemma 14 (Hessian of with 8). For all t E R and all 8 E θ,
Vo ((; VV 00 A()) + ();
(67)
Lemma 15 (Gradient of A with respect to and 0). For all t R and all 0 θ
i VoA(t;0)- - VoA(0) M)t;0) + (1( 0)0.
(68)
22

---

Published as a conference paper at ICLR 2021
E GENERAL PROPERTIES OF TERM SOLUTIONS FOR GLMS
Next, we characterize some of the general properties of the solutions of TERM objectives. Note that these properties are established under Assumptions and Lemma 16. For all IR.
VeA(t; O.
(69)
Proof.
The proof follows from definition and the assumption that is an open set.
Lemma 17. For all R.
Voa((((t) = ((t)
(70)
Proof.
The proof completed by noting Lemma and Lemma
Lemma 18 (Derivative of the solution with respect to tilt). Under Assumption 4 for all t R,
ōt (()) = - (V2o- A(0(1) + (((;((1))) " V();(())(())
(71)
where
2o A(O(1)) + (V((;(()) > O.
(72)
Proof. By noting Lemma
16 and further differentiating with respect to t, have
(oA(t;((1)
(73)
ōt
6 VoA(T;
A(;
ot ((t))
(74)
δT
=V((;(())(()) (IV A(O) 12
( o(())
(75)
where 74 follows from the chain rule, 75 follows from Lemmas 15 and 17 and 14
The proof is
completed by noting that Vor ((t)) 0 for all t E IR under Assumption
Finally, we state an auxiliary lemma that will be used in the proof of the main theorem.
Lemma 19. For all t, R and all E θ,
M(T:0) M(t:0) -- (s. (vvv:ojdu) 0.
(76)
Proof. The proof is completed by noting that
M(T: -M(t;) = S. à ōv Mir - -(. v(ri))du) 0.
(77)
Theorem 1. Under Assumption 3 and Assumption
for any t, T R
(a) [)()((()) iff't <;; (b) & (((T(((())
0 Off T; (c) R((;((()) 0
23

---

Published as a conference paper at ICLR 2021
Proof. The proof proceeds as follows. Notice that
R(t (it;)(Tr)) _ t (2)81)) VoA(t;&(T))
(78)
-- (Vor +(((:(())))
-V(A((t))-
(79)
--)(((() (V A(((T)) + +
- -M({(T7))
(80)
(T)))) ((a(T(((()) + +V;(; (.. v(u: (():((())))) ((T).
(81)
where (78) follows from the chain rule and 54
follows from Lemma 18 and Lemma
3
80)
follows from Lemma 17 and (8T) follows from Lemma 19 Now notice that invoking Lemma
and
noticing that following the strict saddle property
NOT R((:; 0) (n-d(r)
= VoST A(((T)) + +~((T;0(T)) > 0,
(82)
we have
(a) St (vv:((r)ddu < < T:
(b) St V(: iff
(c) & dz
which completes the proof.
Theorem (Average- vs. max-loss tradeoff), Under Assumption and Assumption for any
t R
2 A(((t)) <0,
(83)
ot
à
R(((1)) 20. O.
(84)
Proof of Theorem
To prove
83
first notice that from Lemma
R((0) lim R)t: +-+
(85)
Now, invoking Theorem (Appendix Dp. for any 7, R+ such that
R(t: <0.
(86)
In particular, by taking the limit as t00,
lim
((t; < 0.
(87)
6++7 δT
24

---

Published as a conference paper at ICLR 2021
Notice that
à R((:;(T))
((((T) (o
0 > lim +0+ ōT
lim
(88)
+00
((7)
lim r--
vo
(89)
δ
((1))
vol((((T))
(90)
δr
a R(((T))
(91)
where (90) holds because V R(t (())) is finite weighted sum of the gradients of the individual losses with weights bounded in [o, 11, per Lemma completing the proof of the first part.
To prove (4), notice that by Lemma 2]
R((0) = lim R(t:0). t00
(92)
Now, invoking Theorem
(Appendix Dp. for any T, e g+ such that 7 >
ā R((; 0.
(93)
In partieular, by taking the limit 0,
a ((((T)
ē R((1;(17) > 0,
lim 0 Ōt
(94)
completing the proof.
Theorem 3 (Average- vs. min-loss tradeoff). Under Assumption and Assumption 4 for any & E TR.
à R(((())) > 0. R(Ō(t)) <
(95)
ōt
(96)
ōt
Proof of Thheormm
To prove
95
first notice that from Lemma 2
R((0) lim O)(
(97)
Now, invoking Theorem
1
(Appendix Dj. for any T, / R+ such that
ā
R(t: (()) > o. ōt
(98)
In particular, by taking the limit as -00,
R(((T))
lim
à ki; ((T)) > 0,
(99)
to
completing the proof of the first part.
To prove (96), notice that by Lemma
R(0) lim (((::):
(100)
z00
Now, invoking Theorem 1 (Appendix
D3. for any 7, I E R+ such that
ā
R(t: ((T)) <0
(101)
In particular, by taking the limit as - 0,
a
((((T))
= lim R((:: < 0,
(102)
- ōπ
completing the proof.
n
25

---

Published as a conference paper at ICLR 2021
Theorem is concerned with characterizing the impact that TERM solutions for different t R have on the objective R(T; ((t) for some fixed R. Recall that -co recovers the min-loss, the average-loss, and T = +00 is the max-loss. By definition, if ( = T, 0(T) the minimizer of R(;; ((t)). Theorem shows that for E (-)0, the objective is decreasing; while for t E (T, +00 the objective increasing. Recall that for any fixed r R, R((T; 0) is also related to the k-th smallest loss of the population (Appendix G Hence, the solution O(t) is approximately minimizing the k(t)-th smallest loss where k(t)) is increasing from 1 to N by sweeping in (-00, +00).
Theorem (Variance reduction). Ler f(0) =- [f((=1))) .......... (.( [(NN; 0)). For any E R. ler
mean(u) u) ==
1
Σ [
U4
var(u) == N
Σ (us mean (u))² iE[N]
(103)
Then, under Assumption 3 and Assumptioo
for any LE R,
var(((o(U)) <0. σ2
(104)
Proof. Recall that f(x;;0) A(0) - A Txx:). Thus,
mean(f)
Σ
M( A(O)
1 0 NOT
Σ T(x:) A(O) - MM000) 0) NE[N]
(105)
N
[E[N]
Consequently,
2
1 var(f(0)) N
Σ
f(x;0))
1 Σ
f(zzi0)
(106)
N
JE[N
Σ
(TT()))
T Σ T(x;) N
(107)
N
ic[M]
jc[M]
Σ (T(x;) Σ ((x)))(((N)) - Σ T(x)))
(108)
N
(E[M]
J=[N]
JE[N]
A VuB,
(109)
where
Vo = -[0000 = N
Σ (T(x))
Σ T(x)))(((a))
N Σ T(
(110)
N
ic[M]
jc[M]
je[N]
Hence,
2 δr (var((((())))
( 0 (2)67))
Vo (vr(f()(t))))
(111)
T
((()) Voū(7)
= 2 oT
(112)
--20 -2 (T) + Vo0(())
(113)
0,
(114)
completing the proof.
Theorem 5 (Cosine similarity of the loss vector and the all-ones vector increases with t). For
u, V E R. let cosine similarity be defined
u1 v
s(u, ==
(115)
26

---

Published as a conference paper at ICLR 2021
Let f(0) := (x(11; 0)) f(zn: 8)) and let 1N denote the all-1 vector of length N. Then, under Assumption 3 and Assumption 4 for any t E R.
ā δt (s(((((t)..M)) 0.
(116)
Proof. Notice that
(E((0)1N]] = NV MIaNN f(x;0) 0) V EiELN (2
(117)
Let Mo == M)0 and Vo == V(O;0). 0). Hence,
1
Σ f(z;;0) = A((0) - - TMo.
(118)
N
[c[N]
1
Σ ( 0) (A(0) 0 OoM2)² 0 V00
(119)
N
Notice that
LIE[N Max;
V8 (s = Vo
(120)
N ENEIN| 12 (2 0)
(A(0) 8T MMM)
V
(121)
(A(0) - TT Mo)2 + 0 VoB
2(A(0) - 0 (MMMo - -Mo)0 - -0)))())00M)))>))
((A(0) - Mb)² + +O02
(122)
2(A(0) - OT Mo) (V=(V)A(0) MM) - A(0) (MM)) Vo0
(123)
((A(0) - BT Mo) + VT))))
= 2(A(0)-O) - -TTMM) (o)vo)())) A(O)) V00
(124)
((A(0) - Mo)² + VDO)²
= 2(A(0) (TM) Vi.
(125)
((A(0) - AT Mo) AT V
Hence,
(2)))))) Vo (3(((()))
(F((()))
(126)
(+))((())()7)) (V2))(((T)) + +V(T;
2(A(((T)) (())
((A(()))) -(+))) 7 VoO(()
(127)
0,
(128)
completing the proof.
Theorem 6 (Gradient weights become more uniform by increasing (). Under Assumption Assumption 4 for any T, L E IR,
and
2
((((T: > 0,
(129)
where H()) denotes the Shannon entropy functtio measured in nats,
(w((t: 0)) : Σ
w.(t; f) log (t:
(130)
[
27

---

Published as a conference paper at ICLR 2021
Proof. Notice that
H (w([:))) = Σ
wi(t; 0) wo:
wi(t;
(131)
iE|Ni
Σ (tf(2;)) -(:::))e
(132)
iE[N]
A(t; 0) t Σ f(x;; ((0
(133)
iE|N]
A((40) - LA(O) + 10 M(I:0).
(134)
Thus.
VOH (w():)) = Vo (A(t; tA(o) + to M(t:0))
(135)
(VA((0) - (M (Vo((O) +M(t;)) +
(136)
-1)
(137)
Hence,
δr H (w(t:((r))
oJ (2-06T) VoH (w(t:8(7))
(138)
Vo (A(t; +A(0) t0 M(t(())))
(139)
eO (+)(((()()) +((;;(()))++ ((t;(())))(T)
(140)
> 0,
(141)
completing the proof.
L
Theorem 7 (Tilted objective increasing with (). Under Assumption 3 for all IR, and all 0 O
R(t; 0) 2 O.
(142)
02
Proof. Following (56).
a
R(t:0)
ōt 1 i
[
(143)
1
1
t2 r(t;0)
M(t;0),
(144)
t.
=: ();
(145)
where (144) follows from Lemma and (45) defines
g(1;
Let g(0; 0) = lim,- g( 0) Notice that
t M
g(0; 0) lim
l(t: 0)
(146)
(-0
12
TTt: T M(t:0)
lim t-0
(147)
0 V'0
(148)
where (148) is due to L'Hôpital's rule and Lemma 12 Now consider
δe (Po(t:0))
à
21 (-r(t: 10T t0 M(t:0]
(149)
M(t:0)
(150)
- MMt 0) + +10 v
(151)
t0 v(t;
(152)
28

---

Published as a conference paper at ICLR 2021
where g(: ět R(t 8). (150) follows from Lemma 9
(151) follows from the chain rule and Lemma 10 Hence, (g 0) is increasing function of for e Rt, and decreasing function of for E IR taking its minimum at t = 0. Hence, gt 0) > 0 for all t E R. This implies that g(t; > 0 for all t e R which in conjunction with (145) implies the statement of the theorem. L
Definition 4 (Optimal tilted objective). Let the optimal tilted objective be defined as
F(t) (()).
(153)
Theorem 8 (Optimal tilted objective is increasing with t). Under Assumption 3 for all t R, and all E θ
ēt (t) R(; ((t) > 0.
(154)
ōt
Proof. Notice that for all 0, and all R
R( + E; e; > R(I;;))
(155)
i[: ((1))
(156)
where 1155) follows from Theorem and 156 follows from the definition of o((). Hence,
i((1 0(1 + e))
min (eB(r()).)
i(( c; R((1;(()),
(157)
which completes the proof.
29

---

Published as a conference paper at ICLR 2021
F CONNECTIONS BETWEEN TERM AND EXPONENTIAL TILTING
Here we provide connections between TERM and exponential tilting, a concept previously explored in the context of importance sampling and the theory of large deviations (Beirami al. 2018 Dembo & Zeitouni, 2009; Wainwright et al. 2005). To do so, suppose that X is drawn from distribution p() Let us study the distribution of random variable
f( Let Ay (t) be the cumulant generating function (Dembo & Zeitouni] 2009) Sectiom 2.2). That is
(t) = log (Fp (e
(158)
= log EEp { (
(159)
Now, suppose that IIN...,IN are drawn ii.d. from p(.). Note that this distributional assumption is made solely for providing intuition on the tilted objectives and is not needed in any of the proofs in this paper. Hence, R[( 0) can be viewed as an empirical approximation to the cumulant generating function:
(y 0)
(160)
Hence, (t( 0) provides approximate characterization of the distribution of f(X; 0). Thus, mini- mizing R(t: is approximately equivalent to minimizing the complementary cumulative distribution function (CDF) of ((X;0) 0). In other words, this is equivalent to minimizing P(J(X;0) > a} for some a, which is function of
In the next section, we will explore these connections with tail probabilities dropping the distributional assumptions, effectively drawing connections between superquantile methods and TERM.
30

---

Published as a conference paper at ICLR 2021
G TERM AS AN APPROXIMATE SUPERQUANTILE METHOD
For all a E R, let Q(a; 0) denote the quantile of the losses that are no smaller than a, i.c.
Q(a 0) = N 1E
Σ 1(f(2;0) > at,
(161)
where [[-} is the indicator function. Notice that Q(a; {0, N..... 1} quantifies the fraction of the data for which loss is at least a. In this section, we further assume that is such that f(z;; 0) > for all 0.
Suppose that we are interested choosing in a way that for a given a E I,, we minimize the fraction of the losses that are larger than That is
(a) min (a 0) Q(a; (a)),
(162)
where
(a) arg min Q(a; 0).
(163)
This is non-smooth non-convex problem and solving it to global optimality is very challenging. In this section, we argue that TERM provides a reasonable approximate solution to this problem, which is computationally feasible.
Notice that we have the following simple relation:
Lemma 20. If a < F(-xo) ) then (a) 1. Further, if >> F(+ then ()(a) = 0, where F())
defined in Definition and reproduced here:
F(-oo)= lim R(t; 0()) min min f(z;;)) 0), ie[N]
(164)
A(t ((t;)(t)) = min max f(z;;)) 0). F(+0)) = lim b+*
(165)
0 *e[N]
Next, we present our main result on the connection between the superquantile method and TERM.
Theorem 9. For all t E IR, and all 0, and all E (F(-o0), o(+ P
R(t:0) c (-co) ((a;0) (aa;t,0)=
(166)
eat - (-(0)
Proof. We have
(a- (o-P(-20))a] ((2 31
()a;0) E e c(o-F(-a)))-- -
a-P(-10)
(167)
EMEIN (((ax))))((-a)))
(168)
cla-F(- ((x-((
Rindy P(-c))
(169)
eat ef (-00)a
where (167) follows from Lemma 21 168 follows from Lemma 22 the fact that e is strictly increasing (resp. decreasing) for > 0 (resp. < 0) and (e(e-F(-w)) 1) positive (resp. negative) for > 0 (resp. f < 0), and (169) follows from definition.
Lemma 21. For all e R, and all r
1 Q(a:0) N Eiel la (oa-r(-on (( -1
(170)
cla-F(-a))1 -1
WWe define the RHS at f ( via continuous extension.
We define the RHS f ( via continuous extension.
31

---

Published as a conference paper at ICLR 2021
Proof. The proof is completed following this identity:
1 N
Σ
( Q(a: 0) (a F(-20)1 + (1 Q(a; 0)).
(171)
[
Lemma 22. For I 2 O. we have 1(x: 2 1) & x.
Theorem directly leads the following result.
Theorem 10. For all E (F(-o),, F (++o))), we have
F(()) e (F(-))))
(a(a)= $ (a) & (a())) & (²
inf tER
(172)
Eat
(-oo)s
where
(a = inf Q(a: SR
(173)
(a(a) = Q(a;
(174)
(² ((a:Ma),O((l))))
(175)
and
F()t (())))
E(a) == arg inf
(a: B(0)) = arg inf
(176)
teR
teR
-at e
Proof. The only non-trivial step is to show that (?(a)=)()))))))))())) (a). Following Theorem
(a(a) = Q(a; (((()))
(177)
< inf 0(a 1, 0())
(178)
= Qa(a),
(179)
which completes the proof.
Theorem 10 motivates us with the following approximation on the solutions of the superquantile method. Approximation For all e (((-2));(+000)
Q(a;0 = (a) Q²(a) - = Q(a;
(180)
and hence, 8(T(a) is an approximate solution to the superquantile optimization problem.
While we have not characterized how tight this approximation for a E (F(-o0), ((+z))) F(+z)), we believe that Approximation Itttttiooonpppvviio provides a reasonable solution to the superquantile optimization problem general. This is evidenced empirically when the approximation evaluated on the toy examples of Figure 1 and compared with the global solutions of the superquantile method. The results are shown in Figure 6 As can be seen, Q" (a) Q²(a) as suggested by Approximation Also, we can see that while the bound in Theorem 10 not tight, the solution that is obtained from solving it results in
a good approximation to the superquantile optimization.
Finally, we draw connections between these results and the k-loss. Notice that minimizing Q(a; 0) for a fixed a is equivalent to minimizing a for a fixed Q(a; .). If we fix Q(a; 8) = (N - k)/N, minimizing would be equivalent minimizing the k-loss. Formally, let ((x)(0) be the k-th order statiste the loss vector. Hence, R(y the k-th smallest loss, and particularly
( T((0):
(181)
(0) R((
(182)
32

---

Published as a conference paper at ICLR 2021
(a), point estimation
('aa), linear regression
0.20
@*(a)
-1
0.15
Q'(a)
('(a)
(a(
('(a)
(a)
(%(a)
0.95
(a(a)
0.00
04
quantiles 0.8
quantiles
(a) Numerical results showing the bounds Q' (a). and (*(a) for Q²(a) on point estimation example.
(b) Numerical results showing the bounds
Q' (a), Q* @*(a), and (a(a) for @" (a) on the linear
regression example.
Figure (a)a) and (a) are close (a), which indicates that the solution obtained from solving (a) (which is (a)a) is tight approximation of the globally optimal solution of Q" (a).
Thus, for any l [M], we define
R( min (0))
(183)
(k)) == arg min (0)
(184)
Note that
Ri, = F(-00),
(185)
R(N) = F(+00).
(186)
Theorem directly implies the following result: Corollary 11. For all E (2....,N 1}, and all RR
N [l [ & -
(187)
Proof. We proceed by setting ((a; result.
N and (0) in Theorem 9 which implies the N
While the bound left implicit in Corollary I1 we can obtain an explicit bound if we only consider e I (i.e., we are interested in k-losses for larger k):
Corollary 12. For all & e (2...., NN 1), and all te IR+
1
((i(tt0)) -F F(-20))
-
(0) (--00) + log
N
(188)
Proof. The statement follows by algebraic manipulation of Corollary 11
33

---

Published as a conference paper at ICLR 2021
H ALGORITHMS FOR SOLVING TERM
In the main text, we present TERM in the batch setting (Algorithm[]) [ Here we provide the stochastic variants of the solvers in the context of hicrarchical multi-objective tilting (see Eq. (4).
There are a few points to note about stochastic solvers (Algorithm 2):
intractable to compute the exact normalization weights for the samples in the minibatch. Hence, we use Rg. term that incorporates stochastic dynamies, to follow the tilted objective for each group g. which is used for normalizing the weights in (3)
2. While we sample the group from which draw the minibatch, for small number of groups, one might want to draw onc minibatch per each group and weight the resulting gradients accordingly.
3. The second last line in Algorithm 2 concerning the update of Rg.r is not trivial linear averaging. Instead, we use a tilted averaging to ensure an unbiased estimator (if 0 is not being updated).
Algorithm 2: Stochastic TERM
Initialize: Rg 0 V [G]
Input: a,
while stopping criteria not reached do
sample g on [G] from a Gumbel-Sofftax distribution with logits Rg + & log [g] and
temperature
sample minibatch B uniformly at random within group g
compute the loss f(x; 8) and gradient V fof(x; for all e B
RB - 7-tilted loss (2) on minibatch B
Rg - + log (1 Re. + +xerBe.r). wr - (xx())))
0 0 |8 ELEB W (x)
end
The stochatic algorithm above requires roughly the same time/space complexity as mini-batch SGD, and thus scales similarly for large-scale problems. TERM for the non-hierarchical cases can be recovered from Algorithm and 2by setting the inner-level tilt parameter = O. For completeness, we also describe them here. Algorithm BJis the sample-level tilting algorithm the batch setting, and Algorithm is its stochastic variant.
Algorithm 3: Batch Non Non-Hierarelical TERM
Input: a
while stopping criteria not reached do
compute the loss f (x;;; f) and gradient (of(z; all [N]
R((; () - t-tilted loss (2) on all i [N]
wr((;; - (((((,;))))))) -(t())))))))))))))))))))))))))))
0 -- A N EieINI (o.
end
In order verify the correctness of Algorithm 4 we plot the distance of the solution 0 the solution 8* obtained by running the full gradient method (Algorithm I in terms of the number of iterations. In Figure 7 we see that 9 can be arbitrarily close to 6* and Algorithm with t * converges similarly to mini-batch SGD with / = O. As mentioned in the main text, theoretically analyze the convergence of stochastic solvers would interesting direction of future work. The challenges would to characterize the tightness of the estimator to the true risk at each iteration leveraging the proposed tilted averaging structure.
We summarize the applications we solve TERM for and the algorithms we use in Table below on
the left.
34

---

Published as a conference paper at ICLR 2021
Algorithm 4: Stochastic Non-Hierarchical TERM
Initialize R. =
Input: t, a,
while stopping criteria not reached do
sample minibatch B uniformly at random from [N]
compute the loss [x;; 0) and gradient (os(a; 0) for all E
RR,- (-tilted loss (2) minibatch B
Re log (1 - A)e xelRin We, exf(x;0))
0 - 0 Enen 1 Vof(x;0)
end
point estimation, batch size=10
Three toy examples (Figure
Algorithm
10
Robust Regression (Table |
Algorithm
Robust Classification (Tabic
Algorithm +
Low-quality Annotators (Figure
Algorithm (r
0)
16-47
10
Fair PCA (Figure
Algorithm
T
Class Imbulance (Figure
Algorithm
Variance Reduction (Table 8
Algorithm
Ilierarchical TERM (Table
Algorithm
10
iters
Figure 7: Correctness of Algorithm The y-axis is the normalized distance between obtained by running Alg 4 and the optimal solution 8 via the full batch method. For different values t, can be arbitrarily close 1*
Table 4: Applications and their corresponding solvers.
H.1 CONVERGENCE WITH
First, note that t-tilted losses 3(t)- for all In small neighborhood around the tilted solution, (()) is bounded for all negative t and moderately positive t, whereas it scales lincarly with t as f +00, which has been previously studied in the context of exponential smoothing of the max (Kort & Bertsekas 1972, Pee & Royset (01T). We prove this formally in Appendix [B] Lemma
but can also be observed visually via the toy example Figure 2 convergence result below for Algorithm 3
Based on this, we provide
Theorem 13. Under Assumption 2
there exist C1, C2 < oc that do not depend on t such that for any te RR setting the step size Ci+C21 after iterations:
To(1, π((1,((1) < (1-
Ci Cat ( (f(((1,))) r((,,(1)))
Buin
)"r
(189)
Proof. First observe that by Lemma 5 R(t, 0) is Bmin -Stonnlyy convex for all e R+ Next, notice that by Lemma 4. there exist C1, C2 < oc such that R((: 0) has (C1 Cap)-Lipschitz gradient for all t e Rt Then, the result follows directly from (Krimi et al. 2016) l].
Theorem 13 indicates that solving TERM lo- cal optimum using gradient-based methods will tend be as efficient as traditional ERM for small-to-moderate values of / (Jin et al.) 2017)
convergence with
(Rt.)) Rit Avni
10-11
which we corroborate via experiments on mul- tiple real-world datasets in Section 5 This is in contrast to solving for the min-max solution, which would be similar to solving TERM
101-1
[=0
10
t +00 (Kort & Bertsekas 1972. Ostrovskii
Figure 8: As +00, the objective becomes less smooth in the vicinity of final solution, hence suf- fering from slower convergence. For negative values of I, TERM converges fast due to the smoothness in the vicinity of solutions despite its non-convexity.
al. 2020 Pee & Royset| 2011).
Second, recall that the f-tilted loss remains strongly convex for >> so long the origi-
35

---

Published as a conference paper at ICLR 2021
nal loss function is strongly convex. On the other hand, for sufficiently large negative t, the t-tilted loss becomes non-convex. Hence, while the t-tilted solutions for positive are unique, the objective may have multiple (spurious) local minima for negative t even if the original loss function is strongly convex. For negative f, we seek the solution for which the parametric set of I-tilted solutions obtained by sweeping IR remains continuous (as in Figure P.c). To this end, for negative TERM by smoothly decreasing from ensuring that the solutions form a continuum in E Despite the non-convexity of TERM with multiple real-world problems in Section S Additionally, as the objective remains smooth, it is still relatively efficient solve. We plot the convergence with on a toy problem in Figure
solve
find that this approach produces effective solutions to
36

---

Published as a conference paper at ICLR 2021
1 ADDITIONAL EXPERIMENTS
In this section we provide complete experimental results showcasing the properties of TERM (Appendix[[] LII and the use-cases covered in Section (Appendix 1.2). Details on how the experiments themselves were executed are provided in Appendix J
I.1 EXPERIMENTS TO SHOWCASE PROPERTIES OF TERM
Recall that in Section Interpretation is that TERM can be tuned to re-weight samples to magnify or suppress the influence of outliers. In Figure below, we visually show this effect by highlighting the samples with the largest weight for t +0 and -c0 on the logistic regression example previously described in Figure
logistic regression
logistic regression
-2-
-2
2
(a) Samples with the largest weights when t + +00 (b) Samples with the largest weights when + -00.
Figure 9: For positive values of I, TERM focuses the samples with relatively large losses (rare instances). When 4:00 (left), few misclassified samples have the largest weights and are highlighted. the other hand, for negative values of i, TERM suppresses the effect of the outliers, and as t - 00 (right), samples with the smallest losses hold the the largest weights.
Interpretation concerned with smooth tradeoffs between the average-loss and max/min-loss In Figure 10 we show that (1) tilted solutions with positive t's achieve smooth tradeoff between average-loss and max-loss, (2) similarly, negative t's result a smooth tradeoff between average-loss and min-loss, and (3) increasing from -00 to oo reduces the variance of the losses.
average loss tradeoffs
average min less tradeoffs
variance reduction
2.5
average loss
loss variance
awer ogg
6.0
2219
-0.
t
+000
10
-6
-2
max loss
min loss
[4]
average vs. max tradeoffs
average vs. min loss tradcoffs
variance reduction
0.6
0.5
11
average 1685
vorGance
overage
63
1-3
++
6.1
20
10-
16
10-1
max loss
min loss
16
The tradeoffs between the average-loss and the max/min-loss offered by TERM on point estimation (top) and logistic regression (bottom) toy examples presented in Figure [ empirically validating Thcorems [ Positive values of t trade the average-loss for the max-loss, while negative values of t trade the average-loss for the los-loss. Inereasing from -oo to +00 results in the reduction of loss variance, allowing the solution to tradeoff between bias/variance and potentially improve generalization.
Figure 10:
37

---

Published as a conference paper at ICLR 2021
1.2 COMPLETE CASE STUDIES
Here we provide complete results obtained from applying TERM to a diverse set of applications. We either present full metrics of the empirical results discussed in Section or provide additional experiments demonstrating the effects of TERM in new settings.
Robust regression. In Section 5.1 we focused on noise scenarios with random label noise. Here, we present results involving both feature noise and target noise. We investigate the performance of TERM on two datasets (cal-housing (Pace & Barry, 1997) and abalone (Dua & Graff 2019) ) used in (Yu et al. 2012). Both datasets have features with 8 dimensions. We generate noisy samples following the setup in (Yu et al., 2012)-sampling 100 training samples, and randomly corrupting 5% of them by multiplying their features by 100 and multiply their targets by 10,000. From Table 5
below, we see that TERM significantly outperforms the baseline objectives in the noisy regime on both datasets.
Table 5: An alternative noise setup involving both feature noise and label noise. Similarly, TERM with < 0 significantly outperforms several baseline objectives for noisy outlier mitigation.
test RMSE (cal-hous
test RMSE (abalone)
objectives
clean
noisy
clean
noisy
HRM
0.766 m022) 239
2.444 (0:05) 1013
Tn
0.759 more) 139 (1))
2.435 (1001) 1008 (117)
Huber (Huber 1964
0.762 (0.009)
163 (
2.449 (0.01))
922 (45)
CRR (Bhatia ct at. 2017
0.766 (0004)
245 DM
2.444 (x00)> 986 (146)
TERM
0.745 morr)
0.753 (0.01e)
2.477
2.449 (0.12))
Genie ERM
0.766 (002)) 0.766 (0:025)
2.444 0.:18)
2.450 109)
We also provide results on synthetic data across different noise levels in two settings. In Figure [1 the mean of the noise is different from the mean of the clean data, and in Figure [2] the mcan of two groups of data are the same. Similarly, TERM (t = 2) can effectively remove outliers in the presence of random noise.
reprssion, 0%
Enear regression 20% moise
linnar regression, noise
regrosion, 30% nois
65
-6.
Figure 11: Rohust regression on synthetic data. In the presence of random noise, TERM with negative t's (blue, t t= -2) can fit structured clean data at all noise levels. while ERM (purple) and TERM with positive i's (red) overfit to corrupted data. We color inliers in green and outliers in brown for visualization purposes.
Irear regremion, 0% moie
lineee regneaion, nake
Innar regresion, 40% nois
liner nigisiins, 80% mise
045
-19
Figure 12:
In the presence of random noise with the same mean as that of clean data, TERM with negative t's (bluc) can still surpass outliers in all cases, while ERM (purple) and TERM with positive i's (red) overfit corrupted data. While the performance drops for 80% noise, TERM can still learn useful information, and achieves much lower error than ERM.
38

---

Published as a conference paper at ICLR 2021
Robust classification. Recall that in Section 5.1 for classification in the presence of label noise, we only compare with baselines which do not require clean validation data. In Table 6 below, we report the complete results of comparing TERM with all baselines, including MentorNet-DD DD (Jiang eet al. 2018) which needs additional clean data. In particular, in contrast to the other methods, NenDorNet-DD uses 5,000 clean validation images. TERM is competitive with can even exceed the performance of MentorNet-DD, even though it does not have access to this clean data.
Table 6: A complete comparison including two MentorNet variants. TERM is able to match the performance of MentorNet-DD. which needs additional clean labels.
test accuracy (CIFAR- 1 0, Inception)
objectives
20% noise 40% noise 80% noisc
ERM
0.775 (004)
0.719 (003)
0.284 (004)
RandomRect (Ren et al.
2018
0.744 (004))
0.699 (005)
0.384 (005)
SelfPaced (Kumar el al. 2010
0.784 (004))
0.733 (004)
0.272 (004)
MentorNet-PID (Jiang el al. 2018
0.798 (.004)
0.731 (004)
0.312 (005)
GCE (hhng & Sabuncu 2018
0.805 (004)
0.750 (004)
0,433 (005)
NettorNet-DD (Jang et al. 2018
0.800
0.763 (004)
0,461
TERM
0.795 (0044)
0.768 (004)
0.455 (005)
Genie ERM
0.828 (004))
0.820 (004)
0.792 (004))
To interpret the noise more easily, we provide toy logistic regression example with synthetic data here. In Figure [3 we see that TERM with = -2 (blue) can converge to the correct classifier under 20%, 40%, and 80% noise.
logistic regrassion, noise
logiatic reguassion noise
logstic regression. 40%
logistic regression. 80%
21
Robust classification using synthetic data. On this toy problem, we show that TERM with negative t's (blue) can be robust to random noisy samples. The green line corresponds the solution of the generalized cross entropy (GCE) baseline (Zhang & Sabuneu| 2018). Note that on this toy problem, GCE is as good as TERM with negative f's, despite its inferior performance on the real-world CIFARIO dataset.
Figure 13:
(Adversarial or structured noise.) As a word of caution, we note that the experiments thus far have focused on random noise; as one might expect, TERM with negative t's could potentially overfit to outliers if they are constructed in an adversarial way. In the examples shown in Figure [4] under 40% noise and 80% noise, TERM has a high error measured on the clean data (green dots).
Inear regression, 40% noise
linear reg regression, 40% noise
linear regression, 80% noise
lincar regression, 80% noise
18
85
-85
30
455
+20
-55
08
05
15
26
-20
-45
08
05
18
Figure 14: TERM with negative t's (bluc) cannot fit clean data if the noisy samples (hrown) are adversarial or structured in manner that differs substantially from the underlying true distribution.
Low-quality annotators. In Section 5.
we demonstrate that TERM can be used to mitigate the
effect of noisy annotators, and we assume each annotator is either always correct, always uniformly
39

---

Published as a conference paper at ICLR 2021
CIFARIO
vehicle
FocAug (MccMahan et al.
q-FFI (1) en all)
test accuracy
TERM
Devices
full clean data
Genie FRM
TEHM
remove two noisy annotators remove one noisy annotater
20
60
GB
30
11.0
0.2
0..
12.55
0.88
1.0
# epochs
test accuracy
Figure 15: TERM achieves higher test accuracy than the baselines, and can match the performance of Genic ERM (i.c., training on the clean data combined).
Figure 16: TERM FL (f 0.1) significantly increases the accuracy the porst-performing device (similar to q-FFL et (020b) ) while
obtaining a similar average accuracy (Table
assigning random labels. Here, we explore a different and possibly more practical scenario where there are four noisy annotators who corrupt 0%, 20%, 40%, and 100% of their data by assigning labels uniformly at random, and there is one additional adversarial annotator who always assigns wrong labels. We assume the data points labeled by each annotator do not overlap, since (Khetan) ct al. 2018) show that obtaining one label per sample is optimal for the data collectors under fixed annotation budget. We compare TERM with several baselines: (a) training without the data coming from the adversarial annotator, (b) training without the data coming from the worst two annotators, and (c) training with all the clean data combined (Genie ERM). The results are shown in Figure [5 We see that TERM outperforms the strong baselines of removing one or two noisy annotators, and closely matches the performance of training with all the available clean data.
Fair federated learning. Federated learning involves learning statistical models across massively distributed networks of remote devices isolated organizations (Li et al. 2020a McMahan et al.) 2017). Ensuring fair (i.e., uniform) performance distribution across the devices is a major concern in federated settings (Li al., 22220b Mohri et al./ 2019), as using current approaches for federated learning (FedAvg (McMahan et al. 2017)) may result in highly variable performance across the network. (Li et al.. (0200) consider sol solving an alternate objective for federated learning, called q-FFL, to dynamically emphasize the worst- porst-performing devices, which is conceptually similar to the goal of TERM, though applied specifically to the problem of federated learning and limited to the case of positive t. Here, we compare TERM with g-FFL in their setup on the vehicle dataset (Duarte & Hu 2004) consisting of data collected from 23 distributed sensors (hence 23 devices). We tilt the L2 regularized linear SVM objective at the device level. At each communication round,
weight the accumulated local model updates from each selected device based on the weights estimated via Algorithm 2 From Figure T6, we see that similar q-FFI., TERM (t 0.1) can also significantly promote the accuracy on the worst device while maintaining the overall performance. The statistics of the accuracy distribution reported in Table below.
Table 7:
Both F-FFL. and TERM encourage more uniform accuracy distributions across the devices in federated networks while maintaining similar average performance.
test accuracy
objectives
average
worst 10%
best 10%
standard deviation
FedAvg
0.853 (0.13)) 0.421 (0016) 0.951 (0.008)
0.173 (0003))
F-LFL (g = 5)
0.862 (0.65)
0.704 (0.03))
0.929 (0.006)
0.064 (0.1))
TERM (t 0.1) 0.853 (0.61) 0.707 (0021) 0.926
(0.005)
0.061 (0.006)
Improving generalization via variance reduction. We compare TERM (applied at the class-level as in 4 with logistic loss) with robustly regularized risk (RgbustRegRisk) as in (Namkoong & Duchi 2017) the HIV-1 (Dua & Graff 2019 Rögnvaldsson 2013) dataset originally investigated
40

---

Published as a conference paper at ICLR 2021
by (Namkoong & Duchi 2017). We examine the accuracy the rare class (Y 0), the common class (Y = 1), and overall accuracy.
The mean and standard error of accuracies reported in Table RobustRegRisk and TERM offer similar performance improvements compared with other baselmns, such as linear SVM, Learn- Rewight (Ren et al.] 2018), FocalLoss (Lin et al. 2017), and HRM (Leqi et al. 2019). For larger t, TERM achieves similar accuracy both classes, while RobustRegRisk does not show similar trends by sweeping its hyperparamettrs.. It is common to adjust the decision threshold boost the accuracy on the rare class. We do this for ERM and RobustRegRisk and optimize the threshold so that ERM+ and RobustRegRisk. result in the same validation accuracy on the rare class as TERM (t = 50). TERM achieves similar performance to RobustRegRisk, without the need for an extra tuned hyperparameter.
Table TERM 0.1) is competitive with strong baselines in generalization. TERM 50) outperforms F (with decision threshold changed for providing fairness) and is competitive with RobustRegRisk, with no need for extra hyperaarameter tuning.
accuracy (Y
accuracy (Y
overall accuracy (%)
objectives
train
test
train
test
train
test
HRM
0.841 (005)
0.822
0..97
0.966 (030) 0.944
0.934
Linear SVM
0.873 (105)
0.838
0..665
0.964 (0st) 0.951
0.937
Reweihh (Ren al. 2018
0.860
0.841 (o14 0.960
0.961
0.940
0.934
FocalLoss (Lin et al. 2017
0,871 (003)
0.834 (013) 0.970
0,966
0.949
0.937
HRM Legi et al. 2019
0,875 (003)
0.839 (012) 0.972
0.965
0.952
0.937
RohustRegKisk [Namkoong Duchi 2017)
0.875 (n01)
0.844 (om 0.971
0.966
0.951
0,939
TERM (t 0.1)
0.864 (005)
0.840 com))
0.970
0.964
0.949
0.937
ERM, (thresh=0.22 0.26)
0.943 (101)
0.916 (006)
0.919
(,00))
0.917
(005)
0.924 (mm)
0.917 (007)
RobustRegRisk. (thresh=0.49)
0.943 (0000
0.917 6005)
0.928
(,00))
0.928
(00))
0,931 (mm)
0.924 (001)
TERM (t 50)
0.942 (001)
0.917 (005)
0.926
(200)
0,925
(03))
0.929 (107)
0.924 (00T)
41

---

Published as a conference paper at ICLR 2021
J EXPERIMENTAL DETAILS
We first describe the datasets and models used in each experiment presented in Section and then provide detailed setup including the choices of hyperparameters, All code and datasets are publicly available at github.com//itiann/
J.1 DATASETS AND MODELS
We apply TERM to diverse set of real-world applications, datasets, and models.
In Section 5.1 for regression tasks, we use the drug discovery data extracted from (Diakonikolas et al. 2019) which is originally curated from (Olier et al. 2018) and train linear regression models with different losses. There are 4,085 samples in total with each having 411 411 features. We randomly split the dataset into 80% training set, 10% validation set, and 10% testing set. For mitigating noise on classification tasks, we use the standard CIFAR- 10 data and their standard train/val/tes partitions along with standard inception network (Szegedy al., 2016). For experiments regarding mitigating noisy annotators, we again use the CIFAR- 10 data and their standard partitions with a ResNet20 model. The noise generation procedure is described in Section [..]
In Section 5.2 for fair PCA experiments, we use the complete Default Credit data to learn low- dimensional approximations and the loss is computed on the full training set. We follow the exact data processing steps described in the work (Samadi et al. 2018) we compare with. There are 30,000 total data points with 21 -d-dimensional features (after preprocessing). Among them, the high education group has 24,629 samples and the low education group has 5,371 samples. For class imbalance experiments, we directly take the unbalanced data extracted from MNIST (LeCun et al., 1998) used in (Ren et al.) (2018). When demonstrating the variance reduction of TERM, we use the HIV-1 dataset (Rögnvaldsson, 2013) as (Namkoong & Duchi 2017) and randomly split it into 80% train, 10% validation, and 10% test set. There 6,590 total samples and each has 160 features. We report results based on five such random partitions of the data. We train logistic regression models (without any regularization) for this binary classification task for TERM and the baseline methods. We also investigate the performance of a linear SVM
In Section the HIV-1 data are the same that in Section 5.2 data to make it more imbalanced, or inject random noise, as described in Section 5.3
We also manually subsample the
J.2 HYPERPARAMETERS
Selecting In Section 5.2 where we consider positive t's, we select from a limited candidate set of (0.1, 0.5, 1, 5, 10, 50, 100, 2003 on the held-out validation set. For initial robust regression experiments, RMSE changed by only 0.08 on average across t; we thus used t -2 for all experiments involving noisy training samples (Section 5.1 and Section
Other parameters. For all experiments, we tune all other hyperparameters (the learning rates, the regularization parameters, the decision threshold for ERM,, p for (Namkoong & Duchi] (0177). a and y for focal loss (Lin et al. 2017)) based on a validation set, and select the best one. For experiments regarding focal loss (Lin et al. 2017 7), we select the class balancing parameter (a in the original focal loss paper) from range (0.05, 0.95, 0.05) and select the main parameter y from {0.5, 2,2,3, 3, 4, 5). We tune p in (Namkoong & Duchi 2017) such that & is selected from (0.5, 2, 3, 4, 5, 10) where n the training set size. All regularization parameters including regularization for linear SVM selected from (0.0001, 0.01, 0.1, 1, 2). For all experiments the baseline methods, default hyperparameters in the original paper (or the open-sourced code).
the
We summarize a complete list of main hyperparameter values as follows.
Section 5.7
Robust regression. The threshold parameter 8 for Huber loss for all noisy levels is 1, the corruption parameter for CRR 500 (20% noise), 1000 (40% noise), and 3000 (80% noise); and TERM uses -2.
Robust classification. The results are all based on the default hyperparameters provided by the open-sourced code of MentorNet (Jiang et al. 2018), if applicable. We tune the g parameter for
42

---

Published as a conference paper at ICLR 2021
generalized cross entropy (GCE) from {0.4, 0.8, 1.0) and select best one for each noise level. For TERM, we scale linearly as the number of iterations from 0 to -2 for all noise levels.
Low-quality annotators. For all methods, we use the same set of hyperparameters. The initial step-size is set to 0.1 and decayed to 0.01 at epoch 50. The batch size is 100.
Section 5.2
Fair PCA. We use the default hyperparameters and directly run the public code of (Samadi et al.
2018) to get the results the min-max fairness baseline. We use learning rate of 0.001 for gradient-base basde solver for all target dimensions.
Handling class imbalance. We take the open-sourced code LearnReweight (Ren et al. 2018) and use the default hyperparameters for the baselines of LearnReweight, HardMine, and ERM. We implement focal loss, and select 0.05, y
Variance reduction. The regularization parameter for linear SVM is y for focal loss 2. We perform binary search on the decision thresholds for ERM, and RobustRegRisk,, and choose 0.26 and 0.49, respectively.
Section 5.3
We tune the parameter for GCE based validation data. We use 0, 0, 0.7, 0.3 respectively
for the four scenarios we consider. For RobustlyRegRisk, we use & = 10 (where n is the training sample size) and we find that the performance is not sensitive to the choice of For focal loss, we tune the hyperparameters for best performance and select 7 = 2, =0.5, 0. 1, 0.5, and 0.2 four scenarios. We use -2 for TERM in the presence of noise, and tune the positive t's based on the validation data. In particular, the values of tilts under four cases are: (0, 0.1), (0, 50), (-2, 5), and (-2, 10) for TERM, sc and (0.1, 0), (50, 0), (1, -2) and (50, -2) for TERM...
43

---

Published as a conference paper at ICLR 2021
K
DISCUSSION
Our proposed work provides an alternative to empirical risk minimization (ERM), which is ubiquitous throughout machine learning. As such, our framework (TERM) could be widely used for applications both positive and negative. However, our hope is that the TERM framework will allow machine learn- ing practitioners easily modify the ERM objective handle practical concerns such as enforcing fairness amongst subgroups, mitigating the effect of outliers, and ensuring robust performance on new, unseen data, One potential downside of the TERM objective is that if the underlying dataset nof well-understood, incorrectly tuning could have the unintended consequence of magnifying the impact of biased/corrupted data in comparison to traditional ERM. Indeed, critical the success of such framework is understanding the implications of the modified objective, both theoretically and empirically. The goal this work is therefore to explore these implications so that is clear when such modified objective would be appropriate.
In terms of the use-cases explored with the TERM framework, we relied on benchmark datasets that have been commonly explored in prior work (e.g.. Samadi et al. 2018 Tantipongpipat al. 2019 Yang et al. 2010; Yu et al., 2012). 2. However, we note that some of these common benchmarks, such cal-housing (Pace & Barry 1997) and Credit (Yeh & Lien 2009), contain potentially sensitive information. While the goal of our experiments was to showcase that the TERM framework could be useful in learning fair representations that suppress membership bias and hence promote fairer performance, developing an understanding for-and removing- such membership biases requires more comprehensive treatment of the problem that outside the scope of this work.
44


Reviews:
[{"review_id": "qLJgnLurpD", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\n  *  Summary of the paper.\n  The paper presents a modification of the empirical risk minimization (ERM) framework in order to obtain more robust or fairer results, using tilted objective. The paper exhibit several properties of the tilted empirical risk minimization (TERM) algorithm applied to classification and regression, TERM exhibits a trade-off between average loss and max loss for instance and this trade-off can be handled with a parameter t that control how robust one wants to be or how fair one wants to be. The claims are supported by a number of numerical illustrations that show the practical efficiency of the method for diverse tasks.\n \n  * Strong points: the article is entirely reproducible as the author furnishes a well documented code. The figures and experiments made in the article provide a good illustration of the algorithm and a few theoretical lemma come to help understand the algorithm better.\n   \n  * Weak points: Use of 80% outliers in Table 1 without further explications. I think there is too much material, you made a lot of different experiments and it would have been great to have less experiments but more explications. There is no theoretical risk bound that would give us the efficiency of TERM, for instance in a corrupted setting or with respect to a fairness loss.\n    \n  *  Recommendation.\n    I vote for accept. The algorithm seems efficient and easy to implement and it allows the user a broad choice of different extensions of the basic learning framework in particular to fairness and robustness in classification and regression.\n\n**Most of my review will be about the robustness part of the article because it is a subject I am familiar with.**\n\n  *  Questions:\n    * It is very weird that TERM works in Table 1 even when there are 80% outliers , as my understanding of outliers is that they must be in minority. I would say that if 80% of the points are outliers, maybe the 20% points are in fact the outliers and I don't see a practical application where the inliers would be in minority. It seems counterintuitive. Can you explain that ? This is even more counterintuitive in classification where the error is smaller when the corruption is 80% than when it is 40%. I am not sure what is the task and what it is that your algorithm do in the 80% noise context. All the definitions of noise/outliers that I know of suppose that the proportion of outliers is smaller than 50%. In fact I think the problem with 80% outliers is theoretically impossible except when doing list decoding (see for instance the article \"List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians\" by Diakonikolas, Kane and Stewart).\n    \n    * Why did you not compare your algorithms with scikit-learn algorithms or scikit-learn-contrib algorithms ? I am thinking about HuberRegressor, RANSAC, TheilSenRegressor. To go further you could also test algorithms from scikit-lego for fairness or scikit-learn-extra for robust classification. To compare to a second party and not only your algorithms vs your algorithms.\n    \n    * Why did you only corrupt the labels in a robust classification task ? At least in the regression experiment, you could have corrupted the features and it works well. This is a very interesting property of your algorithm, there are not a lot of robust regression and classification algorithms that are robust to outliers in the feature space ! Is it a misunderstanding on my part or do you algorithm really work when feature space is corrupted ? I tested your algorithm on drug experiment with outliers in feature space and it worked. Huber and L1 did not work in this context.\n    \n    * Is the TERM problem convex when t<0 ? As it is, there is no reason that your algorithm will always converge to a global minimum.\n\n  * Additional Feedback.\n    * The 80% noise in Table 1 really bugged me when I read your article, maybe you may want to explain more or to remove it as it can cause misunderstandings I think.\n    * When comparing robust methods, (Table 1), the authors did not compare their methods to the mainstream algorithms like RANSAC or Theil-Sen regression. It would have been interesting to do so.\n    * The classification task considered by the authors in Table 1 (CIFAR-10) is not easy to interpret. What is an outlier for a neural network ? For a linear classifier, an outlier is readily defined for a very non-linear classifier; this is not so easy because most neural networks will be so nonlinear that the introduction of outliers in the training dataset will not change the performances of the algorithm.\n    * It would have been interesting to compare TERM to other robust classification algorithms on an easier dataset in low dimension to exhibit the comparative performances similarly to what is done for regression.\n    * You talk of \"minimax\" in a way that is unusual. Most of the time, at least in theoretical ML, minimax algorithms refer to algorithms which attain the optimal rate of convergence (see Section 14.1 in \"A Probabilistic Theory of Pattern Recognition\" by Devroye, Gyorfi and Lugosi). I think this is not what you mean, what you used I call it minmax. I don't know if yours is a common use of the term and if this is the case, sorry for this comment and don't take it into account.\n    * Typo: Section 5.3 inn -> in.\n    * The fact that the objective is strongly convex when t>0 is fairly important (this proves the convergence), I think that you should include the whole proof and not an abridged version of it (see proof Lemma 3).\n    \n    \n    \n    \n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XV4Nntx_9Ac", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provide nice discussions of a simple modification of ERM paradigm. Mainly, it consists in applying an exponential smoothing to the loss function. The authors provide several interpretations and connexions with (robustness/fairness/quantile regression etc...) literature and show how the TERM can be adapted to such problem. The paper is well written, contains pedagogical illustrations and detailed properties of TERM.\n\n- The success of Term heavily rely on a *magical* tuning of the parameter $t$ depending on the application. Grid search was used in this paper which considerably increases the complexity of the algorithm without necessarily improving significantly the accuracy when compared to competitors.\n\n- The experiments does not report standard deviation in the train/test splitting. Averaging the test accuracy after several random splitting would be beneficial for clarity.\n\n- The classical ERM formulation is written as sum of functions, which allows several advanced stochastic optimization algorithm. Such structure is destroyed in the tilted formulation.\n\n- In Assumption 2, isn't it too restrictive to assume that $f(x_i, \\cdot)$ does not have critical point (which does not seems true for quadratic loss)? \n\n- To help the reader, the authors might recall on which quotient the L'hopital rule is applied (after verification of assumptions)\n\n- In equation (87), the limit and derivation are permuted without justification (uniform convergence might be needed). Same for Eq (90)\n\n- Should be interesting to compare with recent robust estimation such as median of means or robust gradient descent (Holland and Ikeda, 2019).\n\n- Should be also interesting to know how the generalization bound (and sample complexity) of TERM compare with the one of ERM wrt $t$.", "extra_scores": {}, "extra_text": {}}, {"review_id": "UDJeH2eg16", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work analyzes the LogSumExp aggregated loss (named tiled empirical risk minimization, or TERM, in the paper). It provides several general properties of the loss, such as its relation to min/avg/max-loss, and interpretations of different trade-offs. Empirically, it is shown that TERM can be applied to a diverse set of problems, including robust optimization, fairness and generalization.\n\nStrength:\n1. Provide theoretical analysis on the properties of TERM\n2. Various experiments to showcase the usefulness of TERM as objective\n\nWeakness:\n1. Unclear convergence of the optimization procedure\n2. Missing literature\n\nDetails:\n1. The LogSumExp has been extensively studied in geometric programming (Calafiore and El Ghaoui, 2014, Sec.9.7) and boosting (Mason et al., 2000; Shen and Li, 2010). The current manuscript does have some novel interpretations such as the trade-off between avg-min losses. However, I am not an expert in this field, thus not sure how much the new analysis will contribute to the community (or the analysis may exist somewhere). Additionally, LogSumExp is called \"tilted\" without explanation. Why not call it LogSumExp, which is well-known?\n\nRef:\n- Calafiore, G.C. and El Ghaoui, L., 2014. Optimization models. Cambridge university press.\n- Mason, L., Baxter, J., Bartlett, P.L. and Frean, M.R., 2000. Boosting algorithms as gradient descent. In Advances in neural information processing systems (pp. 512-518).\n- Shen, C. and Li, H., 2010. On the dual formulation of boosting algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(12), pp.2216-2231.\n\n2. Some of the technical details are missing.\n- What is the range of t in Fig.1?\n- The interpretation 2 is constrained to be t<0 for avg-min trade-off (and t>0 for avg-max, as shown empirically in Fig.9). This should be clear in the informal statement to avoid confusion. Also, the interpretation 3 is valid for t>0.\n- Algorithm 2 claims that t is temperature, but in fact, t is more like the inverse of temperature in common sense (consider softmax).\n\n3. Convergence of the optimization procedure is not convincing. Since Algo.2 is using a non-trivial averaging for the normalization term, the convergence of the stochastic version is unclear. It seems that the convergence discussion in Appendix H is only for the batch version.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-nFZF8lNkM6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers a unified framework named TERM for addressing a bunch of problems arising in the simple averaged empirical minimization. By leveraging the key hyper-parameter t in the TERM loss, it can recover the original average loss and approximate robust loss, min/max loss, and the superquantile loss, etc. The authors also propose gradient-based optimization algorithms for solving the TERM problem.  \n\nOne thing that I do not understand very well is the paragraph under Lemma 1. Why is it necessary that outliers can cause a large (positive t) or small (negative t)  losses? Note that outliers can be arbitrary, say adversarial. \n\nAlso, do you have numerical issues for large enough t?\n\nIs it possible to show certain convergence results of the algorithms for solving the TERM? Especially, the TERM has the nice property that it is always smooth (depending on the value of t). \n\nOverall, the TERM seems to be a good unification of different losses used in machine learning society for different purposes. The theoretical justifications also look reasonable and informative. In addition, the authors conduct a series of experiments to show the good performance of TERM for different tasks such as robustness to outliers, handling imbalance, and improving generalization, etc. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear Authors,

Thank you very much for your detailed feedback to the initial reviews and also for further answering additional questions raised by a reviewer. Your effort has been certainly contributed to clarifying some of the concerns raised by the reviewers and improving their understanding of this paper.

Overall, all the reviewers found a merit in this paper and thus I suggest its acceptance. However, as Reviewer #2 suggested, investigating the convergence in the stochastic case is very important. More discussion on this would be a valuable addition to the paper, which the authors can incorporate in the final version.
Decision: Accept (Poster)