5.3 Gradients, Condition Numbers, and Regularization Paths: What You Converge To Matters More Than How Many Steps You Take

With the same training data, switching the learning rate causes divergence. Master Chen asks Ah Hua to first inspect the scale, curvature, and objective function before discussing training iterations.

On the same dataset, a learning rate of 0.1 leads to divergence, while 0.0001 results in almost no change. After normalization, the gap between the two behaviors shrinks dramatically. Even when the objective function is convex, optimization speed is governed by scale, curvature, sparsity, and the solver used.

Learning Objectives

• Derive the computational cost of batch and minibatch gradient descent;
• Understand convexity, the Hessian matrix, and conditioning;
• Distinguish the geometric and algorithmic properties of L1, L2, and Elastic Net regularization;
• Use pipeline and cross-validation to select regularization parameters and verify convergence.

1. Batch gradient descent

Linear regression MSE:

$$ L(w)=\frac{1}{n}\lVert Xw-y\rVert_2^2, \quad \nabla L=\frac{2}{n}X^T(Xw-y). $$

Each full-batch dense gradient computation typically requires $O(np)$ operations, rather than $O(n)$ alone. Memory usage, sparse matrix operations, and data loading also impact the overall cost.

def fit_linear_gd(X, y, learning_rate, max_steps, tolerance):
    w = np.zeros(X.shape[1])
    previous = float("inf")
    for step in range(max_steps):
        residual = X @ w - y
        loss = np.mean(residual ** 2)
        gradient = (2.0 / len(y)) * X.T @ residual
        w -= learning_rate * gradient
        if abs(previous - loss) < tolerance:
            break
        previous = loss
    return w, {"steps": step + 1, "loss": loss}

Running a fixed 1000 iterations does not prove convergence. Monitor gradient norm, objective function change, parameter finiteness, and validation performance to assess convergence.

2. Convex does not mean easy optimization

The Hessian of squared loss is:

$$ H = \frac{2}{n} X^T X. $$

It is always positive semidefinite; it becomes positive definite and strictly convex only under specific full-rank conditions. This property leads to a large condition number, elongated contour lines, and oscillations in optimization when using a fixed learning rate, rapid progress along steep directions and slow movement along flat ones.

Normalization improves the conditioning of many optimizers and enables fair comparison of regularization penalties, but it is not a requirement for all tree-based models or closed-form solutions.

3. SGD and Minibatch

• SGD uses an unbiased/random gradient estimate from a single sample;
• minibatch balances vectorization efficiency with gradient noise;
• an epoch represents a rough pass through the data, not an independent sample;
• shuffle, batch size, and learning-rate schedule collectively influence the training trajectory.

When data has temporal or grouped structure, random shuffling may alter the training distribution or disrupt stateful models. Distributed batching increases the need to adjust the learning rate and validate generalization.

4. Choose a Solver

Linear or logical models can use:

• QR/SVD/least-squares solvers;
• normal-equation variants (use with caution due to numerical instability);
• gradient or accelerated gradient methods;
• Newton and quasi-Newton methods (e.g., L-BFGS);
• coordinate descent;
• stochastic variance-reduced methods.

Selection should consider $n$, $p$, sparsity, loss function, penalty terms, memory constraints, and precision. It is not simply "gradient descent scaled up to arbitrary size"; full-data gradient computation per iteration remains expensive on very large datasets.

5. L2, L1, and Elastic Net

L2

$$ L(w) + \lambda \sum_j w_j^2. $$

Applies smooth shrinkage, spreading weights across correlated features and improving conditioning; it does not encourage uniformity of weights.

L1

$$ L(w) + \lambda \sum_j |w_j|. $$

Non-smooth, with solutions that can contain exact zeros. Typically requires coordinate descent or proximal methods to solve. The selection of which column among correlated features may be unstable, and the presence of zero coefficients does not imply the absence of predictive information.

Elastic Net

A combination of L1 and L2 regularization, balancing sparsity with stability in the presence of correlated feature groups. Both regularization parameters and the mixing ratio must be selected through validation.

6. Regularization Strength and Scale

Different libraries may use alpha, lambda, or C=1/lambda, and may apply sum or mean over loss, making parameter values non-comparable across implementations.

The intercept is typically not penalized; one-hot encoding or drop-reference strategies can affect penalty symmetry. When numerical features are not scaled, the same coefficient penalty produces different functional changes in the original units.

7. Pipeline and CV

from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import GridSearchCV
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

candidate = Pipeline([
    ("scale", StandardScaler()),
    ("model", LogisticRegression(max_iter=2000)),
])

search = GridSearchCV(
    candidate,
    param_grid={
        "model__C": [0.01, 0.1, 1.0, 10.0],
        "model__penalty": ["l2"],
    },
    scoring="neg_log_loss",
    cv=group_or_time_aware_cv,
)

Compatibility between specific solvers and penalty terms varies with library versions and should be verified against the current official documentation. Scaling, missing value handling, and selection are all performed within each fold during the fit process.

8. Convergence Warnings Cannot Be Ignored

Failure to converge may stem from:

• Poor scale or condition number;
• Complete separation;
• Under-regularization;
• max_iter being too small;
• Learning rate being too large;
• Solver mismatch with penalty or sparse input;
• Data containing NaN/Inf values or extreme outliers.

Simply increasing max_iter by a factor of ten may only delay identifying the root cause. Compare the objective function, gradient, parameter ranges, and different solvers, and validate all results under the same validation protocol.

9. Regularization Paths and Stability

Track along $\lambda$ from strong to weak regularization:

• training and validation loss;
• sum of non-zero coefficients and coefficient paths;
• frequency of selection across folds;
• calibration and group-wise error;
• convergence status and runtime.

The one-standard-error rule can select a simpler or stronger regularization scheme when performance is comparable. Final selection still depends on business loss, rather than on having fewer non-zero coefficients alone.

10. Why Linear Models Remain a Strong Baseline

• Training and inference are inexpensive;
• Scalable with sparse, high-dimensional features;
• Feature contributions have a clear, interpretable structure;
• Easy to calibrate, monitor, and deploy;
• Often more stable with small datasets.

However, challenges like feature engineering, multicollinearity, extrapolation, and concept drift can still lead to performance degradation. Interpretability stems from the complete pipeline and feature semantics, not from the model class label itself.

Common Misconceptions

• GD per iteration is $O(n)$: This also includes the cost of feature dimensions and data layout.
• The Hessian is always positive definite: It becomes only semi-definite when rank-deficient.
• L1 automatically identifies truly important variables: Correlations and the choice of $\lambda$ can alter the selection.
• A convergence warning can be fixed by simply increasing iterations: First check scaling, separation, and the solver configuration.

Exercise

1. Compare the Hessian condition numbers of unscaled versus scaled data with respect to the gradient descent (GD) trajectory.
2. Assess the Hessian eigenvalues when the matrix X is rank-deficient.
3. Plot the L1 and Elastic Net regularization paths, along with the frequency of cross-validation selection across paths.
4. Compare the runtime and loss performance of QR, L-BFGS, and SGD under identical cross-validation settings.

Summary

The objective function of linear models is often convex, yet correct numerical representation and a suitable solver are still essential. Regularization improves generalization and stability, but it also alters the estimand; the choice of regularization depends on validation performance, coefficient paths, and actual decision-making requirements.

The next chapter moves into trees and ensembles: representing nonlinearity and interactions through recursive partitioning, while confronting new challenges related to depth, variance, boosting objectives, and probabilistic calibration.