PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Bounds for Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function

Anh Tuan Nguyen, Viet Anh Nguyen

arXiv:2608.17343v1cs.LGstat.ML

TL;DR

Multi-dimensional hyperparameter tuning lacks rigorous generalization guarantees because performance depends implicitly and non-smoothly on hyperparameters. The paper uses nested block elimination and invariant connected sign cells to derive sharper pseudo-dimension bounds, proving tightness across combinatorial and algebraic regimes.

  • Problem

    Multi-dimensional hyperparameter tuning lacks rigorous generalization guarantees for its implicit, non-smooth dependence on hyperparameters.

  • Method

    The paper replaces standard quantifier elimination with nested block elimination that tracks logical invariance across connected sign cells in bi-level optimization.

  • Results

    Multi-regime lower bounds match the upper bound’s dependencies on Tf and ∆f and nearly match its dependence on Mf, establishing practical tightness.

  • Takeaways & Limitations

    The framework provides tighter pseudo-dimension guarantees for data-driven tuning and extends to validation-loss tuning and broader semi-algebraic structures.

  • Takeaways & Limitations

    The complexity analysis assumes piecewise-polynomial objectives and an ordered-block structure for quantified variables.

Abstract

from arXiv · show

Data-driven algorithm design frames hyperparameter tuning as a statistical learning problem, but establishing generalization guarantees remains challenging due to the implicit, non-smooth dependence of model performance on hyperparameters. Existing multi-dimensional bounds under piecewise-polynomial assumptions remain theoretically loose and lack comprehensive lower bounds. We resolve this by establishing tight pseudo-dimension bounds for multi-dimensional data-driven tuning. First, we refine the learning-theoretic upper bound using real algebraic geometry; by analyzing invariant connected sign cells during block elimination rather than isolated sign vectors, we avoid topological over-counting to derive strictly sharper sample complexities. Second, we present a multi-regime lower-bound framework that disentangles combinatorial and algebraic capacities. By constructing shattered problem instances across distinct regimes, we prove our upper bounds are tightly saturated. Finally, we extend our topological framework to accommodate general bi-level validation-loss tuning and broader semi-algebraic applications.

1 Introduction

The paper frames continuous hyperparameter tuning as a statistical learning problem whose main challenge is the implicit, non-smooth dependence of validation loss on hyperparameters through inner optimization. It addresses limitations of existing bounds with a geometric analysis tailored to piecewise-polynomial objectives and multi-dimensional, bi-level tuning.

  • Motivation: Hyperparameter tuning is central to machine-learning deployment but is still treated largely as empirical search over discretized continuous spaces.Traditional grid and random search identify high-performing configurations empirically rather than providing rigorous statistical guarantees.
  • Problem formulation: Data-driven algorithm design formalizes tuning as learning a hyperparameter configuration that generalizes from sampled problem instances to unseen instances from the same distribution.The framework uses a finite training sample drawn from an unknown application-specific distribution over problem instances.
  • Problem formulation: The fundamental hurdle is bounding the complexity of validation loss when hyperparameters affect performance only implicitly through the argmin of an auxiliary optimization problem.This dependence can be non-smooth, and the paper measures the resulting loss-class capacity using pseudo-dimension.
  • Approach: The proposed framework exploits piecewise-polynomial structure in hyperparameters and model parameters and recursively constructs geometric sign cells through nested block elimination.This geometric strategy is introduced to obtain sharper statistical bounds than quantifier elimination followed by the Goldberg-Jerrum framework.
  • Prior limitations: Existing analyses are limited by restrictive assumptions or suboptimal bounds, including one-dimensional or single-level settings and severe topological overcounting after standard quantifier elimination.The paper targets multi-dimensional hyperparameters and general bi-level objectives while avoiding isolated-sign-condition counting.

2 Preliminaries

This section introduces pseudo-dimension as the complexity measure supporting ERM generalization and develops polynomial first-order logic, connected sign cells, and nested block-sign profiles for sharper block-elimination analysis.

  • Learning-theoretic background: Pseudo-dimension measures whether a real-valued function class can realize all 2^N threshold-label patterns on an N-point input set.A finite pseudo-dimension guarantees uniform convergence through empirical risk minimization.
  • Polynomial first-order logic: Polynomial first-order logic represents quantified optimization variables and a free variable through alternating quantifier blocks and polynomial atomic predicates.Its quantifier-free part is a Boolean combination of polynomial inequalities or equalities.
  • Connected sign cells and elimination: Connected sign cells partition realizable sign patterns into their connected components, providing geometric regions on which block-elimination sign information can be preserved.The block-elimination process produces polynomials in free variables whose connected sign cells retain sign information attainable by varying eliminated variables.
  • Nested block-sign profiles: Nested block-sign profiles retain the block-wise grouping of realizable sign patterns as a depth-K sign tree, unlike ordinary sign conditions formed by varying all quantified variables simultaneously.For one quantified block, the profile reduces to the set of realizable sign conditions, which must remain unchanged on each induced connected sign cell.

3 Problem Settings

The paper formulates data-driven hyperparameter tuning over bounded instance, hyperparameter, and model-parameter spaces, with performance defined by a bi-level validation-loss objective. It seeks hyperparameters minimizing expected loss from an unknown distribution and analyzes this problem under piecewise-polynomial structural assumptions.

  • Problem formulation: The framework uses an instance space X ⊂ R^q, continuous hyperparameter space A = [α_min, α_max]^p, and model parameter space Θ = [θ_min, θ_max]^d.The parameter domains are restricted to bounding boxes for analytical compactness.
  • Bi-level objective: For each instance x and hyperparameter configuration α, the induced loss is ℓ_α(x) = inf_{θ∈S(x,α)} g(x, α, θ), where S(x, α) minimizes the training objective over Θ.The validation objective g assesses out-of-sample model performance, while the training procedure implicitly determines model behavior through lower-level optimization.
  • Statistical learning goal: The statistical goal is to choose α* ∈ arg min_{α∈A} E_{x∼D}[ℓ_α(x)] when instances come from an unknown application-specific distribution D.Because D is unobservable, learning uses a finite dataset S = {x_1, ..., x_N} sampled from D^N.
  • Structural assumptions: The complexity analysis assumes that objective functions have piecewise-polynomial structure characterized by boundary-polynomial count, piece count, and degree parameters.The paper notes that this structural assumption has been established across applications in learning theory and data-driven algorithm design.

4 A General Learning-theoretic Complexity Framework via Block Elimination

This section develops a general pseudo-dimension upper-bound framework for threshold conditions represented by polynomial first-order logic. Its key mechanism is nested block elimination, which preserves logical truth values across connected sign cells and yields a complexity bound in terms of p, L, M, Δ, and block-elimination parameters.

  • Cellwise logical invariance: Proposition 4.1 establishes that a polynomial first-order logic formula has constant truth value on every connected sign cell of a nested sign-invariant projection.Thus, any two parameter points in the same connected sign cell satisfy the formula equivalently.
  • Pseudo-dimension upper bound: Theorem 4.2 applies branchwise nested block elimination to function classes whose threshold indicators are Boolean combinations of L polynomial first-order logic formulas.Each formula uses K ordered quantified-variable blocks with dimensions d1, ..., dK and at most M atomic polynomials of degree at most Δ.
  • Pseudo-dimension upper bound: Pdim(F) = O (p log(2L) + pAK log(2M) + pBK log(2∆)) under the theorem’s block-dimension and degree assumptions.The bound is derived by controlling the size and degrees of nested sign-invariant projections and counting connected sign cells.
  • Proof mechanism: Nested projections preserve each branch’s truth value on connected sign cells, and therefore preserve the combined threshold label produced by the Boolean function βx,τ.The proof also incorporates the affine polynomials describing the parameter region A.

5 Tuning via Training Objective

For identical training and validation objectives, the paper derives a sharper pseudo-dimension upper bound through nested block elimination and establishes matching or nearly matching lower bounds across combinatorial and algebraic regimes.

  • 5.1 Upper bound: Pdim(L) = O(p log Tf + pd log(Mf + d) + pd log ∆f).The bound applies to piecewise polynomial training objectives over p-dimensional hyperparameter and d-dimensional parameter domains.
  • 5.1 Upper bound: Nested block elimination removes the prior p2 dependence on algebraic capacity and sharpens the combinatorial dependencies.Prior work obtained O(pd log(Mf+Tf+d)+p2d log ∆f).
  • 5.2 Lower bounds: Prior results provide the algebraic lower bound Ω(pd log ∆f), matching the upper bound’s algebraic dependence.The paper combines this result with its new combinatorial lower bounds to assess tightness across regimes.
  • 5.2 Lower bounds: Pdim(L) = Ω(p log Tf) for piecewise polynomial objectives with Tf ≥4.This lower bound establishes tight dependence on the number of pieces across every p and d ≥1.
  • 5.2 Lower bounds: The boundary-capacity lower bound Ω(pd log(1 + Mf/d)) confirms that the dependence on Mf is nearly tight.Lemma 5.3 constructs objectives with exact Mf realized sign conditions and piece polynomials of degree at most 2.

6 Tuning via Validation Objective

This section extends hyperparameter tuning to a bi-level setting where training and validation objectives may differ. It develops a tighter validation bound by jointly encoding validation performance and lower-level optimality.

  • Bi-level validation objective: The bi-level formulation selects model parameters by minimizing training objective f while evaluating hyperparameters with potentially different validation objective g.The validation loss is defined through lower-level training optima and validation performance.
  • Bi-level validation objective: Analyzing the validation loss requires simultaneously encoding validation performance and lower-level optimality, unlike the training-loss setting.
  • Improved validation bound: Theorem 6.1 is strictly tighter than prior multi-dimensional validation bounds by removing one factor p from the degree-dependent term and moving Tg outside the d2-scaled logarithm.The comparison is attributed to Le, Nguyen, and Nguyen (2026b, Theorem 6.1), with further details in Appendix D.

7 Applications

The framework is applied to data-driven Weighted Group Lasso tuning with group-specific penalty hyperparameters. It yields a sharper pseudo-dimension bound by encoding the semi-algebraic norm polynomially and preserving invariant connected sign cells during elimination.

  • Weighted Group Lasso application: Weighted Group Lasso tuning partitions θ into p groups, with α ∈ R^p controlling each group’s penalty weight.The training and validation objectives use weighted group penalties and squared validation loss.
  • Pseudo-dimension bound: Pdim(Lval) = O(p(d + p)^2 log p) for the induced validation-loss class.This is the bound established in Theorem 7.1 for Weighted Group Lasso objectives.
  • Improvement over prior work: Theorem 7.1 improves the prior O(p^3d + p^2d^2) upper bound by removing a full factor of p from the dominant algebraic term.The improvement comes from preserving invariant connected sign cells during block elimination rather than using standard quantifier elimination.
  • Proof mechanism: The proof introduces auxiliary variables to represent the semi-algebraic L2 norm using purely polynomial constraints.This enables direct use of the nested block elimination framework in Theorem 4.2.

8 Conclusion and Future Work

The paper establishes tighter pseudo-dimension bounds for multi-dimensional data-driven hyperparameter tuning in bi-level optimization. It uses invariant connected sign cells and multi-regime lower bounds to address topological over-counting and show tightness for training-loss tuning.

  • Conclusion: Invariant connected sign cells in nested block elimination yield strictly tighter pseudo-dimension bounds than standard quantifier elimination.The framework bypasses topological over-counting in multi-dimensional data-driven hyperparameter tuning for bi-level optimization.
  • Conclusion: Multi-regime lower bounds for the training-loss setting show that the derived upper bounds are tightly saturated.The lower-bound construction addresses both combinatorial and algebraic capacities, though the supplied passage truncates before specifying them fully.

A Additional Definitions and Results … A.4 Supporting Lemmas

The appendix defines the Goldberg–Jerrum framework and its complexity measures, contrasts prior quantifier-elimination bounds with the paper’s sign-cell approach, and records supporting definitions and a logarithmic-growth lemma.

  • A.1 The Goldberg-Jerrum framework: The Goldberg–Jerrum framework models parameterized function evaluation using arithmetic assignments and conditional branching over real-valued inputs.Intermediate values are generated sequentially from external inputs or previously computed values.
  • A.1 The Goldberg-Jerrum framework: GJ algorithm complexity is characterized by the maximum degree of computed rational functions and the number of distinct rational predicates evaluated.For f(α) = g(α)/h(α), degree is max{deg(g), deg(h)}.
  • A.1 The Goldberg-Jerrum framework: Pdim(L) = O(p log(∆Λ)) when threshold evaluation is implemented by GJ algorithms with p parameters, maximum degree ∆, and predicate complexity Λ.The guarantee applies for every problem instance and real-valued threshold.
  • A.2 A detailed discussion on the technical difference compared to prior works: Prior work first converts the bi-level optimization objective into a polynomial first-order logic statement through quantifier elimination, then applies the Goldberg–Jerrum framework.This rigid two-step pipeline is presented as the prior approach whose limitation motivates the paper’s alternative.
  • A.2 A detailed discussion on the technical difference compared to prior works: The proposed method directly bounds the distinct sign patterns realized by thresholded loss functions, using geometric sign-cell analysis instead of explicit logical-formula evaluation.Its target is the shattering coefficient across a dataset, rather than an explicitly manipulated quantifier-free formula.
  • A.3 Additional Definitions: Connected sign cells are defined through connected subsets and maximal connected components within a set S ⊆ R^d.Connectedness excludes decompositions into two nonempty, disjoint subsets open relative to S.
  • A.4 Supporting Lemmas: Proposition A.2 establishes t = O(log A) for t ≥ 0 and A ≥ 2 whenever 2^t ≤ c(t + 2)A with c ≥ 1.The proposition supplies a supporting inequality used in the appendix’s later bounds.

B Additional Results and Omitted Proofs for Section 4 · C Additional Results and Omitted Proofs for Section 5

The omitted results establish that nested sign-invariant projections preserve quantified logical truth on connected sign cells and use this property to derive the pseudo-dimension upper bound. The proof constructs a global polynomial family whose cells carry constant labeling vectors, then applies cell-counting bounds to obtain the final complexity rate.

  • B Additional Results and Omitted Proofs for Section 4: Nested sign-invariant projections make every polynomial first-order formula constant on each connected sign cell.The result follows because recursive existential and universal evaluations depend only on nested block-sign profiles, which are invariant within each cell.
  • B Additional Results and Omitted Proofs for Section 4: Theorem 4.2 models threshold predicates using L polynomial formulas combined by a Boolean function.Each formula has K ordered quantified variable blocks with dimensions d1, …, dK and at most M atomic polynomials of degree at most ∆.
  • B Additional Results and Omitted Proofs for Section 4: The pseudo-dimension proof bounds the largest shattered instance set by controlling the number of attainable threshold-labeling patterns.Shattering requires all 2^N binary vectors to arise as hyperparameters vary, so the argument upper-bounds the shattering coefficient and solves the resulting inequality.
  • B Additional Results and Omitted Proofs for Section 4: Branch elimination combines the branchwise projection families with affine polynomials defining the hyperparameter box into one global polynomial family.The construction accounts for all N instances and L branches while incorporating the 2p box-boundary polynomials.
  • B Additional Results and Omitted Proofs for Section 4: Every connected global cell has a constant labeling vector because each branch formula is constant there and the Boolean aggregation is fixed.Applying Proposition 4.1 branchwise and then across all instances shows that the complete threshold-labeling pattern does not change within a global cell.
  • B Additional Results and Omitted Proofs for Section 4: Cell counting converts the global polynomial construction into a pseudo-dimension upper bound by enforcing 2^N ≤ |Cell(˜Q)|.The remaining argument bounds the number of connected sign cells using the polynomial count and degree, then solves for the maximum shattered-set size.
  • B Additional Results and Omitted Proofs for Section 4: The final substitution yields N = O(p log(2LS^K D^K)) before replacing S_K and D_K with their parameter-dependent expressions.The intermediate rate uses u = O(log(2LS^K D^K)), followed by the stated substitutions for S_K and D_K.

C.1 Omitted Proofs for Section 5.1 · C.2 Proofs for Section 5.2

The omitted proofs establish the upper pseudo-dimension guarantee by rewriting threshold events as bounded-complexity polynomial first-order formulas and applying real algebraic geometry. The subsequent proofs construct shattering instances that yield matching lower bounds driven by the number of pieces and boundary-induced sign regions.

  • C.1 Omitted Proofs for Section 5.1: Pdim(L) = Ω(p log Tf + pd log(Mf + d) + pd log ∆f).The lower bound matches the upper-bound terms in Theorem 5.1.
  • C.1 Omitted Proofs for Section 5.1: Each polynomial formula uses one quantified block over θ, at most Mf + 2d + 1 atomic predicates, and degree at most ∆f.The predicates comprise boundary, domain, and value polynomials.
  • C.1 Omitted Proofs for Section 5.1: Theorem 5.1 bounds Pdim(L) by O(p log Tf + pd log(Mf + d) + pd log ∆f).The proof represents each threshold event as a Boolean combination of at most Tf polynomial formulas and applies Theorem 4.2.
  • C.1 Omitted Proofs for Section 5.1: Nested block elimination removes a factor p from the degree-dependent term and decouples Tf from the d-scaled logarithm.The passage states that these improvements are supported by complementary lower bounds.
  • C.2 Proofs for Section 5.2: The piece-count construction shatters pB problem instances, proving Pdim(L) = Ω(p log Tf).The constructed functions have complexity (⌊Tf −1, Tf, 1), and the piece functions encode binary labels through bitb(r).
  • C.2 Proofs for Section 5.2: The boundary-count construction realizes SM,d = Qd i=1(2mi + 1) sign patterns and RM,d = Qd i=1(mi + 1) zero-free regions.The zero-free regions correspond to distinct integer vectors and are non-empty within Θ.
  • C.2 Proofs for Section 5.2: Pdim(L) ≥ pB = p ⌊log2 RM,d⌋ for instances whose piecewise polynomial complexity is (M, SM,d, 2).The proof selects K = 2B distinct zero-free grid regions and encodes labels through their indexed sign patterns.

D Additional Results and Proofs for Section 6 · E Additional results and Omitted proofs for Section 7

The appendix proves Theorem 6.1 by encoding validation-threshold events as Boolean combinations of polynomial first-order formulas and applying nested block elimination. It also shows sharper algebraic and combinatorial dependencies than prior standard quantifier-elimination bounds.

  • D Additional Results and Proofs for Section 6: The proof represents each fixed-instance validation-threshold event as a Boolean combination of polynomial first-order formulas.This representation enables application of Theorem 4.2.
  • D Additional Results and Proofs for Section 6: Piecewise-polynomial training and validation regions are indexed by sign conditions, with separate region predicates and a parameter-feasibility condition characterizing u ∈ Θ.The construction uses training and validation sign-condition sets and verifies parameter feasibility exactly.
  • D Additional Results and Proofs for Section 6: A candidate is certified as a training minimizer by comparing it against every competing solution within the relevant active training sign condition.The proof handles active and inactive sign conditions through comparison predicates.
  • D Additional Results and Proofs for Section 6: Candidate conditions can be arranged into two ordered quantifier blocks, (∃θ ∈ R^d)(∀u ∈ R^d), so every branch has K = 2 and d_1 = d_2 = d.This follows because the candidate conditions do not depend on u.
  • D Additional Results and Proofs for Section 6: The validation threshold is expressed using at most L ≤ T_fT_g polynomial branches, each containing at most M_tot = 2M_f + M_g + T_f + 4d + 1 atomic predicates of degree at most Δ_f,g = max{1, Δ_f, Δ_g}.The argument does not require the validation-loss infimum to be attained.
  • D Additional Results and Proofs for Section 6: Prior work obtained O(pd^2 log(M_f + T_F + M_g + T_g + d) + p^2d^2 log Δ_f,g) using standard quantifier elimination.The comparison identifies the earlier bound before stating the improvements of Theorem 6.1.
  • D Additional Results and Proofs for Section 6: Theorem 6.1 reduces the degree-dependent term from p^2d^2 log Δ_f,g to pd^2 log Δ_f,g and the T_g dependence from pd^2 log T_g to p log T_g.These improvements come from nested block elimination and separate logical branches for the T_fT_g active-piece pairs.

E.1 Omitted proof for Section 7 … Multi-penalty ridge regression

The paper proves sharper pseudo-dimension guarantees for structured data-driven tuning and applies its framework to cost-sensitive SVMs and multi-penalty ridge regression. These results use piecewise-polynomial or more general structures convertible to the paper’s general theorem.

  • E.1 Omitted proof for Section 7: Theorem 7.1 bounds the Weighted Group Lasso validation-loss class by Pdim(Lval) = O(p(d + p)^2 log p) under Θ = R^d and A ⊂ (0, ∞)^p.The proof converts group norms into polynomial form and applies nested block elimination.
  • E.2 Other Applications: The framework’s main contribution is a general method for learning guarantees when data-driven algorithms have piecewise-polynomial structure or can be converted to Theorem 4.2’s form.The paper introduces further applications to demonstrate this framework’s applicability.
  • Data-driven Cost-sensitive SVM.: The cost-sensitive SVM analysis establishes a generalization guarantee by uniformly bounding realized training and validation sign conditions.The parameter domain is bounded, and strong convexity gives a unique minimizer, although the general framework does not require uniqueness.
  • Data-driven Cost-sensitive SVM.: The SVM training objective has piecewise-polynomial complexity (Mf, Tf, ∆f) = (n, Ttr, 2), while validation has (Mg, Tg, ∆g) = (m, Tval, 1).The training pieces have total degree at most two because mixed terms are bilinear; Ttr ≤ 3n and Tval ≤ 3m.
  • Multi-penalty ridge regression: Multi-penalty ridge regression tunes several regularization penalties over box-like hyperparameter and parameter domains to promote different structural properties of fitted solutions.Its optimistic validation-loss class is denoted Lridge.
  • Multi-penalty ridge regression: Corollary E.2 gives the ridge-regression pseudo-dimension bound Pdim(Lridge) = O(pd^2 log d).The training and validation objectives have complexities (Mf, Tf, δf) = (0, 1, 3) and (Mg, Tg, ∆g) = (0, 1, 2), respectively.
Loading 2608.17343v1…