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

# Tight Bounds for Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function
Source: [https://arxiv.org/html/2608.17343](https://arxiv.org/html/2608.17343)
###### Abstract

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\.

## 1Introduction

The success of modern machine learning relies heavily on the meticulous selection of hyperparameters\([27](https://arxiv.org/html/2608.17343#bib.bib25);[1](https://arxiv.org/html/2608.17343#bib.bib21)\)\. Despite its central role in model deployment, hyperparameter tuning is predominantly treated as an empirical art rather than a rigorous analytical discipline\. Traditional approaches, such as exhaustive grid search or random search, discretize continuous parameter spaces to identify high\-performing configurations through empirical validation\. While straightforward in practice, these brute\-force methods are theoretically unprincipled and fail to provide formal generalization guarantees across continuous hyperparameter spaces\.

To automate this process, practitioners often rely on sophisticated heuristic search strategies, including Bayesian optimization\([14](https://arxiv.org/html/2608.17343#bib.bib22)\)and spectral methods\([18](https://arxiv.org/html/2608.17343#bib.bib23)\)\. However, these techniques typically hinge on restrictive structural assumptions, such as modeling the loss landscape as a smooth Gaussian process, that often fail to capture the highly volatile, non\-convex nature of modern objective functions\. Furthermore, resource\-allocation strategies like Hyperband\([22](https://arxiv.org/html/2608.17343#bib.bib24)\)excel at computational efficiency via early stopping, yet they primarily focus on discrete search spaces for fixed problem instances\. Consequently, these frameworks lack the theoretical machinery to characterize the fundamental statistical complexity of identifying optimal continuous hyperparameters\.

To bridge this theoretical gap, thedata\-driven algorithm designparadigm\([17](https://arxiv.org/html/2608.17343#bib.bib9);[8](https://arxiv.org/html/2608.17343#bib.bib10)\)frames hyperparameter tuning as a formal statistical learning problem over an unknown, application\-specific problem distribution𝒟\\mathcal\{D\}over the problem space𝒳\\mathcal\{X\}\. Given a finite sample of training instancesS∼𝒟NS\\sim\\mathcal\{D\}^\{N\}, the goal is to identify a hyperparameter configuration that provably generalizes to unseen problem instancesx∼𝒟x\\sim\\mathcal\{D\}from the exact same distribution\. This process is inherently bi\-level: the induced lossℓα​\(x\)=infθ∈𝒮⁡\(x,α\)g⁡\(x,α,θ\)\\ell\_\{\\alpha\}\(x\)=\\inf\_\{\\theta\\in\\mathcal\{S\}\(x,\\alpha\)\}g\(x,\\alpha,\\theta\)is evaluated on a target validation objectivegg, subject to the model parametersθ\\thetabeing optimized over a surrogate training objectiveff, that is,𝒮⁡\(x,α\)=arg⁡minθ∈Θ⁡f⁡\(x,α,θ\)\\mathcal\{S\}\(x,\\alpha\)=\\arg\\min\_\{\\theta\\in\\Theta\}f\(x,\\alpha,\\theta\)\. For example, in ridge regression, a problem instancex=\(A,b,A′,b′\)∈𝒳x=\(A,b,A^\{\\prime\},b^\{\\prime\}\)\\in\\mathcal\{X\}consists of a training and a validation set\. The hyperparameterα\\alphaexplicitly regularizes the training objectivef\(x,α,θ\)=∥Aθ−b∥\+22α∥θ∥22f\(x,\\alpha,\\theta\)=\\\|\{\}A\\theta\-b\\\|\{\}\_\{2\}^\{2\}\+\\alpha\\\|\{\}\\theta\\\|\{\}\_\{2\}^\{2\}, but impacts the validation targetg\(x,α,θ\)=∥A′θ−b′∥22g\(x,\\alpha,\\theta\)=\\\|\{\}A^\{\\prime\}\\theta\-b^\{\\prime\}\\\|\{\}\_\{2\}^\{2\}only implicitly via the optimal weightsθ∈𝒮⁡\(x,α\)\\theta\\in\\mathcal\{S\}\(x,\\alpha\)\. Bounding the statistical complexity of this non\-smooth dependency, whereα\\alphaacts exclusively through the argmin of an auxiliary problem, is our fundamental theoretical hurdle\.

To overcome this challenge, we leverage statistical learning theory to bound the generalization capacity, measured via the pseudo\-dimension, of the hyperparameter\-induced loss function classℒ=\{ℓα:𝒳→\[−H,H\]∣α∈𝒜\}\\mathcal\{L\}=\\\{\\ell\_\{\\alpha\}:\\mathcal\{X\}\\to\[\-H,H\]\\mid\\alpha\\in\\mathcal\{A\}\\\}\. Our analysis relies on the structural observation that for many practical machine learning problems, the training objectivefx​\(α,θ\)≜f⁡\(x,α,θ\)f\_\{x\}\(\\alpha,\\theta\)\\triangleq f\(x,\\alpha,\\theta\)admits apiecewise polynomial structurewith respect to both the hyperparameterα\\alphaand the model parameterθ\\theta; see e\.g\., Definition[7](https://arxiv.org/html/2608.17343#Thmdefinition7)for the formal definition and Figure[2](https://arxiv.org/html/2608.17343#S3.F2)for a simple example\. This piecewise polynomial assumption ishighly ubiquitous: it has been rigorously established across a wide spectrum of applications in classical learning theory\([11](https://arxiv.org/html/2608.17343#bib.bib26);[24](https://arxiv.org/html/2608.17343#bib.bib28);[10](https://arxiv.org/html/2608.17343#bib.bib27)\)and in recent data\-driven algorithm design frameworks\([5](https://arxiv.org/html/2608.17343#bib.bib19);[7](https://arxiv.org/html/2608.17343#bib.bib18);[25](https://arxiv.org/html/2608.17343#bib.bib13)\)\.

Despite the prevalence of this structure, existing generalization guarantees remain fundamentally limited\.[3](https://arxiv.org/html/2608.17343#bib.bib5)provided the first formal framework for this setting, but their ad\-hoc, low\-dimensional geometric analysis is highly restrictive: it applies exclusively toone\-dimensional hyperparameters\(α∈ℝ\\alpha\\in\\mathbb\{R\}\) andsingle\-level objectives\(f≡gf\\equiv g\)\.[21](https://arxiv.org/html/2608.17343#bib.bib6)successfully extended this analysis to multi\-dimensional hyperparameters \(α∈ℝp\\alpha\\in\\mathbb\{R\}^\{p\}\) and general bi\-level objectives \(f≢gf\\not\\equiv g\) using a model\-theoretic approach\. However, their statistical bounds are demonstrably suboptimal\. Relying heavily on Quantifier Elimination \(QE\)\([13](https://arxiv.org/html/2608.17343#bib.bib4)\)followed by the Goldberg\-Jerrum \(GJ\) framework\([9](https://arxiv.org/html/2608.17343#bib.bib2)\), their approach generates overly conservative upper bounds due to topological under\-counting and inflated algebraic dependencies\. Furthermore, their approach fails to establish a lower bound that captures the true combinatorial capacity of the problem, specifically one that scales with the piecewise structural complexities, such as the number of pieces and the number of boundaries\. These unresolved theoretical gaps directly motivate the tight bounding techniques developed in this work\.

Contributions\.In this work, we resolve the theoretical limitations of prior data\-driven hyperparameter tuning frameworks by establishing improved pseudo\-dimension bounds for the multi\-dimensional setting\. Our core contributions are:

- •We establish in Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)that if a loss function is definable in polynomialfirst\-order logic\(FOL\), its pseudo\-dimension is tightly bounded by the topological complexity of a nested block elimination process\. By analyzing invariant connected sign cells, this approach bypasses the inflated algebraic dependencies of prior quantifier elimination methods\([21](https://arxiv.org/html/2608.17343#bib.bib6)\)\.
- •We apply our nested block elimination framework to the standard training\-loss setting \(f≡gf\\equiv g\), where the underlying objectivef⁡\(x,α,θ\)f\(x,\\alpha,\\theta\)exhibits a piecewise polynomial structure \(Theorem 5\.1\)\. By representing the induced lossℓα​\(x\)=minθ∈Θ⁡f⁡\(x,α,θ\)\\ell\_\{\\alpha\}\(x\)=\\min\_\{\\theta\\in\\Theta\}f\(x,\\alpha,\\theta\)as a polynomial FOL, we derive strictly sharper pseudo\-dimension bounds that directly resolve the suboptimal multi\-dimensional guarantees of prior work\([21](https://arxiv.org/html/2608.17343#bib.bib6)\)\.
- •We complement our upper bounds with a novel multi\-regime lower\-bound framework in Lemmas[5\.2](https://arxiv.org/html/2608.17343#S5.Thmtheorem2)and[5\.3](https://arxiv.org/html/2608.17343#S5.Thmtheorem3)\. By independently analyzing the combinatorial \(Tf,MfT\_\{f\},M\_\{f\}\) and algebraic \(Δf\\Delta\_\{f\}\) capacities, we prove that our upper bounds are tight with respect toTfT\_\{f\}andΔf\\Delta\_\{f\}, and nearly tight with respect toMfM\_\{f\}\. This establishes the fundamental necessity of each structural parameter in our theoretical guarantees\.
- •We extend our framework to the general bi\-level validation\-loss setting and broader semi\-algebraic applications \(Theorems[6\.1](https://arxiv.org/html/2608.17343#S6.Thmtheorem1)and[7\.1](https://arxiv.org/html/2608.17343#S7.Thmtheorem1)\)\. By applying nested block elimination to validation\-loss tuning, we eliminate the inflated algebraic dependencies of prior work\. Furthermore, we demonstrate the framework’s versatility by analyzing the Weighted Group Lasso, accommodating structures beyond piecewise polynomials and strictly improving existing sample complexity bounds by a full factor ofpp\.

Technical difference and overviews\.Bounding the generalization capacity of multi\-dimensional, bi\-level hyperparameter tuning requires capturing the implicit, non\-smooth dependency of the validation loss on the hyperparameters\. Prior model\-theoretic work approached this by applying standard Quantifier Elimination \(QE\) followed by the Goldberg\-Jerrum framework\([21](https://arxiv.org/html/2608.17343#bib.bib6)\)\. However, this strategy yields highly suboptimal statistical bounds due to severe topological overcounting\. To resolve this, we introduce a novel geometric framework based on nested block elimination\. Rather than evaluating isolated sign conditions, we recursively construct a nested block\-sign profile that tracks the logical invariance of polynomial formulas across entire connected sign cells\. This topological shift completely bypasses the algebraic inflation inherent to standard QE, enabling us to derive strictly sharper, optimal sample\-complexity guarantees for the multi\-dimensional tuning problem\. See Appendix[A\.2](https://arxiv.org/html/2608.17343#A1.SS2)for a detailed discussion\.

Notations\.For a real\-valuedt∈ℝt\\in\\mathbb\{R\}, we denotesign​\(t\)=0\{\\text\{sign\}\}\(t\)=0ift=0t=0,sign​\(t\)=1\{\\text\{sign\}\}\(t\)=1ift\>0t\>0, andsign​\(t\)=−1\{\\text\{sign\}\}\(t\)=\-1otherwise\. For avariablez∈ℝkz\\in\\mathbb\{R\}^\{k\}, we denoteℝ⁡\[z\]\\mathbb\{R\}\[z\]thepolynomial ringofzz, containing all \(multivariate\) polynomials ofzz; e\.g\.,P⁡\(z\)=z12\+z22∈ℝ⁡\[z\]P\(z\)=z\_\{1\}^\{2\}\+z\_\{2\}^\{2\}\\in\\mathbb\{R\}\[z\]forz∈ℝ2z\\in\\mathbb\{R\}^\{2\}\. Given a polynomialP⁡\(z\)P\(z\), we denotedeg⁡\(P\)\\deg\(P\)thedegreeofP⁡\(z\)P\(z\); e\.g\.,deg⁡\(P\)=2\\deg\(P\)=2forP⁡\(z\)=z12\+z22P\(z\)=z\_\{1\}^\{2\}\+z\_\{2\}^\{2\}\. For a functionh⁡\(z,x\)h\(z,x\)that takes both variableszzandxxas inputs, we denotehx​\(z\)≜h⁡\(z,x\)h\_\{x\}\(z\)\\triangleq h\(z,x\)theinduced functionwhen we treatxxas fixed and varyzz\. For a logic sentenceAA, we denote𝕀⁡\(A\)=1\\mathbb\{I\}\(A\)=1ifAAis true, else 0; e\.g\.,𝕀⁡\(1\>0\)=1\\mathbb\{I\}\(1\>0\)=1, and𝕀⁡\(0\>1\)=0\\mathbb\{I\}\(0\>1\)=0\.

### 1\.1Related Works

##### Data\-driven algorithm design\.

Data\-driven algorithm design\([17](https://arxiv.org/html/2608.17343#bib.bib9);[8](https://arxiv.org/html/2608.17343#bib.bib10)\)adapts hyperparameters to specific problem distributions rather than relying on worst\-case instances\. This paradigm has achieved significant empirical success across diverse domains, including sketching\([23](https://arxiv.org/html/2608.17343#bib.bib11);[19](https://arxiv.org/html/2608.17343#bib.bib12)\), linear and mixed\-integer programming\([29](https://arxiv.org/html/2608.17343#bib.bib14);[25](https://arxiv.org/html/2608.17343#bib.bib13);[4](https://arxiv.org/html/2608.17343#bib.bib15);[15](https://arxiv.org/html/2608.17343#bib.bib16);[20](https://arxiv.org/html/2608.17343#bib.bib7)\), and regularization tuning\([6](https://arxiv.org/html/2608.17343#bib.bib17);[7](https://arxiv.org/html/2608.17343#bib.bib18)\)\.

##### Theoretical guarantees for data\-driven algorithm design\.

Motivated by empirical successes, recent work has sought to establish statistical guarantees for data\-driven algorithm design\([5](https://arxiv.org/html/2608.17343#bib.bib19);[9](https://arxiv.org/html/2608.17343#bib.bib2);[2](https://arxiv.org/html/2608.17343#bib.bib20)\)\. However, the non\-smooth, potentially discontinuous hyperparameter landscapeℓx​\(α\)\\ell\_\{x\}\(\\alpha\)makes this challenging, leading most analyses to avoid inner optimization over model parametersθ\\theta\. While[3](https://arxiv.org/html/2608.17343#bib.bib5)tackled this harder bi\-level case, their framework is restricted to one\-dimensional hyperparameters \(α∈ℝ\\alpha\\in\\mathbb\{R\}\) and single\-level objectives \(f≡gf\\equiv g\)\.[21](https://arxiv.org/html/2608.17343#bib.bib6)recently extended this to multi\-dimensional \(α∈ℝp\\alpha\\in\\mathbb\{R\}^\{p\}\) and general bi\-level settings \(f≢gf\\not\\equiv g\), but their complexity bounds remain theoretically loose and lack lower bounds; these are the gaps we resolve in this work\.

## 2Preliminaries

### 2\.1Backgrounds on Learning Theory

We first recall some standard results in learning theory, which play the central role in this work\.

###### Definition 1\(Pseudo\-dimension\([26](https://arxiv.org/html/2608.17343#bib.bib1)\)\)\.

Consider a real\-valued function classℒ=\{ℓα:𝒳→ℝ∣α∈𝒜\}\\mathcal\{L\}=\\\{\\ell\_\{\\alpha\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}\\mid\\alpha\\in\\mathcal\{A\}\\\}parameterized byα∈𝒜\\alpha\\in\\mathcal\{A\}\. Given a set of inputsS=\(x1,…,xN\)⊂𝒳S=\(x\_\{1\},\\dots,x\_\{N\}\)\\subset\\mathcal\{X\}, we say thatSSis shattered byℒ\\mathcal\{L\}if there exists a set of real\-valued thresholdτ1,…,τN∈ℝ\\tau\_\{1\},\\dots,\\tau\_\{N\}\\in\\mathbb\{R\}such that\|\{\(𝕀⁡\(ℓα​\(x1\)≥τ1\),…,𝕀⁡\(ℓα​\(xN\)≥τN\)\)∣ℓα∈ℒ\}\|=2N\\left\|\\\{\(\\mathbb\{I\}\(\\ell\_\{\\alpha\}\(x\_\{1\}\)\\geq\\tau\_\{1\}\),\\dots,\\mathbb\{I\}\(\\ell\_\{\\alpha\}\(x\_\{N\}\)\\geq\\tau\_\{N\}\)\)\\mid\\ell\_\{\\alpha\}\\in\\mathcal\{L\}\\\}\\right\|=2^\{N\}\. The pseudo\-dimension ofℒ\\mathcal\{L\}, denotedPdim​\(ℒ\)\\text\{Pdim\}\(\\mathcal\{L\}\), is the maximum sizeNNof an input set thatℒ\\mathcal\{L\}can shatter\.

A finite pseudo\-dimension guarantees uniform convergence via empirical risk minimization \(ERM\)\.

###### Theorem 2\.1\([26](https://arxiv.org/html/2608.17343#bib.bib1)\)\.

Consider a real\-valued function classℒ=\{ℓα:𝒳→\[−H,H\]∣α∈𝒜\}\\mathcal\{L\}=\\\{\\ell\_\{\\alpha\}:\\mathcal\{X\}\\rightarrow\[\-H,H\]\\mid\\alpha\\in\\mathcal\{A\}\\\}parameterized byα∈𝒜\\alpha\\in\\mathcal\{A\}\. Assume thatPdim​\(ℒ\)\\text\{Pdim\}\(\\mathcal\{L\}\)is finite\. Then givenϵ\>0\\epsilon\>0andδ∈\(0,1\)\\delta\\in\(0,1\), for anyN≥N⁡\(ϵ,δ\)N\\geq N\(\\epsilon,\\delta\), whereN⁡\(ϵ,δ\)=𝒪⁡\(H2ϵ2​\(Pdim​\(ℒ\)\+log⁡\(1/δ\)\)\)N\(\\epsilon,\\delta\)=\\mathcal\{O\}\\left\(\\frac\{H^\{2\}\}\{\\epsilon^\{2\}\}\(\\text\{Pdim\}\(\\mathcal\{L\}\)\+\\log\(1/\\delta\)\)\\right\), with probability at least1−δ1\-\\deltaover the draw ofS=\(x1,…,xN\)∼𝒟NS=\(x\_\{1\},\\dots,x\_\{N\}\)\\sim\\mathcal\{D\}^\{N\}, where𝒟\\mathcal\{D\}is a distribution over𝒳\\mathcal\{X\}, we have𝔼x∼𝒟​\[ℓα^​\(x\)\]≤infα∈𝒜𝔼x∼𝒟​\[ℓα​\(x\)\]\+ϵ\.\\mathbb\{E\}\_\{x\\sim\\mathcal\{D\}\}\[\\ell\_\{\\hat\{\\alpha\}\}\(x\)\]\\leq\\inf\_\{\\alpha\\in\\mathcal\{A\}\}\\mathbb\{E\}\_\{x\\sim\\mathcal\{D\}\}\[\\ell\_\{\\alpha\}\(x\)\]\+\\epsilon\.Hereα^∈arg⁡min⁡∑x∈Sα∈𝒜⁡ℓα​\(x\)\\hat\{\\alpha\}\\in\\arg\\min\_\{\\alpha\\in\\mathcal\{A\}\}\\sum\_\{x\\in S\}\\ell\_\{\\alpha\}\(x\)is the ERM minimizer w\.r\.t\. the set of instancesSS\.

### 2\.2Backgrounds on Real\-Algebraic Geometry

In this section, we present the necessary background for our block elimination approach\. First, we introduce the notion offirst\-order formula\(FOL\)\.

###### Definition 2\(First\-order formula, quantified/free variables, and polynomial first\-order logic\([28](https://arxiv.org/html/2608.17343#bib.bib3)\)\)\.

A first\-order formula \(FOL\)Φ⁡\(α\)\\Phi\(\\alpha\)admits the form:

\(q1​θ\[1\]∈ℝd1\)​…​\(qK​θ\[K\]∈ℝdK\)​ψ​\(α,θ\[1\],…,θ\[K\]\),\(q\_\{1\}\\theta^\{\[1\]\}\\in\\mathbb\{R\}^\{d\_\{1\}\}\)\\ldots\(q\_\{K\}\\theta^\{\[K\]\}\\in\\mathbb\{R\}^\{d\_\{K\}\}\)\\psi\(\\alpha,\\theta^\{\[1\]\},\\ldots,\\theta^\{\[K\]\}\),\(1\)where

1. 1\.Eachqkq\_\{k\}is one of the quantifiers∃\\existsor∀\\forall\. The sequence\{qk\}k=1K\\\{q\_\{k\}\\\}\_\{k=1\}^\{K\}alternates between∃\\existsand∀\\foralland we denoteKKas the number of quantifier blocks\.
2. 2\.θ\[1\],θ\[2\],…,θ\[K\]\\theta^\{\[1\]\},\\theta^\{\[2\]\},\\ldots,\\theta^\{\[K\]\}are called the quantified variables, whileα∈ℝp\\alpha\\in\\mathbb\{R\}^\{p\}is called the free variable\.
3. 3\.ψ⁡\(α,θ\[1\],θ\[2\],…,θ\[K\]\)\\psi\(\\alpha,\\theta^\{\[1\]\},\\theta^\{\[2\]\},\\ldots,\\theta^\{\[K\]\}\)is a boolean combination of atomic predicates of the form: Pj​\(α,θ\[1\],θ\[2\],…,θ\[K\]\)​χj​0,P\_\{j\}\(\\alpha,\\theta^\{\[1\]\},\\theta^\{\[2\]\},\\ldots,\\theta^\{\[K\]\}\)\\,\\chi\_\{j\}\\,0,whereχj∈\{\>,≥,<,≤,=,≠\}\\chi\_\{j\}\\in\\\{\>,\\geq,<,\\leq,=,\\neq\\\}is relational operator\.

The formulaψ\\psiis called the quantifier\-free part ofΦ\\Phi\. A FOLΦ\\Phiis a*polynomial*FOL if eachPjP\_\{j\}is a polynomial ofα\\alphaandθ\[1\],…,θ\[K\]\\theta^\{\[1\]\},\\dots,\\theta^\{\[K\]\}\.

While our bi\-level optimization naturally maps to a polynomial FOL, applying standard QE yields conservative upper bounds\. To derive a sharper sample complexity, we track logical invariance across geometric regions rather than isolated points\. We formalize these regions using sign conditions\.

###### Definition 3\(Sign conditions and their realizations\)\.

Let𝒫=\{P1,…,Ps\}⊂ℝ⁡\[z\]\\mathcal\{P\}=\\\{P\_\{1\},\\dots,P\_\{s\}\\\}\\subset\\mathbb\{R\}\[z\]be a finite set of polynomials inz∈ℝpz\\in\\mathbb\{R\}^\{p\}, and letZ⊂ℝpZ\\subset\\mathbb\{R\}^\{p\}\. A sign condition on𝒫\\mathcal\{P\}is a vectorσ=\(σ1,…,σs\)∈\{−1,0,1\}s\\sigma=\(\\sigma\_\{1\},\\dots,\\sigma\_\{s\}\)\\in\\\{\-1,0,1\\\}^\{s\}\. The realizationReali𝒫​\(σ,Z\)\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\\sigma,Z\)of sign conditionσ\\sigmaoverZZis a set ofz∈Zz\\in Zsuch thatsign​\(Pi​\(z\)\)=σi\{\\text\{sign\}\}\(P\_\{i\}\(z\)\)=\\sigma\_\{i\}for everyi=1,…,si=1,\\dots,s, that is,

Reali𝒫\(σ,Z\)=\{z∈Z∣sign\(Pi\(z\)\)=σi,i=1,…,s\}\.\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\\sigma,Z\)=\\\{z\\in Z\\mid\{\\text\{sign\}\}\(P\_\{i\}\(z\)\)=\\sigma\_\{i\},i=1,\\dots,s\\\}\.We then denoteSign​\(𝒫,Z\)\{\\textup\{Sign\}\}\(\\mathcal\{P\},Z\)the set of all possible sign conditionsσ\\sigmathat we can have by varyingz∈Zz\\in Z, that is

Sign​\(𝒫,Z\)=\{σ∈\{−1,0,1\}s∣Reali𝒫​\(σ,Z\)≠∅\}\.\{\\textup\{Sign\}\}\(\\mathcal\{P\},Z\)=\\\{\\sigma\\in\\\{\-1,0,1\\\}^\{s\}\\mid\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\\sigma,Z\)\\neq\\emptyset\\\}\.Equivalently,Sign​\(𝒫,Z\)=\{sign​\(𝒫⁡\(z\)\):z∈Z\}\{\\textup\{Sign\}\}\(\\mathcal\{P\},Z\)=\\\{\{\\text\{sign\}\}\(\\mathcal\{P\}\(z\)\):z\\in Z\\\}, where we abuse notation and write

sign​\(𝒫⁡\(z\)\)=\(sign​\(P1​\(z\)\),…,sign​\(Ps​\(z\)\)CLOSE\.\{\\text\{sign\}\}\(\\mathcal\{P\}\(z\)\)=\(\{\\text\{sign\}\}\(P\_\{1\}\(z\)\),\\dots,\{\\text\{sign\}\}\(P\_\{s\}\(z\)\)\.WhenZ=ℝpZ=\\mathbb\{R\}^\{p\}, we shorten the notation and writeReali𝒫​\(σ\)=Reali𝒫​\(σ,ℝp\)\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\\sigma\)=\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\\sigma,\\mathbb\{R\}^\{p\}\)andSign​\(𝒫,ℝp\)=Sign​\(𝒫\)\{\\textup\{Sign\}\}\(\\mathcal\{P\},\\mathbb\{R\}^\{p\}\)=\{\\textup\{Sign\}\}\(\\mathcal\{P\}\)\.

###### Definition 4\(Connected sign cells\)\.

Let𝒫⊂ℝ⁡\[z\]\\mathcal\{P\}\\subset\\mathbb\{R\}\[z\]be a finite set of polynomials\. For each realizable sign patternσ∈Sign​\(𝒫\)\\sigma\\in\{\\textup\{Sign\}\}\(\\mathcal\{P\}\), letCc​\(Reali𝒫​\(σ\)\)\{\\textup\{Cc\}\}\(\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\\sigma\)\)denote the set of connected components of the realizationReali𝒫​\(σ\)\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\\sigma\)\. We then denoteCell​\(𝒫\)\{\\textup\{Cell\}\}\(\\mathcal\{P\}\)the set of connected sign cells induced by𝒫\\mathcal\{P\}, that is

Cell​\(𝒫\)=⋃σ∈Sign​\(𝒫\)Cc​\(Reali𝒫​\(σ\)\)\.\{\\textup\{Cell\}\}\(\\mathcal\{P\}\)=\\bigcup\_\{\\sigma\\in\{\\textup\{Sign\}\}\(\\mathcal\{P\}\)\}\{\\textup\{Cc\}\}\(\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\\sigma\)\)\.We further denoteb0​\(S\)b\_\{0\}\(S\)the number of connected components ofSS, and therefore

\|Cell​\(𝒫\)\|=∑σ∈Sign​\(𝒫\)b0​\(Reali𝒫​\(σ\)\)\.\|\{\\textup\{Cell\}\}\(\\mathcal\{P\}\)\|=\\sum\_\{\\sigma\\in\{\\textup\{Sign\}\}\(\\mathcal\{P\}\)\}b\_\{0\}\(\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\\sigma\)\)\.

zz−1\-111C1C\_\{1\}C3C\_\{3\}C5C\_\{5\}C2C\_\{2\}C4C\_\{4\}Figure 1:A demonstration of sign conditions, realizations, and cells for𝒫=\{P\(z\)=z2−1\}⊂ℝ\[z\]\\mathcal\{P\}=\\\{P\(z\)=z^\{2\}\-1\\\}\\subset\\mathbb\{R\}\[z\]\. The realizationReali𝒫​\(1\)\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(1\)yields two connected components:C1=\(−∞,−1\)C\_\{1\}=\(\-\\infty,\-1\)andC5=\(1,∞\)C\_\{5\}=\(1,\\infty\)\. Conversely,Reali𝒫​\(−1\)\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(\-1\)yields a single componentC3=\(−1,1\)C\_\{3\}=\(\-1,1\), andReali𝒫​\(0\)\{\\textup\{Reali\}\}\_\{\\mathcal\{P\}\}\(0\)yieldsC2=\{−1\}C\_\{2\}=\\\{\-1\\\}andC4=\{1\}C\_\{4\}=\\\{1\\\}\. Ultimately,𝒫\\mathcal\{P\}induces\|Cell​\(𝒫\)\|=5\|\{\}\{\\textup\{Cell\}\}\(\\mathcal\{P\}\)\|\{\}=5connected sign cells:Cell​\(𝒫\)=\{C1,C2,C3,C4,C5\}\{\\textup\{Cell\}\}\(\\mathcal\{P\}\)=\\\{C\_\{1\},C\_\{2\},C\_\{3\},C\_\{4\},C\_\{5\}\\\}\.Figure[1](https://arxiv.org/html/2608.17343#S2.F1)demonstrates the concepts above\. We now formulate block elimination in terms of these connected sign cells\. Given polynomials in free variableszzand variablesttto be eliminated, the block elimination process aims to produce a set of polynomials inzzwhose connected sign cells preserve the sign information attainable by varyingtt\. Critically, our multi\-dimensional tuning problem involves distinct blocks of quantified variables that must be eliminated sequentially\. Evaluating them simultaneously destroys this block\-wise grouping, leading to topological under\-counting\. To bypass this algebraic inflation, we track sign invariance sequentially by constructing nested profiles\.

###### Definition 5\(Nested block\-sign profiles\)\.

Let𝒫=\{P1,…,Ps\}⊂ℝ⁡\[z,t\(1\),…,t\(K\)\]\\mathcal\{P\}=\\\{P\_\{1\},\\dots,P\_\{s\}\\\}\\subset\\mathbb\{R\}\[z,t^\{\(1\)\},\\dots,t^\{\(K\)\}\], wherez∈ℝpz\\in\\mathbb\{R\}^\{p\}andt\(k\)∈ℝdkt^\{\(k\)\}\\in\\mathbb\{R\}^\{d\_\{k\}\}fork=1,…,Kk=1,\\dots,K\. We define the terminal sign vectorΣK​\(z,t\(1\),…,t\(K\)\)=sign​\(𝒫⁡\(z,t\(1\),…,t\(K\)\)\)\\Sigma\_\{K\}\(z,t^\{\(1\)\},\\dots,t^\{\(K\)\}\)=\{\\text\{sign\}\}\(\\mathcal\{P\}\(z,t^\{\(1\)\},\\dots,t^\{\(K\)\}\)\)\. Recursively, fork=K,…,1k=K,\\dots,1, we define

Σk−1​\(z,t\(1\),…,t\(k−1\)\)=\\displaystyle\\Sigma\_\{k\-1\}\(z,t^\{\(1\)\},\\dots,t^\{\(k\-1\)\}\)\\\!=\\\!\{Σk​\(z,t\(1\),…,t\(k−1\),u\):u∈ℝdk\}\.\\displaystyle\\qquad\\qquad\\\{\\Sigma\_\{k\}\(z,t^\{\(1\)\},\\dots,t^\{\(k\-1\)\},u\)\\\!:\\\!u\\in\\mathbb\{R\}^\{d\_\{k\}\}\\\}\.Then, we callΣ0​\(z\)\\Sigma\_\{0\}\(z\)the nested block\-sign profile of𝒫\\mathcal\{P\}at a fixed pointz∈ℝpz\\in\\mathbb\{R\}^\{p\}, relative to the ordered variable blockst\(1\),…,t\(K\)t^\{\(1\)\},\\dots,t^\{\(K\)\}\.

Roughly speaking, in Definition[5](https://arxiv.org/html/2608.17343#Thmdefinition5), we can think of theterminal sign vectorΣK\\Sigma\_\{K\}as an ordinary sign vector, and subsequentlyΣK−1\\Sigma\_\{K\-1\}is a set of sign vectors, and so on\. Finally, the nested block\-sign profileΣ0​\(z\)\\Sigma\_\{0\}\(z\)can be thought of as a depth\-KKsign tree\. Specifically, unlike the ordinary set of sign conditions obtained by varying all quantified variables simultaneously,Σ0​\(z\)\\Sigma\_\{0\}\(z\)retains the block\-wise grouping of realizable sign patterns, which is crucial in our analysis\. Based on this definition, we can now formally define thenested sign\-invariant projectionas follows\.

###### Definition 6\(Nested sign\-invariant projection\)\.

A set of polynomialsQ⊂ℝ⁡\[z\]Q\\subset\\mathbb\{R\}\[z\]is a nested sign\-invariant projection of𝒫⊂ℝ⁡\[z,t\(1\),…,t\(K\)\]\\mathcal\{P\}\\subset\\mathbb\{R\}\[z,t^\{\(1\)\},\\dots,t^\{\(K\)\}\], relative to the ordered blockst\(1\),…,t\(K\)t^\{\(1\)\},\\dots,t^\{\(K\)\}, if the nested block\-sign profileΣ0​\(z\)\\Sigma\_\{0\}\(z\)is constant on every connected sign cell induced by𝒬\\mathcal\{Q\}\. That is, for everyC∈Cell​\(𝒬\)C\\in\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)and everyz1,z2∈Cz\_\{1\},z\_\{2\}\\in C, we haveΣ0​\(z1\)=Σ0​\(z2\)\\Sigma\_\{0\}\(z\_\{1\}\)=\\Sigma\_\{0\}\(z\_\{2\}\)\.

Specially, whenK=1K=1, we haveΣ0\(z\)=\{sign\(𝒫\(z,u\):u∈ℝd1\}=Sign\(𝒫z,ℝd1\)\\Sigma\_\{0\}\(z\)=\\\{\{\\text\{sign\}\}\(\\mathcal\{P\}\(z,u\):u\\in\\mathbb\{R\}^\{d\_\{1\}\}\\\}=\{\\textup\{Sign\}\}\(\\mathcal\{P\}\_\{z\},\\mathbb\{R\}^\{d\_\{1\}\}\)\. Thus, in the one\-block case, Definition[6](https://arxiv.org/html/2608.17343#Thmdefinition6)simply requires the set of realizable sign conditions to be unchanged on every connected sign cell induced by𝒬\\mathcal\{Q\}\. To help the audience quickly grasp the concepts of nested block\-sign profiles in Definition[5](https://arxiv.org/html/2608.17343#Thmdefinition5)and nested\-sign invariant projection in Definition[6](https://arxiv.org/html/2608.17343#Thmdefinition6), we present the following simple example\.

###### Example 1\.

Letz,u,v∈ℝz,u,v\\in\\mathbb\{R\}, with ordered quantified blockst\(1\)=ut^\{\(1\)\}=uandt\(2\)=vt^\{\(2\)\}=v\. Consider the set of polynomials𝒫=\{P1,P2\}⊂ℝ⁡\[z,u,v\]\\mathcal\{P\}=\\\{P\_\{1\},P\_\{2\}\\\}\\subset\\mathbb\{R\}\[z,u,v\], whereP1​\(z,u,v\)=u2−zP\_\{1\}\(z,u,v\)=u^\{2\}\-zandP2​\(z,u,v\)=vP\_\{2\}\(z,u,v\)=v\. Then the terminal sign vectorΣ2​\(z,u,v\)\\Sigma\_\{2\}\(z,u,v\)isΣ2​\(z,u,v\)=\(sign​\(u2−z\),sign​\(v\)\)\.\\Sigma\_\{2\}\(z,u,v\)=\(\{\\text\{sign\}\}\(u^\{2\}\-z\),\{\\text\{sign\}\}\(v\)\)\.Fora∈\{−1,0,1\}a\\in\\\{\-1,0,1\\\}, we defineEa=\{\(a,−1\),\(a,0\),\(a,1\)\}E\_\{a\}=\\\{\(a,\-1\),\(a,0\),\(a,1\)\\\}, then after varying the innermost blockvv, we obtainΣ1​\(z,u\)=Esign​\(u2−z\)\\Sigma\_\{1\}\(z,u\)=E\_\{\{\\text\{sign\}\}\(u^\{2\}\-z\)\}\. After subsequently varyinguu, the nested sign profileΣ0​\(z\)\\Sigma\_\{0\}\(z\)becomes

Σ0​\(z\)=\{\{E1\},z<0,\{E0,E1\},z=0,\{E−1,E0,E1\},z\>0\.\\Sigma\_\{0\}\(z\)=\\begin\{cases\}\\\{E\_\{1\}\\\},&z<0,\\\\ \\\{E\_\{0\},E\_\{1\}\\\},&z=0,\\\\ \\\{E\_\{\-1\},E\_\{0\},E\_\{1\}\\\},&z\>0\.\\end\{cases\}Consequently,𝒬=\{z\}\\mathcal\{Q\}=\\\{z\\\}is a nested sign\-invariant projection of𝒫\\mathcal\{P\}asΣ0​\(z\)\\Sigma\_\{0\}\(z\)is constant on each of the three connected sign cells\(−∞,0\),\{0\}\(\-\\infty,0\),\\\{0\\\}, and\(0,∞\)\(0,\\infty\)induced by𝒬\\mathcal\{Q\}\.

To rigorously bound the statistical complexity of bi\-level hyperparameter tuning, we must first formalize the implicit dependency in the validation loss\. We achieve this by formulating continuous\-optimization objectives in polynomial first\-order logic \(FOL\)\.

###### Theorem 2\.2\(Nested block elimination, Adapted from[13](https://arxiv.org/html/2608.17343#bib.bib4)\)\.

FixK≥1K\\geq 1, letz∈ℝpz\\in\\mathbb\{R\}^\{p\},t\(k\)∈ℝdkt^\{\(k\)\}\\in\\mathbb\{R\}^\{d\_\{k\}\}fork=1,…,Kk=1,\\dots,K, and let𝒫⊂ℝ⁡\[z,t\(1\),…,t\(K\)\]\\mathcal\{P\}\\subset\\mathbb\{R\}\[z,t^\{\(1\)\},\\dots,t^\{\(K\)\}\]be a finite set of polynomials satisfying \(i\)\|𝒫\|≤s\|\\mathcal\{P\}\|\\leq s, and \(ii\)deg⁡\(R\)≤Δ\\deg\(R\)\\leq\\Deltafor everyR∈𝒫R\\in\\mathcal\{P\}\. Then there exists a nested sign\-invariant projection𝒬⊂ℝ⁡\[z\]\\mathcal\{Q\}\\subset\\mathbb\{R\}\[z\]of𝒫\\mathcal\{P\}, relative to the ordered blockst\(1\),…,t\(K\)t^\{\(1\)\},\\dots,t^\{\(K\)\}, such that the nested block\-sign profileΣ0​\(z\)\\Sigma\_\{0\}\(z\)is constant on everyC∈Cell​\(𝒬\)C\\in\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)\. Moreover, definingAK≜∏k=1K\(dk\+1\),BK≜∏k=1Kdk,A\_\{K\}\\triangleq\\prod\_\{k=1\}^\{K\}\(d\_\{k\}\+1\),B\_\{K\}\\triangleq\\prod\_\{k=1\}^\{K\}d\_\{k\},then there exists a constantcKc\_\{K\}, depending only onKK, such that

\|𝒬\|≤sAK​ΔcK​BK,and​maxR∈𝒬​deg⁡\(R\)≤ΔcK​BK\.\|\\mathcal\{Q\}\|\\leq s^\{A\_\{K\}\}\\Delta^\{c\_\{K\}B\_\{K\}\},\\textup\{ and \}\\max\_\{R\\in\\mathcal\{Q\}\}\\deg\(R\)\\leq\\Delta^\{c\_\{K\}B\_\{K\}\}\.

Finally, we recall a useful result that allows us to give an upper bound for the number of elements in the set of connected sign cellsCell​\(𝒬\)\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)corresponding to a set of polynomials𝒬\\mathcal\{Q\}\.

###### Lemma 2\.3\([12](https://arxiv.org/html/2608.17343#bib.bib8)\)\.

Let𝒬⊂ℝ⁡\[z\]\\mathcal\{Q\}\\subset\\mathbb\{R\}\[z\]be a set ofsspolynomials inz∈ℝpz\\in\\mathbb\{R\}^\{p\}of degree at mostΔ\\Delta, wheres,p,Δ≥1s,p,\\Delta\\geq 1\. Then there exists an universal constantCCsuch that\|Cell​\(𝒬\)\|≤\(C​s​Δp\)p\|\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)\|\\leq\\left\(\\frac\{Cs\\Delta\}\{p\}\\right\)^\{p\}ifs≥ps\\geq p, and\|Cell​\(𝒬\)\|≤\(C​Δ\)p\|\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)\|\\leq\\left\(C\\Delta\\right\)^\{p\}ifs<ps<p\.

## 3Problem Settings

z1z\_\{1\}z2z\_\{2\}f\(−1\)​\(𝒛\)f\_\{\(\-1\)\}\(\\boldsymbol\{z\}\)f\(1\)​\(𝒛\)f\_\{\(1\)\}\(\\boldsymbol\{z\}\)f\(0\)​\(𝒛\)f\_\{\(0\)\}\(\\boldsymbol\{z\}\)Figure 2:An example of a piecewise polynomial functionf⁡\(z\)f\(z\)\(Definition[7](https://arxiv.org/html/2608.17343#Thmdefinition7)\) with parabolic boundaryh1​\(z\)=z1−z22h\_\{1\}\(z\)=z\_\{1\}\-z\_\{2\}^\{2\}\. The function evaluates tof\(−1\)​\(z\)=z1f\_\{\(\-1\)\}\(z\)=z\_\{1\}in the pink region \(σ⁡\(z\)=−1\\sigma\(z\)=\-1\),f\(1\)​\(z\)=z2f\_\{\(1\)\}\(z\)=z\_\{2\}in the blue region \(σ⁡\(z\)=1\\sigma\(z\)=1\), andf\(0\)​\(z\)=z12\+z22f\_\{\(0\)\}\(z\)=z\_\{1\}^\{2\}\+z\_\{2\}^\{2\}on the black boundary \(σ⁡\(z\)=0\\sigma\(z\)=0\)\. With 1 boundary, 3 pieces, and maximum polynomial degree 2, the function’s complexity is\(1,3,2\)\(1,3,2\)\.Our data\-driven framework models hyperparameter tuning across three foundational spaces: a problem instance space𝒳⊂ℝq\\mathcal\{X\}\\subset\\mathbb\{R\}^\{q\}, a continuous hyperparameter space𝒜⊂ℝp\\mathcal\{A\}\\subset\\mathbb\{R\}^\{p\}, and a model parameter spaceΘ⊆ℝd\\Theta\\subseteq\\mathbb\{R\}^\{d\}\. To ensure analytical compactness, we restrict the parameter domains to bounding boxes, defining𝒜=\[αm​i​n,αm​a​x\]p\\mathcal\{A\}=\[\\alpha\_\{min\},\\alpha\_\{max\}\]^\{p\}andΘ=\[θm​i​n,θm​a​x\]d\\Theta=\[\\theta\_\{min\},\\theta\_\{max\}\]^\{d\}\. For any given instancex∈𝒳x\\in\\mathcal\{X\}, the learning procedure evaluates a model parameterized byθ∈Θ\\theta\\in\\Thetaalongside hyperparametersα∈𝒜\\alpha\\in\\mathcal\{A\}via two distinct objectives:

- •Training Objectivef:𝒳×𝒜×Θ→\[−H,H\]f:\\mathcal\{X\}\\times\\mathcal\{A\}\\times\\Theta\\rightarrow\[\-H,H\]: The surrogate loss directly minimized by the algorithm during training\.
- •Validation Objectiveg:𝒳×𝒜×Θ→\[−H,H\]g:\\mathcal\{X\}\\times\\mathcal\{A\}\\times\\Theta\\rightarrow\[\-H,H\]: The true target metric utilized to assess the quality of the model’s out\-of\-sample performance\.

Here,HHacts as a positive constant bounding the function values\.

##### The Bi\-level Optimization Objective\.

The ultimate performance of a hyperparameter configurationα\\alphaon a specific problem instancexxis quantified by the induced lossℓα​\(x\)\\ell\_\{\\alpha\}\(x\)\. Because hyperparameters generally dictate model behavior implicitly through the training procedure,ℓα​\(x\)\\ell\_\{\\alpha\}\(x\)is naturally cast as a bi\-level optimization problemℓα​\(x\)=infθ∈𝒮⁡\(x,α\)g⁡\(x,α,θ\)\\ell\_\{\\alpha\}\(x\)=\\inf\_\{\\theta\\in\\mathcal\{S\}\(x,\\alpha\)\}g\(x,\\alpha,\\theta\)where the set of optimal lower\-level model parameters is defined as𝒮⁡\(x,α\)=arg⁡minθ∈Θ⁡f⁡\(x,α,θ\)\\mathcal\{S\}\(x,\\alpha\)=\\arg\\min\_\{\\theta\\in\\Theta\}f\(x,\\alpha,\\theta\)\. By evaluating the infimum over the set𝒮⁡\(x,α\)\\mathcal\{S\}\(x,\\alpha\), this framework employs the standard optimistic bi\-level formulation\. This guarantees that the validation loss remains strictly well\-defined even if the inner surrogate optimization yields a non\-singleton set of minimizers\.

##### Statistical Learning Goal\.

We assume the existence of an unknown, application\-specific distribution𝒟\\mathcal\{D\}from which problem instances are drawn\. The theoretical goal of data\-driven tuning is to isolate a configurationα∗\\alpha^\{\*\}that minimizes the expected validation loss, i\.e\.,α∗∈arg⁡minα∈𝒜​𝔼x∼𝒟​\[ℓα​\(x\)\]\\alpha^\{\*\}\\in\\arg\\min\_\{\\alpha\\in\\mathcal\{A\}\}\\mathbb\{E\}\_\{x\\sim\\mathcal\{D\}\}\[\\ell\_\{\\alpha\}\(x\)\]\. Given that the true distribution𝒟\\mathcal\{D\}is unobservable, the learner is instead provided with a finite datasetS=\{x1,…,xN\}∼𝒟NS=\\\{x\_\{1\},\.\.\.,x\_\{N\}\\\}\\sim\\mathcal\{D\}^\{N\}consisting ofNNtraining instances\. The task therefore reduces to Empirical Risk Minimization \(ERM\), where the algorithm computes an empirical minimizerα^​\(S\)\\hat\{\\alpha\}\(S\), that is,α^​\(S\)∈arg⁡minα∈𝒜​1N​∑i=1Nℓα​\(xi\)\\hat\{\\alpha\}\(S\)\\in\\arg\\min\_\{\\alpha\\in\\mathcal\{A\}\}\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\ell\_\{\\alpha\}\(x\_\{i\}\)\.

##### Structural Assumptions\.

As in prior works\([3](https://arxiv.org/html/2608.17343#bib.bib5);[21](https://arxiv.org/html/2608.17343#bib.bib6)\), a central theoretical pillar of our subsequent complexity analysis requires the objective functions to exhibit specific algebraic geometries\.

###### Definition 7\(Piecewise polynomial function\([3](https://arxiv.org/html/2608.17343#bib.bib5)\)\)\.

A real\-valued functionffadmits a piecewise polynomial structure with complexity\(Mf,Tf,Δf\)\(M\_\{f\},T\_\{f\},\\Delta\_\{f\}\)if there exists a set of boundary polynomialsℍ=\{h1,…,hMf\}\\mathbb\{H\}=\\\{h\_\{1\},\\dots,h\_\{M\_\{f\}\}\\\}and a set of value polynomials𝔽=\{f𝛔\}𝛔∈Σf⊂ℝ⁡\[z\]\\mathbb\{F\}=\\\{f\_\{\\boldsymbol\{\\sigma\}\}\\\}\_\{\\boldsymbol\{\\sigma\}\\in\\Sigma\_\{f\}\}\\subset\\mathbb\{R\}\[z\], whereΣf⊆\{−1,0,1\}Mf\\Sigma\_\{f\}\\subseteq\\\{\-1,0,1\\\}^\{M\_\{f\}\}and\|Σf\|≤Tf\|\\Sigma\_\{f\}\|\\leq T\_\{f\}, both with polynomial degrees at mostΔf\\Delta\_\{f\}, such that for anyzz, we havef​\(z\)=f𝛔⁡\(z\)​\(z\)f\(z\)=f\_\{\\boldsymbol\{\\sigma\}\(z\)\}\(z\), where𝛔⁡\(z\)∈Σf\\boldsymbol\{\\sigma\}\(z\)\\in\\Sigma\_\{f\}is the sign pattern ofzzwith respect to the set of functionsℍ\\mathbb\{H\}, i\.e\.,𝛔​\(z\)j=sign​\(hj​\(z\)\)\\boldsymbol\{\\sigma\}\(z\)\_\{j\}=\{\\text\{sign\}\}\(h\_\{j\}\(z\)\)\. The functions in𝔽\\mathbb\{F\}are called the piece functions and the functions inℍ\\mathbb\{H\}are called the boundary functions\.

###### Assumption 1\(Structural assumption\([21](https://arxiv.org/html/2608.17343#bib.bib6)\)\)\.

Given any problem instancexx, the dual parameter\-dependent training objectivefx​\(α,θ\)≜f⁡\(x,α,θ\)f\_\{x\}\(\\alpha,\\theta\)\\triangleq f\(x,\\alpha,\\theta\)and dual parameter\-dependent validation objectivegx​\(α,θ\)≜g⁡\(x,α,θ\)g\_\{x\}\(\\alpha,\\theta\)\\triangleq g\(x,\\alpha,\\theta\)admits piecewise polynomial structure as functions ofα\\alphaandθ\\thetawith complexity\(Mf,Tf,Δf\)\(M\_\{f\},T\_\{f\},\\Delta\_\{f\}\)and\(Mg,Tg,Δg\)\(M\_\{g\},T\_\{g\},\\Delta\_\{g\}\)that are independent of the problem instancexx, respectively\. Moreover, the set𝒮⁡\(x,α\)\\mathcal\{S\}\(x,\\alpha\)of minimizes off\(x,α,⋅\)f\(x,\\alpha,\\cdot\)is non\-empty, for all\(x,α\)\(x,\\alpha\)\.

Although recent work has successfully extended data\-driven algorithm design to multi\-dimensional hyperparameters and bi\-level objectives\([21](https://arxiv.org/html/2608.17343#bib.bib6)\), their sample complexity guarantees are fundamentally suboptimal\. By analyzing invariant connected sign cells rather than relying on the inflated algebraic dependencies of Quantifier Elimination, we now present anested block elimination frameworkthat entirely eliminates this theoretical looseness\.

## 4A General Learning\-theoretic Complexity Framework via Block Elimination

In this section, we introduce a new general upper bound for learning\-theoretic complexity by leveraging nested block elimination\. First, we establish Proposition[4\.1](https://arxiv.org/html/2608.17343#S4.Thmtheorem1), which guarantees that the truth value of a polynomial first\-order logic formula remains invariant across the connected sign cells of a nested sign\-invariant projection\.

###### Proposition 4\.1\(Cellwise logical invariance\)\.

LetΦ⁡\(z\)=\(q1​t\(1\)∈ℝd\(1\)\)​…​\(qK​t\(K\)∈ℝd\(K\)\)​ψ​\(z,t\(1\),…,t\(K\)\)\\Phi\(z\)=\(q\_\{1\}t^\{\(1\)\}\\in\\mathbb\{R\}^\{d^\{\(1\)\}\}\)\\dots\(q\_\{K\}t^\{\(K\)\}\\in\\mathbb\{R\}^\{d^\{\(K\)\}\}\)\\psi\(z,t^\{\(1\)\},\\dots,t^\{\(K\)\}\)be a polynomial FOL, and let𝒫\\mathcal\{P\}be the family of atomic polynomials appearing in the atomic predicates ofψ\\psi\. If𝒬\\mathcal\{Q\}is a nested sign\-invariant projection of𝒫\\mathcal\{P\}relative to the ordered blockst\(1\),…,t\(K\)t^\{\(1\)\},\\dots,t^\{\(K\)\}, thenΦ\\Phihas a constant truth value on every connected sign cellC∈Cell​\(𝒬\)C\\in\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)\. In other words, for everyC∈Cell​\(𝒬\)C\\in\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)and everyz1,z2∈Cz\_\{1\},z\_\{2\}\\in C, we haveΦ⁡\(z1\)⇔Φ⁡\(z2\)\\Phi\(z\_\{1\}\)\\Leftrightarrow\\Phi\(z\_\{2\}\)\.

The proof of Proposition[4\.1](https://arxiv.org/html/2608.17343#S4.Thmtheorem1)is presented in Appendix[B](https://arxiv.org/html/2608.17343#A2)\. Using this cellwise logical invariance alongside the nested block elimination process, we now state the following theorem, which establishes a rigorous pseudo\-dimension upper bound for any function class whose threshold conditions can be formulated via branches of polynomial first\-order logic\.

###### Theorem 4\.2\(Pseudo\-dimension upper\-bound via branchwise nested block elimination\)\.

Consider a real\-valued function classℱ=\{fα:𝒳→ℝ∣α∈𝒜\}\\mathcal\{F\}=\\\{f\_\{\\alpha\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}\\mid\\alpha\\in\\mathcal\{A\}\\\}be a real\-valued function class, where𝒜=\[αmin,αmax\]p⊆ℝp\\mathcal\{A\}=\[\\alpha\_\{\\min\},\\alpha\_\{\\max\}\]^\{p\}\\subseteq\\mathbb\{R\}^\{p\}\. Suppose that there are integersL,M,K≥1L,M,K\\geq 1, whereKKis fixed, block dimensionsd1,…,dK≥1d\_\{1\},\\dots,d\_\{K\}\\geq 1, and a degree upper boundΔ≥1\\Delta\\geq 1satisfying the following conditions: for anyx∈𝒳x\\in\\mathcal\{X\}and a real\-valued thresholdτ∈ℝ\\tau\\in\\mathbb\{R\}, there exists

1. 1\.LLpolynomial FOLsΦx,τ,1​\(α\),…,Φx,τ,L​\(α\)\\Phi\_\{x,\\tau,1\}\(\\alpha\),\\dots,\\Phi\_\{x,\\tau,L\}\(\\alpha\), and
2. 2\.a Boolean functionβx,τ:\{0,1\}L→\{0,1\}\\beta\_\{x,\\tau\}:\\\{0,1\\\}^\{L\}\\rightarrow\\\{0,1\\\}

such that𝕀⁡\(fα​\(x\)≥τ\)=βx,τ​\(Φx,τ,1​\(α\),…,Φx,τ,L​\(α\)\)\\mathbb\{I\}\(f\_\{\\alpha\}\(x\)\\geq\\tau\)=\\beta\_\{x,\\tau\}\(\\Phi\_\{x,\\tau,1\}\(\\alpha\),\\dots,\\Phi\_\{x,\\tau,L\}\(\\alpha\)\)for everyα∈𝒜\\alpha\\in\\mathcal\{A\}\. Furthermore, assuming that every FOLΦx,τ,ℓ\\Phi\_\{x,\\tau,\\ell\}:

1. 1\.hasKKordered quantified variables blocks of dimensiond1,…,dKd\_\{1\},\\dots,d\_\{K\}, respectively, and
2. 2\.contains at mostMMdistinct atomic polynomials, each of degree at mostΔ\\Delta\.

DefineAK=∏k=1K\(dk\+1\)A\_\{K\}=\\prod\_\{k=1\}^\{K\}\(d\_\{k\}\+1\)andBK=∏k=1KdkB\_\{K\}=\\prod\_\{k=1\}^\{K\}d\_\{k\}, then the pseudo\-dimension of the function classℱ\\mathcal\{F\}is at most

Pdim​\(ℱ\)=𝒪⁡\(p​log⁡\(2​L\)\+p​AK​log⁡\(2​M\)\+p​BK​log⁡\(2​Δ\)\)\.\\text\{Pdim\}\(\\mathcal\{F\}\)=\\mathcal\{O\}\\left\(p\\log\(2L\)\+pA\_\{K\}\\log\(2M\)\+pB\_\{K\}\\log\(2\\Delta\)\\right\)\.

Proof Sketch\.Assume there existsNNproblem instancesx1,…,xNx\_\{1\},\\dots,x\_\{N\}that can be shattered byℱ\\mathcal\{F\}, with real\-valued thresholdsτ1,…,τN\\tau\_\{1\},\\dots,\\tau\_\{N\}witness the shattering\. LetSK=MAK​ΔcK​BKS\_\{K\}=M^\{A\_\{K\}\}\\Delta^\{c\_\{K\}B\_\{K\}\}andΔK=ΔcK​BK\\Delta\_\{K\}=\\Delta^\{c\_\{K\}B\_\{K\}\}, wherecKc\_\{K\}depends only onKKfrom Theorem[2\.2](https://arxiv.org/html/2608.17343#S2.Thmtheorem2)\.

For every instancei=1,…,Ni=1,\\dots,N, and a branchℓ=1,…,L\\ell=1,\\dots,L, let𝒫i,ℓ\\mathcal\{P\}\_\{i,\\ell\}be the set of atomic polynomials appearing inΦxi,τi,ℓ\\Phi\_\{x\_\{i\},\\tau\_\{i\},\\ell\}\. From Theorem[2\.2](https://arxiv.org/html/2608.17343#S2.Thmtheorem2), there exists a nested sign\-invariant projection𝒬i,ℓ⊂ℝ⁡\[α\]\\mathcal\{Q\}\_\{i,\\ell\}\\subset\\mathbb\{R\}\[\\alpha\]such that: \(1\)\|𝒬i,ℓ\|≤SK\|\\mathcal\{Q\}\_\{i,\\ell\}\|\\leq S\_\{K\}, and \(2\)maxR∈𝒬i,ℓ⁡deg⁡\(R\)≤DK\\max\_\{R\\in\\mathcal\{Q\}\_\{i,\\ell\}\}\\deg\(R\)\\leq D\_\{K\}\. By Proposition[4\.1](https://arxiv.org/html/2608.17343#S4.Thmtheorem1), the truth value ofΦxi,τi,ℓ\\Phi\_\{x\_\{i\},\\tau\_\{i\},\\ell\}remains unchanged on every connected sign cell induced by𝒬ℓi\\mathcal\{Q\}\_\{\\ell\_\{i\}\}\.

Now, letℬ𝒜\\mathcal\{B\}\_\{\\mathcal\{A\}\}be a family of2​p2paffine polynomials describing the region𝒜\\mathcal\{A\}, and let𝒬~=ℬ𝒜∪⋃i=1N⋃ℓ=1L𝒬i,ℓ\\tilde\{\\mathcal\{Q\}\}=\\mathcal\{B\}\_\{\\mathcal\{A\}\}\\cup\\bigcup\_\{i=1\}^\{N\}\\bigcup\_\{\\ell=1\}^\{L\}\\mathcal\{Q\}\_\{i,\\ell\}\. By definition, we have \(1\)p≤\|𝒬~\|≤N​L​SK\+2​pp\\leq\\left\|\\tilde\{\\mathcal\{Q\}\}\\right\|\\leq NLS\_\{K\}\+2p, and \(2\)maxR∈𝒬~⁡deg⁡\(R\)≤DK\\max\_\{R\\in\\tilde\{\\mathcal\{Q\}\}\}\\deg\(R\)\\leq D\_\{K\}\. Furthermore, from the previous observation about𝒬i,ℓ\\mathcal\{Q\}\_\{i,\\ell\}, we claim that over every connected sign cellC∈Cell​\(𝒬~\)C\\in\{\\textup\{Cell\}\}\(\\tilde\{\\mathcal\{Q\}\}\), the threshold label

𝕀⁡\(fα​\(x\)≥τ\)=βx,τ​\(Φx,τ,1​\(α\),…,Φx,τ,L​\(α\)\)\\mathbb\{I\}\(f\_\{\\alpha\}\(x\)\\geq\\tau\)=\\beta\_\{x,\\tau\}\(\\Phi\_\{x,\\tau,1\}\(\\alpha\),\\dots,\\Phi\_\{x,\\tau,L\}\(\\alpha\)\)remains unchanged\. Therefore, we claim that

2N≤\|Cell​\(𝒬~\)\|≤\(κ⁡\(N​L​SK\+2​p\)​DKp\)p,2^\{N\}\\leq\|\{\\textup\{Cell\}\}\(\\tilde\{\\mathcal\{Q\}\}\)\|\\leq\\left\(\\frac\{\\kappa\(NLS\_\{K\}\+2p\)D\_\{K\}\}\{p\}\\right\)^\{p\},where the latter inequality comes from Lemma[2\.3](https://arxiv.org/html/2608.17343#S2.Thmtheorem3)\. Finally, solving this inequality gives the final conclusion\. See Appendix[B](https://arxiv.org/html/2608.17343#A2)for the detailed proof\. ∎

## 5Tuning via Training Objective

In this section, we focus exclusively on the standard training\-loss setting, where the training and validation objectives are identical \(i\.e\.,f≡gf\\equiv g\)\. Under this regime, we apply our nested block elimination framework to the underlying piecewise polynomial objective to derive a sharp pseudo\-dimension upper bound in Section[5\.1](https://arxiv.org/html/2608.17343#S5.SS1), followed by a comprehensive lower bound analysis in Section[5\.2](https://arxiv.org/html/2608.17343#S5.SS2)to demonstrate tightness\.

### 5\.1Upper Bound

We first bound the generalization capacity of the hyperparameter\-induced loss function\. By formulating the inner minimization problem as a polynomial first\-order logic sentence, we can directly invoke the block elimination argument \(Theorem[2\.2](https://arxiv.org/html/2608.17343#S2.Thmtheorem2)\) to derive the following upper bound\.

###### Theorem 5\.1\(Pseudo\-dimension\)\.

Let𝒜=\[αmin,αmax\]p\\mathcal\{A\}=\[\\alpha\_\{\\min\},\\alpha\_\{\\max\}\]^\{p\}andΘ=\[θmin,θmax\]d\\Theta=\[\\theta\_\{\\min\},\\theta\_\{\\max\}\]^\{d\}be the hyperparameter and parameter domains, respectively\. Assume that for any problem instancex∈𝒳x\\in\\mathcal\{X\}, the training objectivefx​\(α,θ\)≜f⁡\(x,α,θ\)f\_\{x\}\(\\alpha,\\theta\)\\triangleq f\(x,\\alpha,\\theta\), for any\(α,θ\)∈𝒜×Θ\(\\alpha,\\theta\)\\in\\mathcal\{A\}\\times\\Theta, admits a piecewise polynomial structure with complexity\(Mf,Tf,Δf\)\(M\_\{f\},T\_\{f\},\\Delta\_\{f\}\)\. Then, the pseudo\-dimension of the function classℒ=\{ℓα:𝒳→ℝ∣α∈𝒜\}\\mathcal\{L\}=\\\{\\ell\_\{\\alpha\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}\\mid\\alpha\\in\\mathcal\{A\}\\\}, whereℓα​\(x\)=minθ∈Θ⁡f⁡\(x,α,θ\)\\ell\_\{\\alpha\}\(x\)=\\min\_\{\\theta\\in\\Theta\}f\(x,\\alpha,\\theta\), is at most

Pdim​\(ℒ\)=𝒪⁡\(p​log⁡Tf\+p​d​log⁡\(Mf\+d\)\+p​d​log⁡Δf\)\.\\text\{Pdim\}\(\\mathcal\{L\}\)=\\mathcal\{O\}\(p\\log T\_\{f\}\+pd\\log\(M\_\{f\}\+d\)\+pd\\log\\Delta\_\{f\}\)\.

Proof sketch\.For any problem instancex∈𝒳x\\in\\mathcal\{X\}and thresholdτ∈ℝ\\tau\\in\\mathbb\{R\}, our goal is to express the boolean indicator𝕀⁡\(ℓx​\(α\)≥τ\)\\mathbb\{I\}\(\\ell\_\{x\}\(\\alpha\)\\geq\\tau\)as a boolean combination of polynomial first\-order logic \(FOL\) formulas to directly invoke Theorem[2\.2](https://arxiv.org/html/2608.17343#S2.Thmtheorem2)\. Because the induced loss is defined via inner minimization,ℓx​\(α\)=minθ∈Θ⁡fx​\(α,θ\)\\ell\_\{x\}\(\\alpha\)=\\min\_\{\\theta\\in\\Theta\}f\_\{x\}\(\\alpha,\\theta\), the conditionℓx​\(α\)≥τ\\ell\_\{x\}\(\\alpha\)\\geq\\tauis logically equivalent to the universal statement\(∀θ∈Θ\)\[fx\(α,θ\)≥τ\]\(\\forall\\theta\\in\\Theta\)\[f\_\{x\}\(\\alpha,\\theta\)\\geq\\tau\]\. Exploiting the piecewise polynomial structure offxf\_\{x\}, we partition the parameter space into invariant sign regions\. LetWherex,σ\(α,θ\)≜⋀m=1Mx\[sign\(hx,m\(α,θ\)\)=σm\]\\textup\{Where\}\_\{x,\\sigma\}\(\\alpha,\\theta\)\\triangleq\\bigwedge\_\{m=1\}^\{M\_\{x\}\}\[\{\\text\{sign\}\}\(h\_\{x,m\}\(\\alpha,\\theta\)\)=\\sigma\_\{m\}\]be the predicate indicating whether\(α,θ\)\(\\alpha,\\theta\)falls into the region defined by the sign patternσ∈Σx\\sigma\\in\\Sigma\_\{x\}\. We can rewrite𝕀⁡\(ℓx​\(α\)≥τ\)\\mathbb\{I\}\(\\ell\_\{x\}\(\\alpha\)\\geq\\tau\)as a conjunction over all valid regions⋀σ∈ΣxΦx,τ,σ​\(α\)\\bigwedge\_\{\\sigma\\in\\Sigma\_\{x\}\}\\Phi\_\{x,\\tau,\\sigma\}\(\\alpha\)where

Φx,τ,σ\(α\)≜\(∀θ∈Θ\)\[Wherex,σ\(α,θ\)⇒Px,σ\(α,θ\)≥τ\]\.\\Phi\_\{x,\\tau,\\sigma\}\(\\alpha\)\\triangleq\(\\forall\\theta\\in\\Theta\)\[\\textup\{Where\}\_\{x,\\sigma\}\(\\alpha,\\theta\)\\Rightarrow P\_\{x,\\sigma\}\(\\alpha,\\theta\)\\geq\\tau\]\.By substituting the domain constraintInΘ​\(θ\)=⋀r=1d\(θmax−θr≥0\)∧\(θr−θmin≥0\)\\textup\{In\}\_\{\\Theta\}\(\\theta\)=\\bigwedge\_\{r=1\}^\{d\}\(\\theta\_\{\\max\}\-\\theta\_\{r\}\\geq 0\)\\wedge\(\\theta\_\{r\}\-\\theta\_\{\\min\}\\geq 0\)and applying the logical identity\(A⇒B\)≡\(¬A∨B\)\(A\\Rightarrow B\)\\equiv\(\\neg A\\vee B\), we transform each branch into a standard polynomial FOLΦx,τ,σ​\(α\)=\\Phi\_\{x,\\tau,\\sigma\}\(\\alpha\)=

\(∀θ∈ℝd\)\[¬InΘ\(θ\)∨¬Wherex,σ\(α,θ\)∨Px,σ\(α,θ\)≥τ\]\.\(\\forall\\theta\\in\\mathbb\{R\}^\{d\}\)\[\\neg\\textup\{In\}\_\{\\Theta\}\(\\theta\)\\vee\\neg\\textup\{Where\}\_\{x,\\sigma\}\(\\alpha,\\theta\)\\vee P\_\{x,\\sigma\}\(\\alpha,\\theta\)\\geq\\tau\]\.
Crucially, each formulaΦx,τ,σ\\Phi\_\{x,\\tau,\\sigma\}requires exactlyK=1K=1quantifier block of dimensiond1=dd\_\{1\}=d, and contains at mostMf\+2​d\+1M\_\{f\}\+2d\+1distinct atomic polynomial predicates \(accounting for the active boundary pieces, domain edges, and the threshold comparison\)\. Furthermore, the maximum degree across all atomic predicates is strictly bounded byΔf\\Delta\_\{f\}\. Substituting these uniform complexity parameters into our nested block elimination bound in Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)yields the final pseudo\-dimension\. The detailed proof can be found in Appendix[C\.1](https://arxiv.org/html/2608.17343#A3.SS1)\. ∎

### 5\.2Lower Bound

As noted above, prior work only provided an algebraic lower bound ofΩ⁡\(p​d​log⁡Δf\)\\Omega\(pd\\log\\Delta\_\{f\}\)in[21](https://arxiv.org/html/2608.17343#bib.bib6), leaving the necessity of the combinatorial parametersTfT\_\{f\}andMfM\_\{f\}anopen question\. We address this gap by introducing a multi\-regime lower bound framework\. By independently analyzing these capacities, we prove that our upper bounds are tight with respect to the number of piecesTfT\_\{f\}and nearly tight with respect to the number of boundariesMfM\_\{f\}, establishing the fundamental necessity of each structural parameter in our theoretical guarantees\. The detailed proofs of Lemmas[5\.2](https://arxiv.org/html/2608.17343#S5.Thmtheorem2)and[5\.3](https://arxiv.org/html/2608.17343#S5.Thmtheorem3)can be found in Appendix[C\.2](https://arxiv.org/html/2608.17343#A3.SS2)\.

###### Lemma 5\.2\(Lower bound depending onTfT\_\{f\}\)\.

For everyp,d≥1p,d\\geq 1and an integerTf≥4T\_\{f\}\\geq 4, there exists box like regions𝒜⊂ℝp\\mathcal\{A\}\\subset\\mathbb\{R\}^\{p\},Θ⊂ℝd\\Theta\\subset\\mathbb\{R\}^\{d\}, an instance space𝒳\\mathcal\{X\}, and a training objectivef⁡\(x,α,θ\)f\(x,\\alpha,\\theta\)that admits piecewise polynomial structure with complexity\(⌊Tf−12⌋,Tf,1\)\(\\lfloor\\frac\{T\_\{f\}\-1\}\{2\}\\rfloor,T\_\{f\},1\)such that the corresponding function classℒ\\mathcal\{L\}satisfies:Pdim​\(ℒ\)=Ω⁡\(p​log⁡Tf\)\.\\text\{Pdim\}\(\\mathcal\{L\}\)=\\Omega\\left\(p\\log T\_\{f\}\\right\)\.

###### Lemma 5\.3\(Lower bound depending onMfM\_\{f\}\)\.

For everyp,d,Mf≥1p,d,M\_\{f\}\\geq 1, there exists box\-like hyperparameter domain𝒜⊂ℝp\\mathcal\{A\}\\subset\\mathbb\{R\}^\{p\}and parameter domainΘ⊆ℝd\\Theta\\subseteq\\mathbb\{R\}^\{d\}, a finite instance space𝒳\\mathcal\{X\}, and a training objectiveffsuch that:

1. \(i\)For anyx∈𝒳x\\in\\mathcal\{X\}, the functionfx​\(α,θ\)≜f⁡\(x,α,θ\)f\_\{x\}\(\\alpha,\\theta\)\\triangleq f\(x,\\alpha,\\theta\)admits a piecewise polynomial structure with exactsMfM\_\{f\}affine boundary polynomials, at most\(1\+2​Mfd\)d\\left\(1\+\\frac\{2M\_\{f\}\}\{d\}\\right\)^\{d\}realized sign conditions, piece polynomials of degree at most22\.
2. \(ii\)The induced classℒ=\{ℓα:𝒳→ℝ∣α∈𝒜\},ℓα\(x\)=minθ∈Θf\(x,α,θ\)\\mathcal\{L\}=\\\{\\ell\_\{\\alpha\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}\\mid\\alpha\\in\\mathcal\{A\}\\\},\\ell\_\{\\alpha\}\(x\)=\\min\_\{\\theta\\in\\Theta\}f\(x,\\alpha,\\theta\)satisfiesPdim​\(ℒ\)=Ω⁡\(p​d​log⁡\(1\+Mfd\)\)\\text\{Pdim\}\(\\mathcal\{L\}\)=\\Omega\\left\(pd\\log\\left\(1\+\\frac\{M\_\{f\}\}\{d\}\\right\)\\right\)\.

## 6Tuning via Validation Objective

We now consider the general bi\-level setting in which model parameters are selected using the training objectiveff, while the hyperparameters are evaluated using a potentially different validation objectivegg\. Recall thatℓαval​\(x\)=infθ∈𝒮⁡\(x,α\)gx​\(α,θ\)\\ell\_\{\\alpha\}^\{\\text\{val\}\}\(x\)=\\inf\_\{\\theta\\in\\mathcal\{S\}\(x,\\alpha\)\}g\_\{x\}\(\\alpha,\\theta\), where𝒮⁡\(x,α\)=arg⁡minθ∈Θ​fx​\(α,θ\)\\mathcal\{S\}\(x,\\alpha\)=\\arg\\min\_\{\\theta\\in\\Theta\}f\_\{x\}\(\\alpha,\\theta\)\. Unlike the training\-loss setting of Section[5](https://arxiv.org/html/2608.17343#S5), analyzing this loss requires encoding validation performance and lower\-level optimality simultaneously\.

###### Theorem 6\.1\.

Under Assumption 1, letℒval=\{ℓαval:𝒳→\[−H,H\]∣α∈𝒜\}\\mathcal\{L\}\_\{\\text\{val\}\}=\\\{\\ell\_\{\\alpha\}^\{\\text\{val\}\}:\\mathcal\{X\}\\to\[\-H,H\]\\mid\\alpha\\in\\mathcal\{A\}\\\},Δf,g=max⁡\{1,Δf,Δg\}\\Delta\_\{f,g\}=\\max\\\{1,\\Delta\_\{f\},\\Delta\_\{g\}\\\}, andMtot=Mf\+Mg\+Tf\+dM\_\{\\textup\{tot\}\}=M\_\{f\}\+M\_\{g\}\+T\_\{f\}\+d, we have

Pdim⁡\(ℒval\)=𝒪⁡\(p​log⁡\(Tf​Tg\)\+p​d2​log⁡\(2\+Mtot​Δf,g\)\)\.\\operatorname\{Pdim\}\(\\mathcal\{L\}\_\{\\text\{val\}\}\)=\\mathcal\{O\}\\left\(p\\log\(T\_\{f\}T\_\{g\}\)\+pd^\{2\}\\log\\left\(2\+M\_\{\\textup\{tot\}\}\\Delta\_\{f,g\}\\right\)\\right\)\.

The detailed proof can be found in Appendix[D](https://arxiv.org/html/2608.17343#A4)\. Compared with prior multi\-dimensional validation bounds in[21](https://arxiv.org/html/2608.17343#bib.bib6), Theorem[6\.1](https://arxiv.org/html/2608.17343#S6.Thmtheorem1)is strictly tighter by removing one factorppfrom the degree\-dependent term and moves theTgT\_\{g\}dependence outside thed2d^\{2\}\-scaled logarithm\. See Appendix[D](https://arxiv.org/html/2608.17343#A4)for a more detailed comparison\.

## 7Applications

To demonstrate the versatility of our nested block elimination framework, we analyze the data\-driven Weighted Group Lasso\([30](https://arxiv.org/html/2608.17343#bib.bib30);[21](https://arxiv.org/html/2608.17343#bib.bib6)\)\. The training and validation objectives are formulated as:f\(x,α,θ\)=∥Aθ−b∥\+22∑i=1pαi∥θi∥2f\(x,\\alpha,\\theta\)=\\\|\{\}A\\theta\-b\\\|\{\}\_\{2\}^\{2\}\+\\sum\_\{i=1\}^\{p\}\\alpha\_\{i\}\\\|\{\}\\theta\_\{i\}\\\|\{\}\_\{2\}, andg⁡\(x,α,θ\)=12​‖A′​θ−b′‖2g\(x,\\alpha,\\theta\)=\\frac\{1\}\{2\}\\\|A^\{\\prime\}\\theta\-b^\{\\prime\}\\\|^\{2\}\. Here, the model parameterθ\\thetais partitioned intoppdistinct groupsθ=\(θ1,…,θp\)∈ℝd1×⋯×ℝdp\\theta=\(\\theta\_\{1\},\\dots,\\theta\_\{p\}\)\\in\\mathbb\{R\}^\{d\_\{1\}\}\\times\\dots\\times\\mathbb\{R\}^\{d\_\{p\}\}where∑i=1pdi=d\\sum\_\{i=1\}^\{p\}d\_\{i\}=d, and the hyperparameterα∈ℝp\\alpha\\in\\mathbb\{R\}^\{p\}controls the penalty weight for each group\. Using our proposed framework, we have the following results\.

###### Theorem 7\.1\.

Consider the class of validation loss functionsℒval=\{ℓαval:𝒳→\[−H,H\]∣α∈𝒜\}\\mathcal\{L\}\_\{\\text\{val\}\}=\\\{\\ell\_\{\\alpha\}^\{\\text\{val\}\}:\\mathcal\{X\}\\to\[\-H,H\]\\mid\\alpha\\in\\mathcal\{A\}\\\}induced by the Weighted Group Lasso objectives\. The pseudo\-dimension is bounded byPdim⁡\(ℒval\)=𝒪⁡\(p​\(d\+p\)2​log⁡p\)\\operatorname\{Pdim\}\(\\mathcal\{L\}\_\{\\text\{val\}\}\)=\\mathcal\{O\}\(p\(d\+p\)^\{2\}\\log p\)\.

The proof directly leverages our nested block elimination framework in Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)by introducing auxiliary variables to encode the semi\-algebraicL2L\_\{2\}norm as purely polynomial constraints\. Prior work utilizing standard quantifier elimination yielded a looser upper bound of𝒪⁡\(p3​d\+p2​d2\)\\mathcal\{O\}\(p^\{3\}d\+p^\{2\}d^\{2\}\)in[21](https://arxiv.org/html/2608.17343#bib.bib6)\. By preserving invariant connected sign cells during block elimination, Theorem[7\.1](https://arxiv.org/html/2608.17343#S7.Thmtheorem1)removes a full factor ofppfrom the dominant algebraic term, providing a strictly sharper generalization guarantee\. See Appendix[E\.1](https://arxiv.org/html/2608.17343#A5.SS1)for further discussions on the improvement as well as the detailed proof\. We also provided other applications to showcase the applicability of our general frameworks, which can be found in Appendix[E\.2](https://arxiv.org/html/2608.17343#A5.SS2)\.

## 8Conclusion and Future Work

In this paper, we studied the statistical complexity of multi\-dimensional data\-driven hyperparameter tuning for bi\-level optimization\. By replacing standard quantifier elimination with a nested block elimination framework based on invariant connected sign cells, we bypassed topological over\-counting to derive strictly tighter pseudo\-dimension bounds\. For the training\-loss setting, our novel multi\-regime lower bounds proved that these upper bounds are tightly saturated with respect to both combinatorial and algebraic capacities\. We further extended this framework to general validation\-loss tuning and to broader semi\-algebraic structures, such as the Weighted Group Lasso, thereby eliminating the inflated algebraic dependencies of prior work\. While our lower bounds confirm the tightness of our guarantees in the training\-loss setting \(f≡gf\\equiv g\), determining the fundamental minimax lower bounds for the general bi\-level validation\-loss setting \(f≢gf\\not\\equiv g\) remains a compelling open problem for future research\.

## References

- a Ilemobayoet al\.\(2024\)J\. a Ilemobayo, O\. Durodola, O\. Alade, O\. J Awotunde, A\. T Olanrewaju, O\. Falana, A\. Ogungbire, A\. Osinuga, D\. Ogunbiyi, A\. Ifeanyi,et al\.Hyperparameter tuning in machine learning: a comprehensive review\.Journal of Engineering Research and Reports26\(6\),pp\. 388–395\.Cited by:[§1](https://arxiv.org/html/2608.17343#S1.p1.1)\.
- Balcanet al\.\(2025a\)M\. F\. Balcan, A\. T\. Nguyen, and D\. SharmaAlgorithm configuration for structured pfaffian settings\.Transactions on Machine Learning Research\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px2.p1.1)\.
- Balcanet al\.\(2025b\)M\. F\. Balcan, A\. T\. Nguyen, and D\. SharmaSample complexity of data\-driven tuning of model hyperparameters in neural networks with structured parameter\-dependent dual function\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.17343#S1.p5.1),[§3](https://arxiv.org/html/2608.17343#S3.SS0.SSS0.Px3.p1.1),[Definition 7](https://arxiv.org/html/2608.17343#Thmdefinition7),[Remark 1](https://arxiv.org/html/2608.17343#Thmremark1.p1.1.1)\.
- Balcanet al\.\(2022a\)M\. F\. Balcan, S\. Prasad, T\. Sandholm, and E\. VitercikStructural analysis of branch\-and\-cut and the learnability of Gomory mixed integer cuts\.Advances in Neural Information Processing Systems\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1)\.
- Balcanet al\.\(2021\)M\. Balcan, D\. DeBlasio, T\. Dick, C\. Kingsford, T\. Sandholm, and E\. VitercikHow much data is sufficient to learn high\-performing algorithms? generalization guarantees for data\-driven algorithm design\.InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing,pp\. 919–932\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.17343#S1.p4.1),[Remark 1](https://arxiv.org/html/2608.17343#Thmremark1.p1.1.1)\.
- Balcanet al\.\(2022b\)M\. F\. Balcan, M\. Khodak, D\. Sharma, and A\. TalwalkarProvably tuning the elasticnet across instances\.Advances in Neural Information Processing Systems35,pp\. 27769–27782\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1)\.
- Balcanet al\.\(2023\)M\. F\. Balcan, A\. Nguyen, and D\. SharmaNew bounds for hyperparameter tuning of regression problems across instances\.Advances in Neural Information Processing Systems36,pp\. 80066–80078\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.17343#S1.p4.1),[Remark 1](https://arxiv.org/html/2608.17343#Thmremark1.p1.1.1)\.
- Balcan \(2020\)M\. BalcanData\-driven algorithm design\.arXiv preprint arXiv:2011\.07177\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.17343#S1.p3.1)\.
- Bartlettet al\.\(2022\)P\. Bartlett, P\. Indyk, and T\. WagnerGeneralization bounds for data\-driven numerical linear algebra\.InConference on Learning Theory,pp\. 2013–2040\.Cited by:[§A\.1](https://arxiv.org/html/2608.17343#A1.SS1.p1.1),[Theorem A\.1](https://arxiv.org/html/2608.17343#A1.Thmtheorem1),[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.17343#S1.p5.1),[Definition 8](https://arxiv.org/html/2608.17343#Thmdefinition8),[Definition 9](https://arxiv.org/html/2608.17343#Thmdefinition9)\.
- Bartlettet al\.\(2019\)P\. L\. Bartlett, N\. Harvey, C\. Liaw, and A\. MehrabianNearly\-tight VC\-dimension and pseudodimension bounds for piecewise linear neural networks\.Journal of Machine Learning Research20\(63\),pp\. 1–17\.Cited by:[§1](https://arxiv.org/html/2608.17343#S1.p4.1),[Remark 1](https://arxiv.org/html/2608.17343#Thmremark1.p1.1.1)\.
- Bartlettet al\.\(1998\)P\. Bartlett, V\. Maiorov, and R\. MeirAlmost linear VC dimension bounds for piecewise polynomial networks\.Advances in Neural Information Processing Systems11\.Cited by:[§1](https://arxiv.org/html/2608.17343#S1.p4.1),[Remark 1](https://arxiv.org/html/2608.17343#Thmremark1.p1.1.1)\.
- Basuet al\.\(2005\)S\. Basu, R\. Pollack, and M\. RoyOn the Betti numbers of sign conditions\.Proceedings of the American Mathematical Society133\(4\),pp\. 965–974\.Cited by:[Lemma 2\.3](https://arxiv.org/html/2608.17343#S2.Thmtheorem3)\.
- Basuet al\.\(2006\)S\. Basu, R\. Pollack, and M\. RoyAlgorithms in real algebraic geometry\.Springer\.Cited by:[§1](https://arxiv.org/html/2608.17343#S1.p5.1),[Theorem 2\.2](https://arxiv.org/html/2608.17343#S2.Thmtheorem2),[Definition 10](https://arxiv.org/html/2608.17343#Thmdefinition10)\.
- Bergstraet al\.\(2011\)J\. Bergstra, R\. Bardenet, Y\. Bengio, and B\. KéglAlgorithms for hyper\-parameter optimization\.Advances in Neural Information Processing Systems24\.Cited by:[§1](https://arxiv.org/html/2608.17343#S1.p2.1)\.
- Cheng and Basu \(2026\)H\. Cheng and A\. BasuGeneralization guarantees for learning score\-based branch\-and\-cut policies in integer programming\.Advances in Neural Information Processing Systems38,pp\. 118669–118699\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1)\.
- Goldberg and Jerrum \(1993\)P\. Goldberg and M\. JerrumBounding the Vapnik\-Chervonenkis dimension of concept classes parameterized by real numbers\.InProceedings of the Sixth Annual Conference on Computational Learning Theory,pp\. 361–369\.Cited by:[§A\.1](https://arxiv.org/html/2608.17343#A1.SS1.p1.1)\.
- Gupta and Roughgarden \(2020\)R\. Gupta and T\. RoughgardenData\-driven algorithm design\.Communications of the ACM63\(6\),pp\. 87–94\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.17343#S1.p3.1)\.
- Hazanet al\.\(2018\)E\. Hazan, A\. Klivans, and Y\. YuanHyperparameter optimization: a spectral approach\.ICLR\.Cited by:[§1](https://arxiv.org/html/2608.17343#S1.p2.1)\.
- Indyket al\.\(2019\)P\. Indyk, A\. Vakilian, and Y\. YuanLearning\-based low\-rank approximations\.Advances in Neural Information Processing Systems32\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1)\.
- Leet al\.\(2026a\)T\. Q\. Le, A\. T\. Nguyen, and V\. A\. NguyenProvably data\-driven lagrangian relaxation for mixed integer linear programming\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=OwLuqetJuB)Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1)\.
- Leet al\.\(2026b\)T\. Q\. Le, A\. T\. Nguyen, and V\. A\. NguyenProvably data\-driven multiple hyper\-parameter tuning with structured loss function\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=JnuwpwbZ8D)Cited by:[Appendix D](https://arxiv.org/html/2608.17343#A4.p1.1),[1st item](https://arxiv.org/html/2608.17343#S1.I1.i1.p1.1),[2nd item](https://arxiv.org/html/2608.17343#S1.I1.i2.p1.1),[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.17343#S1.p5.1),[§1](https://arxiv.org/html/2608.17343#S1.p8.1),[§3](https://arxiv.org/html/2608.17343#S3.SS0.SSS0.Px3.p1.1),[§3](https://arxiv.org/html/2608.17343#S3.SS0.SSS0.Px3.p2.1),[§5\.2](https://arxiv.org/html/2608.17343#S5.SS2.p1.1),[§6](https://arxiv.org/html/2608.17343#S6.p2.1),[§7](https://arxiv.org/html/2608.17343#S7.p1.1),[§7](https://arxiv.org/html/2608.17343#S7.p2.1),[Assumption 1](https://arxiv.org/html/2608.17343#Thmassumption1),[Remark 1](https://arxiv.org/html/2608.17343#Thmremark1.p1.1.1),[Remark 2](https://arxiv.org/html/2608.17343#Thmremark2.p1.1.1),[Remark 3](https://arxiv.org/html/2608.17343#Thmremark3.p1.1.1),[Remark 4](https://arxiv.org/html/2608.17343#Thmremark4.p1.1.1),[Remark 5](https://arxiv.org/html/2608.17343#Thmremark5.p1.1.1),[Remark 6](https://arxiv.org/html/2608.17343#Thmremark6.p1.1.1)\.
- Liet al\.\(2017\)L\. Li, K\. Jamieson, G\. DeSalvo, A\. Rostamizadeh, and A\. TalwalkarHyperband: a novel bandit\-based approach to hyperparameter optimization\.Journal of Machine Learning Research18\(1\),pp\. 6765–6816\.Cited by:[§1](https://arxiv.org/html/2608.17343#S1.p2.1)\.
- Liet al\.\(2023\)Y\. Li, H\. Lin, S\. Liu, A\. Vakilian, and D\. P\. WoodruffLearning the positions in countsketch\.arXiv preprint arXiv:2306\.06611\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1)\.
- Montúfaret al\.\(2014\)G\. Montúfar, R\. Pascanu, K\. Cho, and Y\. BengioOn the number of linear regions of deep neural networks\.Advances in Neural Information Processing Systems27\.Cited by:[§1](https://arxiv.org/html/2608.17343#S1.p4.1),[Remark 1](https://arxiv.org/html/2608.17343#Thmremark1.p1.1.1)\.
- Nguyen and Nguyen \(2026\)A\. T\. Nguyen and V\. A\. NguyenProvably data\-driven projection method for quadratic programming\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 24541–24548\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.17343#S1.p4.1),[Remark 1](https://arxiv.org/html/2608.17343#Thmremark1.p1.1.1)\.
- Pollard \(1984\)D\. PollardConvergence of stochastic processes\.Springer New York\.Cited by:[Theorem 2\.1](https://arxiv.org/html/2608.17343#S2.Thmtheorem1),[Definition 1](https://arxiv.org/html/2608.17343#Thmdefinition1)\.
- Probstet al\.\(2018\)P\. Probst, B\. Bischl, and A\. BoulesteixTunability: importance of hyperparameters of machine learning algorithms\.arXiv preprint arXiv:1802\.09596\.Cited by:[§1](https://arxiv.org/html/2608.17343#S1.p1.1)\.
- Renegar \(1992\)J\. RenegarOn the computational complexity and geometry of the first\-order theory of the reals\. part i: introduction\. preliminaries\. the geometry of semi\-algebraic sets\. the decision problem for the existential theory of the reals\.Journal of Symbolic Computation13\(3\),pp\. 255–299\.Cited by:[Definition 2](https://arxiv.org/html/2608.17343#Thmdefinition2)\.
- Sakaue and Oki \(2024\)S\. Sakaue and T\. OkiGeneralization bound and learning methods for data\-driven projections in linear programming\.Advances in Neural Information Processing Systems37,pp\. 12825–12846\.Cited by:[§1\.1](https://arxiv.org/html/2608.17343#S1.SS1.SSS0.Px1.p1.1)\.
- Yuan and Lin \(2006\)M\. Yuan and Y\. LinModel selection and estimation in regression with grouped variables\.Journal of the Royal Statistical Society Series B68,pp\. 49–67\.Cited by:[§7](https://arxiv.org/html/2608.17343#S7.p1.1)\.

## Appendix AAdditional Definitions and Results

### A\.1The Goldberg\-Jerrum framework

The Goldberg\-Jerrum \(GJ\) framework was introduced by[16](https://arxiv.org/html/2608.17343#bib.bib29)and subsequently refined by[9](https://arxiv.org/html/2608.17343#bib.bib2)\. It provides a systematic mechanism to bound the pseudo\-dimension of parameterized function classes\. Specifically, it applies to any function classℒ\\mathcal\{L\}where the evaluation of a functionℓα\\ell\_\{\\alpha\}can be modeled as aGJ algorithm\. Such algorithms are restricted to elementary arithmetic operations \(\+,−,×,÷\+,\-,\\times,\\div\) and conditional branching, producing intermediate values that naturally take the form of rational functions of the input parameterα\\alpha\. We formally define this computational model below:

###### Definition 8\(GJ algorithm,\([9](https://arxiv.org/html/2608.17343#bib.bib2)\)\)\.

A GJ algorithmΓ\\Gammaoperates on real\-valued inputs and is restricted to two types of operations:

- •Arithmetic assignments of the formv′′=v⊙v′v^\{\\prime\\prime\}=v\\odot v^\{\\prime\}, where⊙∈\{\+,−,×,÷\}\\odot\\in\\\{\+,\-,\\times,\\div\\\}, and
- •Conditional branching of the form “ifv≥0​…v\\geq 0\\ldotselse…\\ldots"\.

In both instances, the operandsvvandv′v^\{\\prime\}must either be external inputs or intermediate values previously generated by the algorithm\.

Because the intermediate variablesv,v′,v′′v,v^\{\\prime\},v^\{\\prime\\prime\}are generated solely through sequential arithmetic operations on the inputα\\alpha, they inherently manifest as rational functions\. The complexity of a given GJ algorithm is entirely characterized by the algebraic properties of these intermediate rational functions, formally captured by two metrics:degreeandpredicate complexity\.

###### Definition 9\(Complexities of GJ algorithm,\([9](https://arxiv.org/html/2608.17343#bib.bib2)\)\)\.

The degree of a GJ algorithm is the maximum degree of any rational function it computes based on its inputs\. The predicate complexity is defined as the total number of distinct rational functions evaluated within its conditional statements\. For a rational functionf⁡\(α\)=g⁡\(α\)h⁡\(α\)f\(\\alpha\)=\\frac\{g\(\\alpha\)\}\{h\(\\alpha\)\}, whereggandhhare polynomials inα\\alpha, its degree is given bydeg⁡\(f\)=max⁡\{deg⁡\(g\),deg⁡\(h\)\}\\deg\(f\)=\\max\\\{\\deg\(g\),\\deg\(h\)\\\}\.

When the evaluation of every function in a parameterized classℒ\\mathcal\{L\}can be executed by a GJ algorithm with bounded algebraic and predicate complexities, we can invoke the following foundational theorem to explicitly bound its pseudo\-dimension\.

###### Theorem A\.1\([9](https://arxiv.org/html/2608.17343#bib.bib2)\)\.

Suppose that each functionℓα∈ℒ\\ell\_\{\\alpha\}\\in\\mathcal\{L\}is specified byppreal parametersα∈ℝp\\alpha\\in\\mathbb\{R\}^\{p\}\. Suppose further that for every problem instancex∈𝒳x\\in\\mathcal\{X\}and real\-valued thresholdt∈ℝt\\in\\mathbb\{R\}, there exists a GJ algorithmΓx,t\\Gamma\_\{x,t\}that takesα\\alphaas input and returns true” ifℓα​\(x\)≥t\\ell\_\{\\alpha\}\(x\)\\geq tand false” otherwise\. IfΓx,t\\Gamma\_\{x,t\}exhibits a maximum degree ofΔ\\Deltaand a predicate complexity ofΛ\\Lambda, thenPdim​\(ℒ\)=𝒪⁡\(p​log⁡\(Δ​Λ\)\)\\text\{Pdim\}\(\\mathcal\{L\}\)=\\mathcal\{O\}\(p\\log\(\\Delta\\Lambda\)\)\.

In the next section, we will discuss in depth the idea in prior works, its limitation, and how we overcome this with the new block elimination argument\.

### A\.2A detailed discussion on the technical difference compared to prior works

##### Technique in prior works and its limitation\.

In prior work, the standard approach to bounding the pseudo\-dimension relies on a rigid two\-step pipeline\. First, the bi\-level optimization objective is formulated as a polynomial First\-Order Logic \(FOL\) statement, and a standard Quantifier Elimination \(QE\) algorithm is applied to convert it into a quantifier\-free FOL\. Second, the authors apply an off\-the\-shelf result—the Goldberg\-Jerrum \(GJ\) framework—which treats this quantifier\-free formula as a computational algorithm to derive the final pseudo\-dimension bounds\. However, the fundamental problem with this approach is that explicit QE is an exceptionally costly, worst\-case algebraic procedure\. To eliminate quantifiers, the algorithm forces the construction of a massive number of intermediate, redundant polynomial structures to algebraically separate every conceivable outcome\. Because the off\-the\-shelf GJ framework blindly accounts for the quantities and degrees of all these newly generated, bloated polynomials, the resulting pseudo\-dimension bounds suffer from severe algebraic inflation \(such as the suboptimalp2p^\{2\}dependency\)\.

##### Our proposed technique, the difference, and how it resolves the limitation\.

In contrast, our proposed technique takes a more fundamental route\. We recognize that the ultimate goal of bounding the pseudo\-dimension does not actually require evaluating an explicit logic formula; it strictly requires bounding the total number of distinct sign patterns \(the shattering coefficient\) that the thresholded loss functions can realize across a dataset\. Instead of algebraic manipulation, we use a geometric strategy based on nested block elimination to track how logical truth values remain invariant across topologically connected sign cells\. By doing so, we completely bypass the need to ever construct the final quantifier\-free FOL\. Because we do not explicitly generate the redundant polynomial structures required by standard QE, we do not incur their associated complexity blowups\. We simply bound the number of invariant sign regions directly, achieving the same ultimate goal—bounding the sign patterns—but doing so with drastically improved, tightly saturated pseudo\-dimension bounds\.

### A\.3Additional Definitions

In this section, we will formally define the notion ofcells\(or connected components\)\.

###### Definition 10\(Connectedness and connected sign cells\([13](https://arxiv.org/html/2608.17343#bib.bib4)\)\)\.

LetS⊆ℝdS\\subseteq\\mathbb\{R\}^\{d\}be a subset ofℝd\\mathbb\{R\}^\{d\}\. A subsetU⊆SU\\subseteq Sis called open relative toSSif there exists an open setO⊆ℝdO\\subseteq\\mathbb\{R\}^\{d\}such thatU=S∩OU=S\\cap O\. The setSSis called connected if there does not exist two non\-empty, disjoint subsetsU,VU,V, both open relative toSS, such thatS=U∪VS=U\\cup V\. A connected componentCCofSSis a maximal connected subset ofSS, that is \(i\)CCis connected, and \(ii\) there is no connected setC′C^\{\\prime\}such thatC⊊C′⊆SC\\subsetneq C^\{\\prime\}\\subseteq S\.

### A\.4Supporting Lemmas

The following inequality is a well\-known and frequently used result in the learning theory literature\. For completeness, we present its formal statement and detailed proof below\.

###### Proposition A\.2\.

For anyt≥0t\\geq 0andA≥2A\\geq 2, if2t≤c⁡\(t\+2\)​A2^\{t\}\\leq c\(t\+2\)Afor a constantc≥1c\\geq 1, thent=𝒪⁡\(log⁡A\)t=\\mathcal\{O\}\(\\log A\)\.

###### Proof\.

For convenience, we writex=t2x=\\frac\{t\}\{2\}for anyt≥0t\\geq 0\. Note thatx≤2xx\\leq 2^\{x\}for allx≥0x\\geq 0, we have

t\+2=2​\(x\+1\)≤2​\(2x\+2x\)=4⋅2t/2\.t\+2=2\(x\+1\)\\leq 2\(2^\{x\}\+2^\{x\}\)=4\\cdot 2^\{t/2\}\.From the assumption, we have2t≤c⁡\(t\+2\)​A2^\{t\}\\leq c\(t\+2\)A\. Combining with the above, we have

2t≤4​c​A​2t/2⇒2t/2≤4​A​c⇒t≤2​log2⁡\(4​c​A\)\.2^\{t\}\\leq 4cA2^\{t/2\}\\Rightarrow 2^\{t/2\}\\leq 4Ac\\Rightarrow t\\leq 2\\log\_\{2\}\(4cA\)\.SinceA≥2A\\geq 2, we have

log2⁡\(4​A​c\)=log2⁡A\+log2⁡\(4​c\)=𝒪⁡\(log⁡A\)\.\\log\_\{2\}\(4Ac\)=\\log\_\{2\}A\+\\log\_\{2\}\(4c\)=\\mathcal\{O\}\(\\log A\)\.From the above, we have the final conclusion\. ∎

## Appendix BAdditional Results and Omitted Proofs for Section[4](https://arxiv.org/html/2608.17343#S4)

###### Proposition[4\.1](https://arxiv.org/html/2608.17343#S4.Thmtheorem1)\(restated\)\.

LetΦ⁡\(z\)=\(q1​t\(1\)∈ℝd\(1\)\)​…​\(qK​t\(K\)∈ℝd\(K\)\)​ψ​\(z,t\(1\),…,t\(K\)\)\\Phi\(z\)=\(q\_\{1\}t^\{\(1\)\}\\in\\mathbb\{R\}^\{d^\{\(1\)\}\}\)\\dots\(q\_\{K\}t^\{\(K\)\}\\in\\mathbb\{R\}^\{d^\{\(K\)\}\}\)\\psi\(z,t^\{\(1\)\},\\dots,t^\{\(K\)\}\)be a polynomial FOL, and let𝒫\\mathcal\{P\}be the family of atomic polynomials appearing in the atomic predicates ofψ\\psi\. If𝒬\\mathcal\{Q\}is a nested sign\-invariant projection of𝒫\\mathcal\{P\}relative to the ordered blockst\(1\),…,t\(K\)t^\{\(1\)\},\\dots,t^\{\(K\)\}, thenΦ\\Phihas a constant truth value on every connected sign cellC∈Cell​\(𝒬\)C\\in\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)\. In other words, for everyC∈Cell​\(𝒬\)C\\in\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)and everyz1,z2∈Cz\_\{1\},z\_\{2\}\\in C, we haveΦ⁡\(z1\)⇔Φ⁡\(z2\)\\Phi\(z\_\{1\}\)\\Leftrightarrow\\Phi\(z\_\{2\}\)\.

###### Proof\.

For every sign conditionη=\(η1,…,ηs\)∈\{−1,0,1\}s\\eta=\(\\eta\_\{1\},\\dots,\\eta\_\{s\}\)\\in\\\{\-1,0,1\\\}^\{s\}LetEK​\(η\)E\_\{K\}\(\\eta\)be the truth value obtained by evaluating every atomic predicatePi​χi​0P\_\{i\}\\chi\_\{i\}0using the polynomial signηi\\eta\_\{i\}\. LetΣK,ΣK−1,…,Σ0\\Sigma\_\{K\},\\Sigma\_\{K\-1\},\\dots,\\Sigma\_\{0\}be the nested block\-sign profiles of𝒫\\mathcal\{P\}\(as in Definition[5](https://arxiv.org/html/2608.17343#Thmdefinition5)\)\. Recursively, fork=K,K−1,…,1k=K,K\-1,\\dots,1, and every possible valueSSof the nested profileΣk−1\\Sigma\_\{k\-1\}, we define

Ek−1​\(S\)=\{⋁ξ∈SEk\(ξ\),qk=∃,⋀ξ∈SEk\(ξ\),qk=∀\.E\_\{k\-1\}\(S\)=\\begin\{cases\}\\bigvee\_\{\\xi\\in S\}E\_\{k\}\(\\xi\),q\_\{k\}=\\exists,\\\\ \\bigwedge\_\{\\xi\\in S\}E\_\{k\}\(\\xi\),q\_\{k\}=\\forall\.\\end\{cases\}Indeed,Σk−1\\Sigma\_\{k\-1\}records all the values ofΣk\\Sigma\_\{k\}obtained by varyingt\(k\)t^\{\(k\)\}\. Therefore, an existential quantifier \(e\.g,∃\\exists\) takes the logical OR over the these values, whereas a universal quantifier \(e\.g\.,∀\\forall\) takes the logical AND\. Applying this argument recursively from the innermost blockt\(K\)t^\{\(K\)\}to the outermost blockt\(1\)t^\{\(1\)\}, the truth value ofΦ⁡\(z\)\\Phi\(z\)isE0​\(Σ0​\(z\)\)E\_\{0\}\(\\Sigma\_\{0\}\(z\)\)\. Since𝒬\\mathcal\{Q\}is a nested sign invariant projection, by Definition[6](https://arxiv.org/html/2608.17343#Thmdefinition6), we haveΣ0​\(z1\)=Σ0​\(z2\)\\Sigma\_\{0\}\(z\_\{1\}\)=\\Sigma\_\{0\}\(z\_\{2\}\), wheneverz1,z2z\_\{1\},z\_\{2\}belong to the sameC∈Cell​\(𝒬\)C\\in\{\\textup\{Cell\}\}\(\\mathcal\{Q\}\)\. ThereforeE0​\(Σ0​\(z1\)\)=E0​\(Σ0​\(z2\)\)E\_\{0\}\(\\Sigma\_\{0\}\(z\_\{1\}\)\)=E\_\{0\}\(\\Sigma\_\{0\}\(z\_\{2\}\)\), meaning that the truth value ofΦ⁡\(z1\)\\Phi\(z\_\{1\}\)andΦ⁡\(z2\)\\Phi\(z\_\{2\}\)is identical\. ∎

###### Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)\(restated\)\.

Consider a real\-valued function classℱ=\{fα:𝒳→ℝ∣α∈𝒜\}\\mathcal\{F\}=\\\{f\_\{\\alpha\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}\\mid\\alpha\\in\\mathcal\{A\}\\\}be a real\-valued function class, where𝒜=\[αmin,αmax\]p⊆ℝp\\mathcal\{A\}=\[\\alpha\_\{\\min\},\\alpha\_\{\\max\}\]^\{p\}\\subseteq\\mathbb\{R\}^\{p\}\. Suppose that there are integersL,M,K≥1L,M,K\\geq 1, whereKKis fixed, block dimensionsd1,…,dK≥1d\_\{1\},\\dots,d\_\{K\}\\geq 1, and a degree upper boundΔ≥1\\Delta\\geq 1satisfying the following conditions: for anyx∈𝒳x\\in\\mathcal\{X\}and and real\-valued thresholdτ∈ℝ\\tau\\in\\mathbb\{R\}, there exists

1. 1\.LLpolynomial FOLsΦx,τ,1​\(α\),…,Φx,τ,L​\(α\)\\Phi\_\{x,\\tau,1\}\(\\alpha\),\\dots,\\Phi\_\{x,\\tau,L\}\(\\alpha\), and
2. 2\.a Boolean functionβx,τ:\{0,1\}L→\{0,1\}\\beta\_\{x,\\tau\}:\\\{0,1\\\}^\{L\}\\rightarrow\\\{0,1\\\}

such that𝕀⁡\(fα​\(x\)≥τ\)=βx,τ​\(Φx,τ,1​\(α\),…,Φx,τ,L​\(α\)\)\\mathbb\{I\}\(f\_\{\\alpha\}\(x\)\\geq\\tau\)=\\beta\_\{x,\\tau\}\(\\Phi\_\{x,\\tau,1\}\(\\alpha\),\\dots,\\Phi\_\{x,\\tau,L\}\(\\alpha\)\)for everyα∈𝒜\\alpha\\in\\mathcal\{A\}\. Furthermore, assuming that every FOLΦx,τ,ℓ\\Phi\_\{x,\\tau,\\ell\}:

1. 1\.hasKKordered quantified variables blocks of dimensiond1,…,dKd\_\{1\},\\dots,d\_\{K\}, respectively, and
2. 2\.contains at mostMMdistinct atomic polynomials, each of degree at mostΔ\\Delta\.

DefineAK=∏k=1K\(dk\+1\)A\_\{K\}=\\prod\_\{k=1\}^\{K\}\(d\_\{k\}\+1\)andBK=∏k=1KdkB\_\{K\}=\\prod\_\{k=1\}^\{K\}d\_\{k\}, then the pseudo\-dimension of the function classℱ\\mathcal\{F\}is at most

Pdim​\(ℱ\)=𝒪⁡\(p​log⁡\(2​L\)\+p​AK​log⁡\(2​M\)\+p​BK​log⁡\(2​Δ\)\)\.\\text\{Pdim\}\(\\mathcal\{F\}\)=\\mathcal\{O\}\\left\(p\\log\(2L\)\+pA\_\{K\}\\log\(2M\)\+pB\_\{K\}\\log\(2\\Delta\)\\right\)\.

###### Proof\.

By the definition of pseudo\-dimensionPdim​\(ℱ\)\\text\{Pdim\}\(\\mathcal\{F\}\), our goal is to bound the maximum sizeNNof a set of problem instancesS=\{x1,…,xN\}S=\\\{x\_\{1\},\\dots,x\_\{N\}\\\}thatℱ\\mathcal\{F\}can shattered and with real\-valued thresholdsτ=\(τ1,…,τN\)⊂ℝ\\tau=\(\\tau\_\{1\},\\dots,\\tau\_\{N\}\)\\subset\\mathbb\{R\}witness the shattering, that is, the binary vectors

v⁡\(\(S,τ\),fα\)=\(𝕀⁡\(fα​\(x1\)≥τ1\),…,𝕀⁡\(fα​\(xN\)≥τN\)\)v\(\(S,\\tau\),f\_\{\\alpha\}\)=\(\\mathbb\{I\}\(f\_\{\\alpha\}\(x\_\{1\}\)\\geq\\tau\_\{1\}\),\\dots,\\mathbb\{I\}\(f\_\{\\alpha\}\(x\_\{N\}\)\\geq\\tau\_\{N\}\)\)admits all possible sign vectors\{0,1\}N\\\{0,1\\\}^\{N\}when varyingα∈𝒜\\alpha\\in\\mathcal\{A\}\. This can be achieved by giving an upper bound for theshattering coefficient𝒩⁡\(ℱ,N\)\\mathcal\{N\}\(\\mathcal\{F\},N\)of the function classℱ\\mathcal\{F\}with respect toNN, representing the maximum number of possible sign patterns\{v⁡\(S,fα\)∣α∈𝒜\}\\\{v\(S,f\_\{\\alpha\}\)\\mid\\alpha\\in\\mathcal\{A\}\\\}for anyS∈𝒳NS\\in\\mathcal\{X\}^\{N\}andτ∈ℝN\\tau\\in\\mathbb\{R\}^\{N\}, and then solving for the maximumNNthat satisfies the inequality2N≤𝒩⁡\(ℱ,N\)2^\{N\}\\leq\\mathcal\{N\}\(\\mathcal\{F\},N\)\. We will proceed in the following steps\.

Step 1: Branch elimination\.For everyi=1,…,Ni=1,\\dots,Nandℓ=1,…,L\\ell=1,\\dots,L, let𝒫i,ℓ\\mathcal\{P\}\_\{i,\\ell\}be the set of distinct atomic polynomials appearing inΦxi,τi,ℓ​\(α\)\\Phi\_\{x\_\{i\},\\tau\_\{i\},\\ell\}\(\\alpha\)\. From assumption, we have: \(1\)\|𝒫i,ℓ\|≤M\|\\mathcal\{P\}\_\{i,\\ell\}\|\\leq M, and \(2\)maxR∈𝒫i,ℓ⁡deg⁡\(R\)≤Δ\\max\_\{R\\in\\mathcal\{P\}\_\{i,\\ell\}\}\\deg\(R\)\\leq\\Delta\. LetcKc\_\{K\}be the constant appearing in Theorem[2\.2](https://arxiv.org/html/2608.17343#S2.Thmtheorem2), and defineSK=MAK​ΔcK​BKS\_\{K\}=M^\{A\_\{K\}\}\\Delta^\{c\_\{K\}B\_\{K\}\}andDK=ΔcK​BKD\_\{K\}=\\Delta^\{c\_\{K\}B\_\{K\}\}\. By Theorem[2\.2](https://arxiv.org/html/2608.17343#S2.Thmtheorem2), for every pair\(i,ℓ\)\(i,\\ell\), there exists a nested sign\-invariant projection𝒬i,ℓ⊆ℝ⁡\[α\]\\mathcal\{Q\}\_\{i,\\ell\}\\subseteq\\mathbb\{R\}\[\\alpha\]\(Definition[6](https://arxiv.org/html/2608.17343#Thmdefinition6)\) of𝒫i,ℓ\\mathcal\{P\}\_\{i,\\ell\}such that: \(1\)\|𝒬i,ℓ\|≤SK\|\\mathcal\{Q\}\_\{i,\\ell\}\|\\leq S\_\{K\}, and \(2\)maxR∈𝒬i,ℓ⁡deg⁡\(R\)≤DK\\max\_\{R\\in\\mathcal\{Q\}\_\{i,\\ell\}\}\\deg\(R\)\\leq D\_\{K\}\. By Proposition[4\.1](https://arxiv.org/html/2608.17343#S4.Thmtheorem1), the truth value ofΦxi,τi,ℓ​\(α\)\\Phi\_\{x\_\{i\},\\tau\_\{i\},\\ell\}\(\\alpha\)is constant on every connected sign cellC∈Cell𝒬i,ℓC\\in\{\\textup\{Cell\}\}\_\{\\mathcal\{Q\}\_\{i,\\ell\}\}\.

Step 2: Construct one global polynomial family: Letℬ𝒜=\{αj−αmin,αmax−αj∣j=1,…,p\}\\mathcal\{B\}\_\{\\mathcal\{A\}\}=\\\{\\alpha\_\{j\}\-\\alpha\_\{\\min\},\\alpha\_\{\\max\}\-\\alpha\_\{j\}\\mid j=1,\\dots,p\\\}be the family of2​p2paffine polynomials defining the box\-like region𝒜=\[αmin,αmax\]p\\mathcal\{A\}=\[\\alpha\_\{\\min\},\\alpha\_\{\\max\}\]^\{p\}\. We then define the global polynomial set

𝒬~=ℬ𝒜∪⋃i=1N⋃ℓ=1L𝒬i,ℓ\.\\tilde\{\\mathcal\{Q\}\}=\\mathcal\{B\}\_\{\\mathcal\{A\}\}\\cup\\bigcup\_\{i=1\}^\{N\}\\bigcup\_\{\\ell=1\}^\{L\}\\mathcal\{Q\}\_\{i,\\ell\}\.Letq=\|𝒬~\|q=\\left\|\\tilde\{\\mathcal\{Q\}\}\\right\|\. Because there areN​LNLbranchwise projection families𝒬i,ℓ\\mathcal\{Q\}\_\{i,\\ell\}, each contains at mostSKS\_\{K\}polynomials, we haveq≤N​L​SK\+2​pq\\leq NLS\_\{K\}\+2p\.Besides, every polynomial in𝒬~\\tilde\{\\mathcal\{Q\}\}has degree at mostDKD\_\{K\}\.

Step 3: The labeling vector is constant on every global cell\. Consider any connected sign cellC∈Cell​\(𝒬~\)C\\in\{\\textup\{Cell\}\}\(\\tilde\{\\mathcal\{Q\}\}\)\. Fix an instancexix\_\{i\}and a branchℓ\\ell\. Since𝒬i,ℓ⊆𝒬~\\mathcal\{Q\}\_\{i,\\ell\}\\subseteq\\tilde\{\\mathcal\{Q\}\}, the sign of all polynomials in𝒬i,ℓ\\mathcal\{Q\}\_\{i,\\ell\}are constant onCC\. Therefore, there exists a sign conditionσi,ℓ\\sigma\_\{i,\\ell\}on𝒬i,ℓ\\mathcal\{Q\}\_\{i,\\ell\}such thatC⊆Reali𝒬i,ℓ​\(σOPENi,ℓ\)CLOSEC\\subseteq\{\\textup\{Reali\}\}\_\{\\mathcal\{Q\}\_\{i,\\ell\}\}\(\\sigma\_\{i,\\ell\)\}, and therefore in one cell belonging toCell𝒬i,ℓ\{\\textup\{Cell\}\}\_\{\\mathcal\{Q\}\_\{i,\\ell\}\}\. Proposition[4\.1](https://arxiv.org/html/2608.17343#S4.Thmtheorem1)now implies that the truth value ofΦxi,τi,ℓ​\(α\)\\Phi\_\{x\_\{i\},\\tau\_\{i\},\\ell\}\(\\alpha\)is unchanged asα\\alphavaries overCC\.

Note that the above holds for everyℓ=1,…,L\\ell=1,\\dots,L\. Therefore, the binary vector\(Φxi,τi,1​\(α\),…,ΦxN,τN,1​\(α\)\)\(\\Phi\_\{x\_\{i\},\\tau\_\{i\},1\}\(\\alpha\),\\dots,\\Phi\_\{x\_\{N\},\\tau\_\{N\},1\}\(\\alpha\)\)remains unchanged onCC\. Becauseβxi,τi\\beta\_\{x\_\{i\},\\tau\_\{i\}\}is a fixed boolean function, the truth value of

𝕀⁡\(fα​\(xi\)≥τi\)=βxi,τi​\(Φxi,τi,1​\(α\),…,Φxi,τi,L​\(α\)\)\\mathbb\{I\}\(f\_\{\\alpha\}\(x\_\{i\}\)\\geq\\tau\_\{i\}\)=\\beta\_\{x\_\{i\},\\tau\_\{i\}\}\(\\Phi\_\{x\_\{i\},\\tau\_\{i\},1\}\(\\alpha\),\\dots,\\Phi\_\{x\_\{i\},\\tau\_\{i\},L\}\(\\alpha\)\)is also unchanged forα∈C\\alpha\\in C\.

Applying this argument to everyi=1,…,Ni=1,\\dots,N, we claim that

v⁡\(\(S,τ\),fα\)=\(𝕀⁡\(fα​\(x1\)≥τ1\),…,𝕀⁡\(fα​\(xN\)≥τN\)\)v\(\(S,\\tau\),f\_\{\\alpha\}\)=\(\\mathbb\{I\}\(f\_\{\\alpha\}\(x\_\{1\}\)\\geq\\tau\_\{1\}\),\\dots,\\mathbb\{I\}\(f\_\{\\alpha\}\(x\_\{N\}\)\\geq\\tau\_\{N\}\)\)also remains unchanged forα∈C\\alpha\\in C\. Therefore, the task now is to bound\|Cell\(𝒬~\|\|\{\\textup\{Cell\}\}\(\\tilde\{\\mathcal\{Q\}\}\|and solve for the maximumNNthat satisfies2N≤\|Cell\(𝒬~\|2^\{N\}\\leq\|\{\\textup\{Cell\}\}\(\\tilde\{\\mathcal\{Q\}\}\|\.

Step 4: Establish the pseudo\-dimension upper bound\.The set of polynomials𝒬~\\tilde\{\\mathcal\{Q\}\}containsq≥pq\\geq ppolynomials inppvariables, each of degree at mostΔK\\Delta\_\{K\}\. From Lemma[2\.3](https://arxiv.org/html/2608.17343#S2.Thmtheorem3), there exists a universal constantκ\>0\\kappa\>0, such that\|Cell\(𝒬~\|≤\(κ​q​DKp\)p\|\{\\textup\{Cell\}\}\(\\tilde\{\\mathcal\{Q\}\}\|\\leq\\left\(\\frac\{\\kappa qD\_\{K\}\}\{p\}\\right\)^\{p\}\. Note thatq≤N​L​SK\+2​pq\\leq NLS\_\{K\}\+2p, our task now is to solve the inequality

2N≤\(κ⁡\(N​L​SK\+2​p\)​DKp\)p\\displaystyle 2^\{N\}\\leq\\left\(\\frac\{\\kappa\(NLS\_\{K\}\+2p\)D\_\{K\}\}\{p\}\\right\)^\{p\}⇔\\displaystyle\\Leftrightarrow2N/p≤\(κ⁡\(N​L​SK\+2​p\)​DKp\)\.\\displaystyle 2^\{N/p\}\\leq\\left\(\\frac\{\\kappa\(NLS\_\{K\}\+2p\)D\_\{K\}\}\{p\}\\right\)\.For convenience, letu=Npu=\\frac\{N\}\{p\}, and the above becomes

2u≤κ​DK​\(u​L​SK\+2\)≤κ⁡\(u\+2\)​L​SK​DK\.2^\{u\}\\leq\\kappa D\_\{K\}\(uLS\_\{K\}\+2\)\\leq\\kappa\(u\+2\)LS\_\{K\}D\_\{K\}\.Applying Proposition[A\.2](https://arxiv.org/html/2608.17343#A1.Thmtheorem2), we haveu=𝒪⁡\(log⁡\(2​L​SK​DK\)CLOSEu=\\mathcal\{O\}\(\\log\(2LS\_\{K\}D\_\{K\}\), orN=𝒪⁡\(p​log⁡\(2​L​SK​DK\)\)\.N=\\mathcal\{O\}\(p\\log\(2LS\_\{K\}D\_\{K\}\)\)\.Finally, substituteSK=MAK​ΔcK​BKS\_\{K\}=M^\{A\_\{K\}\}\\Delta^\{c\_\{K\}B\_\{K\}\}andDK=ΔcK​BKD\_\{K\}=\\Delta^\{c\_\{K\}B\_\{K\}\}onto that, we have the final conclusion\. ∎

## Appendix CAdditional Results and Omitted Proofs for Section[5](https://arxiv.org/html/2608.17343#S5)

### C\.1Omitted Proofs for Section[5\.1](https://arxiv.org/html/2608.17343#S5.SS1)

In this section, we will present the detailed proof for Theorem[5\.1](https://arxiv.org/html/2608.17343#S5.Thmtheorem1), which establishes the guarantee for data\-driven hyperparameter tuning\. We then provided a detailed discussion on the improvement of our results, compared to prior works as below\.

###### Theorem[5\.1](https://arxiv.org/html/2608.17343#S5.Thmtheorem1)\(restated\)\.

Let𝒜=\[αmin,αmax\]p\\mathcal\{A\}=\[\\alpha\_\{\\min\},\\alpha\_\{\\max\}\]^\{p\}andΘ=\[θmin,θmax\]d\\Theta=\[\\theta\_\{\\min\},\\theta\_\{\\max\}\]^\{d\}be the hyperparameter and parameter domains, respectively\. Assume that for any problem instancex∈𝒳x\\in\\mathcal\{X\}, the training objectivefx​\(α,θ\)≜f⁡\(x,α,θ\)f\_\{x\}\(\\alpha,\\theta\)\\triangleq f\(x,\\alpha,\\theta\), for any\(α,θ\)∈𝒜×Θ\(\\alpha,\\theta\)\\in\\mathcal\{A\}\\times\\Theta, admits a piecewise polynomial structure with complexity\(Mf,Tf,Δf\)\(M\_\{f\},T\_\{f\},\\Delta\_\{f\}\)\. Then, the pseudo\-dimension of the function classℒ=\{ℓα:𝒳→ℝ∣α∈𝒜\}\\mathcal\{L\}=\\\{\\ell\_\{\\alpha\}:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}\\mid\\alpha\\in\\mathcal\{A\}\\\}, whereℓα​\(x\)=minθ∈Θ⁡f⁡\(x,α,θ\)\\ell\_\{\\alpha\}\(x\)=\\min\_\{\\theta\\in\\Theta\}f\(x,\\alpha,\\theta\), is at most

Pdim​\(ℒ\)=Ω⁡\(p​log⁡Tf\+p​d​log⁡\(Mf\+d\)\+p​d​log⁡Δf\)\.\\text\{Pdim\}\(\\mathcal\{L\}\)=\\Omega\(p\\log T\_\{f\}\+pd\\log\(M\_\{f\}\+d\)\+pd\\log\\Delta\_\{f\}\)\.

###### Proof\.

Consider any problem instancex∈𝒳x\\in\\mathcal\{X\}and real\-valued thresholdτ∈ℝ\\tau\\in\\mathbb\{R\}\. Our goal is to show that: the binary value𝕀⁡\(ℓx​\(α\)≥τ\)\\mathbb\{I\}\(\\ell\_\{x\}\(\\alpha\)\\geq\\tau\), whereℓx​\(α\)≜ℓα​\(x\)=minθ∈Θ⁡\(x,α,θ\)\\ell\_\{x\}\(\\alpha\)\\triangleq\\ell\_\{\\alpha\}\(x\)=\\min\_\{\\theta\\in\\Theta\}\(x,\\alpha,\\theta\), as a function ofα\\alphacan be rewritten as a boolean combination of at mostTfT\_\{f\}polynomial FOLsΦx,τ,l\\Phi\_\{x,\\tau,l\}, each satisfying the complexity conditions as in Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)\. This can be done as follows\.

Step 1: Piecewise polynomial representation offx​\(α,θ\)≜f⁡\(x,α,θ\)f\_\{x\}\(\\alpha,\\theta\)\\triangleq f\(x,\\alpha,\\theta\)\.By assumption, for each problem instancexx, there exists: \(1\) a set of boundary polynomialsℋx=\{hx,1,…,hx,Mx\}⊂ℝ⁡\[α,θ\]\\mathcal\{H\}\_\{x\}=\\\{h\_\{x,1\},\\dots,h\_\{x,M\_\{x\}\}\\\}\\subset\\mathbb\{R\}\[\\alpha,\\theta\]whereMx≤MfM\_\{x\}\\leq M\_\{f\}, \(2\) a set of realized sign patternsΣx=\{−1,0,1\}mx\\Sigma\_\{x\}=\\\{\-1,0,1\\\}^\{m\_\{x\}\}, where\|Σx\|≤Tf\|\\Sigma\_\{x\}\|\\leq T\_\{f\}, and \(3\) a set of piece polynomials\{Px,σ\}σ∈Σx⊂ℝ⁡\[α,θ\]\\\{P\_\{x,\\sigma\}\\\}\_\{\\sigma\\in\\Sigma\_\{x\}\}\\subset\\mathbb\{R\}\[\\alpha,\\theta\]such that every boundary polynomialshx,mh\_\{x,m\}\(form=1,…,Mxm=1,\\dots,M\_\{x\}\) and piece polynomialsPx,σP\_\{x,\\sigma\}\(forσ∈Σx\\sigma\\in\\Sigma\_\{x\}\) has degree at mostΔf\\Delta\_\{f\}\. Those piece and boundary polynomials determine the form offx​\(α,θ\)f\_\{x\}\(\\alpha,\\theta\)as follows\.

For a sign patternσ=\(σ1,…,σMx\)∈Σx\\sigma=\(\\sigma\_\{1\},\\dots,\\sigma\_\{M\_\{x\}\}\)\\in\\Sigma\_\{x\}, we define the region predicate

Wherex,σ\(α,θ\)≜⋀m=1Mx\[sign\(hx,m\(α,θ\)=σm\]\.\\textup\{Where\}\_\{x,\\sigma\}\(\\alpha,\\theta\)\\triangleq\\bigwedge\_\{m=1\}^\{M\_\{x\}\}\[\\textup\{sign\}\(h\_\{x,m\}\(\\alpha,\\theta\)=\\sigma\_\{m\}\]\.For each\(α,θ\)∈𝒜×Θ\(\\alpha,\\theta\)\\in\\mathcal\{A\}\\times\\Theta, exact one sign patternσ∈Σx\\sigma\\in\\Sigma\_\{x\}is active, and on its corresponding region,fx​\(α,θ\)f\_\{x\}\(\\alpha,\\theta\)admits the polynomial formsfx​\(α,θ\)=Px,σ​\(α,θ\)f\_\{x\}\(\\alpha,\\theta\)=P\_\{x,\\sigma\}\(\\alpha,\\theta\)\.

Step 2: Rewriteℓx​\(α\)\\ell\_\{x\}\(\\alpha\)in the polynomial FOL form\.Recall that

ℓx​\(α\)=minθ∈Θ⁡fx​\(α,θ\)\.\\ell\_\{x\}\(\\alpha\)=\\min\_\{\\theta\\in\\Theta\}f\_\{x\}\(\\alpha,\\theta\)\.Thereforeℓx​\(α\)≥τ\\ell\_\{x\}\(\\alpha\)\\geq\\taufor a real\-valued thresholdτ\\tauif and only if for allθ∈Θ\\theta\\in\\Theta, we havefx​\(α,θ\)≥τf\_\{x\}\(\\alpha,\\theta\)\\geq\\tau\. Combining with Step 2, we can write the binary value𝕀⁡\(ℓx​\(α\)≥τ\)\\mathbb\{I\}\(\\ell\_\{x\}\(\\alpha\)\\geq\\tau\)as

⋀σ∈Σx\(∀θ∈Θ\)\[Wherex,σ\(α,θ\)⇒Px,σ\(α,θ\)≥τ\]=⋀σ∈ΣxΦx,τ,σ\(α\),\\displaystyle\\bigwedge\_\{\\sigma\\in\\Sigma\_\{x\}\}\(\\forall\\theta\\in\\Theta\)\\left\[\\textup\{Where\}\_\{x,\\sigma\}\(\\alpha,\\theta\)\\Rightarrow P\_\{x,\\sigma\}\(\\alpha,\\theta\)\\geq\\tau\\right\]=\\bigwedge\_\{\\sigma\\in\\Sigma\_\{x\}\}\\Phi\_\{x,\\tau,\\sigma\}\(\\alpha\),whereWherex,σ​\(α,θ\)\\textup\{Where\}\_\{x,\\sigma\}\(\\alpha,\\theta\)is a logical statement defined as in Step 2, and

Φx,τ,σ\(α\)=\(∀θ∈Θ\)\[Wherex,σ\(α,θ\)⇒Px,σ\(α,σ\)≥τ\]\\displaystyle\\Phi\_\{x,\\tau,\\sigma\}\(\\alpha\)=\(\\forall\\theta\\in\\Theta\)\\left\[\\textup\{Where\}\_\{x,\\sigma\}\(\\alpha,\\theta\)\\Rightarrow P\_\{x,\\sigma\}\(\\alpha,\\sigma\)\\geq\\tau\\right\]=\\displaystyle=\(∀θ∈ℝd\)\[¬InΘ\(θ\)∨¬Wherex,σ\(α,θ\)∨Px,σ\(α,σ\)≥τ\]\.\\displaystyle\(\\forall\\theta\\in\\mathbb\{R\}^\{d\}\)\[\\neg\\textup\{In\}\_\{\\Theta\}\(\\theta\)\\lor\\neg\\textup\{Where\}\_\{x,\\sigma\}\(\\alpha,\\theta\)\\lor P\_\{x,\\sigma\}\(\\alpha,\\sigma\)\\geq\\tau\]\.Here,InΘ\(θ\)=⋀r=1d\[θr≥θmin\]∧\[Θmax≥θr\]\\textup\{In\}\_\{\\Theta\}\(\\theta\)=\\bigwedge\_\{r=1\}^\{d\}\[\\theta\_\{r\}\\geq\\theta\_\{\\min\}\]\\land\[\\Theta\_\{\\max\}\\geq\\theta\_\{r\}\]denotes the binary indicator ifθ∈Θ=\[θmin,θmax\]d\\theta\\in\\Theta=\[\\theta\_\{\\min\},\\theta\_\{\\max\}\]^\{d\}, and in the above we use the logical identity that\(A⇒B\)=\(¬A∨B\)\(A\\Rightarrow B\)=\(\\neg A\\lor B\)\. We now see that𝕀⁡\(ℓx​\(α\)≥τ\)\\mathbb\{I\}\(\\ell\_\{x\}\(\\alpha\)\\geq\\tau\)is written in the formβx,τ​\(\{Φx,τ,1\}σ∈Σ\)\\beta\_\{x,\\tau\}\(\\\{\\Phi\_\{x,\\tau,1\}\\\}\_\{\\sigma\\in\\Sigma\}\), whereβx,τ​\(\{bσ\}σ∈Σx\)=⋀σ∈Σxbσ\\beta\_\{x,\\tau\}\(\\\{b\_\{\\sigma\}\\\}\_\{\\sigma\\in\\Sigma\_\{x\}\}\)=\\bigwedge\_\{\\sigma\\in\\Sigma\_\{x\}\}b\_\{\\sigma\}, as required by Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)\.

Step 3: Count the complexity of each brand and apply Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)\.The task left is to bound the complexity ofΦx,τ,σ\\Phi\_\{x,\\tau,\\sigma\}\. Since each polynomial FOL contains exactly one quantified block∀θ∈ℝd\\forall\\theta\\in\\mathbb\{R\}^\{d\}, we haveK=1K=1andd1=dd\_\{1\}=d\.

Note that we have: \(1\)Mx≤MfM\_\{x\}\\leq M\_\{f\}boundary polynomialshx,1,…,hx,Mxh\_\{x,1\},\\dots,h\_\{x,M\_\{x\}\}, \(2\)2​d2ddomain polynomialsθr−θmin\\theta\_\{r\}\-\\theta\_\{\\min\}andθmax−θr\\theta\_\{\\max\}\-\\theta\_\{r\}forr=1,…,dr=1,\\dots,d, and \(3\) a single value polynomialPx,σ​\(α,θ\)−τP\_\{x,\\sigma\}\(\\alpha,\\theta\)\-\\tau\. Therefore, each brand contains at mostMf\+2​d\+1M\_\{f\}\+2d\+1distinct atomic polynomial predicates\. Finally, the maximum degree of all atomic polynomial predicates is simply at mostΔf\\Delta\_\{f\}\. Finally, applying Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2), we obtain

Pdim​\(ℒ\)=𝒪⁡\(p​log⁡Tf\+p​d​log⁡\(Mf\+d\)\+p​d​log⁡ΔfCLOSE\\text\{Pdim\}\(\\mathcal\{L\}\)=\\mathcal\{O\}\(p\\log T\_\{f\}\+pd\\log\(M\_\{f\}\+d\)\+pd\\log\\Delta\_\{f\}as desired\. ∎

### C\.2Proofs for Section[5\.2](https://arxiv.org/html/2608.17343#S5.SS2)

In this section, we will formally present the proofs of Lemmas[5\.2](https://arxiv.org/html/2608.17343#S5.Thmtheorem2)and[5\.3](https://arxiv.org/html/2608.17343#S5.Thmtheorem3), which establish the lower\-bound depending on the number of piecesTfT\_\{f\}and the number of boundaryMfM\_\{f\}\.

###### Proof of Lemma[5\.2](https://arxiv.org/html/2608.17343#S5.Thmtheorem2)\.

Our goal is to show that there existsN=Ω⁡\(p​log⁡Tf\)N=\\Omega\(p\\log T\_\{f\}\)problem instancesx1,…,xNx\_\{1\},\\dots,x\_\{N\}and real\-valued thresholdτ1,…,τN\\tau\_\{1\},\\dots,\\tau\_\{N\}such thatℒ\\mathcal\{L\}can shatter all the problem instancesxix\_\{i\}andτi\\tau\_\{i\}\(fori=1,…,Ni=1,\\dots,N\) witnesses the shattering, that is

\|\{\(𝕀\(ℓα\(x1\)≥τ1\),…,\(𝕀\(ℓα\(xN\)≥τN\)∣α∈𝒜\}\|=2N\.\|\\\{\(\\mathbb\{I\}\(\\ell\_\{\\alpha\}\(x\_\{1\}\)\\geq\\tau\_\{1\}\),\\dots,\(\\mathbb\{I\}\(\\ell\_\{\\alpha\}\(x\_\{N\}\)\\geq\\tau\_\{N\}\)\\mid\\alpha\\in\\mathcal\{A\}\\\}\|=2^\{N\}\.
LetK=⌊Tf\+12⌋K=\\lfloor\\frac\{T\_\{f\}\+1\}\{2\}\\rfloor,B=⌊log2⁡K⌋B=\\lfloor\\log\_\{2\}K\\rfloor,𝒜=\[0,K−1\]p\\mathcal\{A\}=\[0,K\-1\]^\{p\}, andΘ=\[0,1\]d⊂ℝd\\Theta=\[0,1\]^\{d\}\\subset\\mathbb\{R\}^\{d\}be a box\-like region inℝd\\mathbb\{R\}^\{d\}\. We constructp​B=Ω⁡\(p​log⁡Tf\)pB=\\Omega\(p\\log T\_\{f\}\)problem instancesxj,bx\_\{j,b\}, forj=0,…,p−1j=0,\\dots,p\-1andb=0,…,B−1b=0,\\dots,B\-1by first defining the boundary polynomials for each problem instance: for eachxj,bx\_\{j,b\}, introduceK−1K\-1affine boundary polynomials:

hj,q\(α,θ\)=αj−\(q\+12\),q=0,…,K−2\.h\_\{j,q\}\(\\alpha,\\theta\)=\\alpha\_\{j\}\-\\left\(q\+\\frac\{1\}\{2\}\\right\),q=0,\\dots,K\-2\.In other words, each boundary polynomialhj,q​\(α,θ\)h\_\{j,q\}\(\\alpha,\\theta\)is just an affine function that doesnotdepend on the parameterθ\\theta\. The boundaries divide the hyperparameterαj\\alpha\_\{j\}axis intoKKopen intervals\(−∞,12\),\(12,32\),…,\(K−52,K−32\),\(K−32,\+∞\)\(\-\\infty,\\frac\{1\}\{2\}\),\(\\frac\{1\}\{2\},\\frac\{3\}\{2\}\),\\dots,\(K\-\\frac\{5\}\{2\},K\-\\frac\{3\}\{2\}\),\(K\-\\frac\{3\}\{2\},\+\\infty\)andK−1K\-1boundary pointsαj=12,32,…,K−32\\alpha\_\{j\}=\\frac\{1\}\{2\},\\frac\{3\}\{2\},\\dots,K\-\\frac\{3\}\{2\}\.

The task now is to construct the piece function for each problem instancexj,bx\_\{j,b\}\. For convenience, we define the open interval containingr∈\{0,…,K−1\}r\\in\\\{0,\\dots,K\-1\\\}asIrI\_\{r\}, and the sign condition realized in the intervalIrI\_\{r\}asσr\\sigma\_\{r\}\. Letbitb​\(r\)\\textup\{bit\}\_\{b\}\(r\)denote thebt​hb^\{th\}\-binary bit ofrr\. On the intervalIrI\_\{r\}, define

Pxj,b,σr​\(α,θ\)=12​bitb​\(r\),P\_\{x\_\{j,b\},\\sigma\_\{r\}\}\(\\alpha,\\theta\)=\\frac\{1\}\{2\}\\textup\{bit\}\_\{b\}\(r\),which is simply a constant piece function\. For anyαj\\alpha\_\{j\}that lies in one ofK−1K\-1boundary points, we simply assign the value 1 to the corresponding piece functions\. By this construction, the piece and boundary functions are independent ofθ\\theta, so minimizing overΘ\\Thetachanges nothing\.

Now, given an arbitrary sign patterny=\(yj,b\)j,b∈\{0,1\}p​By=\(y\_\{j,b\}\)\_\{j,b\}\\in\\\{0,1\\\}^\{pB\}, we simply chooseα=\(α0,…,αp−1\)\\alpha=\(\\alpha\_\{0\},\\dots,\\alpha\_\{p\-1\}\)such that

αj=∑b=0B−1yj,b​2b\.\\alpha\_\{j\}=\\sum\_\{b=0\}^\{B\-1\}y\_\{j,b\}2^\{b\}\.From the construction, we claim that the functionfxj,b​\(α,θ\)f\_\{x\_\{j,b\}\}\(\\alpha,\\theta\)admits piecewise polynomial structure with complexity\(⌊Tf−12⌋,Tf,1\)\(\\lfloor\\frac\{T\_\{f\}\-1\}\{2\}\\rfloor,T\_\{f\},1\)as expected\. To see this, we haveK−1=⌊Tf−12⌋K\-1=\\lfloor\\frac\{T\_\{f\}\-1\}\{2\}\\rfloorboundary polynomials of the formshj,q​\(α,θ\)=αj−\(q\+12\)h\_\{j,q\}\(\\alpha,\\theta\)=\\alpha\_\{j\}\-\\left\(q\+\\frac\{1\}\{2\}\\right\)forq=0,…,K−2q=0,\\dots,K\-2\. Those boundaries induceKKopen intervals andK−1K\-1boundary points, for a total of2​K−12K\-1pieces\. Therefore, the number of piece functions is at most

\|Σx\|≤2​K−1=2​⌊Tf\+12⌋−1≤Tf\.\|\\Sigma\_\{x\}\|\\leq 2K\-1=2\\left\\lfloor\\frac\{T\_\{f\}\+1\}\{2\}\\right\\rfloor\-1\\leq T\_\{f\}\.Finally, notice that all the piece and boundary functions are linear or constant functions with respect toα\\alphaandθ\\theta, soΔf=1\\Delta\_\{f\}=1\.

Moreover, we have the following claims:

- •0≤αj≤2B−1≤K−10\\leq\\alpha\_\{j\}\\leq 2^\{B\}\-1\\leq K\-1for anyj=0,…,p−1j=0,\\dots,p\-1\. This means thatα∈𝒜=\[0,K−1\]p\\alpha\\in\\mathcal\{A\}=\[0,K\-1\]^\{p\}\.
- •The open interval that containsαj\\alpha\_\{j\}isIαjI\_\{\\alpha\_\{j\}\}, which assigns the sign conditionσαj\\sigma\_\{\\alpha\_\{j\}\}, and therefore
- •the value ofℓα​\(xj,b\)=Pxj,b,σαj​\(α,θ\)=12​bitb​\(αj\)=12​yj,b\\ell\_\{\\alpha\}\(x\_\{j,b\}\)=P\_\{x\_\{j,b\},\\sigma\_\{\\alpha\_\{j\}\}\}\(\\alpha,\\theta\)=\\frac\{1\}\{2\}\\textup\{bit\}\_\{b\}\(\\alpha\_\{j\}\)=\\frac\{1\}\{2\}y\_\{j,b\}\.

Finally, choose the real\-valued thresholdsτj,b=14\\tau\_\{j,b\}=\\frac\{1\}\{4\}for allj=0,…,p−1j=0,\\dots,p\-1andb=0,…,B−1b=0,\\dots,B\-1, we have

𝕀⁡\(ℓα​\(xj,b\)≥τj,b\)=yj,b\\mathbb\{I\}\(\\ell\_\{\\alpha\}\(x\_\{j,b\}\)\\geq\\tau\_\{j,b\}\)=y\_\{j,b\}Therefore, we proved that for any sign patterny∈\{0,1\}p​By\\in\\\{0,1\\\}^\{pB\}, there existsα\\alphasuch that

𝕀⁡\(ℓα​\(x1\)≥τ1\),…,\(𝕀⁡\(ℓα​\(xN\)≥τN\)=yCLOSE,\\mathbb\{I\}\(\\ell\_\{\\alpha\}\(x\_\{1\}\)\\geq\\tau\_\{1\}\),\\dots,\(\\mathbb\{I\}\(\\ell\_\{\\alpha\}\(x\_\{N\}\)\\geq\\tau\_\{N\}\)=y,meaning thatℒ\\mathcal\{L\}can shatter the set of problem instancesxj,bx\_\{j,b\}\(forj=0,…,p−1j=0,\\dots,p\-1andb=0,…,B−1b=0,\\dots,B\-1\) withτj,b=14\\tau\_\{j,b\}=\\frac\{1\}\{4\}witness the shattering\. Sincep​B=Ω⁡\(p​log⁡Tf\)pB=\\Omega\(p\\log T\_\{f\}\), we claim thatPdim​\(ℒ\)=Ω⁡\(p​log⁡Tf\)\\text\{Pdim\}\(\\mathcal\{L\}\)=\\Omega\(p\\log T\_\{f\}\)∎

###### Proof of Lemma[5\.3](https://arxiv.org/html/2608.17343#S5.Thmtheorem3)\.

Again, our goal is to constructN=Ω⁡\(p​d​log⁡\(1\+Md\)\)N=\\Omega\\left\(pd\\log\\left\(1\+\\frac\{M\}\{d\}\\right\)\\right\)problem instancesx1,…,xNx\_\{1\},\\dots,x\_\{N\}and real\-valued thresholdsτ1,…,τN\\tau\_\{1\},\\dots,\\tau\_\{N\}such that

\|\{\(𝕀\(ℓα\(x1\)≥τ1\),…,\(𝕀\(ℓα\(xN\)≥τN\)∣α∈𝒜\}\|=2N\.\|\\\{\(\\mathbb\{I\}\(\\ell\_\{\\alpha\}\(x\_\{1\}\)\\geq\\tau\_\{1\}\),\\dots,\(\\mathbb\{I\}\(\\ell\_\{\\alpha\}\(x\_\{N\}\)\\geq\\tau\_\{N\}\)\\mid\\alpha\\in\\mathcal\{A\}\\\}\|=2^\{N\}\.
Lets≜min⁡\{M,d\}s\\triangleq\\min\\\{M,d\\\},a≜⌊Ms⌋a\\triangleq\\left\\lfloor\\frac\{M\}\{s\}\\right\\rfloor,ρ≜M−a​s∈\{0,…,s−1\}\\rho\\triangleq M\-as\\in\\\{0,\\dots,s\-1\\\}\. We then define

mi≜\{a\+1,1≤i≤ρ,a,ρ<i≤s,0s<i≤d\.m\_\{i\}\\triangleq\\begin\{cases\}a\+1,&1\\leq i\\leq\\rho,\\\\ a,&\\rho<i\\leq s,\\\\ 0&s<i\\leq d\.\\end\{cases\}Then∑i=1dmi=M\\sum\_\{i=1\}^\{d\}m\_\{i\}=M\. We then define

RM,d≜∏i=1d\(mi\+1\),Sm,d≜∏i=1d\(2​mi\+1\)\.R\_\{M,d\}\\triangleq\\prod\_\{i=1\}^\{d\}\(m\_\{i\}\+1\),\\quad S\_\{m,d\}\\triangleq\\prod\_\{i=1\}^\{d\}\(2m\_\{i\}\+1\)\.Roughly speaking,RM,dR\_\{M,d\}is the number of sign regions in which none of the boundary polynomials vanishes, whileSM,dS\_\{M,d\}is the total number of realized sign patterns, including patterns with boundary equalities\.

Step 1: Defining thesharedboundary functions\.For every coordinatei=1,…,di=1,\\dots,dand everyq=0,…,mi−1q=0,\\dots,m\_\{i\}\-1, we define the boundary functionshi,q​\(α,θ\)h\_\{i,q\}\(\\alpha,\\theta\)for all problem instances as

hi,q​\(α,θ\)≜θi−\(q\+12\)\.h\_\{i,q\}\(\\alpha,\\theta\)\\triangleq\\theta\_\{i\}\-\\left\(q\+\\frac\{1\}\{2\}\\right\)\.By construction, there are exactly∑i=1dmi=Mf\\sum\_\{i=1\}^\{d\}m\_\{i\}=M\_\{f\}such boundary affine polynomials, and donotdepend onα\\alpha\. We define the parameter box\-like region asΘ≜∏i=1d\[−1,mi\+1\]\\Theta\\triangleq\\prod\_\{i=1\}^\{d\}\[\-1,m\_\{i\}\+1\]\. For a fixed coordinateii, the ordered thresholds12,32,…,mi−12\\frac\{1\}\{2\},\\frac\{3\}\{2\},\\dots,m\_\{i\}\-\\frac\{1\}\{2\}can produce at mostmi\+1m\_\{i\}\+1non\-zero sign patterns, andmim\_\{i\}zero\-containing sign patterns, one for each threshold equality\. Therefore, the one\-dimensional family\{hi,q\}q=0mi−1\\\{h\_\{i,q\}\\\}\_\{q=0\}^\{m\_\{i\}\-1\}realizes exactly2​mi\+12m\_\{i\}\+1sign patterns on theit​hi^\{th\}coordinateθi\\theta\_\{i\}ofθ∈Θ\\theta\\in\\Theta\.

Note that the ordinatesθi\\theta\_\{i\}are independent: any choice of one realizable coordinate\-wise sign pattern is obtained by choosing the coordinateθi\\theta\_\{i\}separately\. Therefore, the full boundary family\{hi,q​\(α,θ\)\}i,q\\\{h\_\{i,q\}\(\\alpha,\\theta\)\\\}\_\{i,q\}realize exactlySM,d=∏i=1d\(2​mi\+1\)S\_\{M,d\}=\\prod\_\{i=1\}^\{d\}\(2m\_\{i\}\+1\)sign pattern when varyingθ∈Θ\\theta\\in\\Theta\.

Moreover, among these patterns, there are exactlymi\+1m\_\{i\}\+1coordinate\-wise choices that contain no zero for coordinateii\. Therefore, the full product regions containing no boundary equality areRM,d=∏i=1d\(mi\+1\)R\_\{M,d\}=\\prod\_\{i=1\}^\{d\}\(m\_\{i\}\+1\)\. Each such region corresponds to a distinct integer vectoru=\(u1,…,ud\)u=\(u\_\{1\},\\dots,u\_\{d\}\), whereui∈\{0,…,mi\}u\_\{i\}\\in\\\{0,\\dots,m\_\{i\}\\\}\. Thus, every one of theseRM,dR\_\{M,d\}regions is non\-empty and belongs toΘ\\Theta\.

Step 2: Define the problem instances via the piecewise functions\.For convenience, defineB≜⌊log2⁡RM,d⌋B\\triangleq\\lfloor\\log\_\{2\}R\_\{M,d\}\\rfloorandK≜2BK\\triangleq 2^\{B\}\. BecauseK≤RM,dK\\leq R\_\{M,d\}, we may selectKKdistinct zero\-free grid regions and enumerate the asC0,…,CK−1C\_\{0\},\\dots,C\_\{K\-1\}\. Letσr\\sigma\_\{r\}be the boundary sign pattern corresponding toCrC\_\{r\}, and let𝒜=\[0,K−1\]p\\mathcal\{A\}=\[0,K\-1\]^\{p\}be the box\-like hyperparameter regions\. We then define a finite problem instance sets𝒳:=\{xj,b:j∈\{1,…,p\},b∈\{0,…,B−1\}\}\\mathcal\{X\}:=\\\{x\_\{j,b\}:j\\in\\\{1,\\dots,p\\\},b\\in\\\{0,\\dots,B\-1\\\}\\\}, and therefore\|c​X\|=p​B\\left\|cX\\right\|=pB\. Forr∈\{0,…,K−1\}r\\in\\\{0,\\dots,K\-1\\\}, letbitb​\(r\)∈\{0,1\}\\textup\{bit\}\_\{b\}\(r\)\\in\\\{0,1\\\}denote thebt​hb^\{th\}binary bit ofrr\.

We formally construct the problem instancexj,bx\_\{j,b\}as follows\. On the selected sign patternσr\\sigma\_\{r\}, we define the piece functionPxj,b,σr​\(α,θ\)P\_\{x\_\{j,b\},\\sigma\_\{r\}\}\(\\alpha,\\theta\)as

Pxj,b,σr\(α,θ\)≜\(αj−r\)2\+12bitb\(r\),r=0,…,K−1\.P\_\{x\_\{j,b\},\\sigma\_\{r\}\}\(\\alpha,\\theta\)\\triangleq\(\\alpha\_\{j\}\-r\)^\{2\}\+\\frac\{1\}\{2\}\\textup\{bit\}\_\{b\}\(r\),\\quad r=0,\\dots,K\-1\.For all other realized sign patternsσ\\sigma, including all boundary patterns and all unselected zero\-free patterns, we simply define their corresponding piece functions as

Pxj,b,σ​\(α,θ\)≜2\.P\_\{x\_\{j,b\},\\sigma\}\(\\alpha,\\theta\)\\triangleq 2\.
By construction, each problem instancesxj,bx\_\{j,b\}have the functionfj,bf\_\{j,b\}that admitspiecewise polynomial structurewith complexity\(M,SM,d,2\)\(M,S\_\{M,d\},2\)\.

Step 3: Establish the pseudo\-dimension lower\-bound\. We now show that the constructed problem instancesxj,bx\_\{j,b\}can be shattered byℒ\\mathcal\{L\}, and there are appropriate real\-valued thresholdsτj,b\\tau\_\{j,b\}that witness the shattering\.

Consider an arbitrary labelingy=\(yj,b\)j,b∈\{0,1\}p​By=\(y\_\{j,b\}\)\_\{j,b\}\\in\\\{0,1\\\}^\{pB\}\. For anyj=1,…,pj=1,\\dots,p, we define

rj≜∑b=0B−1yj,b​2b∈\{0,…,2B−1\}=\{0,…,K−1\},r\_\{j\}\\triangleq\\sum\_\{b=0\}^\{B\-1\}y\_\{j,b\}2^\{b\}\\in\\\{0,\\dots,2^\{B\}\-1\\\}=\\\{0,\\dots,K\-1\\\},and choose the hyperparameterα=\(α1,…,αp\)\\alpha=\(\\alpha\_\{1\},\\dots,\\alpha\_\{p\}\)such asαj≜rj\\alpha\_\{j\}\\triangleq r\_\{j\}\. Thenα∈𝒜\\alpha\\in\\mathcal\{A\}\.

Consider a problem instancexj,bx\_\{j,b\}\. SinceCrjC\_\{r\_\{j\}\}is not empty, there existsθ∈Crj∩Θ\\theta\\in C\_\{r\_\{j\}\}\\cap\\Theta, and on this region, we have

Pxj,b,σrj​\(α,θ\)=\(rj−rj\)2\+12​bitb​\(rj\)=12​yj,b\.P\_\{x\_\{j,b\},\\sigma\_\{r\_\{j\}\}\}\(\\alpha,\\theta\)=\(r\_\{j\}\-r\_\{j\}\)^\{2\}\+\\frac\{1\}\{2\}\\textup\{bit\}\_\{b\}\(r\_\{j\}\)=\\frac\{1\}\{2\}y\_\{j,b\}\.For any other selected region wheres≠rjs\\neq r\_\{j\}, we have

Pxj,b,σs​\(α,θ\)=\(rj−s\)2\+12​bitb​\(s\)≥1\.P\_\{x\_\{j,b\},\\sigma\_\{s\}\}\(\\alpha,\\theta\)=\(r\_\{j\}\-s\)^\{2\}\+\\frac\{1\}\{2\}\\textup\{bit\}\_\{b\}\(s\)\\geq 1\.The inequality comes from the fact thatrj,sr\_\{j\},sare integer, meaning\(rj−s\)2≥1\(r\_\{j\}\-s\)^\{2\}\\geq 1ifrj≠sr\_\{j\}\\neq s\. This implies that

ℓα​\(xj,b\)=minθ∈Θ⁡f⁡\(xj,b,α,θ\)=12​yj,b\.\\ell\_\{\\alpha\}\(x\_\{j,b\}\)=\\min\_\{\\theta\\in\\Theta\}f\(x\_\{j,b\},\\alpha,\\theta\)=\\frac\{1\}\{2\}y\_\{j,b\}\.Finally, chooseτj,b=14\\tau\_\{j,b\}=\\frac\{1\}\{4\}for allj∈\{1,…,p\}j\\in\\\{1,\\dots,p\\\}andb∈\{0,…,B−1\}b\\in\\\{0,\\dots,B\-1\\\}, we have

𝕀⁡\(ℓα​\(xj,b\)≥τj,b\)=yj,b\.\\mathbb\{I\}\\left\(\\ell\_\{\\alpha\}\(x\_\{j,b\}\)\\geq\\tau\_\{j,b\}\\right\)=y\_\{j,b\}\.Therefore,ℒ\\mathcal\{L\}can shatter the set\{xj,b\}j,b\\\{x\_\{j,b\}\\\}\_\{j,b\}ofp​BpBproblem instances with\{τj,b\}j,b\\\{\\tau\_\{j,b\}\\\}\_\{j,b\}witnesses the shattering\. Therefore, we claim thatPdim​\(ℒ\)≥p​B=p⁡⌊log2⁡RM,d⌋\\text\{Pdim\}\(\\mathcal\{L\}\)\\geq pB=p\\left\\lfloor\\log\_\{2\}R\_\{M,d\}\\right\\rfloor\.

the task now is to show thatlog⁡RM,d=Ω⁡\(d​log⁡\(1\+Md\)\)\\log R\_\{M,d\}=\\Omega\\left\(d\\log\\left\(1\+\\frac\{M\}\{d\}\\right\)\\right\)\. We consider two cases:

- •IfM≤dM\\leq d, thenRM,d=2MR\_\{M,d\}=2^\{M\}\. Sincelog⁡\(1\+t\)≤t\\log\(1\+t\)\\leq tfort≥0t\\geq 0, we haved​log⁡\(1\+Md\)≤Md\\log\(1\+\\frac\{M\}\{d\}\)\\leq M, whereaslog⁡MM,d=M​log⁡2\\log M\_\{M,d\}=M\\log 2\. This meanslog⁡RM,d=Ω⁡\(d​log⁡\(1\+Md\)\)\\log R\_\{M,d\}=\\Omega\\left\(d\\log\\left\(1\+\\frac\{M\}\{d\}\\right\)\\right\)holds true\.
- •IfM\>dM\>d, thens=ds=d, anda=⌊M/d⌋≥1a=\\lfloor M/d\\rfloor\\geq 1\. By definition, we haveRM,d≥\(a\+1\)dR\_\{M,d\}\\geq\(a\+1\)^\{d\}\. Letx=M/d≥1x=M/d\\geq 1, we claim thata\+1≥1\+xa\+1\\geq\\sqrt\{1\+x\}\. To see that, if1≤x<21\\leq x<2, we havea\+1=2≥1\+xa\+1=2\\geq\\sqrt\{1\+x\}\. Ifx≥2x\\geq 2, thena\+1\>x≥1\+xa\+1\>x\\geq\\sqrt\{1\+x\}\. Therefore log⁡RM,d≥d​log⁡\(a\+1\)≥d2​log⁡\(1\+x\)=d2​log⁡\(1\+Md\)\.\\log R\_\{M,d\}\\geq d\\log\(a\+1\)\\geq\\frac\{d\}\{2\}\\log\(1\+x\)=\\frac\{d\}\{2\}\\log\\left\(1\+\\frac\{M\}\{d\}\\right\)\.This also implieslog⁡RM,d=Ω⁡\(d​log⁡\(1\+Md\)\)\\log R\_\{M,d\}=\\Omega\\left\(d\\log\\left\(1\+\\frac\{M\}\{d\}\\right\)\\right\)holds true\.

Therefore, we claim thatPdim​\(ℒ\)=Ω⁡\(p​d​log⁡\(1\+Mfd\)\)\\text\{Pdim\}\(\\mathcal\{L\}\)=\\Omega\\left\(pd\\log\\left\(1\+\\frac\{M\_\{f\}\}\{d\}\\right\)\\right\)\. ∎

## Appendix DAdditional Results and Proofs for Section[6](https://arxiv.org/html/2608.17343#S6)

In this section, we will formally present the proof for Theorem[6\.1](https://arxiv.org/html/2608.17343#S6.Thmtheorem1)\. Again, we then provide a discussion on the improvement of our proposed result compared to prior work by Le et al\.\([21](https://arxiv.org/html/2608.17343#bib.bib6)\)\.

###### Theorem[6\.1](https://arxiv.org/html/2608.17343#S6.Thmtheorem1)\(restated\)\.

Under Assumption 1, letℒval=\{ℓαval:𝒳→\[−H,H\]∣α∈𝒜\}\\mathcal\{L\}\_\{\\text\{val\}\}=\\\{\\ell\_\{\\alpha\}^\{\\text\{val\}\}:\\mathcal\{X\}\\to\[\-H,H\]\\mid\\alpha\\in\\mathcal\{A\}\\\},Δf,g=max⁡\{1,Δf,Δg\}\\Delta\_\{f,g\}=\\max\\\{1,\\Delta\_\{f\},\\Delta\_\{g\}\\\}, andMtot=Mf\+Mg\+Tf\+d\.M\_\{\\textup\{tot\}\}=M\_\{f\}\+M\_\{g\}\+T\_\{f\}\+d\.

Pdim⁡\(ℒval\)=𝒪⁡\(p​log⁡\(Tf​Tg\)\+p​d2​log⁡\(2\+Mtot​Δf,g\)\)\.\\operatorname\{Pdim\}\(\\mathcal\{L\}\_\{\\text\{val\}\}\)=\\mathcal\{O\}\\left\(p\\log\(T\_\{f\}T\_\{g\}\)\+pd^\{2\}\\log\\left\(2\+M\_\{\\textup\{tot\}\}\\Delta\_\{f,g\}\\right\)\\right\)\.

###### Proof\.

Fixed a problem instancex∈𝒳x\\in\\mathcal\{X\}and a real\-valued thresholdτ∈ℝ\\tau\\in\\mathbb\{R\}, our goal is to express𝕀⁡\(ℓαval​\(x\)≥τ\)\\mathbb\{I\}\(\\ell\_\{\\alpha\}^\{\\textup\{val\}\}\(x\)\\geq\\tau\)as a boolean combination of of polynomial FOL to which Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)applies\. Recall that

𝒮⁡\(x,α\)=arg⁡minθ∈Θ​fx​\(α,θ\),and​ℓαval=infθ∈𝒮⁡\(x,α\)gx​\(α,θ\)\.\\mathcal\{S\}\(x,\\alpha\)=\\arg\\min\_\{\\theta\\in\\Theta\}f\_\{x\}\(\\alpha,\\theta\),\\textup\{ and \}\\ell\_\{\\alpha\}^\{\\textup\{val\}\}=\\inf\_\{\\theta\\in\\mathcal\{S\}\(x,\\alpha\)\}g\_\{x\}\(\\alpha,\\theta\)\.We will proceed with the following steps\.

Step 1: Piecewise polynomial representation\.For the given fixed problem instances, letΣxf⊂\{−1,0,1\}Mf\\Sigma^\{f\}\_\{x\}\\subset\\\{\-1,0,1\\\}^\{M\_\{f\}\}, andΣxg⊂\{−1,0,1\}Mg\\Sigma^\{g\}\_\{x\}\\subset\\\{\-1,0,1\\\}^\{M\_\{g\}\}be the sets of of sign conditions indexing the training and validation pieces, respectively\. By Assumption[1](https://arxiv.org/html/2608.17343#Thmassumption1), we have\|Σxf\|≤Tf\|\\Sigma\_\{x\}^\{f\}\|\\leq T\_\{f\}and\|Σxg\|≤Tg\|\\Sigma^\{g\}\_\{x\}\|\\leq T\_\{g\}\. For everyσ∈Σxf\\sigma\\in\\Sigma\_\{x\}^\{f\}, letFx,σF\_\{x,\\sigma\}be the corresponding training piece polynomial\. For everyγ∈Σxg\\gamma\\in\\Sigma^\{g\}\_\{x\}, letGx,γG\_\{x,\\gamma\}be the corresponding validation piece polynomial\. We then define the region predicates as

Wherex,σf\(α,θ\)=⋀m=1Mf\[sign\(hx,m′\(α,θ\)=σm\],\\textup\{Where\}^\{f\}\_\{x,\\sigma\}\(\\alpha,\\theta\)=\\bigwedge\_\{m=1\}^\{M\_\{f\}\}\[\{\\text\{sign\}\}\(h^\{\\prime\}\_\{x,m\}\(\\alpha,\\theta\)=\\sigma\_\{m\}\],and

Wherex,γg\(α,θ\)=⋀m=1Mg\[sign\(hx,mg\(α,θ\)=γm\]\.\\textup\{Where\}\_\{x,\\gamma\}^\{g\}\(\\alpha,\\theta\)=\\bigwedge\_\{m=1\}^\{M\_\{g\}\}\[\{\\text\{sign\}\}\(h^\{g\}\_\{x,m\}\(\\alpha,\\theta\)=\\gamma\_\{m\}\]\.Thus, wheneverWherex,σf​\(α,θ\)\\textup\{Where\}^\{f\}\_\{x,\\sigma\}\(\\alpha,\\theta\)holds, we have

fx​\(α,θ\)=Fx,σ​\(α,θ\),f\_\{x\}\(\\alpha,\\theta\)=F\_\{x,\\sigma\}\(\\alpha,\\theta\),and similarly, wheneverWherex,σf​\(α,θ\)\\textup\{Where\}^\{f\}\_\{x,\\sigma\}\(\\alpha,\\theta\)holds, we have

gx​\(α,θ\)=Gx,γ​\(α,θ\)\.g\_\{x\}\(\\alpha,\\theta\)=G\_\{x,\\gamma\}\(\\alpha,\\theta\)\.Moreover, we also define the parameter\-feasibility checking condition as

InΘ\(u\)=⋀r=1d\[ur−θmin≥0∧θmax−ur≥0\],\\textup\{In\}\_\{\\Theta\}\(u\)=\\bigwedge\_\{r=1\}^\{d\}\[u\_\{r\}\-\\theta\_\{\\min\}\\geq 0\\land\\theta\_\{\\max\}\-u\_\{r\}\\geq 0\],which is true exactly whenu∈Θu\\in\\Theta\.

Step 2: Certifying that a candidate is a training minimizer\.Fixedσ∈Σxf\\sigma\\in\\Sigma^\{f\}\_\{x\}\. For a candidate solutionθ\\thetaand a competing solutionuu, we define

Comparex,σ\(α,θ,u\)≜¬InΘ\(u\)∨⋀ρ∈Σxf\[¬Wherex,ρf\(α,u\)∨Fx,σ\(α,θ\)≤Fx,ρ\(α,u\)\]\.\\textup\{Compare\}\_\{x,\\sigma\}\(\\alpha,\\theta,u\)\\triangleq\\neg\\textup\{In\}\_\{\\Theta\}\(u\)\\lor\\bigwedge\_\{\\rho\\in\\Sigma^\{f\}\_\{x\}\}\\left\[\\neg\\textup\{Where\}^\{f\}\_\{x,\\rho\}\(\\alpha,u\)\\lor F\_\{x,\\sigma\}\(\\alpha,\\theta\)\\leq F\_\{x,\\rho\}\(\\alpha,u\)\\right\]\.Let’s elaborate the predicate above closely\. First, suppose thatu∈Θu\\in\\Theta\. Note that there is exactly one sign conditionsρ∈Σxf\\rho\\in\\Sigma\_\{x\}^\{f\}is active at the point\(α,u\)∈𝒜×Θ\(\\alpha,u\)\\in\\mathcal\{A\}\\times\\Theta\. For that activeρ\\rho, the predicate requires

Fx,σ​\(α,θ\)≤Fx,ρ​\(α,u\)=fx​\(α,u\)\.F\_\{x,\\sigma\}\(\\alpha,\\theta\)\\leq F\_\{x,\\rho\}\(\\alpha,u\)=f\_\{x\}\(\\alpha,u\)\.For all other inactiveρ\\rho, the corresponding implication is automatically true\. Therefore, provided in thatθ\\thetabelong to the training corresponding toσ\\sigma, we have\(∀u∈ℝd\)​Comparex,σ​\(α,θ,u\)\(\\forall u\\in\\mathbb\{R\}^\{d\}\)\\textup\{Compare\}\_\{x,\\sigma\}\(\\alpha,\\theta,u\)is equivalent to

fx​\(α,θ\)≤fx​\(α,u\)​for all​u∈Θ\.f\_\{x\}\(\\alpha,\\theta\)\\leq f\_\{x\}\(\\alpha,u\)\\textup\{ for all \}u\\in\\Theta\.Therefore

θ∈𝒮⁡\(x,α\)⇔InΘ​\(θ\)∧Wherex,σf​\(α,θ\)∧\(∀u∈ℝd\)​Comparex,σ​\(α,θ,u\),\\theta\\in\\mathcal\{S\}\(x,\\alpha\)\\Leftrightarrow\\textup\{In\}\_\{\\Theta\}\(\\theta\)\\land\\textup\{Where\}\_\{x,\\sigma\}^\{f\}\(\\alpha,\\theta\)\\land\(\\forall u\\in\\mathbb\{R\}^\{d\}\)\\textup\{Compare\}\_\{x,\\sigma\}\(\\alpha,\\theta,u\),for the active training sign conditionσ\\sigma\.

Step 3: Encoding a bad training minimizer\.For each pair\(σ,γ\)∈Σxf×Σxg\(\\sigma,\\gamma\)\\in\\Sigma\_\{x\}^\{f\}\\times\\Sigma^\{g\}\_\{x\}, we defineΦx,τ,σ,γ​\(α\)\\Phi\_\{x,\\tau,\\sigma,\\gamma\}\(\\alpha\)as

\(∃θ∈ℝd\)\[InΘ\(θ\)∧Wherefx,σ\(α,θ\)∧Wherex,γg\(α,θ\)∧Gx,γ\(α,θ\)<τ∧\(∀u∈ℝd\)Comparex,σ\(α,θ,u\)\]\.\\displaystyle\(\\exists\\theta\\in\\mathbb\{R\}^\{d\}\)\\left\[\\textup\{In\}\_\{\\Theta\}\(\\theta\)\\land\\textup\{Where\}^\{f\}\_\{x,\\sigma\}\(\\alpha,\\theta\)\\land\\textup\{Where\}\_\{x,\\gamma\}^\{g\}\(\\alpha,\\theta\)\\land G\_\{x,\\gamma\}\(\\alpha,\\theta\)<\\tau\\land\(\\forall u\\in\\mathbb\{R\}^\{d\}\)\\textup\{Compare\}\_\{x,\\sigma\}\(\\alpha,\\theta,u\)\\right\]\.Because the candidate conditions do not depend onuu, the formula above can be equivalently be written in the form with the two ordered blocks\(∃θ∈ℝd\)​\(∀u∈ℝd\)\(\\exists\\theta\\in\\mathbb\{R\}^\{d\}\)\(\\forall u\\in\\mathbb\{R\}^\{d\}\)\. This implies that every branch hasK=2K=2andd1=d2=dd\_\{1\}=d\_\{2\}=d\.

Step 4\. Recovering the validation\-loss threshold event\.Since𝒮⁡\(x,α\)≠∅\\mathcal\{S\}\(x,\\alpha\)\\neq\\emptyset, we haveinfθ∈𝒮⁡\(x,α\)gx​\(α,θ\)<τ\\inf\_\{\\theta\\in\\mathcal\{S\}\(x,\\alpha\)\}g\_\{x\}\(\\alpha,\\theta\)<\\tauif and only if there existsθ∈𝒮⁡\(x,α\)\\theta\\in\\mathcal\{S\}\(x,\\alpha\)such thatgx​\(α,θ\)<τg\_\{x\}\(\\alpha,\\theta\)<\\tau\. Importantly, this does not require the infimum to be attained\. If the infimum is strictly belowτ\\tau, the definition of the infimum guarantees the existence of an element with value belowτ\\tau\. It follows that

ℓαval​\(x\)<τ⇔⋁σ∈Σgf,γ∈ΣxgΦx,τ,σ,γ​\(α\)\.\\ell\_\{\\alpha\}^\{\\textup\{val\}\}\(x\)<\\tau\\Leftrightarrow\\bigvee\_\{\\sigma\\in\\Sigma^\{f\}\_\{g\},\\gamma\\in\\Sigma\_\{x\}^\{g\}\}\\Phi\_\{x,\\tau,\\sigma,\\gamma\}\(\\alpha\)\.This implies that the condition𝕀⁡\(ℓαeval​\(x\)≥τ\)\\mathbb\{I\}\(\\ell\_\{\\alpha\}^\{\\textup\{eval\}\}\(x\)\\geq\\tau\)is a NOR\-type Boolean combination of at mostL≤Tf​TgL\\leq T\_\{f\}T\_\{g\}polynomial branches, as required by Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)\.

Step 5\. Counting the atomic polynomials and applying Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)\. Finally, note that each branch contains at mostMtot=2​Mf\+Mg\+Tf\+4​d\+1M\_\{\\textup\{tot\}\}=2M\_\{f\}\+M\_\{g\}\+T\_\{f\}\+4d\+1distinct atomic polynomial predicate, and each atomic predicate has the degree at mostΔf,g=max⁡\{1,Δf,Δg\}\\Delta\_\{f,g\}=\\max\\\{1,\\Delta\_\{f\},\\Delta\_\{g\}\\\}\. Substituting into Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)we have the final conclusion\. ∎

## Appendix EAdditional results and Omitted proofs for Section[7](https://arxiv.org/html/2608.17343#S7)

### E\.1Omitted proof for Section[7](https://arxiv.org/html/2608.17343#S7)

In this section, we present the detailed proof for Theorem[7\.1](https://arxiv.org/html/2608.17343#S7.Thmtheorem1)\.

###### Theorem[7\.1](https://arxiv.org/html/2608.17343#S7.Thmtheorem1)\(restated\)\.

Consider the class of validation loss functionsℒval=\{ℓαval:𝒳→\[−H,H\]∣α∈𝒜\}\\mathcal\{L\}\_\{\\text\{val\}\}=\\\{\\ell\_\{\\alpha\}^\{\\text\{val\}\}:\\mathcal\{X\}\\to\[\-H,H\]\\mid\\alpha\\in\\mathcal\{A\}\\\}induced by the Weighted Group Lasso objectives\. Assuming thatΘ=ℝd\\Theta=\\mathbb\{R\}^\{d\}and𝒜⊂\(0,∞\)p\\mathcal\{A\}\\subset\(0,\\infty\)^\{p\}, then the pseudo\-dimension is bounded byPdim⁡\(ℒval\)=𝒪⁡\(p​\(d\+p\)2​log⁡p\)\\operatorname\{Pdim\}\(\\mathcal\{L\}\_\{\\text\{val\}\}\)=\\mathcal\{O\}\(p\(d\+p\)^\{2\}\\log p\)\.

###### Proof\.

Assume under standard unconstrained formulation, that isΘ=ℝd\\Theta=\\mathbb\{R\}^\{d\}and𝒜⊂\(0,∞\)p\\mathcal\{A\}\\subset\(0,\\infty\)^\{p\}\. Forv=\(v1,…,vp\)∈ℝdv=\(v\_\{1\},\\dots,v\_\{p\}\)\\in\\mathbb\{R\}^\{d\}andν∈ℝp\\nu\\in\\mathbb\{R\}^\{p\}, we define

Norm\(v,ν\)=∑i=1p\[νi≥0∧νi2=∑j=1divi,j2\]\.\\textup\{Norm\}\(v,\\nu\)=\\sum\_\{i=1\}^\{p\}\\left\[\\nu\_\{i\}\\geq 0\\land\\nu\_\{i\}^\{2\}=\\sum\_\{j=1\}^\{d\_\{i\}\}v\_\{i,j\}^\{2\}\\right\]\.In other words, the termNorm​\(u,ν\)\\textup\{Norm\}\(u,\\nu\)holds exactly whenνi=‖vi‖2\\nu\_\{i\}=\\\|v\_\{i\}\\\|^\{2\}for everyii\. We then define the polynomial lifting of the training objective as

f~x​\(α,v,ν\)=‖A​ν−b‖22\+∑i=1pαi​νi\.\\tilde\{f\}\_\{x\}\(\\alpha,v,\\nu\)=\\\|A\\nu\-b\\\|\_\{2\}^\{2\}\+\\sum\_\{i=1\}^\{p\}\\alpha\_\{i\}\\nu\_\{i\}\.Given a problem instancexxand a real\-valued thresholdτ∈ℝ\\tau\\in\\mathbb\{R\}, consider the polynomial FOL formula

Φx,τ\(α\)≜\(∀θ∈ℝd\)\(∃\(z,νθ,νz\)∈ℝd\+2​p\)\[gx\(θ\)≥τ∨\(Norm\(θ,νθ\)∧Norm\(z,νz\)∧f~x\(α,z,νz\)<f~x\(α,θ,νθ\)\)\]\.\\Phi\_\{x,\\tau\}\(\\alpha\)\\triangleq\(\\forall\\theta\\in\\mathbb\{R\}^\{d\}\)\(\\exists\(z,\\nu^\{\\theta\},\\nu^\{z\}\)\\in\\mathbb\{R\}^\{d\+2p\}\)\\left\[g\_\{x\}\(\\theta\)\\geq\\tau\\lor\\left\(\\textup\{Norm\}\(\\theta,\\nu^\{\\theta\}\)\\land\\textup\{Norm\}\(z,\\nu^\{z\}\)\\land\\tilde\{f\}\_\{x\}\(\\alpha,z,\\nu^\{z\}\)<\\tilde\{f\}\_\{x\}\(\\alpha,\\theta,\\nu^\{\\theta\}\)\\right\)\\right\]\.In words, this formula states that everyθ\\thetaeither has a validation loss at leastτ\\tau, or admits another pointzzwhich strictly smaller training loss\. Therefore

Φx,τ​\(α\)⇔every​θ∈𝒮⁡\(x,α\)​satisfies​gx​\(α\)≥τ\.\\Phi\_\{x,\\tau\}\(\\alpha\)\\Leftrightarrow\\textup\{every \}\\theta\\in\\mathcal\{S\}\(x,\\alpha\)\\textup\{ satisfies \}g\_\{x\}\(\\alpha\)\\geq\\tau\.Indeed, a training minimizer cannot satisfy the second disjunct, while every non\-minimizer admits a strictly better point because𝒮⁡\(x,α\)≠∅\\mathcal\{S\}\(x,\\alpha\)\\neq\\emptyset\. Consequently,

Φx,τ​\(α\)⇔infθ∈𝒮⁡\(x,α\)gx​\(θ\)≥τ,\\Phi\_\{x,\\tau\}\(\\alpha\)\\Leftrightarrow\\inf\_\{\\theta\\in\\mathcal\{S\}\(x,\\alpha\)\}g\_\{x\}\(\\theta\)\\geq\\tau,and therefore

𝕀⁡\(ℓαval​\(x\)≥τ\)=Φx,τ​\(α\)\.\\mathbb\{I\}\(\\ell\_\{\\alpha\}^\{\\textup\{val\}\}\(x\)\\geq\\tau\)=\\Phi\_\{x,\\tau\}\(\\alpha\)\.This one has one branch and two quantified blocks, withL=1L=1,K=2K=2,d1=dd\_\{1\}=d, andd2=d\+2​pd\_\{2\}=d\+2p\. Substituting to Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2), we have the final conclusion\. ∎

### E\.2Other Applications

We note that our main contribution is the an novelgeneralframework to establish statistical learning guarantees for a class of data\-driven algorithms design problems which admits piecewise polynomials structure, or even more general, the structure that can be converted into the form of Theorem[4\.2](https://arxiv.org/html/2608.17343#S4.Thmtheorem2)\. To further showcase the applicability of our general frameworks, in this section we will provide other applications\.

#### Data\-driven Cost\-sensitive SVM\.

Classification errors frequently have heterogeneous costs across classes or subpopulations, motivating cost\-sensitive extensions of support vector machines\. Rather than fixing these costs manually, we treat the group\-specific penalty vector as a data\-driven algorithm configuration learned across problem instances\. The hinge objective is piecewise polynomial: its polynomial representation changes whenever a training or validation example crosses its affine margin boundary\. Consequently, cost\-sensitive SVM provides a direct application of our connected\-sign\-cell framework, complementary to Weighted Group Lasso, which instead illustrates algebraic lifting\.

Fix integersn,m,p,d≥1n,m,p,d\\geq 1\. A problem instancex=\(Dxtr,Dxval\)x=\(D^\{\\textup\{tr\}\}\_\{x\},D^\{\\textup\{val\}\}\_\{x\}\)contains a training setDxtr=\{\(ax,j,yx,j,cx,j\)\}j=1nD\_\{x\}^\{\\text\{tr\}\}=\\\{\(a\_\{x,j\},y\_\{x,j\},c\_\{x,j\}\)\\\}\_\{j=1\}^\{n\}and a validation setDxval=\{\(ax,k′,yx,k′\)\}k=1mD\_\{x\}^\{\\text\{val\}\}=\\\{\(a^\{\\prime\}\_\{x,k\},y^\{\\prime\}\_\{x,k\}\)\\\}\_\{k=1\}^\{m\}\. Hereax,j,ax,k′∈ℝd,yx,j,yx,k′∈\{−1,1\},a\_\{x,j\},a^\{\\prime\}\_\{x,k\}\\in\\mathbb\{R\}^\{d\},\\quad y\_\{x,j\},y^\{\\prime\}\_\{x,k\}\\in\\\{\-1,1\\\},andcx,j∈\{1,…,p\}c\_\{x,j\}\\in\\\{1,\\dots,p\\\}identifies the cost group of training examplejj\. Let𝒜=\[C¯,C¯\]p⊂\(0,∞\)p\\mathcal\{A\}=\[\\underline\{C\},\\overline\{C\}\]^\{p\}\\subset\(0,\\infty\)^\{p\}be the domain of group\-specific penalty parameters, and letΘ=\[−B,B\]d\\Theta=\[\-B,B\]^\{d\}be the model\-parameter domain\. For a fixed regularization coefficientλ\>0\\lambda\>0, define

fx\(α,w\)=λ2∥w∥\+221n∑j=1nαcx,j\[1−yx,jax,j⊤w\]\+,f\_\{x\}\(\\alpha,w\)=\\frac\{\\lambda\}\{2\}\\\|\{\}w\\\|\{\}\_\{2\}^\{2\}\+\\frac\{1\}\{n\}\\sum\_\{j=1\}^\{n\}\\alpha\_\{c\_\{x,j\}\}\\left\[1\-y\_\{x,j\}a\_\{x,j\}^\{\\top\}w\\right\]\_\{\+\},where\[r\]\+=max⁡\{0,r\}\.\[r\]\_\{\+\}=\\max\\\{0,r\\\}\.We use the ordinary validation hinge loss

gx​\(w\)=1m​∑k=1m\[1−yx,k′​ax,k′⊤​w\]\+\.g\_\{x\}\(w\)=\\frac\{1\}\{m\}\\sum\_\{k=1\}^\{m\}\\left\[1\-y^\{\\prime\}\_\{x,k\}\{a^\{\\prime\}\_\{x,k\}\}^\{\\top\}w\\right\]\_\{\+\}\.The induced optimistic validation loss isℓαsvm​\(x\)=infw∈S⁡\(x,α\)gx​\(w\),\\ell\_\{\\alpha\}^\{\\text\{svm\}\}\(x\)=\\inf\_\{w\\in S\(x,\\alpha\)\}g\_\{x\}\(w\),where𝒮⁡\(x,α\)=arg⁡minw∈Θ​fx​\(α,w\)\.\\mathcal\{S\}\(x,\\alpha\)=\\arg\\min\_\{w\\in\\Theta\}f\_\{x\}\(\\alpha,w\)\.BecauseΘ\\Thetais compact andfxf\_\{x\}is continuous,S⁡\(x,α\)S\(x,\\alpha\)is nonempty\. Moreover, the quadratic regularizer makesfx​\(α,⋅\)f\_\{x\}\(\\alpha,\\cdot\)strongly convex, so the minimizer is unique\. The general framework, however, does not require uniqueness\.The boxΘ\\Thetacan be chosen sufficiently large that it does not modify the ordinary unconstrained SVM solution\. Indeed, ifw⋆w^\{\\star\}is the unconstrained minimizer, then

λ2∥w⋆∥≤22fx\(α,w⋆\)≤fx\(α,0\)≤C¯\.\\frac\{\\lambda\}\{2\}\\\|\{\}w^\{\\star\}\\\|\{\}\_\{2\}^\{2\}\\leq f\_\{x\}\(\\alpha,w^\{\\star\}\)\\leq f\_\{x\}\(\\alpha,0\)\\leq\\overline\{C\}\.Therefore∥w⋆∥2≤2​C¯λ,\\\|\{\}w^\{\\star\}\\\|\{\}\_\{2\}\\leq\\sqrt\{\\frac\{2\\overline\{C\}\}\{\\lambda\}\},so it suffices to takeB≥2​C¯λ\.B\\geq\\sqrt\{\\frac\{2\\overline\{C\}\}\{\\lambda\}\}\.

For each training example, define the affine margin polynomialhx,jf\(w\)=1−yx,jax,j⊤w,j=1,…,n\.h\_\{x,j\}^\{f\}\(w\)=1\-y\_\{x,j\}a\_\{x,j\}^\{\\top\}w,\\quad j=1,\\dots,n\.LetTtrT\_\{\\text\{tr\}\}be a uniform upper bound, overxx, on the number of sign conditions of\{hx,1f,…,hx,nf\}\\\{h\_\{x,1\}^\{f\},\\dots,h\_\{x,n\}^\{f\}\\\}realized onΘ\\Theta\. Similarly, definehx,kg\(w\)=1−yx,k′ax,k′⊤w,k=1,…,m,h\_\{x,k\}^\{g\}\(w\)=1\-y^\{\\prime\}\_\{x,k\}\{a^\{\\prime\}\_\{x,k\}\}^\{\\top\}w,\\quad k=1,\\dots,m,and letTvalT\_\{\\text\{val\}\}uniformly bound the number of realized validation sign conditions\. We then have the following result, which establishes generalization guarantee for the problem of data\-driven cost\-sensitive SVM\.

###### Corollary E\.1\(Data\-driven cost\-sensitive SVM\)\.

Letℒsvm=\{ℓαsvm:𝒳→ℝ∣α∈𝒜\}\.\\mathcal\{L\}\_\{\\text\{svm\}\}=\\\{\\ell\_\{\\alpha\}^\{\\text\{svm\}\}:\\mathcal\{X\}\\to\\mathbb\{R\}\\mid\\alpha\\in\\mathcal\{A\}\\\}\.We then havePdim​\(ℒsvm\)=O⁡\(p⁡\(n\+m\)\+p​d2​\(n\+log⁡\(d\+m\+2\)\)\)\.\\text\{Pdim\}\(\\mathcal\{L\}\_\{\\text\{svm\}\}\)=O\\left\(p\(n\+m\)\+pd^\{2\}\\left\(n\+\\log\(d\+m\+2\)\\right\)\\right\)\.

###### Proof of Corollary[E\.1](https://arxiv.org/html/2608.17343#A5.Thmtheorem1)\.

Fix an instancexx\. The training objective has thennaffine boundary polynomialshx,1f,…,hx,nf\.h\_\{x,1\}^\{f\},\\dots,h\_\{x,n\}^\{f\}\.For a realized sign conditionσ∈\{−1,0,1\}n,\\sigma\\in\\\{\-1,0,1\\\}^\{n\},we defineI\+​\(σ\)=\{j∈\{1,…,n\}:σj=1\}\.I\_\{\+\}\(\\sigma\)=\\\{j\\in\\\{1,\\dots,n\\\}:\\sigma\_\{j\}=1\\\}\.On the realization ofσ\\sigma, the hinge terms indexed byj∉I\+​\(σ\)j\\notin I\_\{\+\}\(\\sigma\)vanish, while the remaining hinge terms equal their affine arguments\. Therefore, the active training piece is

Fx,σ\(α,w\)=λ2∥w∥\+221n∑j∈I\+​\(σ\)αcx,j\(1−yx,jax,j⊤w\)\.F\_\{x,\\sigma\}\(\\alpha,w\)=\\frac\{\\lambda\}\{2\}\\\|\{\}w\\\|\{\}\_\{2\}^\{2\}\+\\frac\{1\}\{n\}\\sum\_\{j\\in I\_\{\+\}\(\\sigma\)\}\\alpha\_\{c\_\{x,j\}\}\\left\(1\-y\_\{x,j\}a\_\{x,j\}^\{\\top\}w\\right\)\.This is a polynomial of total degree at most two in\(α,w\)\(\\alpha,w\)\. In particular, the only mixed terms have the formαcx,j​wr,\\alpha\_\{c\_\{x,j\}\}w\_\{r\},which are bilinear\. It follows thatfxf\_\{x\}has piecewise\-polynomial complexity\(Mf,Tf,Δf\)=\(n,Ttr,2\)\(M\_\{f\},T\_\{f\},\\Delta\_\{f\}\)=\(n,T\_\{\\text\{tr\}\},2\), whereTtr≤3nT\_\{\\text\{tr\}\}\\leq 3^\{n\}\. Similarly, fo the validation objective, we conclude thatgxg\_\{x\}has the piecewise polynomial complexity\(Mg,Tg,Δg\)=\(m,Tval,1\)\(M\_\{g\},T\_\{g\},\\Delta\_\{g\}\)=\(m,T\_\{\\text\{val\}\},1\), whereTval≤3mT\_\{\\textup\{val\}\}\\leq 3^\{m\}\. Besides, we note thatΔf,g=max⁡\{1,Δf,Δg\}=2,\\Delta\_\{f,g\}=\\max\\\{1,\\Delta\_\{f\},\\Delta\_\{g\}\\\}=2,andMtot=Mf\+Mg\+Tf\+d=n\+m\+Ttr\+d\.M\_\{\\text\{tot\}\}=M\_\{f\}\+M\_\{g\}\+T\_\{f\}\+d=n\+m\+T\_\{\\text\{tr\}\}\+d\.Substituting to Theorem[6\.1](https://arxiv.org/html/2608.17343#S6.Thmtheorem1), we have the final conclusion\. ∎

#### Multi\-penalty ridge regression

Multi\-parameter ridge regularization uses several penalties to promote different structural properties of the fitted solution\. Let

fx​\(α,θ\)=‖A​θ−b‖22\+∑i=1pαi​‖Di​θ‖22,f\_\{x\}\(\\alpha,\\theta\)=\\\|A\\theta\-b\\\|\_\{2\}^\{2\}\+\\sum\_\{i=1\}^\{p\}\\alpha\_\{i\}\\\|D\_\{i\}\\theta\\\|\_\{2\}^\{2\},and letgx​\(α,θ\)=‖A′​θ−b′‖22g\_\{x\}\(\\alpha,\\theta\)=\\\|A^\{\\prime\}\\theta\-b^\{\\prime\}\\\|\_\{2\}^\{2\}, whereα∈𝒜=\[αmin,αmax\]p\\alpha\\in\\mathcal\{A\}=\[\\alpha\_\{\\min\},\\alpha\_\{\\max\}\]^\{p\}andθ∈Θ=\[θmin,θmax\]d\\theta\\in\\Theta=\[\\theta\_\{\\min\},\\theta\_\{\\max\}\]^\{d\}are box like hyperparameters and parameters domain\. Letℒridge\\mathcal\{L\}\_\{\\textup\{ridge\}\}denote the corresponding optimistic validation\-loss class\. We then have the following result, which establishes the pseudo\-dimension upper bound for the problem of tuning regularization parameters in multi\-penalty ridge regression\.

###### Corollary E\.2\(Pseudo\-dimension for ridge regression\)\.

We have𝑂𝑃𝐸𝑁Pdim​\(ℒridge\)=𝒪⁡\(p​d2​log⁡d\)\)\.\\text\{Pdim\}\(\\mathcal\{L\}\_\{\\textup\{ridge\}\}\)=\\mathcal\{O\}\(pd^\{2\}\\log d\)\)\.

###### Proof of Corollary[E\.2](https://arxiv.org/html/2608.17343#A5.Thmtheorem2)\.

It is clearly that the complexity of the training and validation objectives are\(Mf,Tf,δf\)=\(0,1,3\)\(M\_\{f\},T\_\{f\},\\delta\_\{f\}\)=\(0,1,3\), and\(Mg,Tg,Δg\)=\(0,1,2\)\(M\_\{g\},T\_\{g\},\\Delta\_\{g\}\)=\(0,1,2\), respectively\. Therefore applying Theorem[6\.1](https://arxiv.org/html/2608.17343#S6.Thmtheorem1)gives us the final conclusion\. ∎