Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function
This work addresses a foundational gap in statistical theory for automated hyperparameter tuning, which is crucial for machine learning practitioners, though it is incremental in extending existing frameworks to multi-dimensional settings.
The paper tackles the problem of establishing generalization guarantees for multi-dimensional hyperparameter tuning in data-driven algorithm design, which was previously unresolved, and provides a framework that yields sharper and more broadly applicable guarantees, demonstrated with new learnability results for methods like weighted group lasso.
Data-driven algorithm design automates hyperparameter tuning, but its statistical foundations remain limited because model performance can depend on hyperparameters in implicit and highly non-smooth ways. Existing guarantees focus on the simple case of a one-dimensional (scalar) hyperparameter. This leaves the practically important, multi-dimensional hyperparameter tuning setting unresolved. We address this open question by establishing the first general framework for establishing generalization guarantees for tuning multi-dimensional hyperparameters in data-driven settings. Our approach strengthens the generalization guarantee framework for semi-algebraic function classes by exploiting tools from real algebraic geometry, yielding sharper, more broadly applicable guarantees. We then extend the analysis to hyperparameter tuning using the validation loss under minimal assumptions, and derive improved bounds when additional structure is available. Finally, we demonstrate the scope of the framework with new learnability results, including data-driven weighted group lasso and weighted fused lasso.