Don’t blame Dataset Shift! Shortcut Learning due to Gradients and Cross Entropy
Authors: Aahlad Manas Puli
Lily H Zhang
Yoav Wald
Rajesh Ranganath
Venue: NeurIPS 2023 poster (2023)
Keywords: shortcut learning
spurious correlations
perfect stable feature
perception tasks
implicit bias in optimization
improving inductive biases
TL;DR: Implicit biases toward maximizing margins induce shortcut learning in ERM even in tasks with perfect stable features, controlling margins mitigates shortcuts

Abstract: Common explanations for shortcut learning assume that the shortcut improves prediction only under the training distribution. Thus, models trained in the typical way by minimizing log-loss using gradient descent, which we call default-ERM, should utilize the shortcut. However, even when the stable feature determines the label in the training distribution and the shortcut does not provide any additional information, like in perception tasks, default-ERM exhibits shortcut learning. Why are such solutions preferred when the loss can be driven to zero when using the stable feature alone? By studying a linear perception task, we show that default-ERM’s preference for maximizing the margin, even without overparameterization, leads to models that depend more on the shortcut than the stable feature. This insight suggests that default-ERM’s implicit inductive bias towards max-margin may be unsuitable for perception tasks. Instead, we consider inductive biases toward uniform margins. We show that uniform margins guarantee sole dependence on the perfect stable feature in the linear perception task and suggest alternative loss functions, termed margin control (MARG-CTRL), that encourage uniform-margin solutions. MARG-CTRL techniques mitigate shortcut learning on a variety of vision and language tasks, showing that changing inductive biases can remove the need for complicated shortcut-mitigating methods in perception tasks.

Don't blame Dataset Shift! Shorteut Learning due to Gradients and Cross Entropy
Aahlad Puli
Lily Zhang
Yoav Wald
Rajesh Ranganath 123 423
Depaarmeen of Computer Science, New York University
Center for Data Science, New York University
Department of Population Health, Langone Health, New York University
Abstract
Common explanations for shortcut learning assume that the shorteut improves pre- diction under the training distribution but not in the test distribution. Thus, models trained via the typical gradient- optimization of cross cross-yntropy, which call default-ERM, utilize the shortcut. However, even when the stable feature deter- mines the label in the training distribution and the shortcut does provide any additional information, like in perception tasks, default-FRM still exhibits short- cut learning. Why are such solutions preferred when the loss for default-ERM can be driven to zero using the stable feature alone? By studying a linear per- ception task, show that default-ERM's preference for maximizing the margin leads to models that depend more on the shortcut than the stable feature, even without overparameterization. This insight suggests that default-ERNN 's implicit inductive bias towards max- marxin is unsuitable for perception tasks. Instead, we develop an inductive bias toward uniform margins and show that this bias guar- antees dependence only on the perfect stable feature in the linear perception task. We develop loss functions that encourage uniform-margin solutions, called mar- gin control (MARG-CTRI.). MARG-CTRI mitigates shortcut learning on variety vision and language tasks, showing that better inductive biases can remove the need for expensive two-stage shortcut-mitigating methods in perception tasks.
Introduction
Shortcut learning phenomenon where a model learns to base its predictions on an unstable correlation, or shortcut, that does not hold across data distributions collected at different times and/or places [Geirhos al., 2020]. A model that learns shorteuts can perform worse than random guessing in settings where the label's relationship with the shortcut feature changes [Koh et al., 2021, Puli et al., 2022]. Such drops in performance
not occur if the model depends on features whose relationship with the label does not change across settings; these are stable features.
Shortcut learning is well studied in cases where models that use both shorteut and stable features achieve lower loss than models that only use the stable feature [Arjovsky et al., 2019, Puli et al., 2022, Geirhos et al., 2020]. These works consider cases where the Bayes-optimal classifier - the training conditional distribution of the label given the covariates - depends on both stable and shortcut features. In such cases, shortcut learning occurs as the Bayes-optimal predictor is the target of standard supervised learning algorithms such as the one that minimizes the log-loss via gradient descent (GD), which we call default-ERM.
However, in many machine learning tasks, the stable feature perfectly predicts the label, i.e. perfect stable feature. For example, in task of predicting hair color from images of celebrity faces in the
*CCrresponding email: aahlad@nyu. edu
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

CelebA dataset [Sagawa et al., 2020a], the color of the hair in the image determines the label. This task a perception task. In such classification tasks, the label is independent of the shorteut feature given the stable feature, and the Bayes-optimal predictor under the training distribution only depends on the stable feature. Default-FRM can learn this Bayes-optimal classifier which, by depending solely on the stable feature, also generalizes outside the training distribution. But in practice, default- ERM run on finite data yields models that depend on the shortcut and thus perform worse than chance outside the training distribution [Sagawa et al., 2020a, Liu et al., 2021, Zhang et al., 2022]. The question is, why does default-ERM prefer models that exploit the shortcut even when a model can achieve zero loss using the stable feature alone?
To understand preferences toward shortcuts, we study default-ERM on a linear perception task with stable feature that determines the label and a shortcut feature that does not. The perfect linear stable feature means that data is linearly separable. This separability means that default-ERM-tent M-traied linear models classify in the same way as the minimum 2n-norm solution that has all margins greater than 1; the latter is commonly called max-margn margin classification [Soudry et al., 2018J. We prove that default- ERM'S 's implicit inductive bias toward the max-margin solution is harmful in that default-ERM. Ear-ultt------tinnee trained linear models depend more the shorteut than the stable feature. In fact, such dependence on the shortcut occurs even in the setting with fewer parameters in the linear model than data points, L.e without overparameterization. These observations suggest that a max-margin inductive bias is unsuitable for perception tasks.
Next, we study inductive biases more suitable for perception tasks with perfect stable features. We first observe that predicting with the perfect stable feature alone achieves uniform margins all samples. Formally, if the stable feature s(x) determines the label y via a function d, y = d sxx), one can achieve any positive b as the margin on all samples simultaneously by predicting with b d o sx). We show that in the same setting without overparameterization where max-margin classification leads to shorteut learning, models that classify with uniform margins depend only on the stable feature.
Building on these observations, we identify alternative loss functions that are inductively biased toward uniform margins, which we call margin control (MARG-CTRI.. We empirically demonstrate that MARG-CTRI. mitigates shortcut learning on multiple vision and language tasks without the use of annotations of the shorteut feature in training. Further, MARG-CTRL performs on par or better than the more expensive two-stage phortcut-mitigalte We then introduce a more challenging setting where both training and validation shorteut annotations are unavailable, called the nuisance-free setting. In the nuisance- free setting, MARG-CTRL always outperforms default- ERM and the two-stage shortcut- shortcut-mitigatin mitigating methods. These empirical results suggest that simply incorporating inductive biases more suitable for perception tasks is sufficient to mitigate shorteuts.
methods [Liu et al., 2021, Zhang et al., 2022].
2 Shortcut learning in perception tasks due to maximizing margins
Setup. We use y, z, x to denote the label, the shorteut feature, and the covariates respectively. We let the training and test distributions (Ptr, Pte) be members of family of distributions indexed by p. F= = (y, z, })}p- such that the mhortcut-label relationship Pp (z.y) changes over the family. Many common tasks in the spurious correlations literature have stable features s(x) that are perfect, meaning that the label is a deterministic function of the stable feature: y = d s(x). For example, in the Waterbirds task the bird's s body determines the label and in the CelebA task, hair color deter- mines the label [Sagawa et al., 2020a]. As sx) determines the label, it holds y (x, z) s(x). Then, the optimal predictor on the training distribution is optimal on all distributions in the family F, regardless of the shortcut because
Ptr (y x) (y s(x)) (y sxx)) = (y x).
The most common procedure to train predictive models to approximate Py xx) is gradient-based optimization of cross-entropy (also called log-loss); we call this default-ERM. Default-ERM, targets the Bayes-optimal predictor of the training distribution which, in tasks with perfect stable features, also performs optimally under the test distribution. However, despite targeting the predictor that does not depend on the shortcut, models built with default-ERM still rely on shortcut features that are often less predictive of the label and are unstable, i.e. vary across distributions [Geirhos et al., 2020, Puli et al., 2022]. We study default-FRM's 's preference for shortcuts in a data generating process (DGP) where both the shorteut and the perfect stable feature are linear functions of the covariates.
2

---

2.1 Shortcut learning in linear perception tasks
Let Rad be the uniform distribution over {1. -1), of x, and p E (0, 1), B > 1 be scalar constants. The DGP for pp(y, 2, is:
J,,,N / be the normal distribution, d be the dimension
Pp y = = (p = -1
y ~ Rad, z ~
8~ N~1(0,1' x= [B ==],=,, (I)
This DGP is set up to mirror the empirical evidence in the literature showing that shorteut features are typically learned first [Sagawa et al., 2020a]. The first dimension of x, i.c. X1. is shortcut that is correlated with y according to p. The factor B in X1 scales up the gradients for parameters that interact with X1 in predictions. For large enough B, model dependence on the shortcut feature during default-ERG ERM goes up faster than the stable feature [Idrissi et al., 2022].
The training distribution is Ptr = Pb.9 and the test distribution is one where the short- cut's 's relationship with the label is flipped Pte Po.1. Models achieve worse than random test accuracy (50%) if they ex- ploit the training shorteut relationship and the predicted class flips when the shortcut feature flips. We train with default-FRM which uses log-loss: on a data point (x, y) the log-loss is
Accuracy
Loss
100
302
80
10-
60
test
10"4
40
10-
0
2
5 104
epoch
1o4
epoch
(a) Average accuracy and loss curves.
Accuracy
Loss
boog (y fo(x)) = log [1 + (oo(---f()))
100
Tr, Y-
80
To, Y
With d = 300 and B- = 10, we train linear model on 1000 samples from the training distribution Pp=0.9. and evaluate on 1000 samples from Pp=0.11
60
To, Y
40
20
5000
10000
0
5000
10000
Observations. Figure la shows that when trained with ERR, the lin- model does not do better than chance (< 50%) on the test data even after 50, 000 epochs. So, even in the presence of the perfect feature X2, the model relies on other features like the shorteut X1. Since the final training loss is very small, on the order of 10-9, this result is not due op- timization being stuck in a local minima with high loss. These observations indi- cate that, in the linear setting, gradient- based optimization with log-loss prefers models that depend more on the shortcut than the perfect stable feature.
epochs
epochs
(b) Accuracy and loss shortcut and leftover groups.
Figure 1: Accuracy and loss curves training a linear model with default-ERM on 1000 training samples from po.9, with B = 10, d = 300 (see eq. (1)), and testing on Po.1. (a) The model achieves 100% train accuracy but < 40% test accuracy. (b) The learned model achieves high test accuracy (%s 90%) on the shortcut group and low test accuracy on the leftover group (+s 30%). Models that depend more on the stable feature than on the shortcut, achieve least 50% ac- curacy on both the shorteut and leftover groups. Hence the learned model exploits the shortcut to classify the shorteut group and overfits to the leftover group
To better understand this preference we focus on the errors in specific groups in the data. Con- sider the classifier that only uses the shortcut and makes the Bayes-optimal prediction w.r.t Per: arg max, Ptr (y = y z). We call instances that are classified correctly by this model the shortcut group, and the rest the leftover group. We use these terms for instances in the training set as well as the test set. In this experiment y is positively correlated with z, hence the shortcut group consists of all instances with y' = z' and the leftover group of those with y # z'
Figure lb gives accuracy and loss curves on the shortcut and leftover groups for the first 10000 epochs. The test accuracy for the shortcut group hits 90% while the leftover group test accuracy is < 40%, meaning that the model exploits the shorteuts. Even though a model that relies solely on the shortcut misclassifies the leftover group, we see that the training loss of the learned model on this group approaches 0. The model drives down training loss in the leftover group by depending on noise, which results in larger test loss in the leftover group than the shortcut group. Thus, fig. 1b demonstrates that the default-FRR Frrault-ERM-trainee model classifies the training shorteut group by using the shortcut feature while overfitting to the training leftover group.
3

---

Shortcut dependence like in fig. 1 occurs even with f--regularization and when training neural net- works; see appendix B.1 and appendix B.4 respectively. Next, we analyze the failure mode in fig. 1, showing that the shortcut dependence is due to default-FRM's implicit bias to learn the max- max-margin classifier. Next, we study the failure mode in fig. theoretically, showing that the shorteut depen- dence is due to default-FRM's & inductive bias toward learning the max-margin classifier.
Max-margin classifiers depend more on the the shorteut than the stable feature. We consider training a linear model [o(x) w x where w = [: Wy: We] with default-RRM. Data from eq. (1) is always linearly separable due to the perfect stable feature, but many hyperplanes that separate the two classes exist. When linear model is trained with default-FRM on linearly separable data, it achieves zero training loss and converges to the direction of minimum l2-norm solution that achieves a margin of at least 1 on all samples [Soudry et al., 2018, Wang et al., 2021, 2022]; this is called the max-margin solution. We now show that for small enough leftover group, large enough scaling factor B and dimension d of the covariates, max-margin solutions depend more the shorteut feature than the stable feature:
Theorem 1. Let w" be the max- max-margin predictor n training samples eq. (1) with a leftover group of size k. There exist constants C1, C2, No > 0 such that
d
Y integers & E (0, 10
vn No.
A Cik
A B> C2 Te'
(2)
with probability at least 1 1 1/3n over draws of the training data, it holds that Bw W
The size of the leftover group concentrates around (1 11-A0 p)n because each sample falls in the leftover group with probability (1 - p). Thus, for p > 0.9, that is for a strong enough shortcut, the condition theorem that k < n/10 will hold with probability close to 1; see appendix A.5 for more details.
The proof is in appendix A. The first bit of intuition is that using the shortcut can have lower norm because of the scaling factor B. Using the shorteut only, however, misclassifies the leftover group. The next bit of intuition is that using noise from the leftover group increases margins in one group at a rate that scales with the dimension d, while the cost in the margin for the other group only grows as Vd. This trade-off in margins means the leftover group can be correctly classified using noise without incorrectly classifying the shortcut group. The theorem then leverages convex duality to show that this type of classifier that uses the shortcut and noise has smaller & &y-norm than any linear classifier that uses the stable feature more.
The way the margin trade-off in the proof works is by constructing linear classifier whose weights on the noise features are a scaled sum of the product of the label and the noise vector the leftover group: for scalar 7, the weights w. = = =iE y,o,. The margin change the jth training sample from using these weights w. T For samples in the shorteut group, the margin change looks like a sum of mean zero independent and identically distributed variables; the standard devi- ation of this sum grows as vd. For samples in the leftover group, the margin change is the sum of mean one random variables; this sum grows d and its standard deviation grows as vd. The difference in mean relative to the standard deviation is what provides the trade-off in margins.
We now discuss three implications of the theorem.
First, theorem implies that the leftover group sees worse than random accuracy (0.5). To see this, note that for samples in the leftover group the margin y(w*) ] w Bw" + (w") Tyō yo is a Gaussian random variable centered at a negative number w Bww. Then, with 4. as the CDF of the zero-mean Gaussian random variable (w") 5, accuracy in the test leftover group is
p(y(w") Tx 2 # z) = p 8 > (w;; Bw:)] = - 4 (- -ww") S 0.5.
Second, the leftover group in the training data is overfit in that the contribution of noise in prediction ([(w)) 5) is greater than the contribution from the stable and shorteut features. Formally, in the training leftover group, w Bw: < O. Then, due to max- max-margiin property.
W Bw; + (w:) y y >
(w:) y 2 (w, - Bw?) > /WG Bw
Third, many works point to overparameterization as one of the causes behind shortcut learning [Sagawa et al., 2020a, Nagarajan et al., 2021, Wald et al., 2023], but in the setup in fig. 1, the

---

linear model has fewer parameters than samples in the training data. In such cases with non- overparameterizee linear models, the choice of default-ERN ERM typically not questioned. especially when feature exists that linearly separates the data. Corollary 1 formally shows shorteut learning for non-overparameterizer linear models. In words, default-FRM - that is vanilla logistic regression trained with gradient-based optimization - can yield models that rely more on the shortcut feature even without overparameterization.
Corollary 1. For all n > No - where the constant No is from theorem 1 - with scalar T E (0, such that the dimension of x is tn < n, for all integers h < n X min { model trained via default-ERM yields a predictor w such that Bw w
10 C1 log 3n a linear
default-ERM produces models that suffer from shortcut learning even without overparameteriza- tion, its implicit inductive bias toward max-margin classification is inappropriate for perception tasks in the presence of shortcuts. Next, we study inductive biases more suited to perception tasks.
Toward inductive biases for perception tasks with shortcuts
The previous section formalized how default-ERM solutions, due to the max-margin inductive bias, rely on the shortcut and noise to minimize loss on training data even in the presence of a different vero-population-ring rrik solution. Are there inductive biases more suitable for perception tasks?
Given perfect stable feature s(x) for perception task, in that for function d when y = do s (x). one can achieve margin b E (0, 00) uniformly on all samples by predicting with the stable b (x)).. In contrast, max-marge
classifiers allow for disparate margins as long the smallest margin crosses 1, meaning that it does not impose uniform margins. The cost of allowing disparate margins is the preference for shortcuts however, any uniform-margin classifier for the linear perception task (eq. (1)) relies only on the stable feature:
without overparamterizattoo (corollary 1). In the same setting
Theorem 2. Consider n samples of training data from DGP in eq. (1) with d < n. Consider linear classifier fx(x) = w x such that for all samples in the training data y, w x; boror any b E (0, oo). With probability 1 over draws of samples. w = [0, 02 0d-2].
Theorem 2 shows that uniform-marge classifiers only depend on the stable feature, standing in contrast with max-mane max-mnrgin classifiers which can depend on the shortcut feature (theorem 1). The proof is in appendix A.6. Thus, inductive biases toward uniform margins are better suited for perception tasks. Next, we identify several ways to encourage uniform margins.
Margin control (MARG-CTRL). To produce uniform margins with gradient-based optimization, we want the loss to be minimized at uniform -anggin solutions and be opttmizl-.p We iden- tify variety losses that satisfy these properties, and we call them MARG-CTRL losses. MARG- CTRL losses have the property that per-sample loss monotonically decreases for margins until threshold then increases for margins beyond it. turn, minimizing loss then encourages all margins to move to the threshold.
Mechanically, when models depend more on shortcuts than the stable feature during training, mar- gins on samples in the shorteut group will be larger than those in the leftover group; see the right panel in fig. lb where the train loss in the shortcut group is lower than the leftover group indicating that the margins are smaller in the leftover group. This difference is margins is consequence of the shortcut matching the label in one group and not the other, thus, encouraging the model to have sim- ilar margins across all samples pushes the model to depend less on the shortcut. contrast, vanilla log-loss can be driven to zero in direction with disparate margins across the groups as long as the margins on all samples go to do. We define MARG-CTRL losses for model so with the margin on sample (x.) y) defined as fx))...
As the first MARG-CTRI loss, we develop the o-damped log-loss: we evaluate log-loss multiplied by a monotonically decreasing function of the margin. turn, the input to the loss increases with the margin till point and then decreases. For temperature T and sigmoid function
margin
5

---

G, the o-damped loss modifies the model output fo and plugs it into log-loss:
lo (y: fo) = Liog y
(1(1-o
y fo
fo
T
Accuracy
Train Log Loss
Test Log Loss
For large margin predictions So 0, the term 1-a (xT)())/T) damps down the input to log-loss. The largest the input flog can get is 0.278T, found by setting the derivative zero, thus lower bounding the loss. As log-loss decreasing function of its input, the minimum of do-damp occurs when the margin is 0.278T' on all samples. To demonstrate empirical advantage, we compare standard log-loss to o-damped loss eq. (I); see fig. 2. The left panel of figure fig. 2 shows that test accuracy is better for d-damp. The middle and right panels shows the effect of controlling margins in training, where losses shortcut and leftover groups hover at the same value.
100
ERM,
d-damp, Z=
d-damp, Y
tr p-demo. Tr
ERM, Y
50
ERM,
25
5000 epochs
10000
50000
10000
5000
10000
epochs
opochs
Figure 2: Using o-damped log-loss yields linear models that depend on the perfect stable feature to achieve near perfect test accuracy. The middle panel shows that d-damping maintains similar margins in the training shortcut and leftover groups unlike unconstrained log-loss, and the right panel shows d d-dm achieves better leftover test-loss.
Second, we design the o-sticch loss, which imitates log-loss when fo (x) < u and penalizes larger margins fo > 2) by negating the sign of y fxx):
s-stitch = -Log (x I fx)) + (x) > u2 yfo(x)))
As the third MARG-CTRL loss, we directly penalize large margins via a log-penalty:
lmarg-log = (o())) + Alog (1 + (f)())
(4)
The fourth MARG-CTRL loss controls margins by penalizing 1
ESD Elog (y fo (x)) 2
(5)
This last penalty was called spectral decoupling (SD) by Pezeshki et al. [2021]. who use it as way to decouple learning dynamics in the neural tangent kernel (NTK) regime. Instead, from the lens of MARG-CTRI, SD mitigates shortcuts in eq. (1) because it encourages uniform margins, even though SD was originally derived from different principles, as we discuss in section 4. In appendix B.2, we plot all MARG-CTRL losses and show that MARG-CTRL improves over default-ERg on the linear perception task; see figs. 6 to 8. We also run MARG-CTRL on a neural network and show that while default-ERM achieves test accuracy worse than random chance, MARG-CTRL achieves 100% test accuracy; see figs. 10 to 13 in appendix B.4.
Related work
A large body of work tackles shorteut learning under different assumptions [Arjovsky et al., 2019, Wald et al., 2021, Krueger et al., 2020, Creager et al., 2021, Veitch et al., 2021, Puli et al., 2022, Heinze-Deml and Meinshausen, 2021, Belinkov and Bisk, 2017]. different line of work focuses on learning in neural networks in idealized settings (Yang and Salman, 2019, Ronen et al., 2019, Jo and Bengio, 2017, Baker et al., 2018, Saxe et al., 2013, Gidel et al., 2019, Advani et al., 2020].
Shah et al. [2020] study simplicity bias [Valle-Perez et al., 2018] and show that neural networks provably learn the linear function over a non-linear one, in the first epoch of training. In a simi- lar vein, Hermann and Lampinen [2020] show that neural networks can prefer a linearly feature over non-linear but more predictive feature, and Scimeca et al. [2021] make similar obser- vations and use loss landscapes to empirically study which features are easier to learn. Simplicity bias alone only describes neural biases early in training and does not explain why more predictive stable features are not learned later. Unlike simplicity bias which focuses on linear versus non- linear features, max margin bias is the reason default- ERMM prefers one linear feature, the shortcut, over another, the stable feature, like in the synthetic experiment in section 2.
While Pezeshki et al. [2021] allow for perfect features, they hypothesize that shorteut learning occurs because when one feature is learned first, other features are gradient-starved and are not learned as

---

well. They focus on a special setting where feature representations for different samples have inner product equal to a small constant show that models can depend more on the imperfect feature than the perfect feature. In this special setting. they show that penalizing the magnitudes of what we call the margin mitigates shortcuts; this method is called spectral decoupling (SD). However, as we show in appendix B.5, the assumption in Lemma [Pezeshki et al., 2021] is violated when using linear model to classify in the simple linear DGP in eq. (1). However, SD on a linear model mitigates shortcuts in the DGP in eq. (I); see B.5. Thus, the theory in Pezeshki et al. [2021] JJ fails to not explain why SD works for eq. (I), but the uniform-margin property explains why all the MARG-CTRL losses, including SD, mitigate shortcuts.
Nagarajan et al. [2021] consider tasks with perfect stable features and formalize geometric properties of the data that make max-margin classifiers have non-zero weight on the shortcut feature (w: >> 0). In their set up, the linear models are overparameterized and it is unclear when w > 0 leads to worse-than-randee
accuracy in the leftover group because they do not separate the model's depen- dence on the stable feature from the dependence noise. See fig. 14 for an example where w. > 0 but test accuracy is 100%. In contrast to Nagarajan et al. [2021]. theorem gives DGPs where the leftover group accuracy is worse than random, even without overparameterivation. Ahuja et al. [2021] also consider linear classification with default-ERM with a perfect stable feature and con- clude that default-ERM learns only the stable feature because they assume additional dimensions of noise in the covariates. We develop the necessary nuance by including noise in the problem and showing default-ERM depends on the shortcut feature even without overparameterization.
Sagawa al. [2020b] and Wald et al. [2023] both consider overparameterized settings where the shortcut feature is informative of the label even after conditioning on the stable feature. In both cases, the Bayes-optimal predictor also depends on the shorteut feature, which means their settings do not allow for an explanation of shortcut dependence in examples like fig. 1. In contrast, we show shortcut dependence occurs even in the presence of a perfect stable feature and without overparanettrrizatinn Li et al. [2019], Pezeshki et al. [2022] focus on relative feature complexity and discuss the effects of large learning rate (LR) on which features are learned first during training, but do not allow for perfect features. Idrissi et al. [2022] empirically find that tuning LR and weight decay (WD) gets default-ERM perform similar two-stage shortcut-mitigating methods like Just Train Twice (JTT) [Liu et al., 2021]. We view the findings of [Idrissi et al., 2022] through the lens of MARG-CTRI. and explain how large LR and WD approximate MARG-CTRL to mitigate shortcuts; see section
MARG-CTRL is related to but different from methods proposed in Liu et al. [2017], Cao al. [2019], Kini et al. [2021]. These works normalize representations or the last linear layers and linearly transform the logits to learn models with better margins under label imbalance. Next, methods like Learning from Failure (LFF) [Nam et al., 2020], JTT [Liu et al., 2021], and Correct-n-Contees (CNC) [Zhang et al., 2022] build two-stage procedures to avoid shorteut learning without group annotations in training. They assume that default-FRM produces models that depend more on the shortcut and select hyperparamters of the two stage process using validation group annotations. In the nuisance- free setting where there are no validation group annotations, the performance of these methods can degrade below that of default-ERM. In contrast, better characterizing the source of shortcut learning in perceptual problems leads to MARG-CTRL methods that are not as reliant on validation group annotations (see nuisance-free free results in Section 5). Without any group annotations, encouraging uniform margins via MARG-CTRL mitigates shorteuts better than JTT and CNC.
Soudry et al. [2018] characterize the inductive bias of gradient descent to converge in direction to max-margin solutions when using exponentially tailed loses; Wang et al. [2021, 2022] then prove similar biases toward max-margin solutions for Adam and RMSProp. Ji et al. [2020] show that for general losses that decrease in y fx)), gradient descent has an inductive bias to follow the f2- regularization path. All these inductive biases prefer shortcuts if using them leads to lower loss within an ee-nooo-budgee
MARG-CTRL provides a different inductive bias toward producing the same margin on all samples, which means gradient descent veers models away from imperfect short- cuts that lead to disparity in network outputs. Such inductive biases are suitable for tasks where a feature determines the label (h(x)- y).
5 Vision and language experiments
We evaluate MARG-CTRI on common datasets with shortcuts: Waterbirds, CelebA [Sagawa et al., 2020a], and Civilcomments [Koh et al., 2021]. First, MARG-CTRI. always improves over default- ERM. Then, we show that MARG-CTRL performs similar to or better than two-stage shortcut-
7

---

mitigating methods like JTT [Liu et al., 2021] and CNC [Zhang et al., 2022] in traditional evaluation settings where group annotations are available in the validation data. Finally, we introduce a more challenging setting that only provides class labels in training and validation, called the nuisance- free setting. In contrast to the traditional setting that always assumes validation group annotations, the nuisance-free free setting does not provide group annotations in either training or in validation. In the nuisance-free free setting, MARG-CTRL outperforms JTT and CNC, even though the latter are supposed to mitigate shortcuts without knowledge of the groups.
Datasets. We use the Waterbirds and CelebA datasets from Sagawa et al. [2020a] and the Civil- Comments dataset from Borkan al. [2019], Koh al. [2021]. In Waterbirds, the task is classify images of a waterbird or landbird, and the label is spuriously correlated with the image background consisting of land water. There are two types of birds and two types of background, leading to total of 4 groups defined by values of y, 2. In CelebA [Liu et al., 2015, Sagawa et al., 2020a]. the task is to classify hair color of celebrities as blond or not. The gender of the celebrity is shortcut for hair color. There are two types of hair color and two genders in this dataset, leading to a total of 4 groups defined by values of y, 2. CivilComments- WILDS [Borkan al., 2019, Koh al., 2021], the task is to classify whether an online comment is toxic or non-toxic, and the label is spuriously correlated with mentions of certain demographic identities. There are 2 labels and 8 types of the shortcut features, leading to 16 groups
Metries, model selection, and hyperpa- rameters. We report the worst-group test accuracy for each method. The groups are defined based on the labels and shorteut fea- tures. The more a model depends on the shorteut, the worse the worst-group error. Due to the label imbalance in all the datasets, variants of a-damp, a-stitch, MARG- LOG, and SD with class-dependent hyperpa- rameters; see appendix B.6.2. For all meth- ods, we use the standard Adam optimizer [Kingma and Ba, 2015] and let the learn- ing rate and weight decay hyperparamettes be tuned along with the method's hyperparame- ters. We first report results for all methods using validation worst-group aceuracy to se- lect method and optimization hyperparame- ters and early stop. For both JTT and CNC, this is the evaluation setting that is used in existing work [Liu et al., 2021, Idrissi et al., 2022, Zhang et al., 2022]. Finally, in the nuisance-free setting where group annotations are available, we select hyperparameters using label-balanced average accuracy, Appendix B.6 gives further details about the training, hyperparameters, and ex- perimental results.
CelebA
WB
Civil
ERM
72.8 + 9.4
70.8 + 2.4
60.1 0.4
CNC
81.1 + 0.6
68.0 1.8
68.8 + 0.2
JTT
75.2 4.6
1.07
69.9 + 0.4
marg-log a-damp
82.8 +..8-10 1.1
78.2+13
68.4 + 1.8
79.4 0.6
78.6 + 1.1
69.6 + 0.4
SD o-stitch
81.4
2.5
80.5 1.4
69.9 + 1.1
81.1 = 2.2
75.9 1 3.4
67.8 2.8
Table 1: Mean and standard deviation of test worst- group accuracies over two seeds for default-ERM, JTT, CNC, o-damp, d-stitch, SD, and marg-log. Every MARG- CTRL method outperforms default-ERM on every datasct. On Waterbirds, MARG-CTRL outperforms JTT and CNC. On CelebA, SD, marg-log, and a-stitch beat JTT and achieve similar or better performance than CNC. On Civil- Comments, o-damp and SD beat CNC and achieve similar performance to JTT.
5.1 MARG-CTRL mitigates shortcuts in the default setting
Here, we experiment in the standard setting from Liu et al. [2021], Idrissi et al. [2022], Zhang et al. [2022] and use validation group annotations to tune hyperparameters and carly-stopping.
MARG-CTRL improves over default-ERM. We compare MARG-CTRL to default-ERM on CelebA, Waterbirds, and Civilcomments. Table shows that every MARG-CTRL method achieves higher test worst-group accuracy than default-FRM on all datasets. Default-FRM achieves a mean test worst-group accuracy of 70.8%, 72.8% and 60.1% 1% Waterbirds, CelebA, and Civilcomments respectively. Compared to default-ERM, MARG-CTRL methods provide 5 - 10% improvement on Waterbirds, 10% improvement on CelebA, 7 10% improvement on Civilcomments. These improvements show the value of inductive biases more suitable for perception tasks.
Large LR and WD may imitate MARG-CTRL in ERM. Default-ERM's performance varies greatly across different values of LR and WD on, for instance, CelebA: the test worst-group accuracy im- proves by more than 20 points over different LR and WD combinations. Why does tuning I.R and WD yield such improvements? We explain this phenomenon consequence of instability in optimiza-
8

---

leftover group
shortcut group
full data
LR=10
WD=10
10
LR=10
WD=100
log-loss
train
test
10-1
model w/ best val WG acc
loss 0.4
10
5
10
epochs
epochs
epochs
Figure 3: Loss curves of default-ERM CelebA for two combinations of LR and WD. The combination with the larger learning rate (bluc) achieves 72.8% worst-group accuracy, beating the other combination by 20%. The model that achieves the blue run. This model achieves similar loss in both groups and the full data model suggesting that large LR and WD controls margins from exploding (higher training loss in all panels) and avoids systematically smaller margins in the leftover group compared to the shorteut group.
best validation (and test) worst-group accuracy the one epoch from
tion induced by large LR and WD which prevents the model from maximizing margins and in turn can control margins. Figure 3 provides evidence for this explanation by comparing default-ERM's loss curves for two LR and WD combinations.
The blue curves in fig. 3 correspond to the run with the larger LR and WD combination. The model that achieves the best validation (and test) worst-group accuracy over all combinations of hyperpa- rameters for default-ERM, including those not in the plot, is the one epoch 13 on the blue curves. This model achieves similar train and test losses (Rs 0.4) and thus similar margins the shortcut group, the leftover group, and the whole dataset. The red curves stand in contrast where the lower LR results in the leftover group having higher training and test losses, and therefore smaller margins, compared to the shortcut group. These observations together support the explanation that default- ERM with large LR and WD mitigates shortcuts when controlling margins like MARG-CTRL.
MARG- CTRL performs as well better than two-stage shorteut-mitigatinn methods. Two- stage shortcut mitigating methods like Correct-n-Contras (CNC) and Just Train Twice (JTT) aim to mitigate shorteuts by using a model trained with default-ERM approximate group annotations. They rely on the assumption that a model trained via default-ERM either predicts with the shortcut feature (like background in Waterbirds) or that the model's representations separate into clusters based on the shortcut feature. The methods then approximate group annotations using this default- ERM-trained model and use them mitigate shortcut learning in second predictive model. JTT upweights the loss on the approximate leftover group and CNC uses contrastive loss to enforce the model's is representations to be similar across samples that have the same label but different approxi- mate group annotations. Appendix B.6.1 gives details.
Table compares MARG-CTRL to JTT and CNC on Waterbirds, Celeba, and CivilComments, On CelebA, SD, marg-log, and o-sticch perform similar to CNC while all MARG-CTRI techniques outperform JTT. On Waterbirds, all MARG-CTRL methods outperform JTT and CNC. On CivilCom- ments, d-damp and SD perform similar to JTT and outperform CNC. CNC's performance on Water- birds differs from Zhang et al. [2022] because their reported performance requires unique large WD choices (like WD set to 1) to build a first-stage model that relies most on the shortcut feature without overfitting to the training data.
MARG-CTRL is faster than JTT and CNC. MARG-CTRL takes the same time as default-ERAN taking around 1, 20 and 60 minutes per epoch for Waterbirds, CelebA, and CivilComments respec- tively on an RTX8000 GPU. contrast, on average over runs, JTT takes around 6, 80, 120 minutes per epoch and CNC takes around 8, 180, 360 minutes per epoch. Thus, MARG-CTRL performs as well or better than JTT and CNC while being simpler to implement and computationally cheaper.
5.2 MARG-CTRL mitigates shortcuts in the nuisance-free setting
Work like [Liu et al., 2021, Zhang et al., 2022] crucially require validation group annotations because these methods push the work of selecting models for mitigating shortcuts to validation. Determining shortcuts itself is a laborious manual process, which means group annotations will often be unavail- able. Further, given a perfect stable feature that determines the label and shorteut that does not, only models that rely on the stable feature more than the shortcut achieve the highest validation

---

curacy. Thus. we introduce a more challenging setting that only provides class labels in training and validation, called the nuisance-free setting. In the nuisance-free setting, models are selected based on label-balanced average accuracy: the average of the accuracies over samples of each class.
Table 2 reports test worst-group (WG) ac- curacy in the nuisance-free setting. On all the datasets, every MARG-CTRI. outper- forms default-ERM, JTT, and CNC. On average, the MARG-CTRL methods close at least 61% of the gap between default-ERM in the nuisance-free setting and the best per- formance in table I on every dataset. In contrast, CNC and JTT sometimes perform worse than default-ERM.
CclebA
WB
Civil
ERM CNC
57.5 5.8
69.1 + 2.1
60.7 + 1.5 61.4 1.9 2.14
67.8 0.6
60.0 8.0
JTT
53.3 3.3
71.7 4.0
marg-log o-damp
77.9 1..2
66.8
70.8 0.3
65.6 1.6
SD a-stitch
70.3 10.3
1.
67.8 + 1.3
0.6
7.2
66.0 + 1.0
Table 2: Average and standard deviation of test worst- group accuracy over two seeds of MARG-CTRL, default- ERM, JTT, and CNC in the nuisance-free setting. Hyper- parameter selection and early stopping use label-balanced average accuracy. All MARG-CTRI. methods outperform default-ERM, JTT, and CNC on all datasets.
Discussion
We study why default-ERM gradient-based optimization of log-loss - yields models that depend on the shortcut even when the population minimum of log-loss is achieved by models that depend only on the stable feature. By studying a linear task with perfect stable features, we show that default-ERM's preference toward shortcuts sprouts from inductive bias toward maximizing margins. Instead, inductive biases toward uniform margins improve dependence on the stable feature and can be implemented via MARG-CTRL. MARG-CTRI. improves over default-ERM on variety of perception tasks in vision and language without group annotations in training, and is competitive with more expensive two-stage mittiggtn methods. In the nuisance-free setting, where even validation group annotations are unavailable, MARG-CTRL outperforms all the baselines. The performance that MARG-CTRL yields demonstrates that changing inductive biases can remove the need for expensive shortcut- miitrttttiiiigiingg methods in perception tasks.
Without overparameterization,, uniform-margin classifiers are unique and learn stable features only, while max-margin classifiers can depend more on shortcuts. With overparameterization,, max- margin classifiers are still unique but uniform- margin solutions are not which necessitates choosing between solutions. The experiments in section suggest that choosing between uniform margin classifiers with penalties like l improves over max margmn classifiers with by: all experiments use overparameterized models trained with weight decay and MARG-CTRI. outperforms default-FRM. Further, our experiments suggest that uniform-marge choices, unlike max-margin classifiers; appendix B.8 shows that MARG-CTRI. achieves high perfor- mance for all I.R and WD choices but ERM requires tuning.
classifiers are insensitive to the WD and L.R.
Theorem also explains how balancing may or may not improve dependence on the stable features. For example, a weighting- based approach produces the same max- margin solution as default-ERe ERM [Sagawa et al., 2020b, Rosset et al., 2003], but subsampling leads to a different solution that could depend less on the shortcut. For the latter however, models are more prone to overfitting on the smaller subsampled dataset. Similar observations were made in Sagawa et al. [2020b] but this work extends the insight to tasks with perfect stable features. Comparing ERM and MARG-CTRL on subsampled data would be fruitful.
Any exponentially tailed loss when minimized via gradient descent converges to the max-margin solution in direction [Soudry et al., 2018). Thus, theorem 1 characterizes shortcut learning for any exponentially-taie t(aa = I+a for some K > 0 D do not converge to the max max-margin classifier. One future direction to show -horteut-dependeecc results like theorem for polynomial-tailed losses, which in turn would mean that all common classification losses with a decreasing tail impose inductive biases unsuitable for perception tasks.
loss. However, losses with decreasing polynomial tails - for example,
In the tasks we consider with perfect stable features, Bayes-optimal predictors rely only on the stable feature. A weaker independence condition implies the same property of Bayes-optimal predictors even when y is not determined by sxx): y (x, z) s(x). For example, in the CivilComments dataset a few instances have ambiguous labels [Xenos et al., 2022] meaning that there may not be perfect stable feature. Studying uniform margins and other inductive biases under this independence would be fruitful.
10

---

Acknowledgements. This work was supported by the NIH/NHLBI Award R01HL148248, NSF Award 1922658 NRT-HDR: FUTURE Foundations. Translation, and Responsibility for Data Sci- ence, NSF CAREER Award 2145542, ONR N00014-23-1-2644 Google. Aahlad Puli is partly supported by the Apple Scholars AI/ML PhD fellowship.
References
Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. Shortcut learning in deep neural networks. Nature Machine Intelligence, 2(1 ((1))665-673, 2020.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. Wilds: A benchmark of in-the-wild distribution shifts. In Marina Meila and Tong Zhang, ed- itors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5637-5664. PMLR, 18 24 Jul 2021. URL attps://proceediing mlr wwwpppeesssiieeee v139/kohh11aaaaa hhmml.
Aahlad Manas Puli, Lily Zhang, Eric Karl Oermann, and Rajesh Ranganath. Out-of-distribution generalization in the presence of nuisance- iitiancce-inuuce spurious correlations. In International Con- wtt.iiewwwe//foumiiiii
ference on Learning Representations, 2022. URL
12RoR2o32T.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:1907.02880 2019.
Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks. In International Conference Learning Representations, 2020a. URL https: //openreview net/
Evan Z Liu, Behzad Haghgoo, Annie S Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. In International Conference on Machine Learning, pages 6781-6792. PMLR, 2021.
Michael Zhang, Nimit S Sohoni, Hongyang R Zhang, Chelsea Finn, and Christopher Re. Correct-n- contrast: a contrastive approach for improving robustness to spurious correlations. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Pro- ceedings of Machine Learning Research, pages nttps://proceedin
PMLR, 17-23 Jul 2022. URL mlr. press/vv66 221/6////ag222.... html.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 2018.
Badr Youbi Idrissi, Martin Arjovsky, Mohammad Pezeshki, and David Lopez-Paz. Simple data Bernhard Schölkopf, Caroline Uhler,
balancing achieves competitive worst worst-group- group-accurace and Kun Zhang. editors, Proceedings of the First Conference on Causal Learning and Reasoning, volume 177 of Proceedings of Machine Learning Research, pages 336-351. PMLR, 11-13 Apr 2022. URL https: htttps://proceedinng mmmminnsg...r.....mm..mm.....mm. mlr wwt.mm..s...................e..e press/vv77/ htt7//drrissi22. html.
Bohan Wang, Qi Meng, Wei Chen, and Tie- Yan Liu. The implicit bias for adaptive optimization algorithms on homogeneous neural networks. In International Conference Machine Learning, pages 10849-10858. PMLR, 2021.
Bohan Wang. Qi Meng, Huishuai Zhang, Ruoyu Sun, Wei Chen, Zhi-Ming Ma, and Tie- Yan Liu. Does momentum change the implicit regularization on separable data? Advances in Neural Information Processing Systems, 35:26764-26777 2022.

---

Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understanding the failure modes of out-of-distribution generalization. In International Conference on Learning Repre- sentations, 2021. URL www.hht::://poreiieieeeee
Yoav Wald, Gal Yona, Uni Shalit, and Yair Carmon. Malign overfitting: Interpolation and invariance are fundamentally odds. In The Eleventh International Conference on Learning Representa- lions, 2023. URL https:/ http::://pppneeiieee wwweenreeeeeeeeeeeeeeeeeeeeeeeee
Mohammad Pezeshki, Sékou-Oumar Kaba, Yoshua Bengio, Aaron Courville, Doina Precup, and Guillaume Lajoie. Gradient starvation: learning proclivity in neural networks. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
Yoav Wald, Amir Feder, Daniel Greenfeld, and Uri Shalit. On calibration and out-of-domain gener- alization, arXiv preprint orXiv:2/02.10399 2021.
David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribttion generalization via risk extrapo- lation (rex). arXiv preprint arXiv:2003.0066 2020.
Elliot Creager, Jömn-Herrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. In International Conference Machine Learning, pages 2189-2200. PMLR, 2021.
Victor Veitch, Alexander D' Amour, Steve Yadlowsky, and Jacob Eisenstein. Counterfactual invari- ance spurious correlations: Why and how to pass stress tests. arXiv preprint arXiv:2106.00544: 2021.
Christina Heinze-Deml and Nicolai Meinshausen. Conditional variance penalties and domain shift robustness. Machine Learning, 110())30033444 2021.
Yonatan Belinkov and Yonatan Bisk. Synthetic and natural noise both break neural machine trans- lation. arXiv preprint arXiv:1711.02112 2017.
Greg Yang and Hadi Salman. A fine-graine fine-grained spectral perspective on neural networks. arXiv preprint arXiv:I907. 10599, 2019.
Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural net- works for learned functions of different frequencies. Advances in Neural Information Processing Systems, 32, 2019.
Jason Jo and Yoshua Bengio. Measuring the tendency of cnns to learn surface statistical regularities. arXiv preprint arXiv: 1561, 2017.
Nicholas Baker, Hongjing Lu, Gennady Erlikhman, and Philip J Kellman. Deep convolutional networks do not classify based on global object shape. PLoS computational biology, 14(12): e1006613, 2018
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics learning in deep linear neural networks. arXiv preprint arXiv:1312.6120, 2013.
Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamics of gener- alization error in neural networks. Neural Networks, 132:428-4466 2020.
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. arXiv preprint arXiv:2006.07710. 2020.
Guillermo Valle-Perez, Chico Q Camargo, and Ard A Louis. Deep learning generalizes because the parameter-funntion map is biased towards simple functions. arXiv preprint arXiv:1805.08522. 2018.
Katherine I. Hermann and Andrew K Lampinen. What shapes feature representations? exploring datasets, architectures, and training, arXiv preprint arXiv:2006 12433, 2020.
12

---

Luca Scimeca, Seong Joon Oh, Sanghyuk Chun, Michael Poli, and Sangdoo Yun. Which short- cut cues will dnns choose? study from the caumeeer-space perspective. arXiv preprint arXiv22110.03095, 2021.
Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Shn-Christoppe Gagnon-Audet, Yoshua Bengio, Ioannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out-of- distribution generalization. Advances in Neural Information Processing Systems, 34:3438-3450 2021.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterization exacerbates spurious correlations. In International Conference on Machine Learning. pages 8346-8386 14466..6.. PMLR, 2020b.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Mohammad Pezeshki, Amartya Mitra, Yoshua Bengio, and Guillaume Lajoie. Multi-scale feature learning dynamics: Insights for double descent. In International Conference on Machine Learn- ing. pages 17669-17690 PMLR, 2022.
Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song. Sphereface: Deep hypersphere embedding for face recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 212-220, 2017.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label-distribution -ware aware margin loss. Advances in neural information processing systems, 32, 2019.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and geoup-sensitive classification under overparameterriztton.. Advances in Neural Information Processing Systems, 34:1099--18883, 2021.
Junhyun Nam, Hyuntak Cha, Sungsoo Ahn, Jaeho Lee, and Jinwoo Shin. Learning from failure: De-biasing classifier from biased classifier. Advances in Neural Information Processing Systems, 33:20673-20684, 2020.
Ziwei Ji, Miroslav Dudík, Robert E Schapire, and Matus Telgarsky, Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, pages 2109-2136 PMLR, 2020.
Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced metrics for measuring unintended bias with real data for text classification. In Companion pro- ceedings of the 2019 world wide web conference, pages 491-500, 2019.
Ziwei Liu, Ping Luo. Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference computer vision, pages 3730-3738, 2015.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL fitt:://arxiy wwrrsvv.voor/.eeo. abs/ 1bs.0112.6990.
Saharon Rosset, Ji Zhu, and Trevor Hastie. Margin maximizing loss functions. Advances in neural information processing systems, 16, 2003.
Alexandros Xenos, John Pavlopoulos, Ion Androutsopoulos, Lucas Dixon, Jeffrey Sorensen, and Léo Laugier. Toxicity detection sensitive to conversational context. First Monday, 2022.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Xinlong Feng and Zhinan Zhang. The rank of a random matrix, Applied mathematics and compu- tation, (85(1):689-69)) 2007.
13

---

Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL http://ppprreeee...tnttottooom Bkg6RiCqy7.
Nimit Sohoni, Jared Dunnmon, Geoffrey Angus, Albert Gu, and Christopher Ré. No subclass left behind: Fine-grained robustness in coarse gaarse- classification problems. Advances in Neural 2020.
Information Processing Systems, 33:19339-1999
Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021. URL https: / http///pppeeeeeeeeeeeeeeeee net/ muee/forumtte form? id= IQdXeXDoNtI.
14

---

A Appendix: Proof of Theorem 1, Corollary 1, and Theorem
A.1 Helper Lemmas
A.1.1 Bounding norms and inner products of isotropic random vectors.
The main lemmas of this section are lemma and lemma 4. We will then these two to bound norms of sums of random vectors and inner products between the sum and a single random vector in lemma 5. We first list some facts from [Vershynin, 2018] that will to bound the prob- ability with which norms and inner products Gaussian random vectors deviate far from their mean.
Definition 1. (Sub-Gaussian norm) For an E.V. x, the sub-Gaussian norm, or 1b2-norm, is
|xx| = inf(t > 0, 0, S 2}.
An E.. is called sub-Gaussian if is 1/2-norm is finite and for some fixed constant
p( > 1) S 2 2exp(=cf/Ixxxp
Gaussian r.V. X NN(0, has an 1/2-norm of Go for constant G V 33"
Definition 2. (Sub-exponential norm) For an rv.. x, the sub-exponential norm, or norm, is ||x|v= = in > 0, Eleep((ex//// [x/)]] s 23.
A sub-exponential r.v. is one that has finite Φ -norm.
Lemma 1. (Lemma 2.7.7 2.7.7.fro [Vershynin, 2018)) Products of sub-Gaussian random variables x. y
sub-exponential random variable with it's 1/-noorm bounded by the product of the 1h2-norm
|xyll 01 S |xle=|ly>l
Lemma 1 implies that the product of two mean-zero standard normal vectors is a sub-exponential random variable with -nomm less than G2.
Lemma 2. (Bernstein inequality, Theorem 2.8.2 /Vershynin, 2018]) For i.dd sub-exponential dom variables X1. Xá. for a fixed constant c
(2e) and K = ||x||æ
(-omin { 12 K2d K 5
p
>
2exp
Next, we apply these facts to bound the sizes of inner products between two unit- variance Gaussian vectors.
Lemma 3. (Bounds inner products of Gaussian vectors) Let u, be d-dimensional random vectors where each coordinate is an i.id standard normal r.v. Then, for any scalar e > O such that < G2 /d. a fixed constant (2e)
2
(Iu > eva) < 22exp
-c
2 G
This follows from:
0v2 exp( 1xpp--2//2r) /2/22²) exp(=2/pp)))
100
1
exp
[x² 2 (t² (t- 20
dx
o 0v2
20
1
TT222
$2
2m
(12 [2-2021
(12 - 20
V/ (t2 - 20
2n²
t2
2
i < 1(12
-0
= 80² < 312
inf 80² - 33(?)
[12
20
3
15

---

Proof. First, the inner product is u'v Σx u. it is the sum of products of i.id. standard normal r.v. 1). Then, by lemma 1, each term the sum is sub-exponential r. with Φ/ -oom bounded as follows:
K VllVel S | = G
(6)
We can apply Bernstein inequality lemma sub-exponential r.v. the inner product and then upper bound the probability by replacing K with the larger G² in eq. (6)
1 K2d K })
12
1 1
)
p (Iu T v 1) s 2exp
-emin
< 2exp
-emin
G G2
Substituting = cvd d in the above gives us:
(11 v > evd) s 2exp (-emin { 2d cvd G G2
Using the fact that 2 Gd to achieve the minimum concludes the proof:
? .vd
2d evd
6
c cs GVVV = ? GG = G I
min
G
G G
G4
Lemma 4. Let x be a Gaussian vector of size d where each element is standard normal, meaning that |x>l| G. Then, for any t > and fixed constant (2e)² the norm of the vector
concentrates around vd according to
p
( |x|||
Vd >1) < 2fxx(-off/0)
Proof. Equation 3.3 from the proof of theorem 3.1.1 in [Vershynin, 2018] shows that
x(||x||| vd 1) S exp( (aapp((fffpp (maxx [|x; llo.))).
As has i.i.d standard normal entries, max; ||x; 1l G. concluding the proof.
A.1.2 Concentration of norms of sums of random vectors and their inner products
This is the main lemma that we will use in proving theorem 1.
Lemma 5. Consider a set of vectors V = {o,} where d, E Rd of size Ty 2 where each element of each vector is drawn independently from the standard normal distribution N(0,, 1). Then, for fixed constant (2672 and any e (0, G2 /d) with probability 2 2exp(- g))
1
Σ
6
Va+c
VTV
iEV
and with probability 2 4Tv exp(-e'
(G))
vo, EV
8,1
Σ 8,
2 dl - 30 Tyd
(8)
iEV
Further, consider any set U of vectors U = (5.) of size Tü, where each vector also has co- ordinates drawn i..d from the standard normal distribution N(00 1). Then, with probability 2 2T, exp(=ee )))
(o,
ScVTvd.
vS, EU
(9)
KEV
By union bound, the three events above hold at once with a probability at least 1 2(2Tv T, + 1) @xex(pe2 (T)
Proof. We split the proof into three parts each for eqs. (7) to (9).
16

---

Proof of eq. (7). As 8 is a vector of random i.id standard normal random variables, note that TTv E, o; is also vector of i.d standard normal random variables. This follows from the fact that the sum of Tv standard normal random variables is a mean-zero Gaussian random variable with standard deviation vTv. Thus dividing by the standard deviation makes the variance 1, making standard normal.
Then, applying lemma 4 with t = gives us the following bound:
[
6:
c sp
Σ
5.
Vd > $ 2cxp(-oo//o
Proof of eq. (8) We split the inner product into two cases: Tv and Tv 2 2.
Case TV = 1.
First note that due to lemma 4,
VjEV,
P (16,1 < vd ()
S
|ل,ل||
vd >() S 2expf -ct)))
Then, the following lower bound holds with probability at least
Vj EV,
6, Σ 6
||
2 (vd c)
2 - 2eVd
2d 3e Tvd,
To summarize this case, with the fact that 1 - that
2 -4Tv expl- -ep(-)))/')) we have
VjEV,
8, Σ 8
2d d- - 3e Tvd.
iEV
with probability at least 4Tv exp((=ee/pe
Case Tv 2 First note that,
AjEV
6
Σ
5:
-11,,1
55. Σ
6
ieV
iEV
For each of the Tv different 8j's, using lemma 4 bounds the probability of the norm | being larger than vd
p (16,11 < Vd - e) sp ||ر,|| va >
>c)
s 2 2exp(-<2/c"))
In the case where Tv 2 2, we express the inner product of vector and sum of vectors as follows
8;
TT
85
Σ 6
$EVi
iEV
and noting that like above, apply lemma 3 get
JTv-I
Eiev,
8; is vector of standard normal random variables, we
2
ViEV V
p 8
Σ
6.)
8,
2 2ev(Tv 1)d
S 2eep
-c
G
sEV
Putting these together, by union bound over V
(K0:
(18)] < vd - or
p YjEV
Σ 6;
2 ev (Tv 2cv(Tv - l)d
iEV
17

---

(
)
|, vd
) +D
85 Σ o;
2cv(Tv l)d
p
JEV
iEViss
2
- Σ
2 exp
-0 -0
+ +2exp
G1
jEV
S 47y exp
G4
Thus, with probability at least
4Tv exp (-0 none the events happen and
VjEV
δ 5o 8,
|0, + ôj Σ d;
iEV
VEV,
2 (Vd - c)² <v/ (Tv 1)d
22V + 2 - Ev (Tv - 1)d
2cv (Tv 1)d c/ (Tv 1)d
2 3e Tvd
Thus, putting the analysis in the two cases together, as long as Tv 2 1
AjEV
ブ, 6 iEV
2
30 Tvd.
with probability at least
47v exp
Proof of eq. (9) Next, we apply lemma 3 again to the inner product of two vectors of i.i.d standard normal random variables:
VjEU
j5: vTv
Σo:)
6:
2 2evd
< <2xxp(-a"(0")
iEV
By union bound over U
2 2
p VjEU
6/ VTv
5
<2T, exp(-<e/or))
iEV
Thus, with probability at least 2T, exp
(-c
the following holds, concluding the proof
VJEU
(,, VTV
Σ 8, sevd. TV
Lemma 6. Let (X:.y be a collection of d dimensional covariates x; and label y, sampled according to Pp in eq. (1). The covariates x; = [+ where + B in the middle coordinate for Sshonca and B for i E Siefower The dual formulation of the following norm-minimizatin problem
W stable = arg min
y + w + l|Weel2
w
s.l. i E Syhorcut
wy + Bw, + w.y, >
s.t. i Sieftoer
wy Bw, + w N >
18

---

w 2 Bw:
is the following with <T = -- 1, 0
- - X +
max X20
(10)
where X is matrix with y;x; as its rows.
Proof. We use Lagrange multipliers À E R", E I to absorb the constraints and then use strong duality, Letting ( 1, 0d- "], X be a matrix where the ith row x,Y,
min w
||w|| 2
s.t.
Xw
SWw w 20
has the same solution as
max X20
min
[||| (Xw 1) v5 w
(11)
w
Now, we solve the inner minimization to write the dual problem only terms of X, v. Solving the inner minimization involves solving quadratic program, which is done by setting its gradient to zero,
(|w|12 - (Xw - - 2- u5Tw) 2w X x vs
W 2(Cu + (
Substituting w [[(Cv + X A) in eq. (11)
||| 1 (Xw 1) us Tw w=
7
1
[c + x A|1² - 1 (( ( 1)) 1
- XTA)
(CV
[ + x2113- ([X((V+ xx - -1) 1 111111
1
_ T
2
11s
X 2112 x1112-
((((TTA) a 1
(X(CV)
T 1 + T
_ T
1
4
2
1
+
+
111
2 (XXXX 1))_ x=
111111 + Txx
1
+1
4
2
1
11
A11
(((TA)TxX) x x
-
1
1|12 +us xT)
+1
2
115 + + A11
(IIX x||2 ||_||2 + Tx
x T + +1
2
11 + X A11
~llcv + x1
- + x 2112 +
A.2 Shortcut learning in max-maree max-margin classification
We repeat the DGP from the linear perception task in eq. (1) here.
y Rad, z (z y | y y) (p = -y 1 y) -1))
8 &~1,011)))) x (B
z, 8].
(12)
Theorem 1. Let w be the max-margin predictor on n training samples from eq. (12) with a leftover group of size k. There exist constants C, C2, No >
such that
integers
0. 10
(13)
19

---

A d 2 C1 k log((3))
(14)
R > C2 C2
(15)
with probability at least
3m over draws of the training data, holds that Bw > w
Before giving the proof of theorem I, we first give the corollary showing overparameterization is not necessary for theorem to hold.
Corollary 1. For all No where the constant No is from theorem -- with scalar (0,
such that the dimension Tn < n, theorem holds.
Wk
min
10 Ci log S
a linear model trained via default- ERM yields a predictor w such that Bw? > wy-
Proof. We show that for a range of k. for all 2 theorem holds for 2 No, d = C₁ (og(3n) and
No theorem holds for some d < n. Note that
A4- < n
10
Setting d S rn for some E (0, 1) such that d < n means that theorem holds if
Tn
Cjk log(3n) = S mn = S
C₁
log(3n)
Absorbing this new upper bound into the requirements on h for theorem hold, we get that for any scalar n > No.7 (0, 1), theorem holds for
Vk < n x min
10 C, log(3n)
In turn, even though d n, a linear model trained via default-ERM converges in direction max-mane max-margin classifier such that w with Bw
w
Proof. (of theorem 1) We consider two norm- norn-minimization problems over w, one under constraint Wy 2 Bw, and another under Wy Bw,, We show that the latter achieves lower norm and therefore, max-margin will achieve solutions wy Bw.. The two minimization problems are as follows:
W sttable = arg min
2 w² + ||ell
W Wsborteut = arg min
m + w² + //
s.t. E Sahorteu
wy + Bw: + y.
s.t. E Sahrrtuut
wy + Bw: + w y.y >
s.t. E Sjetover
wy Bw, + w w.y,d, >
i E Sjetover
wy Bw, + w w.y,d; >
Wy 2 Bw:
W Bw
(16)
(17)
From eq. (16), any that satisfy the constraints of the dual maximization problem will lower bound the value of the optimum of the primal, || 2 Waable From the eq. (17), substituting a guess in Whortcut that satisfies the constraints yields upper bound, || | Wahceteut- The actual
computation of the bounds W Whoneutt W Watable is in lemmas 7 and 8 which are proved in appendix A.3 and appendix A.4 respectively. We reproduce the lemmas here for convenience.
Lemma. (7) Consider the following optimization problem from eq. (16) where samples of x;: Y; come from eq. (1) where X; Rdd
Wstoble
arg min
Wyy + w² + +|/wel?
w
s.f. E Schorten
Wy + Bw, + w.y,d, >
(18)
s.t. E Stepover
wy Bw, + w w.y,d. >
Wy 2 Bw
20

---

Let = Sttetoverl > 1. Then, for a fixed constant [2e]a
with any scalar < v with probability
at least 2 exp(pcc /c//)/))))))))))) /c and integers M E [
sstable
W stable
(vā+e)
4
2MK
Lemma. (8) Consider the following optimizaation problem from eq, (16) where n samples of x; V come from eq. (1) where X, R
W arg min
wy + ww² + +|/w?l?
s.t. E Sshortew
wy + Bw, + w. y,o;
(19)
E Siefover
Wy Bw, + w. y;d; >1
Wy < Bw
Let /Stgtover 1. Then, for a fixed constant c [2c] with any scalar < 3/2 1/ Vd, with probability at least 1 2(2k: + (n k) + 1) exp( ). for
2
d-dev/dd
(1+ dk
shorteut
W shorteut
+2 c)2
B²
Together, the lemmas say that for any A integers M E [1, 1 and < $ // E. with probability 2 2 2exp(-22 (c()-c)))))
stablel|
2
W sstable
(va+c)²
4
2M
and with probability least 1 2(2k + (n lt) + 1) (x for d- kd 0,
(1+
2
W Whoortcur
2
W shorecut -2k(VV++))+
B
First, we choose 2² 2 - log(3n). This gives us the probability with which these bounds hold: as l 0.1n have 2 and
1 2(2k + (n k)) 2) exp (xpp-ce-
c
= 1 - 2(n + A: 2)
G7
2 1 - 2 3n
exp( - log(3n))
2
1 exp log(3n) + log (3n))
1 exp( log(3n))
3n
Next, we will instantiate the parameter and set the constants C1, C2 and the upper bound on in theorem to guarantee the following eq. (separation inequality):
W shortcct = =>} + (I+
1
W
Waablee
B²
(vā+e)²
+
2MK
(separation inequality)
which then implies that Wshortcut | concluding the proof.
21

---

Invoking the conditions in theorem 1 and setting the upper bound on k. We will keep the as for simplicity of reading but invoke the inequalities satisfied by log(3n) from theorem
3 constant C1,
d 2 C2 log(n)).
Now we let C1 = 2 G4 002 for a constant CE (0, 3) such that
2 2 log(3n) < c
k = <<<o _ and kkdd < Cd.
(20)
We next find a C E (0, such that eq. (separation inequality) holds with M 5, which upper bounds kt
k
n 10
M
k<
2k
2M
10
Simplifying W shorteut and W Wstable- ity), we compare simplified strict upper bound on the LHS Wstortut and simplified strict lower bound on the RHS W stable
To actually show Wahorteut < W Wattabi in eq. (separation inequal-
For the simplification of the RHS W stable of eq. (separation inequality), we will use the fact that d 2
2 log(3n)k: Given the assumption n > No. choosing No to be an integer such that 1og(3 >
40e means that log(3n) >
40aC2 and we have
G
d
1 d
80
> 8
> 4
(21)
k
10k
2 10k
which gives us, for M
1
W stable
(22)
(va+e)*
+
2M/
1
(23)
(vā+e)²
4 +
10k
1 d
(vā ((++c)) x)²
2
[4 < 20k
<
from eq. (21) }
(24)
3 (va+c)²
2
10k
2
10k
20k
(25)
3 3(vd + c)2
20k
Cvd
(0 <
from eq. (00) }
(26)
3(vd + Cu 22
Vk
20k
(27)
3(1 + yd
20k
1
(28)
3(1 + Cy
Now, we produce a simpler upper bound on the first part of the LHS of eq. (separation inequality): recalling that 7 2
4ev and substituting in the upper bounds on c,
2( 22vV++ +c) d - leVkd
2 kk( Vd + +c²
2
(Va C 1
{E < CVd Vi
4
k
from eq. (20)
d 4Cd
4k (1+ C
2
d 1- 4C'
'The | comes from requiring that e < 1 from lemma 8.
22

---

4k 1+0
[A:1) 1}
(29)
d 4C
Next is simpler upper bound on the second part of the LHS of eq. (separation inequality). Again
2 with 7 d-devkdd
2
2ey 2
1 + YEV dk
1 +
d- levkd
B²
B
+
2Cd 4Cd
B²
+ 20
I-16
B²
Now setting
1 + 20
B > V2
1-16
4k d
1+C
I-1C
gives the lower bound on B from theorem 1:
d B C2
1 + T-46
20
(1 (1-20) 2C)
C2VE
where
C2
K
v2
I+C
V2(1 CC)
1-10
Formally,
B>COV d
1
20 T TC4C
4k d
1 )) T 4C)
2
1 4k
1 C 2
B> CoV
(30)
B²
2
2
1 4C'
By combining the upper bound from eq. (30) and the upper bound from eq. (29), we get an upper bound on the whole of the LHS of eq. (separation inequality), which in turn provides an upper bound
on W W
W shortcuut =>2k(Vd++e? +)²+ (1 yevakk
3 4k
(1 (1+0)
3 ((++))
B
2 d
1 11-4C 4C
S
2 d
11-4C 4C
because l: > 1. Note the upper bound is striet.
Concluding the proof. Now, we show that a C exists such that the following holds, which implies W Whortcut < W Stablee which in turn implies eq. (separation inequality) and the proof concludes:
4k d
(1 C)
20h
W abbortcut
<
Watble
4C
3(1 + Cydd
The above inequality holds when
(1 (1+ 4C
20
10
6
< 3(1 + CF
(1+0)²
4C) 5. 0. V 999
The right hand side holds when the quadratic equation (1 + 0)² v 10 4C' is non-positive, which holds between the roots of the equation. The equation's 's positive solution
-3 + 110
C
R 0.008.
3+ 2 + / 5(8 33/10)
23

---

Setting C' to this quantity satisfies the requirement that C' E (0, 30.
Thus, C exists such that eq. (separation inequality) holds which concludes the proof of theorem for the following constants and constraints implied by C and M = 5:
C2 11 2C)
G
Ci
k
(2(1+
cC2
10
where the noom of a standard normal r.v. and is the absolute constant from the Bernstein inequality in lemma 2.
A.3 Lower bounding the norm of solutions that rely more on the stable feature
Lemma 7. Consider the following optimization problem from eq. (16) where n samples of Xi Y come from eq. (1) where X, E :
stoble
arg min
Wy w + +||wel?
w
s.t. E Sshortent
Wy Bw, + w y,o;
(31)
s.t. E Siefover
Wy Bw, w y,o:
Wy 2 Bw
Letk = SSepover > 1. Then, for a fixed constant c [2e]a.
with any scalar e < Vd, with probability
least 2 eepp(=00 /c=))=/))))))))))))))))))))))/ and's integers M [
1
stuble 2
W stable
(vd+e)
4+
2M
and X is d Proof. By lemma 6, the dual of eq. (16) is the following for < 1-B, matrix with rows y,
max A X20
1
1 + X A112 +1
(32)
Now by duality
1
- ||c X XlI2 + 1
W stable
max A20,220
which means any feasible candidate to eq. (32) gives lower bound on |asttelll 11
Feasible Candidates for X, We now define set U C [n]] and let X; _ > 0 for E U and otherwise. For M (1, []. we take 2M samples from the training data be included in U. Formally,
U Stetwver U (2M 1)k a random samples from Satorteuts
which gives the size [U| = 2MK. Then, we let v/ = a 2M 0.
2(M-1)
Note that for the above choice of X, X T is sum of the rows from U scaled by [ि Adding up rows from Sietioer and rows from Sshorteut cancels the Bs and, so in the B is accumulated |U] - 2k = 2(M 1)k times, and so
X A
U
2h
8 B.
a Eo,
aB 2(M - 1)
Σ 5
|0|
UU
2M
U
iEU
iEU
As X has f0 on |0|| elements and otherwise.
A =1
-(M
As we set
a 2M 2M
2(M 1)
2(M 1)
2(M 1)
v + T
-aB
+
B, a
+ a,
+
Σ 5
2M
2M
2M
U
(33)

---

2(M -1)
0 a
(34)
2M
10
2(M
-1)
I XTA|I A|I2
0, a
+
Σ
8,
(35)
2M
U
NEU
2(M 1)
a
0:
8
(36)
2M
iED
For the chosen values of v, the value of the objective in eq. (32) is
a
2(M 10M-111 1)
Σ 8
0, 1
+
(37)
2M
10
iEV
Letting
0, (1+
2(M - 1)
8
2M
iEU
the objective is of the form a
T To maximize with respect to a, setting the derivative of the
objective w.r.t a gives:
2oT
2
TT
4T
a=
1
r
This immediately gives
2 2
W stable
r
and we lower bound this quantity by upper bounding
By concentration of gaussian norm in lemma 4, with probability least 1 - x
6
d
S V10
(Vd+e).
U
VEU
In turn, recalling that |0| = 2M
(vā+c)
rs (2(M - 1) + 2M)
2
vd+te
vd+e
<
<
<
2M
VITT
VIUI
2M
The upper bound on I gives the following lower bound on |tablel
I stabte||
2 >
F 2 (Vd+e))
4 4+
2MF
A.4 Upper bounding the norm of solutions that rely more on the shortcut.
Lemma 8. Consider the following optimization problem from eq. (16) where n samples of x; Y come from eq. (1) where X, Rd:
shortene arg min
W w + l|we
S.I. E S Shomeeu
Wy Bw: + w y,o;
(38)
E Syntower
Wy Bw, + w y, >
W < Bw
25

---

Let k |Stetover 2 1. Then, for a fixed constant c= [26]2 with any scalar c <
1/2 3 3V < Vd, with
probability least
2(2k: (n k)) 1) exp((ccx),, for
2
d-1evid
(1 (1+ 2
W shortour
1| $ W shortent
= 222k( =>²k(vd+ c)²
B²
Proof. Let lo /Steooerr- The candidate will evaluate the objective for is
B
W
Σ 8zōj JESunoeer
(39)
B
High-probability bounds on the margin achieved by the candidate and norm of w The mar- gins the shorteut group and the leftover group along with the constraints follows:
B B
Vj E
Shorteut
my 0
8
Σ
y,o,
21
IE SE
(40)
3 B
Vj Steftover
y,ōj.7
Σ
y,di
1.
&E
Due to the standard normal distribution being isotropic, and y, E {-1,1), v has the same distribution as öy. Then, we apply lemma 5 with Siatoovers U Sshorteut which means TV and Ta (n k) to bound the margin terms in eq. (40) and ||w|]' with probability at least
1 1 1(2k + (n k) + exp( -c G7
Applying the bound in eq. (9) in lemma 5 between sum of vectors and different i.d vector,
Vjj E
Ssbortcut
Σ y,o,)
$ yovkk
(41)
SE SEaaaee
Applying the bound in eq. (8) from lemma 5
Vj Sieoover
Σ
y,o; (d 3 3evkd)
(42)
VESweoer
The margin constraints on the shortcut and leftover from eq. (40) respectively imply
3 + 7 (d 3c Bevkit kd 2
B 7 yev dk
We choose 3 - + 7e / dk, which implies an inequality that y has to satisfy the following, which
is due to d - -33c 3kc/kdd > 0.
-(1 + yev dk) + (d- 1--3ev kd
2 4ev kd
21
Now, we choose
2
==
4eyhd
Computing the upper bound on the value of the objective in the primal problem in eq. (17)
The feasible candidate's norm ||w||2 is an upper bound on the solution's 's norm W and so
g2
Iw Shorteut 1 S |/|
B
32
7
Σ
=
22
VT
Σ
8
B2
JE Sthte
SE
26

---

3n over By lemma which we invoked,
J/4 Vk jESmee
Σ
6,)
(V)+
To conclude the proof, substitute 3 + dk and get the following upper bound with 7
2
d-3ev/dd
W Wsshortu/ 2 <>>k(vt+ + B² = -VVV++++ (1+ 2
8
B²
A.5
Concentration and intuition behind theorem 1
Concentration of k: around (1 - p)m. Denote the event that the ith sample lies in the leftover group as I; then E|A]] = p and leftover group size is k = E, I. Hoeffding's inequality (Theorem 2.2.6 in [Vershynin, 201 2018]) shows that for any O. k at most (1 p)n + tyn with probability at least 1 - exp( )
(k (1 p)m tvn) = p Σ (1: - (1- tva
E(: -ET,)) > VVn I Sexp(-2f'
Letting 0.9 V
log ön and t Vlog 3n, gives
p ( - (1- p) > t/n) p 0.1n /n log 3n
Vlog 3n 3n
(k- 0.1n > 0)
exp( 2t
= exp( log 3n).
3n
1
3n
To connect p shorteut learning due to max-margin classification, take union bound of the event that < 0.1n, which occurs with probability at least 1 3n and theorem which occurs with probability at least - 3n This union bound guarantees that with probability at least - 2 sampling the training data, max-margin classification on n training samples from eq. (1) relies more on the shortcut feature if is above threshold; and this threshold converges to 0.9 at the rate of /Log 3n/n.
A.6 Bumpy losses improve ERM in the under-parameterrzeed setting
Theorem 2. Consider n. samples of training data from DGP in eq. (1) with d < n. Consider a linear classifier fo(x) x x such that for all samples in the training data y,w x; for any
b E (0, xo). With probability I over draws of samples, = [0, 0d-2].
Proof. Letting X be the matrix where each row is y,,, the theorem statement says the solution w
Xw 61
(43)
First, split w = [w",, w., w Equation (43) says that the margin of the model on any sample satisfies
y(w") x= wiy² + wwiz + y(w",)
y(w",) To b wi,y² w
27

---

We collect these equations for the whole training data by splitting X into columns: denoting Y, Z as vectors of y, and z; and using to denote element wise operation. split X into columns that correspond to y, z and ó respectively as X Y Z X&). Rearranging terms gives us
- Y Z wi1 + Xow3 b1
Xaw3 (6 w 1 - Z.
The elements of Y. . Z lie in {-1, } and, the shortcut feature does not always equal the label, the elements of Y are not all the same sign.
Solutions do not exist when one non-zero element exists in (6 w 1 w Y Z By definition of w
Xaw3 = (b- w w Z.
Denote r = (b (--ww)1- w Z. and A = Xs. Now we show that w.p. 1 solutions do not exist for the following system of linear equations:
Aw = r.
First, note that A = X5 has y,o, for rows and as y; V; and y, E (-1,1), each vector y,o, is distributed identically to a vector of independent standard Gaussian random variables. Thus, A is a matrix of IID standard Gaussian random variables.
Let U denote D 2 indices such that the corresponding rows of A form matrix D 2 D 2 matrix and To has at Ieast one non-zero element; let Ay denote the resulting matrix. Now Au is D - 2 x D - 2 sized matrix where each element is standard Gaussian random variable. Such matrices have rank D 2 with probability I because square singular matrices form a measure zero set under the Lebesgue measure over R D-2xD "[Feng and Zhang, 2007].
We use subscript -- to denote all but the indices in U. The equation Aw implies the following two equations:
Ayw As Ag is has full rank (D - 2), A = ry admits a unique solution w # -ecause TV has at least non-zero element by construction. Then, it must hold that
Auw T-U.
A. -
(44)
For any row T E A-u. (44) implies that v w equals fixed constant. As v is a vector of iidd standard normal random variables, v. w is a gaussian random variable with mean Σ(w?) and variance |/2, Then with probability 1, T w will not equal constant. Thus, w.p.1 A r-u is not satisfied, which means w.p.1 there are no solutions to Aw = r.
Case where - (b-w))) w when w O. Fach element in (b w w Y Z is either b - wy + w or b wy w Thus,
Z is zero element-wise As has rank D 2, X = 0 only
{
b w w 0,
(b-w w w Z =
(45)
b - w w
Adding and subtracting the two equations the right gives
2(b w = and
2w
Thus, w3 = 0, :. = 0, wyy
B
Appendix: further experimental details and results
B.1 Default-ERM with g-reeularrization
In section 3, we show default-ERM achieves zero training loss by using the shortcut to classify the shortcut group and noise to classify the leftover group, meaning the leftover group is overfit. The usual way to mitigate overfitting is via fy-regularization, which, can posit, may encourage models to rely on the perfect stable feature instcad of the imperfect shortcut and noise.
We train the linear model from section with default-FRM and egreguulaiization - implemented as weight decay in the AdamW optimizer [Loshchilov and Hutter, 2019] data from eq. (1) with
28

---

Accuracy
Train Loss
Test Loss
FRM. To
10"
ERM, -1-008, Y
00
ERM, -e-008.
ERM, Y=Z
1c.08,
10-4
10
10-2
10-12
10-3
20
50000 spochs
100000
50000
100000
50000
100000
epochs
epochs
Figure 4: Default-ERM with fz-regularization with penalty coefficient of À 10-8 achieves a test accuracy of ~ 50%. outperforming default-ERM. The right panel shows that l egrreullarization leads to lower test loss on the minority group, meaning that the regularization does mitigate some overfitting, However, the difference between the shorteut and leftover test losses shows that the model still relies on the shortcut.
3
log-loss
Loss value
2
a-damp sd
1
marg-log
0
a-stitch
0
2
4
Margin, yfa(x)
Figure:3 5: Comparing log-loss with MARG-CTRL as functions of the margin. Each MARG-CTRL loss has "bump" which characterizes the loss function's transition from decreasing function of the margin to increasing one. These bumps push models to have uniform margins because the loss function's derivative after the bump is negative which discourages large margins. The hyperpa- rameters (temperature in o-damp or function output target in MARG-LOG.) affect the location of the bump and the slopes of the function on either side of the bump.
= 800, B 10, 1000. Figure 4 plots accuracy and losses for the fz-regularized default-FRM with the penalty coefficient set to 10 ; it shows that fz-regularization leads default-ERM to build models that only achieve 50% accuracy.
For smaller penalty coefficients, default-ERM performs similar to how it does without regularization, and for larger ones, the test accuracy gets worse than default-ERM without regularization, We give an intuitive reason for why larger & penalties may lead to larger reliance Due to the scaling factor B = 10 in the synthetic experiment, for a fixed norm budget, the model achieves lower loss when using the shorteut and noise compared using the stable feature. In turn, heavy le-rgullarization forces the model to rely more on the shorteut to avoid the cost of larger weight needed by the model to rely on the stable feature and the noise.
the shortcut feature.
B.2 Margin control (MARG-CTRI)
In fig. 5, we plot the different MARG-CTRL losses along with log-loss. Each MARG-CTRL loss has "bump" which characterizes the loss function's transition from a decreasing function of the margin to an increasing one. These bumps push models have uniform margins because the loss function's derivative after the bump is negative which discourages large margins. The hyperparameters - like temperature in a-damp function output target in MARG-I.OG affect the location of the bump and the slopes of the function on either side of the bump.
B.3 MARG-CTRL on linear model
In fig. 6, we compare default-ERM to r-stitch. In fig. and fig. 8, compare SD and MARG-LOG respectively to default-ERM. The left panel of all figures shows that MARG-CTRI achieves better test accuracy than default-FRM, while the right most panel shows that the test loss is better on the leftover group using MARG-CTRL. Finally, the middle panel shows the effect of controlling margins
29

---

Accuracy
Train Log Loss
Test Log Loss
100
3
ERM, Tr
o-stitch, Y=
75
0-stitch, Y
2
a-stitch,
ERM,
50
a-stitch, Te
ERM, Y=Z
1
0
5000 epochs
10000
5000 epochs
10000
0
5000 epochs
10000
Figure 6: linear trained with o-stitch depend on the perfect stable feature achieve perfect test accuracy, unlike default-ERM. The middle panel shows that ø-stitch does not let the loss on the training shortcut group to go to zero, unlike default-FRM, and the right panel shows the test leftover group loss is better.
Accuracy
Train Log Loss
Test Log Loss
100
3
ERM, Tr
SD, Y
75
ERM, Te
2
SD, Y =
2
SD, Tr
ERM, Y Y
50
Te
ERM, Y=Z
25
0
5000 epochs
10000
10000
0
5000 epochs
10000
epochs
Figure 7: A linear model trained with SD depend on the perfect stable feature to achieve perfect test accuracy whereas default-ERM, performs worse than random chance. The middle panel shows that SD does not let the loss the training shortcut group to go to zero, unlike vanilla default-ERM, and the right panel shows the test-loss is better for the leftover group.
in training; namely, the margins on the training data do not go to co, evidenced by the training loss being bounded away from Depending on the shortcut feature leads different margins and therefore test losses between the shortcut and leftover groups; the right panel in each plot shows that the the test losses on both groups reach similar values, meaning MARG-CTRI. mitigates dependence on the shortcut. While default-FRM fails to perform better than chance (50%) even after 100, 000 epochs (see fig. 1), MARG-CTEL mitigates shortcut learning within 5000 epochs and achieves 100% test accuracy.
B.4 MARG-CTRL vs. default-ERM with a neural network
With 100 and B 10 in eq. (1), train training distribution. The two layer neural network has 200 unit hidden layer that outputs a scalar. Figure shows that neural network trained via default-ERM fails cross 50% test accuracy even after 40, 000 epochs, while achieving less than 10 10 in training loss.
layer neural network on 3000 samples from the
Accuracy
Train Log Loss
Test Log Loss
100
ERM,
marg-log, Y
80
marg-log, Y
2
marg-log, marg-log, Te
ERM, Y=z
60
ERM, Y
1
40
0
5000 epochs
10000
5000
10000
0
5000 epochs
10000
epochs
Figure linear model trained with MARG-LOG depend on the perfect stable feature achieve perfect test accuracy whereas default-FRM performs worse than random chance. The middle panel shows that MARG-LOG does not let the loss on the training shorteut group to go to zero, unlike default-ERM, and the right panel shows the test-loss is better for the leftover group.
30

---

Accuracy
Loss
100
109
80
10
60
train test
10-6
40
10-9
20
epoch
1e4
egoch
1e4
(a) Average accuracy and loss curves.
Accuracy
100
2.0
75
Tr, Y
Tr, Y=z
Te,
50
Tr, Y
1.0
Tr, Y=2
Te, Y=2
Te, y
25
0.5
0
0.0
1000
2000
3000
4000
1000
2000
3000
4000
epochs
epochs
(b) Accuracy and loss on shortcut and leftover groups.
Figure 9: Training a two-layer neural network default-ERM on data from eq. (1). The model achieves 100% train accuracy but < 40% test accuracy even after 40, 000 epochs. The plot below zooms in on the first 4000 epochs and shows that the model drives down loss on the test shortcut groups but not on the test leftover group. This shows that the model uses the shortcut to classify the shortcut group and noise for the leftover.
In fig. 10, we compare default-ERM o-stitch. In fig. 12 and fig. 13, compare SD and MARG-LOG respectively to defaultERM.. The left panel of all figures shows that MARG-CTRL achieves better test accuracy than def,ult-ERM, while the right most panel shows that the test loss is better on the leftover group using MARG-CTRL. Finally, the middle panel shows the effect of controlling margins in training; namely, the margins on the training data do not go to co, evidenced by the training loss being bounded away from 0.
Accuracy
Train Log Loss
Test Log Loss
stttich,, Y
80
Y
1.5
ERM, Y ERM, Y
1.5
60
ERM, To
o-stitch,
40
o-stiich
0.5
0.5
20
0.0
2000 epochs
apochs
epochs
Figure 10: A neural network trained with o-stitch depend the perfect stable feature achieve perfect test accuracy, unlike default-ERM. The middle panel shows that -sstich does not let the loss on the training shorteut group go zero, unlike default-FRRM and the right panel shows the test leftover group loss is better.
B.5 Spectral decoupling for linear model the linear DGP in eq. (1).
We first show that linear classifier trained with SD achieves 100% test accuracy while default- ERM performs worse than chance on the test data; so, SD builds models with more dependence on the stable perfect feature, compared to Empirical Risk minimization (ERM). Next, we outline the assumptions for the gradient starvation (GS) regime from Pezeshki et al. [2021] I] and then instantiate it for linear model under the data generating process in eq. (1), showing that the assumptions for the GS GS-regime are violated.
Figure shows the results training a linear model with SD on training data of size 1000 sampled as per eq. (1) from Pp= with d 300; the test data also has 1000 samples but comes from Pp=0.1-
31

---

Accuracy
Log
Test Log Loss
100
2.0
o-damp, Z
2.0
80
o-damp. Y
ERM,
1.5
ERM, Y-Z
1.5
60
ERM,
ERM, Y
a d-damp,
1.0
1.0
40
didamp,
20
0.0
0.0
0
1000
2000 opochs
3000
4000
1000
2000 opochs
3000
4000
1000
2000
3000
4000
opachs
Figure 11: A neural network trained with o-damp depend on the perfect stable feature achieve perfect test accuracy whereas default-ERM performs worse than random chance. The middle panel shows that a-damp does not let the loss on the training shorteut group to go to zero, unlike vanilla default-FRM, and the right panel shows the test-loss is better for the leftover group.
Accuracy
Train Log Loss
Test Log Loss
2.0
SD. Y-Z
2.0
80
50. Y Y
ERM,
1.5
ERM, Y-z
1.5
60
ERM, To
Y+2
1.0
40
SD, Te
0.5
0.5
20
11
1000
2000 epochs
4000
1000
2000
3000
4000
1000
2000
3000
4000
apachs
epachs
Figure 12: A neural network trained with SD depend on the perfect stable feature to achieve perfect test accuracy whereas default-ERN performs worse than random chance. The middle panel shows that SD does not let the loss on the training shortcut group to go to zero, unlike vanilla default-ERM, and the right panel shows the test-loss is better for the leftover group.
Figure shows that SD builds models with improved dependence on the perfect stable feature, as compared to ERM, to achieve 100% test accuracy.
B.5.1 The linear example in Equation (1) violates the gradient starvation regime.
Background on Pezeshki et al. [2021]. With the aim of explaining why ERM-trained neural net- works depend more on one feature over more informative one, Pezeshki et al. [2021] derive solu- tions to fz-regularized logistic regression in the NTK; they let the regularization coefficient be small enough for the regularized solution to be similar in direction to the unregularized solution. Given samples y', x², let Y be diagonal matrix with the labels on its diagonal, X be matrix with x" as its rows, and y (X, 0) = [o(X) be the n-ddimensional vector of function outputs where each element is 8 = fe (x'). In gradicnt-bart based training in the NTK regime, the vector of function outputs of the network with parameters 0 can be approximated madomm-feturee (NTRF) matrix at initialization:
Po0, where t is the neural neugen-tangent-
(y(X,00)
T
06g
To define the features, the strength (margin) of each feature, and how features appear in each sample, Pezeshki et [2021] compute the singular value decomposition (SVD) of the NTRF 4o multiplied by the diagonal-labe matrix Y:
Y 8. USVT.
(46)
The rows of are features, the diagonal elements S are the strengths of each feature and the ith row of U denotes how each feature appears in the NTRF representation of the ith sample.
To study issues with the solution to fz-regularized logistic regression, Pezeshki et al. [2021] define the gradient starvation (GS) regime. Under the GS regime, they assume is perturbed identity matrix that is also unitary: for a small constant << 1, such a matrix has all diagonal elements vI - _ and the rest of the elements are of the order 8 such that the rows have unit &g normm.
32

---

Accuracy
Log
Test Log
100
2.0
marg-log, Y- Z
2.0
80
marg-log, Y=2
ERM,
1.5
ERM, Y-Z
1.5
60
ERM,
ERM, 7
marg-log, Tr
1.0
1.0
40
marg log.
0.0
0.0
0
1000
2000 opochs
3000
4000
1000
2000 opochs
3000
4000
1000
2000
3000
4000
opachs
Figure 13: neural network trained with MARG-LOG depend the perfect stable feature to achieve perfect test accuracy whereas default-ERM performs worse than random chance. The middle panel shows that MARG-L.GG does not let the loss on the training shorteut group to go to zero, unlike default-FRM, and the right panel shows the test-loss is better for the leftover group.
The GS regime is violated in eq. (1). When fa is linear, fa(x) = 0 x, the NTRF matrix
0o)
0X0.
X.
08g
06.
In this case, let look at implication of U being perturbed identity matrix that is also unitary, as Pezeshki et al. [2021] assume. With (u')T as the ith row of U, the transpose of ith sample can (u') SV. Pezeshki et al. [2021] assume that d << in that the off-diagonal terms of are small perturbations such that off-diagonal terms of U(S² + AI)U have magnitude much smaller than 1, meaning that the terms (('t) S (2'')) X << for & j and positive and small À <<>> 1. Then,
be written as (x²)
ly'y yy'y(('') (x') x² = =(xt) x5| Tx
(47)
= =Iu') (ivi)sSSTuy SVVVSu'
(48)
=I(n')Te T
(49)
<<1
(50)
In words, this means that any two samples x², x² are nearly orthogonal. Now, for samples from eq. (1), for any i such that z = z' and y¹ yd
((x)) 13z'z'' + y'y' (8') 8 > 100 +++ (8")
(51)
As 5 are isotropic Gaussian vectors, around half the pairs i.j will have T8 > O meaning (xx)) [x] > 101. This lower bound implies that is not a perturbed identity matrix for sam- ples from eq. (1), This violates the setup of the gradient starvation regime from [Pezeshki et al., 2021].
Thus, the linear DGP in eq. (1) does not satisfy the conditions for the GS regime that proposed in [Pezeshki et al., 2021]. The GS regime blames the coupled learning dynamics for the different features as the cause for Seefault-ERM-triingg
models depending more on the less informative feature. Pezeshki et al. [202 derive spectral decoupling (SD) to avoid coupling the training dynamics, which in turn can improve model's dependence on the perfect feature. SD adds penalty to the function outputs which Pezeshki et al. [2021] show decouples training dynamies for the different features as defined by the NTRF matrix:
(o log(1 + (o)) (x))2
As eq. (1) lies outside the GS regime, the success of data from eq. (1) cannot be explained as a consequence of avoiding the coupled training dynamics in the GS regime Pezeshki et al. [2021]. However, looking at MARG-CTRL, the success of SD, in fig. explained consequence encouraging uniform margins.
example of perfect test accuracy even with dependence on the shorteut. In fig. 14, we train linear model with default-ERM data from eq. (1), showing that even when shortcut dependence
33

---

acc
loss
100
10a
train
W
10"²
test
0.2
60
10
0.1
40
train
test
10
20
0.0
0
10000 20000
10000
20000
10000
20000
epoch
Figure 14: With d 200 and 1000. lincar classifier still depend the shorteut feature and achieve 100% test accuracy. Nagarajan al. [2021] consider linearly separable data and formalize geometric properties of the data that make max-margin classifiers give non-zero weight to shorteut feature (w; > 0)- In their example, it is unclear when w. > leads to poor accuracy in the leftover group because Nagarajan et al. [2021] do not separate the model's dependence on the stable feature from the dependence on noise. The example here gives example where leftover group error require comparing Wy wa; the condition w. alone insufficient.
but test accuracy is 100%. demonstrating that guarantees
non-zero, test leftover group accuracy be 100%. Nagarajan al. [2021] consider linearly separable data and formalize geometric properties of the data that make max-margin classifiers give non-zero weight to the shortcut feature (w: 0). In their example, is unclear when w: > 0 leads to poor accuracy in the leftover group because Nagarajan et al. [2021] I] do not separate the model's dependence the stable feature from the dependence
noise. The example in fig. 14 gives example where W: > 0 but test accuracy is 100%, demonstrating that guarantees on test leftover group error require comparing Wy and wa; the condition w 0 alone insufficient. In contrast, theorem I characterizes cases where leftover group accuracy is worse than random even without overparameterization.
B.6
Experimental details
B.6.1 Background on Just Train Twice (JTT) and Correct-n-Contras (CNC)
JTT Liu et al. [2021] develop JTT with the aim of building models robust to subgroup shift, where the mass of disjoint subgroups the data changes between training and test times. To work without training group annotations, JTT assumes ERM builds models with high worst-group error. With this assumption, JTT first builds an "identification" " model via ERM to pick out samples that are misclassified due model's dependence on the shortcut. Then, JTT trains second model again via ERM on the same training data with the loss for the misclassified samples upweighted (by constant A). As Liu et al. [2021] point out, the number of epochs train the identification model and the upweighting constant are hyperparameters that require tuning using group annotations. As Liu et al. [2021], Zhang et al. [2022] show that JTT and CNC outperforms LFF and other two-stage shortcut- mitigating methods ([Zhang et al., 2022]), so we do not compare against them.
Correct-n-Contrast (CNC) In a fashion similar to JTT, the first stage of CNC to train model with regularized ERM to predict based on spurious attributes, i.c. shortcut features. Zhang et al. [2022] develop contrastive loss force the model to have similar representations across samples that share a label but come from different groups (approximately inferred by the first-stage ERM model). Formally, the first-stage model is used to approximate the spurious attributes in one two ways: 1) predict the label with the model, 2) cluster the representations into as many clusters as there are classes, and then use the cluster identity. The latter technique was first proposed in [Sohoni et al., 2020]. For anchor sample (y*, x*) of label y = positive samples P: are those than have the same label but have the predicted spurious attribute different value: é * y. Negatives N, are those that have different label but the spurious attribution is the same: & = For temperature parameter T and representation function ra, the per-sample contrastive loss for CNC is:
(cone(ro. = ExpxPI
log
EneN, exp (Tu(x=)TTar 3/7) EpEp, exp (ru(x") ro(x))/7)
34

---

The samples i are called anchors. For scalar À to trade off between contrastive and predictive loss, the overall per-sample loss in the second-stage in CNC is
(Te. i) + (1 - tostog-toso rx(')))
CNC uses hyperparameters informed by dataset-specific empirical results from prior work. The original implementation of CNC from Zhang et al. [2022] uses specific values of first-stage hyperparameters like weight decay and early stopping epoch for each dataset by using empirical results from prior work [Sagawa al., 2020a, Liu et al., 2021]. The prior work finds weight-decay and early stopping epoch which lead default-FRM models to achieve low test worst-group accuracy, implying that the model depends on the spurious attribute. This means the first-stage models built in CNC are pre-selected to pay attention to the spurious attributes. For example, [Zhang et al., 2022] point out that the first-stage model they use for Waterbirds predicts the spurious feature with an accuracy of 94.7%.
Without using dataset-specific empirical results from prior work, choosing LR and WD requires validating through the whole CNC procedure. We let CNC the same and WD for both stages and then validate the choice using validation performance of the second-stage model. This choice of hyperparameter validation leads similar number of validation queries for all methods that mitigate shortcuts.
B.6.2 Training details
Variants of MARG-CTRL to handle label imbalance. The three datasets that use in our ex- periments - Waterbirds, CelebA, and Civilcomments - all have an imbalanced (non-uniform) marginal distribution over the label; for each dataset,
ply class) 0.75.
cla.s(-11.1)
When there is sufficiently large imbalance, restricting the margins on all samples could bias the training to reduce loss on samples in the most-frequent class first and overfit on the rest of the samples. This could force model to predict the most frequent class for all samples, resulting in high worst-group error.
To prevent such a failure mode, we follow [Pezeshki et al., 2021] and define variants of o-damp, MARG-LOG, and o-stitch that have either 1) different maximum margins for different classes 2) different per-class loss values for the same margin value. Mechanically, these variants encourage uniform margins within each class, thus encouraging the model to rely less on the shortcut feature. We give the variants here for labels taking values 131
1. With per-class temperatures T-1,7h >>
O the variant of o-damp
with fe = wy T T6 (x),
fa-dmmp (y. fo) Llog [Ty 1.278y fe (1 (1.278 y
The 1.278 comes in to make sure the maximum input to log-loss occurs at Se = 1. How- ever, due the different temperatures Ti T-1, achieving the same margin on all samples produces lower loss on the class with the larger temperature.
2. With per-class temperatures T-1,T, > 0 the variant of a-stitch is
with so = Tr((x),
Er = Loog (Tyl (x) < 1] x yfo(x) + 1 1] (2 yfo(x)) 1)
3. With per-class function output targets 7-1, 711 > 0 the variant of MARG-LOG is with fo = wy re(x),
8MARG-LOG (yf)) loog (o) + X Aog((1 + +1o -7yl" 12) These per-class variants are only for training: at test time, the predicted label is sign
Details of the vision and language experiments. We use the same datasets from Liu et al. [2021], downloaded via the scripts in the code from [Idrissi et al., 2022]; see [Idrissi et al., 2022] for sample sizes and the group proportions. For the vision datasets, we finetune resnet50 from Imagenet-pretraine weights and for Civilcomments, we finetune a BERT model.
35

---

B
BA
Figure 15: Images mis-classified by model trained CelebA data with equal group sizes, i.e. without a shortcut. Samples with blonde as the true label have a white strip at the bottom while samples with non-blonde as the true label have black strip the bottom. The figure demonstrates that many images with blonde people in the image have the non-blonde label, thus demonstrating label noise. For example, see blonde man in the first row that labelled non-blonde and a non- blonde lady in the third row that is lablled blonde. Yet, MARG-CTRL improves over ERM for many LR and combinations; see fig. 16.
Optimization details. For all methods and datasets, we tune over the following weight decay (WD) parameters: 10-1, 10-1
10 2 10 10 For the vision datasets, we tune learning rate (LR) over 10-4 7,105 and for CivilComments, we tune over 10 5, 10 For CivilComments, we use the Adam W optimizer while for the vision datasets, we use the Adam optimizer; these are the standard optimizers for their respective tasks [Puli al., 2022, Guirajani and Lopez-Paz, 2021]. We use batch size of 128 for both CelebA and Waterbirds, and train for 20 and 100 epochs respectively. For CivilComments we train for 10 epochs with batch size of 16.
Per-method Hyperparameters. Like in [Pezeshki et al., 2021], the per-class temperatures T-1,7 Ti for a-damp and o-stitch, and the function output targets 7-1, for MARG-LOG are hyper- parameters that we tune using the worst-group accuracy or label-balanced average accuracy com- puted on the validation dataset, averaged over 2 seeds.
1. For o-stitch, select from T-1 E {1,2} and Tj {2,4,8, 12) such that Tj T-1-
2. For o-damp, search over T_1 [1,2] and Ti {2,4) such that Tj > T-1.
3. For SD and MARG-LOG, we search over 7-1 (-1,0,1} 1} and m E 21, 2.5, 3) for the image datasets and 71 E (1,2) for the text dataset, and the penalty coefficient set to be
X = 0.1
36

---

4. For JTT, we search over the following parameters: the number of epochs T {1.2} for CelebA and Civilcomments and T {10, 20, 30) for Waterbirds, and the upweighting constant À E {20, 50, 100] for the vision datasets and À E (4,5, 6) for Civilcomments.
5. For CNC, we search over the same hyperparameter in {0.05, 0.1). the contrastive weight À E {0.5, 0.75), and the gradient accumulation steps (32, 64). For the language task in Civilcomments, we also try one additional 8 128.
[Zhang et al., 2022] : the temperature
B.7 MARG-CTRL improves over default-ERM on CelebA even without the stable feature being perfect.
CelebA a perception task in that the stable feature the color of the hair in the image. But unlike the synthetic experiments, MARG-CTRI does not achieve 100% test accuracy on CelebA We investigated this and found that CelebA fact has some label noise.
We trained a model via the MARG-CTRL method o-damp on CelebA data with no shortcut; this data is constructed by subsampling the groups to all equal size, (5000 samples). This achieves test worst-group accuracy of 89%. We visualized the images that were misclassified by this model and found that many images with blond-haired people were classified as having non-blonde hair. Figure 15 shows 56 misclassified images where samples with blonde as the true label have a white strip at the bottom while samples with non-blonde the true label have black strip the bottom. The figure shows that images with blonde people can have the non-blonde label, thus demonstrating label noise. Thus, MARG-CTHE improves over ERM features do not determine the label.
datasets like CelebA where the stable
dataset = celeba
0.9
0.8
0.7
0.6
0.5
0.4
o-damp ø-stitch
erm marg-log sd [method]
Test worst-group accuracy on CelebA of default-ERM and MARG-CTRL for different values of LR and WD. Default-ERM's performance changes CTRL, which shows that default-ERM is more sensitive than MARG-CTRL. Only 2 combinations of LR and WD improve ERM beyond test worst-group accuracy of 60%, while every MARG-CTRL method achieves more than 70% test worst-group accuracy for every combination of LR and WD.
Figure 16:
with LR and WD than MARG-
B.8 Sensitivity of ERM and MARG-CTRL to varying LR and WD
In fig. 16, we compare the test worst-group accuracy of default-ERM, ERM and MARG-CTRL on CelebA, for different values LR and WD. There are combinations of LR and WD for which ERM run. For each combination of LR and WD, the hyperparameters of the MARG-CTRL method (values of X, T, v) are tuned using validation group annotations, and test worst-group accuracy corresponds to the best method hyperparameters. Default-ERM's performance changes more with LR and WD than MARG-CTRL, which shows that default-ERM is more sensitive than MARG-CTRL. Only 2 com- binations of LR and WD improve ERM beyond test worst-group accuracy of 60%. while every MARG-CTRE method achieves more than 70% test worst-group accuracy for every combination of LR and WD.
37


Reviews:
[{"review_id": "iwnqLUfXbz", "reviewer": "Reviewer_8MoS", "summary": "This paper explores the phenomenon of models using easy-to-learn spurious features (aka, shortcuts) instead of reliable but harder-to-learn true features. They find in their theoretical that max-margin relies on the spurious feature while controlling for uniforming margin induces learning the true feature. With this insight, they try numerous loss functions that provide a bias towards uniform margins and find improved worst-group accuracy on a variety of tasks.", "questions": "* How does the dimensionality (e.g., choosing $d=100$) come into play? The story setting up the analogy does not in principle rely on the dimensionality all, just the gradient sizes of the noisy and true signals. I'm guessing it has something to do with interpolation, but I think it'd be good to have further discussion of this.\n* What's the connection between the neural network trained in section 2.1 and the linear model theorems? What happens if you train a logistic regression model instead?\n* Similar toy settings as in this paper (such as (Sagawa et al., 2020)) have been examined in the past and seemed to rely on overparameterization for their phenomena. What are the particulars in this paper's setup that allow us to observe phenomena in the underparameterized setting?\n* How should I think of the different MARG-CTRL? What factors cause their difference in performance and how should I make the decision in which to pick?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Experiments show good results for their methods.", "weaknesses": "* The informal statement of Theorem 1 in the main text is too vague in my opinion. In particular, it's not stated what the regime of $n$ is and how these other quantities interact with it. \n* The graphs are tough to read (too small) and the legends overlap with the plots.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. We addressed your questions and concerns below. If any residual concerns remain, we would be glad to discuss further. If no concerns remain, we would appreciate it if you could raise your score.\n\n**[The informal statement of Theorem 1 is too vague. In particular, what is the regime of n and how do other quantities interact with it.]**\n\nWe have updated the paper to have a full version of theorem 1, shown below:\n\n> **Theorem 1:** Let $W^*$ be the max-margin predictor on $n$ training samples from the linear perception task in equation 1 and let the leftover group be of size $k = (1-\\rho)n.$ There exist constants $C_1, C_2, N_0 > 0$ such that $$\\begin{align} \\forall \\\\, n > N_0, \\quad\\forall \\\\,\\\\, \\rho \\in \\left[ 0.9, 1 - \\frac{5}{n}\\right], \\quad \\forall \\\\,\\\\, d \\geq C_1 (1-\\rho)n \\log (3n),  \\quad \\forall \\\\,\\\\, B > C_2 \\sqrt{\\frac{d}{(1-\\rho)n}}, \\end{align}$$\n\nwith probability at least $1-\\frac{1}{3n}\\\\,$ over draws of the training data, it holds that $B W_z^* > W_y^*$.\n\nBriefly, the result holds for all $n > N_0 $ where $d$ scales with the size of the leftover group, up to logarithmic factors.\n\n**[Graphs too small and legends overlap.]**\n\nWe have made the plots bigger and cleaned them up.\n\n**[How does the dimensionality ($d=100$) comes into play?]**\n\nThe reviewer is right in that with the additional dimensions of noise, default-ERM can interpolate the training data without relying on the stable feature by using \n\n1. The shortcut feature to classify the shortcut group\n2. The noise to fit the leftover group, i.e. overfit to the leftover group\n\nIn figure 3 in the pdf in the general response [[LINK]](https://openreview.net/attachment?id=jfFAwQVsZg&name=pdf), we show that as data dimension increases, the model achieves worse test leftover group accuracy, meaning that the model depends more on the shortcut. We train the same one-layer-network that we used in the paper on data of increasing dimension and plot its test leftover group accuracy. This larger shortcut reliance occurs because when more noise is available, the model can depend more on the shortcut while driving down leftover group loss by overfitting to it, all within the same norm budget.\n\n**[Connection between the neural network in section 2.1 and linear model theorems? What happens with logistic regression model?]**\n\nWe originally ran the model with a neural network experiment to demonstrate that the shortcut learning behavior is not restricted to linear models. We have since added the linear model experiments to the paper to show that the analysis in Theorem 1 holds empirically. \n\nWe provide the plots in figure 1 in the pdf [[LINK]](https://openreview.net/attachment?id=jfFAwQVsZg&name=pdf). Figure 1 empirically demonstrates that even without overparameterization, default-ERM builds linear models that rely more on the shortcut feature than the stable feature. On the same data, MARG-CTRL builds linear models that do not rely on the shortcut feature and achieve 100% test accuracy. See [[LINK]](https://openreview.net/forum?id=zyZkaqNnpa&noteId=IHkY6ZuSeA) for details.\n\n**[Similar toy settings from the literature (such as (Sagawa et al., 2020)) assume overparameterization for their phenomena. What in this paper's setup allows us to observe phenomena in the underparameterized setting?]**\n\nExisting results like Sagawa et al. typically assume overparameterization to ensure linear separability of the data and then rely on results like Soudry et al. (https://arxiv.org/pdf/1710.10345.pdf) that says default-ERM on linear models converges in direction to the max-margin predictor. In our setting, the stable feature determines the label which guarantees linearly separability without assuming overparameterization. \n\nWe then perform a tight analysis to ensure that the covariate dimension required to induce shortcut learning only scales linearly in the size of the leftover group, up to logarithmic factors in sample size. Given this scaling relationship, we can show that even underparameterized models exhibit shortcut learning when the leftover groups are small enough.\n\nOur work focuses on shortcut learning in default-ERM in the scenario where the stable feature determines the label, which means the bayes-optimal predictor on the training distribution only relies on the stable feature. Understanding why default-ERM favors shortcut-based classification instead of its target bayes-optimal predictor supports discovering novel strategies to mitigate shortcuts — like MARG-CTRL. Further, such understanding can help identify tasks where one should challenge default-ERM as the primary choice for modeling.\n\nWe have added this discussion to the paper.\n\n**[How should I think of the different MARG-CTRL? What factors cause their difference in performance and how should I make the decision in which to pick?]**\n\nGreat question. Two factors affect the performance of MARG-CTRL method: \n\n- the hyperparameter like the temperature in sigmoid-damping. \n\n   - Using too large a temperature makes MARG-CTRL too similar to log-loss and uniform margins are not encouraged, which fails to mitigate shortcuts. Using too small a temperature can mean optimization takes a long time to converge. Searching over a finer grid for the hyperparameters strikes a good tradeoff between optimization speed and controlling margins, and make different MARG-CTRL methods perform more similarly.\n\n- the penalty each method places on small margins and misclassifications compared to the penalty on large margins. \n\n    - For example, figure 11 in the paper shows that sigmoid-stitching penalizes large margins more than sigmoid-damping. In turn, sigmoid-damping may favor fewer small margins.\n\n\nIn practice, we recommend using one MARG-CTRL method and tuning the hyperparameters: while we do not have theoretical guarantees. MARG-LOG is usually near the best and is a safe bet. Studying the existence of uniformly optimal MARG-CTRL would be fruitful future work."}, {"review_id": "tkhjzMGH9Y", "reviewer": "Reviewer_Xk5J", "summary": "Having had my concerns addressed by the authors I have updated my score.\n-----------------------------------------------------------------------------------------\n\n\n\n* The paper proposes an explanation for why neural networks tend to learn spurious features over stable fratures which lead to a lower loss and better performance.\n* The main argument for this is due to the maxmargin losses induced through cross entropy, to counter this the authors propose several losses which induce a uniform margin.\n* The authors propose a nice example and demonstrate the results on vision and language datasets.", "questions": "* The examples in the paper tend to be restricted to linear models, which is not the case in most perception systems, do you have any intuition if these conclusions carry through to a non-linear case? I'm aware it makes the analysis harder, and I'm not asking you to perform it. But it would be nice to hear any issues that may arrise.\n* Are there any experiments in the non over-parameterised setting? As this is discussed in the paper, I would have expected to see them in the experiments.\n* Do you think these shortcuts are a bit artifificial? For instance in the waterbirds dataset, the background should be an important feature in the decision, but not the primary feature, does this method enable predictions from multiple features? Or do you think it will just rely on one?", "limitations": "Not explicitly discussed", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper addresses a very important topic of the simplicity bias, and goes a significant way in addressing it. \n* The comments and explanations are clear and concise, and follow a clear narrative.\n* I find the arguments that inductive bias towards uniform margins for perception tasks to be convincing.\n* The experiments are well conducted and clearly support their statements", "weaknesses": "* I find the scatter approach to testing many margin based losses a little un elegant, I would rather know which is the most effective in the paper and then see the results for other attempted losses in the Appendix. But this is just me preference.\n* Is Corollary one explicitly followed up with an experiment? I would like to know if it actually exhibits this behaviour or is there just the potential to?\n* The experimental datasets are rather limited, Waterbirds, CelebA, Wilds etc. Not a negative per se, but it would be nice to see authors trying to improve the testing framework for this probelm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. We addressed your questions and concerns below. If any residual concerns remain, we would be glad to discuss further. If no concerns remain, we would appreciate it if you could raise your score.\n\n**[I find the scatter approach to testing many margin based losses a little un elegant]**\n\nWe study multiple MARG-CTRL methods to show that the principle of controlling margins is what helps mitigate shortcuts, as opposed to properties specific to a single method.\n\n**[Is Corollary one explicitly followed up with an experiment? I would like to know if it actually exhibits this behaviour or is there just the potential to.]**\n\nThanks for this question. \n\nFigure 1 in the pdf [[LINK]](https://openreview.net/attachment?id=jfFAwQVsZg&name=pdf) empirically demonstrates that even without overparameterization, default-ERM builds linear models that rely more on the shortcut feature than the stable feature. On the same data, MARG-CTRL builds linear models that do not rely on the shortcut feature and achieve 100% test accuracy.  See [[LINK]](https://openreview.net/forum?id=zyZkaqNnpa&noteId=IHkY6ZuSeA) for details. We have added experiments with linear models to the paper.\n\n**[The experimental datasets are rather limited. It would be nice to see authors trying to improve the testing framework for this probelm]**\n\nThanks for this suggestion. We chose these datasets as they are amongst the most popular ones in the spurious correlations literature [1,2,3]. \n\nOne key contribution of this work is an evaluation framework that is more challenging than the ones used in prior work, called the pure setting. Existing methods like CnC and JTT crucially require validation group annotations for model selection to mitigate shortcuts [3,4]. However, given a stable feature that determines the label and a shortcut that does not, using the stable feature alone should achieve the highest accuracy in both classes. In turn, class labels alone should be sufficient to mitigate shortcuts. Further, for new tasks, determining shortcuts is a laborious manual process, which means shortcut annotations will often be unavailable.\n\nIf one should be able to select models with validation class labels alone and unknown shortcuts can exist, model selection metrics should only use class labels. This motivates the pure setting without access to any group annotations. In the pure setting, MARG-CTRL outperforms two-stage shortcut-mitigating methods as the latter push the work to validation by using group annotations to select models. \n\nWe have since updated the validation strategy in the pure setting and give the updated table of results in the general response [[LINK]](https://openreview.net/forum?id=zyZkaqNnpa&noteId=jfFAwQVsZg). We summarize the results here:\n\n- Every MARG-CTRL outperforms every two-stage shortcut mitigating method.\n- Every MARG-CTRL method outperforms ERM on every dataset.\n- In contrast, CnC and JTT without group annotations sometimes do not outperform ERM.\n\n[1] https://arxiv.org/abs/1911.08731\n\n[2] https://arxiv.org/abs/2110.14503\n\n[3] https://arxiv.org/abs/2107.09044\n\n[4] https://arxiv.org/abs/2203.01517\n\n**[The examples in the paper tend to be restricted to linear models. Do you have any intuition if these conclusions carry through to a non-linear case? I'm aware it makes the analysis harder, and I'm not asking you to perform it. But it would be nice to hear any issues that may arrise.]**\n\nThanks for this question. \n\nThe experiments in the paper empirically confirm that our theoretical insights do in fact extend to real deep neural networks: the solutions motivated by the theory — margin-control techniques — mitigate shortcuts in actual deep learning models on real-world vision and language datasets. \n\nMany works in the literature study linear models to develop insights into why deep models fail to be robust [1,2,3]. In a similar vein, we show that shortcut learning occurs in linear models despite the presence of a perfect stable feature because of max-margin classification. As default-ERM also maximizes margins in neural networks [4], the insights from our theory should extend beyond linear models which we confirm empirically.\n\nWe suspect the main challenges in extending the theoretical analysis to neural networks would involve tightly lower-bounding the norm of max-margin solutions that depend only on the stable feature. The reason this may be hard is that we may also have to consider models whose first layer depends on the shortcut but that second layer combines the ReLU responses in ways that cancels out the influence of the shortcut. If one doesn’t consider these models, the norm may not be lower-bounded tightly enough to separate the max-margin predictors that only use the stable feature from the ones that rely on the shortcut. \n\nWe have added this discussion to the paper.\n\n1. https://proceedings.mlr.press/v119/sagawa20a.html\n2. https://openreview.net/forum?id=fSTD6NFIW_b\n3. https://openreview.net/forum?id=dQNL7Zsta3\n4. https://openreview.net/forum?id=SJeLIgBKPS\n\n**[Does this method enable predictions from multiple features?]**\n\nMARG-CTRL only encourages the final output of models to be similar in magnitude across all samples. MARG-CTRL does not restrict which features are used. \n\nWhen using models like neural networks, multiple features are combined to produce a prediction. For example, in datasets like Waterbirds, multiple features together form the shape of the bird, and the shape of the bird is a stable predictor for the task of determining whether the bird is a waterbird or a landbird. MARG-CTRL relies on the available stable features to mitigate shortcuts in waterbirds in both the traditional and the pure setting. This empirically demonstrates that MARG-CTRL does enable prediction from multiple features.\n\nWe have added this discussion to the paper."}, {"review_id": "fEaGpgZJxH", "reviewer": "Reviewer_PgqC", "summary": "This paper provides an in-depth analysis of the phenomenon of \"shortened learning\" in machine learning models, especially in the context of perceptual tasks. The authors confirm that basic empirical risk minimization (ERM) methods tend to prefer models that depend on shortcut features, even when models can achieve zero loss using only stable features. They attribute this to ERM's inductive bias to maximize margins across all samples. To address this, the authors propose an alternative loss function biased inductively with a uniform margin called MARG-CTRL. The paper demonstrates that MARG-CTRL mitigates shortcut learning on multiple vision and language tasks without the use of annotations of the shortcut feature in training or even validation. They also show that MARG-CTRL performs on par or better than the more complex and costly two-step shortcut mitigation method.", "questions": "-How does MARG-CTRL perform in scenarios where the shortcut features and the stable features are highly correlated? Does this affect the effectiveness of MARG-CTRL?\n-What are the trade-offs involved in using MARG-CTRL versus two-stage shortcut-mitigating methods??\n-Are there specific scenarios or types of tasks for which MARG-CTRL may not be as effective?", "limitations": "Please see the weaknesses part.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "-This paper presents a thorough analysis of the shortcut learning problem. \n-The authors propose a novel solution, MARG-CTRL, which has been shown to effectively mitigate shortcut learning in several tasks.\n-The paper is well-written and easy to understand.", "weaknesses": "-Although MARG-CTRL is shown to perform well across different tasks, it is not clear how MARG-CTRL perform in scenarios where the shortcut features and the stable features are highly correlated.\n-The paper compares MARG-CTRL with two-stage shortcut-mitigating methods like JTT and CNC, it would be helpful to understand the specific scenarios where MARG-CTRL outperforms these methods and where it does not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. We addressed your questions and concerns below. If any residual concerns remain, we would be glad to discuss further. If no concerns remain, we would appreciate it if you could raise your score.\n\n**[How does MARG-CTRL perform in scenarios where the shortcut features and the stable features are highly correlated? Does this affect the effectiveness of MARG-CTRL?]**\n\nWe interpret this as the reviewer asking about the situation where conditioning on the shortcut features leaves little randomness in the stable feature. This is already the case in the synthetic experiment; for example, conditioning on the value of the shortcut feature $X_1 = B$, the stable feature $X_2 = 1$ in 90% of the samples. As demonstrated in the paper in figures 2 and 7-10, MARG-CTRL learns the stable feature and achieves 100% test accuracy on this.\n\nIn the case of perfect correlation, the case where $Z=Y$ in the data, even knowing Z is insufficient to build models that depend on the stable feature. To see this, consider the following two families of data-generating processes $p_1$ and $p_2$.\n\nLet $ p_1(Y, Z, X; \\rho)$ be sampled as\n\n$$ \\begin{align}\nY ~ U({-1, 1}) , \\quad \nZ = & \\quad Y \\text{ with probability } \\rho  \t\n\\qquad \\qquad \n  X = \\left[Y ,Z\\right].\n\\\\\\\\\n= & - Y \\text{ with probability } 1-\\rho\n\\end{align}$$\n\nLet $ p_2(Y, Z, X; \\rho)$ the same as $p_1$ except with the feature order in $X$ swapped ($X = [ Z, Y ] $ ). \n\nWhen Z and Y are perfectly correlated, that is $\\rho=1$, $p_1 ( Y, Z, X; \\rho=1) = p_2 ( Y, Z, X; \\rho=1)$ meaning the observed data is the same and any model training procedure would produce the same results in distribution. However, the stable predictor for $p_1$ should place weight on the first feature of $X$, which is different from the stable predictor for $p_2$ that should place weight on the second feature of $X$.\n\nWe have added this discussion to the paper.\n\n**[What are the trade-offs involved in using MARG-CTRL versus two-stage shortcut-mitigating methods?? -Are there specific scenarios or types of tasks for which MARG-CTRL may not be as effective?]**\n\nThanks for this question.\n\nWhen there exists a stable feature that determines the label, MARG-CTRL is better than two-stage shortcut-mitigating methods in the pure setting. This stems from the fact that two-stage methods require validation group annotations for model selection and the pure setting does not provide these annotations. On the other hand, as we show in the results in the general response [[LINK]](https://openreview.net/forum?id=zyZkaqNnpa&noteId=jfFAwQVsZg) MARG-CTRL strictly outperforms two-stage methods in the pure setting.\n\nEven when the stable feature does not determine the label, MARG-CTRL mitigates shortcuts in practice: MARG-CTRL performs competitively on CelebA even though there is label noise in the dataset, meaning that the stable feature is not perfect (see figure 14 in the appendix). When the stable feature is imperfect, validation group annotations are available, and ERM-trained models help infer groups accurately, two-stage methods can outperform MARG-CTRL methods.\n\nWe have added this discussion to the paper."}, {"review_id": "N1iZVpqdC6", "reviewer": "Reviewer_9QKU", "summary": "This paper theoretecally and empirically showed that the inductive bias of default- ERM maximizing the margin causes shortcut learning in  a linear perception task.\nIt proposed uniform margins that leads to models that depend more on the stable than the shortcut feature and suggested loss functions encourage uniform-margin solutions.", "questions": "It seems that this paper forcus on a theoretical analysis in a situation like background shortcuts, where shortcut features make up a large portion of the data as shown in term B. \nLearning  features with a large B preferentially is intuitively reasonable in such a simple situation; however, reading the proof in the Appendix, it seems to require a very tough proof to show that. \nI would like to know where the difficulty of the proof lies, what you devised in the Appendix proof ,and where you derived the key inequality.\n\nShortcut features do not always occupy as much space as stable features as background features. For example, in the following paper, the percentage of partial input is much smaller.\n>Overinterpretation reveals image classification model pathologies Brandon Carter, Siddhartha Jain, Jonas Mueller, David Gifford\nIsn't Bz>y important for the theoretical analysis?\nIf Bz<y, what part of the proof is more difficult? Or what other assumptions are necessary?\n\n\n\n", "limitations": "The theory itself has limited applicability due to the linear model, and we do not know how well it can actually be explained in general terms in actual deep learning models.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper analyzes shortcut learning theoretically in terms of margin maximization.\nI have not seen an analysis from this perspective before.\nIt also proposes the concept of uniform margin from theory and suggests a method to prevent shortcut learning.", "weaknesses": "The theory itself has limited applicability due to the linear model, and we do not know how well it can actually be explained in general terms in actual deep learning models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. We addressed your questions and concerns below. If any residual concerns remain, we would be glad to discuss further. If no concerns remain, we would appreciate it if you could raise your score.\n\n**[The theory itself has limited applicability due to the linear model, and we do not know how well it can actually be explained in general terms in actual deep learning models.]**\n\nThe experiments in the paper empirically confirm that our theoretical insights do in fact extend to real deep neural networks: the solutions motivated by the theory — margin-control techniques — mitigate shortcuts in actual deep learning models on real-world vision and language datasets. \n\nMany works in the literature study linear models to develop insights into why deep models fail to be robust [1,2,3]. In a similar vein, we show that shortcut learning occurs in linear models despite the presence of a perfect stable feature because of max-margin classification. As default-ERM also maximizes margins in neural networks [4], the insights from our theory should extend beyond linear models which we confirm empirically.\n\n1. Sagawa, Shiori, et al. \"An investigation of why overparameterization exacerbates spurious correlations.\" International Conference on Machine Learning. PMLR, 2020.\n2. Nagarajan, Vaishnavh, Anders Andreassen, and Behnam Neyshabur. \"Understanding the failure modes of out-of-distribution generalization.\" International Conference on Learning Representations. 2020.\n3. Wald, Yoav et al. “Malign Overfitting: Interpolation and Invariance are Fundamentally at Odds.” International Conference on Learning Representations (2023).\n4. Lyu, Kaifeng, and Jian Li. \"Gradient Descent Maximizes the Margin of Homogeneous Neural Networks.\" International Conference on Learning Representations. 2019.\n\n**[It seems that this paper focuses on a theoretical analysis in a situation like background shortcuts, where shortcut features make up a large portion of the data as shown in term B. Shortcut features do not always occupy as much space as stable features as background features.]**\n\nThis is a great question!\n\nWe would like to clarify that in the linear perception task, the shortcut is a single scalar coordinate of the covariates. With large B, models that predict with the shortcut can achieve margins greater than 1 while having a small norm: to achieve a margin > 1 on the shortcut group a linear predictor only needs 1/B weight on the shortcut feature. To achieve the same margin with the stable feature, the linear predictor needs a weight of 1.\n\nA large $B$ is analogous to shortcut pixels in images that vary dramatically (+1 to -1 for example in normalized pixel-space) when the label changes. For example, in figure 1 in the paper the reviewer links (https://arxiv.org/abs/2003.08907), classifying the image of the bird mostly requires just the blue pixels, which are part of the background sky. These few background pixels vary a lot between different background types from sky to land.\n\nIn effect, what matters in shortcut learning is pixel values that vary a lot across examples. If large portions of pixels vary together from large to small, models could learn to depend on them faster but it is not necessary for all shortcuts to be large portions of the input. This intuition should help see that the results do not require the backgrounds to make up a large portion of the data.\n\nWe have added this discussion to the paper.\n\n**[Learning features with a large B preferentially is intuitively reasonable in such a simple situation; however, reading the proof in the Appendix, it seems to require a very tough proof to show that. I would like to know where the difficulty of the proof lies, what you devised in the Appendix proof ,and where you derived the key inequality.]**\n\nThe reason the proof is complicated is that there is no closed-form solution for the max-margin classifier, hence we need to derive a bound for the reliance on the shortcut. The key inequality is named the *separation inequality* (on line 709 in the appendix)*,* which shows that max-margin solutions that rely more on the stable feature require higher norm than max-margin solutions that rely on the shortcut feature.\n\n**[Isn't Bz>y important for theoretical analysis? If Bz<y, what part of the proof is more difficult? Or what other assumptions are necessary?]**\n\nWe interpret this as the reviewer asking about the role of the magnitude of $B$, in that what default-ERM would learn if $| B z | < | y |$. It is true that $B$ needs to be a positive number greater than 1; theorem 1 shows a lower bound on $B$ that along with large enough $d, \\rho$ yields shortcut learning in default-ERM.\n\nIf $B<1$, default-ERM leads to models that depend more on the stable feature than the shortcut, which allows them to achieve 100% test accuracy in the linear perception task. Intuitively, this is because when $B < 1$, the model can achieve more margin on every sample by relying on the stable feature instead of the shortcut feature, for the same cost in $\\ell_2$-norm."}]

Author rebuttal:

# General response

We thank the reviewers for their thoughtful feedback.  We are glad the reviewers find that 
- Our paper is well-written
  - “The comments and explanations are clear and concise, and follow a clear narrative” - Xk5J
  - “The paper is well-written and easy to understand” - PgqC
- Our paper presents a thorough, novel, and significant analysis
  - “This paper presents a thorough analysis of the shortcut learning problem” - PgqC
  - “I have not seen an analysis from this perspective before.” - 9QKU:
  - “The paper addresses a very important topic of the simplicity bias, and goes a significant way in addressing it.” - Xk5J
- Our solutions are novel and effective and our experiments are well-conducted
  - “The authors propose a novel solution, MARG-CTRL, which has been shown to effectively mitigate shortcut learning in several tasks.” - PgqC
  - “Experiments show good results for their methods.” - 8MoS
  - “The experiments are well conducted and clearly support their statements” - Xk5J


Our paper begins with the premise that given a stable feature that determines the label, a model trained with gradient-based optimization of the log-loss, which we call default-ERM, can achieve zero training loss using only the stable feature. This model that only uses the stable feature always generalizes outside the training distribution.

However, in popular tasks like classifying hair color from images of celebrities, default-ERM builds a model that relies on shortcuts even though the stable feature is perfect in that it determines the label. Models that rely on shortcuts do not generalize outside the training distribution.

Why does default-ERM prefer shortcuts despite the presence of a perfect stable feature? 


**[Main contributions]**

1. We prove that default-ERM’s inductive bias toward maximizing margins causes shortcut learning in linear models even without overparameterization.
2. In contrast, we show that an inductive bias towards uniform margins favors perfect stable features. 
3. We develop a family of methods that encourage uniform margins; we call these margin-control (MARG-CTRL) methods.
4. We demonstrate that MARG-CTRL mitigates shortcuts as well or better than the best of default-ERM and existing two-stage shortcut-mitigating methods, in deep models for vision and language tasks.
5. We introduce a new experimental setting without group annotations in training or validation. In this more challenging setting, MARG-CTRL strictly outperforms both default-ERM and the more computationally expensive two-stage shortcut-mitigating methods.

**[Paper improvements made in response to feedback]**

In response to the reviewers' feedback, we have improved the paper as follows:

- We have added experiments with underparameterized linear models with both default-ERM and MARG-CTRL to empirically validate theorems 1 and 2, and corollary 1. See pdf [[LINK]](https://openreview.net/attachment?id=jfFAwQVsZg&name=pdf). (reviewers 8MoS, Xk5J)
- We have expanded the discussion of the limitations and trade-offs of MARG-CTRL (reviewers PgqC, Xk5J).
- We have included additional discussion about theorem 1, elaborating on the roles of dimension and the scalar factor $B$ in inducing shortcut learning. (reviewer 9QKU)
- We altered the model selection strategy in the pure setting where group annotations are absent (for details see below [[LINK]](https://openreview.net/forum?id=zyZkaqNnpa&noteId=IHkY6ZuSeA)).  This alteration improves the test performance of multiple methods, including some MARG-CTRL methods and some non-MARG-CTRL methods. We summarize the updated results here:
  - Every MARG-CTRL outperforms every two-stage shortcut mitigating method.
  - Every MARG-CTRL method outperforms ERM on every dataset.
  - In contrast, CnC and JTT without group annotations sometimes do not outperform ERM.

	(reviewer Xk5J)

**[Updated results in the pure setting]** 

|               | CelebA       | WB           | Civil        |
|---------------|--------------|--------------|--------------|
| ERM           | 57.5 ± 5.8   | 69.1 ± 2.1   | 60.7 ± 1.5   |
| CNC           | 67.8 ± 0.6   | 60.0 ± 8.0   | 61.4 ± 1.9   |
| JTT           | 53.3 ± 3.3   | 71.7 ± 4.0   | 53.4 ± 2.1   |
|||||
| **marg-log**     | 74.2 ± 1.4   | 77.9 ± 0.3   | 66.8 ± 0.2   |
| **norm**          | 74.2 ± 1.9   | 74.3 ± 0.1   | 63.9 ± 3.2   |
| **$\sigma$-damp**       | 70.8 ± 0.3   | 74.8 ± 1.6   | 65.6 ± 0.2   |
| **sd**           | 70.3 ± 0.3   | 78.7 ± 1.4   | 67.8 ± 1.3   |
| **$\sigma$-stitch**        | 76.7 ± 0.6   | 74.5 ± 1.2   | 66.0 ± 1.0   |

-------

We address one common concern here. 

**[Does the theory that focuses on linear models and linearly separable data provide insights into shortcut learning with neural networks on general datasets?]**


Reviewers 9QKU and Xk5J raised concerns that the theory is restricted to linear models. They asked questions about whether the insights can be extended to non-linear models.

The experiments in the paper empirically confirm that our theoretical insights do in fact extend to real deep neural networks: the solutions motivated by the theory — margin-control techniques — mitigate shortcuts in actual deep learning models on real-world vision and language datasets. 

Many works study linear models to develop insights into why deep models fail to be robust  [1,2,3]. In a similar vein, we show that shortcut learning occurs in linear models despite the presence of a perfect stable feature because of max-margin classification. As default-ERM also maximizes margins in neural networks [4], the insights from our theory should extend beyond linear models, which we confirm empirically.


1. https://proceedings.mlr.press/v119/sagawa20a.html
2. https://openreview.net/forum?id=fSTD6NFIW_b 
3. https://openreview.net/forum?id=dQNL7Zsta3
4. https://openreview.net/forum?id=SJeLIgBKPS


Meta-review: This paper theoretically analyzes shortcut learning, showing that max-margin learning leads to spurious feature learning, and use this to design loss functions which encourage uniform margins, finding improved worst-group accuracy. Reviewers found the question interesting, paper well-written, the theory well done, and the proposed solutions effective. I therefore recommend acceptance.
Decision: Accept (poster)