Search papers, labs, and topics across Lattice.
This paper establishes tight pseudo-dimension bounds for data-driven hyperparameter tuning by refining upper bounds using real algebraic geometry and presenting a multi-regime lower-bound framework. The authors analyze invariant connected sign cells to avoid topological over-counting, leading to sharper sample complexity results. Their findings demonstrate that the derived upper bounds are tightly saturated, providing a more rigorous foundation for understanding the generalization capabilities of hyperparameter tuning methods.
Tightening the bounds on hyperparameter tuning could revolutionize how we approach model optimization in machine learning.
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.
