Outer-search loops

Two outer loops ship at v0.1. Both step in θ = log α space (positive α without projection), both threadable with any Solver × Criterion × hypergradient triple, and both refit the inner solver on the full problem at the best α seen before returning.

Classical bilevel approximate-gradient descent in θ = log α space.

θ_{k+1} = θ_k - lr · dC/dθ, where dC/dθ = dC/dα · α (chain rule). Fixed learning rate, one value_and_hypergrad call per outer iter. No step-size adaptation — pair with hoag_search() if the inner-solver accuracy varies with the iteration budget or if you want Lipschitz-adaptive steps. Useful as a baseline and for problems where the user has prior knowledge of a good lr.

Parameters:

  • problem (Problem) – The full bilevel problem. The criterion handles train/val splits.

  • hp0 (float | ndarray[tuple[Any, ...], dtype[floating]]) – Initial hyperparameter — scalar or per-feature vector. Must be > 0; the outer loop optimizes in θ = log α space.

  • solver (Solver) – Inner-problem solver. Called by the criterion and once at the end for the full-data refit.

  • criterion (Criterion) – Outer-loop validation oracle (e.g. sparho.criteria.HeldOutMSE, sparho.criteria.CrossVal).

  • hypergrad (Callable[[...], float | ndarray[tuple[Any, ...], dtype[floating]]]) – Hypergradient function. Defaults to sparho.hypergrad.implicit_forward().

  • n_iter (int) – Maximum outer iterations.

  • lr (float) – Learning rate applied in θ-space.

  • tol (float) – Stationarity tolerance on the log-space hypergradient norm.

Return type:

SearchResult

HOAG (Hyperparameter Optimization with Approximate Gradients, Pedregosa 2016).

One val+grad call per outer iter; step size adapted from a Lipschitz proxy L; the acceptance test value ≤ value_prev + C·tol + tol_prev·(C+factor)·||step·g|| - factor·L·||step·g||² carries a slack term that absorbs criterion-value noise due to inner-solver inaccuracy. On bad descent (value ≥ 1.2·value_prev) the step is rejected, L is doubled, and val+grad is recomputed at the restored point with tol/2 — tightening inner accuracy where the outer search needs it.

The inner tolerance is part of the loop state and is threaded into the criterion → solver call each iter via Solver.__call__(tol=...). With tolerance_decrease='exponential' the per-iter tol geometrically decreases from inner_tol_initial to inner_tol across the n_iter outer steps — loose early when only the gradient direction matters, tight late when the value resolution drives convergence.

Parameters:

  • problem (Problem) – The full bilevel problem. The criterion handles train/val splits.

  • hp0 (float | ndarray[tuple[Any, ...], dtype[floating]]) – Initial hyperparameter — scalar or per-feature vector. Must be > 0; the outer loop optimizes in θ = log α space.

  • solver (Solver) – Inner-problem solver. Must accept a tol keyword (built-in adapters and as_solver-wrapped callables both do).

  • criterion (Criterion) – Outer-loop validation oracle.

  • hypergrad (Callable[[...], float | ndarray[tuple[Any, ...], dtype[floating]]]) – Hypergradient function. Defaults to implicit_forward().

  • n_iter (int) – Outer-iteration budget.

  • inner_tol (float) – Final inner-solver tolerance (and the constant value when tolerance_decrease='constant').

  • inner_tol_initial (float) – Starting inner-solver tolerance when tolerance_decrease='exponential'. Must be ≥ inner_tol.

  • tolerance_decrease (str) – 'constant' (default) or 'exponential'.

  • outer_tol (float) – Stationarity tolerance on the log-space hypergradient norm.

  • C (float) – Acceptance-test constants (Pedregosa 2016 calls them C and the scaling on the quadratic term). Defaults match sparse-ho.

  • factor (float) – Acceptance-test constants (Pedregosa 2016 calls them C and the scaling on the quadratic term). Defaults match sparse-ho.

  • max_step (float) – Maximum θ-step magnitude per single step (the algorithm takes up to two steps per iter; the cap applies to each). Acts as a trust region: prevents the first step from overshooting into a zero-gradient region (e.g. when the active set collapses) before the L adaptation has had a chance to discipline the step size.

Return type:

SearchResult