Gradient-based hyperparameter tuning treats a model's training solution as a smooth function of its hyperparameters. It differentiates that function to learn how changing a regularization weight moves the validation error. For sparse models such as the Lasso (least squares with an $\ell_1$ penalty that zeroes out coefficients), this assumption quietly fails in exactly the regimes where the models are used: many more features than samples, duplicated or highly correlated columns, and binary text features. There the training problem has a whole set of equally good solutions rather than one. Which solution the solver returns depends on initialization, warm starts, and coordinate order, so the "hypergradient" it reports (the gradient of validation loss with respect to the hyperparameters) is a gradient of an arbitrary choice. Current methods either assume this cannot happen, through strong convexity or a unique support, or remove it by adding a ridge term that biases the model and degrades conditioning.
We propose to fix the hypergradient by fixing the selection. We define a canonical training solution, the minimum-norm point of the Lasso solution set, and compute its derivative through the dual problem, whose solution is always unique. A property called metric subregularity then lets us bound the error of the computed hypergradient using only the solver's measured optimality violation. Metric subregularity means that distance to the solution set is at most a constant times the optimality violation, even when no strong convexity is present. The result is a hypergradient that is reproducible, carries an error certificate, and makes no uniqueness assumption. It is computed with a second-order solver whose cost scales with the number of active features.
Core Claim
For Lasso-type lower-level problems, the right object to differentiate is a specific, solver-independent selection from the solution set. It is not "the solution" (which may not exist uniquely), and it is not a ridge-perturbed surrogate. The selection can be differentiated cheaply and to a certified accuracy because two structural facts hold together. First, the dual of the Lasso has a unique solution, the optimal residual. The dual determines the equicorrelation set $E$, the features that could be nonzero in some optimal solution. The solution set is then the polyhedron $S^*(\lambda)=\{\theta:\ X\theta=\hat y(\lambda),\ \mathrm{supp}(\theta)\subseteq E,\ \text{signs consistent with the dual}\}$, where $\hat y$ is the unique fitted value. Second, the Lasso is piecewise linear-quadratic, so its optimality map is metrically subregular. This gives
$$ \mathrm{dist}(\hat\theta, S^*(\lambda)) \le \kappa\, r(\hat\theta), $$
where $\hat\theta$ is the solver's iterate, $r$ is its optimality (KKT) residual, and $\kappa$ is the subregularity modulus. Propagating this inequality through the minimum-norm selection yields a hypergradient error bound of the form $C\kappa\, r(\hat\theta)$. The constant $C$ depends on the validation loss's smoothness and on the conditioning of the selection problem restricted to $E$, not on any strong-convexity constant. That bound is what lets the outer loop choose the inner tolerance adaptively.
A secondary empirical claim motivates the work. We expect non-uniqueness in per-feature-weighted Lasso tuning to be persistent rather than a measure-zero accident. When two features are duplicated and start with tied weights, a symmetric hypergradient keeps the weights tied forever. A solver that arbitrarily picks one duplicate produces an asymmetric hypergradient and breaks the tie at random. If this holds on text benchmarks with many duplicated sparse columns, current methods are optimizing a noisy, path-dependent function. The first experiment checks this.
Relation to Prior Work
The closest work is Implicit differentiation of Lasso-type models for hyperparameter optimization. It tunes up to 1.67 million per-feature penalties by identifying the active support with coordinate descent and then differentiating only on that support. It proves linear convergence of the Jacobian after support identification, but it relies on a unique support and an invertible restricted Gram matrix. Those are precisely the assumptions that collinear and duplicated designs break. We reuse its forward, support-restricted structure and replace its uniqueness assumption with an explicit selection and a dual-based support (the equicorrelation set).
Nonsmooth Implicit Differentiation for Machine-Learning and Optimization supplies a calculus for differentiating nonsmooth implicit maps through conservative Jacobians. It also constrains our design: it shows that when its invertibility condition fails, gradient descent can fall into limit cycles and chaotic trajectories. Our selection is built to restore a well-posed derivative in exactly the degenerate case that paper warns about. We then test empirically whether outer-loop oscillation disappears.
The analyses of On the Iteration Complexity of Hypergradient Computations and Accelerating Inexact HyperGradient Descent for Bilevel Optimization motivate the gap. Both require a strongly convex or contractive lower level, and their bounds grow polynomially in the condition number, as $\kappa^{3.25}$ for the restarted accelerated method. Both therefore degenerate when strong convexity is absent.
The method comes from the metric subregularity literature. A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems (SSNAL) solves the Lasso dual with an augmented Lagrangian outer loop and a semismooth Newton inner loop. It proves fast local convergence from metric subregularity alone, without strict complementarity, and exploits sparsity of the generalized Hessian. SSNAL is a single-level solver; we embed it in a hyperparameter loop and differentiate through its dual output. Metric Subregularity of Subdifferential and KL Property of Exponent 1/2 supplies the equivalence, for convex functions, between subregularity and quadratic growth. We use that equivalence to turn a duality gap into a distance-to-solution-set bound, and hence into a certificate. Work on primal-dual coordinate methods, such as On the Convergence of Stochastic Primal-Dual Hybrid Gradient, shows that linear rates on piecewise linear-quadratic problems hold without adding strongly convex regularizers. This is our argument for not adding a ridge term, but it says nothing about hypergradients.
Linearly Constrained Bilevel Optimization: A Smoothed Implicit Gradient Approach handles a related nonsmoothness in a different way. It adds a random linear perturbation so that the active constraints are unique almost surely. That is also a selection, but a random and biased one, and we compare against it.
Research Program
The first component is the selection and its derivative. Given the dual solution, the minimum-norm selection solves a strictly convex quadratic program over the polyhedron $S^*(\lambda)$. On any region where its own sign pattern is fixed, its derivative with respect to $\lambda$ is a minimum-norm solve of a consistent singular linear system on the active columns. The linear system is consistent because the KKT conditions put the right-hand side in the range of the restricted Gram matrix. Where the sign pattern changes, the selection is only piecewise smooth, and we use a conservative Jacobian in the sense of Bolte et al. We will characterize when such changes occur along an outer trajectory and measure how often they do in practice. The derivative of the dual part is well defined almost everywhere, because the dual solution is a projection onto a polytope.
The second component is the certificate. We will prove a bound on the hypergradient error of the form $C\kappa\, r(\hat\theta)$, for both the dual quantities and the selection. We will estimate $\kappa$ online from SSNAL's observed contraction of the KKT residual, and compare that estimate against offline estimates on small problems where the modulus can be computed. This gives an adaptive rule: tighten the inner tolerance only when the certified hypergradient error exceeds a fixed fraction of the current hypergradient norm. Inexact gradient descent with relative errors of this kind keeps standard convergence to stationary points of the outer problem.
The third component is the algorithm. We will implement SSNAL with the forward, support-restricted Jacobian of Bertrand et al. The linear solves use conjugate gradient, which converges to the minimum-norm solution on consistent singular systems. The Sherman-Morrison-Woodbury trick keeps the cost dependent on $|E|$ rather than on the total number of features $p$. We will then extend the construction to the group Lasso, whose solution set has the same polyhedral-plus-unique-dual structure.
Baselines
The naive reference point is a single shared penalty tuned by grid search on validation loss. Bertrand et al. show that this setup is beaten by gradient methods, and with $p$ penalties grid search is infeasible. It anchors what "tuning helps" means. It gets the same wall-clock budget as our method, and our method must reach lower held-out test loss within that budget.
The strongest existing method is implicit forward differentiation from Implicit differentiation of Lasso-type models for hyperparameter optimization, run with its coordinate-descent solver, warm starts, and the same outer optimizer and step-size schedule as ours. No reported result was found on Lacuna for its validation or test loss values or its hypergradient error on rcv1, 20news, or finance. The file only says it beat grid search, random search, and Bayesian optimization and was orders of magnitude faster than backward differentiation. We will therefore rerun it ourselves on identical splits. To beat it, our method must (a) have lower hypergradient error against a high-precision reference on degenerate designs at equal compute, (b) produce reproducible hypergradients across solver seeds and coordinate orders, and (c) reach equal or lower test loss with fewer outer-loop oscillations. On well-posed designs, it must match Bertrand within noise. For solver speed, the relevant reported figures are that SSNAL was "at least 330 times faster than ADMM" on housing7 and solved log1p.E2006.train in about 20 seconds (Li, Sun, Toh). These set the expectation that the inner solve will not be the bottleneck.
The second strong competitor is an elastic net with a vanishing ridge weight $\epsilon$, tuned by the same implicit differentiation with conjugate gradient. As $\epsilon\to 0$ this approaches the minimum-norm Lasso selection, so it targets the same object. We sweep $\epsilon$ over several decades and give each value the same compute.
We also run unrolled differentiation through proximal gradient steps. It is capped by memory: Grazzi et al. report that unrolling exceeded an 11 GB GPU beyond 50 inner steps on 20 Newsgroups. Random linear perturbation smoothing in the style of Khanduri et al. is run with its noise scale tuned on validation data.
Two ablations isolate the key ingredients. The first uses the same SSNAL solver and Jacobian code but takes whatever primal solution SSNAL returns, with no minimum-norm selection, which tests whether the selection matters. The second uses the selection with a fixed tight inner tolerance instead of the certified adaptive rule, which tests whether the certificate saves compute.
Why not just…?
Why not just add a small ridge term and use existing implicit differentiation? This is the most serious threat, because the small-ridge limit targets the same minimum-norm solution. The argument against it is quantitative, not categorical. The restricted system's condition number grows roughly like (largest eigenvalue)/$\epsilon$, so either the bias is large or each solve is slow. The complexity bounds of Yang et al. blow up in that limit. The augmented-Lagrangian route has subproblem conditioning set by its own penalty parameter, independent of the bias. The $\epsilon$-sweep baseline settles this: we plot hypergradient error against compute for each $\epsilon$ and for our method. If some fixed $\epsilon$ traces the same frontier, we will report that the cheaper fix suffices and that the remaining contribution is the certificate.
Why not just use the pseudoinverse on the support Bertrand et al. already find? This alternative is cheap, and on the selected support it is close to what we do. The difference is which support it uses. Coordinate descent on a degenerate problem returns one solution's support, which can be smaller than the equicorrelation set and can change across warm starts. A pseudoinverse on that support differentiates a solver-dependent selection. The "no selection" ablation and the seed-reproducibility metric test exactly this. If supports turn out to be stable on real benchmarks, the gain will be confined to synthetic duplicated designs, and we will say so.
Why not just use random or Bayesian search over a few shared penalties? With one or a handful of shared penalties this is a legitimate competitor, and degeneracy matters less there. With per-feature penalties on 20,000 to 1.67 million features it is infeasible, as Bertrand et al. document. We include the low-dimensional search as a reference, so readers can see when per-feature tuning is worth having at all.
Proposed Experiments
The first experiment is a diagnostic: is non-uniqueness real in these benchmarks? On rcv1, 20news, and finance (the Bertrand et al. benchmarks), we count exactly duplicated columns and measure the dimension of the Lasso solution set at the tuned penalties. We then run Bertrand et al.'s method from symmetric initial weights and track whether weights of duplicated features stay tied or split, and how hypergradients vary across coordinate orders. If duplicates are rare and hypergradients are reproducible, the practical case shrinks to correlated synthetic designs, and the paper becomes primarily theoretical.
The second experiment is a controlled degeneracy sweep. We use synthetic designs with $p\gg n$, planted duplicated columns, and tunable collinearity. We report hypergradient error against a reference computed by the minimum-norm selection at very high precision, measured against compute, for all baselines. We also report the fraction of outer runs that oscillate, which tests the pathology Bolte et al. describe. The key prediction is that the existing methods' error and oscillation grow as collinearity rises, while ours stays flat.
The third experiment tests the certificate. On small problems where $\kappa$ can be estimated offline, we check that the certified bound actually upper-bounds the measured hypergradient error, and we report how loose it is. The bound is useful if it is valid on all runs and within roughly an order of magnitude of the true error. We then measure total inner iterations saved by the adaptive tolerance relative to the fixed-tolerance ablation.
The fourth experiment is end-to-end tuning of weighted Lasso and group Lasso on rcv1, 20news, and finance. We report held-out test loss against wall-clock time under equal budgets, along with the variance of final test loss across solver seeds. The decisive outcome is lower seed-to-seed variance at equal or better test loss. Without it, the selection argument is academic.
References
- Implicit differentiation of Lasso-type models for hyperparameter optimization
- Nonsmooth Implicit Differentiation for Machine-Learning and Optimization
- On the Iteration Complexity of Hypergradient Computations
- Accelerating Inexact HyperGradient Descent for Bilevel Optimization
- A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems
- Metric Subregularity of Subdifferential and KL Property of Exponent 1/2
- On the Convergence of Stochastic Primal-Dual Hybrid Gradient
- Linearly Constrained Bilevel Optimization: A Smoothed Implicit Gradient Approach