Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function
Authors: Maria Florina Balcan
Anh Tuan Nguyen
Dravyansh Sharma
Venue: NeurIPS 2025 poster ()
Keywords: Data-driven algorithm design
generalization guarantee
PAC-learnable bound
provable hyperparameter tuning
Primary area: theory
TL;DR: Provable hyperparameter tuning in data-driven settings under structured parameter dependent dual utility function

Abstract: Modern machine learning algorithms, especially deep learning-based techniques, typically involve careful hyperparameter tuning to achieve the best performance. Despite the surge of intense interest in practical techniques like Bayesian optimization and random search-based approaches to automating this laborious and compute-intensive task, the fundamental learning-theoretic complexity of tuning hyperparameters for deep neural networks is poorly understood. Inspired by this glaring gap, we initiate the formal study of hyperparameter tuning complexity in deep learning through a recently introduced data-driven setting. We assume that we have a series of learning tasks, and we have to tune hyperparameters to do well on average over the distribution of tasks. A major difficulty is that the utility function as a function of the hyperparameter is very volatile, and furthermore, it is given implicitly by an optimization problem over the model parameters. To tackle this challenge, we introduce a new technique to characterize the discontinuities and oscillations of the utility function on any fixed problem instance as we vary the hyperparameter; our analysis relies on subtle concepts, including tools from algebraic geometry, differential geometry, and constrained optimization. We use this to show that the learning-theoretic complexity of the corresponding family of utility functions is bounded. We instantiate our results and provide sample complexity bounds for concrete applications—tuning a hyperparameter that interpolates neural activation functions and setting the kernel parameter in graph neural networks.

Sample complexity of data-driven tuning of model hyperaarameters in neural networks with structured parameter-dependent dual function
Maria-Florina Balcan Carnegie Mellon University ninamf @cs cmu edu
Anh Tuan Nguyen
Carnegie Mellon University atnguyenčcs. cmu edu
Dravyansh Sharma
Toyota Technological Institute Chicago dravySttic.edi
Abstract
Modern machine learning algorithms, especially deep learning-based techniques, typically involve careful hyperparameter tuning to achieve the best performance. Despite the surge of intense interest in practical techniques like Bayesian opti- mization and random search-based approaches to automating this laborious and compute-intensive task, the fundamental lcariig-theooretc complexity of tuning hyperparameters for deep neural networks is poorly understood. Inspired by this glaring gap, we initiate the formal study of hyperparameter tuning complexity in deep learning through a recently introduced data-driven setting. We assume that we have series learning tasks, and we have tune hyperparameters average over the distribution of tasks. A major difficulty is that the utility function as function of the hyperparameter is very volatile and furthermore, implicitly by an optimization problem over the model parameters. To tackle this challenge, we introduce new technique to characterize the discontinuities and oscillations of the utility function any fixed problem instance as vary the hyperparameter; our analysis relies on subtle concepts including tools from alge- braic geometry, differential geometry and constrained optimization. We use this show that the learning- theoretic complexity of the corresponding family of utility functions is bounded. We instantiate results and provide sample complexity bounds for concrete applications cittiiionsttninngggn a hyperparameter that interpolates neural activation functions and setting the kernel parameter in graph neural networks.
do well on
given
Sramiing-theoretic
Introduction
Developing deep neural networks that work best for given application typically corresponds tedious selection of hyperparameters and architectures over extremely large search spaces. This pro- cess of adapting deep learning algorithm model new application domain takes up significant engineering and research resources, and often involves unprincipled techniques with limited or no theoretical guarantees on their effectiveness. While the success of pre-trained (foundation) models have shown the usefulness of transferring effective parameters (weights) of learned deep models across tasks 2. less clear how to leverage prior experience of "good" hyperparameters to new tasks. In this work, we develop a principled framework for tuning continuous hyperparameters in deep networks by leveraging similar problem instances and obtain sample complexity guarantees for learning provably good hyperparameter values.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The vast majority of practitioners still use naive "grid search" " based approach which involves selecting a finite grid of (often continuous-valued) hyperparameters and selecting the one that performs the best. A lot of recent literature has been devoted to automating and improving this hyperparameter tuning process. prominent techniques include Bayesian optimization [ 5 6 and random search based methods 7.8. While these approaches work well in practice, they either lack a formal basis or enjoy limited theoretical guarantees only under strong assumptions. For example, Bayesian optimization analysis assumes that the performance of the deep network function of the hyperparameter can be approximated as a noisy evaluation of an expensive function, typically making assumptions on the form of this noise, and requires setting several hyperparameters and other design choices including the amount of noise, the acquisition function which determines the hyperparameter search space, the type of kernel and its bandwidth parameter. Other techniques, including random search methods and spectral approaches [9 make fewer assumptions but only work for discrete and finite grid of hyperparameters. This necessitates the need of analyzing the landscape of hyperparameter loss (utility) landscape.
In this work, we consider the problem of tuning neural network hyperparameters in a multi-task setting. We assume there is a fixed but unknown distribution over the learning tasks, and we have access to tasks drawn from that distribution at the training time. We want to learn the hyperparameters to use on future tasks from the same distribution, i.e. on any future task we use the learned hyperparameter, and then we find the best network weights for that task. To address this question. we observe parallel to prior work on data-driven algorithm design [I]. Despite a similar formulation, our goal is to learn the network hyperparameters, and not configure the training algorithm that learns the network weights. The best weights learned during training for a fixed task ultimately depend on the hyperparameter selected in a complex way, making our setting more challenging than those previously studied under this paradigm.
Mathematically, we aim to analyze the tearning-theoreticc theoretic complexity of specific function class u = (ua : X' - [0, H] a E A}, where AA = [ar,, ar2] C IR is the hyperparameter space and X' is the set of problem instances. We note that each problem instance æ E X' corresponds to training dataset for a single task (c.g. a dataset of images, as opposed to a single image). We assume there is an application-speciff problem problem distribution D over the datasets (tasks) in X. Each function u. (z) in Z is defined as: un (x) = sup ())) fx, a w), where u, (x) measures the performance of the deep network on problem instance x and hyperparameter a using the best parameter w. Here W = [Wmin; Wmax] C Rd represents a d-dimensional parameter space. Our goal is to establish an upper bound on the learning-theoretic complexity of 24, leveraging the structural properties of f(x, a, w). We introduce two key notations in our analysis: the parameter- dependent dual function (a, w) := f(x, a, w), describing the performance corresponding to hyperparameter a and parameter
for fixed problem instance x, and the dual utility function "a == un (,(x) = maxwew f (a, Inspired by model hyperparameter tuning applications (see Section 5). assume that the parameter-dependent dual (a, w² is the piecewise polynomial function in a and u (see Section for details). Based on this structure of fa (o__w) w.) we aim to understand the structure of or (a) which by the earlier work of Balcan et al. 112 would imply learnability of = {ua X - H] E A].
The major difficulty we have to overcome is that even if [a w) is nicely structured piecewise polynomial function, the function =n (a) = suD w Sa (ax, w) appears to be less structured;
in particular, the function (a) is not necessarily piecewise polynomiaß and might not even have closed form Our key technical innovation is to show that for the case of one hyperparameter a we can still find enough structure in the dual functions u specifically by leveraging the structure of parameter-depender dual functions (ax, w) we show how to bound the number of discontinuities and local maxima of ux which in turn implies that they have bounded oscillations (defined in Section 2. which then imply a bound on the pseudo-dimension of Ul (using results from 12)
1 'This work introduces the relation between the structure of the dual =t, and the learnability of the primal class 24 in a different context of algorithm configuration, but the approach is useful for our setting.
w for ax w 2 0, and define u (ax = sup fa w). One 2 Coonsider the case where fa (a, w) = wa 3
easily show that in this case, u (a) a which is not polynomial in a. *As another example, consider fa, w) = wax + (1/4)w* - (3/2)aw² for a, w E [0, 1Ja In this case,
ug (a) = supwe 10 fa, w) has pieces corresponding to w = and 0fz /0w = a + w" 3ow = 0. The latter is the Folium of Descartes, and does not admit closed-for form expression in terms of elementary functions.

---

Our proposed framework implies generalization guarantees for data-driven model hyperparameter tuning across various applications. We demonstrate this through two concrete examples including the following. Our first application is to tuning an interpolation hyperparameter for the activation function used at each node of the neural network. Different activation functions perform well on different datasets [33 [4]. We analyze the sample complexity of tuning the best combination from a pair of acti- vation functions by learning a real-valuee hyperparameter that interpolates between them. We tune the hyperparameter across multiple problem instances, an important setting for multi-task learning. Our contribution is related to neural architecture search (NAS, [5 16 17). NAS automates the discovery and optimization of neural network architectures, replacing human-led design with computational methods. Several techniques have been proposed [18] 19 20), but they lack principled theoretical guarantees (see additional related work in Appendix Ap. and multi-task learning is known open research direction [1]]. We also instantiate our framework for tuning the graph kernel parameter in Graph Neural Networks (GNNs) 22 designed for more effectively deep learning with structured data. Hyperparameter tuning for graph kernels has been studied in the context of classical non-neural mod- els [23 24] in this work we provide the first provable guarantees for tuning the graph hyperparameter for the more effective modern approach of graph neural networks. While we focus on these specific applications, our proposed framework's generality makes it applicable to many other scenarios.
Our contributions. In this work, we provide an analysis for the learnability of parameterized algorithms involving both parameters and hyperparameters, when the learner has access to problem in- stances drawn from a fixed, unknown distribution. Our analysis captures model hyperparameter tuning in deep networks with piecewise polynomial parameter-dependdee dual function. Concretely,
We introduce general tools which connect the number of discontinuities and local maxima of a piecewise continuous function with its bearning-theoreee complexity (Section (.1).
2. We show that when the parameter-dependent dual function fa (a, w) computed by a deep network on fixed dataset is piecewise constant, the function uz is also piecewise constant. This structure occurs in classification tasks with a 0-1 loss objective. We then establish an upper-bound for the pseudo-dimension of U. which translates learning guarantees for 2/ (Theorem 3.2).
3. As our main contribution, we prove that when the parameter-dependent dual function (a w) exhibits piecewise polynomial structure, under mild regularity assumptions, we can establish an upper bound for the number of discontinuities and local extrema of the dual utility function u We use tools from differential geometry to identify the smooth 1 1-manifolds in the space A x W corresponding to the derivative curves which determine " and results from algebraic geometry and constrained optimization to bound the number of local extrema of u. along such manifolds. We then translate the structure of u to learning guarantees for U/ (Theorem 4.1
4. Finally, we investigate data-driven algorithm configuration problems for deep networks, including tuning interpolation parameters for neural activation functions (Theorem 5.1) and hyperparameter tuning for semi-supervised learning with graph convolutional networks (Theorem H.2). We first uncover the underlying piecewise structure relevant for our framework, and then use this structure to obtain learnability guarantees for tuning the hyperparameters for both classification and regression problems.
Related work. Data-driven algorithm design has been successfully applied to tune fundamental algorithms in machine learning and beyond (Appendix Ap. Our work is the first work to focus on tuning hyperparameters for deep networks using a data-driven lens. A key technical challenge that we overcome is that varying the hyperparameter even slightly can lead learned deep network (even for the same training set) with completely different parameters (weights) which is hard characterize directly. This is very different from typical data-driven problem where one is able to show closed forms or precise structural properties for the variation of the learning algorithm's is behavior as a function of the hyperparameter [12] We elaborate further on our technical novelties below. Our theoretical advances are potentially useful beyond deep networks, to algorithms with a tunable hyperparameter and several learned parameters. We discuss the challenges in our setting and explain why developing novel techniques is required. We also provide a brief technical overview of our approach. See Appendix B for further discussion.
significantly different
Technical challenges and novelty. In typical prior work on data-driven hyperparameter tuning 25 26 27. 28), the hyperparameter tuning process does not involve the parameter w. In such cases, the approach is to show that the utility function u (a) admits a specific piecewise structure in a, typically piecewise polynomial or rational. Some works involve the parameter w [29 30). but the optimal parameter w (a) E arg wax fa (a, w) either has a closed analytical form
3

---

or can be approximated by function w (a) with bounded enror. In contrast, in our setting, un (a) =00mmam max fa w) is defined via an optimization problem involving the parameter and no closed form solution for (a: is known. This difference highlights the challenges of our setting, overcoming which requires the development of novel techniques.
Technical overview. We show in Section 2.1 that if ui (a) is piecewise continuous, we can bound Pdim(()) via bounding the number of discontinuities and local extrema of uz (a). We then show in Section 3 that if (a, w) is piecewise constant, 2 (a) ( is also piecewise constant with finitely many discontinuities. We then present our main technical contribution in Section | if fa w) is piecewise polynomial, then we can bound the pseudo-dimense dimension Uf Concretely, we propose the notion of monotonic curves and study their relevant properties (Appendix (F3). We show that the domain A of u (a) can be partitioned into multiple intervals, over each of which 2n (a) is given by the pointwise maximum of (a w) along some fixed set of monotonic curves. Leveraging tools from algebraic and differential geometry, we show that by bounding the number of local maxima of far (a, up) along monotonic curves, we can bound the number of discontinuities and local extrema of u (a, w) in A, thereby establishing learning- theorettt guarantees for Ut
2 Problem setting and preliminaries
Models with hyperparameters. We introduce the data-driven model hyperparameter tuning framework for models with hyperparameters a and trainable parameters w. Concretely, let f:X² x A x W [0, H] be the purameeterddependen utility function that represents the model's performance, where f(x, w) measures the performance corresponding to problem instance x E X, parameters w E W = [Wmin: Wmax]" 1d, and hyperparameter a E [Oaminn Omax] Here each problem instance x E X' in our hyperparameter tuning framework represents the complete training dataset for a single task, unlike single-task machine learning setting where æ E X' typically represents a single example. For example, in the problem of tuning the interpolation parameter of neural activation functions (Section 5). each problem instance x = (X, Y) consists of a set X of T examples, and the corresponding labels Y. We define the utility function ue (a) quantifying the model's performance with hyperparameter on problem instance x as Ua (x) supwi(a, w) A.A.x W fx, w). This for- mulation can be interpreted as follows: for a given hyperparameter a and problem instance æ, we determine the optimal model parameters that maximize performance.
The dual utility function. For fixed problem instance æ E X, we can define the dual function " A + [0, H]. representing the performance of the network corresponding to the hyperparameter and the best parameter w, as ute (ax) = sup WwW f (ax, w), where [a w) == f(xx ar, w) called the parameter-depender dual function.
Data-driven model hyperparameter tuning problem. Let U = {ua : : [0, H E A} be the utility function class. In the data-driven setting, we assume application-specifi problem distribution 'D over the set of problem instances X. Here, 'D represents a fixed but unknown distribution of over datasets or tasks. Our goal here is find a good hyperparameter à given a small sample of tasks drawn from D, that achieves nearly the same utility on average as the optimal hyperparameter a² E arg max ER [u, (a:)]. Our approach is to bound the pseudo-dimension and the Rademacher complexity of the function class U, given the structure of the parameter- dependent dual function (a(aw))
We consider two situations where (a, w) is either piecewise constans (Section 3 or piecewise polynomial (Section 4 For the piecewise constant case, we assume that for any æ. there is finite partition P of the domain A x W consisting of connected components such that fa (a: w) remains constant each connected component in P. For the second case, we assume that there algebraic sets Zhe, {(a, w) E A x W (a, w) = 0} partitioning the domain A x W. where (a, w) is a polynomial in a and w. In each connected component of the partition, the piece function fa, which equals fa (a, w) in the component is also polynomial of a and w.
2.1 Discontinuities, local extrema and the pseudo-dimension
In this section, we establish connection between the structure of the dual utility function u and the pseudo-dimension of 14 {u., : X - a E TR.. Concretely, we show that if u has bounded number of discontinuities and local extrema, then U has bounded pscudo-dimension.

---

Lemma 2.1. Consider real-valued function class U = {ua : - R | dual function u (a) piecewise continuous, with at most B, discontinuities and Bg local maxima. Then Pdim = (log B1 + B2))-
a R), of which each
The detailed proof of Lemma 2.1 can be found in Appendix D.2 The idea is to show that ug (a) has bounded oscillations (Definition Lemma D.2), which is defined as the maximum number of discontinuities that the function [=] have, for any real threshold z. We then use result by Balcan et al. [1] (Theorem D.I connecting the oscillations and Pdim((4). Note that Lemma 2. does not apply to piecewise constant functions, which have an infinite number local extrema. However, we can still give analogous result for this case as follows (see Appendix D.2 for proof). Lemma 2.2. Consider a real-valued function class U = {wo : X + R a E R), of which each dual function un (a) is piecewise constant with at most B discontinuities. Then Pdim (L) = (log B).
3 Piecewise constant parameter-dependert dual function
We first examine the case where Sm(a, w) is piecewise constant. Concretely, we assume there exists a partition Pe = 1R Re,N } of the domain A x W of Jæ- where each Rg is a connected component (Definition (). and the function (a, w) restricted on Rg constant, i.c.
(a, w) Cz.s for any (a, w) E Rg. Consequently, we can rewrite u. (a) as follows:
u (a) = sup fa(a,, w) = max weW
sup (E( (a),
fa, w) N)) s.t. (a. Cz.i.
max
We first show Lemma which asserts that un (ax is piecewise constant function and provides an upper bound for the number of discontinuities in u (a).
Lemma 3.1. Assume that the piece functions fa, w) ca.s are constant for all i E [N] and all problem instances x. Then u (a) has O(N) discontinuity points, partitioning A into O(N) intervals. In each interval, wig (a) is constant function.
Proof. The proof idea of Lemma 3.1 is demonstrated in Figure 3 corresponding to piece function (a, w) Cz. i, let
For each connected set Ra.
O' O' inf = inf(a: Bw, (ax, w) E Raihh Q' R....s = sup : 3w, (a, (a)w)) E R
There are N connected components, and therefore 2N such points. Reordering those points and removing duplicate points as O'min = 0i < 01 < 02 < ... < ag = Omax, where t = ONN) we 1, the function ur, remains constant.
claim that for any interval I, (a,,0;41 where = 0, ...
Consider any interval J;. By the above construction of a,, for any a I;, there exists a fixed set of regions Rz,1; = {R., [; Ra, C Pa ( .R..1....,, Ra, ). such that for any connected set R E R there exists w such that (a,, w) E R. Besides, for any E R.g,
J: there does not exist ur such that (a, w) R. This implies that for any a E L,, we can write 2 (a) as
" = sup Sz (ax, w) = sup
sup fx w) = max C, RERa, w:)a
weW
cEC,.
where Ca.:: = {CRu.. Ron.j E R contains the constant value that f' w) takes over R. Since the set C.,,1, is fixed, u (a) remains constant over I,-
Hence, we conclude that over any interval == (as, 01+1), for i 1,...., - 1, the function u (o) remains constant. Therefore, there are only the points as, for = 0. o 1, which the function u may not be continuous. Since = O(N), we have the conclusion.
By combining Lemma 3.1 and Corollary 2.2 we have the following result, which establishes learning guarantees for the utility function class li when f (a, w) admits piecewise constant structure.
Theorem 3.2. Consider the utility function class U uu X [0, H] Ia A). Assume that for any x E X there is a partition Pa = (Re,....., Ra.N of A x W, over each of which fa remains
constant. Then for any distribution D over X. and any 8 (0. 1). with probability least 1 5 over
the draw of S = {æI,..., 2m,...mmm } D we have that
(V log NN/))
EEwDD (2:) BowD (ua (x)] (x))l=
=0
5

---

160. and sgle?
(a) The piecewise structure of uz (a) and piecewise polynomial surface fa (a, w) sheer view.
Removing the surface fa (a, w) for better view of uz (a)), the boundaries, and the derivative curves.
Figure 1: demonstration the proof idea for Theorem 4.1 in 2D (w E R). Here, the domain of (a, w) is partitioned into four regions by two boundaries: circle (blue line) and parabola (green line). In each region i, the function fae (a, w) is a polynomial (a, w), which the derivative 0fa. = 0 is demonstrated by the black dot in the plane of (a, un). The value of = (ax is curve the
demonstrated in the red line, and the red dots in the plane (a, w) corresponds to the position where (a, w) = (a). We can that it occurs in either the derivative curves in the boundary. Our goal is to leverage this property to control the number of discontinuities and local maxima of u (a), which can be converted to the generalization guarantee of the utility function class U.
Here, ås E arg min J En (x;), and a E maX EEwD (
Proof. From Lemma 3.1 we know that any dual utility function un is piecewise constant and has at most (NN) discontinuities. Combining with Corollary 2.2 we conclude that Pdim(l() = Olog (log(NN)) Finally, standard result from learning theory (Theorem gives us the final guarantee.
In many applications, the partition of fae (a, w) into connected components typically defined by M boundary functions ha, (a, w).... as (a, w).. When the boundary functions are polynomials with bounded degree, we have the following concrete result for such a case, which is a direct consequence of Theorem 3.2
Corollary 3.3. Consider the utility function class = {ua X' X H) a a A}. Assuming for any x, there are M boundary functions hæ.1...., fe partitioning the domain A x W into over each of which fa. remains constant. Assuming that the boundary functions ha,i where i L,...,M, are polynomials in a,, of degree at most A. Then for any distribution DD over X, and any 8 E (0,1), 1), with probability at least -111, mmn Dmm we have that
Pa = p=={Be, [R.,,...,,Rg.
over the draw of
( MA) + (og(1/8)
D [Mas (x)] E8 ELnD ww (x)] =0
m
d+1
Proof. From Theorem F.9 there are at most N <
O
MA
connected components created by
d+1
M polynomial boundary functions in æ and a of degree at most A. Combining with Theorem 3.2 we have the final conclusion.
Remark Theorem 3.2 can be applied beyond polynomial boundaries, for example, settings where the boundary functions functtions consist of Pfaffian functions (which is generalization of polynomial functions that includes exponential and logarithmic
logarithmicfunctions functions). See Appendix for detailed discussion.

---

4 Piecewise polynomial parameter-dependent dual function
We examine the case where fa w) exhibits piecewise polynomial structure. Concretely, the domain A x W = [mmmin mmax x [min W "mmxx" is partitioned into N connected components by M algebraic sets Zmn.s = {(a, w) E A x W / w) = 0}, for j =
M. Here, each boundary function hæ. (a, w) is a polynomial in a and w of degree most As. The resulting parti- Re,N) consists of connected components Rg,,, each formed by connected component of A x W - - Zin.. and its adjacent boundaries (Definition 8) Within each connected component i the function (a, w) is a polynomial fa. (a, w) of degree at most Ap. We call f the piece function. The dual utility function " (a) can then be written as: max
tion Pæ = {Ræ.1
W (a) w:(a.w)EAXW
sup
far w)
max U (a), sup fa,i(a, w)= NE N. = =E(L,...N) w:)...))RR..
where " (a) = (aPu:(a,,) fa,((,,), w).
For a better understanding of the proof techniques used for the main results (Theorem 4.1 we encourage the reader to consider the simpler case where d demonstrates the piecewise structure of the dual function in this case. We can see that for any a the value of the dual u (a) is given by the value of fa w) on some point (á, w)) that lies either on some derivative curve or on one of the boundaries. Our proof obtains bound on the number of all such points (ā. it) that are "critical", i.e. where switch may occur between boundaries and derivative curves (or between pairs of boundaries, or pairs of derivative curves). Between such critical points, we use the Lagrange's multiplier theorem (Theorem F.3) to express the locations of the local extrema of "e as intersections of algebraic varieties. In summary, we use the above arguments to bound the number of discontinuities and local maxima of uzz (o)), which can converted to the generalization guarantee of the utility function class Ut
(see Appendix [.4). Figure |
Our main result in this section applies to the general multidimensional case, Rd While the overall proof strategy is similar, it needs significant extensions and refinements (Remark 4. We begin with the following regularity assumption on the piece and boundary functions fæ.s and ha.j- Assumption 1. Given any dual utility functions 4n (a) with corresponding boundary functions he. for j j= 1.....,, M, and piece functions fa, for = 1...., N, satisfying the following property: for any set of S boundary functions hy....,h hg chosen from the set of boundaries (ha.1....,,ha }. and any piece function chosen from the set of piece functions "fa. }, we assume
1. Extended linearly independent constraints qualification (ELICQ): The Jucobian Jn(a, w) has full row rank when evaluated at (a, u) E h (0). Moreover, if S S d, we assume that Jr has full row rank hen evaluated at (a, w) E h (O)
2. Non- degeeeeeyyyyyy (ND): the polynomial function P(a, w. A) = d A)) is not identically zero any (d + 1)-dimensional irreducible component of the real algebraic set
Zn {(a, w. A) E B-$4+1 Ib(a, w. A) = =0). Here, L(a, w, A) f(a, w) + X h(a, Remark 2. 1. The ELICQ assumption consists of two parts. The LJCQ part is a standard assumption in parametric optimization literature (or in constraint optimization in general, see e.g., 32)) and corresponds to assuming that Jn ( has full row rank when evaluated at (a,, w) E h (0).
= w).
for S S d. The second part, assuming that the Jacobian Jn,a, w) has full row rank when evaluated at (a, w) E h (O)) essentially says that 0 is regular value of h. This assumption directly implied by LICQ when S S d. For S 2 d+ 1 (where LICQ is inapplicable as rJnk(Jn, (w)) S d) this assumption implies that the solutions that satisfy h(a, w) O are isolated points for S = d + 1, or the solution set is empty for S > d 1. We note that this assumption is relatively mild since Sard's 's theorem (Theorem F.13) asserts that the set of regular value of a smooth map (h in this case) has Lebesgue measure in the co-domain.
2. The ND assumption is also relatively mild. Roughly speaking, it requires that there is at least one point (a. w. X) satisfying h(a, w) = O. where P(a, w, X) is non-zero. Intuitively, we use this assumption to show that the intersection of derivative curves with boundaries can be decomposed into a bounded number of monotonic curves ( (Definition 19), which we show to have favorable structure (Lemma F.19, playing an important role in our analysis.
We now state our main structural result, and provide a brief proof sketch (full proof in Appendix F.5). Theorem 4.1. Consider the utility function class u {ua : X > [0, H
[amin [mma]].. Assume that fa w) admits piecewise polynomial structure with
7

---

N piece functions fa.: (for i 1,.... N) and M boundaries functions has (for = Then for any distribution D over X, for any (0, w.p. at least 1 - 8 over the draw of S
1...., M) satisfying Assumption [
(0.,..., Fm
Dm,, we
0
o(V log Nog
have |BwDD(usead (z)] - BEEDDuu plwa--uuaaaa (2)]1
Here, ås E
arg m mn mum degree of piece functions fæ, and boundaries hej.
1 Ei= ua(a;) (Zi), o E maXaEA Eg-Dlua(at
(2)), and A = max Ap. Ad} is the maxi-
Proof Sketch. The proof consists of three main steps. Step 1: bound the number of possible discontinuities and local maxima of (a) under Assumption stronger assumption compared to Assumption [ Step 2: we show that, for any u (a) that satisfies Assumption | we can construct " (a) satisfies Assumption 3l and is arbitrarily close " (a). Step 3: we can this property to recover the learning guarantee for U. The key ideas of each step are sketched below.
1. We show that if the piece functions fa.: and boundaries l1g.i satisfy stronger assumption (Assumption 3 we can bound the pseudo-dimension of (Theorem F.25). The steps are:
(a) From Lemma 2. we know that it suffices to bound the number of discontinuities and local maxima of u From Lemma and Proposition F.2, we can bound the number of discontinuities and local maxima of uz by bounding those of uzzi for any piece i. Hence, in the next few steps, our main object of study is "z,."
(b) We first demonstrate that the hyperparameter domain A can be partitioned into intervals using d+1
the set of points A1 C A that has at most O (24)d+1 [cM d++1
elements. For each interval
7, there exists set of subsets of boundaries S C 2Ha.. such that for any set of boundaries
S (hs.1..... hs.s} S the intersection of boundaries {(a, w) | h(a, w) O, h S) in S contains feasible point (a, w) for any in that interval. The key idea of this step is to upper bound the number of (--extreme points (Definition 7 of connected components of such intersections, using Warren's 's theorem (Lemma E.8. In words, the goal of this step is partition the hyperparameter space AA into intervals, that over any interval I in the partition, there is some of set of boundaries Sh such that for any a' E Le, there is at least one point that lies in the intersection of set of boundaries S E Sy. that has a-coordinate equal a'.
(c) Now note that, for any wa that maximizes fa, w) for any fixed a, due to the Lagrangian multipliers theorem (Theorem F.3. there is set of boundaries S {hs, hs.s) } such that hs(a, ) = O, Ls War Xa) = 0, for some Xa Here, hs (hs,1, hs,s) is the polynomial mapping constructed by the boundary functions corresponding to some set S of boundaries, Ls(c w, A) fa, w) A hs(a, w) is the corresponding Lagrangian function. Next, our goal is to decompose the solution set of the above Lagrangian into a union of monotonic curves (Definition 19), which we show to have the following property: for any I, there is at most one point (a, w. A) in the monotonic curve C (Lemma
Towards this goal, we refine the partition of A into intervals, using the set of points A2 that contains points in Ai and some additional points in set B, for a total of O (2A)22+1 ( (cM) A 4d ( (eM ())))))) elements. Here, B is the set of a-coordinates of the set of points in B", which contains the points (a, w. A) that satisfy
hs(a, w) = 0. Vw w. = det (w, (w, = 0.
where Jks (w. A) is the Jacobian of T.s = vwLs) with respect to (w, A). Under Assumption 2 the number of such points is bounded, leading the number of elements in B being bounded. In any interval I, in the partition of A created by the set of points A2, we claim that the set Z = (aa, w. >) Essa,, w. A) = 0} defines a smooth one-dimensional manifold in the space of (a, w. A).
(d) Next, we want to partition the hyperparameter space a into intervals, such that in any interval, the function "²,; can be written as the point-wise maximum of the piece function fa, w) along some fixed set of monotonic curves. Concretely, we further refine the partition of into intervals, using the set of points As C A that contains the points in A₂ and some extra points in the set D. Here, D contains the a-extreme points of connected components the algebraic set Z (where kg = (hs, V Vw as defined in (c)) and the a-coordinate of the intersections between Z with
8

---

another boundary h' & S, for some fixed set of the boundaries S. In any interval 1,, there is fixed set C, of monotonic curves such that for any a E I. the function u can be written as U (a)) = maxcec, gc(a'), where (cberegg(a')) gc(a') = fa,i(a', warr), and (a', w'' >a') ) is the unique point in mono- tonic curve C' that has a-coordinate equal to a' (a property of monotonic curve, see Lemma F.19). Therefore, over this interval, (a) is continuous, since each gC ) is continuous (Lemma
(e) Moreover, we show that in each interval /,. any local maximum of M2. (a) is a local maximum of (a, w) along a monotonic curve (Lemma 1.21). Again, we can control the number of such
points using Bezout's theorem (Corollary [F.10] and Assumption 3. Finally, we put together
all the potential discontinuities and local extrema of "2z5- Combining with Lemmal 2.1
we have
the upper-bound for Pdim(L4) (Theorem F.26).
We show that for any function class LI whose dual functions u have piece functions and boundaries satisfying Assumption 1 we can construct a new function class V. The dual functions 2.x of V have piece functions and boundaries that satisfy Assumption 3 Moreover, we show that ||u v= oo can be made arbitrarily small. See Lemma F.30 for proof overview as well as the detailed proof. 3. Finally, using the results from Step (1), we establish an upper bound on the pseedo- dimension for the function class V described in Step (2). The result can then be used to determine the
tearning complexity of 24 by applying Lemma C.3 and Lemma C.4 Standard learning
theory literature then allows us translate the dearning-theoretie complexity of lI into its learning guarantee. This final step is detailed in Appendix F.5
4.1 Relaxation to approximate-ERN oracle
The preceding analysis implicitly assumes access to an exact-ERM (e-ERM) oracle in defining the dual utility function. In practice, however, such an exact oracle is unavailable; instead, we typically have access to an approximate- (a-ERM) orucle (for example, the weights learned using gradient descent based optimization) which we formalize below.
Assumption 2 (ç-a-ERM oracle and its induced function class). Consider a utility function class u = fua= X + [0, H a E A}. Assume that we access to a E-a-ERM oracle such that given (ax)-
a problem instance x and a hyperparameter a, return Wa such that |ut (a) - -v' (a)) < E. where
"ig (a) = suPwila, (aP)) AxX [m( w), and (()( Sm((x, w.). We further define V = {wa X
[0, H] a E A} the induced function class by the E-a-ERM oracle, where vx( 2 (a).
The below gives learning guarantees for the induced function class V (proof in Appendix G
Theorem 4.2. Assuming U = 1wwm= : X + [0, H) | a E [Orming [max]] satisfying Assumption 7 Let V = (va- X [0, H] a E A} be the induced function class by E-a-ERM oracle. Then for any distribution D over X, for any 8 E (0, 1), wap. at least 1 - 5 over the draw of S = {x11,... am ~
DT,, we have EEED ( (x)] - Ex- (Va (x)]l= =0]1=00 0 (V log N+d log(doog(AAA (AM (MM) +
5 Applications
We demonstrate the application of our results to two specific hyperparameter tuning problems in deep learning. We note that the problem might be presented as analyzing a loss function class C fla= : X + [0, H) a E AA} instead of utility function class 44 (ua, X - [0, H) a E A]. but our results still hold, just by defining u, (x) = H - f. (z). We establish bounds on the complexity of tuning the linear interpolation hyperparameter for activation functions, which is motivated by
DARTS [14,, and exploring the tuning of graph kernel parameters in Graph Neural Networks (GNNs), in both regression and classification problems. We present below the guarantee for tuiing interpolation hyperparameter of neural activation functions here (details and other applications in Appendix Hp.
We consider feed-forward neural network with L layers, W: parameters in the 7th layer, and W Σt_ W: is the total number of parameters. We denote by k; the number of computational nodes in layer i, and let ls = Σ - k;, At each node, we choose between two piecewise polynomial activation functions, 01 : R + IR and 02 R + RR. The domain of the activation functions is partitioned by finitely many breakpoints, such that the activation function is polynomial in each partition. For exam- ple, O a breakpoint of the ReLU activation function. Liu et al. [14] propose a simple method for se- lecting activation functions: during training, they define general activation function weighted
9

---

combination of and 02. While their framework is more general, allowing for multiple activation functions and layer-specific activation, we analyze a simplified version. The combined activation func- tion is given by (x)) oo1 (z) + (1 (ar),, where [0. 1] is the interpolation hyperparameter.
This framework can express functions like the parametrie ReIJU, a (z) = max (0. 2} + a mi,(0,2]
which empirically outperforms the regular ReLU which corresponds to = 0 33
In parametric regression, the final layer output g(a, w, x) 2 RD. where E W RW is the parameter vector and a is the architecture hyperparameter. The loss for a single example (æ, y) is llg(a, w. - yl and for T examples, we define
1 Σ
la (x
min WEW T (X.))((X)))
Ils(a, w, y112 min (((X)))) w))
WEW
With A' as the space of Texample sets, we define the loss function class LAF = {la : X
R a E [Omin:: (kmax] }- We aim to provide learning-theoretic guarantee for LAF Given problem instance (X, Y) the key idea is to establish a piecewise polynomial structure for the parameter-dependent dual function (a, w), and then apply our main result Theorem 4.1 We establish this structure by extending the inductive argument due to Bartlett et al. (34) who establish the piecewise polynomial structure of the neural network output as function of just the parameters w (i.e. when there are no hyperparameters) on any fixed collection of input examples.
Theorem 5.1. Let CAF denote loss function class defined above, with activation functions 01,02 having maximum degree A and maximum breakpoints p. Given problem instance æ = (X, (),Y). the dual loss function defined as t (a) == minwew f(x, a, w) min fæ w). Then, a (a, w) admits piecewise polynomial structure with bounded pieces and boundaries. Further, if the piecewise structure of fa w) satisfies Assumption 7 thenfor any ó E (0, 1). w.p. at least 1
over the draw of problem instances S = (xI..... Fm Dm, where D is some distribution over X. we have
={
| (aa-D((aas()) - RENDD (x)) O (
L log A + LW log(T (kk( + log(1 (1/5)
6 Conclusion and future work
In this work, we combined tools from multiple fields, including algebraic geometry. differential geometry, constrained optimization, and statistical learning theory to provide bounds on the sample complexity of hyperparameter tuning when the parameter-dependent dual function admits polynomial structures. We further show that this piecewise polynomial structure is observed in data-driven model hyperparameter tuning of neural networks, specifically for tuning graph kernels for graph convolutional networks and interpolation parameters for neural activation functions. We note that our proposed framework is applicable beyond neural networks for data-driven algorithm design.
A major open question is to extend our work to multiple hyperparameters (i.e., E R"). For the case of one-dimensional hyperparameter, we showed that when the parameter- dependent dual function fo (oe, w) is piecewise polynomial, then the dual utility function (a) has bounded oscillations, even if it is not as structured as the parameter-dependers dual; this bounded oscillations structure is sufficient to imply learnability. An interesting open technical question is determining the analogous structure to bounded oscillations in the case of multiple hyperparameters. In the case of one-dimensional hyperparameters, we leveraged and extended tools from differential geometry, combined with constrained optimization techniques to prove that the dual utility function has bounded oscillations. We believe that our idea can serve as first step in generalizing to the high-dimensional regimes. Another open question is to give a simpler analysis for one-dimensional hyperparameter, potentially under weaker assumptions.
Acknowledgments
This work was supported in part by NSF grants CCF-1910321 and IIS- 19014434
10

---

References
[1] Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2019.
[2] OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Floren- cia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. GPT-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
[3] Frank Hutter, Holger H Hoos, and Kevin Leyton- Broon- Sequential model-based optimization for general algorithm configuration. In Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011. Selected Papers 5, pages 507-523. Springer, 2011.
[4] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. Advances in Neural Information Processing Systems, 24, 2011.
[5] Jasper Snock, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning algorithms. Advances in Neural Information Processing Systems, 25, 2012.
[6] Jasper Snock. Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable Bayesian optimization using deep neural networks. In international Conference on Machine Learning, pages 2171-2180. PMLR, 2015.
[7] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012.
[8] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hy- perband: A novel Learning Research, 18(185)11-5, 2018.
approach to hyperparameter optimization. Journal of Machine
[9] Elad Hazan, Adam Klivans, and Yang Yuan. Hyperparameter optimization: A spectral approach. ICLR, 2018
[10] Rishi Gupta and Tim Roughgarden. PAC approach to application-specific algorithm selection. In Proceedings of the 2016 ACM Conference Innovations in Theoretical Computer Science, pages 123-134, 2016.
[11] Maria-Florina Balcan.
Algorithm Design. In Tim Roughgarden, editor, Beyond Worst Case Analysis of Algorithms. Cambridge University Press, 2020.
[12] Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient learn high-performen algorithms? Generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pages 919-932, 2021.
[13] Prajit Ramachandran, Barret Zoph, and Quoe V Le. Searching for activation functions. arXiv preprint arXiv: 1710.05911, 2017.
[14] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019.
[15] Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In Interna- lional Conference on Learning Representations, 2017.
[16] Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In international Conference on Machine Learning, pages 4095-4104 PMLR, 2018
[17] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European conference computer vision (ECCV), pages 19-34, 2018.
11

---

[18] James Bergstra, Daniel Yamins, and David Cox. Making science of model search: Hyper- parameter optimization in hundreds of dimensions for vision architectures. In international Conference Machine Learning, pages 115-123. PMLR, 2013.
[19] Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network archi- tectures using reinforcement learning. In International Conference on Learning Representations, 2017.
[20] Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 10293-10301) 2021.
[21] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 20(55):1-21, 2019.
[22] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[23] Maria-Florina Balcan and Dravyansh Sharma. Data driven semi semi-supervised learning. Advances Neural Information Processing Systems, 14:14782-14794, 2021.
[24] Dravyansh Sharma and Maxwell Jones. Efficiently learning the graph for semi-supervised learning. In Uncertainty in Artificial Intelligence, pages 1900-1910. PMLR, 2023.
[25] Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning-theoreti foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pages 213-274, PMLR, 2017.
[26] Maria-Florina Balcan, Travis Dick, and Manuel Lang. Learning to link. International Conference Learning Representation, 2020.
[27] Maria-Florina Balcan, Travis Dick, and Colin White. Data-driven clustering via parameterized Lloyd's families. Advances in Neural Information Processing Systems, 31, 2018.
[28] Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Structural analysis of branch-and-cut and the learnability of Gomory mixed integer cuts. Advances in Neural Information Processing Systems, 15:33890-339003 2022.
[29] Maria-Florina Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Provably tuning the ElastioNet across instances. Advances in Neural Information Processing Systems, 35:27769-27782. 2022.
[30] Maria-Florina Balcan, Anh Nguyen, and Dravyansh Sharma. New bounds for hyperparameter tuning of regression problems across instances. Advances in Neural Information Processing Systems, 36, 2023.
[31] Georg Still. Lectures on parametric optimization: introduction. Optimization Online, page 2, 2018.
[32] Jorge Nocedal and Stephen J Wright, Numerical optimization. Springer, 1999.
[33] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026-1033 2015.
[34] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC dimension bounds for piccewise polynomial networks. Advances in Neural Information Processing Systems, 11, 1998.
[35] Wolfgang Maass. Neural nets with superlinear VC-dimension. Neural Computation, 6(5):877~ 884, 1994.
[36] Marek Karpinski and Angus Macintyre. Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks. Journal of Computer and System Sciences, 54(1):169-176. 1997.
12

---

[37] Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC- dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
[38] Peter Bartlett, Dylan J Foster, and Matus Telgarsky. Specttally-normalized margin bounds for neural networks. Advances in Neural Information Processing Systems, 30, 2017.
[39] Nir Ailon, Bernard Chazelle, Kenneth Clarkson, Ding Liu, Wolfgang Mulzer, and C Sesaadhri. Self-improving algorithms. SIAM Journal on Computing, 40(2):300-37,,201
[40] Rishi Gupta and Tim Roughgarden. Data-driven algorithm design. Communications of the ACM, 63(6):87-94 2020.
[41] Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, and David Woodruff. Learning the positions in countsketch. In The Eleventh International Conference Learning Representations, 2023.
[42] Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning-based low-rank approximations. Advances in Neural Information Processing Systems, 32, 2019.
[43] Nir Ailon, Omer Leibovitch, and Vineet Nair. Sparse linear networks with a fixed butterfly structure: theory and practice. In Uncertainty in Artificial Intelligence, pages 1174-1184 PMLR, 2021.
[44] Ila Luz, Meirav Galun, Haggai Maron, Ronen Basri, and Irad Yavneh. Learning algebraic multigrid using graph neural networks. In international Conference on Machine Learning, pages 6489-6499, PMLR, 2020.
[45] Mikhail Khodak, Edmond Chow, Maria-Florina Balcan, and Ameet Talwalkar. Learning to relax: Setting solver parameters across a sequence of linear system instances. In The Twelfth International Conference on Learning Representations, 2024.
[46] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. Advances in Neural Information Processing Systems, 29, 2016.
[47] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. In Proceedings of the 2018 ACM Conference Economics and Computation, pages 173-174, 2018.
[48] Peter Bartlett, Piotr Indyk, and Tal Wagner. Generalization bounds for data-driven numerical linear algebra. In Conference on Learning Theory, pages 2013-2040. PMLR, 2022.
[49] Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems, 34:4015-4027, 2021.
[50] Maria-Florina Balcan and Dravyansh Sharma. Learning accurate and interpretable decision trees. Uncertainty in Artificial Intelligence (UAI), 2024.
[51] Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 603-614, IEEE, 2018.
[52] Maria-Floring Balcan, Travis Dick, and Dravyansh Sharma. Learning piecewise lipschitz functions in changing environments. In International Conference on Artificial Intelligence and Statistics, pages 3567-3577. PMLR, 2020.
[53] Dravyansh Sharma. No internal regret with non-conves loss functions. In Proceedings of the AAAÍ Conference on Artificial Intelligence, volume 38, pages 14919-14927, 2024.
[54] Maria-Florina Balcan, Christopher Seiler, and Dravyansh Sharma. Accelerating erm for data- driven algorithm design using output-enssitive techniques. Advances Neural Information Processing Systems, 37:72648-72683 2024.
13

---

[55] Dravyansh Sharma and Arun Suggala. oo-iine hyperparameter transfer for stochastic bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 20362-20370, 2025.
[56] Hector Mendoza, Aaron Klein, Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Towards automatically-tumn neural networks. In Workshop on automatic machine learning. pages 58-65. PMLR, 2016.
[57] Renato Negrinho and Geoff Gordon. Deeparchitect: Automatically designing and training deep architectures. arXiv preprint XXiv:/704.0879) 2017.
[58] Thomas Elsken, Han-Hen Metzen, and Frank Hutter. Simple and efficient architecture search for CNNs. In Workshop on Meta-Learning at NIPS, 2017.
[59] Xuanyi Dong and Yi Yang. NAS- 20S-Bench-201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations, 2020.
[60] Yash Mehta, Colin White, Arber Zela, Arjun Krishnakumar, Guri Zabergja, Shakiba Moradian, Mahmoud Safari, Kaicheng Yu, and Frank Hutter. NAS-Bench- Bench-Suit: NAS evaluation is (now) surprisingly easy. International Conference on Learning Representations, 2022.
[61] Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Geometry-aware gradient algorithms for neural architecture search. In International Conference on Learning Representations, 2021.
[62] Avrim Blum and Shuchi Chawla. Learning from labeled and unlabeled data using graph mincuts. In Proceedings of the Eighteenth international Conference on Machine Learning, pages 19-26, 2001.
[63] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the 20th International Conference on Machine Learning (ICMI.), pages 912-919, 2003.
[64] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in Neural Information Processing Systems, 16, 2003.
[65] Xiaojin Zhu. Semi-supervised learning with graphs. Carnegie Mellon University, 2005.
[66] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[67] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International Conference on Machine Learning, pages 6861- PMLR, 2019.
[68] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272 PMLR, 2017.
[69] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International Conference on Machine Learning, pages 344-353. PMLR, 2018.
[70] Maria Florina Balcan, Anh Tuan Nguyen, and Dravyansh Sharma. Algorithm configuration for structured pfaffian settings. Transactions on Machine Learning Research, 2025.
[71] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[72] David Pollard. Convergence of stochastic processes. Springer Science & Business Media, 2012.
[73] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Refined bounds for algorithm configuration: The knife-edge of dual class approximability. In international Conference on Machine Learning, pages 580-590. PMLR, 2020.
14

---

[74] Shai Shalev-Shwart and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
[75] Tyrrell Rockafellar. Lagrange multipliers and optimality. SIAM review, 35(2):183-238, 1993.
[76] Norbert Sauer. On the density of families sets. Journal of Combinatorial Theory, Series A. 13(1):145-147, 1972.
[77] Hugh E Warren. Lower bounds for approximation by nonlinear manifolds. Transactions the American Mathematical Sociery, 133()): 1968.
[78] I Shafarevich. Basic algebraic geometry, 1994.
[79] Ernst Kunz and Richard G Belshoff. Introduction to plane algebraic curves, volume 68. Springer, 2005.
[80] Joel Robbin and Dietmar A Salamon. Introduction to differential geometry. Springer Nature, 2022.
[81] Creighton Buck. Advanced calculus. Waveland Press, 2003.
[82] Leonidas Guibas and Micha Sharir. Combinatories and algorithms of arrangements, In New Trends in Discrete and Computationnal Geometry, pages 9-36. Springer, 1993.
[83] Daouda Niang Diatta, Fabrice Rouillier, and Marie-Francoise Roy. On the computation of the topology of plane curves. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pages 130-137, 2014.
[84] Jinsan Cheng, Sylvain Lazard, Luis Peñaranda, Marc Pouget, Fabrice Rouillier, and Elias Tsigaridas. On the topology real algebraic plane curves. Mathematics Computer Science, 4:1 13-137, 2010.
[85] Victor Milenkovic and Elisha Sacks. An approximate arrangement algorithm for semi-algebraic curves. In Proceedings of the twenty-second annual Symposium on Computational Geometry, pages 237-246, 2006.
[86] Jacek Bochnak, Michel Coste, and Marie- Frrie-FFrancise Roy. Real algebraic geometry, volume 36. Springer Science & Business Media, 2013.
[87] Askold G Khovanski. Fewnomials, volume 88. American Mathematical Soc., 1991.
15

---

Contents
Introduction
2
Problem setting and preliminaries
2.1
Discontinuities, local extrema and the pscudo-dimension
Piecewise constant parameter-deepndeet dual function
Piecewise polynomial paramectr-depenndet dual function
4.1
Relaxation to approximate- ERM oracle
Applications
6
Conclusion and future work
10
Additional related work
18
Technical challenges and novelty
19
Learning theory background
20
Uniform convergence
20
Shattering and pseudo-dimension
20
Rademacher complexity
20
D Additional results and omitted proofs for Section 2.1
21
D.I Oscillations and connection pseudo-dimension
D.2 Omitted proof' for Section 2.1
22
An illustration for the proof Section
24
Additional results and omitted proofs for Section
24
F.
General auxiliary results
24
F.1.1
Results for analyzing local maxima of pointwise maximum function
24
F.1.2
Results for bounding the number of connected components defined by alge- braic sets
25
F2
Background differential geometry
26
Monotonic curve and properties
27
Simpler illustrative case: hyperparameter tuning with a single parameter
30
Omitted proofs for Theorem 4.1
33
Additional details for Section 4.1
44
Additional details for Section
44
H.I Tuning the interpolation parameter for activation functions
44
16

---

H.1.1
Omitted proofs for parametric regression setting
44
H.1.2
Binary classification setting
45
H.2
Data-drived hyperparameter tuning for graph polynomial kernels
46
H.2.1
Classification setting
46
H.2.2
The regression setting
48
discussion on how to capture flatness of optima our framework
50
An application to Pfaffian functions
51
17

---

A Additional related work
Learning-theoor theoretic complexity of deep nets. A related line of work studies the learning- theoretic complexity of deep networks, corresponding selection of network parameters (weights) over single problem instance. Bounds on the VC dimension of neural networks have been shown for piecewise linear and polynomial activation functions [35] 34 as well the broader class of Pfaffian activation functions [36]. Recent work includes near near-tight bounds for the piecewise linear activation functions 37 and data data-dependent margin bounds for neural networks [38.
Data-driven algorithm design. Data-driven algorithm design 39 40 is an emerging field that adapts algorithms' internal configuration to specific problem instances, particularly in parameterized algorithms with multiple performance-dictatin hyperparameters. Unlike traditional worst-case or average-case analysis, this approach assumes problem instances come from an application-specife distribution. By leveraging available input problem instances, this approach seeks to maximize empirical utilities that mcasure algorithmic performance for those specific instances. This method has demonstrated effectiveness actoss various domains, including low-rank approximation and 43 accelerating linear system solvers 44 45], mechanism design
dimensionality reduction 41 42
46
47 sketching algorithms
48 branch-and-cut algorithms for (mixed) integer linear programming aaong others. Prior work has also studied online learning of
49
learning decision trees
50
algorithms [51] [2 53 54
55 In this work, focus mainly the statistical learning setting and extending our techniques to online learning is an interesting future direction.
Neural architecture search. Neural architecture search (NAS) captures a significant part of the engineering challenge in deploying deep networks for given application. While neural networks successfully automate the tedious task of "feature engineering" associated with classical machine learning techniques by automatically learning features from data, it requires tedious search over a large search space to come up with the best neural architecture for any new application domain. Multiple different pproaches with different search spaces have been proposed for effective NAS, including searching over the discrete topology of connections between the neural network nodes, and interpolation of activation functions. Due to intense recent interest in moving from hand-crafted to automatically searched architectures, several practically successful approaches have been developed
including framing NAS Bayesian optimization [8 56 20, reinforcement learning [15 19],
tree search [57]58) gradient- based optimization [4]. among others, with progress measured over standard benchmarks [59 66). [61] introduce geometry-aware mirror descent based approach to learn the network architecture and weights simultaneously, within a single problem instance, yielding a practical algorithm but without provable guarantees. Our formulation is closely related tuning the interpolation parameter for activation parameter in the NAS approach of [14] which can be viewed as a herttaatypprrrrattetr generalization of our setup. We establish the first learning guarantees for the simpler case of single perraarameteer tuning.
Graph-based learning. While several classical [62
63
64 65 as well as neural models [22 66
67 68 have been proposed for graph based learning, the underlying graph used to represent the data typically involves heuristically set graph parameters. The latter approach is usually more effective in practice, but comes without formal learning guarantees. Our work provides the first provable guarantees for tuning the graph kernel hyperparameter graph neural networks.
graph-based
Hyperband is one of the most notable works for hyperparameter tuning of deep neural networks with principled theoretical guarantees, albeit under strong assumptions. Here, we provide a detailed comparison between the guarantees presented in Hyperband and our results.
Comparison to Hyperband g
Hy Hyperparameter configuration setting: Theoretical results (Theorem 1, Proposition 4) in Hyperband assume finitely many distinct arms and the guarantees are with respect to the best arm in that set. Even their infinite arm setting considers a distribution over the hyperparameter space from which n arms are sampled. It is assumed that n is large enough to sample a good arm with high probability without actually showing that this holds for any concrete hyperparameter loss landscape. It is not clear why this assumption will hold in our cases. In sharp contrast, we seek optimality over the entire continuous hyperparameter hyperparameter range for concrete loss functions which satisfy a piecewise polynomial dual structure.
18

---

2. Guarantees: The notion of "sample complexity" in Hyperband is very different from ours. Intuitively. their goal is to find the best hyperparameter from learning curves over fewest training epochs, assuming the test loss converges a fixed value for each hyperparameter after some epochs. By ruling out (successively halving) hyperparameters that are unlikely to be optimal early, they speed up the search process (by avoiding full training epochs for suboptimal hyperparameters). In contrast, we focus on model hyperparameters and assume the network can be trained to optimality for any value of the hyperparameter. We ignore the computational efficiency aspect and focus on the data (sample) efficiency aspect which is not captured in Hyperband analysis.
3. Learning setting: Hyperband assumes the problem instance is fixed, and aims to accelerate the random search of hyperparameter configuration for that problem instance with constrained budgets (formulated
eure-explooation non-stochastic infinite- armed bandit). In contrast, our results assume problem distribution D (data-driven setting), and bounds the sample complexity of learning a good hyperparameter for the problem distribution D.
B Technical challenges and novelty
Our main contributions (Lemma 3.2 Theorem in this paper is introducing new technique for analyzing the model hyperparameter tuning lata-driven setting, where the parameter- -eepedee dual function (a, w) admits a specific piecewise polynomial structure. In this section, we will make an in-depth comparison between setting and the settings in prior work in data-driven algorithm hyperparameter tuning, and discuss why our setting is challenging and requires novel techniques to analyze.
Challenges. Our setting requires significant technical novelty beyond prior work in data-driven algorithm design. Generally, most prior work on statistical data-driven algorithm design falls into two categories:
1. The hyperparameter tuning process does not involve the parameters w, that is, the learning algorithm is completely determined by the hyperparameter a and has parameters that need to be tuned using& training set. Some concrete examples include tuning hyperparameters of
hierarchical clustering algorithms (25] 26), branch and bound (B&B) algorithms for (mixed) integer linear programming [69 28 and graph-based semi-supervised learning [23). The typical
approach is to show that the utility function u (a) admits specific piecewise structure of
typically piecewise polynomial and rational.
2. The hyperparameter tuning process involves the parameters w, for example in tuning regularization hyperparameters
linear regression. However, here the optimal parameters w w²(o) (a:) can either have a closed analytical form in terms of the hyperparameter a 22 or can be easily approximated in terms of a with bounded error (70).
However, in our setting, the utility function u (a) is defined via an optimization problem " (a) = max (a, w), where the parameter-dependent dual function fa (a. w) admits a piece- wise polynomial structure. This involves the parameter it does not belong to the first case, and it is not clear how to use the second approach either. This is why our problem is quite challenging and requires the development of novel techniques.
New techniques. guarantee for U.
Two general approaches are known from prior work to establish a generalization
1.
The first approach is to establish pseudo-dimension bound for 24 via alternatively analyzing the searning-thhorede dimensions of the piece and boundary function classes, derived when establishing the piecewise structure of uc (a) (following Theorem 3.3 of (12). We build on this idea. However, in order to apply it we need significant innovation to analyze the structure of the function u* in our case.
2.
The second approach is specialized to the case where the computation of u (a: can be described via the GJ algorithm (4),, where can do four basic operations (+, -, X, +) and conditional statements. However, it is not applicable to our case due to the use of a max operation in the definition.
As mentioned above, we follow the first approach though we have to develop new techniques to analyze our setting, Here, choose analyze ua((a) via indirectly analyzing fa w), which is
19

---

shown in some cases to admit piecewise polynomial structure. To do that, we have to develop the following:
1. A connection between number of discontinuities and local maxima of the dual utility function We (a), and the learning-theoretic complexity of 4.
An approach to upper-bound the number of discontinuities and local extrema of u (a). This is done using ideas from differential/algerrii geometry, and constrained optimization. We note that even the tools needed from differential geometry are not readily available, but we have identify and develop those tools (e.g. monotonic curves and its properties, see Definition 12 and Lemma 18).
That corresponds the main contribution of our papers (Theorem 3.2 4.1). We then demonstrate the applicability of our results to two concrete problems in hyperparameter tuning in machine learning (Section
C Learning theory background
C.1 Uniform convergence
Let F be a real-valued function class which takes input from domain X, and DD is distribution over X. for any e 0, and any 5 E (0, 1), there exists number (e, 8) depending on and 6 such that with probability least 8 over the draw of m 2 (e,, iid. samples ....... Dm D, we have
Definition (Uniform convergence,
1
Am
sup feF
Σ f(x) - EEwDIf(()) <c.
i=1
then say that (the empirical process of) F. uniformly converges with sample complexity N (e,,)) 8).
C.2 Shattering and pseudo-dimension
We now formally recall the definition of shattering and pseudo dimension, the main learning theeortit complexity used throughout this work, as well as the corresponding generalization results.
72)). Let be a real-valued function class, of which each function takes input in X. Given set of imputs (II,.... Fm. C X, say that S is pseudo-shattered by H if there exists set of real-valued thresholds ri,..., I'm E I such that
Definition 2 (Shattering and ggeudo-dimension
H[sign(u( (u(x))) - -r),...., sign((((<m))) rm)) u E 2f) 2m
The pseudo-dimension of H. denoted as Pdim(U), the maximum size m of an imput set that H. can shalter.
The following classical result shows that a real-valued bounded function class has finite pseudo- dimension, then it has uniform convergence property.
Theorem C.1 (172)). Given a real-valued function class U whose range is [0, H), and assume that Pdim(L() is finite. Then, given any ö (0, 1), and any distribution D over the input space X, with probability at least 8 over the drawn of S = = {xi,...,
".....,am, Fm. ~ Dm, we have
Pdim(()) + In 1))
u(x,) EEND[u(x)] 5 HH m
C.3 Rademacher complexity
Besides, we also use the notion of Rademacher complexity, as well as its connection to the pseudo- dimension. This learning-theann thhooretic complexity notion very useful in analysis, especially for simplifying Assumption 3 to Assumption I
critical step when establishing Theorem F25
Definition 3 (Rademacher complexity, X' to J0, 1). For set of inputs $ = {xi,.... am we define the empirical Rademacher complexity
(7)). Let F be a real-valued function class mapping from
20

---

(F)(F)
Rs(F)
-Be
Be widd unif #1
sup cf(x)) fEF i=1
m
We then define the Rademacher complexity D',, where distribution over X, as
D (F)
EgnD (F)
Furthermore, we define
Lm (F)
sup (F). SEX
Theorem C.2 (Empirical Rademacher complexity gives uniform convergence). Let F be a class of functions mapping X [0,1] I.. Then for any ó (0, 1), with probability at least ô the draw of S ~ "Dm, the following holds simultaneously for all E
1 Σ
22)) +3/ In(2/0)
Ba-D[f(e)] & m ZES
The following lemma provides a useful result that allows us to relate the empirical Rademacher complexity of two function classes when the infinity norm between their corresponding dual utility functions is upper-bounded.
Lemma C.3 (73).. Let {fa= + 0, 1] A} and {ga : X - [0, E A}
where A C Rd. For any S S X, we have
1 [
(s(F)
(9)
Ellfa
llfe golloo
where fz A [0, and gh A [0, 1] are defined as
aa) == fa())) == (=a))=9a(z))
The following theorem establishes a connection between eseudo-dimensiog and Rademacher com- plexity.
Lemma C.4 ((74)) Let F be functionn class with bounded pseudo-dimensiee consisting of functions F - [0, 1). Then (m)(F) = O Pdim(
D Additional results and omitted proofs for Section 2.1
In this Appendix, we will recall the definition of oscillations of a real-valued function proposed by Balcan et al. [12), and extend their results obtain useful lemmas for bounding the pseudo-dimension of our function classes.
D.1 Oscillations and connection to pseudo-dimension
When the function class 2/ { (ua X' +
R} is parameterized by real-valued index a, 12 propose a convenient way for bounding the pseudo-dimension of H. via bounding the oscillations of the dual function 4 (a) u. (x) corresponding any problem instance æ. In this section, will recall the notions oscillations and the connection of the pseudo-dimension of a function class with the oscillations of its dual functions. This tool is very helpful in later analyses.
Definition 4 (Oscillations, [22). A function h R + R has at most B oscillations ifr every 2 E R. the function + [(h())2=) is piecewise constant with most B discontinuities.
An illustration of the notion of oscillations can be found in Figure 2 Using the idea of oscillations, one can analyze the seeudo-dimensee the oscillations of their dual functions, formalized as follows.
parameterized function classes by alternatively analyzing
Theorem D.I (12). Lei l = {wg X - a IR), of which euch dual function ui (at) has at most B-oscillations. Then Pdim(U) Olog B).
21

---

Mp)
Byonas)
31
19
Figure 2: This figure demonstrates the oscillation property for function h R - R. The oscillation of function h is defined the maximum number of discontinuities in the function [(b(a)2=)+ the threshold z varies. The figure shows several graphs of [[b(a)2=} corresponding to different choices of the threshold We can observe that when number discontinuities, which is 4. This number of discontinuities also the maximum for any choice of Therefore, conclude that h has 4 oscillations.
21, the function [h(a)2=> exhibits the highest
D.2 Omitted proofs for Section
The following result allows to draw a connection between the number of discontinuities and local maxima of piecewise continuous function and its number of oscillations.
Lemma D.2. Let R + be a piecewise continuous function which has at most B₁ discontinuity points, and has at most B2 local maxima. Then h has most O(B, + B2) oscillations.
Proof. We show that in each interval where h continuous, we can bound for any z, the number of solutions of h(a)= using the number of local maxima of h. Aggregating the number of solutions across all continuous intervals yields the desired result.
For any z E R, consider the function g(a) = [[(a))==)- By definition, on any interval over which
is continuous, any discontinuity point of g((x) is root of the equation I((x)) = z. Therefore, have across
suffices give upper-bound the number of roots that the equation h(a)) all the intervals where continuous.
Let 0 02 <
ON be the discontinuity points of h, where N < B1 from assumption. For convenience, let ag = -0o and aN+1 = 00. For any i ,,...,,, N,, consider an interval I, (a,, ag + 1) over which the function /i is continuous. Assume that there are E, local maxima of the function in the interval I, meaning that there are at most 2E, + 1 local extrema. We now claim that there at most 2E, + 2 roots of h(a) in I. We proceed by contradiction: assume that af < <5 < ... < 02 + are 2E,- + 3 roots the equation h(a) = 2, and there is no other root in between. We have the following claims:
Claim there is at least one local extremum local extrema, meaning that cannot be constant over (a), a +2]. Therefore, there exists some a' E (aj, .3+1) such that l((") * z, and note that h(a?) = h(a)+1) Since continuous over [a3, 11.. from extreme value theorem Theorem F.6). h (when restricted to Jat, a141 reaches minima and maxima over [ar; +1 However, since there exists a' such that I((a)) ) + 2,
in (aj, 0)+1) Since h has finite number of
then has to achieve minima or maxima in the interior (a), a5+1). That is also a local extremum of h.
Claim 2: there are at least 2E, + 2 local extrema in (aj a 22. This claim follows directly from Claim 1.
Claim 2 leads to a contradiction. Therefore, there are at most 2E, + 2 roots in the interval I.. which implics there are EN 2E,- + 2N roots the intervals 4 for = 1,..., NN. Note that Σi=o E, < B2, N Bj by assumption, and each discontinuity point of h could also be discontinuity point of conclude that there are at most O(B1 + B2) discontinuity points for g, for any 2.
We are now ready to give formal proof for Lemma 2.1
Theorem 2.1 (restated). Consider real-valued function class U1 = {un - R of which each dual function ut, (ox) is piecewise continuous, with most B, discontinuities and B3 local maxima. Then Pdim(U) O(log(B, B2)).
22

---

Proof. From assumption, for each problem instance æ, the dual utility function u (a) is piecewise continuous with at most B, discontinuities and B, local maxima. Combining with Lemma D.2 " (a) has (logg B3 + B2)) oscillations. From Theorem D.1 we have the conclusion.
Compared to Lemma 2.1 the proof of Lemma 2.2 is more straightforward as it can directly derived from the definition of oscillation (Definition
Lemma 2.2 (restated). Consider real-valued function class U = {ua X - R E R]. of which each dual function u (a) is piecewise constant with at most discontinuities. Then Pdim(L)) = (log B).
Proof. Consider a dual function (a(a) which is a piecewise constant function with at most B discontinuities. [[ug())2+ (a)2=} is piecewise continuous with at most B discontinuities for any threshold 2 E IR. Assume, for the sake of contradiction, that there exists = E IR such that [(ug(a)zs) has N discontinuities, for some N
+ 1. Since " (ax) is piecewise constant, any discontinuities of qus (o]]=) is also discontinuity of u (a), meaning that ug (a) has at least N discontinuities, which leads to contradiction. Therefore, we conclude that u (a) has most B oscillations, and thus Pdim H) = (log B) by Theorem D.I
Remark 3. In many applications, the partition of fa(a, w) into connected components is rypically defined by M boundary functions ba,, (a, polynomials in d 1 variables with a bounded degree A. For such cases, we can establish an upper bound on the number of connected components created by these boundary functions, represented
N. (ax, w). These boundary functions are often
as TRd+1 UM {(a,, w) Da w) = 0}. using only A and d. This bound (see Theorem F.9 in
Appendix F1.2 serves as a crucial step applying Theorem 3.2
Notice that Lemma D.2 does not apply in the case where the function h may have constant pieces, as they correspond infinitely many local maxima. To handle this more generally, we introduce the following definition.
Definition 5 ( (B-n (B-ooootonicity). A function h R - TR is said to be B-monotonic if its domain can be partitioned into most B intervals such that on each interval: either (a) h is strictly monotonic and continuous, or (b) h is constant function.
While a bounded number of discontinuity points and local maxima implies B-monotonicity, the converse may not be true. We now show how to bound the number of oscillations of B-monotonic functions.
Lemma D.3. Any B-monotonic functioonii h R + IR has O(B) oscillations.
Proof. Suppose I be an interval over which h is piecewise constant. Then the function 9s : H ] also constant over / for any R (either constant zero or constant one throughout depending on z). On the other hand, if f is strictly monotonic and continuous over 1, then is piecewise constant over with at most two pieces. Thus, I= has most 2B discontinuities for any 2, or h has O(B) oscillations by Definition
We conclude with the following corollary (immediate from Lemma D33 and Theorem D.1 for the special case of piecewise constant functions. Compared to Lemma 2.1 the proof of Lemma 2.2 is more straightforward as it can be directly derived from the definition of oscillation (Definition 4p.
Lemma 2.2 (restated). Consider real-valued function class U {ua : X + E a R}. of which each dual function ung (a:) is piecewise constant with at most B discontinuities. Then Pdim(l4) = Olog B).
Proof. Consider a dual function uz(o) which is piecewise constant function with at most B discontinuities. [(ug(a)2e) is piecewise continuous with at most B discontinuities for any threshold E R. Assume, for the sake of contradiction, that there exists e IR such that [(g(())==) has N discontinuities, for some N > B ++1 1. Since (ax) is piecewise constant, any discontinuities of [ug (a)2=} is also a discontinuity of ug (a), meaning that ui (ax) has at least discontinuities, which leads to contradiction. Therefore, we conclude that u (a) has most oscillations, and thus Pdim H.) Olog B) by Theorem D.I
D
23

---

E An illustration for the proof in Section
3
a
R
R
05
0g
R4
R5
0g
02g
R3
R2
(fmin
W
W
min
Figure 3: A demonstration of the proof idea for Theorem 3.1, We begin by partitioning the domain A of the dual utility function ue (a) into intervals. This partitioning is formed using two key points for each connected component R in the partition Pa of the domain A x W of fa, w): Oftiinf inf, {a Eec, (a, w) E R} and &RRsuu sup, {a : Eur, (a, w) E R}. Given that P contains N elements, the number of such points is O(N). We demonstrate that the dual utility functions u remain constant over each interval defined by these points.
Additional results and omitted proofs for Section 4
In this section, we will present the required background and supporting results for Lemma
F1 General auxiliary results
We first present some useful auxiliary lemmas.
F.1.1
Results for analyzing local maxima of pointwise maximum function
In this section, recall some elementary results which crucial in analysis. The following lemma says that the pointwise maximum of continuous functions is also a continuous function.
Lemma F.1. Let fi X + R, where == 1,...,, .N, be continuous functions over subset C IR"" and let f(x)= = max.e(1...... fi(x)) Then we have (x) is a continuous function over X.
Proof. In the case N = 2, we can rewrite f(x)
f1(x) + f2(2)
f(x)
+ 2 fi(()) fa(x)),
2
which is the sum of continuous functions. Hence, f(x) is continuous. Assume the claim holds for N k. we then claim that also holds for N
by rewriting f(x) as
f(x) max max (E(L.....k)
(f(())),
Therefore, the claim is established by induction.
The following results are helpful when we want to bound the number of local maxima of pointwise maximum of differentiable functions. In particular, we show that the local maxima of g(x)
max;e(1....nf (x(x) is the local extrema of one of the functions (.) This property helps us controlling the number of local maxima of (()) by controlling the number of local maxima each function gi (æ))
Proposition F2. Let X be finite-dimensional Euclidean space and gs X + R, where i 1...., N, be continuous functions on X with the local maxima on is given by the set Ct. Then the function g(x) max.e(1.....) (x) has its local maxima contained in the union Use(1....N) Cz.

---

Proof. Let æ' be local maxima of g(z).. It means there exists a neighborhood Ne of x' such that for any Na', we have g(x') ) 2 g(x). Let gi be function s.t. gi(=') g(x"), Then
9: ge( g(x')( 2 2 g Je(I....N)
g)(x) 2 g)
for any Nas. This means that æ' is the local maxima of gi, i.e, x' E C UJE(L....NN) 1
We recall the Lagrangian multipliers theorem, which allows us to give a necessary condition for the extrema of function over a constraint.
Theorem F.3 (Lagrangian multipliers, (75). Let l I + R. R R be Ca funccions, and lei Z {a Ra f(x) = -0 C R. Assume that for all By E Zg
rank(J (x)o))) - n. If is
local extrema of h y, then there exists X (A15...,,.)) An) R" such that:
Vh(a') = _ E (VVi((a)) and f(x')=00
where À is called Lagrangian multipliers.
We next recall the following well-known results that characterize the local extrema of continuously differentiable functions over compact set.
Lemma F.4 (Fermat's s interior extremum theorem). Let f: + IR be continuously differentiable function, where D S 1h is open set, and suppose that x' is local extrema of in D. Then f((x) = =0 O.
Corollary F.5. Let f D - TR. be a differentiable function, where D C R is a compact set. If x' D is a local extrema of f in D, then zu is either: (1) an interior point of D and V ff(x') O, or (2) point the boundary (d( of D.
Lemma F.6 (Extreme value theorem). Let f - R be a continuous function, where D R is compact set, then f is bounded in D and there exists æ 22 E D such that f(x1) = sup f(x) and (xx2 in (xx).
We also recall the well-known Sauer-Shelah Lemma.
Lemma F.7 (76).. Let < le S n, where and n are positive integers. Then
k
n
En
k
j-0
F.1.2 Results for bounding the number of connected components defined by algebraic sets
In this section, we formally define connected components and extreme points.
Definition (Connected components). A connected component of a set C RR is a maximal nonempty subset A C S such that any two points of A are connected by continuous curve lying in A.
Definition (Extreme points of a connected component). Let component of S. We call A.int inf E TR By E Iimm (x, E A}, and AA = -up(a E TR. Ey Rem (x. y) E A} the x-extreme points of A.
Th and let be a connected
The following theorems allow us upper-bound the number of connected components defined by algebraic sets and the complement of algebraic sets.
Lemma F.8 (177). Let p be polynomial in variables. If the degree of polynomial p is A, the number of connected components of {z E 12 p(z) =0 0} is at most "
Theorem F9 (177). Suppose N 2 n. Consider N polynomials Pı. p. in n variables, each of
degree most A. Then the number connected components of R U 1 E RD [p((2) =
NA 7
For connected component C of R - -U ? ppp, we can define its adjacent boundaries, which the algebraic set Zp, that is adjacent to C.
25

---

Definition 8 (Adjacent boundaries). Consider N polynomials Pi.....PPN in n variables, and let Zp. {= E R" [z(z) = be the algebraic set defined by ps. Let C be any connected component of - - p. We say that Zp, is an adjacent boundary to C if Zp, # 0. Here C' is the closure of C.
The following result a direct consequence of Bezout's s theorem
Corollary F.10. Let f1:...:Jy :I......." IR - R be n polynomials in variables of degree di..... dre respectively. Assuming that n;=1 5. has only isolated points, then the number of isolated solutions of is at most [I==1 d4.
We also have the Bezout's theorem specialized for the two-dimensional case.
Corollary F.11 (Bezout's theorem on a plane, (79). Les fi, f2 IR2 R are two polynomials with
no common factor (of degree more than 1). Let z nZ = (x,,)) E R2? [i((z = f2(2, 00. Then the number of points in Z,, C f2 is most deg(ff) dfg(f2).
F.2 Background on differential geometry
In this section, we will introduce some basic terminology of differential geometry, as well key results that we use in our proofs. First, we recall the definition of topological manifold.
Definition (Topological manifold, 80) ). subset M C IR" is a topological manifold of dimension k S if:
For any P. M, there exists an open neighborhood U S R. of p and homeomorphism 6: S:UMM- VV, where V C RR* is open.
M is equipped with the subspace topology inherited from R" (i.e., subset S C M is open in M if there an open set S' in R" such that S S' M), Hausdorff (any two points in M have two corresponding disjoint neighborhoods), and second-countable (M has countable basis).
Using the subspace topology, can define the open set and neighborhood in topological manifold as follows.
Definition 10 (Open set). Let M C R2 be a topological manifold. A subset S C. M called open in M if there exists open set S' in RR" such that S = M S". Definition 11 (Neighborhood). Let M C Rn be a topological manifold, and let p is a point M. Then neighborhood of p in M is open subset S of M that contains p.
We will now define charts, atlases, and smooth (differentiable) manifolds. Roughly speaking, given manifold M, one can think of chart (U, σ), where U is neighborhood of some point in M, as a way to assign (Euclidean) coordinates to local region in M. An atlas then describes the local coordinate systems that cover all M, and the transition map describes how we convert coordinates between overlapping charts.
Definition 12 (Charts, atlas, and transition map. 80 A chart M C R" is pair (U, Ø), where U C. M is open, and o U + R* is homeomorphism. An atlas is a collection of charts {(Ua, da)} covering M, i.e., C Un For overlapping charts (Ua, da) and (Ug, Φg), the map de o o- @a Ug) + @s nUg) called the transition mapping between open subsets of R
Definition 13 (Smooth manifold, (0)) A subset M C Rn is smooth manifold of dimension k S if it has an atlas where all transitions maps are smooth (C*)).
We now define the smooth map between smooth manifolds.
Definition 14 (Smooth map between smooth manifolds, (80). Let M C. R. and N C R. be smooth manifolds in Rn and Rm, respectively. A map f M + N is called smooth if: for every p E M, there exists charts (U.0) containing p and (V, v) containing (') such that the coordinate representation vi o o 6U ( f-)(()()))))) - (V) is smooth in the standard sense (i.e., infinitely differentiable).
In case that M and N are Fuclidean spaces, the definition of smooth map just has the standard sense.
26

---

Definition 15 (Smooth map between Euclidean spaces), f : R + Rm is smooth map if it is infinitely differentiable, i.e., if every partial derivative of f exists and is continuous.
We now define the tangent space and the regular value of smooth map. Intuitively, the tangent space (AM) of a smooth manifold M at point p represents all the directions that we can move along from p and still stay in the manifold M.
Definition 16 (Tangent space, [0). Let Y (-c,e) + M be a smooth curve in M with ((0) = p. The langent vector = (0) represents direction "along M at The langent space T pp(M) is the set of all such vectors v obtained from smooth curves though p. i.e.,
(M( (0) T:: (-c,))
+ M smooth, 700) pp.
Definition 17 (Regular value, (80). Let M C R be smooth k-dimensional submanifold, and let f M + Imm be a smooth map. point e E IRe called a regular value of f if for every P E f (e), the Jucobian evaluated at p of an ambient map f Rt + Re of f extended to the ambienl space IR",, when restricted (p(M), has rank m.
rank Jz(P)) Tp(M))
dim (1Jz(0)) (=E0)
In case M is open subset in 12th (including I= itself), simplify the definition of regular value as follow.
Corollary F.12. Let M is an open set in RR" and let M I. be smooth map. Then is regular value of f for any p E (c), the Jacobian matrix (p) has rank m.
The following result shows the smooth manifold structure of the preimage of regular values. Lemma F.13 (Preimage theorem, [80). Let f M + Rt is a smooth map, where M C IR" is a k-dimensional smooth manifold Th" and l 2 m. Let E E TRm be a regular value of f. Then f (e) defines a (I- m))ddimensional smooth sub-manifold in M.
In the case M IR",, we can further simplify the lemma above as follows.
Corollary F.14. Lei f Rn - IRm is a smooth map, and let E R be a regular value of f. Then f (e) defines (Ic - m) -imensional smooth manifold in R.
The following theorem says that for any smooth map f. the set of non-regular values of f has Lebesgue measure zero.
Theorem F.15 (Sard's theorem, (0)). Let M C R" be a smooth manifold R", and let f M RT be a smooth map. Then the of non-regular value of f has Lebesgue measure zero in R.. Moreover, dim(M) f (M) has measure zero.
then f (E) has dimension dim(M) m, and if dim(M) < m, then
F33 Monotonic curve and its properties
In this section, we propose the definition of monotomic curve and establish some important properties, which will play a key role in our main results.
Definition 18 (Polynomial map and zero set). Let
IR x
R
Rm
(x,y)
+
be a smooth map. for any I.... m f( y) is a polynomial of and y. then we call the polynomial map, and 2 {(. y) E x R" f(z, y) = 0} the zero set of the polynomial map f.
Specifically, if set Zy inherits favorable structure. We note that f being a polynomial map allows us to use Warren's 's theorems (Theorem F99 Lemma F.8) derive the upper-bound for the number of connected components for Zg and R x F. Zy. regardless of whether O is a regular value of f.
and 0 R" is a regular value of the polynomial map, then the zero-
Corollary F.16. Let f
Rm - mm be a polynomial map. Assume that E T a regular value of f. then Zy defines a smooth I-dimensional manifold in R. x mm
27

---

Proof. This result follows directly from Corollary F.14
We are now ready define monotonic eurves.
Definition 19 (x-Monotonic curve). Let f X Tm be a polynomial map, and assume that E Th is a regular value of f. Let C C Z be an connected open set in Zz. The curve C is said to be x-monotonic for any point (a, E C, we have det(J f (a, b)) + 0, where J b) is Jacobian of f with respect to evaluated at (a, b), defined as
(, b) =
(a, b)
key property of an z-monotonic curve Cs that for any zo. there exists at most one y such that (zo, y) E C. We will formalize this claim in Lemma F.19 but first, we will review some fundamental results necessary for the proof.
Theorem F.17 (Implicit function theorem,
81
Let f
f R x R
R
(x. + (f1 y).... ....: fm( y)),
be a continuously differentiable function. Consider point (a, b) E IR" R such that f(a, b) and the Jacobian
Taf Oy,
Jf =
(a. b)
invertible, then there exists neighborhood U of a. in Rp" and neighborhood V of in R such that there exists a unique function g U V such that g(a) b and f(x, g(x)) = 0 for all
U. We can also say that for (x. y) U V, we have y g(x). Moreover, g continuously differentiable and, if we denote
Off Oxx
(,,(a,
(a, b)
then
0g: 0xy
(x:)
= (J g(xx))()))))) ( ((=)))
Theorem F.18 (Vector-valued mean value theorem). Let S S RRn be an open subset on R and
let f S + R. a continuously differentiable function. Consider x. y E such that the line segment connecting these two points is contained in S, i.e. L(x, y) C S, where L(x, y) (læ + (1 f)y 1 E [0, 1]]. Then for every a E RT, there exists a point z E L(x, y) such that (a, f(y) (x)) = (a. (z)(()() x)))
are now ready to present a formal statement and proof for the key property of æ-monotonic curves, which essentially says that for monotonic curve C any zo, there is most one y such that (zo, 8) E C.
Lemma F.19, Let f R Rm Tm be a polynomial map, and assume that 0 E Rm regular value of f. Let ff be monotonic curve in Zy. Then for any zo E R, there is at most one point y Tn such that (ro, y) C.
Proof. (of Lemma F.19) Since 0 E R is regular value of f. then Zy defines smooth 1- dimensional manifold IR x IR.. Therefore, is connected open subset of an I-dimensional smooth manifold Vj means that C' is diffeomorphic to (0, 1). This means there exists continuously differentiable function h, where
h (0, 1) C
t (x,y) = (o()t),
EC,
with corresponding inverse function h- -
C + (0, 1) which is also continuously differentiable.
We will prove the statement by contradiction. Assume that there exists (N0, v1). (æo, 92) C where y1 * y22- Then have two corresponding values h 11((2o, v1) * h
- (zo. y2). Using
28

---

Mean-value Theorem (Theorem F.18) for the function h, for any E Rm+ there exists &a E (0, such that
(a, (0, Ay)) (a, A(Jn,)(=a)),
where Ay 1/2 11 # A l2 # 0, and Jn,e(za) (hha
at (za),
Bh (za)s.... Bhm (za)) of
Choose a 01 = (1,0,....) E R R", then from above, there exists Fas (0, 1) such
that
Bho at
0. Now, consider the point (Far Va.) h(zar). From the assumption,
o 0. Therefore, from Implicit Function Theorem (Theorem F.17 there exists neighborhoods U of Ia, in IR, V of ya, in R" such that there exists a continuously differentiable function g U + R", such that for any (a, 3) U x V. we have y g(z). Again, at the point (Tai Ya,)) corresponding to t Eay we have
Fai det(J (Var Vo,
Oy:
3g:
0.
Øt
Fx
Øt
Zag
8at This means that at the point& ( = Za. we have
By 00
0.
==
Note that since h is a diffeomorphism, we have 1 = -hh- h)). From chain rule, we have
1 = Jn-1, A -h, However, if we let Zai, then Jn, 0, meaning that Jn-1, (n,a(a))) leading to a contradiction.
From Definition 20 and Proposition F:19 for each a-monotonic curve C, can define their x-end points, which are the maximum and minimum of r-coordinate that point in C' can have.
Definition 20 (I-end points monotonic curve). Let C' be a monotonic curve as defined in Desinition 19 Then we call sup(z x By, (z, y) V} and inf By, (x, v) E V} the x-end points of
We now show that the pointwise maximum of continuous functions along monotonic curves is also continuous. We then relate the local maxima of the pointwise maximum with the local maxima of continuous functions along the monotonic curves in Proposition F.21
Proposition F.20. Let M C Rn be a topological manifold, and let S be an open subset in M. Let be a point in S, and assume that V is neighborhood of x in S. Then V also a neighborhood of p in M.
Proof. First, note that since V is neighborhood p in S, V an open set the subspace topology S, meaning that there exists an open set T in M such that V = S n T. However, note that both S and T are open sets in M, which implies V also an open in M. And since V contains p. we have that V is a neighborhood of in M.
Proposition F.21. Let C = (C1...., Ck) be a set of k a-monotonic curves as defined in Definition
19 that have I1 32 as I-end points. Consider smooth function g R. x Rm IR and let h: (2), + IR defined as
h())
max g(lc,()))
il.....k
the point Ic, (x) (x, E C. Then h(x) is continuous over (z1, T2), and for any local maximum x' of h(x)), there exist point (x') that is local maximum of the function g(z, y) restricted to some monotonic curve C C.C. Moreover, if is strictly monotonically decreasing (resp. strictly monotonically increasing, constant) at x' (01, then h(x') g(Ic, (x')) for some such that g Ic. is strictly monotonically decreasing (resp. strictly monotonically increasing, constant).
where Ic. (x1,
X T maps
Proof. From the property of monotonic curves, it is easy show that Ic. is diffeomorphism between (3) 22) and C, Therefore, Ic, : (2) + R is a continuous function. This implies that h is the pointwise maximum of continuous functions, and hence also continuous.
Now consider any monotonic curve E C. Assume x' a local maximum of g o Ic (x1 22). By definition, there exists an open neighborhood V of x' in (æ1, such that for any V.
29

---

glIc(x")) 2 (lI(())). Since Ic is a diffeomorphism between (21, and C. this implies (V) also an open set in V that contains (a(a"). Now for any (z, (V) where yz is the unique value corresponding to z: in C, we have g(z, Uz) s((((a)) S ((T(((')) = g(r,, ya') This means (a', yyx) is a local maximum of g in C.
Finally, it suffices to give proof for the case of k = 2. Let h(x) = ( We claim that any local maximum of h would be local maximum of either g o Lc, or g a Ic, in (#1, (2) Assume that x' is a local maximum of / in (II, 22), then there exists an open neighbor V of x' in (a1, 0r2) such that for any z E V. h(x) I h(z'). WLOG, assume that h(x') = gl (z')).
Then we have:
(()c,(x)) = h(x') 2 h(x) = max (x)) ((cc, 2 ((L,,
for any x E V. This means that x' is a local maximum of g o Jc, in (21, Combining with the above, we also have (a's ]) is the local maximum of g in C1.
Similarly, suppose that is strictly monotonically decreasing at x'. Then for a sufficiently small left-neighoorhood L = (x' E, x'), , we must have that h is strictly monotonically decreasing over L and h(x) = g(Tc, (x)) for all x E L for some fixed i. Moreover, go must be strictly monotonically decreasing over sufficiently small R (a', x'' e'), g(Tc, (z)) I h(z) over R and h is strictly monotonically decreasing for sufficiently small R.
Proposition F.22. Let C {CI,..., Ck} be set of k x-monotonic curves (Definition
19 that
have I1, B2 as x-end points. Consider a smooth fontthfffttii function g R x RRT + R. Define gi
R as
ge(x)) -Ic. (z)). where Ic, x2) - R x R maps to the point Ic, (x) (I. y, C..
Let h: (Z1, + IR be given as
M(x) max gi(x).
i=......
Then if each gi B.-monotonic (Definition) 5). then 0 B.)aaBB.moootttti D.--moootonic.
Proof. Let A; denote the finite set (of smallest size) of critical points for gis such that between any two consecutive points in A; 9i is either strictly monotonic or a constant. By Definition 5 and the assumption that 9s is B,-monotonic, we have that AA, = O(B,). Let A U,A, Clearly,
|A| < E, |4,1 O B:). Consider any two consecutive points @1, 02 in A. We claim that h is 3- 3-monotonic over (21,a2).
To establish this claim, we consider two cases for any point a E (a),
Case: h(aa = gi(a) and gi is strictly monotonically decreasing at We claim that for any a' E (d1,a), h(aa)) is strictly monotonically decreasing. not, then hiaa) = gj (a(" for some function gy that is either constant or monotonically increasing at a' (since there are no critical points for gj in (a1, a2)). But this contradicts h(a) = (a(a) as g((a) < g:(a') & gy(a)) S g) S h(a). (ii) Case: h(a) (a) and gi is strictly monotonically increasing at a. By inverting the argument for Case (i) above, for any a' E (a, 02), h(a') is strictly monotonically increasing.
Let a4 sup(a E (a1, h is strictly monotonically decreasing at a} and al inf E (01, 022) h is strictly monotonically increasing at a}. By cases (i) and (ii) above, and using Proposi- tion F.21 we have a1 < d; S a²z 0g. Thus, h is 3-monotonic over (a1, az) it must be strictly decreasing over (d1,d(), constant over aa) and strictly increasing over (ah, a2). Therefore, is 3| -monotoni or equivalently O monotoncii over the entire domain.
E4 Simpler illustrative case: hyperparameter tuning with single parameter
We provide some intuition for our novel proof techniques by first considering a simpler setting. We first consider the case where there is single parameter and only one piece function. That is, we assume that d = 1, N = 1, and M = O. Since there is only one piece in this case, we abuse the notations and use interchangeably =n and fa for u and fa respectively. This means foe is now a polynomial function of a, w of degree at most Ap, instead of admitting a piecewise polynomial structure.
We first present a structural result for the dual function class 41", which establishes that any function " in the dual utility function class 2t* is piecewise continuous with O(A3) pieces. Furthermore,
30

---

we show that there are ( oscillations in un which implies bound on the pseudo dimension of 2t* using results in Section 2.1
Our proof approach is summarized as follows. We note that the supremum over to E W in the definition of 2ee can only be achieved domain boundary at a point (a, w) that satisfies = fala..) w) = 0, which defines an algebraic curve. We partition this algebraic curve into dug
monotonic arcs [82] 883, which intersect a agg at most once for any ag. Intuitively, a point of discontinuity of = can only occur when the set of monotonic arcs corresponding to fixed value of a changes as is varied, which corresponds a-extreme points of the monotonic arcs. We use a direct consequence of Bezout's theorem (Corollary (.1O) to upper bound these extreme points of (a, w) 0 to obtain an upper bound on the number of pieces of u Next, seek to upper bound the number of local extrema of u2 to bound its oscillating behavior within the continuous pieces. To this end, we need to examine the behavior of uz along the algebraic curve (a, w) 0 and use the Lagrange's 's multiplier theorem (Theorem F.3 to express the locations of the extrema as intersections of algebraic varieties (in a, u and the Lagrange multiplier A). Another application of Bezout's 's theorem (Corollary F.10) gives us the desired upper bound on the number of local extrema of ug.
Lemma E22. 1 = N 1, M, = O. That is, there is single parameter, single piece function, and no boundary functions. Assume that A = [Ominn Omax)] and W = [[Umin; Wmax)- Then
(a) The hyperparameter domain A can be partitioned into O intervals such that ut, is continuous function over any interval in the partition.
(b) 2 is ((4))) -monotonic (Definition) 5
Shr From assumption, f= w²) is a polynomial of a and w, therefore differentiable everywhere in the compact domain [Omin; (Omin;Ommxx) x [Wainn Wmax) Consider any Oop E [Omin: Omaax) we have {(a, w) = ara) n ([Ominn 0max x [Wmin Wmax]] is an intersection of hyperplane and a compact set, hence it is also compact. Thus Fermat's interior extremum theorem (Lemma F.4p applies and, for any ag. fa (ao, w) attains the local maxima either in Wming Wmax, or for w E (Wmin: Wmax) such that (a0, w) = O. Note that from assumption, fa (ox, w) is a polynomial of degree at most Ap in and w. This implies kin (a, w) is a polynomial of degree at most 4,- -1.
Proof. (a) Denote (a, w)) aaa(a.w)
Denote C2 = V(k)) the zero set of he in ;= A W. If Che has any components consisting of axis-parallel straight lines a = 01, we include the corresponding discontinuities (later) via the intersections of C., with the boundary lines w Wmin, Wmaxx Therefore, assume that C. does not have such components. For any agz C. intersects the line a = 0g in at most Ap Bezout's 's theorem (Corollary F.ITp. This implies that, for any a, there are at most 4p + 1 candidate values of w which can possibly maximize fz(a, w), which can be either Wmin, Wmax: or on some point in C.. We can decompose C. into monotonic ares using well-known techniques from algebraic We then define the candidate are set C A + (M,) as the function that maps og A to the set of all maximal a-monotonic ares of Cz (Definition 19 informally ares that
points by
geometry 82 [3
intersect any line a = ag at most once) that intersect with a = ag. By the argument above, we have
[C(a)] < A, + 1 for any a.
We now have the following claims: (1) C is a piecewise constant function, and (2) any point of discontinuity of "n must be a point of discontinuity of C. For (1), we will show that C is piecewise constant, with the piece boundaries contained in the set of a-extreme point: of C₂. and the intersection points of C. with boundary lines w Wmins Wmax. Indeed, for any interval I = (a,, 022) C A. if there is no a-extreme point of CN in the interval, then the set of arcs C(a:) is fixed over I by Definition 19 Next, we will prove (2) via an equivalent statement: assume that C is continuous over an interval I A, we want to prove that ug is also continuous over I. Note that if C is continuous over I, then (a) involves maximum over a fixed set of monooooii arcs of Ca. and the straight lines w = Wmins w = Wmax- Since fo is continuous along these ares, so is the maximum u (Lemma F.I)
of
The above claim implies that the number of discontinuity points of C upper-bounds the number of discontinuity points of u (a). Using a well-known result for algebraic curves (e.g. 84 the number
An a-extreme point of an algebraic curve C' is a point p (a, W) such that there is an open neighborhood N around for which has the smallest or largest a-coordinate among all points p' N on the curve.
31

---

of a-extreme points is (44)). Moreover, there are O(Ap) intersection points between C2 and the boundary lines w Wmin and w Wmax. Thus, the total discontinuities of C are ( giving an upper bound on the number of discontinuity points of u..
(b) Consider any interval I C A over which the function C is continuous. In particular, this means that there is no a-extreme point corresponding to any a E By Proposition F.2 and Proposition F.22. it suffices to bound the B-monotonicity of fa along the algebraic curve Cz (i.e. along fixed set of monotonic arcs of a+) and the straight lines w = Wmin and w = Wmax-
To bound the number of elements of the set of local maxima of fa along the algebraic curve Car, consider the Lagrangian
L(a, w, X) (a, + Aliz (a, w).
From the Lagrange's ' multiplier theorem, any local maxima of fæ along the algebraic curve C is also a critical point of L, which satisfies the following equations
ac 8fæ + X Ōkg
0f
02 fæ fadw
0,
da da
da
da
OC
of.
+ X Ōk
ff
02 fa
Ow
=
Ow
Ow
dw
X
Ow
= 0,
OC = Kin
Sl 0.
0X
Ow
Plugging a = O into the second equation above, we get that either X = 0 or 0² 0. In the tw:
former case, the first equation implies 8ʃ. O. Thus, we consider two cases for critical points of L. Let's suppose (ā, u) is a local maximum of f.r along Cz. There must exist À such that (ā, w A) satisfies the Lagrangian equations above.
Case X = 0. (f((ā,)) = 0, (
Ba = 0. For this to be true, ā, v must be at the intersection the algehraic curves @f=(a,") 0, 0fa(a,w) O. By Bezout's theorem the plane (Corollary F11 Cw
Ere
da
these algebraic curves intersect in at most A points, unless the polynomials Oala.w) (f.
have a common factor. In this case, we can write @f=(a.w) g(a, w)gn (ax, w) and (fa(a.w) do
8w
dw
da
g(a, w ())2(a, w) where g = gcd [1/=, 0f=) de and 91. 92 have no common factors. Now for any point (ā, ú)) on the curve g(a, w) = 0. we have both 0fa(ā.0) 0, (ā=(ā, da
Therefore, for any two points (a1, w1) and (a2, W2) on the curve g(a, w) 0, (a wi) fa (a2, w2). Thus, fz is constant along g(a, w) 0. Recall that we are computing the local maxima on an interval I, corresponding to fixed set of monotonic arcs of Kn (and therefore also g. which is a factor of kz). By Bezout's theorem (Corollary F.11I, 91 (a, w) = 0, (2 w) = 0 intersect in at most deg(9) ddg((g)) I A3 points (since they do not have any common factors), which are the only other candidate points for which (ā, w; 0) satisfies the Lagrangian. Thus, the number of local maxima of - that correspond to this case (i.e. across all monotonic ares not corresponding to g) is (
du
8 fa(a,)) O. This essentially corresponds to the a-extreme points Case À * O. (ā. 0, Ow
Ow
computed above (see e.g. (85) and do not occur over any interval / considered here.
Similarly, the equations (a, Wmin) Putting together, by Theorem F.22 we conclude that ot is ( -monotnin..
and (æ )max) 0 also have most Ap solutions each.
Theorem F.24. Pdim(U()) = Olog Ap).
Proof. From Theorem F:23 and Theorem D.3 we conclude that u has most O oscillations for any u E UT Therefore, using Theorem D.I we conclude that Pdim(l(*) Ollog Ap).
Remark 4. Challenges of generalizing the one-dimensional parameter and single region setting above to high-dimensional parameters and multiple regions. Recall that in the simple setting above, assume that fa (a, w) is a polynomial in the whole domain R == [Omiin Omaxl x [wains Wmax]] In this case, our approach is to characterize the manifold on which the optimal solution of max fa w) lies,
varies. We then use algebraic geometry tools to upper bound the number of discontinuity points and local extrema of uig (a) maXw:(a,))e fa (a, w), leading
32

---

to bound on the pseudo- dindd-nimensonn of the utility function class U by using our proposed tools in Section 2.1 However, to generalize this idea to high-dimensional parameters and multiple regions much more challenging due to the following issues: (1) handling the analysis of multiple pieces while accounting for polynomial boundary functionns tricky as the u² maximizing [a( un) can switch between pieces a is varied, (2) characterizing the optimal solution max ())R E Jæ (ax, w) is not trivial and typically requires additional assumptions to ensure that a general position property is achieved, and care needs to be taken to make that the assumptions
not too strong, (3) generalizing the monotonic curve notion to high-dimensions not trivial and requires a much more complicated analysis invoking tools from differential geometry. and (4) controlling the number of discontinuities and local maxima of u over the nigh-dimensions monotonic curves requires more sophisticated techniques.
F.5
Omitted proofs for Theorem 4.1
In this section, we will present a detailed proof for Theorem 4.1
a
Reil
hy.ca
a1+1
C
G Co
0;
3f.1
w
Figure 4: simplified illustration for the proof idea of Theorem 4.1 where w R. Here, our goal to analyze the number of discontinuities and local maxima of u (a). The idea is to partition the hyperparameter space A into intervals such that over each interval, the function u2 (a) is the pointwise maximum of fæ.i(a, w) along some fixed set of "monotonic curves" C (curves that intersect = Oo at most once for any ax)). (a) is continuous over such interval; this implies that the interval endpoints contain all discontinuities u "n (a). this example, over the interval (a;, as+1), we have (a) = maxc, {f w) : (a, w) E C.}. Then, we can show that over such an interval, any local maximum of (aa) is local extremum of fa, w) along monotonic curve C' E C. Finally, we bound the number of points used for partitioning and local extrema using tools from algebraic and differential geometry.
Theorem 4.1 (restated). Consider the utility function class = {u, X X a E A}.
Assume that the parometer-depender dual function (a, w) admits piecewise polynomial structure with the piece functions fa.; and boundaries hz satisfying Assumption ! Then for any distribution D over X, for any 10, with probability at least 1 5 over the draw of S Dm,, we have
log N + dllo(AM) + log(1/8)
Bu (a=) Ee (ta- (x:) =0
m
Here, M and N are the number of boundaries and connected sets, A = max(6 8d7 is the maximum degree of piece functions fa,i and boundaries hz
Proof. In this section, we will first go through the general idea of the proof for Theorem and its main steps. The proof consists of three main steps. Step 1: we first bound the number of possible discontinuities and local extrema of v (a) under Assumption 3 which is a stronger assumption compared to Assumption 1. Step 2: we show that, for any " (a) that satisfies Assumption [ we can construct v (a) satisfies Assumption and is arbitrarily close to u (a). Step 3: we can use this property to recover the learning guarantee for U. The key ideas of each step sketched below.
33

---

First step: the proof requiring stronger assumption
To begin with, first start by stating the following stronger assumption compared Assumption
Assumption 3 (Regularity assumption). Assume that for any dual utility function u (a), its piece functions fa w) (for i 1,...,N) .N and boundary functions h (a, w) (for 1..... M) satisfy the following property. For any piece function f chosen from ffa.1...... N and S boundary functions .i....,hs chosen from (hm,,,,.... N.., My J. the following conditions are met:
1. Consider the polynomial map h, where
h :RR+1
+ +RS
h(a, w)
+ (hi(a, ....... h......,,s(.,, hasa, w)).
Then O E R& is regular value of h. Furthermore, if S S d, we have Jn (w) has full row rank for (o, w) E (0). 2. Consider the polynomial map k, where
k: Rd+
Rd+s
(a, w. X) 4 (kila, w. kasss,,, w, w))).
Here, S and k(a, w, A) (kila, w, A).... katss,a w, A)) is defined as
ki,aa w. A) h)(a,,
1, . S
ka w, A) :w, Laa A). i = 1...,d,
where L(a, w, = w) w) + h(a, w). Then there exists a set of real values consisting of most A 254 elements such that the Jucobian J k,W, X) has full rank for all (ax, w. A) To (0) such that E. 3. Consider the polynomial map
# RR:22+2843
+R2d 2d4225+1
pla, w. 7,
+ (1, w, 7, X, .....55.. w. Y, 0)).
Here, S Sdd 0 ERS,
RRd, and each μs is defined as follows:
Psla, w. Y, y, x,
hy(a,,); 1
(s w; 7, X, 0)
= y Vwl (a, w) 1,...,
P2s+i(a, w. X, 0)
= Om, la w, A) l....d
P2s+d4i w, 7, 0)
.w, [L 0) + y V w, A)], =1, I.....d
|22++2411 (o, w, 7,
-. [T w, 0) 7 vwll(a; w. A)]-
Then the Jacobian (a, w, 7, X, E E, where E is defined in (2).
7, 0) has full row rank for all (a, w. 7, X, 0) (0) such that
have the following result, which gives the pseudo peeudo-dimension upper-bount bound for the utility function class Ut
Under Assumption
Theorem F.25, Assume that Assumption 3 3holds, then for any problem instance i E X, the dual utility function (0:) satisfies the following:
(a) The hyperparameete domain A can be partitioned into
most O (NAAd (=M) + (N((A))d++) (1a)) (2a))d) intervals such that (z((a) is continu- ous function over any interval in the partition, where N and M are the upper-bound for the number of pieces and boundary functions respectively, and A = max Ab) is the maximum degree of piece and boundary function polynomials.
(b) Over those intervals, 2 (a) has O (NNA4+4 AVA40+ (=)))") local maxima for any problem in- stance
34

---

Proof. (a) First, note that we can rewrite uz (a) as
" (a)
max fa,(a, 10(a, Re..
Since Ri, is a connected component A x W, let
in aa Ew (a, w) Ræ,s) isi sup(a Ew (a, w) E RE be the a-extreme points of R (Definition 7b. Then, for any (im, Oggisup), there exists w such that (a, w) Rg,5.
Let Ha be the set adjacent boundaries of Rz (Definition 8). From assumption of problem setting, there at most M boundary functions hanjj. meaning that |Ha.i I M. For any subset =
C Hx.i where |S] = S, consider the algebraic set Zs. where
Es = -5 ((a, w) E R Id his w) = -0..
If S > d - from Assumption 1, Zs is empty Consider S S d 1, from Assumption 3. Jn (a, w) defines a smooth (d + 5)-dimensional manifold in x Rd. Note that, this is exactly the set of (a, w) defined by the equation
(a, =,
where the left hand side is polynomial in a, of degree at most 2A. Therefore, from Lemma F88 the number of connected components of Zs is at most 2(2))++1 Each connected component a-extreme points, meaning that there are most (22) a-extreme points for all the connected components of Zs. Taking all possible subset S of H.,; with at most d + elements, we have total of at most N o-extreme points, where
corresponds
N s (2A) d+1
Σ
d+1
M (5))
(5)=
S (24)a+1
d+1
eM
4+1
(d+1
Here, the final inequality is from Sauer-Shelah Lemma (Lemmal E.7
Let Aı be the of such o-extreme points. Then for any interval I, (a,, 0++1) formed by two consecutive points in Aj, the set S exists. Here, the set S E 2 contains all subsets S of H such that for any S = /hs.1....,,ss... } E S! and any a E (at, 04+1), there exists uo such that ha, w) = 0 for any j 1, S.
Now, for any fixed the compactness of Rz,;), meaning that (a, wa) is also local extrema in Ra This implies there exists set of boundaries S S) and À such that (ar, w.) satisfies the following due to Lagrange multipliers theorem (Theorem
It, assume that w. is local maxima of fa,
i in Ra, (which exists due to
h(a, wa) Wa, w., A) = 0.
Here h = ........., h.sss) is the polynomial map formed by the boundary functions in S, and
Ma, un A) = (a, u)) + X h( w)
the corresponding Lagrangian. Let MMs be the set points (a, w, A) that satisfy the equations above, which defines algebraic set. From Lemma F.8 the number of connected components of Ms is at most 2(2A)d+5+3 corresponding to most 4(2 ((2 d+ a-extreme points. Moreover, let = (h. V Vw elements such that the Jacobian ( A) has full rank for all (a,, w, X) E k (0) and a g Es.
L). Then from Assumption 3 2, there exists a set of real-valued Es at most +2d
Taking all possible subsets S c S) of at most d elements and noting that |S] < M, we have at most 2d+1 ( (ddd
O (2
+ 4d ( (cM))
such points (that are either a-extreme points in the set of
values Es).
35

---

Let Ag be the (sorted) set that contains all points in A and the points described above. Then for any interval 1 ( 11) formed by two consecutive points in A2, there exists a set S 2 that contains all subsets S = (hs,1:-..,hh, ..s....s...... of H such that for any a E (0t, ac+1). there exist aa and Aa such that (a, wa, Aa) satisfies
wa)
wa) =0
Vul(a, Was >a) =0
and Jz( A) ((,,,. (o.wa. where Te (h, Lw has full row rank. Therefore, over any interval 7,. the set of points (a,, w. A) that that k(a,, w, A) = 0 defines a one-dimensional manifold in the space R x R X R of a, w, A, and furthermore, its connected components are monotonic
curves (Definition 19
Note that for the points (a, wn, Aa). (a, wa) might be in the feasible region R For each set of boundaries S E S7, for each point (a, w) at which Ms can enter or exit the feasible region Rz there exists À such that (a, w, A) satisfies the equations
h(a, w) = 0
V La, w, A) = 0,
h'(a: w) 0, for some h' Hz.i S,
of which the number of solutions finite due to Assumption 3 In the above constraints, the first two equations say that the point (a, w. X) lies in the smooth one-dimensional manifold Ms. and the last equation ensures that (a, w, A) the intersection of MM with the boundaries Zn = {(a, w, A) ha, w) 0}. For each set S E Sj and possible boundary h' E Ha S, the number of such points is at most 2(2A) d+S++ This means that there are at most (2
such points for each S, since a,,, \S S M. Taking all possible sets S and noting that S has at most elements, we have at most (M (MM) () such points (ax, w. A), corresponding to
at most O (M(2))24+ (² values.
Let Ag be the set that contains all the points in A₂ and the points above. Then for any interval 1: = (at, at+1), the set S is fixed. Here, the set S E 2 consists the set of all subsets S = (hs.......k hsss) of Hz. such that for any fixed a E (at, 0141) i), there exist w., and X such that (a,, wa Aa) satisfy
h h(a =,, S,
La, Wa. wa.)a)= =
(.) E Ren, Juw, 2)
has full row rank.
Again, the condition (u,, >) ())(a..))= (,. has full row rank implies that l((,,, w. A) defines a smooth one-dimensional manifold that consists of monotonic curves.
of points As of most O (A 4d (= M(2))2241 (cM)
In summary, there elements such that for any interval I (ax, a(+1) of consecutive points (ar, a(41) in A4, there exists a set C2 of monotonic curves such that for any a E (at, a1+1), we have
Uzz (a) = max [m,,i(x, w) YEE (a, w, X) E C). CEC.
In other words, the value of = for a E T is the pointwise maximum of value of functions fa, along the set of monotonic curves C. From Proposition F.21 we have u (a) is continu- ous over It- Therefore, we conclude that the number of discontinuities of u (a) is at most
O A (eM) ((A)aad+) (eM) d
()))))
Finally, recall that
" (a))
max Uz,((a),
ie iE(I...,N)
and combining with Lemma F.1 we conclude that the number of discontinuity points of u (a) is at
most O (NA dd (eM) MN 2d+1 (cM)
36

---

(b) We now proceed to bound the number of local maxima of 2.( To do that, we proceed with the following steps.
Recalling useful properties from (a). Recall that we can rewrite u (a) as follows
" (c)
max ie ()...N)
u (a))
where
" (a)
max w:(a,w))RRa
fa, w))
In part (a), we show that: there exist 0n d) N 4d (=)) + MN (=)) such that for any interval Le = (ax, 0x41), there exists
where
T
of monotonic curves such that
- (a) CEC,
max w) (a, W) E
Note that, from the property of monotonic curves (Lemma F.19). for each monotonic curve C and each a, there exists at most one (w, A) such that (ae, w, X] E C, hence the definition above is well-defined.
Now, for each interval I, and monotonic curve C C,, there is connected component Rg with the piece function fa. and set of boundaries S (hs, hsss) C H such that C' is on the smooth one-manifold Ms in IR++S+1 defined by
h(a,, w) = 0, V L(, w, w,>) -,
where L(a, w, A) = fa.i(a, w) + X h(a,
AT(a, w) Note that for each a E (at, 0++1) and for each monotonic curve C, there is unique w. such that (a, w. A) E C, and therefore 4 is just pointwise maximum of fm.j along the curves C' C.. From Proposition F22 to bound the number of local maxima of u suffices to bound the number of local extrema of n,, (ax, w) along each monotonic curves.
Analyze the number of local maxima of fa,; along monotonic curves. First, note that the number of local maxima of fa,i along monotonic curve C' is upper-bounded by the number of local extrema along Moreover, any local extrema of fa,s along is a local extrema of fa.i on the smooth 1 1-manifold Mg, i.e., satisfying the following constraints:
{ h(a, w) = 0, V La, w. A) 0,
To see this, WLOG, assume that (a', w', X') a local maximum of fa,; along C. By definition, there exists a neighborhood of (a', w', X') E C such that for any (a, w, A) V, we have f w') > (a, w). Note that by definition (Definition 20). C' is an open set in Ms. Combining with Proposition F.20 we know that V is also an open neighbor of (a', w', X') in Ms. Therefore, (a', w', X') is also local maxima of fa.i along Ms.
Therefore, it suffices to give an eoper-bound for the number of local extrema of fa, restricted to Ms. Consider the Lagrangian function
af w)
oh
(a, w)
L(a, w, ), = (a, w) +
10, (a, w) +
Σg 7
+ Σ
A
m. i.j
Ow
Ow
j=1
j=1
= L(a, w. 0) > V VV w, w, A).
37

---

From Theorem F33 for any local extrema (a, w. X) of fa, w) in Ms. there exists 0 E RR R2d such that
h(a, w) = 0,
V Wwl(a, w, 0,
7 (a w) O,
[T u. 0) + 7 Vw T(a, w, X)] = 0,
0, [a,, w, 0) + + - VV w, X)] - 0.
From Assumption 3/3 and Bezout's theorem. the number of points (a, 7, A, 0) that satisfy the equations above is at most A 22542d-1, Hence, we conclude that there at most 25-224+1 local extrema of fæ, along any monotonic curve C' MMs such that (a, w) E Rg.
Analyzing the number of local extrema of u In the previous step, for any set of boundaries C. Hz. and |S| = S < d 1, we show that between all 4. there are at most A 25++2d+1 local extrema for f along any monotonic curve of Ms. We now take the sum over any C H |8] = S S d and any region R2 for I, then conclude that the number local extrema of u (a) across all intervals I is O(N), where
d Σ
N N
25+22+1
S
S=0
M Σ
d+1
NA 4d+-2
(because S $
5=0
eM
NA 4d+2
(Lemma E.7
d
Combining Theorem F25 and Lemma 2.1 we have the following result.
A}, where A [[mminn 0mmax] C R. Assume that any dual utility function uh admits piecewise polynomial structure that satisfies Assumption 3 Then we have Pdim(L)) Olog N dlog( (AM).. Here, M and N are the number of boundaries and functions. and A is the maximum degree of boundaries and piece functions.
Theorem F.26. Let u {ua
[0,
Second step: Relaxing Assumption Assumption 1
In this section, we show how we can relax Assumption 3 to our main Assumption | In particular, we show that for any dual utility function u that satisfies Assumption I we construct function or such that: (1) The piecewise structure of ex satisfies Assumption B) and (2) || 2 lo can be arbisrarily small. This means that, for utility function class 21 we construct
function class
of which each dual function of satisfies Assumption B We then can establish aseudo-dimensine upper-bound for V using Theorem F25 and then recover the learning guarantee for 'f using Lemma C.4
We will now proceed via sequence of claims towards establishing the reduction. First, we claim that under Assumption [
we have the following regularity condition.
Proposition F.27. Under Assumption 7 the Jacobian J,(w, Y) of the mapping μ (11,.... (2s) for S S where
(my(a, w, y) = hy(a, w), for L,.,,, ( w. = TV Wi w), for I,...,S,
has full row rank when evaluated (a, w. 7) such that p(a, w, 7) 0.
Proof. Note that the Jacobian Ju(u 7) has the form
JJw
Jın
Ju(
J2w J2y
38

---

Essentially, in order to show (w, 7) is full row rank, we will use that J1w and Joy are both full row rank, which follows from Assumption
In more detail, here = (la,..... ,,s))))))))))))).. and
JIw Ju(wwssds Jin Osxds
7 Th (w)
J2w
J2y = (ns)
Y Hns (w)) 8xd
where Hh, (w) is the Hessian of hy w.r.t. Now, in order to prove that (,, y) has full row rank, suppose that there are real coefficients ,1,..., such that
Σ ر
where J, is the 5th row of (n(w,)) 7). Restricting on the columns corresponding to we have
25
Σ
Jy)n(w)) = 0.
$=$+1
From Assumption 11. have J. has full row rank for any (a, w) that satisfies h(a, w) 0. means 6, 0 for j = .,... 28. Combining with Ej= JزJة 3 = 0, we have
8
JJJJ =
Again, using the fact that (w) has full rank, also claim that 6, 0 for 1,...,... Therefore, 6y for j = 1,..., 2S, meaning that Jul (w, 7) has full row rank.
We now present the notion of algebraic dimension from the literature.
Definition 21 (Stratification, real algebraic dimension, 86). Let be semi-algebraic set in TR. Then S can be decomposed to finite disjoint union of smooth, connected manifolds S,, called strata, ie.,
S =
where St a smooth manifold. The algebraic dimension of S the maximum dimension of the smooth manifolds in the stratification of S, i.e., Adim(S) max"_ dim(S.).
We establish the following straightforward connection between the regular values function defined on semi-algebraic set and the algebraic dimension of its domain.
Proposition F.28. Let f 5+ RR be a polynomial map, where S is a semi-algebraic set. Then the set of non-regular values of f has Lebesgue measure 0 in R" Assume that Adim(S) = then given a regular value of f, (v) only contains isolated points in S.
Proof. Consider stratification S S For any strata S,, consider the restricted mapping fls. S₁ > IR From Sard's theorem, the set C2 C Rd of non-regular values of fls, has Lebesgue measure in R., Therefore, the set of non-regular value C U C2 which a finite union of sets with Lebesgue measure 0, also has Lebesgue measure 0 in R
Now, given regular value v E F". and consider the restriction fls, S + R" for any strata S, If S; is a smooth k-dimensional manifold for k < n. then f-) must be empty. To see that, consider the differential map dfz T.S, - R2 (since T2) R R"), which
be a surjective (since dim (S;) < n). Therefore, f (v) has to be an empty so that the surjective condition holds vacuously. If S, is a smooth n-dimensional manifold, then f f-1 f-((w) is smooth O-dimensional manifold in S,, which means that it contains only isolated points.
Finally, the following supporting result uses Bezout's theorem bound the number of non-singular points corresponding the set E in Assumption 3
39

---

Proposition F.29. Consider a piece function fas and set of S boundary functions S = (hi....,hs) Let L(a, w, X) = (a, w) + X h(a, w), where h (hi,..., hs), and con- sider the mapping μ (1........+..
My(a, w, A) hy(a, w), for I, uss=(aa, w, A) Ow, L(a, A), for ..
Under Assumption we can choose T E R such that the set E of parameters a for which the system
(h(a,w) = 0, (wL((a, w, 2) =
has solution (w, X) where the Jucobian (w, 2) is singular, is finite. Moreover
1. Given such T, the set E\r has at most 2884 elements. Here, A is the maximum degree of the piece functions fa, and boundary functions ht-
2. The set of Tis of which does not satisfy the above, has Lebesgue measure 0 in Rd.
Proof. Let Zp. {(a, w. X) E RS+d+1 h(a; w. A) 0), which is an algebraic set. From Assumption 1 since Jn, A) has full rank for any (a, w, A) Zn, Zn, has algebraic dimension (++++1) = d (or more concretely, Zn defines smooth (d + 1)-dimensional manifold in Rd+5+1).
Next, consider Zdee(J, (s) = {(a, w, A) R+d++1 Ju(w. (w. A) is a polynomial, therefore det(J (w. A)) is also polynomial, and Zdet(J,, A)) is an algebraic set. Let W Zp n Z the set W has (algebraic) dimension at most d.
det(J,(w, A)) = 0}. Since each entry of
which is also algebraic set. From Assumption T 2
Now, consider the mapping P: W - Rd where P(a, w, X) v.. A), which maps point (a, w, A) in the algebraic set W to point in Rd From Proposition F.28 the set of non-regular values of has Lebesgue measure 0 in Rd. Let T E IRd be regular value of P. From Proposition P P-1(7) only contains isolated points in W. Now, note that W Zp O (awe())((w,))) and del Jn (wn, A)) is polynomial of degree at most S+d, From Bezout's theorem (Corollary F.10).
F228
we have P [P-((T]
A 2S42d
Therefore, any other solution (a, w, A) that satisfies h(a, w) 0 and L( w. A) T has to have det(Juaa, w, A)) + 0, or [a, w, A) is non-singular, which concludes the proof.
We now present the main claim in this section, which says that for any function u (a) that satisfies Assumption [ we can construct a function o (ax) that satisfies Assumption and that ||u o blo. can be arbitrarily small.
Lemma F.30. Let u be a dual utility function of utility function class U. Assume that the piecewise polynomial structure of u satisfies Assumption 7 then construct the function or such that v has piecewise polynomial structures that satisfies Assumption 3 and u 10lloo can be arbitrarily small.
Proof. Proof overview. First, notice that Assumption immediately implies Assumption 3 Therefore, given a dual utility function u of which the piecewise polynomial structure satishes Assumption [ the task now is to construct "i such that oz has piecewise polynomial structure that satisfies A Assumptions 2 33.
Given a set of boundary functions S = (l,,.... ..s) and a piece functions fa, that satisfies Assumption | we will show that there is a set Ts, C IRd that has Lebesgue measure 0 in Rd such that for any E Rdd - Ts... if we subtract - u from the piece function Jn,i(a, w), i.e., (a, w) = [a, w) - un, then the collection of boundaries functions S (11,-.. hg) as well as the new piece function (a, w) satisfy Assumption 3 2.
Then, given set of boundary S (li,...,hy hs). ). new piece function fa and the set Ts we further show that there exists set ATs:: C. R that has Lebesgue measure in IR such that for
40

---

any a R Ars.. if we consider another new piece function fa w)
f w) on
(perturbing the original piece function fa.i by - - aa), then the set of boundaries functions S = ( his and the new piece function (a, w) satisfies Assumption 2 and 3
Finally, for any piece and any set of boundary functions S, if we choose (a, T E (IR ATS.) x
R Ts,s, we will have the new piecewise structure that satisfies Assumption Furthermore, since
(R ATs.) x R - Ts. has full measure in x R we can choose (a, T) arbitrarily small.
Technical details.
We first calculate the Jacobian matrix Ju. For convenience, let L(a, w, w, 0) fa w) Σラ= fyhs,,(a, w) = fa.i + 00 h. Here, h(a, w) = (hs,i w)...., ( w)) is the mapping of considered boundaries.
We first calculate the Jacobian matrix (a w, A. 0).
For convenience, we decompose
Ju (a, w, 7, X, 0) into block matrices
Jia J1w
Jim
J1A
J10
Jza
J2w
J2n
J2x
J20
(a w, 7.
J3a
J3w
J3n
JaX
J30
Jsn
Jaw
Jan
JAX
J40
Jsa Jsw
Jsn
JaX
Jso
where the rows J2, J3. J4. Js corresponds to (JI,... us), (JS+1,
(2s), (125th...., (2stdd)
(p M2s+2d), (#24+25+1) respectively. For the first column (corresponding to a), we have
T1
Σd 1=
n amn h1
82 aaw,, L(a, w, A) Jan
Jia
J2n
0ahs]
Σ 1== No
orw hs
02 a,uy
L(a, w, A)
8x1
dx1
0 awi
(L(a, w. 0) + + V w,,
Jaa
Jsa = 10 (L(a, w, 0) V L(a, w, A))
Paw, (L(a, w, 0) + + T La, w, A)) dx1
For the second column (corresponding to w), we have H (w)
JIw = (n(w) Sxd Jzw
Jaw = H ()(),w.))(1)) axd
T Hns (w)
Sxd
JAw H (. Lo (2W)) axa Jsw V Walaa w, 0) + T VuL(a, w, A))
Here, Jn. Jn(w) is the Jacobian of h w.r.t. w, and Ha(w) is the Hessian of h w.r.t. For the third column (corresponding y), we have
J17 = Osxd, J2n Jn(w) Jon Oaxds
JAy = () Joy = V (0, La, w, A))ixd
For the fourth column (corresponding to A), we have
JIA Osx J2x Osxs. Jax Jn(w)
J4x H (w)..... Hng (w) (w))las J&A 10,7 V ... Oay V Vuhisliss
For the fifth column (corresponding 0), we have
J1e 05x s, J20
0sxs, J3e Oaxs, J/e Jn (n(w) J5e
41

---

First, consider the mapping (a, w, A) = (h(a, w), L w, A)), where h = (h1,..... hg) is a polynomial mapping formed by the set of considered boundaries, and L(a, w, X) = (a, w) h(a, w) the corresponding Lagrangian. From Proposition F.29 there exists the set Ts C R of Lebesgue measure 0 such that for any T E R - Ts there is a set values S, size at most 25+22 such that any solution (a, w, X) that satisfies the system
h(a w) = O, V VwlLa, w) A a(a, w)] -
will have Jun (w, A) non-singular, except for solutions that have a E S, Therefore, choosing (a, w) = fmi(a, w) - w. and note that Jns (w, 2) =\t
for μí = (h, VuL(a, w, A) -)) we have constructed new piece function fa, such that Ja, and hi...., ......,,, hg that satisfy Assumption
Now, we will show that for any chosen above, we will have the Jacobian Jus(w, 7, X, 0)
(16),(a, w. Y,
hy(a, w), 1, I,...,
(16)s+5(a; w. 7, 7, 0) w. (1h)2s+sl,,,,711 (16)2stdti(a,, W,
Y Vuilijj = 5.....,
= -w, ['(a, w, A), 1...,d
0m, [T, Q) + - TV Tw w. A)), = 1.....d
where L'(a, w, A) = (a, w) + A AThaa, w) is non-singular when evaluated at any solution (a, w; X, 0) of n'(a, w, X, 0) = 0 such that a & E.s. First, recall that the form of Jus (w, 7, X, 0)
(w)
(7) Osxd Jn((w) (w) Oaxd
(A)
(0)
Jn sxd
Osxs
0sxs
Jug (w,7, 1, 0) =
J2w
Osxs
0sx
H Hí x>) () axd
Jn.(w) (w)))x
0ax5
JAw
H L)) (w)axd
J4X
Jn. (ww) dx
The important point is that: (a, w, y, X, 0) that satisfies p (a, w. y, A, 0) = 0 and a E Es,i, also satisfies p1 (a,, w, x)= 0 and
Jn(w)
Osxs
Ju (w, A) HL(a, dxd
Jn (1(w)xx)
has full row rank. We will leverage this observation to show that Jug (w, y, A, 0) also has full row rank. Now, let .,...., 825+24 be real coefficients such that
2S+2d
Σ
82 J. =0
t=1
where Jr the th row of the Jacobian Jus (w. 7; X, 0). First, consider the column corresponding to y and 0 of ung. have
25
28+2d
Σ 1=S-1
6, (-((Jn(w)),,
+
Σ
5, (1) (Jn(w) = 0.
tm 2S24++1
Notice that the above is exactly the rows of Jug (w, A), which has full row rank. Therefore 8, for f = -...... 28, 2S + d 1,..., 25 + 2d. Consider this fact and the column corresponding w. X of Jug. we have
2S+d Σ
Σ 6e ((Jn(w)),,
d, ((HL(,..xx)\W))) (J)
0.
25+1
Again, due Juy (w, A) having full rank, we have & for L = =, 2S + 1,..., 25 + d. In summary, we have & 0 fort
1,...,25 28 + 2d, which implies Jug having full row rank.
42

---

Now, we will show that there exists set ATs, C R with Lebesgue measure 0 such that for any a E IR- ATs.: we have that the Jacobian J (a, w, 7, X, 0) with nM given by
(a, w; 7, 7,,,,,>. 0)
hy(a, w) [
Msttla (a, w. Y,
VV Vung.j = ,, 1...,
M2s+s w. 7;
Dwc, (a, w. w,))
Mos+e45 (a, w, W. Y, 0)
= =iw,lL" w, 0) + 7 VV w, A) l....,d = (a( w, 0) + 7 V T. (a, w. A)];
22242241 (a,, w. 7. 0)
has full row rank when evaluated at the solution (a, w. Y. X, 0) of μ (a, pa, W, ), 0) and & Es,t. Here, L"(a, w, X) I² (a w) + À h(a, w). and (a, w) = f w) aak (e.g., perturbing (a, w) T w aa to have (a, w)). The important point in this step is that: any solution (a, W; X, 0) of 1 1a(a, w, 7, X, O) = 0 also satisfies μ2 w, A, 0) O, and J Pii (w, y, X, 0) is exactly J/1 (w, 7, X, O). Therefore, consider any interval = (ar, Q++1) where 04,, ac+1 are two consecutive points in Es,s, we have Ju 24 (a, w, Y, X, 0) has full row rank, since Jul (w, Y, 0) has full row rank. Now, M1:25+24 0 defines smooth manifold M. Consider the mapping P: M where P 1 p22++24+1- From Sard's theorem F.15 there exists the set Arg C I with Lebesgue measure such that any E R - ATs... is regular value of P. Let ATs., = AtATs...s which has Lebesgue measure in R, we have for any
ATs
we have Jn w, 7, X, 0) has full row rank when evaluated at the solution (a, w, 7, X, 0) of p² (a, w. Y, X, 0) 0 and & E. This is exactly Assumption 3
Now, to choose (a, r) that works for any fa.i and any set of boundary functions S (hi,.... hssh we simply choose (a, 7) E = ni Ts..) x (Rd ATs,))), which full measure set in R x Idd since it is a finite intersection of full measure sets.
Finally, we will construct the v that: (1) has the piecewise structure that satisfies Assumption and (2) ||ue loo can arbitrarily small. The construction is as follows:
The set of boundary functions the same as uZ : (Mee......,hua M.. any connected components Rays the piece functions fa, w) is perturbed by an amount aa w. i.e.
fa w) < fa,ila w) aa TTw,
where, (a, T) chosen random from B. 0 Here, B. {(a, T) max (a, T1, , ra} < is the 6- ball in T x A. We note that B, n B is non-empty, since B has full measure in T 4, meaning that we can always choose (a, w), no matter how small e is.
By constructing vn as above, we have:
The structure of on satisfies Assumption ! and
In any region Ra,i we have
Sa,i(a, w) S2 (crw)) = =|ac |ac + T S cC,
where C' = max (naxi(/mmin: [Omaae
[Wmin| [Wmax J.
This implies
max Sa,(0, w) - -26C max w:(a,w)EET TRa..
[a w) 5 max wo)a
Sa,(0, w) + 26C,
(a) (a) (a) 2cC ||
2eC S
1l 2cC.
Thus |/ug - uo
- S 2cC' and since can be arbitrarily small, we have the desired conclusion.
43

---

Final step: recovering the guarantee under Assumption 1
We complete the formal proof for Theorem 4.1 Let Uh X
[0, H
A} be
function class which each dual utility us satisfies Assumption | From Lemma F.30 there exists function class V {Na X' [0, H] E A) such that for any problem instance a, have ||u. t ooo can be arbitrarily small, and any the satisfies Assumption
3 From Theorem F.25 we
have Pdim (V) (loo N + d logg)M))) From Lemma
C.4
we have Am (V) = O Pdiml
(v (vios N M+dlo((AM) where S E x Finally, a standard
From Lemma C.3 we have (L o
result from learning theory gives the final claim.
G Additional details for Section 4.1
In this section, we provide the formal proof for Theorem
4.2
Theorem 4.2 (restated). Consider the utility function class U = fwo X 10
E [okmin Omax J- Assume that the parameter-depender dual function fa w) admits piecewise polynomial structure with piece functions fa.s (for i 1,....,. .N and M boundaries functions A} be the induced function class by E-a-ERM oracle of U. Then for any distribution over X, for any 5 E (0,1), with probability least 1 over the draw of S {æI...... Fm Dm, have
hasj (for j 1....,M M) satisfying Assumption 7 Let V = {va X [0, H]
1E Coo.D(uGeerreee (x)] BEw u (2:) = (v Voog +d dlog(AM) log(1/8) + +E) +6)
m
Here, âg E arg EA 1 E Va (z;), a maxaeA En-p (laa()]())), and A max Ap. Aa} is the maximum degree of piece functions fæ,; and boundaries he.j-
mi
Proof. Given the assumption, from the final step of the proof of Theorem 4.1 (Paragraph F.5 we
have ( (V log N+dlog(AM)
where E Xm, Moreover, from the Ç-a-ERM oracle
assumption, given un (a) corresponding problem instance æ and hyperparameter a, we have access to i (a) such that (a) u [a) <. Therefore, from Lemma C.3 we have
(Vigg N + +dlog(AM) +
ks(V) < (() +5=
Finally, a standard result from learning theory (Theorem
gives us the final claim.
H
Additional details for Section 5
H.1
Tuning the interpolation parameter for activation functions
H.1.1
Omitted proofs for parametric regression setting
Theorem 5.1 (restated), Let CAF denote loss function class defined above, with activation functions 01, Og huving maximum degree Å and maximum breakpoints p. Given a problem instance x = (X,Y), the dual loss function is defined
E (a) == minwew f(x, o., w) minnww (a, w) Then, fa (a. w) admits piecewise polynomial structure with bounded pieces and boundaries. Further, if the piecewise structure of fa w) satisfies Assumption ] then for any N (0, 1). w.p. at least 1 8 over the draw of problem instances & ~ D where D is some distribution over X, we have
(V
L log A LW log(Tpkk) log(1/8)
[B=DDlarau - Ea-D((o- =
m
Proof. Let T1, .1...., Tr denote the fixed examples from the fixed dataset (X, Y). We will show bound N on partition of the combined parameter-hyperparame space W x R, such that within
44

---

each piece the function f(x,r) (a, w) is given by a fixed bounded-degre polynomial function in a, w on the given fixed dataset (X,, Y) where the boundaries of the partition are induced by at most M distinct polynomial threshold functions. This structure allows us to use our result Theorem 4.1 to establish a learning guarantee for the function class LAF.
The proof proceeds by an induction on the number of network layers L. For single layer L the neural network prediction at node j E [k1] is given by
Pij a01 (w,zz) + (1 a))2(
for i E [T]. W R can be partitioned by 27k affine boundary functions of the form w 1x- where tx is a breakpoint of 01 or o2. such that Øij is a fixed polynomial of degree at most A + in a, in any piece of the partition P1 induced by the boundary functions. By Warren's 's theorem,
4eTk:p((+1) W1
have [P S
W1
Now suppose that the neural network function computed at any node in layer S T. for some 2 1 is given by a piecewise polynomial function of a, w with at most [P, [T ( (eTTkpp(A+)) Wg W.
pieces, and most 2Tp Eq=1 ky polynomial boundary functions with degree at most (A + 1)" Let E [1p++] be a node layer r + 1. The node prediction is given by Diy = 001 (w (1-a)oy(wy'' where ÿt denotes the incoming prediction to node j' for input I,. By inductive hypothesis, there are at most 2T 1PP polynomials of degree at most (Á + 1)" + such that in cach piece of the refinement of P, induced by these polynomial boundaries, Diy is fixed polynomial with degree at most (A + 1)r+1 By Warren's 's theorem, the number of pieces in this refinement is at most [P,+1
4eTTk, p(Akk)(A+1) Wq
g==
W.
1 lgg = 2mpk polynomial Thus (a, w) is piecewise polynomial with at most 2Tp E
boundary functions with degree most (A + 1)25, and number of pieces at most |PL] S Assume that the piecewise polynomial structure of f(x,)) w) satis- fies Assumption I then applying Theorem 4.T and a standard learning theory result gives us the final claim.
1 1eThop((+1))) W.
H.1.2 Binary classification setting
In this section, we consider an alternative setting of tuning the interpolation parameter for activation functions in the classification setting. In the binary classification setting, the output of the final layer corresponds to the prediction g(a, w, x) = ÿ E K, where w E W C w is the vector of parameters (network weights), and a is the architecture hyperparameter. The 0-1 loss single example x = (X,Y) is given by ()(()) and on a set of T examples as
min 1 Σ T(o(a,w.)) = min f(x, w, a...
t. (ι)
wEW T (x,))(XX))
wEW
For fixed dataset x = (X, Y), the dual class loss function is given by LAF = (ES X + [0,1] A).
Theorem H.1. Let CA denote loss function class defined above, with activation functions 01, O2 having maximum degree A and maximum breakpoints p. Given problem instance x (X,Y), the dual loss function defined as t (a)a) := min f(x, a, w) = min (a, w). Then, fa,a, w) admits piecewise constant structure. For any 5 (0, 1), w.p. at least - over the draw of problem instances S ~ DmD, where D is some distribution over X, we have
E - ((X, = (0 LAW log A + LW log Tpk log(1/8)
-
Proof. As the proof of Theorem 5.1 the loss function L. can be shown to be piecewise constant as (eTRkp(A+1))) pieces. We can apply Theorem We
function of o w. with at most |Pr| < TT (
3.2 to obtain the desired learning guarantee for CAP.
45

---

H.2
Data-driven hyperparameter funing for graph polynomial kernels
H.2.1
Classification setting
In this section, we demonstrate the applicability of our proposed results in a simple scenario: tuning the hyperparameter of graph kernel. Here, we consider the classification case and defer the regression case to the Appendix.
Partially labeled graph instance. Consider a graph 9 = &), where V and & are sets of vertices and edges, respectively. Let n [V] be the number of vertices. Each vertex in the graph is associated with d-dimensional feature vector, and let X [xxd d denote the matrix that contains all the vertices (as feature vectors) in the graph. We also have a set of indices V/ C [7]] of labeled vertices, where each vertex belongs to one of C. categories and L [3/2 is the number of labeled vertices. Let
y E [F] be the vector representing the true labels of labeled vertices, where the coordinate yi of corresponds to the label of vertex 1 E V'z.
We want to build a model for classifying the remaining (unlabeled) vertices, which correspond to A popular and effective approach for this is to train graph convolutional network (GCN) [22]. Along with the vertex matrix X, we are also given the distance matrix 6 [ encoding the correlation between vertices in the graph. The adjacency matrix A is given by a polynomial kernel of degree A and hyperparameter a > 0, i.c., A = (6(i.)) + -=)= Let Å A + In. where In is the identity matrix. Also, let Đ = [Di where Dr, 0 if i + j. and Di. ビド= Ai.j for i E [n]. We then denote a problem instance (X, y, ).)2 and call X' the set of all problem instances.
O'r = [n] Vr., where [n]
Network architecture. We consider a simple two-layer GCN f [22]. which takes the adjacency matrix A and vertex matrix X as inputs and outputs Z =(X, A) of the form
Z = (eLU((XX:"))))
where Á = D- A is the now-normalized adjacency matrix, W d is the weight matrix of the first layer, and W()) E Rddoxf is the hidden-to-outpe weight matrix. Here, is the jth-row of Z representing the score prediction of the model. The prediction ÿ; for vertex i E Yo is then computed from Z as max 2, which is the maximum coordinate of vector 24.
Objective function and the loss function class. We consider the 0-1 loss function corresponding
to hyperparameter a and network parameters w (w) w()) for given problem instance æ, fa (a, w)= = D.. Eiery [(n The dual loss function corresponding to hyperparameter a for instance x given as (2r) = min fa (a, w)) and the corresponding loss function class is CGCN (la X - 0., 1 E A).
To analyze the learning guarantee of LGCN we first show that any dual loss function (a) l. = minw fa (a, w), (a, w) has a piecewise constant structure, where: The pieces are bounded by rational functions of a and with bounded degree and positive denominators. We bound the number of connected components created by these functions and apply Theorem 3.2 to derive our result.
Theorem H.2. Let [GCN denote the loss function class defined above. Given a problem instance
x, the dual loss function defined as (aaa) == mil ff f(z a, w) min fa (a, w). Then fa (a, w) admits piecewise constant structure. Furthermore, for any ō E (0, 1). w.p. at least 1 1 ò over the draw of problem instances S = ...,..... ~ D where D some problem distribution over X, we have
F)logn) ( /dold F) log RignFA + log(1/8)
EE (x)] Ex Dla. =
m
To prove Theorem H.2 we first show that given any problem instance æ, the function f(x wi a) fa (a. w) is a piecewise constant function, where the boundaries are rational threshold functions of and w. We then proceed bound the number of rational functions and their maximum degrees, which can be used to give an upper-bound for the number of connected components, using Lemma F9 After giving an upper-bound for the number of connected components, we then use Theorem 3.2 to recover the learning guarantee for U.
46

---

Lemma H.3. Given problem instance a = (X, V.K, 5)) that contains the vertices representation X, the label of labeled vertices, the indices of labeled vertices Yr, and the distance matrix consider the function
(a, un) = [(x (0,000. w)
Σ LEV2
VVL
which measures the 0-1 loss corresponding to the GCN parameter w, polynomial kernel parameter a, and labeled vertices problem instance æ. Then
partition the space of w and into
(nF3) )2A + +6) 1+ddg + ((14% ddg doF
(A + (1+1)ad)
connected components, in each of which the function fa fa w) is constant function..
Proof. First, recall that GCN(X, A) ARLLU(AX((()) where À 1 is the row-normalized adjacency matrix, and the matrices À [Аt,] A In and D [Da.g] are calculated as
A = (ōi.) + aa)
n D = Oifif and D.s = A for i [n].
j=1
Here, recall that 5 [6t,] is the distance matrix. We first proceed to analyze the output Z step by step as follow:
Consider the matrix ( (W of size dg. is clear that each element of T is polynomial of ( of degree at most 1.
Consider the matrix T2) (1 of size x dg. We can see that each element of matrix Å is a rational function of a of degree at most A. Moreover, by definition, the denominator of each rational function strictly positive. Therefore, each element of matrix (2) is rational function of (())) and a of degree most A +
Consider the matrix T3)) (2LU(T(()) of size n dg- By definition, we have
T:(3)
(2
T 20 otherwise.
0,
This implies that there are n do boundary functions of the form T,22 where T:(2) i.5 a rational
function of ()() and a of degree at most A + with strictly positive denominators. From Theorem the number connected components given by those n. do boundaries are ((D 1)ndo).
R99
In each connected component, the form of (3(3) is fixed, in the sense that each element of 73) is rational function W(O) and a of degree at most A +
Consider the matrix ((1) = (1)),, In connected components defined above, it is clear that
each element of (44) is either or a rational function in (0)),, W(),, and a of degree at most A 2.
Finally, consider Z = (4( In each connected component defined above, we can see that each element Z is either or rational function W(0), W(),, and a of degree at most A 3.
In summary, we proved above that the space of w. a can be partitioned into O(AA +1)nda) connected components, over each of which the output function in W1 W(),, and a of degree most A + Now in each connected component C, each corresponding to fixed form of 2, we will analyze the behavior of fa (o, w), where
GCN(X, A) a matrix with each element is rational
(a w) =
Σ Ig. iEVo
Here 0 = arg max j1a...l..... Zij, assuming that we break tie arbitrarily but consistently. For any F > j & 2 1, consider the boundary function Iz,,Z%,, where Zi, and Zr, are rational functions in and w of degree at most A + 3, and have strictly positive denominators. This means that the
47

---

boundary function Iz,, 22. can also equivalently rewritten as 12,,00 where Zt, is a polynomial in a and w of degree at most 2A + 6. There are O such boundary functions, partitioning the connected component C' into most O (( (nF (2A-6) I+ddo+doF)) connected components. In each connected components, y is fixed for all E (I...., n meaning that (a, w) is a constant function.
In conclusion, O (nFF (2A++) ) 1+ddo+ x (A + 11 connected components, in each of which the 1+ddo function fa (a, w) is constant function.
can partition the space of and
into
O
Theorem H.2 (restated). Let LGCN denote the loss function class defined above. Given a problem in-
stance the dual loss function is defined E (a) == milwww f(x a, w)) win fw fa(a, w).
Then fa (a, w) admits piecewise constant structure. Furthermore, for any 6 E (0, 1), w.p. at least Dm, where 'D is some problem
1 - ô over the draw of problem instances x (01,.... F.mm
distribution over X, we have
F)lognl (v dolld+ + +F)FF))( log PggnFAr + log(1/6)
m
H.33 can partition the space of w and d4 ) 1+ddoo (A + 1)md)) connected components, each of which the function fa (a, w) remains constant. Combining with Theorem 3.2 we have the final claim.
Proof. Given problem instance æ, from Lemma
into O (( (mF')(+++))
H.2.2 The regression setting
The case a bit more tricky, since our piece function now is not a polynomial, but instead a rational function of a and w. Therefore, need a stronger assumption (Assumption 2) have Theorem
H.5
Graph instance and associated representations. Consider a graph G (V,E), where V and & are sets of vertices and edges, respectively. Let n n= | be the number of vertices. Each vertex in the graph associated with a feature vector of d-dimension, and let E R be the matrix that contains the feature vectors for all the vertices in the graph. We also have set of indices V/. [r] of labeled vertices, where each vertex belongs to one of categories and = D/ the number of labeled vertices. Let y E R., R) be the vector representing the true labels of labeled vertices, where the coordinate yi of Y corresponds to the label vector of vertex E VL.
Label prediction. We want to build model for classifying the other unlabeled vertices, which belongs the index set Di, [n] yr.. To do that, we train a graph convolutional network (GCN) [22 using superviee learning. Along with the vertices representation matrix X, we are also given the distance matrix [ō_,) (t.))e() encoding the correlation between vertices in the graph.
Using the distance matrix D, we then calculate the following matrices A, A, Đ which serve as the inputs for the GCN, The matrix A ((..))( is the adjacency matrix which is calculated using distance matrix d and the polynomial kernel of degree A and hyperparameter >> 0
As,j = (5(i.)) + +
We then let À - A Ins where is the identity matrix, and ò [Dislmnaa of which each element is calculated as
D.g = Off and Des
Σ Ang for E [n].
1=1
Network architecture.
We consider simple two-layer graph convolutional network (GCN) 22 which takes the adjacency matrix A and vertices representation matrix X as inputs and output f(X, A) of the form
= GCN(X, A) ARLLU((XX(O)))
48

---

where D W( E Raxdo is the weight matrix of the first layer, and W(1) E R is the hidden-to-output weight matrix. Here, 2; is the tth element of Z representing the prediction of the model for vertice i.
Objective function and the loss function class. We consider mean squared loss function corre- sponding hyperparameter and networks parameter (w((), w!!) when operating on the problem instance æ as follows
fa w) Di.
Σ (z -2)) iEVr
We then define the loss function corresponding to hyperparameter when operating on the problem instance æ as
(x) min (a, w).
We then define the loss function class for this problem follow
CoON fla X R²) a E A},
and our goal is analyze the pseudo-dimension of the function class L
Lemma H.4. Given a problem instance = (X, 5, 8,)1. that contains the graph G. its vertices representation X, the indices of labeled vertices Yt, and the distance matrix consider the function
1
fa w) a(xx,,, w)
Σ (2 (1-2 TeV1
which measures the mean squared loss corresponding to the GCN parameter w. polynomial kernel parameter a, and labeled vertices on problem instance æ. Then we can partition the space of w and into O( + 1)ndd) connected components, each of which the function f w) is rational function in a and us of degree at most 2( 3).
Proof. First, recall that Z GCN(X, A) AReLU((XT""O))T where Å 1-1/2AD-1/2 the row-normalized adjacency matrix, and the matrices [As.]] = + I, and Ó = [Dty] are calculated as
Ar = (ōi. + a)
D.g = 0 j. and D..- =
EAi for E [n].
j=1
Here, recall that 5 [8t,] the distance matrix. We first proceed to analyze the output Z step by step as follows:
Consider the matrix (()) = XW of size n x dg. It is clear that each element ( is a polynomial of (')) of degree at most 1.
Consider the matrix (22) () of size do- We can see that each element of matrix Á is rational function of a of degree at most A. Moreover, by definition, the denominator of each rational function is strictly positive. Therefore, each element of the matrix (2) is a rational function of (0))) and a of degree at most + 1.
Consider the matrix (3) Re)L((((2) of size n x dg- By definition, we have
(2)
if i 20 otherwise.
lij
This implies that there are n x do boundary functions of the form 1,,3 20 where T: is rational
function of (0) and of degree at most A + with strictly positive denominators. From Theorem F.9 the number of connected components given by those n x do boundaries are O ((D + 1)
In each connected component, the form of (3) is fixed, in the sense that each element of (3) is rational function in (())) and of degree most A + 1.
49

---

Consider the matrix (44 (() In connected components defined above, it is clear that each element of ( is either 0 or a rational function in W W(U), and a of degree at most
A 4+2 2.
Finally, consider Z = (T( In each connected component defined above, we can see that each element of Z is either 0 or rational function in W W and a of degree at most A + 3.
In summary, we proved that the space of w. a can be partitioned into O((A 1)mde) connected components, over each of which the output Z = GCN(X, A) is a matrix with each element is a rational function in W(O), W and a of degree at most A + 3. It means that in each piece, the loss function would be rational function of degree at most 2(A 3), claimed.
Theorem H.S. Consider the loss function class LCCN defined above. For problem instance a, the dual loss function Ez (ax) = win [a w) where [a w) admits piecewise polynomial structure (Lemma) H.4). If we assume the piecewise polynomial structure satisfies Assumption 3 then for any E (0, 1), w.p. at least 1 over the draw of m problem instances S D where 'D is some problem distribution over X, we have
(v
ndo log + dlog( + log (1/8)
[Bs=D[Camu (5)] ESwD =0
m
I A discussion on how to capture flatness of optima in our framework
Our definition of dual utility function w (a) max [a w) implicitly assumes an ERM oracle. As discussed in Section B this ERM oracle assumption makes the function u (a) well- defined and simplifies the analysis. However, one may argue that assuming the ERM oracle will make the behavior of tuned hyperparameters significantly different compared to when using common optimization algorithms in deep learning. The difference potentially stems from the fact that the global optimum found by an ERM oracle might have a sharp curvature, compared to the local optima found by other optimization algorithms, which tend to have flatter local curvature due to their implicit bias.
In this section, we consider the following simplified scenario where the ERM oracle also finds the near-optimum that is locally flat, and explain how our framework could potentially be useful in this case. Instead of defining ux (a) max Jn (a, w)), we define u (ax) = max I'g (a, w), where the surrogate function (a, w) is defined as follows.
Definition 22 (Surrogate function construction). Assume that fa u)) admits piecewise polynomial structure, meaning that:
1. The domain A X W of fo is divided into N connected components by M polynomi- als Ne...... ha in a, w, each of degree at most Db. The resulting partition Pe (Ra.1.... Re,N consists of connected sets Re,s, each formed by a connected component
Cas and its adjacent boundaries.
Within each Rg,5 fa takes the form of a polynomial fa,i in a and w of degree at most Ap.
Defining the function surrogate f' (a, w) as follows:
1. The domain A W of f/ (ax w) is partitioned into N connected components by M polynomials ha.1.-... N in a, w similar to fa. This results in a similar partition Pa = { (Ræ,,..... R
2. In each region Ru in St is defined as
fa w) Sa, w) fa,i(a, 77 V wn (a, w) 12
for some sixe 1 > Here, I1- denotes the Frobenius norm. We can see that || V w fa (a, w) is a polynomial of a, of degree at most 2Ap- Therefore, f'z (a, w) is also polynomial of degree at most 2Ap in the region R
From the above construction, we can see that fa (a, w) also admits piecewise polynomial structure, where the input domain partition Pa is the same as [a, w). In each region Rz, the function I' (ox, w) is also polynomial in w of degree at most 24 Therefore, our framework is still applicable this case. Moreover, the construction above naturally introduces an extra hyperparameter n, which is the magnitude of curvature regularization. This makes the analysis more challenging, but
50

---

for simplicity, we here assume that is fixed and good enough for balancing the effect of the flatness regularization.
We can see that by defining uze (a) = wax La (a, w), we can capture the generalization behavior of tuned hyperparameter (t when the solution w of max fa (a, u)) is: (1) near optimal w.r.t. waX f (a, w), and (2) locally flat.
We note that the example above is an oversimplified scenario. To truly understand the behavior of data-driven hyperparumeter luning without ERM oracle, we need a better analysis to capture the behuvior of uz (a) in such scenario. This unalysis should consider the joint interaction between the model, data, and the optimization algorithm, and remains an interesting direction for future work.
Remark 5.
J An application to Pfaffian functions
In this section, we demonstrate how to apply our results beyond polynomial settings. In particular, we will apply our results to the case where the boundary functions involve Pfaffian functions, which includes commonly appearing functions like the exponential function and the logarithm function. We refer the reader to [70] for formal background on Pfaffian functions.
We first consider the case where the boundary functions are Pfaffian functions instead of polynomials as discussed in Section 3 Concretely, given a problem instance æ E X, there are M boundary functions hg.1.... 1............................... he.N that partition the space AA x W hyperparameter a and parameters w into connected components. in each of which the dual utility function ug (a) remains constant. In this case. following Theorem 3.2, the main idea is again to bound the number of connected components in the space A x W partitioned by M Pfaffian boundary functions. We now recall a standard result that allows us to handle this case.
Lemma J.1 770 (77). Let hı,..., hM be M Pfaffian functions of degree at most A that come from a Pfaffian chain C(#1,.... Id: fi...., f4) of d variables, length 9, and Pfaffian degree D. Then the number of connected components of the complement of solution sets Rd -U, f E RR h,(()) = 0}
upper-bounded by 2od(ad-1)// 11/2
D)]da (2eM)
Combining J.I and and Theorem 3.2 we have the following result, which provides generalization guarantee for function classes for which each dual utility function admits piecewise constant structure partitioned by Pfaffian boundary functions.
Corollary J.2. Consider the utility function class U = {ua X' [0, [0, a E A}. Assuming
that for any x, there are M boundary functions he.1.-...,haa ha,M partitioning the domain A x W into
Pe = ={ (Rw,,,.... Rg,N), ). over each of which fa.i remains constant. Assuming that the boundary functions hz where i =1...., 1....,M. ,,, Pfaffian functions of degree most A from a Pfaffian chain of length g and Pfaffian degree D. Then for any distribution DD over X, and any ō E (0, 1), with probability least 8 over the draw of S {111,... 3m Dmn, we have that
D (x)] =0 (v
/ / + qd log( A D) dlog M + log( (1/5))
[EEDDD (uas (x)] EEw (ua
m
Proof. From Lemma J.1 we have N < 0 (2mttadd11/222((((A+++) (2 (2aM)))
Substituting
into Theorem 3.2 we have the conclusion.
We leave the more general scenario of Siicewise-Pfaffian setting (where the piece functions Pfaffian in addition to the boundaries) as an open question for future work and have the following conjectured bound.
Conjecture 1. Consider the utility function class 2 = x a E [amin- Omaax } Assume that the parumeler-dependem dual function [a, w) admits piecewise Pfaffian structure with N piece functions Sa,i (for 1,..., N) and M boundaries functions has (for -...., M) satisfying Assumption 3 Furthermore, assuming that the boundary functions hen. and piece functions fa, are Pfaffian functions of degree most a from Pfaffian chain of length q and Pfaffian degree
51

---

D. Then for any distribution D over X, for any 8 E (0, 1), with probability at least 8 over the draw of {II,..., Fm)] Dm,, we have
[R Warnn (x)) EEND (x=)l
0 q2 gdlog(( A + D) + log N + dlog M + T + log(1/6)
m
Here, äs E arg min L m
Ei=1 uo (2;) and a² E maxoeA Ex Uo (z))
52

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
All of the theoretical results provided this paper are justified by mathematical proofs.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We did discuss the limitations of this work in the Conclusion and Future works section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
53

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All the assumptions and proofs are included in the main body and Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is purely theoretical work.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
54

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This is purely theoretical work. We do not have any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /nips.ccc/pulli//guui
Cooe/obbeeeeeeeee wetbbbmmsssinnni ssionpolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
This is purely theoretical work. We do not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
55

---

Justification:
This is purely theoretical work. We do not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is purely theoretical work. We do not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that NeurlPS Code of Ethics http://////aaaaaa....c/pp/////aa
didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: We did review the NeurlPS code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
56

---

10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is theoretical (enhances mathematical understanding of topic under study) and has no direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper has no such risk as there is no data or implemented models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
57

---

Answer: [NA]
Justification:
This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, papprssii theode www.com//aaaaa com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
58

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMSs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We only use LLMs for grammatical error checking and formatting purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy for what should or should not be described.
59


Reviews:
[{"review_id": "TncV854gcM", "reviewer": "Reviewer_sAc2", "summary": "- Hyperparameter tuning across tasks is still dominated by heuristic search – theory lags behind practice.\n- The paper develops a learning-theoretic framework that links the number of discontinuities and local extrema of the task-wise dual utility to the pseudo-dimension of the whole class.  \n- The paper analyzes two structural cases: (i) piecewise-constant and (ii) piecewise-polynomial parameter-dependent dual functions $f_x(\\omega,w)$, yielding explicit sample-complexity bounds.  \n- Applications illustrate how the theory certifies learnability when tuning an activation-function interpolation parameter and a GNN kernel bandwidth, although only single-hyperparameter settings are treated.", "questions": "1. Can the authors supply concrete evidence that common activations or graph kernels yield piecewise-polynomial $f_x$ in practice?  \n2. How do the bounds scale when extending to two continuous hyperparameters?\n3. Compared to Bayesian optimization, do your bounds imply a smaller or larger sample requirement under comparable smoothness assumptions? A discussion would clarify practical relevance.", "limitations": "n/a", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- *Originality* - Introduces a novel bridge between algebraic/differential-geometric regularity of deep nets and classical capacity measures.\n- *Quality* - Proofs are mathematically detailed and cover both piecewise-constant and considerably harder piecewise-polynomial regimes.  \n- *Significance* - Provides the first non-trivial sample-complexity guarantees for continuous hyperparameter tuning in deep networks.\n\n**Weaknesses**\n\n- *Clarity* - Core definitions (e.g. monotonic curves, ELICQ/ND conditions) are deferred to long appendices; the main text gives few intuitive examples, making it hard to grasp practical meaning.  \n- *Significance* - Results hold for a single scalar hyperparameter and require piecewise-polynomial structure – assumptions whose prevalence in modern architectures is unverified.  \n- *Quality* - No experiments demonstrate whether the theoretical bounds are tight or how they translate to wall-clock savings vs. Bayesian optimization; even toy simulations would strengthen claims.", "was_revised": true, "final_justification": "Authors addressed my concerns satisfactorily", "rebuttal": "We thank the reviewer for their time and their recognition of the importance and lack of theoretical results for hyperparameter tuning, given that the state-of-the-art is largely dominated by heuristic search. We also appreciate that the reviewer finds our results novel, non-trivial, and significant, and acknowledges the technical challenge as well as the connection between the advanced geometrical tools and learning theoretic results that we draw upon. We address the reviewer’s concerns and questions below.\n\n## Questions\n1. __Question__: \"Core definition (e.g., monotonic curves, ELICQ/ND conditions) are deferred to appendices; the main text gives few intuitive examples, making it hard to grasp practical meaning.\"\n\n    __Answer__: It is true that we have to defer some of the core definitions (including “monotonic curves”) to the Appendix, mainly due to the page limit. However, __for ELICQ/ND conditions, we give formal definitions as well as a detailed discussion (see Page 6,  Assumption 1 and Remark 1)__, and we highlight the __key property of monotonic curves in the appropriate context within the proof sketch (lines 294-295, 308-310)__. We will elaborate further on the core notions (e.g. monotonic curves) in the main body for better readability in the final version of the paper.\n\n2. __Question__: \"Results hold for a single scalar hyperparameter and require piecewise-polynomial structure-assumptions whose prevalence in modern architectures is unverified./Can the authors supply concrete evidence that common activations or graph kernels yield piecewise-polynomial fix in practice?\"\n\n   __Answser__:\n\n      - __On the piecewise-polynomial property__: Indeed, the piecewise-polynomial structure of NN output is a __very well-known and classical fact in the machine learning literature__ (see e.g., [1,2,3] for examples) for piecewise-polynomial activation functions, including the popular ReLU activation (for ReLU the activation itself is piecewise linear, but the network output is a piecewise polynomial function of the weights and hyperparameters). This is also the foremost motivation of our analysis. Moreover, __in terms of our results (e.g., Theorem 6.1, H.1, H.2, H.3), we give concrete proofs for the piecewise polynomial structure__ for actual examples of hyperparameters in neural network activation functions and graph kernels, not just assuming that property. For example, we have shown the piecewise-polynomial structure in the following scenarios:\n        - Polynomial kernels: E.g., tuning the scaling parameter $\\gamma$ in $k_\\textup{poly}(x_1, x_2) = (\\gamma(x_1 \\cdot x_2) + c_0)^d$ \n       - Interpolating two distance metrics using a polynomial map $k_\\textup{interp}(x_1, x_2) = (\\alpha d_1(x_1, x_2) + (1 - \\alpha)d_2(x_1, x_2) + c_0)^d$.\n       - Another example includes tuning the hyperparameter in the parametric ReLU (PReLU) activation function given by $f(x​)= x , \\text{ if } x>0   \\text{ and }  f(x​) = \\alpha x, \\text{ for } x\\le 0$, where $\\alpha$ is a learnable hyperparameter.\n       - There are further examples, for which we have concrete proofs (see e.g., Theorem 6.1 (from lime 1534), Theorem H.1 (from line 1561), Theorem H.3 (from line 1606)). \n   - __On the single-scalar hyperparameter scenario__: It is true that our results hold for a single scalar hyperparameter. However, as the reviewer agrees, __this is a novel and non-trivial technical contribution that requires a novel connection between algebraic/differential geometries and learning theory__. Solving the non-trivial single hyperparameter setting achieved in this work is crucial if one ever hopes to understand the structure of the neural network behaviour as a function of multiple hyperparameters. Moreover, __our analysis also serves as a basis for potential future work on tuning multiple hyperparameters__, as __many ideas of our techniques are concrete and helpful for such extension__ (as noticed by reviewers uK76 and p5UX). Concretely, the following key components of our analysis can be extended into a high-dimensional case:\n     - For “monotonic curves”: a natural analog would be “monotonic hypersurfaces”, which should have this property: for any $\\alpha’ \\in R^N$, there is at most one point $s$ in the monotonic hypersurface $M$ in the space $\\mathcal{A} \\times \\mathcal{W}$ such that its $\\alpha$-coordinate is equal to $\\alpha’$, e.g., $s[\\alpha] = \\alpha’$. For example, the hyperplane $\\alpha_1 = w, \\alpha_2 = 2w$ is an example of monotonic hypersurface in the space $\\mathbb{R}^2 \\times \\mathbb{R}$. We expect the condition of “monotonic hypersurface” would also be $|J_{f, w}(\\alpha, w)|_{(\\alpha, w) = (a, b)} \\neq 0$ when evaluating at any point $(a, b)$ on the monotonic hypersurface $M$ (potentially with some additional conditions), and we also expect the use of the Implicit Function Theorem, similar to “monotonic curves”.\n      - For “bounded oscillations”, we also expect a high dimensional extension: given a set of problem instances $x_1, \\dots, x_N$ and real-valued thresholds $r_1, \\dots, r_N$, can we control the number of connected components of a partition in the space $\\mathcal{A}$ such that in each connected component $C$, $(sign(u^*_\\alpha(x_1) - r_1)$,...,$sign(u_\\alpha(x_N) - r_N))$ is fixed for any $\\alpha \\in C$. To do that, one might want to use some of our tools (e.g. Lemma F.9) as well as some more advanced tools from algebraic and differential geometry (e.g., algebraic projection, stratification, or surgery theory might potentially help), to first analyze the number of connected components formed by the projection of monotonic hypersurfaces on the space $\\mathcal{A} \\times \\mathcal{W}$ onto the space $\\mathcal{A}$, and then analyzing the behavior of $u_x(\\alpha)$ on each component.\n\n       Besides, some other additional extensions of our techniques and arguments have to be developed for the high-dimensional hyperparameter case, but we note that our approach offers concrete ideas and notions to attack that problem. We are happy to incorporate this discussion in the final version of the paper.\n\n3. __Question__: \"How do the bounds scale when extending to two continuous hyperparameters?\"\n    \n   __Answer__: We note that extension to two continuous hyperparameters is an interesting question for further investigation. As discussed above, we believe that our work can serve as a strong starting point to attack the high-dimensional scenario.\n\n4. __Question__: \"Compared to Bayesian optimization, do your bounds imply a smaller or larger sample requirement under comparable smoothness assumptions? A discussion would clarify practical relevance.\"\n\n   __Answer__: Great question. Strictly speaking, our results are incomparable with the sample requirement in Bayesian optimization for the following reasons:\n\n      - We give uniform convergence bounds, which imply small generalization error for *any* approach that achieves a small training set error. This includes a bound on the error of the hyperparameter learned by Bayesian optimization even if the assumptions of smoothness and bounded noise needed in the usual analysis of Bayesian optimization do not hold. Our results say if the training sample size is large enough (roughly Pdim/epsilon^2 using our bounds on the pseudo-dimension Pdim), then the test error will be within epsilon of the training error.\n\n    - Bayesian optimization assumes a Gaussian prior and the sample complexity depends on the prior parameters (e.g. bound on variance) as well as kernel hyperparameters, while our results are more worst-case and apply to arbitrary unknown distributions. Our assumptions are more realistic, at least in the case of neural networks with piecewise polynomial activation functions. Also, note that Bayesian optimization requires careful tuning of additional hyperparameters (e.g. kernel and acquisition function design).\n\n   To summarize, our theory complements the known bounds for Bayesian optimization and also applies in broader, more worst-case contexts. We are happy to include this discussion in our paper and thank the reviewer for prompting this comparison.\n\n## Summary\nWe hope that our answers address the reviewer’s concerns, and we are happy to answer any further questions from the reviewer. We respectfully request the reviewer to re-evaluate our work in light of our rebuttal. Many thanks!\n\n## References\n[1] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC dimension bounds for piecewise polynomial networks. NeurIPS’98\n\n[2] G Montúfar, R Pascanu, K Cho, Y Bengio, On the number of linear regions of deep neural networks, NeurIPS’14\n\n[3] PL Bartlett, N Harvey, C Liaw, A Mehrabian, Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks, JMLR’19"}, {"review_id": "R8iHwUSyiL", "reviewer": "Reviewer_uK76", "summary": "This paper introduces a novel theoretical framework to analyze the sample complexity of tuning a single, continuous hyperparameter for deep neural networks in a data-driven, multi-task setting. The central challenge addressed is that the network's performance for a given hyperparameter, $\\alpha$, is defined implicitly through an optimization over the high-dimensional weight parameter, $w$. This makes the utility function, $u_x^*(\\alpha) = \\sup_w f_x(\\alpha, w)$, difficult to analyze directly.\n\nThe authors' main contribution is a new technique that leverages tools from differential and algebraic geometry to bound the learning-theoretic complexity of the utility function class. They show that even if $u_x^*(\\alpha)$ is not a well-behaved function (e.g., not piecewise polynomial), its structural properties can be bounded. Specifically, by bounding the number of discontinuities and local extrema of $u_x^*(\\alpha)$, they can bound its pseudo-dimension. This is achieved by analyzing the geometry of the underlying parameter-dependent dual function, $f_x(\\alpha, w)$. The analysis is presented for two cases: when $f_x(\\alpha, w)$ is piecewise constant and, more generally, when it is piecewise polynomial. These theoretical results are then instantiated to provide sample complexity guarantees for tuning an activation function interpolation parameter and a graph kernel parameter in GNNs.", "questions": "1.  he restriction to a single hyperparameter ($\\alpha \\in \\mathbb{R}$) is the main limitation. The analysis relies on properties of 1D curves and partitioning the real line. Could you elaborate on the fundamental obstacles to extending this to $\\alpha \\in \\mathbb{R}^n$? What would be the high-dimensional analog of \"bounded oscillations\" or the \"monotonic curves\" that are central to your proof? A more detailed discussion on a potential (even if speculative) path forward would greatly strengthen the paper's perceived long-term impact.\n\n2.  The sample complexity bounds (e.g., in Theorem 6.1) have dependencies on network size ($W, L$) and polynomial degrees. Could you comment on whether you believe these bounds are tight or if they are primarily intended to show polynomial learnability? Furthermore, regarding Assumption 1 (ELICQ/ND), could you provide some intuition on why one might expect these to hold (or fail) for a standard architecture like a ResNet with common loss functions? For instance, do symmetries in the network architecture pose a problem for the LICQ condition?\n\n3.  Theorem 5.1 accounts for an approximate-ERM oracle via an additive error term $\\xi$. In practice, the optimization error from GD-based methods might depend on the hyperparameter, i.e., $\\xi = \\xi(\\alpha)$, as $\\alpha$ can affect the difficulty of the optimization landscape. Does your analysis assume $\\xi$ is a constant independent of $\\alpha$? If so, how would the results change if $\\xi$ is a function of $\\alpha$, and what assumptions might be needed on the function $\\xi(\\alpha)$ to retain the guarantees?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n\n1. Addresses the critical and under-theorized problem of hyperparameter tuning in deep learning.\n2. The technical approach is highly novel, applying advanced geometric tools in a creative way to a problem in learning theory. \n3. The work appears technically rigorous and provides a foundational result for a difficult problem.\n\nWeakness:\n\n1. The analysis is restricted to a single hyperparameter, and the path to extending it to multiple hyperparameters is not obvious. \n2. The theory relies on regularity assumptions that may be difficult to verify for large, practical deep learning models. \n3. The paper is very technical and dense, which may limit the reach of its core ideas to a broad audience.", "was_revised": true, "final_justification": "My questions are well addressed and I will keep my score.", "rebuttal": "We thank the reviewer for the very careful and constructive feedback. We appreciate that the reviewer found our technique highly novel and creative, and our results to be foundational for a difficult problem. We address the reviewer’s concerns and questions below.\n\n## Questions\n1. __Question__:\"The fundamental obstacles to extending this to the high-dimensional case? What would be the analog for “bounded oscillations” and the “monotonic curves” that are central to your proof.\"\n\n    __Answer__: We appreciate your deep understanding of our technique and this brilliant question! It is true that “bounded oscillations” and “monotonic curves” are two important recipes of our proofs, and they are the key to generalizing this framework to the high-dimensional case.\n\n     - For “monotonic curves”: a natural analog would be “monotonic hypersurfaces”, which should have this property: for any $\\alpha’ \\in R^N$, there is at most one point $s$ in the monotonic hypersurface $M$ in the space $\\mathcal{A} \\times \\mathcal{W}$ such that its $\\alpha$-coordinate is equal to $\\alpha’$, e.g., $s[\\alpha] = \\alpha’$. For example, the hyperplane $\\alpha_1 = w, \\alpha_2 = 2w$ is an example of monotonic hypersurface in the space $\\mathbb{R}^2 \\times \\mathbb{R}$. We expect the condition of “monotonic hypersurface” would also be $|J_{f, w}(\\alpha, w)|_{(\\alpha, w) = (a, b)} \\neq 0$ when evaluating at any point $(a, b)$ on the monotonic hypersurface $M$ (potentially with some additional conditions), and we also expect the use of the Implicit Function Theorem, similar to “monotonic curves”.\n\n      - For “bounded oscillations”, we also expect a high dimensional extension: given a set of problem instances $x_1, \\dots, x_N$ and real-valued thresholds $r_1, \\dots, r_N$, can we control the number of connected components of a partition in the space $\\mathcal{A}$ such that in each connected component $C$, $(\\text{sign}(u^*_\\alpha(x_1) - r_1)$,...,$\\text{sign}(u_\\alpha(x_N) - r_N))$ is fixed for any $\\alpha \\in C$. To do that, one might want to use some of our tools (e.g. Lemma F.9) as well as some more advanced tools from algebraic and differential geometry (e.g., algebraic projection, stratification, or surgery theory might potentially help), to first analyze the number of connected components formed by the projection of monotonic hypersurfaces on the space $\\mathcal{A} \\times \\mathcal{W}$ onto the space $\\mathcal{A}$, and then analyzing the behavior of $u_x(\\alpha)$ on each component.\n\n   Some of the other tools that we used are already applicable to high-dimensional cases (see e.g., Lemma F.9), and some additional tools have to be developed for the high-dimensional hyperparameter case, but we note that our approach offers concrete ideas and notions to attack that problem. We are happy to incorporate this discussion in the final version.\n\n2. __Question__: \"Could you comment on whether you believe these bounds are tight or if they are primarily intended to show polynomial learnability? Furthermore, regarding Assumption 1 (ELICQ/ND), could you provide some intuition on why one might expect these to hold (or fail) for a standard architecture like a ResNet with common loss functions? For instance, do symmetries in the network architecture pose a problem for the LICQ condition?\".\n\n    __Answer__: This is a great question. Developing lower bounds to determine if our bounds are tight is an interesting question, and the main achievement of the current work is to establish a polynomial upper bound on the sample complexity (which was previously unknown for hyperparameter tuning in neural networks). \n \n     Regarding Assumption 1 (ELICQ/ND), one would expect these conditions to hold almost surely for a random problem instance $x$ (or hold for a very slight perturbation of the problem instance if not the original problem instance $x$, thanks to Sard’s theorem, see Theorem F.15, line 1041 in Appendix). For example, see our Figure 1 ($w \\in \\mathbb{R}^2$), page 6, where we use a random $x$ which dictates the coefficient of $f_x(\\alpha, w)$, and the geometry behaves as expected. We expect that in the very high-dimensional regime, the degenerate case will be even more unlikely to occur, and even if it occurs, a small perturbation on the problem instance $x$ should do the trick (which is a key technique of our proof, relaxing Assumption 3 (very complicated, see line 1268) to Assumption 1 (see from line 1391), and we suspect that a more advanced perturbation analysis can even remove Assumption 1 completely. Also, intuitively, symmetries should actually reduce the complexity of the dual utility function $u_x(\\alpha)$ (e.g. fewer discontinuities and local extrema), even though the proofs are technically more challenging and perturbation analysis seems more technically feasible.\n\n3. __Question__: “In Theorem 5.1, what if the optimization error $\\xi$ depends on $\\alpha$, as $\\alpha$ can affect the difficulty of the optimization? Does your analysis assume $\\xi$ is a constant independent of $\\alpha$? If so, how would the results change if $\\xi$ is a function of $\\alpha$, and what assumptions might be needed on the function $\\xi(\\alpha)$ to retain the guarantee?”\n\n   __Answer__: We assume that the error of the approximate optimizer of the network is upper bounded by $\\xi$ for all $\\alpha$, although it need not be the same for all $\\alpha$. While it seems interesting to try to get a sharper bound in terms of $\\xi(\\alpha)$ instead of a uniform approximation error bound of $\\xi$ for all $\\alpha$, prior work ([1] Theorem 4.9) shows examples indicating the tightness of this analysis.\n\n## Summary\nAgain, we thank the reviewer for the very fruitful discussion. We hope that we have sufficiently addressed the reviewer’s concern, and we are happy to address further questions from the reviewer.\n\n\n## References\n[1] Balcan et al. Refined Bounds for Algorithm Configuration: The Knife-edge of Dual Class Approximability, ICML’20"}, {"review_id": "XCqlkAZHIz", "reviewer": "Reviewer_p5UX", "summary": "This work tackles the challenge of hyperparameter tuning in deep learning by analyzing its sample complexity in a multi-task setting, where tasks are drawn from an unknown distribution. The authors develop a theoretical framework to study the learning complexity of tuning hyperparameters, focusing on utility functions that depend on both hyperparameters and model parameters. By analyzing the structure of the dual utility function—which measures performance under optimal model parameters—they derive bounds on its discontinuities and oscillations using tools from differential geometry, algebraic geometry, and constrained optimization. \n\nTheir key results include sample complexity guarantees for tuning hyperparameters when the underlying parameter-dependent dual function is piecewise constant or piecewise polynomial. They apply these insights to practical settings, such as interpolating between activation functions in neural networks and tuning graph kernel parameters in graph neural networks. Additionally, they relax the assumption of exact optimization, showing their guarantees hold even with approximate empirical risk minimization. The work provides a rigorous foundation for understanding hyperparameter selection in multi-task learning scenarios.", "questions": "1. The piecewise-polynomial assumption for the dual function $f_x(\\alpha, w)$ is central to the theory. Is there any possible empirical studies (even on simple synthetic tasks) that the theoretical results holds for some toy models?\n\n2. (related to weaknesses 2) Could the analysis be extended to multiple hyperparameters? What are the major challenges in such multi-dimensional scenarios.\n\n3. The theoretical guatantee is build on the exact minimizer of the optimization problem (u^*_{x}(\\alpha) = \\sup_{w}f_{x}(w,\\alpha)). However, in practice, optimized with solvers that converge to approximate solutions. I am wondering whether the structural properties (e.g., discontinuities, oscillations of $u_x^*$) are preserved under approximation.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. Theoretical results are technically solid and fine-grained, proofs are well-structured. Although I didn't check every detail of the proofs, the results seem to present no apparent error.\n2. Their results captures good characteristics of the parameter-dependent utility function and its dual functions, and then establishes concrete bounds for learnability of the utility function class. New techniques are developed to support these results. The formalization of this general framework in analysis of hyperparameter tuning is a significant contribution.\n3. This paper is well-written and easy to under stand, presenting complex theoretical concepts in a clear and accessible manner.\n\nWeaknesses:\n\n1. The theoretical result is developed for one-dimensional hyperparameter, whilst real-world tuning often involves many hyperparameters of very different nature (such as learning rates, dropout rates, batch sizes...). Extending the analysis to hyperparameter spaces with larger dimensions remains an open challenge.\n2. I am concerning the applicability of the result in practice. Since the theory is build over the draw of problem instances $S=\\left\\{x_1, \\ldots, x_m\\right\\} \\sim \\mathcal{D}^m$, as most real-world problems occurs to one dataset, without access to multiple independent problem instances for hyperparameter tuning.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reviewing our paper. We appreciate that the reviewer found our paper clear and easy to understand and values our technical contributions. We will address the reviewer’s concerns as follows. \n\n## Questions\n1. __Question__: \"Theoretical is developed for one-dimensional … extending the analysis to high-dimensional hyperparameter spaces remains an open challenge.\"\n\n   __Answer__:  It is true that our results hold for a single scalar hyperparameter. However, we note that this contribution is already novel and requires novel connection between algebraic/differential geometries and learning theory. Moreover, we strongly believe that our techniques can be helpful for future work to attack the high-dimensional hyperparameter case. See below for the concrete example.\n\n2. __Question__: \"The theory is built over the draw of problem instances, while most real-world problems occur in one dataset.\"\n\n    __Answer__: We note that our data-driven framework is designed for a different, and increasingly common, class of problems where the goal is to find hyperparameters that generalize across a distribution of related tasks. In this framework, a “problem instance” can also be interpreted as a task, not necessarily a massive, monolithic dataset, and we may want to learn how to set the best hyperparameter for fine-tuning for a new unseen task. This setting relates to several modern machine learning paradigms, for example:\n\n      - Multi-task learning: this is the most related application. Imagine a scenario where a company wants to build predictive models for hundreds of different clients, each has its own dataset/problem instance $x_i$. Our theory provides guarantees for learning a hyperparameter $\\alpha$ (i.e., weight decay magnitude of NNs), using the datasets of previous clients, for a new client in the future.\n    \n     -  Meta-learning: In meta-learning, the training data itself consists of a large number of small learning tasks. \n\n     - Scientific applications (i.e., GNNs for drug discovery): in this case, a single problem instance is a single graph already. \n  Therefore, though not covering every scenario of machine learning, we strongly believe that our contribution is still valuable for future work. \n\n3. __Question__: The piecewise-polynomial assumption for the dual function fx(α,w) is central to the theory. Is there any possible empirical studies (even on simple synthetic tasks) that the theoretical results holds for some toy models?\n\n   __Answer__: Indeed, the piecewise-polynomial structure of NN outputs is a __very well-known and classical fact in the machine learning literature__ (see e.g., [1,2,3] for examples). This is also the foremost motivation of our analysis. Moreover, __in terms of our results (e.g., Theorem 6.1, H.1, H.2, H.3), we give concrete proofs for the piecewise polynomial structure__, not just assuming that property. For example, we showed the piecewise structure in the following scenarios:\n\n      - Polynomial kernels: E.g., tuning the scaling parameter $\\gamma$ in $k_\\textup{poly}(x_1, x_2) = (\\gamma(x_1 \\cdot x_2) + c_0)^d$.\n\n     -  Interpolating two distance metrics using a polynomial map $k_\\textup{interp}(x_1, x_2) = (\\alpha d_1(x_1, x_2) + (1 - \\alpha)d_2(x_1, x_2) + c_0)^d$.\n\n     - Another example includes tuning the hyperparameter in the parametric ReLU (PReLU) activation function given by $f(x​)= x , \\text{ if } x>0   \\text{ and }  f(x​) = \\alpha x, \\text{ for } x\\le 0$, where $\\alpha$ is a learnable hyperparameter.\n\n   __There are further examples, for which we have concrete proofs (see e.g., Theorem 6.1 (from line 1534), Theorem H.1 (from line 1561), Theorem H.3 (from line 1606)).__\n\n4. __Question__: \"(related to weaknesses 2) Could the analysis be extended to multiple hyperparameters? What are the major challenges in such multi-dimensional scenarios.\"\n\n   __Answer__: We thank the reviewer for asking this question. Though providing analysis on a single hyperparameter, we strongly believe that our technique can serve as a starting point for future works attacking the high-dimensional hyperparameter scenario. As observed by Reviewer uK76, there are two key components in our analysis: bounded oscillations and monotonic curves. To attack the high-dimensional case, one may want to find the analog of those components in such a setting. \n\n      - For “monotonic curves”, a natural analog would be “monotonic hypersurfaces”, which should have this property: for any $\\alpha’ \\in \\mathbb{R}^N$, there is at most one point $s$ in the monotonic hypersurface $M$ in the space $\\mathcal{A} \\times \\mathcal{W}$ such that its $\\alpha$-coordinate is equal to $\\alpha’$, e.g., $s[\\alpha] = \\alpha’$. For example, the hyperplane $\\alpha_1 = w, \\alpha_2 = 2w$ is an example of monotonic hypersurface in the space $\\mathbb{R}^2 \\times \\mathbb{R}$. We expect the condition of “monotonic hypersurface” would also be $J_{f, w}(\\alpha, w)|_{(\\alpha, w) = (a, b)} \\neq 0$ when evaluating at any point $(a, b)$ in monotonic hypersurface $M$ (potentially with some additional conditions), and the extension idea will also base on Implicit Function Theorem, similar to “monotonic curves”.\n\n    - For “bounded oscillations”, we also expect a high dimensional extension: given a set of problem instances $x_1, \\dots, x_N$ and real-valued thresholds $r_1, \\dots, r_N$, can we control the number of connected components of a partition in the space $\\mathcal{A}$ such that in each connected component $C$, $(\\text{sign}(u^*_\\alpha(x_1) - r_1)$,...,$\\text{sign}(u_\\alpha(x_N) - r_N))$ is fixed for any $\\alpha \\in C$. To do that, one might want to use some of our tools (e.g. Lemma F.9) as well as some more advanced tools from algebraic and differential geometry (e.g., algebraic projection, stratification, or surgery theory might potentially help), to first analyze the number of connected components formed by the projection of monotonic hypersurfaces on the space $\\mathcal{A} \\times \\mathcal{W}$ onto the space $\\mathcal{A}$, and then analyzing the behavior of $u_x(\\alpha)$ on each component. \n\n   Some of the other tools that we used are already applicable to high-dimensional cases (see e.g., Lemma F.9), and some additional tools have to be developed for the high-dimensional hyperparameter case, but we note that our approach offers concrete ideas and notions to attack that problem. We are happy to incorporate this discussion in the final version of the paper.\n\n5. __Question__: \"The theoretical guarantee is built on the exact minimizer of the optimization problem (u^{x}(\\alpha) = \\sup{w}f_{x}(w,\\alpha)). However, in practice, optimized with solvers that converge to approximate solutions. I am wondering whether the structural properties (e.g., discontinuities, oscillations of $ u_x^*$) are preserved under approximation.\"\n\n   __Answer__: We thank the reviewer for this insightful question. __Actually, this is exactly what we cover in Section 5__, where we assume that we only have access to an approximate solution $v_\\alpha(x)$ that is close enough to $u^{x}(\\alpha) = \\sup{w}f_{x}(w,\\alpha)$. We note that the underlying structure remains unchanged because the structure of $f_{x}(w,\\alpha)$ is unchanged. What actually changes is the point $w’$ that we use to evaluate the performance of the network — this is $w^*$ that maximizes $f_{x}(w,\\alpha)$ for the exact case $u_x(\\alpha)$, or $\\tilde{w}_\\alpha$ such that $f(\\tilde{w}, \\alpha)$ is close to $u_x(\\alpha)$ for the approximation case (e.g., $w'$ is learned using SGD with momentum).\n\n## Summary\nAgain, we thank the reviewer for the very fruitful discussion. We hope that we have sufficiently addressed the reviewer’s concern, and we are happy to address further questions from the reviewer.\n\n## References\n\n[1] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC dimension bounds for piecewise polynomial networks. NeurIPS’98 \n\n[2] G Montúfar, R Pascanu, K Cho, Y Bengio, On the number of linear regions of deep neural networks, NeurIPS’14\n\n[3] PL Bartlett, N Harvey, C Liaw, A Mehrabian, Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks, JMLR’19"}, {"review_id": "VIFNM0epkD", "reviewer": "Reviewer_x4WD", "summary": "This paper seeks to address a special case for hyperparameter setting wherein one wishes to tune hyperparameters for training in a manner suitable for retaining the same set of hyperparameters throughout a variety of learning tasks/objectives applied to a comparable data corpus. Their method involves tuning (one hyperparameter at a time?) by way of aggregating the tuning into a dual utility function in which they show they can bound the number of discontinuities in a manner that bounds oscillations and a resulting pseudo-randomness of such dual objective function. This helps them to reduce sample complexity. They leave extension of the methods towards a setting with multiple hyperparameters to future work.", "questions": "I found the claim in Related Work section represents this as \"the first work to focus on tuning hyperparameters for deep networks using a data driven lens\" kind of suspect. Can you please clarify what is meant by \"a data driven lens\" in this context and how it significantly differs from prior training conventions?", "limitations": "The limitations to practical applications leveraging multiple hyperparameters are fairly apparent. I am not sure if the claimed contributions, even taken at face value, would be sufficient to compensate for that.", "rating": 3, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\nQuestions surrounding how we could treat functions containing discontinuities as polynomial class are very interesting and of potential relevance to all kind of domains.\n\nWeaknesses:\nIn the context of an AI research conference the idea that a hyperparameter training objective targeting a single variable at a time is possibly kind of laughable, but then I have seen interviews with Turing award winners where they describe spending the majority of their research career trying to iterate on how they train models on MNIST data set, so perhaps it is not that far fetched.", "was_revised": true, "final_justification": "Based on consideration of the author's rebuttal (particular noting that relevant work has been accepted to other conferences) I have reduced my confidence score from 2 to 1 (meaning my review can be considered an educated guess). Apologies that I don't feel qualified to consider the full theoretical scope of your work, but the next time I find an application in industry requiring tuning of a single hyper-parameter I will consider taking another look.", "rebuttal": "We thank the reviewer for the feedback. We appreciate that the reviewer found our work interesting and potentially relevant to all kinds of domains. We address the reviewer's concerns below.\n\n## Questions\n1. __Question__: “The idea that a hyperparameter training objective targeting a single variable at a time is possibly kind of laughable”.\n\n   __Answer__: \n\n     - We note that in machine learning research, __theoretical research is far lagging behind empirical research__. In the context of hyperparameter tuning, it is true that one might tune multiple hyperparameters using arbitrarily fancy rules, provided that the tuned hyperparameters work better in some sense. However, __theoretical analysis for hyperparameter tuning remains an under-explored question__, and __our work is one of the first works attacking this question theoretically in the context of deep learning__, with strong guarantees. __Even for a single hyperparameter case, our results are non-trivial and require lots of advanced tools__ from algebraic/differential geometry. \n\n     - Another example is paper [1], which __provides guarantees for learning just a single multi-head attention layer__ (with very strong data assumptions as well), while nowadays, LLMs typically have dozens (e.g., 80 for Llama 3) of multi-head attention layers (along with other layers) stacked together. Yet, __this paper is still presented at STOC’25, one of the best theory conferences__. That is just __one among many examples that theory in machine learning needs to start with simplified settings__ compared to empirical research, but is still valuable. Understanding simple scenarios is the first and necessary step to advance the understanding of the field, and the questions for learnability and computational efficiency are active areas of research even for a single-layer neural network, or in some case, even a single neuron (our work applies to any number of layers and neurons). __Therefore, we feel that this criticism is a bit harsh and unfair.__ \n\n2. __Question__: \"What is meant by “data-driven lens” and how it significantly differs from prior training conventions.\"\n\n   __Answer__: The data-driven setting assumes that we have to __tune the hyperparameter for multiple related tasks comes from some application-specific task distribution__. Our goal is to tune the hyperparameter so that it performs well for future/unseen tasks that come from such a task distribution. Unlike prior work with theoretical guarantees (e.g. Bayesian Optimization), this learning-theoretic framework enables much stronger guarantees that are distribution-independent (previous work assumes strong priors like Gaussian data and the guarantees depend on the Gaussian variance parameters) and do not need unrealistic smoothness or convexity assumptions on the function that captures the performance of the algorithm as a function of the hyperparameter. __We have discussed the data-driven line of work in Appendix A, as well as describing this setting in detail in the main body (see Section 2, from Line 171).__ We are happy to reiterate this point again in the final version of the paper. \n\n3. __Question__: \"The limitations to practical applications leveraging multiple hyperparameters are fairly apparent. I am not sure if the claimed contributions, even taken at face value, would be sufficient to compensate for that.\"\n\n   __Answer__: \n        - Again, we understand that practically, one might want to tune multiple hyperparameters. However, we want to emphasize again that the __theoretical analysis for the hyperparameter tuning is far lagging behind__. __As agreed by all other reviewers (p5Ux, uK76, and sAc2), our theoretical analysis, even for one single parameter, is a novel contribution and non-trivial__, requiring many advanced tools in algebraic and differential geometry. \n\n      - Moreover, __we strongly believe that our techniques can be helpful for future work to attack the high-dimensional hyperparameter case__. Many of __our key techniques can potentially be generalized and serve as critical components for attacking this case__. As observed by reviewers uK76 and p5uX, there are two key components in our analysis: bounded oscillations and monotonic curves. To attack the high-dimensional case, one may want to find the analog of those components in such a setting. \n         \n     - For “monotonic curves”, a natural analog would be “monotonic hypersurfaces”, which should have this property: for any $\\alpha’ \\in \\mathbb{R}^N$, there is at most one point $s$ in the monotonic hypersurface $M$ in the space $\\mathcal{A} \\times \\mathcal{W}$ such that its $\\alpha$-coordinate is equal to $\\alpha’$, e.g., $s[\\alpha] = \\alpha’$. For example, the hyperplane $\\alpha_1 = w, \\alpha_2 = 2w$ is an example of monotonic hypersurface in the space $\\mathbb{R}^2 \\times \\mathbb{R}$. We expect the condition of “monotonic hypersurface” would also be $J_{f, w}(\\alpha, w)|_{(\\alpha, w) = (a, b)} \\neq 0$ when evaluating at any point $(a, b)$ in monotonic hypersurface $M$ (potentially with some additional conditions), and the extension idea will also base on Implicit Function Theorem, similar to “monotonic curves”.\n\n    - For “bounded oscillations”, we also expect a high dimensional extension: given a set of problem instances $x_1, \\dots, x_N$ and real-valued thresholds $r_1, \\dots, r_N$, can we control the number of connected components of a partition in the space $\\mathcal{A}$ such that in each connected component $C$, $(\\text{sign}(u^*_\\alpha(x_1) - r_1)$,...,$\\text{sign}(u_\\alpha(x_N) - r_N))$ is fixed for any $\\alpha \\in C$. To do that, one might want to use some of our tools (e.g. Lemma F.9) as well as some more advanced tools from algebraic and differential geometry (e.g., algebraic projection, stratification, or surgery theory might potentially help), to first analyze the number of connected components formed by the projection of monotonic hypersurfaces on the space $\\mathcal{A} \\times \\mathcal{W}$ onto the space $\\mathcal{A}$, and then analyzing the behavior of $u_x(\\alpha)$ on each component. \n\n   - Some of the other tools that we used are already applicable to high-dimensional cases (see e.g., Lemma F.9), and some additional tools have to be developed for the high-dimensional hyperparameter case, but we note that our approach offers concrete ideas and notions to attack that problem. We are happy to incorporate this discussion in the final version of the paper.\n\n## Summary\nWe hope that our answers sufficiently address the reviewer’s concerns, and we are happy to answer any further questions. __We respectfully request that the reviewer re-evaluate our work in light of our rebuttal. Many thanks!__\n\n## References\n\n[1] Sitan Chen and Yuanzhi Li, Provably learning a multi-head attention layer, STOC’25"}]

Author rebuttal:

Meta-review: This paper proposes a framework for theoretically analyzing the complexity of hyperparameter tuning in machine learning (e.g., deep learning) settings. They use the so-called dual utility function to derive bounds on the learning complexity using technical tools from differential/algebraic geometry in tandem with optimization. Under the assumption that the underlying parameter-dependent dual function belongs to a certain class (e.g., piecewise polynomial), they are able to give rigorous complexity guarantees.

The strengths of the paper are mostly in its rigorous, original approach to the problem. The setting is quite general as well, since the lower level problem is not required to have a unique solution, in contrast to many works on hyperparameter tuning that take a bilevel optimization perspective. Another strength would be that the paper makes a lot of progress towards bridging the gap between rigorous theory and practical empirics, by allowing for inexact optimization (which allows approximate empirical risk minimization).

The main weakness of the paper has to do with the dimensionality of the hyperparameters - it is assumed that they are one-dimensional. Reviewer x4WD pointed this out as a weakness and the authors responded in the rebuttal that it's very difficult to make progress in this very general setting (i.e., without a unique solution to the lower level problem) and that it might eventually be possible to extend this approach to high-dimensional problems. I agree with Reviewer x4WD that this is a weakness but I also agree with the authors that their work represents nontrivial progress even if it cannot yet handle the high-dimensional case yet.

Since, on the whole, the reviews of the paper were positive and the main criticism, brought by Reviewer x4WD, was sufficiently addressed during the rebuttal period, I recommend accepting the paper.
Decision: Accept (poster)