New Bounds for Multi-Dimensional Hyperparameter Tuning Established

Data-driven algorithm design often treats hyperparameter tuning as a statistical learning problem, yet establishing reliable generalization guarantees has been difficult. This difficulty arises from the complex, non-smooth, and implicit relationship between model performance and hyperparameters. Existing multi-dimensional bounds, which often rely on piecewise-polynomial assumptions, have been criticized for being theoretically loose and lacking comprehensive lower bounds. This research aims to resolve these issues by establishing tight pseudo-dimension bounds for multi-dimensional data-driven tuning. The authors refine the learning-theoretic upper bound by applying real algebraic geometry, specifically analyzing invariant connected sign cells rather than isolated sign vectors. This approach avoids topological over-counting, leading to strictly sharper sample complexities. Furthermore, the paper introduces a multi-regime lower-bound framework that effectively separates combinatorial and algebraic capacities. By constructing shattered problem instances across distinct regimes, the researchers demonstrate that their derived upper bounds are tightly saturated. The framework is also extended to accommodate general bi-level validation-loss tuning and broader semi-algebraic applications, offering a more robust theoretical foundation for hyperparameter optimization.