📚TheoryIntermediate

Early Stopping

Key Points

•
Early stopping halts training when the validation loss stops improving, preventing overfitting and saving compute.
•
It monitors a hold-out validation set rather than the training set to approximate generalization performance.
•
Common strategies use patience (allowing several non-improving epochs) and a minimum improvement threshold (mi $n_{d} e lt a$ ).
•
You should always checkpoint and restore the best model weights observed on the validation set.
•
Early stopping acts like a form of regularization, often comparable to L2/weight decay in effect for linear models.
•
Validation curves are noisy, so smoothing or mi $n_{d} e lt a$ avoids stopping due to random fluctuations.
•
Choose patience relative to noise level and epoch time; too small over-regularizes, too large wastes compute.
•
Implementation is simple: track best validation loss, count non-improving epochs, and break when the counter exceeds patience.

Prerequisites

→Supervised learning basics — Understanding training vs validation sets and loss functions is essential for why early stopping works.
→Loss functions (e.g., MSE, cross-entropy) — Early stopping monitors a scalar metric derived from a loss.
→Gradient descent/SGD — Early stopping is applied over iterative optimization procedures like gradient descent.
→Train/validation/test split — A proper hold-out validation or cross-validation is needed to drive stopping decisions.
→Basic probability and expectation — Validation loss estimates expected risk; understanding noise and variance helps tune patience and min_delta.

Detailed Explanation

Tap terms for definitions

01Overview

Early stopping is a training strategy where you pause or terminate learning when performance on a separate validation set stops getting better. In supervised learning, models typically improve on the training set as we iterate, but after some point they begin to memorize noise rather than learn useful patterns. The validation loss—an estimate of how well the model will perform on new, unseen data—usually decreases at first and then starts to increase once overfitting kicks in. Early stopping catches this turning point automatically. Practically, you record the best validation score seen so far and count how many consecutive epochs fail to beat that score by some margin. If the count exceeds a patience threshold, you stop training and often restore the best model weights. This strategy saves computation and commonly improves generalization, particularly when data is limited or models are large. It is lightweight to implement, model-agnostic, and compatible with other techniques like regularization and learning-rate schedules. While simple, you need to pick sensible hyperparameters—patience and minimum improvement (min_delta)—and ensure the validation set is representative to make reliable decisions.

02Intuition & Analogies

Imagine studying for a test with a set of practice questions. At first, each study session helps you understand the material better, so your performance on practice exams (analogous to validation) improves. But after many sessions, you might start memorizing answers to specific practice questions rather than grasping the concepts—that is, you overfit to your practice set. If you track your practice exam scores over time, you’d notice they rise, peak, and then sometimes decline as you keep cramming. A smart strategy is to stop studying intensively when your practice scores stop improving for a while. This avoids burnout and frees your time, while securing the best score you’ve actually demonstrated on practice tests. Early stopping is the same idea for machine learning: the training loss is like how comfortable you feel with the study material (it almost always improves), while the validation loss is like your practice exam score (a realistic check). Because practice scores can wiggle up and down due to randomness—like a bad night’s sleep—we don’t stop at the first dip. Instead, we allow a few non-improving attempts (patience) and only consider “real” improvements that beat the previous best by a noticeable margin (min_delta). We also keep a copy of the best state so that, even if we trained past the sweet spot, we can revert to our best observed performance. This is a gentle, adaptive brake that prevents over-training and keeps the model at its most generalizable point.

03Formal Definition

Consider a learning algorithm that produces parameters

w^{(t)}

after epoch t by minimizing empirical risk on training data

D_{t r ain}

. Let

L_{v a l}

(w) denote the validation loss computed on a held-out dataset

D_{v a l}

. Define the best epoch

t^{*}

up to time t as

t^{*}

ar g min_{0 \leq s \leq t}

L_{v a l}

(

w^{(s)}

). Early stopping with parameters (patience p, improvement threshold

ϵ

) halts at the smallest epoch

τ

such that there is no epoch s in [

τ

- p + 1,

τ

] satisfying

L_{v a l}

(

w^{(s)}

)

\leq

L_{v a l}

(w^{(

t_{τ - 1}^{*}

)}) -

ϵ

, where

t_{τ - 1}^{*}

is the best epoch before

τ

. In words, stop when for p consecutive epochs you fail to beat the best validation loss by at least

ϵ

. The final returned parameters are typically w^{(

t^{*}

)}, not

w^{(τ)}

. This procedure approximates minimizing the true risk R(w) =

E_{(x, y) \sim D}

[

ℓ

(

f_{w}

(x), y)] by using

L_{v a l}

as an unbiased estimator (under i.i.d. assumptions) and choosing a stopping time that aims near the minimizer of validation loss. In linear models trained with gradient descent, early stopping can be interpreted as implicit regularization, shrinking parameters toward zero as a function of training time.

04When to Use

Use early stopping whenever training is iterative and you can measure validation performance per epoch or step. It is especially helpful when: (1) Models are flexible enough to overfit, such as deep networks or high-degree polynomials; (2) Data is limited, making overfitting likely; (3) You want to save compute by not training past the useful point; (4) Hyperparameter searches where you need an automatic, comparable stopping rule across runs; (5) Non-convex optimization where the path to good generalization may not correlate strictly with training loss. It pairs well with learning-rate schedules: you can stop after the last schedule plateau or bake early stopping into each phase. It’s also useful in online or streaming settings by monitoring a moving average of validation metrics. Avoid or modify early stopping when validation curves are extremely noisy (increase patience, add smoothing, or use larger validation sets) or when evaluating very infrequently makes the signal too stale. For tasks with severe class imbalance or mismatched metrics, monitor a relevant metric (e.g., AUC, F1) rather than raw loss.

⚠️Common Mistakes

Using the training loss to decide when to stop. This defeats the purpose because training loss often keeps decreasing even while generalization worsens; always use a held-out validation set or cross-validation.
Setting patience too small. You may stop on a random fluctuation and underfit; prefer larger patience when validation loss is noisy or when each epoch is cheap.
Ignoring min_delta. With floating-point noise, tiny changes look like improvements; require an improvement of at least min_delta to reset patience.
Not restoring the best weights. If you stop after performance has already degraded, returning the last epoch’s weights yields worse results than returning the checkpoint with the lowest validation loss.
Data leakage into validation. If you tune preprocessing or hyperparameters using the validation set repeatedly without a final test set, your validation performance can be overly optimistic.
Monitoring the wrong metric. Choose a metric aligned with your goal (e.g., macro-F1 for imbalanced classification); loss and accuracy can disagree.
Evaluating too infrequently. If you validate every many epochs, you may miss the true minimum; align evaluation frequency with how quickly the model changes.
Forgetting reproducibility. Record random seeds and early stopping hyperparameters; otherwise results are hard to compare.

Key Formulas

Empirical Risk

R_{emp} (w) = \frac{1}{n} i = 1 \sum n ℓ (f_{w} (x_{i}), y_{i})

Explanation: This is the average loss on the training data. It is what training procedures typically minimize directly.

True (Population) Risk

R (w) = E_{(x, y) \sim D} [ℓ (f_{w} (x), y)]

Explanation: This is the expected loss on the true data distribution. We cannot compute it directly, but validation loss estimates it.

Validation Loss at epoch t

L_{val}^{(t)} = \frac{1}{m} i = 1 \sum m ℓ (f_{w^{(t)}} (x_{i}^{val}), y_{i}^{val})

Explanation: Compute the average loss on the validation set using the model parameters after epoch t. Early stopping monitors this quantity.

Best Epoch

t^{*} = ar g 0 \leq t \leq T min L_{val}^{(t)}

Explanation: The best epoch is the one with the smallest validation loss. Early stopping should return the model from this epoch.

Stopping Time with Patience and Threshold

τ = min {t : \forall s \in [t - p + 1, t], L_{val}^{(s)} > L_{val}^{(t_{t - 1}^{*})} - ϵ}

Explanation: Training stops at the first time t when, for p consecutive evaluations, the validation loss fails to improve the previous best by at least epsilon.

Exponential Moving Average (EMA)

\tilde{L}_{t} = α \tilde{L}_{t - 1} + (1 - α) L_{t}, 0 < α < 1

Explanation: A smoothed version of the loss can reduce noise. Monitor $\tilde{L}_{t}$ instead of $L_{t}$ when validation metrics fluctuate widely.

Generalization Gap (proxy)

gap (t) = R_{emp} (w^{(t)}) - L_{val}^{(t)}

Explanation: The difference between training and validation losses at epoch t indicates overfitting when the gap grows large and validation stops improving.

Epoch-wise Training Cost

T (E) = O (E \cdot (n_{train} + n_{val}) \cdot c)

Explanation: Total time is proportional to epochs times the number of training and validation examples times the per-example compute cost c.

Complexity Analysis

Let

n_{t} r ain

and

n_{v} a l

be the numbers of training and validation examples, and let c be the average per-example computational cost for forward/backward passes (including gradient computation). For full-batch gradient descent, each epoch requires O(

n_{t} r ain

· c) time for training and O(

n_{v} a l

c_{f} or w a r d

) time for validation, where c_

f or w a r d \leq c

because validation typically omits backprop. Thus, per epoch cost is O(

n_{t} r ain

· c +

n_{v} a l

c_{f} or w a r d

). With E epochs before early stopping triggers, total time is O(E · (

n_{t} r ain

· c +

n_{v} a l

c_{f} or w a r d

)). In practice, early stopping reduces E relative to a fixed training budget, often yielding significant savings. Space complexity is dominated by model parameters P and any optimizer state S (e.g., momentum buffers), plus memory for a mini-batch. For SGD-like methods, this is O(P + S + B · d), where B is batch size and d is feature dimension; for full-batch, it’s O(P + S + d). Implementations that checkpoint the best model require an additional O(P) space to store the best weights. Tracking early stopping adds only O(1) extra space (best score, counters) and negligible time per epoch. If smoothing (EMA) is used, it adds O(1) additional state and computation per evaluation. Therefore, early stopping’s asymptotic overhead is minimal compared to the training process itself, while its benefit is to cap E by detecting validation non-improvement, often improving both generalization and wall-clock time.

Code Examples

Linear regression with SGD and early stopping (patience)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Model {
5     // y_hat = w * x + b
6     double w = 0.0;
7     double b = 0.0;
8 
9     double predict(double x) const { return w * x + b; }
10 };
11 
12 struct Dataset {
13     vector<double> x, y;
14 };
15 
16 // Mean Squared Error on a dataset
17 double mse(const Model& m, const Dataset& data) {
18     double s = 0.0;
19     size_t n = data.x.size();
20     for (size_t i = 0; i < n; ++i) {
21         double diff = m.predict(data.x[i]) - data.y[i];
22         s += diff * diff;
23     }
24     return n ? s / n : 0.0;
25 }
26 
27 // One full-batch gradient descent step for MSE
28 void train_step(Model& m, const Dataset& train, double lr) {
29     double grad_w = 0.0, grad_b = 0.0;
30     size_t n = train.x.size();
31     if (n == 0) return;
32     for (size_t i = 0; i < n; ++i) {
33         double y_hat = m.predict(train.x[i]);
34         double err = y_hat - train.y[i];
35         grad_w += 2.0 * err * train.x[i];
36         grad_b += 2.0 * err;
37     }
38     grad_w /= static_cast<double>(n);
39     grad_b /= static_cast<double>(n);
40     // Update parameters
41     m.w -= lr * grad_w;
42     m.b -= lr * grad_b;
43 }
44 
45 // Generate synthetic linear data y = 3x + 2 + noise
46 Dataset make_data(size_t n, unsigned seed) {
47     mt19937 rng(seed);
48     normal_distribution<double> noise(0.0, 0.5);
49     uniform_real_distribution<double> xdist(-5.0, 5.0);
50     Dataset d; d.x.resize(n); d.y.resize(n);
51     for (size_t i = 0; i < n; ++i) {
52         double x = xdist(rng);
53         double y = 3.0 * x + 2.0 + noise(rng);
54         d.x[i] = x; d.y[i] = y;
55     }
56     return d;
57 }
58 
59 int main() {
60     ios::sync_with_stdio(false);
61     cin.tie(nullptr);
62 
63     // Create train/val splits
64     Dataset train = make_data(400, 42);
65     Dataset val   = make_data(100, 123);
66 
67     Model model; // starts at w=0, b=0
68     double lr = 0.05;
69     int max_epochs = 1000;
70 
71     // Early stopping hyperparameters
72     int patience = 20;          // allow 20 non-improving epochs
73     double min_delta = 1e-4;    // require at least this improvement
74 
75     double best_val = numeric_limits<double>::infinity();
76     Model best_model = model;
77     int non_improve = 0;
78 
79     for (int epoch = 1; epoch <= max_epochs; ++epoch) {
80         // One training step over full batch
81         train_step(model, train, lr);
82 
83         // Compute train and validation loss
84         double train_loss = mse(model, train);
85         double val_loss = mse(model, val);
86 
87         // Check improvement (lower is better)
88         if (val_loss < best_val - min_delta) {
89             best_val = val_loss;
90             best_model = model; // checkpoint best weights
91             non_improve = 0;    // reset patience counter
92         } else {
93             non_improve++;
94         }
95 
96         // Logging
97         if (epoch % 10 == 0 || non_improve == 0) {
98             cout << "Epoch " << epoch
99                  << " | Train MSE: " << train_loss
100                  << " | Val MSE: " << val_loss
101                  << " | Best Val: " << best_val
102                  << " | Non-improve: " << non_improve << "\n";
103         }
104 
105         // Early stopping condition
106         if (non_improve >= patience) {
107             cout << "Stopping early at epoch " << epoch
108                  << ". Best Val MSE: " << best_val << "\n";
109             break;
110         }
111     }
112 
113     // Restore best weights
114     model = best_model;
115     cout << fixed << setprecision(6);
116     cout << "Final (restored) parameters: w=" << model.w << ", b=" << model.b << "\n";
117     cout << "Validation MSE at best: " << best_val << "\n";
118 
119     return 0;
120 }
121

This program fits a 1D linear regression model using full-batch gradient descent and applies early stopping. It monitors the validation MSE, resets a counter on significant improvements (exceeding min_delta), checkpoints the best weights, and stops once the number of consecutive non-improving epochs reaches patience. Finally, it restores the best weights and reports them.

Time: O(E · (n_train + n_val)) per run, where E is the number of epochs before stopping.Space: O(1) for model parameters plus O(n_train + n_val) to hold the datasets.

Early stopping with exponential moving average (EMA) smoothing and min_delta

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Model {
5     double w = 0.0, b = 0.0;
6     double predict(double x) const { return w * x + b; }
7 };
8 
9 struct Dataset { vector<double> x, y; };
10 
11 double mse(const Model& m, const Dataset& d){
12     double s=0; size_t n=d.x.size();
13     for(size_t i=0;i<n;++i){double e=m.predict(d.x[i])-d.y[i]; s+=e*e;}
14     return n? s/n : 0.0;
15 }
16 
17 void train_step_l2(Model& m, const Dataset& train, double lr, double lambda){
18     // Full-batch gradient descent with L2 regularization (weight decay on w)
19     double gw=0.0, gb=0.0; size_t n=train.x.size(); if(!n) return;
20     for(size_t i=0;i<n;++i){ double err = (m.w*train.x[i] + m.b) - train.y[i]; gw += 2*err*train.x[i]; gb += 2*err; }
21     gw = gw/n + 2*lambda*m.w; // L2 gradient on w
22     gb = gb/n;                // no L2 on bias
23     m.w -= lr*gw; m.b -= lr*gb;
24 }
25 
26 Dataset make_data(size_t n, unsigned seed){
27     mt19937 rng(seed); normal_distribution<double> noise(0.0,0.6); uniform_real_distribution<double> xd(-6.0,6.0);
28     Dataset d; d.x.resize(n); d.y.resize(n);
29     for(size_t i=0;i<n;++i){ double x=xd(rng); d.x[i]=x; d.y[i]=3.0*x+2.0+noise(rng);} return d;
30 }
31 
32 int main(){
33     Dataset train = make_data(600, 7);
34     Dataset val   = make_data(150, 8);
35     Model m; double lr=0.03; double lambda=1e-3; int max_epochs=2000;
36 
37     // Early stopping with EMA smoothing of validation loss
38     double alpha = 0.9;      // higher = smoother
39     double ema = NAN;        // smoothed val loss
40     double best_ema = numeric_limits<double>::infinity();
41     double min_delta = 1e-4; // require this much improvement in EMA
42     int patience = 30;       // allow many small oscillations
43     int non_improve = 0;
44     Model best = m;
45 
46     for(int epoch=1; epoch<=max_epochs; ++epoch){
47         train_step_l2(m, train, lr, lambda);
48         double val_loss = mse(m, val);
49         // Initialize EMA at first observation
50         if (std::isnan(ema)) ema = val_loss; else ema = alpha*ema + (1.0-alpha)*val_loss;
51 
52         if (ema < best_ema - min_delta){
53             best_ema = ema; best = m; non_improve = 0;
54         } else {
55             ++non_improve;
56         }
57 
58         if (epoch % 25 == 0){
59             cout << "Epoch " << epoch
60                  << " | Val MSE: " << val_loss
61                  << " | EMA: " << ema
62                  << " | Best EMA: " << best_ema
63                  << " | Non-improve: " << non_improve << "\n";
64         }
65 
66         if (non_improve >= patience){
67             cout << "Early stop at epoch " << epoch << " with best EMA " << best_ema << "\n";
68             break;
69         }
70     }
71 
72     m = best; // restore best weights according to EMA
73     cout << fixed << setprecision(6);
74     cout << "Restored parameters: w=" << m.w << ", b=" << m.b << "\n";
75     cout << "Final validation MSE (restored): " << mse(m, val) << "\n";
76     return 0;
77 }
78

This variant adds L2 regularization and monitors an exponential moving average (EMA) of the validation loss. EMA reduces noise in the stopping signal. We require min_delta improvements in the EMA and stop if no improvement occurs for patience evaluations. The best checkpoint is restored at the end.

Time: O(E · (n_train + n_val)) per run; EMA adds O(1) overhead.Space: O(1) for model plus O(n_train + n_val) for data; O(1) extra for EMA and checkpoint.

Reusable early-stopping monitor for any training loop

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Generic early stopping monitor for a metric where lower is better (e.g., loss)
5 class EarlyStopper {
6 public:
7     EarlyStopper(int patience, double min_delta)
8         : patience_(patience), min_delta_(min_delta), best_(numeric_limits<double>::infinity()),
9           non_improve_(0) {}
10 
11     // Returns true if training should stop
12     bool update(double current_metric) {
13         if (current_metric < best_ - min_delta_) {
14             best_ = current_metric;
15             non_improve_ = 0;
16         } else {
17             ++non_improve_;
18         }
19         return non_improve_ >= patience_;
20     }
21 
22     double best() const { return best_; }
23     int non_improve() const { return non_improve_; }
24 
25 private:
26     int patience_;
27     double min_delta_;
28     double best_;
29     int non_improve_;
30 };
31 
32 // Minimal toy training loop that calls a black-box evaluate() function.
33 // Here we simulate a noisy validation loss curve that first decreases then increases.
34 double simulated_val_loss(int epoch, mt19937& rng){
35     normal_distribution<double> noise(0.0, 0.01);
36     // A convex curve with minimum around epoch 80
37     double base = 0.5 + 0.002 * pow(epoch - 80, 2) / 6400.0; // ~U-shaped
38     return base + noise(rng);
39 }
40 
41 int main(){
42     EarlyStopper stopper(/*patience=*/10, /*min_delta=*/1e-3);
43     mt19937 rng(123);
44 
45     int max_epochs = 200;
46     for(int epoch=1; epoch<=max_epochs; ++epoch){
47         // ... your train step here ...
48         double val = simulated_val_loss(epoch, rng);
49         bool should_stop = stopper.update(val);
50         if (epoch % 10 == 0) {
51             cout << "Epoch " << epoch
52                  << " | Val: " << val
53                  << " | Best: " << stopper.best()
54                  << " | Non-improve: " << stopper.non_improve() << "\n";
55         }
56         if (should_stop){
57             cout << "Stopped at epoch " << epoch << ". Best val: " << stopper.best() << "\n";
58             break;
59         }
60     }
61     return 0;
62 }
63

This snippet factors early stopping into a reusable EarlyStopper class. Any training loop can call update(metric) each evaluation. The example simulates a noisy validation curve and stops when there is no improvement by at least min_delta for patience evaluations. In a real project, you would also save and restore a checkpoint when best() improves.

Time: O(E) for the monitor (O(1) per update), negligible compared to training.Space: O(1) for the monitor.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Model {
5	// y_hat = w * x + b
6	double w = 0.0;
7	double b = 0.0;
8
9	double predict(double x) const { return w * x + b; }
10	};
11
12	struct Dataset {
13	vector<double> x, y;
14	};
15
16	// Mean Squared Error on a dataset
17	double mse(const Model& m, const Dataset& data) {
18	double s = 0.0;
19	size_t n = data.x.size();
20	for (size_t i = 0; i < n; ++i) {
21	double diff = m.predict(data.x[i]) - data.y[i];
22	s += diff * diff;
23	}
24	return n ? s / n : 0.0;
25	}
26
27	// One full-batch gradient descent step for MSE
28	void train_step(Model& m, const Dataset& train, double lr) {
29	double grad_w = 0.0, grad_b = 0.0;
30	size_t n = train.x.size();
31	if (n == 0) return;
32	for (size_t i = 0; i < n; ++i) {
33	double y_hat = m.predict(train.x[i]);
34	double err = y_hat - train.y[i];
35	grad_w += 2.0 * err * train.x[i];
36	grad_b += 2.0 * err;
37	}
38	grad_w /= static_cast<double>(n);
39	grad_b /= static_cast<double>(n);
40	// Update parameters
41	m.w -= lr * grad_w;
42	m.b -= lr * grad_b;
43	}
44
45	// Generate synthetic linear data y = 3x + 2 + noise
46	Dataset make_data(size_t n, unsigned seed) {
47	mt19937 rng(seed);
48	normal_distribution<double> noise(0.0, 0.5);
49	uniform_real_distribution<double> xdist(-5.0, 5.0);
50	Dataset d; d.x.resize(n); d.y.resize(n);
51	for (size_t i = 0; i < n; ++i) {
52	double x = xdist(rng);
53	double y = 3.0 * x + 2.0 + noise(rng);
54	d.x[i] = x; d.y[i] = y;
55	}
56	return d;
57	}
58
59	int main() {
60	ios::sync_with_stdio(false);
61	cin.tie(nullptr);
62
63	// Create train/val splits
64	Dataset train = make_data(400, 42);
65	Dataset val = make_data(100, 123);
66
67	Model model; // starts at w=0, b=0
68	double lr = 0.05;
69	int max_epochs = 1000;
70
71	// Early stopping hyperparameters
72	int patience = 20; // allow 20 non-improving epochs
73	double min_delta = 1e-4; // require at least this improvement
74
75	double best_val = numeric_limits<double>::infinity();
76	Model best_model = model;
77	int non_improve = 0;
78
79	for (int epoch = 1; epoch <= max_epochs; ++epoch) {
80	// One training step over full batch
81	train_step(model, train, lr);
82
83	// Compute train and validation loss
84	double train_loss = mse(model, train);
85	double val_loss = mse(model, val);
86
87	// Check improvement (lower is better)
88	if (val_loss < best_val - min_delta) {
89	best_val = val_loss;
90	best_model = model; // checkpoint best weights
91	non_improve = 0; // reset patience counter
92	} else {
93	non_improve++;
94	}
95
96	// Logging
97	if (epoch % 10 == 0 \|\| non_improve == 0) {
98	cout << "Epoch " << epoch
99	<< " \| Train MSE: " << train_loss
100	<< " \| Val MSE: " << val_loss
101	<< " \| Best Val: " << best_val
102	<< " \| Non-improve: " << non_improve << "\n";
103	}
104
105	// Early stopping condition
106	if (non_improve >= patience) {
107	cout << "Stopping early at epoch " << epoch
108	<< ". Best Val MSE: " << best_val << "\n";
109	break;
110	}
111	}
112
113	// Restore best weights
114	model = best_model;
115	cout << fixed << setprecision(6);
116	cout << "Final (restored) parameters: w=" << model.w << ", b=" << model.b << "\n";
117	cout << "Validation MSE at best: " << best_val << "\n";
118
119	return 0;
120	}
121

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Generic early stopping monitor for a metric where lower is better (e.g., loss)
5	class EarlyStopper {
6	public:
7	EarlyStopper(int patience, double min_delta)
8	: patience_(patience), min_delta_(min_delta), best_(numeric_limits<double>::infinity()),
9	non_improve_(0) {}
10
11	// Returns true if training should stop
12	bool update(double current_metric) {
13	if (current_metric < best_ - min_delta_) {
14	best_ = current_metric;
15	non_improve_ = 0;
16	} else {
17	++non_improve_;
18	}
19	return non_improve_ >= patience_;
20	}
21
22	double best() const { return best_; }
23	int non_improve() const { return non_improve_; }
24
25	private:
26	int patience_;
27	double min_delta_;
28	double best_;
29	int non_improve_;
30	};
31
32	// Minimal toy training loop that calls a black-box evaluate() function.
33	// Here we simulate a noisy validation loss curve that first decreases then increases.
34	double simulated_val_loss(int epoch, mt19937& rng){
35	normal_distribution<double> noise(0.0, 0.01);
36	// A convex curve with minimum around epoch 80
37	double base = 0.5 + 0.002 * pow(epoch - 80, 2) / 6400.0; // ~U-shaped
38	return base + noise(rng);
39	}
40
41	int main(){
42	EarlyStopper stopper(/patience=/10, /min_delta=/1e-3);
43	mt19937 rng(123);
44
45	int max_epochs = 200;
46	for(int epoch=1; epoch<=max_epochs; ++epoch){
47	// ... your train step here ...
48	double val = simulated_val_loss(epoch, rng);
49	bool should_stop = stopper.update(val);
50	if (epoch % 10 == 0) {
51	cout << "Epoch " << epoch
52	<< " \| Val: " << val
53	<< " \| Best: " << stopper.best()
54	<< " \| Non-improve: " << stopper.non_improve() << "\n";
55	}
56	if (should_stop){
57	cout << "Stopped at epoch " << epoch << ". Best val: " << stopper.best() << "\n";
58	break;
59	}
60	}
61	return 0;
62	}
63