Diagnosing Numerical Convergence in Penalized Fits

Why Convergence Needs More Than One Check

A numerical algorithm can stop because its updates have become small, because the objective barely changes, or because a preset iteration limit has been reached. None of these statements alone establishes that the reported coefficients solve the intended optimization problem. In high-dimensional genomic data, where many predictors may be correlated and \(p\) may exceed \(n\), the distinction matters: a fit can look stable while still violating an optimality condition, and coefficients can keep changing even when the fitted values and objective have essentially stabilized.

This tutorial considers convergence diagnostics for coordinate-descent and proximal-gradient fits of penalized least squares. The central principle is to monitor changes across iterations but also check the Karush-Kuhn-Tucker (KKT) conditions, which characterize an optimum for the convex objective considered here.

Model and Optimality Conditions

Assume the response \(y\in\mathbb{R}^n\) and predictor matrix \(X\in\mathbb{R}^{n\times p}\) are fixed, and consider a centered response with no intercept in the displayed objective. Predictors may be standardized for numerical comparability, but standardization is not required for the mathematical conditions. For a lasso or elastic-net fit, define

Here \(\beta\in\mathbb{R}^p\) is the coefficient vector, \(\lambda_1\) controls the absolute-value penalty, and \(\lambda_2\) controls the squared-coefficient penalty. Lasso is the case \(\lambda_2=0\); ridge is the case \(\lambda_1=0\). The objective is convex. Its smooth part is the squared-error term plus the squared-coefficient penalty, and the absolute-value penalty is convex but not differentiable at zero.

Let \(r=y-X\beta\) be the residual vector and define the gradient of the smooth part by

For a coordinate with \(\beta_j\neq 0\), the KKT condition is \(g_j(\beta)+\lambda_1\operatorname{sign}(\beta_j)=0\). For a coordinate with \(\beta_j=0\), it is \(|g_j(\beta)|\leq\lambda_1\). Together, these conditions say that zero belongs to the subgradient of \(F\) at \(\beta\). For a convex objective, this is necessary and sufficient for \(\beta\) to be a global minimizer.

If the model includes an unpenalized intercept, its separate KKT condition is that the mean residual is zero. The displayed coordinate residuals concern the penalized coefficients. If coefficients are subject to additional constraints, the corresponding optimality conditions must also be checked.

Three Complementary Diagnostics

An objective-change diagnostic monitors whether the objective has stopped improving. At iteration \(t\), one useful relative change is

A small \(d_t\) indicates that the objective changed little in that iteration. For exact coordinate minimization, the objective should not increase, apart from possible rounding error. A properly chosen proximal-gradient step also has a descent guarantee. But a small objective change is not an optimality certificate: steps can be tiny because of a small step size, poor conditioning, or a stalled implementation.

A coefficient-change diagnostic monitors movement in the parameter vector, for example \(\|\beta^{(t)}-\beta^{(t-1)}\|_2/\max\{1,\|\beta^{(t-1)}\|_2\}\). Small movement can be useful evidence that the iterates are stabilizing. It is not decisive when different coefficient vectors give nearly identical predictions, as can happen with collinear predictors. Conversely, a relatively large coefficient movement may have little effect on predictions if the movement is mostly in a direction to which \(X\) is insensitive.

The KKT residual checks whether the current coefficients satisfy the objective’s optimality conditions, rather than simply whether the last update was small. For the convex objective above, \(V(\beta)=0\) certifies a global minimum. In computation, one accepts a small residual relative to a stated tolerance. Because the residual is expressed in gradient units, it should be interpreted in relation to the scaling of \(X\), \(y\), and the objective.

Why the KKT Residual Works

The KKT residual is more than a convenient numerical summary. It measures failure of the conditions that characterize a minimum. For one coordinate, the absolute-value penalty has subgradient \(\operatorname{sign}(\beta_j)\) when \(\beta_j\neq0\), and the interval \([-1,1]\) when \(\beta_j=0\). Therefore the subgradient of the full objective in coordinate \(j\) is \(g_j+\lambda_1\operatorname{sign}(\beta_j)\) off zero, and the set \(g_j+\lambda_1[-1,1]\) at zero.

At a nonzero coefficient, zero belongs to that subgradient exactly when \(g_j+\lambda_1\operatorname{sign}(\beta_j)=0\). At a zero coefficient, it belongs exactly when there is some \(u\in[-1,1]\) for which \(g_j+\lambda_1u=0\). Such a \(u\) exists precisely when \(|g_j|\leq\lambda_1\). These are the coordinatewise KKT conditions used in \(V(\beta)\).

For a convex function, a point is a global minimizer if and only if zero belongs to its subgradient there. Hence all coordinatewise residuals being zero is sufficient for global optimality. A small but nonzero residual is evidence of approximate KKT satisfaction, not an exact certificate of a specified coefficient error. The relationship between residual size and coefficient error can depend on curvature; if the objective is not strongly convex, small residuals need not imply that every nearly optimal coefficient vector is close to one unique solution.

Descent and Practical Stopping

For cyclic coordinate descent with exact minimization of each coordinate while the others are held fixed, each coordinate update cannot increase \(F\): the old coordinate value remains an available candidate in that one-dimensional minimization. Consequently, the objective after a complete sweep is no larger than before it, up to numerical error. This monotonicity does not guarantee that a finite number of sweeps has reached the KKT conditions.

For proximal gradient, write \(F=f+h\), where \(f\) is the smooth part and \(h(\beta)=\lambda_1\|\beta\|_1\). The gradient of \(f\) is Lipschitz with constant no greater than \(L=\|X\|_2^2/n+\lambda_2\), where \(\|X\|_2\) is the largest singular value of \(X\). A step size \(1/L\), or a smaller one, gives the standard quadratic upper bound for \(f\). The proximal update minimizes that upper bound plus \(h\), so its objective does not exceed the objective at the previous iterate. If a step size is too large for the bound and no safeguard is used, monotone decrease is not guaranteed.

A sound stopping rule combines evidence. For example, require both a small relative objective change and a maximum KKT residual below a chosen tolerance, and inspect coefficient or fitted-value changes as an additional stability check. Tolerances are numerical choices, not universal constants. They should be recorded along with the objective scaling, penalty values, iteration limit, and whether the algorithm stopped by its convergence criteria or by a limit.

When Coefficients Do Not Settle Uniquely

A small objective change does not ensure a unique coefficient vector. If predictors are collinear, multiple coefficient vectors can produce the same fitted values and the same penalized objective. This is especially important for interpreting coefficient-change diagnostics: a continuing redistribution of weight across redundant predictors may be computationally visible even when prediction and objective are stable. A positive squared-coefficient penalty can improve uniqueness by making the objective strictly convex, but lasso alone need not do so.

Diagnostics, Alternatives, and Common Pitfalls

When a fit behaves unexpectedly, first check that all diagnostics use the same objective convention. For example, changing the squared-error factor from \(1/(2n)\) to \(1/2\) changes the gradient scale and the corresponding penalty scale. Mixing a gradient from one convention with a \(\lambda_1\) from another produces misleading KKT residuals. Also check the predictor scaling, the penalty values, and whether the gradient includes the \(\lambda_2\beta\) term.

If the objective rises repeatedly under a method expected to descend, inspect the step-size rule, coordinate-update implementation, and arithmetic. If the objective barely changes but the KKT residual remains large, the method may be stalled, taking overly cautious steps, or using an inconsistent objective or gradient. If coefficients move substantially while fitted values barely change, collinearity or weak curvature may be responsible. These patterns are diagnostic clues, not automatic proof of a particular software defect.

Objective and coefficient changes are inexpensive and useful for tracking progress; KKT residuals are more directly tied to optimality. Comparing fitted values \(X\beta\) is often helpful when coefficients are not uniquely determined. These checks serve different purposes, so one should not be presented as a complete substitute for the others. None addresses whether the chosen penalty or predictive model is appropriate for the scientific goal.

• Mistake: “The objective changed by almost nothing, so the solution is optimal.”
  Correction: A tiny change can reflect stalling or a tiny step. Evaluate the KKT residual before claiming approximate optimality.
• Mistake: “The coefficients changed, so the predictions must be unstable.”
  Correction: Correlated or duplicate predictors can allow different coefficients to produce the same fitted values and objective.
• Mistake: “A KKT residual of 0.05 is small in every problem.”
  Correction: Residuals have gradient units and depend on objective and data scaling. State the tolerance and assess it under the actual convention used.