Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function

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.

Questions

1. Question: “The idea that a hyperparameter training objective targeting a single variable at a time is possibly kind of laughable”.

   Answer:

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

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

2. Question: "What is meant by “data-driven lens” and how it significantly differs from prior training conventions."

   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.

3. 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."

   Answer: - 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.

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

   • 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”.

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

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

Summary

We 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!

References

[1] Sitan Chen and Yuanzhi Li, Provably learning a multi-head attention layer, STOC’25

We are reaching out to follow up on our response and to check if you have any further questions. In our rebuttal, we addressed your concerns about:

1. We show multiple other scenarios, where theoretical papers presented at highly respected conferences in the field also initiate the theoretical understanding by analyzing very simple scenarios corresponding to important deep learning problems (e.g., studying a single-layer network or even a single neuron). We can provide many examples if requested, and we want to emphasize that, though lagging behind empirical research, theoretical research can also bring insightful views and be helpful for future research.

2. The scope of our results by showing that it is novel and non-trivial, and foremostly, our overall approach can potentially be extended to the high-dimensional case. Furthermore, there are already several interesting single hyperparameters, e.g., in activation functions and graph kernels.

We hope that this resolves the weaknesses outlined in your review and would really appreciate a prompt response for confirmation, or any additional questions or clarifications. Thank you again for your thoughtful feedback.

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.

Questions

1. Question: "Theoretical is developed for one-dimensional … extending the analysis to high-dimensional hyperparameter spaces remains an open challenge."

   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.

2. Question: "The theory is built over the draw of problem instances, while most real-world problems occur in one dataset."

   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:

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

   • Meta-learning: In meta-learning, the training data itself consists of a large number of small learning tasks.

   • Scientific applications (i.e., GNNs for drug discovery): in this case, a single problem instance is a single graph already. Therefore, though not covering every scenario of machine learning, we strongly believe that our contribution is still valuable for future work.

3. 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?

   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:

   • 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$.

   • 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$.

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

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

4. Question: "(related to weaknesses 2) Could the analysis be extended to multiple hyperparameters? What are the major challenges in such multi-dimensional scenarios."

   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.

   • 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”.

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

   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.

5. 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."

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

Summary

Again, 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.

References

[1] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC dimension bounds for piecewise polynomial networks. NeurIPS’98

[2] G Montúfar, R Pascanu, K Cho, Y Bengio, On the number of linear regions of deep neural networks, NeurIPS’14

[3] PL Bartlett, N Harvey, C Liaw, A Mehrabian, Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks, JMLR’19

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.

Questions

1. 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."

   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.

   • 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”.

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

   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.

2. 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?".

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

   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.

3. 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?”

   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.

Summary

Again, 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.

References

[1] Balcan et al. Refined Bounds for Algorithm Configuration: The Knife-edge of Dual Class Approximability, ICML’20

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.

Questions

1. 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."

   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.

2. 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?"

   Answser:

   • 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:

     • 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$ - 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$. - 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. - 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)).

   • 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:

     • 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”.
     • 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.

     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.

3. Question: "How do the bounds scale when extending to two continuous hyperparameters?"

   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.

4. 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."

   Answer: Great question. Strictly speaking, our results are incomparable with the sample requirement in Bayesian optimization for the following reasons:

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

   • 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).

   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.

Summary

We 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!

References

[1] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC dimension bounds for piecewise polynomial networks. NeurIPS’98

[2] G Montúfar, R Pascanu, K Cho, Y Bengio, On the number of linear regions of deep neural networks, NeurIPS’14

[3] PL Bartlett, N Harvey, C Liaw, A Mehrabian, Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks, JMLR’19

We are reaching out to follow up on our response and to check if you have any further questions. In our rebuttal, we addressed your concerns about:

1. core definitions deferred to Appendix, by pointing out that some of the mentioned definitions actually presented formally as well as informally in the main body (ELICQ/ND conditions and their discussion, Page 6), and the rest have been discussed intuitively (monotonic curves, lines 294-295, 308-310),
2. The scope of our results by showing that it is novel and non-trivial, and foremostly, the general idea can potentially be extended to the high-dimensional case.
3. Comparison to the Bayesian optimization (which we already did, see lines 32-45), showing that our result is fundamentally different and is hard to compare with it.

We hope that this resolves the weaknesses outlined in your review and would really appreciate a follow-up response for confirmation, or any additional questions or clarifications. Thank you again for your thoughtful feedback.