Implicit Regularization of SGD Reduces Shortcut Learning
Authors: Nahal Mirzaie
Alireza Alipanah
Ali Abbasi
Amirmahdi Farzane
Hossein Jafarinia
Erfan Sobhaei
Mahdi Ghaznavi
Amir Najafi
Mahdieh Soleymani Baghshah
Mohammad Hossein Rohban
Venue: ICLR 2026 Poster (2026)
Keywords: Spurious Correlations
Stochastic Gradient Descent (SGD)
Implicit Regularization
Primary area: learning theory

Abstract: Training with stochastic gradient descent (SGD) at moderately large learning rates has been observed to improve robustness against spurious correlations, strong correlation between non-predictive features and target labels. Yet, the mechanism underlying this effect remains unclear. In this work, we identify batch size as an additional critical factor and show that robustness gains arise from the implicit regularization of SGD, which intensifies with larger learning rates and smaller batch sizes. This implicit regularization reduces reliance on spurious or shortcut features, thereby enhancing robustness while preserving accuracy. Importantly, this effect appears unique to SGD: gradient descent (GD) does not confer the same benefit and may even exacerbate shortcut reliance. Theoretically, we establish this phenomenon in linear models by leveraging statistical formulations of spurious correlations, proving that SGD systematically suppresses spurious feature dependence. Empirically, we demonstrate that the effect extends to deep neural networks across multiple benchmarks. Our code is available at
\href{https://github.com/mirzanahal/sgd-implicit-regularization-shortcuts}{https://github.com/mirzanahal/sgd-implicit-regularization-shortcuts}.

IMPLICIT REGULARIZATION SHORTCUT LEARNING
OF SGD REDUCES
Nahal Mirzaie Alireza Alipanah' f
Ali Abbasi
Amirmahdi 2arzane
Hossein Jafarinia' Erfan Sobhaei
Mahdi Ghaznavi"
Amir Najafi'
Mahdieh Soleymani Baghshah', and Mohammad Hossein Rohban
'Computer Engineering Department, Sharif University of Technology
*Computer Engineering Department, University of Tehran *Department of Mathematical Sciences, Sharif University of Technology
ABSTRACT
Training with stochastic gradient descent (SGD) at moderately large learning rates has been observed to improve robustness against spurious correlations, strong cor- relation between non-predictive features and target labels. Yet, the mechanism underlying this effect remains unclear. In this work, identify batch size an additional critical factor and show that robustness gains arise from the implicit regularization of SGD, which intensifies with larger learning rates and smaller batch sizes. This implicit regularization reduces reliance on spurious or short- cut features, thereby enhancing robustness while preserving accuracy. Impor- tantly, this effect appears unique to SGD: gradient descent (GD) does not con- fer the same benefit and may even exacerbate shorteut reliance. Theoretically, we establish this phenomenon in linear models by leveraging statistical formula- tions of spurious correlations, proving that SGD systematically suppresses spu- rious feature dependence. Empirically, we demonstrate that the effect extends to deep neural networks across multiple benchmarks. Our code available at
INTRODUCTION
The primary goal of generalization in machine learning is develop models that perform robustly across diverse realizations of one or more distributions. However, this goal is often compromised when models rely on shortculs, or spurious features: features that are correlated with the target in the training distribution but unstable across environments (Geirhos et al. 2020). Such spurious correlations impede the learning of invariant features that remain stable across different distributions. As result, models that achieve high accuracy on the training data can fail dramatically on both in- distribution and distrr-iistiitttinn samples (Koh al. 2021b Puli et al. 2022).
This phenomenon persists even in the presence of Fully Informative Invariant Features (FIIF), which can perfectly predict the label. Despite their predictive power, gradient-base optimizers often se- lect solutions that rely on spurious features (Puli et al.) 2023; Nagarajan et al., 202T). In these settings, the label is conditionally independent of the spurious feature given the invariant one, and the Bayes-optimal predictor under the training distribution depends solcly on the invariant feature.
Nevertheless, models that use both invariant and spurious features typically achieve lower empiri- cal loss than those that rely only on the invariant feature (Arjovsky et al.) 2019:; Puli et al. 2022 Geirhos et al. 2020). This occurs because spurious features, while less predictive, often increase loss functions, making solutions that include them more attractive to gradient-based optimization (Soudry et al.) 2018)). In other words, even when the invariant feature alone suffices for perfect separation, incorporating spurious features can reduce the empirical loss by amplifying the margin.
the margin in margin-sensinnn
"Conresponding to: nahal. mirzaie ce.sharif.edu 1 Equal contribution.

---

The impact of data-dependent factors suctorrs-suhhae as the strength of spurious correlations and the geom- etry of the data on a model's reliance on shortcuts has been extensively studied in linear settings where a FIIF coexists with spurious feature (Puli et al. 2023; Xue et al. 2024 Nagarajan et al. 2021]. In these works, gradient-based optimizers are often treated as black boxes that converge to the max-margin solution, while the role of training hyperparameters, such as batch size b and learning rate e, in modulating shortcut reliance remains poorly understood. Empirically, higher learning rates have been observed reduce shortcut dependence and improve robustness (Idrissi al., 2022 Puli et al. 2023 Barsbey et al., (025), yet this phenomenon cannot be fully explained within existing frameworks. Consequently, the mechanisms by which gradient-based optimizer hyperparameters influence shortcut learning remain unclear, representing important open question.
1.1 FOUR-POINT DATA GENERATING MODEL
To concretely study the phenomenon described above, researchers have introduced a simple yet the- oretically rich data-generating model. A widely used instance is the four-point model, defined in two dimensions: a Fully Informative Invariant Feature (FIIF) and a spurious feature. Despite its simplic- ity, this model exposes fundamental limitations of empirical risk minimization (ERM) algorithms, including gradient-descent methods in linear classification, and has become a standard framework for theoretical investigations in aut-of-distribution generalization and shorteut learning (Rosenfeld et al.) 2021; Puli et al. 2023] Xue et al. 2024 Nagarajan et al.) 2021 Ahuja et al. (021). The model continues to inspire research and raises several open questions.
Definition 1.1 (Four-Point Data Model). Let Rad denote the Rademacher distribution over (-1, Fix parameters p E (0, 1) and B 1. The data distribution cally as:
Pp.B (P,.(XX0) (X, defined hierarchi-
{or {1-P p
if z = y/
y ~ Rad, 2 21y~
(1)
if z = -
and X A [v. Bz).
Here, X1 = is the FIIF, and X₂ = Bz is the spurious feature. The scaling factor B > 1 amplifies the influence of X2, so for large B, models tend to rely on the spurious feature over the invariant one. A natural, margin-sensee sensitive hypothesis set and cost function in this setting is the class of linear classifiers H 2 X + wt X w E IR?, ||l||2 S 1} with the exponential loss
A C(w)=
vilw" X.)
(2)
2=1
where (X,, y:) are i..dd samples from Definition Although X, can fully predict the label, the spurious feature X₂ = Bz can increase the margin and reduce the loss when is not too large. Consequently, the learned classifier w* [w will depends strongly on the specific optimization algorithm (e.g., GD, SGD), its hyperparameters such as learning rate and batch size b, as well as the choice of the loss function.
While prior work has mainly studied the effect of the data-generating parameters B and p shortcut reliance (Puli et al. 2023 Nagarajan et al. 2021 Xue et al. 20224] Sagawa et al. (0220b), our focus shifts to training hyperparameters- sppecifiisssecclllllll.......al. batch size b and learning rate roles through the lens of the implicit regularization GD and SGD algorithms.
1.2 OUR CONTRIBUTION
We theoretically examine how Gradient Descent (GD) and Stochastic Gradient Descent (SGD) in- fluence reliance on spurious features in the setting of Section [.] We then extend these theoretical insights with extensive experiments on real-world datasets, empirically validating the results across a broader family of loss functions and classifiers, including cross-entropy loss and deep neural net- In summary, we report two striking findings:
works (see Section
SGD reduces reliance spurious features, with this effect strengthening the batch size b decreases and/or the learning rate e increases. We provide explicit, con-asymptotic guar- antees (see Theorem 3.2
2

---

(a) Four-point dataset with FII
(b) Gradient flow of GD and SGD
(c) Implicit regularization (d) Implicit regularization of SGD
of GD
Figure 1: Implicit Regularization of GD and SGD on Four-Point dataset with FIIE, (a) Four- point dataset with a FIIF. The data lie in two dimensions: an invariant feature (v) and a spuri- ous feature (z). The majority of samples are shown in saturated colors. The invariant solution WINV achieves perfect classification. Similarly, the solutions that minimize C'(w), CGD (w), and (wG)(w). denoted by w", wan and WEGD, respectively, also achieve perfect accuracy, but with larger margin with respect to majority samples. (b) Comparison of the minima of C(w). CGD (CD(w) (w), and CSGD (w). along with schematic trajectories illustrating the flows of SGD (blue line) and GD (red line). (c, d) Implicit regularization of GD and SGD. Darker regions indicate lower values. No- tably, the implicit regularization of SGD imposes weaker penalty on solutions with smaller w., thereby favoring parameters that rely less on the spurious feature.
In contrast, GD does not confer the same benefit and may even slightly increase reliance on shortcuts (see Figure Dp. This behavior is also supported theoretically (Theorem 3.1
A key insight into why the above phenomena occur is that, for non-negligible learning rates 0, neither GD nor SGD exactly follows the gradient flow, i.c. gradient descent with an infinitesimal learning rate, of the original loss C(w) (Smith et al. [021 Barrett & Dherin 2021). Instead, both methods approximately follow the gradient flow of modified (surrogate) loss that augments the original cost with an additional regularization term, known as the implicit regularization of GD and SGD.
The mechanisms of implicit regularization differ between the GD and SGD. For GD, the regular- ization penalizes the squared norm of the full-batch gradient, |/VC(w)]] favoring flatter minima. In addition, SGD also penalizes the average squared norm of the gradients across A n non- overlapping mini-batches, thereby reducing gradient variance between mini-batches. This differ- ence, both theoretically and empirically, leads markedly different behaviors in group robustness and reliance on spurious features. Specifically, stronger implicit regularization in SGD, scaling with the learning to batch size ratio, more effectively suppresses gradient variance across mini- batches, yielding more consistent performance across subpopulations and greater reliance on invari- features.
Our work aims to provide a foundation for understanding shortcut Iearning through the lens of opti- mizer dynamics. In particular, clarify the scemingly paradoxical benefits large learning rates and show that combining small batch sizes with appropriately tuned higher learning rates introduces favorable inductive bias toward robustness against spurious features. This perspective reduces the need for exhaustive hyperparameter searches in explicit Mhortcut-mitigatioo methods (Kirichenko
al. 2023, Qiu et al. 2023 Ghaznavi al. 2025). by leveraging the natural regularization effects of SGD.
THE CORE IDEA: IMPLICIT REGULARIZATION OF GD AND SGD
In the continuous limit, gradient descent with infinitesimal step size is described by the ordinary differential equation (ODE):
d
(1) (C()())) 11 7>>0 0,
(3)
di
3

---

which defines the gradient flow. GD approximates this continuous process with discrete updates:
(4) This discretization introduces deviations from the exact gradient flow trajectory. As result, the optimizer effectively follows the gradient flow of modified loss function that includes an additional regularization term, this is known as implicit regularization. It is called "implicit" because no explicit penalty added; rather, the discretization inherent in GD biases the trajectory away from steep regions with large gradients. Formally, this implicit regularization can be expressed as (Barreti & Dherin 202T):
w (++1)) w <VC(w()). Yt = =,,
CGD(w) - C(w) + [|
(5)
4
Consequently, GD trajectories are repelled only from regions of high loss but also from areas with large gradient norms. A formal statement is given in Lemma A..] A similar characterization
holds for SGD, where the implicit regularization is expressed in terms of the average squared norm of the mini-batch gradients (Smith et al. 2021):
CSGD (w) A C(w) + 4m
(6)
with m denoting the number of mini-batches and VC&(w) represents the gradient computed over the k-th mini-batch. This result is formalized in Lemma A.4
We now sketch the key idea behind our theoretical analysis. In the four-poim data generation model, the SGD modified loss can be decomposed as:
CSGD (w) = CCD(w) + (ar(p1.)) f(w; B,
(7)
4
where ý is the empirical estimate of p based on the dataset {(X;, (1)) Var(p denotes the variance of estimates across the mini-batches of size b, and f(w: B) is function with specific properties. Notably, the magnitude of the second term scales as c/b. We show that f(-) effectively shifts the optimal solution toward smaller wa (less reliance on the spurious feature) and larger wy (more reliance on the invariant feature), explaining why SGD with appropriate hyperparameters suppresses shortcut learning.
3 MAIN RESULTS
Our main theoretical results are presented in this section. The following theorem shows that under two conditions: (i) sufficiently large B, and (ii) sufficiently large n so that the sample mean i close to its population mean p. Gradient Descent (GD) provably increases reliance on spurious features. This theorem provides a asymptotic guarantee, showing that the degree of worsening scales linearly with the learning rate c.
Theorem 3.1 (Main Result on Gradient Descent), Assume the four-point data generation model
described in Definition 1.1 with parameters E (0, h) and B > 1. Let D = {(,,,))) be dataset of n Li.d samples drawn from this model. Assume
3
1 1-
2 C'
B
log
n 288 log
2
P
for some Ç E (0, 1). Let w G.D denote the solution obtained using gradient descent with suffi- ciently small step size >> 0 (such that LemmalA. applies), and w be the solution using gradient flow of the original loss. Then, there exists a constant C > depending only on B and satisfying C O(1) with respect to B, such that
w² w
Cc) +O))
with probability at least 1 1
with with respect to the randomness of drawing D.
This shows that GD could result in higher wa with respect to the true optimizer, worsening the reliance on the spurious feature. The proof is given in Appendix A.3
In contrast GD. SGD has the potential yield the opposite effect. This benefit, however, only manifests when the minibatch size b is sufficiently small, large b recovers the GD regime, where the improvement disappears. The following theorem formalizes this phenomenon:
4

---

Theorem 3.2 (Main Result Stochastic Gradient Descent). Assume the four-point data generation
model described in Definition I.1 with parameters E 100 3) and > 1. Let = {(X; ; y1) Vi=1 be a dataset of n i...d. samples drawn from this model. Suppose that
3 log
1 1-P)
8b log( {)
26 26log(
B
max
{
(0(1 0))
p - S
for some ÇE (0, 1). Let 2ZGDD denote the solution obtained using stochastic gradient descent with sufficiently small step size e > and minibatch size b 2 1 over a single epoch, and let w be the solution using gradient flow. Then, there exist constants C1. C2 > 0. depending on (B, p) and satisfying C₁, C2 = (1) with respect to both parameters, such that
BE + +O(6++B+) +B+)), b
W SGGD w S Ci Crevp(1-p)
with probability at least 1 - with respect to the randomness Df
The proof is deferred to Appendix A.33 The key observation is that the negative term dominates whenever B is sufficiently large and/or is small, which implies w sCD < wws. that is, SGD shifts
the solution toward the invariant feature. Moreover, just as in Theorem 3.1 the effect scales linearly with 6, so larger learning rates intensify the phenomenon.
Corollary 3.3 (Upper bound on minibatch size). In the setting of Theorem 3.2 descent provably reduces the reliance on the spurious feature Bz provided that
stochastic gradient
b < T (6-1) p(1 p)
for a sufficiently small step size > O.
Intuitively, small mini-batches inject gradient variance that counteracts shortcut reliance. Our anal- ysis shows that whenever is small or B is large, there exists an explicit upper bound on b below which SGD provably improves robustness. In other words, stronger spurious correlations, arising from smaller or larger B, require smaller batch sizes to guarantee that SGD effectively suppresses shortcut learning. The dependence on is natural, while the required sample size remains moder- ate rather than prohibitively large.
The core contribution of this work is the rigorous analysis of the four-point data-generating model under the exponential loss and linear classifiers. To further clarify why the same mechanism should persist beyond this stylized setting, we also provide a general result under mild assumptions. In particular, in the regime n,, - oc, suppose there exists a shortcut solution Whad that minimizes the empirical risk, and group-robust solution Wgoood that is not a minimizer. If, for every minibatch, the gradient discrepancy between majority and minority subpopulations is uniformly smaller at Wooo than at Wbad, then SGD's s modified loss with implicit regularization assigns a smaller penalty to wgood thereby favoring it relative to the shortcut solution Wbad In contrast, full-batch GD lacks this variance-depee deeendent effect and instead amplifies the preference for the Wbad A formal statement and proof provided in Appendix A.4
4 EXPERIMENTS
We extend our analysis beyond theory with empirical evaluations on deep models (MLP, ResNets He al. (2015). and Bert Devlin et al. (2019b)) trained on established ppurious-correlation bench- marks. We focus on regimes achieving near-optimal in-distribution generalization, as indicated by stable accuracy (ACC). We report worst-group accuracy (WGA) as a metric of shortcut reliance, where higher WGA reflects stronger core feature learning and reduced dependence on spurious cor- relations. These results confirm that strengthening the implicit regularization of SGD effectively improve WGA.
4.1 NON-MONOTONIC EFFECT OF LEARNING RATE ON GROUP ROBUSTNESS
Theoretically, the strength of implicit regularization of SGD scales with increasing the learning rate Smith et al. 2021). In practice, however, very small learning rates lead to under-training, while
5

---

WGA (mean std)
ACC (mean std)
Blased
Balanced
CI
CMNIST
CelebA
Domino
Waterbirds
Valce
0.5
0.0
-6
-2
6
-2
-
-2
-6
-2
logle)
log(E)
logle)
log(e)
log(e)
Figure 2: Effect of Learning Rate on WGA and ACC. Test set ACC and WGA are reported for a fixed batch size of b = 128 on both balanced and biased datasets with spurious correlation (p = 5%). As shown, once ACC reaches an optimal or near-optimal level, WGA continues to increase with learning rate up to an optimal point, beyond which both ACC and WGA decline.
Best WGA across batch sizes (b). On datasets with spurious correlation (p 5%), report for each batch size the highest mean WGA achieved across six learning rates. Within each dataset, the maximum value is highlighted in blue, the minimum in orange, and A denotes the difference between them.
Table I:
CMNIST
Domino
Waterbirds
CelebA
CIFAR10
b
WGA
WGA
WGA
WGA
WGA
8
67.5+1.1
59.3
79.7
46.0+1.0
80.
16
68.4+1.2
56.3_3.6
77.7=28
51.9 +6.8
78.9
32
68.0+1.9
49.4
73.2
45.3+1.8
79,6+1.7
64
20.6
51.9_3.6
67.9
40.5
78.8
128
66.0
50.0
70.4
44.3
76.3
256
64.7=0.9
43.4-2.1
68.2=1.9
45.0+1.3
77.9
A
+3.7
+15.9
+11.5
+11.4
+3.8
excessively large learning rates destabilize training or cause divergence Goodfellow al. (2016);
Nocedal & Wright 2006); Smith et al. (2021).
Within the regimes that an near-optimal in bnndistrbutionngeeeraiizzzzzz is achievable, and for fixed batch size, increasing the learning rate, equivalently, increasing log(c), improves the WGA, as re- flected in the solid curves (Figure This effect is especially pronounced in biased datasets relative to balanced ones, as illustrated by the blue and orange curves, respectively. Overall, the results reveal a non-monotonic relationship between the learning rate and group robustness: WGA in- creases with the learning rate, reaches near-optimal point, and subsequently declines, likely due to convergence instability. Once the learning rate becomes sufficiently large to achieve near-optimal in-distribution generalization, further increases in learning result in improved robustness and yield higher WGA. However, when the learning rate grows too large, hinders convergence, and therefore both ACC and WGA decline. This pattern consistent across different batch sizes and datasets (see Figure 6)
4.2 SMALLER BATCH SIZES, STRONGER GROUP ROBUSTNESS
After confirming the effect of learning rate group robustness, we investigate whether reducing batch size enhances group robustness. Figure 3 presents both ACC and WGA.in biased datasets with spurious correlation (p 5%), where the hatched bars correspond to ACC and the solid bars to WGA. Although datasets exhibited varying sensitivities of WGA batch size, consistent trend emerged: once in-distribution generalization is saturated, training with smaller batch sizes improved the final WGA of the model. These results suggest that, once the learning rate secures strong gen- eralization, reducing the batch size also guides the optimizer toward solutions that are more robust across both minority and majority groups. This effect also observed in Transformer architectures for language Patasets(Tablee]
Furthermore, we optimized the learning rate separately for each batch size to determine the max- imum WGA achievable under that configuration. Across all datasets, the highest WGA occurred

---

b-8 Ase
b-16 Ace
b-32 Ave
bi664 Aec
b-125 Aue
b-2266 Aue
0.75
15.20
0.50
0.00
c le-
< 1e-10
e 0.0000
0.001
c 0.01
c 0.1
Learinng Rate
(a) CMNIST
0.75
Value
0.50
0.25
c-
c= 05
0=000
0.001
c=0.01
0=0.1
Learnnng Rate
(b) Domino
1.00
Value
0.50
0.25
0.00
0-00001
0.001
Learning
(c) Waterbirds
1.00
0.79
Value
0.25
0.00
6=10-05
Learingg Rate
CIFARIO
Figure 3: Joint Effect of Learning Rate and Batch Size on WGA and ACC. When in-distribution generalization is ensured, smaller batch sizes consistently yield higher WGA across all datasets, indicating improved robustness. For extremely high or low learning rates, in-distribution general- ization fails; these regimes, reliable conclusions about robustness cannot be drawn.
Table 2: WGA and ACC across batch sizes on language datasets. WGA and ACC for Multi-NLI and CivilComments across batch sizes for fixed learning rate.
Multi-NLI
CivilComments
b
WGA
ACC
WGA
ACC
8
10
76. 76.75
82.1840.04
10
60.72+3..v
91.76+4026
16
10
76.58+2.01
82.40+0.0r
10-5
59.73
92.12+0.12
32
10
76.50
81.7440.20
10-5
54.89
92.34
64
10 10-4
75.80+1.85
81.93 81.93+0.18
10
53.40++0.4
92.30
128
10-4
75.78 10.68
80.96 80.9610.05
10-5
53.70.0.74
92.0210.00
256
10-4
75.17 D.66
79.3440.02
A
+1.58
+7.32
consistently with smaller batch sizes (8 or 16), while the lowest values were typically observed at the largest batch sizes (64 or higher) (see Table D.. These results indicate that smaller batch sizes systematically enhance group robustness and allow the model to reach fundamentally higher ceilings of group robustness.
7

---

52
139
200
10
10
10
10
0.00
0.00
1.00
0.95
0.90
0.90
0.75
0.00
0.80
0.56
0.00
0.50
40.45, p p-0.083
044
pm
0.50
F--0.16 p
8.50
(a) CMNIST
(b) Domino
(c) Waterbirds
(d) CelebA
(c) CIFARIO
Figure 4: Scatter Plot and Pearson Correlation between R and WGA. negative correlation between It and WGA indicates that models converging to minima with more optimized implicit regularization terms, exhibiting greater robustness to spurious correlations.
4.3 IMPLICIT REGULARIZATIO FOR GROUP ROBUSTNESS
key question is whether the observed improvement in group robustness under stronger implicit regularization arises from distinct mechanism that enhances robustness, if it is merely conse- quence of overall improvements in standard generalization. To address this, we monitor improve- ments in ACC and WGA. WGA is substantially more sensitive to variations in batch size and learn- ing rate than ACC (Table 5 and Figure 3 Once the learning rate is within a range that ensures in-distribution generalization, fluctuations WGA are therefore much more pronounced than those observed in ACC (Table 5). These findings indicate that improvements in group robustness are not simply byproduct of uniform gains in generalization. Instead, they reflect a distinct mechanism by which the choice of batch size and learning rate directs the model toward solutions that have better performance on minority groups.
To examine the relationship between implicit regularization and group robustness more rigorously, we select models based on best validation performance and compute both the implicit regularization term of SGD and worst-group accuracy (WGA) biased test set that matches the training distri- bution. Recall that the implicit regularization of SGD can be computed as: R Σ |/ For consistency across experimental settings, we normalize by b and report its logarithm, denoted by R (see Figure 4 As we expected the more robust solutions exhibit lower gradient variance across mini-batches and consequently lower R.
To intuitively clarify why penalizing gradient variance across ness, view each mini-batch as sampled "domain" from the training distribution. Smaller batch sizes increase variability in subpopulation composition across mini-batches, resulting fluctuating spurious correlations. Suppressing gradient variance under these shifts promotes reliance on sta- ble, invariant features rather than shortcuts, thereby improving robustness. very similar principle that has been observed in domain generalization |ame al. (2022); Shh al. (2022). Therefore, stronger suppression gradient variance across mini-batches corresponds to improved robustness and reduced shortcut reliance.
improves group robust-
4.4 SMALL BATCH SIZE AS A TRICK FOR MULTI-LEVEL SPURIOUS CORRELATIONS
Existing methods for mitigating shorteut learning perform well on single-level spurious datasets such as CelebA, Waterbirds, and CMNIST. However, on more realistic datasets that contain complex or unknown spurious attributes, such as multi-level spurious correlations in Domino-Cii -ME. these meth- ods often perform at or below random chance on the minority groups Ghaznavi et al. (2025). This happens because, even after applying these methods, the second-level spurious attribute remains encoded in the learned representation and cannot be corrected when the algorithm only targets the first (known) spurious correlation (see Figure 5). In these scenarios, training with small batch sizes provides stronger inductive bias for current explicit methods. As shown in Table 2, applying DER, AFR, and EVLLS with small batch sizes yields substantial WGA improvements of 25-35-37 37% compared to training the same methods with larger batch sizes.
8

---

Group Info
Waterbirds
CelebA
CMNIST
Domino-CMi
Method
Train/Val
Small
Large
Small
Large
Small
Large
Small
Large
DFR
4/4
90.610.7
92.9
86.512.3
88.3
84.9
79.73
72.924.7
42.7
AFR
X/V
77. 77.8
90.421.1
71.528
82.0.0.5
72.92+1.7
68.11
37.3
40.3
EVaLS
X/X
78.4
88.4
56.0+10.5
85.3
78.3s19
73.37
76.7
51.2+14
ERM
x/x
74.5+2.9
67.420.6
59.9
47.7
71.3212
65.220.8
59.0
36.822.
Table 3: Effect of batch size on explicit methods performance. Results are grouped by dataset with comparisons between small and large batch sizes. The best result for each dataset is bolded, and colored cells highlight the higher WGA between small and large batch settings for each method. Notably, on the multi-level spurious dataset Domino-CMF using small batch sizes with explicit methods yields particularly significant gains.
Class: Car
Clasc Track
Class
Clisa:
D
2
2
1p-rea/00107
Maet
Lase Staples Mone
2
(a) level spurious
(b) two-level spurious
Figure 5: Illustration of datasets with and 2 level of spurious(a) Domino dataset Murali et al. 2023) pairs label-bearing CIFAR-10 10 image with same-class Fashion-MNIST tile that adds spu- rious shortcut. Debiasing against MNIST shortcut result balanced groups. (b) Domino-CMP Ghaaz navi et al. (2025) uses a CIFAR-I0 10 top and red/green MNIST or FashionMNIST bottom, introduc- ing two level of spurious correlations (style and color). Debiasing against color, lead to still a biased dataset based on FashionMNIST shape.
RELATED WORK
5.1 BATCH SIZE AND LEARNING RATE FOR IN- D--DISRIBUTION GENERALIZATION
Prior work on in-distribution generalization consistently shows that small-batch SGD outperforms large-batch training. Studies focusing on batch size find that, for any fixed learning rate, general- ization peaks at a moderate (non-large) batch size, while very large batches degrade performance (Keskar al. 2017: Smith Le 2018). Most studies examine batch size and learning rate jointly, demonstrating that their ratio controls solution sharpness and, consequently, generalization (Goyal jet al., 2018 Jastrzebski et al. 2017 Chaudhari & Soatto 2018 Park al. (201)). Yet, how these mechanisms extend beyond in-distribution generalization remains underexplored.
5.2
BATCH SIZE AND LEARNING RATE FOR ROBUSTNESS
The effects of batch size and learning rate on robustness are more nuanced. In adversarial training, Wang et al. (2024); Yao al. (2018) vary the inner mini-batch size used to generate adversarial examples and show that increasing this batch size improves certified robustness up to moderate scale, after which gains saturate. Beyond adversarial settings, smaller batches have been shown to improve performance under data imbalance (Shwartz-Ziv et al. 2023). In contrast, robustness to label noise favors the opposite regime, large batch sizes and small learning rates, highlighting a tension between hyperparameter choices that address different robustness objectives (Rolnick al., 2018). More recently, higher learning rates have been observed to reduce shortcut reliance and im- prove robustness (Idrissi et al. 2022 Puli et al. 2023 Barsbey al. 2025). Despite these empirical findings, the mechanisms linking learning rate and especially batch size, to group robustness remain largely unexplained.

---

5.3 CONNECTION TO DOMAIN AND OUT-OF--ISTREE DISTRIBUTIN GENERALIZATION
In the domain generalization literature, reducing gradient variance across domains has been consis- tently shown to improve out-of-distribution performance Rame al. : et al. (2022). this work we show that similar principle arises in the context of mini-batch training: each mini-batch can be interpreted as a domain sampled from the overall training distribution. Smaller batch sizes in- crease the likelihood that mini-batch will contain disproportionate representation of underrepre- sented samples relative to the majority, thereby inducing varying spurious correlations. Controlling the variance of mini-batch gradients effectively enforces robustness to such distributional shifts. In other words, minimizing gradient variance across mini-batches encourages the model to rely on fea- tures that remain stable across changing correlation patterns, thereby promoting out-of-distribution robustness.
DISCUSSION
Our study highlights how learning rate and batch size influence reliance on spurious features, through the lens of implicit regularization. We show that SGD mitigates shortcut dependence, es- pecially with smaller batch sizes and larger learning rates, while GD offers no such benefit and even exacerbate it. The distinction arises from different mechanism of implicit regularization of these algorithms: GD penalizes full-batch gradient norms leading to flatter minima, whereas SGD also reduces gradient variance across mini-batches, fostering robustness for underrepresented groups. This explains the advantages of high learning rates and small batches for group robustness, showing that robustness can emerge naturally from SGD's inductive bias. We hope this work lays foundation for further research and reduces extensive hyperparameter tuning by encouraging smaller batch sizes leverage SGD's implicit regularization.
REFERENCES
Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Jean-Christophe Gagnon-Audet, Yoshua Ben- gio, loannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out-of-distribution generalization. Advances Neural Information Processing Systems, vol- ume 34, December 2021. URL http::://prcceeiiiitit fi File/jichsFOLfeF
nwwriee. http:ippp.ccpppppp////////
pdf Spotlight.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:1907.0289) 2019. htttt:: orq/ abs abw.aa/ss..aaa/...a//..a//.aaaee 1907. 02893
David G.T. Barrett and Benoit Dherin. Implicit gradient regularization. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Melih Barsbey, Lucas Pricto, Stefanos Zafeiriou, and Tolga Birdal. Large learning rates simulta- neously achieve robustness to spurious correlations and compressibility. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2025.
Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced metrics for measuring unintended bias with real data for text classification. In Compan- ion Proceedings of The 2019 World Wide Web Conference, WWW '19, pp. 491-500, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450366755. 33C8560 3317593
doi:
10.1145/3308560.33175999 URL /tRpsttts:/// 1145////..1111////. 1145//3381168600
Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, converges limit cycles for deep networks. In International Conference Learning Represen- tations (ICLR) Workshop ITA 2018, 2018.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the As- sociation for Computational Linguistics, 2019a. URL https:/ //pp. semanticscholar: Btt//CorppuSD::5277339
10

---

Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. 2019b. URL attpss//axxiv.orr
abs/ 04805
R. Geirhos, J.-H. Jacobsen, C. Michaelis, R. Zemel, W. Brendel, M. Bethge, and F. A. Wichmann. Shortcut learning in deep neural networks. Nature Machine Intelligence, 2(1 2(11):665-673, 2020.
Mahdi Ghaznavi, Hesam Asadollahzadch, Fahimeh Hosseini Noohdani, Soroush Vafaie Tabar, Hosein Hasani, Taha Akbari Alvanagh, Mohammad Hossein Rohban, and Mahdich Soleymani Baghshah. Exploiting what trained models learn for making them robust to spurious correlations without group annotations. In Workshop on Spurious Correlation and Shortcut Learning: Founda- lions and Solutions, 2025. URL
net forum? dd-oooidddoooloo YSAt 6g
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. URL org
Priya Goyal, Piotr Dollár, Ross Girshick, Picter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour, 2018.
Ernst Hairer, Christian Lubich, and Gerhard Wanner. Geometric Numerical Integration: Structure- Preserving Algorithms for Ordinary Differential Equations, volume 31 of Springer Series in Com- putational Mathematics. Springer- Verlag, Berlin, 2nd edition, 2006, ISBN 3-540-30663-3 (hard- cover), 978-3-540-30663-44 doi: 10. 100703--0500
Second edition.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition, 2015. URL.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Badr Youbi Idrissi, Martin Arjovsky, Mohammad Pezeshki, and David Lopez-Paz. Simple data balancing achieves competitive worst- worst-group- group-accuracy. In Bernhard Schölkopf, Caroline Uhler, and Kun Zhang (eds.), Proceedings of the First Conference on Causal Learning and Reasoning, volume 177 of Proceedings of Machine Learning Research, pp. 336-351. PMLR, 11-13 Apr 2022. URLhttps: httpttttttppoceeeeeeee http://pttceee..ccce///o mlr http://iinnn.m...p.pessss//////
html
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Ben- gio, and Amos J. Storkey. Three factors influencing minima in sgd. ArXiv, abs//771.00422 2017. URL https: www.ateissssiioo. ar wwt.oo////ooooo Coruss ID: 7311295
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations (ICLR) Workshop, 2017.
Polina Kirichenko, Pavel Izmailov, and Andrew Gordon Wilson. Last layer re- re-training is sufficient for robustness spurious correlations. In International Conference on Learning Representations,
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 Leskovee, 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 (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 5637-5664. PMLR, 18-24 Jul 2021a. URL hettps://proceeda:
mlr wwt.mmttts...////ee/eceeeo http//hhhlaa...t
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.
11

---

Wilds: A benchmark of in-the-wild distribution shifts. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Interaational Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 5637-5664. PMLR, 18-24 Jul 2021b. URL
ptttps://proceedinng /tt.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced re- search). 2009. CtLLhttp:///
www. cs
html
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In International Conference on Computer Vision, 2015. URL. httts:://rxiv..or abs/
1411. 7766
Ekdeep Singh Lubana, Eric J Bigelow, Robert P Dick, David Krueger, and Hidenori Tanaka. Mech- anistic mode connectivity. In International Conference on Machine Learning, pp. 22965-23004. PMLR, 2023.
Nihal Murali, Aahlad Manas Puli, Ke Yu, Rajesh Ranganath, and Kayhan Batmanghelich. Beyond distribution shift: Spurious features through the lens of training dynamics. Transactions on Ma- chine Learning Research (TMLR). 2023.
Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understanding the fail- ure modes of -ut-of-distribution generalization. In 9th International Conference on Learning Representations, ICLR 2021, May 2021. URL hatp::://ppereeviiee new.ne/// forum?id
ESTD6NFIW b. Poster.
Jorge Nocedal and Stephen Wright. Numerical Optimization. Springer Series in Operations Re- search and Financial Engineering. Springer, 2 edition, 2006. doi: 11110077978---337-0005-----
Daniel S. Park, Jascha Sohl-Dickstein, Quac V. Le. and Samuel L. Smith. The effect of network
width on stochastic gradient descent and generalization: an empirical study, 2019. URL
7/arxiv. org wrs/ 905 03776
Aahlad Manas Puli, Lily H. Zhang, Eric Karl Oermann, and Rajesh Ranganath. Out-of-diistriuutin generalization in the presence of nuisance-induced spurious correlations. In International Con- ference on Learning Representations (ICLR), 2022. URL httpt:://////c. http///ppneeeeiieneeeee .ntt/ Forum?1d=12RoR2o33
OpenReview preprint / proceedings version.
Aahlad Manas Puli, Lily Zhang, Yoav Wald, and Rajesh Ranganath. Don't blame dataset shift! shortcut learning due gradients and cross entropy. In A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 71874-71910. Curran Associates, Inc., ca/pper files/paper/2023/ Paneereaeeeeeeeeeeeeeeee
2023. URL
fi ffle:355460000F55f55555555635533
Shikai Qiu, Andres Potapezynski, Pavel Izmailov, and Andrew Gordon Wilson. group robustness by automatic feature reweighting. In International Conference on Machine Learning, 2023.
Simple and fast
org/ abs.ab/......... 11074
Alexandre Rame, Corentin Dancette, and Matthieu Cord, Fishr: Invariant gradient variances for out- of-distribution generalization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepes- vari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 18347-18377. PMLR, 17-23 Jul 2022. URL https: https::/proceedingg mlr press /vlsss/vllo 62 rame22a. html
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive label noise, 2018. URL http:///epppppaeeeeeeeeeesesnrna
Blepammmii--1p111111111 616bbw net forummic=Biii
Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. In International Conference on Learning Representations, ICLR 2021, 2021. URL https:
//openreviews www.:eeeeeeeooommmem.oooaaaaaeee
Poster.
12

---

Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks. In International Conference on Learning Representations, 2020a. URL https:
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterization exacerbates spurious correlations. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8346-8356. PMLR, 13-18 Jul 2020b. URL https://proceeccnng wwr.m.r...... www.sppesssiiii.. wttp:////aaaaaaaaaaa html
Yuge Shi, Jeffrey Seely, Torr Philip H. S. Siddharth N. Awni Hannun, Nicolas Usunier, and Gabriel Synnaeve. Gradient matching for domain generalization. In International Conference on Learning Representations (ICLR), 2022. URL https: Stttps://opereevieee net. forumm/f
vDWBW4 9Hm0
OpenReview preprint / ICLR 2022 version.
Ravid Shwartz-Ziv, Micah Goldblum, Yucen Lily Li, C. Bayan Bruss, and Andrew Gordon Wilson. Simplifying neural network training under class imbalance. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. /RLptttpp:://peeeeveev.
id= i GmDQn4CRJ
Samuel L. Smith and Quoe V. Le. bayesian perspective on generalization and stochastic gradient descent. In International Conference on Learning Representations (ICLR), 2018.
Samuel I. Smith, Benoit Dherin, David Barrett, and Soham De. On the origin of implicit regular- ization stochastic gradient descent. In International Conference on Learning Representations, 2021. URL /ttttps://oeneeeiiee.... net http:///wwwweeeeeeeeoooeeeeeeeee forum?id-rr ot..ommn..........ooo.........
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data, Journal of Machine Learning Reseurch, 19(70): 1-57, 2018. URL BtRL:tts::////t
jmlr org. http://ppprss//1/// 188 html
Zekai Wang, Zhengyu Zhou, and Weiwei Liu. Drf: Improving certified robustness via distributional robustness framework. Proceedings of the AAAI Conference on Artificial Intelligence, 38(14); 15752-15760, Mar. 2024. doi: 10. 10..1609/aaii..... http://aaa.i.......... 28814..99544 UtLhtps: aaai. org/
index. Stt.a//ariieeeeiee///55
Adina Williams, Nikita Nangia, and Samuel Bowman. A broad-coverage challenge corpus for sen- tence understanding through inference. In Proceedings the 2018 Conference the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pp. 1112-1122. 1122. Association for Computational Linguisties, 2018. URL http:/ / ac acwweb. o an ho Mogooooogy//io /11-1111111111111111
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowiez, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers: State-of-the-at natural language processing. In Qun Liu and David Schlangen (eds.), Proceedings of the 2020 Confer- ence on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 38- 45, Online, October 2020. Association for Computational Linguistics. doi: 10.1 10.166///112220. emnlp-demos.6. URL
wrtp:gyyrrrg/00000// emmlp demos 6/
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018
Yihao Xue, Siddharth Joshi, Dang Nguyen, and Baharan Mirzasoleiman. Understanding the ro- bustness of multi-modal contrastive learning to distribution shift. In International Conference on Learning Representations, ICLR 2024, April 2024. URL pettps://openreviie Forum?id=zte 14XJJBBh Poster.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W. Mahoney. Hessian-based analysis of large batch training and robustness to adversaries. In Proceedings the 32nd International Con- the
ference on Neural Information Processing Systems, NIPS' 18, pp. 4954 4964, Red Hook, NY, USA, 2018 Curran Associates Inc.
13

---

Theoretical Analysis
14
Preliminaries
14
A.1.1
Notation
14
A.
1.2
Data Generation Model
15
1.3
Background Theory
15
2
Basic Lemmas
16
A.3
Exponential Results
20
A.3.1
Gradient Descent
20
A.3.2
Stochastic Gradient Descent
24
A.4
General Results
25
4.11
Stochastic Gradient Descent
26
A.4.2
Gradient Descent
27
Experiments
28
Datasets
28
B.2
Experimental Setup
29
B.3
3
Explicit Debiasing Methods
B.4
Optimal WGA and ACC per Batch size
30
B.5
Effect of Batch Size and Learning Rate on WGA and ACC
30
Large Language Model (LLM) Usage Disclosure
30
A THEORETICAL ANALYSIS
A.
PRELIMINARIES
This section introduces notation and reviews set of relevant theorems and theoretical results from prior work. We also present our main statistical data model: the four-point data generation process.
A.1.1 NOTATION
Let [n]] denote (1. n for n E N. Vectors are denoted by bold letters, c.g. X, and scalars are written ordinary letters, for example y. For vector X and for < j. by X we mean the subvector of X from the ith component to the jth component.
Assume binary classification problem with feature vector X X' and binary label y E (-1,1). Here, X' could be any measurable space, but we usually consider X' C Rd for some dimension E our analysis, we consider a linear classifier of the form
F A
[sm X + u X w Rd ||l/|22 11},
where F represents the set of linear classifiers without bias. For given feature-label pair (X, y) and classifier Sax we define the exponential loss Ely, fxx( as
((y, fw (X)) w/
(10)
This loss, when averaged, provides a smooth, margin-sensitive estimate of the classification error rate.
14

---

A.1.2 DATA GENERATION MODEL
We adopt recurrent statistical data model used in related works, particularly in the literature on spurious features, known as the four-point data model. This simple construction captures funda- mental effects of spurious features, while several theoretical and practical aspects of this model are still unresolved.
Definition A.1 (Four-Point Data Generation Process with FIlF). Assume d 2 Let Rad denote the Rademacher distribution over {-1,1}, 1, and let N denote the zero-mean Gaussian distribution with identity covariance I. Fix parameters p E (0, 1) and B 1. The data distribution IP, ( defined via the following hierarchical process:
(x,,)) y) is
Rad,
p
if y,
= y
P if y/,
3 NN Ia-2).
(11)
We then define X - [y, Bz, 3. J. In this construction, X1 B= is the spurious feature, X2 the FIIF, and the remaining d coordinates are independent Gaussian noise.
For some E N, assume the dataset D & ((,,,,)) e [n] consists of n ii.d. samples from Pp for some fixed but unknown E (0, 1) and B > 1. Also, the empirical average loss with respect to DD and for any w E Red with ||wl|2 S is defined as
n
((w)
Eyvi (X,).
(12)
The Good Bad Solutions. In the above model, the first component of the feature vector, X, = always provides a perfect estimate of the label. The spurious component, X₂ = B2, coincides with the label with probability 1 P, in which case it yields larger margin for B > this component provides an incorrect estimate of the label. The remaining d components of X are independent of the label and therefore irrelevant for prediction. We are interested in those solutions w of the linear model that assign significant weight to X1 while placing small weights on the remaining components.
1. However, with probability
For now, assume d 2, i.e., only the core and the spurious components are present. In this case, we partition the parameter space of = [wy. w=]] I into good and bad solutions according the model's 's relative reliance on the spurious feature = versus the core feature
Definition A.2 (Good and Bad Solutions). For any w [wy w=] R we call w bad if Bw, > Wy, and good otherwise, i.e., Bw, I Wy.
In words, solution is classified as bad if the weighted contribution of the spurious feature (scaled by B) dominates that of the core feature; otherwise, it is classified as good.
A.1.3 BACKGROUND THEORY
Barrett and Dherin Barrett Dherin (021) analyzed the effect of finite learning rates on the dy- namics of gradient descent (GD) using backward error analysis, technique from numerical ODE theory [Haieer et al. (2006). Recall that the gradient descent method applied to differentiable loss
((w) with step size 0 is given by
(t+1) f- (( - (t),
Vt = 1, 1,
continuous- analogue of GD is the so-called gradient flow (GF), formulated as the ODE
d (t)
())
AI > 0,
di
which, unlike GD, defined for all real times t. > 0. The goal of such analyses is to compare the behavior of the discrete trajectory w(!) with that of the continuous trajectory w(t) across different cost functions and step sizes The key observation of Barrett & Dherin (2021) is that the discrete
iterates of GD do not exactly follow the gradient flow of the original cost C (w). Instead, they remain close to the trajectory of modified cost function. Formally:
15

---

Lemma A.3 (Trajectory of Gradient Descent, from Barrett & Dherin descent on a differentiable cost ((w) with step size >> O, and assume is sufficiently small. Then, given some mild conditions on C, the trajectory of the iterates w(() resembles the gradient flow trajectory. but with respect to the modified cost
2021
Consider gradient
(u - C(w) + ( [|V[C(w)]*
(13)
where VC(w) denotes the gradient of the original cost.
This result follows from backward error analysis, which shows that for small but finite e, GD iterates track the gradient flow of CGD rather than of the original C.
Smith et al. (2211) introduced an alternative form of backward error analysis that explicitly accounts for correlations between mini- batches within single training epoch. Using this approach, it is shown that for sufficiently small learning rates, the mean Stochastic Gradient Descent (SGD) iterate after one epoch, averaged over all possible mini-batch orderings. remains close to the trajectory of gradient flow on a modified cost function.
Lemma A.4 (Trajectory of Stochastic Gradient Descent, from (Smith et al. 2021)). Consider the setting of Lemma A.3 and assume SGD applied with a sufficiently small step size using m non-overlapping mini-batches with m & n. Then the trajectory of SGD iterates resembles that of gradient flow, but with respect to the modified cost
(SGD(W) A C(w) +
Σ
(14)
4m k=
where (v+ denotes the gradient of the empirical loss on the k-th mini-batch.
Analogous to the GD case, this modified loss consists of the original full-batch loss plus an implicit regularization term. However, the structure of this regularizer differs from that of GD, potentially leading to distinct local and global minima.
We note that Lemmas A.3 and A.4 are derived for unconstrained optimization. Under the exponen- tial loss, however, the unconstrained minimizer lies infinity for separable data, meaning that the norm of the weights grows without bound. To obtain a well-defined solution, we therefore restrict the parameter space the unit ball W {w E Rd | la S 1). In this constrained problem, the minimizer necessarily lies the boundary ||la|| 1.
After the trajectory reaches the boundary, projection removes the radial component of the gradient (which would otherwise increase the norm), and only the tangential component determines how the direction of w evolves along the sphere.
In our analysis, we assume that the first-order modified-loss characterization continues to describe this tangential component of the projected GD/SGD dynamics. Thus, implicit regularization in- fluences not only the loss landscape but also the directional evolution of the classifier within the constrained domain.
A.2
BASIC LEMMAS
In this section, we present a collection of fundamental lemmas that will be used in the proofs of Section A.3 where we state our main results on the comparison between GD and SGD with gradient flow.
Lemma A.5 (Exponential Loss). For constants B > 1 and p E 1/2). and assuming B 2 log((1 p), consider the constrained program
-"= ("u(pe Bw, + (1- (1-p) p)e Bws) subject to w w s 1.
min 305
(15)
Then the optimal solution is given by
e = 2w
w r A), w /1 w²z
x²
v Vp(1 p) (C E- BTA)
(16)
16

---

where X is the Lagrange multiplier at the optimal point and
1 P-P
r _
log
O11/B").
2B
1+ BH-B r 1-12
Proof. For notational convenience set g(w=) = pe. Bw + (1 p)e- -Bw., The optimization problem is
Swwy wz) - g(w=)
min
[W wa) subject to
wy + w S 1.
(wy. ERR
Form the Lagrangian with multiplier X > 0: L(Wly W/ 2) = X (ws + u -1). The
KKT conditions consist of
(i) V Vu VwL(w, A) 0,
(ii) wy + w $
(ii) À (my + u - 1) = O,
(iv) A 2 0.
(17)
Differentiating we obtain
Ow,f = - - wy g(wz) + 2XW, =0 Bv f = uy (w=) + 2\w; = 0,
where g'(wz)= = B (pe - (1- p) Bw:). -)e--B-).. g" (w=) B² If A then -v (w==) = 0,
impossible since the left side is strictly negative. Hence X > 0, and by complementary slackness wy : With À 0 the stationarity equations read
2AW, = "rw'g(w>) 2Aw= = Wx (w:).
Eliminating À gives Wi contradiction), write Wy /1 w². Thus the necessary condition
g (w=))
Since wy (otherwise the first equation would give
s(mu.)
w= g ((ww) g(w2)
w
Define (wwz)= = VI-w?
V (wz) =
(ww))
For we have v'(w)) = (1 (1-w))-00 > 0, hence
s(w,)
is strictly increasing. For v, v V'(w:) ("(w. )o(w g'w Substituting g" gm(w;) B²g(w,)) and simplifying yields
)(w.))²
g"(w=gg(w.) - g' d((w))²= 4p(1-p111111111 Bp 0.
so V(() < 0. Thus + is strictly increasing, strictly decreasing; therefore (*) admits at most one solution. Since the feasible set compact and continuous, a minimizer exists, hence there is exactly one solution w E (-1, 1). The minimizer is therefore
" ((ww) 0.
" v1 2
2w0
Looking back (x), it can be equivalently written as
B De - (1- p) Bw:
-Bw:
= DeBu, + + p)e Bws
- B tanh Bwz + 1 1lg 1-
(18)
We now try to approximate A up to an error of at most )c- 1
Without loss of generality, let us
write wi- = r + with I
2B log( 1-)). Then, we have
T+A
B (ttan((B))
VI- (T+
17

---

By assuming BA < 1, aim approximate A. Therefore, we have tanh BA BA and result, we have
r
B
+ A
+O(A3),
VI P
(1- r2)3/2
which implies the following approximation:
-(1-
A = B² 12)3/2
+ OOTT/B²)
+++I r
: [(1 1 B2
+ +OTBB
(19)
Next, we derive an explicit formulation for Lagrange multiplier X1. We have
hT exp
1
log
1-p
P
1
BT
2
p
p
p
Hence,
s(w²)) = pe
P) e
Bee
-P
I P
BTA +(1 PV
BTA
P
p
= p( P) (e BTA + - BTA)
(20)
Substituting into X+ - (" completes the proof.
2
Lemma A.6. C Rdd that its unconstrained minimizer lies strictly outside the unit ball, i.e., ||arg minw C(w)ll2 > 1. Consider the constrained optimization problem
a twice continuously differentiable cost function, and assume
(w",
A
arg min C(w) subject
| 1
(21)
where, with a slight abuse of notation, denotes the Lagrange multiplier associated with the quadratic constraint. By standard KKT arguments, we have X* 0 at the optimum. Let Rd R be another differentiable function. For sufficiently small > 0, consider the perturbed problem
arg argmin C(w) + =.((w))
subject
1w12211.
(22)
Then the perturbed optimizer satisfies the first-order expansion
T = w 8A* (I w """"" "0 (I+ 2A V'C(ww)) VV((w)) + O(22).
(23)
Proof. Let w = w- + and denote the perturbed multiplier as X X + As E + 0, both
and A vanish. The KKT conditions for the perturbed program are
(i) VC(w" +5) VVww" + +) 2(x* A) + +5) = 0,
(ii) (X* + A) (Ilw* + + - 1) = 0,
(iii) X + 0.
(24)
Since X > 0, condition (iii) is automatically satisfied for small Expanding (i)-ii) to first order yields
(x) V'C(w")6 8 (-V((="w)))) + 2X + Aw" = =O(22)
(x*) 8 dTw n
=(22)
(25)
From (+) we obtain
c I 21-
V'C(w")) "f(w")) +yw",
81a
18

---

where y depends on A. Imposing the orthogonality condition (**) determines y uniquely, ensuring that ö has no component in the direction of w". This yields
8A* (1 w " ") 2A v'C(w")) -1 V VV((w") + O(E2)
c
which proves the claim.
Lemma A.7. Let XI...., N, be i..d Bernoulli(p) random variables with parameter E (0. 1/3). Fix integers m 2 1 and b 2 such that n mb. Partition the indices {L....,n} into m disjoint blocks of size b and let P:
Σ jEblockk i Xj, i = ,,...,m m be the block (mini-batchy averages.
Define the sample variance of the block means by S E (i. p)² 1 Li Pr. Set o² & Var(ps) p(1-)) Fix a confidence parameter Ç E (0, 1). If
b
86 log
2b sblg(( :
a 2 max
(26)
(0(1 - p))
p(1 p)
then with probability at least 1 - we have
p(1 p)
82
2b
2
Proof. For each block write p.
-=== E X where, for fixed the X,D iid.
Bernoulli(p) Then E[p:] P and Var(p.) p(1-p) - 0². Introduce the population second moment about the true mean
Σ (p. p)? 171
Vpp
i=1
Using the identity 1 Σx (p: p)2 = Vpppp (ø p) it suffices to ensure simultaneously
(A) Voop 2 3
and
(B) (p- p)² < 10²;
for then S = Vopp (p- - p)² 2 0² 1 = o We bound the failure probabilities of (A) and
(B) using Hoeffding's 's inequality.
(A) bound. Define Y; (p. p)². The Y, are i.d.d, satisfy 0 s Y, S 1, and E[Y,] = 0². By Hoeffding's 's inequality, for any > 0,
Σ 52 -e) S Sexp - -2mm=).
Taking 0² /4 yields IP (Vpop < -0² exp( - 2m /4)))) exp(
(B) bound. The overall average p is the average of all n = mb Bernoulli draws. By Hoeffding's inequality, for any t > 0.
P(pp - pl 2) $ cxp ( 2nt²).
Set t = 0/2. Then P((p p)² > ) < 2 eexp( 2n(2022222220 = 2 exp( -
no² 2
Using = mb
and 0² = p(1 - p)/b we have no² = mp(1 - p), hence
((B fails) < 2xxp( mp(1 me()-el).
By the union bound,
P((A) fails or (B) fails) < exp( mat + eexp( mp(1 mp(]-p)
To guarantee this is at most ( it suffices to require each summand to be < C/2, i.e. exp( moo
and cxp( mmp1-p)) < Taking logarithms and rearranging gives the sufficient conditions
2
8 8log(2/C) and m> p(1-p) 44
2log(4/CC
Substituting ,² = (p(1-p)) ?)) /62 yields the condition displayed in equation 26 Under that condition
the total failure probability is at most Ç, so with probability least 1 Ç both (A) and (B) hold and therefore
0²
p(1 - p)
S
2b
claimed. The proof is complete.
19

---

A.3 EXPONENTIAL RESULTS
Recall the four-point data generation model and the respective exponential loss function from Sec- tion A.1 According this setting, the cost function ((w) can be rewritten follows:
((w)
Vys ( (X.))
n viw '
(e 1/z + Vi + e-- Bus 11z1 Wib3
i=1
Byy
Bwz
-
1
Σ 1 2 # veb
+ +e ee-Bu= Bw=
1
i=1
E my (pe
(1 π) Bws)
(27)
where
Σ
1
12
denotes the empirical fraction of samples with misaligned spurious component with respect the core label y. Note that [[p] = p. Moreover, by a Chernoff bound, for all s > 0,
p - pl 2 2) 2e n=a
(28)
In the following subsections, analyze how i) Gradient Descent (GD) and ii) Stochastic Gradient Descent (SGD) with strictly positive step sizes e > (and, for SGD, a specified number of mini- batches m) affect convergence to the optimal point of the above loss. In both cases, compare the resulting solution to the optimal w the linear classifier at the minimum loss.
Specifically, Theorem A.8 shows that GD, relative to gradient flow, increases the reliance the spurious feature by raising the optimal value of Wz, which undesirable.
In contrast, Theorem A.9 surprisingly demonstrates that SGD reduce reliance the spurious feature, particularly when small batch sizes are used. Our results hold with high probability over the randomness of the training data and provide strict, concrete, non-asymptotic bounds the increase or decrease of Wz-
A.3.1 GRADIENT DESCENT
This thcorem is our main result on gradient descent.
Theorem A.8 (Main Result Gradient Descent for Exponential Loss). Assume the four-point data generation model described in Section A.1.2 with parameters E (0, }) and B > 1. Let D (X1, (X), be a dataset of i.i.d. samples drawn from this model. Assume
3 2 log
1-2
2 2 288 log "
B
for some Ç E (0, Let WOGGD denote the solution obtained using gradient descent with suf- ficiently small step size e > 0, and w be the solution using gradient flow. Then, there exists a constant C > 0, depending only B and satisfying C = O with respect to B, such that
wa,G - w Z Cc +(())
with probability at least 1 with respect to the randomness of drawing D.
The proof provided after brief discussion. The theorem considers a four-point data generation model with hardness parameter B > 1 (see Section A.1.2) and misalignment probability p. It states
that, as long as B is sufficiently larger than the logarithmic ratio log I- and n is moderately
20

---

large that p and p do not deviate significantly, GD always increases reliance spurious fea- tures by increasing w/.- The magnitude of this increase, up to first order in the step size > 0, is proportional to both and v -), p). but does not grow unboundedly with B.
The conditions in the theorem intuitive: when B is very close to 1 (especially for moderate p), the spurious feature far less strong than the core feature from a margin perspective. In this regime, reliance the spurious feature inherently small, and the analysis becomes cumbersome. Apart from this, no additional restrictions are imposed.
The proof relies tools from constrained optimization and KKT theory, combined with concentra- tion bounds and basic linear and nonlinear algebra.
Proof of Theorem A.8 The proof proceeds in four stages:
Concentration of p: First, we show that the empirical quantity ÿ-the fraction of samples in D with counter-aligned core and spurious features (y. concentrates around the true value with high probability.
Gradient of the perturbation term: We leverage Lemma A.6 and compute the gradient the additional perturbation term, vf(w"), where
[(n) 4
[VC(w)
1 Ve.
and u² denotes the optimal solution of the unperturbed problem (i.e., the gradient flow
solution). Lemma A.5 provides explicit expression for this unperturbed solution w".
Computation of the matrix term: Next, compute the second component required by Lemma A.6 namely
I - --ww"" w"w"" (I+ 1 v²C(w")) 2
Analysis of the final solution: Finally, analyze the resulting solution and determine the condition under which it is positive-i.e., when gradient descent increases the reliance on the spurious feature by enlarging Wzz. We show that this holds under the stated constraints of the theorem, and we further simplify the magnitude of this increase.
Concentration of around p: For the remainder of the proof, work with the empirical quantity p in place of the statistical parameter p, where
Σ
1( + wch
(30)
since only أ appears in our subsequent formulas. By the Chernoff bound, have
PP 1 - pl EE) S 2exp
ne
(31)
Note that < $. and the condition B 2 log 1- implics B log 1-2 i. + 1.
provided that 12. Thus, it suffices to ensure 1p p < 12 Applying the Chernoff bound, we see that this event holds with probability least 1 whenever
n 288 log
Henceforth, we condition on this event and proceed under the assumption that B log 1-B
Computing V fw=": Next, we aim compute V f(() the optimal point w where (as defined above) is the perturbation term which is added to the original cost due to applying Gradient Descent (GD). In this regard, we have the following relations:
C(w) (pe Bor (1 p)e Bu: e
VC(w) (C((w) Be-w, (peBus (1 -ppe-- Bus
-))--Bus)
(32)
21

---

Therefore, we have
IVC(w))11 -C + -20, e (1 2)
2Bw. - -2p((1 ())
=(1 + B²) (p² e 2Bw, + +11 (1-p))
- - 2Bm, - 2w1
- (B² - 1) - pi)ee 2mly.
(33)
The above can be represented in the following compact form:
f(wy: w.) e 2 (1 + B2) 2B e eBB (1 (1-p)
2(B2 -1
We aim to compute the term V v at the optimal point of the constrained ordinary loss, which is already carried in Lemma A.5 i.e.,
w²
Wyy w==
w² -
W
where A
28 log 1-Ø and A defined according to the lemma. Define the auxiliary function
g(-)
g(wz) (1 B²) _ 2Bm p² te -2Bm. (1-1(111)))1 p)}] -2(B² 1)p(1 p).
Then f(wy, wx) 2w, g(w), , so the gradient is
8f Dur af Jws
- 2e 2v0 g(wz) 210
f
e 22w (w==
This way, have
g((w.) = (1+ 11++B)) [2B 2Bw Φ -BBe -2Bw= (1 - |)
= 2B + B²) 2Bw p² 2B (1 - p)
(34)
where the terms can be simplified as follows:
Wz 2B
1 1
log
+IA
2Bw= 1 -- 2BTA 2Bw
p
e 2
P
1
Then
((ww)) 2BB11 B²) p)e 2BTA
p(1
D)E 2
-11(1 B²) - p) sinh(2B
(35)
On the other hand, using the same logic, we simply have
B²
g(w,) 2(1 + B²) p) (cos)(2BTA)
B3 +
Hence,
f((w)) -4(1 + B²) p)e 2n, (cosh(2BTA)
B²_1
B2+
Bsinh(2BBB
Computing the matrix (I w TT (I+ 2x- V²C(w")) ' We now aim to find closed-form
formula for the 2 x matrix which should be multiplied to vf(w"). Recall the auxiliary function Bws Then, C(w") = = =e-wug(w=) and therefore the Hessian matrix
g(w>)= مe Bw: + pBe-Bus
can be written as
C
-O...
V²C(w") (-aw.
B²C
with Ow,, 1 (ppeBul (1 -Bw)). Using the special choice of T, we simplify
g(wx) 2 p) cosh (BT)); g'(wz) -2 p( p) (BTA)
hence
= = 2 w, p( 1 - p) cosh BTA),
O,,, C -2B " V p(1 p) sinh BTA)
(36)
22

---

Since X² -- Wy
Vp(1 p) cosh(BTA), obtain
B (tanh(BrA)) )
vCC(w") 20yx" taan((BBA)
B
which leads to the following formulations:
M - I+ 1 V²C(w") ( (((n)
1 Wy Buy tanh(BrA)
Bwy tanh(Bra) 1+ Bruy
2
1 + B²
- -Bwy tanh(BrAA)
M det(M) (BBy, tanh (BTA)
(37)
1 1 wyy
where the determinant can be computed det(M) (1 wy+ B wy wu tanh (BrA). Since w (wy, w.)² satisfies wÿ + w² 1, the tangent-space projection operator can be written as
p I wn"""" -Wy WyyWl
uy [02
w wy
wyy00 10
1 w
Then, have the following final formulation:
I 1 v2((w"))
P
(38)
2x-
w + BZuy + BwGw, tanh Canh(BAA) W1 (1+ + B²a wyy Bug tanh ()
- -ww tanh -WyWy (1 + wyy) Buy w- tanh BTA) + u + wyy
det(M)
Determining WGD w": We now determine the sign and magnitude of the change in wt when the implicit regularization term induced by Gradient Descent (GD) is applied to the original cost function. By Lemma A.6 have
(I - wn www"===))) (T+ I+
1 v'((w")) V\(w)) 2X"
W GD
w
+ +0(2)
82*
4(1 + B²) Die 2wy
wy 0(
8 my
p(1 P) cosho (Bo)(BBA))
e(1 B²) p(1 P)e "y
wy G
(39)
2 cosh BTA)
where defined as
Gi + G2
G
+ w1 + BBw,)) Be tanh (BTA)*
G A (I((1 + B²ur,) - Bwü lanh (BT () cosh((BBA)) B²-1
B=41)
G2 2 B (Bw, we tanh (Brl) + (1 (1++w,,))) wy)) (2BBA).
(40)
Noting I' < 2/3 due to the assumptions of the theorem, we have A < 1. Then, applying Taylor expansion (valid for A & 1) and keeping only first-order terms yields
2 2w=
2B2 w. (B2 + wyy) + 11 +
G =
A. (B² + 1)(1 + w1 + B2w,)
(41)
(B² + 1)(1 +wy
Thus, G 2 0 whenever
W/ (1+ + B2
A >
+ O(B-3)
BdT my (B2 + wy) +1)
B + )
(42)
23

---

This implies that the reliance the spurious feature (measured by w2,GD) is strictly larger under GD than under gradient flow. On the other hand, we always have
A 1 + B + O( 2 1 +O(BB))
for sufficiently large B, ensuring that the above condition is satisfied. Finally, note that G = O(B-2) 2) by definition, and
<1+ (1+B))ptt p)e Wy wy OBB-BBBBL-LL--- p))
2 cosh (BTA)
Therefore, the unbounded terms with respect to B cancel out, and the proof complete.
A.3.2 STOCHASTIC GRADIENT DESCENT
This theorem is our main result on gradient descent.
Theorem A.9. [Main Result Stochastic Gradient Descent for Exponential Loss] Assume the four- point data generation model described in Section 1.1.2 with parameters p E 100 3) Let D = {XX, 1,9:))==11 be dataset of n. i.i.d. samples drawn from this model. Suppose that
1) and B > 1.
8b logl)
2b +
log (1-)).
B 2
T M max
p(1 D) S
2
(0(1 p))2
for some Ç E (0, 1). Let SSGDD denote the solution obtained using stochastic gradient descent with sufficiently small step size e > 0 and minibatch size b 2 over a single epoch, and let w be the solution using gradient flow. Then there exist constants C1, C2 > depending on (B, p) and satisfying C1, C2 = @(1) with respect to both parameters, such that
C2 Be
w SGGG w S CCcE/p11-p)
+ O +B b(
(43)
with probability at least 1 - with respect to the randomness Df
Proof of Theorem A.9 A.9 We revisit the derivation for gradient descent, now in the stochastic setting.
From Lemma A.4, recall that the surrogate cost for SGD is
CSGD (w)) C(w)
Σ
VC. (C
(44)
4m
where (w) ) the empirical cost on ith minibatch of size = n/m. ps denotes the fraction of "bad" samples (those with # y) in minibatch i, then
Cr(wx) (p:e + (1 pi)e BBss) e-
(45)
-c,(w)
VČ,(w)=
(46)
BB tyy (w. -(1 pi)e -Brs)) -t))-B
Consequently,
(v((w) ||= 2= = (w) + B2e 22y (0)e2Bus + +1-1i)²² -2Bw, - 2pp pi))
= B²) (pf 2Bw= + +1 c -2w0 - -((B² 1)p;(1
pi)e 201
-2wy.
(47)
Substituting into CSGD w) yields
2Bw 1
(so = C(w)= + _ 2my
(1 (1)
2Bm,
2 +
Σ pt)
pi
1
m
1=1
1=1
- 2(B22 1) 1)
P1(1 pi)
(48)
i=1
24

---

Define the minibatch averages
172
(1-p)² p)²
Σ pi);
p(1 p)
1 m
m
P:(1 pi).
Then CSGD can be expressed as perturbation of CaD:
CSGD(w) CGD(w) + @Var(ptm)) 2w, (2) +e = +2B22 2(BB-11)) (49)
where Var(P).m) p2
2 is the sample variance across the minibatch proportions.
The remainder of the proof is very similar that of Theorem A.8
Defining the above residual perturbation term as (Var(Pt:)))(() Lemma A.6 applies. Therefore, we need to find how the addition of perturbation term would alter the solution from GD. As in the proof of Theorem A.8 one needs the operator
[I - wen wGD)
(I +
2X
which suffices at zeroth order in The same holds for V fu(mn)) Consequently, one can simply consider the and Cc:) of the ordinary (non-GD) loss and use the result of Theorem A.8 Carrying out the calculations gives
cosh (logI=((1- A) + ++
ff(w=) = 4411 + B 2
(50)
Bishnh log 1 (1 (1- A)
After simplification, and noting the fact that due to the assumptions of the theorem we have w < 2 log( 1e) and A << L, this term contributes as rho
V'CoD(wGD)) 'V(('') = - ( B
wCD a (I
+0()+
O(B
2X"
p(1
Applying Lemma A.6 we obtain
" SCD "O - Be Var(pim)
+ 002)+
(51)
(Ø(1 0))3/2
Finally, Lemma guarantees that, under the stated conditions on n. we have
P (Var(pum)
> p(l-p) 1-
Thus, we have the following with probability at least 1 - (:
- SCD w < 6(evol1- -1) - Be
+ +066++B'
(52)
byp(1-p)
and the proof complete.
A.4 GENERAL RESULTS
We present a general result that does not rely the four-point data-generating model of pre- vious results 1.1.2 or on any specific choice of loss function or model architecture. Based on the Lemma A.4 show that in a generic mixture setting with subpopulations overrepresented (major- ity) and underrepresented (minority), the distributional heterogeneity itself strengthens the implicit regularization induced by SGD. This effect biases the optimization trajectory toward solutions with more uniform performance across subpopulations, thereby reducing the loss gap between Bad solu- tions and group-robust solutions. In contrast, the implicit regularization induced by GD in the opposite direction and amplifies this gap-
Let Dmaj and D Pii denote the majority and minority data distributions, respectively, and let
D, = (1 - --p)Dmmj + +pC D Puins
E (0, 1),
be their mixture.
25

---

A.4.1 STOCHASTIC GRADIENT DESCENT
In the following theorem, we show that the quantitative analysis carried out for the four-point model under the exponential loss in Section A.3 can be extended qualitatively general loss functions (e.g., logistic loss, cross-entropy loss) and general hypothesis classes (e.g.. deep neural networks), at least in the asymptotic case where m. + Specifically, we consider two solutions, Whad and Wgoodd, where Whad relies on spurious correlations but attains a smaller loss value, while ugood exhibits reduced dependence common in practice). We prove that the implicit regularization induced by SGD with sufficiently small minibatch size 6 tends to favor ggood over Wbad by assigning it smaller regularization value.
spurious features but typically incurs larger loss value (as is
The key idea is that hypotheses such as Wbads which rely heavily on spurious correlations, ex- perience significant fluctuations in the number of samples in each minibatch with aligned versus misaligned spurious features. As a result, their minibatch gradients exhibit larger variance and consequently a larger second moment-whice increases the regularization term. In contrast, for the solution Wgond. these fluctuations are controlled due to its reduced reliance on spurious features and prediction based on core. and therefore leading to a smaller regularization penalty,
Theorem A.10 (Main Result (Asymptotic) General Loss Functions and Hypothesis Sets). As- sume any hypothesis set W (e.g.. deep neural networks) and an arbitrary loss function C(w) for E W. Let Wbad; ggood W be any hypotheses. In particular, the hypothesis Whad denotes a minimizer obtained by training on a dataset whose samples exhibit spurious correlations at rate p. while Wgood denotes a group-robust hypothesis whose predictive performance almost-uniform across both majority and minority subpopulations, yet it is not a minimizer of C(w). For some
A 2 assume the following conditions hold:
C(wrad) C(Wgood);
ViEm
(WWgood) "ajj)
(WWgood) min,i
11 S
Viem
|| (
( min,i
112 A
where G(w) = V maj,, (w) and G(w)
min,i = Ve Cmin,, denote the average gradients of the majority and minority distributions within the th batch, respectively. Define the SGD implicit regularization term (ef. Lemma A.4) as
majai
R (w)
4m
km
where m = n//b is the number of mini-batches, in SGD, and denotes the batch size. Then, for
b < p (1 (1-p)) (A =²)
sup VC
we have
SGD (Wbad) > R. R.D. (Wgoood) R.
Proof. We model the random composition of each mini-batch follows. Let a; Binomial (b, p) denote the number of minority samples in the i-th mini-batoi where b is the batch size and p is the minority fraction in the dataset.
The empirical gradient of the i-th mini-batch can then be expressed as
((w) x (()) = a, min,i + (b - cv)) G(w) (wD(w) + majji
()(w)
where D(w)) ((w) G(w) m= and Gmin.. Gmaja are the average of gradients of minority and
min.i
majority samples in the - th batch, respectively. Using Lemma A.4 and taking the large-sample limit n, m -> oo, the expected implicit regularization term becomes
SGD (w) = E {
26

---

Let us define
ww)
-
(a;
pb)
ulww) blp@mai + (1 p manja)
Then we have the decomposition
x ()) =m!w) + 5
By construction,
E (
Var(a:) bp(1 - p),
E|ll |: 6p(1 - -))l 12.
Using the zero-mean property of E
E| x 112 | 122 + E
Substituting the definitions yields
X (0)
112
| (w)) min
+(1 (1- (1--p) +11-p) p)G((e)) mma))
1|2
+ bbpp1 -))l
(53)
2
6² (VC(w)) ||² 6p(1 p)|lD 11
(54)
Substituting into RSGD (Wbad)
R.GD (Wgood) have
R. (Wbad)
R. (w0 gooo
=
X (Wbod) 1/ { (W
(55)
4
e 62
V VC (good) 11-
(56)
4
p(1 p)
(115 ([/mmame))) 113 -1 ((((cooo)))
(13)
(57)
b
< bb
2
VC (TCCladd || (wgo 112
(58)
4
p(1 p) (A²-e")
(59)
b
Since Whad is a stationary point of C, we have IVC((wbol) ) = O. Using condition on b we have:
SGD (w goood) 2 e bb
RD
SGD (Whod) - RD
||VC 12 + sup HuPP||CC()]] 2 0
(60)
4
w
This establishes that and therefore completes the proof.
RSGD (Whad)
2
RS
RSGD (ugood);
A.4.2 GRADIENT DESCENT
Theorem A.1I (General Result on the Implicit Regularization of GD). Consider two parameter vec- tors Whad, good E TR.d. The solution Woad denotes a minimizer obtained by training on a dataset whose samples exhibit spurious correlations at rate p. while Wgood denotes a group-robust classifier whose predictive performance is uniform across both majority and minority subpopulations.
Assume that the corresponding population losses satisfy
C(Wbad) C(Wgood)
Define the GD implicit regularization term (ef. Lemma A.3 as
RCD (w) A VC(w)
Then, we have
RGD (Wbdd)
RRDD (w (Wgood). )
27

---

Proof. Since whad is minimizer of C, it is a stationary point and therefore satisfies (C(Wbad) Consequently,
RD (wbad) - RDD (w (W (Wgood) c
VC
(bad))
-
(61)
4
< 0,
(62)
which establishes the claim.
Theorems A.10 and A.11 show that, for any cost function C' and any model architecture, the mere presence of gradient discrepancies between samples in the training data is sufficient to increase the implicit regularization effect of SGD. This effect acts to reduce the loss gap between shortcut and group-robust solutions. Our findings align with the general understanding of implicit regularization of SGD that smooths the loss landscape by penalizing gradient variance across samples, thereby favoring solutions with more uniform loss across samples. In contrast, full-batch GD lacks this mechanism and, in our setting, exhibits the opposite behavior, amplifying rather than reducing the gap between bad and good solutions.
B EXPERIMENTS
B. DATASETS
In our experiments, we evaluate models on a diverse set datasets that are specifically designed to test robustness against spurious correlations. Each dataset introduces known, controllable spurious feature that can confound standard training methods. Below, we briefly describe the datasets used in our experiments. Some example images from each dataset, including both majority and minority samples, are shown Table 4
Waterbirds (Sagawa et al. 2020a) is synthetic dataset generated by placing bird images from the CUB dataset onto backgrounds from the Places dataset. The task is binary classi- fication: waterbird versus landbird. In this dataset, the background type (water land) is strongly correlated with the bird type, creating a pronounced bias-most waterbirds appear water backgrounds, and most landbirds land. Consequently, models trained normally often rely on the background instead of bird-specific features, which reduces generalization performance for minority groups where this correlation is reversed.
2015) contains over 200,000 celebrity face images annotated with 40 binary attributes (c.g., smiling, wearing glasses, hair color) along with identity labels. It presents multi-label classification challenge, as each image can have multiple attributes simultaneously. The dataset exhibits natural biases in attribute co-occurrence and demo- graphic distributions- for example, blonde hair is far more common among women than men. As result, standard models may rely on hair color shortcut for predicting gen- der, failing to generalize to minority groups where this correlation does not hold. CelebA thus serves valuable benchmark for testing methods that aim for robust and fair facial attribute prediction.
CelebA (Liu et
CIFAR-10 (Car vs. Truck) Lubana et al. (2023) is a subset of the CIFAR-10 dataset (Krizhevsky al. 2009) limited two classes: car and truck. To create a spu- rious correlation, small colored square is added to the top-left corner of each image. The square's 's color is strongly associated with the label (c.g., green for cars, pink for trucks). A small portion of samples breaks this correlation by having an opposite or random color. This setup allows evaluation of whether models rely on the spurious cue or on the object's true shape for classification.
Cmnist Arjovsky et al. (2019) is variant of the MNIST dataset with 10 classes corre- sponding to the digits O through 9. Each grayscale digit is assigned a color determined primarily by its label (e.g., - red, 1 green), while small proportion is colored ran- domly to introduce variation. This setup creates a strong but spurious correlation between digit identity and color, even though the true predictive signal is the digit shape. As result,
28

---

standard models often over-rely color, leading to reduced performance when the corre- lation changes at test time. Cmnist thus serves as a simple and interpretable benchmark for evaluating robustness to spurious features.
Cmnist2 is binary-class variant of Cmnist constructed using only the digits 0 and 1. It follows the same coloring scheme as Cmnist, but restricts the task to distinguishing between two classes, providing simpler setting for studying robustness methods.
Dominoes Murali et al. 2023 is a synthetic dataset designed to examine model behavior under multiple potential spurious features. It pairs CIFAR-10 images with Fashion-MNIST images of the same class (c.g., a "caat" image with a "pullover"), forming composite images. The CIFAR-10 segment serves the primary cue, while the MMNSST segment introduces structured but potentially spurious feature. Models may preferentially use the easier-to-leam Fashion-MNIS" portion during training. Domino supports controlled interventions like removing randomizing the Fashion-MNIST side, making it ideal for studying spurious feature learning and robustness.
MultiNLI Williams et al. (2018) is a dataset where each sentence pair is labeled as entail- ment, neutral, or contradiction. The dataset contains many examples of these three types of relationships. We use a spurious feature from Sagawa al. (2020a), which is the pres- ence of negation words in the second sentence. Because of the way the data was collected, sentences labeled as contradictions often contain negation words.
CivilComments-WIL.D (Borkan al. 2019 Koh et al. (021a) is dataset designed for the task of classifying online comments as toxic or non-toxic. In this dataset, the la- bels are spuriously correlated with mentions of specific demographic identities. Following the evaluation protocol of (Koh et al. [2021a), we consider 16 overlapping groups-cace demographic identity paired with toxic or non-toxic labels.
B.2 EXPERIMENTAL SETUP
For architectures, we used the PyTorch implementations of ResNet-50 (He al., 2016) for Water- birds, ResNet-18 for CIFAR-10 Domino, and CelebA and three-layer MLP with two hidden lay- ers of 128 units for Colored MNIST. ResNet backbones were initialized with ImageNet-pretraine weights; inputs were normalized using the ImageNet mean and standard deviation. Colored MNIST images were normalized with a mean and standard deviation of 0.5 across all channels. For fair comparison of performance under small and large batch sizes, BatchNorm layers in ResNets were replaced with Group.Norm (Wu & He 2018)) using 32 groups as suggested in (mmth et al.] (2021). For the MultiNLI and CivilComments datasets, we used BERT (Devlin al. 2019a). We applied the HuggingFace implementation of BERT (Wolf et al. 2020 and started from the pretrained model weights.
All models were optimized with SGD with momentum 0.9 and weight decay 10-5 and learning rates {10-5, 6, 10-3
10-1). All ResNet models were trained for 300 epochs; the Colored MNIST MLP was trained for 150 epochs.
All reported results for effect of learning rate and batch size on WGA and ACC reported by final model (without model selection based on validation set). In contrast, when analyzing the correlation between the normalized SGD implicit regularization term and WGA, we perform model selection using validation-se set ACC. This approach allows us to approximate the choice of parameters corresponding to local minima.
We used an NVIDIA GeForce RTX 4090 for all runs, except Waterbirds runs with batch sizes of 128 and 256, which were executed on an NVIDIA A 100 (80 GB) to accommodate the memory required to compute the implicit regularization term at the end of training across all splits.
Results are reported as mean + standard deviation over three independent random seeds; seeds affect dataset generation and model initialization.
B.3 EXPLICIT DEBIASING METHODS
AFR (Quu et al. 2023) first trains a model using standard ERM, and then retrains the classifier on a weighted held-out dataset. The weights for each sample are based on the probability that the ERM-
29

---

pretrained model assigns to the correct label, effectively giving more importance samples from minority groups. This approach aims to reduce bias by emphasizing underrepresented groups during the retraining phase.
DFR (Kirichenko et al. 2023 assumes that ERM-trained models are capable of capturing the core, invariant features of the data. It first trains the full model with ERM, and then retrains only the last linear classifier layer using a
subset of the validation set or held-out training data. While DFR minimizes the need for extensive group annotations, it still requires group labels for the retraining step.
EVaLS Ghaznavi al. 2025) (Environment-bassed Validation and Loss-based Sampling) removes the need for group annotations entirely. It leverages the loss values of an ERM-trained model to identify hard misclassified samples and constructs balanced held-out dataset for last-layer re- training. This approach improves robustness to spurious correlations by using high-loss samples as proxies for underrepresented groups, effectively achieving group robustness without explicit group labels.
B.4 OPTIMAL WGA AND ACC PER BATCH SIZE
Across all datasets, worst-group accuracy (WGA) exhibits a substantially larger drop with increasing batch size compared to overall accuracy (ACC). This indicates that once in-distribution generaliza- tion is saturated, implicit regularization continues to drive out-of-disrribution gains by enhancing group robustness. In particular, smaller batch sizes tend achieve the highest WGA, whereas larger batches often degrade it, even when ACC remains nearly unchanged. The consistent gap between AWGA and AACC confirms that improvements in robustness cannot be solely attributed to better average accuracy, but rather to the differential inductive biases induced by the optimization dynam- ics (Table
B.5 EFFECT OF BATCH SIZE AND LEARNING RATE ON WGA AND ACC
Across vision datasets, overall accuracy (ACC) quickly saturates the learning rate increases, while worst-group accuracy (WGA) continues to benefit from stronger implicit regularization (Table ( This effect is particularly pronounced in biased datasets, where higher learning rates substantially improve WGA even after ACC has plateaued. The contrast between biased and balanced settings highlights that optimization dynamics influence robustness more strongly than average accuracy. A similar trend is observed in the text domain on the MultiNLI dataset (Table G). indicating that the relationship between learning rate, batch size, and worst-group robustness generalizes beyond vision tasks.
C LARGE LANGUAGE MODEL (LLM) USAGE DISCLOSURE
We used large language models (LLMs) only for editing support (clarity/grammarr) and for minor non-core code cleanup (formatting, doestrings, renaming, etc.). All LLM-assisted edits were re- viewed by the authors, who remain fully responsible under the ICLR 2026 policy.
30

---

WGA (mean std)
ACC (mean std)
Biased
Balanced
Vahie
-2
-2
-2
log(e)
logle)
logle)
log(e)
logle)
log(e)
CMNIST
b
b= 16
b 32
64
= 128
b= 256
log(e)
leglen
logle)
log(e)
log
log(n)
(b) CMNIST2
128
b- 256
Value
logle)
logle)
logle)
logle)
loglé)
logie)
(c) Domino
D 16
0=3
128
256
log(e)
logle)
logle)
logle)
logle)
logiz)
(d) Waterbirds
1.0
64
128
256
0.5
4
2
4 log(e)
(og(c)
loglen
logle)
log Lm)
logtn
(e) CelebA
0.5
(og(e)
logle)
(ogle))
log(e)
logle)
logiz)
(i) CIFAR10
Figure 6: WGA and ACC across batch sizes (b) and learning rates (c) for biased (p = 5%) and balanced datasets. After ACC saturates (dashed lines), increasing the learning rate substantially boosts WGA (solid lines). The effect is stronger in biased datasets (orange) than in balanced ones (blue).
31

---

Table Representative examples of majority and minority groups from the benchmark datasets (Waterbirds, CelebA, C-MNIST, CIFAR-10, and Domino). For each dataset, majority and minority samples are shown side by side to illustrate the spurious feature: background Waterbirds, hair color in CelebA, digit color in C-MNIST, small square in the left corner in CIFAR- 10, and number position in the lower part of each image in the Domino dataset.
Dataset
Group
Examples
Majority
Waterbirds
Minority
Majority
CclebA
Minority
Majority
CIFARIO
Minority
Cmnist
Majority
Z
3
6
8
9
Minority
2
3
L
8
9
Majority
Domino
Minority
32

---

Table 5: Optimal learning rates and their corresponding WGA and ACC on the test set, reported as mdd (%) for each batch size across biased datasets with spurious correlation 5%. The highest and lowest values for each dataset are highlighted in blue and yellow, respectively. At the end of each dataset block, A is defined as the difference between the maximum and minimum values. The magnitude of changes in WGA exceeds that of ACC across all datasets, suggesting that improvements group robustness are not merely a byproduct of in-distribution generalization enhancement achieved through strong implicit regularization.
CMNIST
CIFARIO
b
WGA*
ACC
WGA
ACC
8
10 3
67.5+1.1
99.5+
10
80.1+2.2
98.7+0.1
16
10
68.441.2
99.5+0.0
16
10-3
78.9+1.7
98. 98.8+0.1
32
10
68.0+1.9
99.640.0
32
10-3 3
79.641.7
98.9 98.940.2
64
10
67. 4U.6
99.5
10 2
78 78.842.8
98 98.8+u.1
128
10
66.041.3
99.5
128
10-2 2 76.342.8
98 98.640.2
256
10-2
64.7
99.5
256
10-2
77.942.5
98.7+0.2
A
+3.7
+0.1
A
+3.8
+0.3
Waterbirds
Domino
b
6*
WGA
ACC
b
WGA
ACC
8
10
19.7
97.3
10-4
59.3
97.2
16
10
77.742.8
97.4.10.3
16
10-3
56.343.6
97.4.10.3
32
10
73.2+8.7
96.9
10 2
49.4
96.840.3
64
10-3
67.945.0
97.0+0.33
64
10-2
51.943.6
97.240..
128
10
70.4
97.0.10.2
128
10-2
50.0
96.8
256
68.2 10
10.9
256
10 2
43.4
96.5
A
+11.5
+0.5
+15.9
+0,9
CMNIST2
CelebA
6
WGA
ACC
ex
WGA*
ACC
8
10
99.1+0.2 40.2
100.0+0.0
8
10
46.04
87.641.2
16
10 10-3
99.2+0.2
100.040.0
16
10-1
51.946.8
88. 88.240.6
32
10-3 3
99. 10.2
100.040.0
10-5
45.3
88.4411.2
64
10
99.0+0.3
100.0+0.0
64
10
40.5+2.4
86.641.2
128
10-2
99.0+0.2
100.0+0.0
128
10-4
44.3+1.3
87.2+1.6
256
10-3
98.9+0.1
100.0+0.0
256
10-4
45.0
87.7
A
+0.3
+0.0
A
+11.4
+1.8
Table 6: Effect of batch sizes and learning rates WGA and ACC for the Multi-NLI dataset.
10
10
10
b
WGA
ACC
WGA
ACC
WGA
ACC
8
78. 78.2440.58
81.25
76.75
82.18
76.88
81.72+0.09
16
77. 77.6440.89
81.29
76.58
82.40+0.0
76.31
81.3120.65
32
77. 77.4541.21
82.12+o.61
76.50
81.74+4.20
76.73+0.88
81.59+u.13
64
77 1...5
81.81
75580+11.5
81.93
74.57
79.46=0.00
128
77.7340.86
81.86 1.11
75.
+0.08
80.96 aa.us
73.92
78.33
256
76.7420.48
81.67+0.277
75.17 77.17
79.34-2.00
71.37 20.24
77.93
33

---

WGA
WGA
WGA
2- WGA
b-8 Ape
b-16 Ace
b-52 Ave
b-64 Acc
28 Are
b-256 Ace
0.75
Valoe
0.50
0.90
1e 06
c= 1e 05
t=00001
C= 0.001
c- 0.01
6-011
Learning Rate
(a) CMNIST
0.75
Value
0.50
0.35
6-
z- 05
A- 0.0001
C- 0.001
c- 0.01
0.1
Learning Rate
(b) Domino
1.00
Valuo
0.50
0.25
0.00
05
0.0001
0.001
Learning
Waterbirds
1.00
0.75
Value
0.50
0.25
0:00
6-10-06
0.001
Leaning Rate
CIFARIO
1.00
0.75
Value
0.50
11 06
4- le 06
6- 0.0001
4- 0.001
0.00
2- 0.1
Learning Rate
(e) CMNIST2
0.75
Value
0.50
6.25
1= 06
1= 05
0.0001
0.001
0.01
2- 0.1
Learning Rate
(f) CelebA
Figure 7: Joint Effect of Learning Rate and Batch Size on WGA and ACC. Once the learning rate is sufficiently large to guarantee ACC, smaller batch sizes consistently yield higher WGA across all datasets, indicating improved robustness. is important to note, however, that for very high or very low learning rates, some datasets fail to achieve in-distribution generalization (e.g.. = 0.1 across all datasets or e = 10-6 for Waterbirds). In such cases, reliable conclusions regarding robustness cannot be drawn.
34


Reviews:
[{"review_id": "VqlhO3kMw6", "reviewer": "Reviewer_XpZs", "summary": "This paper investigates how the implicit regularization effect of stochastic gradient descent contributes to group robustness. Starting from a simple four-point linear model containing one invariant and one spurious feature, the authors theoretically show that SGD implicitly minimizes the variance of mini-batch gradients, which discourages the model from relying on spurious or shortcut features. Through analytical comparison with full-batch gradient descent, they demonstrate that SGD systematically assigns lower weights to spurious dimensions when the learning rate is moderately large. The paper further presents empirical results on multiple deep learning benchmarks (e.g., CMNIST, CelebA, Waterbirds, CIFAR10, Domino)", "questions": "See weaknesses", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Within the four-point linear model, the analysis is mathematically valid and well-grounded in prior implicit-regularization theory.\n\nThe paper is clearly written and visually well-organized.", "weaknesses": "The entire formal analysis is restricted to a two-dimensional linear model with exponential loss, where spurious and invariant features are explicitly separable. The main results (Theorems 3.1–3.3) therefore have no direct generalization to nonlinear networks.\n\nThe paper claims that “the phenomenon extends to deep neural networks,” yet the deep network experiments are purely phenomenological and do not demonstrate the mechanism at play.\n\nThe derivation equates “mini-batch gradient variance” with “dependence on spurious features,” which is only true under the toy model’s assumptions. In higher-dimensional or nonlinear cases, gradient variance can stem from many other sources (noise, imbalance, stochasticity).\n\nThe implicit-regularization analysis assumes infinitesimal step size and small learning rate, yet the empirical improvements occur at large learning rates, outside the theoretical validity region.\n\nThe findings largely confirm existing empirical wisdom (“small batch, large lr improves robustness”) without offering new algorithmic insights or a quantifiable predictive model for hyperparameter selection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WDUp26JpjZ", "reviewer": "Reviewer_EN6D", "summary": "This paper proposes the implicit regularization of SGD as a factor in robustness against spurious correlations. The main contribution is a theoretical analysis of SGD implicit regularization in a linear setting, under the four-point data model. The batch size and learning rate are identified as key factors in the bound. Experiments are also provided which transition the insights to neural networks, and training with small batch sizes is proposed as a trick to improve robustness.", "questions": "1. It would be nice to make clear where the $\\epsilon/b$ scaling comes from in Equation 7. I assume the $1/b$ is hidden in the $f$ term.\n\n2. See Weakness 1a/b: how should this paper’s findings be contextualized with the broader literature on a) gradient descent and spurious correlations, and b) small-batch SGD learning?\n\n3. Minor clarity/grammatical improvements:\n\n    a. \\citep should be used on line 52, 72, 196, 293, 410, Fig 5, etc\n\n    b. Malformed citation on line 739, 764\n\n    c. The word “rate” is missing in line 313", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written and easy to follow. The overview of the theoretical results in Sections 2/3 has an appropriate level of detail, and the appendix is nicely organized.\n\n2. The intuitive explanation -- that SGD controls the variance of mini-batch gradients, preventing certain mini-batches from overfitting to the gradient in the direction of the optimal majority group classifier -- makes sense and is illustrated well in Section 2.\n\n3. The dichotomy that full-batch GD increases reliance on spurious correlations while small-batch SGD mitigates it is interesting and to my knowledge novel. More generally, this paper fills a gap in the literature on the understanding of how learning rate and batch size, in conjunction with the implicit regularization of gradient descent, affect robustness to spurious correlations.\n\n4. The experiments in Section 4 are rigorous and interesting, both in the validation of the theory and in providing takeaways for practitioners.", "weaknesses": "1. A related work section is missing. This is important for contextualization of this paper’s results with the literature. A few references are provided in Section 1.1 and 2.1, but results and implications are not discussed in-depth.\n\n    a. Some papers studying theory for gradient descent in the presence of spurious correlations which may be relevant for discussion: [5, 6, 7, 8]\n\n    b. It would also be great to include more references on small-batch or large-LR training in the vein of [2, 3]. Also, I am particularly curious whether the community has found any other robustness benefits of small batch training (as briefly discussed in Section 2.1). I am aware of at least one reference [4] which showed that small-batch training has benefits for adversarial robustness, via a flat-minima argument. Are there more?\n\n2. The four-point data setting is a relatively simple toy setting and has been well-studied since at least [1]. However, I believe this is acceptable for this paper, as its primary contribution is a new analysis of batch size/learning rate effects of SGD, which is still interesting in the four-point data setting.\n\n3. From a technical perspective, it is unclear whether the proof techniques are particularly novel or sophisticated, i.e., whether this paper introduces any methods that might be generalizable beyond the scope of this paper. From what I can tell, the proofs mainly utilize existing results from KKT theory and probability/concentration, with a substantial amount of careful algebra. (Note: I do not consider this criteria as necessary for acceptance at ICLR, but it would perhaps constitute the difference between an 8 and a 10).\n\n4. A minor critique is that only vision datasets are used for the experiments. While not strictly necessary, showing the small-batch results hold on a language dataset or two (e.g., CivilComments, MultiNLI) with a Transformer architecture would be interesting.\n\n[1] Nagarajan et al. Understanding the failure modes of out-of-distribution generalization. ICLR 2021.\n\n[2] Keskar et al. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima. ICLR 2017.\n\n[3] Goyal et al. Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour. ArXiv 2017.\n\n[4] Yao et al. Hessian-based Analysis of Large Batch Training and Robustness to Adversaries. NeurIPS 2018.\n\n[5] Qiu et al. Complexity Matters: Feature Learning in the Presence of Spurious Correlations. ICML 2024.\n\n[6] Yang et al. Identifying Spurious Biases Early in Training through the Lens of Simplicity Bias. AISTATS 2024.\n\n[7] Ye et al. Freeze then Train: Towards Provable Representation Learning under Spurious Correlations and Feature Noise. AISTATS 2023.\n\n[8] Jain et al. Bias in Motion: Theoretical Insights into the Dynamics of Bias in SGD Training. NeurIPS 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "STaTjpUTJw", "reviewer": "Reviewer_AkY5", "summary": "The paper studies the effect of batch size on the reliance of stochastic gradient descent on spurious features. The paper considers a simple 4 point model where there are two binary features, one exactly equal to the label and one spurious feature with high correlation with the label  and the spurious one is also larger in magnitude. The paper studies the solution for this problem returned by gradient descent and stochastic gradient descent with an exponential loss function. It shows that due to implicit bias, gradient descent increases the coefficient of the spurious feature whereas stochastic gradient descent with small batch sizes reduces the coefficient of the spurious feature.", "questions": "Could you please explain the reason for changing the loss function.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper demonstrates an interesting phenomenon relating the implicit biases of different algorithms to their robustness to spurious features. I am not very familiar with the literature on implicit biases but I have not seen this relation being explored before.\n\nThe experiments show that the conclusions also hold to some extent on realistic cases with standard datasets. For a fixed batch size, increasing step size appears to improve the worst group error. For a fixed step size, reducing batch size also appears to improve the worst group error (only if the average error is maintained).", "weaknesses": "The previous works by Puli et al. and Sagawa et al. cited by the paper use the logistic loss function whereas this paper uses an exponential loss function. It would be helpful to explain this change and whether the conclusion continues to hold in the same setting as previous works.\n\nThe conclusions for GD and SGD also need not hold for more sophisticated methods for debiasing, as described in section 4.4.\n\nThe amount of robustness provided by SGD with small batch size seems very small compared with more sophisticated methods in the experiments. If one's goal is to achieve robustness, other methods might be the major factors and the batch size a minor one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)