Theory

This section derives the math behind sparho’s hypergradient, active-set restriction, prox kernels, and criteria, at enough depth that a reader should not need to fetch the underlying papers. Each page is a self-contained derivation with pointers into the implementation it backs.

If you only need the user-facing summary, Concepts covers the same ideas in two screens. Use this section when you want to understand why a particular line in hypergrad.py looks the way it does, or to extend sparho with a new datafit/penalty/criterion.

Contents

• Implicit differentiation
• Active sets and why we restrict
• Penalties: prox, Jacobian, \(\partial_\beta s\), \(\partial_\alpha s\)
• Criteria and the outer chain rule
• Convergence: HOAG outer loop
• References

The bilevel problem

sparho solves

\[ \min_{\alpha \,\in\, \mathcal{A}} \; C(\beta^\star(\alpha)) \quad \text{s.t.} \quad \beta^\star(\alpha) \;=\; \arg\min_{\beta \in \mathbb{R}^p} \; L(X\beta, y) + R(\beta; \alpha). \]

Two layers: an inner convex (typically non-smooth) problem in \(\beta\) with a closed-form Bayes-style structure (Lasso, ElasticNet, WeightedL1, GroupL1, possibly with LogisticLoss), and an outer problem in the hyperparameter \(\alpha\) governed by a criterion \(C\) — held-out MSE, K-fold CV, SURE.

The unique inner solution \(\beta^\star(\alpha)\) defines a map \(\alpha \mapsto \beta^\star(\alpha)\). Computing \(dC/d\alpha\) through that map is the central technical problem; sections Implicit differentiation and Active sets and why we restrict derive the linear system sparho solves. The pages Penalties: prox, Jacobian, \partial_\beta s, \partial_\alpha s and Criteria and the outer chain rule enumerate the (datafit, penalty) dispatches and the criterion chain rule; Convergence: HOAG outer loop sketches why the HOAG outer loop converges to a stationary point of the (noisy) outer objective.

Notation

The following symbols are used consistently across this section unless explicitly re-defined.

Symbol	Meaning
\(n,\,p\)	Number of samples / features. \(n = \) problem.n_samples, \(p = \) problem.n_features.
\(X \in \mathbb{R}^{n \times p}\)	Design matrix. problem.design. May be dense or scipy.sparse.csc_matrix.
\(y \in \mathbb{R}^n\) or \(\{-1, +1\}^n\)	Target. problem.target. Regression vs. binary classification by datafit.
\(\beta \in \mathbb{R}^p\)	Inner parameter (coefficient vector). \(\beta^\star(\alpha)\) at optimum.
\(\alpha\)	Hyperparameter. Scalar for L1 / ElasticNet / GroupL1, length-\(p\) for WeightedL1. Strictly positive componentwise.
\(\theta = \log\alpha\)	Log-parametrization. Outer loops in search.py step in \(\theta\); chain rule \(dC/d\theta = dC/d\alpha \cdot \alpha\).
\(L(\cdot,\cdot)\)	Datafit. \(\tfrac{1}{2n}\|X\beta - y\|^2\) for SquaredLoss (sklearn convention), \(\sum_i \log(1 + e^{-y_i (X\beta)_i})\) for LogisticLoss.
\(R(\beta;\alpha)\)	Penalty. L1, WeightedL1, ElasticNet, GroupL1 — enumerated in Penalties: prox, Jacobian, \partial_\beta s, \partial_\alpha s.
\(C(\beta)\)	Outer criterion. HeldOutMSE, HeldOutLogistic, CrossVal, Sure — enumerated in Criteria and the outer chain rule.
\(A \subseteq \{0, \dots, p-1\}\)	Active set. \(A = \{j : \beta^\star_j \neq 0\}\) for separable penalties; for GroupL1 it is the union of coordinates in nonzero groups (see Active sets and why we restrict).
\(H_L = \nabla_{\beta\beta}^2 L(X\beta^\star, y)\)	Inner-loss Hessian at \(\beta^\star\).
\(H_{L,AA}\)	Submatrix of \(H_L\) on rows/cols in \(A\). Restricted Hessian.
\(M_{AA}\)	\(H_{L,AA} + \nabla_{\beta\beta}^2 R\big|_A\) — the augmented Hessian sparho’s CG solver inverts; see Implicit differentiation.
\(r\)	Right-hand side \(\nabla^2_{\alpha\beta} R\big|_A\) of the implicit-diff linear system; penalty-specific column built in sparho.implicit_forward().

The key load-bearing fact across this section: every algorithm sparho exposes operates only on \(A\). The inactive coordinates contribute zero to \(d\beta^\star/d\alpha\) — see Active sets and why we restrict — so the implicit-diff linear system is \(|A| \times |A|\) rather than \(p \times p\). For sparse problems where \(|A| \ll p\) this is the difference between a tractable hypergradient and an intractable one.