Research map / Learning theory and algorithms / Sample complexity

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

NeurIPS 2025 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of learning distributions · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formal sample-complexity (pseudo-dimension) analysis of data-driven tuning of a neural-network hyperparameter whose dual utility is piecewise polynomial in hyperparameter and weights, with applications to activation interpolation and GNN graph kernel tuning.

Problem

Learning-theoretic sample complexity of tuning continuous hyperparameters of deep networks when the utility is defined implicitly by an optimization over network weights, which makes the utility volatile and discontinuous in the hyperparameter.

Approach

Bounds discontinuities and local maxima of the dual utility u*(alpha)=max_w f(alpha,w) for piecewise polynomial parameter-dependent duals using algebraic geometry (Bezout, monotonic arcs) and Lagrange multipliers, then converts these oscillation bounds into pseudo-dimension bounds for the utility class.

Key results

• For a single hyperparameter and single polynomial piece of degree Delta_p, the dual utility has O(Delta_p^2) pieces and O(Delta_p^2) oscillations, giving Pdim = O(log Delta_p).
• For piecewise constant pieces with N partition regions, the utility class has Pdim = O(log N) and generalization error O(sqrt(log(N/delta)/m)).
• Applications to activation-function interpolation and GNN kernel tuning are given with sample complexity bounds derived from the framework.

Surprising findings

• The dual utility max_w f(alpha,w) is not in general piecewise polynomial even when f is polynomial (e.g., (2/3)alpha^{3/2}).

Limitations

• Main piecewise-polynomial results are proven only for a single hyperparameter and a single piece; extending to multiple pieces and high-dimensional weights is stated as challenging.
• Relies on regularity assumptions (ELICQ, non-degeneracy) that the authors note may be restrictive.
• Assumes ERM oracle finds global optimum over weights; no empirical experiments reported.

Experimental setup

Metrics: pseudo-dimension sample complexity

Baselines: Bayesian optimization random search Hyperband

Builds on: data-driven algorithm design pseudo-dimension oscillation framework Bezout's theorem

Closest papers by meaning

• Exploring the Complexity of Deep Neural Networks through Functional Equivalence (ICML 2024 · similarity 0.87)
• On the Provable Separation of Scales in Maximal Update Parameterization (ICML 2025 · similarity 0.87)
• Loss Landscape Characterization of Neural Networks without Over-Parametrization (NeurIPS 2024 · similarity 0.86)
• No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths (ICML 2024 · similarity 0.86)
• On the Parameterization of Second-Order Optimization Effective towards the Infinite Width (ICLR 2024 · similarity 0.86)
• Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.86)