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

On one dataset, a learning rate can make loss diverge while a smaller value barely moves the parameters. Even a convex objective depends on curvature, scale, sparsity, and the solver. Standardization often helps; “another thousand steps” is not a diagnosis.

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}\Vert Xw-y{\Vert }_2^2,\mathrm{\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.

This Python 3 + NumPy function fragment (partial) takes a design matrix and response vector. tolerance is an absolute gradient-norm threshold, and max_steps is the update budget. Reported loss belongs to the returned weights; exhausting the budget returns converged=False.

import numpy as np

def fit_linear_gd(X, y, learning_rate, max_steps, tolerance):
    X, y = np.asarray(X, dtype=float), np.asarray(y, dtype=float)
    if X.ndim != 2 or y.ndim != 1 or len(y) == 0 or len(X) != len(y):
        raise ValueError("X must be a nonempty matrix and y a matching vector")
    if not np.isfinite(X).all() or not np.isfinite(y).all():
        raise ValueError("X and y must be finite")
    if (not np.isfinite(learning_rate) or learning_rate <= 0
            or not np.isfinite(tolerance) or tolerance <= 0
            or not isinstance(max_steps, int) or max_steps < 0):
        raise ValueError("invalid step size, tolerance, or update budget")

    w = np.zeros(X.shape[1])
    for step in range(max_steps + 1):
        with np.errstate(over="raise", invalid="raise"):
            residual = X @ w - y
            loss = float(np.mean(residual ** 2))
            gradient = (2.0 / len(y)) * X.T @ residual
            gradient_norm = float(np.linalg.norm(gradient))
        if not np.isfinite(loss) or not np.isfinite(gradient_norm):
            raise FloatingPointError("non-finite optimization state")
        converged = gradient_norm <= tolerance
        if converged or step == max_steps:
            return w, {
                "steps": step, "loss": loss,
                "gradient_norm": gradient_norm, "converged": converged,
            }
        w -= learning_rate * gradient

A fixed iteration count does not establish convergence. With a tiny learning rate, a small loss change can simply mean that the parameters hardly moved. This example checks gradient norm, whose threshold still depends on scale and conditioning and is not a prediction-error bound. With max_steps=0, expect initial zero weights and their actual loss; after one update, the loss must correspond to the updated weights.

2. Convex does not mean easy optimization

The Hessian of squared loss is:

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

The Hessian is positive semidefinite and becomes positive definite when X has full column rank. Strongly correlated features can create a large condition number and elongated contours. Fixed-step descent then risks oscillation along steep directions while moving slowly along flatter 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

Squared-loss and logistic-loss models use partly different solvers:

• QR/SVD/least-squares solvers directly solve squared-loss problems;
• 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

This Python 3 + scikit-learn fragment (partial) expects aligned X, y, and team_id arrays, at least five groups, and adequate class coverage in every training and validation fold. For future-time generalization, use a suitable temporal split instead. The example searches C for default L2 logistic regression, preserves groups, and fits imputation and scaling within each fold.

from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import GridSearchCV, GroupKFold
from sklearn.impute import SimpleImputer
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

candidate = Pipeline([
    ("impute", SimpleImputer(strategy="median")),
    ("scale", StandardScaler()),
    ("model", LogisticRegression(max_iter=2000)),
])

search = GridSearchCV(
    candidate,
    param_grid={
        "model__C": [0.01, 0.1, 1.0, 10.0],
    },
    scoring="neg_log_loss",
    cv=GroupKFold(n_splits=5),
    error_score="raise",
)
search.fit(X, y, groups=team_id)

This was checked with scikit-learn 1.9.0, using default lbfgs and L2 settings without explicitly passing that version's deprecated penalty parameter. Check the LogisticRegression parameter reference before switching solvers or using L1/Elastic Net. Imputation, scaling, and selection are fitted within each fold.

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 QR, L-BFGS, and SGD on the same squared-loss objective and cross-validation splits, reporting runtime and loss.

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.