Early Stopping Check

1. Background Knowledge

Early stopping is a fundamental regularization technique in machine learning that halts training when model performance on a validation set stops improving, preventing overfitting to training data. Overfitting occurs when a model memorizes training examples but fails to generalize, leading to degraded validation performance.

Key concepts:

• Validation loss: Metric (typically mean squared error or cross-entropy) computed on held-out validation data after each epoch.
• Patience parameter: Number of consecutive epochs allowed without improvement before stopping.
• Improvement threshold: Often 0 (strict) or small tolerance $\epsilon > 0$ for numerical stability.
• Mathematical intuition: Training loss $\mathcal{L}_{train}(t)$ typically decreases monotonically, while validation loss $\mathcal{L}_{val}(t)$ follows a U-shape: initial decrease, then increase due to overfitting.

The best validation loss is $\min_{s \leq t} \mathcal{L}_{val}(s)$, and we stop if no improvement occurs for patience epochs: $\mathcal{L}_{val}(t-p+1), \dots, \mathcal{L}_{val}(t) \geq \min_{s \leq t-p} \mathcal{L}_{val}(s)$.

2. Algorithm Approach

Sliding window comparison: Track the minimum validation loss seen so far and count consecutive non-improving epochs.

Core logic:

Track best_loss = minimum loss in history[0..current]
Count consecutive epochs where loss >= best_loss
Stop if count >= patience

Pseudocode:

function should_stop(history_losses, patience):
 if len(history_losses) < patience:
 return False

 best_loss = min(history_losses)
 consecutive_no_improvement = 0

 for loss in reversed(history_losses):
 if loss < best_loss:
 break
 consecutive_no_improvement += 1

 return consecutive_no_improvement >= patience

3. Step-by-Step Strategy

1. Base case check: If len(history_losses) < patience, return False (insufficient epochs).
2. Find global minimum: best_loss = min(history_losses) – the target all subsequent losses must beat.
3. Count trailing failures: From the end of history_losses, count consecutive losses $\geq$ best_loss.
4. Decision: Return True if count $\geq$ patience.

Sample walkthrough [5.0, 4.0, 4.1, 4.2] with patience=2:

• best_loss = min([5.0, 4.0, 4.1, 4.2]) = 4.0
• Check from end: 4.2 ≥ 4.0 (count=1), 4.1 ≥ 4.0 (count=2)
• count=2 ≥ patience=2 → True

4. Common Pitfalls

• Off-by-one errors: Forgetting that patience=1 should stop immediately after first non-improvement.
• Empty/insufficient history: Must handle len(history) < patience correctly.
• Floating-point precision: Use tolerance $\epsilon = 10^{-6}$ for loss < best_loss comparisons.
• Misinterpreting "improvement": Improvement means strictly less than best loss (not ≤).
• Wrong window: Don't compare to recent local minimum; use global minimum up to current epoch.

Edge cases to test:

should_stop([5.0], 1) # False (insufficient epochs)
should_stop([5.0, 4.0], 1) # False (improved)
should_stop([5.0, 4.0, 4.1], 1) # True (1 non-improvement)
should_stop([4.0, 4.0], 2) # True (2 equal to best)

5. Time & Space Complexity

Time complexity: $O(n)$ where n = \text{len(history_losses)}

• Finding min(): $O(n)$
• Reverse scan: $O(n)$ worst case (all non-improving)

Optimized version: $O(1)$ amortized using running minimum tracking:

def should_stop(history_losses, patience):
 if len(history_losses) < patience:
 return False

 best_loss = min(history_losses[:-patience+1]) # O(n-patience)
 return all(loss >= best_loss for loss in history_losses[-patience:])

• min() over prefix: $O(n-patience)$
• Final check: $O($\text{patience}$)$
• Total: $O(n)$

Space complexity: $O(1)$ – pure functional, no extra storage needed.

Production optimization: Maintain running best_loss and consecutive_count during training for $O(1)$ checks per epoch.