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

• URL: http://arxiv.org/abs/2608.17343v1
• Date: Tue, 18 Aug 2026 04:02:51 GMT
• Title: Tight Bounds for Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function
• Abstract summary: We introduce tight pseudo-dimension bounds for multi-dimensional data-driven tuning.<n>By constructing problem instances across distinct sample regimes, we prove our upper bounds are tightly saturated.<n>We extend our framework to accommodate general bi-level validation-loss tuning and broader semi-algebraic applications.
• Score: 18.20955065779317
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Data-driven algorithm design frames hyperparameter tuning as a statistical learning problem, but establishing generalization guarantees remains challenging due to the implicit, non-smooth dependence of model performance on hyperparameters. Existing multi-dimensional bounds under piecewise-polynomial assumptions remain theoretically loose and lack comprehensive lower bounds. We resolve this by establishing tight pseudo-dimension bounds for multi-dimensional data-driven tuning. First, we refine the learning-theoretic upper bound using real algebraic geometry; by analyzing invariant connected sign cells during block elimination rather than isolated sign vectors, we avoid topological over-counting to derive strictly sharper sample complexities. Second, we present a multi-regime lower-bound framework that disentangles combinatorial and algebraic capacities. By constructing shattered problem instances across distinct regimes, we prove our upper bounds are tightly saturated. Finally, we extend our topological framework to accommodate general bi-level validation-loss tuning and broader semi-algebraic applications.

Related papers

• Restricted Dynamic Geometric Complexity: Path-Space Reduction and Möbius--Jacobi Response [0.0]
  We study restricted dynamic geometric complexity as a path-space value problem.<n>The main response result is global on a Hadamard state space.
  arXiv  Detail & Related papers  (2026-07-08T09:36:45Z)
• Pseudospectral Bounds for Transient Amplification in Coupled Gradient Descent [0.0]
  We develop a pseudospectral theory for block-triangular Jacobians.<n>We show that the Kreiss constant satisfies $K(J) leq 2/ (1-) + |C|/(4 (1-))$ when the diagonal blocks are symmetric with spectral radii at most $ 1$.<n>Experiments on linear-quadratic problems, IQC-based comparisons, and neural-network training confirm the theory.
  arXiv  Detail & Related papers  (2026-06-01T20:42:04Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• A Mean Curvature Approach to Boundary Detection: Geometric Insights for Unsupervised Learning [52.452902154360565]
  We introduce Mean Curvature Boundary Points (MCBP), a novel geometric framework grounded in Geometric Machine Learning.<n>MCBP explicitly models the intrinsic curvature of the data manifold and computes pointwise mean curvature without requiring principled manifold parametrization.<n>Experiments on synthetic and real-world datasets demonstrate that MCBP consistently improves clustering performance.
  arXiv  Detail & Related papers  (2026-05-05T20:19:09Z)
• PAC-Bayes Bounds for Gibbs Posteriors via Singular Learning Theory [10.93258787701145]
  We derive explicit non-asymptotic PAC-Bayes generalization bounds for Gibbs posteriors.<n>Unlike classical worst-case complexity bounds based on uniform laws of large numbers, our analysis yields posterior-averaged risk bounds.
  arXiv  Detail & Related papers  (2026-04-19T03:00:18Z)
• Schrödinger bridge for generative AI: Soft-constrained formulation and convergence analysis [6.584866740785309]
  We study the so-called soft-constrained Schr"odinger bridge problem (SCSBP)<n>We prove that as the penalty grows, both the controls and value functions converge to those of the classical SBP at a linear rate.<n>These results provide the first quantitative convergence guarantees for soft-constrained bridges.
  arXiv  Detail & Related papers  (2025-10-13T18:29:15Z)
• On The Sample Complexity Bounds In Bilevel Reinforcement Learning [49.19950489963245]
  Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models.<n>We present the first sample of $mathcalO(epsilon)$ in continuous state-action complexity.<n>Our analysis also extends complexity improving upon existing bounds of $mathcalO(epsilon)$.
  arXiv  Detail & Related papers  (2025-03-22T04:22:04Z)
• A space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraints [8.902244235284229]
  We propose a space-decoupling framework for optimization on bounded-rank matrices.<n>We show that the tangent cone of coupled constraints is the intersection of tangent cones of each constraint.<n>We unveil the equivalence between the reformulated problem and the original problem.
  arXiv  Detail & Related papers  (2025-01-23T16:54:03Z)
• Multi-Grid Tensorized Fourier Neural Operator for High-Resolution PDEs [93.82811501035569]
  We introduce a new data efficient and highly parallelizable operator learning approach with reduced memory requirement and better generalization. MG-TFNO scales to large resolutions by leveraging local and global structures of full-scale, real-world phenomena. We demonstrate superior performance on the turbulent Navier-Stokes equations where we achieve less than half the error with over 150x compression.
  arXiv  Detail & Related papers  (2023-09-29T20:18:52Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.