Computational Cost

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

def nested_cv_cost(
    N,                    # Total dataset size
    K_outer,              # Number of outer folds
    K_inner,              # Number of inner folds
    n_params,             # Number of hyperparameter configurations
    T_train_per_sample,   # Training time per sample (seconds)
    T_predict_per_sample  # Prediction time per sample (seconds)
):
    """
    Calculate total computational cost of nested cross-validation.
    Assumes linear scaling of training time with dataset size.
    """
    # Outer training set size
    outer_train_size = (K_outer - 1) / K_outer * N
    
    # Inner training set size
    inner_train_size = (K_inner - 1) / K_inner * outer_train_size
    
    # ==== INNER LOOP COSTS ====
    # Per outer fold: K_inner × n_params training runs
    inner_trains_per_outer = K_inner * n_params
    inner_train_time_per_outer = inner_trains_per_outer * inner_train_size * T_train_per_sample
    
    # Inner validation predictions (K_inner × n_params × validation_size)
    inner_val_size = outer_train_size / K_inner
    inner_predict_time_per_outer = inner_trains_per_outer * inner_val_size * T_predict_per_sample
    
    # ==== FINAL MODEL TRAINING (per outer fold) ====
    final_train_time_per_outer = outer_train_size * T_train_per_sample
    
    # ==== OUTER EVALUATION ====
    outer_test_size = N / K_outer
    outer_predict_time_per_outer = outer_test_size * T_predict_per_sample
    
    # ==== TOTAL ====
    total_per_outer = (
        inner_train_time_per_outer + 
        inner_predict_time_per_outer + 
        final_train_time_per_outer + 
        outer_predict_time_per_outer
    )
    
    total_time = K_outer * total_per_outer
    
    return {
        'total_training_runs': K_outer * (K_inner * n_params + 1),
        'total_time_seconds': total_time,
        'total_time_hours': total_time / 3600,
        'inner_loop_fraction': (inner_train_time_per_outer / total_per_outer) * 100,
    }
 
# Example: Random Forest with 100 hyperparameter configurations
result = nested_cv_cost(
    N=10000,
    K_outer=5,
    K_inner=5,
    n_params=100,
    T_train_per_sample=0.001,  # 1ms per sample for RF
    T_predict_per_sample=0.0001
)
 
print(f"Total training runs: {result['total_training_runs']:,}")
print(f"Total time: {result['total_time_hours']:.2f} hours")
print(f"Inner loop accounts for: {result['inner_loop_fraction']:.1f}% of total time")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

from sklearn.model_selection import RandomizedSearchCV, HalvingGridSearchCV
from scipy.stats import loguniform, randint
 
# ========================================
# Strategy 1: Random Search (faster than grid)
# ========================================
param_distributions = {
    'C': loguniform(1e-3, 1e3),        # Log-uniform distribution
    'gamma': loguniform(1e-4, 1e1),
    'kernel': ['rbf', 'poly', 'sigmoid']
}
 
random_search = RandomizedSearchCV(
    estimator=SVC(),
    param_distributions=param_distributions,
    n_iter=30,  # Only 30 random samples instead of 10×10×3 = 300 grid points
    cv=inner_cv,
    random_state=42,
    n_jobs=-1
)
 
# ========================================
# Strategy 2: Successive Halving (early stopping of bad configs)
# ========================================
halving_search = HalvingGridSearchCV(
    estimator=SVC(),
    param_grid={
        'C': [0.001, 0.01, 0.1, 1, 10, 100, 1000],
        'gamma': [0.0001, 0.001, 0.01, 0.1, 1, 10]
    },
    cv=inner_cv,
    factor=3,  # Eliminate 2/3 of candidates at each stage
    resource='n_samples',  # Use subsample training at early stages
    min_resources=100,
    random_state=42,
    n_jobs=-1
)
 
# ========================================
# Strategy 3: Bayesian Optimization with Optuna
# ========================================
import optuna
from optuna.integration import OptunaSearchCV
 
optuna_search = OptunaSearchCV(
    estimator=SVC(),
    param_distributions={
        'C': optuna.distributions.FloatDistribution(1e-3, 1e3, log=True),
        'gamma': optuna.distributions.FloatDistribution(1e-4, 1e1, log=True),
    },
    cv=inner_cv,
    n_trials=30,  # Guided, not random
    timeout=300,  # Maximum 5 minutes
    n_jobs=-1
)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

from sklearn.model_selection import train_test_split, GridSearchCV
 
def holdout_evaluation(X, y, model, param_grid, test_size=0.2, cv_inner=5):
    """
    Holdout-based unbiased evaluation.
    
    Cost: K_inner × |params| training runs (same as standard GridSearchCV)
    Bias: Unbiased (final test never seen during selection)
    Variance: Higher than nested CV (single test set)
    """
    # Step 1: Split off final test set
    X_dev, X_test, y_dev, y_test = train_test_split(
        X, y, test_size=test_size, random_state=42, stratify=y
    )
    
    # Step 2: Hyperparameter search on development set only
    grid_search = GridSearchCV(
        estimator=model,
        param_grid=param_grid,
        cv=cv_inner,
        n_jobs=-1
    )
    grid_search.fit(X_dev, y_dev)
    
    # Step 3: Single unbiased evaluation on final test
    test_score = grid_search.score(X_test, y_test)
    
    return {
        'test_score': test_score,
        'best_params': grid_search.best_params_,
        'cv_score_biased': grid_search.best_score_,  # For reference only
    }
 
# Usage
result = holdout_evaluation(X, y, SVC(), param_grid)
print(f"Unbiased test score: {result['test_score']:.4f}")
print(f"(Biased) CV score: {result['cv_score_biased']:.4f}")  
# The gap shows the selection bias that was avoided

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

from sklearn.ensemble import GradientBoostingClassifier
from sklearn.model_selection import cross_val_score, KFold
import numpy as np
 
def nested_cv_with_early_stopping(X, y, K_outer=5, K_inner=5):
    """
    Nested CV for gradient boosting with early stopping.
    
    The inner CV uses early stopping to determine optimal n_estimators,
    which dramatically reduces training cost.
    """
    outer_cv = KFold(n_splits=K_outer, shuffle=True, random_state=42)
    outer_scores = []
    
    for outer_train_idx, outer_test_idx in outer_cv.split(X):
        X_outer_train = X[outer_train_idx]
        y_outer_train = y[outer_train_idx]
        X_outer_test = X[outer_test_idx]
        y_outer_test = y[outer_test_idx]
        
        # Inner loop with early stopping
        inner_cv = KFold(n_splits=K_inner, shuffle=True, random_state=42)
        
        best_params = None
        best_score = -np.inf
        
        # Reduced param grid (don't search n_estimators—let early stopping find it)
        param_grid = [
            {'learning_rate': lr, 'max_depth': md, 'subsample': ss}
            for lr in [0.01, 0.05, 0.1]
            for md in [3, 5, 7]
            for ss in [0.7, 0.8, 1.0]
        ]
        
        for params in param_grid:
            inner_scores = []
            optimal_n_estimators_per_fold = []
            
            for inner_train_idx, inner_val_idx in inner_cv.split(X_outer_train):
                X_inner_train = X_outer_train[inner_train_idx]
                y_inner_train = y_outer_train[inner_train_idx]
                X_inner_val = X_outer_train[inner_val_idx]
                y_inner_val = y_outer_train[inner_val_idx]
                
                # Initialize with large n_estimators; will early stop
                model = GradientBoostingClassifier(
                    n_estimators=1000,  # Maximum
                    **params,
                    n_iter_no_change=10,  # Early stopping patience
                    validation_fraction=0.1,  # Uses part of inner train
                    random_state=42
                )
                
                model.fit(X_inner_train, y_inner_train)
                
                score = model.score(X_inner_val, y_inner_val)
                inner_scores.append(score)
                optimal_n_estimators_per_fold.append(model.n_estimators_)
            
            mean_score = np.mean(inner_scores)
            if mean_score > best_score:
                best_score = mean_score
                # Use median n_estimators from inner folds
                best_params = {
                    **params,
                    'n_estimators': int(np.median(optimal_n_estimators_per_fold))
                }
        
        # Final training with best params (include early stopping result)
        final_model = GradientBoostingClassifier(
            **best_params,
            n_iter_no_change=10,
            validation_fraction=0.1,
            random_state=42
        )
        final_model.fit(X_outer_train, y_outer_train)
        
        outer_score = final_model.score(X_outer_test, y_outer_test)
        outer_scores.append(outer_score)
    
    return np.mean(outer_scores), np.std(outer_scores)