Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen Abstract Data-driven algorithm design automates hyperparameter tuning, but its statistical foundations remain limited because model performance can depend on hyperparameters in implicit and highly non-smooth ways. Existing guarantees focus on the simple case of a one-dimensional (scalar) hyperparameter. This leaves the practically important, multi-dimensional hyperparameter tuning setting unresolved. We address this open question by establishing the first general framework for establishing generalization guarantees for tuning multi-dimensional hyperparameters in data-driven settings. Our approach strengthens the generalization guarantee framework for semi-algebraic function classes by exploiting tools from real algebraic geometry, yielding sharper, more broadly applicable guarantees. We then extend the analysis to hyperparameter tuning using the validation loss under minimal assumptions, and derive improved bounds when additional structure is available. Finally, we demonstrate the scope of the framework with new learnability results, including data-driven weighted group lasso and weighted fused lasso. 1 Introduction Hyperparameter tuning ( 1 ) is a cornerstone of the modern machine learning paradigm, often determining a model’s performance. Despite its critical role, this tuning process is often regarded more as an art than a rigorous scientific endeavor. In practice, the vast majority of practitioners rely on naive grid search, which discretizes continuous hyperparameter spaces and selects the candidate that yields the best empirical results. While straightforward, this exhaustive approach is theoretically unprincipled and offers no performance guarantees. To automate this tedious task, recent literature has introduced computational techniques such as Bayesian optimization and random search. While empirically effective, these methods lack robust theoretical foundations or rely on restrictive assumptions. For instance, Bayesian optimization ( 12 ; 28 ) generally assumes that a model’s performance can be approximated as a noisy evaluation of a smooth, expensive function. In reality, this assumption could fail due to the volatile loss landscapes of complex models. Furthermore, these methods introduce their own complexity, requiring the selection of meta-hyperparameters, such as the acquisition function, kernel type, and bandwidth. Similarly, other approaches, including random search and spectral methods ( 13 ; 18 ) , often provide theoretical guarantees only for discrete, finite grids. Meanwhile, advanced resource-allocation strategies like Hyperband ( 21 ) , which are effective at accelerating search via early stopping, primarily optimize computational efficiency for a fixed problem instance over discrete search spaces. Consequently, they do not characterize the fundamental theoretical complexity of identifying optimal continuous parameters. This gap highlights the pressing need for a rigorous theoretical foundation for hyperparameter tuning. To address this gap, the data-driven algorithm design framework models the hyperparameter tuning problem as a statistical learning problem over an unknown, application-specific distribution \mathcal{D} of problem instances ( 5 ; 17 ) . From a finite set of training instances drawn from \mathcal{D} , we seek to identify the hyperparameter configuration that is provably guaranteed to perform well on future, un seen instances drawn from the same distribution. To this end, we define the loss function \ell_{*}(x) via a bi-level optimization structure: \displaystyle\ell_{*}(x)=\inf_{\theta\in\mathcal{S}(x,*)}g(x,*,\theta), (1) \displaystyle\textup{where \,\,} \displaystyle\mathcal{S}(x,*)\triangleq\arg\min_{\theta\in\Theta}f(x,*,\theta). Here, f represents the training objective (i.e, the optimization surrogate), while g represents the validation objective (i.e., the target metric). For instance, consider the linear regression problem in which we would like to tune the (one-dimensional) ridge regularization parameter. The problem instance can be represented as x=(A,b,A^{\prime},b^{\prime}) containing both the training set (A,b) and the validation set (A^{\prime},b^{\prime}) , which could be extracted from the available data. The training objective f(x,*,\theta) explicitly includes the regularization term \|A\theta-b\|_{2}^{2}+*\|\theta\|_{2}^{2} to stabilize the solution, whereas the validation objective g(x,*,\theta)=\|A^{\prime}\theta-b^{\prime}\|_{2}^{2} evaluates performance with out the penalization. In this context, the regularization parameter * shapes the optimization landscape of the training objective f , but affects the validation objective g only implicitly through the learned parameters. Analyzing this implicit dependency is the core challenge that we need to overcome. The approach we take in this paper leverages statistical learning theory to bound the learning-theoretic complexity of the family of loss functions induced by the hyperparameters. Formally, it behooves us to analyze the learning-theoretic complexity (e.g., pseudo-dimension) of the function class \mathcal{L}=\{\ell_{*}:\mathcal{X}\rightarrow[-H,H]\mid*\in\mathcal{A}\} , where \mathcal{A} is the hyperparameter space and H is a positive-valued bound of the loss functions. The analysis in 2 leverages the observation that for many problems of interest, given the problem instance x , f_{x}(*,\theta)\triangleq f(x,*,\theta) admits a piecewise polynomial structure with respect to * and \theta (see Definition 3.1 and Figure 1 for a simple illustration). This structural assumption is ubiquitous: it has been established for a wide range of applications in both classical learning theory ( 9 ; 23 ; 8 ) as well as data-driven algorithm design problems ( 3 ; 6 ; 24 ; 14 ) . On the downside, the result from 2 suffers from numerous limitations that hinder its general applicability. First, their analysis is strictly confined to one-dimensional hyperparameters (i.e, \mathcal{A}=\mathbb{R} ) due to ad-hoc geometric arguments (e.g., oscillations, monotonic curves). In reality, many ML/AI pipelines rely on stacking multiple regularization terms to achieve the desired effects; the most popular is the elastic net, which combines L1 (lasso) and L2 (ridge) penalties with different hyperparameter weights. However, this geometric approach breaks down in this multi-dimensional setting ( *\in\mathbb{R}^{p} ), where critical sets become high-dimensional manifolds rather than simple curves. Second, their results are limited to the simple setting where the training and evaluation objectives are identical (i.e., f\equiv g ). For the ridge regression illustrated above, this requirement imposes that the training and validation sets to be identical, i.e., (A,b)=(A^{\prime},b^{\prime}) . This restriction violates the fundamental principles of model selection, which require the training and validation sets to be well separated to prevent overfitting and produce an unbiased estimate of the performance. Finally, their approach requires strong regularity assumptions on the boundaries of the piecewise structure (e.g., ELICQ conditions in 2 ). These limitations motivate the development of the general model-theoretic framework we present in this paper. Contributions. In this work, we provide an affirmative answer to the open question posed by 2 by establishing the concrete sample complexity for the function class \mathcal{L}=\{\ell_{*}:\mathcal{X}\rightarrow[-H,H]|*\in\mathcal{A}\} , where \mathcal{A}\subset\mathbb{R}^{p} with p\geq 1 . Our contributions are as follows: • We establish in Theorem 4.1 a general tool that connects the learning-theoretic complexity of a function class \mathcal{L} to the logical complexity of its functions \ell_{*} . Specifically, we show that if the loss function can be described by a polynomial first-order logic , its pseudo-dimension is bounded by the complexity of the quantifier elimination process ( 10 ) . • Second, we apply this framework to the training-loss setting (i.e., f\equiv g ) studied by 2 . We show in Theorem 5.1 that if the objective f(x,*,\theta) admits a piecewise polynomial structure for any given problem instance x , the induced loss \ell_{x}(*)=\min_{\theta\in\Theta}f(x,*,\theta) is expressible as a polynomial FOL formula. This allows us to derive the first generalization guarantees for multi-dimensional hyperparameters ( *\in\mathbb{R}^{p} ), effectively resolving the main open question in prior work. • Third, we extend our analysis to the general bi-level validation tuning setting ( f\neq g ). We prove in Theorem 6.1 that validation loss functions are definable in FOL, ensuring learnability under minimal assumptions. • Forth, we show in Section 7 how we can exploit the optimal solution path structure to improve the bounds. • Finally, we demonstrate in Section 8 the versatility of our framework by establishing the first learnability guarantees for two new applications: data-driven tuning for weighted group LASSO and weighted fused LASSO, some of which go beyond the piecewise polynomial assumptions . Technical challenges. The key challenge in our setting is that the loss function \ell_{*}(x) is defined implicitly via a bi-level optimization problem involving non-convex, non-smooth objectives. Consequently, the dependence of \ell_{*}(x) can be highly volatile, exhibiting discontinuities and potentially singularities. To overcome these challenges, we adopt a model-theoretic perspective using tools from real algebraic geometry. Instead of analyzing the local geometry of the solution paths (i.e., \mathcal{S}(x,*)=\arg\min_{\theta\in\Theta}f(x,*,\theta) ), we view the optimality conditions of the inner problem as a predicate in polynomial first-order logic (FOL). After that, we use quantifier-elimination technique, transforming polynomial FOLs to a quantifier-free formula (QFF), of which the computation can then be described as a Goldberg-Jerrum (GJ) algorithm ( 16 ; 7 ) . This allows us to use the GJ framework to establish the generalization guarantee for the function class of interest Notations. We denote {\text{sign}}(t)=0 if t=0 , 1 if t>0 , and -1 if t<0 . For z\in\mathbb{R}^{k} , we denote \mathbb{R}[z] the polynomial ring in z over \mathbb{R} , i.e., P(z)\in\mathbb{R}[z] is a (multi-variate) polynomial of z . We denote \textup{deg}(P) the degree of the polynomial P . For a multiple inputs functions h(z_{1},z_{2}) , given a fixed component, says z_{1} , we denote h_{z_{1}}(z_{2})\triangleq h(z_{1},z_{2}) is an induced function where we treat z_{1} as fixed and z_{2} as the only variables. 1.1 Related Works Data-driven hyperparameter tuning , initiated by ( 5 ; 17 ) , frames hyperparameter tuning as a multi-task learning problem. This data-driven perspective has demonstrated significant empirical success across diverse fields, including low-rank approximation ( 22 ; 20 ) , accelerated linear system solvers ( 27 ; 24 ) , and branch-and-cut strategies for (mixed integer) linear programming ( 4 ) , among others. Theoretical analysis for data-driven hyperparameter tuning. The practical success of data-driven hyperparameter tuning has motivated a line of theoretical work aimed at establishing rigorous generalization guarantees ( 3 ; 4 ; 7 ; 6 ) . Analyzing these problems is generally more challenging than standard statistical learning theory due to the volatile, non-smooth dependence of the loss \ell_{x}(*) on the hyperparameters * . Most prior guarantees focus on settings where the algorithm’s behavior is determined solely by * , typically by exploiting the piecewise structure of \ell_{x}(*) w.r.t. * . Recently, 2 provided the first general framework for the harder case where \ell_{x}(*) involves an inner optimization over model parameter \theta . However, as discussed, their results are restricted to one-dimensional hyperparameters and single-level objectives ( f\equiv g ). Our work directly extends this line of inquiry. 2 Preliminaries 2.1 Backgrounds on Learning Theory We recall the notion of pseudo-dimension, a learning-theoretic complexity for a real-valued function class. Definition 2.1 (Pseudo-dimension, 25 ) . Consider a real-valued function class \mathcal{L}=\{\ell_{*}:\mathcal{X}\rightarrow\mathbb{R}\mid*\in\mathcal{A}\} parameterized by *\in\mathcal{A} . Given a set of inputs S=(x_{1},\dots,x_{N})\subset\mathcal{X} , we say that S is shattered by \mathcal{L} if there exists a set of real-valued threshold t_{1},\dots,t_{N}\in\mathbb{R} such that \left|\{({\text{sign}}(\ell_{*}(x_{1})-t_{1}),\dots,{\text{sign}}(\ell_{*}(x_{N})-t_{N}))\mid\ell_{*}\in\mathcal{L}\}\right|=2^{N} . The pseudo-dimension of \mathcal{L} , denoted \text{Pdim}(\mathcal{L}) , is the maximum size N of an input set that \mathcal{L} can shatter. A standard result in learning theory states that a real-valued function class with bounded pseudo-dimension is Probably Approximately Correct (PAC)-learnable with empirical risk minimization (ERM). Theorem 2.2 ( 25 ) . Consider a real-valued function class \mathcal{L}=\{\ell_{*}:\mathcal{X}\rightarrow[-H,H]\mid*\in\mathcal{A}\} parameterized by *\in\mathcal{A} . Assume that \text{Pdim}(\mathcal{L}) is finite. Then given \epsilon>0 and \delta\in(0,1) , for any N\geq N(\epsilon,\delta) , where N(\epsilon,\delta)=\mathcal{O}\left(\frac{H^{2}}{\epsilon^{2}}(\text{Pdim}(\mathcal{L})+\log(1/\delta))\right) , with probability at least 1-\delta over the draw of S=(x_{1},\dots,x_{N})\sim\mathcal{D}^{N} , where \mathcal{D} is a distribution over \mathcal{X} , we have \mathbb{E}_{x\sim\mathcal{D}}[\ell_{\hat{*}}(x)]\leq\inf_{*\in\mathcal{A}}\mathbb{E}_{x\sim\mathcal{D}}[\ell_{*}(x)]+\epsilon. Here \hat{*}\in\arg\min_{*\in\mathcal{A}}\sum_{x\in S}\ell_{*}(x) is the ERM minimizer w.r.t. the set of instances S . 2.2 First-order Formula and Quantifier Elimination In this section, we will present the necessary background for quantifier elimination, a key component of our analysis. First, we introduce the notions of first-order formula . Definition 2.3 (First-order formula, quantified/free variables, and polynomial first-order logic ( 26 ) ) . A first-order formula (FOL) \Phi(*) admits the form: (Q_{1}\theta^{[1]}\in\mathbb{R}^{d_{1}})\ldots(Q_{K}\theta^{[K]}\in\mathbb{R}^{d_{K}})P(*,\theta^{[1]},\ldots,\theta^{[K]}), (2) where 1. Each Q_{k} is one of the quantifiers \exists or \forall . The sequence \{Q_{k}\}_{k=1}^{K} alternates between \exists and \forall and we denote K as the number of quantifier alternations. 2. \theta^{[1]},\theta^{[2]},\ldots,\theta^{[K]} are called the quantified variables, while *\in\mathbb{R}^{p} is called the free variable. 3. P(*,\theta^{[1]},\theta^{[2]},\ldots,\theta^{[K]}) is a boolean combination of atomic predicates of the form: P_{j}(*,\theta^{[1]},\theta^{[2]},\ldots,\theta^{[K]})\,\chi_{j}\,0, where \chi_{j}\in\{>,\geq,<,\leq,=,\neq\} is relational operator. A FOL \Phi is a polynomial FOL if each P_{j} is a polynomial of * and \theta^{[1]},\dots,\theta^{[K]} . Essentially, a polynomial FOL is a logical statement built from three simple components: polynomial (in)equalities, Boolean operators (e.g., AND and OR), and quantifiers (e.g., ‘there exists’ \exists and ‘for all’ \forall ). The variables linked internally with the quantifiers (in our application is the parameters \theta we optimize over) are called quantified variables , and the ones that are external inputs (in our application is the hyperparameters * we tune) are called free variables . We now introduce the notion of quantifier-free formula , which is an FOL that has no quantified variables. Definition 2.4 (Quantifier-free formula) . A polynomial FOL is a quantifier-free formula (QFF) if it has no quantified variables. In other words, it is a boolean combination of atomic predicates of the form P_{j}(*)\chi_{j}0 , where P_{j} is a polynomial of *\in\mathbb{R}^{p} and \chi_{j}\in\{>,\geq,<,\leq,=,\neq\} . Example 1 . We provide two examples of polynomial FOL for illustration purposes. Let *\in\mathbb{R}^{p} and \theta\in\mathbb{R}^{d} , then: • The formula \Phi(*)=(\forall\theta\in\mathbb{R}^{p})(\sum_{i=1}^{p}*_{i}^{2}-\sum_{j=1}^{d}\theta_{j}^{2}\geq 0) is a polynomial FOL, where \theta are quantified variables and * are free variables. In this case, there is only one quantifier alternation (e.g., \forall\theta\in\mathbb{R}^{n} ), and therefore the number of quantifier alternations of \Phi is K=1 . Furthermore, there is only one atomic predicate P(*,\theta)\geq 0 , where P(*,\theta)=\sum_{i=1}^{p}*_{i}^{2}-\sum_{j=1}^{d}\theta_{j}^{2} and since P is a polynomial of * and \theta , \Phi is a polynomial FOL. • The formula \Phi^{\prime}(*)=(\sum_{i=1}^{p}*_{i}^{2}-1\geq 0) is a quantifier-free polynomial FOL. Finally, the following result asserts that we can transform a polynomial FOL to a polynomial QFF with a bounded number of atomic predicates and a maximum polynomial degree of those atomic predicates. Theorem 2.5 (Quantifier elimination algorithm, 10 ) . Given a polynomial FOL \Phi as in ( 2 ), there exists an equivalent polynomial QFF \Psi consisting of (polynomial) atomic predicates in the free variables *\in\mathbb{R}^{p} . Let M be the number of atomic predicates in \Phi , and \Delta be their maximum degree. Then the formula \Psi(*) satisfies the following structural complexities: 1. Predicate complexity I : the number of distinct atomic polynomials appearing in \Psi(*) is at most I\leq M^{\prod_{k=1}^{K}(d_{k}+1)}\cdot\Delta^{\mathcal{O}(p)\cdot\prod_{k=1}^{K}(d_{k}+1)}. 2. Degree complexity \Delta_{QE} : the degree of these atomic polynomials is at most \Delta_{QE}\leq\Delta^{\mathcal{O}(p)\cdot\prod_{k=1}^{K}(d_{k}+1)}. Later, we will see that the computation of a polynomial QFF can be described by a GJ algorithm, which is the key idea of our analysis. 3 Problem Settings We follow the setting from 2 by considering a data-driven framework involving three fundamental spaces: (1) a problem instance space \mathcal{X}\subseteq\mathbb{R}^{q} , (2) a hyperparameter space \mathcal{A}\subseteq\mathbb{R}^{p} , and (3) a model parameter space \Theta\subseteq\mathbb{R}^{d} . For simplicity, we assume \mathcal{A}=[*_{\min},*_{\max}]^{p} and \Theta=[\theta_{\min},\theta_{\max}]^{d} . For any problem instance x\in\mathcal{X} , we evaluate the performance of a model parameterized by \theta\in\Theta and hyperparameters *\in\mathcal{A} using two distinct objective functions: • Training objective f:\mathcal{X}\times\mathcal{A}\times\Theta\rightarrow[-H,H] : the surrogate loss minimized by the algorithm, and • Validation objective g:\mathcal{X}\times\mathcal{A}\times\Theta\rightarrow[-H,H] : the target metric used to evaluate the quality of the solution. Here, H is a boundedness threshold. The induced loss \ell_{*}(x) measures the performance of the model on the problem instance x given hyperparameters * , defined via the bi-level structure in ( 1 ). Notice that we adopt the optimistic bi-level optimization formulation ( 15 ) , which is standard in the literature to ensure the validation is well-defined then lower-level set \mathcal{S}(x,*) is not a singleton. Objectives. We assume there is an application-specific, unknown problem distribution \mathcal{D} over \mathcal{X} . The goal of data-driven hyperparameter tuning is to find a value *^{*} that minimizes the expected loss *^{*}\in\arg\min_{*\in\mathcal{A}}\mathbb{E}_{x\sim\mathcal{D}}[\ell_{*}(x)]. Since \mathcal{D} is unknown, we observe N training instances S=\{x_{1},\dots,x_{N}\}\sim\mathcal{D}^{N} and minimize the empirical risk \hat{*}(S)\in\arg\min_{*\in\mathcal{A}}\frac{1}{N}\sum_{i=1}^{N}\ell_{*}(x_{i}). Our primary theoretical goal is to establish sample complexity guarantees for this learning problem. Exploiting results Theorem 2.2 , it suffices to study the induced function class \mathcal{L}=\{\ell_{*}:\mathcal{X}\rightarrow[-H,H]\mid*\in\mathcal{A}\} , and bound its pseudo-dimension \text{Pdim}(\mathcal{L}) . f_{(1)}(\boldsymbol{z}) f_{(-1)}(\boldsymbol{z}) f_{(0)}(\boldsymbol{z}) Figure 1 : A simple illustration of the piecewise polynomial structure. Here, the set of boundary polynomials \mathbb{H}=\{h_{1}\} , where h_{1}(z)=z_{1}^{2}+z_{2}^{2}-4 . In the region \{z\in\mathbb{R}^{2}\mid h_{1}(z)>0\} (i.e, the region outside the circle, the sign pattern \boldsymbol{\sigma}(z)=(1)\in\{-1,0,1\}^{1} ), the function f(z) admits the polynomial form f_{(-1)}(z)=z_{1}-z_{2} . Similarly, in the region \{z\in\mathbb{R}^{2}\mid h_{1}(z)<0\} inside the circle (i.e., the sign pattern \boldsymbol{\sigma}(z)=(-1) ), we have f(z)=f_{(-1)}(z)=z_{1}+z_{2} . Finally, in the region where \{\boldsymbol{z}\in\mathbb{R}^{2}\mid h_{1}(z)=0\} (i.e., the boundary of the circle, \boldsymbol{\sigma}(z)=(0) ), f(z)=f_{(0)}(z)=z_{1}^{3} . Note that all pieces are polynomials in z , and the complexity of the function f(z) is (1,3,\Delta) , where \Delta=\max\{\textup{deg}(h_{1}),\textup{deg}(f_{(0)}),\textup{deg}(f_{(-1)}),\textup{deg}(f_{(1)})\}=3 . Structural assumption. We focus on the case where f and g admits piecewise polynomial structure , formally defined as follows. Definition 3.1 (Piecewise polynomial function ( 2 ) ) . A real-valued function f admits a piecewise polynomial structure with complexity (M_{f},T_{f},\Delta_{f}) if there exists a set of boundary polynomials \mathbb{H}=\{h_{1},\dots,h_{M_{f}}\} and a set of value polynomials \mathbb{F}=\{f_{\boldsymbol{\sigma}}\}_{\boldsymbol{\sigma}\in\Sigma_{f}}\subset\mathbb{R}[z] , where \Sigma_{f}\subseteq\{-1,0,1\}^{M_{f}} and |\Sigma_{f}|\leq T_{f} , both with polynomial degrees at most \Delta , such that for any z , we have f(z)=f_{\boldsymbol{\sigma}(z)}(z) , where \boldsymbol{\sigma}(z)\in\Sigma_{f} is the sign pattern of z with respect to the set of functions \mathbb{H} , i.e., \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 3.2 (Structural assumption) . Given any problem instance x , the dual parameter-dependent training objective f_{x}(*,\theta)\triangleq f(x,*,\theta) and dual parameter-dependent validation objective g_{x}(*,\theta)\triangleq g(x,*,\theta) admits piecewise polynomial structure (as functions of * and \theta ) with complexity (M_{f},T_{f},\Delta_{f}) and (M_{g},T_{g},\Delta_{g}) (independent of the problem instance x ), respectively. Moreover, the set \mathcal{S}(x,*) of minimizes of f(x,*,\cdot) is non-empty, for all (x,*) . Remark 3.3 (Ubiquity of structure) . As noted by 2 , this structural assumption is robust and ubiquitous. it has been established for a wide range of applications in both classical learning theory ( 9 ; 23 ; 8 ) and data-driven algorithm design problems ( 3 ; 6 ; 24 ; 14 ) . While 2 initiated the formal study of this setting, their results are restricted to one-dimensional hyperparameter case ( \mathcal{A}\subset\mathbb{R} ) and the single-level setting ( f\equiv g ). We now present our general results which fully eliminate these two restrictions. 4 A General Learning-theoretic Complexity Framework via First-Order Logic In this section, we present a general result that bounds the pseudo-dimension of a function class \mathcal{F}:=\{f_{*}:\mathcal{X}\rightarrow[-H,H]\mid*\in\mathcal{A}\subseteq\mathbb{R}^{p}\} . The next theorem serves as the engine of our analysis, converting logical definability into statistical learnability. Its proof is presented in Appendix B . Theorem 4.1 (Pseudo-dimension bound) . Consider a class of functions \mathcal{F}:=\{f_{*}:\mathcal{X}\subseteq\mathbb{R}^{q}\to\mathbb{R}\mid*\in\mathcal{A}\} , where \mathcal{A}=[*_{\textup{min}},*_{\textup{max}}]^{p}\subset\mathbb{R}^{p} . Suppose that for any fixed instance x\in\mathcal{X} and threshold t\in\mathbb{R} , the boolean value \mathbb{I}(f_{*}(x)\geq t) is equivalent to a polynomial FOL \Phi_{x,t}(*) (cf. Definition 2.3 ). Assume that for any problem instance x and threshold t : • \Phi_{x,t} involves K blocks of quantifiers with variable dimensions (d_{1},\dots,d_{K}) • The number of polynomials appearing in \Phi_{(x,t)} and their maximum degree are uniformly bounded by M and \Delta Then the pseudo-dimension \text{Pdim}(\mathcal{F}) is upper-bounded by O\left(p\prod_{k=1}^{K}(d_{k}+1)\log M+p^{2}\prod_{k=1}^{K}(d_{k}+1)\log\Delta\right). Comparison to existing works. To the best of our knowledge, 16 is the only work in the literature investigating the pseudo-dimension of the polynomial FOLs. 16 proved a bound O\big(2^{O(K)}p(p+q)\prod_{k=1}^{K}d_{k}\left(\log M+\log\Delta\right)\big), and our Theorem 4.1 is finer than this bound. In particular, we remove the dependency on the data dimension q and a factor p in front of \log M . This improvement is significant, for example, when the function class contains piecewise polynomial functions with exponential pieces/boundaries or when the data dimension is bigger than the number of tuning parameters q\gg p . Theorem 4.1 applies to many practical learning situations. The only condition we need to verify is that the objective functions f and g can be described as polynomials and/or polynomial FOLs. The class of functions that admit description with polynomials is precisely the set of semi-algebraic functions. We provide interested readers with more details about semi-algebraic functions in Appendix C . In fact, many functions used in the learning context are semi-algebraic because this class does not only contain piecewise polynomial functions (cf. Definition 3.1 ), but also many others such as \|x\|_{p},p\in\mathbb{N},p\geq 2 or well-known sparse regularisations such as \ell_{2}/\ell_{1} ratio, group LASSO, which are not instances of Definition 3.1 (also see Appendix C for more details). Therefore, the scope of Theorem 4.1 can go up to the set of semi-algebraic functions. In Section 5 and Section 6 , we demonstrate applications of Theorem 4.1 for f and g being piecewise polynomial functions and address an open question posed in ( 2 ) . In addition, we also demonstrate an example of a learning problem whose functions are semi-algebraic but not covered by Section 5 and Section 6 : hyper-parameter tuning for the weighted group LASSO in Section 8.1 . 5 Data-driven Tuning via Training Objective In this section, we first analyze the setting where the hyperparameter * is tuned to minimize the training objective directly (i.e., the case where f\equiv g ). In this scenario, for a fixed problem instance x and hyperparameter * , the loss \ell_{*}(x) is defined implicitly as the optimal value of the training problem: \ell_{*}(x)=\min_{\theta\in\Theta}f(x,*,\theta). Recall that from Assumption 3.2 , for any given problem instance x , f_{x}(*,\theta)\triangleq f(x,*,\theta) admits piecewise polynomial structure (Definition 3.1 ) with complexity (M_{f},T_{f},\Delta_{f}) . Under such assumption, the following result establishes a pseudo-dimension upper-bound for the function class \mathcal{L} induced by \ell_{*}:\mathcal{X}\rightarrow[-H,H] when varying *\in\mathcal{A}=[*_{\textup{min}},*_{\textup{max}}]^{p}\subset\mathbb{R}^{p} . Theorem 5.1 (Pseudo-dimension – Training loss) . Let \mathcal{A}=[*_{\textup{min}},*_{\textup{max}}]^{p} and \Theta=[\theta_{\textup{min}},\theta_{\textup{max}}]^{d} . Suppose that for any instance x , the training objective f_{x}(*,\theta)\triangleq f(x,*,\theta) for (*,\theta)\in\mathcal{A}\times\Theta admits a piecewise polynomial structure (cf. Definition 3.1 ) with complexity (M_{f},T_{f},\Delta_{f}) . Then, the pseudo-dimension of the function class \mathcal{L}=\{\ell_{*}:\mathcal{X}\rightarrow[-H,H]\mid*\in\mathcal{A}\} , where \ell_{*}(x)=\min_{\theta\in\Theta}f(x,*,\theta) , is bounded by \text{Pdim}(\mathcal{L})=\mathcal{O}(pd\log(M_{f}+T_{f}+d)+p^{2}d\log\Delta_{f}). Proof. To apply Theorem 4.1 , given a problem instance x and a real-valued threshold t , our goal is to construct a polynomial FOL formula \Phi_{x,t}(*) equivalent to \mathbb{I}(\ell_{*}(x)\geq t) . Since \ell_{*}(x)=\min_{\theta\in\Theta}f_{x}(*,\theta) is a minimization over \Theta , the condition \ell_{*}(x)\geq t is equivalent to stating that for all parameter \theta\in\Theta , the function value f_{x}(*,\theta) is greater or equal than t , and \Phi_{x,t}(*) is defined as \displaystyle\Phi_{x,t}(*) \displaystyle\triangleq(\forall\theta\in\mathbb{R}^{d})[(\theta\in\Theta)\Rightarrow f_{x}(*,\theta)\geq t] \displaystyle=(\forall\theta\in\mathbb{R}^{d})[\neg(\theta\in\Theta)\lor(f_{x}(*,\theta)\geq t)]. Here, we use the logical identity (A\Rightarrow B)=(\neg A\lor B) (i.e., not A or B ). It is now sufficient to apply Theorem 4.1 . Details are in Appendix D . ∎ Combining Theorem 5.1 with Theorem 2.2 , we could establish the sample complexity guarantee for multi-dimensional hyperparameter tuning using the training loss function. Our result generalizes the guarantees of 2 from one-dimensional hyperparameters to the multi-dimensional case, where p>1 . Moreover, our logic-based analysis avoids the need for strong regularity assumptions on the boundary polynomials \{h_{x,i}\}_{i=1,\dots,M_{f}} (see e.g., 2 ), which were required by the geometric approach to prevent topological pathologies in the solution path. 6 Data-driven Tuning via Validation Objective We now address the general data-driven setting in which the hyperparameter * is tuned to minimize a validation objective g evaluated on the optimal training parameters. As noted earlier, this formulation is general and can capture standard practices in hyperparameter tuning (e.g., tuning a regularization coefficient to minimize validation loss in LASSO). In this scenario, for a fixed problem instance x and hyperparameter * , the loss \ell_{*}(x) is defined as \ell_{*}(x)=\inf_{\theta\in\mathcal{S}(x,*)}g_{x}(*,\theta) , where \mathcal{S}(x,*)=\arg\min_{\theta\in\Theta}f_{x}(*,\theta) . Recall from Assumption 3.2 that for any fixed problem instance x , f_{x}(*,\theta) and g_{x}(*,\theta) admits piecewise polynomial structure with complexity (M_{f},T_{f},\Delta_{f}) and (M_{g},T_{g},\Delta_{g}) , respectively. Under such an assumption, we have the following result, which establishes the learning guarantee for the problem of data-driven hyperparameter tuning with a validation objective. Theorem 6.1 (Pseudo-dimension – Validation loss) . Let \mathcal{A}=[*_{\textup{min}},*_{\textup{max}}]^{p} and \Theta=[\theta_{\textup{min}},\theta_{\textup{max}}]^{d} . Suppose that for any instance x , the training objective f_{x}(*,\theta) and the validation objective g_{x}(*,\theta) , for (*,\theta)\in\mathcal{A}\times\Theta , admit piecewise polynomial structures (cf. Definition 3.1 ) with complexity (M_{f},T_{f},\Delta_{f}) and (M_{g},T_{g},\Delta_{g}) , respectively. Then, the pseudo-dimension of the function class \mathcal{L}=\{\ell_{*}:\mathcal{X}\rightarrow[-H,H]\mid*\in\mathcal{A}\} , where \ell_{*}(x)=\inf_{\theta\in\mathcal{S}(x,*)}g_{x}(*,\theta) and \mathcal{S}(x,*)=\arg\min_{\theta\in\Theta}f_{x}(*,\theta) , is bounded by \text{Pdim}(\mathcal{L})=\mathcal{O}(pd^{2}\log M_{\textup{tot}}+p^{2}d^{2}\log\Delta_{\textup{tot}}), where M_{\textup{tot}}=M_{f}+T_{f}+M_{g}+T_{g}+d , and \Delta_{\textup{tot}}=\max(\Delta_{f},\Delta_{g}) . Proof. Similar to the proof of Theorem 5.1 , the idea is to use Theorem 4.1 by showing that: given a problem instance x and a real-valued threshold t , there is a polynomial FOL \Phi_{x,t}(*) equivalent to \mathbb{I}(\ell_{x}(*)\geq t) with bounded complexities. Such a polynomial FOL can be defined as follows: \displaystyle\Phi_{x,t}(*) \displaystyle\triangleq(\forall\theta\in\mathbb{R}^{d})\left[(\theta\in\mathcal{S}(x,*))\Rightarrow(g(x,*,\theta)\geq t)\right] \displaystyle=(\forall\theta\in\mathbb{R}^{d})\left[\neg(\theta\in\mathcal{S}(x,*))\lor(g(x,*,\theta)\geq t)\right]. Here, we again use the identity (A\Rightarrow B)=(\neg A\lor B) . We first expand the optimality constraints \theta\in\mathcal{S}(x,*) . Note that a parameter \theta is not optimal (i.e., \neg(\theta\in\mathcal{S}(x,*)) if it is not in the region \Theta or if there exists a better candidate \theta^{\prime} such that f_{x}(*,\theta^{\prime})\mathcal{X}\to[-H,H]\mid*\in\mathcal{A}\} where \ell_{*} is defined as in ( 1 ) and f,g are defined as in ( 3 ). We have: \text{Pdim}(\mathcal{L})=\mathcal{O}(p^{3}d+p^{2}d^{2}). Proof sketch. To use Theorem 4.1 , we can add additional variables to represent f with polynomials. Indeed, with extra scalar variables \nu_{1},\ldots,\nu_{p} , we have: f(x,*,\theta)=\|A\theta-b\|^{2}+(*_{1}\nu_{1}+\ldots*_{p}\nu_{p}), with polynomial constraints: \nu_{i}^{2}=\sum_{j}[\theta_{i}]_{j}^{2}\quad\text{and}\quad\nu_{i}\geq 0\quad\forall i=1,\ldots,p. The detailed proof is presented in Appendix G . ∎ 8.2 Data-driven Weighted Fused Lasso We consider the problem of signal denoising with structural change-point detection, commonly modeled using the Weighted Fused LASSO ( 29 ) . Given a noisy signal b , the goal is to recover an approximation \theta\in\mathbb{R}^{d} . While standard Fused LASSO uses simple scalar regularization parameters, practical applications often benefit from allowing spatially varying regularization weights *\in\mathbb{R}^{d-1} to capture the heterogeneous noise levels or varying structural density across the signal. In particular, we consider Problem ( 1 ) with: \displaystyle f(x,*,\theta)= \displaystyle\frac{1}{2}\|b-A\theta\|_{2}^{2}+\sum_{i=1}^{d-1}*_{i}\left|\theta_{i+1}-\theta_{i}\right|, (4) \displaystyle g(x,*,\theta)= \displaystyle\frac{1}{2}\|A^{\prime}\theta-b^{\prime}\|^{2}, where x=(A,A^{\prime},b,b^{\prime}),*\in\mathbb{R}^{p} with p=d-1,\theta\in\mathbb{R}^{d} . No constraint is imposed, i.e., \Theta=\mathbb{R}^{d} . In particular, we assume that the data distribution of x satisfies that the matrix A always has full column rank. We have the next result. Theorem 8.2 (Pseudo-dimension for weighted fused lasso) . Consider the class of functions \mathcal{L}=\{\ell_{*}\>\mathcal{X}\to[-H,H]\mid*\in\mathcal{A}\} where \ell_{*} is defined as in ( 1 ) and f,g are defined as in ( 4 ). We have: \text{Pdim}(\mathcal{L})=\mathcal{O}(d^{2}). The proof exploits Theorem 7.2 ; the details can be found in Appendix G . 9 Conclusion and Future Works Our paper established a general learning-theoretic framework for data-driven hyperparameter tuning with implicitly defined loss functions. By bridging statistical learning theory and model theory, we derived the first general sample-complexity guarantees for multi-dimensional hyperparameter tuning ( *\in\mathbb{R}^{p} ), thereby resolving a key open question in the existing literature. Furthermore, we demonstrated that by leveraging additional algebraic structure and explicit solution paths, we can bypass the general worst-case analysis to achieve significantly tighter bounds. Finally, we illustrated the versatility of our framework through new applications in sparse learning and robust optimization. Our work opens two primary questions for future research. First, the fundamental lower bounds for the general bi-level setting remain unknown. Although we established matching lower bounds for specific cases with explicit solution paths (Section 7 ), determining the minimax lower bound for the general implicitly defined setting is an important open problem. Second, our current framework relies on semi-algebraic geometry. A natural extension is to generalize this logic-based approach to o-minimal structures ( 32 ) , such as Pfaffian functions. This would extend our guarantees to a much broader class of machine learning objectives involving transcendental functions like \exp , \log , and \tanh , moving beyond the polynomial limitations of the current work. Appendix A The Goldberg-Jerrum (GJ) Framework The Goldberg-Jerrum (GJ) framework was originally proposed by 16 , and later refined by 7 . It establishes the pseudo-dimension upper-bound for parameterized function class \mathcal{L} , of which the computation of each function \ell_{*} can be described by an GJ algorithm using basic operators ( +,-,\times,\div ), conditional statements, and intermediate values which are typically rational functions (e.g., fractions of two polynomials) of * . The formal definition of the GJ framework is as follows. Definition A.1 (GJ algorithm, ( 7 ) ) . A GJ algorithm \Gamma operates on real-valued inputs, and can perform two types of operations: • Arithmetic operators of the form v^{\prime\prime}=v\odot v^{\prime} , where \odot\in\{+,-,\times,\div\} , and • Conditional statements of the form “if v\geq 0\ldots else \ldots ”. In both cases, v and v^{\prime} are either inputs or values previously computed by the algorithm. The intermediate values v,v^{\prime},v^{\prime\prime} computed by the GJ algorithm \Gamma can be considered as rational functions of its real-valued inputs * . Based on its intermediate values, one can define the degree and the predicate complexity , which serve as complexity measures for the GJ algorithm. Definition A.2 (Complexities of GJ algorithm, ( 7 ) ) . The degree of a GJ algorithm is the maximum degree of any rational function that it computes of the inputs. The predicate complexity of a GJ algorithm is the number of distinct rational functions that appear in its conditional statements. Here, the degree of rational function f(*)=\frac{g(*)}{h(*)} , where g and h are two polynomials in * , is \deg(f)=\max\{\deg(g),\deg(h)\} . For a parameterized function class \mathcal{L} of which each function can be described by a GJ algorithm with bounded complexities, the following result establishes a concrete upper-bound for the pseudo-dimension \text{Pdim}(\mathcal{L}) . Theorem A.3 ( 7 ) . Suppose that each function \ell_{*}\in\mathcal{L} is specified by p real parameters *\in\mathbb{R}^{p} . Suppose that for every problem instance x\in\mathcal{X} and real-valued threshold t\in\mathbb{R} , there is a GJ algorithm \Gamma_{x,t} that, given \ell_{*}\in\mathcal{L} , returns “true” if \ell_{*}(x)\geq t and “false” otherwise. Assume that \Gamma_{x,t} has degree \Delta and predicate complexity \Lambda . Then, \text{Pdim}(\mathcal{L})=\mathcal{O}(p\log(\Delta\Lambda)) . The GJ algorithm \Gamma_{x,t} in Theorem A.3 is determined for each specific problem instance x and a real-valued threshold t . The input of \Gamma_{x,t} is the hyperparameter * that parameterizes \ell_{*} . Appendix B Proofs for Section 4 In this section, we will present the formal proof for Theorem 4.1 . Proof of Theorem 4.1 . By Theorem 2.5 , there exists an equivalent QFF \Psi_{x,t}(*) such that \Phi_{x,t}(*)\Leftrightarrow\Psi_{x,t}(*) . Moreover, \Psi_{x,t}(*) is a Boolean combination of I atomic polynomial predicates in * , with degree at most \Delta_{QE} , where \displaystyle I \displaystyle\leq M^{\prod_{k=1}^{M}(d_{k}+1)}\cdot\Delta_{f}^{\mathcal{O}(p)\prod_{k=1}^{M}(d_{k}+1)}, \displaystyle\Delta_{QE} \displaystyle\leq\Delta^{\mathcal{O}(p)\prod_{k=1}^{M}(d_{k}+1)}. We can construct a GJ algorithm \Gamma_{x,t} to evaluate the formula \Psi_{x,t}(*) as follows: 1. For each polynomial P_{j}(*) appears in \Psi_{x,t}(*) , the algorithm \Gamma_{x,t}(*) computes its intermediate value v_{j}=P_{j}(*) using standard operators ( +,-,\times ). Since P_{j} are polynomials in * , this step is valid. 2. For each predicate P_{j}(*)\chi_{j}0 , the algorithm checks the condition (e.g., “if v_{j}\geq 0 ”) using a conditional statement. 3. Finally, the algorithm \Gamma_{x,t}(*) combines the Boolean results of these checks according to the AND/OR structure of \Psi_{x,t} to return the final truth. The degree of \Gamma_{x,t} is simply the maximum degree of the intermediate polynomials computed, which is at most \Delta_{QE} . The predicate complexity is the number of distinct polynomials in the conditional statements, which is at most I . Finally, applying Theorem A.3 , the pseudo-dimension of \mathcal{L} is upper-bounded by: \displaystyle\mathcal{O}(p\log(I\cdot\Delta_{QE}))= \displaystyle\mathcal{O}\left(p\log M^{\prod_{k=1}^{M}(d_{k}+1)}\cdot\Delta^{2\mathcal{O}(p)\prod_{k=1}^{M}(d_{k}+1)}\right) \displaystyle= \displaystyle O\left(p\prod_{k=1}^{M}(d_{k}+1)\log M+p^{2}\prod_{k=1}^{M}(d_{k}+1)\log\Delta\right). as desired. ∎ Appendix C Semi-algebraic Functions and Their Properties We start with the notion of semi-algebraic functions and sets: Definition C.1 (Semi-algebraic sets and functions) . A subset A of \mathbb{R}^{n} is called semi-algebraic if it can be described by a finite number of polynomial equalities and inequalities, i.e. : A=\bigcup_{i\in\mathcal{I}}\{x\mid P_{i}(x)=0\text{ and }Q_{i,j}(x)>0,\forall j\in\mathcal{J}_{i}\}, where \mathcal{I} and \mathcal{J}_{i},i\in\mathcal{I} are finites index sets. A function is semi-algebraic if and only if its graph is semi-algebraic. Semi-algebraic functions are stable under many operations. Proposition C.2 (Properties of semi-algebraic functions ( 10 , Theorem 2.84 and 2.85) ) . The set of semi-algebraic functions is closed under composition, summation, and multiplication. It is noteworthy that the set of piecewise polynomial functions (cf. Definition 3.1 ) is a strict subset of the set of semi-algebraic functions. Indeed, to show that a piecewise polynomial function g is semi-algebraic, it is sufficient to express its graph as: \mathtt{graph}\,g=\bigcup_{\sigma\in\Sigma_{f_{x}}}\left\{(x,y)\mid\left(\bigcap_{k=1}^{M_{f}}{\text{sign}}(h(x))=\sigma_{k}\right)\cap(y=f_{\sigma}(x))\right\} Other examples of semi-algebraic functions in the learning context that are not piecewise polynomial are: 1. Norm \ell_{p},p\in\mathbb{N} : because its graph is given by: \{(x,y)\mid y>0,\left(\sum_{i=1}^{d}x_{i}^{p}\right)-y^{p}=0\}\cup\{(0,0)\}\subseteq\mathbb{R}^{d+1}. Note that \ell_{p} is not piecewise polynomial because it is equal to (\sum_{i=1}^{p}x_{i}^{p})^{\frac{1}{p}} . 2. The \ell_{2}/\ell_{1} ratio, i.e., \|x\|_{2}/\|x\|_{1} : Note that f(x,y)=x/y is semi-algebraic since their graph is \{(x,y)\mid xy=1\} . The \ell_{2}/\ell_{1} ratio is, thus, also semi-algebraic because it is the composition of g and f where: g:\mathbb{R}^{d}\to\mathbb{R}^{2}:x\mapsto\begin{pmatrix}\|x\|_{2}\\ \|x\|_{1}\end{pmatrix} The \ell_{2}/\ell_{1} ratio is not piecewise polynomial either because it is a rational function (and not polynomial). 3. Group LASSO: Let (\theta_{1},\ldots,\theta_{p})\in\mathbb{R}^{d_{1}}\times\ldots\times\mathbb{R}^{d_{p}} be a decomposition of \theta\in\mathbb{R}^{d} , then the group LASSO is given by: f(\theta)=\sum_{i=1}^{p}\|\theta_{p}\|_{2}. As seen previously, \|\cdot\|_{2} is semi-algebraic and semi-algebraic functions are stable under summation; group LASSO is also semi-algebraic. It is not piecewise polynomial either since it is equal to the sum of \ell_{2} norms. Appendix D Proofs of Section 5 Proof of Theorem 5.1 . To apply Theorem 4.1 , given a problem instance x and a real-valued threshold t , our goal is to construct a polynomial FOL formula \Phi_{x,t}(*) equivalent to \mathbb{I}(\ell_{*}(x)\geq t) . Since \ell_{*}(x)=\min_{\theta\in\Theta}f_{x}(*,\theta) is a minimization over \Theta , the condition \ell_{*}(x)\geq t is equivalent to stating that for all parameter \theta\in\Theta , the function value f_{x}(*,\theta) is greater or equal than t , and \Phi_{x,t}(*) is defined as \displaystyle\Phi_{x,t}(*) \displaystyle\triangleq(\forall\theta\in\mathbb{R}^{d})[(\theta\in\Theta)\Rightarrow f_{x}(*,\theta)\geq t] \displaystyle=(\forall\theta\in\mathbb{R}^{d})[\neg(\theta\in\Theta)\lor(f_{x}(*,\theta)\geq t)]. Here, we use the logical identity (A\Rightarrow B)=(\neg A\lor B) (i.e., not A or B ). The task now is to analyze the structural complexity of \Phi_{x,t}(*) : • The formula involves exactly one block of quantifiers: (\forall\theta\in\mathbb{R}^{p}) . Thus, the number of quantifier alternations is K=1 , and the dimension of the quantified variables is d_{1}=d . • The formula involves two types of predicates: – Domain constraints: because \Theta=[\theta_{\textup{min}},\theta_{\textup{max}}]^{d} is a box in \mathbb{R}^{d} , cheking the condition \theta\in\Theta requires evaluating 2d linear inequalities (i.e., \theta_{j}\geq\theta_{\min} and \theta_{j}\leq\theta_{\textup{max}} , for j=1,\dots,d ). – Function structure: The condition f_{x}(*,\theta)\geq t relies on the piecewise polynomial structure of f_{x} (cf. Definition 3.1 ). Formally, this condition holds if the pair (*,\theta) falls into a specific region indexed by a binary vector \sigma=(\sigma_{1},\dots,\sigma_{M_{f}})\in\Sigma_{f_{x}} , and the corresponding value polynomial P_{x,\sigma}(*,\theta) that f_{x} admits in such region satisfies P_{x,\sigma}(*,\theta)\geq t . We can express this logically as disjunctions over all valid sign patterns \Sigma_{f} : \bigvee_{\sigma\in\Sigma_{f}}\Big(\underbrace{\Big[\bigwedge_{j=1}^{M_{f}}\text{sign}(h_{x,j}(*,\theta))=\sigma_{j}\Big]}_{\text{Region Check}}\land\underbrace{\left[P_{x,\sigma}(*,\theta)\geq t\right]}_{\text{Value Check}}\Big), where h_{x,j} and P_{x,\sigma} are boundary and piece polynomials in the piecewise polynomial structure of f_{x} . Consequently, the set of atomic polynomials appearing in this formula consists of: (1) M_{f} boundary polynomials \{h_{x,1},\dots,h_{x,M_{f}}\} , (2) at most T_{f} polynomial \{P_{x,\sigma}-t\}_{\sigma\in\Sigma_{f_{x}}} . Therefore, the total number of distinct atomic predicates is bounded by M_{\textup{total}}=M_{f}+T_{f}+2d , and the maximum degree is \Delta_{f} (as linear constraints have degree 1). ∎ Appendix E Proofs of Section 6 Proof of Theorem 6.1 . Similar to the proof of Theorem 5.1 , the idea is to use Theorem 4.1 by showing that: given a problem instance x and a real-valued threshold t , there is a polynomial FOL \Phi_{x,t}(*) equivalent to \mathbb{I}(\ell_{x}(*)\geq t) with bounded complexities. Such a polynomial FOL can be defined as follows: \displaystyle\Phi_{x,t}(*) \displaystyle\triangleq(\forall\theta\in\mathbb{R}^{d})\left[(\theta\in\mathcal{S}(x,*))\Rightarrow(g(x,*,\theta)\geq t)\right] \displaystyle=(\forall\theta\in\mathbb{R}^{d})\left[\neg(\theta\in\mathcal{S}(x,*))\lor(g(x,*,\theta)\geq t)\right]. Here, we again use the identity (A\Rightarrow B)=(\neg A\lor B) . We first expand the optimality constraints \theta\in\mathcal{S}(x,*) . Note that a parameter \theta is not optimal (i.e., \neg(\theta\in\mathcal{S}(x,*)) if it is not in the region \Theta or if there exists a better candidate \theta^{\prime} such that f_{x}(*,\theta^{\prime})0} denote the regularization hyperparameters controlling the magnitude of the \ell_{1} and \ell_{2} regularization. Then, the solution \theta(x,*) is evaluated in the validation set (A_{\textup{val}},b_{\textup{val}}) of the problem instance x \ell_{*}(x)=\frac{1}{2m^{\prime}}\|b_{\textup{val}}-A_{\textup{val}}\theta(x,*)\|_{2}^{2}. Assuming that there is an application specific problem distribution \mathcal{D} over the space of problem instance \mathcal{X}=\mathbb{R}^{m\times d}\times\mathbb{R}^{m}\times\mathbb{R}^{m^{\prime}\times d}\times\mathbb{R}^{m^{\prime}} , our goal is to answer the question of how many problem instances do we need to learn a good hyperparameter * for the problem distribution \mathcal{D} . Denote \mathcal{L}=\{\ell_{*}:\mathcal{X}\rightarrow[-H,H]\mid*\in\mathbb{R}^{2}_{>0}\} , the previous question is equivalent to giving an upper-bound for the pseudo-dimension of \mathcal{L} . Recovering the pseudo-dimension upper-bound. We now demonstrate how to use our general result to establish an upper bound for \text{Pdim}(\mathcal{L}) . First, we will invoke the properties of the solution path of the ElasticNet, a rephrasing of the structural result mentioned in 6 . Proposition F.1 (Theorem 3.2, 6 ) . For any fixed problem instance, the unique mapping *\rightarrow\theta^{*}(x,*) satisfies Assumption 7.1 with • T_{\textup{path}}=\mathcal{O}(3^{d}) : the domain \mathbb{R}^{2}_{0} is partitioned into disjoint regions corresponding to the sign patterns (e.g., active sets) of the optimal coefficients. The number of regions is bounded by the total number of sign patterns, i.e., T_{\textup{path}}\leq 3^{d} . • M_{\textup{path}}=\mathcal{O}(d3^{d}) : the boundaries separating these regions are defined by conditions where a coefficient vanishes. The number of such boundary polynomials is bounded by M_{\textup{path}}\leq d3^{d} . • \Delta_{\textup{path}}=\mathcal{O}(d) : inside each region, the solution is given by a rational function (derived using Cramer’s Rule on the active linear system). The degree of these rational functions is bounded by \Delta_{\textup{path}}\leq 2d . We are now ready to recover the upper-bound for the pseudo-dimension of \mathcal{L} , which then implies the generalization guarantee for data-driven tuning of the regularization hyperparameters for ElasticNet, by combining Proposition F.1 and Theorem 7.2 . Corollary F.2 . Let \mathcal{L} be the class of validation loss functions for ElasticNet as defined above. Then \text{Pdim}(\mathcal{L})=\mathcal{O}(d) . Proof. We first calculate the total complexities M_{\textup{total}},\Delta_{\textup{total}} . First note that p=2 (as *\in\mathbb{R}^{2}_{>0} ), and then we have: • The piecewise rational structural complexities of the tuning objective k_{x}(*,\theta)=\frac{1}{2}\|b_{\textup{val}}-A_{\textup{val}}\theta\|_{2}^{2} are M_{k}=0 , T_{k}=1 , and \Delta_{k}=2 . • Combining with Proposition F.1 , the total complexities are – M_{\textup{total}}=M_{\textup{path}}+T_{\textup{path}}(M_{k}+T_{k})\leq(d+1)3^{d} , – \Delta_{\textup{total}}=\Delta_{k}\cdot\Delta_{\textup{path}}\leq 4d . Finally, applying Theorem 7.2 gives us \text{Pdim}(\mathcal{L})=\mathcal{O}(p\log(M_{\textup{total}}\Delta_{\textup{total}}))=\mathcal{O}(d). This completes the proof. ∎ Remark F.3 . Note that in Theorem 3.5 by 6 , we have \text{Pdim}(\mathcal{L})=\Omega(d) . Therefore, applying Theorem 7.1 successfully recovers a tight bound for the pseudo-dimension of \mathcal{L} . Appendix G Proofs of Section 8 G.1 Data-driven Weighted Group Lasso Proof of Theorem 8.1 . The proof is fairly similar to the previous. The only difference is how we describe f as polynomials since the function is no longer piecewise polynomial. This is possible by adding extra \nu_{1},\ldots,\nu_{p} scalar variable and write: f(x,*,\theta)=\|A\theta-b\|^{2}+\sum_{i=1}^{p}*_{i}\nu_{i} with polynomial constraints: \nu_{i}^{2}=\sum_{j}[\theta_{i}]_{j}^{2}\quad\text{and}\quad\nu_{i}\geq 0,\forall i=1,\ldots,p. (5) The corresponding first-order formula is given by: \forall\theta\in\mathbb{R}^{d},\exists(z,\nu^{\theta},\nu^{z})\in\mathbb{R}^{d+2p},(T_{1}\lor T_{2}), where T_{1} and T_{2} are: \displaystyle T_{1} \displaystyle=(\|A\theta-b\|^{2}+\sum_{i}*_{i}\nu_{i}^{\theta}>\|Az-b\|^{2}+\sum_{i}*_{i}\nu_{i}^{z})\land(\text{conditions }\eqref{eq:condition-l2}\text{ for }\nu^{\theta}\text{ and }\nu^{z}), \displaystyle T_{2} \displaystyle=\|A^{\prime}\theta-b\|^{2}\geq t. Overall, we have \Delta=2 and M=2(1+2p) . Applying Theorem 4.1 , we obtain: \text{Pdim}(\mathcal{L})=\mathcal{O}(p(d+1)(d+2p+1)\log(2+4p)+p^{2}(d+1)(d+2p+1)\log 2)=\mathcal{O}(p^{3}d+p^{2}d^{2}).\qed G.2 Data-driven Weighted Fused Lasso We remind the problem setting and prove Theorem 8.2 . To prove the results of the Weighted Fused LASSO, we first need to reformulate the optimization problem into a canonical form. Let D\in\mathbb{R}^{(d-1)\times d} be the first-difference matrix, i.e., D=\begin{bmatrix}-1&1&0&\cdots&0&0\\ 0&-1&1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-1&1\end{bmatrix}. The Weighted Fused LASSO estimation problem can be rewritten as \min_{\theta\in\mathbb{R}^{d}}\frac{1}{2}\|b-A\theta\|_{2}^{2}+\sum_{i=1}^{p}*_{i}\left|(D\theta)_{i}\right|, or equivalently, \min_{\theta\in\mathbb{R}^{d}}\frac{1}{2}\|b-A\theta\|_{2}^{2}+\sum_{i=1}^{p}*_{i}\left|z_{i}\right|,\textup{ s.t. }z=D\theta. First, we will show that the dual form of Weighted Fused LASSO takes the multi-parametric Quadratic Programming (mp-QP) ( 11 ) . Proposition G.1 . The dual formulation of Weighted Fused LASSO is \min_{u\in\mathbb{R}^{p}}\frac{1}{2}\|\tilde{b}-\tilde{A}u\|_{2}^{2},\textup{ s.t. }\left|u_{i}\right|\leq*_{i},i=1,\dots,p, where \tilde{A}=(A^{\top}A)^{-1/2}D^{\top} and \tilde{y}=(A^{\top}A)^{-1/2}A^{\top}y . Proof. We first define the Lagrangian function L(\theta,z,u) as L(\theta,z,u)=\frac{1}{2}\|b-A\theta\|_{2}^{2}+\sum_{i=1}^{p}*_{i}\left|z_{i}\right|+u^{\top}(D\theta-z), where u\in\mathbb{R}^{p} is a Lagrangian variables. Strong duality holds due to the convexity and linear-quadratic structure of the original problem. We now derive the dual objective function, which is the separable infimum of the Lagrangian function w.r.t. the primal variables \theta and z , i.e., \displaystyle g(u) \displaystyle=\inf_{\theta,z}L(\theta,z,u) \displaystyle=\underbrace{\inf_{\theta}\left(\frac{1}{2}\|y-A\theta\|_{2}^{2}+u^{\top}D\theta\right)}_{\textup{First term}}+\underbrace{\inf_{z}\left(\sum_{i=1}^{p}(*_{i}\left|z_{i}\right|-u_{i}z_{i})\right)}_{\textup{Second term}}. For the first term, we simply take the gradient w.r.t. \theta and set it to zero, i.e. \nabla_{\theta}\left(\frac{1}{2}\|b-A\theta\|_{2}^{2}+u^{\top}D\theta\right)=-A^{\top}(b-A\theta)+D^{\top}u=0. If A has full column rank (or in the general position ) ( 31 ) , we conclude that the optimal \theta^{*}(u) is \theta^{*}(u)=(A^{\top}A)^{-1}(A^{\top}b-D^{\top}u). For the second term, the infimum of *_{i}\left|z_{i}\right|-u_{i}z_{i} is bounded only if \left|u_{i}\right|\leq*_{i} . If this holds, the infimum is 0 ; otherwise, it is -\infty . This gives us the box constraints \left|u_{i}\right|\leq*_{i} . Therefore, we conclude that the dual problem is \begin{array}[]{cl}\min_{u\in\mathbb{R}^{p}}&\frac{1}{2}(A^{\top}y-D^{\top}u)^{\top}(A^{\top}A)^{-1}(A^{\top}b-D^{\top}u),\\ \textup{ s.t. }&\left|u_{i}\right|\leq*,i=1,\dots,p.\end{array} Simply setting \tilde{A}=(A^{\top}A)^{-1/2}D^{\top} and \tilde{b}=(A^{\top}A)^{-1/2}A^{\top}y , we have the final conclusion. ∎ Since the above take the form of mp-QP with linear constraints (i.e., -*\leq u_{i}\leq* ), from Theorem 2 in 11 , the solution u^{*}(x,*) is a piecewise affine function of * , where each piece corresponds to an active constraint. Using this property, we are now ready to prove the generalization guarantee for the problem of data-driven tuning regularization parameters for Weighted Fused LASSO in Theorem 8.2 . Proof of Theorem 8.2 . To bound the pseudo-dimension, we use our proposed Theorem 7.2 . The complexity depends on the number of region M_{\textup{path}} in the partition: • Each critical regions correspond to a stable set of active constraints. • For each of p=d-1 dual variables, the box constraints allow for at most 3 states at optimality: (1) u_{i}=*_{i} , (2) u_{i}=-*_{i} , or (3) -*_{i}